基于最小生成樹的圖像分割

黎瑩，戴芳，郝勇，左濤

西安理工大學(xué) 理學(xué)院應(yīng)用數(shù)學(xué)系，西安 710054

基于最小生成樹的圖像分割

黎瑩，戴芳，郝勇，左濤

西安理工大學(xué) 理學(xué)院應(yīng)用數(shù)學(xué)系，西安 710054

1 引言

圖像分割是利用圖像某些特性，如灰度、顏色、紋理等，將圖像分割成若干個獨立且有意義的連續(xù)區(qū)域或?qū)ο骩1]。在每個區(qū)域內(nèi)有相同的特性，這些區(qū)域能夠表達(dá)設(shè)計的場景或者物體，符合現(xiàn)實中人眼的視覺特性。按照實現(xiàn)原理的不同，圖像分割算法可分為以下四大類：基于閾值的分割方法、基于邊緣檢測的分割方法、基于區(qū)域提取的分割方法和結(jié)合特定理論的分割方法。隨著各學(xué)科新理論和新方法的提出，出現(xiàn)了許多與特定理論相結(jié)合的圖像分割方法，如基于聚類分析的圖像分割方法、基于模糊集理論的分割方法、基于小波變換的分割方法、基于神經(jīng)網(wǎng)絡(luò)的分割方法和基于圖論的分割方法等。

圖論中，將圖像的像素映射為圖的頂點，頂點和頂點之間的連接映射為邊，邊的權(quán)值代表頂點之間的相似性或差異性，通常構(gòu)造圖的鄰接矩陣來實現(xiàn)圖像分割。經(jīng)典的利用圖理論進(jìn)行圖像分割的方法有Normalized-Cut（N-Cut）方法[2]、最小生成樹方法[3]、最大流最小割方法[4]等。N-Cut方法考慮了所分子區(qū)域內(nèi)的自相似性，利用區(qū)域的全局特征，采用“歸一化”的方法使算法的分割效果得到改善，然而，歸一化分割方法是一個NP完全問題，計算復(fù)雜度過高。最大流最小割方法將圖像映射為一個網(wǎng)絡(luò)，對待分割的物體內(nèi)部（目標(biāo)）及其外部（背景）像素分別做出不同的標(biāo)記，給予不同的權(quán)重，利用能量最小化的原理進(jìn)行分割，獲得物體的輪廓。該框架具有快速性好，全部最優(yōu)及抗噪性強的優(yōu)點，但其必須人工指定目標(biāo)內(nèi)部及其外部的像素作為種子點才能進(jìn)行分割，限制了算法在圖像分割中的應(yīng)用。最小生成樹方法進(jìn)行圖像分割時，對圖像信息可從全局進(jìn)行把握，最小生成樹的生長過程可以保留低變化區(qū)域內(nèi)部的細(xì)節(jié)，并且尋找最小權(quán)值的過程具有自適應(yīng)性，從而表現(xiàn)圖像的全局特征，符合人眼的視覺特性[5]，保證了算法能夠獲得比較好的全局分割結(jié)果，并且分割效率高，算法數(shù)據(jù)結(jié)構(gòu)簡單。但是當(dāng)圖像的尺寸增加時，構(gòu)造最小生成樹對邊進(jìn)行排序?qū)⒃黾舆\算負(fù)擔(dān)。另外，利用最小生成樹進(jìn)行全局閾值分割易受到圖像噪聲以及不同區(qū)域間邊界的影響，因此利用最小生成樹進(jìn)行圖像分割，鄰接矩陣的構(gòu)造和閾值的選取是該方法的關(guān)鍵。文獻(xiàn)[6]在閾值的選取上對最小生成樹方法進(jìn)行改進(jìn)；文獻(xiàn)[7]將最小生成樹算法和Mumford-Shah理論結(jié)合，提出新的優(yōu)化方案，得到了好的分割效果。

文獻(xiàn)[8]提出了一種新的類似最小生成樹的方法，減少了構(gòu)建最小生成樹的過程，但是利用類似的最小生成樹方法進(jìn)行分割會得到很多過分割的塊。本文基于文獻(xiàn)[8]構(gòu)造了新的分割方法，保留了圖像的全局信息，并提出了利用Nearest Neighbor Graph（NNG）對初分割的結(jié)果進(jìn)行合并。該方法較好地保留了圖像特征信息，對初分割后的結(jié)果進(jìn)一步的處理，使分割的效果得到改善。

2 結(jié)合改進(jìn)的最小生成樹和NNG方法的圖像分割

2.1 利用改進(jìn)的最小生成樹進(jìn)行圖像初分割

給定一個無向圖G=(V，E)，這里V代表像素集，E代表像素之間的連接稱為邊，E的大小代表兩個相鄰像素的差異稱為權(quán)，若找到連接所有像素的非連通的子集，連接像素的權(quán)值和最小則稱為最小生成樹。利用最小生成樹進(jìn)行圖像分割，則是通過割斷最小樹邊的權(quán)值大于閾值的邊。

圖像利用最小樹分割，首先要將圖像映射到圖空間，構(gòu)造區(qū)域鄰接圖（Region Adjacency Graph，RAG）；對于m×n大小的圖像，若構(gòu)造鄰接矩陣將產(chǎn)生(m×n)2大小的矩陣，對于尺寸較大的圖像，直接構(gòu)造RAG耗費大量時間。因此本文改進(jìn)了最小生成樹的構(gòu)造過程，節(jié)約了分割時間。

圖1為最小生成樹進(jìn)行圖像分割的原理示意圖，其中圖（a）為人工合成圖像，圖（b）為將圖像（a）映射為圖后得到的最小生成樹，（c）為割斷最小生成樹大于閾值的邊（閾值設(shè)置為1），得到的最后分割圖。

圖1 最小生成樹分割過程示意圖

對于大小為m×n的圖像I，本文重新構(gòu)造一個(2m-1)×(2n-1)大小的矩陣M來存儲圖的頂點和邊，在M中位置(2i-1，2j-1)存儲頂點V(i，j)，位置(2i-1，2j)存儲頂點V(i，j)與V(i+1，j)的邊，位置(2i，2j-1)存儲頂點V(i，j)與V(i，j-1)的邊，位置(2i，2j)存儲頂點V(i，j)與V(i+1，j+1)的邊和V(i，j+1)與V(i+1，j)的邊中的最小值，在文中令閾值等于I的方差。

對于邊的構(gòu)造，取

圖2為本文構(gòu)造的算法進(jìn)行圖像分割的過程示意圖，其中圖（a）為對圖1（a）中的人工合成圖構(gòu)造的M矩陣，這里對于頂點位置設(shè)置為1，邊的計算由公式（1）得到；在圖（b）中大于閾值的邊設(shè)為0（這里閾值設(shè)定為1）；圖（c）為對頂點標(biāo)號，若一個像素周圍的8鄰域都為1，則這些像素屬于同一區(qū)域，將一個區(qū)域的元素標(biāo)記為一類。

圖2 本文構(gòu)造的算法分割過程示意圖

2.2 利用NNG方法對初分割圖像進(jìn)行合并

本文對于利用改進(jìn)的最小生成樹方法得到的初分割結(jié)果，設(shè)最后得到k個區(qū)域，每個區(qū)域代表一個頂點，區(qū)域的信息用灰度均值代表分別為c(1)，c(2)，…，c(k)，構(gòu)造RAG，對于新構(gòu)造的RAG邊的定義為：

對于一個RAG和一個無向圖G(V，E)，NNG的定義如下：它是一張有向圖Gm=(Vm，Em)，其中Vm=V。其邊(u，h)的構(gòu)造如下，u，h∈V，并且如果

由公式（3）可以得到NNG中的邊，按如下方法確定：對于RAG中某個頂點u，設(shè)在所有與其相連的邊中，只保留具有最小權(quán)值的那條邊所連接的相鄰頂點。因此，在NNG中，頂點u有且僅有一條指向節(jié)點v的邊，并且當(dāng)有多于一個頂點使sm（u，v)最小化時，則邊指向具有最小標(biāo)記值的那個頂點。

在構(gòu)造的相似性矩陣RAG中只保存相似性函數(shù)值為1的，其余的值設(shè)為∞，利用公式（3）得到最后的NNG。若頂點u和頂點v都保留了s(u，v)這條邊，則將u、v這兩個區(qū)域進(jìn)行合并，對于合并后的區(qū)域更新灰度值以及標(biāo)號，根據(jù)圖像的大小設(shè)置不同的迭代次數(shù)。

3 實驗結(jié)果

實驗1對風(fēng)景圖進(jìn)行分割，圖3（a）為原圖，圖3（b）為本文方法，圖3（c）為文獻(xiàn)[8]的方法。

圖3 風(fēng)景圖的分割比較

通過實驗1，由圖3（b）和（c）可以看出本文方法得到了較好的分割效果，從云層和山峰可以看出本文方法得到的分割效果更好。

實驗2對Lena圖，利用本文和文獻(xiàn)[8]方法對分割結(jié)果進(jìn)行比較。圖4（a）為原圖，圖4（b）為本文方法的分割結(jié)果，圖4（c）為利用文獻(xiàn)[8]方法分割并進(jìn)行NNG合并后的分割結(jié)果。

圖4 分割效果比較

由實驗2的結(jié)果可以看出，在圖4（c）的面部有過分割的現(xiàn)象，而圖4（b）為本文的分割效果，減少了過分割現(xiàn)象的產(chǎn)生。本文方法更好地抓住了全局信息，得到了較好的分割效果。

實驗3利用NNG方法進(jìn)行圖像合并，其迭代次數(shù)的選取也影響分割的效果，對Lena圖選取不同的迭代次數(shù)，比較分割后的結(jié)果。圖5（a）為利用NNG方法進(jìn)行合并時迭代次數(shù)為23的分割效果，圖5（b）為利用NNG方法合并時迭代次數(shù)為50的分割效果，圖5（c）為利用NNG方法合并時迭代次數(shù)為100的分割效果。

圖5 迭代次數(shù)對比圖

由圖5（a）的結(jié)果可以看出，當(dāng)合并的次數(shù)過少時，得到的分割區(qū)域很多，有明顯的過分割效應(yīng)。在圖5（b）中很多過分割的區(qū)域被有效的合并，得到了較好的分割效果，保留了圖像的細(xì)節(jié)信息。但是當(dāng)合并次數(shù)較大時，由圖5（c）可以看到其較好地保留了目標(biāo)區(qū)域，但圖像的很多細(xì)節(jié)信息被合并了。

本文的時間復(fù)雜度主要包括兩部分：（1）利用改進(jìn)方法構(gòu)造最小生成樹進(jìn)行分割的時間復(fù)雜度為O(m×n)；（2）NNG算法進(jìn)行圖像合并必須構(gòu)造鄰接矩陣，若初始分割得到k個區(qū)域則最大時間復(fù)雜度為O(k!)，若迭代次數(shù)為k1則合并總的時間復(fù)雜度為O(k1×k!)?？偟臅r間復(fù)雜度為O(m×n+k1×k!)，其計算時間復(fù)雜性主要集中在利用NNG合并時構(gòu)造的鄰接圖上，因此減少區(qū)域塊是提升時間復(fù)雜度的主要途徑。

4 結(jié)論

首先采用了改進(jìn)的最小生成樹方法對圖像進(jìn)行分割，其次利用了NNG方法對初分割后的圖像進(jìn)行合并。本文方法減少了最小生成樹的構(gòu)造過程，節(jié)省了分割時間，通過合并使過分割的區(qū)域得到了有效的減少，較好地保留了全局信息。但是利用NNG方法進(jìn)行迭代合并時，迭代次數(shù)影響著分割的效果，關(guān)于迭代次數(shù)的確定還需要進(jìn)一步探討。

[1]孫即祥.圖像分析[M].北京：科學(xué)出版社，2005.

[2]Shi J，Malik J.Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888-905.

[3]Suk M，Cho T H.Segmentation of images using minimum spanning tree[J].Applications of Digital Processing V，1983，397：180-185.

[4]Boykov Y，Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[C]//Proceedings of International Conference on Computer Vision，2001：105-112.

[5]Zahn C T.Graph theoretical methods for detecting and describing gestalt clusters[J].IEEE Trnas on Computers，1997，20（1）：68-86.

[6]Haddon J F，Boyce J F.Image segmentation by unifying region and boundary information[J].Transactions on Pattern Analysis and Machine Intelligence，1990，12（10）：929-948.

[7]葉偉，王遠(yuǎn)軍.基于Mumford-Shah理論的最小生成樹圖像分割方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（8）：1127-1134.

[8]Cha B，Suetake N，Kawano H，et al.Fast minimum-spanningtree-likeimagesegmentation[C]//Proceedingsofthe4th International Conference on Natural Computation，2008：152-156.

LI Ying,DAI Fang,HAO Yong,ZUO Tao

School of Science,Xi’an University of Technology,Xi’an 710054,China

Based on minimum spanning tree,a method of image segmentation using improved minimum spanning tree is presented.The procedure of generating minimum spanning tree is reduced,and then the similarity-based neighborhood graph method is applied to merge image split by minimum spanning tree.The proposed method saves the time of image segmentation,meanwhile,based on the effective merger the better segmentation results are obtained.

minimum spanning tree;NNG（Nearest Neighbor Graph）method;image segmentation

基于最小生成樹思想，給出了一種利用改進(jìn)的最小生成樹進(jìn)行圖像分割的方案，減少了最小生成樹的構(gòu)建過程，對初分割的結(jié)果利用NNG算法進(jìn)行合并。該方案節(jié)約了分割時間，并且對分割后的圖像進(jìn)行了有效的合并，達(dá)到了較好的分割效果。

最小生成樹；相似鄰近圖；圖像分割

A

TN911.73

10.3778/j.issn.1002-8331.1111-0064

LI Ying,DAI Fang,HAO Yong,et al.Image segmentation based on minimum spanning tree.Computer Engineering and Applications,2013,49（13）：149-151.

黎瑩（1986—），女，碩士研究生，主要研究領(lǐng)域為智能計算與信息處理；戴芳（1966—），女，博士，教授，碩士生導(dǎo)師，主要研究領(lǐng)域為智能計算與信息處理。E-mail：li_ying1108@126.com

2011-11-08

2012-01-02

1002-8331（2013）13-0149-03

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1722.087.html