基于RANSAC 的道路影像控制點(diǎn)選取方法研究

方林波，石昊蘇，路雅寧，武鵬輝

（西北政法大學(xué) 商學(xué)院，陜西西安 710122）

近年來，隨著計(jì)算機(jī)處理速度的快速提升，基于多傳感器融合的移動(dòng)近景攝影快速測(cè)量新技術(shù)得到了迅速發(fā)展[1-2]。一個(gè)典型的近景移動(dòng)測(cè)量系統(tǒng)是將IMU、CCD 和GPS 3 種類型的傳感器集成在一起，如在移動(dòng)載體上，用IMU 和GPS 兩種傳感器對(duì)移動(dòng)載體進(jìn)行組合定位，同時(shí)，對(duì)CCD 拍攝獲取的立體影像進(jìn)行處理，最后基于前方交會(huì)計(jì)算出立體影像中地物的坐標(biāo)位置[3-7]。從以上過程可以看出，自主定位問題是移動(dòng)測(cè)量的一個(gè)基本問題，在GPS 信號(hào)受到干擾（或遮擋）的情況下，由于漂移等造成的誤差逐漸積累增加，僅僅依靠IMU 進(jìn)行獨(dú)立定位，無法獲得所需要的精度。為解決這一問題，數(shù)字可量測(cè)影像（Digital Measurable Image，DMI）技術(shù)被引入到自主定位中，基于DMI 的坐標(biāo)信息、基于后方交會(huì)計(jì)算出移動(dòng)載體的位置坐標(biāo)，并將其與GPS、IMU 結(jié)合，形成DMI/IMU/GPS 組合定位系統(tǒng)[8-10]，其優(yōu)點(diǎn)是把多種技術(shù)結(jié)合起來，使各子系統(tǒng)的優(yōu)勢(shì)互補(bǔ)，最終提高定位的精度和穩(wěn)定性。在影像匹配方面，這些研究均采用SIFT 算法對(duì)影像進(jìn)行特征點(diǎn)的提取，但沒有對(duì)大量的特征點(diǎn)進(jìn)行有效的分析和篩選，并提取控制點(diǎn)。控制點(diǎn)是影像中不受光照、形變和角度等變化影響的特征點(diǎn)，具有穩(wěn)定、準(zhǔn)確和分布均勻等特征。控制點(diǎn)的提取是影像匹配、圖像拼接、以及利用道路立體影像進(jìn)行車輛定位的前提。在影像匹配方面通常采用SIFT 算法對(duì)影像進(jìn)行特征點(diǎn)的提取，針對(duì)該算法的改進(jìn)和擴(kuò)展一直是研究熱點(diǎn)[11-13]。

道路立體影像中地物平面層次多、背景復(fù)雜，控制點(diǎn)往往隱沒在背景噪音中，直接用SIFT 算法獲取的特征點(diǎn)多數(shù)是背景產(chǎn)生的，可靠性和均勻性較差，必須通過特定的方法將其中穩(wěn)定、準(zhǔn)確、分布均勻的控制點(diǎn)篩選出來，才能使下一步的移動(dòng)測(cè)量、定位導(dǎo)航高效準(zhǔn)確。

文中針對(duì)道路立體影像的SIFT 特征，提出了基于RANSAC 和均勻度理論相結(jié)合的控制點(diǎn)篩選方法，該方法保證了特征點(diǎn)選取的均勻、準(zhǔn)確。實(shí)驗(yàn)表明，該方法能夠從道路立體影像中提取出穩(wěn)定、準(zhǔn)確、分布均勻的控制點(diǎn)，為后續(xù)的定位導(dǎo)航奠定基礎(chǔ)。

1 相關(guān)理論

1.1 SIFT算法

在圖像匹配的眾多算法中，SIFT 算法具有良好的尺度和空間旋轉(zhuǎn)的不變性，得到了廣泛的應(yīng)用，該算法提取特征分為以下4 步[14-15]：

1）尺度空間極值檢測(cè)。該步驟的主要任務(wù)是得到多尺度圖像序列，如式（1）所示。

其中，σ為尺度因子，G為σ的高斯核，I為原圖像，L為I在尺度σ下的空間表示。

在式（1）的基礎(chǔ)上建立DOG 金字塔，如式（2）所示。

DOG 金字塔中每個(gè)像素均與相鄰以及上、下鄰層的26 個(gè)鄰域像素進(jìn)行比較，如果是極值點(diǎn)，則該點(diǎn)為候選的特征點(diǎn)，并記錄該點(diǎn)的位置與尺度。

2）精確確定關(guān)鍵點(diǎn)。主要任務(wù)是確定關(guān)鍵點(diǎn)的參數(shù)，并將不穩(wěn)定的邊緣響應(yīng)點(diǎn)篩選掉。

3）確定特征點(diǎn)的梯度模值和方向。應(yīng)用公式（3）、（4）計(jì)算出特征點(diǎn)(x,y)處的梯度模值m(x,y)和方向θ(x,y)值。

每個(gè)特征點(diǎn)具有3 個(gè)方面的屬性值，分別為所在的位置、尺度和方向。

4）生成SIFT 特征描述子為了增強(qiáng)特征點(diǎn)的穩(wěn)健性，每個(gè)特征點(diǎn)用相鄰的種子點(diǎn)描述，即每個(gè)特征點(diǎn)用4×4×8=128 維的向量描述。

1.2 RANSAC算法

即使經(jīng)過多重篩選，兩幅影像間的SIFT 特征點(diǎn)匹配的結(jié)果中還會(huì)有許多的錯(cuò)誤匹配對(duì)，需要進(jìn)一步優(yōu)化。隨機(jī)抽樣一致性估計(jì)算法（Random Sample Consensus，RANSAC）可以進(jìn)行較為魯棒的優(yōu)化[16]。RANSAC 的主要特點(diǎn)隨著迭代次數(shù)的增加模型的參數(shù)正確概率會(huì)相應(yīng)提高。

1.3 均勻度理論

定義1 獨(dú)占球：對(duì)n維歐氏空間的至多可數(shù)的有限點(diǎn)集s，對(duì)于任意x∈s，記M(x)=min(d(x,y))，y∈s，y≠x，則 存 在x1∈s使 得M(x)=d(x,x1)，記 緊 鄰MP(x)=x1，M(x)為緊鄰距離。其中d(·)是歐氏距離。把x作為球的中心，M(x)/2 為球的半徑的閉球，B(x)稱為x的獨(dú)占球，其體積記為v(x)。B(x)的外切閉立方體的數(shù)量很多，但體積相等，記其一為CU(x)，稱為x的獨(dú)占體，體積記為vc(x)。

引理1 在一定的邊界內(nèi)點(diǎn)集中，所有點(diǎn)的獨(dú)占球互不重疊，而且這些獨(dú)占球最近的空間關(guān)系是相切的。

定義2 均勻度：設(shè)pt:S?A?Rn為一個(gè)格局。獨(dú)占球的總體積為為多面體A的體積，稱為格局S的均勻度。

2 維的均勻度定義：長(zhǎng)方形內(nèi)所有點(diǎn)的總獨(dú)占圓面積與長(zhǎng)方形總面積的π 4 倍之比稱為格局均勻度。把點(diǎn)的總獨(dú)占圓面積記為a，長(zhǎng)方形面積記為A，則格局均勻度的值為。

2 基于RANSAC和均勻度理論的立體影像控制點(diǎn)篩選

文中方法包括4 個(gè)主要步驟：1）SIFT 特征點(diǎn)提取；2）基于區(qū)域均勻度的特征點(diǎn)初步篩選；3）立體像對(duì)特征點(diǎn)匹配；4）基于RANSAC 和均勻度的特征點(diǎn)篩選。

2.1 SIFT特征點(diǎn)提取

道路立體影像平面層次多、背景復(fù)雜，而且受天氣、光線影響較大，獲得穩(wěn)定、準(zhǔn)確、分布均勻而且盡量多的特征點(diǎn)是道路立體影像進(jìn)一步研究和應(yīng)用的前提和難點(diǎn)。SIFT 特征點(diǎn)對(duì)圖像各種變化具有較強(qiáng)的穩(wěn)定性，相對(duì)邊緣、角點(diǎn)、形狀等特征，更適合道路立體影像。

2.2 基于區(qū)域均勻度的特征點(diǎn)初步篩選

區(qū)域均勻度是影像中某一特定區(qū)域的均勻度。用a(x,y)表示影像的某一個(gè)SIFT 特征點(diǎn)的坐標(biāo)，t為設(shè)定的均勻度閾值。特征點(diǎn)初步篩選的步驟如下：

1）把a(bǔ)(x,y)作為中心，距其上、下、左、右各20 像素為邊長(zhǎng)，形成一個(gè)正方形；

2）對(duì)該正方形中所包含的SIFT 特征點(diǎn)計(jì)算均勻度；

3）當(dāng)均勻度小于t時(shí)，除去該正方形中梯度峰值最小的特征點(diǎn)；

4）重復(fù)2）和3）直到該正方形內(nèi)均勻度大于或等于t。

文中實(shí)驗(yàn)中t設(shè)為0.28。

通過以上步驟，大量SIFT 特征點(diǎn)中滿足設(shè)定均勻度、大梯度峰值的特征點(diǎn)被篩選了出來。

2.3 立體像對(duì)特征點(diǎn)匹配

對(duì)立體影像進(jìn)行SIFT 特征點(diǎn)提取和初步篩選后，需要對(duì)像對(duì)中的左圖和右圖進(jìn)行特征點(diǎn)匹配，以查找像對(duì)中的同名像點(diǎn)。取出左圖的一個(gè)SIFT 特征點(diǎn)，基于K-D 樹搜索策略，在右圖SIFT 特征點(diǎn)中找出最近鄰（NN）特征點(diǎn)和次近鄰（SCN）特征點(diǎn)。計(jì)算NN 距離和SCN 距離的比值，當(dāng)該比值小于設(shè)定的閾值時(shí)，接受這一對(duì)匹配點(diǎn)，閾值越低，SIFT 匹配點(diǎn)越少，匹配越穩(wěn)定。但穩(wěn)定的代價(jià)是損失掉大量有效的特征點(diǎn)，所以該閾值取值較為關(guān)鍵。根據(jù)查閱文獻(xiàn)和實(shí)驗(yàn)，該閾值取在[0.6,0.7]區(qū)間最為合適。

2.4 基于RANSAC和均勻度的特征點(diǎn)篩選

基于RANSAC 算法的SIFT 特征點(diǎn)篩選方法在圖像拼接、圖像配準(zhǔn)等方面應(yīng)用廣泛。由于RANSAC 主要依靠符合模型的匹配點(diǎn)數(shù)量的大小為評(píng)判條件，而忽略了這些匹配點(diǎn)的分布情況，所以只適合于特征點(diǎn)分布較為均勻的圖像，對(duì)于特征點(diǎn)分布不均勻的圖像，不但不能提高其篩選結(jié)果的均勻度，甚至?xí)岩恍┓浅Ｖ匾植驾^為離散的特征點(diǎn)除去，降低了篩選的質(zhì)量。道路立體影像平面層次多、特征點(diǎn)分布不均勻，直接使用RANSAC 進(jìn)行篩選效果差。

文中將均勻度理論引入RANSAC 中，將符合模型的匹配點(diǎn)數(shù)量與該點(diǎn)集均勻度的乘積作為評(píng)判標(biāo)準(zhǔn)，使得RANSAC 對(duì)特征點(diǎn)的篩選既滿足幾何一致性，又滿足特征點(diǎn)的均勻性。基本步驟如下：

1）利用2、3 節(jié)中介紹的方法對(duì)像對(duì)進(jìn)行特征點(diǎn)匹配，得到的匹配點(diǎn)數(shù)量設(shè)為M，根據(jù)公式N=log(1-pn)/log[1-(1-a)m]確定隨機(jī)采樣次數(shù)N，其中，pn=0.95，m=4，a為數(shù)據(jù)錯(cuò)誤率；

2）利用隨機(jī)選取的4 對(duì)匹配點(diǎn)計(jì)算初始單應(yīng)矩陣；

3）設(shè)置約束條件，滿足者為內(nèi)點(diǎn)，不滿足者為外點(diǎn)。約束條件設(shè)置方法為：把左圖中的匹配點(diǎn)通過單應(yīng)矩陣進(jìn)行變換，對(duì)變換后的匹配點(diǎn)與右圖對(duì)應(yīng)的匹配點(diǎn)進(jìn)行歐式距離計(jì)算，此歐式距離d即為約束條件，d＞4 的點(diǎn)為外點(diǎn)，d≤4 的點(diǎn)為內(nèi)點(diǎn)；

4）計(jì)算內(nèi)點(diǎn)集的均勻度L，記內(nèi)點(diǎn)數(shù)量c與均勻度乘積R=cL，如果R大于等于設(shè)定閾值時(shí)，用內(nèi)點(diǎn)數(shù)重新估計(jì)單應(yīng)矩陣，結(jié)束本輪運(yùn)算；如果R小于閾值，則重新在數(shù)據(jù)集中選取數(shù)據(jù)樣本，重復(fù)2）、3）、4）三步；

5）經(jīng)過N次迭代，得到N個(gè)內(nèi)點(diǎn)集，選取R值最大的內(nèi)點(diǎn)集，算法結(jié)束。

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

文中采用的道路立體影像大小為1 392×1 040像素，在野外道路、鄉(xiāng)村道路和城市道路3 個(gè)場(chǎng)景下進(jìn)行實(shí)驗(yàn)，首先對(duì)立體像對(duì)進(jìn)行SIFT 特征提取，然后對(duì)文中算法和傳統(tǒng)的RANSAC 算法的篩選結(jié)果進(jìn)行比較。

圖1 像對(duì)的SIFT特征點(diǎn)檢測(cè)

圖1 是野外道路立體影像的SIFT 特征點(diǎn)提取圖，圖1（a）、（b）分別為像對(duì)中的左圖和右圖，包含的特征點(diǎn)數(shù)分別為308 和508。

圖2 是該像對(duì)的SIFT 特征點(diǎn)進(jìn)行區(qū)域均勻化后的特征圖，像對(duì)的左圖和右圖分別得到144 和235 個(gè)特征點(diǎn)。對(duì)比圖1 和圖2 可以看出：經(jīng)過區(qū)域均勻化，扎堆的特征點(diǎn)得到了有效抑制，特征點(diǎn)的分布更加均勻。

圖2 區(qū)域均勻化后的SIFT特征點(diǎn)

圖3 是對(duì)野外道路立體影像進(jìn)行特征點(diǎn)匹配和匹配點(diǎn)篩選的4 個(gè)實(shí)驗(yàn)結(jié)果。圖3（a）是對(duì)SIFT 特征點(diǎn)進(jìn)行直接匹配的結(jié)果，匹配點(diǎn)數(shù)為79；圖3（b）是對(duì)SIFT 特征點(diǎn)進(jìn)行區(qū)域均勻化后進(jìn)行匹配的結(jié)果，匹配點(diǎn)數(shù)為48；圖3（c）是對(duì)圖3（a）匹配點(diǎn)利用RANSAC算法進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為17；圖3（d）是對(duì)圖3（b）匹配點(diǎn)利用文中方法（2.4 節(jié)）進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為15。可以看出，圖3（c）中的匹配點(diǎn)都集中到了兩個(gè)區(qū)域，均勻度較差；圖3（d）中匹配點(diǎn)均勻度分布有明顯的改善。

圖4 是對(duì)鄉(xiāng)村道路立體影像進(jìn)行特征點(diǎn)匹配和匹配點(diǎn)篩選的4 個(gè)實(shí)驗(yàn)結(jié)果。圖4（a）是對(duì)SIFT 特征點(diǎn)進(jìn)行直接匹配的結(jié)果，匹配點(diǎn)數(shù)為204；圖4（b）是對(duì)SIFT 特征點(diǎn)進(jìn)行區(qū)域均勻化后進(jìn)行匹配的結(jié)果，匹配 點(diǎn)數(shù)為82；圖4（c）是對(duì)圖4（a）匹配點(diǎn)利用RANSAC 算法進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為64；圖4（d）是對(duì)圖4（b）匹配點(diǎn)利用文中方法（2.4 節(jié)）進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為35。可以看出，圖4（c）中的匹配點(diǎn)過于扎堆，均勻度較差；圖4（d）中匹配點(diǎn)均勻度分布有明顯改善。

圖5 是對(duì)城市道路立體影像進(jìn)行特征點(diǎn)匹配和匹配點(diǎn)篩選的4 個(gè)實(shí)驗(yàn)結(jié)果。圖5（a）是對(duì)SIFT 特征點(diǎn)進(jìn)行直接匹配的結(jié)果，匹配點(diǎn)數(shù)為236；圖5（b）是對(duì)SIFT 特征點(diǎn)進(jìn)行區(qū)域均勻化后進(jìn)行匹配的結(jié)果，匹配點(diǎn) 數(shù) 為97；圖5（c）是 對(duì)圖5（a）匹 配點(diǎn)利用RANSAC 算法進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為52；圖5（d）是對(duì)圖5（b）匹配點(diǎn)利用文中方法（2.4 節(jié)）進(jìn)行篩選的結(jié)果，匹配點(diǎn)數(shù)為42。可以看出，圖5（c）中的匹配點(diǎn)過于集中，均勻度較差；圖5（d）中匹配點(diǎn)均勻度分布有明顯的改善。

圖3 野外道路像對(duì)匹配點(diǎn)篩選對(duì)比

圖6 是傳統(tǒng)方法與文中方法在3 種典型場(chǎng)景（野外道路、鄉(xiāng)村道路、城市道路）的篩選結(jié)果對(duì)比圖，可以看出：

1）對(duì)于3 種類型的圖像，在經(jīng)過區(qū)域均勻化后，匹配點(diǎn)數(shù)量均大幅減少，匹配正確率優(yōu)于傳統(tǒng)方法。

2）文中方法篩選出的匹配點(diǎn)分布的均勻度大大提升。

綜上所述，文中方法相對(duì)傳統(tǒng)方法是一種更有效的道路立體影像特征點(diǎn)提取和篩選的方法。

4 結(jié)束語

圖4 鄉(xiāng)村道路像對(duì)匹配點(diǎn)篩選對(duì)比

圖5 城市道路像對(duì)匹配點(diǎn)篩選對(duì)比

基于DMI 的車輛定位導(dǎo)航技術(shù)是移動(dòng)測(cè)量領(lǐng)域的前沿和趨勢(shì)，其中，立體影像控制點(diǎn)的篩選是難點(diǎn)和關(guān)鍵，控制點(diǎn)必須是準(zhǔn)確、穩(wěn)定的特征點(diǎn)，而且分布盡量均勻。目前，立體影像控制點(diǎn)篩選技術(shù)還未見報(bào)道。文中結(jié)合SIFT 算法、RANSAC 算法和均勻度理論，將均勻度理論引入RANSAC-SIFT 過程中，提出了一套道路立體影像控制點(diǎn)篩選方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠獲取準(zhǔn)確、穩(wěn)定、分布均勻的控制點(diǎn)，為立體影像匹配、控制點(diǎn)運(yùn)動(dòng)軌跡的Kalman估算、以及車輛自主定位導(dǎo)航的研究奠定基礎(chǔ)。

圖6 兩種方法的控制點(diǎn)篩選結(jié)果對(duì)比