牛文斐，汪西莉

陕西师范大学 计算机科学学院，西安 710062

图像分割是利用图像的某些特性，如灰度、颜色、纹理、形状等信息将图像划分成若干个独立的有意义的连续区域或对象，在每个区域内部具有同质的特性。图像的分割结果直接影响到后期的图像分析理解。利用图割理论进行图像分割是近年来基于能量最小化框架的一个研究热点。该理论的新颖之处在于它的全局最优求解能力及结合多种知识的统一图像分割框架。1989年，Greig等人[1]为了验证模拟退火算法解决全局优化问题的不足，首次将图割理论引入计算机视觉领域。2001年，Boykov和Jolly[2]首次提出了基于图割的图像分割方法Interactive Graph Cuts，它有着获取全局最优解以及融合多种先验知识的能力，奠定了运用图割理论进行图像分割的基本架构。

传统的图割方法对简单图像的分割是成功的，但是对于含有噪声或遮挡物的复杂图像的分割效果并不好。针对该缺陷，本文提出以图割算法为基础，增加形状先验知识，运用形状先验信息和组合图割优化的方法进行图像分割，可以有效改善这些问题。

1 基于图割的图像分割

1.1 图割理论

图割是一种基于图论的组合优化方法，它将一幅图像映射成一个网络图，其中像素点对应图中的节点，相邻像素点之间的关系对应图中节点之间边，并建立关于标号的能量函数，割的容量对应能量函数。运用最大流/最小割算法对网络图进行切割，得到网络图的最小割，即对应于待分割的目标边界。

1.2 图割方法解决图像分割的一般框架

（1）构造能量函数，从而将分割问题转化为能量函数最小化问题，该能量函数反映了图像分割结果的好坏。

（2）根据图像构造s-t网络图，这个图将能量函数视为其中边的集合，使能量与网络图的割相对应，从而将能量最小化问题转化为求网络图最小割问题。

（3）根据最大流/最小割定理，将网络图最小割问题转化为最大流问题。

（4）求得网络图的最大流，即对应着图的最小割，从而得到能量函数的全局最优解，最终得到图像分割结果[4]。

图割理论的核心思想是构造一个能量函数，能量函数一般由两项组成[5]：

其中，数据项Edata(f)用来衡量像素p所分配的标号fp与观察到的数据不一致性；光滑项Esmooth(f)用于约束邻接像素间具有一致视差，它体现了区域内部的连续性和边界的不连续性。不同的能量函数对应网络图中的边所赋权值的方法是不同的，但能量函数最终是解决标号问题的。运用图割算法求解能得到该能量函数的全局最优解。

2 基于形状先验和图割的图像分割

传统图割方法可以获取全局最优解或者是带有很强特征的局部最优解，但是对含有噪声或遮挡物等复杂图像，算法会受图像中噪声、遮挡等的影响，分割得到的目标不完整或者包含一些杂质。而目前提出的很多在已有算法中加入形状先验的思想，使算法包含更多约束信息，限制了感兴趣区域的搜寻空间，从而更好地分割出完整目标。如Slabaugh[6]等提出了基于椭圆形状先验和图割的图像分割方法；Veksler[7]提出一种融合星形形状先验到图割算法中的图像分割方法。引入形状先验的思想，关键要考虑如何将形状先验惩罚添加到传统图割算法中，从而进行有效的分割。形状先验模板可以选用一个简单的模板，也可以选用多个形状先验模板的训练集，后者更为灵活，适用于变形的形状，但计算是复杂而耗时的。因此本文在图割算法的基础上，加入了简单的形状先验知识，有效提高了图割的分割精度，使图割方法更具有鲁棒性。若给定形状先验模板与待分割目标存在平移、旋转、尺度缩放等刚性变换，则运用（Scale Invariant Feature Transform，SIFT）算法进行特征匹配，通过仿射变换将给定模板与分割目标进行对齐，解决形状先验模板与待分割目标存在的仿射不同，使该算法更灵活。

2.1 形状先验模型

首先定义形状先验能量，根据文献[8]中提到的运用Chan和Zhu[9]提出的形状距离的描述形式，将形状先验能量通过终端边缘权值合并到图中。该方法中的形状距离是对称的，而且遵循了三角不等式，其使用的形状模板是和待分割目标相同的二值形状模板。

对于给定的一个形状模板φ0，定义二值标签f的能量：

由上述思想可以得到，形状先验惩罚为：

其中f表示未含形状先验得到的分类标记，φ0表示已知的二值形状模板。

加入形状惩罚的思想：如果分类得到的标记模板和已知形状的二值模板在某点的标记不一致，如p点的标记fp=0，而模板=1，或p点的标记fp=1，而模板=0，则表示分割有误，需要加入形状惩罚1；如果分割得到的标记模板和已知二值模板的像素点的标记一致，则形状惩罚为0，即不需要加入任何惩罚。

2.2 模板仿射变换

如果给定的二值形状模板和分类得到的标记模板不完全相同，存在平移、旋转、尺度缩放等差异，则需要将两个形状通过仿射变换进行配准。通过仿射变换实现图像配准有多种方法，比如归一化算法[10]、梯度下降法[11]等，但归一化算法是根据图像矩来求解的，对于含有阴影等杂质的模板处理效果不好，往往得不到正确的形式；梯度下降法求解容易陷入局部最优，找不到最优解。本文运用SIFT特征匹配算法[12]，SIFT由Lowe于1999年提出，2004年完善总结，其匹配能力较强，可以处理两幅图像之间发生平移、旋转、尺度缩放等情况下的匹配问题。SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置、尺度、旋转不变量。极值点是一些十分突出的点，比如角点、边缘点、暗区域的亮点以及亮区域的暗点，如果两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，则这些点之间会有相互对应的匹配点。

根据正确匹配的特征点，运用仿射变换公式求得变换参数，从而使两幅图像正确匹配。

2.3 本文方法

2.3.1 算法设计

本文算法的思想：首先建立关于标号的能量函数EA(f)，利用图割方法最小化该能量函数求得最优解，从而得到初始分割结果。在此基础上，运用上述提到的添加形状先验的思想，在能量函数中添加形状项，构成新的能量函数，通过终端边缘权值将形状惩罚合并到图中，运用图割算法求得最终分割结果。

算法流程为：

步骤1首先选取一幅彩色图像，对图像构造s-t网络图，建立关于此标号的能量函数EA(f)，根据定义好的能量函数，确定图的边缘之间的权值。

步骤2在该网络图上运用最大流/最小割算法求得图的最大流，即对应着最小割，从而得到初始的图像分割结果。

步骤3在上述算法的基础上，结合添加形状先验的思想，定义形状先验能量，在能量函数中添加形状项，构成新的能量函数E(f)，然后把这些形状能量通过终端边缘权值合并到图中。

步骤4运用图割方法进行分割，得到加入形状以后的图像分割结果。

2.3.2 能量函数的定义

算法步骤1和步骤3是建立关于标号的能量函数，本文选择的能量函数形式为：

该能量函数包括两项：第一项是基于图像信息的能量项；第二项是形状能量项。算法步骤1中建立的是基于图像的能量函数，对应式（4）的第一项，这一项是基于图像信息的，包含数据项和平滑项；算法步骤3建立的能量函数如式（4）所示，包括两项。

能量函数中第一项E(A)采用文献[2]定义的形式：

其中R(A)是数据项，B(A)是平滑项；系数λ≥0表示了区域项R(A)和边界项B(A)的相对重要性。数据项和平滑项的定义如下：

式（6）中R(A)表示像素p属于背景或者目标的概率的代价。式（9）中系数B{p，q}≥0表示像素p和q之间的不相似性的代价，δ(Ap，Aq)表示像素点标号的值，式（11）中Ip和Iq表示像素点的值。算法中，数据项选用高斯模型来建模，采用K均值算法。将图像像素点聚为两类，得到样本的标记并计算每类的均值和协方差，从而估计得到参数进行建模。

能量函数中第二项形状项ES(f)采用2.1节描述来定义。如果给定的形状模板经过了仿射变换，则采用2.2节的思想来定义。

3 实验结果与分析

运用上述方法对彩色图像进行分割。程序用Matlab编写，其核心部分由C++语言实现，编程环境为Matlab 2009b和VC2008。选用标准图像库Weizmann Horse Database（msri.org/people/members/eranb/）中 的 图 像 进行实验，该数据库中马的颜色、大小、形态各异，而且背景也十分复杂，有些与马的颜色很接近，不同图像中的目标之间、背景之间也有着明显的差异。本文分别用传统图割算法和添加形状先验后的算法对图像进行分割，两种方法的能量函数定义的参数λ均设置为43。

图1（a）是一幅加入均值为0，方差为0.01的高斯噪声后的彩色图像，使用传统图割方法时得到初始分割结果如图1（b）；添加形状先验能量后，使用图割方法得到分割结果和标记如图1（c）。从图中可以看到，分割效果得到了优化，错误率明显降低。图2和图3是加入和上图相同大小的噪声后得到的图像分割结果。从这三个图像的分割结果图来看，加入形状先验后的图割算法，对含有噪声的图像具有更强的鲁棒性，得到了更完整的目标分割。

图1 horse320.jpg加入高斯噪声分割结果

图2 horse125.jpg加入高斯噪声分割结果

图3 horse321.jpg加入高斯噪声分割结果

图4（a）是一幅在原图上添加一部分遮挡物后得到的彩色图像；使用传统图割方法得到初始分割结果如图4（b）。从结果图中可以看到，遮挡物部分没有得到有效分割，仍然属于一个整体被错分给了目标部分。添加形状先验能量后，使用图割方法得到分割结果和标记如图4（c）。从图中可以看到，遮挡物部分得到了正确分割，目标部分分割更加完整，分割效果得到了优化，错误率明显降低。

图4 horse002.jpg加入遮挡物分割结果

图5（a）是一幅彩色图像。该图像本身就含有遮挡物，图中人坐在马上，人的上部分身体属于背景，下部分身体属于目标，人为遮挡物。使用传统图割方法得到初始分割结果如图5（b）。从图中可以看出，人的部分没有得到正确分割，目标分割不完整。添加形状先验能量后，使用图割方法得到分割结果和标记如图5（c）。从图中可以看到，错误部分得到了很大改善，分割效果得到了优化。

图5 horse097.jpg含遮挡物分割结果

图6（a）为一幅彩色图像。图中人和马都有影子，含有阴影遮挡。首先使用传统图割方法得到初始分割结果如图6（b）。从结果图中看出，阴影部分均还存在，没有得到正确分割。在上述图割算法中添加形状先验惩罚后，得到分割结果如图6（c）。从图中可以看到，阴影部分得到正确分割，分割结果得到了优化。

图7的图像分割使用的模板是尺度缩放后的模板（a），和分割得到的标记图不相同，则使用上述匹配思想进行模板匹配，在此基础上加入形状先验，得到结果如图所示。图8和图9使用的先验模板分别是平移以后和旋转以后的模板。

图6 horse099.jpg含阴影遮挡分割结果

图7 horse129.jpg的图像分割结果

图8 horse008.jpg的图像分割结果

图9 horse182.jpg的图像分割结果

从表1看出，添加形状先验后的错误率大幅度下降，图像分割效果良好，而耗时会增加，主要是由于增加形状惩罚部分引起的，因为形状惩罚是按图像的像素点加进去的，所以需要逐个像素点来判断，但是并没有增加太多的时间复杂度。实验数据进一步表明了本文算法的有效性和分割效率，表明了本文算法针对含噪、有遮挡或阴影的复杂图像可以较完整地分割出目标，取得了较好的结果。

表1 未含形状信息和包含形状信息的分割错误率和算法运行时间比较

4 结束语

传统的图割方法对简单图像的分割可以得到良好的效果，但是对于含有噪声、遮挡物等的复杂的图像，它的分割效果不能令人满意，有的图像目标分割不完整，有的图像分割结果包含杂质或阴影等部分。本文提出的基于形状先验和图割的图像分割算法，比传统的图割方法分割精度高，特别是对上述提到的复杂图像也能得到良好的分割结果，为图割融合先验知识提供了一种思路。文中选用一个形状先验模板，对一些特定的目标分割具有局限性，只能分割和该形状先验模板一样或仿射不同的目标，对于和形状模版有非刚性变形的目标分割则不适用。针对该局限性，可以考虑采用多个形状先验模板，以适应局部和全局变形。

[1]Greig D，Porteous B，Seheult A.Exact maximum a posteriori estimation for binary image[J].Journal of the Royal Statistical Society：Series B，1989，51（2）：271-279.

[2]Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary®ion segmentation of objects in N-D images[C]//Proceedings of Internation Conference on Computer Vision，July 2001.

[3]Ford L，Fulkerson D.Flows in networks[M].Princeton，New Jersey：Princeton University Press，1962.

[4]杨建功，汪西莉.一种结合图割与双水平集的图像分割方法[J].计算机工程与应用，2012，48（3）：195-197.

[5]Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（11）：1222-1239.

[6]Slabaugh G，Unal G.Graph cuts segmentation using an elliptical shape prior[C]//Proceedings of International Conference on Image Processing，2005：1222-1225.

[7]Veksler O.Star shape prior for graph-cut image segmentation[C]//Proceedigns of ECCV 2008，2008，5304：454-467.

[8]Vu N，Manjunath B S.Shape prior segmentation of multiple objects with graph cuts[C]//Proceedings of CVPR 2008，24-26 June，2008.

[9]Chan T，Zhu W.Level set based shape prior segmentation[C]//Proceedings of CVPR 2005，June 2005，2005：1164-1170.

[10]Pei S C，Lin C N.Imagenormalization for pattern recognition[J].Image and Vision Computing，1995，13（10）.

[11]Paragios N，Rousson M，Ramesh V.Non-rigidregistration using distancefunctions[J].Computer Vision and Image Understanding，2003，89（2/3）：142-165.

[12]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.