基于图论的图像分割方法具有良好的分割结果和特性,近年来已成为图像处理和计算机视觉领域的研究热点^[1]。Graph cut算法是基于图论的图像分割方法中的一种,因具有全局最优化能力、数值鲁棒性强、执行效率高等优点引起众多国内外研究人员对其进行深入地分析与研究^{[2, 3, 4, 5, 6]}。

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算法进行了研究,使其达到了在短时间内获得高质量分割结果的目的。

基于图论的图像分割方法都是先将图像映射成图,图像中的像素点与图中的节点对应,并用边将有关系的点连接起来,定义合适的权重,权值越大,说明两节点联系越紧密,也可以说相似度较高,权值越小,相似度越低。当图像映射成图后,将图中的联系不大的节点分割开来,形成几个独立连通的子图,就是最后的图像分割结果,其中被切断的边的权值总和称为cut^[11]:

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

${\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]。

相似矩阵真实地描述了像素点的内在结构,所以相似矩阵的构造对于图像的分割结果有很大程度的影响。将图像映射成带权无向图后,边上的权值用来反映两个节点间的相似程度,权值越大表示两节点越相似。权值的大小要根据像素点的强度、空间位置和图像边缘的幅度共同确定。若没有空间位置的限制,背景与对象中强度值相似的像素点就可能被划分到同一区域。当背景与对象有相似的强度值的时候,纹理比较模糊,要想区分清楚图像中的轮廓,通过计算像素点间的图像边缘的幅度来权衡。

当只考虑像素点的强度值和位置,两个像素点间的权值定义为^[11]

其中:F(i),F(j)是图像的特征,比如图像的强度值;X(i)是节点i的空间位置；σ_I和σ_X的值是根据人工经验获得的,分别表示点的差异和敏感度参数。根据两个像素点间的图像边缘幅度定义的权值为^[17]

line(i,j)表示连接像素点i和j的直线,Edge(x)表示x位置的边缘强度。将强度、位置和轮廓结合起来定义权重矩阵(相似矩阵)^[17]

在式(3)中提到,当两像素点间的距离在r范围内,需要用边将两点连接起来并定义合适的权值,距离超过r,认为两点间没有连接的必要性。r值越大,相似矩阵的规模越大,分割越准确,计算复杂度越高,所以图连接半径r的大小的选取是至关重要的。

如图 1所示,随着r值的增大,带有模糊轮廓的松鼠越来越清晰,但是图的相似矩阵变得越来越密集。较小的r值通常使分割更迅速,但是需要许多的扩散操作,才能在更大邻域里传播本地分组线索(local grouping cues)。比如从远处观察一个物体时,看到的是轮廓、形状等较大尺度的特征,近距离观察到的是物体的组成、纹理等精细结构,选择不同的尺度对于目标的识别和理解很重要^[23]。在粗尺度图像图 2(b)中,纹理的边缘往往会模糊且被压缩,图 2(c)反映了在细尺度图像中,模糊细长的边缘和纹理边缘很容易被检测到。从粗尺度考虑,分割顾全大局容易进行,从细尺度考虑,分割结果精确效率较低。只在固定尺度上进行考虑是不够的,要将粗尺度和细尺度完美地结合起来。

图1(Fig. 1)

图1 不同r值对应的分割结果 Fig. 1 Segment results corresponding to different r values

图2(Fig. 2)

图2 固定像素点i对应的图的权重 Fig. 2 Graph weights for a fixed pixel i

理想的图连接半径r是需要考虑计算成本和分割结果的。有效的解决方法是将远距离连接图分解成独立的子图。定义不同距离的图连接半径r_ij(r_ij=‖X_i-X_j‖),图的相似矩阵W_ij有不同的特性。因此根据潜在的图连接半径,将图连接分离成不同尺度。

W_s表示某图连接半径下的相似矩阵。这种分解允许研究不同图连接半径下的图的权重。当权值方差迅速减小,这说明在给定的尺度下,可以“凝结”小邻域中的像素变成代表像素点,并且只存储这些像素之间的权值。当W_s中的元素以s的平方增加,有效地表示W_s的方法是:对于第1个图尺度W₁,把每1个像素作为图节点,通过图的边缘连接相距r的像素点。对于第2个图尺度W₂,没有短的图连接,在原始图像网格中相距2r+1取样像素点作为代表节点。一直递归下去,对于尺度s,以原始图像网格中相距(2r+1)^s-1取样代表像素点。图的不同尺度被定义在图像金字塔的不同层。大半径的图被分解成不同尺度,每个尺度包含特定半径的图连接。尺度越大,邻域的图的权重变化越平缓。将图分解成不相交的尺度,每个尺度都可以通过递归采样像素点来压缩。以较少的图的连接数反映出与原来完全连通图同样的效果。

根据基于Normalized cut准则的应用框架,采用多尺度Normalized cut对图像进行分割,主要工作如下:

(1)将图像映射成Graph,Graph中的每1个节点对应1个像素点,把相似的节点连接起来,并且用边上的权值表示节点之间的相似程度,由此构造出相似矩阵。

(2)建立Laplacian矩阵以及特征方程,求出特征值和特征向量。

(3)选取合适的特征向量对图像进行分割。

(4)检查分割的稳定性确定当前图是否有必要再分,若有的话,进行递归重分。

根据以上步骤及本研究采用的解决问题的思想,多尺度Normalized cut算法流程的主要步骤如图 3所示。

图3(Fig. 3)

图3 多尺度Normalized cut实现流程图 Fig. 3 Flow chart of multi-scale Normalized cut

图像预处理、特征提取并构造相似矩阵、建立并求解特征方程和选取特征向量是多尺度Normalized cut算法的关键步骤,具体意义及实现过程如下:

(1)图像预处理。图像预处理主要是转化图像信息,有利于后续对图像的处理,减少不利因素。不同的图像分割算法的预处理是不同的,比如有的先将图像灰度化再处理,比对彩色图像进行处理的效率更高;有的对图像进行滤波、除噪声等以避免干扰;有的需要建立合适的数据结构,比如多尺度分割。

(2)特征提取并构造相似矩阵。特征是用来代表对象的特殊属性,通过特征可以区分不同的对象。比如寻找边缘就得通过像素的强度值和位置来确定。不同的特征提取会导致不同的图像分割结果。通过构造相似矩阵来体现图像的主要特征信息。

(3)建立并求解特征方程。求得相似矩阵后,便可求出对角矩阵D :

D是以D_ii为对角线元素的N×N矩阵,N为图像的像素个数。L是一个对称矩阵,L=D-W。将求解最小割的问题连续放松,变成了对特征系统求解特征值和特征向量的问题,接下来求解特征方程:

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

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

本研究选取了两组图像进行测试,试验结果如图 4所示。分析图 4可知,在多尺度的Normalized cut上进行分割比普通的Normalized cut的分割结果要精确。不仅把对象从背景中提取出来,还把对象按区域分开,使得特征在同一区域内相似,而在不同区域间表现出明显的不同。把一幅图像根据某些特征分割成若干“有意义”的互不交叠的区域,达到了图像分割的目的。

图4(Fig. 4)

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

采用多尺度的Normalized cut进行图像分割,使用的多尺度图像数据结构^[24]是金字塔结构,底层保存原始图像,每上一层数据都由下一层数据产生。根据输入图像的大小,给出分解的层数以及相关的参数,计算出多尺度相似矩阵,对矩阵进行特征值和特征向量的求解,最后再将连续问题离散化就得到了最后的分割结果。以图 4(a)的左图为例,原图分别被压缩为0.05,0.1,0.2,0.3,0.4,0.5,0.7,1倍后进行多尺度分解的分解结果如图 5所示。

图5(Fig. 5)

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

图 6表示求解不同像素大小的图片的特征值所花费的计算时间。分析图 6可知,随着像素点数目的增加,多尺度的Normalized cut的运行时间成线性增加。

图6(Fig. 6)

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

针对原有Graph cut方法对整幅图像进行处理时,由于像素点数目庞大造成的计算效率低的问题,采用多尺度的Normalized cut作为优化准则,对像素点进行采样,不仅降低了复杂度,还保持了原来像素点间的关系。最后运用谱聚类的思想进行求解得到分割结果。试验结果也充分证明了改进的Graph cut方法的有效性,不管图像大小如何,都可以在线性时间内进行有效地多尺度分解。

本研究将求解最优准则的问题转化为求解矩阵方程,矩阵进行特征分解的时间复杂度是O(n³)^[25],随着图像变大分割效果变差,所以求解矩阵特征向量的一些中间过程需要改进,比如黄先楼提出的将Normalized cut算法在并行平台上实现就是一种很好的研究方法^[26]。另外确定合适的图像分割块数是个难点。不同类型的图像分割块数是不同的,现在只是通过人为经验来确定,所以鲁棒性不够高。对于分割结果的评估,只是定性地比较了不同算法的分割结果,定量评估方法还需待进一步的研究。