基于圖論的Normalized Cut圖像分割算法

趙春蘭

摘 要：基于圖論的圖像分割算法是近年來圖像分割領域研究的的熱點問題，該文就其Normalized Cut算法進行了簡要的介紹，并利用其對圖像進行了仿真分割。

關鍵詞：圖論 圖像 分割算法

中圖分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）06（c）-0049-01

1 圖論相關背景知識

圖論（Graph Theory），起源于18世紀歐拉研究和解決的柯尼斯堡七橋問題（Konigsberg），是研究頂點與邊所組成的圖形的理論與方法，20世紀50年代初剛剛開始發展，以圖（Graph）作為研究對象，是離散數學的分支。近年來，計算機技術在各個領域的被廣泛應用，使得圖論其在電子、信息論等學科中的應用也取得了很大的進展。

2 基于圖論的圖像分割準則

基于圖論的圖像分割方法主要是利用分割準則實現的，到目前為止，基于圖論的圖像分割準則主要被分為基于特征向量分割準則、基于區域合并分割準則、與基于歸一化割分割準則三類。

（3）利用步驟（2）中求出的第二小特征向量將圖像分割為兩部分。

（4）判斷圖像是否還需要做進一步的分割，若需要繼續分割，則遞歸調用該算法完成圖像的分割。通常，作者設定的最大允許SNcut值或分割區域所包含的最小像素數SArea作為是否需要繼續分割判斷依據，作為Ncut算法最終迭代停止條件。

3.2 具體分割實例

（1）本文涉及到測試用顱腦MR圖像均為灰度圖像，為了實現腫瘤圖像的分割，衡量像素間相似度矩陣W選擇如公式（4）所示：

（4）

在公式（4）中，F（i）用于表示圖像像素灰度值，x（i）為圖像像素按列元素從上至下重新排列后位置，在引入像素灰度信息的同時也引入像素坐標信息。、為控制像素點間值域差異與空域差異的敏感程度參數，r為兩個像素點之間設定的有效距離。

（2）算法中設置迭代次數為1000，兩個算法停止條件，sNcut表示Ncut所允許的最小值，sArea則表示Ncut分割區域允許包括的最小像素數，以先達到者為算法停止條件。

4 結語

本章內容首先對經典Normalized Cut所涉及到的理論及相關知識做了簡要介紹，并利用matlabR2010a對Normalized Cut進行算法仿真，并將其應用到相關圖像分割中，該算法基本可以將目標從背景圖像中分割出來，但分割的精度有待于進一步提高，這與分割中相關參數的設定、權重矩陣的選取有關，將在以后做進一步的研究。

參考文獻

[1] 孫惠泉.圖論及其應用[M].科學出版社，2004：1-2.

[2] 劉建龍.基于圖論的圖像分割算法研究[D].哈爾濱工業大學，2006.

[3] 孫亮.基于圖論的文檔圖像分割應用研究[D].山東師范大學，2009.

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學報，2007（1）：110-119.

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

摘 要：基于圖論的圖像分割算法是近年來圖像分割領域研究的的熱點問題，該文就其Normalized Cut算法進行了簡要的介紹，并利用其對圖像進行了仿真分割。

關鍵詞：圖論 圖像 分割算法

中圖分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）06（c）-0049-01

1 圖論相關背景知識

圖論（Graph Theory），起源于18世紀歐拉研究和解決的柯尼斯堡七橋問題（Konigsberg），是研究頂點與邊所組成的圖形的理論與方法，20世紀50年代初剛剛開始發展，以圖（Graph）作為研究對象，是離散數學的分支。近年來，計算機技術在各個領域的被廣泛應用，使得圖論其在電子、信息論等學科中的應用也取得了很大的進展。

2 基于圖論的圖像分割準則

基于圖論的圖像分割方法主要是利用分割準則實現的，到目前為止，基于圖論的圖像分割準則主要被分為基于特征向量分割準則、基于區域合并分割準則、與基于歸一化割分割準則三類。

（3）利用步驟（2）中求出的第二小特征向量將圖像分割為兩部分。

（4）判斷圖像是否還需要做進一步的分割，若需要繼續分割，則遞歸調用該算法完成圖像的分割。通常，作者設定的最大允許SNcut值或分割區域所包含的最小像素數SArea作為是否需要繼續分割判斷依據，作為Ncut算法最終迭代停止條件。

3.2 具體分割實例

（1）本文涉及到測試用顱腦MR圖像均為灰度圖像，為了實現腫瘤圖像的分割，衡量像素間相似度矩陣W選擇如公式（4）所示：

（4）

在公式（4）中，F（i）用于表示圖像像素灰度值，x（i）為圖像像素按列元素從上至下重新排列后位置，在引入像素灰度信息的同時也引入像素坐標信息。、為控制像素點間值域差異與空域差異的敏感程度參數，r為兩個像素點之間設定的有效距離。

（2）算法中設置迭代次數為1000，兩個算法停止條件，sNcut表示Ncut所允許的最小值，sArea則表示Ncut分割區域允許包括的最小像素數，以先達到者為算法停止條件。

4 結語

本章內容首先對經典Normalized Cut所涉及到的理論及相關知識做了簡要介紹，并利用matlabR2010a對Normalized Cut進行算法仿真，并將其應用到相關圖像分割中，該算法基本可以將目標從背景圖像中分割出來，但分割的精度有待于進一步提高，這與分割中相關參數的設定、權重矩陣的選取有關，將在以后做進一步的研究。

參考文獻

[1] 孫惠泉.圖論及其應用[M].科學出版社，2004：1-2.

[2] 劉建龍.基于圖論的圖像分割算法研究[D].哈爾濱工業大學，2006.

[3] 孫亮.基于圖論的文檔圖像分割應用研究[D].山東師范大學，2009.

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學報，2007（1）：110-119.

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

摘 要：基于圖論的圖像分割算法是近年來圖像分割領域研究的的熱點問題，該文就其Normalized Cut算法進行了簡要的介紹，并利用其對圖像進行了仿真分割。

關鍵詞：圖論 圖像 分割算法

中圖分類號：TP391 文獻標識碼：A 文章編號：1674-098X（2014）06（c）-0049-01

1 圖論相關背景知識

圖論（Graph Theory），起源于18世紀歐拉研究和解決的柯尼斯堡七橋問題（Konigsberg），是研究頂點與邊所組成的圖形的理論與方法，20世紀50年代初剛剛開始發展，以圖（Graph）作為研究對象，是離散數學的分支。近年來，計算機技術在各個領域的被廣泛應用，使得圖論其在電子、信息論等學科中的應用也取得了很大的進展。

2 基于圖論的圖像分割準則

基于圖論的圖像分割方法主要是利用分割準則實現的，到目前為止，基于圖論的圖像分割準則主要被分為基于特征向量分割準則、基于區域合并分割準則、與基于歸一化割分割準則三類。

（3）利用步驟（2）中求出的第二小特征向量將圖像分割為兩部分。

（4）判斷圖像是否還需要做進一步的分割，若需要繼續分割，則遞歸調用該算法完成圖像的分割。通常，作者設定的最大允許SNcut值或分割區域所包含的最小像素數SArea作為是否需要繼續分割判斷依據，作為Ncut算法最終迭代停止條件。

3.2 具體分割實例

（1）本文涉及到測試用顱腦MR圖像均為灰度圖像，為了實現腫瘤圖像的分割，衡量像素間相似度矩陣W選擇如公式（4）所示：

（4）

在公式（4）中，F（i）用于表示圖像像素灰度值，x（i）為圖像像素按列元素從上至下重新排列后位置，在引入像素灰度信息的同時也引入像素坐標信息。、為控制像素點間值域差異與空域差異的敏感程度參數，r為兩個像素點之間設定的有效距離。

（2）算法中設置迭代次數為1000，兩個算法停止條件，sNcut表示Ncut所允許的最小值，sArea則表示Ncut分割區域允許包括的最小像素數，以先達到者為算法停止條件。

4 結語

本章內容首先對經典Normalized Cut所涉及到的理論及相關知識做了簡要介紹，并利用matlabR2010a對Normalized Cut進行算法仿真，并將其應用到相關圖像分割中，該算法基本可以將目標從背景圖像中分割出來，但分割的精度有待于進一步提高，這與分割中相關參數的設定、權重矩陣的選取有關，將在以后做進一步的研究。

參考文獻

[1] 孫惠泉.圖論及其應用[M].科學出版社，2004：1-2.

[2] 劉建龍.基于圖論的圖像分割算法研究[D].哈爾濱工業大學，2006.

[3] 孫亮.基于圖論的文檔圖像分割應用研究[D].山東師范大學，2009.

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學報，2007（1）：110-119.

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