1.1.2 科学原理

1. 问题描述

本节将介绍自然图像抠图中前景/背景像素对优化所涉及的像素采样问题的数学模型。考虑到像素采样由于前景、背景像素的组合数量过于庞大，无法在有效时间内评价所有可能的前景/背景像素对，不能实现最优前景/背景像素对的选取。因此，像素采样是从给定三分图的已知前景（背景）区域的像素所构成的集合中，通过一定的选择策略获得一个基数较小的前景（背景）像素样本集合的过程。

设Ω_F、Ω_B分别为给定的一个三分图中已知前景区域和已知背景区域的像素集合，P（*）表示一个抠图像素采样算法P对像素集合*进行采样，对已知前景及背景区域像素采样问题可以建模为：

其中分别为采集得到的前景、背景像素样本集合，|*|表示集合*的基数。高质量的像素样本集合应对任意的未知像素z均满足以下条件：

其中表示将前景/背景像素对（p，q）所对应颜色值代入到式（1-4）中所估计的像素z的透明度。为标准抠图透明度遮罩中像素z的透明度值。ε为一个数值较小的常数。

当满足上述条件时，每一个未知像素在样本集合中均有像素对使其估计的透明度接近于标准透明度遮罩中的值。当不满足上述条件时，对于部分或全部未知像素，前景及背景样本集合中的像素任意两两组成的所有可能的前景/背景像素对，均与该未知像素对应的最优前景/背景像素对有较大差别，导致所估计的透明度值与标准透明度遮罩中的值存在较大偏差，从而造成了最优前景/背景像素对的丢失问题。

2. 基于像素级多目标全局采样的抠图算法

为了解决基于优化抠图算法求解速度慢的问题，文献[185]结合基于优化的抠图算法和基于采样的抠图算法，提出了一种基于像素级多目标全局采样的抠图算法。该算法的核心是像素级多目标全局采样算法。与现有的采样算法假设最优前景/背景像素对分布在特定区域不同，该文献提出的采样算法利用多目标优化实现了像素采样。与现有采样算法相比，像素级多目标全局采样算法主要有两个创新点。

1）通过多目标优化实现多个采样准则之间的自适应权衡，解决了多采样特征对应的采样准则之间的冲突问题。对于一个未知像素，考虑将多个采样特征的前景或背景像素采样问题建模为一个离散多目标优化问题。文献[185]提出的算法通过对离散多目标优化问题进行求解，将帕累托最优解集（Pareto Set）中的所有像素均作为样本实现了全局采样，由于帕累托最优（Pareto optimal）解[1]与各个采样目标之间的尺度无关，因此该算法不需要进行不同采样准则的加权，不涉及经验参数的调教。

2）区别于超像素级采样，通过将像素聚类成超像素实现采样空间的缩减，文献[185]提出的算法在完整的采样空间中采集样本，避免了因为采样空间不完整带来的最优前景/背景像素对丢失问题。因此，在已知前景、背景区域的每一个像素都可能被采集为像素样本，这里将该策略称为像素级采样（Pixel-Level Sampling）。

在像素级多目标全局采样算法中，针对前景/背景像素对评价函数设计了三个采样准则，包括与未知像素的颜色相似、空间距离相近以及纹理相似。一个未知像素的前景或背景像素采样问题被建模为一个包含两个及以上目标的离散多目标优化问题。为了快速求解大量的多目标优化问题，文献[185]提出了时间复杂度为O（kn）、空间复杂度为O（n）的快速离散多目标优化算法[2]，帕累托最优解集中的所有像素均被采集为样本。

基于像素级多目标全局采样的抠图算法在像素级多目标全局采样算法基础上，采用一个像素对目标函数实现最优像素对选择，进而得到对应的透明度。具体来说，像素级多目标全局采样算法所获得的前景样本集合与背景样本集合通过笛卡儿积的形式生成前景/背景像素对候选集合；通过最小化一个包含两个广泛使用评价项[3-8]的前景/背景像素对目标函数，从像素对候选集合中选择目标函数值最优的前景/背景像素对，并将其对应颜色代入式（1-4）从而估计出未知像素的透明度，所使用的前景/背景像素对目标函数包含颜色失真项以及空间距离项。给定一个未知像素z以及候选集合中的一个前景/背景像素对（p，q），其中，所采用的前景/背景像素对目标函数可表示为：

其中颜色失真项及空间距离项的定义由以下两个公式给出。

C_z、C_p和C_q分别表示像素z、像素p和像素q的RGB空间颜色向量，S_z、S_p和S_q分别表示像素z、像素p和像素q的空间坐标向量。

下面将对像素级多目标全局采样算法所涉及的像素级离散多目标采样策略以及快速离散多目标优化算法进行介绍。

（1）像素级离散多目标采样策略

为了解决多个采样特征对应的采样准则之间的冲突问题，文献[185]提出了像素级离散多目标采样Pixel-level Discrete Multiobjective Sampling，PDMS策略。该策略将关于每一个未知像素的前景或背景像素采样问题分别建模为一个离散多目标优化问题，针对评价函数设计可近似其最优解的采样准则，且每一个采样准则均建模为一个优化目标。如1.1.1节所述，不完整的采样空间会导致最优前景/背景像素对丢失问题。为了避免出现该问题，像素级离散多目标采样策略从已知区域所有像素所组成的集合中采集样本，实现了像素级的采样，这区别于超像素级采样从超像素平均颜色构成的集合中采集样本。

本节首先介绍像素级离散多目标采样策略所涉及的采样准则。北京航空航天大学的梁晓辉教授指出，基于单一空间相近采样准则的采样算法会导致丢失最优样本的问题[4]。为了解决该问题，像素级离散多目标采样策略采用了颜色、空间、纹理三个采样特征，为每一个特征分别设计了采样准则。

颜色是抠图的重要特征。像素级离散多目标采样策略将与给定的未知像素颜色相近作为一种有效的采样准则。给定一个未知像素z以及已知（前景或背景）区域中的一个像素x，颜色相近采样准则可建模为以下目标函数：

g₁（x）=‖C_x−C_z‖ （1-8）

其中C_x与C_z分别表示已知区域像素x与未知区域像素z的RGB空间颜色向量，‖*‖表示向量*的模。

像素级离散多目标采样策略考虑了广泛使用的空间距离特征，将与给定的未知像素空间距离相近作为一个采样准则，空间距离相近采样准则可建模为以下目标函数：

g₂（x）=‖S_x−S_z‖ （1-9）

其中S_x与S_z分别表示已知区域像素x与未知区域像素z的空间坐标向量。

此外，Shahrian等人的研究表明纹理特征可有效提高复杂场景下的抠图像素采样性能[5]。像素级离散多目标采样策略也考虑了图像的纹理特征，设计了基于局部二值模式（Local Binary Pattern）的纹理相似采样准则。其对应的目标函数可以表示为：

g₃（x）=‖T_x−T_z‖ （1-10）

其中T_x与T_z分别表示已知区域像素x与未知区域像素z对应的局部二值模式特征向量。

正如本节开头所述，提出多目标采样的目的是解决多个采样准则之间冲突导致的最优前景/背景像素对丢失问题。在基于多特征的采样算法中，多个特征所对应的采样准则往往不能同时被满足。例如，最优前景或背景像素可能与给定未知像素具有相近的颜色，但位于距离未知像素较远的区域。在这种情况下，虽然已知区域像素与未知像素之间的颜色差别较小，但是两者之间的空间距离却较大，造成颜色相近采样准则与空间距离相近采样准则存在冲突，两个准则不能同时被满足。

像素级离散多目标采样策略将前景、背景像素采样建模为两个离散多目标优化问题。该多目标优化问题旨在同时优化所有的目标函数。设有n个采样准则，前景像素采样问题所对应的多目标优化问题可以表示为：

min g₁（x），min g₂（x），···，min g_n（x）s.t. x∈Ω_F

（1-11）

其中g_i（x）为第i个需要优化的目标，i=1，2，···，n。决策变量x为已知前景区域像素的一维索引，x=1，2，···，|Ω_F|。由于决策变量为离散的整数值，因此该问题为离散的多目标优化问题。多目标优化问题中所涉及的目标往往存在冲突，不存在一个解可以同时使所有目标达到最优的情况。因此，多目标优化问题的最优解是指不存在其他在每个目标上都比其更优的可行解，称为帕累托最优解。像素级离散多目标采样策略将上述多目标优化问题的所有帕累托最优解作为像素样本。可以通过类似思路建立背景像素采样问题的多目标优化模型。

为了避免采样空间不完整所导致的最优前景/背景像素对丢失问题，这里提出了像素级采样策略，从已知前景或背景区域的所有像素所构成的集合中采集像素样本。为了获得完整的采样空间，像素级离散多目标采样策略没有采用超像素级采样算法[4-8]中普遍采用的像素聚类步骤。因此，已知前景或背景区域的每一个像素均有可能被采集为样本。像素样本的多样性是获得高质量抠图结果的关键因素[4-6]，像素级离散多目标采样策略在完整的采样空间中采样，与超像素级采样相比，这种采样策略增加了样本的多样性。

（2）快速离散多目标优化算法

像素级离散多目标采样策略将每个未知像素的前景或背景采样问题建模为一个离散多目标优化问题，这带来了数量巨大的多目标采样优化问题。如何在有效时间内求解数量庞大的离散多目标优化问题，是像素级离散多目标全局采样算法面临的重大挑战。虽然离散多目标优化问题是一个组合优化问题，但考虑到所涉及的离散多目标优化问题目标数量较少、决策变量维度较低以及可行解数量不是特别巨大等因素，像素级离散多目标采样策略所涉及的单个多目标优化问题并不是难以求解的。

其中一个求解思路是采用时间复杂度为O（n2）的蛮力法[3]。一方面，由于采用了像素级采样策略，多目标优化问题的可行解数量较超像素级采样大大增加；另一方面，对于一幅三十万像素的图像，像素级离散多目标采样策略涉及的多目标优化问题数量可达十几万个。因此，采用蛮力法计算非常耗时，在实际应用中是不可行的。

现有的求解多目标优化问题的算法可以分为确定性算法与近似算法两类。以天际线算法[9]为代表的确定性算法可以保证精确求解出所有帕累托最优解，这类算法可求解可行解数量随问题规模呈线性增长的多目标优化问题。由于这类算法被设计用于SQL查询，因此主要用于求解少量的可行解数量相对较大的多目标优化问题。为了实现在大量记录中的SQL查询，这类算法在设计时考虑了所有可行解只会访问一次等特性。这些特性对于动辄涉及上亿条记录的SQL查询来说固然十分重要，但是其对像素级离散多目标采样策略所涉及的多目标优化问题则没有显著的好处，因为这类多目标优化问题只涉及数量相对较少的可行解[4]，更重要的是实现这些特性可能会带来不必要的计算开销。采用这类算法可能会导致采样消耗的时间较长。以启发式优化算法为代表的近似算法旨在获得复杂多目标优化问题近似解，其主要面向确定性算法不能解决的NP难的复杂优化问题。近似算法的不足在于这类算法具有较高的时间复杂度，其不能在有效时间内求解数量庞大的多目标优化问题。

为了高效地求解像素级离散多目标采样策略所涉及的数量庞大的离散多目标优化问题，我们提出了时间复杂度为O（kn）、空间复杂度为O（n）的快速离散多目标优化（Fast Discrete Multiobjective Optimization，FDMO）算法[5]。快速离散多目标优化算法属于确定性算法，即保证可以找到多目标优化问题所有的帕累托最优解。该算法的基本思想是在每轮迭代中找到一个帕累托最优解，并在算法迭代的比较过程中将被支配的解从候选集中删除，从而避免不必要的计算量。

快速离散多目标优化算法主要包括四个步骤：

1）从可行解全集Ω中选择一个可行解，对于前景像素采样问题Ω=Ω_F，对于背景像素采样问题Ω=Ω_B。

2）逐一比较选中的可行解与可行解全集Ω中的其他解。若比较过程中其中一个解被另一个解支配[6]，则将被支配的解从Ω中移除。若选中的解被移除，则参与比较的另一个解成为被选中的解，并重复步骤2。

3）将选中的可行解加入帕累托最优解集合，并将其从Ω中移除。

4）重复上述步骤直到Ω为空。

算法1-1给出了快速离散多目标优化算法的具体实现方式。其中，swap()表示交换赋值算子。每经过一轮迭代，该算法可保证找到一个帕累托最优解。假设一个给定的离散多目标采样问题包含k个帕累托最优解，快速离散多目标优化算法可以在k轮迭代中找到所有的帕累托最优解，在比较过程中被支配的可行解不可能为帕累托最优解，因此把它从Ω集合中移除。当可行解集合中存在非帕累托最优解时（即k<n），由于Ω集合的基数不断变小，每轮迭代所需的比较次数会逐渐减少。对于多目标采样问题，帕累托最优解的数量通常小于可行解的数量。以图像抠图基准测试集[11]中植物图像的前景多目标像素采样问题为例，该图像对应的多目标像素采样问题的可行解数量为168 409，其中只有11个可行解为帕累托最优解。在多目标像素采样问题中，帕累托最优解的数量远远小于可行解的数量。因此，快速离散多目标优化算法的每一轮迭代都会将大量的被支配的可行解移除，下一轮迭代所需要的比较次数将会大幅减少，从而实现了多目标优化问题的快速求解。

输入: 一个离散多目标前景或背景采样问题，包含该问题所有可行解的数组C
输出: 修改后的可行解数组C、i （数组C的前i − 1个解为帕累托最优解）
 1: i ← 1
 2: j ←数组C的长度
 3: while i ≤ j do
 4: cmp ← i + 1
 5: while cmp ≤ j do
 6: if数组C中第i个可行解支配第cmp个可行解then
 7:        swap（C[cmp], C[j]）
 8:    j ← j − 1
 9: else if数组C中第cmp个可行解支配第i个可行解then
10:        swap（C[i]，C[cmp]）
11:        swap（C[cmp]，C[j]）
12:    j ← j − 1
13:    cmp ← i + 1
14: else
15:    cmp ← cmp + 1
16: end if
17: end while
18: i ← i + 1
19: end while

下面对快速离散多目标优化算法的时间及空间复杂度进行分析。在复杂度分析中，我们将两个可行解的支配关系比较作为算法的基本操作，并将该操作的时间复杂度与空间复杂度均认为是O（1）。首先分析算法在最优、最差及平均情况下的时间复杂度。假设对于给定多目标采样问题的可行解集为Ω，其中包含k个帕累托最优解。快速离散多目标优化算法每一轮迭代均能找到一个帕累托最优解，经过k轮迭代后，所有的帕累托最优解均可获得，满足停机条件。由于在每一轮迭代中有不少于一个可行解从Ω集合中被移除，第i轮迭代所需的比较次数不多于2（n−1−i）次，经过k轮迭代完成计算，由此可知快速离散多目标优化算法的平均时间复杂度为O（kn）。在最好的情况下，可行解全集中仅有一个可行解为帕累托最优解，即k=1。在第一轮迭代中即可求得所有帕累托最优解，且由于在比较中其余可行解均被该帕累托最优解支配，因此均从Ω集合中移除。经过第一轮迭代Ω集合即为空集，达到停机条件。因此，在最好的情况下，快速离散多目标优化算法的时间复杂度为O（n）。在最坏的情况下，所有的可行解均为帕累托最优解，即k=n。每轮迭代中仅有求得的帕累托最优解从Ω集合中被移除。因此，最坏情况下的时间复杂度为O（（1+n）n/2），简化后得到O（n2）。由于除包含所有可行解的数组以及数量有限的临时变量之外，快速离散多目标优化算法在所有情况下均不需要占用其他存储空间，因此其在最好情况下、最坏情况下以及平均情况下的空间复杂度均为O（n）。表1-1总结了快速离散多目标优化算法的时间与空间复杂度分析结果。

表1-1 快速离散多目标优化算法的时间与空间复杂度

3. 实验结果与讨论

下面通过两个实验对像素级多目标全局采样算法进行全面的测试。第一个实验验证文献[185]提出的采样算法是否解决了由于采样准则冲突或采样空间不完整导致的最优前景/背景像素对丢失问题。第二个实验验证文献[185]提出的采样算法是否能提高基于采样的抠图算法获得透明度遮罩的质量。

实验中所使用的图像来源于Rhemann等人提出的抠图透明度遮罩客观评价基准数据集[11]。该数据集包含35幅自然图像，其中27幅为提供标准抠图透明度遮罩的训练图像，其余8幅为不公开抠图透明度遮罩的测试图像。该数据集为测试集中的图像提供三种不同类型的三分图，其中一种由用户手工标记获得，其余两种是通过使用不同大小的结构元素对标准的抠图透明度遮罩做形态学操作自动产生的（其中使用较小的结构元素所获得的三分图未知区域较小，使用较大的结构元素所获得的三分图未知区域较大）。该数据集为训练集中的图像仅提供自动产生的三分图。本实验在一台配有双路英特尔至强E5 2620中央处理器和32GB内存的服务器上进行。

（1）像素级多目标全局采样算法性能验证实验

本实验通过将像素级多目标全局采样算法与两个先进抠图像素采样算法进行对比，验证其采样性能。

本实验采用两个评价指标定量评价像素级多目标全局采样算法的采样性能。第一个评价指标为最小透明度绝对误差。绝对误差之和已经被广泛应用于抠图透明度遮罩的客观评价[3-8，11]。在基于采样的抠图算法中，给定一个前景/背景像素对就可以通过式（1-4）求得一个未知像素的透明度值，即对于一个未知像素，前景/背景像素对直接决定了其估计的透明度。因此，可以通过透明度遮罩的误差来评价前景/背景像素对的质量。给定一个未知像素，如果与其他前景/背景像素对相比，一个前景/背景像素对所对应的透明度更接近于标准透明度遮罩中该像素的透明度的取值，则可认为该像素对优于其他像素对。本实验通过比较前景/背景像素对对应的透明度绝对误差来比较不同像素采样算法的性能。首先将采样所获得的前景样本集合与背景样本集合做笛卡儿积，得到前景/背景像素对候选集；然后计算每个前景/背景像素对对应的透明度，并与标准透明度遮罩中对应的透明度进行对比，取候选集中误差最小的透明度绝对误差作为采样算法评价指标。最小透明度绝对误差越小，表示采样算法发生最优前景/背景像素对丢失的情况越少，其采样性能越好。当最优前景/背景像素对丢失时，候选集中的像素对所对应的透明度均与标准抠图透明度遮罩中对应的透明度存在较大偏差，造成最小透明度绝对误差指标的值显著增大。本实验中采用的第二个评价指标为通过采样获得的前景样本集合与背景样本集合的笛卡儿积产生的候选像素对集合的基数。最新的研究表明少量的像素样本即可有效地表示未知区域的颜色[7-8]，由于最优像素对选择环节将逐一评价候选集合中的像素对，基数较大的候选集将耗费大量的时间。如果两个采样算法所获得的像素样本集合具有相同的最小透明度绝对误差，其中一个产生的候选集基数庞大，则产生基数较小候选集的采样算法具有更好的实用性。候选像素对集合的基数对抠图实际应用具有重要意义。

本实验中使用了基准数据集的27幅提供标准抠图透明度遮罩的图像以及对应的自动生成的未知区域较小的三分图。所使用的27幅图像分别包含38 573、57 461、121 014、178 728、29 357、55 831、52 970、142 232、90 208、51 540、61 930、33 836、143 935、37 039、43 538、87 834、51 098、56 751、25 462、49 105、121 177、65 605、63 437、49 174、59 459、153 224、102 471个未知像素。

本实验使用了两个先进的抠图像素采样算法作为采样性能的基准，分别是基于KL散度的采样算法[7]（KL-Divergence）以及综合采样算法[6]（Comprehensive）。基于KL散度的采样算法在对GT02及GT25图像采样过程中所采集到的所有像素均落在已知前景区域，未能采集到背景像素，无法得到实验结果。

图1-3a以箱线图的方式给出了像素级多目标全局采样算法及其他两个先进像素采样算法在27幅图像上的最小透明度绝对误差。图中每一个立柱描述了一个采样算法在基准数据集中一幅图像的所有未知像素对应的最小透明度绝对误差的分布情况。如图1-3a所示，与现有的像素采样算法相比，像素级多目标全局采样算法在绝大部分图像中最小透明度绝对误差较低，表示文献[185]提出的采样算法对于不同的未知像素所获得的样本集合均包含透明度误差较小的前景/背景像素对。在GT16图像中，基于KL散度的采样算法及综合采样算法，对于超过四分之一的未知像素的最小透明度绝对误差超过0.5，说明在该图像采样过程中存在最优前景/背景像素对丢失的问题。像素级多目标全局采样算法对应的最小透明度绝对误差四分位数仅为0.1左右，远低于参与比较的另两个采样算法。该实验结果表明像素级多目标全局采样算法有效缓解了最优前景/背景像素对丢失的问题。图1-3b为像素级多目标全局采样算法及其他两个先进像素采样算法在27幅图像上对应候选像素对集合的基数的箱线图。图中每一个立柱描述了一个采样算法在基准数据集中一幅图像的所有未知像素对应的候选像素对集合基数的分布情况。此外，从图1-3b中可以发现，像素级多目标全局采样算法以及基于KL散度的采样算法获得的前景/背景像素对候选集基数较少，比综合采样算法获得的候选集基数低了一个数量级。该实验结果进一步说明了像素级多目标全局采样算法能使用较小的候选集涵盖针对不同未知像素的高质量的前景/背景像素对，实现精准的像素样本采集。

图1-3 像素级多目标全局采样算法与先进抠图像素采样算法定量比较实验结果（见彩插）

表1-2、表1-3分别对三个像素采样算法的最小透明度绝对误差的第一、第二、第三分位数进行了比较和统计分析。表1-3最后一列汇总了27幅图像中像素级多目标全局采样算法最小透明度绝对误差指标在该分位数占优及不占优的图像数量。与基于KL散度的采样算法相比，像素级多目标全局采样算法的最小透明度误差的第一、第二、第三分位数在所有参与实验的图像中均占优。与综合采样算法相比，像素级多目标全局采样算法的最小透明度误差第三分位数在所有参与实验的图像中均占优，其最小透明度绝对误差第一、第二分位数在大部分参与实验的图像中占优。

表1-2 像素级多目标全局采样算法与现有像素采样算法的最小透明度误差分位数对比结果

注：1. “+”表示像素级多目标全局采样算法获得的最小透明度误差小于参与比较的采样算法。

2. “-”表示像素级多目标全局采样算法获得的最小透明度误差大于参与比较的采样算法。

3. 最小透明度绝对误差越小越好。

表1-3 像素级多目标全局采样算法与现有像素采样算法的最小透明度误差分位数对比结果（续）

注：1. “+”表示像素级多目标全局采样算法获得的最小透明度误差小于参与比较的采样算法。

2. “-”表示像素级多目标全局采样算法获得的最小透明度误差大于参与比较的采样算法。

3. 最小透明度绝对误差越小越好。

上述实验结果表明，像素级多目标全局采样算法生成的前景/背景像素对候选集具有基数小的优势，可获得较小的透明度绝对误差，且能适应在不同场景的图像中不同未知像素的变化。这一实验结果还说明了像素级多目标全局采样算法能精确地覆盖大部分未知像素的最优前景/背景像素对，具有较好的像素采样性能。

为了进一步分析采样性能，实验中以GT16图像为例比较了三个像素采样算法所采集样本的分布情况。图1-4展示了像素级多目标全局采样算法以及其他两个先进采样算法所获得像素样本的分布情况。图中未知像素用“+”标注，各个采样算法采集到的前景像素样本与背景像素样本分别用红色及蓝色点表示。前景/背景像素对候选集中透明度绝对误差最小的像素对用浅红色与浅蓝色标注。在这个例子中，未知像素对应的最优前景/背景像素对使得颜色相近与空间距离相近的采样准则冲突。如图1-4c所示，虽然综合采样算法采集了大量的样本，但是其未能采集到蓝色旗子的前景样本，造成了最优前景/背景像素对丢失问题。如图1-4a、图1-4b所示，像素级多目标全局采样算法与基于KL散度的采样算法均能采集到蓝色旗子样本，像素级多目标全局采样算法所采集的样本更接近于未知像素的颜色，其对应的最小透明度绝对误差为0.37，远小于基于KL散度的采样算法所对应的最小透明度绝对误差0.89。该实验结果说明了与现有的采样算法相比，像素级多目标全局采样算法可采集更准确的前景/背景像素对。

图1-4 像素级多目标全局采样算法与其他两个先进像素采样算法获得的像素样本分布对比（见彩插）

本实验表明像素级多目标全局采样算法可自适应地为不同的未知像素提供一个基数较小但能获得较低最小透明度绝对误差的前景/背景像素对候选集合。像素级多目标全局采样算法兼具基于KL散度的采样算法前景/背景像素对候选集合基数小以及综合采样算法前景/背景像素对候选集合对应最小透明度误差小的优点。即便在多个采样准则存在冲突的情况下，像素级多目标全局采样算法依然能自适应权衡多个准则，覆盖最优的前景/背景像素对，有效缓解了最优前景/背景像素对丢失问题。

（2）基于像素级多目标全局采样的抠图算法性能验证实验

本实验将利用Rhemann等人提出的抠图透明度遮罩客观评价基准数据集[11]的在线测试，实现对基于像素级多目标全局采样的抠图算法所获得的抠图透明度遮罩的客观定量分析，验证基于像素级多目标全局采样算法对抠图性能提升的影响。

在本实验中采用梯度误差性能指标，定量评价所获得的抠图透明度遮罩，选用该指标的原因在于Rhemann等人指出梯度误差与绝对误差之和、均方误差相比更能接近于主观评价的结果[11]。因此，使用该指标可获得更准确的客观评价结果，梯度误差越小说明抠图透明度遮罩质量越好。

为了验证像素级多目标全局采样算法的可扩展性，双目标及三目标两个版本的基于像素级多目标全局采样的抠图算法参与了本次实验。其中，双目标版本包括颜色及空间距离相近两个目标，三目标版本包括颜色、空间距离以及纹理特征相近三个目标。为了验证像素级采样策略的有效性，我们提出将像素级多目标全局采样算法中的像素级采样策略替换成现有算法所使用的超像素级采样策略，得到基于超像素级多目标全局采样的抠图算法（Superpixel-level Discrete Multiobjective Sampling，SDMS），并在实验中将其与基于像素级多目标全局采样的抠图算法进行比较。本实验通过Achanta等人提出的SILC算法[12]将像素聚类为超像素实现超像素级采样策略。其中，所涉及的经验参数设置与文献[6]一致。除了以上三种与像素级多目标全局采样算法相关的抠图算法外，我们将近年来提出的八种先进抠图算法，即基于稀疏编码的抠图算法[8]、基于像素块的抠图算法[13]、基于KL散度采样的抠图算法[7]、基于综合采样的抠图算法[6]、基于颜色与纹理特征加权的抠图算法[5]、K近邻抠图算法[14]、基于全局采样的抠图算法[3]、基于共享的抠图算法[15]作为测试的基准。

现有的抠图算法采用了抠图预处理与后处理流程提高其估计的抠图透明度遮罩的质量。抠图预处理通过扩大已知区域、减小未知区域的方式获得更多的已知信息，从而提高抠图质量，文献[16]详细讨论了不同预处理算法的作用。基于采样的抠图算法没有考虑像素之间的局部平滑特性，抠图后处理可以使其获得的抠图透明度遮罩更加平滑。考虑到现有的基于采样的抠图算法均采用了预处理和后处理来提高抠图的质量，为了保证比较的公平性，基于像素级多目标全局采样的抠图算法以及基于超像素级多目标全局采样的抠图算法采用了基于综合采样的抠图算法所使用的预处理及后处理方法，参数设置也与其保持一致。下面简单介绍所使用的预处理及后处理方法。预处理算法通过比较已知区域像素与未知区域边缘处的像素的相似性，扩展三分图的已知区域。给定一个已知前景区域的像素p，当未知区域的像素z满足以下条件时，未知像素z将被扩展为已知前景像素：

条件1：‖S_p−S_z‖<t_E，p∈Ω_F

条件2：‖C_p−C_z‖<t_C，p∈Ω_F （1-12）

其中，C_p、S_p分别表示像素p的RGB空间颜色向量及空间距离向量。t_C、t_E分别为颜色与空间距离特征的阈值，本实验中按照文献[6]的推荐将其均设为9。在抠图后处理中，估计的抠图透明度遮罩通过最小化一个包含拉普拉斯平滑项（Laplacian Smoothness Term）的目标函数从而获得更精确的抠图透明度遮罩。下式给出后处理涉及的目标函数的数学描述：

其中，λ为数值较大的常数，取值为1000。γ为控制数据项与平滑项之间权重的参数，取值为0.1。Λ与Γ均为对角矩阵。Λ中对应于已知区域像素的对角元素取1，对应于未知区域像素的对角元素取0。Γ中对应于已知区域像素的对角元素取0，对应于未知区域像素的对角元素取其目标函数值。

实验中使用了未知区域较大、未知区域较小以及人工标记的三种类型的三分图。对每一种类型的三分图，分别计算抠图算法在测试集中每个图像所获得的抠图透明度遮罩与标准透明度遮罩之间的梯度误差，并以所有图像的平均梯度误差作为抠图算法在对应类型三分图上的性能指标。通过取三种类型三分图对应的平均梯度误差的平均值，得到总体的平均梯度误差评价指标。

表1-4汇总了参与实验的11个抠图算法在在线图像抠图基准数据集[11]的7幅测试图像上对应不同类型三分图以及总体的平均梯度误差。如表1-4中所示，两种版本的基于像素级多目标全局采样的抠图算法（双目标采样与三目标采样）均显著改善了所估计的抠图透明度遮罩的梯度误差，两种版本的基于像素级多目标全局采样的抠图算法在总体梯度误差比较汇总分别排名第一（三目标版本）和第二（双目标版本）。三目标采样版本的基于像素级多目标全局采样的抠图算法，在未知区域较大的三分图以及人工标记的三分图的平均梯度误差比较中均排名第一。基于像素级多目标全局采样的抠图算法在三目标版本上梯度误差性能优于双目标版本。该实验结果一方面说明了基于像素级多目标全局采样的抠图算法可以通过考虑更多的采样准则提高采样性能，另一方面也说明了像素级多目标全局采样算法可以自适应地权衡多个采样准则获得高质量的像素样本。此外，基于超像素级多目标全局采样的抠图算法的梯度误差显著高于基于像素级多目标全局采样的抠图算法的梯度误差，该结果反映了超像素采样造成了最优前景/背景像素对丢失的问题，从而导致抠图性能显著下降。

表1-4 基于像素级多目标全局采样的抠图算法及现有先进抠图算法在在线图像抠图基准数据集的7幅测试图像上的梯度误差

图1-5给出了不同抠图算法获得的抠图透明度遮罩的比较。图1-5a为输入图像，图1-5b为图1-5a中黄色框区域的局部放大图像，图1-5c为基于像素级多目标全局采样的抠图算法获得的抠图透明度遮罩局部放大图像，图1-5d为基于稀疏编码的抠图算法获得的抠图透明度遮罩局部放大图像，图1-5e为基于KL散度采样的抠图算法获得的抠图透明度遮罩局部放大图像，图1-5f为K近邻抠图算法获得的抠图透明度遮罩局部放大图像，图1-5g为基于综合采样的抠图算法获得的抠图透明度遮罩局部放大图像，图1-5h为基于颜色与纹理特征加权的抠图方法获得的抠图透明度遮罩局部放大图像，图1-5i为基于全局采样的抠图算法获得的抠图透明度遮罩局部放大图像。图中的黄色箭头指示了抠图透明度遮罩误差较大的区域，与其他抠图算法相比，基于像素级多目标全局采样的抠图算法获得了边缘更锐利的高质量抠图透明度遮罩。该视觉比较结果与抠图透明度遮罩的客观定量比较结果相一致。基于像素级多目标全局采样的抠图算法可获得边缘更锐利的抠图透明度遮罩的原因主要在于其采用了像素级采样策略。前景物体的边缘处经常包含阴影及高光。由于已知前景或背景像素阴影及高光区域面积很小，因此在超像素级采样中超像素的平均颜色不能代表阴影及高光的颜色。超像素采样的像素聚类过程往往造成最优的前景/背景像素对的丢失，导致估计的抠图透明度遮罩在前景边缘区域出现较大的误差。像素级多目标全局采样算法舍弃了像素聚类操作，每一个像素均可以采集为样本。多目标优化可自适应地权衡不同的采样准则，即便在多个采样准则发生冲突的情况下依然能采集高质量的像素样本。

图1-5 不同抠图算法获得的抠图透明度遮罩的比较（见彩插）

然而，基于像素级多目标全局采样的抠图算法也存在一些局限。如图1-6所示，图1-6a为输入图像，图1-6b为图1-6a中黄色框区域局部放大图像，图1-6c为基于像素级多目标全局采样的抠图算法获得的抠图透明度遮罩局部放大图像，图1-6d为基于稀疏编码的抠图算法获得的抠图透明度遮罩局部放大图像，图1-6e为基于KL散度采样的抠图算法获得的抠图透明度遮罩局部放大图像，图1-6f为K近邻抠图算法获得的抠图透明度遮罩局部放大图像，图1-6g为基于综合采样的抠图算法获得的抠图透明度遮罩局部放大图像。在前景、背景颜色分布重合的情况下，未知像素的颜色既可以由前景像素样本表示，也可以由背景像素样本表示。基于像素级多目标全局采样的抠图算法所采用的评价函数不能在该情况下准确地选择最优的前景/背景像素对，导致抠图透明度遮罩估计的误差。

图1-6 基于像素级多目标全局采样的抠图算法的局限性（见彩插）

[1] 帕累托最优解指不存在其他在每个目标上都比其更优的可行解，帕累托最优解是多目标优化问题的最优解。

[2] n为离散多目标优化问题中可行解的数量，k为离散多目标优化问题中帕累托最优解的数量。

[3] n为多目标优化问题中可行解的数量。

[4] 对于一幅三十万像素的图像，可行解的数量通常在105数量级。

[5] n为离散多目标优化问题中可行解的数量，k为离散多目标优化问题中帕累托最优解的数量。

[6] 在多目标优化问题中，当一个解x在所有的目标中均不劣于另一个解y，且至少有一个目标上优于y时，称x支配y[10]。