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

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

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

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

3(沈陽市環境監測中心站,沈陽 110016)

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

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

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

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

1 特征提取與特征匹配

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

1.1 SURF與ORB

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

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

(2)Hessian 矩陣求極值點.

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

圖1 積分圖像

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

圖2 盒式濾波器

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

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

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

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

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

Hessian矩陣判別式:

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

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

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

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

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

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

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

(4)具有旋轉不變性的去相關BRIEF算法.

1.2 最鄰近匹配

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

2 RANSAC 與 LCMF

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

2.1 RANSAC

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

再次，集中管制力度弱，缺乏有效的內部控制。一般來說，國有企業內部的層次相對較多，其投資的權利也是層層下放，并且缺乏統一的金內部控制標準，財務管制薄弱，導致難以實施科學有效的內部監控手段。

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

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

(3)統計σ誤差范圍內的內點數M;

(4)迭代上述過程;

(5)選取內點數最多的作為算法結果.

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

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

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

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

2.2 LCMF

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

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

圖3 聚類模型簡化圖

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

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

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

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

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

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

與RANSAC算法相比,該算法的優勢在于:

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

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

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

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

3 實驗結果及分析

3.1 實驗環境

實驗環境如下:操作系統版本Win10,處理器i3 4150,內存 8 GB,OpenCV 庫版本 3.3.1.

3.2 匹配篩選

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

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

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

圖4 圖像融合原圖

圖5 SURF 特征提取圖

圖6 ORB 特征提取圖

圖7 Surf無 BA 效果圖

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

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

圖8 ORB 無 BA 效果圖

圖9 ORB 未篩選特征匹配

圖10 SURF 未篩選特征匹配

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

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

圖11 ORB RANSAC 篩選特征匹配 1

圖12 ORB RANSAC 篩選特征匹配 2

圖14 ORB LCMF 篩選特征匹配 2

4 結論

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

圖15 全景融合效果圖

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