基于基本塊分組與融合的特征直線檢測算法

馬 瑞，胡立華，左威健，劉愛琴

(太原科技大學 計算機科學與技術學院，山西 太原 030024)

0 引 言

基于圖像的特征檢測是實現三維重建[1]、圖像匹配[2]、物體檢測[3]以及遙感圖像分析[4]等實際應用的重要步驟之一。基于圖像的特征檢測主要包括特征點、特征直線和特征區域，相較于特征點和特征區域，特征直線具有特征表達能力強，描述特征幾何信息、特征間拓撲關系清晰豐富等優點，成為特征檢測的研究熱點之一。近年來，基于圖像的特征直線檢測已廣泛應用于SLAM[5]、場景跟蹤[6]、無人駕駛[7]以及工業檢測[8]等系統中。然而針對場景復雜、結構各異、紋理重復嚴重的對象，現有特征直線檢測方法存在嚴重的斷線以及斷線過融合的現象，導致出現完整直線數量較少、錯誤檢測率較高的問題。

針對上述問題，文中結合改進的自適應Canny邊緣檢測算法[9]，提出基本塊的概念，設計了一種基于基本塊分組、漸進式融合的特征直線檢測方法。利用新的Helmholtz原理準則剔除由噪聲等外界干擾形成的虛假特征直線，得到準確特征直線集。實驗用Matlab 仿真工具進行了驗證，結果證明了該算法對特征直線檢測的高效性。

1 相關工作

目前，常見的兩類特征直線檢測方法為：基于圖像空間變換域的特征直線檢測方法和基于圖像像素信息的特征直線檢測方法。

基于圖像空間變換域的特征直線檢測方法是一種全局特征線檢測方法，其基本思想是在圖像的整體范圍內提取特征點，以特征點位置作為驅動數據，設置參數方程將圖像中的點映射為參數空間中的點，依據參數空間網格進行投票累計，由此將圖像空間中的特征線提取問題轉化為參數空間中的極值搜索問題。典型算法有：D.H. Ballard提出的Hough變換(HT)[10]，它將圖像域中的全局模式檢測問題轉化為參數空間中的有效峰值檢測問題，但是該算法存在復雜的閾值設置問題，對紋理清晰的圖像及低對比度區域出現錯誤檢測，且算法計算量大，內存消耗大。因此，近幾十年來學者們對HT的缺點進行了仔細的研究并提出許多改進方法。如廣義霍夫變換(GHT)[11]、隨機霍夫變換(RHT)[12]、數字霍夫變換(DHT)[13]等，這些算法主要集中在提高HT的效率，僅僅提供特征直線的長度和它與軸線的夾角，不提供關于特征直線端點的信息。Matas J等人[14]嘗試使用錯誤檢測機制來自動設置檢測閾值，然而該方法在實際應用中時間復雜度較高，缺乏可伸縮的終止準則。Atiquzzaman M等人[15]提出了確定一條線的長度和端點的算法，具有高計算性，不適合實時應用。Chao X等人[16]提出了一種基于改進隨機霍夫變換的線檢測算法，利用像素梯度方向差的概念，計算每個邊緣組中相鄰像素的梯度方向差。盡管研究者對HT算法做了如此多改進，但基于Hough的方法都有一個共同的缺點，即它們的性能取決于邊緣檢測的質量，這是因為它們使用的是邊緣映射而不是原始圖像。

基于圖像像素信息的特征直線檢測方法是一種局部感知組合法，其基本思想是從圖像中提取邊緣灰度或梯度等局部信息，利用局部特征的相鄰性、延續性等幾何關系確定候選直線區域。典型算法有：董晶等人[17]提出邊緣主方向和圖像梯度方向相結合的算法，該算法結合主元方向和梯度方向信息連接方向相似的邊緣，增強了候選直線段的抗干擾性，但是算法參數較多，線段碎片化嚴重，無法完整檢測交叉線特征；戴激光等人[18]提出基于邊緣跟蹤的算法，但算法計算復雜度較高；Akinlar等人[19]提出基于邊緣信息的檢測算法(edge drawing lines，EDLines)，該算法能夠在較短時間內給出比較準確的直線檢測結果，但對弱邊緣圖像特征檢測不準確；Lu等人[20]提出一種自適應參數的 Canny算法，該算法直接從圖像或包含所有結構信息的邊緣圖中提取共線點簇進行擴展合并，利用最小二乘擬合方法檢測特征直線，但其依賴于邊緣檢測方法，對噪聲敏感；Gioi等人[21]提出一種快速的特征線段檢測算法(line segment detector，LSD)，該算法通過圖像各像素梯度方向進行矩形擬合，利用Helmholtz原理進行驗證產生準確線段，并在低水平上控制誤檢測的數量，具備運行速度快，算法參數能夠自適應等一系列顯著優點，被看作是現代特征線檢測算法的一個標桿；Cho等人[22]提出一種基于線段片(Linelet)算法，該算法在圖像數字化后，用一組水平或垂直方向上可連成特征線的像素點集來模擬圖像空間中特征線的內在屬性，但針對高分辨率圖像易產生過分割現象。Almazan 等人[23]提出融合圖像域中的感知組合法以及Hough域中的全局積累法的優點來檢測特征線，然而易將特征線段分割成多個特征線段；Yang Liu等人[24]在LSD算法的基礎上提出基于長度的特征線實時檢測器LB-LSD，融合了圖像中的梯度信息和結合邊緣鏈接思想進行特征線檢測，結果出現過融合現象，錯誤檢測較多。

BPC_GF算法的主要工作有以下幾點：(1)目前人工場景中的大多數建筑都具有結構化構造，很容易用直線來勾勒，并且圖像中直線結構類似邊緣屬性，其精度取決于邊緣檢測的質量，因此文中采用改進的自適應Canny邊緣檢測算法檢測圖像邊緣點的屬性；(2)針對現有的特征直線檢測器在場景復雜、紋理重復的圖像中易將感知上單一的直線段過分割成多條短線段的缺點，結合貪心算法引入基本塊概念，提出了一種基于基本塊分組與漸進式融合的特征直線檢測方法，從而克服了短線段之間的重疊；(3)針對圖像易受噪聲、光照、尺度變化等影響在基本塊的融合過程中易發生過融合現象，導致特征直線的錯誤檢測率升高，采用了一種新的基于Helmholtz原理的特征直線驗證準則，以確定檢測出的特征直線的準確性。

2 基本概念

給定灰度圖像I,采用改進的自適應Canny算子[9]進行邊緣檢測后得到n個邊緣像素點集P={Pi(Mi,Gi,Xi),i∈[1,n],Mi∈[0,255],Gi∈[0,360]}，其中Mi為邊緣點Pi的梯度幅值，Gi為邊緣點Pi的梯度方向，Xi(xi,yi)為邊緣點Pi的幾何位置坐標信息。基于邊緣信息點集P，給出如下定義：

定義1 瞄點K：在給定邊緣像素點集P中，K(MK,GK,XK)為瞄點當且僅當滿足如下條件：

(1)

定義2 次瞄點SK：設K為邊緣像素點集P的瞄點，K的次瞄點SK(MSK,GSK,XSK)滿足如下條件：

(2)

其中，N_8(K)表示瞄點K的八鄰域信息。

定義3 搜索方向SD(A,B)：給定當前圖像I內任一特征邊緣點A(MA,GA,(xA,yA))及相鄰特征邊緣點B(MB,GB,(xB,yB))。如果點B在點A的左右位置時代表橫向搜索SDH，上下位置時代表縱向搜索SDV，左下右上位置時代表45°斜向搜索SDS45°，左上右下位置時代表135°斜向搜索SDS135°，則當前邊緣點A,B可確定的搜索方向SD(A,B)形式化描述為：

(3)

定義4 基本塊C：給定邊緣點集P、瞄點K及次瞄點SK，若像素點子集{K,SK,Pi,Pi+1,…,Pi+j}滿足如下條件時，則可構成基本塊C：

(4)

從定義1、2出發，邊緣點集之間依照不同的搜索方向(定義3)，如果滿足定義4則可構成基本塊，由此基本塊可劃分為：橫向基本塊H、縱向基本塊V、45°斜向的基本塊S45、135°斜向的基本塊S135。

定義5 基本塊C的長度LC：設P1(M1,G1,X1)，P2(M2,G2,X2)為基本塊C的起始邊緣像素點和終止邊緣像素點，則基本塊C的長度為：

LC=Dist(X1,X2)

(5)

其中，函數Dist()計算基本塊C的歐氏距離。

定義6 主方向角θ：給定基本塊C，C的主方向角θ可通過下面步驟計算：

(1)計算C={Pi(Mi,Gi,Xi),0

(6)

(2)對基本塊C內所有特征邊緣點Pi的水平線角求均值即為基本塊的主方向角：

(7)

定義7 基本塊間空間距離S：給定基本塊Ci鄰域內的同類基本塊Cj，Ci、Cj鄰近端點的橫坐標或縱坐標的偏移量ζ、μ滿足0≤ζ≤2或0≤μ≤2時，計算兩基本塊間的歐氏距離S(Ci,Cj)：

(8)

S(Ci,Cj)=Dist(ci,cj)

(9)

其中，Ci,Cj兩端邊緣像素點坐標分別為(xi1,yi1)、(xi2,yi2)和(xj1,yj1)、(xj2,yj2)；ci,cj表示為Ci,Cj鄰近端點。

定義8 自適應空間距離標準τs：如果基本塊間空間距離S小于τs，則基本塊可以進行分組。

τs=ξ·LCi

(10)

由于每個基本塊的長度是隨機的，如果僅用基本塊的長度和基本塊間空間距離S做比較，其檢測結果的誤差明顯較大，所以引入參數ζ，其取值0<ζ<1。

3 算法思想及其流程

BPC_GF算法主要分為三個關鍵步驟：基本塊劃分、基本塊分組融合、錯誤特征線的剔除。算法的整體設計流程如圖1所示。

圖1 算法流程

3.1 基本塊劃分

依據每個邊緣像素之間梯度、灰度的屬性，將同一搜索方向的邊緣像素劃分成不同類型的基本塊，從而進行分組融合，使得特征直線檢測更準確。邊緣像素劃分為基本塊的算法流程如下：

算法1：邊緣像素劃分基本塊算法。

輸入：灰度圖像I

輸出：圖像I的基本塊集C={Ci,Ci∈{H={Hi，0

(1)采用改進的自適應Canny方法獲得圖像I的邊緣點集P={Pi(Mi,Gi,Xi),i∈[1,n],Mi∈[0,255]，Gi∈[0,360]}

(2)依照邊緣點的幅值信息對所有邊緣點集進行降序排序

(3)初始化基本塊C=Φ

(4)For eachPi∈Pdo

(5)Find the pointsK(由定義1確定) andSK(由定義2確定) in thePaccording to definitions 1 and 2

(6)According toKandSKCompute the direction of search SDi,SD={SDH,SDV,SDS45,SDS135}

(7)AddKandSKtoCi，Ci∈{H={Hi，0

(8)WhilePi∈N_8(SK) and satisfy SD(Pi,SK)∈SD(SK,K) do

(9)AddPitoCi

(10)K=SK

(11)SK=Pi

(12) end while

(13) if length(Ci)≥ 3, then

(14)C=C∪Ci

(15) End if

(16) Delete edge pixel in theC,updateP

(17)End for

3.2 基本塊分組融合

經過3.1過程后圖像中的邊緣像素點被合理分配到不同基本塊中，基于單個基本塊長度較短，因此，依據相鄰基本塊間主方向角相近且空間距離較小的特點，將滿足以下兩個約束條件的同類型基本塊進行分組融合。

(1)基本塊間的空間距離(定義7)滿足一定的自適應空間距離標準τs(定義8)；

(2)基本塊間的主方向角(定義6)之差Δθ滿足一定的自適應空間角度標準τθ。

以橫向基本塊集為例，基本塊分組融合算法基本流程如下：

算法2：基本塊分組融合算法。

輸入：橫向基本塊集H={Hi，0

輸出：圖像中的特征線及特征線的條數num

(1)計算H中基本塊的長度L，并進行降序排序

(2)計算H中基本塊的主方向角θ

(3)初始化線段集合:D=H,GroupG=Φ

(4)forD1∈Ddo

(5)L1=MAXlength(D1)

(6) For eachDi∈D-1 do

(7)Ifθ(Di)-θ(D1)<τθthen

(8)G=G∪Di

(9)End if

(10)End for

(11)P=Φ

(12)For eachGi∈Gdo

(13) IfS(Gi,D1)<τsthen

(14)P=P∪Gi

(15) End if

(16)End for

(17)R=Φ

(18)ForD2∈Pdo

(19)M=MergeTwoLines(D1,D2)

(20) IfM≠Φthen

(21)D1=M

(22)R=R∪D2

(23)End if

(24) End for

(25)D=DR

(26)End for

同理，檢測其余三類基本塊中的特征直線。

3.3 Helmholtz原理準則驗證

在對基本塊進行劃分時,由于邊緣檢測得到邊緣像素的密集區域容易對基本塊產生錯誤判斷，而邊緣像素稀疏區域由于噪聲影響導致基本塊錯誤分布，從而影響特征直線檢測，因此為使檢測到的特征直線更精確，對檢測結果進行驗證已成為直線檢測算法的重要步驟之一。常用于驗證所檢測直線的準確性的方法為Helmholtz原理，如：LSD、cannyline及EDline。

在LSD檢測算法中，建立了抑制虛假線段出現的數學模型，模型假設梯度方向是獨立的，并且在圖像中均勻分布，與“零假設”的顯著偏差具有相關性，并揭示了線段的存在，因此該方法是一種反向準則。在含有特征線的情況下，考慮噪聲模型中的虛警特征直線具有與所觀測的真實特征直線一樣多或更多對齊邊緣點的事件。如果隨機期望很小，則感知上是有意義的。定義一個“虛假警報的數”(number of false alarms，NFA)即：

NFA(s,p)=γNLB(|s|,ks,p)

(11)

(12)

其中，s是圖像中檢測到的特征直線，|s|是s的矩形擬合區域，ks是矩形內與特征線方向對齊的像素點，p是隨機像素q具有相同方向的概率，NL是圖像中可能的特征直線數，γ是歸一化值，B(|s|,ks,p)是二項分布。

LSD算法中的驗證步驟只查找了與擬合矩形的主方向軸完全對齊的像素點，為了克服檢測出的直線的碎片化，Yohann Salaün等人[25]將驗證公式進行推廣，以LSD算法中短線段S={s1,s2,…,sn}為基準進行融合驗證。

BPC_GF中圖像中檢測到的特征直線是由多個空間距離相近，主方向角相似的基本塊融合而成的直線。因此，通過檢測構成一條特征直線的每個基本塊的NFA與該特征直線的NFA進行比較來判斷該特征直線是否檢測正確。假設一幅圖像大小為M*N，則定義一條特征直線的NFA為：

1)B(|Ci|,kCi,p)

(13)

其中，m是基本塊融合后的特征直線，MN5/2是圖像中可能的特征直線數目，n是檢測到的特征直線中的基本塊數。

為了計算特征直線中各個基本塊的NFA，可采用LSD中使用的相同背景和對象模型，其表達式同LSD。

(14)

通過上式計算如果F<0,則認為分組融合后的特征直線是有意義的。

4 實驗結果與分析

算法實驗的環境為:Windows 10操作系統，2.3 GHz Intel(R) Core(TM) i5處理器，4 GB內存；山西太原晉祠圖像采集工具參數為像素1 200萬的三星智能手機，中國科學院自動化研究所模式識別國家重點實驗室提供的三維重建數據集[26]采集設備為佳能EOS 5D，采集圖像像素為4 368*2 912。基于上述環境，采用Matlab編程語言，以山西晉祠和中科院三維重建數據集為對象，實現了基本塊檢測分組、漸進式融合、特征驗證的直線檢測算法。文中的對比實驗的源代碼可以在網上公開獲取。其中實驗操作時首先需對采集圖像進行預處理，處理后的圖像像素為640*480。

4.1 算法參數分析

BPC_GF算法涉及到的關鍵參數分別為:Canny邊緣檢測時的高斯濾波參數δ，高閾值τh，低閾值τl，主方向角偏差閾值τθ與空間距離閾值τs，系數ζ，其中δ，τh，τl默認使用改進的自適應Canny邊緣檢測算法[9]中的參數,τθ進行自定義，τs根據基本塊的長度和ζ而定，ζ是用來計算距離偏差的系數，檢測結果最終采用圖像中檢測到的特征線數量進行判斷。為了驗證參數值對圖像特征線檢測的影響，在數據集上隨機選取三幅古建筑圖像進行檢測，表1表示參數τθ與ζ的選取對圖像特征線檢測結果的影響。

表1 τθ與ζ取值對直線結果的影響

從表1中可以看出，當參數設置為τθ>pi/8,ζ>0.1時，算法檢測效果逐漸變差，當參數設置為τθ<=pi/8,ζ>=0.1時，算法檢測結果基本保持穩定變化。由表1可知，當τθ=pi/10、ζ=0.1時圖像中檢測到的直線不再受參數取值的影響，且檢測到的特征直線最多，因此，將τθ=pi/10、ζ=0.1作為BPC_GF算法實驗的參數設置。

4.2 算法量化分析

為了更加清楚地說明BPC_GF算法檢測的特征直線性能，記TP(true positive)為真正例，即正確檢測到的特征線的數量，FP(false positive)為假正例，即錯誤檢測到的特征線的數量；FN(false negative)為假反例,即漏檢的特征線的數量，然后通過以下3個評價指標對算法進行客觀定量的評估。

(1)精確率(precision)，表示在檢測到的所有特征直線中檢測正確的特征直線所占的比例，計算公式如下所示：

(15)

(2)召回率(recall)，表示在檢測到的所有特征線中檢測正確的特征線所占人工標注圖像中的比例，計算公式如下所示：

(16)

(3)F-得分(F-score)，表示精確率和召回率的調和平均數，計算公式如下所示：

(17)

其中，β為精確率和召回率的比值，BPC_GF算法認為精確率和召回率同樣重要，因此設β=1。采用不同算法即LB-LSD、LSD、Linelet、Cannylines和BPC_GF對圖像數據集上隨機選取的100幅古建筑圖像進行實驗，其精確度、召回率、F-得分如圖2所示。與其他方法相比，BPC_GF方法具有更高的檢測性能。不同算法的平均量化評測結果如表2所示。

(a)精確度

(b)召回率

(c)F-得分

表2 不同算法在所給數據集上的量化評測結果

由此可得出，BPC_GF算法在特征直線檢測的精確率方面明顯優于現有的算法；在召回率方面，Linelet算法的效果最好，主要原因在于Linelet算法是基于圖像中像素局部特征來進行特征線檢測。根據實驗，以像素的梯度導向為指導對像素進行劃分的特征直線檢測有利于特征直線召回率檢測。BPC_GF算法在邊緣檢測基礎上對像素進行基本塊劃分，綜合考慮算法在精確率和召回率兩個方面的性能，BPC_GF算法均取得了較好的結果。

4.3 算法時間分析

對圖像在不同算法檢測情況下的時間復雜度進行分析，如圖3所示。從圖中可以看出，對于同一幅圖像，BPC_GF算法的時間最短，相較于最新的LB-LSD算法，BPC_GF算法的時間性能提高了約20%。

圖3 在同一圖像上不同算法檢測所用時間比較

4.4 算法效果對比

為進一步驗證BPC_GF算法的性能，在古建筑數據集上隨機選取三幅灰度圖像進行不同算法的檢測，不同算法上的特征檢測結果如圖4所示。

圖4 數據庫中不同圖像在不同算法上的檢測結果

從檢測的結果中可以看出，LB-LSD算法檢測的線段長度長，但是檢測數量少，檢測錯誤率較高；LSD、Linelet算法檢測的線段數量較多，但是線段的碎片化比較嚴重，導致將感知上單一線段在交點處分割成多個短線段；Cannylines 算法沒有克服圖像的寬像素邊緣；BPC_GF算法精準地檢測到的圖像中的線段，能夠很好地呈現圖像的輪廓。

5 結束語

針對場景復雜紋理重復的圖像直線提取中存在斷線、誤檢的問題，提出了BPC_GF算法，算法具有以下優點：(1)利用改進的自適應Canny邊緣檢測算法提取圖像邊緣點，提高了邊緣檢測的質量，為特征直線檢測奠定了基礎；(2)提出對邊緣像素點進行基本塊劃分，分組融合，克服了短線段之間的重疊檢測；(3)提出新的基于Helmholtz原理的特征直線驗證準則，提高了特征直線檢測的效率。經仿真實驗和實際應用分析，BPC_GF算法檢測效率更高。