层次式图切分快速分割算法

蒋建国， 张 婕， 詹 曙， 郭艳蓉

（合肥工业大学计算机与信息学院, 安徽 合肥 230009）

层次式图切分快速分割算法

蒋建国， 张 婕， 詹 曙， 郭艳蓉

（合肥工业大学计算机与信息学院, 安徽 合肥 230009）

图切分（Graph Cuts，GC）是近年来兴起的基于图论框架的图像分割方法，该理论的新颖之处在于它的全局最优性和结合多种知识的统一性。 但当图像较大时运算非常耗时。该文提出了一种基于GC的层次式图像分割方法。先在低分辨率中用GC以较低的分割代价获取粗尺度的初始分割，再将结果轮廓映射回高分辨率图像中并构造出窄带，进而采用matting思想，在窄带内获取精确分割。实验结果表明，本文方法在确保分割结果准确性的同时，运算速度大幅度提高。

信息处理技术；图像分割；图切分；多层次分割；抠图

图像分割是计算机视觉以及数字图像处理领域的研究热点和难点之一，由于此问题的重要性和困难性，从70年代起图像分割问题一直吸引着国内外研究人员为此努力， 至今已提出了上千个各种类型的分割算法[1]。传统的图像分割方法一般基于区域的信息或者基于边界的信息。但是由于这些图像分割方法只能利用图像信息中的部分特征分割区域，因此必然带有局限性和针对性。近年来，一种结合了基于区域和基于边的图像分割各自优势的Graph Cuts方法引起众多学者的注意[2]。Graph Cuts方法最早是2001年由Boykov等人[3]提出的，该方法将图论思想应用于图像分割，将组合优化理论中的最大流最小割(Max flow-Min Cut)算法用于解决最小能量条件下的图像分割问题，获得全局最优解，具有较强的鲁棒性，集成了机器学习，非线性优化和图论等方面的优势，已经广泛地应用于医学领域[4]和自然图像处理[5]等领域。

Boykov等人提出的Graph Cuts方法[6]，首先分别选定部分像素作为分割目标和背景的种子点，然后将图像中所有像素作为节点，以像素之间的相邻关系作为边，构造一个图，最后通过最大流最小割算法分割目标。最大流最小割算法要穷举所有从源到汇的增广路径[8]，当图像较大时，巨量的图节点使得建立增广路径需搜索大量节点，造成效率低下。为了减少图节点数量，Yin Li等人提出了Lazy Snapping[9]方法，首先利用分水岭(watershed)方法将图像预分割为很多小区域，然后将每个小区域作为一个节点，再利用Graph Cuts方法得到最后分割。虽然该方法将图像预分割后构造出来的图节点数明显减少，初始分割速度得到了很大的提高。但是，基于分水岭法的预分割也要以一定的时间开销为代价，同时，分水岭预分割后的区域大小和数目都是不定的，这样对于大量的图像以及视频序列来说，分割速度和内存开销也都是不确定的。而且这种方法初始分割效果并不理想，为了获得精确的分割边界，后期还需要用户沿着目标边界更多的交互以修正，比较耗时。

本文以Graph Cuts算法框架为基础，运用多层次分析思想，对图像进行多尺度分解，建立金字塔式的多尺度数据结构。在低分辨率通过Graph Cuts算法提取出目标物体的边缘后，通过线性插值方式将其投射到高分辨率图像。由于待分割目标物体内部区域已经确定，因而在高分辨率图像主要进行边界细化，本文采用一种闭合求解的alpha matting算法在物体轮廓周围的窄带内进行细化分割，获得了精确的边缘。

本文把粗糙尺度的易分割性与精细尺度的精确性两者有机的统一起来，使得算法效率显著提高。通过实验表明，相比于直接Graph Cuts方法，本文算法不仅使得内存开销和运算时间都成倍降低，而且能够获得更加精确的分割结果。

1 Graph Cuts

首先简要介绍一下Graph Cuts的分割思想。对于一幅给定的图像I，我们可用图论的思想描述为G=，其中V表示顶点集，E为连接相邻顶点的边集（对于2D图像来说，可以是4邻域或者8邻域，本文采用4邻域系统），W为边的权重。图的顶点集V包括图像I中的像素点和两个特殊的顶点：源点s和汇点t。同样，网络图中的边也分为两种：n-links和 t-links。n-links表示图像中邻接像素对之间的边， t-links表示两个特殊顶点s、t与图像中各个像素之间的边。如图1所示，图中连接边的粗细代表权重大小。因此我们就可以把图像分割问题转换为求图G中的最小割问题。

图1 图的构造

上式中，E1是数据项代价，表示将每个像素点i标记为ix的代价，即将每个像素点分配到前景或者背景的惩罚值，与 t-links有关。E2是平滑项代价，表示相邻节点被分别标记为xi与xj的代价，与n-links有关。

本文采用交互式图像分割思想，先对一幅图像通过不同的颜色分别标记出部分前景点和背景点，作为前景种子点F和背景种子点B，图中剩余未被标记的区域称为未知区域，记为U。为计算E1，我们先通过K均值算法分别将种子点F和B聚类，各聚类中心分别表示为｝与｛｝。然后，对于每个节点i，我们分别计算该点颜色C(i)到前景与背景每聚类中心的颜色距离的最小值，分别记为本文定义E1公式如下

对于平滑项代价E2，定义如下

Graph Cuts方法最显著的特点之一就是具有全局寻优的能力。在寻求最小代价切割问题的过程中，为了快速的计算最小能量，避免冗余且缓慢的组合计算方法，本文采用Boykov提出的基于增广路径的新最大流/最小割算法[11]。该算法与DINIC算法相似，都通过建立查找树来寻找增广路径，但是有两个显著的区别：第一，建立两个搜索树，一个起于源s，另一个起于汇t；第二，重用而不是重新构造搜索树。

2 层次式Graph Cuts

Graph Cuts是基于图论框架兴起的分割方法，通过最大流最小割算法计算得到最小切割代价，具有全局最优，不限制物体拓扑结构，可用于多维图像等优势。但传统的Graph Cuts方法对海量数据进行分割时内存开销巨大、运算时间也无法忍受。例如，Boykov的最大流算法需要24|V|+14|E|Bytes的内存开销来构造图，对5123的三维CT数据进行分割时需要8GBytes的运行内存开销，且需要近小时的处理时间。为此，本文提出了一种层次式分割方法，以减少Graph Cuts在分割大量数据时的内存开销和处理时间，算法流程如图2所示。

图2 本文算法流程图

1） 在进行分割之前，需要先通过用户交互方式在原图像I0指定部分区域分别作为前景和背景的种子点，用白色线段标记前景F，黑色线段标记背景B。然后对交互后图像进行高斯低通滤波，并以一定采样因子进行下采样，建立高斯金字塔。下采样获得低分辨率图像I1（包括交互指定区域）。

2） 在低分辨率图像I1上进行Graph Cuts分割。按照本文第2部分所描述方法对I1构造对应赋权图G1=，利用最大流最小割算法计算得最小割，由此获得I1上的分割结果。

3） 将低分辨率图像的分割边界位置记录下来，并通过线性插值方式投影到高级分辨率图像I0，得到原图像待分割物体的模糊轮廓。

4） 在轮廓内外各膨胀w像素宽度，形成一个包含带分割物体边界的窄带作为不确定区域Tu，窄带宽度为w2 ，并将该带状最内一层设定为前景种子点，最外一层设定为背景种子点。这里w大小的选取根据下采样因子的大小自适应确定。

5） 最后在这个窄带内进行边界细化，以获得精确的物体分割边界。

初始快速分割结果映射到高分辨率图像，必然会带来分割结果不准确，这里需要解决边界粗糙问题。图像上物体的边界附近颜色是由前景和背景以一定系数α线性组合而成的，为了解决初始分割边界粗糙问题，获得真实自然的分割结果，本文采用alpha matting方法在高分辨率图像对分割边界进行细化。现行的alpha matting有很多种方法，一般都是通过非线性迭代来同时计算出α，F和B，会花费大量的计算时间，而且需要较多的用户交互使得未知区域尽可能小，提取效果却不是很好。本文采用一种求前景映射图的闭式解决方案[7]，基于对图像颜色的局部平滑性假设导出一个关于α的二次代价函数，然后通过解一个稀疏线性方程组（4）就可以获得全局最优解。该方法对于前景和背景颜色变化复杂的图像，甚至自然图像中的动物毛发，仍可得到精确的边缘。

这里，L为一个N×N的矩阵，它的第(i,j)项为

对于本文要细化的物体边界窄带，构造一个对角矩阵Ds（N×N，这里N为该窄带内像素数目），对于已经标记为前景或者背景的像素，它对应的对角元素为1，其余元素为0。另设一个向量bs(N×1)，对于标记为白色像素点（前景点），其对应的值为1；黑色像素点（背景点）以及其余未知像素部分，对应为0。在式（4）的基础上加上用户约束，本文边界细化只需在该窄带内计算下式即可

为了直观清晰的了解本文算法思路，图3通过一个分割实例给出了本文算法过程图。图3(a)为待分割图像；(b)是用户交互后图像，白色标记为前景种子点F，黑色标记为背景种子点B；(c)是对标记后图像进行下采样后所得图像，这里所选下采样因子为2；(d)是对(c)所得低分辨率图像进行Graph Cuts分割结果；(e)为将低分辨率分割出的物体边界映射到原图像，并在边界周围膨胀一定像素宽度，形成一个待细化边界窄带；(f)为对该窄带通过alpha matting进行细化得到精确的分割结果。

图3 本文算法分割过程实例图

3 实验与分析

本文实验是在Matlab7.4平台上实现，其中Graph Cuts的优化算法部分是通过调用C程序实现，所用计算机为 Inter(R) CoreTM2 CPU 2.0GHz，3GB内存。下采样因子的选择可由用户根据实际需要选定，对于一般图像选择下采样因子θ为2即可，在实现快速分割的同时保证结果的精确度，对于较大的图像（如实验中选用的1024×1024遥感图像）可选择下采样率为4对图像进行分割。窄带宽度选取经验值θ2。

为了验证本文所提算法的有效性，对同一组灰度图像用本文方法和Graph Cuts进行实验，分别在分割效果、内存开销、时间消耗三方面进行比较，如图4所示。图4中第1列为标记后原图像并给出图像大小；第 2列为直接使用 Graph Cuts分割结果，并给出内存开销和时间消耗；第3列为本文算法分割结果图，以及所消耗的内存和运算时间。这里下采样因子均为2。由对比实验结果可以看出，本文算法较直接采用 Graph Cuts方法，不仅在分割速度上提高近4倍（对于本文算法的分割时间计算包括边界优化所用时间），而且节省了约4倍的内存开销。与此同时，由于本文采用 matting方法对分割图像的边界进行优化，仔细对比第2列与第3列分割结果，可以看出，本文算法所获得分割结果边界更加精确。

图4 本文算法与Graph Cuts分割对比图

为了进一步验证本文算法的优势，分别将本文算法与直接用Graph Cuts方法对32幅不同尺寸图像进行分割，统计两种算法分割的时间代价和内存开销如图5所示。

图5 本文算法与Graph Cuts分割时间和内存对比

图6是对彩色自然图像进行分割的实例，进一步说明了本文分割的效果，观察图6 ii（b）老虎的胡须部位的分割结果可以看出，即使对于毛发这类细小的物体，本文算法依然可以获得精确的分割结果。

图6 自然图像分割实例

图7是本文算法应用于医学图像分割，图8是对遥感图像进行分割，可以看出均获得了较为满意的结果。这类图像含有较多噪声，由此可以看出本文算法具有一定的抗噪性能。

图7 医学图像分割实例

图8 遥感图像分割实例

4 结 论

本文提出了一种基于Graph Cuts的多层次图像分割算法，先在低分辨率图像上进行Graph Cuts分割出初始目标，然后将物体轮廓通过线性插值投影到高分辨率图像，为了解决边界粗糙问题，采用一种alpha matting对其进行细化，从而得到精确的抠像结果。由于低分辨率图像具有较小尺寸，Graph Cuts方法分割初始图像的计算代价很低，而对高分辨率图像只在边界的带状区域进行细化分割。通过与直接使用Graph Cuts方法进行分割的对比实验结果表明，本文算法不仅成倍降低了运算时间和内存开销，而且获得了更加精确的分割结果。实验中将本文算法分别应用于自然图像，医学图像，遥感图像，均取得了理想的分割结果。因此可以看出本文算法具有一定的实用价值。

[1]Nikhil R P, Sankar K P. A review on image segmentation techniques [J]. Pattern Recognition,1993, 26(9)：1277-1294.

[2]Qiu G, Yuen P C. Interactive imaging and vision——Ideas, algorithms and applications [J]. Pattern Recognition, 2010, 43：431-433.

[3]Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts [J]. IEEE Transaction on PAMI, 2001, 23(11)：1222-1239.

[4]Chittajallu D R, Brunner G, Kurkure U, et al.Fuzzy-cuts：a knowledge driven graph-based method for medical image segmentation[C]//IEEE Conference on Computer Vision and Pattern Recognition, Miami,USA：2009：715 – 722.

[5]Jong S K, Kisang H. Color-texture segmentation using unsupervised graph cuts [J]. Pattern Recognition, 2009,(42)：735-750.

[6]Boykov Y, Funka-Lea G. Graph cuts and efficient N-D image segmentation [J]. International Journal of Comouter Vision, 2006, 70(2)：109-131.

[7]Levin A, Lischinski D, Weiss Y. A closed fom solution to natural image matting[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, New York, USA：2006：61-68.

[8]Ahuja R K, Magnanti T L. Network flows：theory,algorithms and application [M]. 北京：机械工业出版社, 2005：111-159.

[9]Li Yin, Sun Jian, Tang Chikeung, et al. Lazy snapping [C]//Proceedings of ACM SIGGRAPH,2004：303-308.

[10]Geman S, Geman D. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images [J].Journal of Applied Statistics, 1993, 20(6)：25- 62.

[11] Boykov Y, Kolmogorov V. An experimental comparison of mincut/max-flow algorithms for energy minimization in vision [J]. IEEE Transactions on Pattern Analysis and Machine Interlligence, 2004,26(9)：1124-1137.

Multilevel graph cuts for fast image segmentation

Jiang Jianguo, Zhang Jie, Zhan Shu, Guo Yanrong
( School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China )

Graph Cuts (GC) is a novel image segmentation method based on graph theory framework. The innovations of this theory lie in its global optimization and the unity of knowledge. However, if the image is large, computation will be very time-consuming. This paper presents a GC-based Hierarchical image segmentation method. First the initial segmentation is obtained through GC in the low-resolution with a very low computational cost. Then the contour is projected back to the high-resolution image to construct a narrow band. At last accurate segmentation in the narrow-band is achieved by using of matting arithmetic. Experimental results show that this method can ensure the accuracy of segmentation results with a significant increasing in computing speed.

information processing technology; image segmentation; graph cuts; multilevel segmentation; matting

TP 391

A

1003-0158(2012)01-0044-06

2010-04-01

安徽省2010高校省级自然科学研究重点资助项目（KJ2010A193）；教育部博士点基金资助项目（20060359004）；教育部留学归国人员科研启动基金资助项目（413117）

蒋建国（1955-），男，安徽广德人，教授，主要研究方向为数字图像分析与处理、数字信号处理、分布式智能系统。