利用超圖圖割的圖像共分割算法

袁飛，朱利，張磊

（1.西安交通大學電子與信息工程學院，710049，西安；2.西安交通大學軟件學院，710049，西安；3.北京理工大學計算機學院，100081，北京）

單幅圖像分割是計算機視覺領域的一個難題。 完全非監(jiān)督的圖像分割算法依賴于圖像的局部特征而缺少圖像內(nèi)或圖像間的鄰域域信息，使得圖像分割的結果不佳；監(jiān)督或半監(jiān)督的圖像分割算法雖然能獲得較好的結果，但是通常依賴于大量的人為標注訓練數(shù)據(jù)，且圖像分割的速度通常很慢［1］。因此，近年來解決單幅圖像分割的圖像共分割就成為新的研究熱點。圖像共分割是指從具有相同或者相似目標的2幅或者多幅圖像中通過聚類算法［2-6］來分割出目標。相對于單幅圖像的分割，共分割對多幅相似圖像同時進行處理，引入了更多的先驗信息（例如多個目標的相似性等），所以能更準確有效地完成圖像內(nèi)容的分割任務。

在圖像分割算法中，基于圖割的圖像分割技術是研究廣泛的熱點問題之一。其基本思想是將圖像映射為圖，通過對所構造的圖的聚類，完成對圖像的分割。同其他圖像分割技術一樣，基于圖割的圖像分割技術也可以應用于圖像共分割問題上，且相比傳統(tǒng)方法具有更好的分割結果。文獻［2］采用對輸入圖像潛在前景直方圖的L1距離來衡量前景差異，并作為全局約束加入基于馬爾科夫隨機場（MRF）的能量函數(shù)，通過優(yōu)化能量函數(shù)的方法來實現(xiàn)圖像共同前景的分割，但能量函數(shù)的優(yōu)化求解過程的計算復雜度相對較高，使得算法耗費時間較長，同時其分割效果并不理想。文獻［3］同樣采用輸入圖像潛在前景直方圖距離作為前景差異，利用最大流最小割的算法對優(yōu)化問題求解，提高了分割的效率，但其算法基于圖像像素計算，計算復雜度仍然很高。文獻 ［6］首先通過對圖像的歸一化分割和基于核的方法進行分割，然后根據(jù)分塊相似性建立優(yōu)化問題能量函數(shù)，通過降低節(jié)點數(shù)目來提高算法效率，但預處理所耗費的時間較長。Huang等借助圖像共分割的思想實現(xiàn)高效的重復前景物體分割［7］和視頻分割［8］，但構造的圖比較復雜，無法有效表示圖像和視頻場景中的共性對象，從而不利于高效求解。目前基于圖割的圖像共分割算法都是在傳統(tǒng)簡單圖的基礎上對圖像進行表示，需要引入更多的特征信息，從而增加了優(yōu)化過程的計算復雜度。本文引入超圖模型替代傳統(tǒng)簡單圖，可以更好地對圖像內(nèi)和圖像間的相關關系進行表達，同時通過降低圖構造的復雜度和維度來降低算法計算的復雜度，從而達到提高分割算法效率的目的。

1 超圖模型介紹

Berge于1970年第一次提出超圖并對其進行系統(tǒng)的闡述［9］，其初衷是表示多端子網(wǎng)絡所聯(lián)成的超網(wǎng)絡的拓撲結構。超圖理論已經(jīng)在計算機科學和人工智能領域得到長足發(fā)展。

設G=｛V，E｝為超圖，其中V=｛v1，v2，…，vn｝為超圖節(jié)點集，vj∈V 為超圖節(jié)點，E=｛e1，e2，…，em｝為超邊集，ei∈E為超邊，且滿足

超圖可由一個m×n的矩陣H表示，稱H為超圖的關聯(lián)矩陣。h（i，j）表示矩陣H中第i行第j列的元素，定義為

若給第i條超邊賦予權值ω（ei），則對角矩陣W表示超邊權值矩陣，且對角線上第i個元素為w（ei）。令Dv表示節(jié)點度的對角陣，對角線上第i個元素表示節(jié)點vj∈V的度定義為

令De表示超邊度的對角陣，對角線上第i個元素表示超邊ei∈E的度定義為

超圖克服了簡單圖只能表示2個頂點之間的雙向關系的缺點，可以表示多個頂點之間的局部聚合信息，這樣就能完整地描述客觀世界中數(shù)據(jù)間的復雜多重的相關關系。圖像作為一種數(shù)據(jù)形式，其中包含了大量的特征，可以提取高維特征來代表圖像。對于圖像分割來說，用簡單圖映射圖像，只能保留每2個像素或分塊間的相關關系，而實際上它們間的相關關系是十分復雜的，這勢必導致信息的丟失；超圖可以同時表示像素或分塊在局部鄰域與多個像素或分塊間的多重相關關系，從而保留了更多的特征信息。超圖表示示例如圖1所示。

從圖1b可以看出，超圖能表示任意數(shù)目的節(jié)點間的相關關系，即包含在同一超邊內(nèi)的節(jié)點相互關聯(lián)。超圖能更好地表示多個數(shù)據(jù)之間的相關性，同時使得數(shù)據(jù)的表達更加簡單。因此，利用超圖對圖像進行映射，可以對圖像中局部或者全局信息進行更簡單完備的進行表達，從而提高圖像分割的效率。

2 算法介紹

圖1 超圖表示示例

利用超圖圖割的共分割算法將圖像以超圖的形式來表達，首先對具有相似前景的2幅圖像分別進行Mean-shift過分割，并將得到的過分割區(qū)域分塊作為超圖的節(jié)點；然后利用分塊的顏色直方圖計算所有分塊間的相似性，并將相似的分塊對應的相似節(jié)點集合和單幅圖像中相鄰節(jié)點集合作為超邊并計算其權值，構造超圖；最后利用基于譜分析的近似算法求解超圖歸一化分割問題，獲得圖像對的共分割結果。

2.1 Mean-shift過分割處理

在圖像至超圖的映射過程中，一般選用圖像的單像素、超像素或者區(qū)域分塊作為節(jié)點。本文采用Mean-shift算法［10］先對圖像進行過分割的預處理，將得到的分割分塊作為超圖節(jié)點，如對圖2a、2b分別進行過分割，得到的結果如圖2c、2d所示。Mean-shift算法先在特征空間中算出當前點的偏移均值，將該點移動到其偏移均值處，然后以此為新的起始點，重復上述移動，直到滿足一定的收斂條件結束。采用Mean-shift算法對圖像進行預處理，能很好的保持目標局部的一致性，從而提高共分割結果的質(zhì)量；同時，能降低超圖的節(jié)點數(shù)目，從而降低超圖分割的計算復雜度，提高分割的效率。

2.2 超圖構造

將2幅圖像分別做預分割處理，得到每個分塊作為超圖的節(jié)點，通過節(jié)點的某種相鄰關系，例如歐式空間的相鄰、特征相似等，將這些節(jié)點劃為一個集合作為超邊，如圖3所示。具體構造過程如下。

圖2 圖像過分割實例

圖3 圖像對超圖構造

在同一幅圖像中，將空間相鄰的2個分塊劃為一個超邊。分塊相鄰也就是在2個分塊中存在像素點4相鄰。這樣就將2幅圖像分別構造了2個獨立的超圖。由于在不同的圖像中，相似區(qū)域的空間位置一般不會保持不變，故不能采用上面的分塊空間相鄰的方法將不同圖像的分塊聯(lián)系起來，而超邊可以理解為具有某種一致性的節(jié)點的集合，這樣就可以將分塊的特征將相似度較高的分塊劃為一個超邊集合，利用分塊的R、G、B顏色直方圖判斷其相似性。H1、H2分別為2幅圖中的某一分塊的歸一化R、G、B 顏色直方圖，Hl=［Hl，1，Hl，2，Hl，3］，l=1，2，其中 Hl，k，k=1，2，3表示分塊l顏色直方圖的k分量，計算（H1、H2）的 Chi距離d（H1，H2）作為分塊的相關系數(shù)，即

由式（5）可知，分塊相似度越高，相關系數(shù)越小。故將相關系數(shù)小于0.1的分塊作為相似分塊，否則為非相似分塊。然后將2幅圖中相似的分塊集合劃為一個集合，該集合則可以作為聯(lián)系2幅圖的一條超邊，從而構造超圖。

由于分塊相似性判斷方法是基于分塊的顏色直方圖，則計算超邊權值的時候也采用分塊的顏色信息進行計算。Cm、Cn分別代表分塊m、n的R、G、B顏色均值，則定義Cm、Cn的相似度為

式中：α為0到1的系數(shù)。

在超圖中，對相關性越強的節(jié)點，其所屬的超邊具有更大的權值。選擇超邊中圖像分塊間相似度的最大值作為超邊的權值。由于通過直方圖相關性判斷得到的超邊中的圖像分塊具有更強的相關性，故對其權值乘上權值系數(shù)λ（λ＞1）后作為該超邊的權值。權值系數(shù)越大，表示通過直方圖相關性判斷得到的超邊中的圖像分塊的相似性在超圖中得到了強調(diào)，尤其減小了由前景背景分塊過于相似造成的對共分割結果的影響，得到更好的共分割結果。

2.3 超圖分割

根據(jù)上述方法將圖像對構造為對應的超圖，本文采用超圖歸一化分割算法［9］對其進行分割。假設節(jié)點子集S?V，Sc表示S的補集。Ω表示超圖邊界包含的被分割的超邊集合，將超圖分割為S、Sc兩部分

式中：e為任意超邊，超圖的分割可以定義為

式中：vol表示圖的分割。

超圖G的歸一化分割則可以定義為

這是一個NP-hard的優(yōu)化問題，根據(jù)文獻［11］可以被松弛為一個實值優(yōu)化問題。根據(jù)文獻［9］求解，可以采用譜分析的近似算法，定義超圖的拉普拉斯矩陣為

由文獻［9］可以知道超圖拉普拉斯矩陣最小非零特征值對應的特征向量即為該實值優(yōu)化問題的最優(yōu)解，即該特征向量對應一個超圖的二值劃分，其第N列的數(shù)大于0時，則對應標號為N的分塊為前景分塊，反之，則屬于背景分塊，從而通過對超圖的歸一化分割，得到對圖像對的前景背景共分割的結果。

3 實驗結果分析

為了驗證本文分割提出算法的有效性，對MSCR數(shù)據(jù)集［4］和 FlickrMFC數(shù)據(jù)集［12］中的部分圖像進行了共分割實驗。作為對比，將本文算法的實驗結果與單幅圖像的歸一化分割算法［11］以及共分割算法［6］進行了比較。

實驗中所用的機器配置如下：AMD速龍雙核CPU，2GHz主頻，2GB內(nèi)存，32位操作系統(tǒng)。Mean-shift算法中2個參數(shù)的選擇為：位置空間帶寬5，顏色空間帶寬5。圖像間超邊相似度計算系數(shù)α=0.1，超邊的權值系數(shù)λ，在實驗中取λ=2。

圖4為本文算法及對比算法的圖像分割實驗結果。從實驗結果來看，本文算法在實驗中能更好地對圖像進行共分割。由于本文算法首先基于Meanshift算法進行預分割處理，所以最后的分割結果對于目標的完整性保持得較好。文獻［11］算法為單圖歸一化分割，對2幅圖像分別進行分割，沒有引入圖像間分塊的相關關系作為相似性約束，因此分割誤差較大。文獻［6］算法基于像素進行共分割處理，沒有預先對圖像中局部連通的區(qū)域進行聚類，最終共分割結果中產(chǎn)生了相應誤差。

圖4 共分割實驗結果對比

超邊權值系數(shù)λ對分割結果有較大的影響。圖5所示為圖像對中的一幅圖像以及在不同權值系數(shù)下的分割結果。從實驗結果來看，隨著權值系數(shù)的增大，圖像分割的結果能更好地將較為相似的前景與背景分塊分割開來，得到更好的分割結果。

圖5 超邊權值系數(shù)λ對實驗結果的影響

實驗的時間對比如表1所示。算法均選擇采用顏色特征實現(xiàn)分割。本文算法與文獻［6］算法相比，求解優(yōu)化問題的計算復雜度降低，分割所需時間減少。文獻［11］算法對每一幅圖像單獨進行歸一化分割，本文算法與文獻［11］算法相比，由于是對2幅圖像同時進行分割，因而分割所需的時間減少了。從實驗結果來看，本文算法相較于對比算法，其共分割的效率明顯提高，分別為文獻［6］和［11］算法所需時間的4%～10%、32%～55%。本文算法所耗的時間主要在Mean-shift預處理過程。

表1 采用3種算法對4組圖像對進行共分割所需時間比較

4 總 結

本文針對基于傳統(tǒng)簡單圖割算法的圖像共分割方法效率低的問題，提出了一種基于超圖模型的圖像共分割算法。利用Mean-shift預分割所得到的分塊作為節(jié)點，將相似的分塊和相鄰的分塊劃為一個超邊子集，從而構造超圖。然后，利用超圖的歸一化分割算法對所構造的超圖進行劃分，從而得到最終的圖像共分割結果。實驗結果表明，本文方法在分割質(zhì)量和計算效率上均有很大的提高。然而，本文算法仍然存在一些需要進一步完善的地方，例如共分割結果對Mean-shift初始分割結果的要求較高，分塊數(shù)不能過多，同時為了保證共分割的質(zhì)量，分塊必須保持良好的獨立性等。此外，如何簡單高效地判斷并計算分塊間的相似性是算法的關鍵，還有待進一步研究。

［1］ 林開顏，吳軍輝，徐立鴻等.彩色圖像分割方法綜述［J］.中國圖象圖形學報，2005，10（1）：1-10.LIN Kaiyan，WU Junhui，XU Lihong.A survey on color image segmentation techniques ［J］.Journal of Image and Graphics，2005，10（1）：1-10.

［2］ ROTHER C，MINKA T，BLAKE A，et al.Cosegmentation of image pairs by histogram matching-incorporating aglobal constraint into MRFs［C］∥Proceedings of 2006IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2006：993-1000.

［3］ HOCHBAUM D S，SINGH V.An efficient algorithm for co-segmentation ［C］∥Proceedings of 2009IEEE 12th International Conference on Computer Vision.Piscataway，NJ，USA：IEEE，2009：269-276.

［4］ CHANG K Y，LIU T L，LAI S H.From co-saliency to co-segmentation：an efficient and fully unsupervised energy minimization model［C］∥Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2011：2129-2136.

［5］ VICENTE S，ROTHER C，KOLMOGOROV V.Object cosegmentation ［C］∥Proceedings of 2011IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2011：2217-2224.

［6］ JOULIN A，BACH F，PONCE J.Discriminative clustering for image co-segmentation ［C］∥Proceedings of 2010IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2010：1943-1950.

［7］ HUANG Hua，ZHANG Lei， ZHANG Hongchao.RepSnapping：efficient image cutout for repeated scene elements［J］.Computer Graphics Forum，2011，30（7）：2059-2066.

［8］ 張洪超，張磊，黃華.基于跨時空域相似鄰接圖的視頻分割方法 ［J］.圖學學報，2012，33（2）：83-88.ZHANG Hongchao，ZHANG Lei，HUANG Hua.Video cutout method based on spatio-temporal similarity neighboring graph［J］.Journal of Graphics，2012，33（2）：83-88.

［9］ BERGE C.Graph and hypergraph［M］.Amsterdam，Holland：North-Holland Publishing Company，1973.

［10］COMANICIU D，MEER P.Mean shift：a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.

［11］SHI J，MALIK J.Normalized cuts and image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

［12］汪粼波，郭延文，夏天辰，等.樣本驅動的半自動圖像集前背景分割 ［J］.計算機輔助設計與圖形學學報，2013，25（6）：794-801.WANG Linbo，GUO Yanwen，XIA Tianchen，et al.Example-driven semi-automatic image collection segmentation［J］.Journal of Computer-Aided Design &Computer Graphics，2013，25（6）：794-801.