基于歸一化割的圖像分割

徐齊高

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

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

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

0引言

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

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

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

一副圖像可以采用一個無向圖來G=（V，E）表達，其中V 是節點的集合，是E 連接節點的邊的集合，V的基為N=|V|。……