高　晶，陳　莉，蘭小艷，靳立燕，楊　洲

(西北大學 信息科學與技術(shù)學院，陜西 西安　710127)

?

·信息科學·

基于FAST特征點提取的圖像拼接算法

高晶，陳莉，蘭小艷，靳立燕，楊洲

(西北大學 信息科學與技術(shù)學院，陜西 西安710127)

針對SIFT圖像拼接算法在特征點提取階段，采用基于差分高斯金字塔的方式導致的算法運行時間較長，且易造成特征點漏檢、位置偏移的問題,提出一種基于FAST特征點提取的圖像拼接算法。該算法首先對拼接圖像進行基于FAST算法的特征點提取，取代原有SIFT算法中特征點提取方式,然后對提取特征點進行描述和向量匹配,利用歐氏距離和RANSAC算法實現(xiàn)配準,最后通過加權(quán)平均融合算法完成圖像拼接。仿真實驗表明,該算法加快了特征點的提取速度，提高了定位準確性,更有利于得到灰度整體和諧的拼接圖像。

FAST；特征點；SIFT；圖像拼接

圖像拼接是指通過圖像間的重疊部分找出圖像間對應(yīng)的幾何坐標變換模型,將多幅圖像無縫拼接成一幅具有高分辨率、寬視角的大圖。特征點具有可以較好表征原有圖像且不隨圖像變換而改變的優(yōu)勢，因而基于特征點的圖像拼接算法得到了廣泛應(yīng)用[1]。

常見的基于特征點的圖像拼接算法主要包括：基于SUSAN的圖像拼接算法[2]、基于Harris的圖像拼接算法[3]、基于尺度變換不變特征提取(Scale invariant feature transform,SIFT)算法[4]等。SIFT算法作為經(jīng)典的圖像拼接算法,是目前使用比較廣泛的圖像拼接算法之一,但該算法過于依賴局部像素的梯度方向，且圖像層層金字塔差分構(gòu)造易造成特征點定位偏差的問題,同時耗時較長[5],無法高效完成圖像拼接任務(wù)。對此,很多學者對SIFT算法做了相應(yīng)的改進,文獻[6]將PCA和SIFT算法相結(jié)合來減少運行時間,但當圖像出現(xiàn)尺度變換或旋轉(zhuǎn)變化時,拼接效果不甚理想;文獻[7]提出的SUFT算法，通過使用積分圖像求導的方法加快拼接速度,但該算法抗噪能力較差，且在圖像發(fā)生尺度變換情況下拼接效果并不理想。現(xiàn)有改進算法無法在較好保證圖像拼接效果的前提下加快算法的運行速率[8]。

基于SIFT的圖像拼接算法在特征點提取階段采用高斯金字塔差分取極值的方式，運行時間較長，本文為兼顧拼接效果與效率,采用FAST角點算法對其進行改進。FAST角點提取算法[9]作為SUSAN角點提取算法的改進,保留了SUSAN算法可以檢測出各類特征點的特性[10]，而且快速準確[11]。本文利用FAST算法在特征提取時具有的獨特優(yōu)勢,將該算法用于SIFT算法的特征提取階段，提出了一種新的基于FAST特征點提取的圖像拼接算法。該算法不僅能得到良好的圖像拼接效果,而且能加快圖像拼接速度。

1　SIFT圖像拼接算法

SIFT圖像拼接算法主要分為4個階段:特征點提取、特征點描述、特征點匹配和圖像融合。特征點提取采用基于高斯差分金字塔的方法獲取。

1.1尺度空間極值檢測

一幅二維圖像在不同尺度下的尺度空間表示可以由圖像和高斯核卷積得到

L(x,y,δ)=G(x,y,δ)*I(x,y)。

(1)

其中,(x,y)是圖像點的像素坐標,δ是尺度空間因子,I(x,y)為原圖像，G(x,y,δ)為高斯核函數(shù),

(2)

SIFT算法在實際應(yīng)用中使用差分高斯(DifferenceofGaussian,DoG)算子來建立尺度空間。它是歸一化LoG(LaplacianofGaussian,LoG)算子的近似。DoG定義如下

D(x,y,δ)=

(G(x,y,kδ)-G(x,y,δ))*I(x,y)。

(3)

其中,D(x,y,δ)的構(gòu)造需要建立高斯金字塔與DoG兩個金字塔,而高斯金字塔分為多組,每組間又分為多層。尺度因子因組和層的不同而不同,同時為了獲取DoG極值,需要生成δ·(S+3)的平滑圖像(S代表尺度數(shù))。

1.2尺度空間極值點判定

DoG局部極值的檢測依據(jù)構(gòu)造的金字塔。金字塔每層的每個像素需要和同一尺度的周圍鄰域8個像素和上下相鄰尺度對應(yīng)位置的鄰域9個像素，一共26個像素進行比較,如果當前像素比周圍26個像素都大或者都小時就認為該點屬于極值點。

經(jīng)上述兩步所得極值點即為特征點。由此可見,SIFT圖像拼接算法在特征點提取時,采用分組分層并遍歷的方式提取特征點,造成被描述的特征點數(shù)成倍增多,特征點提取時間增加的同時加大了拼接算法的耗時。同時SIFT方法雖然能夠從尺度空間尋找出具有結(jié)構(gòu)化特性的特征點，但忽略了實際圖像中很多具有視覺意義的特征位置,造成特征點漏檢的情況。對圖像進行高階導數(shù)運算,也會出現(xiàn)噪聲放大、像素位置偏移的問題[12]。因此,本文用FAST特征提取算法取代基于高斯差分金字塔的特征提取方法,實現(xiàn)SIFT圖像拼接算法的改進，提高算法運行效率。

2　基于FAST的圖像拼接算法

2.1FAST特征點檢測算法

FAST 算法是一種對待檢測點鄰域范圍內(nèi)角點分布進行分段檢測的特征檢測方法[13]，其周圍鄰域如圖1所示。

圖1　FAST檢測領(lǐng)域示意圖Fig.1　Schematic diagram of FAST detection field

圖中的每個小方格代表一個像素,中心的m點是待檢測的點,檢測點的鄰域半徑是3個像素值,圓周的像素用1～16順時針標注。以圖中檢測m點是否為特征點為例說明該算法思想。首先將圓周上的1～16個像素點分為如下3類:

(4)

式中Im代表m點的像素值,Im→i代表圓周上第i個像素點,n是一個參數(shù)。得到的結(jié)果Sm→i有3種取值:d代表比檢測點暗,s代表與檢測點相似,b代表比檢測點亮。實際檢測時,為了提高速度,一般先檢測圓周上的第1和9兩個像素點,如果Sm→1=s和Sm→9=s同時發(fā)生,則不把該點選擇為候選點。否則繼續(xù)檢測Sm→5和Sm→13,若以上4個值中有3個值都是d或者b,則該點將作為候選點,繼續(xù)計算其余點的Sm→i值，如果檢測的16個點的Sm→i值中有p個連續(xù)的值為d或者b,則該點被確定為特征點。

其中,參數(shù)n的選擇會影響檢測到的特征點的數(shù)量,通過文獻及已有實驗[14]可知，n取值為30，p取值為9時，可以較好地保留特征點，剔除偽特征點。

圖2是SIFT特征檢測算法和FAST算法針對某一幾何圖形的特征檢測結(jié)果。由圖2可以看到，SIFT算法提取出的特征點位置發(fā)生了一定程度的偏移,同時出現(xiàn)漏檢的情況,這是由于高斯平滑的過程中極值點會隨著像素擴散引起的,圖像上曲率變化大的點以及角點往往是進行圖像匹配比較理想的特征點,但該方法遺漏了某些重要的特征信息,不利于后續(xù)特征點匹配以及拼接圖像的形成。而FAST算法檢測的特征點,誤檢測點數(shù)少,且數(shù)量穩(wěn)定,可一次性檢測出角點、交點、邊緣點等各類特征點。

圖2　SIFT算法與FAST算法特征點提取對比圖Fig.2　Feature points extraction comparison chart of SIFT and FAST algorithm

經(jīng)實驗測試，對同一幅圖像使用基于SIFT的特征檢測算法耗時2.021s,而使用FAST算法檢測特征點耗時0.453s,可知FAST算法提取特征點所用時間遠小于基于SIFT的特征檢測算法。其原因在于,SIFT算法需遍歷考察一幅圖像經(jīng)高斯算法處理后的不同組不同層間的像素對比值,且其運行時間復雜度會隨著圖像像素的增加而增加,而FAST算法只需比較該幅圖像自身像素間的對比值,因而其時間復雜度遠小于SIFT算法。

綜上可知,FAST算法提取特征點具有快速且準確的特性,本文充分利用這一優(yōu)勢,提出一種新的基于FAST特征點檢測的圖像拼接算法,在保證圖像拼接效果的同時加快拼接速度。

2.2算法

SIFT圖像拼接算法在特征點提取階段耗時長，且易出現(xiàn)特征點漏檢的問題,本文采用FAST算法進行特征點檢測,再將提取出的特征點進行描述,最終完成圖像拼接。算法流程圖如圖3所示。

算法主要步驟如下:

1)圖像獲取。采用定點旋轉(zhuǎn)或沿垂直于照相機光軸的方向移動拍攝，獲取源圖像I1和I2。

2)提取特征點。對源圖像I1和I2經(jīng)向量變化得到相應(yīng)的向量矩陣,對圖像矩陣采用FAST算法提取特征點,得到對應(yīng)特征點坐標,其中參數(shù)n取值為30,p取值9,通過使用角點提取的方式提高特征點定位精度，并加快特征點的提取速度。

3)選取特征點主方向。計算檢測出的每個特征點的梯度模值和方向。以關(guān)鍵點所在位置為中心，在半徑為4的鄰域窗口內(nèi)采樣,以此增加鄰域點對關(guān)鍵點的影響,然后用直方圖統(tǒng)計鄰域像素的梯度方向,選取直方圖的主峰值作為關(guān)鍵點的主方向,80%主峰值的局部峰值作為該點的輔助方向。

4)生成特征向量。利用直方圖統(tǒng)計8×8小塊上8個方向的梯度方向直方圖,繪制每個方向的累加值,形成4個種子點,每個關(guān)鍵點就形成2×2×8=32維的描述子。對向量進行歸一化處理,進一步去除光照影響,增加匹配的穩(wěn)健性。

5)特征匹配。本文采用兩個向量的歐氏距離作為相似性的判斷度量。為了提高圖像匹配精度，采用RANSAC算法對變換矩陣進行求解與精煉。

6)圖像融合。本文采用簡單快速的加權(quán)平滑算法[15]處理拼縫問題。

7)輸出拼接圖像。即輸出經(jīng)過特征提取、特征匹配和融合的拼接圖像。

圖3　本文算法流程圖Fig.3　The flow chart of this algorithm

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

本算法在Core 2,2.66 GHz CPU,2.0 GB RAM的PC機上,Matlab R2010a 環(huán)境下實現(xiàn)。為了驗證本文算法的有效性,將本文算法與基于SIFT的拼接算法以及SIFT算法的改進算法——PCA-SIFT算法及SUFT算法進行比較。使用兩組圖像對算法進行檢驗,其中圖像組1為標準灰度Lena圖像，圖像組2為景物灰度圖像,如圖4所示。

圖4　原始圖像組Fig.4　The original image groups

對兩組圖像分別進行特征點的提取和匹配,以圖像組2為例,特征點提取如圖5所示,特征點匹配如圖6所示。

圖5　圖像組2特征點提取對比圖Fig.5　Image feature point extraction contrast figure of group 2

圖6　圖像組2特征點匹配對比圖Fig.6　Image feature point matching contrast figure of group 2

對兩組圖像使用4種拼接算法實驗結(jié)果如圖7,圖8所示。

圖7　圖像組1拼接結(jié)果對比圖Fig.7　Mosaic results contrast figure of group 1

圖8　圖像組2拼接結(jié)果對比圖Fig.8　Mosaic results contrast figure of group 2

圖9　圖像組1右側(cè)圖像旋轉(zhuǎn)后待拼接圖像組Fig.9　Mosaic image group after rotation for the image on the right side of group 1

為了進一步驗證本文算法的有效性,對圖像組1右側(cè)圖像進行任意角度的旋轉(zhuǎn)，如圖9所示，然后進行拼接實驗，拼接結(jié)果如圖10所示。

為了驗證算法的魯棒性,給兩組圖像添加密度為0.02的椒鹽噪聲,并與其他3種拼接算法比較,圖像組1拼接結(jié)果如圖11所示,圖像組2拼接結(jié)果如圖12所示。

圖10　圖像組1右側(cè)圖像旋轉(zhuǎn)后拼接結(jié)果對比圖Fig.10　Contrast figure of mosaic results after rotation for the image on the right side of group 1

圖11　圖像組1添加椒鹽噪聲后拼接結(jié)果對比圖Fig.11　Contrast figure of mosaic results after add salt and pepper noise to group 1

圖12　圖像組2添加椒鹽噪聲后拼接結(jié)果對比圖Fig.12　Contrast figure of mosaic results after add salt and pepper noise to group 2

分別統(tǒng)計原始圖像組采用SIFT拼接算法、PCA-SIFT算法、SUFT拼接算法以及本文算法進行拼接所對應(yīng)的特征點數(shù)、匹配點對數(shù)和算法運行時間,結(jié)果分別如表1(“/”符號前為左側(cè)圖像提取特征點數(shù),符號后為右側(cè)圖像提取特征點數(shù))、表2和表3所示。

表1　4種算法特征點提取個數(shù)對比結(jié)果

表2　4種算法特征點匹配個數(shù)對比結(jié)果

表3　4種算法運行時間對比結(jié)果

從直觀效果來看,由圖5圈內(nèi)標注的特征點提取情況可知,SIFT算法提取特征點位置存在一定偏移，但本文算法提取特征點定位準確且數(shù)目較多。由圖6匹配對比圖可以看出,本文算法的匹配情況優(yōu)于原有SIFT算法,誤匹配對數(shù)較少。由圖7和圖8兩組圖像的拼接結(jié)果對比圖可以得出,本文算法拼接結(jié)果與SIFT算法相近,PCA-SIFT拼接算法拼縫處過渡不光滑,SUFT拼接算法拼縫處有細微裂痕。由圖10旋轉(zhuǎn)后的拼接結(jié)果可知,其他3種算法出現(xiàn)不同程度的拼縫，但本文算法拼接效果良好,可以完整顯示拼接圖像。由圖11和12噪聲影響下的拼接結(jié)果可以看出，SUFT算法拼接圖像受噪聲干擾明顯,PCA-SIFT算法拼接圖出現(xiàn)一定拼縫,而本文算法仍可以較好地實現(xiàn)拼接,證明其對噪聲具有一定魯棒性。

從定量角度分析,由表1、表2和表3可得,本文算法提取的特征點數(shù)及匹配對數(shù)多于其他3種拼接算法,但運行時間均小于其他3種算法,即本文算法在更短的時間內(nèi)取得了較好的拼接效果。

4　結(jié)　論

本文算法采用FAST特征點提取融合SIFT特征點描述的方式,改進原有SIFT圖像拼接算法。仿真實驗表明，該算法相較原有算法減少了拼接運行時間,增加了準確定位特征點數(shù),提高了匹配準確率，有利于拼接圖像的快速生成，適應(yīng)于實時性要求較高的場景。

[1]袁杰. 基于 SIFT 的圖像配準與拼接技術(shù)研究[D]. 南京: 南京理工大學, 2013.

[3]HARRIS C, STEPHENS M. A combined corner and edge detector [C]∥Alvey vision conference, The University of Manchester,1988,15:147-151.

[4]LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[5]蘇麗穎, 李小鵬, 么立雙. 一種改進的SIFT特征提取新算法[J]. 華中科技大學學報(自然科學版), 2013, 41(1):396-398.

[6]KE Y, SUKTHANKAR R. PCA-SIFT: A more distinctive representation for local image descriptors[J]. Computer Vision and Pattern Recognition, 2004, 2:506-513.

[7]MIKOLAJCZYK K, SCHMID C. A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005,27(10):1615-1630.

[8]楊恒, 王慶. 一種新的局部不變特征檢測和描述算法[J]. 計算機學報, 2010, 33(5): 935-944.

[9]ROSTEN E, DRUMMOND T. Fusing points and lines for high performance tracking[C]∥Tenth IEEE International Conference on Computer Vision. IEEE, 2005, 2: 1508-1515.

[10] 孫波. 數(shù)字圖像角點檢測算法的研究[D]. 合肥:合肥工業(yè)大學, 2013.

[11] 梁艷菊,李慶,陳大鵬,等.一種快速魯棒的LOG-FAST角點算法[J].計算機科學，2012，39(6)：251-254.

[12] MA Y, REN Z. Image mosaic method based on improved SIFT feature detection algorithm[C]∥Proceedings of the 9th International Symposium on Linear Drives for Industry Applications, Springer Berlin Heidelberg, 2014: 771-779.

[13] ALDANA-MURILLO N G, HAYET J B, BECERRA H M. Evaluation of Local Descriptors for Vision-Based Localization of Humanoid Robots[M]//Pattern Recognition.Berlin:Springer International Publishing, 2015: 179-189.

[14] ROSTEN E,DRUMMOND T. Faster and better: a machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(1):105-119.

[15] ZHANG Y, CHEN L,ZHAO Z,et al.Multi-focus image fusion with sparse feature based pulse coupled neural network[J].TELKOMNIKA (Telecommunication Computing Electronics and Control),2014,12(2):357-366.

(編輯李靜)

Image mosaic algorithm based on the FAST feature points extraction

GAO Jing, CHEN Li, LAN Xiao-yan, JIN Li-yan, YANG Zhou

(School of Information Science and Technology, Northwest University, Xi′an 710127， China)

Aiming at the feature invariants and position deviation caused by a long run time in feature points extraction when adopting difference of Gaussian pyramid method based on SIFT image mosaic algorithm, an image mosaic algorithm based on the FAST feature points extraction was proposed. In this algorithm, the first step is replacing original SIFT algorithm with feature extraction method based on FAST. The step followed by is describing and vector-matching the feature points, then registering image by Euclidean distance and RANSAC algorithm.The final mosaic image is accomplished by using weighted average fusion algorithm.Simulation results show that the new algorithm is more suitable to get seamless image in that it not only accelerates the extraction rate of the feature points, but also improves the accuracy of positioning.

FAST; feature points; SIFT; image mosaic

2015-11-03

國家科技支撐基金資助項目(2013BAH49F02，2013BAH49F03)

高晶，女，山西呂梁人，從事數(shù)字圖像處理、智能信息處理研究。

TP751.1

A

10.16152/j.cnki.xdxbzr.2016-03-009