Phân đoạn ảnh và NCuts

 TẠP CHÍ KHOA HỌC HO CHI MINH CITY UNIVERSITY OF EDUCATION 
 TRƯỜNG ĐẠI HỌC SƯ PHẠM TP HỒ CHÍ MINH JOURNAL OF SCIENCE 
 Tập 18, Số 6 (2021): 1100-1112 Vol. 18, No. 6 (2021): 1100-1112 
 ISSN: 
 2734-9918 Website:  
 Bài báo tổng quan* 
 PHÂN ĐOẠN ẢNH VÀ NCUTS 
 Trần Như Ý1, Nguyễn Viết Hưng2*, Nguyễn Quốc Huy3, Phạm Thế Bảo3 
 1Khoa Công nghệ thông tin, Trường Đại học Công nghiệp Thực phẩm Thành phố Hồ Chí Minh, Việt Nam 
 2Khoa Công nghệ thông tin, Trường Đại học Sư phạm Thành phố Hồ Chí Minh, Việt Nam 
 3Khoa Công nghệ thông tin, Trường Đại học Sài Gòn, Việt Nam 
 *Tác giả liên hệ: Nguyễn Viết Hưng – Email: hungnv@hcmue.edu.vn 
 Ngày nhận bài: 17-4-2021; ngày nhận bài sửa: 13-5-2021;ngày duyệt đăng: 10-6-2021 
TÓM TẮT 
 Trong nhiều thập kỉ qua, nhiều công trình nghiên cứu khoa học đóng góp không ngừng trong 
lĩnh vực thị giác máy tính nói chung cũng như nghiên cứu phân đoạn ảnh nói riêng. Trong đó, phân 
đoạn ảnh là quá trình tiền xử lí quan trọng trong hầu hết các ứng dụng xử lí ảnh. Chúng tôi tóm tắt 
và đánh giá các kĩ thuật phân đoạn ảnh và phân chia các kĩ thuật này thành các nhóm gồm: kĩ thuật 
dựa trên phát hiện cạnh/biên, kĩ thuật phân ngưỡng, phương trình vi phân, phương pháp gom nhóm, 
kĩ thuật dựa trên phân hoạch đồ thị. Tiếp theo, chúng tôi trình bày ưu điểm và khuyết điểm của thuật 
toán Ncuts, là thuật toán kinh điển khá phổ biến trong phân đoạn ảnh dựa trên đồ thị. Thuật toán 
Ncuts (Shi, & Malik, 2000) được đưa ra năm 2000 nhưng đã được áp dụng thành công và cho kết 
quả tối ưu cho nhiều ứng dụng xử lí ảnh cũng như các ứng dụng khoa học kĩ thuật. 
 Từ khóa: eigenvalue; graph-cut; Ncuts 
1. Bài toán phân đoạn ảnh 
 Ảnh số ngày càng trở nên phổ biến và phong phú hơn, đặc biệt là có liên quan đến 
nhiều ứng dụng khoa học kĩ thuật. Ảnh số được xem là một trong những phương tiện quan 
trọng nhất trong việc truyền tải thông tin trong lĩnh vực thị giác máy tính. Việc hiểu các 
thông tin từ ảnh giúp thực hiện được nhiều nhiệm vụ trong các ứng dụng khoa học kĩ thuật 
như xác định các tế bào ung thư trong y khoa, xác định vị trí sân bay từ dữ liệu điều khiển 
cảm biến. Và mục tiêu cần thiết phải xác định các phân vùng hay các đối tượng trong ảnh để 
xử lí hay rút trích thông tin ở mức cao là rất quan trọng trong các quá trình xử lí ảnh và thị 
giác máy tính (Wang, Jensen, & Im, 2010; Wang, Kong, Lu, Qi, & Zhang, 2008; Guo, Ng, 
Goubran, Petersen, Piechnik, Neubauer, & Wright, 2020). 
 Phân đoạn ảnh là quá trình phân chia ảnh thành các vùng không giao nhau hay các đối 
tượng như tập các điểm ảnh, hoặc vùng gồm các điểm ảnh có tính chất tương đồng nhau theo 
một tiêu chuẩn đồng nhất nào đó, ví dụ như màu sắc, cường độ, kết cấu, mức xám để từ 
Cite this article as: Tran Nhu Y, Nguyen Viet Hung, Nguyen Quoc Huy, & Pham The Bao (2021). Image 
Segmentation and Ncuts. Ho Chi Minh City University of Education Journal of Science, 18(6), 1100-1112. 
 1100 
Tạp chí Khoa học Trường ĐHSP TPHCM Trần Như Ý và tgk 
đó xác định vị trí đối tượng và biên trong ảnh (Dass, Priyanka, & Devi, 2012). Đây là một 
trong những nhiệm vụ quan trọng nhất trong phân tích ảnh số tự động vì các kết quả của 
phân đoạn ảnh sẽ có ảnh hưởng cốt yếu đến tất cả các quá trình tiếp theo trong nhiều ứng 
dụng của xử lí ảnh và thị giác máy tính, như biểu diễn và mô tả đối tượng trong ảnh, xử lí 
nhận dạng đối tượng, phân loại ảnh, nén ảnh dựa trên đối tượng hay truy vấn ảnh dựa trên 
nội dung 
 Trong lĩnh vực thị giác máy tính và xử lí ảnh, phân đoạn ảnh là một trong những công 
đoạn quan trọng và được quan tâm nghiên cứu rất nhiều do tính cần thiết trong nhiều ứng 
dụng. Quá trình phân đoạn ảnh số còn có nhiều đóng góp quan trọng trong nhiều lĩnh vực 
(Hoang, & Nguyen, 2018; Almotiri, Elleithy, & Elleithy, 2018; Jain, Prabhakar, Member, & 
Hong, 1999; Chandra, & Bajpai, 2019; Wang, Jensen, & Im, 2010; Wang, Kong, Lu, Qi, & 
Zhang, 2008; Dimauro, & Simone, 2020; Guo, Ng, Goubran, Petersen, Piechnik, Neubauer, 
& Wright, 2020) như y tế, viễn thám, dự báo thời tiết, các bài toán nhận dạng, các bài toán 
giao thông... 
2. Các hướng tiếp cận 
 Việc nghiên cứu phân đoạn ảnh đã có nhiều thành tựu và nhiều kĩ thuật phân đoạn ảnh 
được đưa ra. Tuy nhiên, không có một phương pháp nào là tốt nhất cho các loại ảnh khác 
nhau, cũng như không phải tất cả các phương pháp là tốt nhất cho một loại ảnh đặc trưng 
nào. Vì vậy, việc lựa chọn kĩ thuật phân đoạn ảnh nào đó còn dựa trên tính chất của ảnh và 
vấn đề cần giải quyết. Có nhiều cách để phân loại các kĩ thuật này, theo (Dass, Priyanka, & 
Devi, 2012; Misal, & Singh, 2013; Cheng, Jiang, Sun, & Wang, 2001) các kĩ thuật có thể 
phân loại. 
 a. Hướng tiếp cận phát hiện cạnh/biên 
 Kĩ thuật này dựa trên việc phát hiện các cạnh hay các điểm ảnh giữa các vùng khác 
nhau về mức độ biến đổi cường độ nhằm thành các biên giữa các vùng hay đối tượng 
(Zaitoun, & Aqel, 2015). Hai phương pháp phân đoạn dựa trên cạnh cơ bản là: lược đồ xám 
của ảnh và ... ượng kết nối đến tất cả các đỉnh trong đồ thị, công thức (1). 
 푡( , ) 푡( , ) (1) 
 푡( , ) = + 
 푠푠표 ( , ) 푠푠표 ( , )
 Với 푠푠표 ( , ) = ∑ ∈ ,푣∈ 푤( , 푣) là tổng trọng lượng của các kết nối từ đỉnh trong 
A đến tất cả các đỉnh trong đồ thị. 
 Đặt là vector có | | chiều, đại diện cho các phân vùng của đồ thị trong hai tập A 
và B. Ta có 푖 = 1 nếu đỉnh 푖 thuộc A và 푖 = −1 nếu đỉnh 푖 thuộc B. 푡( ) được định 
nghĩa như 푡( , ). 
 Đặt (푖) = ∑푗(푖, 푗) là tổng các liên kết từ đỉnh 푖 tới tất cả các đỉnh còn lại. 
 ∑ 
Nếu = 푖 ( ) và = 푖>0 푖, công thức (2) (Shi, & Malik, 2000), 
 푖 ∑ 
 푖<0 푖
 1105 
Tạp chí Khoa học Trường ĐHSP TPHCM Tập 18, Số 6 (2021): 1100-1112 
 ( − 푊) (2) 
 min 푡( ) = min 
 Với 푖 ∈ {1, − } và 1 = 0. Gọi là biến được tính theo công thức (3). 
 1 + 1 − (3) 
 = − 
 2 2
 Từ công thức (3), có thể thấy rằng 푖 = 1 nếu đỉnh 푖 thuộc A và 푖 = − nếu đỉnh 푖 
thuộc B. Công thức (2) có thể được tối thiểu hóa bằng cách giải bài toán tìm trị riêng bằng 
phương trình (4). 
 ( − 푊) = 휆 (4) 
 Phương trình (4) có thể được viết lại thành (5). 
 1 1 1
 − − (5) 
 2( − 푊) 2 = 휆 , với = 2 . 
 Một số tính chất: 
 1 1
 − −
 - 2( − 푊) 2 là ma trận các trục đường chéo đối xứng với các giá trị không âm, 
nghĩa là ma trận này có dạng bán xác định dương, vì vậy, ma trận chỉ có các trị riêng dương. 
 1
 - 21 một vector riêng của phương trình (5) với trị riêng là 0. 
 1 1
 − −
 - Vì ma trận 2( − 푊) 2 đối xứng, nên các vector riêng của nó trực giao với nhau. 
 1
 −
Cụ thể vector riêng của phương trình (5) ở trị riêng nhỏ thứ hai phải trực giao với 21 và 
 1
thỏa điều kiện 1 1 = 0 với 1 = 2 1. 
 Theo định lí về Rayleigh quotient (Golub, & Loan, 2013), nếu A là một ma trận đối 
xứng thực, với điều kiện trực giao với 푗 − 1 vector riêng nhỏ nhất 1,  , −1. Thương số 
 được tối thiểu hóa bằng vector tương ứng với trị riêng nhỏ nhất 휆 . 
 푗 푗
 Kết quả thu được công thức (6) và (7). 
 1 1
 − − (6) 
 2( − 푊) 2 
 = . min 
 1 
 0=0 
 Do đó ( −푊) 1 (7) 
 1 = . min và 0 = 21 
 1=0 
 Tập các phần tử có thể được chia thành hai tập con, một tập chứa các phần tử mang 
giá trị dương trong vector riêng và tập còn lại chứa các phần tử có giá trị âm trong vector 
riêng. Cách chia này được lặp lại cho đến khi đặt được số nhóm cần phân đoạn. Nhóm tác 
giả J. Shi (Shi, & Malik, 2000). cho rằng, vector riêng của trị riêng nhỏ nhất thứ hai trong 
phương trình (5) xấp xỉ một lời giải tối ưu của bài toán tối thiểu hóa Ncuts, được mô tả thông 
qua công thức (8). 
 2 (8) 
 ∑푖 ∑푗( (푖) − (푗)) 푤푖푗
 inf 
 2
 1=0 ∑푖 (푖) (푖)
 Cuối cùng, để phân vùng đồ thị, ta có thể đặt một ngưỡng trên vector riêng này để chia 
 1106 
Tạp chí Khoa học Trường ĐHSP TPHCM Trần Như Ý và tgk 
đôi đồ thị và đệ qui theo kiểu two-way-cut (Shi, & Malik, 2000) để đạt kết quả. 
 b. Thực nghiệm 
 Chúng tôi thực nghiệm trên máy tính sử dụng hệ điều hành Windows 10 Pro bản 64bit, 
RAM 8 GB, Chip Intel Core (TM) 5i-3210M CPU @ 2.5GHz. Ngôn ngữ lập trình Matlab 
phiên bản R2016a. 
 Kết quả thực nghiệm các phương pháp Prewitt, Roberts, Sobel, Laplacian of Gaussian, 
Ncuts nhằm phát hiện cạnh/biên đối tượng qua dữ liệu Hình 1, 2, 3, 4 được sử dụng nguồn 
tại (Zaitoun, & Aqel, 2015; Ganesan, & Sajiv, 2017). 
 (a) (b) (c) 
 (d) (e) (f) 
 Hình 1. Kết quả phân đoạn cạnh ảnh võng mạc: (a) ảnh gốc, 
 (b) Prewitt, (c) Roberts, (d) LoG, (e) Sobel, (f) NCuts 
 (a) (b) (c) 
 (d) (e) (f) 
 Hình 2. Kết quả phân đoạn cạnh ảnh cameraman: (a) ảnh gốc, 
 (b) Prewitt, (c) Roberts, (d) LoG, (e) Sobel, (f) NCuts 
 1107 
Tạp chí Khoa học Trường ĐHSP TPHCM Tập 18, Số 6 (2021): 1100-1112 
 (a) (b) (c) 
 (d) (e) (f) 
 Hình 3. Kết quả phân đoạn cạnh ảnh củ quả: (a) ảnh gốc, (b) Prewitt, 
 (c) Roberts, (d) LoG, (e) Sobel, (f) Ncuts 
 (a) (b) (c) 
 (d) (e) (f) 
 Hình 4. Kết quả phân đoạn cạnh ảnh cổng đại học Bharathiar: (a) ảnh gốc, 
 (b) Prewitt, (c) Roberts, (d) LoG, (e) Sobel, (f) NCuts 
 Nhận xét: nhóm Hình 1, 2 dấu hiệu sai khác các đối tượng nhiều trong ảnh phương 
pháp Prewitt, Roberts, Sobel, Laplacian of Gaussian, Ncuts cho kết quả độ chính xác tốt. 
Nhóm Hình 3, 4 độ tương phản giữa các đối tượng sai khác không nhiều trong ảnh thì phương 
pháp Ncuts cho kết quả tốt nhất. 
 c. Ứng dụng 
 Phương pháp Ncuts (Dimauro, & Simone, 2020; Guo, Ng, Goubran, Petersen, 
Piechnik, Neubauer, & Wright, 2020) được sử dụng để tự động phân đoạn kết mạc mí mắt 
 1108 
Tạp chí Khoa học Trường ĐHSP TPHCM Trần Như Ý và tgk 
cho phép chẩn đoán bệnh thiếu máu. Hay trong việc chăm sóc bệnh nhân lâm sàn liên quan 
đến tim mạch bằng ảnh MRI tim. Để tăng cường phân đoạn đa lớp MRI tim bằng cách kết 
hợp các điểm mạnh của CNN và phương pháp Ncuts phân đoạn cấu trúc tim. Ứng dụng 
(Wang, Lin, & Chen, 2019) phương pháp Ncuts để tự động phân đoạn hình ảnh sỏi. Với độ 
chính xác của phân đoạn cạnh so với phương pháp đo thủ công và phương pháp xử lí ảnh 
khác. Ứng dụng này có vai trò quan trọng trong nghiên cứu định lượng về sự phân bố cỡ hạt, 
có ý nghĩa lớn đối với địa chất, thủy văn và sinh thái học. 
4. Kết luận 
 Với ảnh có độ tương phản giữa các đối tượng sai khác không nhiều, thuật toán Ncuts 
cho kết quả tốt hơn so với các phương pháp gồm Prewitt, Roberts, LoG và Sobel. Tuy nhiên, 
thuật toán Ncuts cũng tồn tại những khuyết điểm: 
 - Tập ảnh lớn thuật toán thực thi với tốc độ chậm, mất nhiều thời gian và chiếm nhiều 
bộ nhớ trong tính toán. 
 - Vấn đề tìm số phân vùng cần phân vùng có thể chủ yếu còn dựa vào cảm tính trực 
quan, chưa có cơ sở lí thuyết để áp dụng chung. 
 Chúng tôi nhận thấy quá trình phân đoạn ảnh bằng thuật toán Ncuts có hiệu suất thời gian 
còn thấp; Vì vậy, việc song song hóa thuật toán Ncuts trong quá trình tính toán ma trận sẽ cho 
phép tăng hiệu suất bài toán. Ngoài ra, chúng ta có thể sử dụng 1 số phương pháp gom cụm tìm 
số phân vùng cần phân vùng, thuật toán Ncuts có cơ sở để phân vùng ảnh tốt hơn. 
 ❖ Tuyên bố về quyền lợi: Các tác giả xác nhận hoàn toàn không có xung đột về quyền lợi. 
 TÀI LIỆU THAM KHẢO 
Almotiri, J., Elleithy, K., & Elleithy, A. (2018). Retinal Vessels Segmentation Techniques and 
 Algorithms: A Survey. Applied Science, MDPI, 8(2). 
Bai, X., Zhang, Y., Liu, H., & Chen, Z. (2019). Similarity Measure-Based Possibilistic FCM with 
 Label Information for Brain MRI Segmentation. IEEE Transactions on Cybernetics, 49, 
 2618-2630. 
Bejar, H. H. C., Guimaraes, S. J., & Miranda, P. A. V. (2020). Efficient hierarchical graph 
 partitioning for image segmentation by optimum oriented cuts. Pattern Recognition Letters, 
 131, 185-192. 
Bezdek, J. C. (2013). Pattern Recognition with Fuzzy Objective Function Algorithms. Springer 
 Science & Business Media. 
Chandra, S. K., & Bajpai, M. K. (2019). Mesh free alternate directional implicit method based three 
 dimensional super-diffusive model for benign brain tumor segmentation. Computers & 
 Mathematics with Applications, 77(12), 3212-3223. 
Cheng, H. D., Jiang, X. H., Sun, Y., & Wang, J. L. (2001). Color image segmentation: advances and 
 prospects, Pattern Recognition, 34, 2259-2281. 
 1109 
Tạp chí Khoa học Trường ĐHSP TPHCM Tập 18, Số 6 (2021): 1100-1112 
Chen, Y., Zhang, H., Zheng, Y., Jeon, B., & Wu, Q. M. J. (2016). An improved anisotropic 
 hierarchical fuzzy c-means method based on multivariate student t-distribution for brain MRI 
 segmentation. Pattern Recognition, 60, 778-792. 
Dass, R., Priyanka, & Devi, S. (2012). Image Segmentation Techniques. International Journal on 
 Electronics & Communication Technology, 3(1). 
Dhankhar, P., & Sahu, N. (2013). A Review and Research of Edge Detection Techniques for Image 
 Segmentation. International Journal of Computer Science and Mobile Computing, 2(7), 86-92. 
Ding, Y., & Fu, X. (2016). Kernel-based fuzzy c-means clustering algorithm based on genetic 
 algorithm. Neurocomputing, 188, 233-238. 
Dimauro, G., & Simone, L. (2020). Novel Biased Normalized Cuts Approach for the Automatic 
 Segmentation of the Conjunctiva. MDPI Multidisciplinary Digital Publishing Institute, 9(6). 
Ganesan, P., & Sajiv, G. (2017). A comprehensive study of edge detection for image processing 
 applications. International Conference on Innovations in Information, Embedded and 
 Communication Systems (ICIIECS 2017), 2018, 1-6. 
Golub, G. H. & Loan, C. F. V., (2013). Matrix Computations. John Hopkins University Press. 
Guo, F., Ng, M., Goubran, M., Petersen, S. E., Piechnik, S. K., Neubauer, S., & Wright, G. (2020). 
 Improving cardiac MRI convolutional neural network segmentation on small training datasets 
 and dataset shift: A continuous kernel cut approach. Medical Image Analysis, 61. 
Hawas, A. R., Guo, Y., Du, C., Polat, K., & Ashour, A. S. (2020). OCE-NGC: A neutrosophic graph 
 cut algorithm using optimized clustering estimation algorithm for dermoscopic skin lesion 
 segmentation. Applied Soft Computing, 86. 
Hoang, N. D., & Nguyen, Q. L. (2018). Metaheuristic Optimized Edge Detection for Recognition of 
 Concrete Wall Cracks: A Comparative Study on the Performances of Roberts, Prewitt, Canny, 
 and Sobel Algorithms. Advances in Civil Engineering, 2018. 
Huang, H., Meng, F., Zhou, S., Jiang, F., & Manogaran, G. (2019). Brain Image Segmentation Based 
 on FCM Clustering Algorithm and Rough Set. IEEE Access, 7, 12386-12396. 
Huttenlocher, D. P., & Felzenszwalb, P. F. (2004). Efficient graph based image segmetnation. 
 International Journal of Computer Vision, 59(2), 167-181. 
Jain, A. K., Prabhakar, S., Member, S., & Hong, L. (1999). A Multichannel Approach to Fingerprint 
 Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(4), 348-359. 
Kamil, M. Y., & Salih, A. M. (2019). Mammography Images Segmentation via Fuzzy C-mean and 
 K-mean. International Journal of Intelligent Engineering and Systems, 12(1). 
Khairuzzaman, A. K. M., & Chaudhury, S. (2017). Multilevel thresholding using grey wolf optimizer 
 for image segmentation. Expert Systems with Applications, 86, 64-76. 
Kirti, & Bhatnagar, A. (2017). Image Segmentation Using Canny Edge Detection Technique. 
 International Journal of Techno-Management Research, 4(4). 
Kouhi, A., Seyedarabi, H., & Aghagolzadeh, A. (2020). Robust FCM clustering algorithm with 
 combined spatial constraint and membership matrix local information for brain MRI 
 segmentation. Expert Systems with Applications, 146. 
Luo, S., Tai, X. Ch., Huo, L., Wang, Y., & Glowinski, R. (2019). Convex Shape Prior for Multi-object 
 Segmentation Using a Single Level Set Function. Proceedings of the IEEE/CVF International 
 Conference on Computer Vision (ICCV), 613-621. 
 1110 
Tạp chí Khoa học Trường ĐHSP TPHCM Trần Như Ý và tgk 
Manic, K. S., Priya, R. K., & Rajinikanth, V. (2016). Image Multithresholding based on Kapur/Tsallis 
 Entropy and Firefly Algorithm. Indian Journal of Science and Technology, 9(12). 
Misal, A., & Singh, M. (2013). A survey paper on various visual image segmentation techniques. 
 International Journal of Computer Science and Management Research, 2. 
Ruthotto, L., & Haber, E. (2020). Deep Neural Networks Motivated by Partial Differential Equations. 
 Journal of Mathematical Imaging and Vision, 62, 352-364. 
Senthilkumaran, N. & Rajesh, R. (2009). Edge Detection Techniques for Image Segmentation A 
 Survey of Soft Computing Approaches. International Journal of Recent Trends in 
 Engineering, 1(2). 
Sezgin, M., & Sankur, B. (2004). Survey over image thresholding techniques and quantitative 
 performance evaluation. Journal of Electronic Imaging, 13(1), 146-165. 
Shi, J., & Malik, J. (2000). Normalized cuts and Image Segmentation. Pattern Analysis and Machine 
 Intelligence. IEEE Trans., 22, 888-905. 
Wang, Z., Jensen, J. R., & Im, J. (2010). An automatic region-based image segmentation algorithm 
 for remote sensing applications. Environmental Modelling & Software, 25, 1149-1165. 
Wang, J., Kong, J., Lu, Y., Qi, M., & Zhang, B. (2008). A modified FCM algorithm for MRI brain 
 image segmentation using both local and non-local spatial constraints. Computerized Medical 
 Imaging and Graphics, 8, 685-698. 
Wang, S., & Siskind, J. M. (2001). Image Segmentation with Minimum Mean Cut. IEEE International 
 Conference on Computer Vision (ICCV 2001), 1, 517-524. 
Wang, C., Oda, M., Hayashi, Y., Yoshino, Y., Yamamoto, T., Frangi, A. F., & Mori, K. (2020). Tensor-
 cut: A tensor-based graph-cut blood vessel segmentation method and its application to renal 
 artery segmentation. Medical Image Analysis, 60. 
Wang, S., & Siskind, J. M. (2003). Image Segmentation with Ratio Cut. Pattern Analysis and 
 Machine Intelligence, IEEE Trans., 25(6), 675-690. 
Wang, C., Lin, X., & Chen, C. (2019). Gravel Image Auto-Segmentation Based on an Improved 
 Normalized Cuts Algorithm. Journal of Applied Mathematics and Physics, 7(3). 
Weickert, J. (2001). Efficient image segmentation using partial differential equations and 
 morphology. Pattern Recognition, 34(9), 1813-1824. 
Yang, X., Shen, X., Long, J., & Chen, H. (2012). An Improved Median-based Otsu Image 
 Thresholding Algorithm. AASRI Procedia, 3, 468-473. 
Zaitoun, N. M., & Aqel, M. J. (2015). Survey on Image Segmentation Techniques. International 
 Conference on Communication. Management and Information Technology (ICCMIT 2015), 
 797-806. 
Zhang, L., Zhang, D., & Peng, B. (2013). A survey of graph theoretical approaches to image 
 segmentation. Pattern Recognition, 46(3), 1020-1038. 
Zhu, H., Zhang, J., Xu, G., & Deng, L. (2021). Tensor Field Graph-Cut for Image Segmentation: A 
 Non-Convex Perspective. IEEE Transactions on Circuits and Systems for Video Technology, 
 31(3), 1103-1113. 
 1111 
Tạp chí Khoa học Trường ĐHSP TPHCM Tập 18, Số 6 (2021): 1100-1112 
 IMAGE SEGMENTATION AND NCUTS 
 Tran Nhu Y1, Nguyen Viet Hung2*, Nguyen Quoc Huy3, Pham The Bao3 
 1Faculty of Information Technology, Ho Chi Minh city, University of Food Industry, Vietnam 
 2Faculty of Information Technology, Ho Chi Minh city, University of Education, Vietnam 
 3Faculty of Information Technology, Saigon University, Vietnam 
 *Corresponding author: Nguyen Viet Hung – Email: hungnv@hcmue.edu.vn 
 Received: April 17, 2021; Revised: May 13, 2021; Accepted: June 10, 2021 
ABSTRACT 
 In the past decades, many studies have been conducted in computer vision and image 
segmentation. Image segmentation is the process of image preprocessing in most image processing 
applications. We summarize and evaluate image segmentation techniques and categorize them, 
including edge detection, thresholding, partial differential equation, clustering, and graph-based. 
Next, we present the pros and cons of the Ncuts algorithm, which is typical of graph-based image 
segmentation. The Ncuts algorithm was introduced in 2000 and showed optimal results for image 
processing and other applications. 
 Keywords: eigenvalue; graph-cut; Ncuts 
 1112