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

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

?

·信息科學(xué)·

基于FAST特征點(diǎn)提取的圖像拼接算法

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

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

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

FAST；特征點(diǎn)；SIFT；圖像拼接

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

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

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

1　SIFT圖像拼接算法

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

1.1尺度空間極值檢測

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

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

(1)

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

(2)

SIFT算法在實(shí)際應(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兩個(gè)金字塔,而高斯金字塔分為多組,每組間又分為多層。尺度因子因組和層的不同而不同,同時(shí)為了獲取DoG極值,需要生成δ·(S+3)的平滑圖像(S代表尺度數(shù))。

1.2尺度空間極值點(diǎn)判定

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

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

2　基于FAST的圖像拼接算法

2.1FAST特征點(diǎn)檢測算法

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

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

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

(4)

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

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

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

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

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

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

2.2算法

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

算法主要步驟如下:

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

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

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

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

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

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

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

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

3　實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

對兩組圖像使用4種拼接算法實(shí)驗(yàn)結(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

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

為了驗(yàn)證算法的魯棒性,給兩組圖像添加密度為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)計(jì)原始圖像組采用SIFT拼接算法、PCA-SIFT算法、SUFT拼接算法以及本文算法進(jìn)行拼接所對應(yīng)的特征點(diǎn)數(shù)、匹配點(diǎn)對數(shù)和算法運(yùn)行時(shí)間,結(jié)果分別如表1(“/”符號前為左側(cè)圖像提取特征點(diǎn)數(shù),符號后為右側(cè)圖像提取特征點(diǎn)數(shù))、表2和表3所示。

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

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

表3　4種算法運(yùn)行時(shí)間對比結(jié)果

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

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

4　結(jié)　論

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

[1]袁杰. 基于 SIFT 的圖像配準(zhǔn)與拼接技術(shù)研究[D]. 南京: 南京理工大學(xué), 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]蘇麗穎, 李小鵬, 么立雙. 一種改進(jìn)的SIFT特征提取新算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 計(jì)算機(jī)學(xué)報(bào), 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ù)字圖像角點(diǎn)檢測算法的研究[D]. 合肥:合肥工業(yè)大學(xué), 2013.

[11] 梁艷菊,李慶,陳大鵬,等.一種快速魯棒的LOG-FAST角點(diǎn)算法[J].計(jì)算機(jī)科學(xué)，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

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

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

TP751.1

A

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