一种基于KNN后处理的鲁棒性抠图方法

白 杨 姚桂林

(哈尔滨商业大学计算机与信息工程学院 黑龙江 哈尔滨 150028)

0 引 言

图像抠图技术是把图像的前景从背景中精确地分离出来的过程，图像合成[1]则是把分离出来的前景通过某种方法放到新背景中的过程。利用抠图与合成技术，可以将一个实体的目标放到虚拟的环境中，这种技术已经被影视业广泛应用，同时这种功能也被一些图像处理软件所应用，例如目前使用最为广泛的Photoshop。

图像抠图和图像分割仍有较大区别，对于前景物体的边缘和一些半透明物体，图像分割只能将它们和背景分割成二值化形式。但在实际图像的形成过程中，在前景物体边缘附近的像素值是很复杂的，并不是简单的前景/背景这两种模式。图像抠图则对前景物体加入了α通道(或称为Alpha通道，透明度)，成功解决了这个问题，从而可以更加精确地提取物体的前景。

对于一幅图像中的某个像素，假设其坐标为z，观察到的颜色为Iz，前景的颜色为Fz，背景的颜色为Bz，则物体的实际颜色可由{Fz,Bz}的线性组合得到：

Iz=αzFz+(1-αz)Bz

(1)

式中：Fz、Bz、αz为未知量;αz的取值范围是[0,1]中的一个数。将αz∈(0,1)时的所有点称作混合点，这些点通常在图像的前景和背景的分界处，比如物体的头发或者一些半透明物体等，并将αz=0或1的点称为不透明点或绝对点。在自然图像中，大部分点都是绝对前景点和绝对背景点，而混合像素点所占的比例非常小，如何将{Fz,Bz,αz}准确地计算出来是抠图问题所面临的任务。

式(1)有三个未知数，即有无穷多解，所以必须加上一些约束条件才能求解。在以往的抠图过程中都会使用单一的背景(蓝屏抠图)来减少未知量，但是该方法对于颜色较复杂的前景效果并不好。于是提出了一种基于Trimap的交互式抠图，人为将图像标注成三个区域绝对前景ΩF、绝对背景ΩB和未知区域ΩU。其算法实例如图1所示，前两个区域为已知区域，分别用白色、黑色表示，未知区域用灰色表示。在绝对前景ΩF中包含大部分α=1的点，在绝对背景ΩB中包含大部分α=0的点，在未知区域ΩU中则包含全部0<α<1的混合点，并且有少量绝对点。本文将Trimap作为算法的先验信息，然后求出未知区域的{Fz,Bz}。

图1 图像抠图算法实例

1 相关工作

当前基于Trimap的主流抠图方式有采样法[2]和仿射法[3]。基于仿射的抠图方法并不孤立地计算每个未知点，而是考虑像素邻域之间的联系，利用递归的方法求出每个未知像素的Alpha值。基于采样的抠图方法和仿射方法正好相反，该方法对每个未知点都独立计算，并不考虑像素之间的相关性。针对未知区域ΩU中的像素z，假设其前景和背景为{Fz,Bz}，可以在ΩF和ΩB中可以直接找到或者通过计算找到一些近似样本，并计算α。

1.1 采样类方法

较早的采样类方法采用高斯混合模型[4]分离前景和背景。贝叶斯抠图[5]将图像前景F、背景B和α看作一种概率分布，对于每一个待计算的像素z，建立先验概率模式进行求解。Wang等[6]提出了一种优化采样方式的鲁棒性抠图算法，该方法为每个未知点建立前景、背景样本对，分别计算每个样本对的信度值和Alpha值，然后选出三个信度值最高的样本对，将这三个样本对计算出的Alpha值取平均作为未知点的Alpha值。Gastal等[7]提出了共享采样的抠图方法，该方法以未知点作为起点，然后向空间中发射4条射线，每条射线最多采集一个前景点和一个背景点，经过一些优化方式得到未知点的最终Alpha值。文献[8]提出了一种全局采样的方法，对于未知区域，在靠近已知区域处用较小的邻域进行采样，在远离已知区域处采用较大的邻域采样。

1.2 仿射类方法

泊松抠图[9]将图像的α看成一个场，将泊松方程引入到了抠图问题中，随机游走抠图[10]将像素当成是图的节点，用邻域权值的方法去求解抠图问题。而闭合形式(Closed Form)抠图[11]假设在3×3或者5×5的小窗口符合颜色线性模型的性质，即该窗口中所有的像素值都是由某个固定的前景颜色F和背景颜色B的线性组合得到，构造拉普拉斯抠图矩阵，并求解相应的稀疏线性方程得到每个未知像素的Alpha值。KNN抠图[12]利用K近邻算法来匹配非局部的邻域像素，为每个未知点建立空间加颜色的特征，然后将未知点的K个邻域设置权值，最后通过求解类似的稀疏线性方程得到未知像素的Alpha值。

2 后处理介绍

3 算法设计

3.1 对未知点进行鲁棒性采样

从已知区域的边界ΦF和ΦB找到与未知点z在空间距离上最近的点FC和BC，然后以这2个点为起点，沿着上述边界向两侧方向每隔一定的距离采集一个样本点，对于每个未知点，共采集20个前景样本点和20个背景样本点，共包括400个样本对。

3.2 初始Alpha估计与可信度计算

在采集了样本点后，需要从上述样本对中选择较好的样本对。为了使采集到的前景/背景样本对能够精确地体现未知点的前景与背景颜色，本文算法分为如下4步进行。

(1) 用每个样本对估计未知点的α：

(2)

(2) 定义距离比率：

(3)

(3) 在普通图像中，大部分像素都是绝对前景或绝对背景，因此需要额外设置以下两个权值：

(4)

(5)

式中：DF=maxi‖Fi-C‖；DB=maxj‖Bj-C‖。在颜色空间中，前景或背景样本点与未知点的颜色越接近，权值就越大。

(4) 最终的信度值计算如下：

(6)

式中：σ为常数，通常取0.1。

采用上述4个步骤可以计算出每一对样本点的信度值f(Fi,Bj)和初级Alpha值，之后选择3个最高信度的样本对，对每个未知点，分别求出其信度值的平均值和初级Alpha值的平均值。

3.3 构建未知像素的数据权重矩阵

(7)

(8)

3.4 KNN后处理算法

3.4.1KNN算法流程

KNN算法是利用FLANN算法在指定的特征(一般为颜色特征)下寻找与未知点i最近的K个点，这里的“最近”指的是未知点与指定的颜色特征最近，而非空间距离最近，即以颜色特征的相似性代替了空间距离相似性，这样可以搜寻到更多的空间远距离像素，其具体步骤如下：

(1) 建立特征。为每个未知点i建立特征，并寻找在此特征下最接近i的K个像素。令{Bi,Gi,Ri}为像素点i的颜色特征，{xi,yi}为像素点i的空间特征。那么在RGB颜色空间下，未知点i的特征可以表示为：

(9)

(2) 计算权值。为每个未知点建立了特征以后，对未知点i的K个最近邻点设置权值，其计算公式为：

(10)

式中：Xi为未知点i的特征；Xik为K个近邻点的特征；c为一个权值系数。如果未知点i与样本k的特征差异越大，权值越小。

(3) 构造稀疏矩阵。将计算的权值映射到一个稀疏对称矩阵中。

3.4.2后处理的过程

在建立了KNN类型的稀疏矩阵后，就可以对采样得到的初级α进行后处理。令α*为最终后处理的值，它的表达式为：

(11)

(L+θD+λ·diag(P(F)+P(B)))α=

θbs+λ·P(F)

(12)

3.5 算法优势

在以往的仿射类后处理算法中采用的是基于空间特征和颜色线性模型的Closed Form算法对α进行后处理，但该方法存在两个问题：(1) 局部窗口wk大小通常需要根据前景与背景的颜色分布进行选取，以往经验上大小一般是3×3或5×5大小，但对于颜色分布复杂的场景，通常需要选取更大的窗口。(2) 假设算法在这个小窗口中的像素满足颜色线性模型，然后利用抠图公式和局部窗口进行复杂的权值累加计算。这种模型在局部颜色变化较缓慢的区域效果尚可，但颜色变化比较剧烈的区域效果不好。

针对上述两个问题，本文采用KNN类方法做后处理，相比于Closed Form算法，其优点如下：(1) 颜色相似性的优势，KNN类方法为每个未知点寻找K个近邻点，这些近邻点的颜色与当前未知点的颜色比较相近，因此用它们去线性组合未知点的颜色所形成的拟合误差要比单纯的采用空间特征去拟合的误差要小。另外，由于KNN类方法采用的是颜色相似性，对于不同的颜色分布可能产生不同的颜色模型，相较于简单的颜色线性模型要准确得多。(2) 全局搜索的优势性。对于一些分布较广但是前景、背景颜色差异较大的颜色分布，非常适合用KNN类方法去搜索像素。相较于只利用空间特征去寻找像素的一些算法，该算法能够使未知点找到空间距离比较远的像素，尤其是绝对前景和背景像素。另外，由于绝对前景和背景像素在未知区域内的比例很大，而对它们的计算也会更加准确，因此也能使得最终的α结果更加准确。

4 实验结果分析

本实验的硬件为Core i7四核3.8 GHz的CPU 以及8 GB内存的PC机，实验环境采用的是Visual Studio 2017结合OpenCV，并采用C++语言实现。鉴于本文算法的特点，将该方法命名为RobustKNN。

本文采用Rhemann等[15]提出的在线抠像训练数据集。该系统提供了27幅训练图像，并且使用均方误差(MSE)和绝对误差(SAD)作为误差评判标准，其公式如下：

(13)

(14)

式中：m是图像的宽；n是图像的高；E(i,j)为抠图算法得到的结果；H(i,j)为训练集提供的真实结果。

4.1 定性观察

本文选取了训练集中的3幅图像。图2为前景区域存在孔洞的2幅图像经各算法处理得到的Alpha结果图。其中，图2(a)为GT01，其特点是前景存在较多空洞，这些空洞处的背景与已知背景距离较远。Trimap为原图的三分图，Ground Truth为GT01的真实Alpha值(只展示在Trimap图中用黑色矩形框框住的那一部分)，下面的三幅图分别是Closed Form、Robust和RobustKNN算法输出的结果(只展示在Trimap图中用黑色矩形框框住的那一部分)。从图中可以看出，三种算法都能将物体的前景轮廓抠取出来，但是对于前景空洞(如用椭圆框住的那一部分)，Closed Form算法和Robust算法表现要稍微差一些，前者将这部分空洞划分到前景中去，后者虽然能抠取出这部分空洞的大致轮廓，但是还是有很多像素被划分到前景中导致抠图准确性下降，这也是单一的使用距离作为特征所带来的问题。而本文算法(RobustKNN)能够准确地将这部分空洞抠取出来，这得益于本文算法在后处理阶段使用的是颜色特征与距离特征相结合的方式，能够利用颜色相似性找到与未知点颜色相近但空间距离比较远的像素，提高了Alpha值的准确性。

另一个前景存在空洞的例子如图2(b)所示，其中GT02为原始图像，其特点为前景中同样存在大量的空洞。Trimap为原图的三分图，Ground Truth为GT02的真实Alpha值(只展示在Trimap图中用黑色矩形框框住的那一部分)，下面的三幅图分别是Closed Form、Robust和RobustKNN算法输出的结果(只展示在Trimap图中用黑色矩形框框住的那一部分)。从图中可以看出，三种算法都能将物体的前景轮廓提取出来，但是在轮廓内部的一些空洞点，三种算法的表现不尽相同。Closed Form算法表现的最差，大量的空洞点被划分到前景中去，造成错误划分。而Robust算法稍好一些，但一些细小的空洞点也被其划分到前景中，造成错误划分。本文算法的效果最好，能够准确地划分出一些细小的空洞点。

图2 各算法对前景区域存在大量孔洞时的图像的Alpha结果图

对于有效样本缺失的情况，原图及各算法处理结果如图3所示。其中GT03为原始图像，其特点为国旗部分缺少有效样本。Trimap为原图的三分图，Ground Truth为GT03的真实Alpha值，下面的三幅图分别是Closed Form、Robust和本文算法输出的结果。可以看出，Robust算法表现最差，国旗的轮廓没有完整地抠取出来。Closed Form算法表现稍好一些，能提取出国旗的轮廓，但是国旗内部许多地方还是划分到背景中，造成划分错误。本文算法的表现最好，它将国旗的整体区域都划分到前景中。

图3 各算法对有效样本缺失时的图像的Alpha结果图

4.2 定量分析

4.1节是从视觉角度对算法进行评价，本节通过MSE和SAD这两个指标来对算法进行评价。表1与表2为上述3幅图像的MSE和SAD。可以看出，本文算法无论是均方误差还是绝对误差都比其他算法小，即本文算法的结果最接近真实结果。

表1 3幅图片的均方误差(MSE)

表2 3幅图片的绝对误差(SAD)

为了更加客观地评价本文算法，将训练集中的27幅图像的均方误差和绝对误差全部计算出，并求平均值，同时计算出在不同型号Trimap下各个算法的误差，结果如表3、表4所示。这些不同型号的Trimap最主要的区别就是在标注前景区域、背景区域和未知区域时的精准程度，其中小型号的Trimap标注最为精细而巨大型号的Trimap标注则比较粗糙。可以看出，同一种算法中小型号Trimap的误差要小于巨大型号的误差；在相同Trimap型号下，本文算法造成的误差要小于其他两种算法。

表3 27幅图像的平均均方误差

表4 27幅图像的平均绝对误差

5 结 语

本文在鲁棒抠图算法的基础上，采用KNN算法对采样得到的初级α进行后处理，算法弥补了以往使用传统仿射类算法做后处理时，使用单一的空间距离作为特征的缺陷，这会造成搜索范围较小。而在局部窗口中使用简单的颜色线性模型使得对于颜色分布较复杂的图片造成较大的误差。本文采用KNN搜索方法用作后处理，为每个未知点建立颜色特征和空间特征，使得未知点能找到与其颜色相近的一些近邻点，同时KNN类仿射算法具备采样范围较宽的特点，能搜索到较远处的像素。实验结果表明，使用KNN类仿射算法做后处理相较于传统的仿射类算法，无论在视觉方面还是准确性方面，其Alpha结果都有较大的提高。