一種快速的誤匹配篩選算法

宋孟良，張國偉，盧秋紅，張蘇蘇

（1.上海電力大學 自動化工程學院，上海200082；2.上海合時智能科技有限公司，上海201100；3.上海太陽能工程技術研究中心有限公司，上海201100）

0 引言

目前，機器視覺發展迅速并廣泛應用于各個領域。圖像的特征點提取與匹配屬于機器視覺的基礎組成部分，在圖像配準、視覺SLAM、三維重建等多個領域都起著重要的作用[1-3]。特征匹配的結果是下一個環節的輸入數據，是其他圖像處理的前提和關鍵[4]。因此，在特征匹配中減少誤匹配的數量并提高特征匹配的正確率與效率會對實際應用產生較大的影響。

在SIFT[5]中,作者提出一種基于KNN的比例誤匹配篩選方法，但這種方法魯棒性較差。Fischler等[6]提出基于統計模型的經典方法RANSAC（Random Sample Consensus）,該方法可以在包含“局外點”的數據中，通過迭代有效地得到高精度的數學模型，該方法具有一定的魯棒性，但是迭代次數沒有上限計算時間較長，當數據整體錯誤率較高時，其計算結果也會有較高的錯誤率。文獻[7]中，將前兩種算法相融合，減少了RANSAC的迭代次數并且提高了正確匹配率。文獻[8]中，提出了一種改進RANSAC的方法，通過改進損失函數使模型考慮到了不同匹配的誤差，相比于傳統方法提高了模型的估算精度。文獻[9]在文獻[8]的基礎上使用具有更大概率的“內點”的數據點來指導數據采樣，并且在估算單應矩陣時使用這些點作為先驗知識，進一步提高了模型估算的精度。文獻[10]中，將所有匹配點以先驗知識為依據進行排序，將“內點”概率大的點排在前面，有序地進行采樣而不是隨機進行，進一步提高了算法的運行速度和魯棒性。文獻[11]中，為了解決大比例的誤匹配會影響模型精度問題，以一個更好的模型為基礎進行局部優化，以克服大比例誤匹配對模型精度的影響。

為了兼顧魯棒性和計算速度，本文在前人的基礎上提出了一種快速的誤匹配篩選算法，融合使用Otsu算法和RANSAC算法，在保證正確率與充足匹配對的情況下提高了算法的計算速度。最后在TMU數據集上驗證了該方法的有效性。

1 誤匹配篩選算法

1.1 歐式距離(Euclidean Distance)

在特征匹配中，假設待匹配圖像矩陣的個數為n元素值，用個數為n的元素值(x1，x2，…，xn)組成該圖像的特征組，特征組構成了n維空間，特征組中的元素值構成了每一維的數值。在n維空間下，待匹配的兩張圖像的特征點的集合分別記為A與B：

1.2 基于歐氏距離的最大間類方差法（Otsu）

最大類間方差法是由日本學者大津展之[12]于1979年提出的，是一種自適應的閾值確定方法，簡稱Otsu，該方法的本質上是一種分類算法。

本文將該算法應用于特征點的誤匹配篩選，具體算法如下。

假設2張圖片特征匹配完成后得到的所有匹配對的數量為N，將匹配對歐式距離映射為d∈［0，255］,歐氏距離等級為d的匹配對的個數為nd，則每個等級的歐氏距離出現的概率為pd=nd/N；假設最佳閾值為t，則根據閾值t將所有匹配對劃分為正確匹配與錯誤匹配2類：

歐氏距離越小則說明匹配對是正確匹配的概率越高，則正確匹配對對應的范圍為Right∈（0，T）。

1.3 基于Otsu的初次篩選

圖像特征點匹配初次匹配完成后得到的特征點包含大量的錯誤匹配，本文利用所有特征匹配對的平均歐氏距離進行初次篩選，提高算法的運行效率[13]。在1.2節中基于歐式距離的Otsu算法中，根據式（1）～式（3）可知：

由此可得|μ-μR(t)|-|μ-μW(t)|>0，即表明，特征匹配對的歐氏距離均值μ更接近于錯誤匹配所對應的歐式距離均值μR(t)，即更接近于錯誤匹配對應的峰值，則說明Otsu算法的最佳閾值在本算法中處于2個峰值之間的峰谷處，即T∈(0，μ)，μ大于T，表明所有的匹配對中歐氏距離大于μ的匹配對應該剔除。

1.4 隨機取樣一致（RANSAC）

在特征匹配完成后，待匹配的2張圖像之間特征帶點的對應關系確定。此時圖片A與圖片B之間存在對應關系A=H·B，矩陣H是一個3×3的最佳單應性矩陣，通常令h33歸一化矩陣。

式中：S為圖像尺度參數；(x′，y′)為圖像A角點位置；(x，y)為圖像B角點位置。

假設樣本數（即特征匹配對的總數）為M，從數據集中隨機抽取m個樣本，因為單應性矩陣H中共有8個未知數，至少需要8個線性方程組求解，所以m≥4，根據樣本計算得到的模型后將滿足該模型的特征匹配對的個數與重投影誤差，通過多次迭代使得重投影誤差最小的模型即為所求。

雖然RANSAC具有較強的魯棒性，但是該算法的迭代次數沒有上限算法，運行時間較長，限制迭代次數可能會導致無法得到最優模型。為了進一步提高RANSAC的算法運行速度與模型精度，我們采用文獻[10]中的算法思想，將2次篩選后的特征匹配對根據歐式距離從大到小依次排序后，對RANSAC進行優化。

1.5 基于歐氏距離的誤匹配篩選算法

為了解決圖像特征帶點誤匹配篩選算法魯棒性較差、耗時較長等問題，本文提出了基于歐氏距離的特征匹配對誤匹配篩選算法。首先，使用歐氏距離作為圖像特征匹配對的置信度，特征匹配對的歐氏距離越小則說明特征匹配對的置信度越高，然后在歐氏距離的基礎上構建Otsu算法，通過平均歐式距離進行初次篩選，然后通過迭代計算得到最佳閾值T，在二次篩選完成后將剩余匹配對根據歐氏距離排序，最后通過RANSAC算法迭代計算出最優模型。

2 實驗與分析

為了驗證本文提出的誤匹配算法的有效性，在德國慕尼黑大學TUM數據集中進行實驗，實驗平臺采用Windows10操作系統、AMD Ryzen 2600 Six-Core Processor(3400 MHz)、16GB DDR4 RAM，不使用GPU加速，編程環境為Visual Studio2017。

為了驗證算法的有效性，我們分別對Otsu算法及基于Otsu的閾值篩選算法進行實驗。選取圖像為ORBSLAM中使用的TMU數據集。該數據集是汽車行駛中的實際路況，圖像分辨率為800×900，采樣頻率為10 fps，兩張圖像之間的時間間隔為18 ms以上，提取的特征匹配對的數量為500。

圖2 平均歐氏距離的篩選結果

由實驗結果可以觀察到，在Otsu算法篩選后仍然存在一些誤匹配，并不能直接使用得到的結果，因此需要與RANSAC算法融合進一步篩選。

圖3 傳統RANSAC篩選結果

圖4 本文算法篩選結果

表1 算法性能對比

由圖1、圖2中實驗結果可知，本文提出的基于歐氏距離的Otsu篩選算法及平均歐氏距離篩選算法的有效性，可以篩選掉大量的錯誤匹配。

由圖3、圖4及表1中的結果可知，本文提出的融合算法可以有效地進行誤匹配篩選，并且能夠保留較多的特征匹配對，算法得到的篩選結果正確率較高，與傳統RANSAC算法相對比，本文算法的運行速度大幅度上升，篩選結果正確率也有所提高。與傳統RANSAC算法相比，本文算法篩選后的匹配對數量有所下降，但是比其他種類的算法保留的匹配對數量要多，并且斜率較為固定，具有良好的自適應性。與傳統RANSAC算法相比，本文算法運行時間大幅度減小，對篩選數據進行排序，提升了算法的運行速度。由表1中實驗結果可知，本文算法在處理500個匹配對時運行時間基本在5 ms左右，能夠滿足實時性要求，與其他算法相比，本文算法的正確率較高。

3 結論

針對傳統的特征匹配對誤匹配篩選算法魯棒性差、效率低等問題，本文提出了一種快速的特征點誤匹配篩選算法。在特征匹配對的歐氏距離基礎上，引入Otsu算法對數據進行初次篩選和二次篩選，大大提升了算法的篩選效率，不僅快速得到了篩選結果，而且保證了充足的匹配對數量，提升了算法的魯棒性；另外，進一步提升了RANSAC的運行速度和算法精度，對篩選后數據進行排序。在TUM數據集上進行實驗，實驗表明本文算法比傳統算法具有更好的魯棒性和實時性。