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

黎瑩，戴芳，郝勇，左濤

西安理工大學 理學院應用數學系，西安 710054

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

黎瑩，戴芳，郝勇，左濤

西安理工大學 理學院應用數學系，西安 710054

1 引言

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

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

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

2 結合改進的最小生成樹和NNG方法的圖像分割

2.1 利用改進的最小生成樹進行圖像初分割

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

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

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

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

對于大小為m×n的圖像I，本文重新構造一個(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的方差。

對于邊的構造，取

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

圖2 本文構造的算法分割過程示意圖

2.2 利用NNG方法對初分割圖像進行合并

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

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

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

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

3 實驗結果

實驗1對風景圖進行分割，圖3（a）為原圖，圖3（b）為本文方法，圖3（c）為文獻[8]的方法。

圖3 風景圖的分割比較

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

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

圖4 分割效果比較

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

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

圖5 迭代次數對比圖

由圖5（a）的結果可以看出，當合并的次數過少時，得到的分割區域很多，有明顯的過分割效應。在圖5（b）中很多過分割的區域被有效的合并，得到了較好的分割效果，保留了圖像的細節信息。但是當合并次數較大時，由圖5（c）可以看到其較好地保留了目標區域，但圖像的很多細節信息被合并了。

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

4 結論

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

[1]孫即祥.圖像分析[M].北京：科學出版社，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]葉偉，王遠軍.基于Mumford-Shah理論的最小生成樹圖像分割方法[J].計算機輔助設計與圖形學學報，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

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

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

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—），女，碩士研究生，主要研究領域為智能計算與信息處理；戴芳（1966—），女，博士，教授，碩士生導師，主要研究領域為智能計算與信息處理。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