基于改進(jìn)SIFT和RANSAC的物體特征提取和匹配的研究

張春林 陳勁杰

摘 要：使用基于RANSAC提純的改進(jìn)SIFT算子和SIFT算子分別在兩張不同視角的圖像中提取并匹配特征點(diǎn)對，通過實(shí)驗(yàn)結(jié)果驗(yàn)證了基于改進(jìn)的SIFT算提取特征點(diǎn)的準(zhǔn)確率和匹配的精度都要比SIFT算子和Harris算子高，改進(jìn)SIFT算子提取匹配出的特征點(diǎn)對更加的有利于目標(biāo)物體的三維重建工作。

關(guān)鍵詞：物體特征提取和識(shí)別；SIFT；RANSAC；三維重建

中圖分類號：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號：2096-1472（2018）-11-07-03

1 引言（Introduction）

目前現(xiàn)有的幾種常用的圖像特征提取算子，例如：SUSAN算子、Harris特征提取算子、SIFT（Scale Invariant Feature Transform）特征提取匹配算子等。Harris特征提取算法則是C.Harris和J.Stephens于1998年提出的一種特征提取算子[1]。具體提取步驟：運(yùn)算所有的像素點(diǎn)梯度，然后選取兩個(gè)方向上的梯度都是最大值的點(diǎn)作為Harris角點(diǎn)。這種算子能夠提前去除信息較強(qiáng)的角點(diǎn)，是一種很經(jīng)典的算子。SUSAN算子和Harris算子都是基于像素級別的特征提取算子，提取出來的特征的精度并不是很高，對后面的三維重建勢必會(huì)造成一定的影響。而David Lowe在總結(jié)優(yōu)化了這幾種算子的研究過程中，提出了一種不受圖像尺度和旋轉(zhuǎn)變化，甚至不受光線強(qiáng)度和拍攝角度變化的特征提取算子—SIFT算子[2]。所以說SIFT算子是一種比較優(yōu)秀的特征提取算法。但仍然存在容易誤匹配等缺點(diǎn)。

為此，本文提出將RANSAC算法與改進(jìn)的SIFT算子結(jié)合[3]，通過實(shí)驗(yàn)對比其與SIFT算子及Harris的在特征提取和匹配效果。

2 基于Harris算法的角點(diǎn)檢測（Corner detection based on Harris algorithm）

2.1 Harris特征提取

Harris角點(diǎn)檢測算法首先計(jì)算所有像素的梯度，隨后選取兩個(gè)方向都是最大梯度的點(diǎn)，并以此作為Harris的角點(diǎn)[4]。圖像內(nèi)的角點(diǎn)就是指目標(biāo)物體的輪廓上曲率的局部極大值，它是通過目標(biāo)物體曲率較大的區(qū)域或者兩條、多條邊緣的角點(diǎn)所構(gòu)成的，位于不同圖像亮區(qū)域的交界線上。Harris的角點(diǎn)檢測器公式如下：

如果大于某個(gè)閾值，而且成為相鄰區(qū)域最大值的時(shí)候，我們就能判斷這個(gè)點(diǎn)為角點(diǎn)。其中閾值的選取依靠場景實(shí)際圖像的尺寸、紋理和對比度等。選取閾值的步驟是：通過確定圖像中最大數(shù)量的特征點(diǎn)來選取灰度值最大的一些像素點(diǎn)作為特征點(diǎn)。再依據(jù)所有灰度值的排列序號，選取前個(gè)特征點(diǎn)，然后對特征點(diǎn)進(jìn)行加權(quán)重心化。并且為了降低噪聲對角點(diǎn)選取的影響，我們可以先用高斯平滑對圖像進(jìn)行處理。

其中，和分別是在灰度圖像中的點(diǎn)處u和v兩個(gè)方向上的偏微分。則是二階的混合偏導(dǎo)。X和Y為一階偏導(dǎo)，可以分別的運(yùn)用微分算法在u和v方向與灰度圖像進(jìn)行卷積處理得到。

2.2 Harris角點(diǎn)匹配

歸一化互相關(guān)是一種非常經(jīng)典的匹配算法，并且它具有一定的抗噪聲性能，而且比較容易實(shí)現(xiàn)。但是它的計(jì)算量比較大，對于試驗(yàn)計(jì)算和分析來看，這種匹配算法的運(yùn)行速度太慢，需要進(jìn)一步的優(yōu)化。兩張圖像之間的匹配就是比較兩者之間的相似度，同理，我們應(yīng)用在圖像的特征點(diǎn)匹配也是這樣的，具體就是把特征點(diǎn)作為中心，進(jìn)而比較模板之間的相似程度。

3 基于SIFT的物體特征提取與匹配（Object feature extraction and matching based on SIFT）

SIFT（Scale Invariant Feature Transform）特征匹配算法是一種魯棒性很高的局部特征描述子，運(yùn)用SIFT生產(chǎn)的圖像特征向量的性能穩(wěn)定，對旋轉(zhuǎn)、縮放、目標(biāo)遮擋、噪聲等都有良好的不變性。特征提取主要包括四個(gè)步驟：

（1） 尺度空間極值檢測。

首先對圖像進(jìn)行高斯差分塔金字塔得到高斯差分圖像，然后對高斯差分圖像在多尺度范圍內(nèi)進(jìn)行關(guān)鍵點(diǎn)檢測。

通過高斯函數(shù)與原始圖像的卷積可以得到圖像的尺度空間。

在DoG空間進(jìn)行極值檢測時(shí)，需要將關(guān)鍵點(diǎn)與同一尺度的八個(gè)相鄰和上下相鄰尺度的9×2個(gè)點(diǎn)，共26個(gè)點(diǎn)進(jìn)行比較。如果該關(guān)鍵點(diǎn)在DoG尺度空間中，本層和相鄰兩層的26個(gè)領(lǐng)域中都是最大或者最小，那么該點(diǎn)就可以作為圖像的一個(gè)特征點(diǎn)。

（2） 特征點(diǎn)精確定位。

在得到大量圖像的候選特征點(diǎn)之后，通過擬合三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度，同時(shí)去除低對比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)，以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。

（3） 特征點(diǎn)方向標(biāo)定。

利用圖像的局部性質(zhì)，運(yùn)用關(guān)鍵點(diǎn)領(lǐng)域像素的梯度分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，從而保證算子具有旋轉(zhuǎn)不變性。圖像中某一像素（x，y）處梯度幅值可以用式（9）來表示：

通過這些大小和方向的數(shù)據(jù)，可以創(chuàng)建方向直方圖，從而可以計(jì)算每一個(gè)關(guān)鍵點(diǎn)的主導(dǎo)方向。

（4） 特征描述子的生成。

特征描述子可以通過高斯窗口區(qū)域內(nèi)所有點(diǎn)的梯度和方向唯一表征。將每一個(gè)關(guān)鍵點(diǎn)周圍的16×16鄰域，分割成16個(gè)4×4的子區(qū)域，然后在每一個(gè)4×4的子區(qū)域中計(jì)算生成一個(gè)8方向直方圖。通過對該關(guān)鍵點(diǎn)的所有子區(qū)域都進(jìn)行上述計(jì)算，可以產(chǎn)生一個(gè)4×4×8=128維的特征向量（SIFT描述子）。每一個(gè)關(guān)鍵點(diǎn)都可以由它的特征向量唯一確定[5]。

4 基于RANSAC和改進(jìn)SIFT的特征提取匹配算法

即使運(yùn)用抗干擾能力比較強(qiáng)的SIFT特征提取算子，在匹配時(shí)也會(huì)不可避免的出現(xiàn)少量錯(cuò)配特征點(diǎn)對，為了滿足實(shí)驗(yàn)的需要，結(jié)合RANSAC算法對提出出的特征點(diǎn)進(jìn)行提純[6]。RANSAC算法選取大量的樣本，依次評估它們的參數(shù)，并且每次也隨機(jī)的選取大量的數(shù)據(jù)運(yùn)算參數(shù)模型，隨后對依次得出的參數(shù)進(jìn)行分類，把在誤差范圍內(nèi)的點(diǎn)稱為內(nèi)點(diǎn)，誤差范圍外的點(diǎn)稱為外點(diǎn)。并且RANSAC對錯(cuò)誤匹配率超過50%的點(diǎn)仍然進(jìn)行分析。RANSAC算法具體步驟如下：

首先假設(shè)初始的最佳內(nèi)點(diǎn)數(shù)有0個(gè)，隨機(jī)從I對待分配的特征點(diǎn)對中選取四對原始的特征匹配點(diǎn)對，兩個(gè)平面之間的投影變換矩陣參數(shù)能夠依據(jù)四組點(diǎn)進(jìn)行線性運(yùn)算。

隨后運(yùn)算剩余下的I-4個(gè)特征點(diǎn)對，將它們依次通過變換矩陣獲得坐標(biāo)值，以及它們與對應(yīng)的待匹配點(diǎn)間的距離。

如果它們的距離比閥值T小，那么就判斷這個(gè)特征匹配點(diǎn)對是內(nèi)點(diǎn)，反之就是外點(diǎn)。

將當(dāng)前的內(nèi)點(diǎn)數(shù)量進(jìn)行比較，如果數(shù)量大于，那么當(dāng)前的變換矩陣參數(shù)H是最佳的矩陣估計(jì)，并且將進(jìn)行更新。

通過運(yùn)算大量的隨機(jī)特征點(diǎn)對后，選取內(nèi)點(diǎn)數(shù)量最多，并且誤差函數(shù)最小的變換矩陣參數(shù)，并用這個(gè)參數(shù)作為匹配圖像之間的投影變換矩陣，通過這種變換矩陣能夠提高匹配的精度。

采用RANSAC算法對匹配之后的錯(cuò)誤匹配點(diǎn)對進(jìn)行提純[7]，并且還估算出了圖像間的變換矩陣參數(shù)，進(jìn)而明確了待匹配圖像的精確特征點(diǎn)對。

5 實(shí)驗(yàn)結(jié)果與分析（Experimental results and analysis）

實(shí)驗(yàn)平臺(tái)為VS2015+Opencv2.4.13，操作系統(tǒng)為Windows 10，GPU為GTX1050ti，顯存為4GB。采用GPU并行計(jì)算，運(yùn)用了NVIDIA提供的CUDA通用并行計(jì)算架構(gòu)和cuDNN計(jì)算加速方案。

5.1 特征提取實(shí)驗(yàn)結(jié)果與分析

5.1.1 特征提取的實(shí)驗(yàn)結(jié)果

為了證明本文的物體特征提取的效果，通過兩組圖片進(jìn)行對比分析，圖片大小都是640×480，如圖1（a）所示。

（1）Harris特征提取。在OpenCV中，Harris角點(diǎn)提取是通過cornerHarris（）函數(shù)提取角點(diǎn)的，將cornerHarris（）函數(shù)進(jìn)行封裝，獲得一個(gè)檢測角點(diǎn)類。調(diào)整閾值為70時(shí)，特征提取效果如圖1（b）所示。

（2）SIFT特征提取。實(shí)驗(yàn)中運(yùn)用OpenCV函數(shù)庫中的SiftFeatureDetector類對圖像進(jìn)行特征檢測，特征提取效果如圖1（c）所示。

（3）改進(jìn)SIFT特征提取。使用基于尺度、方向和距離約束來去除錯(cuò)誤匹配點(diǎn)對，從特征點(diǎn)的匹配精度和特征匹配的數(shù)目上進(jìn)行優(yōu)化改良，提高了提取特征點(diǎn)的精度，特征提取效果的如圖1（d）所示。

5.1.2 特征提取結(jié)果分析

通過圖1和表1可以發(fā)現(xiàn)，Harris算子提取的特征點(diǎn)最少，改進(jìn)SIFT算子提取的特征點(diǎn)最多，同時(shí)改進(jìn)SIFT算法的特征點(diǎn)提取的效果分布比Harris、SIFT都均勻。

5.2 特征匹配實(shí)驗(yàn)結(jié)果與分析

5.2.1 特征匹配實(shí)驗(yàn)結(jié)果

為了驗(yàn)證基于改進(jìn)SIFT算子的特征匹配的效果，采用兩組圖像來進(jìn)行特征的提取與匹配實(shí)驗(yàn)，如圖2所示。

通過實(shí)驗(yàn)知道，OpenCV函數(shù)庫的GoodFeatureToTrack函數(shù)的qualityLevel取值0.04時(shí)，提取匹配的效果更好，本文以下的實(shí)驗(yàn)都把qualityLevel取值0.04。

5.2.2 特征匹配實(shí)驗(yàn)分析

從圖2和表2可以看出，經(jīng)RANSAC算法剔除錯(cuò)誤匹配（提純）后[8]，已經(jīng)去除大量的錯(cuò)誤匹配點(diǎn)，SIFT算子還存在少量的錯(cuò)誤匹配，而基于改進(jìn)的SIFT算法的特征點(diǎn)提取匹配基本沒有了錯(cuò)誤匹配。

6 結(jié)論（Conclusion）

通過物體特征提取和匹配實(shí)驗(yàn)將Harris、SIFT、改進(jìn)SIFT算法進(jìn)行對比，改進(jìn)的SIFT算法通過RANSAC剔除錯(cuò)誤匹配后，克服了其他兩種算法的缺點(diǎn)，在特征提取和匹配上效果更好。

參考文獻(xiàn)（References）

[1] 李鵬程，曾毓敏，張夢.一種改進(jìn)的Harris角點(diǎn)檢測算法[J].南京師大學(xué)報(bào)（自然科學(xué)版），2014，37（02）：49-54.

[2] 周穎.基于SIFT算法的圖像特征匹配[J].現(xiàn)代計(jì)算機(jī)，2015（5）：63-68.

[3] 曾巒，王元?dú)J，譚久彬.改進(jìn)的SIFT特征提取和匹配算法[J].光學(xué)精密儀器，2011，19（06）：1392-1396.

[4] S.Bell，C.L.Zitnick，K.Bala，et al.Inside-outside net：Detecting objects in context with skip pooling and recurrent neural net works[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Reco}nition_2016：2874-2883.

[5] Fang Xianyong，Zhang Mingmin，Pan Zhigeng，et al.A new method of manifold mosaic for large displacement images[J].Journal of Computer Science and Technology，2006，21（2）：214-223.

[6] 錐偉群，高屹.基于改進(jìn)RANSAC算法的圖像拼接方法[J].科技創(chuàng)新與應(yīng)用，2015，26（5）：21-22.

[7] Kasar T，Ramakrishnaa A G.Block-based feature detection and matching for mosaicing of camera-captured document images [C].Pros of IEEE region 10 conference.Taipei：IEEE.

[8] 周建平，楊金坤，鄭宇.基于改進(jìn)SIFT特征匹配的視頻拼接—在倒車系統(tǒng)中的應(yīng)用[J].企業(yè)技術(shù)開發(fā)，2011，30（22）：70-71.

作者簡介：

張春林（1987-），男，碩士生.研究領(lǐng)域：智能制造.

陳勁杰（1969-），男，碩士，副教授.研究領(lǐng)域：智能制造.