黎瑩，戴芳，郝勇，左濤

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

基于最小生成樹(shù)的圖像分割

黎瑩，戴芳，郝勇，左濤

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

1 引言

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

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

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

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

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

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

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

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

圖1 最小生成樹(shù)分割過(guò)程示意圖

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

圖4 分割效果比較

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

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

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

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

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

4 結(jié)論

首先采用了改進(jìn)的最小生成樹(shù)方法對(duì)圖像進(jìn)行分割，其次利用了NNG方法對(duì)初分割后的圖像進(jìn)行合并。本文方法減少了最小生成樹(shù)的構(gòu)造過(guò)程，節(jié)省了分割時(shí)間，通過(guò)合并使過(guò)分割的區(qū)域得到了有效的減少，較好地保留了全局信息。但是利用NNG方法進(jìn)行迭代合并時(shí)，迭代次數(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理論的最小生成樹(shù)圖像分割方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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

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

最小生成樹(shù)；相似鄰近圖；圖像分割

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)域?yàn)橹悄苡?jì)算與信息處理；戴芳（1966—），女，博士，教授，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄苡?jì)算與信息處理。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