4.基于图论的图像分割

将图论的方法用于图像处理，主要是将图像与图进行映射，利用图的分割方法进行图像分割。

通俗来说，图像映射为图之后，根据采取的准则方法，图像中的前景和背景都转化为了图中的顶点，并且每个顶点之间都被赋予了一定的权值。若将这个图割开来一分为二，当割在前景顶点和背景顶点之间时能得到最小的一个割。GraphCut^[10]采用图论中的最小割（Minimum Cut）来实现分割，并用最大流（Max-flow）来得到这个最小割^[11]。

GraphCut有两个关键步骤：一、构造网络图，网络图中有图像中的N个像素作为顶点，还有一个源点S和一个汇点T，最后希望得到所有前景与源点相连，背景与汇点相连的分割结果。二、是构造能量函数，每一个割对应一个能量函数的值，当割处在前景和背景之间时，能量函数达到最优值。这样对图像的分割问题转化为了利用图论对能量函数进行优化的问题。

在构造网络图中，需要通过用户交互的方式，指定一些像素作为前景和背景（例如在前景和背景上分别划线，选择被覆盖的像素）。然后开始对每个顶点建立连接、并对边赋予权值。每个顶点（除图像边界点外），有2种类型的边，共10条。一类是分别与源点S、汇点T建立的连接叫T-link，剩下的是与周围8邻域顶点建立的连接叫n-link，T-link负责决定一个像素在灰度上是偏向前景多一些还是偏向背景多一些，N-link则考虑像素之间在空间上的邻接关系。

每个像素通过与指定的前景和背景像素的比较，利用灰度相似性的信息，可以确定他们与S和T的连接强弱（权值大小），此时T-link是根据直方图模型来进行建模的。同时根据邻域关系建立的边，把图像分割时的空域信息考虑进去了，这样通过最优化能量函数得出的网络图中的割能从复杂背景中很好的分割出目标。

GrubCut^[12]是另一种基于图论的图像分割方法。其从图像到图的基本映射原理与GraphCut是一样的，区别在于GrubCut的交互方式更简单，只需要用户画一个矩形框，将待分割的目标完整地框起来，算法将自动迭代完成图像的分割。同时与GraphCut的目标和背景的模型是灰度直方图不同，GrabCut取代为RGB三通道的混合高斯模型GMM。

GrubCut的基本方法是，将图像中用户指定的框外的像素全部作为背景，而框内的像素设定为可能前景。通过背景元素和可能的前景元素分别训练前景和背景的混合高斯模型GMM的参数，然后通过这个的混合高斯模型GMM计算网络图中T-link，再根据邻域关系建立N-link，到此网络图构造结束。

根据最小割-最大流的方法，求此GMM模型下的最佳分割，然后，再用分割后的数据再次训练前景和背景的GMM参数，再次计算T-link，并进行求割，如此迭代，因为每次迭代能量都是递减的，所以可以保证收敛，并得到最后的分割结果。

5.基于主动轮廓模型的图像分割

主动轮廓模型（Active Contour Model，ACM）是偏微分方程在图像分割中的应用，由Kass、Witkin和Terzopoulos^[13]等1987年提出来的。这是一种基于能量的图像分割方法，其能量函数为基于曲线的内部能量和基于图像数据外部能量的加权和。通过极小化能量泛函，使得待分割目标周围的一条曲线在固有内力和图像外力的共同作用下不断演化，最终收敛到目标的边界轮廓。活动轮廓模型依据其表达和实现方法不同可分为两种，参数化的Snake及其改进模型和几何形变模型——水平集（LevelSet）。

Snake图像分割的主要思想：

（1）       初始化一条可形变的参数化闭合曲线，将待分割的目标包含在曲线内；

（2）       构造能量方程。以闭合曲线为参数，构造一个包含内能项和外能项两部分能量项的能量方程。内能项：指的是与曲线形状有关的，用于控制轮廓线的弹性形变，起到保持轮廓连续性和平滑性的能量项。外能项：指与图像有关的，用于控制形变终止的能量项。

根据能量方程，计算出表示曲线受力的欧拉方程（因为能量方程极小化是求解泛函极值问题，求解欧拉方程可以得到使泛函取极值的驻函数，将变分问题转化为微分问题），按照曲线各控制点的受力来对曲线进行形变，弹性力使曲线收缩成一个圆，弯曲力使曲线成为光滑曲线或直线，图像力则使曲线向目标轮廓靠拢，当受合力为0，此时的能量方程达到最小值，曲线收敛到分割目标的边缘。

归一化参数曲线表达式：

曲线长度归一化能量方程：

其中称为弹性能量，称为弯曲能量，是图像力能量。

根据图像力的建模方式，除了kass的snake模型，还有Balloons Snakes模型^[14]和GVF Snakes模型^[15]。Balloons模型使用了归一化的外部图像力，对梯度值较小的边缘也能进行较好的分割，同时引入一个膨胀的外部力使曲线不仅能收缩还具有膨胀的行为能力。GVF（Gradient Vector Flow）Snakes将传统Snakes的外部力用扩散方程（Edge Map）进行处理，得到整个图像域的梯度向量场（GradientVector Flow Field）作为外部力，扩大轮廓线的捕获范围，解决了演化曲线无法收敛到图像深度凹陷区域的缺点。

Level Set（水平集）方法^[16]：

根据活动轮廓的表示方法，若采用参数化表示，则是参数化的Snakes模型。若用几何方法进行表示，就是几何活动轮廓模型，即Level Set（水平集）。

水平集方法，是把二维平面的闭合曲线用三维空间连续曲面函数的一个水平层隐式表示。将二维曲线的演化，转化为三维曲面函数的演化。

三维空间的水平集函数，通常根据初始轮廓线，由其符号距离函数（Signed Distance Function，SDF）生成。

其演化的运动表示为：

力F控制着水平集函数曲面的演化，与位置，时间和接触点几何形状有关，通常情况下力F只在曲线位置（零水平层）有意义，因此需要将F扩展到，整个三维函数曲面，称为扩展速度场。为了使轮廓在演化过程中保持光滑连续，F中必须包含常量F₀和基于曲率k的F（k）。另外，还应该加上图像边界信息量K_i，使轮廓靠近目标边界时，F趋于0，演化结束。

F中包含对流项（为演化提供动力）、曲率相关的扩散项（保持轮廓外形光滑）及衰减因子（是轮廓演化到目标边缘停止）。Level Set通过计算时间内，距离函数的演化，将零水平层像素连接起来，并重新计算F，推动函数进一步演化，如此迭代直至分割完成。

其他水平集算法有降低计算复杂度的窄带水平集算法、基于变分的Chan-Vese模型方法。

传统水平集方法用于整个图像范围计算，图像数据为N那么计算复杂度为O(N*N)，窄带水平集算法^[17]，利用将演化过程收缩至以零水平层为中心的一个有限范围内，计算复杂度减小至O(kN)。

Chan-Vese变分的水平集算法^[18]是利用分段常数，对Mumford-Shah模型进行简化，求取分割曲线函数能量最小化，而这里的分割曲线则用水平集的方式隐式表达。采用能量函数表示可以很自然地融入图像的边界信息、区域信息获得较好的分割效果。

6.   总结
简单地介绍了一部分常用的图像分割算法，还有一些如基于聚类的图像分割技术、基于神经网络ANN和一些启发式算法的图像分割技术等没有提到。图像分割算法种类繁多，图像分割技术的应用邻域又非常之广，每种好的算法并不代表在各个邻域都能取得好的效果，需要根据实际情况选用性价比最高的算法。.

7.   参考文献

[1]      龚声蓉, 刘纯平, 季怡. 复杂场景下图像与视频分析[M]. 北京：人民邮电出版社，2013.

[2]      Marr D, Hildreth E. Theory ofedge detection[J]. Proceedings of the Royal Society of London. Series B.Biological Sciences, 1980, 207(1167): 187-217.

[3]      Canny J. A computationalapproach to edge detection[J]. Pattern Analysis and Machine Intelligence, IEEETransactions on, 1986 (6): 679-698.

[4]      Otsu N. A threshold selectionmethod from gray-level histograms[J]. Automatica, 1975, 11(285-296): 23-27.

[5]      Vincent L, Soille P. Watershedsin digital spaces: an efficient algorithm based on immersion simulations[J].IEEE transactions on pattern analysis and machine intelligence, 1991, 13(6):583-598.

[6]      孙小炜, 李言俊, 陈义. Mean Shift 图像分割的快速算法[J]. 测控技术, 2008, 27(7):23-25.

[7]      Fukunaga K, Hostetler L. Theestimation of the gradient of a density function, with applications in patternrecognition[J]. Information Theory, IEEE Transactions on, 1975, 21(1): 32-40.

[8]      Deng Y, Manjunath B S, Shin H.Color image segmentation[C]//Computer Vision and Pattern Recognition, 1999.IEEE Computer Society Conference on. IEEE, 1999, 2.

[9]      Deng Y, Kenney C, Moore M S, etal. Peer group filtering and perceptual color image quantization[C]//Circuitsand Systems, 1999. ISCAS'99. Proceedings of the 1999 IEEE International Symposiumon. IEEE, 1999, 4: 21-24.

[10]  Boykov Y Y, Jolly M P.Interactive graph cuts for optimal boundary & region segmentation ofobjects in ND images[C]//Computer Vision, 2001. ICCV 2001. Proceedings. EighthIEEE International Conference on. IEEE, 2001, 1: 105-112.

[11]  Boykov Y, Kolmogorov V. Anexperimental comparison of min-cut/max-flow algorithms for energy minimizationin vision[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2004, 26(9): 1124-1137.

[12]  Rother C, Kolmogorov V, BlakeA. Grabcut: Interactive foreground extraction using iterated graph cuts[C]//ACMTransactions on Graphics (TOG). ACM, 2004, 23(3): 309-314.

[13]  Kass M, Witkin A, TerzopoulosD. Snakes: Active contour models[J]. International journal of computer vision,1988, 1(4): 321-331.

[14]  Cohen L D, Kimmel R. Globalminimum for active contour models: A minimal path approach[J]. Internationaljournal of computer vision, 1997, 24(1): 57-78.

[15]  Xu C, Prince J L. Snakes,shapes, and gradient vector flow[J]. Image Processing, IEEE Transactions on,1998, 7(3): 359-369.

[16]  Osher S, Sethian J A. Frontspropagating with curvature-dependent speed: algorithms based on Hamilton-Jacobiformulations[J]. Journal of computational physics, 1988, 79(1): 12-49.

[17]  Adalsteinsson D, Sethian J A. Afast level set method for propagating interfaces[J]. Journal of computationalphysics, 1995, 118(2): 269-277.

[18]  Chan T F, Vese L A. Active contours without edges[J].Image processing, IEEE transactions on, 2001, 10(2): 266-277.