基于動態拓展的特征匹配方法

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

(太原科技大學 計算機科學與技術學院，山西 太原 030024)

0 引 言

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

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

1 相關研究

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

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

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

2 基礎定義

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

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

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

(1)

式中：函數dist() 計算取值為特征點p，q間坐標的歐式距離。即

(2)

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

定義3 直接密度可達：特征點q由特征點p直接密度可達所滿足的條件為

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

(3)

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

定義5 密度相連：存在特征點o，使得特征點p和q均由o密度可達，則p與q密度相連。

定義6 噪聲點：動態迭代聚類延展后，生成n個聚類簇，若某特征點p不屬于n個聚類簇中任意一個，則認為p點為數據集中噪音點。

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

(4)

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

3 本文方法

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

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

因此，結合KNN與DBSCAN思想，本文提出一種動態拓展聚類的特征匹配方法。該方法主要有3個關鍵步驟：構建特征點數據集、特征聚類區域劃分、聚類簇匹配。

3.1 構建特征點數據集

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

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

(5)

構建尺度空間時，所需高斯模糊差值為式(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算子提取特征，可獲得基礎數據集SD1，SD2。其中，SD1,2中的每一特征點坐標可描述為p(px，py)， 來表示特征點p的幾何坐標信息。

3.2 特征聚類區域劃分

構建特征點數據集后，依據特征點間幾何信息，確定圖像聚類簇。針對任一圖像IL，聚類過程為：

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

(2)針對圖像IL內的任一核心點p，依據參數Dmax，在圖像IL中，每點所在區域可劃分為3種圓形區域(circle region，CR)：核心區域、漸進區域、邊界區域。具體定義如下：①核心區域(kernal region，KR)：依據定義2，以任一核心點p為圓心，Dmax為半徑確定圓形區域CR(p)，若CR(p)內特征點全為核心點，則該區域為點p核心區域，記為KR(p)；②漸進區域(progressive region，PR)：依據定義2，核心點p確定的圓形區域CR(p)內，部分特征點為核心點，此時，點p所在區域為漸進區域，記為PR(p)；③邊界區域(boundary region，BR)：依據定義2，核心點p確定的圓形區域CR(p)內，沒有核心點，此時，點p所在區域為邊界區域，記為BR(p)。

(3)基于上述區域，對不同區域內特征點，進行分類拓展，拓展條件為：①若核心點p所在區域為核心區域，此區域內核心點不做處理，與點p無約束關系，直接列入核心隊列，且標注p點類別，進行下次拓展。(函數2)；②若核心點p所在區域為漸進區域，此區域內核心點q與點p間存在約束關系，即Dmax(q)≤Dmax(p)*1.5。 若滿足上述約束，才列入核心隊列，并標注p點類別。否則，只標注p點類別。而非核心點直接標注p點類別。(函數3)；③若核心點p所在區域為邊界區域，此區域內雖無核心點，但非核心點q與點p間存在約束關系，即Dmax(q)≤Dmax(p)*2.0。 若滿足約束，才標注p點類別。當聚類初始時，點p便位于邊界區域，則跳過此點，隨機選取下一核心點。(函數4)。

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

算法1：KD聚類

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

輸出： (p，cluster) //每一個特征點的聚類結果

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

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

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

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

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

(6)CR(p) (p∈SD1)//各點所標定的圓形區域

(7)for(p∈SD1)do

(8) ifp== unclassified then

(9) ifDmax(p) ≤δthen

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

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

(12) end if

(13) end if

(14)end for

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

說明： 基于核心點p的分類處理

輸入：p、cluster、Dmax(p)

輸出：clusters//基于點p生成的聚類簇

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

(2)p= visited

(3)cluster(p) =cluster//當前類別賦予點p

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

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

(6)p= visited

(7)cluster(p) =cluster

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

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

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

(11)cluster=cluster-1

(12) continue

(13) else //聚類延展，遇到BR內核心點

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

(15) end if

(16)end if

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

說明： 遍歷點p核心區域內數據， 聚類延展

輸入：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

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

說明： 遍歷點p漸進區域內數據， 聚類延展

輸入：cluster,p,Dmax(p)

輸出：clusters

(1)forq∈PR(p) do

(2) ifq== unclassified then

(3)cluster(q) =cluster

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

(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

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

說明： 遍歷點p邊界區域內數據， 聚類不延展

輸入：cluster,p,Dmax(p)

輸出：clusters

(1)forq∈BR(p) do //此處不導入數據到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聚類算法生成相應聚類簇后，下一步需要確定兩幅圖像間的對應相似簇，即同一對象。兩簇間的相似性度量依據如下兩個參數：

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

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

從上述兩個參數出發，兩幅圖像間相似因子SE可定義為：

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

SEA,B=ADIL/BDIR+ANIL/BNIR

(7)

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

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

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

(8)

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

3.4 算法設計

基于上述過程，設計了一種基于KNN與DBSCAN聚類的動態拓展匹配算法KN_DB：匹配算法的基本流程如下所示：

輸入：圖像IL、IR

輸出：特征匹配結果匹配對數目M

(1)對圖像IL、IR構建尺度空間，生成SIFT特征點數據集SD1,2；

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

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

(4)找到圖像IL、IR間對應聚類簇后，依據對應簇內特征點坐標，構建其SIFT描述子，并采用最近鄰次近鄰原則輸出特征匹配結果，得到匹配數M；

3.5 復雜度分析

特征匹配算法KN_DB主要包括3個主要步驟：K近鄰計算，類DBSCAN的聚類簇生成，查找對應簇并匹配。其中，為方便表述，SD1,2內的數據總數均為N。

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

而聚類簇生成，首先需要確定核心點，劃分區域，并構造核心隊列，然后，遍歷核心隊列，開始延展聚類，生成聚類簇，它的時間復雜度近似為O(NK)。

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

4 實驗結果

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

4.1 聚類效果

以Oxford VGG Paris標準數據集為對象，提取SIFT關鍵點，分別實現KD、DBSCAN[17]、Kmeans[20]算法，聚類參數分別設置為：①KD：δ=5，K=10；②DBSCAN：δ=5，MinPts=15；③Kmeans：K=9。聚類效果如圖1所示。

圖1 聚類效果

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

4.2 參數設置

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

表1 聚類效果分布

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

經多次實驗，針對像素大小為500*300的圖像，K值確定方式為式(9)，N為SD中特征點的數目，且N*0.05所得數值向下取整

(9)

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

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

(10)

4.3 特征匹配結果與分析

(1)Oxford VGG標準數據集

為評估效果，從Oxford VGG數據集內，選取標準圖像作為實驗對象，采用KN_DB、GMS[6]、ORB[9]等幾類特征匹配算法進行驗證。其中，Oxford VGG數據集內示例圖像如圖2所示。

圖2 數據集內圖像

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

表2 匹配數據分布

圖3 匹配效果

由圖3可以看出：算法KN_DB在圖像發生旋轉、光照變化等情況下，能通過逐層約束，穩定找到圖像間各對應區域，匹配準確率較高，適用性較強。GMS算法在圖像發生旋轉、光照變化時，匹配效果較好，但在圖像發生尺度變化時，雖能提取較多特征點，但正確匹配率較低。ORB算法在3種圖像變化中，通過暴力匹配來處理圖像，錯誤匹配率較高，匹配效果不理想。

由表2可以看出：由于ORB算法采用FAST算子檢測關鍵點，并基于二進制描述子，進行暴力匹配，因此匹配時間最短，但正確率R最低。算法KN_DB采用SIFT算子，構建高斯尺度空間，提取特征點，所用時間較多，但基于同一對象進行匹配，效果穩定，故正確率R最高。GMS算法提取ORB基礎特征點，并基于網格，依據運動平滑性，認為正確匹配點相對錯誤匹配點，其鄰域內有較多正確匹配點，進行匹配。提取特征點數目較多，但需通過比較匹配點鄰域信息進行特征統計，所以時間最多，但正確率R居中。

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

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

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

圖4 匹配正確率分布

圖5 匹配時間分布

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

5 結束語

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