圖小波變換在圖像分割中的應用研究

王 林，樊淋杰

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

圖小波變換在圖像分割中的應用研究

王 林，樊淋杰

(西安理工大學 自動化與信息工程學院，陜西 西安 710048)

在圖像處理領域中，圖像分割占有舉足輕重的地位。傳統的基于小波變換的圖像分割算法，僅在規則域內能夠有效地檢測出圖像的邊緣信息。為了在不規則域內能夠有效地檢測出圖像的邊緣信息，提出一種基于圖小波變換的圖像分割算法。首先，將圖像轉換成圖，在圖域進行研究；然后，利用圖小波變換進行圖像分割。實驗結果表明，與傳統邊緣算法相比，該算法用于圖像分割，不僅能夠有效地檢測出圖像邊緣信息，而且對噪聲具有較好的魯棒性。

圖論；圖小波變換；圖像分割

0 引言

圖像分割是模式識別、計算機視覺、圖像處理領域中的基礎和關鍵。圖像分割的質量直接影響到圖像分析的效果[1-2]。所謂圖像分割是根據灰度、顏色、紋理和形狀等特征把圖像分成若干個特定的、互不交迭的、具有獨特性質的區域。各區域的并集是整個圖像，各區域的交集為空，并且這些特征在同一區域內呈現相似性，而在不同區域間呈現明顯的差異性[3]。常用的圖像分割方法包括：閾值分割法、邊緣檢測法、區域分割法、圖論分割法等[4]。

圖像分割技術近幾十年來飛速發展，引起人們廣泛關注。許多研究工作由原來的規則域拓展到不規則域[5-6]。尤其是圖論分割法成為國內外研究人員的重點研究對象之一。基于圖論的圖像分割是一種自上而下的全局分割方法，其主要思想是將一幅原始圖像映射成一個加權、無向圖，該圖像中的像素對應于圖中的節點，像素之間的關系對應于節點間的邊，像素間的相關程度(差異性或相似性)對應于邊的權重[7]。然后在所建立的圖上利用分割準則對圖中的節點進行劃分，進而完成對圖像的分割。

ZAHN C[8]提出一種基于圖的最小生成樹的圖像分割方法，主要是通過將圖中權值最小的邊分割開來構造子圖從而得到分割結果，此方法主要考慮圖的局部特征，導致分割效果不理想。之后MALIK J等人[9]提出了一種歸一化分割算法，其考慮到了圖像所分區域內部的自相似性，具有捕捉圖像非局部特性的能力，分割效果得到很大提高，但是計算復雜度較高。FELZENSZWALB P F等人[10]提出了一種快速算法，通過評估圖的邊緣值來尋找一個分段之間邊界的依據，提高了分割速度，但穩定性不夠。BOYKOV Y Y等人[11]對于N維圖像提出了半自動分割方法，主要考慮節點之間的邊以及目標與背景之間的明顯部分，然后利用圖割來獲取特定目標的邊界，此方法擴展了處理圖像的維數，但分割速度較低。GRADY L等人[12]提出基于等周算法的全自動圖像分割方法，主要通過尋找最小等周率來進行圖像分割，此方法分割速度和穩定度均有了一定的提高。

近幾年，研究人員對圖論分割算法進行了改進。強軻楠[13]提出一種基于圖論使用蟻群算法分割圖像的算法，本算法分割圖像的分割效果較為精確，計算復雜度較低。楊丹丹等人[14]提出一種基于圖論和多尺度分析的圖像分割算法，本算法分割效果較好，但存在一定的時間復雜度和一定的過分割現象。吳秋紅等人[15]提出一種基于圖論和FCM(模糊C均值聚類，Fuzzy C Means)的圖像分割算法，該算法不僅保證了圖像分割質量，而且提高了圖像分割速度。田利平等人[16]提出了一種基于圖論最小生成樹和閾值的圖像分割算法，不但改善了分割效果，而且提高了分割效率。

由于圖小波變換提供了類似于傳統小波變換的多尺度分析，而且在不規則域內能夠有效地檢測出圖像的邊緣信息，因此提出一種基于圖小波變換的圖像分割算法。在本文中，將介紹如何利用圖小波變換對定義在圖上的函數進行不規則性檢測；對于圖像分割問題，會對圖小波變換進行調整來開發一種替代工具。首先，將一幅圖像映射成圖。其次，利用圖小波變換[17]來獲取圖上節點間的小波系數。然后，對這些小波系數進行閾值處理，從而識別出圖像中相應的邊緣像素。最后，通過采樣圖像來評估本文提出算法對噪聲的魯棒性，并將其與現有的算法進行比較來評估本文提出算法的性能。

1 基礎理論(圖小波變換)

CROVELLA M等人[17]早期定義了圖小波變換(Graph Wavelet Transform, GWT)，用于總結網絡交通信息，其利用跳鄰居節點的信息對傳統小波變換中的平移和縮放操作進行調整。

(1)

為了滿足基本條件：

(2)

則歸一化常數Cj,k需要滿足如下條件：

(3)

因此，小波信號Ψj,k可寫成：

(4)

(5)

設g:V→R為圖上節點的任意函數，Ψj,k為小波信號，則圖小波變換可定義如下：

(6)

ψj,h=(j+1)∫Ij,hψ(x)dx

(7)

2 研究方法

2.1 將圖像映射成圖

圖像中相鄰像素的強度值沿著連續段移動平緩變化，像素強度值的突變部分可以看作兩個不同像素集群之間的邊緣。一個二維、無向、稀疏圖G=(V,E)可以由灰度圖像IM×N映射形成，如下：

(1)圖像中像素點形成圖的節點：I(m,n)→Vi，其中m∈{1,2,…,M}，n∈{1,2,…,N}，i=M(n-1)+m。

(2)圖像中相鄰像素點之間的關系形成圖中節點之間的邊：

Ei,j=h(I(mi,ni),I(mj,nj))

(8)

h(I(mi,ni),I(mj,nj))=

(9)

其中τ∈{1，2，…,N}，i≠j。τ值決定了相鄰像素的范圍。例如，τ=1，那么相鄰像素由8個最近鄰像素組成。

(3)圖像像素的強度值形成定義在圖上的節點函數：

f(Vi)=I(m,n)

(10)

其中，I(m,n)為圖像像素的強度值。

2.2 計算小波系數

利用GWT結合哈爾小波(j=1)的方法對圖計算小波系數Wi。由于哈爾函數是最簡單的小波函數，并且可以有效地檢測出信號的突變部分，因此選擇哈爾小波對圖像進行研究分析。此外，由于更高的尺度小波分解需要考慮更多的相鄰像素，然而感興趣的只是第一尺度的分析，因此選擇j=1。

2.3 閾值處理

根據得到閾值的方法的不同，可將閾值分為以下幾種類型，如圖1所示。

圖1 閾值處理分類

對計算得到的小波系數進行局部閾值處理，從而確定圖像邊緣的像素：

(11)

其中Wi為對應于節點vi的小波系數，t為設定的閾值。

3 實驗及結果分析

實驗對象：下載的貓圖像；實驗環境：MATLAB(R2009b)。

首先，將下載的貓圖像轉換為灰度圖像；然后，利用如前面所述方法形成圖以及相應的函數。分別利用GWT、Canny和Sobel三種算法對貓圖像進行圖像分割處理，得出結果如圖2所示。由圖2可以看出，利用GWT算法能夠有效地檢測出圖像的邊緣，然而利用其他兩種算法可能會導致圖像邊緣的部分像素丟失。

圖2 貓原圖像以及利用GWT、Canny、Sobel方法對貓原圖像分割的結果

圖3 對貓原圖像進行一階哈爾小波分解且閾值化后的結果

對于常規的二維離散小波變換(2D-DWT)來說，其細節系數對應于圖像的高頻細節部分，近似系數對應于圖像的低頻近似部分。為了說明GWT和2D-DWT之間的區別，利用2D-DWT對實驗對象進行處理。首先，通過丟棄一階哈爾小波分解的低頻近似系數來重構圖像。然后，對得到的圖像進行硬閾值化處理，得出結果如圖3所示。由圖3可以看出，利用2D-DWT對圖像進行分割，會導致圖像邊緣的部分像素丟失。

通過設置τ= 1 、τ= 2，噪聲級別分別為10 dB、20 dB、30 dB，針對不同圖結構對邊緣檢測性能的影響分別進行了評估，得出結果如圖4所示。通過觀察實驗結果得出：選擇τ= 2，對噪聲提供了更好的魯棒性，即增加τ值會導致產生更多的相鄰像素，同時表現出小波系數的平滑效應。

圖4 令τ= 1 、τ= 2，噪聲級別為10 dB、20 dB、30 dB，對貓原圖像進行邊緣提取后的結果

4 結論

本文提出一種利用圖小波變換進行圖像分割的方法。實驗結果表明，圖小波變換結合第一尺度哈爾小波，這一方法對定義在任意圖上函數的變化點(對應于圖像的邊緣)進行檢測非常有效。圖的結構直接影響到方法的魯棒性。未來工作是，在不同尺度下利用不同的母小波函數進行研究，也會考慮利用不同的方法由圖像構造圖。

[1] 杜雯超, 陳其松, 周瑩. 基于分段自適應遺傳算法的圖像閾值分割[J]. 微型機與應用, 2015, 34(3): 58-62.

[2] 隋然, 潘點飛. 基于分段自適應遺傳算法的圖像閾值分割[J]. 微型機與應用, 2015, 34(14): 45-47.

[3] 李余錢, 蘇光大. 基于鄰域處理器自適應圖像分割高速實現[J]. 電子技術應用, 2016, 42(2): 99-101.

[4] 柳歡歡, 姚明海, 王憲保. 基于小波變換的GrabCut圖像分割[J]. 計算機系統應用, 2014, 23(8): 154-157.

[5] SHUMAN D I, NARANG S K, FROSSARD P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Transactions on Signal Processing Magazine, 2013, 30(3): 83-98.

[6] HAMMOND D K, VANDERGHEYNST P, GRIBONVAL R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.

[7] DAVID I SHUMAN, BENJAMIN RICAUD, PIERRE VANDERGHEYNST. Vertex-frequency analysis on graphs[J]. Applied & Computational Harmonic Analysys, 2016,40(2):260-291.

[8] ZAHN C. Graph theoretical methods for detecting and describing gestalt clusters[J]. IEEE Transactions on Computation, 1971, 20(1): 68-86.

[9] Shi Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[10] FELZENSZWALB P F, HUTTENLOCHER D P. Efficient graph-based image segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

[11] BOYKOV Y Y, JOLLY M P. Interactive graph cuts for optimal boundary & region segmentation of objects in Nd images[C]. Eighth IEEE International Conference on Computer Vision, 2001: 105-112.

[12] GRADY L, SCHWARTZ E L. Isoperimetric graph partitioning for image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(3): 469-475.

[13] 強軻楠. 基于圖論的蟻群算法在圖像分割中的應用[J]. 計算機光盤軟件與應用, 2012,48(14):105-106.

[14] 楊丹丹, 王衛星, 廖一鵬. 基于多尺度分析及圖論歸一化割的礦巖顆粒圖像分割及應用[J]. 四川大學學報, 2015, 47(1): 118-124.

[15] 吳秋紅, 吳謹, 朱磊，等. 基于圖論和FCM的圖像分割算法[J]. 液晶與顯示, 2016, 31(1): 112-116.

[16] 田利平, 謝忠和. 基于閾值和圖論的圖像分割算法研究[J]. 寧德師范學院學報, 2016, 28(1):62-65.

[17] CROVELLA M, KOLACZYK E. Graph wavelets for spatial traffic analysis[C]. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, 2003: 1848-1857.

Application of graph wavelet transform in image segmentation

Wang Lin, Fan Linjie

(School of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

In the field of image processing, image segmentation occupies a pivotal position. The traditional image segmentation algorithm based on wavelet transform can only effectively detect the image edge information on regular domains. In order to be able to effectively detect the image edge information on irregular domains, the paper proposes the image segmentation algorithm based on Graph Wavelet Transform. The images are firstly transformed to the graph domain and the graph wavelet transform is used for image segmentation. Experimental results prove that proposed algorithm can not only effectively detect the image edge information, but also has better noise robustness compared with the traditional edge algorithms for image segmentation.

graph theory; graph wavelet transform; image segmentation

TP391

A

10.19358/j.issn.1674- 7720.2017.08.013

王林，樊淋杰.圖小波變換在圖像分割中的應用研究[J].微型機與應用，2017,36(8)：39-41，44.

2016-11-26)

王林(1963-)，男，博士，教授，主要研究方向：復雜網絡、大數據理論與應用、無線傳感器及計算機應用。

樊淋杰(1988-)，通信作者，男，碩士研究生，主要研究方向：通信網絡理論與物聯網技術。E-mail: 846495390@qq.com。

________________________