一種基于LSD改進(jìn)的室內(nèi)直線特征匹配算法

李玉峰，張 宸

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

0 引言

隨著計(jì)算機(jī)技術(shù)的進(jìn)步發(fā)展，計(jì)算機(jī)視覺憑借其成本低、適用場(chǎng)景多的特點(diǎn)而被國(guó)內(nèi)外廣泛關(guān)注應(yīng)用，包括圖像檢測(cè)、圖像配準(zhǔn)、圖像拼接、三維重建技術(shù)，上述技術(shù)已經(jīng)被廣泛應(yīng)用到遙感圖像、醫(yī)學(xué)圖像、自動(dòng)駕駛等領(lǐng)域。特征檢測(cè)與匹配在其中起到了不可代替的作用?；谔卣鞯钠ヅ浞椒梢詫?duì)有遮擋、旋轉(zhuǎn)、縮放等圖片進(jìn)行快速良好的匹配，因此是目前圖像匹配中主流的研究方法。

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

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

1 LSD算法介紹

1.1 算法思想概述

LSD 是一種可以在線性時(shí)間內(nèi)達(dá)到亞像素級(jí)別精度的直線檢測(cè)算法，并且在實(shí)際運(yùn)用中不需要任何參數(shù)設(shè)置，所以在各種直線檢測(cè)場(chǎng)景下得到廣泛運(yùn)用。

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

圖1 Gradient和Level-Line

通過計(jì)算圖像中每個(gè)像素的梯度得到每個(gè)像素的level-line，進(jìn)而得到一張由每個(gè)像素level-line 構(gòu)成的圖，稱之為L(zhǎng)evel-line Field。如果其中部分level-lines 之間相互的角度差都不大于一個(gè)容忍值π，那這些連接組成的區(qū)域被叫做line support regions，如圖2所示。

圖2 line support region與外接矩形

而每一個(gè)line support region 又是line segment 的候選，line-support region 的邊緣被矩形所包圍，其方向由line-support region 的慣性主軸所決定。矩形中l(wèi)evel-line 角度與矩形角度差小于容忍值2π 的像素被稱為aligned points，如圖3 所示。一個(gè)line support region 中像素總數(shù)量和其中aligned points 的數(shù)量被用來評(píng)價(jià)是否可以被認(rèn)定為是一個(gè)line segment。

圖3 Aligned points示意

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

在圖4中我們可以看出很多直線特征因?yàn)閿?shù)字圖像像素點(diǎn)的緣故都存在鋸齒效應(yīng)，導(dǎo)致檢測(cè)出的特征出現(xiàn)斷連或者漏檢測(cè)現(xiàn)象。

圖4 鋸齒效應(yīng)及其帶來的誤差

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

圖5 上采樣優(yōu)化后的結(jié)果

1.2 LSD算法具體流程

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

（2）針對(duì)圖像中每個(gè)像素計(jì)算其梯度值和方向，然后根據(jù)梯度值進(jìn)行升序排列。

（3）根據(jù)設(shè)置的閾值，將梯度小于的像素點(diǎn)添加一個(gè)USED 狀態(tài)，其他像素點(diǎn)添加為UNUSED。

（4）根據(jù)設(shè)置的最大容忍值τ 進(jìn)行區(qū)域生長(zhǎng)Region Grow。

（5）計(jì)算通過Region Grow 算法得到的新區(qū)域的同性點(diǎn)密度

（6）根據(jù)截?cái)嚅撝?。如果密?，重新截?cái)嘀敝翝M足條件；如果密度>，計(jì)算錯(cuò)誤控制函數(shù)NFA。

（7）根據(jù)錯(cuò)誤控制閾值，如果<，輸出直線段數(shù)據(jù)。

（8）查看排序表是否還有UNUSED 的點(diǎn)，如果有，跳轉(zhuǎn)至步驟（4），否則結(jié)束程序。

2 Light-LSD算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 改進(jìn)算法重要概念

在新提出的改進(jìn)算法中，有一些概念至關(guān)重要。

如圖6所示，由于室內(nèi)長(zhǎng)廊的空間線條多為豎直方向的，所以設(shè)定Y表示線段特征的與豎直方向的偏離程度，已知線段起點(diǎn)坐標(biāo)為（,），終點(diǎn)為（,），那么new gradient由下式計(jì)算得出。

圖6 Gradient計(jì)算圖示

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

圖7 高低位線段

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

圖8 new distance示意

在后續(xù)處理中還需要判斷兩條線段特征是否重疊，在改進(jìn)算法中我們依照?qǐng)D9 規(guī)定重疊情況。

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

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

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

其中為當(dāng)前特征線段長(zhǎng)度，max 為最長(zhǎng)特征線段?？尚怕试礁撸硖卣骶€段長(zhǎng)度越長(zhǎng)，越有可能是一條完整描述物體特征的線段；可信率越低，代表特征線段很短，越有可能是一條對(duì)物體特征描述不完整的短線段。根據(jù)反復(fù)實(shí)驗(yàn)中產(chǎn)生的經(jīng)驗(yàn)閾值0.75 進(jìn)行篩選，所得線段能較好地描述圖像中物體特征。

2.2 Light-LSD算法設(shè)計(jì)思想

針對(duì)室內(nèi)長(zhǎng)廊場(chǎng)景下存在大量垂直線段特征，改進(jìn)算法的主要任務(wù)就是用盡可能少的線段特征描述出室內(nèi)結(jié)構(gòu)，原版LSD 造成大量冗余線段特征的原因是大量長(zhǎng)短不一的短線段描述了圖像中的同一處線特征。如圖10 所示，原版LSD 會(huì)在圖像中物體邊緣處產(chǎn)生多條短線段，但理想情況下只應(yīng)該有一條長(zhǎng)線段緊緊貼合物體邊緣處完整地描述物體的邊緣。

圖10 LSD算法效果和理想效果對(duì)比

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

2.3 Light-LSD算法流程

（1）計(jì)算各個(gè)特征線段的豎直梯度Y（new gradient）；

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

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

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

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

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

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

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

（9）根據(jù)可信率閾值進(jìn)行最終篩選；

（10）輸出特征線段進(jìn)行剩余匹配流程。

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

3.1 數(shù)據(jù)集介紹

本實(shí)驗(yàn)采用自建數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中圖片來自于酒店或?qū)懽謽鞘覂?nèi)走廊拍攝視頻中截取的多幀圖像。這些圖片中的場(chǎng)景大多包含明顯的線特征，并且有著不同的色彩、角度和光照條件，便于測(cè)試對(duì)比兩種算法的效果。如圖11所示。

圖11 部分?jǐn)?shù)據(jù)集展示

3.2 實(shí)驗(yàn)結(jié)果

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

圖12 LSD實(shí)驗(yàn)結(jié)果

圖13是改進(jìn)后的LSD特征匹配結(jié)果。

圖13 Light-LSD實(shí)驗(yàn)結(jié)果

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

圖14 實(shí)驗(yàn)結(jié)果局部對(duì)比

圖15 展示了更多實(shí)驗(yàn)結(jié)果中的局部特征提取效果對(duì)比。

圖15 部分對(duì)比實(shí)驗(yàn)結(jié)果

此外在實(shí)驗(yàn)中還統(tǒng)計(jì)對(duì)比了原LSD 和改進(jìn)LSD的運(yùn)行效率，如表1所示。

表1 LSD與Light-LSD算法在部分實(shí)驗(yàn)圖像上的性能對(duì)比

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

效率提高比例按照下式計(jì)算，其中代表 原 版LSD 計(jì)算 時(shí) 間，代 表改進(jìn)LSD計(jì)算時(shí)間。

4 結(jié)語

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