基于图割的图像分割方法及其新进展

刘松涛; 殷福亮

doi:10.3724/SP.J.1004.2012.00911

基于图割的图像分割方法及其新进展

doi: 10.3724/SP.J.1004.2012.00911

刘松涛^1,2,,
殷福亮¹

1.
大连理工大学电子信息与电气工程学部大连 116024;
2.
海军大连舰艇学院信息与通信工程系大连 116018

详细信息

通讯作者:
刘松涛,海军大连舰艇学院信息与通信工程系副教授.大连理工大学信息与通信工程博士后流动站在站博士后.2000年获得海军航空工程学院航空雷达专业学士学位,并分别于2003年和2006年获得该校信号与信息处理专业硕士和博士学位.主要研究方向为图像处理,成像制导,光电对抗.

计量
- 文章访问数: 3757
- HTML全文浏览量: 125
- PDF下载量: 6982
- 被引次数: 0
出版历程
- 收稿日期: 2011-03-18
- 修回日期: 2011-07-25
- 刊出日期: 2012-06-20

The Basic Principle and Its New Advances of Image Segmentation Methods Based on Graph Cuts

LIU Song-Tao^{1,2
,},
YIN Fu-Liang¹

1.
Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024;
2.
Department of Information and Communication Engineering, Dalian Naval Academy, Dalian 116018

摘要

摘要: 鉴于图割的理论意义和实际应用价值,系统综述了基于图割的图像分割方法. 首先,深入分析了基于图割的图像分割方法的基本原理,主要从定性和定量角度剖析了图割与能量函数最小化之间的关系, 然后,概括了基于图割的图像分割方法的基本步骤,包括能量函数的设计、图的构造和最小割/最大流方法, 其次,系统梳理和评述了基于图割的图像分割方法的国内外研究现状,最后,指出了基于图割的图像分割方法的发展方向.
- 图像分割 /
- 图割 /
- 能量最小化 /
- 图论
Abstract: In view of the theoretical significance and practical value of graph cuts, the image segmentation methods based on graph cuts are reviewed in this paper. Firstly, the basic principle of image segmentation method based on graph cuts is analyzed in detail, which mainly focuses on the relation between graph cuts and energy minimization involving both qualitative and quantitative analysis. Secondly, the steps of image segmentation methods based on graph cuts are generalized as designing energy function, constructing graph, and minimum cut/maximum flow approaches. Thirdly, the current status of image segmentation methods based on graph cuts is combed and commented. Finally, the future for these segmentation methods is pointed out.
- Image segmentation /
- graph cuts /
- energy minimization /
- graph theory

HTML全文

参考文献(1)

[1]

Pal N R, Pal S K. A review on image segmentation techniques. Pattern Recognition, 1993, 26(9): 1277-1294[2] Veksler O. Efficient Graph-based Energy Minimization Methods in Computer Vision [Ph.D. dissertation], Cornell University, USA, 1999[3] Bhandarkar S M, Zhang H. A comparison of stochastic optimization techniques for image segmentation. International Journal of Intelligent Systems, 2000, 15(5): 441-476[4] Wang J S, Swendsen R H. Cluster Monte Carlo algorithms. Physica A: Statistical Mechanics and Its Applications, 1990, 167(3): 565-578[5] Tu Z W, Zhu S C. Image segmentation by data-driven Markov chain Conte Carlo. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 657-673[6] Barbu A, Zhu S C. Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(8): 1239-1253[7] Martelli A. An application of heuristic search methods to edge and contour detection. Communications of the ACM, 1976, 19(2): 73-83[8] Asano T, Chen D, Katoh N, Tokuyama T. Efficient algorithms for optimization-based image segmentation. International Journal of Computational Geometry and Applications, 2001, 11(2): 145-166[9] Mortensen E, Morse B, Barrett W, Udupa J. Adaptive boundary detection using “live-wire” two-dimensional dynamic programming. In: Proceedings of the Computers in Cardiology. Durham, USA: IEEE, 1992. 635-638[10] Cheng D C, Jiang X. Detections of arterial wall in sonographic artery images using dual dynamic programming. IEEE Transactions on Information Technology in Biomedicine, 2008, 12(6): 792-799[11] 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[12] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11): 1222-1239[13] Zhao H K, Chan T, Merriman B, Osher S. A variational level sets approach to multiphase motion. Journal of Computational Physics, 1996, 127(1): 179-195[14] Caselles V, Catte T, Coll T, Dibos F. A geometric model for active contours in image processing. Numerische Mathematik, 1993, 66(1): 1-31[15] Caselles V, Kimmel R, Sapiro G. Geodesic active contours. International Journal of Computer Vision, 1997, 22(1): 61-79[16] Mumford D, Shah J. Optimal approximation by piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics, 1989, 42(5): 577-685[17] Chan T, Vese L. Active contours without edges. IEEE Transactions on Image Processing, 2001, 10(2): 266-277[18] Paragios N, Deriche R. Geodesic active regions and level set methods for motion estimation and tracking. Computer Vision and Image Understanding, 2005, 97(3): 259-282[19] Besag J. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, 1986, 48(3): 259-302[20] Stuart G, Donald G. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(6): 721-741[21] Besag J. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society, Series B, 1974, 36(2): 192-236[22] Kolmogorov V, Zabin R. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 147-159[23] Boykov Y, Jolly M P. Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In: Proceedings of the 8th IEEE International Conference on Computer Vision. Vancouver, Canada: IEEE, 2001. 105-112[24] Boykov Y, Veksler O. Graph cuts in vision and graphics: theories and applications. Handbook of Mathematical Models in Computer Vision. New York: Springer, 2006. 79-96[25] Cherkassky B V, Goldberg A V. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 1997, 19(4): 390-410[26] Goldberg A V, Tarjan R E. A new approach to the maximum-flow problem. Journal of the ACM, 1988, 35(4): 921-940[27] Ford L, Fulkerson D. Flows in Networks. Princeton: Princeton University Press, 1962[28] Dinic E A. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics-Doklady, 1970, 11(5): 1277-1280[29] Greig D, Porteous B, Seheult A. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 1989, 51(2): 271-279[30] Boykov Y, Jolly M P. Interactive organ segmentation using graph cuts. In: Proceedings of the 3rd International Conference on Medical Image Computing and Computer-Assisted Intervention. Pittsburgh, USA: Springer, 2000. 276-286[31] Blake A, Rother C, Brown M, Perez P, Torr P. Interactive image segmentation using an adaptive GMMRF model. In: Proceedings of the 8th European Conference on Computer Vision. Prague, Czech Republic: Springer, 2004. 428-441[32] Rother C, Kologorov V, Blake A. “GrabCut”: interactive foreground extraction using iterated graph cuts. In: Proceedings of the ACM SIGGRAPH Conference. Los Angeles, USA: ACM, 2004. 309-314[33] Lempitsky V, Kohli P, Rother C, Sharp T. Image segmentation with a bounding box prior. In: Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 277-284[34] Li Y, Sun J, Tang C K, Shum H Y. Lazy snapping. In: Proceedings of the ACM SIGGRAPH Conference. Los Angeles, USA: ACM, 2004. 303-308[35] Bai X, Sapiro G. A geodesic framework for fast interactive image and video segmentation and matting. In: Proceedings of the 11th IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil: IEEE, 2007. 1-8[36] Price B L, Morse B, Cohen S. Geodesic graph cut for interactive image segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA: IEEE, 2010. 3161-3168[37] Das P, Veksler O, Zavadsky V, Boykov Y. Semiautomatic segmentation with compact shape prior. Image and Vision Computing, 2009, 27(1-2): 206-219[38] Bioucas-Dias J, Valadao G. Phase unwrapping via graph cuts. IEEE Transactions on Image Processing, 2007, 16(3): 698-709[39] Suga A, Fukuda K, Takiguchi T, Ariki Y. Object recognition and segmentation using SIFT and graph cuts. In: Proceedings of the 19th International Conference on Pattern Recognition. Tampa, USA: IEEE, 2008. 1-4[40] Tang Z, Miao Z J, Wan Y L, Li J. Automatic foreground extraction for images and videos. In: Proceedings of the 17th IEEE International Conference on Image Processing. Hong Kong, China: IEEE, 2010. 2993-2996[41] Russell C, Restif C, Metaxas D, Torr P. Using the Pn. Potts model with learning methods to segment live cell images. In: Proceedings of the 11th IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil: IEEE, 2007. 1-8[42] Malcolm J, Rathi Y, Tannenbaum A. A graph cut approach to image segmentation in tensor space. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Minnesota, USA: IEEE, 2007. 1-8[43] Malcolm J, Rathi Y, Tannenbaum A. Graph cut segmentation with nonlinear shape priors. In: Proceedings of the IEEE International Conference on Image Processing. San Antonio, USA: IEEE, 2007. 365-368[44] Veksler O. Star shape prior for graph-cut image segmentation. In: Proceedings of the 10th European Conference on Computer Vision. Marseille, France: Springer, 2008. 454-467[45] Wang H, Zhang H. Adaptive shape prior in graph cut segmentation. In: Proceedings of the 17th IEEE International Conference on Image Processing. Hong Kong, China: IEEE, 2010. 3029-3032[46] Liu X Q, Veksler O, Samarabandu J. Order preserving moves for graph-cut-based optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(7): 1182-1196[47] Nowozin S, Lampert C H. Global connectivity potentials for random field models. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 818-825[48] Candemir S, Akgul Y S. Adaptive regularization parameter for graph cut segmentation. In: Proceedings of the 7th International Conference on Image Analysis and Recognition. Povoa de Varzim, Portugal: Springer, 2010. 117-126[49] Rao J, Abugharbieh R, Hamarneh G. Adaptive regularization for image segmentation using local image curvature cues. In: Proceedings of the 11th European Conference on Computer Vision. Crete, Greece: Springer, 2010. 651-665[50] Le T H, Jung S W, Choi K S, Ko S J. Image segmentation based on modified graph-cut algorithm. Electronics Letters, 2010, 46(16): 1121-1122[51] Komodakis N, Tziritas G. Approximate labeling via graph cuts based on linear programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(8): 1436-1453[52] Alahari K, Kohli P, Torr P H S. Dynamic hybrid algorithms for MAP inference in discrete MRFs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1846-1857[53] Lempitsky V, Rother C, Roth S, Blake A. Fusion moves for Markov random field optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(8): 1392-1405[54] Veksler O. Multi-label moves for MRFs with truncated convex priors. In: Proceedings of the 7th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition. Bonn, German: Springer, 2009. 1-13[55] Feng W, Jia J Y, Liu Z Q. Self-validated labeling of Markov random fields for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1871-1887[56] Kolmogorov V, Rother C. Minimizing nonsubmodular functions with graph cuts --- a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(7): 1274-1279[57] Ishikawa H. Higher-order clique reduction in binary graph cut. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 2993-3000[58] Ishikawa H. Transformation of general binary MRF minimization to the first-order case. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(6): 1234-1249[59] Ishikawa H. Higher-order gradient descent by fusion-move graph cut. In: Proceedings of the 20th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 568-574[60] Ning J F, Zhang L, Zhang D, Wu C K. Interactive image segmentation by maximal similarity based region merging. Pattern Recognition, 2010, 43(2): 445-456[61] Alper A, Stefano S. Motion segmentation with occlusions on the superpixel graph. In: Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 727-734[62] Lombaert H, Sun Y, Grady L, Xu C Y. A multilevel banded graph cuts method for fast image segmentation. In: Proceedings of the 10th IEEE International Conference on Computer Vision. Beijing, China: IEEE, 2005. 259-265[63] Strandmark P, Kahl F. Parallel and distributed graph cuts by dual decomposition. In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA: IEEE, 2010. 2085-2092[64] Kohli P, Torr P H S. Dynamic graph cuts for efficient inference in markov random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(12): 2079-2088[65] Juan O, Boykov Y. Active graph cuts. In: Proceedings of the IEEE Conputer Society Conference on Computer Vision and Pattern Recognition. New York, USA: IEEE, 2006. 1023-1029[66] Huang Y C, Liu Q S, Metaxas D. Video object segmentation by hypergraph cut. In: Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 1738-1745[67] Chung C Y, Chen H H. Video object extraction via MRF-based contour tracking. IEEE Transactions on Circuits and Systems for Video Technology, 2010, 20(1): 149-155[68] Wang T H, Guillemaut J Y, Collomosse J. Multi-label propagation for coherent video segmentation and artistic stylization. In: Proceedings of the 17th IEEE International Conference on Image Processing. Hong Kong, China: IEEE, 2010. 3005-3008[69] Tao Wen-Bing, Jin Hai. A new image thresholding method based on graph spectral theory. Chinese Journal of Computers, 2007, 30(1): 110-119(陶文兵, 金海. 一种新的基于图谱理论的图像阈值分割方法. 计算机学报, 2007, 30(1): 110-119)[70] Ma Xiu-Li, Jiao Li-Cheng. SAR image segmentation based on watershed and spectral clustering. Journal of Infrared and Millimeter Waves, 2008, 27(6): 452-456(马秀丽, 焦李成. 基于分水岭---谱聚类的SAR图像分割. 红外与毫米波学报, 2008, 27(6): 452-456)[71] Yan Cheng-Xin, Sang Nong, Zhang Tian-Xu. Survey on graph theory based image segmentation technique. Computer Engineering and Applications, 2006, 42(5): 11-14(闫成新, 桑农, 张天序. 基于图论的图像分割研究进展. 计算机工程与应用, 2006, 42(5): 11-14)[72] Liu Jia, Wang Hong-Qi. A graph cuts based interactive image segmentation method. Journal of Electronics and Information Technology, 2008, 30(8): 1973-1976(刘嘉, 王宏琦. 一种基于图割的交互式图像分割方法. 电子与信息学报, 2008, 30(8): 1973-1976)[73] 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)[74] Han S D, Tao W B, Wu X L, Tai X C, Wang T J. Fast image segmentation based on multilevel banded closed-form method. Pattern Recognition Letters, 2010, 31(3): 216-225[75] Li Xiao-Bin, Tian Zheng, Liu Mi-Ge, Xu Hai-Xia. Weighted cut based image segmentation. Acta Electronica Sinica, 2008, 36(1): 76-80(李小斌, 田铮, 刘密歌, 徐海霞. 基于加权割的图像分割. 电子学报, 2008, 36(1): 76-80)[76] Li Yu-Chuan, Tian Zheng. Multiscale image segmentation based on graph weighted kernel K-means. Acta Optica Sinica, 2009, 29(10): 2762-2767(李昱川, 田铮. 基于图的加权核K均值的图像多尺度分割. 光学学报, 2009, 29(10): 2762-2767)[77] Zheng Jia-Ming, Chen Zhao-Jiong. Connectivity constrained graph-cut for fast interactive image segmentation. Journal of Computer-Aided Design and Computer Graphics, 2011, 23(3): 399-405(郑加明, 陈昭炯. 带连通性约束的快速交互式Graph-Cut算法. 计算机辅助设计与图形学学报, 2011, 23(3): 399-405)[78] Tang Peng, Gao Lin, Sheng Peng. A novel dynamic shape based infrared object subtraction method. Journal of Optoelectronics · Laser, 2009, 20(8): 1049-1052(唐鹏, 高琳, 盛鹏. 基于动态形状的红外目标提取算法. 光电子· 激光, 2009, 20(8): 1049-1052)[79] Liu Chen, Li Feng-Xia, Zhang Yan. An interactive object cutout algorithm based on graph-cut and generalized shape prior. Journal of Computer-Aided Design and Computer Graphics, 2009, 21(12): 1753-1760(刘陈, 李凤霞, 张艳. 基于图割与泛形信息的对象分割方法. 计算机辅助设计与图形学学报, 2009, 21(12): 1753-1760)[80] Li Shuan-Qiang, Feng Qian-Jin. Liver tumor segmentation using graph cuts based on CUDA. Chinese Journal of Biomedical Engineering, 2010, 29(5): 641-647(李拴强, 冯前进. 统一计算设备架构并行图割算法用于肝脏肿瘤图像分割. 中国生物医学工程学报, 2010, 29(5): 641-647)[81] Jiang T T, Jurie F, Schmid C. Learning shape prior models for object matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 848-855[82] Campbell N, Vogiatzis G, Hernandez C, Cipolla R. Automatic 3D object segmentation in multiple views using volumetric graph-cuts. In: Proceedings of the British Machine Vision Conference. Warwick, UK: BMVA, 2007. 530-539[83] Zhang Q, Ngan K N. Multi-view video based multiple objects segmentation using graph cut and spatiotemporal projections. Journal of Visual Communication and Image Representation, 2010, 21(5-6): 453-461[84] Tan S, Kakadiaris I A. Kernel active contour. In: Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 521-528[85] El-Zehiry N, Sahoo P, Elmaghraby A. Combinatorial optimization of the piecewise constant Mumford-Shah functional with application to scalar/vector valued and volumetric image segmentation. Image and Vision Computing, 2011, 29(6): 365-381[86] Olsson C, Byrod M, Overgaard N C, Kahl F. Extending continuous cuts: anisotropic metrics and expansion moves. In: Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan: IEEE, 2009. 405-412

施引文献

资源附件(0)

访问统计