第41 卷第8 期自动化学报Vol. 41, No. 82015 年8 月ACTA AUTOMATICA SINICA August, 2015基于图割的低景深图像自动分割刘毅1 陈圣磊1 冯国富1 黄兵1 夏德深2摘要结合图割算法, 提出了一种针对低景深(Depth of ¯eld, DOF) 图像的自动分割模型. 首先, 通过改进的点锐度算法得到图像的点锐度图, 并结合图像的颜色特征, 得到一个四维的特征向量. 其次, 通过对图像点锐度图强边缘的计算, 利用图像清晰部分边缘较连续, 模糊部分边缘较弱、连续性较差的特点得到图像初步的前景/背景区域. 然后, 对前景/背景的颜色和点锐度特征进行高斯混合模型(Gaussian mixture model, GMM) 建模, 结合全局、局部自适应的¸ 值, 对图割算法的Shrinkingbias 现象进行改善. 最后, 通过迭代的图割算法对前景/背景区域进行修正. 实验结果表明, 该模型鲁棒性较高, 分割结果更加精确.关键词图割, 低景深, 点锐度图, 高斯混合模型引用格式刘毅, 陈圣磊, 冯国富, 黄兵, 夏德深. 基于图割的低景深图像自动分割. 自动化学报, 2015, 41(8): 1471¡1481DOI 10.16383/j.aas.2015.c140734Automatic Segmentation of Images with Low Depth of Field Based on Graph CutsLIU Yi1 CHEN Sheng-Lei1 FENG Guo-Fu1 HUANG Bing1 XIA De-Shen2Abstract An automatic segmentation model combined with graph cuts algorithm for low depth of ¯eld (DOF) imagesis proposed. Firstly, the point sharpness algorithm is improved to extract the point sharpness map of the image. Incombination with color features, a four dimensional vector is constructed. Secondly, strong edges of the point sharpnessmap are exacted and the characteristics that the edges of clear part of an image are commonly continuous and the edges ofblurred part are weak and discontinuous are used to get the preliminary foreground/background regions. Then, Gaussianmixture model (GMM) is used to model the features of point sharpness and color and by using global and local adaptive¸ the shrinking bias problem of graph cuts algorithm is improved e®ectively. Finally, the iterative graph cuts algorithmis used to revise the foreground/background regions. Experiments show that the proposed segmentation model is morerobust and more accurate.Key words Graph cuts, low depth of ¯eld, point sharpness map, Gaussian mixture model (GMM)Citation Liu Yi, Chen Sheng-Lei, Feng Guo-Fu, Huang Bing, Xia De-Shen. Automatic segmentation of images withlow depth of ¯eld based on graph cuts. Acta Automatica Sinica, 2015, 41(8): 1471¡1481随着数码相机及智能手机的发展, 数码照片的数量也以惊人的速度增长. 低景深拍摄技巧由于能较好地突出主体、虚化背景, 使照片的主题更加明确而被人们广泛使用. 自动提取低景深图像中具有语义特征的对象, 是基于内容的图像检索、基于感兴趣区域(Region of interest, ROI) 的图像压缩等研究领域中一项基础而关键的工作.目前发展出了许多低景深图像自动分割算法,收稿日期2014-10-22 录用日期2015-04-11Manuscript received October 22, 2014; accepted April 11, 2015国家自然科学基金(61473157), 江苏省高校自然科学研究项目(13KJB520013, 14KJB520019) 资助Supported by National Natural Science Foundation of China(61473157) and Natural Science Foundation of the JiangsuHigher Education Institutions of China (13KJB520013, 14KJB520019)本文责任编委封举富Recommended by Associate Editor FENG Ju-Fu1. 南京审计学院工学院南京210094 2. 南京理工大学计算机科学与技术学院南京2100291. School of Technology, Nanjing Audit University, Nanjing210094 2. School of Computer Science and Technology, Nan-jing University of Science and Technology, Nanjing 210029这些算法主要利用了低景深图像的频率分布特性:高频成分主要分布在聚焦区域, 而离焦区域则因为模糊分布较少. Kim[1] 在2005 年提出使用高阶统计量(Higher-order statistics, HOS) 的方法来获取图像的高频分布, 通过形态学滤波, 将图像中四阶矩值高的区域作为种子进行区域合并. 邓小玲等[2] 提出了一种融合HOS、纹理和颜色信息的提取方法. Li等[3] 在2007 年利用高频部分受模糊影响较大的特点, 通过对图像进行二次模糊(Reblur) 得到聚焦显著图(Focused saliency map). Li 等[4] 在2011 年进一步结合灰度变化、颜色及图像的几何特征提取聚焦对象. 由于采用监督学习, 该方法需要大量图像样本作为训练集, 并对前景和背景对比不强的图像难以有效分割. Graf 等[5] 提出的鲁棒的、无参的分割方法将分割过程分成5 个阶段, 分割效果较好, 但算法复杂, 效率较低. Chen 等[6] 提出了幅度谱分解模型, 将低景深图像的幅度谱减去其离焦模糊图像的幅度谱, 得到对应于聚焦对象的高频差分幅度谱,1472 自动化学报41 卷并将其变换回空间域, 得到能定位聚焦对象的聚焦图, 该算法对前景和背景具有相似颜色分布的图像分割效果不佳. Konik 等[7] 提出了基于边缘锐度的方法, 将边缘分为清晰和模糊两类, 并根据边缘的分类结果对图像的Mean Shift 过分割区域进行分类, 分割效果较好, 但分割结果受Canny 边缘检测及Mean Shift 预分割结果的影响较大. Mei 等[8] 提出了基于主动轮廓的低景深图像自动分割模型, 但算法的效率较低, 很难用于实时图像分割.针对上述问题, 本文充分利用图割(Graphcuts)[9¡13] 模型能很好地将图像边缘特征与区域特征结合起来, 并具有全局最优、多特征融合、算法效率高的优良特性, 提出了基于图割的低景深图像自动分割算法. 首先, 通过改进的点锐度算法得到图像的点锐度图, 对每个像素的清晰度进行评价, 并结合图像的颜色特征, 得到一个四维的特征向量. 其次, 通过对图像点锐度图强边缘的计算, 利用图像清晰部分边缘较连续, 模糊部分边缘较弱、连续性较差的特点初步得到图像大致的前景/背景区域. 然后, 对前景/背景的颜色和点锐度特征进行高斯混合模型(Gaussian mixture model, GMM) 建模, 结合全局、局部自适应的¸ 值, 对图割算法的Shrinkingbias 现象进行改善. 最后, 通过迭代的图割算法对前景/背景区域进行逐步修正. 实验结果表明, 本文算法鲁棒性较高, 分割结果更加精确.1 图割模型特点分析图割算法主要用于交互式图像分割, 通过用户指定的前景/背景种子对图像的前景/背景颜色分布进行估计, 从而构造一个包含区域项(数据项) 和边界项(光滑项) 的能量函数, 将图像分割问题转化为求解该能量函数的最小值. 为此, 将图像映射成一个带权图G = (V;E) (V 为顶点;E为边), 将能量函数的全局最优求解转化为对应带权图的最大流/最小割问题. 图割能量函数定义为E(A) = R(A) + ¸B(A) =Xp2PRp(Ap) + ¸Xfp;qg2NBfp;qg ¢ ±(Ap;Aq)(1)其中, ±(Ap;Aq) =(1; 若Ap 6= Aq0; 其他, A 2 f0; 1g为前景/背景标号, N 为相邻像素对, 区域项R(A)用来约束将像素分配到前景/背景的惩罚, 边界项B(A) 用来约束相邻像素应具有相同的标号值, ¸ 调节两者的比重.由于图割算法综合考虑了图像的区域和边界信息, 分割效果通常较好, 但对细长边界进行分割时,特别是当前景和背景颜色相似时, 能量函数主要取决于边界项, 该算法容易产生Shrinking bias 现象,即分割结果趋向于边界少的分割, 如图1 (b) 所示.(a) 图割算法种子标记(a) Markers (seeds) of graph cuts(b) 图割算法分割结果(b) Result of graph cuts(c) 本文算法分割结果(c) Result of our method图1 图割算法中的Shrinking bias 现象Fig. 1 Shrinking bias problem of graph cuts2 基于图割的低景深图像自动分割模型2.1 点锐度图的获取低景深图像前景清晰、背景模糊, 因此要区分前景和背景, 首先必须对图像的清晰度进行评价, 而图像清晰度的高低与边缘处的灰度变化密切相关, 即灰度变化越大、边缘宽度越窄则越清晰(图2). 因此, 可以通过统计图像边缘法向方向的灰度变化来评价. 点锐度算法[14] 统计每个像素点周围灰度的扩散程度, 计算每个像素的8 邻域像素与该像素灰度差的绝对值加权和, 扩散越剧烈, 其值越大, 图像越清晰. Marziliano 等[15] 则将边缘宽度作为图像清晰度的衡量指标, 在垂直边缘点邻域寻找局部极大、极小值, 两者的距离即为边缘宽度.点锐度算法仅考虑了灰度变化的大小, 而忽略了边缘的变化方向及边缘宽度, 通过加权求和容8 期刘毅等: 基于图割的低景深图像自动分割1473易将各个方向均衡变化的点误判为高清晰点, 而Marziliano 等提出的算法则没有考虑边缘的灰度变化大小, 在边缘宽度相同的情况下, 无法区分清晰度的差异. 因此, 本文综合这两种算法, 提出了改进的点锐度算法.(a) 清晰图像及其某行边缘灰度变化(a) Intensity change in an edge of one row ofsharp image(b) 模糊图像及其某行边缘灰度变化(b) Intensity change in an edge of one row ofblurred image图2 清晰图像与模糊图像某行边缘灰度变化Fig. 2 Intensity change in an edge of one row ofsharp or blurred image由于LUV 颜色空间是均匀的色度空间, 色差公式即为LUV 空间下的欧氏距离, 因此首先将图像由RGB 颜色空间变换到LUV 颜色空间, 对亮度分量L 进行点锐度计算. 改进的点锐度算法同样考虑像素的8 邻域, 考虑到边缘的变化方向, 为简化计算,分别对水平、垂直、45±、135± 四个方向计算点锐度:si =jI(bi) ¡ I(ai)jWi(2)其中, i = 0; 1; 2; 3 分别代表四个方向, ai, bi 即为该方向的极大值与极小值, Wi 为边缘宽度. 很显然,当同一方向的三个点灰度变化方向一致时, ai, bi 即为当前像素该方向的两个邻域点, 考虑到权值变化,水平、垂直方向有Wi = 2; 45±、135± 方向有Wi =2p2, 当同一方向三个点灰度变化方向不一致时, 该方向的点锐度值可对相邻点分别计算, 取最大值. 为综合考虑像素的色彩变化, 某一方向的点锐度计算可进一步修改为si =q(Lai ¡ Lbi)2 + (Uai ¡ Ubi)2 + (Vai ¡ Vbi)2Wi(3)对像素p 的点锐度计算, 可取变化最大的方向, 即点锐度公式可定义为Sp = max(spi) (4)对整幅图像进行点锐度计算, 可得到点锐度图S, 如图3 所示.图3 点锐度图Fig. 3 Point sharpness map2.2 种子区域的自动获取图割算法主要用于交互式图像分割, 必须由用户通过交互指定图像的前景/背景种子. 因此, 将图割用于自动图像分割, 必须能够自动获取种子区域.本文利用低景深图像清晰部分边缘较连续, 模糊部分边缘较弱、连续性较差的特点, 自动得到图像大致的前景/背景种子区域, 具体步骤如下.2.2.1 清晰边缘检测对点锐度图S 进行清晰边缘检测, 为使检测到的边缘尽可能封闭, 使用动态双阈值.步骤1. 根据式(5) 及强清晰边缘阈值T 对点锐度图S 进行二值化, 得到强清晰边缘图B (图4 (a)).B(i; j) =(1; S2(i; j) > T0; S2(i; j) · T(5)式中, 阈值的计算如式(6)[16] 所示, M 和N 分别为图像的长和宽.T =4MNMXi=1XNj=1S2(i; j) (6)步骤2. 计算弱清晰边缘阈值T0, 对点锐度图S 进行二值化, 得到弱清晰边缘图B0 (图4 (b)). 为使边缘尽可能完整, 又不引入过多的噪声, 并考虑到低景深图像整体均值较小、标准差较大的特点, 本文采用迭代的方式计算T0.1474 自动化学报41 卷步骤2.1. 计算点锐度图S 的均值m, 标准差¾, 令T0 = T.步骤2.2. 在点锐度图S 中, 去除经阈值T0 二值化(式(5)) 得到的边缘点, 在剩下的点中用式(6)计算新的阈值T0.步骤2.3. 重复步骤2.2, 直到T0 · m + ¾.步骤3. 边缘连接. 根据强清晰边缘图B 中的边缘点, 在弱清晰边缘图B0 中寻找相应点的8 邻域. 若存在相邻点, 则递归进行边缘连接, 得到边缘较完整的图B00 (图4 (c)).(a) 强清晰边缘检测(a) Strong sharp edge detection(b) 弱清晰边缘检测(b) Weak sharp edge detection(c) 边缘连接(c) Edge linking图4 清晰边缘检测Fig. 4 Sharp edge detection2.2.2 形态学处理及边界扫描步骤1. 形态学处理. 为进一步封闭弱边缘, 对图B00 进行形态学闭运算, 如图5 (a) 所示.步骤2. 边界扫描. 进行闭运算后的图B00, 仍可能存在未封闭的边缘, 因此, 常见的孔洞填充操作并不能得到预期的种子区域. 本文通过边界扫描的方法, 对进行闭运算后的图B00 从水平、垂直、45±、135± 四个方向进行边界扫描(扫描线在该方向进行逐行扫描, 保留每行可能遇到的第一个和最后一个边缘点之间的区域), 取四个方向扫描得到的共有区域作为前景种子区域, 剩下的区域即为背景种子区域, 如图5 (b) 所示.(a) 形态学处理(a) Morphological processing(b) 边界扫描(b) Boundary scanning图5 形态学处理及边界扫描Fig. 5 Morphological processing and boundary scanning2.3 能量函数的构造2.3.1 清晰度约束的区域项由图割能量函数(式(1)) 可知, 当前景和背景颜色相似时, 区域项基本不起作用, 能量函数主要由边界项决定, 由于能量函数的最小化, 分割结果趋向于边界少的分割. 为弥补仅依靠颜色特征带来的不足,引入清晰度约束, 对每个像素点p 结合点锐度的计算, 得到一个四维的特征向量Zp = fLp;Up; Vp; Spg,其分布可由GMM 进行描述:f(Z) =XKk=1¼kg(Z; ¹k;§k) (7)式中, ¼k 为混合权重, ¹k 为均值, §k 为协方差矩阵,K 值一般取5, g(¢) 为高斯函数(d 为特征向量的维数):8 期刘毅等: 基于图割的低景深图像自动分割1475g(Z; ¹k;§k) =1(2¼)d2 j§kj12£expµ¡12(Z ¡ ¹k)T§k¡1(Z ¡ ¹k)¶(8)对自动获取的前景和背景种子区域, 分别对其进行GMM 建模[17], 得到式(1) 中的区域项:Rp(Ap) = ¡logXKk=1¼kg(Zp; ¹k;§k) (9)当Ap = 1 时, 取前景的GMM 参数f¼k; ¹k;§kg;当Ap = 0 时, 取背景的GMM 参数.2.3.2 带自适应¸ 值的边界项由于图割算法存在Shrinking bias 现象, 不利于细长边界的分割, Candemir 等[18¡19] 分析了¸ 取值对分割结果的影响: 当¸ 过小时, 分割结果噪声较多; 当¸ 过大时, 会导致细长型边界的缺失. 基于此分析结果, 本文从全局、局部两个角度进行自适应¸值的计算.1) 全局自适应的¸ 值由图割模型特点分析可知, 当前景与背景差异较大时, 分割结果主要由区域项决定, 此时适当减小¸ 的取值, 降低边界项的光滑作用对分割结果影响不大, 反而有利于细长边界的出现. 因此, 为衡量前景和背景的差异性, 计算前景和背景GMM 颜色分量之间的KL 距离[20]:KL(GMMF ;GMMB) =XKk=1¼Fk mini2f1;¢¢¢ ;KgµKL(gFk ; gBi ) + log ¼Fk¼Bi¶(10)式中, F 和B 分别代表前景和背景, gFk 和gBi 分别代表前景GMM 中的第k 个高斯和背景GMM 中的第i 个高斯, 两者之间的KL 距离定义为KL¡gFk ; gBi¢=12µlogj§Bi jj§Fk j+ tr¡(§Bi )¡1(§Fk )¢+¡¹Fk ¡ ¹Bi¢T¡§Bi¢¡1 ¡¹Fk ¡ ¹Bi¢¶(11)KL 距离越大, 意味着前景和背景的颜色分布越不相似, 可进一步减小¸ 的取值, 降低边界项的光滑作用, 保证细长边界的出现. 因此, 全局自适应的¸ 值调节项® 可定义为® =1KL(GMMF ;GMMB)(12)2) 局部自适应的¸ 值Candemir 等[18¡19] 进一步通过局部自适应的¸ 值对边缘像素采取较小的惩罚, 提高了细长边界出现的概率. 基于这一思想, 在清晰度高的像素点降低¸ 的取值, 有利于细长边界的出现, 在清晰度低的像素点提高¸ 的取值, 有利于加强边界项的光滑作用. 为对点清晰度概率进行评价, 需要对点锐度图S根据式(13) 进行归一化处理, 结果如图6 所示.Pp =8><>:1; S2(i; j) ¸ TSpT; S2(i; j) < T(13)图6 点锐度概率图Fig. 6 Point sharpness probability map从图6 可以发现, 鹿角部分清晰度概率较高, 但由于Shrinking bias 现象的存在, 鹿角依然会被割断(图1). 根据前述思想, 在清晰度高的像素点降低¸ 的取值, 提高细长边界出现的概率, 局部自适应的¸ 值调节项¯ 可定义为¯ = 1 ¡11 + e¡°(max(Pi;Pj )¡0:5) (14)引入的sigmoid 函数加强了高清晰部分边界的出现, 而对模糊区域则加强光滑, 参数° > 0 用来调节对清晰度差异的敏感程度(° 越小对清晰度差异越敏感), 使用式(14) 的分割结果如图7 所示.从图7 可以发现, Shrinking bias 现象已有所缓解, 但由于在清晰度高的像素点降低了¸ 的取值, 必然也降低了边界项的光滑作用, 从而导致在鹿角内部也出现了孔洞(图7 (c) 圆圈标注部分), 也带来了噪声(图7 (a)), 而且可以发现分割的前景边界不够干净, 带有和背景交界的背景像素(图7 (c)). 原因在于式(14) 没有考虑点锐度变化方向的影响, 由于在点锐度的计算中, 选取了每个像素8 邻域四个方向中变化最大的方向, 因此, 对相邻的两个像素i 和j, 当像素i 位于背景边缘, 像素j 位于前景边缘, 边eij 处在像素i 的主变化方向上时(图8), 由于此时i和j 的清晰度概率均较高, 按照式(14) 计算将导致像素i 与其邻域像素j1 »j7 的¸ 取值同样会以较高1476 自动化学报41 卷(a) 整体分割结果(a) The whole segmentationresult(b) 局部原始图像(b) Original local image(c) 式(14) 分割结果(c) Result of (14)(d) 本文算法分割结果(d) Result of our method图7 式(14) 的整体与局部分割结果Fig. 7 The whole and local segmentation results of (14)图8 相邻像素及其位置变化Fig. 8 Neighboring pixels and the changes of position的概率Pi 被减小, 显然不利于背景内部像素的光滑,而且对像素j 而言, 其主变化方向在j3 方向, 即像素j 与像素j3 的差异更大, ejj3 上的¸ 取值也应该降低得更多, 而不是与eij 一样. 可见, 必须考虑像素点之间的差异大小.因此, 局部自适应的¸ 值调节项¯ 可调整为¯ = 1 ¡11 + e¡°(Dijmax(Si;Sj;Dij ) max(Pi;Pj )¡0:5)(15)式中, Dij =q(Li ¡ Lj)2 + (Ui ¡ Uj)2 + (Vi ¡ Vj)2为像素i, j 在LUV 色度空间的欧几里得距离, Si,Sj , Pi, Pj 为像素i, j 相应的点锐度值与点锐度概率值.参考文献[11], 边界项可定义为Bfp;qg = e¡kZp¡Zqk22¾2 dist(p; q)¡1 (16)综合式(9)、式(12)、式(15) 和式(16), 式(1)中的能量函数可构造为E(A) =Xp2P¡logXKk=1¼kg(Zp; ¹k;§k) +Xfp;qg2N®¯¸e¡kZp¡Zqk22¾2 dist(p; q)¡1 ¢ ±(Ap;Aq)(17)2.4 本文算法基本步骤本文提出的基于图割的低景深图像自动分割算法框图如图9 所示. 具体步骤如下:步骤1. 计算点锐度图. 对输入图像进行RGB到LUV 的颜色空间转换, 根据式(4) 进行点锐度的计算, 得到点锐度图S.步骤2. 种子区域的自动获取. 通过双阈值及边缘连接对点锐度图S 进行清晰边缘的检测, 形态学闭运算进一步对边缘进行闭合, 由于仍有可能存在不闭合的边界, 因此通过水平、垂直、45±、135± 四个方向的边界扫描获得大致的前景/背景种子区域.步骤3. 图割算法对图像进行分割.步骤3.1. 结合点锐度的计算, 得到一个四维的特征向量Zp = fLp;Up; Vp; Spg, 分别对前景、背景种子区域进行GMM 建模.步骤3.2. 根据式(13) 对点锐度图S 进行归一化处理, 得到点锐度概率Pp.步骤3.3. 迭代分割. 由步骤2 得到的前景/背景种子区域只是一个大致的区域, 并不准确, 借鉴GrabCut 算法非完全标号(Incomplete labeling)的思想进行迭代分割, 逐步提高分割的准确性, 具体过程如下:1) 根据前景、背景种子区域的GMM 模型, 结合式(9) 得到区域项的值;2) 根据式(12) 计算全局自适应的¸ 值调节项®, 根据式(15) 计算局部自适应的¸ 值调节项¯, 并结合式(16) 计算边界项的值;3) 根据区域项和边界项的值构造s-t 网络流图,利用最大流/最小割算法求解能量函数(17) 的最小值, 得到分割结果;4) 利用得到的分割结果更新前景/背景GMM参数;8 期刘毅等: 基于图割的低景深图像自动分割1477图9 算法框图Fig. 9 Block diagram of our algorithm5) 迭代执行1)»4), 直到满足终止条件(本文迭代分割5 次).3 实验结果及分析为验证算法的有效性, 从算法的鲁棒性、分割效果、分割效率三方面分析本文算法的性能. 本文算法的实验平台为: Microsoft Visual Studio 2010,CPU: Intel i5-520 M, RAM 2 GB, 参数均设置为°= 10, ¸ = 210.3.1 鲁棒性分析由于图割算法在前景和背景相似时容易存在分割错误及Shrinking bias 现象, 为验证算法的鲁棒性, 从BSDS500 图像数据库中挑选前景与背景相似度比较大的图像进行测试, 并与文献[1]、文献[3] 和文献[5] 算法的分割结果进行比较. 分割过程如图10 所示. 可以发现: 1) 边界扫描算法的鲁棒性. 部分图像的弱清晰边缘仍然不够连续, 从而导致经过边缘连接后前景物体边界仍未封闭, 形态学闭运算仅能消除小的孔洞, 而边界扫描算法则较好地保留了前景区域的绝大部分. 2) 自动选取的前景种子区域的鲁棒性. 即便种子区域存在部分缺失或多余, 对分割结果依然影响不大, 通过自适应的¸ 值调节边界项的光滑作用及迭代分割, 有效地弥补了种子区域的误差, 并缓解了Shrinking bias 现象. 可见本文算法具有较好鲁棒性, 而其他三个算法对此类图像的分割结果则较差, 容易存在较多的冗余或缺失.3.2 分割效果及分割效率定量分析为进一步验证本文算法的分割效果, 利用文献[4] 提供的测试图像1, 将本文算法与文献[1]、文献[3]、文献[5] 和文献[4] 算法进行对比, 分割结果如图11 所示. 通过各种类型图像的分割结果对比, 可以发现本文算法对细长物体、阴影、弱边缘的分割效果均较好.为对分割效果进行定量比较, 本文将原始图像(图11 (a)) 的分割结果(图11 (b)»11 (f)) 与文献[4] 提供的Ground truth 图像(图11 (g)) 进行比较,用查准率(Precision, P) 和查全率(Recall, R) 作为评价的准则, 比较结果如表1 所示. 由表1 可见, 本文算法的分割效果较好, 平均查准率和查全率均优于其他四个算法.进一步对算法的分割效率进行比较, 由于文献[4] 算法需要进行监督学习, 因此仅与其他三个算法进行比较, 比较结果如表2 所示. 由表2 可见, 由于本文采用图割算法框架(图9), 而图割算法所依赖的最大流/最小割算法可在多项式时间内求解, 例如Boykov 等的改进算法, 最坏情况下的时间复杂度为O(mn2 jCj) (jCj 为所得到的割集的势, m、n 分别为边和顶点的数量), 一定程度上保证了本文算法的效率, 但本文为对分割结果进行逐步修正, 采用了迭代的图割算法, 使得分割时间比文献[1]、文献[3] 有1http://ivipc.uestc.edu.cn/hlli/projects/ ldof test.rar1478 自动化学报41 卷图10 算法的鲁棒性Fig. 10 Robustness analysis of our algorithm图11 各种算法分割结果的比较Fig. 11 Comparison of the results given by di®erent methods8 期刘毅等: 基于图割的低景深图像自动分割1479表1 查准率和查全率对比Table 1 Comparison of precision and recall图像编号文献[1] 算法文献[3] 算法文献[5] 算法文献[4] 算法本文算法P R P R P R P R P R11 0.916 0.999 0.826 0.999 0.97 0.994 0.978 0.988 0.985 0.99258 0.931 0.449 0.929 0.577 0.909 0.508 0.973 0.449 0.995 0.99788 0.824 0.448 0.863 0.554 0.571 0.281 0.799 0.07 0.877 0.988117 0.819 0.91 0.694 0.992 0.836 0.422 0.968 0.744 0.89 0.93980 0.881 0.989 0.769 0.991 0.952 0.482 0.868 0.798 0.951 0.98107 0.976 0.987 0.964 0.909 0.992 0.748 0.994 0.856 0.977 0.977平均0.891 0.797 0.841 0.837 0.872 0.573 0.93 0.651 0.946 0.979表2 分割效率对比(ms)Table 2 Comparison of segmentation e±ciency (ms)图像编号文献[1] 算法文献[3] 算法文献[5] 算法本文算法11 4 191 3 308 29 241 5 70958 3 841 2 436 22 336 5 72688 4 596 3 452 16 407 6 910117 3 303 2 093 9 622 6 58380 3 880 2 566 8 642 7 176107 4 038 2 870 27 769 6 989平均3 975 2 788 19 003 6 516所增加, 但比文献[5] 要少很多.此外, 本文从文献[4] 提供的测试图像库中随机抽取了50 幅图像进行测试, 进一步验证了本文算法的查准率、查全率均较高, 平均耗时6 秒左右, 远低于文献[5] 算法, 与文献[1]、文献[3] 算法耗时较接近, 如图12 所示.3.3 存在问题虽然本文算法具有较好的鲁棒性(见第3.1 节),但当图像的前景部分与图像边框相交, 且相交部分内部较光滑, 不存在强边缘时, 由于本文的边界扫描算法取四个方向扫描得到的共有区域作为前景种子区域, 此时将可能得不到该部分的前景种子, 从而导致分割结果中该部分的缺失, 如图13 所示.4 结论本文提出了一个新的基于图割的低景深图像自动分割模型, 很好地将图像边缘特征与区域特征结合起来. 通过改进的点锐度算法将图像的清晰特征与图像的颜色特征融合, 种子区域的自动获取算法得到图像初步的前景/背景区域, 迭代的图割算法则对前景/背景区域不断进行修正, 模型中引入的全局、局部自适应的¸ 值, 对图割算法的Shrinkingbias 现象进行了改善. 实验结果表明, 本文模型对前景/背景种子的选取具有较高的鲁棒性, 分割结果更加精确. 但本文算法由于迭代分割的缘故, 耗时依然较高, 而随着图像获取设备的进步, 高分辨率图像越来越常见, 如何进一步提高算法的效率, 达到对高分辨率低景深图像的实时分割, 并进一步改进边界扫描算法, 提高算法的实用性, 是我们下一步要重点研究的问题.(a) 平均查准率、查全率对比(a) Comparison of average precision and recall(b) 平均耗时对比(b) Comparison of average running time图12 随机抽取图像对比Fig. 12 Comparison of the results on randomlysampled images1480 自动化学报41 卷(a) 原始图像(a) Original image(b) 本文算法结果(b) Result of our method图13 存在问题Fig. 13 Existing problemReferences1 Kim C. Segmenting a low-depth-of-¯eld image using mor-phological ¯lters and region merging. IEEE Transactions onImage Processing, 2005, 14(10): 1503¡15112 Deng Xiao-Ling, Ni Jiang-Qun, Li Zhen, Dai Fen. Fore-ground extraction from low depth-of-¯eld images based oncolour-texture and HOS features. Acta Automatica Sinica,2013, 39(6): 846¡851(邓小玲, 倪江群, 李震, 代芬. 多特征融合的低景深图像前景提取算法. 自动化学报, 2013, 39(6): 846¡851)3 Li H L, Ngan K N. Unsupervized video segmentation withlow depth of ¯eld. IEEE Transactions on Circuits and Sys-tems for Video Technology, 2007, 17(12): 1742¡17514 Li H L, Ngan K N. Learning to extract focused objects fromlow DOF images. IEEE Transactions on Circuits and Sys-tems for Video Technology, 2011, 21(11): 1571¡15805 Graf F, Kriegel H P, Weiler M. Robust segmentation of rel-evant regions in low depth of ¯eld images. In: Proceedingsof the 18th International Conference on Image Processing.Brussels, Belgium: IEEE, 2011. 2861¡28646 Chen T T, Li H L. Segmenting focused objects based on theamplitude decomposition model. Pattern Recognition Let-ters, 2012, 33(12): 1536¡15427 Konik H, Neverova N. Edge-based method for sharp regionextraction from low depth of ¯eld images. In: Proceedingsof the 2002 International Conference on Visual Communica-tions and Image Processing. San Diego, USA: IEEE, 2012.1¡68 Mei J Y, Si Y L, Gao H J. A curve evolution approach forunsupervised segmentation of images with low depth of ¯eld.IEEE Transactions on Image Processing, 2013, 22(10): 4086¡40959 Boykov Y Y, Jolly M P. Interactive graph cuts for optimalboundary and region segmentation of objects in N-D im-ages. In: Proceedings of the 2001 International Conferenceon Computer Vision. Vancouver, Canada: IEEE, 2001. 105¡11210 Liu Song-Tao, Yin Fu-Liang. The basic principle and its newadvances of image segmentation methods based on graphcuts. Acta Automatica Sinica, 2012, 38(6): 911¡922(刘松涛, 殷福亮. 基于图割的图像分割方法及其新进展. 自动化学报, 2012, 38(6): 911¡922)11 Liu Song-Tao, Wang Hui-Li, Yin Fu-Liang. Interactive shipinfrared image segmentation method based on graph cut andfuzzy connectedness. Acta Automatica Sinica, 2012, 38(11):1735¡1750(刘松涛, 王慧丽, 殷福亮. 基于图割和模糊连接度的交互式舰船红外图像分割方法. 自动化学报, 2012, 38(11): 1735¡1750)12 Zhou H L, Zheng J M, Wei L. Texture aware image seg-mentation using graph cuts and active contours. PatternRecognition, 2013, 46(6): 1719¡173313 Zhang Shi-Hui, Luo Yan-Qing, Kong Ling-Fu. Shadow de-tection based on graph cuts for a single image. Acta Auto-matica Sinica, 2014, 40(10): 2306¡2315(张世辉, 罗艳青, 孔令富. 基于图割的单幅图像影子检测. 自动化学报, 2014, 40(10): 2306¡2315)14 Wang Hong-Nan, Zhong Wen, Wang Jing, Xia De-Shen. Re-search of measurement for digital image de¯nition. Journalof Image and Graphics, 2004, 9(7): 828¡831(王鸿南, 钟文, 汪静, 夏德深. 基图像清晰度评价方法研究. 中国图象图形学报, 2004, 9(7): 828¡831)15 Marziliano P, Dufaux F, Winkler S, Ebrahimi T. Perceptualblur and ringing metrics: application to JPEG2000. SignalProcessing: Image Communication, 2004, 19(2): 163¡17216 Pratt W K. Digital Image Processing. New York: John Wi-ley and Sons, Inc., 1978. 51417 Rother C, Kolmogorov V, Blake A. GrabCut: interactiveforeground extraction using iterated graph cuts. In: Pro-ceedings of the 31st ACM International Conference on Com-puter Graphics and Interactive Techniques. Los Angeles,USA: ACM, 2004. 309¡31418 Candemir S, AkgÄul Y S. Adaptive regularization parameterfor graph cut segmentation. In: Proceedings of the 7th In-ternational Conference on Image Analysis and Recognition.P¶ovoa de Varzim, Portugal: Springer, 2010. 117¡12619 Candemir S, AkgÄul Y S. Statistical signi¯cance based graphcut segmentation for shrinking bias. In: Proceedings of the8th International Conference on Image Analysis and Recog-nition. Burnaby, Canada: Springer, 2011. 304¡3138 期刘毅等: 基于图割的低景深图像自动分割148120 Goldberger J, Gordon S, Greenspan H. An e±cient im-age similarity measure based on approximations of KL-divergence between two Gaussian mixtures. In: Proceedingsof the 10th International Conference on Computer Visionand Pattern Recognition. Nice, France: IEEE, 2003. 487¡493刘毅博士, 南京审计学院讲师. 主要研究方向为图像处理与模式识别. 本文通信作者. E-mail: s worm@163.com(LIU Yi Ph. D., lecturer at NanjingAudit University. His research inter-est covers image processing and patternrecognition. Corresponding author ofthis paper.)陈圣磊博士, 南京审计学院副教授, 澳大利亚莫纳什大学信息技术学院兼职研究员. 主要研究方向为数据挖掘与机器学习. E-mail: tristan chen@126.com(CHEN Sheng-Lei Ph. D., asso-ciate professor at Nanjing Audit Uni-versity, an adjunct research fellow inthe Faculty of Information Technology,Monash University, Australia. His research interest coversdata mining and machine learning.)冯国富博士, 南京审计学院副教授. 主要研究方向为分布式计算, 云计算和计算机审计. E-mail: njufgf@gmail.com(FENG Guo-Fu Ph. D., associateprofessor at Nanjing Audit University.His research interest covers distributedcomputing, cloud computing, and com-puterized auditing.)黄兵博士, 南京审计学院教授. 主要研究方向为智能信息处理.E-mail: hbhuangbing@126.com(HUANG Bing Ph. D., professor atNanjing Audit University. His main re-search interest is intelligent informationprocessing.)夏德深博士, 南京理工大学教授. 主要研究方向为图像处理与模式识别.E-mail: deshen x@263.net(XIA De-Shen Ph. D., professor atNanjing University of Science and Tech-nology. His research interest coversimage processing and pattern recogni-tion.)