基于马氏距离和模糊C均值聚类的抠图算法与应用

第36卷第5期 北京科技大学学报 Vol.36 No.5 2014年5月 Journal of University of Science and Technology Beijing May 2014 基于马氏距离和模糊C均值聚类的抠图算法与应用 张 敏”，闵乐泉2，张群，刘飒动回 1)北京科技大学数理学院，北京1000832)北京科技大学自动化学院，北京100083 3)北京农学院计算机科学系，北京102206 ☒通信作者，Emai:liusa@bae.cdu.cn 摘要基于马氏距离和模糊C均值聚类算法提出了一种数字彩色图像抠图算法.该算法首先对彩色图像像素的红绿蓝三 种彩色分量进行正则化处理：然后在正则化图像背景中选取适当的掩膜作为样本集，计算各像素与样本集之间的马氏距离： 再利用模糊C均值聚类算法对计算出的马氏距离进行分类：最后利用填洞操作提高抠图质量.对八幅彩色数字图像进行对比 实验，结果显示本算法可以自动抠图，且结果优于马氏距离算法、Grow-Cut算法和正则化线性回归算法的相应抠图效果. 关键词图像抠图：马氏距离：模糊C均值聚类：填洞 分类号TP391 Matting algorithm and application based on Mahalanobis distance and the fuzzy C-means clustering algorithm ZHANG Min,MIN Le-quan',ZHANG Qun2,LIU Sa 1)School of Mathematics and Physics,University of Science and Technology Beijing,Beijing 100083,China 2)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 3)Department of Computer Science,Beijing University of Agriculture,Beijing 102206.China Corresponding author,E-mail:liusa@bac.edu.cn ABSTRACT Based on Mahalanobis distance and the fuzzy C-means algorithm,this article introduces a digital color image matting algorithm.First the red,green and blue color components of color image pixels are normalized.Second the appropriate mask as a sample set is selected in the background of the normalized image,and the Mahalanobis distance between each pixel and the sample set is calculated.Third the calculated Mahalanobis distances are classified into two categories using the fuzzy C-means clustering algorithm:the foreground and the background.Finally,the quality of the matting is improved using the filling-hole technique.Eight images have been processed for comparison,the results show that this algorithm can automatically segment these images,and is better than the Mahalanobis distance algorithm,fuzzy C-means clustering algorithm and linear regression algorithm. KEY WORDS image matting:Mahalanobis distance;fuzzy C-means clustering algorithm:filling-holes 数字抠图是一种将图像的前景部分从背景中分 数字抠图问题首先是由Porter和Dufr提出 离出来的技术，其目的之一是把前景物体从图像中 的.现今流行的众多抠图算法需要用户交互来实 提取出来并与其他图像合成新的图像.它通过用户 现-.用户首先选择图像的部分目标前景和背景 指定的图像中部分前景和背景区域，根据指定的区 区域，然后通过所选区域精确分割图像的前景 域信息按照一定的判定规则准确地分离出前景物 数字抠图已经成为了计算机视觉与图像处理的 体口.数字抠图己广泛应用在视频处理和影视制作 焦点.近年来，一些研究者在该领域做了深入的研 等领域回 究，提出了一系列数字抠图算法.吴玉娥等提出 收稿日期：201302-27 基金项目：国家自然科学基金资助项目(61074192)：北京市教有委员会科学研究基金资助项目(KM201110020013) DOI:10.13374/j.issn1001-053x.2014.05.018:http://journals.ustb.edu.cn

第 36 卷 第 5 期 2014 年 5 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 5 May 2014 基于马氏距离和模糊 C 均值聚类的抠图算法与应用 张 敏1) ，闵乐泉1，2) ，张 群2) ，刘 飒3)  1) 北京科技大学数理学院，北京 100083 2) 北京科技大学自动化学院，北京 100083 3) 北京农学院计算机科学系，北京 102206  通信作者，E-mail: liusa@ bac． edu． cn 摘 要 基于马氏距离和模糊 C 均值聚类算法提出了一种数字彩色图像抠图算法． 该算法首先对彩色图像像素的红绿蓝三 种彩色分量进行正则化处理; 然后在正则化图像背景中选取适当的掩膜作为样本集，计算各像素与样本集之间的马氏距离; 再利用模糊 C 均值聚类算法对计算出的马氏距离进行分类; 最后利用填洞操作提高抠图质量． 对八幅彩色数字图像进行对比 实验，结果显示本算法可以自动抠图，且结果优于马氏距离算法、Grow-Cut 算法和正则化线性回归算法的相应抠图效果． 关键词 图像抠图; 马氏距离; 模糊 C 均值聚类; 填洞 分类号 TP 391 Matting algorithm and application based on Mahalanobis distance and the fuzzy C-means clustering algorithm ZHANG Min1) ，MIN Le-quan1，2) ，ZHANG Qun2) ，LIU Sa3)  1) School of Mathematics and Physics，University of Science and Technology Beijing，Beijing 100083，China 2) School of Automation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China 3) Department of Computer Science，Beijing University of Agriculture，Beijing 102206，China  Corresponding author，E-mail: liusa@ bac． edu． cn ABSTＲACT Based on Mahalanobis distance and the fuzzy C-means algorithm，this article introduces a digital color image matting algorithm． First the red，green and blue color components of color image pixels are normalized． Second the appropriate mask as a sample set is selected in the background of the normalized image，and the Mahalanobis distance between each pixel and the sample set is calculated． Third the calculated Mahalanobis distances are classified into two categories using the fuzzy C-means clustering algorithm: the foreground and the background． Finally，the quality of the matting is improved using the filling-hole technique． Eight images have been processed for comparison，the results show that this algorithm can automatically segment these images，and is better than the Mahalanobis distance algorithm，fuzzy C-means clustering algorithm and linear regression algorithm． KEY WOＲDS image matting; Mahalanobis distance; fuzzy C-means clustering algorithm; filling-holes 收稿日期: 2013--02--27 基金项目: 国家自然科学基金资助项目( 61074192) ; 北京市教育委员会科学研究基金资助项目( KM201110020013) DOI: 10． 13374 /j． issn1001--053x． 2014． 05． 018; http: / /journals． ustb． edu． cn 数字抠图是一种将图像的前景部分从背景中分 离出来的技术，其目的之一是把前景物体从图像中 提取出来并与其他图像合成新的图像． 它通过用户 指定的图像中部分前景和背景区域，根据指定的区 域信息按照一定的判定规则准确地分离出前景物 体［1］． 数字抠图已广泛应用在视频处理和影视制作 等领域［2］． 数字抠图问题首先是由 Porter 和 Duff［3］ 提出 的． 现今流行的众多抠图算法需要用户交互来实 现［4--6］． 用户首先选择图像的部分目标前景和背景 区域，然后通过所选区域精确分割图像的前景． 数字抠图已经成为了计算机视觉与图像处理的 焦点． 近年来，一些研究者在该领域做了深入的研 究，提出了一系列数字抠图算法． 吴玉娥等［7］提出

第5期 张敏等：基于马氏距离和模糊C均值聚类的抠图算法与应用 ·689· 了简单笔画抠图算法；Fan等网提出了一种笔画跟 景作为两个未知样本集，先选定一个已知部分的背 踪数字抠图算法；Wang和Fei提出了利用模糊C 景B(明显是背景的一部分)作为背景样本集.通过 均值聚类分割核磁共振脑图像算法：He等o提出 计算包含着未知前景和背景P\B={x∈PIxB} 了图像快速抠图算法：刘濛等u提出了基于Kalman 中像素与背景样本集B之间的马氏距离，将图像P 滤波器的随机游走算法；Kannan等提出了模糊C 的前景和背景区分出来.具体计算第i个元素与背 均值聚类(FCM)分割动态反向增强胸片算法；Vezh- 景样本集之间的马氏距离计算过程如下. nevets和Konouchine提出了多标签分割n维图像 设P为含有n个像素的彩色图像，第i个像素 Gow-Cut算法：康家银等提出了改进的模糊C均 的亮度值表示为(XB.i XG.ix,i).设BCP为含有l 值聚类分割图像算法 个像素已知部分背景的样本集，P\B为包含未知前 尽管抠图技术已经取得了很大的成功，但自动、 景和背景的样本集.定义 精确且省时的图像抠图算法仍然是一个具有挑战性 的难题.例如：文献14]所述抠图细节具有细长结 XG.1 TXR.k XG.k1 XB.k1 . B= 构的丢失；文献5]中算法则容易造成较大的采样 误差，从而影响到整个算法的性能 B,n XB.k 基于上述问题，本文提出了一种基于马氏距 (1) 离和模糊C均值聚类的彩色数字图像自动抠图 ug meanx.,x., (NM-FCM)算法，并与马氏距离算法、Grow-Cut算法 uc meanxc., 和正则化线性回归算法闭的抠图结果进行了比较. ug=mean{xg.k,xg.b’…,xg.} (2) 本文第1节介绍马氏距离：第2节介绍基于彩 色图像正则化(normlized)的马氏距离(Mahalanobis 则第i个像素马氏距离的平方定义为 distance)和模糊C均值(fuzzy C-means)聚类抠图算 XB.i -LR 法，为方便表述本文将此算法简记为NMF℃M;第3 D()= XG.i -LG cov (B) -1 xc.i-uc 节将本文算法与其他三种抠图算法的抠图结果进行 XB,i一LB XB,i一B 对比，该算法的应用性也在本节进行了相关介绍；第 i=1,2,…,n (3) 4节对本文进行总结. 其中，cov(B)代表B的协方差矩阵.关于马氏距离 D()的原始定义及其统计学解释请见文献16]和 1 马氏距离及其计算 Matlab R2011b马氏函数mahal的解释 马氏距离是由Mahalanobis在1936年提出的. 图1(a)是一幅具有188×281像素的果树害虫 它描述了数据间的相关性，是一种有效计算两个未 彩色图像，图1(b)是该图的前景图像.计算该图像 知样本集相似度的方法.如果将图像P的前景和背 的马氏距离步骤如下. 图1原始图像P(a)、前景图像P。(b)和掩膜B(c) Fig.1 Original color image P(a),foreground image Po(b)and mask B(c) (1)从背景中选择一块50×50像素大小的样 害虫图像P中各像素的马氏距离。 本集（掩膜）B(图1(c)中的白色矩阵). (4)设定马氏距离阈值T,若原始图像第(i,) (2)将掩摸B各像素的红、绿和蓝三个亮度值 点像素对应的马氏距离大于阈值T时，则将该像素 按列矩阵形式排成向量YR、Y。和Yg,分别计算这三 归为前景：否则归为背景 个向量的均值uRHc和ug: (5)通过反复试验，当取阈值T为550时，视觉 (3)由式(3)计算得到D(i).图2(a)为果树 抠图效果最好（见图2(b))

第 5 期 张 敏等: 基于马氏距离和模糊 C 均值聚类的抠图算法与应用 了简单笔画抠图算法; Fan 等［8］提出了一种笔画跟 踪数字抠图算法; Wang 和 Fei［9］提出了利用模糊 C 均值聚类分割核磁共振脑图像算法; He 等［10］提出 了图像快速抠图算法; 刘濛等［11］提出了基于Kalman 滤波器的随机游走算法; Kannan 等［12］提出了模糊 C 均值聚类( FCM) 分割动态反向增强胸片算法; Vezh￾nevets 和 Konouchine［5］提出了多标签分割 n 维图像 Grow-Cut 算法; 康家银等［13］提出了改进的模糊 C 均 值聚类分割图像算法． 尽管抠图技术已经取得了很大的成功，但自动、 精确且省时的图像抠图算法仍然是一个具有挑战性 的难题． 例如: 文献［14］所述抠图细节具有细长结 构的丢失; 文献［15］中算法则容易造成较大的采样 误差，从而影响到整个算法的性能． 基于上述问题，本文提出了一种基于马氏距 离［16］和模糊 C 均值聚类的彩色数字图像自动抠图 ( NM-FCM) 算法，并与马氏距离算法、Grow-Cut 算法 和正则化线性回归算法［17］的抠图结果进行了比较． 本文第 1 节介绍马氏距离; 第 2 节介绍基于彩 色图像正则化( normlized) 的马氏距离( Mahalanobis distance) 和模糊 C 均值( fuzzy C-means) 聚类抠图算 法，为方便表述本文将此算法简记为 N-M-FCM; 第 3 节将本文算法与其他三种抠图算法的抠图结果进行 对比，该算法的应用性也在本节进行了相关介绍; 第 4 节对本文进行总结． 1 马氏距离及其计算 马氏距离是由 Mahalanobis 在 1936 年提出的． 它描述了数据间的相关性，是一种有效计算两个未 知样本集相似度的方法． 如果将图像 P 的前景和背 景作为两个未知样本集，先选定一个已知部分的背 景 B( 明显是背景的一部分) 作为背景样本集． 通过 计算包含着未知前景和背景 P \B = { x∈P | xB} 中像素与背景样本集 B 之间的马氏距离，将图像 P 的前景和背景区分出来． 具体计算第 i 个元素与背 景样本集之间的马氏距离计算过程如下． 设 P 为含有 n 个像素的彩色图像，第 i 个像素 的亮度值表示为( xＲ，i xG，i xB，i ) ． 设 BP 为含有 l 个像素已知部分背景的样本集，P \B 为包含未知前 景和背景的样本集． 定义 P = xＲ，1 xG，1 xB，1    xＲ，n xG，n xB，        n ，B = xＲ，k1 xG，k1 xB，k1    xＲ，kl xG，kl xB，k          l  ， ( 1) μＲ = mean{ xＲ，k1 ，xＲ，k2 ，…，xＲ，kl } ， μG = mean{ xG，k1 ，xG，k2 ，…，xG，kl } ， μB = mean{ xB，k1 ，xB，k2 ，…，xB，kl } ． ( 2) 则第 i 个像素马氏距离的平方定义为 D( i) = xＲ，i － μＲ xG，i － μG xB，i － μ          B  T cov( B) － 1 xＲ，i － μＲ xG，i － μG xB，i － μ          B  ， i = 1，2，…，n． ( 3) 其中，cov( B) 代表 B 的协方差矩阵． 关于马氏距离 D( i) 的原始定义及其统计学解释请见文献［16］和 Matlab Ｒ2011b 马氏函数 mahal 的解释． 图 1( a) 是一幅具有 188 × 281 像素的果树害虫 彩色图像，图 1( b) 是该图的前景图像． 计算该图像 的马氏距离步骤如下． 图 1 原始图像 P( a) 、前景图像 P0 ( b) 和掩膜 B( c) Fig． 1 Original color image P( a) ，foreground image P0 ( b) and mask B( c) ( 1) 从背景中选择一块 50 × 50 像素大小的样 本集( 掩膜) B( 图 1( c) 中的白色矩阵) ． ( 2) 将掩摸 B 各像素的红、绿和蓝三个亮度值 按列矩阵形式排成向量 YＲ、YG 和 YB，分别计算这三 个向量的均值 μＲ、μG 和 μB ． ( 3) 由式( 3) 计算得到 D( i) ． 图 2( a) 为果树 害虫图像 P 中各像素的马氏距离． ( 4) 设定马氏距离阈值 T，若原始图像第( i，j) 点像素对应的马氏距离大于阈值 T 时，则将该像素 归为前景; 否则归为背景． ( 5) 通过反复试验，当取阈值 T 为 550 时，视觉 抠图效果最好( 见图 2( b) ) ． · 986 ·

·690· 北京科技大学学报 第36卷 然而，阈值T是人工实验得到的，而非理论分 描述一种基于马氏距离和模糊C均值聚类阁算法 析结果.为得到更好的抠图效果，本文将在第3节 组合的自动抠图新算法. (a) (b) 2000 1500 1000 400 500 300 200 100 200 100 300 0 图2(a)原始图像P的马氏距离：(b)取马氏距离的阈值T=550后的抠图结果 Fig.2 (a)Mahalanobis distances for image P:(b)matted image from image P when the threshold T=550 2 N-M-FCM算法 B,B2]T=（BB)-1BY,其中y:=B。+BG+ B,B,(i=1,2,…,m),Y=12…y)] 本文提出的N-MFCM算法属于无监督分类方 在文献7]中用上述方法成功对医学口腔图 法.它将原图像自动分成前景和背景两部分，从而 像的牙齿与牙龈进行了分割，但该方法对类似 达到自动抠图的目的. 图1(a)中前景和背景正则化后不具有较好的线性 首先将图像P的像素(i,)亮度值的红绿蓝三 性的昆虫图像分割效果不理想.在此基础上，本文 个分量R(i,j)、G(i,)和B(i,)进行正则化处理. 发现对于此类图像用基于马氏距离和模糊C均值 令(i,》、C(i,》和B(i,》分别为R(i,》、G(i,》和 聚类算法可以提高分割效果 B(i,》的方向余弦. 模糊C均值聚类算法首先是由Bezdek⑧提出 的.它是一种逐步迭代的算法，每步迭代都沿着目 (i,》= R(i,》 (4) √R(i,》2+G(i,j》2+B(i,》2 标函数减小的方向进行.该算法主要是通过提前设 定划分类数c(2≤c≤n),当目标函数达到最小时得 G(i,j》= G(i,》 (S) 到最佳聚类，从而得到目标的一个模糊划分 VR(i,》'+G(i)2+B(i,) 设X={x1,x2,…,x}是图像P的特征数据集， B(i,）= B(i,) n是图像像素个数.x:是第i个像素的马氏距离. 6) √R(i,j》)2+G(i,)2+B(i,)2 将计算得到的马氏距离划分为c类，得到X的一个 将原图像P像素(i,)处的亮度值(R(i,j), 模糊c划分，通过求目标函数的最小值，以得到最佳 聚类.N-MFCM方法的目标函数表示如下回： G(i,》,B(i,))用((i,》,C(i,》,B(i,j》)替换， 得到的图像称为P的正则化图像.假设图像背景正 J=∑∑%(x-)2 (8) 则化的亮度值R(i,》、(i,j)和B(i,j)近似地满足 式中：uu是第l个像素隶属于第k类的程度，且满足 一个平面方程： 约束条件 R=B。+BC+B,B. (7) (9) 取具有m个像素的背景样本区域B.为便于表 召=1（对于任意的》： 述，将样本区域的亮度矩阵表示为 U={uu}为隶属度矩阵；m表示加权指数；V={, 2,…,}是聚类中心 「R G B 用模糊C均值聚类算法对一特定的待掘图像 B= 进行c聚类掘图意指：假设图像背景像素的马氏距 LR G B 离值可归为一类，而前景的像素的马氏距离值可分 通过线性回归，式(7)中的拟合系数B=B。: 为c-1类.目标函数达到最小值得到各类的中心

北 京 科 技 大 学 学 报 第 36 卷 然而，阈值 T 是人工实验得到的，而非理论分 析结果． 为得到更好的抠图效果，本文将在第 3 节 描述一种基于马氏距离和模糊 C 均值聚类［18］算法 组合的自动抠图新算法． 图 2 ( a) 原始图像 P 的马氏距离; ( b) 取马氏距离的阈值 T = 550 后的抠图结果 Fig． 2 ( a) Mahalanobis distances for image P; ( b) matted image from image P when the threshold T = 550 2 N-M-FCM 算法 本文提出的 N-M-FCM 算法属于无监督分类方 法． 它将原图像自动分成前景和背景两部分，从而 达到自动抠图的目的． 首先将图像 P 的像素( i，j) 亮度值的红绿蓝三 个分量 Ｒ( i，j) 、G( i，j) 和 B( i，j) 进行正则化处理． 令 Ｒ 槇( i，j) 、G 槇( i，j) 和 B 槇( i，j) 分别为 Ｒ( i，j) 、G( i，j) 和 B( i，j) 的方向余弦． Ｒ 槇( i，j) = Ｒ( i，j) Ｒ( i，j) 2 + G( i，j) 2 槡 + B( i，j) 2 ， ( 4) G 槇( i，j) = G( i，j) Ｒ( i，j) 2 + G( i，j) 2 槡 + B( i，j) 2 ， ( 5) B 槇( i，j) = B( i，j) Ｒ( i，j) 2 + G( i，j) 2 槡 + B( i，j) 2 ． ( 6) 将原图像 P 像素( i，j) 处的亮度值( Ｒ ( i，j) ， G( i，j) ，B( i，j) ) 用( Ｒ 槇( i，j) ，G 槇( i，j) ，B 槇( i，j) ) 替换， 得到的图像称为 P 的正则化图像． 假设图像背景正 则化的亮度值 Ｒ 槇( i，j) 、G 槇( i，j) 和 B 槇( i，j) 近似地满足 一个平面方程: Ｒ 槇 = β0 + β1G 槇 + β2B． 槇 ( 7) 取具有 m 个像素的背景样本区域 B． 为便于表 述，将样本区域的亮度矩阵表示为 B = Ｒ1 G1 B1    Ｒm Gm B         m ． 通过线性回归，式( 7) 中的拟合系数 β =［β0， β1，β2］T = ( BT B) － 1 BT Y，其 中 yi = β0 + β1Gi + β2Bi ( i = 1，2，…，m) ，Y =［y1，y2，…，ym) ］T ． 在文献［17］中用上述方法成功对医学口腔图 像的牙齿与牙龈进行了分割，但该方法对类似 图 1( a) 中前景和背景正则化后不具有较好的线性 性的昆虫图像分割效果不理想． 在此基础上，本文 发现对于此类图像用基于马氏距离和模糊 C 均值 聚类算法可以提高分割效果． 模糊 C 均值聚类算法首先是由 Bezdek［18］提出 的． 它是一种逐步迭代的算法，每步迭代都沿着目 标函数减小的方向进行． 该算法主要是通过提前设 定划分类数 c( 2≤c≤n) ，当目标函数达到最小时得 到最佳聚类，从而得到目标的一个模糊划分． 设 X = { x1，x2，…，xn } 是图像 P 的特征数据集， n 是图像像素个数． xi 是第 i 个像素的马氏距离． 将计算得到的马氏距离划分为 c 类，得到 X 的一个 模糊 c 划分，通过求目标函数的最小值，以得到最佳 聚类． N-M-FCM 方法的目标函数表示如下［9］: J = ∑ c k = 1 ∑ n l = 1 um k，l ( xl － vk ) 2 ． ( 8) 式中: ukl是第 l 个像素隶属于第 k 类的程度，且满足 约束条件 ∑ c k = 1 ukl = 1 ( 对于任意的 l) ; ( 9) U = { ukl} 为隶属度矩阵; m 表示加权指数; V = { v1， v2，…，vc} 是聚类中心． 用模糊 C 均值聚类算法对一特定的待掘图像 进行 c 聚类掘图意指: 假设图像背景像素的马氏距 离值可归为一类，而前景的像素的马氏距离值可分 为 c － 1 类． 目标函数达到最小值得到各类的中心 · 096 ·

第5期 张敏等：基于马氏距离和模糊C均值聚类的抠图算法与应用 ·691· V1,V2,…V。和像素P,属于类k的隶属度u,k=1, 的矩阵，即为 2,,c.如u最大，则将像素P1归为第j类.由文 YR.1 yG.1 献9]可得使目标函数达到最小值的有关参数可通 ! (14) 过下式求出： LYR.jx对j YGj对YBxj (10) (5)计算图像P中像素的马氏距离D(x).然 后将所计算的马氏距离排成向量形式X={x1,x2, 4=()(五)· (11) …,xn},这里n=M×N (6)设定聚类数目c=4(通过实验验证聚类数 对uu进行反复迭代，直至‖V+)-V0‖20）迭代终止.此时，目标函数达到最小值，从 (经实验验证，加权指数m值的选取对抠图效果基 而得到最佳聚类. 本无影响)，算法终止阈值ε=10-7 如果图像P中像素P:的马氏距离隶属于j的隶 (7)初始化聚类中心为零矩阵 属度高，则它就属于第j类.下面通过一幅像素个数 (8)随机选择满足步骤(4)条件的隶属度矩阵 为M×N的彩色图像为例，介绍N-MFCM算法. (uu(0)）. (1)选择图像P中一块j×j个像素的掩膜作为 (9)计算目标函数（式(8）). 样本集B. (10)根据式(10)和(11)更新聚类中心和隶属 (2)对图像中每个像素P∈B的坐标进行坐 度函数. 标变换. (11)选取矩阵二范数，如果IV+w-V0I2<e T(i,j)i+(+1)N 运算终止：否则t=t+1,返回步骤(10) (i=1,2,…,Mj=1,2,…,N）. (12) 对图像P利用N-M-FCM算法分割当算法收敛 (3)重新排列图像P矩阵的三个亮度矩阵为 时，即完成对马氏距离向量矩阵D的聚类划分因 (M×W)×3的矩阵： 马氏距离向量矩阵D中的各元素对应原始图像P XR.I XG.1 的每个像素点.从而算法N-M-FCM成功将前景图 (13) 像从原图像中抠出. R,M×N xG,M×N XB.M×N- 从图3(a)可以看到，掘出的前景中存在少量的 式中，(xR4xc.kxg.4)表示由式(12)变换后第k个 孔洞.为了提高抠图效果，利用Matlab命令imfill对 像素的亮度 得到的前景图3(a)进行填洞处理操作.处理结果 (4)类似的，将样本集矩阵B也排成(×j)×3 如图3(b)所示，图3(a)前景中的孔洞已被充填. 图3(a)N-M-FCM算法的抠图结果：(b)加权指数m=3时填洞处理后前景图：(c)加权指数m=4时填洞处理后前景图 Fig.3 (a)Extracted foreground image using N-M-FCM algorithm:(b)reprocessed foreground image when m=3:(c)reprocessed foreground im- age when m =4 3实验模拟 Grow-Cut算法是由Vezhnevets和Konouchine 提出的一种经典的交互式分割算法.用户需要先给 3.1四种抠图算法实验对比 定一些种子点，然后通过细胞机原理将前景图像分 为了进一步说明N-MFCM算法的有效性，本文 割出来.Grow-Cut算法提供了一种合理的分割，但 通过实验与马氏距离算法、Grow-Cut算法和正规 由于受迭代过程中自定义选取点的多少会使分割结 化线性回归算法叨进行比较 果有所限制阿

第 5 期 张 敏等: 基于马氏距离和模糊 C 均值聚类的抠图算法与应用 V1，V2，…Vc 和像素 pl 属于类 k 的隶属度 ukl，k = 1， 2，…，c． 如 ujl最大，则将像素 pl 归为第 j 类． 由文 献［9］可得使目标函数达到最小值的有关参数可通 过下式求出: ukl = [ ∑ c i = ( 1 | xl － vk | | xl － vi ) | 2 ( m － 1 ] ) － 1 ， ( 10) vk = ( ∑ n i = 1 μm kixi ) ( ∑ n i = 1 μm ki ) － 1 ． ( 11) 对 ukl、vk 进行反复迭代，直至‖V( t + 1) － V( t) ‖2 ＜ ε( ε ＞ 0) 迭代终止． 此时，目标函数达到最小值，从 而得到最佳聚类． 如果图像 P 中像素 pi 的马氏距离隶属于 j 的隶 属度高，则它就属于第 j 类． 下面通过一幅像素个数 为 M × N 的彩色图像为例，介绍 N-M-FCM 算法． ( 1) 选择图像 P 中一块 j × j 个像素的掩膜作为 样本集 B． ( 2) 对图像中每个像素 pi，j∈B 的坐标进行坐 标变换． T∶ ( i，j) →i + ( j + 1) N ( i = 1，2，…，M; j = 1，2，…，N) ． ( 12) ( 3) 重新排列图像 P 矩阵的三个亮度矩阵为 ( M × N) × 3 的矩阵: P = xＲ，1 xG，1 xB，1    xＲ，M × N xG，M × N xB，M ×         N ． ( 13) 式中，( xＲ，k，xG，k，xB，k ) 表示由式( 12) 变换后第 k 个 像素的亮度． ( 4) 类似的，将样本集矩阵 B 也排成( j × j) × 3 的矩阵，即为 B = yＲ，1 yG，1 xB，1    yＲ，j × j yG，j × j yB，j ×        j ． ( 14) ( 5) 计算图像 P 中像素的马氏距离 D( xi ) ． 然 后将所计算的马氏距离排成向量形式 X = { x1，x2， …，xn } ，这里 n = M × N． ( 6) 设定聚类数目 c = 4( 通过实验验证聚类数 4 对图像 1( a) 分割效果相对较好) ． 加权指数 m = 3 ( 经实验验证，加权指数 m 值的选取对抠图效果基 本无影响) ，算法终止阈值 ε = 10 － 7 ． ( 7) 初始化聚类中心 V0 为零矩阵． ( 8) 随机选择满足步骤( 4) 条件的隶属度矩阵 ( ukl ( 0) ) ． ( 9) 计算目标函数( 式( 8) ) ． ( 10) 根据式( 10) 和( 11) 更新聚类中心和隶属 度函数． ( 11) 选取矩阵二范数，如果‖V( t + 1) －V( t) ‖2 ＜ ε 运算终止; 否则 t = t + 1，返回步骤( 10) ． 对图像 P 利用 N-M-FCM 算法分割当算法收敛 时，即完成对马氏距离向量矩阵 D 的聚类划分． 因 马氏距离向量矩阵 D 中的各元素对应原始图像 P 的每个像素点． 从而算法 N-M-FCM 成功将前景图 像从原图像中抠出． 从图 3( a) 可以看到，掘出的前景中存在少量的 孔洞． 为了提高抠图效果，利用 Matlab 命令 imfill 对 得到的前景图 3( a) 进行填洞处理操作． 处理结果 如图 3( b) 所示，图 3( a) 前景中的孔洞已被充填． 图 3 ( a) N-M-FCM 算法的抠图结果; ( b) 加权指数 m = 3 时填洞处理后前景图; ( c) 加权指数 m = 4 时填洞处理后前景图 Fig． 3 ( a) Extracted foreground image using N-M-FCM algorithm; ( b) reprocessed foreground image when m = 3; ( c) reprocessed foreground im￾age when m = 4 3 实验模拟 3. 1 四种抠图算法实验对比 为了进一步说明 N-M-FCM 算法的有效性，本文 通过实验与马氏距离算法、Grow-Cut 算法［5］和正规 化线性回归算法［17］进行比较． Grow-Cut 算法是由 Vezhnevets 和 Konouchine［5］ 提出的一种经典的交互式分割算法． 用户需要先给 定一些种子点，然后通过细胞机原理将前景图像分 割出来． Grow-Cut 算法提供了一种合理的分割，但 由于受迭代过程中自定义选取点的多少会使分割结 果有所限制［19］． · 196 ·

·692 北京科技大学学报 第36卷 图4(a)显示了Grow-Cut算法在图像中所选取 (b) 的种子点（由红色点表示）：图4(b)显示了其分割 结果，此分割结果是根据Lankton0所写算法得到. 可以发现选取更多的种子点（图4(c))分割效果没 有太大改善（如图4(d)所示）. 正规化线性回归算法是一种正规化RGB值的 多元线性回归算法.该算法需要在背景中选取 几块掩膜正规化RGB值，然后自动分割图像.此算 法在临床牙菌斑图像处理中m得到应用.图5(a) 显示了所选取的七块背景掩膜，图5(b)显示了正规 化线性回归算法的分割结果. 图4标记较少标签点(a)和较多标签点(b)的原图以及对应的 为了对上述分割算法效果定量评判，本文定义 Grow-Cut分割结果(c,d) 了误分率△来定量评判算法的优劣性.其定义 Fig.4 Original images labeled by small number of pixels (a)and 如下： large number of pixels (b)and their corresponding segmentation re- sults via the Grow-Cut algorithm (c,d) 4-x100 (15) 式中，N。代表所抠出的图像与所给前景图像（见 图1(b))亮度不同像素的个数，N代表前景像素个 数.计算结果列在表1中.数据显示(N-M-FCM) 算法具有更好的分割结果.表2为不同加权指数 N-M-FCM抠图算法分割效果定量比较.因数据模 a (b) 拟显示，当加权指数不同时对N-M-FCM算法抠图 图5原图取七块背景掩膜(：)及对应的正规化线性回归算法分 直观效果无较大差异，限于篇幅本文只将m=3, 割结果(b) m=4,m=5,m=6,m=7几种情况误分率4值列 Fig.5 Original image with seven extracted background areas (a) 在表2中. and corresponding segmentation result by normalized regression (b) 表1不同抠图算法分割效果定量比较 Table 1 Comparison of matting results by different matting algorithms 误分率 N-M-FCM 马氏距离 Grow-Cut标记点少 Grow-Cut标记点多 正规化线性回归 4 3.2149 3.9735 30.1987 31.4148 11.8483 表2 不同加权指数抠图算法分割效果定量比较 图6()为原图6(d)在聚类数n=4时得到的抠图 Table 2 Comparison of matting results by different weights 结果.从四种不同背景昆虫图像处理结果可以看到 误分率 m=3 m=4 m=5 m=6 m=7 本文算法N-M-FCM具有一定的普适性. 3.2149 3.3997 3.4895 3.46543.4052 3.2.2不同种类昆虫图像抠图模拟 为进一步研究本算法的适用性，对农学院所提 3.2算法适用性研究 供其他四类果树害虫进行了抠图实验，抠图结果如 3.2.1不同背景昆虫图像抠图模拟 图7所示.其中图7(e)为原图7(a)在本文所提算 为研究本文算法的适用性，对本文所处理果树 法N-M-FCM下取聚类数n=2,两次分别取掩膜大 害虫在其他四种背景下进行抠图，抠图结果如图6 小为50×50像素和20×20像素得到的抠图结果； 所示.图6(e)为原图6(a)在本文所提算法NM- 图7()为原图7(b)在聚类数n=4,两次分别取掩 FCM下聚类数n=4得到的抠图结果，图6(f)为原 膜大小为45×45像素和5×5像素得到的抠图结 图6(b)在聚类数n=2时得到的抠图结果，图6(g) 果：图7(g)为原图7(c)在聚类是n=3时得到的抠 为原图6(c)在聚类是n=4时得到的抠图结果， 图结果；图7(h)为原图7(d)在聚类数n=3时得到

北 京 科 技 大 学 学 报 第 36 卷 图 4( a) 显示了 Grow-Cut 算法在图像中所选取 的种子点( 由红色点表示) ; 图 4( b) 显示了其分割 结果，此分割结果是根据 Lankton［20］所写算法得到． 可以发现选取更多的种子点( 图 4( c) ) 分割效果没 有太大改善( 如图 4( d) 所示) ． 正规化线性回归算法是一种正规化 ＲGB 值的 多元线性回归算法［17］． 该算法需要在背景中选取 几块掩膜正规化 ＲGB 值，然后自动分割图像． 此算 法在临床牙菌斑图像处理中［17］得到应用． 图 5( a) 显示了所选取的七块背景掩膜，图 5( b) 显示了正规 化线性回归算法的分割结果． 为了对上述分割算法效果定量评判，本文定义 了误 分 率 Δ 来定量评判算法的优劣性． 其 定 义 如下: Δ = N0 N × 100． ( 15) 式中，N0 代表所抠出的图像与所给前景图像( 见 图 1( b) ) 亮度不同像素的个数，N 代表前景像素个 数． 计算结果列在表 1 中． 数据显示( N-M-FCM) 算法具有更好的分割结果． 表 2 为不同加权指数 N-M-FCM 抠图算法分割效果定量比较． 因数据模 拟显示，当加权指数不同时对 N-M-FCM 算法抠图 直观效果无较大差异，限于篇幅本文只将 m = 3， m = 4，m = 5，m = 6，m = 7 几种情况误分率 Δ 值列 在表 2 中． 图 4 标记较少标签点( a) 和较多标签点( b) 的原图以及对应的 Grow-Cut 分割结果( c，d) Fig． 4 Original images labeled by small number of pixels ( a) and large number of pixels ( b) and their corresponding segmentation re￾sults via the Grow-Cut algorithm ( c，d) 图 5 原图取七块背景掩膜( a) 及对应的正规化线性回归算法分 割结果( b) Fig． 5 Original image with seven extracted background areas ( a) and corresponding segmentation result by normalized regression ( b) 表 1 不同抠图算法分割效果定量比较 Table 1 Comparison of matting results by different matting algorithms 误分率 N-M-FCM 马氏距离 Grow-Cut 标记点少 Grow-Cut 标记点多 正规化线性回归 Δ 3. 2149 3. 9735 30. 1987 31. 4148 11. 8483 表 2 不同加权指数抠图算法分割效果定量比较 Table 2 Comparison of matting results by different weights 误分率 m = 3 m = 4 m = 5 m = 6 m = 7 Δ 3. 2149 3. 3997 3. 4895 3. 4654 3. 4052 3. 2 算法适用性研究 3. 2. 1 不同背景昆虫图像抠图模拟 为研究本文算法的适用性，对本文所处理果树 害虫在其他四种背景下进行抠图，抠图结果如图 6 所示． 图 6( e) 为原图 6( a) 在本文所提算法 N-M￾FCM 下聚类数 n = 4 得到的抠图结果，图 6( f) 为原 图 6( b) 在聚类数 n = 2 时得到的抠图结果，图 6( g) 为原图 6 ( c) 在聚类是 n = 4 时得到的抠图结果， 图 6( h) 为原图 6( d) 在聚类数 n = 4 时得到的抠图 结果． 从四种不同背景昆虫图像处理结果可以看到 本文算法 N-M-FCM 具有一定的普适性． 3. 2. 2 不同种类昆虫图像抠图模拟 为进一步研究本算法的适用性，对农学院所提 供其他四类果树害虫进行了抠图实验，抠图结果如 图 7 所示． 其中图 7( e) 为原图 7( a) 在本文所提算 法 N-M-FCM 下取聚类数 n = 2，两次分别取掩膜大 小为 50 × 50 像素和 20 × 20 像素得到的抠图结果; 图 7( f) 为原图 7( b) 在聚类数 n = 4，两次分别取掩 膜大小为 45 × 45 像素和 5 × 5 像素得到的抠图结 果; 图 7( g) 为原图 7( c) 在聚类是 n = 3 时得到的抠 图结果; 图 7( h) 为原图 7( d) 在聚类数 n = 3 时得到 · 296 ·

第5期 张敏等：基于马氏距离和模糊C均值聚类的抠图算法与应用 ·693· d (g) 图6不同背景原图(a~d)及对应的分割结果(e~h) Fig.6 Images of different backgrounds (a-d)and corresponding segmentation results (e-h) (a) e 图7不同昆虫原图(a~d)及对应的分割结果(e~h) Fig.7 Images of different insects (a-d)and corresponding segmentation results (e-h) 的抠图结果.从四种不同昆虫图像抠图结果可以看 Zeng X P,Li J Z.Liu G J.Natural image matting based on 到本文算法N-MFCM仍具有一定的普适性 RWR.Comput Eng Appl,2010.46(25)160 (曾孝平，李金枝，刘国金.基于RWR的自然图像抠图.计算 4结论 机工程应用，2010,46(25)：160) B3]Porter T.Duff T.Compositing digital images.ACM Siggraph (1)背景无需预处理，可以直接进行抠图. Comput Graphics,1984,18(3):253 (2)N-MFCM算法操作简单易行，与交互式算 4]Boykov YY,Jolly MP.Interactive graph cuts for optimal bounda- 法相比，能够实现自动化，处理过程省时，复杂度低 ry and region segmentation of objects in ND images//Proceedings of Eighth IEEE International Conference on Computer Vision.Can- (3)与马氏距离算法、Grow-Cut算法和正规化 ada,2001:105 线性回归算法相比，N-M-FCM算法有更好的抠图效 5]Vezhnevets V,Konouchine V.GrowCut:Interactive multi-abel 果，抠出的图像清晰，基本没有缺失与多余 ND image segmentation by cellular automata Proceedings of (4)N-M-FCM算法具有一定的普适性，对于存 Graphicon.Russia,2005:150 在不同背景且能明显提取不同背景部分样本集的果 6]Lempitsky V,Kohli P,Rother C,et al.Image segmentation with a bounding box prior /Proceedings of IEEE 12th International 树害虫图像均得到了较好的抠图结果 Conference on Computer Vision.Kyoto,09:277 参考文献 7]Wu Y E.He FZ,Zhang S L,et al.A simple stroke-based itera- tive image matting approach.J Image Graphics,2010,15(12): [Lin S Y,Pan R F,Du H,et al.A survey on digital matting.J 1769 Comput Aided Des Comput Graphics,2007,19(4):473 (吴玉娥，何发智，张胜龙，等.一种基于简单笔画交互的迭 (林生佑，潘瑞芳，杜辉，等.数字抠图技术综述。计算机辅 代图像抠图方法.中国图象图形学报，2010,15(12)：1769) 助设计与图形学学报，2007,19(4)：473) [8]Fan J L,Shen X H Wu Y.Scribble tracker:a matting-ased

第 5 期 张 敏等: 基于马氏距离和模糊 C 均值聚类的抠图算法与应用 图 6 不同背景原图( a ～ d) 及对应的分割结果( e ～ h) Fig． 6 Images of different backgrounds ( a － d) and corresponding segmentation results ( e － h) 图 7 不同昆虫原图( a ～ d) 及对应的分割结果( e ～ h) Fig． 7 Images of different insects ( a － d) and corresponding segmentation results ( e － h) 的抠图结果． 从四种不同昆虫图像抠图结果可以看 到本文算法 N-M-FCM 仍具有一定的普适性． 4 结论 ( 1) 背景无需预处理，可以直接进行抠图． ( 2) N-M-FCM 算法操作简单易行，与交互式算 法相比，能够实现自动化，处理过程省时，复杂度低． ( 3) 与马氏距离算法、Grow-Cut 算法和正规化 线性回归算法相比，N-M-FCM 算法有更好的抠图效 果，抠出的图像清晰，基本没有缺失与多余． ( 4) N-M-FCM 算法具有一定的普适性，对于存 在不同背景且能明显提取不同背景部分样本集的果 树害虫图像均得到了较好的抠图结果． 参 考 文 献 ［1］ Lin S Y，Pan Ｒ F，Du H，et al． A survey on digital matting． J Comput Aided Des Comput Graphics，2007，19( 4) : 473 ( 林生佑，潘瑞芳，杜辉，等． 数字抠图技术综述． 计算机辅 助设计与图形学学报，2007，19( 4) : 473) ［2］ Zeng X P，Li J Z，Liu G J． Natural image matting based on ＲWＲ． Comput Eng Appl，2010，46( 25) : 160 ( 曾孝平，李金枝，刘国金． 基于 ＲWＲ 的自然图像抠图． 计算 机工程应用，2010，46( 25) : 160) ［3］ Porter T，Duff T． Compositing digital images． ACM Siggraph Comput Graphics，1984，18( 3) : 253 ［4］ Boykov Y Y，Jolly M P． Interactive graph cuts for optimal bounda￾ry and region segmentation of objects in ND images / / Proceedings of Eighth IEEE International Conference on Computer Vision． Can￾ada，2001: 105 ［5］ Vezhnevets V，Konouchine V． GrowCut: Interactive multi-label ND image segmentation by cellular automata / / Proceedings of Graphicon． Ｒussia，2005: 150 ［6］ Lempitsky V，Kohli P，Ｒother C，et al． Image segmentation with a bounding box prior / / Proceedings of IEEE 12th International Conference on Computer Vision． Kyoto，2009: 277 ［7］ Wu Y E，He F Z，Zhang S L，et al． A simple stroke-based itera￾tive image matting approach． J Image Graphics，2010，15 ( 12) : 1769 ( 吴玉娥，何发智，张胜龙，等． 一种基于简单笔画交互的迭 代图像抠图方法． 中国图象图形学报，2010，15( 12) : 1769) ［8］ Fan J L，Shen X H ，Wu Y． Scribble tracker: a matting-based · 396 ·

·694· 北京科技大学学报 第36卷 approach for robust tracking.IEEE Trans Pattern Anal Mach In- [14]Levin A,Lisehinski D,Weiss Y.A closed form solution to natu- tell,2012,34(8):1633 ral image matting /Proceedings of Computer Vision and Pattern 9]Wang H S,Fei B W.A modified fuzzy C-Means classification Recognition.Washington DC,2008:228 method using a multiscale diffusion filtering scheme.Med Image [15]Guan Y,Chen W,Liang X,et al.Easy matting a stroke based Amal,2009,13(2):193 approach for continuous image matting.Comput Graphics Forum, [10]He K M,Sun J,Tang X 0.Fast matting using large kemel mat- 2006,25(3):567 ting Laplacian matrices /Proceedings of IEEE Computer Vision [16]Mahalanobis P C.On the generalised distance in statistics / and Pattern Recognition (CVPR).Hong Kong,2010:2165 Proceeding of the National Institute of Sciences of India,1936:49 [11]Liu M,Wu C D,Wang L,et al.Method for shadow and occlu- [17]Feng L,Min L Q,Chen M,et al.Dental image segmentation sion based on the improved random walk algorithm.I Comput Ai- based on multiple linear regression correlates with normalized rgb ded Des Comput Graphics,2010,22(1):60 values Proceedings of the IASTED International Conference on (刘濛，吴成东，王力，等.基于改进随机游走算法的阴影与 Imagining and Signal Processing in Health Care and Technology. 遮挡处理方法.计算机辅助设计与图形学学报，2010， Baltimore,2012:83 22(1):60) 18]Bezdek IC.Pattern Recognition with Fuzy Objectire Function Al- [2]Kannan S R,Ramathilagam S,Devi R,et al.Robust kemnel gorithms.New York:Springer US,1981:309 FCM in segmentation of breast medical images.Expert Syst Appl, [19]Chosh P,Antani S K,Rodney L,et al.Unsupervised grow-cut: 2011,38(4):4382 Cellular automata-based medical image segmentations//Proceed- [13]Kang JY,Min LQ.Image segmentation based on weighted fuzzy ings of the first IEEE International Conference on Healtheare Infor C-means clustering accounting for pixel spatial information.J mation,Image and Systems Biology.Washington DC,2011:40 Univ Sci Technol Beijing,2008,30 (9):1072 220]Lankton S.Grow-eut region growing algorithm [/OL].Sharn (康家银，闵乐泉.基于顾及像素空间信息的加权FCM聚类 Lankton Online [2012-10-19].http://www.shawnlankton. 的图像分割.北京科技大学学报，2008,30(9)：1072) com/2008/03 /growcut-segmentation

北 京 科 技 大 学 学 报 第 36 卷 approach for robust tracking． IEEE Trans Pattern Anal Mach In￾tell，2012，34( 8) : 1633 ［9］ Wang H S，Fei B W． A modified fuzzy C-Means classification method using a multiscale diffusion filtering scheme． Med Image Anal，2009，13( 2) : 193 ［10］ He K M，Sun J，Tang X O． Fast matting using large kernel mat￾ting Laplacian matrices / / Proceedings of IEEE Computer Vision and Pattern Ｒecognition ( CVPＲ) ． Hong Kong，2010: 2165 ［11］ Liu M，Wu C D，Wang L，et al． Method for shadow and occlu￾sion based on the improved random walk algorithm． J Comput Ai￾ded Des Comput Graphics，2010，22( 1) : 60 ( 刘濛，吴成东，王力，等． 基于改进随机游走算法的阴影与 遮挡处 理 方 法． 计算机辅助设计与图形学学报，2010， 22( 1) : 60) ［12］ Kannan S Ｒ，Ｒamathilagam S，Devi Ｒ，et al． Ｒobust kernel FCM in segmentation of breast medical images． Expert Syst Appl， 2011，38( 4) : 4382 ［13］ Kang J Y，Min L Q． Image segmentation based on weighted fuzzy C-means clustering accounting for pixel spatial information． J Univ Sci Technol Beijing，2008，30 ( 9) : 1072 ( 康家银，闵乐泉． 基于顾及像素空间信息的加权 FCM 聚类 的图像分割． 北京科技大学学报，2008，30( 9) : 1072) ［14］ Levin A，Lisehinski D，Weiss Y． A closed form solution to natu￾ral image matting / / Proceedings of Computer Vision and Pattern Ｒecognition． Washington DC，2008: 228 ［15］ Guan Y，Chen W，Liang X，et al． Easy matting a stroke based approach for continuous image matting． Comput Graphics Forum， 2006，25( 3) : 567 ［16］ Mahalanobis P C． On the generalised distance in statistics / / Proceeding of the National Institute of Sciences of India，1936: 49 ［17］ Feng L，Min L Q，Chen M，et al． Dental image segmentation based on multiple linear regression correlates with normalized rgb values / / Proceedings of the IASTED International Conference on Imagining and Signal Processing in Health Care and Technology． Baltimore，2012: 83 ［18］ Bezdek J C． Pattern Ｒecognition with Fuzzy Objective Function Al￾gorithms． New York: Springer US，1981: 309 ［19］ Ghosh P，Antani S K，Ｒodney L，et al． Unsupervised grow-cut: Cellular automata-based medical image segmentations / / Proceed￾ings of the first IEEE International Conference on Healthcare Infor￾mation，Image and Systems Biology． Washington DC，2011: 40 ［20］ Lankton S． Grow-cut region growing algorithm ［J/OL］． Shawn Lankton Online ［2012--10--19］． http: / /www． shawnlankton． com /2008 /03 /growcut-segmentation · 496 ·