雷俊鋒，郭 勇，肖進勝，朱月苓，張 存

（武漢大學 電子信息學院，湖北 武漢430072）

0 引 言

SIFT算法［1，2］存在計算量大、實時性差等缺點。很多學者在SIFT的基礎(chǔ)上做出了改進，Calonder M.等基于SIFT提出了BRIEF算法［3］，提高了運算速度，但抗旋轉(zhuǎn)和多尺度效果不明顯；Rublee E.等在BRIEF的基礎(chǔ)上提出的ORB算法［4］，一定程度上增強了BRIEF的抗旋轉(zhuǎn)性能；Faraj A.等將SIFT特征點增加角度特征［5］，根據(jù)角度特征將特征點分類，以提高匹配效率；徐陽等，在SIFT的極值點檢測時增加自適應閾值［6］，根據(jù)圖像情況，生成適當數(shù)目的極值點，減少圖像中特征點的數(shù)目，進而降低匹配運算量。有些學者借助于多核CPU、GPGPU和FPGA等硬件設(shè)備實現(xiàn)算法加速?；诙嗪薈PU的SIFT算法［7］和基于GPGPU的SIFT算法［8］主要使用大量的并行計算以提高運算速度；基于FPGA的SIFT算法［9］利用并行FPGA資源以提高運算速度。

近幾年隨著移動平臺的飛速發(fā)展，移動設(shè)備的數(shù)據(jù)處理能力越來越強大，將優(yōu)秀的算法移植到移動端是一種趨勢，這也極大方便了復雜算法在儀器儀表等便攜式設(shè)備上的使用。很多學者利用移動處理器的特點，使用移動GPU和CPU將復雜算法在移動端實現(xiàn)，G.－R.Kayombya對SIFT算法在Z400系列高通移動GPU上的實現(xiàn)做了研究［10］。K.－T.Cheng等對面部識別算法在移動 GPU上的實現(xiàn)做了研究［11］，與移動CPU相比速度有所提升，卻犧牲了一定的運算精度。Rister B.等在G.－R.Kayombya的基礎(chǔ)上，對SIFT算法在移動GPU上進行了一定的優(yōu)化［12］。對于SIFT特征點生成這一階段，他們的工作在一定程度上優(yōu)化了算法在移動平臺上的實現(xiàn)效率，但是由于目前移動設(shè)備及編程語言的限制，SIFT算法的匹配階段還無法借用移動處理器的GPU優(yōu)化匹配效率，只能通過理論方面的優(yōu)化實現(xiàn)匹配階段的加速。

針對上述算法的缺點和不足，本文提出了一種四鄰域梯度值分組的匹配方法，將特征點與周圍4個點的梯度值作為特征之一，在匹配之前對特征點對的主梯度值關(guān)系進行判斷，只將符合條件的點進行匹配運算，相當于減少了大量的特征點，提高了匹配效率。

1 SIFT算法的基本原理

SIFT算法是通過提取圖像局部特征以實現(xiàn)圖像間準確的匹配，它在尺度空間上尋找極值點，提取圖像的特征不變量，以此構(gòu)成圖像的特征描述符。主要過程為：①建立多尺度空間。②極值點檢測及定位。③確立特征方向。④計算特征描述子。⑤特征點匹配與錯誤剔除。

1.1 建立多尺度空間

一幅二維圖像，在不同尺度下的空間表示可由圖像與高斯核空間域卷積得到，如式 （1）所示

式中：G（x，y，σ）——尺度可變的二維高斯函數(shù)；＊——卷積運算；I（x，y）——待處理圖像，表示圖像的尺度空間。Lowe提出了高斯差分函數(shù)算子 （difference of Gaussian，DoG）對原始圖像進行卷積計算，以有效的在尺度空間檢測穩(wěn)定的關(guān)鍵點，如式 （2）所示

式中：k——不同的高斯核尺度，k的初始值為1，尺度以k倍遞增。

1.2 尺度空間極值點檢測及精確定位

在高斯差分空間中，選擇中間的幾層圖像，將圖像的每個點和同一尺度上周圍的8個點以及上下相鄰尺度圖像對應位置的9x2個點進行比較，以判斷其是否是極值點，檢測到的所有極值點就是SIFT待選特征點的集合。由于DoG算子會產(chǎn)生比較強的邊緣響應，還需要舍棄的對比度邊緣響應的不穩(wěn)定點以及高對比度的點，以獲得比較穩(wěn)定的特征點。

1.3 確立關(guān)鍵點特征方向

首先計算關(guān)鍵點鄰域內(nèi)每個像素點的梯度和方向的分布特征，然后進行統(tǒng)計以計算每個關(guān)鍵點的方向參數(shù)，如式 （3）和式 （4）所示

式中：m（x，y）和θ（x，y）分別為高斯空間圖像中點 （x，y）處的梯度值和方向，L所用的尺度為每個關(guān)鍵點各自所在的尺度圖像。

將鄰域內(nèi)所有點的梯度值按照角度值進行求和統(tǒng)計，把最大梯度值對應的角度值作為關(guān)鍵點的主方向，如果次大梯度值大于最大值的0.8倍時，所對應的角度值也作為該點的主方向。

1.4 特征描述子的計算

針對任意的關(guān)鍵點，選擇其所在的高斯尺度圖像，以關(guān)鍵點為中心選擇16像素x16像素大小的區(qū)域，將該區(qū)域進行均勻劃分，使每個子區(qū)域的大小為4像素x4像素，共為16個子區(qū)域。獲得每個4像素x4像素的子區(qū)域中的8方向梯度直方圖，再對16個子區(qū)域的8方向梯度值按照位置進行依次排序，最后生成16x8＝128維向量，SIFT描述子就是該128維向量。

1.5 特征點匹配與誤匹配點的剔除

生成當兩幅圖像的SIFT特征描述子之后，計算關(guān)鍵點128維向量特征描述子的歐氏距離，以此為判斷依據(jù)以確定兩幅圖像中關(guān)鍵點相似性。這樣的匹配結(jié)果會存在一定的錯誤匹配點，再使用RANSAC算法處理以消除錯誤匹配。

2 四鄰域梯度值閾值的匹配控制方法

傳統(tǒng)SIFT算法在匹配時的特征點有3個特征信息，即坐標、尺度、128維描述子，在匹配過程中使用關(guān)鍵點128維向量描述子的歐式距離作為判斷依據(jù)以確定兩幅圖像中關(guān)鍵點相似性。匹配時，需要找出兩幅圖像中關(guān)鍵點對之間的最近歐氏距離和次最近歐氏距離，并將兩個距離進行對比，符合條件的則為相似點。歐氏距離是指在m維空間向量中兩個點之間的真實距離，定義為

式中：D為m＝128維向量描述子的歐氏距離，xi，yi為相匹配圖像的描述子相對應維的值，可以看出，如果進行傳統(tǒng)的匹配方法，將所有的特征點都進行歐氏距離計算的計算量會很大，這也是SIFT算法匹配過程中計算復雜度高，耗時久的原因。因此，如何減少歐氏距離的計算是降低算法復雜度的有效方法。

特征點的描述子的生成，是在將特征點鄰域內(nèi)，不同的像素的梯度值與和像素與特征點距離相關(guān)的加權(quán)系數(shù)的乘積所生成的，加權(quán)系數(shù)如式 （6）所示

式中，weight——梯度值的加權(quán)系數(shù)，x——區(qū)域內(nèi)的點與關(guān)鍵點的列向距離，y——區(qū)域內(nèi)的點與關(guān)鍵點的行向距離，σ——描述子窗口寬度與直方圖列數(shù)一半的乘積。由此可知在匹配過程中，距離特征點越近的特征點區(qū)域內(nèi)的像素點的梯度值對匹配結(jié)果影響越大，距離特征點越遠的特征點區(qū)域內(nèi)的像素點的梯度值對匹配結(jié)果影響越小，特征點周圍四鄰域的梯度值對匹配起著關(guān)鍵作用。

因此根據(jù)描述子的特點，特征點的匹配是和特征點鄰域的梯度值是有關(guān)系的，根據(jù)大量的實驗統(tǒng)計特征點鄰域內(nèi)不同區(qū)域梯度值與正確匹配點的梯度值的關(guān)系，本文提出了一種四鄰域主梯度值閾值進行匹配控制的方法。該方法將關(guān)鍵點四鄰域主梯度值作為特征點的特征之一，在進行主方向統(tǒng)計時，計算特征點周圍四鄰域的梯度值之和，即將特征點主方向所對應的梯度值作為新的特征，在匹配階段中使用。

對高斯差分空間所檢測的穩(wěn)定極值點，在相對應的高斯空間圖像上特征點的3×1.5σ鄰域內(nèi)，根據(jù)式 （4）計算像素的角度值，根據(jù)式 （3）計算相對應梯度值，使用角度所對應的梯度直方圖對區(qū)域內(nèi)像素點的梯度和方向進行統(tǒng)計。直方圖劃分規(guī)則為，將360°分為36個柱，每一個柱為10°，每個直方圖的值表示相對應方向范圍的梯度值和。將特征點周圍四鄰域的梯度值作為特征點新的特征，在圖像的特征點進行匹配前，比較圖像1和圖像2中的特征點的四鄰域梯度值，并將比較的值按照閾值進行分類，符合條件的則繼續(xù)進行相對應的歐氏距離計算和后續(xù)匹配計算，不符合條件的舍去，不進行歐氏距離計算和匹配計算，這樣可以大量減少進行歐氏距離計算的特征點，從而降低運算復的雜度，節(jié)約運算時間。

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

實驗所使用的移動處理器為：瑞芯微RK3066。CPU為：ARM Cortex－A9，RAM：1GB，頻率：1.6GHz。軟件環(huán)境：Android平臺為4.1。算法使用Android NDK在Eclipse工具上實現(xiàn)。使用標準圖像數(shù)據(jù)庫［13］里面圖像，在同樣的實驗環(huán)境條件下，運行傳統(tǒng)算法和優(yōu)化算法，并對實驗結(jié)果進行對比和分析。其中的幾對圖像在不同閾值下的實驗結(jié)果見表1和表2。

表1 不同閾值條件下匹配點數(shù)的對比

表2 不同閾值條件下匹配時間的對比

表1為不同的圖像對分別在0.01至0.05閾值條件下的匹配結(jié)果與傳統(tǒng)算法的匹配結(jié)果的對比，每組圖像的數(shù)據(jù)分別為原始尺寸實驗數(shù)據(jù)，和對原始圖像進行適當縮小之后的數(shù)據(jù)。從實驗結(jié)果中可以看出，隨著閾值的增加，匹配的點數(shù)不斷增加。當閾值比較小的時候，匹配的點數(shù)與傳統(tǒng)算法相比，匹配的點數(shù)較少，隨著閾值增加匹配點數(shù)增加，當閾值超過0.02之后，匹配的點數(shù)趨于穩(wěn)定，并與傳統(tǒng)算法匹配數(shù)目基本一致。同時，對匹配的點的坐標進行檢查，相對應圖像間匹配點的坐標也是一致的。

表2為不同圖像對分別在0.01至0.05閾值條件下的匹配時間與傳統(tǒng)算法匹配時間的對比，每組圖像的數(shù)據(jù)分別為原始尺寸實驗數(shù)據(jù)，和對原始圖像進行適當縮小之后的數(shù)據(jù)。從實驗結(jié)果可以看出，閾值越小匹配的時間越短，隨著閾值的增加匹配時間不斷增加。但是由于原始圖像尺寸較大，所檢測的特征點數(shù)目較多，運算時間因此實現(xiàn)實時性比較困難，這一點不如桌面電腦處理器，這是由于移動處理器的帶寬和頻率遠遜于電腦處理器所導致的。通過對表中實驗數(shù)據(jù)分析可以看出，對圖像進行適當縮放之后，匹配時間就會減少很多。通過對表1和表2的綜合分析，當選取閾值為0.02時，本文改進的算法的匹配結(jié)果和傳統(tǒng)算法的匹配結(jié)果基本保持一致，而且也明顯的減少了匹配所消耗的時間，不同圖像對的匹配一致性和加速效果分析見表3。

表3 匹配效率和一致性分析

表3為相對應圖像對在優(yōu)化算法和傳統(tǒng)算法的條件下匹配效率和一致性分析結(jié)果。左側(cè)為對原始圖像適當縮小之后的實驗數(shù)據(jù)，右側(cè)為原始圖像的實驗數(shù)據(jù)。加速比為傳統(tǒng)算法的匹配時間和優(yōu)化算法在閾值為0.02時匹配時間的比值，匹配重合率為優(yōu)化算法的正確匹配點數(shù)與傳統(tǒng)算法的正確匹配點數(shù)的比值。

隨機選擇圖像庫中的一對測試圖像，在傳統(tǒng)算法和優(yōu)化算法不同閾值條件下的實驗測試結(jié)果如圖1所示。圖1中選擇的是boat中的一對圖像，即為表1、表2、表3中的尺寸為420x340的boat圖像，圖像間有一定的縮放、旋轉(zhuǎn)和仿射變換。圖1中，圖1（a）為傳統(tǒng)匹配方法中匹配結(jié)果，圖1（b）至圖1（f）為優(yōu)化之后的匹配算法在閾值為0.01至0.05的不同與之條件下的匹配結(jié)果，0.02之后，匹配點數(shù)趨于穩(wěn)定，并與傳統(tǒng)算法匹配數(shù)目基本一致，但匹配時間增加，當閾值為0.02時，可以保證匹配結(jié)果的同時大幅提高匹配效率。

圖1 傳統(tǒng)匹配方法和優(yōu)化匹配方法不同閾值的匹配結(jié)果對比

通過對實驗數(shù)據(jù)的分析可以看出，當優(yōu)化后的算法閾值為0.02時，傳統(tǒng)匹配方法和優(yōu)化后匹配方法的匹配點數(shù)基本完全一致，其中對于匹配點數(shù)少于傳統(tǒng)方法的圖像，匹配點的重合率也是很高的，在實際應用中幾乎不影響匹配結(jié)果，甚至對于某幾幅圖像優(yōu)化算法的匹配點數(shù)多出幾個；實驗還對不同匹配方法的匹配點的坐標進行分析，匹配點的坐標也基本一致。此外優(yōu)化的四鄰域梯度閾值方法的匹配速度較傳統(tǒng)方法相比有2.0倍至3.0倍的提高。實驗結(jié)果表明當閾值選取0.02時，在保證匹配點數(shù)和結(jié)果正確性的前提下也提高了匹配效率。實驗還通過對200組圖片進行對比實驗并對結(jié)果進行分析，實驗結(jié)果與上述實驗結(jié)果基本相符，平均可以提高2.0至3.0倍匹配速度。因此，該優(yōu)化算法在保證匹配結(jié)果正確性的前提下，可以提高匹配效率。由于目前移動平臺的處理器在頻率和帶寬方面和桌面電腦處理器都有較大的差距，對于大尺寸圖像的處理實時性效果沒有較小尺寸的圖像的明顯。對于尺寸較小的圖像或者將較大尺寸圖像適當縮小之后，在移動平臺上基本可以實現(xiàn)實時性。

4 結(jié)束語

在原有SIFT匹配算法的基礎(chǔ)上，另外增加特征點周圍四鄰域的主梯度值作為該特征點的特征之一，對匹配算法進行控制。圖像進行128維向量描述子的歐氏距離計算之前，使用閾值0.02對特征點對之間的四鄰域主梯度值分組，符合條件的組內(nèi)的點繼續(xù)進行運算，組外的點予以刪除，以此來減少運算量達到減少運算時間的目的。實驗結(jié)果表明，所提出的主梯度閾值控制法，不但保證了匹配結(jié)果的正確性也提高了運算效率。對于尺寸較小的圖像，或者將尺寸較大圖像適當縮小，在移動端基本可以實現(xiàn)實時性。

［1］Sima AA，Buckley SJ.Optimizing SIFT for matching of short wave infrared and visible wavelength images ［J］.Remote Sensing，2013，5 （5）：2037－2056.

［2］Liu Xuejun，Shao Zhenfeng，Liu Jun.Ontology－based image retrieval with SIFT features ［C］／／First International Conference on Pervasive Computing Signal Processing and Applications.Harbin，China：IEEE，2010：464－467.

［3］Calonder M，Lepetit V，Strecha C，et al.BRIEF：Binary robust independent elementary features ［G］.LNCS 6314：Computer Vision－ECCV，2010：778－792.

［4］Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF ［C］／／IEEE International Conference on Computer Vision.Barcelona，Spain：IEEE，2011：2564－2571.

［5］Faraj A，Danijela RD，Axel G.VF－SIFT：Very fast SIFT feature matching ［G］.LNCS 6376：Pattern Recognition，2010：222－231.

［6］XU Yang，CAO Jie.Improved SIFT algorithm based on the contrast threshold ［J］.Electronic Design Engineering，2012，20 （19）：174－177 （in Chinese）.［徐陽，曹杰.一種基于對比閾值的改進SIFT算法 ［J］.電子設(shè)計工程，2012，20（19）：174－177.］

［7］OUYANG Peng，YIN Shouyi，GAO Hui，et al.Parallelization of computing－intensive tasks of SIFT algorithm on a reconfigurable architecture system ［J］.IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences，2013，E96A （6）：1393－1402.

［8］Sinha N，F(xiàn)rahm JM，Pollefeys M，et al.Feature tracking and matching in video using programmable graphics hardware ［J］.Machine Vision and Application，2011，22 （1）：207－217.

［9］Chiu Liang－Chi，Chang Tian－Sheuan，Chen Jiun－Yen，et al.Fast SIFT design for real－time visual feature extraction ［J］.IEEE Transactions on Image Processing，2013，22 （8）：3158－3167.

［10］Kayombya G－R.SIFT feature extraction on a smartphone GPU using OpenGL ES 2.0 ［D］.Massachusetts： MIT.Department of Electrical Engineering and Computer Science，2010.

［11］Cheng K－T，Wang Y.Using mobile GPU for general purpose computing－a case study of face recognition on smartphones［C］／／International Symposium on VLSI Design，Automation and Test.Hsinchu，Taiwan：IEEE，2011：54－57.

［12］Rister B，Wang Guohui，Wu M，et al.A fast and efficient sift detector using the mobile GPU ［C］／／IEEE International Conference on Acoustics，Speech and Signal Processing.Vancouver，Canada：IEEE，2013：2474－4678.

［13］Oxford.Visual geometry group－affine covariant regions dataset［EB／OL］.http：／／www.robots.ox.ac.uk／～vgg／data／data－aff.html，2014.