CRF分割后处理（二）

Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials        2012年

摘要：大多数用于多类图像分割和标记的最新技术使用在像素或图像区域上定义的条件随机场。虽然区域级模型通常具有密集的成对连通性，但像素级模型要大得多，并且只允许稀疏的图(graph)结构。本文定义了一个在图像所有像素上的全连接的CRF，由此得到的图有数十亿条边，这使得传统的推理方法是不可行的。我们的主要贡献是为全连接的CRF提供了一种高效的近似推理算法，其中成对的边势(edge potential)由高斯核的线性组合定义。我们的实验表明，像素级的紧密连接大大提高了分割和标记的准确性。

多类图像分割与标记的一种常见的方法是将此问题作为在像素或图像区域上定义的条件随机场(CRF)中的最大后验（MAP）推理[8,12,18,19,9]。CRF势函数包含了使相似像素之间的标签一致性最大化的平滑项，并且可以集成更精细的项来模拟对象类之间的上下文关系。

基本的CRF模型由单个像素或图像区域上的一元势和相邻像素或图像块上的成对势组成[19,23,7,5]。这导致邻接的CRF结构对图像的长距离连接的建模的能力受限，并导致物体边界的过度平滑。为了提高准确度，[8,12,9,13]提出了扩展CRF，将层次连接和定义在图像区域上的高阶势结合起来。然而，这些方法依赖于无监督图像分割计算模型运行的区域，因而其精度受到无监督图像区域分割的限制，这导致难以在复杂物体边界生成精确的轮廓，尽管已经取得了重大进展[9,13,14]。

本文提出一种不同的结构来精确地语义分割，使用一个全连接的CRF，在图像的所有像素上建立成对的势。在语义分割中，全连接CRF过去也被用过[18,22,6,17]，但是推理太复杂，因而只能用在数百个或更少的图像区域上。这些方法的精度同样受到无监督图像分割的限制。相比之下，我们的模型是将图像中所有像素连接成对，从而实现了非常精确的分割和标记，主要挑战是模型太大，即使在低分辨率图像上，它也有成千上万的节点和数十亿的边。

我们的主要贡献是为全连接CRF提供了一种高效的推理算法，其中成对的边势由任意特征空间中高斯核的线性组合定义。该算法基于CRF分布的平均场近似。这种近似通过一系列消息传递步骤进行迭代优化，每个步骤通过聚合来自所有其他变量的信息来更新单个变量。我们证明了在特征空间中使用高斯滤波可以对全连接CRF中的所有变量进行平均场更新。这使得我们可以通过使用有效的近似高维滤波来降低从二次型到线性的变量数量的消息传递的计算复杂性[16,2,1]。得到的近似推理算法在模型的边数上是次线性的。

图1中，对于MSRC-21数据集的两张图像的多类分割，我们的方法能提升分割的性能。图1(d)是全连接CRF的近似MCMC推断的结果[17]。MCMC程序运行了36个小时，仅部分收敛于底图。我们也在全连接模型[11]中试验了图割推理，但运行了72小时还是没有收敛。与之不同的是，我们提出的方法在单线程下可以0.2秒内生成详细的像素级标签，如图1（e）所示。第6节提供了对MSRC-21和PAS-CAL VOC 2010数据集的定量评估。据我们所知，我们是首个在像素级全连接CRF模型实现快速推断的。

2 全连接CRF模型

给定一个在一组变量上定义的随机场。每个变量的值域是一组标签。同样的，给定在一组变量上定义的随机场。的取值遍布所有可能的、大小为的图像的输入，的取值遍布所有可能的像素级标签。用人话说，就是，表示像素的颜色向量，是该像素的标签。

一个条件随机场被描述为一个Gibbs分布：

其中

在完全连通的成对CRF模型中，G是X上的完全图，CG是所有一元和成对群的集合。相应的吉布斯能量是

在I和J范围从1到n的情况下，通过一个分类器，在一个分类器上独立地计算每个元的单元电位u（Xi），该分类器在给定图像特征的标签分配席席上产生分布。在我们的实现中使用的一元势结合了形状、纹理、位置和颜色描述符，在第5节中进行了描述。由于每个像素的一元分类器的输出独立于其他像素的分类器的输出，因此仅由一元分类器生成的地图标签通常是噪声和不一致的，如图1（b）所示。

我们模型中的成对势有如下形式

fj是任意特征空间中像素i和j的特征向量，w（m）是线性组合权重，μ是标签兼容性函数。每个核k（m）的特征是一个对称的正定精度矩阵∧（m），它定义了它的形状。

对于多类图像分割和标记，我们使用对比度敏感的两个核电位，根据颜色向量Ii和Ij以及位置pi和pj定义：

外观内核的灵感来自于这样一个观察，即附近颜色相似的像素可能在同一个类中。贴近度和相似度由参数θα和θβ控制。光滑核移除了小的孤立区域[19]。参数从数据中学习，如第4节所述。

一个简单的标签兼容性函数是由POTS模型，（席席，XJ）= [Xi＝XJ]给出的。它引入了对附近被分配不同标签的相似像素的惩罚。虽然这个简单的模型在实践中运行良好，但它对标签之间的兼容性不敏感。例如，它惩罚一对标记为“天空”和“鸟”的附近像素，惩罚程度与标记为“天空”和“猫”的像素相同。我们可以学习一个一般对称相容函数席（XI，XJ），它考虑标签之间的交互作用，如第4节所述。

全连通crf中的3个有效推理

我们的算法基于对CRF分布的平均场近似。这种近似产生了用于近似推理的迭代消息传递算法。我们的主要观察结果是，该模型中的信息传递可以在特征空间中使用高斯滤波来完成。这使得我们能够利用高效的高维近似来进行高维滤波，从而降低了信息从二次传递到线性传递的复杂性，从而得到了一种完全连通crf的近似推理算法，该算法在变量N的数量上是线性的，在模型的边数上是次线性的。

3.1平均场近似

平均场近似不计算精确分布P（X），而是计算一个分布Q（X），该分布Q（X）使所有分布Q中的KL发散D（QkP）最小化，Q（X）=Qi Qi（Xi）[10]。

最小化KL散度，同时将Q（X）和Qi（Xi）限制为有效分布，得到以下迭代更新方程：

补充材料中给出了方程4的详细推导。此更新公式导致以下推理算法：

算法1的每次迭代都执行消息传递步骤、兼容性转换和本地更新。兼容性转换和局部更新都是线性时间的，并且效率很高。计算瓶颈是消息传递。对于每个变量，此步骤要求对所有其他变量求和。因此，一个简单的实现在变量N的数量上具有二次复杂度。接下来，我们将展示如何使用近似的高维滤波来降低消息传递到线性的计算成本

3.2使用高维过滤的高效消息传递

从信号处理的角度来看，信息传递步骤可以表示为特征空间中高斯核G∧（m）的卷积：

我们从卷积函数中减去Qi（l）

此卷积执行低通滤波器，本质上是带限Q（m）i（l）。根据采样定理，这个函数可以从一组样本中重构出来，这些样本的间距与滤波器的标准差成正比[20]。因此，我们可以通过下采样Q（l），将样本与G∧（m）卷积，并在特征点处对结果进行上采样来执行卷积[16]。

高斯核的一个常见近似是截断高斯，其中超过两个标准差的所有值都设置为零。由于样本的间距与标准差成正比，因此截断核的支持度仅包含固定数量的样本点。因此，可以通过仅从恒定数量的相邻样本聚集值来近似地计算每个样本的卷积。这意味着可以在O（N）时间内执行近似的消息传递[16]。

采用这种方法的高维滤波算法在d中仍然具有指数级的计算复杂度。然而，聪明的滤波方案可以将卷积运算的复杂度降低到O（nd）。我们使用了一种高效的卷积数据结构permutohedratic，它将沿着d+1轴排列的单纯形分片到特征空间[1]。超多面体晶格利用单位方差高斯核的可分性。因此，我们需要对特征空间应用一个白化变换∮f=Uf来使用它。利用∧（m）到UU T的Cholesky分解发现了白化变换，在变换空间中，高维卷积可以沿晶格轴分离成一系列一维卷积。由此产生的近似消息传递过程是高效的，即使是完全顺序实现，也不利用并行性或图形硬件的流能力，如果需要，可以提供进一步的加速。

4学习

我们通过分段训练来学习模型的参数。首先，使用JointBoost算法[21]训练增强的一元分类器，使用第5节中描述的特征。接下来我们学习Potts模型的外观核参数w（1）、θα和θβ。将期望最大化和高维滤波相结合，可以有效地求出w（1）。不幸的是，这种方法不能有效地计算核宽度θα和θβ，因为它们的梯度包含一组非高斯核，这些核不适用于相同的加速技术。我们发现，对于所有三个核参数w（1）、θα和θβ，在保持有效集上使用网格搜索更有效。

平滑度核参数w（2）和θγ对分类精度影响不显著，但对视觉效果的改善很小。我们发现w=θγ=1在实际中工作良好。

使用L-BFGS学习相容性参数μ（a，b）=μ（b，a），以使图像I的验证集的模型的对数�似然`（μ：I，T）与相应的地面真值标签T最大化。L-BFGS需要计算梯度`，这是很难准确估计的，因为它需要计算分割函数Z的梯度。相反，我们使用第3节中描述的平均场近似来估计Z的梯度。这导致每个训练图像的梯度的简单近似：

其中（I（n），T（n））是具有其地面真值标记的单个训练图像，T（n）（a）是其中第I像素T（n）I（a）具有值1的二值图像，前提是T（n）的第I像素处的地面真值标记是a，否则为0。补充材料中给出了方程6的详细推导。

Pj=i k（fi，fj）Tj（b）和Pj=ik（fi，fj）Qi（b）的和都是直接计算的昂贵值。如第3.2节所述，我们使用高维滤波有效地计算这两个和。五阶学习算法的运行时间在变量数N上是线性的。

5实施

我们实现中使用的一元电位来自TextonBoost[19，13]。我们使用Shotton等人提出的17维滤波器组。[19] ，并跟随Ladicky等人。[13] 通过添加颜色、方向梯度直方图（HOG）和像素位置特征。我们对MSRC-21数据集的评估使用这个扩展版本的TextonBoost来计算一元电位。对于VOC 2010数据集，我们将每个对象类的边界框对象检测器的响应[4]作为20个附加特征。这将一元分类器在VOC 2010上的性能从13%提高到22%。通过训练一个logistic回归分类器对增强分类器的响应，我们获得了额外的5%。

为了有效地进行高维滤波，我们使用了一个公开的permutohedrattice实现[1]。我们发现一个标准差的下采样率对我们所有的实验都是最好的。基于采样的滤波算法低估了非常相似特征点的边缘强度k（fi，fj）。正确的规范化可以消除大部分错误。permutohedral晶格允许两种类型的规范化。平均核强度k=1npi，jk（fi，fj）的全局标准化可以修正常值误差。由Ki＝Pj k（Fi，FJ）进行像素化归一化处理区域误差，但违反CRF对称假设p（席席，XJ）＝P（XJ，XI）。我们发现像素级规范化在实践中效果更好。

6评价

我们在两个多类图像分割和标记的标准基准上对所提出的算法进行了评估。第一个是MSRC-21数据集，它由591幅320×213大小的彩色图像和21个对象类的相应地面真值标签组成[19]。第二个是PASCAL VOC 2010数据集，它包含1928幅大小约为500×400的彩色图像，共有20个对象类和一个背景类[3]。该方法与Shotton等人的邻接（网格）CRF一起进行了评估。[19] 以及Kohli等人的稳健P n-CRF。[9] ，使用公共可用的引用实现。为了确保公平比较，所有模型都使用了第5节中描述的一元电位。所有的实验都是在英特尔i7-930处理器上进行的，其时钟为2.80GHz。八个CPU核用于训练；所有其他实验都在一个核上进行。推理算法在单个CPU线程中实现。

汇聚。

我们首先通过分析Q和P之间的KL散度来评估平均场近似的收敛性。图2显示了在推理算法的连续迭代中Q和P之间的KL散度。KL散度被估计为一个常数，如补充材料中所述。结果表明，核的标准差θα和θβ不同。这些图在20次迭代时对齐，以便进行视觉比较。在随后的所有实验中，迭代次数都设置为10。

MSRC-21数据集。

我们将数据集分成45%的训练图像、10%的验证图像和45%的测试图像[19]。在训练集上学习一元电位，而所有CRF模型的参数则通过holdout验证来学习。CRF的总训练时间为40分钟。学习的标签兼容性函数与此数据集上的Potts模型相同。图3提供了数据集的定性和定量结果。我们报告了多类分割精度的标准度量：“全局”表示正确分类图像像素的总体百分比，“平均”是每类分类精度的未加权平均值[19，9]。本文提出的基于全连通CRF的推理算法明显优于其他模型，并与数据集提供的标准地面真值数据进行了比较。MSRC-21数据集提供的地面真值标签是相当不精确的。特别是，对象边界周围的区域通常没有标记。这使得很难定量评估那些追求像素级精度的算法的性能。遵循Kohli等人。[9] ，我们为MSRC-21数据集的一组图像手动生成精确的分割和标记。每个图像都在像素级进行了完整的注释，并在复杂的边界周围进行了仔细的标记。该标记是由手工从MSRC-21数据集94个代表性的图像。为单个图像添加标签平均需要30分钟。图3显示了这个“精确地面真相”集合中的一些图像。图3报告了对该地面真实数据的分割精度，以及对标准地面真实数据的评估。结果是通过5倍交叉验证获得的，94张图像中有45张用于训练CRF参数。一元电位是在一个单独的训练集上学习的，其中不包括94个精确注释的图像。

我们还采用了Kohli等人提出的方法。[9] 用于评估边界周围的分割精度。具体来说，我们计算从精确的地面真值图像中获得的实际物体边界周围窄带（“trimap”）内的误分类像素的相对数量。如图4所示，我们的算法在所有trimap宽度上都优于以前的工作。

帕斯卡VOC 2010。

由于在帕斯卡VOC 2010测试集中没有公开的地面真实性标签，我们使用所有实验的训练和验证数据。我们将图像随机分为3组：40%训练组，15%验证组和45%测试集组。使用标准VOC测量法测量分割精度[3]。在训练集上学习一元电位，平均分类准确率为27.6%。在验证集上学习了全连接CRF模型中Potts电位的参数。Potts电位全连通模型的分类准确率平均为29.1%。在验证集上学习的标签相容性函数进一步提高了分类精度，达到30.2%。相比之下，grid-CRF达到28.3%。训练时间为2.5小时，推理时间为0.5秒。定性结果如图5所示。

远程连接。

我们通过改变外观核的空间和颜色范围θα和θβ，并分析由此产生的分类精度，检验了模型中长距离连接的值。在这个实验中，w（1）保持不变，w（2）设为0。结果如图6所示。随着距离的增加，精度逐渐提高，在空间标准差θα=61像素和颜色标准差θβ=11时达到峰值。在此设置下，模型中超过50%的成对势能被分配给长度为35像素或更高的边。然而，远程连接也可能传播误导性信息，如图7所示。

讨论。

针对完全连通的CRF模型，提出了一种高效的近似推理算法。结果表明，密集像素级的连通性可以显著提高像素级分类的精度。我们的单线程实现在几秒钟内处理基准图像，并且该算法可以并行化以进一步提高性能。