一種基于LSD改進的室內直線特征匹配算法

李玉峰，張 宸

（沈陽航空航天大學電子信息工程學院，沈陽 110000）

0 引言

隨著計算機技術的進步發展，計算機視覺憑借其成本低、適用場景多的特點而被國內外廣泛關注應用，包括圖像檢測、圖像配準、圖像拼接、三維重建技術，上述技術已經被廣泛應用到遙感圖像、醫學圖像、自動駕駛等領域。特征檢測與匹配在其中起到了不可代替的作用。基于特征的匹配方法可以對有遮擋、旋轉、縮放等圖片進行快速良好的匹配，因此是目前圖像匹配中主流的研究方法。

基于特征的圖像匹配方法，是在模板圖像和待匹配圖像中提取特征，然后根據二者的相似性進行匹配，目前基于特征點匹配的方法有SIFT 算法、SURF 算法、Harris 角點檢測法等。其中SIFT 算法可謂是最著名的特征點提取算法之一，但由于其特征提取過程需要大量時間，算法整體運行效率難以滿足實時需求。近年提出的ORB 算法不但繼承了SIFT 算法的旋轉尺度不變性，還對計算流程進行了優化，使得運算效率更高，可更快地完成圖像精確匹配，因此ORB 算法被廣泛應用到各種計算機視覺實時系統中。但上述這些算法全部是基于點特征對圖像進行匹配，如果在室內長廊等弱紋理場景下，通常空間結構簡單，點特征難以提取且分布不均勻；相反這些場景存在很多直線，并且這些直線段特征對視角和光照變化具有很好的魯棒性，通過少量的線段即可勾勒出空間的整體結構。因此直線匹配就成為室內長廊等弱紋理場景中新的研究熱點。Bose 等人利用圖像的深度信息簡化了邊緣檢測計算量，提高了算法運行效率，但算法過于依賴深度圖像，在深度攝像頭未普及的情況下很難推廣應用。目前主流的直線特征匹配算法是文獻［4］提出的LSD算法。其算法通過對圖像的灰度進行求導得到的梯度提取出直線，具有良好的特征提取能力。但LSD 仍存在一些問題，如重復提取特征線段、特征線段斷連、長度過短的無意義線段。后來Akinlar等又提出了EDLines 算法，基于像素之間的梯度幅度變化進行線段檢測，并且可以實時得出結果，適用于需要實時性的系統。但由于EDLines算法中判斷線段的機制，導致圖像中較長邊緣處容易出現特征線段斷連的問題。

針對上述問題，研究提出了一種基于LSD改進的算法Light-LSD，通過對線段起始點以及各線段之間距離進行分析，將斷連線段重新進行連接，并剔除重復提取的冗余特征線段，最后根據自適應閾值剔除沒有特征表現力的低質量線段。實驗表明，改進后的算法有效剔除了大量冗余特征線段并能夠保留大部分具有特征表現力的線段，減少計算負擔提高算法計算效率。

1 LSD算法介紹

1.1 算法思想概述

LSD 是一種可以在線性時間內達到亞像素級別精度的直線檢測算法，并且在實際運用中不需要任何參數設置，所以在各種直線檢測場景下得到廣泛運用。

在LSD 算法中，Gradient 梯度和level-lines是最重要的兩個概念，如圖1所示。

圖1 Gradient和Level-Line

通過計算圖像中每個像素的梯度得到每個像素的level-line，進而得到一張由每個像素level-line 構成的圖，稱之為Level-line Field。如果其中部分level-lines 之間相互的角度差都不大于一個容忍值π，那這些連接組成的區域被叫做line support regions，如圖2所示。

圖2 line support region與外接矩形

而每一個line support region 又是line segment 的候選，line-support region 的邊緣被矩形所包圍，其方向由line-support region 的慣性主軸所決定。矩形中level-line 角度與矩形角度差小于容忍值2π 的像素被稱為aligned points，如圖3 所示。一個line support region 中像素總數量和其中aligned points 的數量被用來評價是否可以被認定為是一個line segment。

圖3 Aligned points示意

如果在所有被算法判定為aligned points 的像素外圍接一個矩形框，這個矩形框就是被檢測出的線段特征。并且LSD 算法還會采用Region Grow 算法對檢測出的線段特征進行增長，以確保最大程度提取出圖像中的線段特征。Region Grow 會從被標記為UNUSED 的有序像素中取一個像素作為起始點，并將其像素的levelline 角度定義為region angle（區域角度），接著遞歸地計算其鄰居像素的角度和region angle（區域角度）的差值，如果差值小于容忍值τ，那么將該像素標記為USED，并且按照下面公式更新區域角度，其中是在區域范圍之內的。

在圖4中我們可以看出很多直線特征因為數字圖像像素點的緣故都存在鋸齒效應，導致檢測出的特征出現斷連或者漏檢測現象。

圖4 鋸齒效應及其帶來的誤差

因此LSD 算法對圖像像素進行梯度計算之前，還會有一步預處理，通過高斯上采樣對圖像進行模糊處理，盡量消除鋸齒效應帶來的影響。圖5展示了同樣的輸入圖像在經過高斯上采樣處理后算法效果得到了顯著提升。

圖5 上采樣優化后的結果

1.2 LSD算法具體流程

（1）對圖像進行二值化處理得到灰度圖，并以采樣率=0.8對圖像進行上采樣。

（2）針對圖像中每個像素計算其梯度值和方向，然后根據梯度值進行升序排列。

（3）根據設置的閾值，將梯度小于的像素點添加一個USED 狀態，其他像素點添加為UNUSED。

（4）根據設置的最大容忍值τ 進行區域生長Region Grow。

（5）計算通過Region Grow 算法得到的新區域的同性點密度

（6）根據截斷閾值。如果密度<，重新截斷直至滿足條件；如果密度>，計算錯誤控制函數NFA。

（7）根據錯誤控制閾值，如果<，輸出直線段數據。

（8）查看排序表是否還有UNUSED 的點，如果有，跳轉至步驟（4），否則結束程序。

2 Light-LSD算法設計與實現

2.1 改進算法重要概念

在新提出的改進算法中，有一些概念至關重要。

如圖6所示，由于室內長廊的空間線條多為豎直方向的，所以設定Y表示線段特征的與豎直方向的偏離程度，已知線段起點坐標為（,），終點為（,），那么new gradient由下式計算得出。

圖6 Gradient計算圖示

如圖7 設定坐標值較小的線段為低位線段，坐標值較大的線段為高位線段，且線段的方向皆是從低位到高位，如圖7所示。

圖7 高低位線段

new distance 表示兩特征線段之間的豎直距離，如圖8所示。

圖8 new distance示意

在后續處理中還需要判斷兩條線段特征是否重疊，在改進算法中我們依照圖9 規定重疊情況。

圖9 兩線段排列的三種方式

如果符合圖中情況（a），兩特征線段在Y 軸上的投影沒有重合部分，我們稱兩特征線段不相交；如果符合情況（b），兩特征線段在Y 軸上的投影有部分重疊，我們稱兩特征線段相交；如果符合情況（c），其中一特征線段在Y 軸上的投影被另一特征線段在Y 軸上的投影完全覆蓋，我們稱兩特征線段相包含。

特征線段的可信率代表線段是有效線段的概率，由下式計算得出：

其中為當前特征線段長度，max 為最長特征線段。可信率越高，代表特征線段長度越長，越有可能是一條完整描述物體特征的線段；可信率越低，代表特征線段很短，越有可能是一條對物體特征描述不完整的短線段。根據反復實驗中產生的經驗閾值0.75 進行篩選，所得線段能較好地描述圖像中物體特征。

2.2 Light-LSD算法設計思想

針對室內長廊場景下存在大量垂直線段特征，改進算法的主要任務就是用盡可能少的線段特征描述出室內結構，原版LSD 造成大量冗余線段特征的原因是大量長短不一的短線段描述了圖像中的同一處線特征。如圖10 所示，原版LSD 會在圖像中物體邊緣處產生多條短線段，但理想情況下只應該有一條長線段緊緊貼合物體邊緣處完整地描述物體的邊緣。

圖10 LSD算法效果和理想效果對比

Light-LSD 是在LSD 算法的基礎上，對LSD提取出的特征線段進行合并、剔除處理，以求達到用少量必要的線段描述出完整的物體邊緣特征。對于LSD 提取出的大量聚集堆疊在一起的特征線段，首先兩兩計算線段的距離和角度，如果距離很近角度方向相似，那么判定兩條線段在描述同一個物體邊緣特征，對其進行合并、剔除操作。對LSD 提取出的所有線段進行如上操作，最終一束聚集的短線段會被合并成一條完整的長線段，大大減少了特征線段的數量，為下一步特征匹配減輕了資源消耗，進而提升算法整體效率。

2.3 Light-LSD算法流程

（1）計算各個特征線段的豎直梯度Y（new gradient）；

（2）取第一個特征線段作為線段，依次計算和其他特征線段的距離和角度差；

（3）如果距離小于閾值且角度差也小于閾值，那么進入步驟（4），否則跳至步驟（9）；

（4）判斷、兩線段的重疊程度，如果是情況1，進入步驟（5）；如果是情況2，進入步驟（6）；如果是情況3，進入步驟（7）；

（5）將低位線段的終點重新賦值成高位線段的終點值，并刪除高位線段；

（6）將低位線段的終點重新賦值成高位線段終點值，并刪除高位線段；

（7）直接刪除高位線段；

（8）對所剩線段計算可信率，并根據可信率由高到低排序；

（9）根據可信率閾值進行最終篩選；

（10）輸出特征線段進行剩余匹配流程。

3 實驗結果

3.1 數據集介紹

本實驗采用自建數據集進行實驗，其中圖片來自于酒店或寫字樓室內走廊拍攝視頻中截取的多幀圖像。這些圖片中的場景大多包含明顯的線特征，并且有著不同的色彩、角度和光照條件，便于測試對比兩種算法的效果。如圖11所示。

圖11 部分數據集展示

3.2 實驗結果

圖12是原版LSD對于圖像的特征匹配效果。

圖12 LSD實驗結果

圖13是改進后的LSD特征匹配結果。

圖13 Light-LSD實驗結果

可以看出LSD 提取出了大量的線特征，但在門框邊緣處，存在著大量的長度相似，距離接近的線段。如下圖所示截取了對比實驗結果圖的左下角部分，可以看出有多條特征線段被描繪在門框邊緣，這些線段描繪的是同一條空間特征，屬于重復描述。并且這些線段長度并未完全覆蓋門框特征，也屬于不完整描述。圖14 為算法改進前后的同一處細節結果，通過對比觀察可以明顯看出，改進LSD 提取出的特征線段更長、更簡潔，可以用數量更少、質量更高的線段描述出門框的特征。

圖14 實驗結果局部對比

圖15 展示了更多實驗結果中的局部特征提取效果對比。

圖15 部分對比實驗結果

此外在實驗中還統計對比了原LSD 和改進LSD的運行效率，如表1所示。

表1 LSD與Light-LSD算法在部分實驗圖像上的性能對比

冗余特征消除比例按照下式計算，其中代表原版LSD 提取特征數量，代表改進LSD提取特征數量。

效率提高比例按照下式計算，其中代表 原 版LSD 計算 時 間，代 表改進LSD計算時間。

4 結語

本文提出了基于LSD 改進的線特征提取算法Light-LSD，實驗表明該算法在室內長廊等場景下運行效果良好，能完整地提取出圖片中主要的線段特征，并且相較于原版LSD，Light-LSD能剔除60%～80%的冗余線段特征，減少匹配過程中的計算資源消耗，在特定場景下的算法運行效率可提升高達30%，對SLAM等依賴特征匹配算法的研究領域有重要影響意義。