高宇田，楊陽，趙廣帥，劉智

（長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

機(jī)器人在探索未知環(huán)境過程中通常需要與周圍環(huán)境之間進(jìn)行交互感知，例如對(duì)桌子上的水杯進(jìn)行抓取操作或者計(jì)算距離最近的椅子的位置等等。因此，視覺場景的理解對(duì)于機(jī)器人[1]來說至關(guān)重要。語義分割對(duì)機(jī)器人視場中每個(gè)對(duì)象進(jìn)行語義標(biāo)注，為機(jī)器人提供豐富的語義信息，能夠很好的表示出機(jī)器人來到了什么地方，“看”到了什么樣的東西，有效地解決了機(jī)器人的場景理解問題。

本文利用具有稀疏高階項(xiàng)的全連接條件隨機(jī)場來解決語義分割問題。條件隨機(jī)場（Condi?tional Random Field，CRF）是計(jì)算機(jī)視覺中幾種問題建模的常用框架[2-3]。目前，隨著深度學(xué)習(xí)的發(fā)展，卷積神經(jīng)網(wǎng)絡(luò)逐漸開始在圖像語義分割方面占據(jù)主導(dǎo)地位，F(xiàn)CN（fully convolutional network）[4]，SegNet[5]、DeepLab[6]等深度學(xué)習(xí)框架實(shí)現(xiàn)了像素級(jí)別的語義分割。但這種黑盒模型并不能很好的給予明確的數(shù)學(xué)解釋，而且由于這種不透明性，深度學(xué)習(xí)只能依賴網(wǎng)絡(luò)層數(shù)的增加來提高分割的結(jié)果。條件隨機(jī)場能夠提取圖像的多方面信息，通過圖像像素間的相關(guān)性構(gòu)建能量函數(shù)模型，最后通過能量最小化方法來求解該模型，實(shí)現(xiàn)圖像的語義分割。

傳統(tǒng)CRF[7-8]的能量函數(shù)由兩項(xiàng)組成：依賴于一個(gè)隨機(jī)變量標(biāo)簽的一元?jiǎng)莺瘮?shù)和依賴于兩個(gè)隨機(jī)變量標(biāo)簽的二元?jiǎng)莺瘮?shù)。這種傳統(tǒng)模型只考慮到了圖像局部像素之間的約束關(guān)系，沒有關(guān)注到更高級(jí)依賴關(guān)系。而高階CRF[9-10]在傳統(tǒng)基礎(chǔ)上增加了由多個(gè)隨機(jī)變量集合的高階勢函數(shù)，使得依賴關(guān)系由局部推廣到全局圖像，將模型擴(kuò)展到超像素[15]之間的依賴關(guān)系。能量函數(shù)模型建立之后，接著利用能量最小化方法進(jìn)行模型求解。針對(duì)CRF能量函數(shù)的最小化問題，研究者們開發(fā)了幾個(gè)精準(zhǔn)的離散優(yōu)化問題[11-12]的連續(xù)松弛推理算法。這種松弛推理法的一個(gè)重要優(yōu)點(diǎn)是便于分析，但是用于求解這種松弛的算法卻不能很好地解決成對(duì)連接的數(shù)量問題。為了克服上述不足，傳統(tǒng)的能量最小化方法使用4鄰域或者8鄰域的稀疏CRF網(wǎng)絡(luò)連接結(jié)構(gòu)。雖然稀疏連接結(jié)構(gòu)能夠很好地適應(yīng)這種松弛法，但是由于自身稀疏的局限性，構(gòu)建的模型無法獲得準(zhǔn)確的標(biāo)記，而全連接的CRF網(wǎng)絡(luò)中每一個(gè)像素節(jié)點(diǎn)和網(wǎng)絡(luò)中所有像素有關(guān)，可以獲得更準(zhǔn)確的標(biāo)記。為了解決全連接CRF 的能量最小化問題，Krahenbuhl和 Koltun[13]使用了平均場（mean-filed，MF）推理算法[14]，Vineet等人[15]同樣利用這種算法對(duì)具有稀疏高階勢的全連接CRF進(jìn)行平均場推理，進(jìn)一步提高了分割精度，但是這種濾波算法存在一定的弊端，不能對(duì)解的質(zhì)量提供有力的理論保證。Desmaison等人針對(duì)傳統(tǒng)CRF提出了二次規(guī)劃（quadratic programming，QP）松弛推理算法來求解能量最小化問題，消除了平均場推理算法的弊端，但是傳統(tǒng)CRF的局限性又限制了算法的分割效果。

針對(duì)上述問題，論文提出了一個(gè)具有稀疏高階勢的全連接CRF的QP松弛以及其能量最小化框架。將能量函數(shù)表示為QP松弛，并且提出了基于Pn-Potts模型[16]的高階項(xiàng)的松弛，利用現(xiàn)有能量最小化算法處理這些高階勢，同時(shí)在每次迭代中保持標(biāo)簽和隨機(jī)變量數(shù)量的線性復(fù)雜度。本文證明了QP松弛的條件梯度可以用標(biāo)簽數(shù)和隨機(jī)變量數(shù)的復(fù)雜線性來計(jì)算，通過分析計(jì)算得到下降方向的最佳步長，最后使用Frank-Wolfe算法有效地最小化QP松弛。

1 高階條件隨機(jī)場模型建立

具有稀疏高階勢的全連接CRF模型是由隨機(jī)變量及其對(duì)應(yīng)標(biāo)簽描述的。定義N個(gè)隨機(jī)變量集合X={X1,…,XN}，其中每個(gè)隨機(jī)變量Xa從M個(gè)標(biāo)簽的集合L={l1,…,lM}中取一個(gè)標(biāo)簽，記為標(biāo)簽向量x∈LN，其中x的元素xa對(duì)應(yīng)于隨機(jī)變量Xa。其中，隨機(jī)變量對(duì)應(yīng)一個(gè)像素節(jié)點(diǎn)，相關(guān)標(biāo)簽對(duì)應(yīng)一個(gè)語義類。接著引入團(tuán)的概念，團(tuán)代表一個(gè)超像素，超像素是共享相似顏色信息的相鄰像素的集合，在這里使用均值漂移算法[17]來生成超像素。將包含三個(gè)或更多隨機(jī)變量的團(tuán)表示一個(gè)高階勢，而包含兩個(gè)隨機(jī)變量的團(tuán)表示一個(gè)二元?jiǎng)?。給定的團(tuán)Sp為X的子集，包含高階勢的團(tuán)集合S定義如下：

其中，R表示集合S中團(tuán)的總數(shù)。集合Rp表示團(tuán)Sp中隨機(jī)變量的索引集，可以形式化地表示為Rp={a∈{1,…,N}|Xa∈Sp}。接著引入向量xp，由兩個(gè)以上元素xi構(gòu)成，即團(tuán)Sp中隨機(jī)變量的標(biāo)簽。因此將能量函數(shù)定義如下：

其中，ψa(xa)為一元?jiǎng)?，表示將隨機(jī)變量Xa賦值為標(biāo)簽xa的代價(jià)；ψa,b(xa,xb)為二元?jiǎng)荩硎緦㈦S機(jī)變量Xa和Xb分別分配給xa和xb的代價(jià)；ψp(xp)為高階勢函數(shù)，表示Sp中所有隨機(jī)變量分配標(biāo)簽xp的代價(jià)。下面將分別介紹能量函數(shù)中每項(xiàng)的具體表現(xiàn)形式。

1.1 一元?jiǎng)?/h3>

本文使用的一元?jiǎng)輥碜訲extonBoost[18]。其一元?jiǎng)荻x為分配給每個(gè)像素的標(biāo)簽概率分布的負(fù)對(duì)數(shù)，其中p(xa)是第a個(gè)超像素的標(biāo)簽概率分布，通過基于像素特征訓(xùn)練的分類器對(duì)像素分類獲得。形式如下：

1.2 高斯二元?jiǎng)?/h3>

高斯二元?jiǎng)荻x為兩個(gè)連接的像素節(jié)點(diǎn)的標(biāo)簽概率函數(shù)，形式如下：

其中，μ(xa,xb)表示標(biāo)簽兼容性函數(shù)；Kab是像素兼容性函數(shù)；w(m)是一個(gè)標(biāo)量加權(quán)因子；為高斯核函數(shù)。二元?jiǎng)莺瘮?shù)起到平滑的作用，即當(dāng)兩相鄰像素點(diǎn)標(biāo)簽不具備一致性時(shí)，給予一定的懲罰。將像素兼容函數(shù)定義為雙高斯核形式：

式中，Ia、Ib和pa、pb分別表示像素a和b的顏色向量和空間位置向量；參數(shù)w(1)和w(2)為平衡兩項(xiàng)的權(quán)重為模型參數(shù)，可以通過交叉驗(yàn)證得到。第一項(xiàng)為外觀內(nèi)核，根據(jù)相似顏色和位置的像素可能具有相同的標(biāo)簽得到；第二項(xiàng)為平滑內(nèi)核，用于懲罰孤立的小區(qū)域。

標(biāo)簽兼容性函數(shù)μ(xa,xb)構(gòu)成分配隨機(jī)變量Xa和Xb的代價(jià)的一部分，標(biāo)簽分別對(duì)應(yīng)于xa和xb的值。本工作使用的標(biāo)簽兼容函數(shù)為Potts模型，具體如下：

1.3 高階勢

利用Pn-Potts模型[19]推導(dǎo)出高階勢。高階勢表示如果團(tuán)Sp的元素的標(biāo)簽與當(dāng)前超像素標(biāo)簽一致，不進(jìn)行懲罰；否則給與一定的懲罰，將其設(shè)置為與超像素顏色信息的方差成正比。高階勢定義為：

其中，Γ和η是交叉驗(yàn)證的參數(shù)，表示團(tuán)Sp內(nèi)像素顏色值的方差。團(tuán)Sp代表一個(gè)超像素，在這里使用均值漂移算法來生成超像素的同時(shí)，通過交叉驗(yàn)證確定超像素的大小以確保得到與問題相匹配的高階勢。

2 QP松弛推理算法

在建立高階CRF模型后，需要對(duì)該模型進(jìn)行高效求解，即對(duì)函數(shù)能量進(jìn)行最小化以獲得最優(yōu)標(biāo)記結(jié)果。一般將求解CRF模型作為最大后驗(yàn)概率問題，或者叫做作推理問題。Desmaison等人針對(duì)傳統(tǒng)CRF提出了QP松弛推理算法來求解能量最小化問題，本文在其基礎(chǔ)上提出了一種基于高階CRF的QP松弛推理算法。算法先將帶有高階勢的能量函數(shù)轉(zhuǎn)化為整數(shù)規(guī)劃形式，再得到QP松弛的目標(biāo)函數(shù)，最后通過Frank-Wolfe算法[20]對(duì)其進(jìn)行最小化。

2.1 整數(shù)規(guī)劃

整數(shù)規(guī)劃方法是目前適合連續(xù)松弛的能量最小化方法。因此，先將能量函數(shù)式（3）轉(zhuǎn)化為整數(shù)規(guī)劃形式：

其中，二元變量ya:i∈{0,1}表示隨機(jī)變量Xa是否具有標(biāo)簽li；向量中包含指標(biāo)變量xp。第一項(xiàng)約束確保每個(gè)隨機(jī)變量只能分配一個(gè)標(biāo)簽，第二項(xiàng)約束確保標(biāo)簽是二進(jìn)制的 。是階數(shù)等于團(tuán)Sp中的隨機(jī)變量數(shù)的多項(xiàng)式。為了簡化θp(?)運(yùn)算，利用稀疏高階勢中的標(biāo)簽一致性，可以重新構(gòu)造該高階多項(xiàng)式簡化計(jì)算。定義如下：

由于式（10）為NP-hard問題[18]，通過放寬整數(shù)約束來近似IP進(jìn)而解決能量最小化問題，得到QP松弛，接下來使用基于濾波器的方法來優(yōu)化QP松弛。將式（9）中一元?jiǎng)莺投獎(jiǎng)荼硎緸橄蛄啃问?，其中一元?jiǎng)轂橄蛄縴與一元項(xiàng)的向量ψa∈?NM的點(diǎn)積；二元?jiǎng)荭譨b∈?NM×NM表示為標(biāo)簽兼容函數(shù)矩陣μ∈?M×M與像素兼容函數(shù)矩陣K(m)的克羅內(nèi)克積，ψab∈ ?NM×NM定義如下：

接著對(duì)目標(biāo)函數(shù)的高階項(xiàng)進(jìn)行定義。通常，高階多項(xiàng)式的階數(shù)等于每個(gè)團(tuán)中的隨機(jī)變量數(shù)。由于利用標(biāo)簽一致性可以將這個(gè)高階多項(xiàng)式重新表示為一個(gè)低階多項(xiàng)式，因此引入一個(gè)二值變量zp:i，表示團(tuán)Sp中的所有隨機(jī)變量是否都使用標(biāo)簽Li。定義如下：

接著引入一個(gè)指標(biāo)項(xiàng)Hp(a)，用來表示隨機(jī)變量Xa是否屬于團(tuán)Sp，定義如下：

由此，將目標(biāo)函數(shù)的高階項(xiàng)進(jìn)行如下定義：

根據(jù)式（13）和式（14）的定義，容易發(fā)現(xiàn)最后一項(xiàng)的值總是為0，當(dāng)放寬指標(biāo)變量ya:i和輔助變量zp:i的二值約束，使它們?nèi)?到1之間的分?jǐn)?shù)時(shí)，后一項(xiàng)就提供了zp:i和ya:i之間的耦合，同時(shí)也解決了無法在多項(xiàng)式時(shí)間內(nèi)求解的NP-hard問題。Hp(a)的值構(gòu)成了稀疏矩陣H，H是一個(gè)由1組成的稀疏矩陣，使得元素按照正確的順序進(jìn)行求和；矩陣C是包含常數(shù)Cp的對(duì)角矩陣；向量1z和1y是所有1的向量；zp:i向量形式表示為z。最后，QP松弛可以正式定義為：

2.2 最小化

完成目標(biāo)函數(shù)（16）的定義后使用Frank-Wolfe算法[12]對(duì)其進(jìn)行最小化。通過計(jì)算目標(biāo)函數(shù)的梯度、有效的條件梯度和最佳步長實(shí)現(xiàn)。算法在每次迭代中保持像素和標(biāo)簽數(shù)量的線性關(guān)系，通過像素和標(biāo)簽數(shù)量線性的復(fù)雜度來計(jì)算條件梯度。

將目標(biāo)函數(shù)的梯度定義為：

一元項(xiàng)保留為常數(shù)，使其與標(biāo)簽和隨機(jī)變量的數(shù)量成線性關(guān)系；二元項(xiàng)計(jì)算利用基于濾波器的方法；對(duì)于高階項(xiàng)，由于團(tuán)與團(tuán)之間沒有交集，因此只對(duì)每個(gè)團(tuán)中的標(biāo)簽和像素進(jìn)行求和。然后按照標(biāo)簽和像素?cái)?shù)量線性變化的復(fù)雜度進(jìn)行條件梯度計(jì)算。條件梯度計(jì)算公式為：

其中，sy和sz為f(y,z)的條件梯度。最佳步長通過最小化單個(gè)變量的二次函數(shù)來計(jì)算，最小值可以通過分析計(jì)算得到。Frank-Wolfe算法的最佳步長計(jì)算公式為：

根據(jù)式（19）得到最佳步長，使目標(biāo)函數(shù)得到快速收斂，算法不斷循環(huán)直到實(shí)現(xiàn)最終收斂。由于算法中基于過濾器的方法每次迭代只調(diào)用一次，使QP最小化算法具有一定的高效性。

3 仿真驗(yàn)證與分析

為了驗(yàn)證算法的有效性，采用Pascal VOC2012公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，該數(shù)據(jù)集為驗(yàn)證圖像語義分割的基準(zhǔn)。Pascal包含1 928張彩色圖像，尺寸約為500×400像素。將數(shù)據(jù)集中50%的圖像作為訓(xùn)練集，進(jìn)行一元?jiǎng)莸挠?xùn)練，15%作為驗(yàn)證集，得到內(nèi)核和高階勢參數(shù)，最后35%作為測試集進(jìn)行評(píng)估。將本文高階CRF算法表示為QP-H，同時(shí)在不引入高階勢的情況下進(jìn)行了實(shí)驗(yàn)，能量函數(shù)僅由一元?jiǎng)莺投獎(jiǎng)?，同時(shí)使用QP推理算法進(jìn)行能量最小化，表示為QP。為了驗(yàn)證算法的優(yōu)越性，對(duì)基于平均場推理算法[10]的全連接CRF也進(jìn)行實(shí)驗(yàn)，表示為MF。所有實(shí)驗(yàn)都在2.80 Ghz Intel Core i5-8400處理器上進(jìn)行。

本次實(shí)驗(yàn)將平均能量、時(shí)間、準(zhǔn)確性以及重疊度作為評(píng)估標(biāo)準(zhǔn)。其中重疊度表示正確標(biāo)記的像素與語義分割后的像素的交集占正確標(biāo)記的像素與分割后的像素的并集的比例。表1給出了MF、QP及QP-H三種算法的實(shí)驗(yàn)結(jié)果，圖1表示了三種算法的能量的下降過程，圖2和圖3給出了三種算法的語義分割結(jié)果。

表1 綜合對(duì)比

圖1 三種算法的能量下降過程

圖2 Pascal數(shù)據(jù)集MF、QF、QF-H三種算法的語義分割結(jié)果對(duì)比（一）

圖3 Pascal數(shù)據(jù)集MF、QF、QF-H三種算法的語義分割結(jié)果對(duì)比（二）

表1給出的結(jié)果可以看出，QP與MF相比，平均能量更低，算法時(shí)間有所增加，但是準(zhǔn)確性及重疊度提高不明顯；QP-H與MF和QP比較的平均能量更低，同樣由于模型復(fù)雜度的提高，算法時(shí)間做出了一些犧牲，但是準(zhǔn)確性和重疊度得到了一定的提高。由圖1中三種算法的下降過程可以明顯的看出QP-H能量最小化的效果最為明顯。由圖2中三種算法的分割結(jié)果可以明顯的看出QP-H的分割精度有了一定的提高。由此可以得到，QP-H以犧牲了部分算法時(shí)間為代價(jià)實(shí)現(xiàn)了更有效的能量最小化，最終分割精度得到了一定提高。

4 結(jié)論

本文提出了具有稀疏高階勢的全連接CRF的QP松弛以及其能量最小化框架，并通過Pascal公開數(shù)據(jù)集進(jìn)行驗(yàn)證，實(shí)驗(yàn)證明該算法能夠有效地實(shí)現(xiàn)能量最小化，并使得語義分割結(jié)果有一定的提高。該模型消除了傳統(tǒng)CRF的局限性，而且由于使用了高斯二元?jiǎng)?，并在高階項(xiàng)上加強(qiáng)了標(biāo)記一致性，算法的每次迭代在標(biāo)記數(shù)和像素?cái)?shù)上都表現(xiàn)出時(shí)間復(fù)雜度的線性關(guān)系。但是由于高階勢提高了模型復(fù)雜度，使得算法執(zhí)行時(shí)間有一定的犧牲，未來還需要繼續(xù)進(jìn)行相關(guān)工作的研究。目前看來，高階勢的利用是條件隨機(jī)場未來的發(fā)展趨勢，并且在結(jié)合深度學(xué)習(xí)后，會(huì)更加提高語義分割的精度，推動(dòng)語義分割算法的發(fā)展。