程俊廷， 張俊峰， 胡 瑾

(1.黑龍江科技大學(xué) 機(jī)械工程學(xué)院， 哈爾濱 150022； 2.合肥財(cái)經(jīng)職業(yè)技術(shù)學(xué)院 人工智能學(xué)院， 合肥 230000)

0 引 言

在建筑物三維重建的過程中，對(duì)采集的圖像進(jìn)行特征匹配，是至關(guān)重要的一個(gè)環(huán)節(jié)[1]。圖像特征匹配既可以利用相對(duì)較少的圖像比如兩幅，也可以用更多的圖像，比如三幅乃至更多，通過特定算法，對(duì)圖像內(nèi)容、關(guān)系、結(jié)構(gòu)等進(jìn)行相似性和一致性分析，從而識(shí)別出同名點(diǎn)的過程。特征點(diǎn)的匹配分為三個(gè)步驟：第一步為特征提取，第二步為特征描述，最后一步為特征匹配。特征提取就是從給定的圖像中提取出關(guān)鍵點(diǎn)(或角點(diǎn)、特征點(diǎn))等[2]。特征描述就是利用數(shù)學(xué)向量對(duì)提取到的關(guān)鍵點(diǎn)進(jìn)行一系列的描述，其目的是為了保證向量和特征點(diǎn)之間一一對(duì)應(yīng)的關(guān)系。特征匹配實(shí)際上就是計(jì)算特征向量之間二者的距離，最常用的是計(jì)算歐式距離。在進(jìn)行圖像特征匹配時(shí)，有Susan算法[3]、Moravec算法[4]、Forstner算法[5]等，但使用最廣泛的算法是David.Lowe教授提出的尺度不變特征SIFT算法[6-7]，此算法具有相對(duì)較強(qiáng)的魯棒性，當(dāng)圖像進(jìn)行尺度大小縮放、多角度旋轉(zhuǎn)、亮度變化時(shí)能夠保持不變性[8]。SIFT算法在具備以上諸多優(yōu)點(diǎn)之外，也存在容易對(duì)出現(xiàn)多個(gè)相似特征點(diǎn)共存時(shí)，出現(xiàn)誤匹配的狀況和計(jì)算復(fù)雜繁瑣的缺點(diǎn)[9]。為了改善這些缺點(diǎn)，提出一種改進(jìn)的SIFT算法，一方面通過降低描述子向量維度，降低計(jì)算量和復(fù)雜度；另一方面通過考慮匹配點(diǎn)的最近鄰歐式距離，剔除誤匹配點(diǎn)，提高特征點(diǎn)匹配準(zhǔn)確度。

1 改進(jìn)的SIFT算法

1.1 SIFT算法

目前，在建筑物三維重建過程中，圖像特征匹配的主流算法是SIFT算法，SIFT算法實(shí)現(xiàn)圖像特征匹配包括構(gòu)建尺度空間、高斯差分、生成特征描述和特征向量匹配。

1.1.1 構(gòu)建尺度空間

特征點(diǎn)檢測(cè)是在尺度空間中完成的，從較遠(yuǎn)的地方采集建筑物的圖像，尺度空間越大，圖像越模糊，大尺度空間能還原建筑物表面的概貌，小的尺度空間能夠還原建筑物表面的細(xì)節(jié)特征[10]。為了更詳細(xì)的表示尺度空間，可以采用將圖像的卷積和高斯函數(shù)二者結(jié)合進(jìn)行表示

L(x,y,σ)=G(x,y,σ)I(x,y)，

(1)

式中：L(x,y,σ)——圖像的尺度空間；

G(x,y,σ)——尺度空間大小可以變得函數(shù)；

σ——尺度；

I(x,y)——原始圖像的尺度坐標(biāo)。

1.1.2 高斯差分

為了能夠提高提取尺度空間極值點(diǎn)的穩(wěn)定性，文中采用高斯差分尺度空間(DoG)來(lái)檢測(cè)部分區(qū)域的極值點(diǎn)。高斯差分函數(shù)為

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))I(x,y)=

L(x,y,kσ)-L(x,y,σ)，

(2)

式中，k——放大因子。

1.1.3 特征描述子

為了保證圖像在旋轉(zhuǎn)時(shí)，描述子不變，首先需要定出方向參數(shù)。高斯差分尺度空間中檢測(cè)出來(lái)的特征點(diǎn)梯度的數(shù)值以及方向計(jì)算為

m(x,y)=(L(x+1,y)-L(x-1,y))2+

(3)

(4)

特征點(diǎn)存在的尺度用L表示。目前，使用的SIFT算法，普遍選擇以關(guān)鍵點(diǎn)為中心其鄰域內(nèi)16×16的窗口，在這基礎(chǔ)上，進(jìn)一步將窗口進(jìn)行劃分，變?yōu)?6個(gè)4×4的子窗口，每個(gè)子窗口又含有8個(gè)方向的向量信息，故最終特征描述子有4×4×8共128維向量。

1.1.4 特征向量匹配

歐式距離是圖像特征匹配的一個(gè)重要參數(shù)，當(dāng)歐式距離小于特定閾值時(shí)，即認(rèn)為匹配成功。歐式距離作為判定特征點(diǎn)相似度的一個(gè)重要依據(jù)，也有其局限性，當(dāng)亮度發(fā)生變化時(shí)，會(huì)對(duì)歐式距離的結(jié)果造成偏差，導(dǎo)致匹配的準(zhǔn)確度不高，往往結(jié)合特征向量的次近鄰距離大小，來(lái)判定特征向量的相似度，整個(gè)匹配過程的公式為

(5)

(6)

式中：dab——兩特征點(diǎn)之間的歐式距離；

da(j)、db(j)——特征點(diǎn)的描述符分量；

dN——兩點(diǎn)之間的最近鄰距離；

dS——兩點(diǎn)間的次近鄰距離；

t——閾值。

在歐式距離小于給定閾值的基礎(chǔ)上，如果dN/dS也小于給定的某個(gè)閾值t，即可認(rèn)定點(diǎn)匹配正確。

1.2 改進(jìn)的SIFT算法

為了簡(jiǎn)化計(jì)算，提高匹配的準(zhǔn)確度，在進(jìn)行特征匹配時(shí)，采用一種改進(jìn)的SIFT算法。

1.2.1 描述子

描述子是用特征點(diǎn)周圍16×16的鄰域當(dāng)作采樣窗口，在此基礎(chǔ)上，需要進(jìn)一步劃分種子區(qū)域，傳統(tǒng)的SIFT算法種子區(qū)域有16個(gè)，每個(gè)區(qū)域內(nèi)含有16個(gè)像素。文中采用的改進(jìn)SIFT算法，降低描述子的采樣窗口，將特征點(diǎn)周圍15×15的像素當(dāng)作采樣窗口，再將窗口劃分為3×3的種子區(qū)域，每個(gè)種子區(qū)域有5×5的25個(gè)像素點(diǎn)。

與傳統(tǒng)的SIFT算法相比，改進(jìn)的SIFT算法描述子有3×3×8的72維向量，向量維度下降率為43.75%，向量維度的降低，可以大大減小計(jì)算量和計(jì)算過程中的復(fù)雜度，改善時(shí)間性能。

1.2.2 匹配算子

傳統(tǒng)的SIFT算法中，忽視了匹配點(diǎn)對(duì)的最近鄰歐式距離與點(diǎn)對(duì)匹配正確率之間的關(guān)系。在研究了大量點(diǎn)對(duì)的匹配結(jié)果后，發(fā)現(xiàn)特征匹配正確率與dab、dN以及dN/dS有如下規(guī)律：

(1)增大圖像視角，會(huì)降低特征匹配的正確率。

(2)在采集圖像時(shí)，如果角度沒有變化，當(dāng)dab>0.4時(shí)，匹配點(diǎn)對(duì)的正確率幾乎為0；當(dāng)dab<0.4時(shí)，匹配正確率顯著提升，且dab越小，匹配正確率越高。

(3)特征點(diǎn)匹配的準(zhǔn)確率與dN/dS有一定的關(guān)系，即二者比值小于0.5時(shí)，匹配的準(zhǔn)確率高；當(dāng)比值大于0.5時(shí)，匹配準(zhǔn)確率低。

結(jié)合上述三點(diǎn)規(guī)律，文中將dab，dN和dN/dS結(jié)合起來(lái)，作為特征點(diǎn)匹配準(zhǔn)確率的依據(jù)。

在初始計(jì)算時(shí)，如果dN≥0.4，則直接舍棄該點(diǎn)。

若dN<0.4，開始計(jì)算dN/dS的值，并根據(jù)所得值進(jìn)行討論。若dN/dS≤0.5，則認(rèn)為特征點(diǎn)匹配的準(zhǔn)確率較高，將此類點(diǎn)歸為集合A中，定義為A類點(diǎn)集；如果計(jì)算的比值大于0.5且小于0.8，則認(rèn)為特征點(diǎn)匹配的準(zhǔn)確率較低，將此類點(diǎn)集歸為集合B中，定義為B類集合；若dN/dS≥0.8，則認(rèn)為匹配錯(cuò)誤，直接舍棄。

具體的匹配流程如圖1所示。

圖1 初始匹配流程Fig. 1 Initial matching flow

2 實(shí)驗(yàn)對(duì)比分析

采用VS2018和OPENMVG搭建實(shí)驗(yàn)平臺(tái)，配準(zhǔn)SIFT算法與改進(jìn)的SIFT算法的圖像實(shí)驗(yàn)數(shù)據(jù)圖如圖2所示。采用傳統(tǒng)的SIFT算法和文中的算法得出的結(jié)果如圖3所示。

圖2 實(shí)驗(yàn)數(shù)據(jù)Fig. 2 Experimental data graph

圖3 匹配結(jié)果Fig. 3 Matching results

對(duì)兩種算法的執(zhí)行速度和匹配結(jié)束的效果進(jìn)行對(duì)比分析，如表1和表2所示，其中初始匹配點(diǎn)數(shù)為n，特征點(diǎn)提取時(shí)間為t，初始匹配點(diǎn)對(duì)為m，初始匹配時(shí)間為t0，正確匹配點(diǎn)對(duì)為mt，誤匹配點(diǎn)對(duì)為mf，誤匹配率為e。

表1 兩種算法相關(guān)運(yùn)行時(shí)間對(duì)比Table 1 Comparison of relative running time of two algorithms

表2 兩種算法匹配準(zhǔn)確率對(duì)比Table 2 Comparison of matching accuracy of two algorithms

由表1可知，采用改進(jìn)的SIFT算法，進(jìn)行特征點(diǎn)提取時(shí)，所用的時(shí)間降低了46.87%，同時(shí)，初始匹配時(shí)間也降低了16.17%。節(jié)省了大量的時(shí)間，提高了匹配的效率，故改進(jìn)的SIFT算法在時(shí)間性能上優(yōu)于傳統(tǒng)的SIFT算法。

由表2可知，采用傳統(tǒng)的SIFT算法和本文改進(jìn)的SIFT算法，從表2數(shù)據(jù)分析可得，采用改進(jìn)的SIFT算法進(jìn)行特征匹配，誤匹配率減少了5.1%，匹配準(zhǔn)確度更高。因此，改進(jìn)的SIFT算法在匹配準(zhǔn)確度上也優(yōu)于傳統(tǒng)的SIFT算法。

3 結(jié)束語(yǔ)

在原SIFT算法的基礎(chǔ)上，給出了一種改進(jìn)的SIFT算法進(jìn)行圖像特征點(diǎn)匹配。該算法通過減少SIFT算法描述子向量維度與改進(jìn)SIFT算法匹配算子，來(lái)降低匹配過程所用的時(shí)間和提高特征匹配的準(zhǔn)確率。通過對(duì)改進(jìn)的SIFT算法和原SIFT算法的匹配結(jié)果進(jìn)行分析，得出改進(jìn)的算法提取特征點(diǎn)時(shí)，用時(shí)降低了46.87%，特征點(diǎn)匹配時(shí)，用時(shí)降低了16.17%，誤匹配率降低了5.1%。因此，該算法在圖像的特征匹配過程中具有廣泛的應(yīng)用價(jià)值。