結合Harris與SIFT算子的圖像快速配準算法

（1.中國科學院航空光學成像與測量重點實驗室，吉林 長春 130033；2.中國科學院長春光學精密機械與物理研究所，吉林 長春 130033）

（1.中國科學院航空光學成像與測量重點實驗室，吉林 長春 130033；2.中國科學院長春光學精密機械與物理研究所，吉林 長春 130033）

本文提出了一種結合Harris與SIFT算子的快速圖像配準方法。首先，對Harris算法進行兩方面的改進：一是構建高斯尺度空間，提取具有尺度不變性的角點特征；二是采用Forsnter算子對提取的角點精定位，提高配準精度。然后，利用SIFT算子的特征描述方法描述提取到的特征點，通過隨機kd樹算法對兩幅影像的特征點進行匹配。最后采用RANSAC算法對匹配點對進行提純，并通過最小二乘法估計兩幅影像間的空間變換單應矩陣，完成圖像配準。實驗結果表明：本文方法在基本保持配準精度的同時，在配準過程的時間消耗上比標準SIFT算法減少了64％。

圖像配準；多尺度Harris算子；SIFT；RANSAC

1 引言

基于特征的配準方法的首要任務是進行特征點檢測及匹配。SIFT是目前公認的最為魯棒的特征匹配算子，它是由Lowe［1］在總結了現有基于不變量技術特征提取方法基礎上提出的一種基于尺度空間的局部特征描述算子。SIFT具有尺度不變性、旋轉不變性及光照不變性等諸多優點，但其存在一個巨大缺陷——運算復雜，處理速度慢，難以處理大幅面影像或進行實時應用［2］。在其它的特征檢測算子（如Maravec算子、Harris算子、Susan算子等）中，Harris角點檢測算法計算簡單、穩定且不受光照、旋轉、噪聲等影響，具有最好的檢測效果［3-5］。但是Harris算子不具有尺度不變性，而且在角點定位方面存在偏差，可能導致匹配不準確，難以精確配準。

本文結合Harris角點檢測和SIFT特征描述的優點，采用多尺度Harris算子檢測圖像角點特征，并利用Forstner算子思想對角點精定位，然后使用SIFT特征描述方法進行特征描述和匹配；最后利用獲得的匹配點對采用最小二乘法計算圖像變換參數，完成圖像配準。

2 改進的Harris角點檢測算法

Harris角點檢測算法是由Chris Harris和Mike Stephens提出的一種基于信號的點特征提取算法。該算法利用Taylor級數展開法擴展了Moravec算法的思路，計算窗口沿任意方向移動后的灰度變化趨勢，進而利用數學解析式檢測出角點［6］。目前針對Harris的改進算法有很多，大部分集中在多尺度與精定位兩方面。

2.1 快速多尺度Harris角點檢測

本文引入高斯尺度空間思想以解決Harris算法不具有尺度不變性的缺點，提取具有尺度信息的Harris角點信息。

陳小華：基本上這個行業里大部分創業者都認識，往往他們做不下去的都會來找我們溝通，姚勁波（58集團CEO）還經常感嘆悲劇一再重演。很多創業者會和我們說，你再給我一個億我就能干到一百億，因為我這個模式實在太好了。但我們在這個時候往往有一種無力感，這個教訓只有自己走過才能算教訓，別人提醒，你還會覺得是不是別人看我收入這么多眼紅？這種案例很多，我們會建議一些公司在現金為零的時候停止，出售企業或者放緩節奏，活下來就好。但是這些企業往往會進行最后一搏，就是去讓用戶充值，等到了不得不去找投資人救市的時候，這些公司就不僅是一個價值為零的公司，而是一個負數，一個非常大的坑，沒有投資人會愿意進來。

高斯尺度空間是采用不同尺度的高斯卷積核對圖像進行卷積得到的［7］，如圖1所示。因此，一幅圖像的高斯尺度空間可以表示為：

圖1 高斯尺度空間Fig.1 Gaussian scale-space

運用高斯尺度空間的概念，預先定義一組尺度：{σ1，…，σi}={σ0，…，kiσ0}，相應地，多尺度Harris算子的二階矩可以改寫為：

經典的Harris角點檢測算法采用的角點響應函數CRF為：

式中，gx、gy分別為x、y方向上的梯度；λ1、λ2是矩陣M的特征值；k為常數項，它的取值通常是憑經驗確定的，范圍在0.04～0.06。但在實際應用中，靠經驗選取k值往往會使結果存在偏差，影響后續的配準拼接效果。因此，為了避免k值的選取，引入新的角點響應函數［8］，考慮到多尺度特征，其表示如下：

式中，ε為一極小量（可取ε=10—6），以防止分母為零時出現異常。

多尺度Harris算法需要在多個尺度上檢測角點，計算量比傳統算法大大增加，因此本文參考王葳等人［9］提出的8鄰域相似像素數目分析法，在圖像進行梯度運算之前先剔除部分非角點；如圖2所示，對于目標像素點I（x，y），通過計算與8鄰域范圍內像素點I（x+j，y+i）灰度差的絕對值，并與設定的閾值（記為T）相比較來確定該點是否可能為角點。以函數Num（x，y）表示鄰域相似點數目的公式表達如下：

式中：

當Num（x，y）在［2，6］時，該點可能為角點，將進一步計算其角點響應函數以確定是否為角點。

圖2 8鄰域相似像素分析Fig.2 Similarity operation within 8 neighborhood pixels

2.2 Harris角點精定位

傳統Harris算法獲得的均是整數級像素坐標，而且使用CRF局部非極大值抑制法忽略了周圍可能存在相似角點簇的影響，使得角點檢測易受噪聲影響，導致角點定位存在偏差［10］。本文借鑒Forstner算子思想對Harris角點進行精定位。

Forstner算子是攝影測量中經典的興趣點定位算子，其特點是精度高、速度快。基本思想是：首先獲得候選角點，然后以該點為中心建立最佳窗口，對最佳窗口內通過每個像素的邊緣直線（垂直于梯度方向）進行加權中心化，得到角點的精確坐標［11］。

利用Harris算子提出的角點作為Forstner算子的最佳窗口中心點，在窗口內進行加權中心化精確定位角點坐標的具體計算原理如下：

最佳窗口內任一像素（x，y）的邊緣直線l的方程可以表示為：

式中，ρ為原點（最佳窗口的左上角像素）到直線l的距離，θ為梯度角，tanθ=gy/gx，gy、gx為該點的robert梯度。設角點坐標為（x0，y0），v是點（x，y）到直線l的垂直距離，在（x，y）處的誤差方程為：

式（8）的含義是：將原點到邊緣直線的距離視為觀測值，而邊緣直線的方向保持不變，權w（x，y）是梯度模的平方，因此，權的實質即是該邊緣尺度。對式（8）法化，得到法方程：

對式（9）求解，即可得到精確角點坐標（x0，y0）。

3 圖像配準

3.1 特征描述與匹配

為了獲得穩定準確的匹配效果，本文借鑒SIFT方法對提取的角點進行特征描述與匹配。SIFT特征描述方法分為四步：構建尺度空間檢測極值；關鍵點精確定位；確定關鍵點主方向；生成關鍵點描述向量。本文中，角點檢測與精定位已由其它方法完成，因此只需確定角點的主方向并生成描述子即可，具體過程請參考文獻［1，12-14］。

完成特征描述之后，就要進行特征點匹配，即找出兩幅影像特征點之間的對應關系。針對SIFT描述字的高維特點，本文采用Silpa-Anan［15］等人提出的隨機kd樹算法進行特征點搜索。

3.2 圖像配準

圖像配準是將一幅圖像作為參考，對另一幅圖像進行幾何變換，使圖像之間的重疊區在空間上對準。幾何變換的實質是確定圖像間的對應關系模型，因此，一旦確定了圖像間的關系模型，那么圖像配準即轉化為確定圖像之間對應關系模型的參數過程。目前常用的關系模型主要有剛性變換模型、仿射變換模型、投影變換模型等。

針對目前的應用需求，圖像間一般存在旋轉、平移、縮放變換，因此采用具有8參數的投影變換模型基本上可以滿足需求。圖像間的投影變換可用矩陣表示如下：

式中：（x1，y1，1）、（x2，y2，1）分別為參考圖像和待變換圖像對應特征點的齊次坐標，（h0，…，h7）為間接投影變換參數。

式（10）有8個未知參數，至少需要4對特征點對建立方程組解求變換參數。為了獲得準確的變換參數，本文首先采用RANSAC算法［16］對匹配點對進行提純，去除誤匹配點；然后建立誤差方程，利用最小二乘法解求變換參數［17］。

4 實驗及分析

為了驗證本文算法的配準效果以及速度上的優勢，選取幾種不同平臺的圖片進行配準實驗。實驗中，仿真平臺硬件環境為：Intel（R）Core（TM）i5-3337U CPU，1.8GHz，4G內存的PC機；軟件開發工具為Window 8 64位操作系統，VS2010編程環境。實驗所用的圖像均為實拍影像。圖3中（a）、（b）為手持單反相機拍攝的市區影像，大小為2 464pixel×1 632pixel，（c）、（d）為城郊地區的航空影像，大小為1 024pixel×720pixel，（e）、（f）為QuickBird拍攝的不同時期的某市郊區影像，大小為510pixel×472pixel。

圖3 3組測試圖片Fig.3 Three groups of testing images

首先，通過實驗對比以證明本文方法在特征點檢測時間上相較于SIFT的優勢。分別采用本文提出的Harris-SIFT算法以及標準SIFT算法與SURF算法對圖3中的三組圖像進行特征點檢測比較實驗，3種方法的時間統計結果見表1。結果表明，采用Harris算法進行特征檢測確實具有明顯的時間優勢：在圖3的三組測試圖像中，Harris特征檢測時間比標準SIFT至少減少了42％，最多減少量達到了79％，其特征提取速度基本達到了SURF算法的水平。這是因為多尺度Harris不需要構造太復雜的尺度空間，所需計算的像素量大大減少，節省了相當一部分計算時間。另外，通過比較本文方法與標準SIFT算法所提特征點在圖像中的分布（見圖4）可以看出，采用本文方法所獲得的特征點數量雖然少，但在圖像中分布均勻，并不過密，這也節省了后續匹配過程的時間消耗。

表1 分別用本文方法以及SIFT、SURF進行特征點檢測的時間統計Tab.1 Statistics of cost time for feature points detection using SIFT，SURF and the proposed method

圖4 特征點分布比較Fig.4 Comparison of feature points distribution

然后，通過實驗證明在保證配準正確率的前提下，本文提出的多尺度Harris-Sift算法相對于標準SIFT在整體配準速度上的提高。利用2種方法對圖3中的3組測試圖象進行特征點匹配的正確率與時間統計對比見表2、表3、表4。

表2 本文方法特征點匹配的正確率和時間統計Tab.2 Statistics of accuracy and cost time of feature points matching using the proposed method

表5 使用不同方法對圖3（c）和圖3（d）進行配準的精度對比Tab.5 Comparison of registration accuracy for Fig.3（c）and Fig.3（d）using different methods

最后，統計所有匹配點對變換后坐標與參考坐標間的均方根誤差RMSE以定量的評價配準精度，公式表示如式（11）［18］。

式中，pi和q是匹配點對變換前后的坐標，k為最終匹配點對個數。

圖5 圖3（c）和圖3（d）匹配結果及配準結果Fig.5 Results of（a）feature matching and（b）registration for Fig.3（c）and Fig.3（d）

圖5是特征匹配和圖像配準結果，表5為使用不同方法對圖3（c）和圖3（d）進行配準的精度對比，在保證配準正確率的前提下，本文提出的改進Harris-SIFT算法比標準SIFT算法在整體配準過程的時間消耗上減少了64％。

5 結論

本文針對SIFT算法匹配速度慢的問題，提出了改進Harris算法與SIFT算子相結合的快速圖像配準方法。該方法以Harris角點檢測代替SIFT算法的極值檢測部分，同時為了保證特征點的尺度不變性，對Harris進行了改進。首先建立高斯尺度空間，檢測具有尺度信息的Harris角點，，然后利用攝影測量學中的Forstner算子思想對角點進行精定位，最后采用SIFT描述符對角點進行描述，利用RANSAC法以及隨機K-D樹算法完成特征點匹配。實驗表明，該算法比標準SIFT算法在整體配準過程的時間消耗上減少了64％，是一種快速魯棒的圖像配準算法。

［1］LOWE D.Distinctive image features from scale-invariant keypoints［J］.International J.Computer Vision，2004，60（2）：91-110.

［2］賈平，徐寧，張葉.基于局部特征提取的目標自動識別［J］.光學 精密工程，2013，21（7）：1898-1905.

JIA P，XU N，ZHANG Y.Automatic target recognition based on local feature extraction［J］.Opt.Precision Eng.，2013，21（7）：1898-1905.（in Chinese）

［3］CORDELIA S，ROGER M，CHRISTIAN B.Evaluation of interest point detectors［J］.International J.Computer Vision，2000，37（2）：151-272.

［4］劉志文，劉定生，劉鵬.應用尺度不變特征變換的多源遙感影像特征點匹配［J］.光學 精密工程，2013，21（8）：2146-2153.

LIU Z W，LIU D S，LIU P.SIFT feature matching algorithm of multi-source remote image［J］.Opt.Precision Eng.，2013，21（8）：2146-2153.（in Chinese）

［5］余先川，呂中華，胡丹.遙感圖像配準技術綜述［J］.光學 精密工程，2013，21（11）：2960-2972.

YU X CH，LV ZH H，HU D.Review of remote sensing image registration techniques［J］.Opt.Precision Eng.，2013，21（11）：2960-2972.（in Chinese）

［6］CHRIS H，MIKE S.A combined corner and edge detector［A］.In Proceedings of the 4th Alvey Vision conference［C］，Manchester.United Kingdom：the University of Sheffield Printing Unit，1988.

［7］王國棟，徐潔，潘振寬，等.基于歸一化超拉普拉斯先驗項的運動模糊圖像盲復原［J］.光學 精密工程，2013，21（5）：1340-1348.

WANG G D，XU J，PAN ZH K，et al..Blind image restoration based on normalized hyper laplacian prior term［J］.Opt.Precision Eng.，2013，21（5）：1340-1348.（in Chinese）

［8］ROCKETT P I.Performance assessment of feature detection algorithms a methodology and case study on corner detectors［J］.IEEE Transactions on Image Processing，2003，12（12）：1668-1676.

［9］王葳.一種改進的Harris角點提取算法［J］.光學 精密工程，2008，16（10）：1995-2001.

WANG W.An improved algorithm for Harris corner detection［J］.Opt.Precision Eng.，2008，16（10）：1995-2001.（in Chinese）

［10］何海清，黃聲享.改進的Harris亞像素角點快速定位［J］.中國圖象圖形學報，2012，17（7）：853-857.

HE H Q，HUANG SH X.Improved algorithm for Harris rapid sub-pixel corners detection［J］.J.Image and Graphics，2012，17（7）：853-857.（in Chinese）

［11］FORSTNER W，GULCH E.A fast operator for detection and precise location of distinct points，corners and centres of circulat features［C］.Proceeding of the ISPRS，In Proceeding of Intercommission Workshop on Fast Processing of Photogrammetric Data，Interlaken Switzerland，1987：281-305.

［12］程德志，李言俊，余瑞星.基于改進SIFT算法的圖像匹配方法［J］.計算機仿真，2011，28（7）：285-289.

CHENG D ZH，LI Y J，YU R X.Image matching method Based on Improved SIFT algorithm［J］.Computer Simulation，2011，28（7）：285-289.（in Chinese）

［13］劉立，彭復員，趙坤，等.采用簡化SIFT算法實現快速圖像匹配［J］.紅外與激光工程，2008，37（1）：181-184.

LIU L，PENG F Y，ZHAO K，et al..Simplified SIFT algorithm for fast image matching［J］.Infrared and Laser Engineering，2008，37（1）：181-184.（in Chinese）

［14］劉小軍，楊杰，孫堅偉，等.基于SIFT的圖像配準方法［J］.紅外與激光工程，2008，37（1）：156-160.

LIU X J，YANG J，SUN J W，et al..Image registration approach based on SIFT［J］.Infrared and Laser Engineering，2008，37（1）：156-160.（in Chinese）

［15］SILPA-ANAN C，HARTLEY R.Optimised KD-trees for fast image descriptor matching［C］.In Computer Vision and Pattern Recognition，2008（CVPR 2008），23-28 June 2008，Anchorage，AK，2008：1-8.

［16］FISCHLER M A，BOLLES R C.Random sample consensus：a paradigm for model fitting with applications to image analysis and automated cartography［J］.Commun.ACM，1981，24（6）：381-395.

［17］趙立榮，朱瑋，曹永剛，等.改進的加速魯棒特征算法在特征匹配中的應用［J］.光學 精密工程，2013，21（12）：3263-3271.

ZHAO L R，ZHU W，CAO Y G，et al..Application of improved SURF algorithm to feature matching［J］.Opt.Precision Eng.，2013，21（12）：3263-3271.（in Chinese）

［18］丁南南，劉艷瀅，張葉，等.基于SURF-DAISY算法和隨機kd樹的快速圖像配準［J］.光電子·激光，2012，2（7）：1395-1402.

DING N N，LIU Y Y，ZHANG Y，et al..Fast Image registration based on SURF-DAISY algorithm and randomized kd trees［J］.J.Optoelectronics·Laser，2012，2（7）：1395-1402.（in Chinese）

許佳佳（1986—），男，河南信陽人，碩士，助理研究員，2012年于武漢大學獲得碩士學位，主要從航空圖像拼接方面的研究。E-mail：xujia_whu@163.com

結合Harris與SIFT算子的圖像快速配準算法

許佳佳1，2

Fast image registration method based on Harris and SIFT algorithm

XU Jia-jia1，2
（Key Laboratory of Airborne Optical Imaging and Measurement，hinese Academy of Science，Changchun 130033，China； 2.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Science，Changchun 130033，China）
*Corresponding author，E-mail：xujia_whu@163.com

A new method for fast image registration based on improved Harris-Sift algorithm is proposed.Firstly，classic Harris algorithm is improved by building Gaussian scale space to extract scale invariant Harris corners and they are refined to sub-pixel corners using Forsnter algorithm.Then the SIFT descriptor is utilized to characterize those feature points and the matching procedure is carried out via randomized kd trees.At last，RANSAC is used to remove wrong matches and the optimal transform parameters are estimated using the least square method to accomplish the image registration process.The experimental results demonstrate that compared with the classic SIFT algorithm the proposed method decreases the cost time of the registration procedure mostly by 64％while almost keeping the same performance.

image registration；multiple scale Harris operator；SIFT；RANSAC

吉林省重大科技攻關資助項目（No.11ZDGG001）

2095-1531（2015）04-0574-08

TP391 文獻標識碼：A doi：10.3788/CO.20150804.0574

2015-02-18；

2015-03-22