基于改进Graph Cuts的图像分割
|
摘要
随着计算机视觉和数字图像处理技术的发展,图像分割已成为各种图像处理和图像分析必不可少的步骤。因交互式分割相较于自动分割能达到更准确的结果,已逐渐成为了图像分割中流行的方法。而在交互式分割方法中,Graph Cuts因其全局最优性与快速性,受到了越来越多的关注。本文正是基于改进Graph Cuts的图像分割。
Graph Cuts是一种能够实现全局最优解的交互式分割方法,根据用户提供的前、背景种子点,该算法能够实现图像的后续的自动分割。其最大的特点是克服了传统分割方法容易陷入局部最优的缺点,并且适用于多维图像分割。
超像素(Super Pixel)越来越多地应用于图像处理中。最主要的原因是使用超像素可以有效地减少图像的局部信息冗余,使图像处理的复杂度大大地减少。同时,由于超像素保留的图像的边界信息,使得分割的结果更加准确。传统的Graph Cuts是基于像素水平的,而本文采用基于超像素的Graph Cuts,使得构成图的节点数大大减少,加快了Graph Cuts的运算速度。同时,本文使用了将位置、颜色、形状和纹理特征结合的超像素描述算子,与传统的使用单一特征描述的超像素块相比,能更好的描述超像素的特征,在衡量超像素间的相似度时有更好的表现。
传统的Graph Cuts边界项的设置是基于图像本身的特征差值,使得分割结果的边界易出现在颜色亮度差异大的位置。为此本文提出了基于成对超像素学习的Graph CutS。通过学习的方法衡量两个超像素特征间的相似度函数,将其应用于Graph Cuts的边界项的设置中,为分割正确的目标边界提供更加有效的指导。
With the development of technology of computer vision and digital image processing, image segmentation has becomes vital step of image processing and image analysis.Because interactive segmentation can achieve more accuracy result comparing with automatic method, it becomes more and more popular. And at the same time, Graph Cuts with its excellent behavior in segmentation field, has receives more and more attraction.
Graph Cuts is an interactive segmentation method which can achieve global optimization. With the user assigning foreground and background seeds, it can segment out the object automatically.It can avoid the drawback of local optimization by conventional segmentation.
Recently, Super Pixel has been used in image preprocessing, for that it can capture redundancy in image and greatly reduce the complexity of subsequent image processing tasks, and also for its ability to preserve boundary to make segment results more like an object.So we form a Graph Cuts base on Super Pixel instead of pixel level,which make a great reduce in the number of graph nodes and make the Graph Cuts more efficient. At the same time, we propose to use location, color, texture and shape combining feature to describe the Super Pixel. Comparing single feature descriptor, our method can capture more Super Pixel's information, making it works well in pair Super Pixel likelihood measure.
Conventional Graph cuts'boundary term is determined by the image information itself, the result boundary mainly may appear in the interior of object.So that, we propose a pairwise Super Pixel learning to guide the setting of boundary term.With the supervise learning information,it can guide the Graph cuts to segment right boundary.
Graph Cuts是一种能够实现全局最优解的交互式分割方法,根据用户提供的前、背景种子点,该算法能够实现图像的后续的自动分割。其最大的特点是克服了传统分割方法容易陷入局部最优的缺点,并且适用于多维图像分割。
超像素(Super Pixel)越来越多地应用于图像处理中。最主要的原因是使用超像素可以有效地减少图像的局部信息冗余,使图像处理的复杂度大大地减少。同时,由于超像素保留的图像的边界信息,使得分割的结果更加准确。传统的Graph Cuts是基于像素水平的,而本文采用基于超像素的Graph Cuts,使得构成图的节点数大大减少,加快了Graph Cuts的运算速度。同时,本文使用了将位置、颜色、形状和纹理特征结合的超像素描述算子,与传统的使用单一特征描述的超像素块相比,能更好的描述超像素的特征,在衡量超像素间的相似度时有更好的表现。
传统的Graph Cuts边界项的设置是基于图像本身的特征差值,使得分割结果的边界易出现在颜色亮度差异大的位置。为此本文提出了基于成对超像素学习的Graph CutS。通过学习的方法衡量两个超像素特征间的相似度函数,将其应用于Graph Cuts的边界项的设置中,为分割正确的目标边界提供更加有效的指导。
With the development of technology of computer vision and digital image processing, image segmentation has becomes vital step of image processing and image analysis.Because interactive segmentation can achieve more accuracy result comparing with automatic method, it becomes more and more popular. And at the same time, Graph Cuts with its excellent behavior in segmentation field, has receives more and more attraction.
Graph Cuts is an interactive segmentation method which can achieve global optimization. With the user assigning foreground and background seeds, it can segment out the object automatically.It can avoid the drawback of local optimization by conventional segmentation.
Recently, Super Pixel has been used in image preprocessing, for that it can capture redundancy in image and greatly reduce the complexity of subsequent image processing tasks, and also for its ability to preserve boundary to make segment results more like an object.So we form a Graph Cuts base on Super Pixel instead of pixel level,which make a great reduce in the number of graph nodes and make the Graph Cuts more efficient. At the same time, we propose to use location, color, texture and shape combining feature to describe the Super Pixel. Comparing single feature descriptor, our method can capture more Super Pixel's information, making it works well in pair Super Pixel likelihood measure.
Conventional Graph cuts'boundary term is determined by the image information itself, the result boundary mainly may appear in the interior of object.So that, we propose a pairwise Super Pixel learning to guide the setting of boundary term.With the supervise learning information,it can guide the Graph cuts to segment right boundary.
引文
[1]章毓晋.图象分割[M].北京：科学出版社,2001.
[2]BOYKOV Y, JOLLY M P. Interactive graph cut s for optimal boundary & region segmentation of object s in N-D images[A].IEEE International Conference on Computer Vision and Pattern Recognition[C].2001:731-738.
[3]BOYKOV Y, JOLLY M P. An Experimental Comparison of Min-Cut/Max-Cut Algorithms for Energy Minimization in Computer Vision[J].IEEE Transactions on Pat tern Analysis and Machine Intelligent,2004:1124-1137.
[4]PAWAN K M, PHILIP H S.TORR A, et al."OBJ CUT" [C].2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR'05)2005:18-25
[5]FREEDMAN. D, TAO Z.Interactive Graph Cut Based Segmentation With Shape Prior [C]. Computer Vision and Pattern Recognition,2005,1:755-762.
[6]VU N, MANJUNATH B S.Shape prior segmentation of multiple objects with graph cuts [C].Computer Vision and Pattern Recognition,2008.
[7]ROTHER C, KOLMOGOROV V, BLAKE A. Grabcut-interactive foreground extraction using iterated graph cuts[J].In ACM SIGGRAPH,2004:309-314.
[8]JUSTIN F T, XIAOQIAN. X. Implementing GrabCut[C].Brigham Young University, April,2006.
[9]LI Y, SUN J, TANG C K, et al.Lazy snapping[J].ACM Transactions on Graphics, pp. 303-308,2004.
[10]PRICE B L, MORSE B, COHEN S.Geodesic graph cut for interactive image segmentation [C].In:CVPR,2010.
[11]BAI X, SAPIRO G. A geodesic framework for fast interactive image and video segmentation and matting[C].ICCV,2007,2007:1-8.
[12]Wenxian Yang, Jianfei Cai.User-friendly Interactive Image Segmentation through Undefined Combinatorial User Inputs 2010
[13]FORD L, FULKERSON D. Flows in Networks,Princeton University Press,1962.
[14]ORCHARD M T, BOUMAN C A.Color Quantization of Images[J].IEEE Transactions on Signal Processing 1991,39(12):2677-2690.
[15]SHI J, MALIK J. Normalized cuts and image segmentation[J].PAMI,2000:888-905.
[16]FELZENSZWALB P, HUTTENLOCHER D. Ecient graph-based image segmentation[J].IJCV, 2004:167-181.
[17]VEDALDI A, SOATTO S. Quick shift and kernel methods for mode seeking[C].ECCV, 2008.
[18]RADHAKRISHNA A,SHAJI A,SMITH K,et al.SLIC Superpixels[R].Technical Report 149300, EPFL,June 2010.
[19]SHOTTON J,WINN J M, ROTHER C, CRIMINISI A. TextonBoost:Joint Appearance, Shape and Context Modeling for Multi-Class Object Recognition and Segmentation[C].Proc. European Conf. Computer Vision,2006:1-15.
[20]LIU K,CHENGETAL Y Q. Algebraic Feature Extraetion for Image Reeognition based on Optimal Discriminant Criterion pattern Recognition,1993,26(6):903-911.
[21]TIMO O,MATTI P,Multiresolution Gray-Scale and Rotation Invariant Texture Classification with Local Binary Patterns [J],pattern analysis and machine intelligence,2002,24(7)
[22]DAVID G, LOWE. Object recognition from local scale-invariant features[C]. International conference on Computer Vision. Corfu.Greece.1999(9):1150-1157.
[23]SANDE V D, GEVERS T. SNOEK C G M. Evaluation of Color Descriptors for Object and Scene Recognition [J].Pattern Analysis and Machine Intelligence,2010,32(9).
[24]ANNA B, ANDREW Z,Scene Classification Using a Hybrid Generative/Discriminative Approach[J].Pattern Analysis And Machine Intelligence,2008,30(4).
[25]FULKERSON B, VEDALDI A, SOATTO S.Class Segmentation and Object Localization with Superpixel Neighborhood [C].International Conference of Computer Vision Sept. 2009.
[26]HOIEM D, EFROS A A, HEBERT M. Geometric context from a single image [C].In ICCV, 2005.
[27]LUCCHI A, SMITH K, ACHANTA R, et al.A Fully Automated Approach to Segmentation of Irregularly Shaped Cellular Structures in EM Images[C].International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), Beijing, China,2010.
[28]RONALD L R, ROBERT E S. A new approach to unsupervised learning in deterministic environments [J].In Yves Kodratoff and Ryszard Michalski,editors, Machine Learning:An Artificial Intelligence Approach,volume Ⅲ,Morgan Kaufmann,1990: 670-684.
[29]YOAV F. Boosting a weak learning algorithm by majority [J].Information and Computation,1995,121(2):256--285.
[30]YOAV F, ROBERT E S. Adaptive game playing using multiplicative weights [J].Games and Economic Behavior,1999:79--103.
[31]COLLINS M, SCHAPIRE R, SINGER Y. Logistic regression, adaboost and bregman distances[J].Machine Learning,2002:48(1-3).
[32]ORCHARD M T,BOUMAN C A. Color Quantization of Images [J].IEEE Transactions on Signal Processing,1991,39(12):2677-2690.
[33]SUDHEENDRA V, KRISTEN G. Top-Down Pairwise Potentials for piecing together multi-class segmentation Puzzles[C].CVPR,2010.
[34]MARTIN D, FOWLKES C, MALIK J. Learning to detect natural image boundaries using local brightness, color, and texture cues[J].PAMI,2004,26(5):530-549.
[35]VINCENT L, AND SOILLE P.Watersheds in digital spaces:an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-13,6 (June),1991:583-598.
[36]BLAKE A, ROTHER C, BROWN M, et al.Interactive image segmentation using an adaptive GMMRF model[C].ECCV,2004:428-441.
[37]GELMAN A, CARLIN J, STERN H, et al.Bayesian Data Analysis [C].Chapman and Hall, 1995.
[38]THAYANANTHAN A, STENGER B, TORR P H S,et al.Shape context and chamfer matching in cluttered scenes[C].CVPR,2003:127-133.
[39]STENGER B, THAYANANTHAN A, TORR P H S,et al.Hand pose estimation using heirarchical detection [C].Intl.Workshop on Human-Computer Interaction,2004:105-116.
[40]MOORE A, PRINCE S, WARRELL J, et al.Superpixel lattices [C].CVPR,2008.
[41]MORRONE M, BURR D. Feature Detection in Human Vision:A Phase Dependent Energy Model [J].Royal Soc. of London B,vol.235,1988:221-245.
[42]PERONA P, MALIK J. Detecting and Localizing Edges Composed of Steps[C].Peaks and Roofs. Int'1 Conf. Computer Vision,1990.
[43]PUZICHA J, RUBNER Y, TOMASI C, et al.Empirical Evaluation of Dissimilarity Measures for Color and Texture [C].Proc.Int'l Conf. Computer Vision,1999.
[2]BOYKOV Y, JOLLY M P. Interactive graph cut s for optimal boundary & region segmentation of object s in N-D images[A].IEEE International Conference on Computer Vision and Pattern Recognition[C].2001:731-738.
[3]BOYKOV Y, JOLLY M P. An Experimental Comparison of Min-Cut/Max-Cut Algorithms for Energy Minimization in Computer Vision[J].IEEE Transactions on Pat tern Analysis and Machine Intelligent,2004:1124-1137.
[4]PAWAN K M, PHILIP H S.TORR A, et al."OBJ CUT" [C].2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR'05)2005:18-25
[5]FREEDMAN. D, TAO Z.Interactive Graph Cut Based Segmentation With Shape Prior [C]. Computer Vision and Pattern Recognition,2005,1:755-762.
[6]VU N, MANJUNATH B S.Shape prior segmentation of multiple objects with graph cuts [C].Computer Vision and Pattern Recognition,2008.
[7]ROTHER C, KOLMOGOROV V, BLAKE A. Grabcut-interactive foreground extraction using iterated graph cuts[J].In ACM SIGGRAPH,2004:309-314.
[8]JUSTIN F T, XIAOQIAN. X. Implementing GrabCut[C].Brigham Young University, April,2006.
[9]LI Y, SUN J, TANG C K, et al.Lazy snapping[J].ACM Transactions on Graphics, pp. 303-308,2004.
[10]PRICE B L, MORSE B, COHEN S.Geodesic graph cut for interactive image segmentation [C].In:CVPR,2010.
[11]BAI X, SAPIRO G. A geodesic framework for fast interactive image and video segmentation and matting[C].ICCV,2007,2007:1-8.
[12]Wenxian Yang, Jianfei Cai.User-friendly Interactive Image Segmentation through Undefined Combinatorial User Inputs 2010
[13]FORD L, FULKERSON D. Flows in Networks,Princeton University Press,1962.
[14]ORCHARD M T, BOUMAN C A.Color Quantization of Images[J].IEEE Transactions on Signal Processing 1991,39(12):2677-2690.
[15]SHI J, MALIK J. Normalized cuts and image segmentation[J].PAMI,2000:888-905.
[16]FELZENSZWALB P, HUTTENLOCHER D. Ecient graph-based image segmentation[J].IJCV, 2004:167-181.
[17]VEDALDI A, SOATTO S. Quick shift and kernel methods for mode seeking[C].ECCV, 2008.
[18]RADHAKRISHNA A,SHAJI A,SMITH K,et al.SLIC Superpixels[R].Technical Report 149300, EPFL,June 2010.
[19]SHOTTON J,WINN J M, ROTHER C, CRIMINISI A. TextonBoost:Joint Appearance, Shape and Context Modeling for Multi-Class Object Recognition and Segmentation[C].Proc. European Conf. Computer Vision,2006:1-15.
[20]LIU K,CHENGETAL Y Q. Algebraic Feature Extraetion for Image Reeognition based on Optimal Discriminant Criterion pattern Recognition,1993,26(6):903-911.
[21]TIMO O,MATTI P,Multiresolution Gray-Scale and Rotation Invariant Texture Classification with Local Binary Patterns [J],pattern analysis and machine intelligence,2002,24(7)
[22]DAVID G, LOWE. Object recognition from local scale-invariant features[C]. International conference on Computer Vision. Corfu.Greece.1999(9):1150-1157.
[23]SANDE V D, GEVERS T. SNOEK C G M. Evaluation of Color Descriptors for Object and Scene Recognition [J].Pattern Analysis and Machine Intelligence,2010,32(9).
[24]ANNA B, ANDREW Z,Scene Classification Using a Hybrid Generative/Discriminative Approach[J].Pattern Analysis And Machine Intelligence,2008,30(4).
[25]FULKERSON B, VEDALDI A, SOATTO S.Class Segmentation and Object Localization with Superpixel Neighborhood [C].International Conference of Computer Vision Sept. 2009.
[26]HOIEM D, EFROS A A, HEBERT M. Geometric context from a single image [C].In ICCV, 2005.
[27]LUCCHI A, SMITH K, ACHANTA R, et al.A Fully Automated Approach to Segmentation of Irregularly Shaped Cellular Structures in EM Images[C].International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), Beijing, China,2010.
[28]RONALD L R, ROBERT E S. A new approach to unsupervised learning in deterministic environments [J].In Yves Kodratoff and Ryszard Michalski,editors, Machine Learning:An Artificial Intelligence Approach,volume Ⅲ,Morgan Kaufmann,1990: 670-684.
[29]YOAV F. Boosting a weak learning algorithm by majority [J].Information and Computation,1995,121(2):256--285.
[30]YOAV F, ROBERT E S. Adaptive game playing using multiplicative weights [J].Games and Economic Behavior,1999:79--103.
[31]COLLINS M, SCHAPIRE R, SINGER Y. Logistic regression, adaboost and bregman distances[J].Machine Learning,2002:48(1-3).
[32]ORCHARD M T,BOUMAN C A. Color Quantization of Images [J].IEEE Transactions on Signal Processing,1991,39(12):2677-2690.
[33]SUDHEENDRA V, KRISTEN G. Top-Down Pairwise Potentials for piecing together multi-class segmentation Puzzles[C].CVPR,2010.
[34]MARTIN D, FOWLKES C, MALIK J. Learning to detect natural image boundaries using local brightness, color, and texture cues[J].PAMI,2004,26(5):530-549.
[35]VINCENT L, AND SOILLE P.Watersheds in digital spaces:an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-13,6 (June),1991:583-598.
[36]BLAKE A, ROTHER C, BROWN M, et al.Interactive image segmentation using an adaptive GMMRF model[C].ECCV,2004:428-441.
[37]GELMAN A, CARLIN J, STERN H, et al.Bayesian Data Analysis [C].Chapman and Hall, 1995.
[38]THAYANANTHAN A, STENGER B, TORR P H S,et al.Shape context and chamfer matching in cluttered scenes[C].CVPR,2003:127-133.
[39]STENGER B, THAYANANTHAN A, TORR P H S,et al.Hand pose estimation using heirarchical detection [C].Intl.Workshop on Human-Computer Interaction,2004:105-116.
[40]MOORE A, PRINCE S, WARRELL J, et al.Superpixel lattices [C].CVPR,2008.
[41]MORRONE M, BURR D. Feature Detection in Human Vision:A Phase Dependent Energy Model [J].Royal Soc. of London B,vol.235,1988:221-245.
[42]PERONA P, MALIK J. Detecting and Localizing Edges Composed of Steps[C].Peaks and Roofs. Int'1 Conf. Computer Vision,1990.
[43]PUZICHA J, RUBNER Y, TOMASI C, et al.Empirical Evaluation of Dissimilarity Measures for Color and Texture [C].Proc.Int'l Conf. Computer Vision,1999.