基于閾值自適應調(diào)整的圖像特征均勻分布ORB算法改進

時培成，楊劍鋒，梁濤年，齊 恒

（1. 安徽工程大學 汽車新技術安徽省工程技術研究中心，蕪湖 241000，中國；2. 蕪湖伯特利汽車安全系統(tǒng)股份有限公司，蕪湖 241009，中國）

汽車工業(yè)的蓬勃發(fā)展使得近年來無人駕駛汽車成為了人們的研究熱點。無人駕駛汽車要想在環(huán)境中自主運動，就必須獲取詳細的周圍環(huán)境地圖以及精準的自身定位信息。所以，同步定位與地圖構建變成實現(xiàn)無人駕駛汽車應用的必要前提條件[1]，它包含了定位和建圖。通常，無人駕駛汽車通過攝像頭拍照來定位和建圖，稱無人車視覺同步定位與地圖構建 (simultaneous localization and mapping， SLAM) 算法，而要從圖像中獲取車輛運動信息，必須對圖像提取特征點并進行特征匹配，進而估計相機的運動，再反推出車輛的所處位置[2]。目前，常用的圖像特征點提取方法有 SIFT（scale-invariant features transform）[3]、SURF (speededup robust features)[4]和ORB (Oriented FAST and Rotated BRIEF) 算法。其中，ORB算法相比于SIFT算法和SURF算法提取速度高，可以滿足無人駕駛汽車SLAM系統(tǒng)實時性的要求[6]。

傳統(tǒng)ORB算法因實時性較好，被廣泛應用于視覺SLAM系統(tǒng)中，但它也有比較明顯的缺陷，如提取的特征點在圖像中分布不均勻、聚集嚴重，從而導致后續(xù)圖像匹配精度較差，使相機位姿估計結果出現(xiàn)較大偏差。為此，文獻[7]在提取特征點后，采用四叉樹算法對圖片進行區(qū)域劃分，將特征點平均分配到這些區(qū)域中，通過計算Harris響應值[8]保留響應值最大的特征點，但是該算法消耗時間較長，實時性不好。

文獻[9]在文獻[7]基礎上對傳統(tǒng)四叉樹算法進行改進，提高了特征點的均勻度，但沒有限制節(jié)點的分裂次數(shù)，算法運行時間仍然較長。文獻[10]通過設定閾值限制每層圖像提取的特征點數(shù)目，使算法運行時間大大減少，但是卻造成了特征點分布不均勻，降低了后續(xù)圖像的匹配精度。文獻[11]通過設置不感興趣區(qū)域來剔除那些在初始化時無法提取特征點的柵格，加速了特征點的提取，但是分布均勻度較低，影響后續(xù)圖像匹配精度。

本文針對以上算法的缺點，提出了一種閾值自適應調(diào)整的改進的ORB (advanced ORB，A-ORB)算法，該算法運行時間短，提取的特征分布均勻度高。A-ORB算法依據(jù)圖像大小，來計算需要構建的圖像金字塔層數(shù)，避免了過度增加金字塔層數(shù)而造成算法運行時間延長；并在每層圖像金字塔上設立特征點提取閾值，當提取的特征點數(shù)目滿足閾值條件時，則終止該層圖像特征點的提取，減少特征點的冗余。A-ORB算法在利用四叉樹算法剔除每層圖像上的冗余特征點時，限制四叉樹算法分裂的節(jié)點數(shù)，不但能提高算法的運行效率，也能提高特征點的分布均勻度。

1 ORB算法原理

1.1 FAST關鍵點

圖像的特征點可以形象的理解為圖像中更加重要的像素點，例如圖形邊緣點，灰度值變換較大的點等。ORB算法利用FAST特征點檢測算法來對圖像提取特征點[12]。如圖1所示，F(xiàn)AST算法通過比較圖片中某一個像素點和其周圍的灰度值，如果滿足一定條件則認為它是特征點。

圖1 FAST算法提取示意圖

其具體計算過程如下所示：

步驟1：在待提取的圖像中選取某個像素P；判斷是否可以作為特征點，假設該點的灰度值為IP；

步驟2：人為設定一個閾值T，比如說IP的30%；

步驟3：選取P為圓心，3為半徑的圓上的16個像素點；

步驟4：假如這16個像素點中有連續(xù)L點的灰度都大于IP + T或者小于IP-T，判定P為一個特征點（L一般取12）。

在FAST算法實際提取中，可以通過如下方法加速特征點檢測：直接對圓上第1、5、9、13個像素點的灰度值進行比較，如果他們均滿足判定條件，那么目標點才有可能是特征點；如果不滿足判定條件，則直接跳過該點，判斷下一個像素點。依照此方法計算圖像中的每一個像素點，直到結束。

FAST算法只依靠圖像中像素點灰度值的對比來確定，所以依靠此方法檢測出來的待選點作為特征點非常不可靠，在圖像發(fā)生平移或者旋轉變化時，往往會造成特征點冗雜或者丟失的情況。針對此類缺陷，ORB算法添加了特征點尺度和旋轉的描述。ORB算法通過構建圖像金字塔為提取的特征點添加尺度描述。圖像金字塔是計算機視覺中一種常見的處理方法。金字塔的底層是原始圖像，每往上一層就對原始圖像進行一定倍率的縮放，從而得到不同分辨率的圖像。在每層圖像金字塔上提取特征點后，在進行特征匹配算法時，可以匹配不同層上的圖像，從而實現(xiàn)了尺度不變性。

ORB算法利用了圖像塊的灰度質心為特征點添加旋轉的描述。具體方法如下：

1） 在一個圖像塊A中，定義圖像塊的矩為

式中：I(x,y)為圖像中像素點(x,y)處的灰度值，p、q的取值范圍均為{0,1}。

2） 定義圖像塊的質心為

3） 連接圖像塊幾何中心與質心得到一個方向向量OC，將特征點的方向定義為

1.2 BRIEF描述子

在提取了Oriented FAST 特征點以后，ORB算法使用BRIEF描述子來對特征點進行描述。BRIEF是一種二進制描述子，其描述向量由多個0和1組成[13]。其具體思想是在特征點P周圍以特定模式選取N點對，比較灰度值的大?。ū热鐇,y）。若x比y大，則取1，反之就取0，即：

式中：P(x)、P(y)分別為點x、y處的灰度值大小。故BRIEF描述子可以表示為

如圖2所示，假設像素點V1繞圖像中心點旋轉θ角至像素點V2，r為像素點距圖像中心距離。設像素點V1坐標為(x1,y1)，像素點V2坐標為(x2,y2)，由三角關系可知：

圖2 BRIEF描述子旋轉不變性示意圖

寫成矩陣形式：

故對于N點對，可以得到如下式的描述子矩陣Sθ:

在計算旋轉后，描述子為

2 A-ORB算法設計

本文提出的A-ORB算法，首先通過圖像尺寸大小來確定所需要構建的金字塔的層數(shù)；接著針對每層金字塔圖像的大小來劃分網(wǎng)格；然后利用圖像的灰度值來計算特征點的提取閾值，對每層圖像金字塔中的網(wǎng)格按照一定順序提取特征點，若提取特征點數(shù)目滿足每層設定的特征點數(shù)便提前結束，以提高計算效率；最后采用四叉樹算法對提取的冗余特征點進行剔除。A-ORB算法流程如圖3所示。

圖3 A-ORB算法流程圖

A-ORB算法關鍵步驟如下：

1） 通過圖像的大小構造圖像金字塔，將其分為M層，若設圖像的寬度高度分別為W、H，則M層設定為：

式中：round[·]為取整函數(shù)。

2） 設定圖像的縮放因子為s(0＜s＜1)，設需要提取的特征點總數(shù)為N，分別計算出每層圖像金字塔的面積，將特征點均攤到每層圖像上。設圖像金字塔的總面積為S，則有：

單位面積的特征點數(shù)X為

第i(0 ≤i≤ (M－1))層需要提取的特征點數(shù)目為

在劃分特征點時往往不能完全劃分完整，將剩余的特征點全部歸于圖像金字塔的頂層：

高?；鶎有姓藛T的職業(yè)生涯基本都是單調(diào)無趣的。這就要求高校在工作之余，為他們搭建其他興趣交流平臺，讓他們在工作的同時學習到自身感興趣的知識和能力，只有這種氛圍持續(xù)存在，員工才會自我要求進步，只有進步才能推動工作的動力，提高工作效率。

3） 傳統(tǒng)ORB算法采用的檢測閾值T為一個常數(shù)，魯棒性較差，當場景明暗變化明顯時，容易造成特征點丟失的情況。本文算法根據(jù)圖像灰度信息計算出一種自適應提取閾值，若此閾值提取的特征點數(shù)目不滿足要求，則降低閾值至T/2，直到提取的特征點數(shù)目達到要求。

式中：λ為比例因子，一般取0.01；m為圖片中像素點的個數(shù)；分別為每個像素點的灰度值以及該圖像的灰度平均值。

4） 對每層圖像進行網(wǎng)格劃分，分成L×Z個大小相同的區(qū)域。劃分網(wǎng)格之后，從圖像金字塔的第一層開始遍歷網(wǎng)格進行特征提取，奇數(shù)層從圖像的左上方開始按照先行后列的方式往下提取特征點，偶數(shù)層從圖像的右下方按照先行后列的方式往上提取特征點。在提取過程中，對每個網(wǎng)格提取的特征點進行計數(shù)。如果總數(shù)大于等于Ni，則退出循環(huán)，結束該層特征點的提取。

5） 通過以上方法提取的特征點存在冗余，故本算法也采用四叉樹算法對冗余特征點進行剔除[14]。四叉樹算法中每個節(jié)點下至多有4個子節(jié)點。具體做法是：將輸入的圖像劃分成4個區(qū)域，逐步判斷每個區(qū)域中包含特征點數(shù)量，若該區(qū)域特征點數(shù)量大于1，則繼續(xù)分裂成4個節(jié)點，若等于1，則該區(qū)域不在劃分子節(jié)點并將該節(jié)點儲存，若等于0，則剔除該節(jié)點。這種劃分方法雖然能夠保證特征點均勻化，但是容易造成分割次數(shù)過多，降低算法運行速度，故本文在四叉樹算法分裂時限定分裂次數(shù)。當四叉樹算法分裂的節(jié)點數(shù)大于等于所需要提取的特征點數(shù)時便停止分裂，此時計算四叉樹算法節(jié)點內(nèi)Harris響應值，保留最大值對應的特征點，其余剔除。若只有一個特征點，則不進行計算，直接保留。具體流程如圖4所示。

圖4 改進四叉樹算法流程圖

6） 本文算法在對圖像提取特征點之后，也需要去除圖像的高頻部分，增加算法魯棒性。故先對圖像進行Gauss模糊處理，再計算圖像的描述子[15]。本文采用Gauss函數(shù)用于對圖像進行模糊處理。二維Gauss函數(shù)表達為

式中：x、y分別為像素點到x軸、y軸的距離；σ為Gauss函數(shù)的標準差。

3 實驗結果與分析

本實驗中，使用了OpenCV 3.2.0的計算機視覺庫，在Ubuntu 18.04操作系統(tǒng)上進行算法驗證，計算機的中央處理器（CPU）為AMD Ryzen5, 16 GB內(nèi)存。原始圖像來自于Mikolajczyk開源圖像庫，該圖像庫中 包 括Bark、Bikes、Boat、Leuven、Ubc、Graf等一系列圖像[2]。對圖像庫中包含圖像旋轉、圖像平移、視角變化、光照變換等不同圖像檢測實驗，驗證本文算法與傳統(tǒng)的ORB算法、文獻[7]所提的MA算法以及文獻[10]所提的S-ORB算法進行比較，檢測算法的優(yōu)劣性。

為了不失一般性，每組圖片均進行20次實驗，最后結果采用平均值。為了量化分布均勻度，采用文獻[2]的計算方法：從豎直、水平、45°和135°等4個方向以及中心、外圍對圖像進行區(qū)域劃分，分別統(tǒng)計每個區(qū)域內(nèi)的特征點數(shù)目，將其記作區(qū)域統(tǒng)計分布向量，計算該向量的方差V，均勻度u計算表達式如下：

根據(jù)式（17），均勻度越小，分布均勻度越高，特征點在圖像中分布越均勻，后續(xù)圖像匹配的精度就會越高。采用均勻度u和運行時間t作為評價指標，對圖像數(shù)據(jù)集進行測試。原始圖片以及測試結果見圖5。均勻度與運行時間統(tǒng)計見表1。

圖5 原始圖片及圖像提取4種算法結果

表1 分布均勻度與耗時比較

根據(jù)圖5及表1，在提取相同數(shù)目的特征點時（這里提取500個特征點），A-ORB算法相比傳統(tǒng)的ORB算法提取的特征點分布均勻度平均提高了16.77%，運行速率提高了39.81%，說明A-ORB算法優(yōu)于傳統(tǒng)的ORB算法。相較于MA算法，A-ORB算法運行速率提高了52.19%，分布均勻度下降了9.13%，分布均勻度下降的原因是因為MA算法是過量提取特征點，這雖然會提高分布均勻度，但會增加算法耗時。相較于S-ORB算法, A-ORB算法的分布均勻度提高了20.70%，運行速率減少了22.47%。這是由于S-ORB算法在特征提取時，易提前檢測，特征點也有冗余，雖然算法運行時間很快，但分布均勻度較差，造成后續(xù)圖像匹配進度不高。

在SLAM過程中，由于輸入圖像的清晰程度、復雜程度等不同，采用固定閾值ORB算法很難在一次圖像遍歷中獲得所需要的特征點，在遇到紋理缺失的場合（例如墻面）很有可能造成特征點丟失的情況出現(xiàn)，對后續(xù)相機位姿估計以及地圖構建帶來較大誤差，采用自適應閾值則可以增加算法的魯棒性。為了驗證動態(tài)閾值對于特征提取時間以及特征分布均勻度的影響，采用固定閾值傳統(tǒng)ORB算法以及自適應動態(tài)閾值ORB算法對同一圖像進行特征提取。采用運行時間t和特征點均勻度u作為指標，對圖5中的原始圖片進行測試，測試結果見圖6。

由圖6可以看出：在不同圖像序列中，使用自適應閾值對圖像進行特征點提取比使用固定閾值消耗時間更少，平均減少了10%以上，所得到的特征點分布度平均提高了12%以上。

圖6 固定閾值和自適應閾值ORB算法提取圖像數(shù)據(jù)集

提取特征點的目的主要是為了后續(xù)圖像匹配從而計算運動信息，故匹配精度也是衡量特征提取算法優(yōu)越性的重要指標，故本文采用圖像庫中的圖片對本算法以及其他3種算法進行匹配驗證，驗證本文算法在匹配精度方面的有效性。原始圖片如圖5所示，驗證結果見圖7，匹配精度與匹配時間對比見表2。

由圖7、表2可知：在匹配光照條件不同的Leuven圖片時，A-ORB算法在匹配精度上優(yōu)于傳統(tǒng)ORB算法63%以上，優(yōu)于MA算法17%以上，優(yōu)于S-ORB算法30%以上，在匹配時間上優(yōu)于傳統(tǒng)ORB算法3%以上，優(yōu)于MA算法8%以上。

表2 匹配精度與匹配時間對比

圖7 4種算法匹配原始圖像部分結果

在匹配模糊程度不同的Bikes圖像時，A-ORB算法在匹配精度上優(yōu)于傳統(tǒng)ORB算法45%以上，優(yōu)于MA算法13 %以上，優(yōu)于S-ORB算法35%以上，在匹配時間上優(yōu)于傳統(tǒng)ORB算法6%以上，優(yōu)于MA算法13%以上。

在匹配壓縮程度不同的Ubc圖像時，A-ORB算法在匹配精度上優(yōu)于傳統(tǒng)ORB算法14%以上，優(yōu)于MA算法7%以上，優(yōu)于S-ORB算法20%以上。

在匹配時間上優(yōu)于傳統(tǒng)ORB算法7%以上，優(yōu)于MA算法11%以上。綜上所述，本文所提出的A-ORB算法不僅加快了特征點的提取速度，也使得特征點分布更加均勻，匹配精度更高。

4 結 論

1） 針對傳統(tǒng)ORB算法所提取的特征點存在分布不均勻，聚集嚴重的問題，提出了一種A-ORB算法。

2） 本文所提出的A-ORB算法，相比于傳統(tǒng)ORB算法以及MA算法，在光照強度不同、模糊程度不同、圖片壓縮度不同等條件下，運行效率提高了30%以上，匹配精度提高了10%以上。

3） A-ORB算法更有利于后續(xù)圖像運動信息的計算。在接下來的工作中，將考慮增加描述子維度的方法等來提高特征點的區(qū)分度，進一步提高算法提取征點的分布均勻度和匹配精度。