移動(dòng)平臺上四鄰域梯度閾值的SIFT匹配優(yōu)化

雷俊鋒，郭 勇，肖進(jìn)勝，朱月苓，張 存

（武漢大學(xué) 電子信息學(xué)院，湖北 武漢430072）

0 引 言

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

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

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

1 SIFT算法的基本原理

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

1.1 建立多尺度空間

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

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

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

1.2 尺度空間極值點(diǎn)檢測及精確定位

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

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

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

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

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

1.4 特征描述子的計(jì)算

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

1.5 特征點(diǎn)匹配與誤匹配點(diǎn)的剔除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

隨機(jī)選擇圖像庫中的一對測試圖像，在傳統(tǒng)算法和優(yōu)化算法不同閾值條件下的實(shí)驗(yàn)測試結(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之后，匹配點(diǎn)數(shù)趨于穩(wěn)定，并與傳統(tǒng)算法匹配數(shù)目基本一致，但匹配時(shí)間增加，當(dāng)閾值為0.02時(shí)，可以保證匹配結(jié)果的同時(shí)大幅提高匹配效率。

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

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

4 結(jié)束語

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

［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）.［徐陽，曹杰.一種基于對比閾值的改進(jìn)SIFT算法 ［J］.電子設(shè)計(jì)工程，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.