徐齊高

摘 要 本文研究了基于歸一化割（Ncut）的圖像分割方法的原理及算法實現(xiàn)過程，并進(jìn)行仿真實驗來驗證算法的可行性。實驗表明，Ncut圖像分割方法能在一定條件下取得較好的分割效果，但分類數(shù)目的設(shè)定以及權(quán)值矩陣的計算需進(jìn)一步的探討和分析。

關(guān)鍵詞 圖像分割 歸一化割 權(quán)值矩陣

中圖分類號：TP391.4 文獻(xiàn)標(biāo)識碼：A

0引言

基于圖論進(jìn)行圖像分割是一種較新的圖像分割方法。由于其可獲得良好的結(jié)果，近年來引起人們的興趣，是國際上圖像分割領(lǐng)域的一個研究熱點，尤其是圖切割技術(shù)因它的全局能量最優(yōu)化而格外引人注目?；趫D論進(jìn)行圖像分割其基本思想是將圖像看作一個帶權(quán)圖，其每個節(jié)點對應(yīng)圖像的一個像素或區(qū)域，連接每兩個節(jié)點的邊的權(quán)值表示該兩節(jié)點屬于同一區(qū)域的可能性，權(quán)值的大小與兩節(jié)點的相似性、鄰近性以及連續(xù)性等相關(guān)。根據(jù)圖的某種特定劃分建立相應(yīng)的能量函數(shù)，該能量函數(shù)的最小值即對應(yīng)圖像的一個最佳分組。依據(jù)此思想， 研究者提出了其各自的圖論分割準(zhǔn)則， 其中比較有代表性的為最小割、平均劃分、歸一化割及比例劃分等[1-3]。

其中最小割和歸一化割由于其計算較為簡便使用較廣泛。Wu和Leahy[4]的研究發(fā)現(xiàn)，最小割準(zhǔn)則很容易分割出圖像中的孤立點集合。而歸一化割（NCut）則可以避免分割出孤立點情況。因此，本文采用歸一化割進(jìn)行圖像分割。

1基于歸一化割的圖像分割方法

一副圖像可以采用一個無向圖來G=（V，E）表達(dá)，其中V 是節(jié)點的集合，是E 連接節(jié)點的邊的集合，V的基為N=|V|。連接每兩個節(jié)點的邊均賦予權(quán)值w（u，n），該權(quán)值衡量節(jié)點u 和v的相似程度。圖像G=（V，E）通過簡單的移除兩部分之間相連接的邊，就可以分割為兩個不相交的集合A和B，并且滿足A∪B=V，A∩B= 。這兩部分的不相似的程度可以用移除的邊的權(quán)重之和來計算，通常將他定義為割[5-6]：

cut（A，B）=w（u，v） （1）

最小割準(zhǔn)則就是通過計算割式（1）的最小值來得到圖像的分割方法。

Wu和Leahy提出了基于最小割準(zhǔn)則的聚類方法，而且他們還試圖將一幅圖像分割為k個子區(qū)域，這可以通過遞歸調(diào)用最小割的方法實現(xiàn)。實驗證明，在一些圖像中，這種全局優(yōu)化準(zhǔn)則可以產(chǎn)生比較好的分割結(jié)果。然而，Wu和Leahy在他們的工作中發(fā)現(xiàn)了一個問題，最小割準(zhǔn)則很容易分割出圖像中的孤立點集合。通過最小割的定義式（1）可以分析出現(xiàn)這種現(xiàn)象的原因：最小割的值會隨著連接兩區(qū)域的邊的數(shù)量的增加而變大。假設(shè)邊的權(quán)值與兩個節(jié)點之間的距離成反比，那么將節(jié)點n1單獨分割出來的情況下，所得割的值會非常的小。可以看出，任何一個將右邊的孤立點分割出來的情況都比將圖分割為左右兩個幾乎相等的部分的情況時得到的割的值要小。

為了避免分割出孤立點情況的出現(xiàn)，歸一化分割準(zhǔn)則被提出來。歸一化分割在最小割的基礎(chǔ)上加入了每個區(qū)域的節(jié)點與所有節(jié)點的權(quán)值之和的比，來平衡分割。歸一化分割的公式通?？梢詫憺椋?/p>

Ncut（A，B）=+ （2）

其中assoc（A，V）=∑u∈A，t∈Vw（u，t）是A中所有的節(jié)點到圖像中所有節(jié)點的邊的權(quán)值之和，assoc（B，V）是B中所有的節(jié)點到圖像中所有節(jié)點的邊的權(quán)值之和。通過式（2）可以看出，分割孤立點的情況，在歸一化分割中的值是比較大的。

同樣地，可以有如下的定義：

Nassoc（A，B） =+ （3）

其中，assoc（A，A）和assoc（B，B）分別表示A和B中節(jié)點之間相互連接的邊的權(quán)值之和。式（3）反映了定義的平衡性，他表示每個分組內(nèi)節(jié)點的關(guān)聯(lián)度。

通過式（2）和式（3），可以得到：

（4）

從式（4）可以看出，想要求得的歸一化分割的最小值，也就是求分組內(nèi)的

最大關(guān)聯(lián)度的過程。

采用Ncut 準(zhǔn)則就可以克服劃分孤立點的問題，最小的Ncut 值對應(yīng)的劃分即為圖G 的最優(yōu)劃分。在這種情況下，最小化Ncut 可以轉(zhuǎn)化為如下的標(biāo)準(zhǔn)特征系統(tǒng)

（5）

其中D是N€譔的對角矩陣，其對角線上的元素為=w（i，j），W是對稱矩陣，其元素為w（i，j）， 和z分別為相應(yīng)的特征值和特征矢量。

特征系統(tǒng)（5）的第二個最小的特征值對應(yīng)的特征矢量可以用來完成全圖的最優(yōu)劃分，從而得到對應(yīng)圖像的一個分割結(jié)果?？梢圆捎眠f歸算法以相同的方式進(jìn)一步對分割得到的子圖進(jìn)行劃分，直至滿足終止條件為止。

2實驗結(jié)果及分析

本文實驗所用計算機(jī)CPU主頻為2.5GHz，內(nèi)存為1GB，軟件為MATLAB2014a。下圖中從左至右依次為原圖，采用Ncut分割為3類的結(jié)果圖以及分割為5類的結(jié)果圖。本實驗的權(quán)志矩陣w（u，v）是基于像素（i，j）的相似程度計算的。權(quán)值wij與像素i與j之間的距離及灰度差值成反比。

對比原圖和分割結(jié)果圖可以看出，Ncut分割方法基本可以將前景（小孩）和背景比較好的分離出來。而且設(shè)定的分割類別數(shù)目不同，分割的精細(xì)程度也不同。

3結(jié)論

本文分析了Ncut圖像分割方法的原理及算法求解過程，并利用Ncut進(jìn)行圖像分割。實驗表明，Ncut圖像分割方法能在一定條件下取得較好的分割結(jié)果。但分割種類的設(shè)定、權(quán)值矩陣的計算方法需根據(jù)分割的目的以及特定圖像進(jìn)行分析。

參考文獻(xiàn)

[1] 劉松濤，殷福亮.基于圖割的圖像分割方法及其新進(jìn)展 自動化學(xué)報，2012.38（6）：911-922.

[2] 侯葉.基于圖論的圖像分割技術(shù)研究.西安電子科技大學(xué).博士論文，2011.

[3] J.Shi and J.Malik， “Normalized cuts and image segmentation，” IEEE Trans.Pattern Anal.Mach.Intell.，vol.22，no.8，pp.888–905，Aug.2000.

[4] Wu Z Y， Leahy R. An optimal graph theoretic approach to data clu-stering：Theory and its application to image segmentation.IEEE Transactions on Pattern Analysis Machine Intelligence，1993，15（11）：1101-1113.

[5] 徐俊明.圖論.合肥：中國科學(xué)技術(shù)大學(xué)出版社，2010.3.

[6] 胡曉雷.圖論支持下的圖像分割理論與方法研究.武漢大學(xué)遙感信息工程學(xué)院，2007.

[7] 劉嘉，王宏琦.一種基于圖割的交互式圖像分割方法.電子與信息學(xué)報，2008.30（8）：1973-1976.

[8] 韓守東，趙勇，陶文兵，桑農(nóng).基于高斯超像素的快速Graph Cuts圖像分割方法.自動化學(xué)報，2011.37（1）：11-20.