基于提升小波和雙樹復小波的圖像檢索新算法

舒彬

(陜西學前師范學院 數(shù)學系,陜西 西安 710100)

基于提升小波和雙樹復小波的圖像檢索新算法

舒彬

(陜西學前師范學院 數(shù)學系,陜西 西安 710100)

由于提升小波的高效性,雙樹復小波的多方向選擇性等特點,所以本文提出了一種新的檢索算法:基于提升小波和雙樹復小波變換的圖像檢索算法。此算法首先對圖像分別進行提升小波和雙樹復小波變換,得到每層各個方向上的高頻子圖像;然后將各層上各方向的高頻子圖像組合,提取它們的紋理特征;最后通過計算特征向量之間的canberra距離,檢索出相似度高的圖像。實驗結(jié)果說明,此算法的檢索效率高于提升小波和雙樹復小波的算法。

提升小波; 雙樹復小波;紋理特征; canberra距離;圖像檢索

由于計算機技術(shù)突飛猛進地發(fā)展,海量的圖像數(shù)據(jù)不斷地涌現(xiàn),如何快速準確地檢索出用戶所需要的圖像數(shù)據(jù),已成為研究人員的熱門課題。紋理是圖像明顯而穩(wěn)定的性質(zhì),能表達圖像中像素的灰度空間的分布現(xiàn)象,方向性為紋理的非常重要的性質(zhì),如果能提取到很多的方向信息,將有助于提高紋理識別的效率。迄今為止,已有很多研究者將小波理論應用到圖像得特征提取中。因為,小波變換具有很好的時(空)頻域性,將小波變換應用到圖像處理中,此時,圖像信號將由時間域(空間域)轉(zhuǎn)換到小波域表示?？梢岳眯〔ㄗ儞Q的正交／雙正交的變換特性,將圖像的像素間的相關(guān)性消除。從而降低了圖像信號在空間中的冗余。由于傳統(tǒng)的卷積小波(第1代小波)變換過程的復雜,運算的量大,實時性比較差,20世紀90年代,小波提升算法(lifting scheme)或稱為自舉法[2]由Sweldens提出,完成了空間域上小波的構(gòu)造完全。提升小波變換又稱作第二代小波變換技術(shù),和經(jīng)典的Mallat算法相比較,它可以實現(xiàn)小波變化的原位計算;且其減少了一半的運算量;整數(shù)到整數(shù)的小波變換容易實現(xiàn),會極大地減少計算的時間和空間的復雜度。所以,應用提升小波變換對圖像進行分解,將有利于縮短檢索的時間,提高準確率。因為傳統(tǒng)的小波變換具有有限的方向性,進行紋理特征描述時不夠充分,因此一種雙樹復小波變換(Dual-tree Complex Wavelet Transform,DT-CWT)[3]信號分析方法由Kingsbury[4]提出,它建立在實數(shù)小波理論框架的基礎(chǔ)上,具有如下優(yōu)點:良好的多方向選擇性,近似的平移不變性,計算量很小,有限的冗余度,因為這些優(yōu)點,方便了紋理特征的提取。

1 小波變換的提升實現(xiàn)

1.1 db2小波變換的提升理論[5]

基于提升格式的小波變換,在對系統(tǒng)內(nèi)存需求以及變換實現(xiàn)的復雜度等方面都是一種非常有效的實現(xiàn)形式。有限長雙正交小波變換,可以通過有限步的提升和對偶提升操作完成。為得到提升小波變換的形式,令小波濾波器的多相矩陣為:

其中,he( z)、ho( z)、ge(z)、go(z)分別為合成低通濾波器h及高通濾波器g的奇偶分量。對于雙正交小波,其分解濾波器與合成濾波器是相同的,因此,對偶多相矩陣p( z)與p( z)相等。對于給定互補濾波器對(h, g),總是存在洛朗多項式si( z)和ti( z),(其中1≤i≤m)以及常數(shù)k有:

換句話說,所有有限長沖激響應濾波器小波變換都可以從一個懶小波變換開始,經(jīng)過m步提升和雙提升操作,最后進行尺度變換來完成。

1.2 二維圖像的小波變換提升

設F是一個M×N的圖像矩陣,第一步:對F的每一行按1.1節(jié)所述方法進行一維提升小波變換,低頻分量存儲在矩陣F每一行的前[N/2]項,高頻分量存儲在后[N/2]項;再對F的每一列進行一維提升小波變換,方法同行變換。

2 基于雙樹復小波變換的理論知識[7]

雙樹復小波變換采用兩個實小波可稱為樹A和樹B。其中,變換的實部由上部樹A給出,變換的虛部由下部樹B給出。兩個實小波變換采用不同的兩個濾波器集合,每一個集合都滿足完美重建條件。將這兩組濾波器設計在一起,變換是近似可分析的。

那么可得到以下6個小波:

因為雙樹復小波變換的二維形式是通過對二維信號(圖像)分別對行和列進行一維分解。同時分解行和列,抑制負頻率，二維信號頻譜的第一象限被保留，方向選擇性由高維的復數(shù)小波變換提供。6個不同的方向由以上6個實數(shù)方向小波成功分離，它們都來自于一對經(jīng)典的小波，都近似滿足ψg（t）=h｛ψh（t）｝［8］。雙樹復小波的冗余性與分解的尺度數(shù)無關(guān)。它提供了良好的方向選擇性，如：6個方向的紋理特征。而經(jīng)典的2-D DWT僅能提供3個方向。

3 基于提升小波和雙樹復小波的圖像檢索算法

3.1 紋理特征

對圖像分別進行K層db2小波提升變換和雙樹復小波變換，圖像紋理主要集中在高頻部分，因此，選用高頻子圖像的均值和標準差來表示其紋理信息。提升小波變換后，得到9K個高頻子圖像記做ft，t=1，2，???，9K。第t個高頻子圖像的均值Mt和標準差St分別為：

i=1，2，???，8k ｛M1，S1，M2，S2，???，Mi，Si｝i=1，2，…R， j=1，2，…C其，中，R和C是每一個高頻子圖像的行數(shù)和列數(shù)，代表子圖像的大小。于是，整幅圖像F的紋理特征可表示為1*16k維的向量，記為：，其中：

3.2 相似度的度量

通過上述特征提取公式可以建立紋理特征數(shù)據(jù)庫。檢索性能不僅與提取的特征有關(guān)，而且還與相似性的計算方法有關(guān)。好的相似性計算方法提高檢索效率的同時，還能縮短檢索的時間。由于提取的紋理特征用均值和標準差表示，它們具有不同的物理意義，并且量綱不同，如果使用歐式距離進行相似性計算，對不相同物理意義的特征需要歸一化處理，從而使計算復雜化，為了使計算量減少，采用Canberra距離，此距離能夠解決量綱產(chǎn)生的問題，定義公式，如下：

其中：d（x，y）表示兩個特征向量x，y之間的距離，D表示特征向量的維數(shù)，xi，yi則表示特征向量x，y的第i個分量。

3.3 圖像檢索算法

取8K幅高頻子圖像的均值和標準差作為它們的紋理特征，得到維的特征向量；記為：

｛M1，S1，M2，S2，???，Mi，Si｝ i=1，2，???，8k 從圖庫中讀入每幅圖像，并對圖庫中的每個圖像都重復進行與查詢圖像同樣的步驟（1）-（4）操作。

求取每幅圖像的紋理特征數(shù)據(jù)與查詢圖像的紋理特征數(shù)據(jù)的Canberra距離。距離越小，相似程度越高。

4 實驗結(jié)果和分析

本文實現(xiàn)了一個實驗系統(tǒng)。測試使用文獻［6］中SIMPLIcity系統(tǒng)測試集，它是從Corel圖像庫選取的600幅圖像，包括10類，每類60張，如恐龍，汽車、花、、海灘、建筑、非洲土著居民等。在下面的實驗中，共選取6類圖像（恐龍，馬、海灘、公共汽車、花、建筑），對每一類圖像隨機抽取1幅作為查詢圖像，用基于提升小波變換的紋理特征的圖像檢索算法和基于雙樹復小波變換的紋理特征圖像檢索算法與本文的算法做比較，并選取系統(tǒng)返回的前20幅的圖像作為檢索結(jié)果。限于篇幅，只取一類結(jié)果，如圖3-圖5所示：

圖3 基于提升小波變換的圖像檢索算法

圖4 基于雙樹復小波變換的圖像檢索算法

圖5 本文檢索算法

圖3到圖5中，系統(tǒng)返回20幅圖像，其中第一幅圖為查詢圖像。在圖3到圖5中，可以看到對于紋理清晰的公共汽車類圖像，用提升小波變換的紋理特征的檢索算法檢索出了5幅，基于雙樹復小波變換的紋理特征檢索算法檢索出了6幅，本文的算法檢索出了16幅。

文中用查全率（recall）［9］及查準率（precision）［10］來評價檢索算法的好壞。查全率：返回的圖像中，與查詢圖像相關(guān)的數(shù)目占圖庫中相關(guān)圖像的總數(shù)的比例。設w是原始圖像，其查全率及查準率可以設為：

其中，N是圖庫中與原始圖像w相類似的圖像總數(shù)；n是系統(tǒng)檢索到的與原始圖像相似的圖像數(shù)目；F是系統(tǒng)自動搜索得到圖像的總數(shù)目。當查全率及查準率越大時，說明該算法的檢索率越高。

下面是三種算法檢索出來的結(jié)果的比較。

實驗：對公共汽車、建筑物、海灘風景圖像檢索

表1 三種方法的檢索性能數(shù)據(jù)比較

從表1中容易得出，基于提升小波的圖像檢索算法，雖然對各類圖像查詢所需的時間比基于雙樹復小波變換的紋理特征圖像檢索算法的短，但它的查全率P（%）和查準率R（%），顯然低于基于雙樹復小波變換的紋理特征圖像檢索算法，而本文檢索算法的查全率及查準率不但高于文中的其他兩種檢索算法，并且檢索時間也比其他兩種算法的查詢時間短。綜上所述，本文的檢索算法優(yōu)于文中其他的兩種圖像檢索算法。

5 結(jié)束語

本文提出：基于提升小波和雙樹復小波變換的圖像檢索算法。第一步：對圖像分別進行K層db2小波提升變換和K層雙樹復小波變換；得到各層的3個方向上的和6個方向上的高頻子圖像，第二步：將各層上的8K個方向上的高頻子圖像組合在一起，得到8K幅高頻子圖像。第三步：取8K幅高頻子圖像的均值和標準差作為它們的紋理特征，計算圖像間的紋理特征數(shù)據(jù)的Canberra距離，完成檢索過程。雖然本文的檢索算法，具有紋理特征描述能力，但是缺乏對圖像語義的描述，如對食物的檢索效果有待提高，對此將在以后進行研究討論。

［1］趙珊.基于內(nèi)容的圖像檢索關(guān)鍵技術(shù)研究［博士學位論文］.西安：西安電子科技大學，2007.

［2］SWELDENS W. The lifting scheme： A custom design construction of biorthogona lwavelets， ApplHarmon.Anal，1996，3（2）：186-200.

［3］Nick Kingsbury. The Dual-tree Complex Wavelet Tra nsform： a New Technique for Shift Invariance and Directional Filters［C］//Proc 8 IEEE DSPW orkshop，［S I ：Bryce Canyon ，1998.］

［4］Kingsbury N.Complex wavelets for shift invariant analysis and filtering of signals［J］.Applied and Computational Har-monic Analysis，2001，10（3）：234-253.

［5］趙志杰，林茂六，曹志民，劉增玉.基于db2提升小波的可伸縮視頻編碼方法.通信學報， 2009，1，30（1）：88-94.

［6］DAUBECHIES I .et al.Factoring wavelet transforms into lifting steps.J Fourier Anal Appl，1998， 4（3）：247-269.

［7］基于多尺度及多方向分析的紋理圖像檢索算［J］.鄭州大學學報，2009，41（1）：27-32.

［8］Haralick R M，Shanmugam K，Dinstein I.Textures features for image classification［J］.IEEE Transactions on Systems，Man and Cybernetics，1973，3（6）：610-621.

［9］劉忠偉，章毓晉.綜合利用顏色和紋理特征的圖像檢索.通信學報，1999，20（5）：36-40.

［10］王華，戴芳.一種基于基元的彩色圖像檢索方法.計算機系統(tǒng)應用，2011，20（1）：95-99.

TP391

A

1003-5168(2015)11-267-03