流形排序的交互式图像分割

曾宪华，易荣辉，何姗姗

(1.重庆邮电大学 计算机科学与技术学院，重庆 400065； 2.重庆邮电大学 计算智能重庆市重点实验室，重庆 400065)

流形排序的交互式图像分割

曾宪华1,2，易荣辉1,2，何姗姗1,2

(1.重庆邮电大学 计算机科学与技术学院，重庆 400065； 2.重庆邮电大学 计算智能重庆市重点实验室，重庆 400065)

摘要：针对显著目标检测难以获得有效的目标整体检测导致目标分割困难的问题，采用一种在初始显著图的指导下添加有效交互信息的方式来获得目标的准确分割。该方法利用边界先验对超像素进行流形排序获得初始显著图，参照显著图对不显著的目标部分添加目标标记，显著背景部分添加背景标记，利用标记信息对超像素重新进行流形排序，将获得的显著图与初始显著图融合，对融合后的显著图采用自适应阈值法来获得目标的分割。在BSD图像数据库中的实验得到的平均正确分割率(TPR)和平均错误分割率(FPR)优于经典的最大相似合并图像分割算法(MSRM)，表明了该算法能有效分割出正确的目标。

关键词：流形排序；交互式图像分割；显著目标；目标检测；显著图；背景标记；目标标记

中文引用格式：曾宪华，易荣辉，何姗姗.流形排序的交互式图像分割[J]. 智能系统学报， 2016, 11(1): 117-123.

英文引用格式：ZENG Xianhua, YI Ronghui, HE Shanshan,et al. Interactive image segmentation based on manifold ranking[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 117-123.

图像分割是图像处理中的一个重要环节，其主要的任务是将图像划分为若干具有一致性的不重叠区域。图像分割按照是否需要用户交互处理可以分为自动图像分割、半自动图像分割、纯手动分割。自动图像分割在没有用户先验指导的前提下对图像进行分割往往难以获得可信赖的结果。半自动图像分割方法主要指的是交互式图像分割方法，通过简单的用户标记，对较为复杂的图像或者难以区分相似的前景和背景区域的图像，具有较好的分割效果。

当前，交互式图像分割是一个热点研究问题，获得了较大的发展，其中经典的方法，如live wire算法[1-2]、snake算法[3]、随机游走[4-5]、图割算法[6-7]、最大相似区域合并算法[8]等。在交互式分割算法中，用户通过人机交互，使用鼠标在待分割图像中进行一定的目标和背景标记，给予图像一定的分割指导先验信息，然后根据先验信息建立分割算法模型，这样交互式分割算法获得的分割目标较为精确。

受显著目标检测算法启发，当使用显著目标检测[9-12]来获得目标的分割时，理想情况是通过自动的方法获得目标的整体检测，并能对目标进行有效分割。然而，当背景环境较为复杂或者背景中有细小较为突出的物体时，显著目标检测算法很容易失效，图像中部分不显著目标部分被抑制，而部分显著背景部分被突出，获得有效完整的目标分割将会是一件较为困难的事情。当前，在显著目标检测模型中，经典的有Ma等[9]通过在LUV颜色空间计算像素与局部邻域像素的差异来获得显著图，然后利用模糊增长来分割出显著区域。Gopalakrishnan等[10]提出了基于颜色和方向分布建模的显著区域检测算法。该算法思想是利用颜色和方向视觉特征进行基于分布建模的显著性度量，并生成对应的显著图，然后在其中选择一个更能体现目标显著性的作为最终显著图。Wei等[11]提出基于边界先验的显著性检测算法，该算法利用边界先验和背景先验，将区域的显著性定义为该区域到图像四周的最短距离，通过对背景的检测获得相应的目标检测。Yang等[12]提出一种基于流形排序的显著性检测算法，利用边界先验对超像素进行流形排序获得初始显著图，然后再将显著值高的部分作为目标先验，再次对超像素进行流形排序获得显著图。

针对利用显著目标检测算法难以获得有效目标整体检测导致目标分割困难的问题，本文在文献[12]的基础上，提出了一种基于流形排序[14-15]的交互式图像分割(interative image segmentation based on manifold ranking, IISMR)算法。该算法主要在如下两点进行改进：1)使用交互的方式对超像素进行流形排序来增强不显著的目标部分，抑制显著的背景部分，能有效避免不显著的目标部分被误分为背景，显著背景部分被误分为目标；2)采用融合初始显著图和交互获得的显著图来增强背景和目标部分的差异，并使用一种自适应的阈值来获得此类图像的有效目标分割。最后，本文算法在BSD图像分割数据[16]中选取部分图像进行测试，以验证该算法的有效性。

1流形排序

流形排序由Zhou等[14-15]提出，可以看成是对假设具有流形分布结构的数据进行排序处理。流形排序过程具体描述如下。

给定数据集X={x1,x2,…,xk,xk+1,…,xn}属于Rm×n。其中x1,x2,…,xk表示选出作为标签的数据，那么相应的xk+1,…,xn表示未添加标签需要待排序的数据。使用：X→Rn表示一个排序函数，其中可以看成是一个排序向量=[1f2…n]T，k表示每个点xk分配的排序值，令y=[y1y2…yn]T，表示一个指示向量。当xk是添加了标签的数据时，yk=1；当xk是未添加标签的数据时，yk=0。

首先，对数据集X构建K近邻(K-nearest neighbor, K-NN)图G(V,E)，V表示数据集X，其中E表示图边的权值，即数据之间的关联度。

(1)

(2)

利用排序公式进行迭代处理，当排序得分收敛不再发生变化时停止，排序公式如式(3)所示。

(3)

(4)

式中：I因为(1-α)对数据之间相对排序关系没有影响，流形排序最终收敛公式可以写成如式(5)所示。

(5)

相应地，通过矩阵变换可以得到非标准化的流形排序公式

(6)

2基于流形排序的交互式图像分割

本文采用显著目标检测来获得图像的目标分割，其中文献[12]已经表明流形排序能有效用于显著目标检测。将超像素用于流形排序，能更加真实表示超像素之间相关性，通过对图像中全局的超像素进行流形排序能有效突出目标中的显著部分。但是对于目标不显著部分，或者显著的背景部分，导致利用显著目标检测来获得完整的图像目标分割仍然比较困难。为了有效利用显著图来进行目标分割，通过交互的方式，突出不显著目标部分，抑制显著背景部分，能较好地获得目标的图像分割。

先采用简单线性迭代聚类(simple linear interative clusterimg, SLIC)算法[13]对图像进行预处理，将图像分割成许多小区域，这些由像素集合构成小区域在颜色、亮度、纹理等特性上具有相似性，这种小区域称之为超像素。该算法可以控制所分割的超像素数目，获得的超像素大小具有较为一致和较好的边界贴合度，便于后面的排序处理。

然后对超像素进行流形排序获得初始显著图，在初始显著图的指导下有针对地在目标不显著部分添加背景标记信息，增强目标部分的显著性，在较显著的背景部分添加背景标记信息，抑制背景部分的显著性，利用标记信息重新对超像素进行流形排序，将获得的显著图与初始显著图融合，形成背景与目标灰度差异较大的显著图，然后通过自适应阈值分割获得目标分割，并在BSD图像数据库中测试，能获得较好的目标分割结果。该算法(IISMR)流程如图1所示。

图1　IISMR算法流程Fig.1　The process of IISMR

2.1流形排序获得初始显著图

(7)

式中：Ai表示超像素i近邻的超像素，SAi表示Ai的近邻的超像素，Ci和Cj表示对应超像素两点在CIELAB颜色空间的均值[12]，σ是一个控制权重的因子。

将图像四边边界超像素集表示为{Xt,Xb,Xl,Xr}首先将图像顶部边界超像素Xt作为标签，然后利用非标准化的超像素流形排序公式(6)，求得归一化的排序ft(xk),k=1,2，…，n,得到相应的显著目标得分ft(xk)=1-ft(xk)，然后依次使用图像下边界Xb，左边界Xl，右边界Xr作为标签，得到归一化排序得分fb(xk)、fl(xk)、fr(xk)，从而得到相应的显著目标得分fb(xk)、fl(xk)、fr(xk)，xk∈X并按照式(8)将4个显著目标得分通过融合,归一化获得初始显著目标得分F1(xk)=[f1(x1)f1(x2) …f1(xn)]T。

(8)

式中：k=1,2,…，n。将排序得分F1(xk)×255映射到灰度图像获得初始显著图S1(xk)，xk∈X。

2.2目标和背景标记

现有显著目标检测算法很难做到将目标整体部分检测出来，因为目标可能存在不显著部分，背景区域存在显著部分。这样图像中不显著的目标部分则难以检测，而一些属于背景中突出部分被检测出来，难以做到对目标进行有效的分割。本文为了利用显著目标检测算法获得目标的有效分割，采用人工标记的方法来突出不显著的目标区域，抑制突出的背景区域，通过获得的初始显著图，对初始显著图中不显著的目标部分对应的原始图像部分进行目标标记y+，y+=[y1y2…yp]表示标记的超像素；对初始显著图中显著的背景部分对应的原始图像部分进行背景标记y-，y-=[y1y2…yq]；未标记的超像素由y0表示。那么新定义排序指示向量y由3部分构成，如式(9)所示。

(9)

当超像素为目标标记y+时，超像素xk对应的指示向量yk=1；当超像素标记为背景时y-，超像素xk对应的指示向量yk=-1；当超像素未标记y0时，相应的超像素xk对应的指示向量yk=0。这样设定指示向量，使其在排序处理能有效增加背景和目标的差异，并能有效抑制背景的显著部分，同时通过初始显著图来添加标记信息，能增加标记信息的有效性，减少重复标记处理。

2.3显著图融合

(10)

将目标和背景标记作为相应处理的排序得分F2(xk)×255映射到灰度图像获得显著图S2(xk)，xk∈X。为有效利用初始显著图，本文将初始目标排序得分进行融合，能让2幅显著图进行有效互补，使其目标部分能较为突出，显著性较为光滑，背景部分的显著性得到抑制，背景与目标间差异较大，便于通过有效的阈值分割获得目标，其中融合公式如式(11)所示。

(11)

式中：λ是一个平衡项，让2个归一化的向量在融合时尽可能突出目标，抑制背景。经过大量实验表明λ=0.3较为合适。

2.4获取目标

本文将目标排序得分映射到超像素对应的显著图，通过融合后的显著图的灰度直方图显示，该图像背景部分有明显的波峰，目标部分不光滑导致目标部分的波峰不稳定，并且离散幅度较大，常规的阈值方法难以获得图像的有效分割。本文采用一种结合背景波峰和最大相邻灰度间距的方法来确定自适应阈值。

图像中背景部分和目标部分灰度差异较大，同时背景部分灰度值较低，为了有效避免目标波峰不稳定的给确定阈值带来的干扰，将阈值确定在某一个灰度值的子区间，然后利用背景和目标灰度差异较大来寻找子区间中灰度值的直方图不为0的最大间隔的2个相邻灰度值，取这2个相邻灰度值的平均值作为阈值。同时为了避免因背景和目标部分波峰明显，通过相邻灰度子区间之差获得的最大值不是有效的最大灰度间隔，对于这种情况本文重新限定阈值，即确定灰度子区间最大值，选择离它最近的直方图非0的灰度，计算两者的灰度差。当灰度差大于灰度子区间中直方图的非0灰度差时，阈值则为灰度子区间的最大值。确定阈值后，将灰度图像二值化获得目标分割，并将分割区域用原始目标图像体现。显著图中背景直方图最大的灰度值如式(12)所示。

(12)

式中：R表示一个限定灰度;H(k)表示图像中灰度为k的像素点个数。式(12)表示图像中在[0,R]区间灰度值为k的像素最多，其中R=110。

直方图中两个相邻的灰度值ki、kj(图像中灰度ki、kj对应的像素个数不为0)的最大间距如式(13)所示。

(13)

式(13)表示在灰度区间[k,R]中满足灰度差Lij最大的像素个数不为0的两个相邻灰度值为ki、kj，并且ki>kj，那么阈值T=0.5(ki+kj)，当(R-km)>max(ki-kj)时，则阈值T=R，km表示离R最近的像素个数不为0的灰度值。

2.5算法实现

输入彩色图像

输出分割目标

1)图像预分割处理。首先使用SLIC算法获得原始图像的超像素集X={x1,x2,…,xk,xk+1,…,xn}。

2)超像素排序。构建近邻图G(V,E)并通过式(7)获得权重矩阵，通过背景先验{Xt,Xb,Xl,Xr}利用式(6)获得相应的超像素归一化排序得分向量ft(xk)，fb(xk)，fl(xk)，fr(xk)，k=1,2，…，n。

3)获得显著图。利用获得的超像素排序向量获得相应的显著目标得分ft(xk)，fb(xk)，fl(xk)，fr(xk)，k=1,2，…，n，并通过式(8)获得初始显著目标得分F1(xk)，通过F1(xk)×255将其映射到灰度图像中，得到初始显著图S1(xk)。

4)目标和背景标记。参照初始显著图对原始图像添加目标和背景标记，并将目标标记的超像素指示向量y+=[y1y2…yp]标记为1，并将背景标记的超像素指示向量y-=[y1y2…yq]标记为-1，其余未标记的超像素指示向量y0标记为0。

5)融合显著图。利用标记信息得到新的显著图S2(xk)，将获得的显著图S2(xk)与初始显著图S1(xk)和按照式(12)融合，得到最终显著图Sz(xk)。

6) 计算自适应阈值。计算灰度k使直方图H(k)在[0,R]取得最大值，获得相邻灰度值ki，kj，令其在区间[k,R]中满足灰度差Lij最大，则阈值T=0.5(ki+kj)；当(R-km)>max(ki-kj)时，阈值T=R。

7) 目标获取。通过阈值公式将融合后的图像二值化，并将二值图中目标部分对应的原始目标部分提取出来得到分割目标。

3实验结果与分析

本文在BSD数据库中选取2组图像进行仿真实验，来验证本文算法的可行性。一组是本文算法对不同特征图像的仿真实验；一组是通过本文算法与GC算法[6]，最大相似合并(maximal similarity based region merging, MSRM)算法[8]比较的仿真实验。实验通过在仿真软件MATLAB2012b上编程实现。

3.1评价指标

本文使用TPR(正确的分割率)和FPR(错误的分割率)2种性能指标来客观评价分割精度[8]。TPR表示实际分割出来的目标轮廓中与理想分割目标轮廓内交集的像素点数目，和理想分割目标轮廓内交集的像素点数目的比值。FPR表示实际分割出来的目标轮廓中属于理想图像背景部分像素的数目，和理想图像背景的像素数目的比值。

3.2仿真实验

先采用SLIC算法对图像进行预分割处理，其中预分割获得超像素数目统一设为450个。本文算法为了获得有效标记信息，其中标记信息是添加在超像素图像中，这样有助于避免错误标记。图2表示本文的算法对不同特征的图像进行分割的结果。其中图2(a)表示原始图像,图2(b)表示添加标记的图像,图2(c)表示理想分割目标,图2(d)表示本文算法的分割结果。从图2看以看出本文算法获得的目标分割结果较好，表1客观定性地列出了本文算法对图2中图像分割获得TPR和FPR，可以看出本文算法分割获得的图像TPR较高，FPR较低。

图2　图像分割结果Fig.2　Image segmentation results

表1列出了图一中各种特征图像的TPR和FPR。

表1图像分割结果性能指标

Table 1The performance measures of the image segmentation

情能指标工人犀牛猩猩老人女生鸟TPR/%95.5894.4596.4998.6292.0193.15FPR/%0.310.180.180.430.060

为了进一步验证本文算法的可行性，这一组实验通过对比本文算法与GC算法、MSRM算法在相同标记信息下的分割结果，并分别使用TPR和FPR从客观角度分析这几种算法的性能。其中，MSRM与本文方法都采用SLIC对其进行预分割处理，其中预分割的超像素数目都为450个。图3表示本文算法与GC，MSRM算法的图像对比分割结果。其中图3(a)表示原始标记图像，图3(b)表示GC算法，图3(c)表示MSRM算法，图3(d)表示本文算法。

图3　图像的分割结果Fig.3　Image segmentation results

从图3可以看出，由于GC算法的局限性，分割效果不是特别理想，分割的目标图像中包含大量的细小背景部分。通过SLIC预处理的MSRM算法，需要对不同特征的目标区域添加有效的标记，获得的分割结果才较为理想，如马的后腿部因为没有添加标记信息，就没有分割出来；老鹰的尾部与树枝颜色及其相似，合并处理的时候该部分区域被认为是背景部分，那么获得的目标就会存在缺失。MSRM对包含的目标内部区域的背景部分很容易将其作为目标部分而合并到目标图像中，如瓶子的手柄部分。部分目标区域也会被合并到背景区域中。最后，从图3可以看出本文获得的目标分割效果较好，同时，本文算法获得的目标部分也包含少量背景部分，是因为图像预分割的SLIC算法将部分边界的目标部分与图像背景部分颜色相似的区域分为同一个超像素，超像素作为一个整体分割会导致小部分边界不光滑。表2列出来图3中3种算法的TPR和FRP值。图中MSRM和本文算法对蘑菇的分割具有相同的TPR和FPR，这是因为它们是以相同超像素作为处理对象。最后计算了3种算法的平均TPR和FPR，可以看出本文算法具有较高的TPR和较低FPR，优于GC、MSRM算法，有效验证了本文算法的可行性。

表2对比图像的分割结果性能指标

Table 2The contrast of the image segmentation result performance indicators

图像算法TPR/%FPR/%老鹰GC91.505.98MSRM90.200.06本文算法95.310.12马GC85.0917.41MSRM85.730.15本文算法88.240.15黑熊GC94.571.60MSRM98.831.29本文算法98.401.21树懒GC90.2312.40MSRM86.700.40本文算法88.800.58蘑菇GC92.941.19MSRM97.780.29本文算法97.780.29瓶子GC95.850.45MSRM98.931.48本文算法98.680.33GC(均值)91.706.51MSRM(均值)92.980.61本文方法(均值)94.530.45

4结束语

将显著性目标检测用于图像分割中，往往图像中一些属于背景中突出部分被检测出来，而目标部分则被抑制，利用这样的显著图往往难以获得目标的有效分割。为了解决上述问题，本文利用边界先验对超像素进行流形排序获得初始显著图，随后适当利用初始显著图来指导标记，通过交互的方式重新对超像素进行流形排序获得显著图，并将交互获得的显著图与初始显著图融合得到背景与目标差异较大的显著图，然后利用自适应的阈值分割获得目标有效分割。在本文算法中，利用初始先验显著图的指导能减少无效标记的次数，降低交互操作的繁琐性，最后融合初始显著图和利用交互获得的显著图，能有效突出整体部分，抑制背景部分。同时，本文使用SLIC算法对图像进行预处理，SLIC算法本身存在一定的局限性，在复杂边界区域容易将小部分目标和背景部分作为一个超像素，而本文算法是针对超像素的整体处理，最后获得的目标分割可能边界会存在不光滑现象，后期研究希望对这方面问题进行有效改善。

参考文献:

[1]MORTENSEN E, MORSE B, BARRETT W, et al. Adaptive boundary detection using ‘live-wire’ two-dimensional dynamic programming[C]//Proceedings of Computers in Cardiology. Durham, North Carolina, UK, 1992: 635-638.

[2]HE Huiguang, TIAN Jie, LIN Yao, et al. A new interactive segmentation scheme based on fuzzy affinity and live-wire[C]//Proceedings of the 2ndInternational Conference on Fuzzy Systems and Knowledge Discovery. Changsha, China, 2005: 436-443.

[3]KASS M, WITKIN A, TERZOPOULOS D. Snakes: Active contour models[J]. International journal of computer vision, 1988, 1(4): 321-331.

[4]GRADY L, FUNKA-Lea G. Multi-label image segmentation for medical applications based on graph-theoretic electrical potentials[C]//Proceedings of the Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis. Prague, Czech Republic, 2004: 230-245.

[5]GRADY L, SINOP A K. Fast approximate random walker segmentation using eigenvector precomputation[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK, USA, 2008: 1-8.

[6]BOYKOV Y Y, JOLLY M P. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[C]//Proceedings of the 8thIEEE International Conference on Computer Vision. Vancouver, BC, Canada, 2001, 1: 105-112.

[7]LI Yin, SUN Jian, TANG C K, et al. Lazy snapping[J]. ACM transactions on graphics (TOG), 2004, 23(3): 303-308.

[8]NING Jifeng, ZHANG Lei, ZHANG D, et al. Interactive image segmentation by maximal similarity based region merging[J]. Pattern recognition, 2010, 43(2): 445-456.

[9]MA Yufei, ZHANG Hongjiang. Contrast-based image attention analysis by using fuzzy growing[C]//Proceedings of the 11thACM International Conference on Multimedia. New York, USA, 2003: 374-381.

[10]GOPALAKRISHNAN V, HU Yiqun, RAJAN D. Salient region detection by modeling distributions of color and orientation[J]. IEEE transactions on multimedia, 2009, 11(5): 892-905.

[11]WEI Yichen, WEN Fang, ZHU Wangjiang, et al. Geodesic saliency using background priors[C]//Proceedings of the 12thEuropean Conference on Computer Vision. Florence, Italy, 2012: 29-42.

[12]YANG Chuan, ZHANG Lihe, LU Huchuan, et al. Saliency detection via graph-based manifold ranking[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Portland, OR, USA, 2013: 3166-3173.

[13]ACHANTA R, SHAJI A, SMITH K, et al. SLIC superpixels, Technical Report on 149300[R]. EPFL, Lausanne, Switzerland, 2010.

[14]ZHOU Dengyong, WESTON J, GRETTON A, et al. Ranking on data manifolds[J]. Advances in neural information processing systems, 2004, 16: 169-176.

[15]ZHOU D, BOUSQUET O, LAL T N, et al. Learning with local and global consistency[J]. Advances in neural Information processing systems, 2004, 16: 321-328.

[16]ARBELAEZ P, FOWLKES C, MARTIN D. A database of human segment natural images and its application to evaluating segmentation algorithms and measuring ecological statistics [C]// Poceeding of the 18th International Conference on Computer Vision,Vancouver,B.C., Canada, 2001,416-423.

Interactive image segmentation based on manifold ranking

ZENG Xianhua1,2, YI Ronghui1,2, HE Shanshan1,2

(1. College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing 400065, China; 2. Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunication, Chongqing 400065, China)

Abstract：The unsatisfactory results of salient object detection have made object segmentation difficult. In this study, we obtain accurate object segmentation by combining effective interactive information under the guidance of an initial saliency map. This method obtains the original saliency map using priori boundaries of the manifold ranking of the superpixels, and based on the obtained saliency map, marks the object labels of the non-salient object parts and the background labels of the salient background parts. Next, the superpixels for generating the new saliency map are re-sorted by manifold ranking with label information, and the newly obtained and original saliency maps are merged. Finally, object segmentation is achieved by adopting the adaptive threshold method for the merged saliency map. Image segmentation experiments with images from the Berkeley segmentation dataset (BSD) image database demonstrate that the proposed method can correctly segment objects from images and that the true positive rate (TPR) and the false positive rate (FPR) results are better than those achieved using the classical maximal similarity-based region merging (MSRM) image segmentation algorithm.

Keywords：manifold ranking; interactive image segmentation; saliency object; object detection; saliency map; background label; object label

DOI:10.11992/tis.201505037

收稿日期：2015-05-19. 网络出版日期：2015-12-29.

基金项目：国家自然科学基金重点资助项目 (U1401252)；国家自然科学基金资助项目 ( 61075019, 61379114) ;重庆市基础与前沿研究计划资助项目 (cstc2015jcyjA40036).

通信作者：曾宪华. E-mail：xianhuazeng2005@163.com.

中图分类号：TP319.4

文献标志码：A

文章编号：1673-4785(2016)01-0117-07

作者简介：

曾宪华，男，1973年生，副教授，博士，中国计算机学会会员，主要研究方向为流形学习、计算机视觉等。主持国家自然科学基金、重庆自然科学基金等省级以上项目3项。发表学术论文30余篇。

易荣辉，男，1988年生，硕士研究生，主要研究方向为流形学习、图像分割等。

何姗姗，女，1992年生，硕士研究生，主要研究方向为流形学习、图像分割等。

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20151229.0837.012.html