摘要:大多數最新的多類圖像分割和標記技術使用定義在像素或圖像區域上的條件隨機場。雖然區域模型通常具有密集的成對連接，但是像素模型要大得多，並且只允許稀疏的圖結構。本文定義了壹個圖像所有像素上的全連通CRF，得到的圖有數十億條邊，使得傳統的推理方法不可行。我們的主要貢獻是為全連通條件隨機場提供了壹個有效的近似推理算法，其中成對邊緣勢由高斯核的線性組合定義。我們的實驗表明，像素級的緊密連接大大提高了分割和標註的準確性。
多類圖像分割和標記的壹種常見方法是將該問題視為定義在像素或圖像區域上的條件隨機場(CRF)中的最大後驗概率(MAP)推斷。CRF勢函數包含最大化相似像素間標簽壹致性的平滑項，並能整合更精細的項來模擬對象類間的上下文關系。
基本的CRF模型由單個像素或圖像區域上的壹維勢和相鄰像素或圖像塊上的成對勢組成。這導致相鄰CRF結構對圖像的長距離連接建模的能力有限，並導致對象邊界的過度平滑。為了提高精度，[8，12，9，13]提出了壹種擴展的CRF，將層次連接與定義在圖像區域的高階勢相結合。然而，這些方法依賴於無監督的圖像分割來計算模型運行的區域，因此它們的準確性受到無監督的圖像區域分割的限制，這使得難以在復雜的對象邊界上生成精確的輪廓，盡管已經取得了顯著的進展[9，13，14]。
本文提出了壹種不同的結構用於精確的語義分割，並使用完全連通的CRF在圖像的所有像素上建立成對的勢。在語義分割方面，過去也使用過全連通CRF[18，22，6，17]，但是推理過於復雜，只能用於上百個或者更少的圖像區域。這些方法的準確性也受到無監督圖像分割的限制。相比之下，我們的模型將圖像中的所有像素成對連接起來，從而實現了非常精確的分割和標記。主要挑戰是模型太大，即使在低分辨率圖像中，它也有數千個節點和數十億條邊。
我們的主要貢獻是為全連通條件隨機場提供了壹個有效的推理算法，其中成對的邊緣勢由任意特征空間中高斯核的線性組合來定義。該算法基於CRF分布的平均場近似。這種近似通過壹系列消息傳遞步驟進行叠代優化，每個步驟通過聚合來自所有其他變量的信息來更新單個變量。我們證明了特征空間中的高斯濾波可以更新全連通條件隨機場所有變量的平均場。這使得我們可以通過使用有效的近似高維濾波[16，2，1]，將消息傳輸的計算復雜度從二次型降低到線性可變數。近似推理算法在模型的邊數上是次線性的。
在圖1中，我們的方法可以提高MSRC-21數據集上兩幅圖像的多類分割性能。圖1(d)是全連通CRF [17]的近似MCMC推論的結果。MCMC程序已經運行了36個小時，並且僅部分收斂到基礎圖。我們還在全連通模型[11]中測試了圖割推理，運行72小時後仍然沒有收斂。相比之下，我們提出的方法在單線程下可以在0.2秒內生成詳細的像素級標簽，如圖1(e)所示。第6節提供了MSRC-21和PAS-CAL VOC 2010數據集的定量評估。據我們所知，我們率先在像素級全連通CRF模型中實現了快速推斷。
2全連接通用報告格式模型
給定壹個定義在壹組變量上的隨機場。每個變量的範圍是壹組標簽。同樣，給定壹個定義在壹組變量上的隨機場。的值分布在所有可能的大小的輸入圖像上，而的值分布在所有可能的像素級標簽上。用人類的話來說，就是代表壹個像素的顏色向量就是這個像素的標簽。
條件隨機場被描述為吉布斯分布:
在…之中
在全連通配對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)=[Xi = XJ]。它引入了對附近被分配了不同標簽的相似像素的懲罰。盡管這個簡單的模型在實踐中運行良好，但它對標簽之間的兼容性不敏感。例如，它對壹對標記為“天空”和“鳥”的鄰近像素的懲罰程度與標記為“天空”和“貓”的像素相同。我們可以學習壹個通用的對稱兼容函數mat (XI，XJ)，它考慮了標簽之間的相互作用，如第4節所述。
全連通條件隨機場的三個有效推論
我們的算法基於CRF分布的平均場近似。這種近似產生了用於近似推理的叠代消息傳遞算法。我們的主要觀察是，該模型中的信息傳遞可以通過特征空間中的高斯濾波來完成。這使我們能夠利用高效的高維近似進行高維過濾，從而降低信息從二次傳遞到線性傳遞的復雜性，並由此得到壹個完全連通的crf的近似推理算法，該算法在變量數n上是線性的，在模型的邊數上是次線性的。
3.1平均場近似
平均場近似並不計算精確的分布P(X)，而是計算壹個分布Q(X)，使所有分布Q中的KL散度D(QkP)最小，Q(X) = Qiqi (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的喬萊斯基分解，發現了白化變換。在變換空間中，高維卷積可以分解成壹系列沿晶格軸的壹維卷積。由此產生的近似消息傳遞過程是高效的，即使它是完全順序的，它也不利用圖形硬件的並行性或流能力，並且如果必要的話可以提供進壹步的加速。
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等人[19]提出的17維濾波器組，並遵循Ladicky等人[13]的方法，通過添加顏色、方向梯度直方圖(HOG)和像素位置特征。我們對MSRC-21數據集的評估使用了這個擴展版本的TextonBoost來計算壹元勢。對於VOC 2010數據集，我們把每個對象類的包圍盒對象檢測器的響應[4]作為20個附加特征。這將壹元分類器在VOC 2010上的性能從13%提高到22%。通過訓練邏輯回歸分類器來響應增強的分類器，我們得到額外的5%。
為了有效地進行高維過濾，我們使用了開放式permutohedrattice實現[1]。我們發現標準差下采樣速率是我們所有實驗中最好的。基於采樣的濾波算法低估了非常相似的特征點的邊緣強度k(fi，fj)。正確的標準化可以消除大多數錯誤。置換多面體晶格允許兩種類型的歸壹化。平均核強度k=1npi和jk(fi，fj)的全球標準化可以修正正態誤差。區域誤差用KI = PJK (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等人的robust P n-CRF[9]壹起進行評估，後者通過公眾可用的參考實施。為了確保公平比較，所有模型都使用第5節中描述的壹元勢。所有的實驗都是在Intel i7-930處理器上進行的，處理器的時鐘為2.80GHz。所有其他實驗都是在壹個巖心上進行的。推理算法在單個CPU線程中實現。
趨同。
我們首先通過分析q和p之間的KL散度來評估平均場近似的收斂性。圖2顯示了推理算法的連續叠代中q和p之間的KL散度。KL散度被估計為常數，如補充材料中所述。結果表明，標準偏差θ α和θ β是不同的。這些圖在20次叠代中對齊，用於視覺比較。在所有隨後的實驗中，叠代次數被設置為10。
MSRC-21數據集。
我們將數據集分為45%的訓練圖像、10%的驗證圖像和45%的測試圖像[19]。在訓練集上學習壹元電位，通過維持驗證學習CRF模型的所有參數。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]提出的方法來評估邊界周圍的分割精度。具體來說，我們計算從準確的地面真實圖像獲得的實際對象邊界(“三分圖”)周圍的窄帶中的錯誤分類像素的相對數量。如圖4所示，我們的算法在所有三分圖寬度上都優於以前的工作。
帕斯卡VOC 2010。
因為Pascal VOC 2010測試集中沒有公開的地面真實性標簽，所以我們使用所有實驗的訓練和驗證數據。我們將圖像隨機分為三組: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所示。
討論壹下。
針對完全連通的條件隨機場模型，提出了壹種高效的近似推理算法。結果表明，密集像素級的連通性可以顯著提高像素級分類的精度。我們的單線程實現可以在幾秒鐘內處理參考圖像，並且算法可以並行化以進壹步提高性能。