基于圖割的圖像分割方法及其新進(jìn)展

劉松濤; 殷福亮

doi:10.3724/SP.J.1004.2012.00911

基于圖割的圖像分割方法及其新進(jìn)展

doi: 10.3724/SP.J.1004.2012.00911

劉松濤^1,2,,
殷福亮¹

1.
大連理工大學(xué)電子信息與電氣工程學(xué)部大連 116024;
2.
海軍大連艦艇學(xué)院信息與通信工程系大連 116018

詳細信息

通訊作者:
劉松濤,海軍大連艦艇學(xué)院信息與通信工程系副教授.大連理工大學(xué)信息與通信工程博士后流動(dòng)站在站博士后.2000年獲得海軍航空工程學(xué)院航空雷達專(zhuān)業(yè)學(xué)士學(xué)位,并分別于2003年和2006年獲得該校信號與信息處理專(zhuān)業(yè)碩士和博士學(xué)位.主要研究方向為圖像處理,成像制導,光電對抗.

計量
- 文章訪(fǎng)問(wèn)數: 3972
- HTML全文瀏覽量: 134
- PDF下載量: 6999
- 被引次數: 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

摘要

摘要: 鑒于圖割的理論意義和實(shí)際應用價(jià)值,系統綜述了基于圖割的圖像分割方法. 首先,深入分析了基于圖割的圖像分割方法的基本原理,主要從定性和定量角度剖析了圖割與能量函數最小化之間的關(guān)系, 然后,概括了基于圖割的圖像分割方法的基本步驟,包括能量函數的設計、圖的構造和最小割/最大流方法, 其次,系統梳理和評述了基于圖割的圖像分割方法的國內外研究現狀,最后,指出了基于圖割的圖像分割方法的發(fā)展方向.
- 圖像分割 /
- 圖割 /
- 能量最小化 /
- 圖論
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 “l(fā)ive-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(陶文兵, 金海. 一種新的基于圖譜理論的圖像閾值分割方法. 計算機學(xué)報, 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(馬秀麗, 焦李成. 基于分水嶺---譜聚類(lèi)的SAR圖像分割. 紅外與毫米波學(xué)報, 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(閆成新, 桑農, 張天序. 基于圖論的圖像分割研究進(jìn)展. 計算機工程與應用, 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(劉嘉, 王宏琦. 一種基于圖割的交互式圖像分割方法. 電子與信息學(xué)報, 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圖像分割方法. 自動(dòng)化學(xué)報, 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(李小斌, 田錚, 劉密歌, 徐海霞. 基于加權割的圖像分割. 電子學(xué)報, 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均值的圖像多尺度分割. 光學(xué)學(xué)報, 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算法. 計算機輔助設計與圖形學(xué)學(xué)報, 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(唐鵬, 高琳, 盛鵬. 基于動(dòng)態(tài)形狀的紅外目標提取算法. 光電子· 激光, 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(劉陳, 李鳳霞, 張艷. 基于圖割與泛形信息的對象分割方法. 計算機輔助設計與圖形學(xué)學(xué)報, 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(李拴強, 馮前進(jìn). 統一計算設備架構并行圖割算法用于肝臟腫瘤圖像分割. 中國生物醫學(xué)工程學(xué)報, 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

相關(guān)文章

施引文獻

資源附件(0)

訪(fǎng)問(wèn)統計