一種圖像特征點匹配算法
——Haar-Gaussian&NICD算法

北京信息科技大學(xué) 自動化學(xué)院，北京 100192

一、引言

隨著社會的發(fā)展，在圖像識別領(lǐng)域小波變換是傅里葉變換之后的另外一個比較有力的工具。原則上講，傳統(tǒng)意義上使用傅里葉分析的地方，都可以用小波分析來替代[1]。就多分辨率分析而言，小波變換的出現(xiàn)使得圖像處理領(lǐng)域又提供了一種新思路，小波框架的產(chǎn)生使得處理數(shù)字信號更加的精準。1989年，為了研究圖像的紋理特征Mallat引入了小波的概念，為后續(xù)的基于小波紋理分析的方法提供了扎實的理論基礎(chǔ)。小波變換是在不同尺度上研究分析圖像文理細節(jié)的一種工具，為更精準的進行圖像紋理分類和分析提供了新的思路，在紋理分析中有廣闊的發(fā)展空間[2]。

圖像的局部特征提取——特征點提取，在實現(xiàn)圖像合成、圖像校正、識別分類、圖像匹配等圖像領(lǐng)域常見問題中是及其重要的一個環(huán)節(jié)，關(guān)于如何在一幅圖像中精準的定位其穩(wěn)定的特征點用于后續(xù)的相關(guān)工作，國內(nèi)外大量的相關(guān)學(xué)者和專家都做了深入的研究工作。

其中有一種較為廣為人知的圖像特征點提取算法稱為Harris角點檢測算法[3]。雖然這種算法對圖像平移、旋轉(zhuǎn)、和噪聲具有較強的魯棒性，但是當(dāng)圖像遭遇到尺幅變換之后其效果會很糟糕，因此從一定程度上來講它的使用會受到限制。隨著圖像技術(shù)的發(fā)展，越來越多的基于強特征點提取匹配的算法被提出，其中包括SIFT算法[4]、Harris-Laplacian算法[5]等。

本文主要討論一種特征點檢測子算法的實現(xiàn)，并與規(guī)范化強對比度描述子（Normalized intensity contrast descriptor，NICD）相結(jié)合，目的是設(shè)計實現(xiàn)一種適用于一定程度的尺度變換、旋轉(zhuǎn)情況下快速提取獨特性強特征點的特征檢測算法。本文的主要思路是將原始圖片進行3層哈爾小波變換，得到不同尺度和不同方向上的圖像信息，利用高斯函數(shù)進行不同尺度的高斯濾波進而產(chǎn)生哈爾小波高斯金字塔塔林，再利用高斯拉普拉斯函數(shù)計算提取相對最穩(wěn)定的圖像強度特性特征點，在通過計算來修正特征點，最后引進NICD描述子對所提特征點進行描述。

二、檢測子的設(shè)計

1、小波理論

小波理論中重要的部分是多分辨率分析即多尺度分析，這也是與我們?nèi)说难劬τ^察物體時的機理高度相似的。因為我們是對圖像進行操作所以在這里我們重點討論二維小波變換。在二維情況下，首先定義一個尺度基函數(shù)和平移基函數(shù)：

其中，上標i—沿列、行、對角方向。

于是，大小為M×N的圖像f(x,y)的離散小波變換是：

其中，j0是其中一個開始的任意尺度，Wφ(j0,m,n)系數(shù)為定義f(x,y)在尺度j0處的近似，WΨ i(j,m,n)系數(shù)對尺度j≥j0增添了水平、鉛垂和斜對角方向的細節(jié)。

因為有j=0,1,2,…,J-1和m=n=0,1,2,…,2j-1，所以通常情況下令j0=0，并且選擇N=M=2J。圖1展示了這一過程，在二維情況下我們得到3組細節(jié)系數(shù)——水平系數(shù)、鉛垂系數(shù)和對角線細節(jié)系數(shù)。

本文中主要應(yīng)用哈爾小波變換，因為它的基波是最古老的且最簡單的正交小波，所以哈爾小波變換是其中最重要的一個環(huán)節(jié)。哈爾變換可以用如下矩陣形式表示：

其中，F(xiàn)—一個N×N的圖像矩陣；

H—一個N×N的哈爾變換矩陣；

T—一個N×N的變換結(jié)果。

因為H的非對特性，所以在這里轉(zhuǎn)置是必須要有的，其包含哈爾基函數(shù)hk(z)。它們定義在連續(xù)閉區(qū)間z∈[0,1]，k=0,1,2,…,N-1 上，其中N=2n。

為了得到矩陣H，本文在這里定義整數(shù)k，即k=2p+q-1，其中0≤p≤n-1。當(dāng)p=0時，q=0或1；當(dāng)p≠0時，1≤q≤2p。

因此，哈爾基函數(shù)為：

N×N哈爾變換矩陣的第i行包含了元素hi(z)，其中：。

2、Haar-Guassian金字塔塔林

早在1962年，Lijima提出來了尺度空間的思想，由于Witkin和Koenderink等人的研究工作，使得尺度空間的思想能夠被計算機領(lǐng)域廣泛使用[3]。尺度空間的主要是思想是：首先定義一個系數(shù)——尺度系數(shù)，引入到圖像信息處理的模型中，由于尺度系數(shù)變化的連續(xù)性，會產(chǎn)生很對的尺度描述序列，然后基于輪廓的描述對這些尺度序列進行特征提取，并將提取到的特征數(shù)據(jù)組合成一種特征向量，進而能夠得到圖像中相應(yīng)的邊緣信息、角點信息以及不同分辨率上的特征信息等。

尺度空間中是滿足視覺不變性的，可以有如下解釋：當(dāng)物體被我們用肉眼觀察時，由于背景光強度的不同，圖像的光亮被視網(wǎng)膜感知的效果以及對比度是截然不同的，因此分析圖像時要求尺度空間算子能夠做到不被圖像灰度和對比度影響，也就是說在一定程度上滿足灰度和對比度不變性。此外，在同一坐標系下，當(dāng)物體和我們的肉眼觀察的發(fā)生相對位置變化時，圖像位置、大小、角度和形狀在我們的肉睛的視網(wǎng)膜上的成像是不同的，所以在進行圖像分析時，圖像的位置信息、大小信息、角度信息以及仿射變換等信息具備的互不干擾性，也就是滿足平移、尺度、歐幾里得不變以及仿射不變性。

本文在這里使用一個變換尺度的高斯函數(shù)G(x,y,σ)與原圖像I(x,y)的卷積和來定義該圖像的尺度空間L(x,y,σ)，即：

其中，m×n為模板大小，(x,y)為像素的位置，σ是正態(tài)分布的標準差，作為尺度空間描述子，σ的值越大，圖像越平滑（模糊），σ的值越小表示圖像被平滑的越少，對應(yīng)的尺度也就越小。這樣在分析圖像時，圖像的全局特征與相對較大尺度的特征圖相對應(yīng)，細節(jié)特征則與相對較小尺度的特征圖相對應(yīng)。

接著本文就要對圖像進行哈爾分解。首先對圖像進行哈爾變換產(chǎn)生多分辨率序列，并以不同分辨率的哈爾特征圖為金字塔底層，為了使尺度體現(xiàn)連續(xù)性，對每一層的一張圖片進行不同參數(shù)的高斯模糊，因為每一種分辨率都有三或四種基礎(chǔ)特征圖，所以多種分辨率的情況下會產(chǎn)生多個金字塔林列，所以在這里引進了金字塔塔林的概念。

2002年，Mikolajczyk在詳細的實驗比較中發(fā)現(xiàn)尺度歸一化的高斯拉普拉斯特征提取函數(shù)的極值更能產(chǎn)生穩(wěn)定的特征圖像[5]。與非常相似的函數(shù)是高斯差分函數(shù)（Difference of Gaussian，簡稱DOG算子）。D(x,y,σ)與的關(guān)系可推導(dǎo)如下：

將微分用差分來代替得到如下：

其中，k-1為常數(shù)，不影響極值點所在地方。

本文使用效率更高的DOG算子來替代拉普拉斯算子進行極值點的檢測，如下：

為了得到高斯差分圖像，計算時將上下兩層圖像的相減，如圖2所示，進而進行極值點的檢測。

3、特征點的定位和修正

特征點的定位是通過同組高斯金字塔內(nèi)各DOG相鄰之間的比較完成的，按SIFT算法的思想將中間點的像素值和周圍26個點作比較，以保證在尺度和二維圖像空間都可以檢測到極值點。如圖3所示。

通過上面步驟檢測到的極值點可大致分為兩種：強特征性極值點和弱特征性極值點，強特征性極值點的提取是本文的主要目的，而弱特征性極值點的存在往往會對后續(xù)的研究工作和應(yīng)用產(chǎn)生誤差。因此本文在引用SIFT特征點修正的基礎(chǔ)上，首先利用哈爾變換的去噪機理對DOG圖像進行處理，然后將DOG數(shù)據(jù)進行歸一化的處理，并設(shè)定合理閾值，最后得到較為整齊的強特征性極值點。

三、特征點描述子選擇

在SIFT描述子中，采用加權(quán)的梯度方向直方圖[6]，維度較高大大地影響了計算效率。隨后，Ke等人提出了PCA-SIFT描述子降維后進行匹配[7]。SURF描述子是在SIFT的基礎(chǔ)上，計算興趣點的尺度相關(guān)鄰域內(nèi)X和Y方向的哈爾小波，并選擇相對鄰域內(nèi)響應(yīng)最大的作為主方向[8]。Huang等人[9]提出了對比上下文直方圖，利用鄰域區(qū)域的像素強度之間的線性關(guān)系進行特征描述，減少局部特征描述的計算時間，但是他僅僅考慮了常量強照度的變化。

本文采用NICD來對本文介紹檢測子檢測到的特征點進行描述，在將局部鄰域內(nèi)的像素強度規(guī)格化后，描述每個子區(qū)域中的像素與中心像素的強度對比關(guān)系[10]，可得到48維或者64維的特征描述向量。

四、實驗結(jié)果與分析

1、實驗過程

本文在特征點檢測試驗中采用重復(fù)率[11]來評價特征點檢測子的魯棒性。首先對原始圖像和變換圖像進行特征點的解算，然后求取特征點重復(fù)的數(shù)量與這兩幅圖像分別提取的特征點的最小值的比值作為重復(fù)率。實際計算中，通過兩幅圖像提取出的特征點不可能完全的對應(yīng)，所以，計算時取圖像位置小于2i（i為特征點所在不同分辨率的級數(shù)，i=0, 1, 2, ……）個像素。此外，實驗中采用64維的NICD描述子并用特征點檢測時的特征點的梯度和偏移量等對描述子向量進行擴展，構(gòu)成73維的描述向量。

2、評估標準

采用計算余弦相似度的方法來對描述子向量進行匹配，匹配結(jié)果用對應(yīng)特征點連線圖來展示。

3、實驗結(jié)果

（1）尺度變換匹配實驗

本文使用的原始圖片為512px×512px，變換后圖片為256px×256px。圖4分別展示了SIFT和本文所用方法的效果。經(jīng)過對比可以看出，本文的算子提取的強特征性特征點的數(shù)量要優(yōu)于SIFT算法，進而可以更好地應(yīng)用于圖像局部特征的匹配，另外特征描述子的維度只有SIFT算子的一半，從匹配速度上來說要優(yōu)于SIFT，從匹配效果上來說和SIFT相當(dāng)。

（2）尺度和旋轉(zhuǎn)變換匹配實驗

在尺度變換的基礎(chǔ)上加上旋轉(zhuǎn)變換，效果如圖5所示。經(jīng)過對比可以看出，首先從特征點的數(shù)量上來講要優(yōu)于SIFT算法，在圖像局部特征匹配方面的實用性更強，速度上由于維數(shù)的降低要優(yōu)于SIFT算法，在這種變換情況下，從匹配效果上來講要略好于SIFT算法。

（3）亮度變換匹配實驗

亮度變換匹配實驗匹配效果如圖6所示。通過對比可以看出，由于NICD描述子的構(gòu)建過程中，去除亮度的相對干擾，對亮度不敏感，所以匹配效果要明顯優(yōu)于SIFT算法。

本文分別在圖像的尺度變換、旋轉(zhuǎn)尺度變換以及亮度變換的情況下進行了特征點的匹配實驗，實驗表明本文所提的方法有效，滿足圖像在以上三種情況變換下所提特征點的強特征性不變，并可以有效的應(yīng)用于圖像的局部特征匹配。

五、總結(jié)

特征點的強特征性在尺度、亮度、旋轉(zhuǎn)等變換下都可以保持不變，繼而成為近年來機器視覺和模式識別的研究熱點。本文的思路是將哈爾小波變換和高斯函數(shù)相結(jié)合，構(gòu)建金字塔塔林的結(jié)構(gòu)作為特征點的提取工具，引入NICD快速描述子將局部鄰域像素規(guī)范化，通過對目標區(qū)域中特征點與周圍像素點之間的規(guī)范化強度差進行計算，并結(jié)合特征點檢測時的特征點的梯度和偏移量等數(shù)據(jù)合并組成73維的描述特征向量。在實驗中分別考慮了尺度、旋轉(zhuǎn)、亮度的變換情況，證明了該算法的有效性。

機器人視覺識別系統(tǒng)都是對局部特征的重要應(yīng)用，在未來的工作中，我們將把這種特征點檢測算法應(yīng)用到機器人視覺物品識別中，驗證它的性能。仿真實驗已經(jīng)證明這種算法的有效性，此外我們還會對該算法進行改進，提出更好的描述子和其搭配用于實時的特征檢測和貨架商品識別。