基于随机游走的自动图像分割算法*

茅正冲， 韩 毅

0 引 言

近年来，基于图论的图像分割算法成为研究的热点，应用图论进行图像处理具有直观、速度快、效率高等诸多优点。依据用户参与与否，图像分割可分为交互式图像分割和自动图像分割。Boykkov Y等人[1]提出了Graph Cut算法，结合了图像的区域信息和边界信息，目前已成为广泛使用的交互分割方法。Grady L等人[2]率先将随机游走模型应用到图像分割中，计算速度快，可很好地检测弱边缘，并且对噪声有较强的鲁棒性，但需要用户标记标记点，是一种半自动分割算法。

郭丽等人[3]利用背景差分实现了自动识别目标区域，通过形态学方法求得骨架结构，从中获取标记点，再采用随机游走算法进行自动图像分割，在多车辆检测领域解决了交互分割速度慢的问题;但对背景建模时，背景的更新是一个难点。李昌兴等人[4]引入了加速均值算法，提出了一种加速谱聚类的图像分割算法。Qin C C等人[5]对图像进行超像素分割，使用近邻传播聚类算法求取超像素区域中心点，通过固定阈值对中心点标记，自动地为随机游走算法标定标记点。文献[6]中采用模式挖掘算法选取标记点，在显著性提取中取得了不错的效果。

本文提出了一种结合显著性,模式挖掘算法和随机游走的自动分割算法，通过计算图像的显著性图，初步确定感兴趣目标的区域；通过模式挖掘算法为随机游走初步选取标记点，结合位置信息进一步筛选标记点；使用随机游走算法对输入图像进行分割。实验结果表明：本文方法可以自动对图像进行较精确地分割。

1 随机游走算法

根据图像构成加权图G(V,E)，图中任意顶点v∈V视为图像中的一个像素点或者超像素块，将顶点分作VM和VU2个集合，VM表示已标记点的集合，VU表示未标记点的集合，任意一个边e∈E⊆V×V视为两个相邻像素之间的关系，边的权值w视为像素之间的相似或差异性度量

di=∑wij

(1)

式中di为顶点vi的度，表示所有与顶点vi连接的边的权重之和。

根据顶点、边以及权重可以构建图的Laplace矩阵L,将顶点分为VM和VU后，Laplace矩阵表示为

(2)

随机游走的求解过程可以转化为求解Dirichlet问题[7]，即寻求一个满足边界条件的调和函数u(x,y)，使得Dirichlet积分达到最小值，Dirichlet积分为

(3)

(4)

由以上分析可知，随机游走算法进行图像分割的数学理论完整，度量特征选取合适，可以对图像进行完全地分割，但该算法要求用户指定标记点，限制了其在自动图像分割中的应用。

2 显著性检测

为了实现随机游走算法自动分割，本文通过视觉显著性初步确定目标区域。Sun J G[7]等人提出了一种基于马尔科夫吸收概率的(Markov absorption probability,MAP)显著性检测算法，对于一个给定的状态集S={s1,s2,…,sl}，pij表示状态si转移到状态sj的概率，马尔科夫过程表示为转移矩阵P。给定k个吸收节点，m个暂态的马尔科夫链，转移矩阵P为

(5)

式中Q∈[0,1]mm为暂态之间的概率转移矩阵；R∈[0,1]mk为暂态与吸收状态之间的转移概率；I为k×k的单位矩阵。可得基础矩阵N,N的元素nij表示暂态si转移到暂态sj的估计转移次数

N=(I-Q)-1=I+Q+Q2+…

(6)

马尔科夫链中每个暂态si都将独立地转移至吸收状态sj，吸收概率矩阵为

B=NR

(7)

式中B的每个元素bij表示暂态si到吸收状态sj的概率。

3 模式挖掘算法

文献[6]提出了通过模式挖掘算法选取标记点。给定一个有M项的集合I={i1,i2,…,iM}，交易集T为I的子集，交易数据库D={T1,T2,…,TN}由N个不同的交易集组成。集合A由交易集T∈D中部分元素组成，且满足A⊆I，A的支持度定义为

(8)

当supp(A)大于固定的阈值tmin时，集合A称为频繁项集。

关联规则A→p描述A和p同时出现的可能性，关联规则强度可以用支持度和自信度描述，关联支持度、自行度分别定义为

supp(A→p)=supp(A∪{p})

(9)

(10)

支持度和自信度越高，关联规则越强，二者相关性越强。

4 基于随机游走的自动图像分割

4.1 显著性确定目标区域

为了选择一种更有效的显著性提取方法，本文使用若干常见算法求取显著性图，结果如图1所示，图中依次采用的CA[8]，SR[9]，MSS[10]，FASA[11]，MAP[7]算法。由实验结果分析可知:CA和SR得到的显著图中目标外轮廓较清晰，但内部信息未很好地显示，MSS和FASA算法部分对背景的抑制能力相对较弱，而基于马尔科夫链的MAP算法提取显著图目标鲜明，对背景抑制较好，本文根据显著图进行目标的初步定位，采用基于马尔科夫链的MAP算法确定目标区域。

图1 不同算法显著性检测结果

4.2 基于模式挖掘的标记点确定

基于模式挖掘算法确定的标记点如图2所示。首先对给定的图像进行超像素分割，通过显著图确定目标区域，将显著区域的像素块标记为正样本，显著区域外的像素块标记为负样本，采用模式挖掘算法确定和正样本相关的超像素块。具体流程如下：

1)采用SLIC[12]算法在三个尺度对图像进行超像素分割，得到一个超像素集S={s1,s2,…,sN},结合显著图，当每个超像素块在显著图中对应区域亮度值大于一定阈值时，该像素块认定为正样本；否则，认定为负样本。

2)对每个超像素块进行K均值聚类，计算其聚类中心在整幅图像中的索引，表示超像素块的全局位置信息。

3)将包含样本标签和全局位置信息的超像素输入到Apriori频繁项挖掘算法中，得到显著性的频繁超像素集。

4)对相同尺度的超像素和频繁超像素集进行关联规则分析，求取显著的超像素，并将其中心认定为标记点。

结合上述流程，部分初步提取的标记点如图2(b)所示，分析可知，通过模式挖掘算法求得的标记点较丰富，标记点也聚集在目标区域，部分标记点位于目标周围。为了进一步地将标记点分为前景标记点和背景标记点，本文对标记点的位置进行分析，将显著目标内部的标记点判定为前景标记点，外部的标记点判定为背景标记点，处理后的结果如图2(c)所示。

图2 模式挖掘算法确定的标记点

4.3 随机游走算法图像分割

本文结合显著图和模式挖掘算法，自动提取标记点，融合显著性特征进一步将标记点分为前景标记点和背景标记点两类，最终使用随机游走算法对图像进行分割，整体流程如图3所示。

图3 自动图像分割算法流程

5 实验与结果分析

为了验证本文算法的有效性，选取若干样本进行仿真实验，数据来自Berkeley数据集。作为实验对比，使用人工给定标记点，经典随机游走算法进行图像分割，同时采用Grab Cut算法对样本进行交互分割，本文提出的随机游走进行自动分割，对比结果如图4所示。

图4 图像分割结果对比

由图4(b)可以观察到，传统的随机游走算法的图像分割结果依赖于人工给定的标记点，在标记点不很充分的情况下容易出现过分割和欠分割现象。分析图4(d)可知，本文算法取得了良好的检测结果，基于模式挖掘算法选取的标记点数量丰富，对背景抑制能力较强，分割的目标轮廓清晰，为图像的后续处理奠定了良好的基础。将结果与图4(c)Grab Cut算法迭代分割结果进行对比，在背景不是特别复杂的情况下，本文算法的分割结果接近交互分割，可以注意到Grab Cut处理后图像轮廓更完整，本文算法有少量边界出现了过分割现象，如飞机的后部机翼和犀牛的牛角部分，但本文算法可以无需用户参与自动地完成图像分割。

为了进一步说明算法的有效性，提取分割结果边界与图像标准轮廓进行对比，采用正确率(P)、召回率(R)以及F值量化评价实验结果。P表征检测点为真正的轮廓的概率；R表征检测检测点的数量比例；F=2×P×R/(P+R)为准确率和召回率的调和评价，反映整体效果。部分实验样本的评价结果平均值如图5所示。

图5 3种算法仿真数值评价结果

由数值可以看出，相较于传统随机游走分割算法，本文算法分割的结果在正确率和召回率方面均具有明显的提升，图像分割质量较好，但与Grab Cut算法相比，分割结果表现略微欠佳。在要求精细分割的应用中，更好的选择是交互分割方法，但在自动图像检测和批量处理图像时，本文算法分割效果良好，具有一定的优势。

6 结 论

为了实现自动图像分割，重点研究了显著性提取、模式挖掘算法以及随机游走算法。采用模式挖掘算法进行初步确定标记点，进一步结合显著图将标记点分类为前景和背景标记点，算法自动地为随机游走提供标记点；应用显著图和模式挖掘算法确定标记点，随机游走算法最终实现图像分割，效果较好，且分割过程不需用户指定区域。实验结果表明：本文方法处理效果较好，具有一定的应用研究价值。

参考文献:

[1] 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.

[2] Grady L．Random walks for image segmentation[J].IEEE Tran-sactions on Pattern Analysis and Machine Intelligence，2006，28(11):1768-1783．

[3] 郭 丽，高立群，刘 濛，等.一种新的随机游走多车辆检测算法[J].中国图象图形学报，2010(3)：392-396.

[4] 李昌兴,黄艳虎,支晓斌,等.基于加速k均值的谱聚类图像分割算法改进[J].传感器与微系统,2016,35(9):137-140.

[5] Qin C C,Zhang G P,Zhou Y C,et al.Integration of the saliency-based seed extraction and random walks for image segmentation[J].Neuro Computing,2014,129:378-391.

[6] Kong Y Q,Wang L J,Liu X P,et al.Pattern Mining Saliency[C]∥ECCV,2016.

[7] Sun J G,Lu H C,Liu X P.Saliency region detection based on Markov absorption probabilities[J].IEEE Transaction on Image Processing,2015,24(5):1639-1649.

[8] Goferman S,Zelnik-Manor L,Tal A.Context-aware saliency detection[C]∥Computer Vision and Pattern Recognition,2010:2376-2383.

[9] Hou X,Zhang L.Saliency detection.A spectral residual approa-ch[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2007:1-8.

[10] Radhakrishna Achanta,Sabine Susstrunk.Saliency detection using maximum symmetric surround[C]∥International Conference on Image Processing(ICIP),Hong Kong,2010.

[11] Yildirim G,Süsstrunk S.FASA:Fast,accurate,and size-aware salient object detection[C]∥Asian Conferenceon Computer Vision,ACCV 2014,2014:514-528.

[12] Achanta Radhakrishna,Shaji Appu,Smith Kevin,et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(11):2274-2282.