﻿ 基于多尺度的改进Graph cut算法
 «上一篇 下一篇»
 山东大学学报(工学版)  2016, Vol. 46 Issue (1): 28-33  DOI: 10.6040/j.issn.1672-3961.1.2015.030 0

### 引用本文

FAN Shuyan, DING Shifei. An improved multi-scale Graph cut algorithm[J]. Journal of Shandong University(Engineering Science), 2016, 46(1): 28-33. DOI: 10.6040/j.issn.1672-3961.1.2015.030.

### 文章历史

1. 中国矿业大学计算机科学与技术学院, 江苏 徐州 221116;
2. 中国科学院计算技术研究所智能信息处理重点实验室, 北京 100190

An improved multi-scale Graph cut algorithm
FAN Shuyan1, 2, DING Shifei1, 2
1.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, Jiangsu, China;
2.Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Science, Beijing 100190, China
Abstract: Aimed at Graph cut algorithm that has the short comings of high computational and possible aver-segmentation, a developed algorithm was presented. The algorithm used multi-scale normalized cut as an objective function of Graph cut algorithm which could avoid the over-segmentation phenomenon. Meanwhile, by combining accuracy of fine scale and easy divisibility of rough scale, sampling pixels not only retained the relationship between the original pixels, but also reduced computational complexity. By using the solving approach based on spectral graph theory, the problem was transformed into similarity matrix eigenvalue and eigenvectors problems, and the similarity was high. Experimental results showed that the proposed algorithm could effectively segment images without user interaction. The segmentation process was fast and segmentation results were accurate.
Key words: graph cut    multi-scale    Normalized cut    spectral clustering    image segmentation    graph theory
0 引言

Graph cut算法是将图像分割问题转换为图论中网络图的切割问题,依据合适的能量函数建立相应的网络图,通过最大流/最小割算法求解网络图的最小割,将求解结果反射到图像中,从而获取图像的分割结果[7]。但是当对整幅图像进行处理时,图像映射成的网络图的节点数目庞大,计算复杂度高,内存开销大。所以人们提出了各种行之有效的改进算法,主要有两类:一类是将Graph cut算法和其他算法结合,另一类是将图像映射为图后,将问题转换为能量函数优化的问题,改进优化准则,使得分割结果最优,效率较高。从改进优化准则的角度对Graph cut算法进行改进的算法已有不少,但仍存在不足:WU Z和LEAHY R将最小割(minimum cut)运用到图像分割领域,并基于网络最大流理论求解最小割,得到分割结果[8]。最小割准则进行图像分割时一般会得到不错的分割结果,但有时候的分割结果严重失衡,如出现“孤点”,就是过分割的现象。WEI Y C和CHENG C K提出的比率割(ratio cut)减小了过分割的可能性,但仅着眼于减小类之间的相似度[9]。SARKAR S提出了平均割(average cut),能够产生较准确地类划分,但是仅考虑了类之间的连接,而忽略了类内部的连接[10]。SHI J B和MALIK J提出的规范割(Normalized cut)既考虑了分割区域间的连接,也考虑了区域内部的连接,同时避免了出现孤立点的情况[11]。DING C提出的最小最大割准则(min/max cut)倾向于产生平衡的区域划分,可以避免分割出只包含几个顶点的较小子集,但是算法复杂度较高,运行速度慢[12]。近十年来复杂网络的研究迅速崛起,Newman运用模块度准则的思想分割复杂网络,还可以进行有效地社团发现[13, 14, 15, 16]。针对Graph cut算法存在着计算复杂度高及可能出现过分割等不足,本研究对多尺度下的Normalized cut准则[17]作为目标函数的Graph cut算法进行了研究,使其达到了在短时间内获得高质量分割结果的目的。

1 Graph cut算法分析 1.1 图的划分

 ${\rm{cut}}(A,B)=\sum\limits_{u \in A,v \in B} {w{{(u,v)}_.}}$ (1)

cut值越小,说明被分割开的节点间的相似度越小,同一区域内的节点的相似度较大[18]。显然,当两个子图间断开的边数越少,权重和就小,容易出现孤点的情况。若采用Normalized cut准则进行图像分割,Normalized cut(简称为Ncut)的定义为[7]

 ${\rm{Ncut}}(A,B)=\frac{{{\rm{cut}}(A,B)}}{{{\rm{assoc}}(A,V)}}+\frac{{{\rm{cut}}(A,B)}}{{{\rm{assoc}}(B,V)}},$ (2)

${\rm{assoc}}(A,V)=\sum\limits_{u \in A,t \in V} {w(u,t)}$表示A中节点集到图中整个节点集之间的权重和,assoc(B,V)的定义是相似的。假设A只包含一个孤立点,那么cut(A,B)=assoc(A,B),则显然Ncut值较大,所以以Normalized cut作为最优化准则完全避免了出现孤立点的情况。但是对于求解Normalized cut目标函数的问题被证明是NP-hard问题[19]。幸运的是,可以借助谱聚类的方法,将原来的离散最优化问题松弛到实数域,问题可在多项式时间内求解,最终得到一个近似最优解[20]。谱聚类的思想来源于谱图理论,根据给定的样本数据定义数据点间的相似性度量,基于该相似性度量,构造数据点的相似度矩阵,再求出拉普拉斯矩阵,对拉普拉斯矩阵进行特征分解求出特征值和特征向量,基于一个或多个向量,把每个数据点映射到一个低维的代表点;最后,基于新的代表点,将数据点划分成两个或多个类[21]。经过数学推导可以证明,拉普拉斯矩阵的特征值和特征向量中包含了数据点的分类信息,在聚类过程中充分利用这些分类信息,就可以得到较好的聚类结果[22]

1.2 相似矩阵的构造

 $\begin{array}{l} {W_I}(i,j)={e^{\frac{{ - \left\| {\left.{{F_{(i)}} - {F_{(j)}}} \right\|_2^2} \right.}}{{\sigma _I^2}}}}\\ \left\{ {\begin{array}{*{20}{c}} {{e^{\frac{{ - \left\| {\left.{{X_{(i)}} - {X_{(j)}}} \right\|_2^2} \right.}}{{\sigma _X^2}}}},}&{if\left\| {{{\left.{{X_{(i)}} - {X_{(j)}}} \right\|}_2} 其中:F(i),F(j)是图像的特征,比如图像的强度值;X(i)是节点i的空间位置；σIσX的值是根据人工经验获得的,分别表示点的差异和敏感度参数。根据两个像素点间的图像边缘幅度定义的权值为[17] ${W_C}(i,j)={e^{\frac{{ - {{\max }_{x \in line(i,j)}}{{\left\| {\left.{Edge(x)} \right\|} \right.}^2}}}{{{\sigma _C}}}}},$(4) line(i,j)表示连接像素点ij的直线,Edge(x)表示x位置的边缘强度。将强度、位置和轮廓结合起来定义权重矩阵(相似矩阵)[17] ${{\bf{W}}_{ij}}=\sqrt {{{\bf{W}}_I}(i,j)\times {{\bf{W}}_C}(i,j)}+\alpha {{\bf{W}}_C}(i,j).$(5) 1.3 图连接半径大小的确定 在式(3)中提到,当两像素点间的距离在r范围内,需要用边将两点连接起来并定义合适的权值,距离超过r,认为两点间没有连接的必要性。r值越大,相似矩阵的规模越大,分割越准确,计算复杂度越高,所以图连接半径r的大小的选取是至关重要的。 图 1所示,随着r值的增大,带有模糊轮廓的松鼠越来越清晰,但是图的相似矩阵变得越来越密集。较小的r值通常使分割更迅速,但是需要许多的扩散操作,才能在更大邻域里传播本地分组线索(local grouping cues)。比如从远处观察一个物体时,看到的是轮廓、形状等较大尺度的特征,近距离观察到的是物体的组成、纹理等精细结构,选择不同的尺度对于目标的识别和理解很重要[23]。在粗尺度图像图 2(b)中,纹理的边缘往往会模糊且被压缩,图 2(c)反映了在细尺度图像中,模糊细长的边缘和纹理边缘很容易被检测到。从粗尺度考虑,分割顾全大局容易进行,从细尺度考虑,分割结果精确效率较低。只在固定尺度上进行考虑是不够的,要将粗尺度和细尺度完美地结合起来。  图1 不同r值对应的分割结果 Fig. 1 Segment results corresponding to different r values  图2 固定像素点i对应的图的权重 Fig. 2 Graph weights for a fixed pixel i 理想的图连接半径r是需要考虑计算成本和分割结果的。有效的解决方法是将远距离连接图分解成独立的子图。定义不同距离的图连接半径rij(rij=‖Xi-Xj‖),图的相似矩阵Wij有不同的特性。因此根据潜在的图连接半径,将图连接分离成不同尺度。 ${\bf{W}}={{\bf{W}}_1}+{{\bf{W}}_2}+..+{{\bf{W}}_s}$(6) Ws表示某图连接半径下的相似矩阵。这种分解允许研究不同图连接半径下的图的权重。当权值方差迅速减小,这说明在给定的尺度下,可以“凝结”小邻域中的像素变成代表像素点,并且只存储这些像素之间的权值。当Ws中的元素以s的平方增加,有效地表示Ws的方法是:对于第1个图尺度W1,把每1个像素作为图节点,通过图的边缘连接相距r的像素点。对于第2个图尺度W2,没有短的图连接,在原始图像网格中相距2r+1取样像素点作为代表节点。一直递归下去,对于尺度s,以原始图像网格中相距(2r+1)s-1取样代表像素点。图的不同尺度被定义在图像金字塔的不同层。大半径的图被分解成不同尺度,每个尺度包含特定半径的图连接。尺度越大,邻域的图的权重变化越平缓。将图分解成不相交的尺度,每个尺度都可以通过递归采样像素点来压缩。以较少的图的连接数反映出与原来完全连通图同样的效果。 2 多尺度Normalized cut的计算过程 根据基于Normalized cut准则的应用框架,采用多尺度Normalized cut对图像进行分割,主要工作如下: (1)将图像映射成Graph,Graph中的每1个节点对应1个像素点,把相似的节点连接起来,并且用边上的权值表示节点之间的相似程度,由此构造出相似矩阵。 (2)建立Laplacian矩阵以及特征方程,求出特征值和特征向量。 (3)选取合适的特征向量对图像进行分割。 (4)检查分割的稳定性确定当前图是否有必要再分,若有的话,进行递归重分。 根据以上步骤及本研究采用的解决问题的思想,多尺度Normalized cut算法流程的主要步骤如图 3所示。  图3 多尺度Normalized cut实现流程图 Fig. 3 Flow chart of multi-scale Normalized cut 图像预处理、特征提取并构造相似矩阵、建立并求解特征方程和选取特征向量是多尺度Normalized cut算法的关键步骤,具体意义及实现过程如下: (1)图像预处理。图像预处理主要是转化图像信息,有利于后续对图像的处理,减少不利因素。不同的图像分割算法的预处理是不同的,比如有的先将图像灰度化再处理,比对彩色图像进行处理的效率更高;有的对图像进行滤波、除噪声等以避免干扰;有的需要建立合适的数据结构,比如多尺度分割。 (2)特征提取并构造相似矩阵。特征是用来代表对象的特殊属性,通过特征可以区分不同的对象。比如寻找边缘就得通过像素的强度值和位置来确定。不同的特征提取会导致不同的图像分割结果。通过构造相似矩阵来体现图像的主要特征信息。 (3)建立并求解特征方程。求得相似矩阵后,便可求出对角矩阵D : ${{\bf{D}}_{i,i}}=\sum\limits_{j=1}^N {{w_{i,j}}},$(7) D是以Dii为对角线元素的N×N矩阵,N为图像的像素个数。L是一个对称矩阵,L=D-W。将求解最小割的问题连续放松,变成了对特征系统求解特征值和特征向量的问题,接下来求解特征方程: ${\bf{Lq}}=\lambda {\bf{Dq}},\$ (8)

q表示N维指示向量。从另一个角度看,将原来离散化的问题变成了连续问题。

(4)选取特征向量。选取特征向量是很重要的,并不是每个特征向量都对分割结果有用。经过多次实践,使用第二小特征向量对应的特征值找到图形的切割点后,会得到当前图的最佳分割。这也是许多谱聚类算法都将图划分问题转化为求解Laplacian矩阵的第二小特征向量问题的原因。

3 试验与结果分析

 图4 两组图像的分割结果 Fig. 4 Segment results of two groups of images

 图5 大小不同的图像多尺度分割的结果 Fig. 5 Multi-scale segment results for images with different sizes

 图6 求解特征值的总计算时间 Fig. 6 The total computing time of solving eigenvalues
4 结语

 [1] 艾海舟, 兴军亮. 计算机视觉:算法与应用[M].北京:清华大学出版社, 2012:206-235.AI Haizhou, XING Junliang. Computer Vision:Algorithms and Applications[M]. Beijing:Tsinghua University Press, 2012:206-235.(1) [2] 韩守东, 赵勇, 陶文兵, 等. 基于高斯超像素的快速 Graph Cuts 图像分割方法[J]. 自动化学报, 2011, 37(1):10-20.HAN Shoudong, ZHAO Yong, TAO Wenbing, et al. Gaussian super-pixel based fast image segmentation using graph Cuts[J]. Acta Automatica Sinica, 2011, 37(1):10-20.(1) [3] OTSUKI K, KOBAYASHI Y, MUROTA K. Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network[J]. European Journal of Operational Research, 2016, 248(2):396-403.(1) [4] ZHOU Xiangyang, ZHANG Jiaxin, KULIS Brian. Power-Law graph cuts[J]. Computer Vision and Pattern Recognition, 2014:1411-1971.(1) [5] SESHADRI K, SHALINIE S M. Parallelization of a graph-cut based algorithm for hierarchical clustering of web documents[J]. Concurrency and Computation:Practice and Experience, 2015, 27(17):5156-5176.(1) [6] ZHANG D, JODOIN P M, LI C, et al. Novel graph cuts method for multi-frame super-resolution[J]. IEEE Signal Processing Letters, 2015, 22(12):2279-2283.(1) [7] BOYKOV Y, JOLLY M P. Interactive graph cuts for optimal boundary and region segmentation of objects in ND images[C]//IEEE International Conference on Computer Vision. New York,USA:IEEE, 2001:105-112.(2) [8] WU Z, LEAHY R. An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11):1101-1113.(1) [9] WEI Y C, CHENG C K. Toward efficient hierarchical designs by ratio cut partition[C]//IEEE International Conference on CAD. New York:IEEE, 1989:298-301.(1) [10] SARKAR S, SOUNDARARAJAN P. Supervised learning of large perceptual organization:graph spectral partitioning and learning automata[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(5):504-525.(1) [11] SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.(3) [12] DING C, HE X, ZHA H, et al. A min-max cut algorithm for graph partitioning and data clustering[C]//Proceedings of the 2001 IEEE International Conference on Data Mining. Washington D C, USA:IEEE Computer Society, 2001:107-114(1) [13] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3):36-104.(1) [14] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States, 2006, 103(23):8577-8582.(1) [15] NEWMAN M E J. Analysis of weighted networks[J].Physical Review E, 2004, 70(5):56-131.(1) [16] LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. Physical Review Letters, 2008, 100(11):118-703.(1) [17] COUR T, BENEZIT F, SHI J. Spectral segmentation with multiscale graph decomposition[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). New York,USA:IEEE, 2005:1124-1131.(3) [18] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1):48-61.SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61.(1) [19] 孙惠泉. 图论及其应用[M]. 北京:科学出版社, 2004.(1) [20] PACCANARO A, CHENNUBHOTLA C, CASBON J A. Spectral clustering of protein sequences[J]. Nucleic Acids Research, 2006, 34(5):1571-1580.(1) [21] JIA H, DING S, XU X, et al. The latest research progress on spectral clustering[J]. Neural Computing and Applications, 2014, 6(24):1477-1486.(1) [22] 李建元, 周脚根, 关佶红, 等. 谱图聚类算法研究进展[J]. 智能系统学报, 2011, 6(5):405-414.LI Jianyuan, ZHOU Jiaogen, GUAN Jihong, et al. A survey of clustering algorithms based on spectra of graphs[J]. CAAI Transactions on Intelligent Systems, 2011, 6(5):405-414.(1) [23] LINDEBERG T. Scale-Space theory in computer vision[M].Berlin:Springer Science & Business Media, 2013.(1) [24] 王鹏伟. 基于多尺度理论的图像分割方法研究[D]. 合肥: 中国科学技术大学, 2007.WANG Pengwei. Research on the application of multi-scale analysis method in image segmentation[D]. Hefei:University of Science And Technology of China, 2007.(1) [25] CHEN W Y, SONG Y Q, BAI H J, et al. Parallel spectral clustering in distributed systems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3):568-586.(1) [26] 黄先楼.基于Normalized Cut的图像分割及其CUDA并行实现[D].北京:北京交通大学, 2014.HUANG Xianlou. Image segmentation based on Normalized Cut and CUDA parallel implementation[D]. Beijing:Beijing Jiaotong University, 2014.(1)