基于双重超像素集的快速路径相似度图像分割算法

谭乐怡; 王守觉

doi:doi{10.3724/SP.J.1004.2013.01653

基于双重超像素集的快速路径相似度图像分割算法

doi: doi{10.3724/SP.J.1004.2013.01653

谭乐怡¹,
王守觉^1,2

1.
同济大学电子与信息工程学院上海 200092;
2.
中国科学院苏州纳米所高维仿生信息学与应用实验室苏州 215123

基金项目:

国家自然科学基金(90920013)资助

详细信息

作者简介:
王守觉中国科学院院士.主要研究方向为仿生模式识别,高维信息学.E-mail:shoujuewang@sinano.ac.cn

计量
- 文章访问数: 1342
- HTML全文浏览量: 83
- PDF下载量: 1323
- 被引次数: 0
出版历程
- 收稿日期: 2012-08-16
- 修回日期: 2013-05-07
- 刊出日期: 2013-10-20

A Fast Image Segmentation Based on Path-based Similarity and Dual Super-pixel Sets

TAN Le-Yi¹,
WANG Shou-Jue^1,2

1.
College of Electronics and Information Engineering, Tongji University, Shanghai 200092;
2.
Laboratory of High Dimensional Informatics and Application, Suzhou Institute of Nano-Tech and Nano-Bionics, Chinese Academy of Sciences, Suzhou 215123

Funds:

Support by National Natural Science Foundation of China (90920013)

摘要

摘要: 为克服基于路径相似度计算时间复杂度高以及基于单一过分割区域集的聚类方法容易导致误合并的缺陷, 提出一种结合均值漂移和路径相似度的谱聚类算法. 该算法使用超像素构建基于路径相似度的模型来实现加速. 首先, 利用均值漂移算法对图像进行两次预分割(不同参数), 将这些过分割区域视为两组超像素集合, 构建基于双重过分割区域集的加权图; 之后, 使用各超像素的色彩均值和超像素间存在的交叉像素计算初始相似度, 再利用路径相似度模型得到基于路径的相似度; 最后, 采用Multiway Ncut算法进行聚类. 通过算法自身参数和图结构实验, 测试算法的鲁棒性和稳定性; 通过多幅彩色图片的分割实验, 表明本文的方法在准确性和时效性方面都具有很好的性能.
- 均值漂移 /
- 路径相似度 /
- 谱聚类 /
- 图像分割 /
- Multiway Ncut /
- 半监督聚类
Abstract: Path-based clustering is a recently developed clustering approach that has delivered impressive results in quite a few challenging tasks. However, its extremely high computational complexity limits the application to image segmentation. In this paper, we propose a fast path-based spectral clustering method by defining a dual region-based graphical model for similarity computation. Our method is significantly faster than path-based clustering for considering the over-segmented regions generated from the mean shift algorithm as graph nodes, whose number is much less than that of the image pixels. Besides, taking over-segmented regions as nodes may reduce the sensitivity to noise and outliers. Furthermore, the graphical model combined double segmentations in a principle manner to avoid inappropriate partition which often occurs in a single region-based graphical model. We have performed experiments under both unsupervised and semi-supervised settings, and compared our method with some other methods as well. Experimental results show that our method consistently outperforms other methods due to its great accuracy and lower computational complexity.
- Mean shift /
- path-based similarity /
- spectral clustering /
- image segmentation /
- multiway Ncut /
- semi-supervised learning

HTML全文

参考文献(24)

[1]	Ng A Y, Jordan M I, Weiss Y. On spectral clustering: analysis and an algorithm. In: Proceedings of the 2011 Neural Information Processing System. Vancouver, Canada: NIPS, 2001. 849-856
[2]	Han Shou-Dong, Zhao Yong, Tao Wen-Bing, Sang Nong. Gaussian super-pixel based fast image segmentation using graph cuts. Acta Automatica Sinica, 2011, 37(1): 11-20 (韩守东, 赵勇, 陶文兵, 桑农. 基于高斯超像素的快速Graph Cuts图像分割方法. 自动化学报, 2011, 37(1): 11-20)
[3]	Tao W B, Jin H, Zhang Y M. Color image segmentation based on mean shift and normalized cut. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(5): 1382-1389
[4]	Kohli P, Ladicky L, Torr P H S. Robust higher order potentials for enforcing label consistency. International Journal of Computer Vision, 2009, 82(3): 302-324
[5]	Hoiem D, Efros A A, Hebert M. Geometric context from a single image. In: Proceedings of the 2005 IEEE International Conference on Computer Vision. Atlantic City, USA: IEEE, 2005. 654-661
[6]	Russell B C, Freeman W T, Efros A A, Sivic J, Zisserman A. Using multiple segmentations to discover objects and their extent in image collections. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE, 2006. 1605-1614
[7]	Kim T H, Lee K M, Lee S U. Nonparametric higher-order learning for interactive segmentation. In: Proceedings of the 2010 IEEE International Conference on Computer Vision and Pattern Recognition. Seoul, South Korea: IEEE, 2010. 3201-3208
[8]	Kim T H, Lee K M, Lee S U. Learning full pairwise affinities for spectral segmentation. In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Seoul, South Korea: IEEE, 2010. 2101-2108
[9]	Li Z G, Wu X M, Chang S F. Segmentation using superpixels: a bipartite graph partitioning approach. In: Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA: IEEE, 2012. 789-796
[10]	Wang T H, Collomosse J. Probabilistic motion diffusion of labeling priors for coherent video segmentation. IEEE Transactions on Multimedia, 2012, 14(2): 389-400
[11]	Fischer B, Buhmann J M. Path based pairwise data clustering with application to texture segmentation. Energy Minimization Methods in Computer Vision and Pattern Recognition, 2001, 2134: 235-250
[12]	Fischer B, Buhmann J M. Path-based clustering for grouping of smooth curves and texture segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(4): 513-518
[13]	Fischer B, Buhmann J M. Bagging for path-based clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(11): 1411-1415
[14]	Chang H, Yeung D Y. Robust path-based spectral clustering. Pattern Recognition, 2008, 41(1): 191-203
[15]	Wang F, Zhang C S. Label propagation through linear neighborhoods. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(1): 55-67
[16]	Yu S X, Shi J B. Multiclass spectral clustering. In: Proceedings of the 9th IEEE International Conference on Computer Vision. Nice, France: IEEE, 2003. 313-319
[17]	Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905
[18]	Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619
[19]	Martin D, Fowlkes C, Tal D, Malik J. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of the 8th IEEE International Conference on Computer Vision. Vancouver, BC: IEEE, 2001. 416-423
[20]	Xu Li-Yan, Liu Fu-Chang, Cao Guo, Sun Quan-Sen, Xia　De-Shen. Color image segmentation algorithm based on edgeflow and region merging. Journal of Optoelectronics· Laser, 2011, 22(10): 1581-1587 (徐丽燕, 刘复昌, 曹国, 孙权森, 夏德深. 基于边缘流与区域归并的彩色图像分割方法. 光电子·激光, 2011, 22(10): 1581-1587)
[21]	Cour T, Benezit F, Shi J B. Spectral segmentation with multiscale graph decomposition. In: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Philadelphia, USA: IEEE, 2005. 1124-1131
[22]	Ghanem B, Ahuja N. Dinkelbach NCUT: an efficient framework for solving normalized cuts problems with priors and convex constraints. International Journal of Computer Vision, 2010, 89(1): 40-55
[23]	Li Y, Sun J, Tang C K, Shum H Y. Lazy snapping. ACM Transactions on Graphics, 2004, 23(3): 303-308
[24]	Liu Song-Tao, Ying Fu-Liang. The basic principle and its new advances of image segmentation methods based on graph cuts. Acta Automatica Sinica, 2012, 38(6): 911-922 (刘松涛, 殷福亮. 基于图割的图像分割方法及其新进展. 自动化学报, 2012, 38(6): 911-922)