基于超像素和SVM 的交互式聯(lián)合分割算法研究

喬琪瓏，王繼業(yè)，楊 舒

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

聯(lián)合分割的概念由Rother［1］在2006 年提出，其目的是處理多幅前景相似的圖片，將前景目標(biāo)提取出來(lái)。聯(lián)合分割技術(shù)可應(yīng)用于對(duì)象驅(qū)動(dòng)的圖像檢索、視頻中特定目標(biāo)的檢測(cè)和跟蹤、交互式圖像編輯，以及圖像相似性度量等。隨著近年來(lái)存儲(chǔ)設(shè)備和通信相關(guān)技術(shù)的提高，這類(lèi)針對(duì)圖像集的處理算法更適應(yīng)于圖像大數(shù)據(jù)的發(fā)展。

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

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

本文只使用一幅種子圖像進(jìn)行交互式分割，并采用對(duì)SVM 中的樣本抽取的方式來(lái)平衡正負(fù)樣本數(shù)。相比于其他算法，本文方法更加靈活，可以同時(shí)處理任意張圖片，用戶(hù)交互量小，并且能夠?qū)崿F(xiàn)很好的分割效果。本文的主要貢獻(xiàn)包括:

1)提出了一種基于機(jī)器學(xué)習(xí)的聯(lián)合分割算法框架，使用二分類(lèi)的分類(lèi)器來(lái)實(shí)現(xiàn)，并使用迭代算法拓展到半監(jiān)督學(xué)習(xí)的方式來(lái)訓(xùn)練分類(lèi)器。

2)通過(guò)只選取一幅圖像作為種子圖像，由用戶(hù)手動(dòng)賦予前背景標(biāo)簽，以此減少用戶(hù)工作量，同時(shí)提出了一種樣本抽樣的方法來(lái)平衡正負(fù)樣本數(shù)量。

3)引入Tf－idf 加權(quán)算法來(lái)優(yōu)化特征，解決了前背景特征相似的情況。

1 基于超像素和SVM 的聯(lián)合分割

聯(lián)合分割問(wèn)題可以視為超像素的二分類(lèi)問(wèn)題，在本章中，圖1 展示了本文算法的框架，基于這個(gè)框架，本文從3 個(gè)部分描述算法的細(xì)節(jié):種子圖像交互式分割、特征詞典和SVM 的訓(xùn)練、聯(lián)合分割測(cè)試。

1 基于超像素和SVM 的聯(lián)合分割算法框架

1.1 種子圖像交互式分割

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

進(jìn)行交互式分割之后，可以獲得超像素的前背景標(biāo)簽，這些標(biāo)簽將被用于分類(lèi)器的訓(xùn)練。

1.2 訓(xùn)練分類(lèi)器

1.2.1 加權(quán)改進(jìn)的BOF 特征提取

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

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

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

1.2.2 訓(xùn)練數(shù)據(jù)平衡化

當(dāng)訓(xùn)練SVM 時(shí)，通過(guò)將屬于前景超像素塊的標(biāo)號(hào)和特征作為正樣本，屬于背景的特征和標(biāo)號(hào)作為負(fù)樣本。由于只有一幅種子圖像被用戶(hù)標(biāo)記，因此訓(xùn)練數(shù)據(jù)很有限，為正負(fù)樣本共800 個(gè)左右。實(shí)驗(yàn)表明，當(dāng)種子圖像中的前景面積遠(yuǎn)遠(yuǎn)小于背景面積的時(shí)候，得到的分類(lèi)器不理想。

針對(duì)不同種子圖像的情況不同，通過(guò)抽取前背景中的超像素來(lái)平衡訓(xùn)練數(shù)據(jù)的數(shù)量，抽樣步長(zhǎng)由前景面積和背景面積的比例決定。實(shí)驗(yàn)結(jié)果表明，這種方法在種子圖像中的前景很小時(shí)，可以有效地提高聯(lián)合分割的準(zhǔn)確率，同時(shí)，對(duì)于前景面積大的圖像也不會(huì)有負(fù)面影響。

1.3 測(cè)試圖像聯(lián)合分割

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

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

最后，使用Grabcut［8］來(lái)優(yōu)化分割結(jié)果，將分類(lèi)器SVM 輸出的結(jié)果作為可能的前背景標(biāo)簽，建立像素級(jí)的Grabcut 模型來(lái)糾正分類(lèi)錯(cuò)誤，處理獨(dú)立碎塊問(wèn)題，以及優(yōu)化邊界。實(shí)驗(yàn)結(jié)果表明，這種像素級(jí)優(yōu)化可以有效提高分割精確度，另一方面，由于有分類(lèi)器輸出作為預(yù)標(biāo)記，Grabcut 的迭代收斂過(guò)程明顯加快，因此不會(huì)造成計(jì)算效率的損失。

1.4 半監(jiān)督學(xué)習(xí)方式拓展

本算法可以從兩個(gè)方面拓展到半監(jiān)督學(xué)習(xí)的方式，分別是種子圖像的選取和SVM 的訓(xùn)練。

為同時(shí)解決顏色特征不夠豐富的問(wèn)題，提出了一種智能的種子圖選取方法。首先，由用戶(hù)手動(dòng)或隨機(jī)選取一幅以上的圖像作為待選種子圖像和顏色特征訓(xùn)練集。使用這些圖像中的所有像素點(diǎn)作為顏色特征詞典的訓(xùn)練數(shù)據(jù)，使用與訓(xùn)練分類(lèi)器相同的聚類(lèi)方法得到特征詞典。與用一幅圖像生成特征詞典相比，用多幅圖像聚類(lèi)訓(xùn)練數(shù)據(jù)更豐富，聚類(lèi)效果更好。然后得到這些待選種子圖像的顏色特征，統(tǒng)計(jì)顏色豐富度，選擇顏色最豐富的圖像作為種子圖像推薦給用戶(hù)進(jìn)行交互式分割。同時(shí)使用這幅圖像提取DSIFT 特征詞典，因?yàn)榻鹱炙﨑SIFT 已經(jīng)可以表示不同尺度的目標(biāo)，一幅圖像中已經(jīng)含有豐富的DSIFT 特征。

通過(guò)引入一種改進(jìn)的協(xié)同訓(xùn)練算法來(lái)優(yōu)化分類(lèi)器。首先將上文中選中并手動(dòng)分割的種子圖像作為原始訓(xùn)練樣本，使用重采樣得到3 組訓(xùn)練數(shù)據(jù)，分別選用線(xiàn)性、多項(xiàng)式、徑向基RBF 核函數(shù)的分類(lèi)器，得到3 個(gè)SVM。未被選中為種子圖像的待選種子圖像進(jìn)行特征提取后，作為未標(biāo)記的訓(xùn)練數(shù)據(jù)送入SVM。

與完全監(jiān)督不同，通過(guò)使用2 個(gè)SVM 來(lái)預(yù)測(cè)新的樣本標(biāo)號(hào)，如果得到的結(jié)果相同，這個(gè)樣本就被認(rèn)為具有較高的標(biāo)記置信度，而作為新的訓(xùn)練數(shù)據(jù)加入到第三個(gè)分類(lèi)器的訓(xùn)練集中，這樣就完成了其中一個(gè)分類(lèi)器的更新。接著，使用這個(gè)分類(lèi)器和一個(gè)分類(lèi)器來(lái)預(yù)測(cè)測(cè)試數(shù)據(jù)，用同樣的方法，使用結(jié)果相同的樣本來(lái)更新另一個(gè)分類(lèi)器。直到3 個(gè)分類(lèi)器都被更新了，稱(chēng)作一次半監(jiān)督學(xué)習(xí)，因?yàn)樵谶@個(gè)學(xué)習(xí)過(guò)程中是沒(méi)有用戶(hù)介入的。其中，每次學(xué)習(xí)中使用的測(cè)試樣本是待選種子圖像的全部樣本，擁有較高標(biāo)記置信度的樣本并不會(huì)離開(kāi)測(cè)試集。

經(jīng)過(guò)2 次半監(jiān)督學(xué)習(xí)，將得到的3 個(gè)SVM 中的任意一個(gè)作為最終的分類(lèi)器，來(lái)完成聯(lián)合分割。選用徑向基RBF 核函數(shù)的SVM 作為聯(lián)合分割的分類(lèi)器。

2 實(shí)驗(yàn)結(jié)果與討論

2.1 聯(lián)合分割實(shí)驗(yàn)結(jié)果

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

圖3 聯(lián)合分割實(shí)驗(yàn)結(jié)果

在圖3 所示的分割結(jié)果中，從圖3a 中可以看出，本文的算法得到了很好的分割效果。當(dāng)前背景中存在相似的特征時(shí)，例如圖3b 中的“棕熊”，本文的算法依然得到很好的結(jié)果。在圖3c 中“飛機(jī)”的結(jié)果表明對(duì)SVM 中訓(xùn)練數(shù)據(jù)進(jìn)行抽取的方式可以有效解決“小目標(biāo)”圖像問(wèn)題。

2.2 結(jié)果對(duì)比

表1 使用“交集除以并集”評(píng)分標(biāo)準(zhǔn)，將本文的算法和Joulin A［4］與S. Vicente［11］的算法做比較，其中Joulin A［4］算法是近幾年來(lái)大多數(shù)聯(lián)合分割算法用來(lái)作為基準(zhǔn)比較的算法，具有很好的代表性。結(jié)果表明，本文算法在大多數(shù)測(cè)試圖像組中有更好的表現(xiàn)，且平均精確度比Joulin A［4］高4.4%。

表1 各種聯(lián)合分割算法分割精度比較%

2.3 半監(jiān)督學(xué)習(xí)結(jié)果對(duì)比

將本文算法拓展到半監(jiān)督學(xué)習(xí)的方式，使用未標(biāo)記的圖像訓(xùn)練分類(lèi)器。通過(guò)將一幅測(cè)試圖像加入到訓(xùn)練過(guò)程中，這些被SVM 標(biāo)記的超像素會(huì)作為新的訓(xùn)練數(shù)據(jù)來(lái)訓(xùn)練SVM。使用原始數(shù)據(jù)和新的數(shù)據(jù)來(lái)更新分類(lèi)器，然后使用更新后的分類(lèi)器完成聯(lián)合分割。將拓展后的半監(jiān)督算法與WANG Z［12］的算法進(jìn)行比較，如表2 所示。

表2 半監(jiān)督方式算法分割精度比較 %

3 小結(jié)

綜上所述，本文實(shí)現(xiàn)了一種新的聯(lián)合分割算法，通過(guò)使用改進(jìn)的詞袋BOF 特征和樣本抽取的方式優(yōu)化算法，解決了“小目標(biāo)”和“前背景中含有相似特征”的問(wèn)題。相比于傳統(tǒng)聯(lián)合分割算法，本算法減少了用戶(hù)工作量，并且能夠得到更高的分割精確度。

［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.