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

趙春蘭

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

關(guān)鍵詞：圖論 圖像 分割算法

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

1 圖論相關(guān)背景知識

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

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

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

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

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

3.2 具體分割實例

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

（4）

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

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

4 結(jié)語

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

參考文獻

[1] 孫惠泉.圖論及其應(yīng)用[M].科學(xué)出版社，2004：1-2.

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

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

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學(xué)報，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

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

關(guān)鍵詞：圖論 圖像 分割算法

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

1 圖論相關(guān)背景知識

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

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

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

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

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

3.2 具體分割實例

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

（4）

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

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

4 結(jié)語

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

參考文獻

[1] 孫惠泉.圖論及其應(yīng)用[M].科學(xué)出版社，2004：1-2.

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

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

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學(xué)報，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

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

關(guān)鍵詞：圖論 圖像 分割算法

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

1 圖論相關(guān)背景知識

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

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

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

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

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

3.2 具體分割實例

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

（4）

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

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

4 結(jié)語

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

參考文獻

[1] 孫惠泉.圖論及其應(yīng)用[M].科學(xué)出版社，2004：1-2.

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

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

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計算機學(xué)報，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