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

宋孟良，張國偉，盧秋紅，張?zhí)K蘇

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

0 引言

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

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

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

1 誤匹配篩選算法

1.1 歐式距離(Euclidean Distance)

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

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

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

本文將該算法應(yīng)用于特征點(diǎn)的誤匹配篩選，具體算法如下。

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

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

1.3 基于Otsu的初次篩選

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

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

1.4 隨機(jī)取樣一致（RANSAC）

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

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

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

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

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

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

2 實(shí)驗(yàn)與分析

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

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

圖2 平均歐氏距離的篩選結(jié)果

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

圖3 傳統(tǒng)RANSAC篩選結(jié)果

圖4 本文算法篩選結(jié)果

表1 算法性能對比

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

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

3 結(jié)論

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