一種基于歸一化割的圖像分割算法

摘 要：歸一化割準(zhǔn)則不僅度量了不同分組之間的總體不相似性，同時(shí)度量了各個(gè)組之內(nèi)的總體相似性。具體研究了基于歸一化割的圖像分割算法，并將其應(yīng)用于不同類型的圖像分割中，取得了較好的效果。

關(guān)鍵詞：圖像分割；歸一化割；圖的劃分；分組

中圖法分類號(hào)：TP391.41文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001—3695(2007)02—0165—02

圖像分割是指將一幅圖像分解成若干互不相交區(qū)域的集合，其實(shí)質(zhì)是一個(gè)按照像素屬性（灰度、顏色、紋理等）進(jìn)行聚類的過程。目前存在上千種分割算法，且這方面的研究仍在繼續(xù)，但至今既不存在一種通用的圖像分割方法，也不存在一種判斷是否分割成功的客觀標(biāo)準(zhǔn)[1]。

常見的圖像分割方法有：局部濾波方法，如Canny 邊緣檢測(cè)算子，該方法僅利用圖像局部

信息，并不能保證得到連續(xù)的閉合邊界；活動(dòng)輪廓方法(Active Contour，又稱為Snakes)；區(qū)域生長(zhǎng)與合并算法，如K-均值法、EM算法；基于能量函數(shù)的全局最優(yōu)化方法等[2]。近幾年，基于圖論的圖像分割方法也是人們感興趣的領(lǐng)域之一。Shi 和Malik將圖像分割轉(zhuǎn)換為最優(yōu)化圖的劃分問題，提出了歸一化割準(zhǔn)則（Normalized Cut Criterion）作為全局最優(yōu)準(zhǔn)則，其中加權(quán)圖由任意空間一系列點(diǎn)構(gòu)成，圖中頂點(diǎn)代表圖像的像素或區(qū)域，邊界的權(quán)代表相鄰的像素或者區(qū)域的相似度[2]。圖的劃分技術(shù)是將圖劃分成許多非連接性點(diǎn)集，其中同一點(diǎn)集內(nèi)的點(diǎn)相似程度高，不同點(diǎn)集之間的相似程度低。衡量相似程度的標(biāo)準(zhǔn)可以是位置、灰度、顏色和紋理等[3]。此外，歸一化割的優(yōu)化問題可以近似為一個(gè)廣義特征值問題。

1 歸一化割準(zhǔn)則

歸一化割準(zhǔn)則是由Shi 和Malik 提出的一種無(wú)監(jiān)督圖像分割技術(shù)，它不需要初始化，并具有三個(gè)主要的特點(diǎn)[4]：①它將圖像分割問題轉(zhuǎn)換為圖的劃分問題；②它是一個(gè)全局準(zhǔn)則；③它同時(shí)最大化不同組之間的不相似性和同一組內(nèi)的相似性。

一幅圖的最優(yōu)二分法即是使Cut的值最小，但由于割直接與割中邊的數(shù)目成比例，因此最小割（Minimum Cut）通常并非就是最優(yōu)割。針對(duì)這個(gè)缺點(diǎn)Shi 和Malik提出了一種新的不同組之間的不相似性度量，即歸一化割：

由此可知，在圖的劃分算法中，尋找不同分組之間總體最小不相似性與同一個(gè)組內(nèi)部總體最大相似性實(shí)際上是一樣的，兩者可同時(shí)滿足。

如果y只取實(shí)值，則可以通過解決廣義特征值問題來求解式（6）：

y的約束來自于相應(yīng)的指示向量x的條件。式（7）可以寫成規(guī)范特征值問題：

其中z=D 。該特征值問題的對(duì)應(yīng)具有第二個(gè)最小特征值的特征向量滿足規(guī)范約束，即可以利用該特征向量對(duì)圖進(jìn)行劃分。但由于特征向量的每個(gè)元素一般都是連續(xù)值，因此就需要定義一個(gè)分離點(diǎn)。通常選擇0或這些元素的中值作為分離點(diǎn)，也可以采用試探法尋找最優(yōu)分離點(diǎn)，從而得到圖的最優(yōu)劃分[2，5]。同時(shí)可以證明，利用具有第三個(gè)最小特征值的特征向量可將第一次分割得到的結(jié)果再次進(jìn)行最優(yōu)劃分。若進(jìn)一步地利用具有次最小特征值的特征向量，就可以對(duì)現(xiàn)有的圖進(jìn)行細(xì)分。但是，由于特征向量的元素實(shí)際值與離散值之間存在近似誤差，且所有特征向量必須滿足互相正交的約束，使得此法不妥。最好的辦法還是將每個(gè)子圖單獨(dú)劃分，此時(shí)可用遞歸的方法進(jìn)行處理[3，6]。

通過研究以上原理，可以按照以下步驟實(shí)現(xiàn)該算法[3，7]：

(1）給定一幅圖像或圖像序列，建立一個(gè)加權(quán)圖G=(V，E)，設(shè)定邊的權(quán)值函數(shù)，用來度量?jī)牲c(diǎn)間的相似程度；

(2）利用最小特征值求出對(duì)應(yīng)的特征向量；

(3）利用具有第二個(gè)最小特征值的特征向量來將圖一分為二；

(4）判斷是否需要細(xì)分，如有必要?jiǎng)t采用遞歸方法將已分割的圖再細(xì)分。

2 基于歸一化割的圖像分割實(shí)驗(yàn)

將圖像分割轉(zhuǎn)換為圖的劃分問題，首先要構(gòu)造一個(gè)加權(quán)圖G=(V，E)，圖的每個(gè)頂點(diǎn)代表圖像的每一個(gè)像素，連接點(diǎn)i和j點(diǎn)的邊的權(quán)w(i， j)，表示兩點(diǎn)之間相似程度（根據(jù)圖像的特點(diǎn)，可以選擇位置、灰度、顏色和紋理等特征來衡量相似程度）：

其中d(i， j)表示點(diǎn)i和點(diǎn)j之間的歐幾里得距離，σ_x決定空間相似程度，F(xiàn)_i是基于圖像灰度、顏色或紋理信息的特征向量，σ_I對(duì)應(yīng)決定所選信息的相似程度。

為了檢驗(yàn)本文介紹的算法，先把歸一化割用在一幅簡(jiǎn)單的加權(quán)圖上，如圖1所示。圖1（a）是由v₁，v₂，…，v₇七個(gè)點(diǎn)組成的加權(quán)圖，圖的邊上的數(shù)字表示邊的權(quán)。利用歸一化割可將它一分為二，如圖1（b）所示。

為進(jìn)一步說明歸一化割在圖像分割方面的效果，選取六幅圖像進(jìn)行實(shí)驗(yàn)。如圖2所示，分別是人工圖像、人造物（火車、飛機(jī)）、自然景觀、動(dòng)物和人物圖像。經(jīng)過基于歸一化割的圖像分割算法處理后，即可得到滿意的分割結(jié)果，如圖3所示。

一般基于歸一化割的圖像分割過程較慢，這是因?yàn)閳D像尺寸如果是N×M，則加權(quán)矩陣W是一個(gè)NM×NM的大矩陣。同時(shí)由W的定義可知，它是一個(gè)對(duì)稱稀疏矩陣，當(dāng)點(diǎn)i和點(diǎn)j之間的距離大于r個(gè)像素時(shí)，wij為0。這里，我們選的圖像都不是很大，如果要分割的圖像尺寸較大時(shí)，可對(duì)其進(jìn)行采樣。

3 結(jié)論

本文介紹了歸一化割準(zhǔn)則，它是將圖進(jìn)行劃分的一個(gè)全局最優(yōu)判據(jù)。與以往將局部特征和一致性度量作為解決問題的關(guān)鍵不同，歸一化割著重于提取整幅圖像的特征，同時(shí)度量不同分組之間的總體不相似性和各個(gè)組內(nèi)的相似性的總和。為了計(jì)算最小歸一化割，可以將其轉(zhuǎn)換為廣義特征值問題來對(duì)待。實(shí)驗(yàn)結(jié)果表明，將歸一化割應(yīng)用于醫(yī)學(xué)圖像分割中，可以準(zhǔn)確地提取出目標(biāo)區(qū)域輪廓，具有良好的應(yīng)用前景。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。