Multilevel and Mean Shift Based Image Segmentation Using Kway-Ncut
TAN Le-Yi1,WANG Shou-Jue1,2
1.School of Electronics and Information Engineering,Tongji University,Shanghai 200092 2.High Dimensional Biomimetic Informatics Applications Laboratory,Suzhou Institute of Nano-Tech and Nano-Bionics,Chinese Academy of Sciences,Suzhou 215123
Abstract：A fast image segmentation algorithm is presented,which can segment large images effectively. The kway-normalized cut(Kway-Ncut) graph partitioning is used as a framework of image segmentation. Firstly,the image is pre-segmented by Mean Shift algorithm. Secondly,both the original image and the pre-segment result are compressed into small scale to achieve acceleration. Thirdly,the pairwise pixel similarity is computed in the low-scale image incorporating the prior knowledge of the pre-segment result and the spatial coherence of pixel. Next,Kway-Ncut is used to partition the graph. Finally,the original pre-segment result is used to recover the details and the boundaries of the segmentation. Besides,the recover method is explained through Bayes rules. The proposed algorithm is applied to segment static images and the results show that the proposed method outperforms other ones due to its lower computational complexity and great accuracy.
谭乐怡，王守觉. 基于多尺度分析和均值漂移的Kway-Ncut算法[J]. 模式识别与人工智能, 2013, 26(4): 328-336.
TAN Le-Yi,WANG Shou-Jue. Multilevel and Mean Shift Based Image Segmentation Using Kway-Ncut. , 2013, 26(4): 328-336.
[1] Cour T,Benezit F,Shi Jianbo. Spectral Segmentation with Multiscale Graph Decomposition // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego,USA,2005,II: 1124-1131 [2] Yu S X,Shi Jianbo. Segmentation Given Partial Grouping Constraints. IEEE Trans on Pattern Analysis and Machine Intelligence,2004,26(2): 173-183 [3] Jia Jianhua,Jiao Licheng. Image Segmentation by Spectral Clustering Algorithm with SpatialCoherence Constraints. Journal of Infrared and Millimeter Waves,2010,29(1): 70-74(in Chinese) (贾建华,焦李成.空间一致性约束谱聚类算法用于图像分割.红外与毫米波学报,2010,29(1): 70-74) [4] Yu S X. Segmentation Using Multiscale Cues // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington,USA,2004,I: 247-254 [5] Lombaert H,Sun Yiyong,Grady L,et al. A Multilevel Banded Graph Cuts Method for Fast Image Segmentation // Proc of the 10th IEEE International Conference on Computer Vision. Beijing,China,2005,I: 259-265 [6] Tao Wenbing,Jin Hai,Zhang Yimin. Color Image Segmentation Based on Mean Shift and Normalized Cut. IEEE Trans on Systems,Man and Cybernetics,2007,37(5): 1382-1389 [7] Xu Liyan,Zhang Jieyu,Sun Quansen,et al. Color Image Segmentation Approach by Combining EFD and Ncut. Pattern Recognition and Artificial Intelligence,2010,23(5): 671-677(in Chinese) (徐丽燕,张洁玉,孙权森,等.结合EFD与Ncut的彩色图像分割办法.模式识别与人工智能,2010,23(5): 671-677) [8] Han Shoudong,Zhao Yong,Tao Wenbing,et al. Gaussian Super-Pixel Based Fast Image Segmentation Using Graph Cuts. Acta Automatica Sinica,2011,37(1): 11-20(in Chinese) (韩守东,赵 勇,陶文兵,等.基于高斯超像素的快速Graph Cuts图像分割方法.自动化学报,2011,37(1): 11-20) [9] Xu Liyan,Liu Fuchang,Cao Guo,et al. Color Image Segmentation Algorithm Based on Edgeflow and Region Merging. Journal of Optoelectronics·Laser,2011,22(10): 1581-1587(in Chinese) (徐丽燕,刘复昌,曹 国,等.基于边缘流与区域归并的彩色图像分割方法.光电子·激光,2011,22(10): 1581-1587) [10] Shi Jianbo,Malik J. Normalized Cuts and Image Segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence,2000,22(8): 888-905 [11] Yu S X,Shi Jianbo. Multiclass Spectral Clustering // Proc of the 9th IEEE International Conference on Computer Vision. Madison,USA,2003,I: 313-319 [12] Comaniciu D,Meer P. Mean Shift: A Robust Approach toward Feature Space Analysis. IEEETrans on Pattern Analysis and Machine Intelligence,2002,24(5): 603-619 [13] Wang Fei,Zhang Changshui. Label Propagation through Linear Neighborhoods. IEEE Trans on Knowledge and Data Engineering,2008,20(1): 55-67 [14] Chang Hong,Yeung D Y. Robust Path-Based Spectral Clustering. Pattern Recognition,2008,41(1): 191-203 [15] Fischer B,Buhmann J M. Path-Based Clustering for Grouping Smooth Curves and TextureSegmentation. IEEE Trans on Pattern Analysis and Machine Intelligence,2003,25(4): 513-518 [16] Kim T H,Lee K M,Lee S V. Nonparametric Higher-Order Learning for Interactive Segmentation // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Seoul,South Korea,2010,VI: 3201-3208 [17] Hiroyuki T,Farsiu S,Milanfar P. Kernel Regression for Image Processing and Reconstruction. IEEE Trans on Image Processing,2007,16(2): 349-366 [18] Felzenszwalb F P,Huttenlocher D P. Efficient Graph-Based Image Segmentation. International Journal of Computer Vision,2004,59(2): 167-181 [19] Martin D R,Fowlkes C,Tal D,et al. A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics // Proc of the IEEE International Conference on Computer Vision. Vancouver, Canada,2001,Ⅱ: 416-423 [20] Hochbaum D S. Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut. IEEE Trans on Pattern Analysis and Machine Intelligence,2010,32(5): 889-898 [21] Zhang Xiangrong,Qian Xiaoxue,Jiao Licheng. Immune Spectral Clustering Algorithm for Image Segmentation. Journal of Software,2010,21(9): 2197-2205(in Chinese) (张向荣,骞晓雪,焦李成.基于免疫谱聚类的图像分割.软件学报,2010,21(9): 2197-2205) [22] Wu Z,Leahy R. An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence,1993,15(11): 1101-1113 [23] Cheng Yizong. MeanShift,Mode Seeking,and Clustering. IEEE Trans on Pattern Analysis and Machine Intelligence,1995,17(8): 790-799 [24] Han Shoudong,Tao Wenbing,Wu Xianglin,et al. Fast Image Segmentation Based on Multilevel Banded Closed-Form Method. Pattern Recognition Letters,2010,31(1): 216-225
2013, Vol. 26 
