基于信息瓶頸法的圖像分離-合并分割算法

李德棟，肖楚琬，龐 威

(1.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系，山東 煙臺(tái) 264001;2.海軍航空工程學(xué)院接改裝訓(xùn)練大隊(duì)，山東 煙臺(tái) 264001)

0 引言

圖像分割的主要目的是將一幅圖像劃分為多個(gè)區(qū)域，在考慮某個(gè)給定標(biāo)準(zhǔn)(如顏色或紋理)時(shí)這些區(qū)域是勻質(zhì)的。在圖像分析和計(jì)算機(jī)視覺(jué)中，圖像分割是一個(gè)非常廣泛的研究問(wèn)題，也是通向圖像理解的重要步驟。為此已經(jīng)提出了很多不同的方法，例如閾值法、區(qū)域生長(zhǎng)法、區(qū)域分離-合并法、活動(dòng)輪廓法以及水平集合法等。每一種方法都只從某一個(gè)不同視角考慮分割問(wèn)題，也只適用于解決少數(shù)情況。對(duì)于分割算法的研究，可參見(jiàn)文獻(xiàn)［1］和文獻(xiàn)［2］。

本文的目的是應(yīng)用信息瓶頸法的基本形式來(lái)介紹一種新的分割算法。這種方法的應(yīng)用需要定義一種信息渠道，這個(gè)渠道中一個(gè)隨機(jī)變量通過(guò)保留它們之間的最大互信息來(lái)控制另一個(gè)隨機(jī)變量的聚類。也就是，此方法的目的是在關(guān)于另一變量互信息損失最小的情況下，提取某一隨機(jī)變量的緊密表征。在分離-合并算法中，這個(gè)渠道產(chǎn)生了圖像框架和直方圖格段之間的相互聯(lián)系。這種空間信息使得方法在紋理分析方面更加健全，而不用假設(shè)任何的優(yōu)先亮度或是紋理分布。該方法的整體優(yōu)勢(shì)在于，它們不要假設(shè)任何有關(guān)圖像的優(yōu)先信息(如亮度概率分布等)。實(shí)驗(yàn)結(jié)果表明，信息瓶頸法在處理二維和三維圖像分割技術(shù)方面是可行的。

1 相關(guān)研究

1.1 圖像分割

在圖像處理中，將圖像各部分歸類為一種或多種特性同類的多個(gè)區(qū)域，產(chǎn)生分割后的圖像。分割算法一般基于2個(gè)亮度值特性之一:不連續(xù)性和相似性。第一種特性中，算法基于亮度的突變進(jìn)行分割圖像，比如邊緣［3-4］。第二種特性中，主要的方法基于將圖像分割成多個(gè)區(qū)域，依據(jù)預(yù)先設(shè)定的標(biāo)準(zhǔn)這些區(qū)域相似。閾值法、區(qū)域生長(zhǎng)法、直方圖聚類法、分離-合并法和隨機(jī)場(chǎng)法是這一特性方法的典型例子［2，5-10］。

分離-合并算法［1-2，11-12］由2個(gè)步驟組成。首先，依據(jù)不同標(biāo)準(zhǔn)此方法將整個(gè)圖像細(xì)分為很小的區(qū)域。為了分割圖像，將采用不同的策略，如四叉樹(shù)分割(此處每個(gè)區(qū)域被細(xì)分為四等份)和二元空間分割BSP(采用最優(yōu)的劃分來(lái)分割區(qū)域)。其次，如果符合相似標(biāo)準(zhǔn)，從分割步驟得到的臨近區(qū)域?qū)⒈缓喜?。這些相似和不相似標(biāo)準(zhǔn)基于亮度區(qū)間、梯度、對(duì)比度、區(qū)域統(tǒng)計(jì)或是紋理。這種分割和合并步驟的組合可考慮任意形狀的分割，而不拘泥于垂直或是水平線分割，其只考慮了分割步驟。

1.2 信息論

設(shè)Χ為一有限集，X為一隨機(jī)變量，x在Χ中服從分布p(x)=Pr［X=x］。同樣設(shè)Y為一隨機(jī)變量，y屬于Y。隨機(jī)變量X(輸入)和Y(輸出)之間的信息通道X→Y由一個(gè)概率轉(zhuǎn)移矩陣來(lái)表征，此矩陣由條件概率構(gòu)成，其在假定輸入的條件下確定輸出分布［13］。

隨機(jī)變量X的香農(nóng)熵H(X)定義如下:

也可由H(p)表示，估計(jì)隨機(jī)變量X的平均不確定性。所有算法以2為底數(shù)，熵用比特?cái)?shù)表示。約定0log 0=0。條件熵定義如下:

這里，p(y/x)=Pr［Y=y|X=x］為條件概率。如果知道X的輸出，條件熵H(Y|X)測(cè)量出關(guān)于Y的平均不確定性。一般而言，H(Y|X)≠H(X|Y)，且H(X)≥H(X|Y)≥0。

X和Y之間的互信息(MI)定義如下:

上式計(jì)算出了X和Y之間的共享信息?？梢钥闯鯥(X，Y)=I(Y，X)≥0。MI的一個(gè)基本特性由數(shù)據(jù)處理不等式給出，可用如下方式表示:如果X→Y→Z是馬爾科夫鏈，也就是p(x，y，z)=p(x)p(y|x)p(z|y)，那么:

結(jié)果表明:對(duì)Y的處理，無(wú)論是確定的還是隨機(jī)的，都不能增加Y包含的關(guān)于X的信息量。

這里，JS(π1，…，πn;p1，…，pn)是具有先驗(yàn)概率的概率分布{p1，…，pn}或滿足πi=1的權(quán)重{π1，…，πn}的 Jensen-Shannon 散度。JS-散度度量了概率pi來(lái)自它們共同發(fā)送端的程度πipi，以及當(dāng)且僅當(dāng)所有的pi均等時(shí)接近0的程度。值得注意，當(dāng){π1，…，πn}和{p1，…，pn}分別表示輸入分布和通道X→Y的概率轉(zhuǎn)移矩陣時(shí)，JS-散度對(duì)I(X，Y)來(lái)說(shuō)是恒等的，這里n=|Χ|，m=|Y|。換句話說(shuō)，πi=p(xi)?i∈{1，…，n}，pi=p(Y|xi)?i∈{1，…，n}，p(Y|xi)={p(y1|xi)，…，p(ym|xi)}是條件概率分布。

1.3 信息瓶頸法

由Tishby等［15］提出的信息瓶頸法，提取出了變量X的稠密表征，在關(guān)于另一變量Y的互信息MI損失最小情況下由表示(換言之盡可能多地維持有關(guān)變量Y的信息)?？刹捎肵的軟分割和硬分割。第一種情況下，每簇x∈Χ可通過(guò)某個(gè)條件概率px)分配給每簇(軟聚類)。第二種情況下，每簇x∈Χ只分配給一簇(硬聚類)。

滿足以下特性:

(1)由 x1，…，xl融合引起的從 T(X，Y)到 T(，Y)互信息的減少，由下式給出:

這里，πk=p(xk)/p)，pk=p(Y|xk)。最優(yōu)的聚類算法進(jìn)行最小化δI。

(2)l個(gè)分量的最優(yōu)組合可由各組分量的l-1個(gè)連續(xù)最優(yōu)組合獲得。

Dhillon等［16］提出的聯(lián)合聚類算法，應(yīng)用于文字文檔聚類，同時(shí)使X和Y不相交或硬聚類。最優(yōu)的聯(lián)合聚類算法進(jìn)行最小化I(X，Y)-I(，)的差值。

2 分離-合并算法

圖1 分離-合并算法中圖像區(qū)域與亮度格段間的信息通道

本節(jié)中，提出一種分離-合并算法，它由隨機(jī)變量R(輸入)和B(輸出)之間的信息通道R→B構(gòu)成，2個(gè)隨機(jī)變量分別表示圖像的一組區(qū)域R和一組亮度格段Β(見(jiàn)圖1)。此通道由條件概率矩陣p(B|R)定義，它表示對(duì)應(yīng)于圖像每個(gè)區(qū)域的像素分布于直方圖格段的情況。本文中，作為p()自變量的大寫(xiě)字母R和B用來(lái)表示概率分布。例如，當(dāng)p(R)表示區(qū)域的輸入分布時(shí)，p(r)表示單個(gè)區(qū)域r的概率分布。

假設(shè)，圖像具有N個(gè)像素、Nr個(gè)區(qū)域和Nb個(gè)亮度格段，通道R→B的3個(gè)基本元素如下:

(1)條件概率矩陣p(B|R)，表示圖像每個(gè)區(qū)域到直方圖格段的轉(zhuǎn)移概率，定義為p(b|r)=n(r，b)/n(r)，這里n(r)是區(qū)域r的像素?cái)?shù)，n(r，b)是對(duì)應(yīng)于格段b的區(qū)域r的像素?cái)?shù)。條件概率滿足∑b∈Βp(b|r)=1，?r∈R。

(2)輸入分布p(R)，表示選擇每個(gè)圖像區(qū)域的概率，定義為p(r)=n(r)/N，也就是區(qū)域r的相對(duì)面積。

(3)輸出分布p(B)，表示每個(gè)格段b的歸一化頻率，由下式給出p(b)=∑r∈Rp(r)p(b|r)=n(b)/N，這里n(b)是對(duì)應(yīng)于格段b的像素?cái)?shù)。

2.1 分割

算法的分割階段是一個(gè)期望的自上而下過(guò)程，在準(zhǔn)均質(zhì)區(qū)域中分割圖像。分割策略將整幅圖像作為初始分割塊，然后根據(jù)每個(gè)分割步驟的最大互信息增益逐步細(xì)分圖像。實(shí)驗(yàn)中，將應(yīng)用二元空間分割BSP和四叉樹(shù)策略。

由下式給出:

這里，π1=p(r1)/p，π2=p(r2)/p()。2 個(gè)區(qū)域之間的 JS-散度 JS(π1，π2;p(B|r1)，p(B|r2))，可解釋為它們?cè)诹炼戎捣矫嫦喈愋缘亩攘俊Ｒ簿褪?，?dāng)一個(gè)區(qū)域被分割時(shí)，互信息增益等于分割得到的區(qū)域之間相異度乘以區(qū)域的尺寸。在分割算法中，最優(yōu)的分割通過(guò)最大化互信息增益δI?r來(lái)得到。

這里，π1=p(r1)/p，π2=p(r2)/p(。2 個(gè)區(qū)域之間的 JS-散度 JS(π1，π2;p(B|r1)，p(B|r2))，可解釋為它們?cè)诹炼戎捣矫嫦喈愋缘亩攘俊Ｒ簿褪?，?dāng)一個(gè)區(qū)域被分割時(shí)，互信息增益等于分割得到的區(qū)域之間相異度乘以區(qū)域的尺寸。在分割算法中，最優(yōu)的分割通過(guò)最大化互信息增益δI來(lái)得到。

二元空間分割算法可由一個(gè)進(jìn)化的二叉樹(shù)表示，每一片葉子相當(dāng)于圖像最終的分割區(qū)域。每一分割步驟中，二叉樹(shù)都獲得源自原始圖像的信息，諸如每一個(gè)中間節(jié)點(diǎn)k包含源自其對(duì)應(yīng)分割的信息Ik。在某個(gè)給定時(shí)刻，累加在二叉樹(shù)中間節(jié)點(diǎn)處由p(k)度量的有效信息，可得到I(R，B)，這里p(k)=n(k)/N是與節(jié)點(diǎn)k有關(guān)的區(qū)域的相對(duì)面積，n(k)是這個(gè)區(qū)域的像素?cái)?shù)。因此，通道的互信息由下式給出:

這里，T是中間節(jié)點(diǎn)的數(shù)量。值得強(qiáng)調(diào)，最好分割可局部得到。即給定節(jié)點(diǎn)k的信息增益Ik獨(dú)立于圖像其它區(qū)域的分割水平。

對(duì)于式(3)，分割過(guò)程也可視為H(B)=I(R，B)+H(B|R)，這里H(B)是直方圖熵，I(B，R)和H(B|R)分別表示互信息的連續(xù)值和連續(xù)分割后得到的條件熵。信息的不斷獲取增加了I(R，B)，并減少了H(B|R)。條件熵的減少源自分割得到的區(qū)域的不斷均質(zhì)化。注意到，可得到的最大互信息是直方圖熵H(B)，其在整個(gè)過(guò)程中保持恒定。分割算法可由互信息增益的比率MIRr=I(R，B)/H(B)或預(yù)先設(shè)定的區(qū)域個(gè)數(shù)Nr來(lái)終止。

2.2 合并

從應(yīng)用于通道R→B的凝聚信息瓶頸法中，任何用于R的聚類都不會(huì)增加I(R，B)值。類似于在分割階段獲得的互信息增益，見(jiàn)式(12)，2個(gè)臨近區(qū)域r1和r2聚類引起的互信息損失由下式給出:

正如在分割階段所看到的，2個(gè)區(qū)域之間的JS-散度可解釋為它們之間相異性的度量。當(dāng)2個(gè)區(qū)域有相同的直方圖時(shí)相似性達(dá)到最大:如果p(B|r1)=p(B|r2)，那么δI^r=0。因此，如果2個(gè)區(qū)域非常相似(換言之，它們間的JS-散度很小)，可通過(guò)由這2個(gè)區(qū)域的合并取代它們自己來(lái)簡(jiǎn)化通道，而不會(huì)有太多信息損失。這就是下面合并算法的指導(dǎo)原則。

從給定的圖像分割中，算法連續(xù)地合并臨近區(qū)域?qū)?r1，r2)，這樣的δI^r很小。因此，區(qū)域數(shù)量連同通道的互信息不斷地減少。類似于分割算法，停止準(zhǔn)則可由比率MIRr=I(R，B)/H(B)或預(yù)先設(shè)定的區(qū)域數(shù)量來(lái)確定。

這里，H(B|r)是區(qū)域r規(guī)范化直方圖的熵。如果2個(gè)區(qū)域被聚類

3 算法驗(yàn)證

為了評(píng)估本文的方法，將它與文獻(xiàn)［17］中提出的手工分割和規(guī)范化切割分割作比較。實(shí)驗(yàn)采用Berkeley數(shù)據(jù)庫(kù)中的100幅測(cè)試圖像，它們已被手工分割。為了比較不同的分割結(jié)果，應(yīng)用文獻(xiàn)［17］中提出的LCE和GCE誤差測(cè)量法。這些度量定義為:

這里，R(S，pi)表示在分割S中相當(dāng)于某一區(qū)域的像素集合，S包含像素pi，記號(hào)表示集合差異，‖x‖是集合x(chóng)的勢(shì)。這些度量容許重定義，因此不用太關(guān)切分割細(xì)節(jié)層次的重要性。

因?yàn)長(zhǎng)CE和GCE的計(jì)算都要求分割對(duì)，本文評(píng)估:(1)一對(duì)人工分割;(2)人工分割與分離-合并方法分割對(duì)。獲得的結(jié)果如表1所示，每一行對(duì)應(yīng)于每一個(gè)評(píng)估情況的平均距離值。在考慮相同圖像的不同分割以及不同圖像的不同分割時(shí)計(jì)算每一個(gè)度量。在所有的情況下，3個(gè)不同分割的結(jié)果自動(dòng)獲取，這些分割有相同數(shù)量的手工分割區(qū)域。另外，附上了文獻(xiàn)［17］中當(dāng)應(yīng)用規(guī)范化切割分割算法得到的結(jié)果。注意，這種算法的結(jié)果已經(jīng)在數(shù)據(jù)庫(kù)早期獲得，只用更少的圖像和手工分割。

表1 3種分割算法的總體分割誤差

可以看到，相同圖像應(yīng)用分離-合并算法和手工分割獲得的分割之間的相似度，比不同圖像應(yīng)用這些方法獲得的相似度明顯要高。本文的方法應(yīng)用LCE給出了20%的總體誤差(相比于人工分割的5%)，以及應(yīng)用GCE27%的總體誤差(相比于人工分割的8%)。同樣可以看到，獲得的結(jié)果比規(guī)范化切割分割算法得到的結(jié)果更好。

圖2 分離-合并算法的分割結(jié)果

分離-合并算法很好地發(fā)現(xiàn)了紋理區(qū)域的同質(zhì)性，例如圖2(a)中的場(chǎng)地，圖2(b)中斑馬的皮膚，圖2(c)中狒狒頭發(fā)和圖2(d)中的沙灘。這個(gè)良好的性能緣于分割(合并)判斷是基于區(qū)域直方圖之間的散度的。尤其是，擁有相同紋理的2個(gè)區(qū)域具有相似的概率密度函數(shù)，因此它們之間的JS-散度很低。在分割階段，具有相同紋理的一個(gè)區(qū)域不會(huì)被分段，因?yàn)榛バ畔⒃鲆娣浅５?。另一方面，在合并階段，這些區(qū)域?qū)?huì)被合并，因?yàn)榛バ畔p失非常低。因此，每個(gè)區(qū)域?qū)⒅伙@示一種特有的紋理，只有不連接的區(qū)域才可能有相同的紋理。

4 結(jié)束語(yǔ)

本文介紹了基于信息瓶頸法的圖像分割一般框架，并提出了分離-合并算法。該算法定義了圖像區(qū)域間的信息通道和直方圖格段?；诨バ畔⒌谋４?，空間分布和直方圖格段最大程度地關(guān)聯(lián)起來(lái)。該方法的主要優(yōu)點(diǎn)是:不用假設(shè)關(guān)于圖像的任何優(yōu)先信息(例如亮度概率分布)，重視樣本的空間分布。在自然圖像和醫(yī)學(xué)圖像上的不同試驗(yàn)，以及標(biāo)準(zhǔn)算法的比較顯示了提出算法的優(yōu)良性能。

為確定區(qū)域和組群的最佳數(shù)量，對(duì)停止準(zhǔn)則的進(jìn)一步研究是需要的。另一方面，可測(cè)試新的分割渠道，重視其它類型的信息，如顏色、紋理和梯度。該方法在圖像融合以及細(xì)節(jié)層次方面的應(yīng)用將成為下一步研究的重點(diǎn)。

［1］Freixenet J，Mu?oz X，Raba D，et al.Yet another survey on image segmentation:Region and boundary information integration［C］//Proc.Eur.Conf.Computer Vision.Copenhagen，Denmark，2002:408-422.

［2］Gonzalez R C，Woods R E.Digital Image Processing［M］.Prentice-Hall，2002.

［3］Canny J.A computational approach to edge detection［J］.IEEE Trans.Pattern Anal.Mach.Intell.，1986，8(6):679-698.

［4］Shi J，Malik J.Normalized cuts and image segmentation［J］.IEEE Trans.Pattern Anal.Mach.Intell.，2000，22(8):888-905.

［5］Chung R H Y，Yung N H C，Cheung P Y S.An efficientparameter less quadrilateral-based image segmentation method［J］.IEEE Trans.Pattern Anal.Mach.Intell.，2005，27(9):1446-1458.

［6］Ballard D H，Brown C M.Computer Vision［M］.Prentice-Hall，1982.

［7］Forsyth D A，Ponce J.Computer Vision:A Modern Approach［M］.Prentice-Hall，2003.

［8］Geman S，Geman D.Stochastic relaxation，gibbs distributions，and the bayesian restoration of images［J］.IEEE Trans.Pattern Anal.Mach.Intell.，1984，6(6):721-741.

［9］Li S.Markov Random Field Modeling in Image Analysis［M］.New York:Springer，2001.

［10］Wu Y T，Shih F Y，Shi J，et al.A top-down region dividing approach for image segmentation［J］.Pattern Recognit.2008，41(6):1948-1960.

［11］Horowitz S L，Pavlidis T.Picture segmentation by a tree traversal algorithm［J］.J.ACM，1976，23(2):368-388.

［12］Suri J，Setarehdan K，Singh S.Advanced Algorithmic Approaches to Medical Image Segmentation［M］.London，:Springer-Verlag，2002.

［13］Cover T M，Thomas J A.Elements of Information Theory［M］.New York:Wiley，1991.

［14］Burbea J，Rao C R.On the convexity of some divergence measures based on entropy functions［J］.IEEE Trans.Inf.Theory，1982，28(3):489-495.

［15］Tishby N，F(xiàn).Pereira C，Bialek W.The information bottleneck method［C］//Proc.the 37th Annu.Allerton Conf.Communication，Control and Computing.1999:368-377.

［16］Dhillon I S，Mallela S，Modha D S.Information-theoretic co-clustering［C］//Proc.the 9th ACM SIGKDD Int.Conf..2003:89-98.

［17］Martin D，F(xiàn)owlkes C，Tal D，et al.A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics［C］//Proc.the 8th Int.Conf.Computer Vision.2001:416-423.