基于歸一化割的圖像分割

徐齊高

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

關鍵詞 圖像分割 歸一化割 權值矩陣

中圖分類號：TP391.4 文獻標識碼：A

0引言

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

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

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

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

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

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

Wu和Leahy提出了基于最小割準則的聚類方法，而且他們還試圖將一幅圖像分割為k個子區域，這可以通過遞歸調用最小割的方法實現。實驗證明，在一些圖像中，這種全局優化準則可以產生比較好的分割結果。然而，Wu和Leahy在他們的工作中發現了一個問題，最小割準則很容易分割出圖像中的孤立點集合。通過最小割的定義式（1）可以分析出現這種現象的原因：最小割的值會隨著連接兩區域的邊的數量的增加而變大。假設邊的權值與兩個節點之間的距離成反比，那么將節點n1單獨分割出來的情況下，所得割的值會非常的小?？梢钥闯觯魏我粋€將右邊的孤立點分割出來的情況都比將圖分割為左右兩個幾乎相等的部分的情況時得到的割的值要小。

為了避免分割出孤立點情況的出現，歸一化分割準則被提出來。歸一化分割在最小割的基礎上加入了每個區域的節點與所有節點的權值之和的比，來平衡分割。歸一化分割的公式通常可以寫為：

Ncut（A，B）=+ （2）

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

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

Nassoc（A，B） =+ （3）

其中，assoc（A，A）和assoc（B，B）分別表示A和B中節點之間相互連接的邊的權值之和。式（3）反映了定義的平衡性，他表示每個分組內節點的關聯度。

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

（4）

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

最大關聯度的過程。

采用Ncut 準則就可以克服劃分孤立點的問題，最小的Ncut 值對應的劃分即為圖G 的最優劃分。在這種情況下，最小化Ncut 可以轉化為如下的標準特征系統

（5）

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

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

2實驗結果及分析

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

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

3結論

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

參考文獻

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

[2] 侯葉.基于圖論的圖像分割技術研究.西安電子科技大學.博士論文，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] 徐俊明.圖論.合肥：中國科學技術大學出版社，2010.3.

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

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

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