改進多尺度特征提取的圖像配準算法研究

楊宇光 ，滕義偉

YANG Yuguang1，2,TENG Yiwei1

1.北京工業大學 計算機學院，北京 100124

2.西安電子科技大學 綜合業務網國家重點實驗室，西安 710071

1.School of Computer Science,Beijing University of Technology,Beijing 100124,China

2.The State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China

1 引言

圖像配準是圖像處理領域的一項關鍵技術[1]，它在圖像融合、遙感影像分析、醫學圖像分析以及計算機視覺等應用中發揮著重要的作用。特征提取和匹配是圖像自動配準的兩大難點。利用多尺度采樣理論提取各種特征點具有尺度和仿射不變的特性，為圖像特征提取和匹配提供了良好的途徑。Lowe[2-3]提出了尺度不變特征變換（SIFT）特征點提取算法，被廣泛應用于特征匹配中，具有穩定的旋轉和尺度不變性。Mikolajczyk[4-5]和Schmid[5]提出的Harris-Laplace特征提取算法在位置可重復性、定位精確度、尺度不變性等方面均有較好的性能。

由于一幅圖像的局部結構可能在一定的尺度范圍內被多次檢測到，產生大量的冗余點[6]。這些冗余點在檢測時得到的位置和尺度會有一些差異，降低了圖像的配準精度導致誤匹配產生。為了去除冗余點，本文首先在特征點檢測階段通過對多尺度檢測到的圖像特征點在其鄰域內進行篩選，然后選取最具代表性的唯一特征點作為最終的特征點來表示這一個局部結構。實驗表明，本文改進的算法相較于原來的Harris-Laplace算法檢測到的特征點分布更均勻并且獲得匹配點的數目更穩定。同時，實驗結果表明本文算法具有更高的圖像配準的速度和精度。

2 Harris-Laplace特征檢測及存在的問題

2.1 Harris-Laplace算法

2.1.1 構建尺度空間

尺度空間表示一個平滑圖像集，它是由輸入圖像和可變尺度的高斯核函數進行卷積運算得到的。Lindeberg[7]已經證明高斯核函數是尺度空間的唯一表示。

2.1.2 檢測Harris-Laplace特征點

由于二階矩陣描述一個點在鄰域內的梯度分布，所以它經常用來進行特征點的檢測。歸一化的尺度空間微分表示，如下：

其中，

在公式（2）～（4）中，x，y為圖像中的坐標點，σI，σD分別表示積分尺度和微分尺度，σD=sσI是一個標量。一般來說，積分尺度要比微分尺度大。在本文中，s取0.7。I(x，y)為輸入圖像。通過公式（4），計算每個尺度空間圖像上點的響應值，并將滿足條件的點作為特征點[8]。

α是一個常量，一般取值范圍為0.04～0.06。Threshold為預設閾值，控制提取的特征點數目。

2.2 存在的問題

基于多尺度的特征檢測存在如下問題：一幅圖像中的局部結構可以在一定尺度范圍內檢測到。所以對于同一個局部結構將會檢測到多個特征點，但是這些特征點的在尺度和位置上很小的差別，將在后續匹配時產生誤匹配，同時增加了計算的時間復雜度。

圖1是北京工業大學國際交流中心的圖像，使用Harris-Laplace算子提取圖像的特征點的結果如圖1（a）所示。將圖1（a）中黃色框內圖像放大得到圖1（b）。其中，綠色?表示提取的圖像的特征點，紅色○表示對應特征所在的尺度。從圖1（a），（b）中可以看到，一個綠?同時被多余一個不同半徑圓圈住，即每一個局部結構都會在不止一個尺度上檢測到，這將增加冗余點的數目并增加在特征匹配階段特征點匹配的復雜度。同時，由于同一局部結構的特征點微小的差異將會增大誤匹配的概率。怎么從同一個局部結構所產生的特征點中選取最有代表性的特征點，從而減少冗余點，降低計算復雜度，同時減少圖像配準中的誤匹配，這個問題是本文改進算法討論的重點。

圖1 Harris-Laplace特征點檢測

3 改進的Harris-Laplace特征提取及圖像配準算法

3.1 尺度空間檢測Harris特征點

首先，根據公式（1），通過不同尺度的高斯核函數和輸入圖像作卷積生成尺度空間。然后，利用公式（2）～（5）檢測出每個尺度空間上所有的特征點。

3.2 選擇最優特征點

實驗證明，表示相同局部結構的特征點總是集中在一個特定的尺度范圍內，并且一般來說相鄰尺度的兩個興趣點的距離在1～3個像素內，如圖1（b）所示，即在一定區間內表示相同局部結構的所有特征點在位置和尺度上只有較小的差異。同時，在尺度空間內角點越接近真正的角點，說明該點鄰域的灰度值變化越大，也即是該特征點的角點響應值越強。所以，可以對尺度空間內提取的所有特征點通過統計濾波，求取角點響應值最大的特征點作為最終的候選特征點，實現冗余點的剔除。具體算法如下：

（1）構造選擇模板MASK。構造一個二維矩陣MASK(m，n)，矩陣中每個元素是由點對(response，scale)構成。初始化 MASK(i，j)={0，0}，其中 0≤i＜m，0≤j＜n，m，n為原圖像 I(x，y)的大小。

（2）從高尺度圖像開始提取特征點賦值給對應位置上的MASK點對。由于高斯核函數的尺度越大，經高斯核函數平滑后的圖像紋理變得越稀疏，能夠檢測得到的特征點也越少且分布均勻。所以從高尺度圖像開始對MASK進行賦值，這樣比較容易確定MASK最終選擇值。所以，先提取高尺度圖像中的特征點，并將特征點的響應值 Response(x，y，σ)賦值給對應 MASK(x，y)點對。

（3）提取相鄰尺度圖像上的特征點。從高尺度圖像開始，依次提取相鄰低尺度圖像上的特征點。重復步驟（2），直到所有尺度圖像上的特征點賦值給模板MASK。如果模板相同位置出現不同尺度上檢測到的兩個興趣點，則選擇較大 Response(x,y,σ′)值點賦值給MASK(x，y)。

（4）利用統計濾波器篩選興趣點。由于表示相同局部結構的特征點總是集中在一個特定的尺度范圍內，并且一般來說相鄰尺度的兩個興趣點的距離在1～3個像素內，即在一定區間內表示相同局部結構特征的所有特征點在位置和尺度上只有較小的差異。因此可以利用半徑為3的統計濾波器對模板MASK進行濾波，分別求得每一點處角點響應的最大值Max(x，y)和角點響應次大值 Second(x，y)。如果 Max(x，y)＞Second(x，y)，且滿足 Max(x，y)=MASK(x，y)則記錄下該點坐標。

（5）生成最終的特征點。由步驟（4）計算得到的所有特征點是已經剔除了表示相同局部結構冗余點。它們是圖像局部結構特征的唯一表示。保存這些特征點的尺度、函數響應值，將求得的點作為最終表示局部結構的最優的特征點。

通過對Harris-Laplace算法的改進，在檢測階段剔除大量的冗余點，減少了后續的匹配操作，節省了大量不必要的復雜計算，提高了配準速度。同時，剔除的冗余點減少了對匹配過程的干擾，所以改進的Harris-Laplace算法提高了圖像配準的精度。

3.3 特征描述

為了實現特征準確匹配，每個特征點的描述要盡可能得充分：不同的特征點要具有明顯的差異性，匹配的特征點對要有充分的相似性。Lowe在研究SIFT[2，9-10]算法時，通過實驗證明，128維的SIFT描述子具有很好的旋轉不變性。所以在本文采用SIFT描述子對特征點進行描述。SIFT描述子生成過程如下：

（1）為待配準的特征點分配主方向。在特征點的附近創建方向收集區，收集區域的大小依賴于特征點所在圖像的尺度。尺度越大的圖像中檢測出的特征點，對應的收集區域也越大。根據公式（6）、（7）計算收集區域中每個像素點的梯度大小和方向。在0～2π范圍內，建立n bin的梯度直方圖，則第i bin表示方向在2(i-1)π/n～2i π/n，i=1，2，…，n范圍內的像素。像素的梯度大小加到該像素方向對應的bin上。所得直方圖的最大值位置為主方向所在的相位，將它分配給特征點。如果n過大，使梯度直方圖過于分散，影響峰值的確定；如果n過小，則使得主方向精度過低，不能正確描述主方向。綜合以上兩種情況，本文實驗中n取36。

（2）計算特征點鄰域的種子點。選取特征點為中心的16×16鄰域，將該鄰域平均分成16個大小為4×4的子區域。同步驟（1）在每個子區域中，生成一個8 bin的梯度直方圖。直方圖中每個bin的大小不但與對應像素點的梯度相關，而且還依賴于該像素點到特征點的距離。選取高斯函數G(x，y，σ/2)為加權函數，其中σ為該特征點的尺度值。對每一個區域中的直方圖進行卷積運算，如公式（8）所示。

（3）描述子歸一化。通過步驟（2）計算，每個子區域由一個8維向量來表示。那么一個特征點則由16×8=128維的向量表示。為了使該描述子具有光照不變性，需要再對其進行向量歸一化操作。

3.4 特征點匹配

圖像的特征點匹配是指將不同圖像中的不同點對應于物理空間中的相同點。所以，只要找出了參考圖像特征點與目標圖像特征點間的匹配關系，就能根據特征點的坐標求解圖像變換模型的參數。特征點匹配的原理是檢測不同圖像特征點之間的歐氏距離（Euclidean distance）。一個特征點的最佳匹配點應該是歐氏距離最小的點。SIFT特征點的歐氏距離計算如下：

d(pi)，d(pj)分別表示特征點 pi，pj的不變特征向量。由于有些特征點沒有在參考圖像中檢測出來，或者是根本就不存在于參考圖像中，所以目標圖像中的很多特征點在參考圖像對應的點存在。所以，必須要判斷一個特征點是否有匹配點。更有效的方法是根據公式（10）計算特征點的最小歐式距離點與次最小歐式距離點的距離的比值：其中，d(pi，pj)是最小歐式距離，d(pi，pk)是次最小歐式距離。

如圖2所示，如果比值r大于0.7，意味著不存在最佳匹配點，也就是 pi點在參考圖像中沒有可匹配的特征點存在。此時可認為 pi是無匹配的點，應將其排出特征點集合。所以可以設定匹配閾值為0.7，如果比值r大于0.7，則該點沒有最佳匹配點；否則認為該點的最佳匹配點即為它的最小歐氏距離匹配點。

圖2 特征點歐式距離比值[2]

4 圖像配準實驗結果分析

本文主要從圖像縮放，旋轉，光照方面對基于Harris-Laplace的圖像配準算法和文中提出的基于改進Harris-Laplace的圖像配準算法性能進行了實驗對比。實驗的對比參數包括兩種算法分別檢測到的特征點數目、匹配點數目、圖像配準時間消耗、剔除冗余點數目、匹配效果。

本文實驗所用圖像為北京工業大學國際交流中心大樓，參考圖像為273×377×3大小的jpg格式的圖像，目標圖像為214×222×3大小的jpg格式圖片。工作平臺配置：Lenovo THINKPAD E40，處理器 Intel?CoreTMi5，內存2 GB，32位操作系統，Matlab R2010b。

4.1 圖像縮放配準實驗及分析

由圖 3（a）、（b）可以看出，基于 Harris-Laplace算法的提取的特征點存在大量的同心圓和臨近點。這些同心圓和鄰近點是由于相同的局部特征結構在多個尺度上被檢測到所導致的。基于原始Harris-Laplace算法的特征提取產生了大量的冗余點，尤其對于紋理豐富的圖像產生的冗余點會更多。在圖像配準過程中要對提取的特征點進行特征描述和特征點匹配，檢測中產生的冗余點在后續圖像配準過程中將消耗大量的時間，同時也增加了誤匹配的可能。基于原算法的圖像配準效果如圖3（c）所示，在圖中可以看到有一部分誤匹配的交叉線。與上面的圖3（a）、（b）對比，基于改進Harris-Laplace算法提取的特征點如圖4（a）、（b）所示，消除了同心圓和鄰近點并且特征點分布更均勻。基于改進算法的圖像配準效果如圖4（c）所示，從圖中可以看到匹配點的連線沒有交叉的誤匹配點對。對照圖3和圖4，可以明顯看出在（a）、（b）子圖中圖4比圖3所提取的特征點更均勻；在（c）子圖中，圖4中交叉的藍線也比圖3少，即誤匹配點少。將目標圖像進行不同倍數的縮放后，得到的圖像配準實驗數據如表1所示。

對表1數據進行處理得到圖5。從圖5（a）中的紅色實線和綠色實線可以看到，隨著目標圖像尺寸的變大無論原Harris-Laplace算法檢測到的特征點數目還是改進的Harris-Laplace算法檢測到的特征點數目都在增加。這是由于目標圖像在尺寸放大的過程中經過雙三次插值使得圖像中每個像素間差異更小。這將導致檢測到更多的同心圓點和鄰近點如圖5（a）所示，黑色實線隨圖像尺寸變大也在增加。從圖5（a）中的紅色虛線和綠色虛線可以看到，紅色虛線和綠色虛線非常接近。綠色虛線在除兩端位置外基本呈現一條直線，波動較小；紅色虛線相對綠線有較大的波動。這說明改進的算法對于圖像縮放變換有更好的穩定性。從圖5（b）中的紅色實線和綠色實線可以看出，基于改進算法的圖像配準具有更快的配準速度。這是由于改進的算法雖然在剔除冗余點的過程中消耗一部分時間，但是由于冗余點剔除避免了在特征描述和特征匹配過程中的時間消耗，所以在總體圖像配準過程中時間消耗要明顯少于原來的算法，具有較高的匹配速度。

圖3 縮放：基于Harris-Laplace的特征提取及配準

圖4 縮放：基于改進算法的特征提取及配準

表1 目標圖像縮放后圖像配準實驗數據

圖5 目標圖像縮放變換后兩種算法的性能分析

4.2 光照變化后圖像配準實驗及分析

圖6（b）和圖7（b）是在強光環境下獲取的圖像。對比圖 6（b）和圖7（b）可以發現，利用原 Harris-Laplace算法提取特征的圖6（b）上出現了大量的冗余同心圓點和鄰近點；圖7（b）上的特征點沒有同心圓及鄰近點，并且提取的特征點分布比較均勻。從配準效果上看，基于改進Harris-Laplace算法如圖7（b）較基于原Harris-Laplace算法如圖6（b），由于改進算法圖像配準所匹配的特征點無重合點并且分布均勻，所以可以得到更準確的圖像變換參數。除此之外，基于改進的圖像配準較基于原算法在時間消耗上更少，如表2所示。因此在光照影響條件下與基于原算法的圖像配準相比，基于改進Harris-Laplace算法的圖像配準具有配準精度高、速度快、魯棒性強等優點。

圖6 光照：基于Harris-Laplace的特征提取及配準

圖7 光照：基于改進算法的特征提取及配準

4.3 圖像旋轉配準實驗及分析

從圖 8（b）和圖9（b）中可以看到，由于目標圖像的旋轉在目標圖像的邊緣形成了鋸齒狀的毛邊，在圖像的邊緣處將檢測到大量的角點。對比基于原算法提取特征的圖8（b）和基于改進算法的圖9（b），可以明顯看出圖8（b）中存在大量同心圓和鄰近點并且在邊緣上也存在較多角點，導致形成大量的冗余點；圖9（b）中不但抑制了旋轉圖像中同心圓和鄰近點，同時也抑制了邊緣點的產生。從總體上看，圖9（b）比圖8（b）特征點分布更均勻，可分辨性更強，誤匹配的可能更小。從圖8（c）和圖9（c）兩種算法的配準效果上看，圖8（b）中存在多個鄰近點與多個同心圓點匹配的情況，這將在獲取圖像變換參數產生誤差，從而降低圖像配準的精度；圖9（c）中由于對同心圓點和鄰近點的抑制使得特征點定位更精確。同時由于圖9（c）中匹配點分布均勻，所以可以獲得更精確的圖像變換參數，提高圖像的配準精確度。對目標圖像進行不同角度旋轉后，得到的圖像配準實驗數據如表3所示。

將表3數據進行處理生成圖10。從圖10（a）中可以看到，紅色實線和綠色實線隨著目標圖像旋轉角度的變化有較大的波動。這是由于圖像旋轉出現了不同程度的鋸齒狀毛邊，這直接影響檢測到的特征點數目。從圖10（a）中的紅色虛線和綠色虛線可以看出，雖然Harris-Laplace算法和其改進算法在檢測得到的特征點數目上有較大的差異，但是基于兩種算法匹配的特征點數目相差不大。對比圖10（a）中的綠色虛線和紅色虛線的波動情況，綠色虛線基本呈現一條直線，波動性較紅色虛線非常小。這說明基于改進Harris-Laplace圖像配準算法具有更好的穩定性。同時，圖10（a）中的黑色實線反映了改進算法對同心圓和鄰近特征的點良好抑制功能。從圖10（b）中可以看到，基于原算法的圖像配準所消耗時間和基于改進算法的圖像配準所消耗的時間都隨圖像旋轉角度的變化有較大的波動，但是綠色實線始終在紅色實線下方并保持較大的距離。這說明基于改進Harris-Laplace圖像配準算法相較于原來的算法具有更快的配準速度。

表2 目標圖像不同光照強度下圖像配準實驗數據

圖8 旋轉：基于Harris-Laplace的特征提取及配準

圖9 旋轉：基于改進算法的特征提取及配準

表3 目標圖像旋轉后圖像配準實驗數據

圖10 目標圖像旋轉變換后兩種算法的性能分析

5 結束語

本文提出的改進算法主要解決了圖像中的局部結構合理表示的問題，并在檢測階段剔除冗余特征點，提高圖像的配準速度、穩定性。由于一幅圖像的局部結構利用Harris-Laplace在多尺度上進行特征檢測時，這個局部結構可能在一定的尺度范圍內被檢測到。但是表示相同局部結構多個特征點在位置或尺度會有一些差異，這些產生的冗余點將在特征匹配時導致誤匹配。本文通過對檢測到的候選特征點在其鄰域內與其他候選特征點的響應值比較，選取最大響應值的點來表示這個局部結構。通過這種改進，剔除了表示同一局部結構的其他冗余點。改進算法從圖像縮放變換、光照變化、旋轉變換三個方面和基于原來算法的圖像配準進行了對比。從得到的實驗數據可以看到，改進的Harris-Laplace算法不僅延續了原始Harris-Laplace算法固有的旋轉不變性、尺度不變性和特征點分布均勻等諸多優點，而且在圖像發生縮放變換、光照變化和旋轉變換后仍能檢測到比原算法更穩定的特征點。同時，本文采用SIFT描述子對檢測到的特征點進行描述。這使得生成的描述子具有良好的獨特性，從而提高了特征點匹配準確性。大量的實驗結果表明，基于改進Harris-Laplace特征提取的圖像配準算法相較于未改進算法不僅具有更好的旋轉、光照和尺度不變性，還能較穩定獲取匹配點。同時由于本文算法在特征檢測減少了冗余點數目，避免了對冗余點的特征描述和匹配，減少了計算的復雜度，提高了圖像配準的匹配速度和匹配精度。

[1]李偉生，王衛星，羅代建.用Harris-Laplace特征進行遙感圖像配準[J].四川大學學報：工程科學版，2011，43（4）：89-95.

[2]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[3]Lowe D G.Object recognition from local scale-invariant feature[C]//International Conference on Computer Vision，Corfu，Greece，1999：1150-1157.

[4]Mikolajczyk K.Detection of local features invariant to affine transformations[D].France：Institut National Polytechnique de Grenoble，2002.

[5]Mikolajczyk K，Schmid C.An affine invariant interest pointdetector[C]//European Conference on Computer Vision（ECCV），2002：128-142.

[6]Zhang Jieyu，Chen Qiang.A highly repeatable feature detector：Harris-Laplace[J].Multimed Tools Appl，2011，52（1）：175-186.

[7]Lindeberg T.Scale-space theory：a basic tool for analysing structures at different scales[J].Journal of Applied Statistics，1994，21（2）：224-270.

[8]Harris C，Stephens M.A combined corner and edge detector[C]//Fourth Alvey Vision Conference，1988：147-151.

[9]Brown M，Lowe D.Recognising panoramas[C]//Proceedings of the 9th International Conference on Computer Vision，2003：1218-1227.

[10]Gon?alves H，Corte-Real L，Gon?alves J A.Automatic image registration through image segmentation and SIFT[J].IEEE Transactions on Geoscience and Remote Sensing，2011，49（7）：2589-2600.