趙春蘭

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）06（c）-0049-01

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

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

2 基于圖論的圖像分割準(zhǔn)則

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

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

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

3.2 具體分割實(shí)例

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

（4）

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計(jì)算機(jī)學(xué)報(bào)，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ái)圖像分割領(lǐng)域研究的的熱點(diǎn)問題，該文就其Normalized Cut算法進(jìn)行了簡(jiǎn)要的介紹，并利用其對(duì)圖像進(jìn)行了仿真分割。

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）06（c）-0049-01

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

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

2 基于圖論的圖像分割準(zhǔn)則

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

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

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

3.2 具體分割實(shí)例

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

（4）

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4] 陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法[J].計(jì)算機(jī)學(xué)報(bào)，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ái)圖像分割領(lǐng)域研究的的熱點(diǎn)問題，該文就其Normalized Cut算法進(jìn)行了簡(jiǎn)要的介紹，并利用其對(duì)圖像進(jìn)行了仿真分割。

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）06（c）-0049-01

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

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

2 基于圖論的圖像分割準(zhǔn)則

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

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

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

3.2 具體分割實(shí)例

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

（4）

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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