小波仿射不變函數與凸殼相結合的目標識別

摘 要:提出一種將小波仿射不變函數與凸殼相結合進行目標識別的方法。基于小波仿射不變函數構造了絕對小波仿射不變函數，作為待識別目標的特征向量，與凸殼相結合進行目標識別。該方法首先提取待識別目標的輪廓線，然后以輪廓線的一個凸殼頂點為起始點重新構造目標輪廓線點列，計算輪廓線點列的絕對小波仿射不變函數，與模板庫中的模板進行匹配，根據最大相關原則識別目標。實驗結果表明了該方法的有效性。

關鍵詞:小波仿射不變函數;絕對小波仿射不變函數;仿射變換;相關系數;凸殼

中圖分類號:TP391.4文獻標識碼:A

文章編號:1004-373X(2010)06-156-04

Object Recognition Based on Wavelet Affine Invariant Function and Convex Hull

ZHANG Mingjie

(China Academy of Electronics and Information Technology，Beijing，100041，China)

Abstract:A method which combined Wavelet Affine Invariant Function (WAIF) with Convex Hull for object recognition is proposed.The Absolute Wavelet Affine Invariant Function (AWAIF) is constructed based on WAIF，and is used as the eigenvector of the object to be recognized，and is combined with Convex Hull for object recognition.First，contour line of the object to be recognized is extracted.Then，a new contour line whose start point is one of vertex of the convex hull of the object，and AWAIF of the contour line is calculated and used as the eigenvector.The object is then recognized according to the maximum correlation rule.The experiment results show efficiency of the proposed method.

Keywords:wavelet affine invariant function;absolute wavelet affine invariant function;affine transform;correlation coefficient;convex hull

0 引 言

小波變換是一種有效的信號分析工具，可同時在時域和頻域對信號的局部特性進行描述，被人們譽為“數學顯微鏡”，近年來被廣泛地用于信號分析、圖像壓縮[1]等領域。在基于目標形狀的模式識別領域中，小波變換的應用也越來越多，如Tieng等人利用目標輪廓線的小波變換系數的零交叉點來表示和識別目標[2]，Sun等人將小波變換用于手寫字體的輪廓線檢測[3]，Chen等人結合傅里葉變換和小波描述子進行目標的識別[4] ，Kiymik等人將小波變換與人工神經網絡相結合進行目標識別[5]，Khalil等人使用目標輪廓線的小波變換系數的模極大值來識別目標[6]。Khalil與Bala等人利用目標輪廓線在不同尺度上的小波變換系數構造了小波仿射不變函數，并用模擬實驗驗證了這種小波仿射不變函數對于平面曲線在平面上的仿射變換具有不變性。

這里首先對小波變換、小波仿射不變函數進行介紹，并基于相對小波仿射不變函數構造了絕對小波仿射不變函數;然后對凸殼的仿射不變性進行介紹;接著列出目標識別算法，將絕對小波仿射不變函數作為待識別目標的特征向量與凸殼相結合進行目標識別;最后得出實驗結果和結論。

1 小波變換

小波變換是一種線性變換[9]。假設x(t)∈L2(R)(L2(R)表示定義在實數集R上的所有平方可積函數的集合)。以φ(t)∈L2(R)表示一個小波母函數，該函數滿足容許性條件Cφ=2π∫|ξ|-1|(ξ)|2dξ<∞(其中:(ξ)=12π∫φ(t)e-iξtdt是函數φ(t)的傅里葉變換函數)，將由小波母函數φ(t)經過伸縮和平移得到的小波函數族，記作{φs，k(t)=1sφt-ks|s，k∈R，s>0}。其中:s表示尺度因子;k表示平移因子。則函數x(t)的小波變換系數可表示為:

Wx(s，k)==1s∫x(t)φt-ksdt(1)

式中:φ(#8226;)表示函數φ(#8226;)的共軛函數，該式中積分運算的線性保證了小波變換的線性。

2 小波仿射不變函數

假設使用點集C={(x(t)，y(t))}表示在一個平面上以t為參數的曲線，則對該曲線上任意一點(x(t)，y(t))經仿射變換得到的點((t)，(t))表示為:

x(t)=a0+a1x(t)+a2y(t)(2)

y(t)=b0+b1x(t)+b2y(t)(3)

式(2)和式(3)可以用矩陣的形式表示為:

x(t)

y(t)〗=a1a2

b1b2〗x(t)

y(t)〗+a0b0〗=

Ax(t)

y(t)〗+B(4)

式中:A為非奇異方陣，表示旋轉、縮放以及剪切等變換;B表示平移向量。該仿射變換的Jacobi行列式J=a1b2-a2b1=det(A)。

以I(t)表示一個定義在參數曲線C上的仿射不變函數;I(t)表示定義在曲線C′上的與I(t)形式相同的仿射不變函數(曲線C′是由曲線C經過仿射變換得到的平面曲線)，則這兩個仿射不變函數之間的關系可以表示為:

I(t)=I(t)Jω(5)

式中:指數ω稱為不變權。如果ω=0，那么I稱為絕對仿射不變函數，否則I稱為相對仿射不變函數。

假設使用Wix(t)表示在尺度i上點列x(t)的小波變換，那么對式(2)和式(3)的兩邊都做小波變換可得:

Wix(t)=Wia0+a1Wix(t)+a2Wiy(t)(6)

Wiy(t)=Wib0+b1Wix(t)+b2Wiy(t)(7)

式中:Wia0=Wib0=0。利用目標輪廓線點列在兩個不同尺度i，j上的小波變換系數定義小波仿射不變函數如下:

Ii，j(t)=Wix(t)Wjy(t)-Wjx(t)Wiy(t)

=Wix(t) Wiy(t)

Wjx(t) Wjy(t)，i≠j(8)

可以證明[7]:

Ii，j(t)=Wix(t)Wjy(t)-Wjx(t)Wiy(t)

=det(A)Ii，j(t)(9)

所以，式(8)定義的小波仿射不變函數是相對仿射不變函數，不變權是1，本文將其稱為相對小波仿射不變函數。Khalil與Bala等人利用模擬實驗驗證了相對小波仿射不變函數式(8)在一個平面上對于參數曲線的平移、旋轉、縮放、剪切等仿射變換具有相對不變性。

基于相對小波仿射不變函數式(8)構造絕對小波仿射不變函數。方法是:將相對仿射不變函數除以該函數的所有元素的和，即:

fi，j(t)=Ii，j(t)/∫Ii，j(t)dt(10)

其絕對仿射不變性的證明過程如下:

i，j(t)=Ii，j(t)/∫Ii，j(t)dt =[det(A)Ii，j(t)]/

[det(A)∫Ii，j(t)dt]=Ii，j(t)/∫Ii，j(t)dt=fi，j(t)(11)

使用絕對小波仿射不變函數式(10)的絕對最大值對該函數進行規一化處理，即:

Fi，j(t)=i，j(t)/maxt∈R{|i，j(t)|}(12)

本文使用式(12)中定義的Fi，j(t)作為目標輪廓線的特征函數。由于式(12)是由絕對仿射不變函數式(10)除以一個常數得到的，所以Fi，j(t)對于平面曲線的平移、旋轉、縮放、剪切等仿射變換具有絕對仿射不變性。

3 凸殼的仿射不變性

平面上一個點集的凸殼是包含該點集的最小凸多邊形區域[10]，凸多邊形區域的頂點稱為凸殼頂點。由于對凸多邊形進行仿射變換后仍然是凸多邊形，所以對平面上的點集進行仿射變換不會改變該點集的凸殼頂點，在此將這個性質稱為凸殼的仿射不變性。

4 小波仿射不變函數與凸殼相結合的目標識別方法

容易看出，式(12)定義的絕對小波仿射不變函數與目標輪廓線的起始掃描點相關，即以目標輪廓線上不同的點為起始點進行掃描得到兩個不同的輪廓線點列，這兩個點列的絕對小波仿射不變函數是不同的。為了在應用中消除這種相關性，本文將凸殼的仿射不變性與絕對小波仿射不變函數相結合進行目標識別。這種方法的基本思想是:首先計算目標輪廓線的凸殼，得到目標輪廓線的凸殼頂點;然后以目標輪廓線的所有凸殼頂點為起始點，為一個目標在模式庫中建立多個模式，此處使用目標輪廓線的絕對小波仿射不變函數式(12)作為目標的模式;在目標識別階段，以待識別目標輪廓線的凸殼的所有頂點作為起始點，計算待識別目標的多個絕對小波仿射不變函數，與模式庫中的模式進行匹配，完成目標的分類與識別。

本文使用下列步驟為每種目標的二值圖像在模式庫中建立模式(算法1):

(1) 對目標的二值圖像B使用邊界跟蹤算法得到B的外圍輪廓線C0={(x0(m)，y0(m))|m=0，1，2，…，M-1}，并將該點列的長度使用線性插值標準化為N，得到輪廓線:

C={(x(n)，y(n))|n=0，1，2，…，N-1}

式中:

x(n)=x0(0)， n=0

x0(M-1)，n=N-1

x0n(M-1)N-1，0

式中:floor(#8226;)表示向下取整函數;y與y0的關系同x與x0的關系。

(2) 計算輪廓線點集C的凸殼頂點，假設有L個凸殼頂點，將這些頂點使用集合表示為{Pi|i=1，2，…，L}。

(3) 以Pi為起始點，按順時針方向和逆時針方向跟蹤輪廓線C，可以得到兩個輪廓線點列，這樣的點列共有2L個，也就是說，每個目標的二值圖像在模式庫中的模式有2L個。

(4) 對步驟(3)得到的各個點列使用式(12)計算它的絕對小波仿射不變函數，作為目標的特征向量存入目標模式庫M中，作為二值圖像模板B的模式。

由上述步驟，可以為每種目標的二值圖像在模式庫中建立2L個模式，由絕對小波仿射不變函數的性質可以保證得到的模式具有平移不變性、旋轉不變性和尺度無關性等仿射不變性，步驟(2)和(3)保證了得到的模式與輪廓線的起始點無關。假設有K種目標的二值圖像，則由上述步驟為這K種目標建立的模式庫可以使用下面的集合表示:

M={Mi，j(t)|i=1，2，…，K;j=1，2，…，iL;

t=0，1，2，…，N-1}(13)

其中:M是二值圖像的N維特征向量的集合;iL表示第i個模板圖像在模式庫中擁有的模式個數;N表示特征向量的維數。

對待識別目標的二值圖像Obj進行識別的方法是:首先使用邊界跟蹤算法得到Obj的輪廓線點列;然后以該輪廓線的所有凸殼頂點為起始點跟蹤Obj的輪廓線，得到目標輪廓線的點列集合;之后使用式(12)計算各個輪廓線點列(假設目標輪廓線的凸殼頂點個數為L)的小波仿射不變函數Il(t)，(l=0，1，2，…，L-1;t=0，1，2，…，N-1)，并按式(14)計算Il(t)與模式庫M中各個模式Mi，j的相關系數:

R[Il(t)，Mi，j(t)]=

∑t(Il(t)Mi，j(t))‖Il(t)‖2‖Mi，j(t)‖2(14)

與Il(t)相關系數最大的模式所對應的類別i*即為檢測到的目標Obj所屬的類別，即:

i*=argimax{R[Il(t)，Mi，j(t)]}(15)

式中:l=0，1，2，…，L-1;i，j，t的取值范圍與式(13)中變量的取值范圍相同。

5 實驗結果

在實驗中，首先使用線性插值法將目標輪廓線的長度標準化為64，即將目標輪廓線使用64個輪廓點表示;然后使用db2小波對目標的輪廓線進行連續小波變換，并使用式(12)計算目標輪廓線的絕對小波仿射不變函數作為目標的模式，兩個不同的小波尺度選為8和16，使用式(14)計算相關系數。

使用下面的圖像進行模擬實驗，圖1中表示20種飛機的二值化圖像模板;圖2是圖1中的10個圖像模板經隨機仿射變換得到的10個待識別目標(測試圖像)的輪廓線;表1所示為10個待識別目標與目標模板圖像的對應關系。

圖1 目標圖像模板

圖2 待識別目標的輪廓線

表1 測試圖像與圖像模板的對應關系

待識別目標12345678910

圖像模板圖像621915518162010

由算法1為圖1中的20種二值化圖像模板建立目標模式庫;再使用算法1計算10個待識別目標輪廓線的模式，并使用式(14)計算各個待識別目標模式與模式庫中各模式的相關系數，得出表2。

表2 與待識別目標相關系數最大的5個模板

待識別目標編號

匹配模板順序

12345

10.987 8(6)0.946 31(3)0.927 83(9)0.909 84(14)0.887 34(4)

20.980 03(2)0.954 92(9)0.928 04(3)0.915 83(14)0.904 31(11)

30.982 4(19)0.977 23(18)0.830 91(1)0.795 21(6)0.746 45(14)

40.993 4(15)0.961 55(16)0.934 94(14)0.925 13(13)0.918 93(4)

50.991 34(5)0.848 06(3)0.847 11(11)0.825 76(14)0.815 91(4)

60.988 54(1)0.944 43(3)0.925 62(6)0.864 05(9)0.855 5(14)

70.989 47(8)0.913 55(10)0.909 66(2)0.826 35(11)0.802 89(14)

80.812(16)0.806 92(4)0.799 41(13)0.782 24(3)0.778 59(6)

90.993 94(20)0.984 8(7)0.88 83(17)0.885 51(12)0.726 61(9)

100.886 19(10)0.882 13(8)0.861 38(2)0.731 09(11)0.721 47(4)

表2為11行6列表，每行第一列是待識別目標輪廓線的編號，后面5列是按相關系數從大到小順序排列的5個相關系數，括號中的數字表示圖像模板的編號。由表2可以看出，對圖2中的10個待識別目標的識別結果完全正確。

6 結 語

本文基于相對小波仿射不變函數構造了絕對小波仿射不變函數，并將絕對小波仿射不變函數與凸殼相結合進行目標識別。該方法首先提取待識別二值圖像的輪廓線，并計算輪廓線的凸殼頂點;然后以每個凸殼頂點為起點掃描目標輪廓線得到不同的點列，計算每個點列的絕對小波仿射不變函數作為目標的模式;使用相關系數最大準則進行目標的識別。實驗結果驗證了本文方法的有效性。

參考文獻

[1]Akhtar J，Javed M Y.Image Compression with Different Types of Wavelets.International Conference on Emerging Technologies[C].2006:133-137.

[2]Tieng Q M，Boles W W.Recognition of 2D Object Contours Using the Wavelet Transform Zero-crossing Representation[J].IEEE Trans.on PAMI，1997，19(8):910-916.

[3]Sun Yankui，Huang Wan.Separable 2D Dyadic Wavelet and its Applications in Contour Detection of Handwriting.International Conference on Wavelet Analysis and Pattern Recognition[C].2007(3):1 316-1 321.

[4]Chen Guangyi，Tien D B.Invariant Fourier Wavelet Descriptor for Pattern Recognition[J].Pattern Recognition，1999，32(7):1 083-1 088.

[5]Kiymik M K，Akin M，Subasi A.Automatic Recognition of Alertness Level by Using Wavelet Transform and Artificial Neural Network[J].Journal of Neuroscience Methods，2004，139(2):231-240.

[6]Khalil M，Bayoumi M.Invariant 2D Object Recognition Using the Wavelet Modulus Maxima[J].Pattern Recognition Letters，2000，21(9):863-872.

[7]Khalil M I，Bayoumi M.A Dyadic Wavelet Affine Invariant Function for 2D Shape Recognition[J].IEEE Trans.on PAMI.2001，23(10):1 152-1 164.

[8]Bala E，Cetin A C.Computationally Efficient Wavelet Affine Invariant Functions for Shape Recognition[J].IEEE Trans.on PAMI.2004，26(8):1 095-1 099.

[9]Ingrid Daubechies.Ten Lectures of Wavelets[M].Society for Industrial and Applied Mathematics，1992.

[10]周培德.計算幾何算法分析與設計[M].北京:清華大學出版社，2000.

Yang Zhengwei，Fernand S Cohen.Image Registration and Object Recognition Using Affine Invariants and Convex Hulls[J].IEEE Trans.on Image Processing，1999，8(7):934-946.