基于全连接条件随机场的图像语义分割算法研究

高宇田，杨阳，赵广帅，刘智

（长春理工大学 电子信息工程学院，长春 130022）

机器人在探索未知环境过程中通常需要与周围环境之间进行交互感知，例如对桌子上的水杯进行抓取操作或者计算距离最近的椅子的位置等等。因此，视觉场景的理解对于机器人[1]来说至关重要。语义分割对机器人视场中每个对象进行语义标注，为机器人提供丰富的语义信息，能够很好的表示出机器人来到了什么地方，“看”到了什么样的东西，有效地解决了机器人的场景理解问题。

本文利用具有稀疏高阶项的全连接条件随机场来解决语义分割问题。条件随机场（Condi⁃tional Random Field，CRF）是计算机视觉中几种问题建模的常用框架[2-3]。目前，随着深度学习的发展，卷积神经网络逐渐开始在图像语义分割方面占据主导地位，FCN（fully convolutional network）[4]，SegNet[5]、DeepLab[6]等深度学习框架实现了像素级别的语义分割。但这种黑盒模型并不能很好的给予明确的数学解释，而且由于这种不透明性，深度学习只能依赖网络层数的增加来提高分割的结果。条件随机场能够提取图像的多方面信息，通过图像像素间的相关性构建能量函数模型，最后通过能量最小化方法来求解该模型，实现图像的语义分割。

传统CRF[7-8]的能量函数由两项组成：依赖于一个随机变量标签的一元势函数和依赖于两个随机变量标签的二元势函数。这种传统模型只考虑到了图像局部像素之间的约束关系，没有关注到更高级依赖关系。而高阶CRF[9-10]在传统基础上增加了由多个随机变量集合的高阶势函数，使得依赖关系由局部推广到全局图像，将模型扩展到超像素[15]之间的依赖关系。能量函数模型建立之后，接着利用能量最小化方法进行模型求解。针对CRF能量函数的最小化问题，研究者们开发了几个精准的离散优化问题[11-12]的连续松弛推理算法。这种松弛推理法的一个重要优点是便于分析，但是用于求解这种松弛的算法却不能很好地解决成对连接的数量问题。为了克服上述不足，传统的能量最小化方法使用4邻域或者8邻域的稀疏CRF网络连接结构。虽然稀疏连接结构能够很好地适应这种松弛法，但是由于自身稀疏的局限性，构建的模型无法获得准确的标记，而全连接的CRF网络中每一个像素节点和网络中所有像素有关，可以获得更准确的标记。为了解决全连接CRF 的能量最小化问题，Krahenbuhl和 Koltun[13]使用了平均场（mean-filed，MF）推理算法[14]，Vineet等人[15]同样利用这种算法对具有稀疏高阶势的全连接CRF进行平均场推理，进一步提高了分割精度，但是这种滤波算法存在一定的弊端，不能对解的质量提供有力的理论保证。Desmaison等人针对传统CRF提出了二次规划（quadratic programming，QP）松弛推理算法来求解能量最小化问题，消除了平均场推理算法的弊端，但是传统CRF的局限性又限制了算法的分割效果。

针对上述问题，论文提出了一个具有稀疏高阶势的全连接CRF的QP松弛以及其能量最小化框架。将能量函数表示为QP松弛，并且提出了基于Pn-Potts模型[16]的高阶项的松弛，利用现有能量最小化算法处理这些高阶势，同时在每次迭代中保持标签和随机变量数量的线性复杂度。本文证明了QP松弛的条件梯度可以用标签数和随机变量数的复杂线性来计算，通过分析计算得到下降方向的最佳步长，最后使用Frank-Wolfe算法有效地最小化QP松弛。

1 高阶条件随机场模型建立

具有稀疏高阶势的全连接CRF模型是由随机变量及其对应标签描述的。定义N个随机变量集合X={X1,…,XN}，其中每个随机变量Xa从M个标签的集合L={l1,…,lM}中取一个标签，记为标签向量x∈LN，其中x的元素xa对应于随机变量Xa。其中，随机变量对应一个像素节点，相关标签对应一个语义类。接着引入团的概念，团代表一个超像素，超像素是共享相似颜色信息的相邻像素的集合，在这里使用均值漂移算法[17]来生成超像素。将包含三个或更多随机变量的团表示一个高阶势，而包含两个随机变量的团表示一个二元势。给定的团Sp为X的子集，包含高阶势的团集合S定义如下：

其中，R表示集合S中团的总数。集合Rp表示团Sp中随机变量的索引集，可以形式化地表示为Rp={a∈{1,…,N}|Xa∈Sp}。接着引入向量xp，由两个以上元素xi构成，即团Sp中随机变量的标签。因此将能量函数定义如下：

其中，ψa(xa)为一元势，表示将随机变量Xa赋值为标签xa的代价；ψa,b(xa,xb)为二元势，表示将随机变量Xa和Xb分别分配给xa和xb的代价；ψp(xp)为高阶势函数，表示Sp中所有随机变量分配标签xp的代价。下面将分别介绍能量函数中每项的具体表现形式。

1.1 一元势

本文使用的一元势来自TextonBoost[18]。其一元势定义为分配给每个像素的标签概率分布的负对数，其中p(xa)是第a个超像素的标签概率分布，通过基于像素特征训练的分类器对像素分类获得。形式如下：

1.2 高斯二元势

高斯二元势定义为两个连接的像素节点的标签概率函数，形式如下：

其中，μ(xa,xb)表示标签兼容性函数；Kab是像素兼容性函数；w(m)是一个标量加权因子；为高斯核函数。二元势函数起到平滑的作用，即当两相邻像素点标签不具备一致性时，给予一定的惩罚。将像素兼容函数定义为双高斯核形式：

式中，Ia、Ib和pa、pb分别表示像素a和b的颜色向量和空间位置向量；参数w(1)和w(2)为平衡两项的权重为模型参数，可以通过交叉验证得到。第一项为外观内核，根据相似颜色和位置的像素可能具有相同的标签得到；第二项为平滑内核，用于惩罚孤立的小区域。

标签兼容性函数μ(xa,xb)构成分配随机变量Xa和Xb的代价的一部分，标签分别对应于xa和xb的值。本工作使用的标签兼容函数为Potts模型，具体如下：

1.3 高阶势

利用Pn-Potts模型[19]推导出高阶势。高阶势表示如果团Sp的元素的标签与当前超像素标签一致，不进行惩罚；否则给与一定的惩罚，将其设置为与超像素颜色信息的方差成正比。高阶势定义为：

其中，Γ和η是交叉验证的参数，表示团Sp内像素颜色值的方差。团Sp代表一个超像素，在这里使用均值漂移算法来生成超像素的同时，通过交叉验证确定超像素的大小以确保得到与问题相匹配的高阶势。

2 QP松弛推理算法

在建立高阶CRF模型后，需要对该模型进行高效求解，即对函数能量进行最小化以获得最优标记结果。一般将求解CRF模型作为最大后验概率问题，或者叫做作推理问题。Desmaison等人针对传统CRF提出了QP松弛推理算法来求解能量最小化问题，本文在其基础上提出了一种基于高阶CRF的QP松弛推理算法。算法先将带有高阶势的能量函数转化为整数规划形式，再得到QP松弛的目标函数，最后通过Frank-Wolfe算法[20]对其进行最小化。

2.1 整数规划

整数规划方法是目前适合连续松弛的能量最小化方法。因此，先将能量函数式（3）转化为整数规划形式：

其中，二元变量ya:i∈{0,1}表示随机变量Xa是否具有标签li；向量中包含指标变量xp。第一项约束确保每个随机变量只能分配一个标签，第二项约束确保标签是二进制的 。是阶数等于团Sp中的随机变量数的多项式。为了简化θp(⋅)运算，利用稀疏高阶势中的标签一致性，可以重新构造该高阶多项式简化计算。定义如下：

由于式（10）为NP-hard问题[18]，通过放宽整数约束来近似IP进而解决能量最小化问题，得到QP松弛，接下来使用基于滤波器的方法来优化QP松弛。将式（9）中一元势和二元势表示为向量形式，其中一元势为向量y与一元项的向量ψa∈ℝNM的点积；二元势ψab∈ℝNM×NM表示为标签兼容函数矩阵μ∈ℝM×M与像素兼容函数矩阵K(m)的克罗内克积，ψab∈ ℝNM×NM定义如下：

接着对目标函数的高阶项进行定义。通常，高阶多项式的阶数等于每个团中的随机变量数。由于利用标签一致性可以将这个高阶多项式重新表示为一个低阶多项式，因此引入一个二值变量zp:i，表示团Sp中的所有随机变量是否都使用标签Li。定义如下：

接着引入一个指标项Hp(a)，用来表示随机变量Xa是否属于团Sp，定义如下：

由此，将目标函数的高阶项进行如下定义：

根据式（13）和式（14）的定义，容易发现最后一项的值总是为0，当放宽指标变量ya:i和辅助变量zp:i的二值约束，使它们取0到1之间的分数时，后一项就提供了zp:i和ya:i之间的耦合，同时也解决了无法在多项式时间内求解的NP-hard问题。Hp(a)的值构成了稀疏矩阵H，H是一个由1组成的稀疏矩阵，使得元素按照正确的顺序进行求和；矩阵C是包含常数Cp的对角矩阵；向量1z和1y是所有1的向量；zp:i向量形式表示为z。最后，QP松弛可以正式定义为：

2.2 最小化

完成目标函数（16）的定义后使用Frank-Wolfe算法[12]对其进行最小化。通过计算目标函数的梯度、有效的条件梯度和最佳步长实现。算法在每次迭代中保持像素和标签数量的线性关系，通过像素和标签数量线性的复杂度来计算条件梯度。

将目标函数的梯度定义为：

一元项保留为常数，使其与标签和随机变量的数量成线性关系；二元项计算利用基于滤波器的方法；对于高阶项，由于团与团之间没有交集，因此只对每个团中的标签和像素进行求和。然后按照标签和像素数量线性变化的复杂度进行条件梯度计算。条件梯度计算公式为：

其中，sy和sz为f(y,z)的条件梯度。最佳步长通过最小化单个变量的二次函数来计算，最小值可以通过分析计算得到。Frank-Wolfe算法的最佳步长计算公式为：

根据式（19）得到最佳步长，使目标函数得到快速收敛，算法不断循环直到实现最终收敛。由于算法中基于过滤器的方法每次迭代只调用一次，使QP最小化算法具有一定的高效性。

3 仿真验证与分析

为了验证算法的有效性，采用Pascal VOC2012公开数据集进行实验验证，该数据集为验证图像语义分割的基准。Pascal包含1 928张彩色图像，尺寸约为500×400像素。将数据集中50%的图像作为训练集，进行一元势的训练，15%作为验证集，得到内核和高阶势参数，最后35%作为测试集进行评估。将本文高阶CRF算法表示为QP-H，同时在不引入高阶势的情况下进行了实验，能量函数仅由一元势和二元势，同时使用QP推理算法进行能量最小化，表示为QP。为了验证算法的优越性，对基于平均场推理算法[10]的全连接CRF也进行实验，表示为MF。所有实验都在2.80 Ghz Intel Core i5-8400处理器上进行。

本次实验将平均能量、时间、准确性以及重叠度作为评估标准。其中重叠度表示正确标记的像素与语义分割后的像素的交集占正确标记的像素与分割后的像素的并集的比例。表1给出了MF、QP及QP-H三种算法的实验结果，图1表示了三种算法的能量的下降过程，图2和图3给出了三种算法的语义分割结果。

表1 综合对比

图1 三种算法的能量下降过程

图2 Pascal数据集MF、QF、QF-H三种算法的语义分割结果对比（一）

图3 Pascal数据集MF、QF、QF-H三种算法的语义分割结果对比（二）

表1给出的结果可以看出，QP与MF相比，平均能量更低，算法时间有所增加，但是准确性及重叠度提高不明显；QP-H与MF和QP比较的平均能量更低，同样由于模型复杂度的提高，算法时间做出了一些牺牲，但是准确性和重叠度得到了一定的提高。由图1中三种算法的下降过程可以明显的看出QP-H能量最小化的效果最为明显。由图2中三种算法的分割结果可以明显的看出QP-H的分割精度有了一定的提高。由此可以得到，QP-H以牺牲了部分算法时间为代价实现了更有效的能量最小化，最终分割精度得到了一定提高。

4 结论

本文提出了具有稀疏高阶势的全连接CRF的QP松弛以及其能量最小化框架，并通过Pascal公开数据集进行验证，实验证明该算法能够有效地实现能量最小化，并使得语义分割结果有一定的提高。该模型消除了传统CRF的局限性，而且由于使用了高斯二元势，并在高阶项上加强了标记一致性，算法的每次迭代在标记数和像素数上都表现出时间复杂度的线性关系。但是由于高阶势提高了模型复杂度，使得算法执行时间有一定的牺牲，未来还需要继续进行相关工作的研究。目前看来，高阶势的利用是条件随机场未来的发展趋势，并且在结合深度学习后，会更加提高语义分割的精度，推动语义分割算法的发展。