第47卷第1期自动化学报Vol.47,No.1 2021年1月ACTA AUTOMATICA SINICA January,2021
一种基于双层框架的仿射类图像抠像方法
姚桂林1,2赵志杰1,2苏晓东1,2辛海涛1,2胡文1,2秦相林1
摘要仿射类抠像方法主要分为KNN(K-nearest neighbor)类和Matting Laplacian类方法，本文结合这2种方法的优点提出了一种基于仿射类的双层次抠像方法.其中，第一层为绝对像素的划分层次或预处理层次，采用了基于KNN类简单权重与相对远距离的搜索方法，并结合初始Trimap未知区域大小无关的方式；第二层为混合像素的计算层次或最终抠像层次，充分利用了第一层计算获得的剩余混合像素的宽度，自适应地调整Matting Laplacian中的颜线性模型所构成颜近邻的核宽度.每个层次均按图像的全局颜重叠程度相应调整合理的搜索范围.本文的实验具备以下特点:1)预处理层次之后采用了若干典型的后续抠像方法，以展现本文方法相比于其他预处理方法对后续抠像操作步骤的优越性和兼容性;2)最终抠像层次引入了若干其他抠像方法，以验证本文抠像方法的优越性.实验表明，相比于其他单层次的仿射类方法，无论对于计算绝对像素还是混合像素，本文方法都可以大幅提升计算结果的准确率.
关键词图像抠像，仿射类抠像,Matting Laplacian,KNN搜索，颜线性模型
引用格式姚桂林，赵志杰，苏晓东，辛海涛，胡文，秦相林.一种基于双层框架的仿射类图像抠像方法.自动化学报,2021, 47(1):209−223
DOI10.16383/j.aas.c180356
开放科学(资源服务)标识码(OSID):
A Hierarchical Framework on Affinity Based Image Matting
YAO Gui-Lin1,2ZHAO Zhi-Jie1,2SU Xiao-Dong1,2XIN Hai-Tao1,2HU Wen1,2QIN Xiang-Lin1
Abstract Affinity based image matting methods can be categorized into KNN(K-nearest neighbor)based matting and matting Laplacian based matting,and this paper raises a hierarchical framework on affinity based matting according to the analyses of the advantages of these two popular affinity based image matting methods.Thefirst opaque pixel classification layer,also named as pre-processing layer,employs a relatively far searching fashion based on simple weights in KNN and is spatial irrelevant to the unknown region of the initial Trimap.The second mixed pixel computation layer,also named asfinal matting layer,adaptively adjusts the kernel size of the color line model in matting Laplacian according to the remaining size of the unknown region.Each layer adjusts proper searching range adaptively according to the overlapping degree between global foreground and background colors.The following distinctions are provided in the experiments.First,several representative matting algorithms are processed after thefirst layer to show the superiority and compatibility of our pre-processing method ov
er other pre-processing methods.Second,several alternative matting methods are also processed after thefirst layer to show the superiority of ourfinal matting method over other matting methods.Experimental results show that our approach can greatly raise the solving precisions for both opaque and mixed pixels.
Key words Image matting,affinity based matting,matting Laplacian,KNN(K-nearest neighbor)searching,color line model
Citation Yao Gui-Lin,Zhao Zhi-Jie,Su Xiao-Dong,Xin Hai-Tao,Hu Wen,Qin Xiang-Lin.A hierarchical framework on affinity based image matting.Acta Automatica Sinica,2021,47(1):209−223
收稿日期2018-05-28录用日期2019-01-02
Manuscript received May28,2018;accepted January2,2019黑龙江省自然科学基金(F2018021,LH2019F044)，哈尔滨商业大学校级科研项目(18XN021,2016TD001)，哈尔滨商业大学青年创新人才支持计划(2019CX02)，黑龙江省哲学社会科学研究规划项目(18GLB029)资助
Supported by Heilongjiang Provincial Natural Science Founda-tion(F2018021,LH2019F044),Technological Project of Harbin University of Commerce(18XN021,2016
TD001),Young Cre-ative Talents Support Project of Harbin University of Commerce (2019CX02),Heilongjiang Provincial Philosophy and Social Sci-ence Planning Project(18GLB029)
本文责任编委刘跃虎
Recommended by Associate Editor LIU Yue-Hu
1.哈尔滨商业大学计算机与信息工程学院哈尔滨150028
2.黑龙
数字图像的抠像与合成问题是在虚拟现实中图像处理领域的两种经典问题，目的是从一幅合成图像中将前景物体从背景中分离出来，并合成到一幅新背景图像中.对于合成问题，对于在数字图像I 中的某个位置i=(x,y)，给定前景图像的颜F i、背景图像颜B i以及一个透明度标量αi∈[0,1],
江省电子商务与信息处理重点实验室哈尔滨150028
1.School of Computer and Information Engineering,Harbin University of Commerce,Harbin150028
2.Heilongjiang Provincial Key Laboratory of Electronic Commerce and Infor-mation Processing,Harbin150028
210自动化学报47卷
其观察到的颜I i 能够用如下抠像公式表示为
I i =αi F i +(1−αi )B i (1)
如果αi =0或αi =1，将点i 称作绝对前景或者绝对背景，并统称为绝对像素.对于其余0<αi <1的点，称为混合像素.
抠像问题为合成问题的逆问题，同时也是欠约束问题：给出各点的合成像素I i ，需要求出未知量F i 、B i 与αi .很多一般背景抠像问题都需要用户提供手工输入的辅助三分图Trimap，如图1(a)和(b)所示，它包括已知绝对前景区域ΩF 和已知绝对背景区域ΩB ，剩余部分为未知区域.于是，依据已知像素，并根据抠像公式及某些先验条件，可以估计未知区域内的每个像素的{F ,α}值.基于Trimap 的图像抠像算法通常分为如下2种方式:1)基于仿射的抠像方法[1−7].该方法并不孤立地计算每个点，而是考虑像素间的相关性，利用间接、迭代的方式递归地求出未知区域中各个点的α值.2)基于采样的抠像方法[8−17].该方法对每个未知点独立从已知区域中选取样本，并采用逐对样本的计算方式，而并不考虑各个像素之间的联系.
本文主要讨论仿射类方法[18].虽然相比仿射类方法，采样类方法的采样位置和采样方式变化较多，而且获取样本方式非常直接，然而，仿射类方法具有以下优势.1)仿射类方法充分强调了像素间的相关性，该
方式也可视为由已知区域向未知区域缓慢、渐进的计算，因此在最终α结果的平滑性以及带给或用户的视觉感受上要明显好于采样类方法.2)采用远距离搜索的仿射类方法对绝对点的计算效果较好，而在事实上，未知区域内的大多数点为绝对像素，因此该类方总体准确率上有较为明显的优势.本文在第1节首先阐述了仿射类方法的2种分类方式以及它们优点和缺点，在第2节中针对KNN 类的特点讨论了绝对像素划分(即预处理)方式，在第3节中针对Matting Laplacian 类的特点讨论了剩余混合像素的计算，并在第4节中讨论了这2类方法各自
的实验结果.最后第5、6节讨论了仿射方法目前存在的问题并得出本文的结论.本文基于仿射方法的双层次抠像框架如图1所示.需要说明的是，由于仿射类方法与采样类方法、乃至其他类如特殊类[19]、深度学习类[20−22]等方法采用完全不同的计算机制，而且本文主要研究前者，因此无论在理论研究和实验数据上，本文并未引入任何其他类方法，而且也不将结果传至α评估系统[23]中，以保持仿射类方法的整体一致性.
1仿射类抠像方法概述
假设每个未知像素的α值是它的K 邻域像素α值α1,α2,···,αK 的线性组合，表示为
αi =w 1α1+···+w j αj +···+w K αK (2)
实际求解中，所有未知点i 的αi 可通过求解如下大型稀疏线性方程得到
(L +θD )α=θb (3)
其中,L 为长与宽均为图像像素总数的稀疏方阵，未知点i 所在行对应K 邻域的系数记为w j ,j =1,···,K ,D 为对角阵，在已知点所对应的对角线元素的位置为1，未知点为0,θ为某个较大的数.b 为长度等于像素总数的列向量，前景ΩF 处位置为1，背景未知区域ΩU 位置为0.上式可采用共轭梯度法求解.
1.1仿射类方法的分类
各仿射类方法、亦即稀疏矩阵L 的构造方式之间的主要区别是每个未知点i 的若干近邻像素位置的远近以及相应权值w j 的构造方式.按是否采用抠像公式以及在抠像中的实际效果，仿射类方法可分为不采用抠像公式的简单权重类方法以及采用抠像公式的Matting Laplacian 类方法.
1.1.1简单权重类方法
该类方法如图2左栏所示,
其特点是不采用抠
图1
图像抠像问题的基本输入输出和本文的双层次抠像结构
Fig.1
Input and output of image matting and the hierarchical framework of our method
1期姚桂林等：一种基于双层框架的仿射类图像抠像方法211
像公式，直接采用颜差异的方法确定权重.具体的，当前点i 与各近邻点j 颜差异的某个负函数即为各个权重，即与j 的颜越接近，权值越大，二者的α越相似.起初的Random Walk 算法[6]仅采用8邻域处最近的搜索范围，但无论在绝对像素还是混合像素，其计算效果均很不理想.Nonlocal 算法[3]对邻域空
间进行了扩展，采用以每个未知点为中心、半径为r 的方形搜索寻K 个颜最相近的点.为减少计算量，采样半径r 通常不大.KNN 算法[4]的搜索距离则更远，需要寻每个点在颜约束和空间距离约束的特征下最近的K 个点
.图2仿射类方法的2种分类方式对应的算法及适用范围(其中Lap 表明在原简单权重方法的基础上采用Matting
Laplacian)Fig.2
Two types of affinity based matting method and the corresponding algorithms and application scopes (where Lap denotes the application of matting Laplacian
based on simple weight methods)
根据式(2)，若αi 或其K 个近邻像素的αj 均接近于0或1，即它们均为绝对前景或背景，此时的权值w j 显然几乎无法构成影响.因此，在KNN 算法中讨论的权值是否采用exp(−x )还是1−x 的问题则显得不大重要.但若αi 和αj 为小数，即它们均为混合点，则权w j 非常重要.然而，由于简单权重模式下的w j 的产生并不采用抠像公式，而真实值αtrue 是由抠像公式算出，因此此时的结果肯定不理想.由此可得出的结论是：该类方法适合于计算绝对像素，而不是混合像素.
另一方面，搜索范围较近的Random Walk 和Nonlocal 等方法，需要经过多次传递才能到达已知区域，因此较易造成误差累积.相反，搜索范围较广的KNN 算法可以通过较少次数的传递或直接搜索到达已知区域，会产生较少误差累积，更有利于绝对前景和背景的计算.这与采样类方法中直接访问已知区域的方式较为相似.
绝对像素计算步骤也同时在文献[24]中进行了深入讨论.据统计，在评估系统[23]提供的所有训练
图像中，大型号与小型号Trimap 中的绝对点数量大大超过了混合点的数量，由此可以看出该步骤的重要
性.进一步，该步骤必须单独采用一个独立的、不采用抠像公式的步骤，使其区别于普通的混合像素计算步骤，而简单权重类方法则完全符合这种绝对像素计算准则.目前，绝对像素的计算的算法仅出现在采样类计算方式中，但局部类方法[13−16,19]容易遗漏较远处的样本，误划分率偏高，而全局类方法[17]易受全局前景和背景颜重叠影响，误划分率较高.由此可以看出，目前的绝对像素划分方法仍然受到全局与局部采样方式相互平衡的困扰.
1.1.2Matting Laplacian 类方法
该类方法如图2右栏所示，它假设在某“局部集合”S 内，任何点i 的前景和背景颜F i 和B i 都是两个固定颜{F 1,F 2}和{B 1,B 2}的线性组合，称为颜线性模型(Color line model).结合抠像公式并经推导，结论为在某个集合S 内的(i,j )∈S ，点i 与j 产生的权重为
−1|S | 1+(x i −µS )T
ΣS +
ε|S |
X 3 −1(x j −µS ) (4)
其中,x i 与x j 分别为点i 与j 的三维颜向量,X 3为3×3单位阵,ΣS 、µS 分别为S 内的3×3协方差矩阵与3×1的均值向量,ε为一个较小的数.未知点i 与j 的权重为所有包含二者的集合S 所产生的权重之和.显然，由于采用了抠像公式，该类方法非常适合于混合点的计算，也是目前为止，仿射类方法中对混合点最重要的计算方式.
该类方法的关键问题是相关集合S 如何选择.Closed-Form 算法[1]提出将集合S 定义为较小的局部窗口，对于宽度较窄的前景硬边界效果较好，然而该类小窗口无法充分涵盖较宽的混合区域或前景空洞等实例的颜信息.Large Kernel 算法[2]改进了基于空间局部窗口的思想，提出了核宽度r 与不同未知局部区域的宽度成比例的方式.然而事实上，核宽度很大程度上依赖于真实混合区域的宽度信息，而未知区域仅为用户的粗略手工输入，尤其输入为稀疏的线条不能充分表达混合区域的实际信息，现实中还会存在很多偏差.CCM 算法[5]采用了KNN 方式中的颜近似的方法选取集合S ，取代了空间方式的局部窗口.由于该方法搜索范围过大并引入大量已知样本，在实际中，它对绝对像素计算的效果较好，但对于混合像素的计算也受到全局绝对样本影响，出现过于二值化的现象.
CNN Matting 方法[20]提到,KNN 算法与Closed Form 算法之间的区别并不直接，由此采用基于深度学习方式对二者进行融合.然而经本文
212自动化学报47卷
讨论至此，它们的区别已经非常明朗，即KNN 类方法适用于绝对像素的划分，而Matting Laplacian 类(即Closed Form 类)适用于混合像素的计算.本文从仿射类方法自身入手，据各类方法自身的优点和缺点做出相互的补充，避免了大量训练数据以及长时间训练等问题.
图3显示了5种典型算法在α评价系统[23]的52幅训练图像上(27幅训练图像中的大、小Trimap 且不包含GT16)，各αtrue 区间的平均MSE 比较(不包含Random Walk)，显然,KNN 在0∼0.25与0.95∼1区间较好，印证了它非常擅长于绝对像素划分，而较为平滑的背景使得在绝对背景划分上更加优秀.CCM 仅在0∼0.05区间较好，说明它受前景和背景重叠的影响非常大.Closed Form 与Large Kernel 大致0.25∼0.95间较好，印证了它们擅长混合像素的计算.同时，近距离Nonlocal 算法在各区间中均不理想
.
图3各αtrue
区间中5种传统仿射类算法α结果的平均MSE 比较(其中x 轴坐标中的0.0表示0.0∼0.05区间等)Fig.3
MSE comparison on five traditional affinity based matting algorithms in each αtrue interval (where 0.0in
x -label denotes the range of 0.0∼0.05,etc)1.2本文方法的提出
事实上,KNN 类算法中K 近邻像素的远近的选取，对该类方法的绝对像素划分结果会产生重要影响.在前景与背景的整体重合度不高的前提下，选择更远距离的搜索范围，不仅会为当前未知点提供更多相似的已知点，而且在Trimap 真实样本距离未知点较远时(如未知区域较大、或者前景存在空洞)计算效果更好.但如果较远处的前景与背景颜存在较大重合，则会产生计算错误，此时需要采用较小的搜索范围.因此，所选取的近邻像素的远近也是一个重要的平衡.然而,KNN 采用固定的远距离与近距离相结合的方式，无法根据空间上的颜变化情况进行自适应调整.
基于上述分析，本文在第2节新引入了KNN 搜索上的3种范围(如图2左栏所示)，并依据全局重叠与局部重叠程度，相应采用其中2种层次相结合的方式，以期对大部分绝对像素进行划分，并进
一步缩小未知区域的宽度.同时，由于无法保证初始Trimap 与混合点之间的关系，该层次采用与初始Trimap 未知区域大小无关的方式，这与Large Kernel 算法不同.
如前文所述，混合像素计算过程中的Matting Laplacian 类方法中的核宽度、或者搜索空间的大小，需要与真实未知区域的宽度相一致.若搜索范围过小则无法充分涵知区域的信息，造成CNN 算法[20]提到的“过平滑”，而搜索范围过大会导致混合像素的绝对像素化，如CCM.由于在第2节中，相当多的绝对像素已被划分，且混合像素区域的大致轮廓也已确定，因此在此基础上，第3节引入了KNN 及Nonlocal 搜索上的5种范围(如图2右栏所示)，并采用结合未知区域宽度的Matting Laplacian 方法，计算最终剩余混合像素.
2绝对像素划分
本节讨论基于KNN 搜索方式的绝对像素划分.第2.1节提出了搜索范围因子的概念，并定义3种搜索范围下的直接点差异度，为后续章节打下基础；第2.2节提出了图像重概念，将图像划分为低重合度图像和高重合度图像，前者按2.3节计算α，后者按第2.4节计算α.最后按第2.5节的截取方式得到预处理后的Trimap.
2.1搜索范围因子与直接点差异度
首先，类似于KNN 算法，定义像素i 的特征矢量x s i
(f )=[r i ,g i ,b i ,sx i (f ),sy i (f )]为i 的3个通道的颜值,{r i ,g i ,b i }为点i 的空间距离特征，表述为
sx i (f )=f ·x i (x 2i +y 2i )12
sy i
(f )=f ·y i
(x 2i +y 2i )
12
(5)其中,x i 和y i 为i 的空间横坐标与纵坐标,f 为控
制空间距离远近的重要参数.f 越大，采集的像素越近，反之则越远.在KNN 算法中,f 的取值为1和0.01之间的融合，其最终效果近似于0.5，如图2所示.
前文曾提到，搜集像素位置的远近是KNN 类方法的决定因素之一，该问题非常依赖于前景与背景颜的重合度.然而，传统的仿射类方法并不是直接访问已知区域的，直接获取每个点的前景和背景信息.因此，本文提出一种类似于采样方式的、直接访问已知区域的方法，用来模拟和引导每个未知点间接搜索距离的方式.这里需要利用FLANN (Fast library approximate nearest neighbors)方法，在相关特征x i (f )下，靠近未知区域的5个像素宽度的已知前景区域ΦF 和背景区域ΦB 位置(简记为F
1期姚桂林等：一种基于双层框架的仿射类图像抠像方法213与B)，对每个像素i分别寻最近的前景和背景点
j各K=10个，将它们称为直接点，如图4(a)下
方的j点所示(以背景为例).在x i为x s
i
的前3个
空间无关特征分量、即颜特征下，计算未知点i与
上述前景与背景直接采样点对于K个直接点的平
均颜差异d i(f,F)与d i(f,B)，之后在给定距离参
数f之下，计算点i的前景与背景颜的差异系数:
DF i(f)=max(d i(f,F),d i(f,B))θ1 min(d i(f,F),d i(f,B))
(6)
图4以背景为例，未知点的各种搜索方式与搜索范围
Fig.4Various kinds of searching manners and searching
ranges for an unknown pixel
其中,θ1的取值在1至2之间时，前景与背景的区
分效果最好，这里取经验值θ1=1.5.DF i(f)越高,
表明在距离参数f下，点i的直接前景与背景颜
差异性越大，重合性越低，该距离参数f就比较理
想；否则，该距离参数就不理想.
对每个未知点i，计算近、中、远3个级别的差
异度DF i(0.5),DF i(0.1)和DF i(0.01)，并为后面的
计算所采用.这3个级别的近似搜索范围如图4(b)
所示.
2.2像素采集远近及图像的重合度判别
按文献[25]的理论，局部(或近距离)采样方式
应作为基本方式，而全局(或远距离)采样方式是局
部的一种补充.而这对于仿射类方法同样有效.考
虑到各图像中前中前景与背景的重叠程度不尽相同,
采集像素远与近的范围也不相同.首先，在未知区域
ΩU内、靠近已知前景和背景区域的位置，分别定义
1个像素宽度为“学习区域”(简记为F与B)，首先
在距离参数f之下，计算这2个区域到各自已知前
景和背景的平均颜差异d L(f,F)与d L(f,B),
rt1=max(d L(0.5,F)−d L(0.01,F),
d L(0.5,B)−d L(0.01,B))(7)
rt1越小表明近处像素点已经足够判别绝对像素点;
否则，需要采集远处像素来实现.
其次，在特定集合M下定义如下准则:
rt2(M)=
i∈M
δ(Cr)
i∈M
δ
Cr
(8)
其中，判定条件Cr=(DF i(0.5)<DF i(0.01)),
DF i(f)根据式(6)定义,
Cr为对Cr求反,δ是
判别函数.如果DF i(0.5)大于DF i(0.01)，表明i
点近处的前景和背景的区分度好于远处.而比率rt2
越小则表明幅图像，较远处的重合度较高，计算误差
weight的几种形式也会较大，需要保守的采集近处像素.对整幅图像定
义如下准则T1:
T1=rt1·rt2(M1)θ2·rt2(M2)θ3(9)
其中,M1={i|i∈ΩU∧DF i(0.1)<1},M2=
{i|i∈ΩU∧DF i(0.1)≥1},θ2=0.7,θ3=0.4.之
后，若T1≤0.7×10−4，则该图像为前景与背景重合
度较高的图像；否则，若T1≥1.2×10−4，则该图为
重合度较低的图像.若T1在上述二值之间，则进一
步令T2=rt1·rt2(M1)θ2，若T2<0.8×10−4，则该
图为重合度较高的图像，否则为重合度较低的图像.
上述参数均根据经验取值.
最后，设定低度重合的图像采用2个远距离级
别的f为0.1和0.01，而高度重合的图像采用2个
近距离的0.5和0.1.每种重合度形式均采用近距离
搜索范围为主、远距离为辅的搜索形式.
发表评论