李德棟，肖楚琬，龐 威

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

0 引言

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

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

1 相關(guān)研究

1.1 圖像分割

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

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

1.2 信息論

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

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

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

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

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

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

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

這里，JS(π1，…，πn;p1，…，pn)是具有先驗概率的概率分布{p1，…，pn}或滿足πi=1的權(quán)重{π1，…，πn}的 Jensen-Shannon 散度。JS-散度度量了概率pi來自它們共同發(fā)送端的程度πipi，以及當(dāng)且僅當(dāng)所有的pi均等時接近0的程度。值得注意，當(dāng){π1，…，πn}和{p1，…，pn}分別表示輸入分布和通道X→Y的概率轉(zhuǎn)移矩陣時，JS-散度對I(X，Y)來說是恒等的，這里n=|Χ|，m=|Y|。換句話說，π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∈Χ可通過某個條件概率px)分配給每簇(軟聚類)。第二種情況下，每簇x∈Χ只分配給一簇(硬聚類)。

滿足以下特性:

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

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

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

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

2 分離-合并算法

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

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

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

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

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

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

2.1 分割

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

由下式給出:

這里，π1=p(r1)/p，π2=p(r2)/p()。2 個區(qū)域之間的 JS-散度 JS(π1，π2;p(B|r1)，p(B|r2))，可解釋為它們在亮度值方面相異性的度量。也就是，當(dāng)一個區(qū)域被分割時，互信息增益等于分割得到的區(qū)域之間相異度乘以區(qū)域的尺寸。在分割算法中，最優(yōu)的分割通過最大化互信息增益δI?r來得到。

這里，π1=p(r1)/p，π2=p(r2)/p(。2 個區(qū)域之間的 JS-散度 JS(π1，π2;p(B|r1)，p(B|r2))，可解釋為它們在亮度值方面相異性的度量。也就是，當(dāng)一個區(qū)域被分割時，互信息增益等于分割得到的區(qū)域之間相異度乘以區(qū)域的尺寸。在分割算法中，最優(yōu)的分割通過最大化互信息增益δI來得到。

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

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

對于式(3)，分割過程也可視為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)，其在整個過程中保持恒定。分割算法可由互信息增益的比率MIRr=I(R，B)/H(B)或預(yù)先設(shè)定的區(qū)域個數(shù)Nr來終止。

2.2 合并

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

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

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

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

3 算法驗證

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

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

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

表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)中的場地，圖2(b)中斑馬的皮膚，圖2(c)中狒狒頭發(fā)和圖2(d)中的沙灘。這個良好的性能緣于分割(合并)判斷是基于區(qū)域直方圖之間的散度的。尤其是，擁有相同紋理的2個區(qū)域具有相似的概率密度函數(shù)，因此它們之間的JS-散度很低。在分割階段，具有相同紋理的一個區(qū)域不會被分段，因為互信息增益非常低。另一方面，在合并階段，這些區(qū)域?qū)缓喜?，因為互信息損失非常低。因此，每個區(qū)域?qū)⒅伙@示一種特有的紋理，只有不連接的區(qū)域才可能有相同的紋理。

4 結(jié)束語

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

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

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