吳金津，王鵬程，龍永新，廖飛

（湖南工業(yè)大學計算機與通信學院，湖南株洲412007）

基于FAST角點檢測的圖像配準算法

吳金津，王鵬程，龍永新，廖飛

（湖南工業(yè)大學計算機與通信學院，湖南株洲412007）

提出了一種具有類SIFT描述特征的FAST角點檢測的圖像配準算法。先利用FAST對圖像進行特征點提?。蝗缓?，采用圓環(huán)結(jié)構(gòu)算子對提取出的特征點進行類SIFT的特征描述；最后，通過K-D算法將提取出來的特征點進行粗匹配，并使用視差梯度進行預篩選，使用RANSAC算法提純，從而實現(xiàn)特征點匹配。試驗結(jié)果表明，與SIFT算法和改進的SIFT算法相比，本算法減少了誤匹配的數(shù)目，提高了匹配的精確性和穩(wěn)定性。

FAST角點；K-D算法；RANSAC算法

0 引言

圖像拼接主要包括圖像配準與融合，其中最關鍵的是圖像配準。目前圖像配準的方法有很多，常見的是基于特征提取的圖像配準方法[1]。角點是圖像中一個重要的局部特征。在圖像的各種特征中，角點具有旋轉(zhuǎn)不變性和不隨光照條件變化而變化的特點，還能減少參與計算的數(shù)據(jù)量的同時，又不損失圖像的重要灰度信息。因此， 角點特征能用于圖像匹配、目標跟蹤以及運動估計、目標描述和識別等領域。

E. Rosten和T. Drummond提出了一種既簡單又快速的FAST角點探測算法[2]，對待匹配的2幅圖像進行FAST角點的提取。該算法不僅能降低特征點檢測的時間，還可迅速地排除大量的非特征點。2004年David G. Lowe提出的尺度不變特征變換（scale invari-ant feature transform，SIFT）算法[3]具有尺度旋轉(zhuǎn)、亮度變化、縮放的不變性，且SIFT角點能適應圖像的尺度變化，但其不足在于對特征點的要求過于苛刻，在信息較少的圖像中，特征點的數(shù)量較少，參數(shù)擬合的誤差非常大。張春美等人[4]提出改進的SIFT算法，用基于同心圓形窗口的64維向量代替?zhèn)鹘y(tǒng)SIFT算法的128維。該算法的思想是通過增強特征描述符本身的抗旋轉(zhuǎn)能力和減少特征描述符的維數(shù)來降低計算的復雜度，加快了匹配速度。2012年，芮挺等人[5]改進SIFT對特征點的描述方法，用8個同心圓，在每個圓形的區(qū)域內(nèi)選取10個方向，生成70維向量代替原始SIFT算法中的128維。

針對傳統(tǒng)的SIFT特征匹配算法將時間耗費在特征點檢測以及特征點描述上的缺點，本文提出了具有類SIFT描述特征的FAST角點檢測的圖像配準算法。特征點描述階段，利用圓環(huán)算子進行特征點的描述，由于圓具有旋轉(zhuǎn)性不變性，增強了特征描述符的抗旋轉(zhuǎn)能力，降低了其維數(shù)，最終降低了計算復雜度；特征點匹配階段，先利用K-D樹進行粗匹配，再用視差梯度進行精確配準，消除了大量的誤匹配，最后使用RANSAC提純[6]。本文采用具有類SIFT 描述方式的FAST角點檢測算法進行圖像配準，融合了FAST與SIFT算法各自的優(yōu)點，試驗證明了本算法具有良好的配準效果。

1 算法介紹

圖像匹配的核心問題是將同一目標在不同時間、不同分辨率、不同光照、不同位置情況下所成的像相對應[7]。傳統(tǒng)的匹配算法往往首先直接提取角點或邊緣，對環(huán)境的適應能力較差。針對以上問題，本文提出了一種魯棒性強，能適應不同光照、不同位置等情況的圖像配準方法，即基于FAST角點檢測的圖像配準方法。

1.1 特征提取

圖像配準包括特征提取、特征匹配、轉(zhuǎn)換模型參數(shù)估計、圖像重采樣4個步驟。其中，特征提取是圖像配準中最基礎的一個環(huán)節(jié)。圖像的特征點是指那些十分突出并且不會受光照條件的改變而消失的點，比如角點、邊緣點、暗區(qū)域的亮點以及亮區(qū)域的暗點[8]。FAST角點檢測算法不僅簡單，而且速度快。該算法是指在圖像中選定一個像素點，并以此像素點為中心構(gòu)建一個圓形區(qū)域，將中心像素點的灰度值與圓周中每個像素點的灰度值進行比較，若有足夠多的灰度差值的絕對值小于閾值，則可認為此中心像素點是角點。圖1是以像素點p為中心的圓形區(qū)域的模板情況，圓形區(qū)域是一個以3像素為半徑的離散化區(qū)域。

圖1 圓形模板示意圖Fig.1Schematic diagram of circular template

首先定義一個角點響應函數(shù)來判斷像素點是否為角點，角點響應函數(shù)（corner response function，CRF）[6]為

式中：circle(p)為以p為中心的圓周上的點集合；

I(x)為圓周上任意一點的圖像灰度值；

I(p)為中心像素點p（候選點）的圖像灰度值；

像素點p是否為角點取決于圓周上的16個像素點滿足式（1）的像素點個數(shù)N，如果N大于給定的一個閾值，就可以確定該候選點為角點。通常FAST角點閾值設置為12。

本文對傳統(tǒng)FAST算法進行優(yōu)化。該算法可以迅速排除大量的非特征點，其具體步驟如下：

Step1選擇圖像上的任意一點p，并以此為中心構(gòu)建一個半徑為3的圓形區(qū)域，將圓周上的像素點按順時針順序依次編號1～16。

Step2分別計算中心像素點p與圓周上的像素1和像素9的圖像灰度差值。若它們的絕對值都大于閾值d，則p為非特征點；若它們的絕對值至少有一個小于閾值d，則執(zhí)行Step3。

Step3分別計算中心像素點p與圓周上的像素3和像素11的圖像灰度差值。若它們的絕對值至少有一個大于閾值d，則p為非特征點；若它們的絕對值都小于閾值d，則像素點p為候選特征點，執(zhí)行Step4。

Step4分別計算中心像素點p與圓周上其余的12個像素點的圖像灰度差值。若至少有4個像素點不滿足公式（1），則像素點p為非特征點；若至少有8個像素點滿足公式（1），則像素點p為特征點。經(jīng)過優(yōu)化之后，該算法只需要平均檢測候選特征點周圍的8個點就能判斷是否為角點。

Step5判斷圖像的其他像素點是否為角點，重復Step1～Step4。

該算法可以快速地排除整幅圖像中的很多像素點，提高了特征點檢測的時間。

1.2 類SIFT特征點描述

對檢測到的FAST角點采用圓環(huán)結(jié)構(gòu)算子進行類SIFT特征描述。為了保證特征向量的旋轉(zhuǎn)不變性，傳統(tǒng)的SIFT算法會對SIFT特征描述進行主方向的分配，而本算法采用圓環(huán)結(jié)構(gòu)算子進行類SIFT特征描述，因此其不需要進行主方向的分配。由于圓本身具有旋轉(zhuǎn)不變性，因此，在圖像旋轉(zhuǎn)之后，特征點周圍的部分都不會發(fā)生任何改變。

SIFT特征描述符是一種以特征點周圍像素的方向信息和梯度為特征的描述符。具有類SIFT描述特征的算法對描述符的復雜度、維數(shù)和抗旋轉(zhuǎn)能力進行了改進，以特征點為中心，采用圓環(huán)算子對特征點進行描述。對于圖像在每一尺度空間下的像素點(x, y)，其方向信息H和梯度M如式（2）～（3）所示。

構(gòu)建特征點描述的具體步驟如下：

Step1以特征點為中心、半徑為1，生成第1個圓形區(qū)域，半徑依次增大1，總共生成8個同心圓，如圖2所示。

圖2 關鍵點鄰域梯度信息生成特征向量的過程Fig.2The process of the key point neighborhood gradient information to generate a feature vector

Stpe2利用式（2）和（3）計算每個圓環(huán)內(nèi)各個像素10 個方向的方向信息和梯度模。

Step3分別統(tǒng)計第1個圓環(huán)和第2個圓環(huán)區(qū)域內(nèi)10 個方向的梯度累加值，按角度排序后作為第 1 到第 10 個元素；然后在第2個圓環(huán)和第3個圓環(huán)區(qū)域內(nèi)統(tǒng)計 10 個方向的梯度累加值，按角度排序后作為第 11 到第 20 個元素。在第3個圓環(huán)和第4個圓環(huán)區(qū)域內(nèi)統(tǒng)計 10 個方向的梯度累加值，按角度排序后作為第 21 到第 30 個元素。依次下去直到在第7個圓環(huán)和第8個圓環(huán)區(qū)域內(nèi)統(tǒng)計 10 個方向的梯度累加值，按角度排序作為第 61 到第 70 個元素，共生成7×10個元素。該一維向量就定義為關鍵點的特征描述符。

Step4將特征描述符向量進行歸一化處理，減少光照變化對特征點的影響。

1.3 特征匹配

由于傳統(tǒng)的RANSAC算法存在效率不高的問題，當需要匹配的兩幅圖像誤匹配點的數(shù)目比較大時，其算法的效率也非常低。為了降低誤匹配的概率和提高RANSAC算法的效率，本文先利用K-D樹粗匹配特征點對，再采用視差梯度初選匹配特征點對，然后使用RANSAC算法對預篩選出的特征點對進行精確提純，進而得到匹配的特征點對。

1.3.1 K-D樹粗匹配特征點對

為了能夠快速地提取匹配特征點，本文采用K維二叉搜索樹（K-dimensional binary search trees， K-D樹）算法[9]獲取匹配點，對狀態(tài)空間中的所有特征描述符向量進行分類整理，為圖像中所有特征點建立了一個索引樹。定義目標圖像的特征點與待匹配的特征點之間距離最小與次最小之間的比值作為特征點匹配的相似性度量。假定NN表示目標圖像的特征點與待匹配的特征點之間距離最小值，SCN表示2個匹配點之間的距離為次最小值。通過式（4）和式（5）來判斷關鍵點是否為匹配的特征點對，

式中，t為設定的閾值，依據(jù)經(jīng)驗，本文取[0.6, 0.7]，如果d小于等于t，則匹配點對是較好的匹配。

1.3.2 視差梯度預篩選特征點對

根據(jù)視差梯度的定義[10]，用m，n分別表示原始圖像中的2個相鄰的特征點，m′，n′表示目標圖像中相應的匹配特征點。若原始圖像相鄰的特征點與目標圖像的特征點匹配，則視差梯度Gd應小于2；如果視差梯度大于2，則表示原始圖像的特征點和目標圖像的特征點不匹配。視差梯度的公式為

式中：（m′, m）和（n′, n）是對應特征點的圖像坐標向量；

運用RANSAC算法對這些預篩選出的特征點匹配對提純，以得到誤匹配率幾乎為0的特征點匹配對；利用特征點匹配對計算變換矩陣，最后利用LM（levenberg-marquardt）[11]算法進行優(yōu)化，完成特征匹配。

2 算法流程

本文的算法流程如圖3所示。算法主要由FAST角點檢測、類SIFT特征點描述、特征匹配、變換參數(shù)估計和圖像配準幾個部分組成。

圖3 算法流程圖Fig.3Flow chart of the algorithm

算法實現(xiàn)步驟如下：

1）檢測2幅待匹配圖像的FAST角點。在圖像中，選定任意一個像素點并且以此像素點為中心構(gòu)建圓區(qū)域，將中心像素點的灰度值與圓周中任意像素點的灰度值相比較，若圓周中有足夠多的像素點的灰度值大于或者小于中心像素點的灰度值，則被選為角點。

2）特征點的描述。采用圓環(huán)算子對FAST角點進行類SIFT描述，以特征點為中心，統(tǒng)計10個方向的梯度值累加，按照角度排序之后作為第1到第10個元素，總共有8個同心圓，則圓環(huán)之間的區(qū)域有7個，則可生成70維的特征描述符，2幅圖像根據(jù)特征點的數(shù)量生成相應的特征向量。

3）匹配點對提純。采用K-D算法粗略得到圖像匹配對，然后利用視差梯度初次提純，消除大量的誤匹配點對，最后使用RANSAC算法精確提純。

4）根據(jù)匹配結(jié)果，采用LM算法進行優(yōu)化，求出變換參數(shù)，完成圖像配準。

3 試驗結(jié)果及分析

本文試驗圖像大小為320×240像素。試驗平臺的操作系統(tǒng)為WIN 7， CPU為AMD Athlon(tm) Dual-Core CPU T4400 @ 2.20 GHz，內(nèi)存為2 G。編程環(huán)境為Microsoft Visual C++ 6.0和Open CV。本文比較了SIFT算法、改進的SIFT算法和本文算法3種算法的圖像配準效果。

2幅待匹配的原始圖像如圖4所示。

圖4 原始圖像Fig.4Original image

1）分別利用SIFT算法、改進的SIFT算法和本算法對2幅待匹配圖像進行提取特征點，如圖5所示。

由圖5可知，本文算法提取的特征點比改進的SIFT算法的特征點數(shù)量少，從而減少了待匹配特征點的數(shù)目，縮短了特征描述的時間，并且減少了特征匹配的時間。

2）特征匹配。SIFT算法和改進的SIFT算法需建立高斯金字塔，并對高斯差分圖像進行泰勒展開，浪費了大量的時間。而本文算法用FAST對圖像進行角點提取，計算簡單，算法時間效率更高，且生成的特征點顯著。SIFT算法、改進的SIFT算法和本文算法（通過視差梯度進行初次篩選）3種算法的圖像匹配效果如圖6所示。

圖6 特征匹配Fig.6Feature matching

由圖6可知，平行的連線為正確的匹配對，交叉的連線為誤匹配對，SIFT算法得到的誤匹配對較多，改進的SIFT算法得到的誤匹配對明顯減少，而本文算法得到的誤匹配點很少。

將SIFT算法、改進的SIFT算法和本文算法在特征點提取和特征點匹配的性能上進行對比和分析。部分試驗結(jié)果（5幅圖像的結(jié)果）如表1所示。

表1 部分試驗結(jié)果Table 1Some expreimental results

由表1可知，與SIFT算法和改進的SIFT算法相比，本文算法一方面在特征點檢測階段所用的時間有所減少；另一方面，在特征點匹配階段的誤匹配點數(shù)更少，且算法的復雜度也有所降低。

4 結(jié)語

本文利用FAST角點檢測的優(yōu)勢和圓的旋轉(zhuǎn)不變性特點，在特征點提取階段，使用FAST進行特征點提取，在SIFT特征描述符階段，通過圓的旋轉(zhuǎn)不變性來構(gòu)造特征描述符，使其自身具有旋轉(zhuǎn)不變性，降低了算法的復雜度，并減少了匹配時間。算法的不足之處是匹配點對的數(shù)目較少，不能用于實時的圖像拼接。

[1]廖飛，葉瑋瓊，王鵬程，等. 基于SIFT特征匹配的圖像拼接算法[J]. 湖南工業(yè)大學學報，2014，28(2)：71-75. Liao Fei，Ye Weiqiong，Wang Pengcheng，et al. Image Mosaic Algorithm Based on SIFT Feature Matching[J]. Journal of Hunan University of Technology，2014，28(2)：71-75.

[2]燕鵬，安如. 基于FAST改進的快速角點探測算法[J]. 紅外與激光工程，2009，38(6)：1104-1108. Yan Peng，An Ru. Improved Fast Corner Detection Algorithm Based on FAST[J]. Infrared and Laser Engineering，2009，38 (6)：1104-1108.

[3]Deng Rongfeng，Li Xiying. Robust Image Mosaic Algorithm Based on SIFT Feature Matching[J]. Journal of Computer Applications，2009 (S1)：219-221.

[4]張春美，龔志輝，孫雷. 改進SIFT特征在圖像匹配中的應用[J]. 計算機工程與應用，2008，44(2)：95-97. Zhang Chunmei，Gong Zhihui，Sun Lei. Improved SIFT Feature in Image Matching[J]. Computer Engineering and Applications，2008，44 (2) ：95-97.

[5]芮挺，奡張升，周游，等. 具有SIFT描述的Harris角點多源圖像配準[J]. 光電工程，2012，39(8)：26-31. Rui Ting，Zhang Sheng’ao，Zhou You，et al. Registration of Multi-Sensor Image Based on Harris Corner with SIFT Description[J]. Opto-Electronic Engineering，2012，39 (8)：26-31.

[6]Chen Fuxing，Wang Runsheng. Fast RANSAC with Preview Model Parameters Evaluation[J].Journal of Software，2005，16(8)：1431-1437.

[7]周軍太，龍永紅. 一種改進SURF算法的圖像配準[J]. 湖南工業(yè)大學學報，2011，25(2)：95-99. Zhou Juntai，Long Yonghong. Image Matching Based on Improved Speed-Up Robust Features[J]. Journal of Hunan University of Technology，2011，25(2)：95-99.

[8]武岫緣，龍永新，高總總. 基于SIFT-ACO的圖像拼接算法[J]. 湖南工業(yè)大學學報，2014，28(1)：76-80. Wu Xiuyuan，Long Yongxin，Gao Zongzong. Image Mosaic Optimization Algorithm Based on SIFT-ACO[J]. Journal of Hunan University of Technology，2014，28(1)：76-80.

[9]Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM，1975，18(9)：509-517.

[10]馬頌德，張正友. 計算機視覺[M]. 北京：北京科學出版社，1988：82-83. Ma Songde，Zhang Zhengyou. Computer Vision[M]. Beijing：Beijing Science and Technology Press，1988：82-83.

[11]Szeliski R，Shun Heungyeung. Creating Full View Panoramic Image Mosaics and Environment Maps[C]//SIGGRAPH′97 Proceedings of Computer Graphics. Los Angeles：ACM Press，1997：251-258.

（責任編輯：鄧彬）

Image Registration Algorithm Based on Fast Corner Detection

Wu Jinjin，Wang Pengcheng，Long Yongxin，Liao Fei
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

Proposes an image registration algorithm of FAST corner detection with the description of the characteristics of SIFT. First applies FAST to extract image feature points, then uses the ring structure operator for SIFT description of the feature points, finally conducts coarse matching of the points by means of K-D algorithm, and pre screening through disparity gradient and purification with RANSAC algorithm achieves feature points matching. The experimental results show that compared with SIFT algorithm, the improved SIFT algorithm reduces the number of false matches and improves the accuracy and stability of matching.

FAST corner； K-D algorithm； RANSAC algorithm

TP751

A

1673-9833(2014)04-0071-05

10.3969/j.issn.1673-9833.2014.04.016

2014-03-28

國家自然科學基金資助項目（61170102），湖南省教育廳科學研究基金資助項目（12A039），湖南省自然科學基金資助項目（11JJ3070），湖南省科技發(fā)展基金資助項目（2011GK3145）

吳金津（1988-），女，湖南益陽人，湖南工業(yè)大學碩士生，主要研究方向為數(shù)字圖像處理，E-mail ：514959975@qq.com