1.1.1 研究进展简述

在基于采样的抠图算法中，由于抠图前景/背景像素对组合优化问题决策空间庞大，难以遍历所有可能的前景/背景像素对，因此像素采样是对前景/背景像素对组合优化问题决策空间进行缩减的关键环节。像素采样结果决定了前景/背景像素对优化精度的上界，一旦最优样本未被采集，前景/背景像素对优化的精度将大幅下降，造成估计的抠图透明度遮罩出现较大误差。如图1-1所示，像素采样是基于采样的抠图算法中介于预处理与最优像素对选择之间的重要环节，其为最优像素对选择提供候选的前景及背景像素样本。由于所有可能的前景/背景像素对的数量巨大，评价所有的前景/背景像素对是不可行的，因此，基于采样的抠图算法需要对已知区域进行采样，以大幅减少可行解的数量，使最优像素对采样成为可能，进而从前景及背景样本集合中为每个未知像素选择最优的前景/背景像素对。

图1-1 基于采样的抠图算法的流程图

早期的采样算法主要通过单一的基于空间距离特征的采样策略实现局部采样[1-3]。单特征采样算法通过已知区域像素到未知区域的相近程度判断是否将该像素采集为样本，因为最优的前景/背景像素对不一定落在靠近已知像素的边缘区域，所以基于单一特征的采样策略可能会导致丢失最优样本。为了解决该问题，研究人员提出了考虑多个图像特征的全局采样算法来保证采集到像素样本的多样性，如基于聚类的采样算法（Clustering-Based Sampling Algorithm）[4]、基于颜色与纹理特征加权的抠图算法[5]等。除空间距离特征的多特征采样算法之外，还额外考虑了如颜色特征[4，6-8]、纹理特征[5]等其他采样特征，有效地提升了样本的多样性。现有的基于多特征的采样策略主要通过两种方式融合多个采样特征：第一种方式设计包含多个特征项的目标函数[4]，目标函数中每个数据项对应一个采样特征；第二种方式将多个特征向量串接成一个总的特征向量[6-8]。

最近的研究还提出了基于稀疏编码的抠图算法[8]、基于KL散度采样的抠图算法[7]等更为有效的样本多样性保持策略，这些策略提供了定量评价样本的代表性的计算方法，使其可以在保证采样质量的情况下将样本集合规模维持在一个较小的水平，从而减少最优像素对选择的计算量。然而，这类多样性保持策略具有较高的时间、空间复杂度，使其无法在完整的采样空间中应用。由于超像素（Superpixel）[1]的平均颜色被认为可以代表超像素中大部分像素的颜色，因此，这类算法将像素聚类成为超像素，并以超像素平均颜色集合作为采样空间[4-8]，从而达到缩减采样空间的目的，使其可以在有效时间内完成样本的采集。这里称这种压缩采样空间的策略为超像素级采样（Superpixel-Level Sampling）。

现有的采样策略依然存在最优前景/背景像素对的丢失问题，其原因有两点。

1）没有考虑多个采样特征之间可能存在的冲突。现有的多特征采样算法将多个采样特征通过一个包含多个数据项的目标函数或串接多个特征向量进行简单合并，其背后的假设为：多个采样特征对应的采样准则可以同时被满足。然而，实际采样中并不总能满足该假设。当多个采样准则之间存在冲突时，现有的采样策略可能会遗漏最优的前景/背景像素对。例如，在最优的前景或背景像素与未知像素具有相近的颜色但距离较远的情况下，空间距离相近的采样准则和颜色相近的采样准则会发生冲突，两者不能同时被满足。由于不能满足空间距离相近的采样准则，与满足该准则的像素（即靠近未知像素的已知区域像素）相比，最优的前景或背景像素的评分不佳，造成现有的采样算法遗漏了最优的前景/背景像素对。

2）虽然超像素级采样可以显著地降低复杂采样算法的时间复杂度和空间复杂度，但是超像素级采样同时也使采样空间不完整，不完整的采样空间可能未能包含最优的前景/背景像素对。超像素的平均颜色往往不能代表超像素中离群像素的颜色，而这些离群像素可能为最优的前景或背景像素。图1-2给出了由超像素级采样造成的最优前景/背景像素对丢失的例子，图1-2a为输入图像，图中三分图的已知前景区域边界与已知背景区域边界分别用红色及蓝色表示；图1-2b从上至下分别是图1-2a中紫色区域局部放大图像、图1-2a中紫色区域局部放大标准抠图透明度遮罩、基于KL散度采样的抠图算法[7]获得的图1-2a中紫色区域局部放大抠图透明度遮罩；图1-2c从上而下分别是图1-2a中绿色区域局部放大图像、图1-2a中绿色区域局部放大超像素图像，其中超像素中像素颜色使用超像素的平均颜色替代。从图1-2c中可以发现超像素的平均颜色与超像素内的三角形标注的像素颜色出现明显的差别，三角形标注的像素正是图1-2b中十字标注的未知像素的最优的前景像素。由于最优前景/背景像素对丢失，造成了透明度遮罩估计的较大误差（如图1-2b所示）。这个例子说明了超像素的平均颜色往往不能代表超像素中所有像素的颜色。

图1-2 超像素级采样造成的最优前景/背景像素对丢失的例子（见彩插）

[1] 超像素是由具有相似特征的像素组成的连通子区域。