基于邊緣塊的線段提取方法

申超勝，張敬峰，林靖宇

(廣西大學 電氣工程學院，南寧 530004)

1 引 言

直線檢測是圖像處理和計算機視覺的經典問題.直線包含對象的重要信息，特別是在人造場景中直線是常見特征.直線特征應用于很多任務，如圖像匹配[1，2]，道路檢測[3，4]，三維重建[5，6]等.直線提取方法的優劣將會直接影響到高層次圖像處理的效果.

直線特征的檢測方法主要分為兩類：基于梯度幅值和基于梯度方向.

基于梯度幅值的方法是在邊緣圖像上進行的，而不是輸入圖像，所以這類方法首先需要邊緣檢測器從輸入圖像中提取到邊緣圖.Hough變換法正是一種在圖像邊緣圖上實現的方法，該方法對輸入圖像進行邊緣檢測，然后進行Hough變換提取直線，最后將直線段分割，得到直線段輸出.之后有大量基于Hough 變換法的改進版本出現[7-10].但是基于Hough 變換法的算法，對于有較高邊緣密度的圖像會得到大量錯誤結果，而且由于其忽略邊緣點方向信息，常常會得到異常方向的直線段.為了解決這些問題，Akinla和Topal[11]提出了一個快速、無參數的線段檢測器，命名為EDLines.其優點是運行時間快，抗噪聲能力強，但他們是基于邊緣段進行的，線段檢測結果在很大程度上受到了邊緣段檢測算法的影響，容易丟失低梯度線段.Xiaohu Lu[12]等人認為，邊緣段在檢測過程中已經丟失部分重要的信息，應該從原始圖像或者是從包含圖像的所有結構信息的邊緣圖中檢測線段.因此他們提出了一個基于邊緣圖的直線檢測算法.該方法易于檢測低梯度區域的線段，但也會有過濾部分真實短線段的不足，使得圖像的局部細節不夠完整.

基于梯度方向檢測線段的思想最早由Burns[13]等人在1986年提出.該方法計算圖像像素點的梯度方向，將具有大致相同梯度方向的像素點進行分組得到直線圖像區域.由于只用到梯度方向信息，檢測效果并不理想.2010 年，Gioi 等人[14]在Burns 等人[13]的基礎上提出了一種快速的線段檢測方法，稱為LSD算法.他們的方法同時使用了像素點的梯度方向信息和梯度幅值信息，選取梯度幅度極值處的像素點作為種子點，根據梯度角方向開始區域生長，標記這些像素點為已使用，并且更新區域角度，之后將區域近似成矩形候選直線段.LSD算法能精確地檢測線段，通過有效地結合梯度方向和亥姆霍茲原理來驗證線段，在一定水平上控制錯誤檢測的數量.但是LSD算法的梯度幅度極值是一個安全閾值，會消除一些有用的線段，并且LSD算法會在梯度方向不穩定的區域將長線段分割為多條線段，這就導致了檢測結果會出現線段聚集，以及線段方向不正確等情況.

基于上述分析，為了解決由于梯度信息不足而導致線段被消除的問題，本文提出一種基于邊緣塊的直線檢測算法.通過分析邊緣圖中邊緣點本身的連通域性質，將邊緣點聚合為邊緣塊，最大限度的保留了邊緣圖的信息.之后以鄰接矩陣的方式統計邊緣塊之間的位置信息，根據鄰接矩陣和深度優先搜索算法以及直線的幾何特征，使得邊緣塊連接集合能夠保留物體的輪廓信息，最后對邊緣塊連接集合進行拆分處理，從而完成直線檢測.本文的代碼已經公布在GitHub(1)https：//github.com/GXUVision/LineDetection.

2 基于邊緣塊的直線檢測算法

本文的算法分為以下3個過程：

1)邊緣塊提取

首先提取圖像中的邊緣，并將邊緣處理為單像素寬度.根據邊緣點本身的連通域性質，對邊緣點進行標注.通過對標注結果進行分析，將邊緣點組合為各種類型的邊緣塊.

邊緣塊提取將孤立的邊緣點連接成具有方向的邊緣塊，實現將點特征聚合為塊特征.

2)路徑提取

邊緣塊繼承了邊緣點本身的連通域性質，本文統計每個邊緣塊之間的位置關系，得到了鄰接矩陣.在鄰接矩陣上使用深度優先算法(Depth-First-Search，DFS)，得到了初始路徑集合.

路徑提取將邊緣塊連接成帶有物體幾何特征的線條，實現將塊特征聚合成線特征.

3)直線檢測

對初始路徑集合中的路徑進行篩選，利用直線的幾何定義，將符合直線定義的路徑歸為直線.對于初始路徑集合中不符合直線定義的所有路徑，根據每條路徑的曲折度，將路徑分離為兩部分.之后判斷分離的部分是否是直線，不符合的部分將再次分離，這樣循環分離，直到所有分離的部分都符合直線定義.

圖1 論文工作框圖Fig.1 Paper work block diagram

本文將在第3節中描述邊緣塊提取過程，在第4節中描述路徑提取過程，在第5節中描述直線檢測過程.本文工作框圖如圖1所示.

3 邊緣塊提取

在邊緣圖中，每條邊緣都由大量的邊緣點組成，點與點之間的連通關系構成線，而這種連通關系簡單的說就是位置的相對關系，存在一定的規律，交叉和重疊會影響這種規律.考慮到邊緣圖中的邊緣點較多，且相互之間的連通域關系并不明顯，本文將邊緣點聚合成邊緣塊，以邊緣塊的形式來代表邊緣，能在有效減少重復運算的同時，又能最大限度的保證邊緣信息的完整.

以圖像的左下角為坐標原點，圖像的寬度為X軸正方向，圖像的高度為Y軸正方向，每個像素點作為一個坐標值.本文將邊緣塊分為3類：將平行于X軸的邊緣塊定義為水平邊緣塊ehor，將平行于Y軸的邊緣塊定義為豎直邊緣塊ever，將由單個邊緣點組成的邊緣塊定義為單個邊緣塊es：

ehor={(xf，yf)，(xl，yl)|yf=yl}

(1)

ever={(xf，yf)，(xl，yl)|xf=xl}

(2)

es={(xf，yf)，(xl，yl)|xf=xl，yf=yl}

(3)

其中(xf，yf)，(xl，yl)分別表示邊緣塊中首尾像素點坐標.

邊緣塊類型如圖2所示.

圖2 標準邊緣塊Fig.2 Standard edge block

邊緣塊提取是基于圖像的邊緣進行的.在提取圖像邊緣后，對邊緣圖進行標注，根據對標注結果進行分析和處理，將經過標注處理的邊緣點聚合成邊緣塊.本文將在3.1節中描述標記過程，在3.2節中描述檢測過程.邊緣塊提取的整體流程效果圖如圖3所示.

3.1 邊緣點標注

邊緣點之間存在著本身固有的連通域性質，通過對邊緣點進行標注，讓連通域性質更好的顯現.

首先采用CannyPF算法[12]提取圖像的邊緣E，在這一過程中為了方便后續處理，在保證每條邊緣不斷裂的情況下，將每條邊緣處理為單像素寬度.之后在每個邊緣點八鄰域的基礎上，定義了3×3-ε鄰域：

(4)

其中Ii為3×3-ε鄰域中第i個邊緣點的灰度值，a0表示為當前邊緣點的位置.

(5)

圖3 邊緣塊提取整體流程效果圖Fig.3 Process of edge block extraction

在這基礎上，開始對邊緣點進行初步標注，將lcmp值屬于單個邊緣塊的邊緣點標記為-1，屬于豎直邊緣塊的邊緣點標記為1，屬于水平邊緣塊的邊緣點標記為3.同時將邊緣圖中不符合3種條件的邊緣點標記為-1，將不在邊緣上的像素點標注為0.

之后為了更好地區分每個邊緣點的界限，在3×3-ε鄰域的基礎上引入了特征角公式LCN(a0)：

(6)

其中ai的值與公式(4)中定義一樣.

遍歷邊緣圖中的所有邊緣點，計算每個邊緣點的LCN(a0)值.當任意邊緣點滿足以下兩個條件，即其初始標注值為-1，并且滿足LCN(a0)>0，則將這個邊緣點的標注值修改為9.將不滿足條件的邊緣點的標注值修改為-1，至此所有邊緣點都完成標注.

3.2 邊緣點擬合

在這節中，根據3.1節中的標注結果，將邊緣圖上的邊緣點聚成邊緣塊.從邊緣圖的左下角開始，按行掃描，對于每個邊緣中的邊緣點，考慮以下4種情況：

1)若在其3×3-ε鄰域中，a1和a3位置上的像素點的標注值為0或9，則將當前邊緣點歸類為單個邊緣塊；

2)若在其3×3-ε鄰域中，a1位置上像素點的標注值不為0而和a3位置上邊緣點的標注值為0，則向當前邊緣點的a1方向掃描，遇標記值為0或9的像素點后停止掃描，將當前像素點和掃描期間遇到的像素點整合為一個豎直邊緣塊；

3)若在其3×3-ε鄰域中，a3位置上像素點的標注值不為0而和a1位置上邊緣點的標注值為0，則向當前像素點的a3方向掃描，遇標記值為0或9的像素點后停止掃描，將當前像素點和掃描期間遇到的像素點整合為一個水平邊緣塊；

4)若在其3×3-ε鄰域中，a1和a3位置上像素點的標注值都不為0，則分別向當前像素點的a1和a3方向掃描，遇標記值為0的像素點后停止掃描，統計a1和a3方向掃描得到的像素點個數n1、n3，考慮兩種情況：

①如果n1≠n3，選擇向max{n1，n3}的方向統計邊緣塊.如果n1較大，則往a1方向統計，將當前像素點和掃描期間遇到的像素點整合為一個豎直邊緣塊；如果n3較大，則往a3方向統計，將當前像素點和掃描期間遇到的像素點整合為一個水平邊緣塊.

②如果n1=n3，則計算當前已統計出的水平邊緣塊和豎直類邊緣塊的個數mh，mv.若mh>mv，則往a3方向進行統計，將當前像素點和掃描期間遇到的像素點整合為一個水平邊緣塊.若mh

考慮到兩條相鄰的輪廓線會相互影響的情況，再對已經提取的邊緣塊進行分離.如果組成邊緣塊的像素點標記值為9，則以9為邊界，將大型邊緣塊劃分為多個小型邊緣塊.

通過以上步驟，點元素被整合成線元素，曲線的邊緣塊提取完畢.邊緣圖E可由邊緣塊表示：

E={e1，e2，…，ek}

(7)

圖4 邊緣塊提取效果圖(圖(d)為圖(a)方框位置放大圖)Fig.4 Result of edge block extraction

本文算法邊緣塊提取的效果如圖4所示.

4 路徑提取

現有的直線檢測方法，如EDLines[11]和CannyLines[12]都是基于梯度信息來將邊緣圖中的邊緣組合成像素鏈，當梯度信息不足時就會造成連接的邊緣不夠完整，或者是部分邊緣沒有連接成功從而導致信息缺失.在這一節中，本文通過分析邊緣塊之間的連通域信息，提出了一種新的邊緣塊連接方法.

首先統計邊緣塊相互之間的位置關系，將所有統計結果以矩陣的形式保留.之后對統計結果進行分析，將多個邊緣塊連接得到曲線，并將這種曲線定義為路徑.本文在4.1節中描述邊緣塊位置關系的統計過程，在4.2節中描述對統計結果的處理過程.

4.1 鄰接矩陣獲取

鄰接矩陣中存放頂點間關系的數據.在第3節中，本文將邊緣點組合為邊緣塊，邊緣塊繼承了邊緣點本身的連通域性質，也是就說每個邊緣塊之間也存在一定的位置關系，即距離與方向.因此我們可以將每個邊緣塊視為一個頂點，以鄰接矩陣的方式來統計邊緣塊之間的位置關系.

統計過程如下：從圖片左下角開始，按行掃描圖片，統計每個邊緣塊與其他邊緣塊的位置關系，最終得到鄰接矩陣W.

W=[wij]k×k

(8)

其中k為邊緣塊的個數.

鄰接矩陣中的每一個元素wij表示的是邊緣塊ei與邊緣塊ej的位置關系.W中每個元素wij的計算公式為：

wij=Re(-1)dij·D8(ei，ej)

(9)

其中D8(ei，ej)表示的是邊緣塊ei到邊緣塊ej的棋盤距離.Re(-1)dij表示的是邊緣塊ei與邊緣塊ej的方向.Re(·)是取復數實部，dij有3種取值情況，當ej在ei的左上角時，dij=0；當ej在ei的右上角時，dij=1；當ej與ei不相鄰時，dij=0.5.

4.2 路徑提取

鄰接矩陣W可以看作是加權有向圖，每個邊緣塊相當于圖中的頂點.頂點的連接過程相當于圖的搜索過程，深度優先搜索算法(DFS)是一種將頂點所有分支都統計的搜素算法，因此在這一節中，我們將深度優先搜索算法(DFS)應用到鄰接矩陣上，統計鄰接矩陣中所有頂點的分支，得到由邊緣塊組成的像素鏈，本文將這種像素鏈稱之為路徑.

按行掃描鄰接矩陣W，當遇到一個非0的元素，即wij≠0時，以此時的鄰接矩陣的行數所代表的邊緣塊ei為DFS算法的起始端點，統計ei在鄰接矩陣W中的所有分支.

為了保留更多的信息，算法沒有限制每個邊緣塊被遍歷的次數，因此一個邊緣塊可能會存在于多條路徑中，或者是作為多個路徑的起點.同時為了避免得到的路徑過多且無意義，所以在按行掃描的鄰接矩陣時，只考慮沒有在任何路徑中的邊緣塊可以作為路徑的起點.

在完成掃描后得到了一個路徑集合P：

P={P1，P2，…，Pn}

(10)

圖5 路徑提取效果圖(圖(d)為圖(a)方框位置放大圖)Fig.5 Result of path extraction

本文算法路徑提取的效果如圖5所示.

5 直線檢測

由于使用了貪婪算法，深度優先搜索算法，因此初始路徑集合中包含著大量重復的信息.本節利用直線的幾何特征篩選初始路徑中較為明顯的直線特征，之后再將篩選后路徑集合中的路徑進行分離，最終實現直線檢測.本文在5.1節中描述路徑集合篩選過程，在5.2節中描述路徑分離過程.

5.1 路徑篩選

假設以ei為起始端點的路徑集合為：

(11)

1)計算每個路徑的絕對長度，即計算每條路徑的第一個邊緣塊與最后一個邊緣塊的歐式距離.在所有計算中選擇每個邊緣塊的首尾邊緣點坐標的中值作為每個邊緣塊的坐標.這樣我們就得到了一個集合li：

(12)

當路徑集合Pi中沒有任何路徑滿足直線定義時，此時的路徑集合中剩余的路徑只有第一個邊緣塊相同的路徑或者是最后一個邊緣塊相同的路徑，即起點相同的路徑或終點相同的路徑.

5.2 路徑分離

在這一節中我們對上一節中曲折度不符合直線定義的路徑進行路徑分離.設Po=(er，et，…，ey)，(r，t，…，y)∈(1，2，…，k)，對于任意路徑Po的拆分過程分為兩個步驟：

當路徑集合中的所有路徑都完成拆分后，這樣我們就完成了直線檢測，得到了一個直線集合：

L={l1，l2，…，ln}

(13)

6 實驗結果

為了驗證算法的有效性，將本文提出的算法與LSD[14]算法、EDLines[11]算法、CannyLines[12]算法進行對比.

本文的算法只包含兩個參數，即直線定義中的距離閾值δ以及邊緣檢測算法CannyPF[12]中關于梯度幅值的閾值λv.在理論中，直線上的點到直線的距離為0，考慮到數字圖像是經過離散化的結果以及圖像成像時會受到噪聲的影響，因此我們在直線定義中設定了距離閾值δ.當δ設定的過于嚴苛時，我們在分離步驟中就會得到較多細碎的線段，當δ設定過大時，我們得到的線段就會帶有一定的弧度.經過在多張圖片上進行嘗試，本文將距離閾值δ設置為1.5個像素大小，這樣可以在一定程度上保證線段的長度以及輪廓的完整性.

在CannyLines算法中其選擇的梯度幅值閾值λv為70，這樣保證了邊緣圖不會過度分割也不會過度檢測，本文選擇將λv設置為與CannyLines算法中所設置的一樣.對于LSD算法、EDLines算法、CannyLines算法的參數設置，本文采取了其提供的代碼中的參數設置.本文選用YorkUrbanDB[15]數據集中48張室內照片與48張室外照片用于實驗測試的圖像數據集.

圖6 實驗結果對比Fig.6 Experimental results of line segment extraction

直線檢測的結果如圖6所示.直觀的來看，4個算法都具有較好的檢測效果.對于建筑物外觀圖像的檢測結果中，可以看出LSD算法在玻璃窗戶以及對比度不明顯的建筑物輪廓處的檢測效果較好，能得到建筑物的局部細節較多，但是LSD算法容易在對比度不高的地方使得線段聚.EDLines算法與CannyLines算法，在局部細節的表現不如LSD算法，但不會像LSD算法一樣會出現線段聚集的情況，能夠較好的檢測出物體輪廓中的直線，其不足之處在于依然會丟失部分物體的輪廓信息.在建筑物室內圖像的檢測結果中，4個算法的檢測效果主觀上很相近.在涉及到天花板等對比度不明顯的地方時，LSD算法與EDLines算法在檢測效果上不如CannyLines算法以及本文的算法.

之后對檢測結果的局部細節進行對比，對比結果如圖7所示.

對比中發現，LSD算法，CannyLines算法會出現線段方向不正確，如大樓頂部的弧形曲線直接被直線代替，使得大樓的輪廓信息發生了改變.并且LSD算法和EDLines算法丟失了部分輪廓信息，如樓頂左側的線段未被檢測出來.實驗結果驗證了本文算法的直線檢測效果能完整的保留物體的輪廓信息.不會出現物體輪廓信息不完整以及形變的情況，對于玻璃窗戶以及對比度不明顯的建筑物輪廓處的檢測效果也有著較好的效果，且不會出現線段聚集的情況.

圖7 局部效果對比圖(圖(b)為圖(a)方框位置放大圖)Fig.7 Result of local effect comparison

為了更好地驗證算法的有效性，本文選擇以平均召回率(AR)，平均精確度(AP)，F-值來綜合的評估算法.在實驗中我們認為正樣本為：對于檢測的直線中的任意一個像素點，如果其八鄰域內存在真實樣本的像素點，就認為這個像素點為正樣本.同時為了避免檢測的線條越多，則正樣本數量越多，實驗中每個像素點只被判斷一次.實驗結果如表1和表2所示.

表1 室內線段檢測結果Table 1 Line detection results of indoor iamges

表1中的數據顯示，在室內線段檢測結果中本文的算法與EDLine算法具有最高的召回率，說明本文檢測出直線大部分為真實樣本中所設定的.同時本文的算法與CannyLine算法采用相同的邊緣檢測方法，在3個評估數據中，本文的算法都是優于CannyLine算法，驗證了我們邊緣連接方法的有效性，能夠保留大部分的輪廓信息.表2中的數據顯示，在室外線段檢測結果中本文的算法與EDLine算法具有最高的精確度，即誤檢測的直線最少，驗證了本文算法的有效性.

表2 室外線段檢測結果Table 2 Line detection results of outdoor iamges

7 結 論

本文針對傳統直線檢測算法在梯度信息不足時出現的檢測結果不完整的問題，提出了基于邊緣塊的線段檢測算法.結合邊緣點的連通域性質，將邊緣點聚合成邊緣塊，根據邊緣塊之間的位置關系，提出一種新的邊緣連接方式，解決了之前算法只關注圖像中的梯度信息，而忽略了邊緣本身連通域信息，從而導致檢測結果中物體輪廓不夠完整的問題.本文提出的算法能在最大程度上保留被檢測物體的輪廓，且具有較好的局部細節，有利于后續的直線特征應用.