基于完全联系的条件随机场的图像标注

刘 彤,黄修添,马建设,苏 萍

(清华大学 深圳研究生院,广东 深圳 518055) (*通信作者电子邮箱709794457@qq.com)

基于完全联系的条件随机场的图像标注

刘 彤,黄修添*,马建设,苏 萍

(清华大学 深圳研究生院,广东 深圳 518055) (*通信作者电子邮箱709794457@qq.com)

传统的图像标注模型通常存在两个问题：只能够对短距离的像素上下文信息进行建模和复杂的模型推理过程。为了提高图像标注的精度、简化图像标注的模型推理过程，采用完全联系的条件随机场模型进行图像标注，提出利用基于高斯kd树的平均场估计方法实现该模型的高效推理。为了更好地验证算法的有效性，实验的图片数据库不仅包含标准的图片库——剑桥大学微软研究图片库(MSRC-9)，还包含作者制作的机械零件图片库(MyDataset_1)和办公桌图片库(MyDataset_2)。新算法在三个图片库上的平均标注精度分别可以达到77.96%、97.15%和95.35%，每幅图的平均运行时间为2 s。实验结果表明，基于完全联系的条件随机场的图像标注能够更充分地考虑不同的像素上下文信息来提高标注精度，而基于高斯kd树的模型推理能够提高模型推理的效率。

条件随机场;图像标注;上下文信息;高斯kd树;模型推理

0 引言

图像标注技术能够使计算机自动解析图像场景,对图像中的多类别进行分割和识别,从而完成各种需要人才能完成的任务。由于图像标注能够解析图像场景,因此受到了许多国内外学者的关注和研究。当前,许多多目标类别图像分割和标注问题的先进技术都采用条件随机场(Conditional Random Field, CRF)模型[1]实现:杨耘等[2]利用图像标注对遥感图像进行分类,李林等[3]阐述了基于概率图模型的整体场景理解,张微等[4]提出了基于超像素的条件随机场的图像分类。这些CRF模型不仅可以在图片全局或局部区域实现[5-6],还可以在像素层次实现[7-8]。标准的CRF模型[9]只能对图片的局部信息进行建模,从而损失了图片的全局信息。因此,在图像语义分割实际应用中,一些非常直观的错误就会产生,比如,“狗”可能会出现在“天空”中。为了更好地挖掘图片的局部信息和全局信息,文献[10]提出了多层次的CRF模型。多层次的CRF模型通过组合图片中不同空间尺度的特征信息来获取图片的局部信息和全局信息。然而,虽然多尺度的CRF模型能够同时挖掘图片的局部和全局信息,但是因为考虑到多个层次的空间尺度,因而该模型涉及大量的变量和参数。同时,该模型的学习和推理阶段采用的是随机采样方法,所以效率较低。因此,在图像语义分割的实际应用中,图片数据库的图片数量以及类别数量成为了制约该模型应用的两个主要因素。2009年,Shotton等[7]通过增强学习算法[11]对图片长距离像素的关系进行建模。Pinto等[12]提出了分层的CRF模型,该模型通过采用一种简单的分层结构,能够同时对图片中长距离和短距离像素之间的关系进行建模。其中,第一层结构对图片类别或者相邻区域的相互关系进行建模,而第二层结构则是对相邻像素之间的关系进行建模。虽然分层的CRF模型能够挖掘图片中不同层次的上下文信息,但是却并未考虑到图片的全局信息,从而导致图像语义分割的结果高度依赖于局部特征信息。文献[13]将局部信息和全局信息都作为条件随机场的组成部分,然而由于该方法需要考虑到所有类别之间的关系,因此如果图片中物体类别较多时,基于该模型的图像语义分割不仅计算非常复杂,而且实验结果精度不高。

综上,基于不同层次条件随机场的图像标注存在以下不足:

1)基于区域层次的图像标注通常只能考虑相邻区域块的关系,无法捕捉不相邻图片区域块的上下文语义信息。

2)基于像素层次的图像标注虽然能够在像素层次上提取图片特征信息,但是基于像素层级的图像标注的概率图模型节点和节点之间的边过多,导致模型的推理过于复杂。因此传统的基于像素层次的图像标注通常也只会考虑相邻像素的上下文信息。

3)基于完全联系的条件随机场的图像标注[13]由于每组像素对之间都存在联系,因而模型十分复杂,从而导致模型推理变得困难。

为了解决图像标注技术中图片上下文信息挖掘不充分的问题,本文采用完全联系的条件随机场模型作为图像标注的模型；又由于基于完全联系的条件随机场模型中节点和节点的联系过多导致模型推理困难,还提出了一种新的推理方法——基于高斯kd树[14]的平均场估计方法。

1 完全联系的条件随机场模型

给定定义在变量集合{X1,X2,…,XN} 上的随机场X,N是变量个数。每一个变量的值域是标签集合L={l1,l2,…,lK},其中K是标签个数。同时考虑另外一个随机场F,它是定义在变量集合{F1,F2,…,FN}上的。在本文中,Y代表大小为N的输入图片集合,X代表对应的图片语义分割结果。Fj代表像素j的颜色向量,Xj表示像素j的标签结果，因此条件随机场(F,X)的吉布斯分布表示为:

(1)

其中:G=(ν,ε)是定义在X的图模型,每一个团c都包含一个对应的势能函数φc[1]。每一组标签x∈LN的吉布斯能量为:

(2)

对应的最大后验概率标注是:

(3)

为了书写方便,后文用ψc(xc)代替ψc(xc|F)。

在完全联系的CRF模型中,G是定义在X上的完全图,CG是所有单一团(单一像素点)和成对团(像素对)的集合。对应的吉布斯能量如式(4)所示：

(4)

其中:索引i,j∈{1,2,…,N}代表像素点的索引; p代表势能函数为成对势能; u代表势能函数为单一势能。单一势能项(unary potenials)ψu(xi)是通过训练得到的分类器,它是通过计算像素的标签为xi的概率分布得到的。本文中单一势能项用到的图片特征包括:颜色、纹理、梯度特征等。由于单一势能项中仅考虑独立像素的特征,因而图片标注的结果常常不光滑并且含有噪声,如图1所示。

图1 仅考虑单一势能项的标注结果

本文中的成对势能项(pairwise potentials)具有如下形式:

u(xi,xj)k(fi,fj)

(5)

其中每一个k(m)都是一个高斯核函数,如式(6)所示:

(6)

其中:fi、fj分别是像素i、j位置任意维度的特征向量;w(m)是线性组合的权重;u表示标签兼容函数(compatibility function)。每一个核函数k(m)的形状由对称正定矩阵Λ(m)确定。

针对不同的图片特征,可以使用不同的核势能函数。文献[8]定义了两种对比度敏感的核势能,分别包括颜色和位置两种信息,其表达式如下:

(7)

其中：Ci、Cj代表像素位置pi、pj上的颜色向量。颜色向量由RGB三维向量组成,位置向量由水平和竖直两个方向组成。式(7)右边第一项称为外观内核(appearance kernel),第二项称为平滑内核(smoothness kernel)。外观内核基于这样一种假设:相邻且颜色相近的像素很可能属于同一类别。其中像素相邻和近似的程度由参数θ1、θ2确定。平滑内核的作用是移除孤立的小区域[7]。

波特模型是一种最简单的兼容函数u,它的形式为u(x1,x2)=[x1≠x2],即当x1≠x2时,u的取值为1；反之为0。因而兼容函数的作用是对相邻且相似但是取不同类别标签的像素对进行惩罚补偿，虽然波特模型比较简单,但是在实际应用中它通常能够很好地工作[8]。

2 模型推理

由于高阶CRF模型的精确推理是一个NP困难问题,因此本文采用一种信息传播的近似推理算法。在完全联系的CRF模型中的信息传播可以通过特征空间的高斯滤波实现,通过这种方法可以将信息传播的复杂度从O(N2)减小到O(NlogN),其中N代表CRF模型中的节点个数。

2.1 平均场估计

为了计算精确的概率分布P(X),平均场估计通过最小化KL(Kullback-Leibler)散度从分布集合Q中寻找分布Q(X)代替精确的概率分布P(X),其中分布集合Q都可以写成独立的边缘概率分布的乘积[15],即

(8)

其中:Qi(Xi)表示在变量Xi的边缘概率分布。由式(4)可得完全联系条件随机场的吉布斯分布:

(9)

其中:Z是配分函数。平均场估计通过最小化KL散度寻找近似的概率分布Q(X),具体推导过程如下:

EU～Q[logQ(U)]-EU～Q[logP(U)]=

logZ+EU～Q[E(U)]

(10)

其中EU～Q代表给定分布Q下的期望值。通过拉格朗日方程可以得到边缘概率分布Qi(Xi):

(11)

由式(5)和式(11)可得式(12)：

Qi(xi=l)=

(12)

由式(12)可得完全联系条件随机场的平均场估计算法:

1)按式(13)初始化概率分布Q：

Qi(xi)=(1/Zi) exp(-ψu(xi))

(13)

2)当概率分布Q不收敛时重复执行a)～d):

a)对所有的m,计算所有像素对之间的信息传播值:

(14)

b)考虑兼容函数对概率分布的影响:

(15)

c)局部更新式(15):

(16)

d)归一化Qi(xi)。

上述算法的核心部分由过程a)、b)和c)组成,其中过程b)与过程c)和图模型的变量个数成线性关系,因而执行效率非常高。然而,在过程a)中,对于某个变量需要计算所有其他变量对该变量的信息传播值,所以该过程具有变量的平方复杂度。在图像语义分割中,变量个数即所有图片的像素总数,因而该过程的时间复杂度是不可接受的。本文通过近似的高维过滤使得信息传播过程的时间复杂度从平方复杂度下降为线性复杂度。

2.2 基于高维过滤的信息传播

从信号处理的观点出发,可以将信息传播过程表示成高斯核函数GΛ(m)在特征空间的卷积过程,如式(17)。

(GΛ(m)⊗Qj(l′))(fi)-Qi(l′)=

(17)

1)下采样:Q↓(l)←下采样Q(l)。

2)在采样点f↓点上进行卷积:

在实际应用中通常使用截断的高斯函数作为高斯核函数,截断的高斯函数除了标准差以外其他参数都是0。由于采样点的间距和标准差的距离成正比,因此对截断高斯函数真正起作用的采样点个数为常数，所以每一个采样点的卷积过程可以通过常数个数的相邻样本点的值近似求得。

注意以上讨论的时间复杂度仅仅针对特征空间是一维的情况,如果特征维度为d,那么平均场估计算法的时间复杂度和特征维度呈指数关系,即O(Nd),因此如果完全联系的CRF模型中采用的特征较多,那么也会导致算法执行的效率很低。本文通过高斯kd树[14]对上述高斯卷积过程进行加速。

2.3 高斯kd树

高斯卷积是图像处理中常用的一种技术,通常情况下图像的像素较多,因此传统的高斯卷积效率较低。为了对高斯卷积过程进行加速,学者们提出了一些高速加速方法。图2列出了这些年几种高斯卷积方法的变化,其中白点表示需要计算的点,黑点表示其他特征点,六角星表示不同高斯卷积方法的局部重心，灰点也表示特征点，它和黑点是一一对应的关系，目的是为了区分处理前和处理后的特征点。假设特征点的个数为N,特征空间维度为d,需要对m个点进行卷积计算。

如图2所示,传统的高斯卷积方法只是单纯地将窗口内所有的点进行卷积,因此卷积操作的时间复杂度为O(mNd)。快速高斯卷积方法通过将窗口划分成网格,然后将窗口中的每一个点放到对应网格中的重心上,最后对这些重心进行卷积操作。假设网格数量为k,那么卷积总的操作复杂度为O(mkd)。通常情况下网格个数小于点的个数,因而快速高斯卷积方法对传统的卷积方法进行了提速。和快速高斯卷积方法类似,双边方格高斯卷积方法同样对窗口进行网格划分,然而,双边方格高斯卷积方法不对每一个重心进行卷积,而是对网格的每一个点进行卷积,最后使用插值方式恢复特征点。因此双边方格高斯卷积的时间复杂度为O(mkd)。由于在通常情况下特征点的个数多于网格的个数,所以该方法仍然能够对传统的高斯卷积加速。但是由于时间复杂度和特征维度呈指数关系,该方法并不适用于该维度特征的应用场景。改进的高斯卷积方法不再局限于规则的方格,而是将特征点按照簇(cluster)为单位进行划分。由于每个簇的形状可以是跨维度的,因而卷积的时间复杂度不再是和特征维度呈指数关系,高斯kd树方法正是基于改进的高斯卷积方法被提出来的。

图2 常见的高斯卷积方法

图3 基于高斯kd树的高斯卷积方法

如图3所示,高斯kd树方法分为以下步骤:

1)由给定数据建立高斯kd树。树的每一个内部节点代表一个维的超矩形单元。和普通的kd树不同,高斯kd树中的每一个节点除了存储当前划分的维度、当前划分的维度取值和指向两棵子树的左右指针外,还包含在所有数据在当前划分维度上的最大值和最小值。

2)溅射(Splat)阶段。该阶段通过不同权重对不同位置的像素和它附近的采样点进行卷积计算。

3)模糊(Blur)阶段。模糊阶段则是对这些相邻的采样点进行卷积计算。

4)截割(Slice)阶段。截割阶段通过某像素相邻的采样点从而计算该像素的输出值。

通过重要性采样,高斯kd树的节点个数为m,同时假设搜索树的采样点个数为s。在建立高斯kd树中,每一层需要处理O(N)各节点,由于数据的特征维度为d维,因此每个节点需要处理O(d)次。高斯kd树的高度为log(m),因此建立高斯kd树的时间复杂度为O(Ndlog (m))。由于每次查询的时间复杂度为O(s(logm+d)),所以溅射阶段的时间复杂度为O(Ns(logm+d)),模糊阶段和截割方法的分析方法类似,它们的时间复杂度分别为O(ms(logm+d))和O(Ns(logm+d))。由以上分析可知,高斯kd树滤波处理的总时间复杂度为O(N((s+d)logm+sd)),由于mlt;n,采样点的个数s是个常数,因此最终的时间复杂度为O(dNlogN)。和传统的高斯滤波加速方法相比,该方法的时间复杂度不再具有变量个数的平方复杂度。更多有关高斯kd树内容参考文献[14]。

3 模型参数设置

图4 不同迭代次数的定性结果

表2 本文方法在MSRC-9数据库的混淆矩阵结果 %

表3 不同方法在MyDatase_1的实验结果精度 %

4 实验结果和分析

4.1 图片库和实验平台

本文实验采用的图片库包含标准的图片库——剑桥大学微软研究图片库(MSRC-9)[7]。MSRC-9总共有240张图片,由于“自行车”和“人”类别标注的不确定性,本文实验只选取前150张图片作为实验图片,并分别选取其中50%作为训练和测试。图片库MyDataset_1总共有40张图片,总共包含桌子和4种机械零件,分别是螺母、螺钉、螺柱、桌子和垫片。图片库MyDataset_2包含37张图片,分别包含杯子、书本等物体。实验设备由三个部分组成,分别是图片采集模块、图片处理模块和图片显示模块。其中,图片获取设备采用微软公司的Kinect 2.0,图片处理模块为NVIDIA Jetson TK1嵌入式开发套件,图片显示模块为普通的台式电脑显示屏。实验程序界面由4幅图像组成，分别包括原始输入图、单一分类器处理结果[7]、手动标记结果和本文方法结果。

4.2 实验结果和分析

表1对比了不同方法在MSRC-9图片数据库上的运行结果。需要注意的是,单一分类器方法也是在本文实验平台上运行的,由于该方法并未考虑到像素标签之间的关系,因而运行时间为无。另外,本文方法的运行时间是在平均场估计算法的迭代次数为5时计算得到的,不同迭代次数的定性结果如图4。由图4可知,当迭代次数为5时,基本上平均场算法已经收敛,从而图像标注的结果精度基本不变。本文余下讨论的实验结果的迭代次数都设为5。由表1可知,与RobustPnCRF方法[5]相比,本文方法在图像语义分割结果的平均精度微小提升(0.46%)的情况下,运行时间仅为它的1/15。和单一分类器[7]相比,本文的平均精度提高了8%左右。精度提高的原因是本文采用的完全联系的条件随机场充分考虑了图像中任意两个像素点之间的联系,更好地挖掘了图片的上下文语义信息。而基于高斯kd树的平均场估计方法在保证精度变化不大的条件下能够极大地提高图像标注推理的效率。

表1 不同方法在MSRC-9的实验结果

表2是本文方法在MSRC-9数据库的混淆矩阵结果。其中“飞机”和“羊”标注精度不高(54%左右)。“飞机”标注精度不高的原因是类内图片特征过于复杂且差别较大,同时和其他类别的特征过于相似；而“羊”标注精度不高则是因为该数据库中“羊”训练图片过少引起的。除此之外,其他类别基本上都能取得较好的结果。

表3～4分别是不同方法在MyDatase_1和MyDatase_2的实验结果,由于“垫片”颜色以及纹理和“桌子”过于相似,因此标注精度仅达到64.93%；而其他零件以及桌子的标注精度都能达到较高的结果。“书”和“玩偶”标注精度低的原因和“垫片”类似。由表3～4的数据可知,本文方法无论是整体精度还是类别精度都优于其他两种方法。

表4 不同方法在MyDatase_2的实验结果精度 %

5 结语

本文通过完全联系的条件随机场模型进行图像标注,充分考虑了图片每组像素对之间的上下文语义信息,在一定程度上提高了图像标注的精度。针对模型推理复杂的问题,本文还提出了基于高斯kd树的平均场估计方法,从而将图像推理时间缩短到2 s。虽然本文工作在图像标注的精度和效率上都取得较好的结果,但仍然面临一些问题,这也是下一步工作努力解决的方向:

1)在完全联系的条件随机场模型中如何自动选取高阶项权重的最优值。

2)当类别之间特征过于相似或者训练图片中某类别图片数目较少时,如何提高该类别的标注精度。

3)如何自动选取高斯kd树中不同阶段的标准差以及采样点个数的最优值。

References)

[1] LAFFERTY J D, McCALLUM A, PEREIRA F C N. Conditional random fields: probabilistic models for segmenting and labeling sequence data[C]// ICML 2001: Proceedings of the Eighteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers, 2001: 282-289.

[2] 杨耘, 徐丽. 基于分层特征关联条件随机场的遥感图像分类[J]. 计算机应用, 2014, 34(6): 1741-1745. (YANG Y, XU L. Remote sensing image classification based on conditional random field with hierarchical correlated features[J]. Journal of Computer Applications, 2014, 34(6): 1741-1745.)

[3] 李林, 练金, 吴跃, 等. 基于概率图模型的图像整体场景理解综述[J]. 计算机应用, 2014, 34(10): 2913-2921. (LI L, LIAN J, WU Y, et al. The review of image scenario understanding based on graphical models[J]. Journal of Computer Applications, 2014, 34(10): 2913-2921.)

[4] 张微, 汪西莉. 基于超像素的条件随机场图像分类[J]. 计算机应用, 2012, 32(5): 1272-1275. (ZHANG W, WANG X L. Image classification based on super-pixel condition random fields[J]. Journal of Computer Applications, 2012, 32(5): 1272-1275.)

[5] KOHLIEMAIL P, LADICKY L, TORR P H S. Robust higher order potentials for enforcing label consistency[J]. International Journal of Computer Vision, 2009, 82(3): 302-324.

[6] LADICKY L, RUSSELL C, KOHLI P, et al. Associative hierarchical CRFs for object class image segmentation[C]// Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway, NJ: IEEE, 2009: 739-746.

[7] SHOTTON J, WINN J, ROTHER C, et al. TextonBoost for image understanding: multi-class object recognition and segmentation by jointly modeling texture, layout, and context[J]. International Journal of Computer Vision, 2009, 81(1): 2-23.

[9] VINEET V, WARRELL J, TORR P H S. Filter-based mean-field inference for random fields with higher-order terms and product label-spaces[J]. International Journal of Computer Vision, 2014, 110(3): 290-307.

[10] HE X, ZEMEL R S, CARREIRA-PERPI M A. Multiscale conditional random fields for image labeling[C]// CVPR 2004: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2004,2:695-702.

[11] ABNEY S, SCHAPIRE R E, SINGER Y. Boosting applied to tagging and PP attachment[EB/OL]. [2017- 01- 10]. http://www. vinartus. net/spa/98b. pdf.

[12] PINTO D, McCALLUM A, WEI X, et al. Table extraction using conditional random fields[C]// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2003: 235-242.

[13] TOYODA T, HASEGAWA O. Random field model for integration of local information and global information[J]. IEEE Transactions on Pattern Analysis amp; Machine Intelligence, 2008, 30(8): 1483.

[14] ADAMS A, GELFAND N, DOLSON J, et al. Gaussian KD-trees for fast high-dimensional filtering[J]. ACM Transactions on Graphics, 2009, 28(3): 1-12.

[15] KOLLER D, FRIEDMAN N. Probabilistic Graphical Models: Principles and Techniques — Adaptive Computation and Machine Learning[M]. Cambridge: MIT Press, 2009.

[16] SMITH S W. The Scientist and Engineer’s Guide to Digital Signal Processing[M]. San Diego, CA: California Technical Publishing, 1997: 503-534.

[17] PARIS S, DURAND F. A fast approximation of the bilateral filter using a signal processing approach[J]. International Journal of Computer Vision, 2009, 81(1): 24-52.

Imagelabelingbasedonfully-connectedconditionalrandomfield

LIU Tong, HUANG Xiutian*, MA Jianshe, SU Ping

(GraduateSchoolatShenzhen,TsinghuaUniversity,ShenzhenGuangdong518055,China)

The traditional image labeling models often have two deficiencies; they only can model short-range contextual information in pixel-level of the image and have a complicated inference. To improve the precision of image labeling, the fully-connected Conditional Random Field (CRF) model was used; to simplify the inference of the model, the mean filed approximation based on Gaussian kd-tree for inference was proposed. To verify the effectiveness of the proposed algorithm, the experimental image datasets not only contained the standard picture library MSRC-9, but also contained MyDataset_1 (machine parts) and MyDataset_2 (office table) which made by authors. The precisions of the proposed method on those three datasets are 77.96%, 97.15% and 95.35% respectively, and the mean cost time of each picture is 2 s. The results indicate that the fully-connected CRF model can improve the precision of image labeling by considering the contextual information of image and the mean field approximation using Gaussian kd-tree can raise the efficiency of inference.

Conditional Random Field (CRF); image labeling; contextual information; Gaussian kd-tree; model inference

2017- 04- 10;

2017- 05- 22。

国家863计划项目(2015AA043302);2013年广东省省部产学研合作项目(2013A090100002);2014年广东省花都区科技计划项目(HD14ZD004)。

刘彤(1970—),男,河南洛阳人,讲师,博士,主要研究方向:计算机视觉、LED封装; 黄修添(1991—),男,福建宁德人，硕士研究生,主要研究方向:模式识别、计算机视觉; 马建设(1965—),男,河南郑州人，副教授,博士,主要研究方向:计算机视觉、机器人控制; 苏萍(1975—),女,河南洛阳人，讲师,博士,主要研究方向:三维全息显示系统、图像处理。

1001- 9081(2017)10- 2841- 06

10.11772/j.issn.1001- 9081.2017.10.2841

TP391.413

A

This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA043302), the Program of Industry-university-research Cooperation in Guangdong Province (2013A090100002), the Development Program of Technology Research in Guangdong Huadu District (HD14ZD004).

LIUTong, born in 1970, Ph. D., lecturer. His research interests include computer vision, LED packaging.

HUANGXiutian, born in 1991, M. S. candidate. His research interests include pattern recognition, computer vision.

MAJianshe, born in 1965, Ph. D., professor. His research interests include computer vision, robot control associate.

SUPing, born in 1975, Ph. D., lecturer. Her research interests include 3D holographic display system, image processing.