精确捕捉半透明的视觉效果——基于像素级多目标优化的采样算法
抠图技术（image matting）起源于图像合成（image composition），是一种致力于精确提取前景的图像处理技术。在往期推文《当医学医疗遇上了人工智能，抠图算法应用的又一力作》[3]中，智能算法实验室阐述了抠图技术如何应用在血管分割领域；与此同时，抠图算法在图像合成、视频非线性编辑、图像融合、自动前景提取、目标跟踪、虚拟现实、增强现实等领域有着广泛的应用，抠图的过程如图1所示；除此之外，数字图像合成技术能够有效地降低图像、视频素材的获取成本，因此，受到了影视传媒业的广泛关注，图像合成流程如图2所示。
图1 抠图的过程
图2 图像合成流程示意图
基于采样的抠图算法（sampling-based matting methods）是一种主流的抠图技术，通过为每一个未知区域的像素求解最优的一对前景像素和背景像素（下文称像素对），来实现抠图透明度遮罩的估计，从而得到对应的前景颜色，基于采样的抠图算法主要流程如图3所示。在求解最优像素对的过程中，像素采样（color sampling）是对像素对组合优化问题的决策空间进行缩减的关键环节，该步骤直接决定了像素对优化精度能够达到的上界，一旦最优样本未被采集，最优的像素对求解精度将大幅下降，从而导致估计的抠图透明度遮罩出现较大误差。
图3 基于采样的抠图算法主要流程
早期的采样算法通过单一的空间距离特征来实现局部采样，即采用单特征采样策略。最近提出的采样算法则考虑了多个特征策略，以此维持样本的多样性（如基于KL散度的采样[2]），然而这些多样性保持策略具有较高的时间、空间复杂度，无法对整个采样空间中像素的代表性进行度量。为了降低复杂度，多样性保持策略假设超像素（superpixel）的平均颜色可以代表超像素中的大部分像素的颜色，从而达到缩减采样空间的目的。但是现有的采样策略都无法避免最优像素对丢失的问题（Missing true sample problem），主要有两个原因：第一，没有考虑多个采样特征之间可能存在的冲突；第二，超像素级采样使得采样空间不完整。
为了解决最优像素对丢失问题，智能算法实验室提出了基于像素级多目标优化采样的抠图算法（Pixel-level Discrete Multi-objective Sampling）[1]。该算法通过多个特征采样策略，建立多目标优化模型（MOP），利用一种快速解决离散多目标优化问题的算法求解出帕累托（Pareto）最优解，将帕累托最优解作为采样环节输出的样本集。目前，该研究成果已成功发表在图像处理领域的顶级期刊IEEE Transactions on Image Processing上，下面本文将对本研究工作的相关成果进行介绍。
像素级多目标全局采样算法首先采用了空间、颜色、纹理三个特征采样策略，为每一个特征分别设计了采样准则，即颜色相近采样准则、空间距离相近采样准则、纹理相似采样准则，通过这些准则建立多目标优化模型，像素级多目标全局采样算法的优化模型如图4所示。其中x代表已知（前景或背景）区域中的一个像素，z代表未知区域中的一个像素，C代表RGB空间颜色向量，S代表空间坐标向量，T代表局部二值模式特征向量。
图4 像素级多目标全局采样算法的优化模型
多目标优化问题中，优化目标之间往往存在冲突，不存在一个解可以使所有目标同时达到最优，于是可以将上述多目标优化问题的所有帕累托最优解作为像素样本。在本研究工作中，该实验室使用了一种快速解决离散多目标优化问题的方法，能够在k乘以n的时间复杂度内求得帕累托最优解集，k代表帕累托最优解的个数，n代表所有解集的个数。
相比于单特征采样策略和超像素采样策略，像素级多目标全局采样算法通过建立多目标优化模型，将求得的帕累托最优解作为样本，保证了样本的多样性；与此同时，该算法采用像素级采样策略而非超样本级的采样策略，保证了采样空间的完整性。因此，像素级多目标全局采样算法能够很好地解决最优像素对丢失问题中的两个难点。在本研究工作中，该实验室将该算法与其他先进的像素采样算法进行了多组对比仿真实验，从而验证PDMS算法的有效性。第一个实验通过像素级多目标全局采样算法与两个先进抠图像素采样算法（基于KL散度的采样算法[2]，综合采样算法[4]）的采样指标进行定量对比，验证本文所提出的算法的抠图采样性能；第二个实验是基于提出的采样算法的抠图性能进行验证实验，从而证明该算法的可拓展性。
实验一选取最小透明度绝对误差和候选像素对集合基数这两个评价指标，进行对比实验，实验结果如图5、图6所示。从图5中可以明显地观察到，提出的算法（PDMS）在不同的测试图片上获取的最小透明度绝对误差，皆低于基于KL散度的采样算法及综合采样算法的最小透明度绝对误差。与此同时从图6中可以明显地观察到，相比于综合采样算法所生成的像素对候选集基数，该算法生成的像素对候选集基数低了一个数量级，与基于KL散度的采样算法生成的像素对候选集基数相近。该实验结果进一步说明了像素级多目标全局采样算法能获得较小的候选集，且候选集能够涵盖高质量的像素对，实现更精准的像素样本采集。
图5 采样算法所获得像素对最小透明度绝对误差对比
图6 采样算法所获得候选像素对集合基数对比
实验二在本文提出的采样算法的基础上，采用文献[4]提出的实现最优像素对的选择评价函数，构建了基于像素级离散多目标全局采样的抠图算法。表1展示了提出的算法与现有的10个先进抠图算法进行对比，在图像抠图基准数据集的7幅测试图像上三种类型三分图（trimap）的平均梯度误差。提出算法在采用三目标及双目标的情况下，在总体梯度误差比较中分别排名第一（三目标版本）和第二（双目标版本），优于其他抠图算法。此外采用三目标版本的算法在未知区域较大的三分图以及人工标记三分图的平均梯度误差比较中，均排名第一，整体上略优于现有的双目标版本的算法。
梯度误差可以反映算法的抠图性能，较大的梯度误差会造成最优像素对丢失问题，导致抠图性能显著下降。本文提出的算法以及其他先进算法获得的抠图透明度遮罩图如图7所示，其中(a)为输入图像，(b)为(a)中局部放大图，(c)为基于像素级多目标全局采样的抠图算法获得的抠图透明度遮罩，(d)为基于稀疏编码的抠图算法获得的抠图透明度遮罩，(e)为基于KL散度采样的抠图算法获得的抠图透明度遮罩，(f)为K近邻抠图算法获得的抠图透明度遮罩，(g)为基于综合采样的抠图算法获得的抠图透明度遮罩，(h)为基于颜色与纹理特征加权的抠图算法获得的抠图透明度遮罩，(i)为基于全局采样的抠图算法获得的抠图透明度遮罩。黄色箭头指示了抠图透明度遮罩误差较大的区域，可以观察到相比于其他先进抠图算法，基于像素级多目标全局采样的抠图算法获得了边缘更锐利的高质量抠图透明度遮罩，拥有更好的抠图性能。
图7 本文提出抠图算法获得的抠图透明度遮罩与其他算法进行比较
本文围绕单特征采样以及超像素采样所引起的最优像素对丢失问题，提出了一种基于像素级多目标优化采样的抠图算法（PDMS），该算法与现有的采样算法相比主要有两个创新点：其一，针对多个采样标准，PDMS算法建立多目标优化模型，并通过求取帕累托最优解集的方式来确认像素样本，而不是使用简单的线性加权等将多目标优化模型转换为单目标优化模型的方式，对多目标问题进行求解，从而解决了多采样特征对应的采样准则之间发生冲突的问题。其二，不同于基于超像素级的采样算法，PDMS算法在完整的采样空间中采集样本，避免了由采样空间不完整带来的最优像素对丢失问题。通过实验结果可知，本文提出的PDMS算法相比于其他像素采样算法在采集的精确度上面具有一定优势，并且拥有不俗的效率和性能，具有实际应用价值。
参考文献
[1]Han Huang, Yihui Liang*, Xiaowei Yang, Zhifeng Hao. Pixel-level Discrete Multiobjective Sampling for Alpha Matting, IEEE Transactions on Image Processing, 2019, 27(8): 3739-3751.
[2]Levent Karacan, Aykut Erdem, Erkut Erdem. Image matting with KL-divergence based sparse sampling. IEEE International Conference on Computer Vision. 2015: 424-432.
[3]Zhun Fan, Jiewei Lu, Caimin Wei, Han Huang, Xinye Cai and Xinjian Chen. A hierarchical image matting model for blood vessel segmentation in fundus images. IEEE Transactions on Image Processing, 2018, 28(5): 2367-2377.
[4]Ehsan Shahrian, Deepu Rajan, Brian Price. Improving image matting using comprehensive sampling sets. IEEE Conference on Computer Vision and Pattern Recognition. 2013: 636-643.
研究团队介绍
智能算法实验室（原智能算法与智能软件实验室，2018年更名）依托华南理工大学软件学院而建，坐落于国家级人才培养模式创新实验区内。实验室主要承担国内外重要智能算法类的研究课题，以算法与软件工具包的形式，根据国内外企业、科研与教育机构等单位在智能信息处理方面的需求，解决相关技术难点问题，并从中培养国际化算法研究型人才与算法工程化人才。
实验室必修课
实验室精神
-END-
总编：黄翰
文字：梁椅辉 许珉裴
校稿：冯夫健、黄子洛
图：梁椅辉
（部分图片来源网络）
时间：2019年11月13日
想了解更多智能算法最新研究进展、学术活动与经验交流等
长按二维码关注我们吧
如果有需要咨询的地方
可以联系我们实验室的负责人
实验室负责人：黄翰教授
联系邮箱：hhan@scut.edu.cn