基于局部聚類的特征匹配篩選算法①

王金寶,趙 奎,劉 閩,宗子瀟,王其樂

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110168)

3(沈陽市環(huán)境監(jiān)測中心站,沈陽 110016)

4(東北大學(xué) 計算機科學(xué)與工程學(xué)院,沈陽 110004)

5(沈陽市第三十一中學(xué),沈陽 110021)

特征點匹配即對2幅圖像中具有相同或者相似特征的關(guān)鍵點進行匹配,是圖像拼接、計算機視覺識別等技術(shù)的關(guān)鍵環(huán)節(jié)[1],在全景融合、監(jiān)控、直播及三維仿真等領(lǐng)域有著重要應(yīng)用.但特征點匹配算法基本都或多或少的存在誤匹配,現(xiàn)階段主要通過相關(guān)匹配篩選算法來進行處理,其中比較著名的有隨機抽樣一致性算法(RANSAC),該算法通過利用求解變換矩陣和改進最小二乘法來進行特征點對的匹配篩選.但該算法存在受迭代次數(shù)影響大,自適應(yīng)性差,對匹配數(shù)量缺少約束,隨匹配點對增長計算量暴增等缺陷.基于以上不足,本文從特征匹配點對局部聚類的角度出發(fā),提出了局部聚類的特征匹配篩選算法(LCMF),提高篩選效率.

為驗證LCMF的性能,首先對圖像進行特征提取和匹配,SIFT算法作為最經(jīng)典的特征提取算法有著廣泛的應(yīng)用[2–4],但其發(fā)布時間久遠,后來基于其算法有著大量的改進算法.本文選取偏重質(zhì)量的SIFT的升級版算法SURF和較新的偏重于效率的ORB算法進行特征提取,使用比較常用的最鄰近算法進行特這個匹配.

1 特征提取與特征匹配

本文采用SURF和ORB分別進行特征提取,采用最鄰近匹配算法進行特征匹配.

1.1 SURF與ORB

SURF[5–8],即 Speed Up Robust Feature,是一種加速版的SIFT,2006年被提出.與SIFT算法的主要區(qū)別在于:

(1)提出了盒子濾波矩陣的概念,構(gòu)建尺度空間.

(2)Hessian 矩陣求極值點.

積分圖像定義為原圖像左上角到點X構(gòu)成的矩形區(qū)域中像素的灰度和,對于圖1的M區(qū)域計算積分圖像,只需做如公式(1)運算即可:

圖1 積分圖像

盒式濾波器是積分圖像的一種快速計算,可以將時間復(fù)雜度從O(mn)降到O(1),對于圖2,具體過程如下:

圖2 盒式濾波器

(1)n×m為盒式濾波器尺寸,先建立 1×M的緩沖區(qū);

(2)計算M次n×1區(qū)域的積分圖像存入緩沖區(qū);

(3)計算緩沖區(qū)開始1×M區(qū)域的和,隨濾波器的移動,后續(xù)只需要前后的一加一減操作;

(4)當(dāng)濾波器換行時,先通過上下的一加一減操作更新緩沖區(qū),重復(fù)上述過程.

SURF算法利用Hessian矩陣來判斷極值,Hessian矩陣定義:

Hessian矩陣判別式:

根據(jù)H判別式的正負可以判斷極值點,SURF算法并不是直接計算H的,而是通過一些優(yōu)化來計算的.

SURF算法和SIFT算法很相似,但速度明顯高于SIFT算法,約為3倍左右[5].

ORB[9],即 Oriented FAST and Rotated BRIEF,是基于FAST和BRIEF算法的一種特征提取算法,于2011年被首次提出,在專利方面不同于SIFT與SURF,可自由使用.ORB算法更關(guān)注實時性,速度快于SIFT與SURF,但特征提取質(zhì)量略差于SIFT與SURF.

ORB算法在FAST和BRIEF的基礎(chǔ)上主要做了以下改進和處理:

(1)為FAST算法增加了特征方向.

(2)使用帶方向的BRIEF算法對描述子進行處理[10].

(3)帶方向的BRIEF特征方差和相關(guān)性分析.

(4)具有旋轉(zhuǎn)不變性的去相關(guān)BRIEF算法.

1.2 最鄰近匹配

經(jīng)過特征提取處理后獲得了關(guān)鍵點的描述子,對同一個人描述子進行匹配,一般可以得到多個匹配結(jié)果.計算互相匹配的關(guān)鍵點間的歐式幾何距離,選擇其中最小的d1與次小的d2,設(shè)置閾值β,若其關(guān)系滿足公式d1/d2＜β,則認(rèn)為是正確的匹配,保留結(jié)果,此算法即為最近鄰匹配算法.

2 RANSAC 與 LCMF

在對特征點匹配時,受相機參數(shù)、光影等外在影響以及特征提取、特征匹配算法等內(nèi)在影響,一般會導(dǎo)致較多的誤匹配,需要對匹配的點對進行篩選.現(xiàn)應(yīng)用較廣泛的篩選算法有RANSAC等,但其存在諸多不足.本文基于局部聚類的思想,提出了局部聚類匹配篩選算法(LCMF).

2.1 RANSAC

最小二乘法擬合易受缺陷數(shù)據(jù)影響,產(chǎn)生偏離實際的擬合結(jié)果,RANSAC算法針對此問題進行了算法改善,具體步驟為[11,12]:

再次，集中管制力度弱，缺乏有效的內(nèi)部控制。一般來說，國有企業(yè)內(nèi)部的層次相對較多，其投資的權(quán)利也是層層下放，并且缺乏統(tǒng)一的金內(nèi)部控制標(biāo)準(zhǔn)，財務(wù)管制薄弱，導(dǎo)致難以實施科學(xué)有效的內(nèi)部監(jiān)控手段。

(1)隨機選取4對匹配點,計算變換矩陣H;

(2)利用H計算預(yù)期點位,計算誤差;

(3)統(tǒng)計σ誤差范圍內(nèi)的內(nèi)點數(shù)M;

(4)迭代上述過程;

(5)選取內(nèi)點數(shù)最多的作為算法結(jié)果.

RANSAC算法與最小二乘法相比,具有更高的魯棒性,更易于找到理想擬合.但其缺陷也很明顯:

(1)迭代次數(shù)不易控制,預(yù)設(shè)定可能得不到理想結(jié)果;

(3)只能篩選正確匹配,無法對匹配數(shù)量進行約束;

(4)隨著點對的增加,計算量呈爆炸式增長.

2.2 LCMF

針對RANSAC算法存在的問題,本文提出了一種完全不同的,復(fù)雜度遠低于RANSAC的篩選算法.

圖像融合基于局部相似性原理,因此正確的圖像特征匹配對具有局部聚類的特性,但傳統(tǒng)的二維點聚類算法時間復(fù)雜度高、隨著匹配點對的增多計算量指數(shù)式增長,無法適用于圖像融合匹配點對的篩選.針對圖像融合的特殊性,將聚類模型簡化為圖3.

圖3 聚類模型簡化圖

對于常規(guī)的矩形圖像,將圖像劃分為9部分,對于可以進行圖像融合的2幅圖像存在以下約束:

(1)至多存在6塊圖像區(qū)域具有完全相同的圖像特征.

(2)至少存在1塊區(qū)域存在局部或完全相似.

另外,理論上2幅圖像具有4對以上不共線的特征點匹配就可以進行圖像融合,因此特征點聚類可以丟失信息,為不完全的聚類,如圖3,若特征點匹配點對集中在塊4和5的填色區(qū)域,聚類時可以只保留塊5中紅色區(qū)域舍棄塊4中相連填色區(qū)域.

基于以上思想,LCMF具體算法步驟如下:

算法 1.LCMF 算法1)將進行過特征匹配的兩幅圖像M1,M2各自劃分為9各區(qū)域,統(tǒng)計各區(qū)域內(nèi)匹配特征點的數(shù)目C1,C2,…,C9;2)對C1,C2,…,C9 進行排序,得到遞減序列Cx,首元素為Cx1;3)若Cx1＜25,調(diào)用 RANSAC 算法;4)建立集合 Ω=Cx1;5)若Cx(i)/Cx(i+1)＜5,{Ω=ΩUCx(i+1),i++};6)若Cx1＜50,跳到 9);7)將Ω空間元素區(qū)域繼續(xù)劃分為9個子區(qū)域,迭代一次上述過程,最終得到至多81個元素的Ω={Cy(i)};8)對 Ω 集合元素求和,若∑Ω＞150,計算β=∑Ω/150,設(shè)置隨機因子α,使刪除比例γ=(β–1)/β,進行分塊隨機刪除匹配特征點;9)重新掃描M1、M2,若M1 中匹配特征點已被刪除,則刪除M2 中對應(yīng)點,若M1中匹配特征點已被刪除,也同樣刪除M2中對應(yīng)點;10)更新集合 Z,Z 集合元素數(shù)Cz應(yīng)滿足Cz＜150;11)結(jié)束算法,進行后續(xù)處理.

與RANSAC算法相比,該算法的優(yōu)勢在于:

(1)單步計算速度更快.

(2)計算規(guī)模降低,本算法將圖像劃分為9*9塊,使用迭代式計算,簡化計算過程.

(3)對匹配結(jié)果數(shù)量進行約束,選取閾值 150,兼顧效果與效率,具有自適應(yīng)性.

但當(dāng)匹配結(jié)果過少時,該算法不起作用,因此通過在步驟3)中判斷匹配點過少時,調(diào)用RANSAC算法來解決此問題.實際使用時,該過程被觸發(fā)幾率較低,即使進行RANSAC計算,計算量也很小,因此該算法在所有情況下都具有較好的自適應(yīng)性.

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

3.1 實驗環(huán)境

實驗環(huán)境如下:操作系統(tǒng)版本W(wǎng)in10,處理器i3 4150,內(nèi)存 8 GB,OpenCV 庫版本 3.3.1.

3.2 匹配篩選

圖4中4幅圖像為圖像融合處理實驗中使用的圖像.

圖5是利用SURF算法提取的特征點,圖6是利用ORB算法提取的特征點,由圖可知,同一圖像,SURF算法一般可以獲得更多的特征點.另外,理論上只是匹配點具有局部聚類特征,但從圖中發(fā)現(xiàn)ORB算法獲取的特征點也具有局部聚類特征,這可能與FAST算法本身有關(guān).

多個攝像機的光心與圖像對應(yīng)點連線的延伸線理論上應(yīng)該交于一點,受畸變、誤差等因素影響實際上往往無法交于一點,針對此問題,光束法平差(BA)利用LM算法對相機參數(shù)進行矯正使觀測點坐標(biāo)和預(yù)測點坐標(biāo)間誤差最小[13].圖像拼接無BA矯正時處理結(jié)果有時會比較糟糕,如圖7是基于SURF算法的無BA拼接,圖8是基于ORB算法的無BA拼接.雖然BA算法處理后能獲得較好的圖像融合效果,但其時間開銷很大,表1顯示了有4幅圖像無BA的圖像融合時間.雖然BA開銷較大,但為了獲得效果可觀的拼接圖像,本文后續(xù)實驗都是在有BA的基礎(chǔ)上進行的.

圖4 圖像融合原圖

圖5 SURF 特征提取圖

圖6 ORB 特征提取圖

圖7 Surf無 BA 效果圖

表1 特征提取性能比較 (單位:s)

圖9,圖11,圖13是基于ORB特征提取的相關(guān)圖像,圖10,圖12,圖14是基于 SURF 特征提取的相關(guān)圖像,圖9,圖10是不經(jīng)過篩選的特征匹配點對,從圖中可以看出,其存在大量的誤匹配,圖11,圖12是經(jīng)過RANSANC算法篩選過的特征匹配點對,圖中只存在一個誤匹配,匹配效果較好,圖13,圖14是經(jīng)過本文算法匹配的特征匹配點對,與RANSAC相比,唯一的離群誤匹配也被刪除了,同時也刪除了一部分正確的匹配點對,除了特征匹配點對數(shù)量的規(guī)模不如RANSAC,篩選效果相近.

圖8 ORB 無 BA 效果圖

圖9 ORB 未篩選特征匹配

圖10 SURF 未篩選特征匹配

表2顯示的是利用RANSAC算法和本文算法進行4幅圖像拼接的時間,數(shù)據(jù)表明,RANSAC算法對SURF和ORB都具有較高的穩(wěn)定性,ORB算法具有較快的融合速度;本文算法對于SURF算法不太適用,SURF算法圖像融合時間不穩(wěn)定,波動較大,效果與RANSAC相比也不明顯,表中記錄了3組融合時間,而對于ORB算法卻有較好的效果,速度優(yōu)于RANSAC.

圖15是基于ORB特征提取的最終的全景融合圖像效果圖.

圖11 ORB RANSAC 篩選特征匹配 1

圖12 ORB RANSAC 篩選特征匹配 2

圖14 ORB LCMF 篩選特征匹配 2

4 結(jié)論

針對匹配篩選算法RANSAC存在的不足,本文從特征匹配結(jié)果具有局部聚類的角度出發(fā),提出了局部聚類的匹配篩選算法LCMF.在對其驗證過程中,選擇偏重質(zhì)量的SURF算法和偏重于效率的ORB算法進行特征提取,使用常用的最近鄰算法進行特征匹配.實驗結(jié)果表明,在使用ORB算法進行特征提取時,LCMF獲得優(yōu)于RANSAC算法的實驗結(jié)果,本文算法具有研究的價值,后續(xù)研究將向普適性的改進方向推進.

圖15 全景融合效果圖

表2 RANSAC 與 LCMF 性能比較 (單位:s)