基于動態(tài)拓展的特征匹配方法

左威健，胡立華，劉愛琴，張素蘭，馬 瑞

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

基于圖像的特征匹配方法[1,2]主要包括基于灰度的匹配、基于梯度的匹配、融合多種理論的匹配。然而，針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)的對象，上述特征匹配方法存在以下問題：①圖像區(qū)域內(nèi)各對象提取出的特征點(diǎn)，數(shù)量較少；②圖像中顏色、結(jié)構(gòu)相近的對象，特征點(diǎn)鄰域像素信息趨于相同，采用特征局部描述子生成的描述信息辨識度不高；③采用傳統(tǒng)幾何度量方法，相近的特征描述信息將產(chǎn)生大量錯(cuò)誤匹配結(jié)果。

針對上述問題，結(jié)合最近鄰(K nearest neighbors，KNN)與具有噪聲的基于密度的聚類(density-based spatial clustering of applications with noise，DBSCAN)思想，本文提出了一種基于動態(tài)拓展的特征匹配方法。給定待匹配的兩幅圖像，該方法首先采用尺度不變特征變換(scale-invariant feature transform，SIFT)算子提取圖像特征點(diǎn)，并構(gòu)建匹配基礎(chǔ)數(shù)據(jù)集；其次，基于基礎(chǔ)數(shù)據(jù)集，結(jié)合KNN與DBSCAN思想，設(shè)計(jì)了一種逐層約束的動態(tài)拓展聚類方法，生成待匹配圖像聚類簇；然后，依據(jù)兩幅待匹配圖像聚類簇的簇內(nèi)距離與簇內(nèi)區(qū)域密度，依據(jù)匹配度量因子，獲得待匹配圖像間的對應(yīng)聚類簇；最后，依據(jù)對應(yīng)簇內(nèi)特征描述子的最近鄰與次近鄰比值，得到最終匹配結(jié)果。

1 相關(guān)研究

目前，基于圖像的特征匹配算法主要分為3類：基于灰度的匹配算法、基于梯度的匹配算法、融合多種理論的匹配算法。

基于灰度的匹配算法也稱相關(guān)匹配算法，典型方法有：絕對誤差和算法(sum of absolute differences，SAD)[3]、誤差平方和算法(sum of squared differences，SSD)[4]、歸一化積相關(guān)算法(normalized cross correlation，NCC)[5]等。該方法的優(yōu)點(diǎn)為計(jì)算過程簡單，容易理解，匹配精度高；缺點(diǎn)為運(yùn)算量大，對噪音、光照、色彩差異與旋轉(zhuǎn)等適應(yīng)性較低，匹配效果穩(wěn)定性不高?；谔荻鹊钠ヅ渌惴?，該方法首先提取圖像特征，生成特征描述子，然后依據(jù)一定的度量信息匹配特征。典型方法有：GMS[6]+R、SIFT[7]+R、SURF[8]+R與ORB[9]+R(R=RANSAC)等。融合多種理論的匹配算法，通過引入模型、圖論、交叉變異等理論，構(gòu)建空間約束，實(shí)現(xiàn)特征匹配。典型的有：基于語義網(wǎng)絡(luò)匹配算法[10]、基于深度學(xué)習(xí)匹配算法[11]、基于遺傳理論匹配算法等。典型方法有：基于空間聚類的異常值剔除匹配算法[12]，該方法基于初始匹配集構(gòu)建聚類觀測集，將匹配集中誤匹配剔除問題轉(zhuǎn)換為觀測集中尋找離群點(diǎn)的問題。但該方法依賴于初始匹配集，數(shù)據(jù)分布不同，最終離群點(diǎn)的查找效果也會有很大差異，匹配結(jié)果魯棒性不高；基于語義模板的匹配算法[13]，該方法基于核距離的簡單線性迭代聚類，從模板圖像中提取穩(wěn)定的超像素區(qū)域，并構(gòu)建二進(jìn)制描述符，以構(gòu)造多級語義融合特征向量，但該算法在構(gòu)建區(qū)域描述符時(shí)，需比較每個(gè)超像素區(qū)域與其相鄰像素之間的平均強(qiáng)度差，來獲得每個(gè)超像素的優(yōu)勢梯度取向。因此，時(shí)間復(fù)雜度較高，有待進(jìn)一步的優(yōu)化與改進(jìn)； 基于特征點(diǎn)平面相似性聚類的圖像拼接算法[14]，該方法依據(jù)相同平面特征點(diǎn)符合同一變換的特性，通過度量初始匹配集中對應(yīng)特征點(diǎn)的相似性，利用凝聚層次聚類把特征點(diǎn)劃分為不同平面，篩選誤匹配點(diǎn)。然后結(jié)合平面信息，通過帶權(quán)重的線性變換，計(jì)算網(wǎng)格的局部單應(yīng)性變換矩陣，最后基于此矩陣，利用多頻率融合方法拼接配準(zhǔn)圖像。但該方法對于運(yùn)動場景下變化較大的圖像配準(zhǔn)與拼接，仍存在部分適用性問題；基于幾何離群值去除的匹配算法[15]，該方法首先依據(jù)包含相同場景的兩幅圖像間特征點(diǎn)的全局相似幾何關(guān)系，建立數(shù)學(xué)模型，其次優(yōu)化模型，找到模型的最優(yōu)解，最終基于模型剔除誤匹配，但該方法在求解模型結(jié)果時(shí)，對于紋理重復(fù)對象，時(shí)間復(fù)雜度較高，不適用于大規(guī)模、實(shí)時(shí)性的視覺任務(wù)； 基于DBSCAN與互信息的圖像拼接算法[16]，該方法為保證實(shí)時(shí)性，提取ORB特征點(diǎn)，并利用DBSCAN聚類算法快速構(gòu)建鄰接圖，然后通過鄰接圖來估算圖像的重疊區(qū)域。該方法通過估算兩幅圖像間的重疊區(qū)域，進(jìn)而在重疊區(qū)域內(nèi)進(jìn)行特征匹配來提高特征點(diǎn)的匹配效率。但該方法基于原始DBSCAN聚類算法進(jìn)行對應(yīng)查找，需手動確定重疊區(qū)域，且區(qū)域范圍變化較大，難以保證匹配效果。因此，融合多種理論的特征匹配方法能夠結(jié)合對象局部結(jié)構(gòu)的相似性，對特征點(diǎn)集進(jìn)行結(jié)構(gòu)劃分并配對；但此類方法計(jì)算復(fù)雜度較高，不適用于實(shí)時(shí)場景。

然而，針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)的對象，上述特征匹配算法僅從圖像間局部特征描述信息的角度出發(fā)，進(jìn)行配對，而沒有從全局考慮特征匹配的實(shí)驗(yàn)結(jié)果。實(shí)際上，不同視角下的同一對象，檢測的圖像特征點(diǎn)往往呈現(xiàn)簇狀，且特征匹配結(jié)果在幾何上具有一致性。因此，結(jié)合圖像特征點(diǎn)的局部描述信息與特征點(diǎn)間的幾何約束，可進(jìn)一步提高特征匹配效率。

2 基礎(chǔ)定義

給定圖像I(Image)及初始半徑δ、近鄰參數(shù)K，特征提取后生成的特征點(diǎn)集合為P。進(jìn)而基于特征點(diǎn)集P，基于圖像聚類以及特征匹配方法的相關(guān)定義如下：

定義1K近鄰集KNN(p)：給定圖像I內(nèi)任意特征點(diǎn)p，KNN(p)為特征點(diǎn)p的K近鄰集合且KNN(p)滿足以下條件

?q∈KNN(p),o?KNN(p), dist(p,q)≤dist(p,o)

(1)

式中：函數(shù)dist() 計(jì)算取值為特征點(diǎn)p，q間坐標(biāo)的歐式距離。即

(2)

定義2 核心點(diǎn)C(p)：給定初始半徑δ與近鄰參數(shù)K，置特征點(diǎn)p與KNN(p)內(nèi)所有特征點(diǎn)間歐氏距離最大值為Dmax，若Dmax≤δ，則點(diǎn)p為核心點(diǎn)。

定義3 直接密度可達(dá)：特征點(diǎn)q由特征點(diǎn)p直接密度可達(dá)所滿足的條件為

?p∈C(p) ∧q∈C(q)∧q∈KNN(p)

(3)

定義4 密度可達(dá)：在圖像I中，特征點(diǎn)q由特征點(diǎn)p密度可達(dá)定義為：存在樣本序列p1,p2,…pn， 其中p1=p，pn=q， 且pi+1與pi直接密度可達(dá)。

定義5 密度相連：存在特征點(diǎn)o，使得特征點(diǎn)p和q均由o密度可達(dá)，則p與q密度相連。

定義6 噪聲點(diǎn)：動態(tài)迭代聚類延展后，生成n個(gè)聚類簇，若某特征點(diǎn)p不屬于n個(gè)聚類簇中任意一個(gè)，則認(rèn)為p點(diǎn)為數(shù)據(jù)集中噪音點(diǎn)。

定義7 匹配正確率R定義為

(4)

式中：M為正確匹配對數(shù)目，N1，N2分別為圖像IL(image left)，IR(image right)中提取出的SIFT關(guān)鍵點(diǎn)數(shù)目，R為匹配正確率。

3 本文方法

針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)的對象，基于圖像的特征匹配過程具有以下特點(diǎn)：①不同視角下，同一對象提取的特征點(diǎn)分布密集、間距小、輪廓相似且呈現(xiàn)簇狀；②在初始匹配集中，多數(shù)正確匹配與錯(cuò)誤匹配相比，鄰域信息更密，且正確匹配常位于兩幅圖像間的同一對象；③同一對象間特征點(diǎn)，其特征分布由內(nèi)及外，滿足一定的幾何約束。因此，基于上述匹配特性，本文引入基于密度的聚類思想。在局部特征信息基礎(chǔ)上，增加全局幾何約束信息，即在局部描述子的基礎(chǔ)上，通過查找圖像間的對應(yīng)區(qū)域(聚類簇)，來提高特征匹配的效率。

DBSCAN[17-19]是一種基于密度的空間聚類算法，該方法無需預(yù)先輸入聚類數(shù)量、抗噪能力強(qiáng)、能查找處理任意形狀和大小的簇；但應(yīng)用于圖像數(shù)據(jù)進(jìn)行聚類，存在以下問題：①聚類結(jié)果受輸入的相關(guān)參數(shù)影響較大，當(dāng)參數(shù)取值不同，聚類結(jié)果差異明顯。②區(qū)域內(nèi)最小值MinPts只能作為核心點(diǎn)周圍圓形區(qū)域內(nèi)的度量標(biāo)準(zhǔn)，而無法動態(tài)反映鄰域間的映射關(guān)系。③圖像采集受到光照、設(shè)備等因素影響，當(dāng)采用同一特征提取算法，提取結(jié)果會存在部分差異。因此，針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)的對象，基于DBSCAN的聚類方法所確定的對應(yīng)區(qū)域，精度較低，無法進(jìn)一步進(jìn)行特征匹配。而基于鄰域信息的KNN方法可將特征點(diǎn)間的歐氏距離映射為特征點(diǎn)間的鄰域信息，具有不依賴特定參數(shù)、表征鄰域信息，且能處理不同規(guī)模數(shù)據(jù)的優(yōu)點(diǎn)，但抗噪效果不好。

因此，結(jié)合KNN與DBSCAN思想，本文提出一種動態(tài)拓展聚類的特征匹配方法。該方法主要有3個(gè)關(guān)鍵步驟：構(gòu)建特征點(diǎn)數(shù)據(jù)集、特征聚類區(qū)域劃分、聚類簇匹配。

3.1 構(gòu)建特征點(diǎn)數(shù)據(jù)集

針對結(jié)構(gòu)復(fù)雜、紋理重復(fù)的對象，為了提高特征提取數(shù)量，本文結(jié)合SIFT思想，依據(jù)式(5)對輸入圖像I(x,y) 進(jìn)行圖像高斯模糊，依據(jù)式(6)構(gòu)建尺度空間。不同的尺度空間不僅保證了其特征提取結(jié)果具有尺度、旋轉(zhuǎn)、亮度不變性，而且還可增加特征點(diǎn)提取數(shù)目，具有計(jì)算量小，穩(wěn)定性高等優(yōu)點(diǎn)

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

(5)

構(gòu)建尺度空間時(shí)，所需高斯模糊差值為式(6)

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

(6)

輸入兩幅待匹配圖像IL(x,y)，IR(x,y)， 并分別采用SIFT算子提取特征，可獲得基礎(chǔ)數(shù)據(jù)集SD1，SD2。其中，SD1,2中的每一特征點(diǎn)坐標(biāo)可描述為p(px，py)， 來表示特征點(diǎn)p的幾何坐標(biāo)信息。

3.2 特征聚類區(qū)域劃分

構(gòu)建特征點(diǎn)數(shù)據(jù)集后，依據(jù)特征點(diǎn)間幾何信息，確定圖像聚類簇。針對任一圖像IL，聚類過程為：

(1)輸入基礎(chǔ)數(shù)據(jù)集SD1，依據(jù)給定參數(shù)K與半徑參數(shù)δ，由定義1和定義2，確定圖像IL中的核心點(diǎn)與非核心點(diǎn)，并確定所有核心點(diǎn)的半徑Dmax；

(2)針對圖像IL內(nèi)的任一核心點(diǎn)p，依據(jù)參數(shù)Dmax，在圖像IL中，每點(diǎn)所在區(qū)域可劃分為3種圓形區(qū)域(circle region，CR)：核心區(qū)域、漸進(jìn)區(qū)域、邊界區(qū)域。具體定義如下：①核心區(qū)域(kernal region，KR)：依據(jù)定義2，以任一核心點(diǎn)p為圓心，Dmax為半徑確定圓形區(qū)域CR(p)，若CR(p)內(nèi)特征點(diǎn)全為核心點(diǎn)，則該區(qū)域?yàn)辄c(diǎn)p核心區(qū)域，記為KR(p)；②漸進(jìn)區(qū)域(progressive region，PR)：依據(jù)定義2，核心點(diǎn)p確定的圓形區(qū)域CR(p)內(nèi)，部分特征點(diǎn)為核心點(diǎn)，此時(shí)，點(diǎn)p所在區(qū)域?yàn)闈u進(jìn)區(qū)域，記為PR(p)；③邊界區(qū)域(boundary region，BR)：依據(jù)定義2，核心點(diǎn)p確定的圓形區(qū)域CR(p)內(nèi)，沒有核心點(diǎn)，此時(shí)，點(diǎn)p所在區(qū)域?yàn)檫吔鐓^(qū)域，記為BR(p)。

(3)基于上述區(qū)域，對不同區(qū)域內(nèi)特征點(diǎn)，進(jìn)行分類拓展，拓展條件為：①若核心點(diǎn)p所在區(qū)域?yàn)楹诵膮^(qū)域，此區(qū)域內(nèi)核心點(diǎn)不做處理，與點(diǎn)p無約束關(guān)系，直接列入核心隊(duì)列，且標(biāo)注p點(diǎn)類別，進(jìn)行下次拓展。(函數(shù)2)；②若核心點(diǎn)p所在區(qū)域?yàn)闈u進(jìn)區(qū)域，此區(qū)域內(nèi)核心點(diǎn)q與點(diǎn)p間存在約束關(guān)系，即Dmax(q)≤Dmax(p)*1.5。 若滿足上述約束，才列入核心隊(duì)列，并標(biāo)注p點(diǎn)類別。否則，只標(biāo)注p點(diǎn)類別。而非核心點(diǎn)直接標(biāo)注p點(diǎn)類別。(函數(shù)3)；③若核心點(diǎn)p所在區(qū)域?yàn)檫吔鐓^(qū)域，此區(qū)域內(nèi)雖無核心點(diǎn)，但非核心點(diǎn)q與點(diǎn)p間存在約束關(guān)系，即Dmax(q)≤Dmax(p)*2.0。 若滿足約束，才標(biāo)注p點(diǎn)類別。當(dāng)聚類初始時(shí)，點(diǎn)p便位于邊界區(qū)域，則跳過此點(diǎn)，隨機(jī)選取下一核心點(diǎn)。(函數(shù)4)。

依據(jù)上述過程，針對圖像IL，基于KNN和DBSCAN的聚類算法KD可描述為：

算法1：KD聚類

輸入：SD1、 (δ，K) // |SD1|=N

輸出： (p，cluster) //每一個(gè)特征點(diǎn)的聚類結(jié)果

(1)queue= null //初始核心隊(duì)列置為空

(2)p∈SD1：p= unclassified，p= unvisited

(3)cluster= 0 //初始類別標(biāo)為0

(4)KNN(p) (p∈SD1)//各點(diǎn)的K近鄰集合

(5)Dmax(p) (p∈SD1)//各點(diǎn)的可變半徑

(6)CR(p) (p∈SD1)//各點(diǎn)所標(biāo)定的圓形區(qū)域

(7)for(p∈SD1)do

(8) ifp== unclassified then

(9) ifDmax(p) ≤δthen

(10)cluster=cluster+1 //類別加1

(11) classify(p,cluster,Dmax(p))//函數(shù)1

(12) end if

(13) end if

(14)end for

函數(shù)1： Function classify(p,cluster,Dmax(p))

說明： 基于核心點(diǎn)p的分類處理

輸入：p、cluster、Dmax(p)

輸出：clusters//基于點(diǎn)p生成的聚類簇

(1)ifCR(p)∈KR(p) then

(2)p= visited

(3)cluster(p) =cluster//當(dāng)前類別賦予點(diǎn)p

(4) assignKR(cluster,p,Dmax(p))//函數(shù)2

(5)else ifCR(p)∈PR(p) then

(6)p= visited

(7)cluster(p) =cluster

(8) assignPR(cluster,p,Dmax(p))//函數(shù)3

(9)else ifCR(p)∈BR(p) then

(10) ifp== unvisited then //若聚類初始，核心點(diǎn)位于BR內(nèi)，跳過此點(diǎn)

(11)cluster=cluster-1

(12) continue

(13) else //聚類延展，遇到BR內(nèi)核心點(diǎn)

(14) assignBR(cluster,p,Dmax(p))//函數(shù)4

(15) end if

(16)end if

函數(shù)2： Function assignKR(cluster,p,Dmax(p))

說明： 遍歷點(diǎn)p核心區(qū)域內(nèi)數(shù)據(jù)， 聚類延展

輸入：cluster,p,Dmax(p)

輸出：clusters

(1)forq∈KR(p) do

(2) ifq== unclassified then

(3)cluster(q) =cluster

(4)queue=queue∪q

(5) end if

(6)end for

(7)fore∈queuedo

(8) ife== unvisited then

(9)e= visited

(10) classify(e,cluster,Dmax(e))

(11) end if

(12)end for

函數(shù)3： Function assignPR(cluster,p,Dmax(p))

說明： 遍歷點(diǎn)p漸進(jìn)區(qū)域內(nèi)數(shù)據(jù)， 聚類延展

輸入：cluster,p,Dmax(p)

輸出：clusters

(1)forq∈PR(p) do

(2) ifq== unclassified then

(3)cluster(q) =cluster

(4) ifDmax(q)≤δthen //q為核心點(diǎn)

(5) ifDmax(q)≤Dmax(p) * 1.5 then

(6)queue=queue∪q

(7) end if

(8) end if

(9) end if

(10)end for

(11)fore∈queuedo

(12) ife== unvisited then

(13)e= visited

(14) classify(e,cluster,Dmax(e))

(15) end if

(16)end for

函數(shù)4： Function assignBR(cluster,p,Dmax(p))

說明： 遍歷點(diǎn)p邊界區(qū)域內(nèi)數(shù)據(jù)， 聚類不延展

輸入：cluster,p,Dmax(p)

輸出：clusters

(1)forq∈BR(p) do //此處不導(dǎo)入數(shù)據(jù)到queue

(2) ifDmax(q) ≤Dmax(p) * 2.0 then

(3) ifq== unclassified then

(4)cluster(q) =cluster

(5) end if

(6) end if

(7)end for

3.3 聚類簇匹配

輸入兩幅圖像IL，IR，分別采用KD聚類算法生成相應(yīng)聚類簇后，下一步需要確定兩幅圖像間的對應(yīng)相似簇，即同一對象。兩簇間的相似性度量依據(jù)如下兩個(gè)參數(shù)：

(1)簇內(nèi)距離D：任給圖像的某一簇A，則A的簇內(nèi)距離定義為：簇A中所有核心點(diǎn)間歐氏距離最大值，記為AD，簇B則為BD。

(2)簇密度N：任給圖像的某一簇A，則簇A密度定義為：簇內(nèi)特征點(diǎn)個(gè)數(shù)，記為AN，簇B則為BN。

從上述兩個(gè)參數(shù)出發(fā)，兩幅圖像間相似因子SE可定義為：

設(shè)圖像IL的簇A，簇內(nèi)距離為ADIL，簇密度為ANIL，任取圖像IR的簇B，簇內(nèi)距離為BDIR，簇密度為BNIR，下標(biāo)為圖像標(biāo)號，則簇A、簇B間相似因子SEA,B定義為式(7)

SEA,B=ADIL/BDIR+ANIL/BNIR

(7)

理想狀態(tài)下，兩簇間相似因子SE取值為2。因此，任意兩簇間的比值SE越接近于2，則越相似。

取圖像IL中任意簇A，計(jì)算圖像IR中與簇A最相似的簇B、次相似的簇C。若簇A、B滿足式(8)，則認(rèn)為兩簇為同一對象

MS(A,B)=SEA,B/SEA,C≤0.8

(8)

最相似函數(shù)MS()為兩幅圖像間，聚類簇度量函數(shù)。

3.4 算法設(shè)計(jì)

基于上述過程，設(shè)計(jì)了一種基于KNN與DBSCAN聚類的動態(tài)拓展匹配算法KN_DB：匹配算法的基本流程如下所示：

輸入：圖像IL、IR

輸出：特征匹配結(jié)果匹配對數(shù)目M

(1)對圖像IL、IR構(gòu)建尺度空間，生成SIFT特征點(diǎn)數(shù)據(jù)集SD1,2；

(2)依據(jù)KD算法，分別確定圖像IL、IR的聚類結(jié)果；

(3)依據(jù)度量函數(shù)MS，確定圖像IL、IR間對應(yīng)聚類簇；

(4)找到圖像IL、IR間對應(yīng)聚類簇后，依據(jù)對應(yīng)簇內(nèi)特征點(diǎn)坐標(biāo)，構(gòu)建其SIFT描述子，并采用最近鄰次近鄰原則輸出特征匹配結(jié)果，得到匹配數(shù)M；

3.5 復(fù)雜度分析

特征匹配算法KN_DB主要包括3個(gè)主要步驟：K近鄰計(jì)算，類DBSCAN的聚類簇生成，查找對應(yīng)簇并匹配。其中，為方便表述，SD1,2內(nèi)的數(shù)據(jù)總數(shù)均為N。

對于某次K近鄰計(jì)算，它需要為SD中的每個(gè)樣本，通過KD樹，查找K個(gè)最近鄰的鄰居，其時(shí)間復(fù)雜度接近O(NlogN)。

而聚類簇生成，首先需要確定核心點(diǎn)，劃分區(qū)域，并構(gòu)造核心隊(duì)列，然后，遍歷核心隊(duì)列，開始延展聚類，生成聚類簇，它的時(shí)間復(fù)雜度近似為O(NK)。

在最后查找對應(yīng)簇并匹配中，其時(shí)間復(fù)雜度近似為O(N/K)2。因此，本文算法總的時(shí)間復(fù)雜度約為O(NK)+O(NlogN)+O(N/K)2。

4 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法KN_DB的精確性與魯棒性，采用Oxford VGG標(biāo)準(zhǔn)數(shù)據(jù)集(Paris、Wall、Leuven)、中科院三維重建數(shù)據(jù)集[21]為對象進(jìn)行驗(yàn)證。實(shí)驗(yàn)環(huán)境為：Windows 10操作系統(tǒng)，英特爾Core i7-8750H @ 2.20 GHz 六核處理器，8 G內(nèi)存。采用Matlab編程語言，計(jì)算機(jī)視覺庫Opencv3.4.5。

4.1 聚類效果

以O(shè)xford VGG Paris標(biāo)準(zhǔn)數(shù)據(jù)集為對象，提取SIFT關(guān)鍵點(diǎn)，分別實(shí)現(xiàn)KD、DBSCAN[17]、Kmeans[20]算法，聚類參數(shù)分別設(shè)置為：①KD：δ=5，K=10；②DBSCAN：δ=5，MinPts=15；③Kmeans：K=9。聚類效果如圖1所示。

圖1 聚類效果

從圖1可以看出：KD聚類算法，基于核心點(diǎn)的KNN鄰域信息，劃分3種區(qū)域，并逐層約束，可以有效且準(zhǔn)確的將圖像區(qū)域內(nèi)各對象限制在其本身范圍，即對象內(nèi)，數(shù)據(jù)分布均勻，對象間，邊界界限清晰。DBSCAN聚類算法，僅基于固定參數(shù)δ與MinPts，標(biāo)定核心點(diǎn)，進(jìn)行聚類。此種方式，固化鄰域信息，無法動態(tài)反映數(shù)據(jù)間分布，在圖1顯示效果為，僅能生成部分聚類簇，無法標(biāo)定對象整體區(qū)域。Kmeans聚類算法，預(yù)先輸入K值，僅依據(jù)歐式距離，通過迭代質(zhì)心，來劃分類別。此種方式在圖1聚類效果為，不同對象被劃分成一類。

4.2 參數(shù)設(shè)置

KD聚類算法主要有兩個(gè)參數(shù)：半徑δ與參數(shù)K。而不同的參數(shù)取值下，聚類效果見表1。其中，表1中簇內(nèi)距離表示為當(dāng)前參數(shù)取值下，各簇簇內(nèi)距離D的均值。

表1 聚類效果分布

從表1可以看出，隨著參數(shù)K與半徑δ取值逐漸增大，鄰域信息逐漸拓展，聚類簇?cái)?shù)目逐漸減少，而簇內(nèi)距離逐漸增大。在實(shí)際匹配中，因圖像內(nèi)對象數(shù)目相對有限，針對不同圖像，選擇能較好表示圖像中各對象數(shù)目的K值與δ值就成為影響KD算法性能的一個(gè)關(guān)鍵因素。

經(jīng)多次實(shí)驗(yàn)，針對像素大小為500*300的圖像，K值確定方式為式(9)，N為SD中特征點(diǎn)的數(shù)目，且N*0.05所得數(shù)值向下取整

(9)

半徑δ確定方式為式(10)，此時(shí)，依據(jù)定義2，求出各個(gè)特征點(diǎn)的最大半徑Dmax，然后，從這些最大半徑中，找出最大與最小，再進(jìn)行計(jì)算，求出半徑δ

δ=0.1*(max{Dmax}-min{Dmax})+min{Dmax}

(10)

4.3 特征匹配結(jié)果與分析

(1)Oxford VGG標(biāo)準(zhǔn)數(shù)據(jù)集

為評估效果，從Oxford VGG數(shù)據(jù)集內(nèi)，選取標(biāo)準(zhǔn)圖像作為實(shí)驗(yàn)對象，采用KN_DB、GMS[6]、ORB[9]等幾類特征匹配算法進(jìn)行驗(yàn)證。其中，Oxford VGG數(shù)據(jù)集內(nèi)示例圖像如圖2所示。

圖2 數(shù)據(jù)集內(nèi)圖像

標(biāo)準(zhǔn)數(shù)據(jù)集匹配結(jié)果如圖3所示。其中，圖3(a)～圖3(c)為Wall中的圖片，用以驗(yàn)證旋轉(zhuǎn)變化；圖3(d)～圖3(f)為Paris中的圖片，用以驗(yàn)證尺度變化；圖3(g)～圖3(i)所選圖片為Leuven中的圖片，用以驗(yàn)證光照變化。圖3為分別采用KN_DB、GMS、ORB等算法進(jìn)行特征匹配。標(biāo)準(zhǔn)數(shù)據(jù)集匹配結(jié)果量化描述見表2。

表2 匹配數(shù)據(jù)分布

圖3 匹配效果

由圖3可以看出：算法KN_DB在圖像發(fā)生旋轉(zhuǎn)、光照變化等情況下，能通過逐層約束，穩(wěn)定找到圖像間各對應(yīng)區(qū)域，匹配準(zhǔn)確率較高，適用性較強(qiáng)。GMS算法在圖像發(fā)生旋轉(zhuǎn)、光照變化時(shí)，匹配效果較好，但在圖像發(fā)生尺度變化時(shí)，雖能提取較多特征點(diǎn)，但正確匹配率較低。ORB算法在3種圖像變化中，通過暴力匹配來處理圖像，錯(cuò)誤匹配率較高，匹配效果不理想。

由表2可以看出：由于ORB算法采用FAST算子檢測關(guān)鍵點(diǎn)，并基于二進(jìn)制描述子，進(jìn)行暴力匹配，因此匹配時(shí)間最短，但正確率R最低。算法KN_DB采用SIFT算子，構(gòu)建高斯尺度空間，提取特征點(diǎn)，所用時(shí)間較多，但基于同一對象進(jìn)行匹配，效果穩(wěn)定，故正確率R最高。GMS算法提取ORB基礎(chǔ)特征點(diǎn)，并基于網(wǎng)格，依據(jù)運(yùn)動平滑性，認(rèn)為正確匹配點(diǎn)相對錯(cuò)誤匹配點(diǎn)，其鄰域內(nèi)有較多正確匹配點(diǎn)，進(jìn)行匹配。提取特征點(diǎn)數(shù)目較多，但需通過比較匹配點(diǎn)鄰域信息進(jìn)行特征統(tǒng)計(jì)，所以時(shí)間最多，但正確率R居中。

為了評估本文算法的有效性，以定義7，匹配正確率R為評價(jià)指標(biāo)，在Oxford VGG標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行特征匹配。經(jīng)過多次實(shí)驗(yàn)驗(yàn)證，本文算法的匹配平均正確率R保持在92.85%，說明該方法在圖像發(fā)生旋轉(zhuǎn)、尺度等變化時(shí)，仍具有較好的魯棒性，且從前面的實(shí)驗(yàn)結(jié)果可以看出，本文算法相對于近幾年提出的GMS、ORB算法來說，匹配準(zhǔn)確率較高，魯棒性較強(qiáng)。

(2)中科院三維重建數(shù)據(jù)集

為驗(yàn)證本文算法KN_DB的魯棒性，本節(jié)依據(jù)中科院三維重建數(shù)據(jù)集中的青城山、武當(dāng)山、五臺山，并采用KN_DB、SIFT+RANSAC[7]、GMS、SURF+RANSAC[8]、ORB等5種算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖4、圖5所示。其中圖4為匹配正確率分布，圖5為匹配時(shí)間分布。

圖4 匹配正確率分布

圖5 匹配時(shí)間分布

由圖4、圖5可以看出，SIFT算法基于圖像整體區(qū)域，提取特征，構(gòu)建描述子，計(jì)算相似性，尋找對應(yīng)點(diǎn)，所需時(shí)間最多，匹配正確率較低。而SURF算法在求主方向階段時(shí)太過依賴局部區(qū)域像素的梯度方向，雖相對SIFT算法采用積分圖加速計(jì)算，所需時(shí)間減少，但穩(wěn)定性不高。本文算法雖基于SIFT描述子，但不用遍歷全圖，只需在兩幅圖像間，計(jì)算對應(yīng)區(qū)域內(nèi)特征相似性，減少了匹配時(shí)間，提高了匹配效率。

5 結(jié)束語

針對紋理重復(fù)、結(jié)構(gòu)復(fù)雜的對象，為了提高特征匹配的精確性與魯棒性，本文結(jié)合KNN與DBSCAN思想，提出了一種基于動態(tài)拓展的特征匹配算法KN_DB。該算法依據(jù)圖像特征點(diǎn)間幾何信息，首先構(gòu)建特征點(diǎn)的最近鄰鄰域集合，來描述特征點(diǎn)鄰域信息；其次，基于DBSCAN聚類半徑，標(biāo)定核心點(diǎn)，確定特征點(diǎn)拓展條件，形成特征點(diǎn)聚類簇；然后，從聚類簇內(nèi)，采用相似度量函數(shù)進(jìn)行特征匹配；最后，采用標(biāo)準(zhǔn)數(shù)據(jù)集與古建筑數(shù)據(jù)集為對象驗(yàn)證算法KN_DB的效率。實(shí)驗(yàn)結(jié)果表明，本文方法在圖像發(fā)生旋轉(zhuǎn)、尺度等變化時(shí)，匹配平均正確率保持在92.85%左右。然而，針對像素較大的圖像，本文算法存在參數(shù)不穩(wěn)定的情況，因此，下一步將結(jié)合聚類區(qū)域密度分布差異，研究參數(shù)確定模型。