王 林，樊淋杰

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

圖小波變換在圖像分割中的應(yīng)用研究

王 林，樊淋杰

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

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

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

0 引言

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

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

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

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

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

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

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

(1)

為了滿足基本條件：

(2)

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

(3)

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

(4)

(5)

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

(6)

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

(7)

2 研究方法

2.1 將圖像映射成圖

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

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

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

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)圖像像素的強度值形成定義在圖上的節(jié)點函數(shù)：

f(Vi)=I(m,n)

(10)

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

2.2 計算小波系數(shù)

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

2.3 閾值處理

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

圖1 閾值處理分類

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

(11)

其中Wi為對應(yīng)于節(jié)點vi的小波系數(shù)，t為設(shè)定的閾值。

3 實驗及結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

[4] 柳歡歡, 姚明海, 王憲保. 基于小波變換的GrabCut圖像分割[J]. 計算機系統(tǒng)應(yīng)用, 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] 強軻楠. 基于圖論的蟻群算法在圖像分割中的應(yīng)用[J]. 計算機光盤軟件與應(yīng)用, 2012,48(14):105-106.

[14] 楊丹丹, 王衛(wèi)星, 廖一鵬. 基于多尺度分析及圖論歸一化割的礦巖顆粒圖像分割及應(yīng)用[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

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

2016-11-26)

王林(1963-)，男，博士，教授，主要研究方向：復(fù)雜網(wǎng)絡(luò)、大數(shù)據(jù)理論與應(yīng)用、無線傳感器及計算機應(yīng)用。

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

________________________