FastRanDSac
——一種高效的誤匹配檢測(cè)算法

文吉成，吳麗君，陳金伙，林培杰，程樹(shù)英

(福州大學(xué)物理與信息工程學(xué)院, 微納器件與太陽(yáng)能電池研究所，福建 福州 350116)

?

FastRanDSac
——一種高效的誤匹配檢測(cè)算法

文吉成，吳麗君，陳金伙，林培杰，程樹(shù)英

(福州大學(xué)物理與信息工程學(xué)院, 微納器件與太陽(yáng)能電池研究所，福建 福州 350116)

圖像之間存在光照變化、 旋轉(zhuǎn)、 仿射變換，使得局部特征匹配后，誤匹配無(wú)法避免. 在正確匹配過(guò)半的前提下，提出一種簡(jiǎn)化的誤匹配去除算法FastRanDSac，用于在極短時(shí)間內(nèi)解決圖像匹配對(duì)之間誤匹配點(diǎn)的問(wèn)題. 初步實(shí)驗(yàn)表明，在平移、 旋轉(zhuǎn)、 尺度縮放、 視角以及光照變化的圖像中，F(xiàn)astRanDSac能保存近100%的正確匹配對(duì)，而運(yùn)行速度與RANSAC相比有大幅度的提高.

隨機(jī)抽樣一致算法； 誤匹配去除； 兩次隨機(jī)模型計(jì)算； 反向投影

0 引言

圖像匹配廣泛應(yīng)用于圖像拼接、 變化檢測(cè)、 影像合成、 目標(biāo)跟蹤等領(lǐng)域[1-2]，圖像匹配的正確與否將直接影響后續(xù)應(yīng)用的性能. 基于特征的圖像匹配步驟包括： 特征點(diǎn)提取、 亞像素定位、 描述符計(jì)算、 特征匹配、 誤匹配剔除[3]. 圖像匹配首先需要提取一定數(shù)量的穩(wěn)定特征點(diǎn)，而在實(shí)際應(yīng)用中，由于光照不均、 圖像尺度變化、 視點(diǎn)變化、 圖像旋轉(zhuǎn)等外部客觀干擾的存在，往往造成特征不明確，特征點(diǎn)不穩(wěn)定、 甚至不唯一，容易產(chǎn)生錯(cuò)誤匹配，降低圖像匹配的準(zhǔn)確度，因此, 對(duì)誤匹配的去除具有重要意義[4].

文[5]提出了常用的誤匹配去除方法，大致可分為基于評(píng)價(jià)標(biāo)準(zhǔn)[5-6]以及統(tǒng)計(jì)模型的方法. 增強(qiáng)評(píng)價(jià)標(biāo)準(zhǔn)的方式是將多種評(píng)判方法的匹配交集判斷為正確匹配，例如結(jié)合雙向匹配[6]及余弦相似性[7]來(lái)獲取正確匹配集. 這些方法實(shí)現(xiàn)簡(jiǎn)單，有一定效果，但仍然可能將誤匹配計(jì)算為正確匹配留下，而計(jì)算正確匹配為誤匹配被剔除，且由于要對(duì)每個(gè)匹配點(diǎn)進(jìn)行重復(fù)計(jì)算判斷，計(jì)算時(shí)間長(zhǎng). 另一種方法是通過(guò)統(tǒng)計(jì)估算最佳模型參數(shù)，如RANSAC算法[8]通過(guò)迭代獲得具有最大內(nèi)點(diǎn)的樣本集，以估算最優(yōu)模型. RANSAC算法簡(jiǎn)單，受誤差較大外點(diǎn)的影響小，具有很強(qiáng)的魯棒性，因此得到了廣泛應(yīng)用[9]. 為獲得盡可能多的內(nèi)點(diǎn)數(shù)目，RANSAC可能需要大量的迭代次數(shù)，耗時(shí)隨之增加[10]. 因此, 學(xué)者們提出了多種改進(jìn)方案： 如Sequential probability ratio test randomized RANSAC (SPRT)[11]，PROSAC(progressive sample consensus)[12]. SRPT算法通過(guò)隨機(jī)抽取一組數(shù)據(jù)點(diǎn)來(lái)計(jì)算似然比，用以測(cè)試模型的好壞，并提前結(jié)束錯(cuò)誤的迭代模型. PROSAC算法按照先驗(yàn)知識(shí)進(jìn)行排序，以減少迭代次數(shù). 兩者都能獲得更優(yōu)的迭代次數(shù)，在原來(lái)的基礎(chǔ)上減少了計(jì)算時(shí)間，但是仍然需要較多的迭代次數(shù).

在大部分圖像匹配情況下，有：

1) 隨著越來(lái)越強(qiáng)的特征描述能力，對(duì)光照、 仿射、 旋轉(zhuǎn)等等變換的魯棒性越來(lái)越好，匹配點(diǎn)集合中正確匹配點(diǎn)所占比例并不會(huì)低.

2) 點(diǎn)變換模型矩陣具有8個(gè)自由度，隨機(jī)計(jì)算兩次匹配模型并相互驗(yàn)證，如果兩個(gè)計(jì)算出來(lái)的變換模型在可容忍的誤差范圍內(nèi)，那么便假設(shè)此模型正確.

在上述前提下，本研究提出FastRanDSac隨機(jī)兩次模型一致算法，以實(shí)現(xiàn)迅速確定匹配模型，降低算法所需的運(yùn)行時(shí)間.

1 RANSAC算法

RANSAC方法是從一個(gè)樣本整體集合中，通過(guò)迭代估計(jì)，尋找到具有最大內(nèi)點(diǎn)數(shù)目的模型. 它能夠從包含大量外點(diǎn)的數(shù)據(jù)集中尋找到兩幅圖像點(diǎn)位置的基本矩陣或單應(yīng)矩陣，并據(jù)此得到最大一致內(nèi)點(diǎn)集，將錯(cuò)誤匹配的點(diǎn)(外點(diǎn))去除.

RANSAC方法的基本步驟如下：

1) 從匹配對(duì)集合H中隨機(jī)抽取4個(gè)匹配對(duì)(4個(gè)點(diǎn)剛好計(jì)算一個(gè)8自由度的單應(yīng)矩陣)，估算出單應(yīng)矩陣，得到模型M.

2) 用模型M測(cè)試所有的匹配點(diǎn)，并計(jì)算匹配實(shí)際對(duì)應(yīng)點(diǎn)和實(shí)際點(diǎn)位置的誤差，設(shè)定一個(gè)閾值，統(tǒng)計(jì)小于閾值的內(nèi)點(diǎn)數(shù)目.

3) 當(dāng)?shù)玫絻?nèi)點(diǎn)數(shù)目大于當(dāng)前記錄的最佳樣本best_in(初次設(shè)定為0)時(shí)，將best_in賦值為當(dāng)前內(nèi)點(diǎn)數(shù)目.

4) 迭代1)～3)，當(dāng)?shù)螖?shù)超過(guò)設(shè)定的最大迭代次數(shù)，退出算法，并返回模型M.

即使匹配點(diǎn)集合中初始正確匹配數(shù)較少，隨著迭代次數(shù)增多，內(nèi)點(diǎn)數(shù)量也不斷增加，RANSAC尋找到最優(yōu)模型的幾率隨之增大. 但由于正確匹配率未知，得到最優(yōu)模型所需要的迭代次數(shù)也未知，常通過(guò)下式來(lái)估算迭代次數(shù)：

其中：m為估計(jì)匹配模型需要的最少點(diǎn)數(shù)，即為4；p表示算法能給出最優(yōu)模型的幾率，一般設(shè)為0.99；w表示數(shù)據(jù)點(diǎn)內(nèi)點(diǎn)的比例，在實(shí)際中實(shí)時(shí)更新. 因此RANSAC算法往往非常耗時(shí)，經(jīng)實(shí)測(cè)，在CPU @ 2.80 GHz，4.0 GB RAM的PC上運(yùn)行RANSAC，對(duì)一個(gè)1 644點(diǎn)的匹配集內(nèi)點(diǎn)比例96%，需要26.7 s的時(shí)間.

2 FastRanDSac算法

RANSAC通過(guò)不斷迭代來(lái)尋找最優(yōu)匹配模型，且每次迭代都需要測(cè)試每個(gè)匹配點(diǎn)是否為正確匹配點(diǎn). 即便匹配集合中正確匹配的比例較高，也需要較多的迭代次數(shù)，耗費(fèi)較多的時(shí)間. 經(jīng)分析可得，當(dāng)正確匹配比例較高，即符合正確匹配模型的匹配點(diǎn)集數(shù)量大于符合錯(cuò)誤匹配模型的集合數(shù)量，有以下結(jié)論： 1)隨機(jī)抽取兩組匹配點(diǎn)中不包含誤匹配點(diǎn)的概率較高. 2)如果抽取的樣點(diǎn)中包含錯(cuò)誤匹配，那么計(jì)算的匹配模型不會(huì)一致，因此，一旦隨機(jī)計(jì)算兩次匹配模型一致，那么模型錯(cuò)誤的概率接近于0. 在此前提下，F(xiàn)astRanDSac提出隨機(jī)抽取匹配點(diǎn)來(lái)計(jì)算兩次匹配模型并相互驗(yàn)證，以快速獲取正確模型. 此外，本算法事先對(duì)匹配集合進(jìn)行排序以便穩(wěn)定的特征點(diǎn)具備較高的優(yōu)先級(jí)，然后對(duì)特征點(diǎn)進(jìn)行高斯隨機(jī)采樣，并在計(jì)算匹配模型后，結(jié)合反向投影誤差來(lái)迅速排除錯(cuò)誤模型，進(jìn)一步加速正確模型的建立.

2.1 排序及高斯隨機(jī)采樣

設(shè)匹配集合中正確匹配點(diǎn)的概率為P，則隨機(jī)均勻抽取m個(gè)匹配對(duì)，m個(gè)都為正確匹配的概率為Pmatch. 為提高Pmatch值，F(xiàn)astRanDSac首先根據(jù)匹配判斷規(guī)則，即描述符間次近鄰歐式距離與最近鄰歐氏距離之比，對(duì)匹配集合排序，以保證匹配置信度越高的匹配對(duì)越靠前. 在此基礎(chǔ)上，對(duì)有序的匹配集合進(jìn)行采樣，以更大的幾率抽取更靠前的匹配對(duì)，以提高同時(shí)抽取到的m個(gè)正確匹配對(duì)的幾率，減少采樣及計(jì)算單應(yīng)矩陣的循環(huán)次數(shù).

由于客觀干擾的存在，描述符間歐式距離比例偏大不等同于誤匹配，因此每個(gè)匹配點(diǎn)都應(yīng)有一定的幾率被抽樣. 考慮到干擾噪聲服從正態(tài)分布，采用高斯隨機(jī)采樣來(lái)保證歐式距離比例越小，被抽樣的幾率越大，歐式距離比例越大，被抽樣的概率越小. 其中，高斯隨機(jī)數(shù)可由Box George Edward Pelham和Muller Mervin Edgar[13]提出的算法生成.

2.2 模型估計(jì)與校驗(yàn)

基于高斯隨機(jī)抽取的8對(duì)匹配點(diǎn)可以組成兩組獨(dú)立的匹配對(duì)集合SA和SB，并據(jù)此計(jì)算出兩個(gè)相應(yīng)的匹配模型A和B. 如果條件理想，那么計(jì)算結(jié)果與正確模型參數(shù)必然完全一致. 而現(xiàn)實(shí)情況下由于相機(jī)本身存在的畸變與外部噪聲，特別是特征點(diǎn)的提取無(wú)法保證完全在同一位置，因此計(jì)算結(jié)果必然存在誤差. 不考慮特殊情況，在大部分實(shí)際情況中，大量數(shù)據(jù)符合同一個(gè)模型而匹配出錯(cuò)的概率極小. 本研究正是基于這種先驗(yàn)知識(shí)來(lái)實(shí)現(xiàn)算法加速.

如果兩個(gè)模型一致，則開(kāi)始測(cè)試匹配模型，并作為模型初值. 由于噪聲的存在，實(shí)際應(yīng)用中，F(xiàn)astRanDSac引入一個(gè)閾值，當(dāng)模型的偏差小于此閾值(取3.3)時(shí)，模型便認(rèn)為是合理的. 當(dāng)計(jì)算出的兩個(gè)模型不一致時(shí)，難以判定哪個(gè)模型有誤. 為了更快更精確地判定正確模型，可用模型A去對(duì)SB中的匹配點(diǎn)求反向投影，如果所有匹配點(diǎn)的反向投影誤差都超過(guò)閾值，則認(rèn)為模型A出錯(cuò)； 如果部分匹配點(diǎn)的反向投影誤差都超過(guò)閾值，則認(rèn)為模型A正確，且超出閾值的匹配點(diǎn)為誤匹配點(diǎn). 同樣地，可以對(duì)B進(jìn)行驗(yàn)證. 通過(guò)多次判定，模型的可信度得到提高.

2.3 內(nèi)點(diǎn)篩選以及模型更新

盡管模型一致性符合，仍然無(wú)法確定它的正確性. 因此采用基于數(shù)據(jù)的循環(huán)檢測(cè)求解正確模型. 統(tǒng)計(jì)符合上述模型的內(nèi)點(diǎn)數(shù)量，會(huì)有兩種情況： 1)數(shù)量小于一半，則必然模型出錯(cuò)，重新抽取模型并計(jì)算. 2)當(dāng)數(shù)量超過(guò)一半時(shí)，模型的正確性可以保證，但是精確性有待提高，通過(guò)再次計(jì)算提取更精確的模型，使得模型包含更多的內(nèi)點(diǎn)數(shù)量. 在第2種情況中，由于已經(jīng)獲得了部分正確匹配點(diǎn)集合，對(duì)樣點(diǎn)的采樣并不需要從初始樣本集獲得，而可以從上一步得到的正確樣本中采樣得到. 這樣，不僅可以極大提高采樣到正確樣點(diǎn)的幾率，提高正確模型計(jì)算效率，也極大縮減了時(shí)間. 再次統(tǒng)計(jì)符合模型的內(nèi)點(diǎn)數(shù)量，如果多于上一次的結(jié)果，那么更新模型以及內(nèi)點(diǎn)集，否則保留上次的結(jié)果. 采用新的策略后，F(xiàn)astRanDSac算法流程如圖1所示. 在第三節(jié)中將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證模型的穩(wěn)定性以及效率.

圖1 FastRanDSac方法流程Fig.1 Process of FastRanDSac

3 實(shí)驗(yàn)與結(jié)果分析

表1 測(cè)試圖集

為驗(yàn)證FastRanDSac算法去除誤匹配的效率及穩(wěn)定性，選用對(duì)標(biāo)準(zhǔn)測(cè)試庫(kù)中已知單應(yīng)矩陣的Bike、 Boat、 Bark、 Ubc、 Tree、 Wall圖集, 采用描述能力強(qiáng)[14-15]的SIFT[16-17]算法來(lái)提取特征描述符并完成粗匹配，然后用雙向匹配、 余弦和歐式距離評(píng)判(Cos-Eur)、 RANSAC、 SPRT、 PROSAC以及FastRanDSac分別完成正確匹配提純，從所花時(shí)間、 剩余正確匹配點(diǎn)數(shù)、 以及錯(cuò)誤匹配剩余點(diǎn)數(shù)三個(gè)方面來(lái)對(duì)算法的效率、 可靠度進(jìn)行比較. 本算法采取隨機(jī)抽樣的策略，算法的循環(huán)采樣次數(shù)和估算模型不會(huì)相同，所獲得的模型為次優(yōu)模型，因此本研究記錄百次運(yùn)行時(shí)間，以及相應(yīng)的正確匹配點(diǎn)的變化情況來(lái)驗(yàn)證算法的穩(wěn)定性. 在CPU @ 2.80 GHz，4.0 Gbit RAM的PC上使用VS2013實(shí)現(xiàn)并驗(yàn)證算法, 如表1所示.

首先，基于Bike、 Wall、 Ubc、 Tree圖集對(duì)上述算法的運(yùn)行時(shí)間及正確匹配點(diǎn)數(shù)，即算法效率和可靠性進(jìn)行驗(yàn)證. RANSAC、 SPRT、 PROSAC算法和FastRanDSac算法都采用隨機(jī)選取樣本的策略，但結(jié)果具有一定的不確定性，因此通過(guò)連續(xù)運(yùn)行20次并取平均值的方法來(lái)減少不確定性，運(yùn)行結(jié)果如表2所示.

表2 算法性能比較

經(jīng)SIFT粗匹配后，Bike圖集取得701個(gè)匹配對(duì)，根據(jù)圖集提供的單應(yīng)矩陣可以得知其中有56個(gè)誤匹配，需要采用前述的算法去除誤匹配. 由于需要多次迭代計(jì)算，RANSAC的運(yùn)行時(shí)間最長(zhǎng)，但迭代的過(guò)程能找到最優(yōu)的匹配模型，因此能去除所有的誤匹配, 并保存所有的正確匹配結(jié)果. SRPT算法性能上與RANSAC相當(dāng)，而在時(shí)間上提高了4～10倍，與文[11]中的結(jié)論相同. PROSAC由于同樣采用了基于先驗(yàn)距離比排序，因此，時(shí)間上得到了極大的提升，符合文[12]中時(shí)間提升比的結(jié)論. 雙向匹配、 結(jié)合余弦和歐式距離的增強(qiáng)評(píng)價(jià)法相當(dāng)于要進(jìn)行兩次的評(píng)判計(jì)算，仍需要較多的時(shí)間，且因?yàn)橹皇翘岣哒_匹配評(píng)判的門(mén)檻，因此無(wú)法去除所有的誤匹配，且還會(huì)去除一部分的正確匹配. 本算法由于能迅速找到正確的匹配模型，在運(yùn)行時(shí)間上降低了三個(gè)數(shù)量級(jí)，且能去除所有的誤匹配. 因此，與其他算法相比，F(xiàn)astRanDSac在保持性能的基礎(chǔ)上，大大提升了效率.

為進(jìn)一步驗(yàn)證本算法性能，基于Boat和Bark圖集獲得的匹配對(duì)上對(duì)RANSAC和FastRanDSac算法進(jìn)行測(cè)試，并對(duì)剩余正確匹配數(shù)和運(yùn)行時(shí)間做出比較. 為說(shuō)明算法性能的穩(wěn)定性，對(duì)每組圖集都運(yùn)行FastRanDSac算法100次，并畫(huà)出每次的剩余正確匹配點(diǎn)數(shù)量及運(yùn)行時(shí)間，如圖2所示. 對(duì)Boat圖集，SIFT算法獲得的粗匹配點(diǎn)有1 644個(gè)，其中誤匹配點(diǎn)數(shù)為51. 經(jīng)RANSAC算法提取到正確匹配1 589個(gè)，剩余錯(cuò)誤匹配點(diǎn)數(shù)為0，運(yùn)行時(shí)間26.742 3 s. 對(duì)于Bark圖集，SIFT算法獲得的粗匹配點(diǎn)有521個(gè)，其中誤匹配點(diǎn)數(shù)為2個(gè). 經(jīng)RANSAC算法提取到正確匹配518個(gè)，剩余錯(cuò)誤匹配點(diǎn)數(shù)為0，運(yùn)行時(shí)間1.024 3 s. 通過(guò)運(yùn)行100次FastRanDSac測(cè)試算法穩(wěn)定性，其中性能參量如表3所示. 值得一提的是, 由于單次運(yùn)行的時(shí)間較短，時(shí)間的浮動(dòng)上除了受算法本身性能的影響外，還可能受計(jì)算機(jī)調(diào)度等待時(shí)間的影響. 由此可以看出，F(xiàn)astRanDSac算法可以去除所有的誤匹配，保存的正確匹配點(diǎn)數(shù)接近于RANSAC，且算法性能較穩(wěn)定. 因此，當(dāng)粗匹配中正確匹配率較高時(shí)，依靠本文提出的簡(jiǎn)化策略來(lái)確定匹配模型是可行的. 在運(yùn)行時(shí)間上，與RANSAC相比減少了2～4個(gè)數(shù)量級(jí).

圖2 算法穩(wěn)定性測(cè)試Fig.2 Test of algorithm about stability

表3 100次運(yùn)行的相關(guān)統(tǒng)計(jì)參量

4 結(jié)語(yǔ)

圖像配準(zhǔn)、 拼接等應(yīng)用都以正確匹配為基礎(chǔ)，而經(jīng)過(guò)粗匹配后，存在少量錯(cuò)誤匹配無(wú)法避免. 傳統(tǒng)的RANSAC方法通過(guò)迭代的方式獲取最優(yōu)匹配模型以去除誤匹配，雖然性能高、 穩(wěn)定性好，但迭代的過(guò)程耗費(fèi)大量時(shí)間. 針對(duì)粗匹配中誤匹配率較低的情況，本研究提出一種簡(jiǎn)化的誤匹配去除算法(FastRanDSac). 該算法采用新的策略估計(jì)基本矩陣模型參數(shù)，隨機(jī)抽取兩組匹配點(diǎn)用以計(jì)算出兩個(gè)匹配模型，當(dāng)兩個(gè)模型一致時(shí)即認(rèn)為是正確模型. 并通過(guò)一系列的措施提高快速找到正確模型的幾率，其中包括： 對(duì)匹配集合排序、 高斯采樣、 反向投影加速確認(rèn). 為驗(yàn)證算法的性能及穩(wěn)定性，本研究采用SIFT算法對(duì)Boat, Bark, Bike圖集進(jìn)行特征點(diǎn)提取及初步匹配，然后采用FastRanDSac算法、 RANSAC等算法去除誤匹配. 實(shí)驗(yàn)結(jié)果表明，與RANSAC相比，F(xiàn)astRanDSac可以將運(yùn)行時(shí)間縮短2～3個(gè)數(shù)量級(jí)，同時(shí)去除所有的誤匹配點(diǎn)，并保存大部分的正確匹配點(diǎn)，并具有很高的穩(wěn)定性. 因此，在已有誤匹配率較低的情況下，可以采用FastRanDSac實(shí)現(xiàn)快速誤匹配點(diǎn)的去除. 在已有誤匹配率較高的情況下，如何快速地找到正確的匹配模型，以提高誤匹配去除算法速度，是下一步需要研究的問(wèn)題.

[1] CHEN J, FENG H, PAN K，etal. An optimization method for registration and mosaicking of remote sensing images[J]. International Journal for Light and Electron Optics, 2014,125(2): 697-703.

[2] SEDAGHAT A, EBADI H. Remote sensing image matching based on adaptive binning SIFT descriptor[J]. IEEE Transactions on Geoscience & Remote Sensing, 2015, 53(10): 5 283-5 293.

[3] SHOKOUFANDEH A, YKESELMAN M, DEMIRCI F,etal. Many-to-many feature matching in object recognition: a review of three approaches[J]. Iet Computer Vision, 2012, 6(6): 500-513.

[4] 單小軍, 唐娉. 圖像匹配中誤匹配點(diǎn)檢測(cè)技術(shù)綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2015(9): 2 561-2 565.

[5] RAGURAM R, CHUM O, POLLEFEYS M,etal. USAC: A universal framework for random sample consensus[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(8): 2 022-2 038.

[6] 騫森，朱劍英. 基于改進(jìn)的SIFT特征的圖像雙向匹配算法[J]. 機(jī)械科學(xué)與技術(shù), 2007, 26(9): 1 179-1 182.

[7] 白廷柱, 侯喜報(bào). 基于SIFT算子的圖像匹配算法研究[J]. 北京理工大學(xué)學(xué)報(bào), 2013, 33(6): 622-627.

[8] FISCHLER M A, BOLLES R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[9] CAO S, JIANG J, ZHANG G,etal. An edge-based scale- and affine-invariant algorithm for remote sensing image registration[J]. International Journal of Remote Sensing, 2013, 34(7): 2 301-2 326.

[10] 單小軍，唐鄭柯． GSSAC: 一種用于遙感影像配準(zhǔn)的誤匹配點(diǎn)檢測(cè)方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(6): 62-68.

[11] MATAS J, CHUM O. Randomized RANSAC with sequential probability ratio test[C]// Tenth IEEE International Conference on Computer Vision. Beijing: IEEE, 2005: 1 727-1 732.

[12] CHUM O, MATAS J. Matching with PROSAC - progressive sample consensus[C]//IEEE Computer Society Conference on Computer Vision & Pattern Recognition. San Diego: IEEE, 2005: 220-226.

[13] BOX G E P, MULLER M E. A note on the generation of random normal deviates[J]. Ann Math Statist, 1958, 24(5): 610-611.

[14] KHAN N, Mccane B, MILLS S. Better than SIFT?[J]. Machine Vision and Applications, 2015, 26(6): 819-836.

[15] KASHIF M, DESERNO T M, HAAK D,etal. Feature description with SIFT, SURF, BRIEF, BRISK, or FREAK?: a general question answered for bone age assessment[J]. Computers in Biology and Medicine, 2016, 68(6): 67-75.

[16] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[17] LOWE D G. Object recognition from local scale-invariant features[C]//The Proceedings of the Seventh IEEE International Conference on Computer Vision. Kerkyra: IEEE, 1999: 1 150-1 157.

(責(zé)任編輯： 沈蕓)

FastRanDSac——a fast mismatching elimination algorithm

WEN Jicheng, WU Lijun, CHEN Jinhuo, LIN Peijie, CHENG Shuying

(Institute of Micro-Nano Devices and Solar Cells, College of Physics and Information Engineering,Fuzhou University, Fuzhou, Fujian 350116, China)

Mismatching always exists after matching with local features due to the influences of illumination change, rotation, as well as affine transformation. This work focuses on improving the efficiency of mismatching elimination providing more than half of matching-pairs are correct. A fast random double sample consensus algorithm, called FastRanDSac, is proposed to eliminate the mismatching in a very short time. The power of the methods is that it can keep most correct matching-points while removes all the mismatching-points, and greatly improves the efficiency against RANSAC.

Random sample consensus； mismatching elimination； double random calculations； back projection

10.7631/issn.1000-2243.2017.03.0336

1000-2243(2017)03-0336-06

2016-05-22

吳麗君(1984-)，副教授，碩士生導(dǎo)師, 主要從事圖像處理、 機(jī)器視覺(jué)研究，lijun.wu@fzu.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目(51508105，61601127)； 教育部留學(xué)歸國(guó)人員科研啟動(dòng)經(jīng)費(fèi)資助項(xiàng)目(LXKQ201504)； 福建省自然科學(xué)基金資助項(xiàng)目(2015J05124)； 福建省科技廳高校產(chǎn)學(xué)合作資助項(xiàng)目(206H6012)； 福建省科技廳工業(yè)引導(dǎo)性重點(diǎn)資助項(xiàng)目(2015H0021)； 福建省經(jīng)信委省級(jí)技術(shù)創(chuàng)新重點(diǎn)資助項(xiàng)目(830020, 83016006)； 福州大學(xué)貴重儀器設(shè)備開(kāi)放測(cè)試基金資助項(xiàng)目(2016T042)； 福建省教育廳產(chǎn)學(xué)研資助項(xiàng)目(JA14038)

TP391

A