基于Edline線特征的圖像快速匹配算法?

張 震 王永雄

（上海理工大學光電信息與計算機工程學院 上海 200093）

1 引言

圖像匹配是根據不同視角或者不同傳感器獲得的圖像，提取圖像中的相關信息，如紋理、灰度、結構等的相似性，通過一定的匹配算法將兩幅或者多幅圖像進行匹配。圖像匹配是計算機視覺領域中的研究熱點，高精度的圖像匹配和低的時間計算成本能夠更好地應用在行為識別［1～3］與 VSLAM［4～7］（Visual Simultaneous Localization And Mapping）等算法當中。圖像匹配算法主要可分為以灰度［8］和特征［9］為基礎的圖像匹配方法。其中基于特征的匹配算法，對圖像中的物體旋轉、光照變化和遮擋等方面具有更好的魯棒性?；诨叶刃畔⒌膱D像匹配算法，一般通過利用相關函數、協方差函數等測量極值進行匹配，能夠獲得較高的匹配精度。由于灰度信息對光照變化敏感，因此基于特征的圖像匹配作為主要的研究方法。

SIFT［10］由于其旋轉和尺度不變性等，受到研究者們廣泛的關注，常用于特征的圖像匹配，但是在SIFT特征點提取過程中占用了很長的時間，因此導致匹配時間較長，難以進行實時性的應用。最近提出的ORB［9］特征點，不僅具有SIFT的旋轉、尺度不變性等性質，而且具有較低的時間成本，能夠快速地得到精確圖像匹配對，因此研究者們將其應用在VSLAM當中，得到很好的效果。但是針對于點特征，當環境中特征點缺乏或者分布不均勻時，難以提取到能夠準確代表環境信息的高質量的特征，這樣使得無法獲得高精度的圖像匹配，難以在實際中得到應用。而且目前大多數的基于特征的圖像匹配算法難以同時滿足較高的實時性和準確性，且隨著光照的變化和特征分布不均勻的場景的出現，圖像匹配出現較高的錯誤率，難以在實際應用中得到良好的表現。

由于在室內環境中包含豐富的線特征，并且檢測的邊緣和線段特征對于自然界的光照變化并不敏感。為了在一些低紋理環境中如光滑的走道墻壁等，能夠得到高精度的圖像匹配，李海豐等［11］使用了點和面特征來進行圖像匹配，而這種方法在平面環境中會有較好的表現，但是在非平面環境中，錯誤率很高。近幾年，很多研究將邊緣［12～14］信息應用在圖像匹配中，例如Bose L［12］等提出利用一種基本的邊緣檢測算法，首先對先前深度圖像進行深度邊緣檢測，所獲取到的信息來確定當前深度圖像邊緣的區域，雖然這種方法與在整個深度圖像上進行邊緣檢測搜索相比，節省大量計算成本，但是邊緣檢測完全依賴于所獲得的深度圖像。雖然室內環境中包含豐富的線特征，但是難以提取到高質量的線段信息，因此大多數線特征便只能應用在激光掃描儀［15］上。為了能檢測和提取到高質量的線段信息，大多數線段匹配的研究發現使用一些策略交叉線段以形成交叉點，利用這種交點和線段之間的關系進行匹配，會得到不錯的匹配效果。例如Zhang等［16］利用外觀相似性和幾何約束來進行線段匹配，Li K等分別提出一種Ray-Point-Ray［17］結構描述符和 Line-Junction-Line［18］結構描述符進行線段的匹配，均取得很高準確度的匹配效果，但是，這些線段提取和匹配方法，提取過程復雜，而且具有很高的時間計算成本。因此，為了降低時間成本，同時能夠得到更多的高精度圖像匹配對，在實際應用中有良好的效果，提取高質量的線特征至關重要。

綜上所述，本文針對以上問題，對圖像匹配提出一種基于Edline線特征的圖像快速匹配算法。首先利用邊緣檢測算法進行邊緣繪制，產生像素鏈，從像素鏈中進行線段的提取，并通過設置線段長度進行閾值參數，來構建完整連通的線特征，并利用RANSAC［19］算法去除掉異常線特征，以此減少計算時間。構造線段描述符進行匹配。通過與LSD（Line Segment Detector）［20］和 LBD（Lind Band Descriptor）［21］線段提取的方法在時間和效果上進行對比，本方法不僅在低紋理和結構化場景中能夠獲取高精度的圖像匹配，而且在實時性上均有良好的表現，可在行為識別或VSLAM中得到良好的應用效果。

2 算法原理

基于Edline線特征的圖像匹配算法主要由Edline線段的提取描述和匹配。Edline線段提取描述分為：線段的檢測和提取，利用LBD描述子對所提取的線段進行描述和匹配。其結構流程圖如圖1所示。雖然對于在低紋理和結構化場景中，線特征表現豐富，但是線特征往往會存在線段穩定性和連通性較低的問題，因此利用線段長度閾值參數設置，來增強線特征的連通性和完整性，以此提升在圖像匹配中的性能。

圖1 結構流程圖

3 Edline線特征提取算法

在低紋理場景下線特征表現優異，但是當缺少線特征之間的關聯信息差異時，會產生很多異常的線段，從而影響圖像的匹配效果。為了得到良好的匹配效果，本文提出了一種改進的低計算量的線段提取方法，首先利用邊緣檢測，再利用邊緣檢測算法進行邊緣繪制，并產生連續的像素鏈；其次通過最小二乘線擬合的方法，從連續的像素鏈中提取線段；最后利用設置線段長度閾值參數和RANSAC算法消除錯誤的線段。其過程如圖2所示。

傳統的線段提取算法，通常提取出獨立、不相交、不連續的線段。Edline線段提取算法：首先對平滑處理后的圖像計算其圖像的梯度大小和方向。某一像素點上的總梯度大小為

圖2 線特征提取過程

其中Gx，Gy分別表示水平和垂直方向的梯度值。

通過比較在每個像素的水平和垂直的梯度大小來定義錨點，閾值的設置間接的反應錨點的數量，以及邊緣的繪制。通過連接錨點構造像素鏈，算法過程如下：首先初始選擇一個起始點（x，y），當水平邊緣通過該點時，通過比較（x，y+1），（x，y），（x，y-1）三點處的像素梯度值，最大點定義為錨點（X，Y）；若水平邊緣通過該點（X，Y），則比較（X-1，Y+1），（X-1，Y），（X-1，Y-1）處的像素梯度值，選擇最大值，與（X，Y）相連，直到點（Xi，Yi）不是邊緣像素時。

對構建的像素鏈，利用最小二乘線擬合的方法，進行線段的擬合提取，采用偏差絕對值之和最小的原則進行擬合：

其中xi，yi是像素點坐標。對擬合的線段，計算線段長度，以及線段端點的位置，通過計算兩條相鄰線段端點的歐式距離，并設置閾值參數，來構建完整連通的線段，使用RANSAC算法來剔除異常線段，同時根據兩線段在方向和距離上的差異，通過設置線段中點間的距離閾值，以及方向差大小來合并兩條線段。

4 構造描述子

對線段進行提取后，構造線特征描述子，采用LBD描述符進行匹配，進行線特征的匹配，首先對提取的特征進行預處理，消除無法匹配的線特征，降低匹配的維度，其過程分為：條帶表示線段支持域和條帶描述子的構建。首先對圖像構建尺度空間金字塔，在每層尺度空間提取線段。通過檢測幾何屬性以及局部外觀相似性，來減少匹配的維度，加快匹配的速度。在每一層空間中都能獲得一組線段，將尺度空間中線段進行重組，相對應的線段在同一LineVec中。

4.1 線段支持域

線段描述符由線段支持域計算得到，利用條帶{B1;B2;…;Bm}的形式表示，m為條帶的數目，w是每個條帶的寬度。引入構成局部二維坐標系dl，d⊥，將線段支持域中的點像素的梯度投影局部二維坐標系：

其中g為像素點梯度，g'為局部坐標系中的投影像素。引入全局高斯函數來緩和在線段垂直方向上微小變化的敏感度，以及引入局部高斯函數降低邊緣效應，避免描述符的突變。

4.2 構造條帶描述符

利用定義的線段條帶構建條帶描述子，計算每一個條帶的描述符BDj，由它的兩個相鄰條帶Bj-1和Bj+1構成。LBD描述子由條帶的描述子{BDj}組成：

其中條帶的描述子BDj是條帶Bj的第k行像素的梯度值，對于條帶中某一行，累積該行中四個方向上像素的梯度：

k表示在條帶 Bj的第k行；高斯權重 λ=fg（k）fl（k），則某一行像素有四個方向的梯度，通過累計條帶條帶Bj相關聯的所有行的梯度信息，構造第j個條帶的描述符矩陣，計算BDj由BDMj矩陣的平均向量Mj和標準方差向量Sj，通過對LBD的均值和標準方差部分分別進行歸一化，同時對每個LBD維度進行約束，得到單元LBD。

5 實驗結果和分析

5.1 數據集

本實驗采用了視覺SLAM領域中權威數據集中的多幀圖像進行實驗，有KITTI，TUM RGB-D。KITTI是目前國際上最大的自動駕駛場景下的計算機視覺算法評測數據集。該數據集用于評測立體圖像（stereo），光流（optical flow），視覺測距（visual odometry），3D物體檢測（object detection）和3D跟蹤（tracking）等計算機視覺技術在車載環境下的性能。包含市區、鄉村和高速公路等場景采集的真實圖像數據，每張圖像中最多達15輛車和30個行人，還有各種程度的遮擋與截斷。整個數據集由389對立體圖像和光流圖，39.2 km視覺測距序列以及超過200k 3D標注物體的圖像組成。TUM RGB-D是包含了RGB-D數據和地面實況數據的大型數據集，為視覺測距和視覺SLAM系統的評估建立新的基準，并且包含Microsoft Kinect傳感器沿著地面實況軌跡的顏色和深度信息，全幀速率30Hz，傳感器分辨率為640×480，提供不同類別的圖像數據：手持式SLAM，結構與紋理，動態對象，三維物體重建等。如樣本（a）是TUM RGB-D是數據集中的一幀圖像，記錄一個辦公場景辦公桌環境，有一張桌子，一臺傳真機，一臺固定電話，一個鍵盤等，其中場景特征豐富。樣本（b）是TUM RGB-D數據集中一幀圖像，記錄室內墻壁環境，包含三腳架，墻壁等，其中特征缺乏。樣本（c）是KITTI數據集中的一幀圖像，記錄室外道路上場景，包含建筑物，馬路，樹木等，特征分布豐富。

5.2 實驗分析

光照條件的變化、無紋理表面等都將影響視覺SLAM中的匹配。為了證明本方法能夠在低紋理和特征不豐富的場景中有效地進行匹配運算，我們將本方法應用于多個數據集進行驗證，所用實驗設備為Inter Core i7-6500U和16 Gib RAM。我們采用了KITTI和TUM中的數據，選取有一定角度視差的兩幀圖像，分別在點特征豐富和特征不豐富情況下進行實驗。匹配效果如圖3所示。

圖3 線匹配

由上述匹配結果可以看出，在特征豐富的環境如圖3（a）中，線特征能夠很好地提取和匹配，能夠得到精確的線匹配對。在一些結構化特征不豐富的場景（如圖3（b））中，當遇到空白的墻壁時，難以提取到特征，但是在三腳架上仍然能夠得到精確的匹配對。低質量的特征提取與匹配將降低VSLAM的性能，匹配數量如表1。為了驗證提出的方法計算復雜度，表2、表3列出不同場景中所用時間數據。

表1 特征提取匹配對數量對比

表2 特征提取、描述和匹配時間占比

表3 不同檢測匹配時間對比

從以上3個表格中可以看出：在樣本（a）中，線特征相對豐富，檢測匹配方法在樣本（a）中能獲得足夠的匹配對數，但所需時間為47.66ms，相比使用ORB特征點、LSD+LBD中縮短了10.67%、54.79%。特別在樣本（b）中，本文的方法不僅能夠提取到比ORB更多的精確匹配對數，此時難以提取到足夠的點特征，而且在時間上縮短了5.15%。在樣本（c）中，雖然時間上有所增加，但是同樣能夠獲得足夠的精確匹配對數。在樣本（b）當中，由于點特征的缺乏，無法提取和獲得足夠多的特征點匹配對數，但是線特征能夠良好地檢測和匹配出來，能夠在樣本（b）中獲得足夠的線特征匹配對數，并且相比較使用傳統的LSD+LBD的方法，無論在運行時間還是匹配對數上均表現優勢。通過這些比較，驗證了我們方法的實時性，能夠大幅地提高圖像匹配能力，有利于提高視覺SLAM的后續定位和建圖。

綜上，本文提出的方法對于特征豐富的場景實時有效，在一些低紋理和特征不豐富的場景中，難以提取到足夠的點特征，此時能夠生成足夠高質量的線特征匹配對，并且在實時性上明顯優于傳統的線特征方法。

6 結語

本文針對非結構化和點特征缺失場景中提出了一種改進的Edline線特征的圖像快速匹配算法。該方法彌補低紋理和特征分布不均勻環境下點特征的不足。采用Edline線特征可應用在低紋理環境或者復雜結構場景下，通過使用RANSAC算法和線段長度參數閾值設置，構建完整的線段，優化了匹配算法，提升了算法實時性。利用穩健的LBD描述子，能夠獲得高準確度的圖像匹配效果，并在實時性上達到了良好效果。