基于超像素和SVM 的交互式聯合分割算法研究

喬琪瓏，王繼業，楊 舒

(1.中央民族大學 信息工程學院，北京100081;2.北京理工大學 信息與電子學院，北京100081)

聯合分割的概念由Rother［1］在2006 年提出，其目的是處理多幅前景相似的圖片，將前景目標提取出來。聯合分割技術可應用于對象驅動的圖像檢索、視頻中特定目標的檢測和跟蹤、交互式圖像編輯，以及圖像相似性度量等。隨著近年來存儲設備和通信相關技術的提高，這類針對圖像集的處理算法更適應于圖像大數據的發展。

按照訓練方式不同，聯合分割算法可被分為3 類:完全監督學習［2］，半監督學習［3－4］和非監督學習方式［5－6］。大多數非監督學習的方式是使用前景之間的直方圖一致性來實現分割，這類方法對圖像數量很敏感，例如Jose C［5］的方法就需要同時處理至少兩幅圖像。同時，非監督學習的方式不能很好地處理前背景相似的情況。而以交互式分割為基礎的監督和半監督學習方式能很好地克服這樣的缺陷。

一方面，自聯合分割的概念被提出，研究人員做了很多工作使其在精確度和分割效率上均有提高，但依然存在圖像數量限制，交互工作量大等問題;另一方面，超像素、機器學習等算法在圖像處理中展現優勢，基于此本文提出了一種基于超像素和支持向量機SVM 的聯合分割算法。通過將種子圖像預分割成多個超像素來建立圖割［7］模型，并在最終的聯合分割中使用Grabcut［8］算法來提高分割精確度。在本文方法中，由于分類器的輸入即這些超像素的特征，圖像分割問題被轉化為分類問題，使用分類器SVM 來將超像素最終分為前景和背景兩類。

本文只使用一幅種子圖像進行交互式分割，并采用對SVM 中的樣本抽取的方式來平衡正負樣本數。相比于其他算法，本文方法更加靈活，可以同時處理任意張圖片，用戶交互量小，并且能夠實現很好的分割效果。本文的主要貢獻包括:

1)提出了一種基于機器學習的聯合分割算法框架，使用二分類的分類器來實現，并使用迭代算法拓展到半監督學習的方式來訓練分類器。

2)通過只選取一幅圖像作為種子圖像，由用戶手動賦予前背景標簽，以此減少用戶工作量，同時提出了一種樣本抽樣的方法來平衡正負樣本數量。

3)引入Tf－idf 加權算法來優化特征，解決了前背景特征相似的情況。

1 基于超像素和SVM 的聯合分割

聯合分割問題可以視為超像素的二分類問題，在本章中，圖1 展示了本文算法的框架，基于這個框架，本文從3 個部分描述算法的細節:種子圖像交互式分割、特征詞典和SVM 的訓練、聯合分割測試。

1 基于超像素和SVM 的聯合分割算法框架

1.1 種子圖像交互式分割

通過使用SLIC 算法［9］將每幅圖像過分割成800 個左右超像素，得到具有相似大小的塊，并很好地保留了目標的邊界。用超像素作為節點構建圖割模型，為節點之間的邊賦權值，得到能量方程。本文改進的能量方程同樣分為區域項與邊界項兩部分，其中區域項與lazy snapping［10］中相同，用來衡量每個節點與前背景模型的相似程度。邊界項如式(1)所示，用來衡量相鄰超像素之間的相似程度，公式描述如下其中，fi是超像素的前背景標簽;使用位置數據(xi，yi)和(xj，yj)來計算兩個超像素中心的距離;‖Ci－Cj‖是在CIELAB 空間中的顏色數據(li，ai，bi)和(lj，aj，bj)之間的歐氏距離。常數β 用來使高對比度區域趨于平滑。

進行交互式分割之后，可以獲得超像素的前背景標簽，這些標簽將被用于分類器的訓練。

1.2 訓練分類器

1.2.1 加權改進的BOF 特征提取

要通過分類器的方法實現聯合分割，關鍵是要使用合適的特征來表示圖像，得到目標之間的相似性，本文使用詞袋算法來做特征提取。首先，使用k－means 算法對種子圖像中的顏色RGB 值聚類，得到顏色特征詞典。K 取200，也就是說顏色詞典Dc 中包含200 個單詞，然后使用同樣的方法得到Dense－SIFT(DSIFT)詞典Dd(包含800 個單詞)。DSIFT 特征是對傳統的尺度不變特征SIFT 省略了關鍵點提取的過程，是采用固定間隔采樣(本文中間隔2 個像素采樣)的方式獲取特征點，從而得到稠密的特征。相比于傳統的SIFT 局部特征，DSIFT 可以保證每個超像素中至少含有一個特征點，更有利于超像素的特征描述，但同時也忽略了尺度空間。因此可以從3 個層次計算DSIFT 特征，取掃描塊大小分別為4×4，8×8 和16×16，以此彌補DSIFT 在尺度上的缺陷。

計算超像素中的特征(在Dc 或Dd 中對應的單詞)出現在超像素中的頻數，即BOF 算法的思路。但是，當同一類特征(某個單詞)同時出現在前景和背景中時會存在干擾。很明顯，這個單詞并不能作為區分前背景的有力依據，因此需要降低這類特征對分類器的影響作用。在本文的算法中引入Tf－idf 算法如式(4)所示。Tf－idf 是在文本分類中常用的方法，用來調節特征對分類器的影響力。在式(4)中，ti表示第d 個超像素中的第i 個特征，nid是單詞i 出現在超像素d 中的次數，而nd是超像素d 中出現的所有特征的個數。值得注意的是，對于顏色特征，nd是超像素塊的面積，而在DSIFT 中是超像素塊中特征點個數。遍歷整幅圖像，其中ni個超像素塊中出現了特征i，用ni除N 得到的結果作為第i 個特征的權系數，這里的N 指整幅圖像中的超像素個數。

最后對于每個超像素，遍歷它的鄰域特征，用這些特征的平均值作為該超像素塊的上下文特征。在本文中，上下文特征有200+800=1 000 維。如式(5)所示，TEXi是超像素d 的上下文特征的第i 位數值，集合V 是其鄰域超像素集合，這個信息是在預分割圖像時得到的，tij是鄰域超像素j 的特征描述，nj是鄰域超像素的面積(對于DSIFT 是特征點數)。

1.2.2 訓練數據平衡化

當訓練SVM 時，通過將屬于前景超像素塊的標號和特征作為正樣本，屬于背景的特征和標號作為負樣本。由于只有一幅種子圖像被用戶標記，因此訓練數據很有限，為正負樣本共800 個左右。實驗表明，當種子圖像中的前景面積遠遠小于背景面積的時候，得到的分類器不理想。

針對不同種子圖像的情況不同，通過抽取前背景中的超像素來平衡訓練數據的數量，抽樣步長由前景面積和背景面積的比例決定。實驗結果表明，這種方法在種子圖像中的前景很小時，可以有效地提高聯合分割的準確率，同時，對于前景面積大的圖像也不會有負面影響。

1.3 測試圖像聯合分割

將種子圖像之外的圖像均作為測試圖像，使用SLIC 方法［9］進行預分割，并使用加權改進的BOF 特征提取得到的特征詞典來描述這些超像素的特征。然后將包括顏色、DSIFT和上下文的特征送入訓練好的SVM 中。SVM 的輸出(0、1)表示該超像素塊是否是目標的一部分。SVM 給出的標號是基于超像素屬于前景的概率所得。使用從0～255 的灰度值表示概率值從－1～+1，得到圖2 所示的前景概率圖譜。

圖2 超像素屬于前景概率圖譜

最后，使用Grabcut［8］來優化分割結果，將分類器SVM 輸出的結果作為可能的前背景標簽，建立像素級的Grabcut 模型來糾正分類錯誤，處理獨立碎塊問題，以及優化邊界。實驗結果表明，這種像素級優化可以有效提高分割精確度，另一方面，由于有分類器輸出作為預標記，Grabcut 的迭代收斂過程明顯加快，因此不會造成計算效率的損失。

1.4 半監督學習方式拓展

本算法可以從兩個方面拓展到半監督學習的方式，分別是種子圖像的選取和SVM 的訓練。

為同時解決顏色特征不夠豐富的問題，提出了一種智能的種子圖選取方法。首先，由用戶手動或隨機選取一幅以上的圖像作為待選種子圖像和顏色特征訓練集。使用這些圖像中的所有像素點作為顏色特征詞典的訓練數據，使用與訓練分類器相同的聚類方法得到特征詞典。與用一幅圖像生成特征詞典相比，用多幅圖像聚類訓練數據更豐富，聚類效果更好。然后得到這些待選種子圖像的顏色特征，統計顏色豐富度，選擇顏色最豐富的圖像作為種子圖像推薦給用戶進行交互式分割。同時使用這幅圖像提取DSIFT 特征詞典，因為金字塔DSIFT 已經可以表示不同尺度的目標，一幅圖像中已經含有豐富的DSIFT 特征。

通過引入一種改進的協同訓練算法來優化分類器。首先將上文中選中并手動分割的種子圖像作為原始訓練樣本，使用重采樣得到3 組訓練數據，分別選用線性、多項式、徑向基RBF 核函數的分類器，得到3 個SVM。未被選中為種子圖像的待選種子圖像進行特征提取后，作為未標記的訓練數據送入SVM。

與完全監督不同，通過使用2 個SVM 來預測新的樣本標號，如果得到的結果相同，這個樣本就被認為具有較高的標記置信度，而作為新的訓練數據加入到第三個分類器的訓練集中，這樣就完成了其中一個分類器的更新。接著，使用這個分類器和一個分類器來預測測試數據，用同樣的方法，使用結果相同的樣本來更新另一個分類器。直到3 個分類器都被更新了，稱作一次半監督學習，因為在這個學習過程中是沒有用戶介入的。其中，每次學習中使用的測試樣本是待選種子圖像的全部樣本，擁有較高標記置信度的樣本并不會離開測試集。

經過2 次半監督學習，將得到的3 個SVM 中的任意一個作為最終的分類器，來完成聯合分割。選用徑向基RBF 核函數的SVM 作為聯合分割的分類器。

2 實驗結果與討論

2.1 聯合分割實驗結果

通過使用iCoSeg［2］數據集來評估本文算法。這個圖像集包含38 類圖像，被廣泛應用于聯合分割算法的測試評估中。對于每一類圖像，選擇一幅種子圖像，交互式的方法提取前景，同時得到該類圖像的顏色和DSIFT 特征詞典以及SVM。然后對剩下的圖像進行聯合分割，最后得到的結果如圖3 所示，其中第1 列是使用交互式圖割分割的種子圖像;第2～5 列是使用SVM 的輸出進行Grabcut 的聯合分割結果。

圖3 聯合分割實驗結果

在圖3 所示的分割結果中，從圖3a 中可以看出，本文的算法得到了很好的分割效果。當前背景中存在相似的特征時，例如圖3b 中的“棕熊”，本文的算法依然得到很好的結果。在圖3c 中“飛機”的結果表明對SVM 中訓練數據進行抽取的方式可以有效解決“小目標”圖像問題。

2.2 結果對比

表1 使用“交集除以并集”評分標準，將本文的算法和Joulin A［4］與S. Vicente［11］的算法做比較，其中Joulin A［4］算法是近幾年來大多數聯合分割算法用來作為基準比較的算法，具有很好的代表性。結果表明，本文算法在大多數測試圖像組中有更好的表現，且平均精確度比Joulin A［4］高4.4%。

表1 各種聯合分割算法分割精度比較%

2.3 半監督學習結果對比

將本文算法拓展到半監督學習的方式，使用未標記的圖像訓練分類器。通過將一幅測試圖像加入到訓練過程中，這些被SVM 標記的超像素會作為新的訓練數據來訓練SVM。使用原始數據和新的數據來更新分類器，然后使用更新后的分類器完成聯合分割。將拓展后的半監督算法與WANG Z［12］的算法進行比較，如表2 所示。

表2 半監督方式算法分割精度比較 %

3 小結

綜上所述，本文實現了一種新的聯合分割算法，通過使用改進的詞袋BOF 特征和樣本抽取的方式優化算法，解決了“小目標”和“前背景中含有相似特征”的問題。相比于傳統聯合分割算法，本算法減少了用戶工作量，并且能夠得到更高的分割精確度。

［1］ROTHER C，MINKA T，BLAKE A，et al. Cosegmentation of image pairs by histogram matching－incorporating a global constraint into MRFs［C］//Proc. IEEE Conf. Computer Vision and Pattern Recognition(CVPR).［S.l.］:IEEE Press，2006:993－1000.

［2］BATRA D，KOWDLE A，PARIKH D，et al.icoseg:Interactive cosegmentation with intelligent scribble guidance［C］//Proc. IEEE Conf.Computer Vision and Pattern Recognition(CVPR).［S.l.］:IEEE Press，2010:3169－3176.

［3］MA T，LATECKI L J. Graph transduction learning with connectivity constraints with application to multiple foreground cosegmentation［C］//Proc. IEEE Conf. Computer Vision and Pattern Recognition(CVPR).［S.l.］:IEEE Press，2013:1955－1962.

［4］JOULIN A，BACH F，PONCE J. Discriminative clustering for image co－segmentation［C］//Proc.IEEE Conf.Computer Vision and Pattern Recognition(CVPR).［S.l.］:IEEE Press，2010:1943－1950.

［5］RUBIO J C，SERRAT J，LóPEZ A，et al. Unsupervised co－segmentation through region matching［C］//Proc. IEEE Conf. Computer Vision and Pattern Recognition(CVPR). ［S.l.］:IEEE Press，2012:749－756.

［6］LI H，MENG F，WU Q，et al. Unsupervised multi－class region co－segmentation via ensemble clustering and energy minimization［J］.IEEE Trans.Circuits and Systems for Video Technology，2014(24):789－801.

［7］BOYKOV Y Y，JOLLY M P. Interactive graph cuts for optimal boundary＆region segmentation of objects in ND images［C］//Proc.IEEE Conf.International Conference on Computer Vision(ICCV).［S.l.］:IEEE Press，2001:105－112.

［8］ROTHER C，KOLMOGOROV V，BLAKE A. Grabcut:Interactive foreground extraction using iterated graph cuts［C］//Proc. ACM Transactions on Graphics.［S.l.］:IEEE Press，2004:307－312.

［9］ACHANTA R，SHAJI A，SMITH K，et al.SLIC superpixels compared to state－of－the－art superpixel methods［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2012，34(11):2274－2282.

［10］LI Y，SUN J，TANG C K，et al. Lazy snapping［J］. ACM Trans.Graphics(ToG)，2004，23(3):303－308.

［11］VICENTE S，KOLMOGOROV V，ROTHER C. Cosegmentation revisited:models and optimization［C］//Proc. IEEE Conf. ECCV.［S.l.］:IEEE Press，2010:465－479.

［12］WANG Z，LIU R.Semi－supervised learning for large scale image cosegmentation［C］//Proc. IEEE Conf. Computer Vision(ICCV).［S.l.］:IEEE Press，2013:393－400.