基于SURF算法的雙目視覺特征點定位研究

王永鋒 石超 徐子鋒 陳龍

摘? 要：針對雙目視覺立體圖像特征點匹配質(zhì)量不好導(dǎo)致定位精度低的問題，本文提出改進SURF匹配的特征點定位方法。在改進的SURF匹配算法中，采用雙向匹配、NNDR約束、對稱性約束、極線約束和交叉匹配約束的方法，提高了圖像特征點匹配的質(zhì)量。在雙目視覺特征點定位中，采用公垂線段中點法具有更高的特征點定位精度。實驗證明，該算法的特征點定位精度更高，同時可以達到實時三維重建效率。

關(guān)鍵詞：特征點重建;SURF算法;雙目視覺;最小二乘法;公垂線段中點法

中圖分類號：TP391? ? ?文獻標(biāo)識碼：A

Abstract：Aiming at the problem of low positioning accuracy caused by poor matching quality of binocular stereo image feature points，this paper proposes a feature point 3D reconstruction method based on improved SURF matching algorithm.In the improved SURF matching algorithm，two-way matching，NNDR constraint，symmetry constraint，polar line constraint and cross matching constraint are used to improve the quality of image feature point matching.In binocular vision feature point positioning，the common vertical midpoint method has higher feature point positioning accuracy.Experimental results show that the proposed algorithm has higher accuracy of feature point positioning and can achieve real-time 3D reconstruction efficiency.

Keywords：reconstruction of feature points;SURF algorithm;binocular vision;least square method;midpoint method of

common vertical segment

1? ?引言（Introduction）

隨著工業(yè)4.0時代來臨，工業(yè)機器人智能化應(yīng)用空前廣泛，機器視覺定位作為機器人技術(shù)智能化發(fā)展的重要分支之一，其準(zhǔn)確度的提高成為人們研究的熱點[1]。在機器視覺定位中，雙目視覺具有測量范圍廣和定位精度高的特點，越來越多地出現(xiàn)在工業(yè)領(lǐng)域中[2]。

在雙目視覺系統(tǒng)中，目標(biāo)物體特征點的匹配精度和重建精度是影響雙目視覺系統(tǒng)定位準(zhǔn)確性的主要因素，因此在這兩方面的研究受到廣泛的關(guān)注。在立體圖像特征點匹配中，SURF算法的匹配效果比較穩(wěn)定，但同時存在錯誤匹配現(xiàn)象。在物體特征點重建中定位精度要求高的場合，最小二乘法的定位精度不能滿足需求。

為此，本文提出改進SURF匹配的特征點重建方法，通過實驗對比其匹配效果和重建精度。

2? ?SURF算法和雙目立體視覺（SURF algorithm andbinocular stereo vision）

2.1? ?SURF匹配算法原理

SURF算法主要由特征點檢測、主方向的確定、特征描述的構(gòu)建及特征點匹配等四部分構(gòu)成。

SURF算法采用Hessian矩陣行列式近似值圖像[3]。式（1）為任意像素點的Hessian矩陣計算公式：

矩陣判別式如式（2）所示，根據(jù)其計算結(jié)果正負來定位圖像特征點。

在SURF算法中，以特征點為圓心，一定大小尺度為半徑的圓形領(lǐng)域內(nèi)，將60°扇形區(qū)域作為掃描單位，首先統(tǒng)計該區(qū)域中水平方向的haar小波計算值，然后再統(tǒng)計此區(qū)域垂直方向haar小波計算值，最后將兩者的統(tǒng)計結(jié)果值相加，重復(fù)掃描統(tǒng)計，其結(jié)果值最大的方向為特征點的主方向。

SURF算法構(gòu)建特征描述的基本流程是，首先以選定特征點為中心，建立一個邊長為一定尺度大小的正方形包圍框，該框方向為檢測出特征點的主方向。然后將正方形包圍區(qū)域等分為16個小正方形區(qū)域，在劃分的小正方形區(qū)域中先統(tǒng)計水平方向的haar小波計算值和其絕對值，再統(tǒng)計垂直方向的haar小波計算值和其絕對值，這樣每一個小正方形區(qū)域都可以用一個四維向量來表示：

重復(fù)統(tǒng)計計算每一個形區(qū)域，統(tǒng)計完畢后，每個特征點可以用一個64維的向量來描述。

在圖像匹配中，求得兩張圖像各特征描述向量后，根據(jù)第一張圖像某特征點的描述向量，統(tǒng)計第二張圖像各特征描述向量與該特征描述向量的得分值，在特征點匹配中，得分值的好壞是用歐氏距離的大小來衡量的，距離越小，得分值越大，匹配效果越好。

2.2? ?雙目視覺特征點定位原理

（1）特征點三維重建工作流程

特征點三維重建工作流程如圖1所示。

（2）特征點三維重建模型

空間特征點三維重建的基本模型如圖2所示，對于空間特征點任意一點，像素點和分別為空間點在左右相機像平面的投影點，但是僅僅通過單一像素點或無法獲取到特征點三維坐標(biāo)，由于在直線或上的任意點，在像素平面上的投影點都為點或。所以，利用兩個相機拍攝圖片，這樣直線和可以唯一確定點的位置，實現(xiàn)特征點的三維重建。

3? ?改進的SURF匹配算法（Improved SURF matchingalgorithm）

本文采用經(jīng)典SURF算法檢測到左右圖片特征點后，采用漢明距離完成初步匹配，但是由于存在許多錯誤特征點對，因此需對SURF匹配算法進行改進，設(shè)計流程圖如圖3所示。

實現(xiàn)的具體步驟如下：

（1）讀取左右相機圖片，SURF特征點檢測和特征描述。

（2）分別計算左圖到右圖的匹配集，右圖到左圖的匹配集。

（3）NNDR約束[4]（最近鄰比例策略），分別對、集合中的匹配點做NNDR約束處理。

（4）對稱性測試[5]，例如在集合中特征點a對應(yīng)特征點b，則判斷集合中特征點a是否對應(yīng)特征點b，若完全對應(yīng)相同，則保留該特征點匹配對;否則，篩選掉該特征點匹配對。

（5）采用PROSAC算法[6]計算基礎(chǔ)矩陣F，篩選掉不能通過極線約束[7]測試的特征點匹配對。

（6）交叉匹配約束[5]，經(jīng)過步驟（5）處理后，得到的特征點匹配對理論上不會出現(xiàn)交叉現(xiàn)象，反之篩選掉交叉現(xiàn)象的匹配點對。

3.1? ?最近鄰約束和對稱性檢測

經(jīng)典SURF匹配算法自身存在錯誤匹配現(xiàn)象，為了有效提高特征點匹配準(zhǔn)確率，本文考慮加入最近鄰約束和對稱性檢測。

（1）選取左圖片中的特征點，在右圖片中找到最優(yōu)質(zhì)的匹配點，直至左圖片特征點全部匹配完成，得到匹配集合;同理，對右圖片執(zhí)行相同的操作，得到集合。

（2）在匹配集合中，計算某一特征點匹配的最短距離與次短距離的比值，通過設(shè)置閾值來篩選特征點匹配對。如果，則將匹配結(jié)果存入點集;對于匹配集合，同理，得到點集。

（3）將兩個點集、執(zhí)行求交操作，得到經(jīng)過最近鄰約束和對稱性檢測的匹配集合，即。

3.2? ?利用PROSAC算法剔除誤匹配

PROSAC算法是在RANSAC算法[8]的基礎(chǔ)上改進而來的，RANSAC算法是通過隨機抽取樣本估計參數(shù)模型，而PROSAC算法是將樣本數(shù)據(jù)排列，選取匹配質(zhì)量好的數(shù)據(jù)進行匹配來估計參數(shù)模型，加快特征點匹配的速度。

具體步驟如下：

（1）將集合C按照漢明距離由小到大排序，選取集合C中前m個特征點對。

（2）從m個特征點對中隨機抽樣選取四個，計算對應(yīng)圖像的基礎(chǔ)矩陣H。

（3）根據(jù)步驟（2）求出的變換矩陣計算其他特征點對的誤差，確定該匹配點對是否為內(nèi)點，并且統(tǒng)計內(nèi)點個數(shù)。

（4）判斷內(nèi)點個數(shù)是否超過給定閾值，若超過給定閾值，則當(dāng)前計算的基礎(chǔ)矩陣為最優(yōu)矩陣，否則，再從m個特征點對中隨機抽樣選取四對，進行下一次迭代。

（5）如果當(dāng)前迭代次數(shù)達到最大迭代次數(shù)，則返回內(nèi)點數(shù)目最多的一組參數(shù)模型，得到最優(yōu)質(zhì)的基礎(chǔ)矩陣H。

3.3? ?交叉匹配約束

對于通過極線約束測試的匹配集合，還可能會出現(xiàn)交叉匹配的錯誤匹配現(xiàn)象，如圖4所示，直線和分別是左右圖像上兩條對極線，通過極線約束測試兩組匹配點對和，理論上，例如在第一張圖片的極線上，點位于之上，那么在第二張圖像對應(yīng)極線上，點也應(yīng)該位于之上。所以添加交叉匹配約束步驟處理，可以得到更優(yōu)質(zhì)的匹配集合。

4? ?空間特征點定位（Spatial feature point positioning）

如圖2所示為理想情況下的雙目視覺特征點三維重建模型，由于存在相機標(biāo)定和像素特征點匹配誤差，導(dǎo)致左右相機確定的兩條直線或可能不會相交于點P，所以需要建立近似模型估計點P的三維空間坐標(biāo)。

特征點三維重建的傳統(tǒng)做法是采用最小二乘法[9]，但是它在求解過程中沒有將成像模型的幾何意義考慮在內(nèi)，重建精度有待提高，所以本文采用公垂線段中點法[9]來提高特征點的三維重建精度。

如圖5所示為公垂線段中點法示意圖，理論上空間點P為兩條反射線、的交點，但在實際計算過程中，由于計算誤差的存在，兩條直線、很可能是兩條空間異面直線。

公垂線中點法的步驟是：首先求解兩條異面直線的公垂線，然后求解公垂線與兩條直線的交點坐標(biāo)，最后取兩個交點的中點坐標(biāo)作為特征點三維重建坐標(biāo)。在求解過程中，需要考慮以下兩點：

（a）如果兩條異面直線的公垂線段大于設(shè)定閾值，則判定該匹配點對為錯誤匹配。

（b）如果公垂線段的長度為0，則認為兩條直線不是異面直線，特征點三維重建轉(zhuǎn)化為兩條空間直線求交點的問題。

具體公式推導(dǎo)如下所示：

文獻[9]說明，經(jīng)過化簡，每條異面直線或都可以列出兩個等式，因為點A、B分別在異面直線、上，有四個方程，聯(lián)合上式，得到關(guān)于六個未知數(shù)的六個線性方程，可解得，則重建空間點坐標(biāo)為。

5? ?實驗結(jié)果與分析（Experimental results and analysis）

5.1? ?特征點匹配結(jié)果與分析

為了驗證本文算法的精確性和實時性，將SURF算法、SURF+NNDR算法、SURF+RANRAC算法和本文算法進行驗證和比較，其匹配結(jié)果如圖6所示。

表1為四種算法的匹配結(jié)果對比。

精確性上來說，SURF算法出現(xiàn)明顯的錯誤匹配現(xiàn)象;SURF+NNDR算法是在SURF匹配的基礎(chǔ)上，加入NNDR約束，在一定程度上可以剔除大部分錯誤匹配點; SURF+RANRAC算法是在SURF匹配的基礎(chǔ)上，采用RANRAC進行進一步剔除質(zhì)量不好的匹配點對，提高了匹配的精確性;本文設(shè)計的算法在SURF算法匹配的基礎(chǔ)上，采用對稱性約束、PROSAC算法及交叉匹配約束算法，獲取到更優(yōu)質(zhì)的匹配點對。

匹配速率上，由于SURF+NNDR約束算法、SURF+RANRAC算法和本文算法都是在SURF算法的基礎(chǔ)上改進而來的，消耗的時間比經(jīng)典SURF算法多。其中SURF+RANRAC算法和本文算法的立體匹配效果最好，與SURF+RANRAC算法相比，本文算法的運行速率更快，滿足實時性需求。

5.2? ?特征點三維重建結(jié)果分析

實驗采用兩個大恒MER-500-14GM工業(yè)相機，兩個相機鏡頭的基線距為200mm，以標(biāo)記圖案的左上角點為坐標(biāo)原點，建立世界坐標(biāo)系。對標(biāo)記圖案中的四個標(biāo)記點進行三維定位，將理論值與兩種方法求取值相比較，對比結(jié)果如表2所示。實驗表明，與最小二乘法相比，公垂線段中點法有更高的定位精度。

6? ?結(jié)論（Conclusion）

本文提出改進SURF匹配的特征點定位方法，在圖像匹配算法方面，實驗結(jié)果證明，該算法匹配效果很好，解決了匹配質(zhì)量不高的問題;在雙目視覺特征點定位方面，實驗結(jié)果證明，該算法有更高的定位精度。同時本文設(shè)計的方法具有很快的運行速度，重建效率高。

參考文獻（References）

[1] 湯勃，孔建益，伍世虔.機器視覺表面缺陷檢測綜述[J].中國圖象圖形學(xué)報，2017，22（12）：1640-1663.

[2] 黃鵬程，江劍宇，楊波.雙目立體視覺的研究現(xiàn)狀及進展[J].光學(xué)儀器，2018，40（04）：81-86.

[3] Bay H，Ess A，Tuytelaars T，et al.Speeded-Up Robust Features （SURF）[J].Computer Vision & Image Understanding，2008，110（3）：346-359.

[4] Park H，Mitsumine H，F(xiàn)ujii M.Automatic Adjustment of the Distance Ratio Threshold in Nearest Neighbor Distance Ratio Matching for Robust Camera Tracking[J].IEICE Trans on Information and Systems，2011，E94-D（4）：938-940.

[5] 陳潔，高志強，密保秀，等.引入極線約束的SURF特征匹配算法[J].中國圖象圖形學(xué)報，2016，21（08）：1048-1056.

[6] Chum O.Matching with PROSAC-progressive sample consensus[J].Proc.conf.on Cvpr，2005，1（2）：220-226.

[7] Sui L，Zhang J，Cui D.Image Rectification Using Affine Epipolar Geometric Constraint[C].International Symposium on Computer Science & Computational Technology，2008，4（1）：26-33.

[8] 秦曉飛，皮軍強，李峰.基于極線約束的ORB特征匹配算法[J].計算機應(yīng)用研究，2018，35（09）：2865-2868.

[9] 羅世民，李茂西.雙目視覺測量中三維坐標(biāo)的求取方法研究[J].計算機工程與設(shè)計，2006（19）：3622-3624.

作者簡介：

王永鋒（1992-），男，碩士生.研究領(lǐng)域：圖像處理，機器視覺.

石? ?超（1993-），男，碩士生.研究領(lǐng)域：數(shù)字圖像處理.

徐子鋒（1993-），男，碩士生.研究領(lǐng)域：智能制造.

陳? 龍（1978-），男，博士，副教授.研究領(lǐng)域：產(chǎn)品計算設(shè)計，機器視覺與機器人.