基于合并短線段的直線檢測方法

馮 凱，王 琦，于水源

（1.中國傳媒大學計算機與網(wǎng)絡空間安全學院；2.智能融媒體教育部重點實驗室，北京 100024）

0 引言

直線檢測一直是計算機視覺領域的研究熱點之一。在圖像中，直線段屬于底層的圖像特征，基于直線段的長度、方向和端點檢測都能提取出重要而基本的圖像信息。在許多計算機視覺任務中都能看到直線檢測的影子，如道路檢測［1］、消失點檢測［2-3］、即時定位與地圖構(gòu)建［4-5］及三維重建［6］等。曲線在人們的日常生活中也隨處可見，通過曲線檢測能夠獲取圖像中物體的輪廓信息，因此曲線檢測與直線檢測一樣具有較高的研究價值。

目前直線檢測已取得了許多研究成果，主要包括邊緣連接法和梯度法?；舴蜃儞Q算法屬于邊緣連接法，以其優(yōu)良的檢測能力得到了廣泛應用［7］。近年來也有針對霍夫變換的改進算法，包括霍夫一維變換［8］、隨機霍夫變換［9］、概率霍夫變換法［10-11］和網(wǎng)格霍夫變換［12］等。但是霍夫變換依然存在針對復雜圖像檢測性能不佳、容易誤檢和漏檢直線等問題。CannyLines 方法［13］也是邊緣連接法中的經(jīng)典方法，其能夠根據(jù)圖像自適應調(diào)整參數(shù)，且易于檢測低梯度區(qū)域，卻過濾了一些真實的短線段。梯度法的主流算法包括以下幾種：LSD 方法［14］能夠有效區(qū)別相鄰線段，但容易產(chǎn)生過分割的情況；Linelet 方法［15］易于檢測細小的紋理信息，但存在運行速度慢、易出現(xiàn)孤立的短線段等缺點。

在曲線段檢測方面，目前工業(yè)界最常用的還是霍夫變換算法，霍夫變換可根據(jù)給定的解析式檢測特定曲線（如圓或橢圓），而之后提出的廣義霍夫變換［16］可以不需要解析式檢測任意給定的曲線。

目前很大一部分線段檢測方法都依賴于邊緣檢測，包括霍夫變換法、EDLines 方法和CannyLines 方法等。Canny算子是目前邊緣檢測的主流算法之一，其基本思想是找到像素灰度值變化明顯的地方作為邊緣點。孤立的邊緣點可聚集成直線段，再采用某種擬合方法檢測直線段即可提取出直線。由此可見，在基于邊緣的直線檢測方法中，邊緣檢測算法的優(yōu)劣將直接影響直線檢測效果。

綜上，直線檢測領域還沒有一種通用的高性能方法，只能根據(jù)不同情況選擇不同方法。優(yōu)秀的直線檢測方法應盡可能避免直線斷裂，有較高精度且滿足速度要求［17］。為此，本文提出一種基于合并短線段的直線檢測方法。實驗結(jié)果表明，該方法在檢測精度和速度方面均表現(xiàn)較好，且該方法既能夠檢測邊緣圖中的直線段，也能夠檢測曲線段。

1 直線檢測算法

通常來說，在一張圖片中找到所有線段需要較大的計算量，尤其在圖片分辨率很高的情況下更是如此。如果將圖片切割成多個小矩形框，每個小矩形框中的線段不難檢測，再將各矩形框中的短線段合并成直線。當短線段的長度足夠短時，即可用來近似曲線段，這種采用逐次近似思想擬合曲線的方式通常被稱為“直線簡化”。對于直線段檢測，該方法最后會輸出直線段的兩個端點坐標；對于曲線段檢測，該方法會輸出曲線段上的多個點坐標。

本文方法基本步驟如下：①將圖像邊緣圖切分成若干區(qū)域；②通過若干個匹配矩陣檢測短線段；③將所有短線段合并成直線或曲線；④探測并補全斷裂的線段。

1.1 將圖像邊緣圖切分成若干區(qū)域

為了提高算法運行效率與檢測精度，對于偏向水平的線段和偏向豎直的線段分開進行檢測處理。

（1）針對偏向水平的線段，將邊緣圖（見圖1（a））從左到右切分成若干區(qū)域（見圖1（b）），也即從左到右設置若干個檢測框進行檢測。每個檢測框的寬度可設置不同數(shù)值，該寬度越小，檢測到的線段越精細，也能夠顯示更多細節(jié)，圖1 中的寬度為8 個像素。

（2）針對偏向豎直的線段，在邊緣圖中從上到下設置若干個檢測框（見圖1（c））。

Fig.1 Image segmentation圖1 切分圖像

這種針對水平和豎直兩個方向分別進行處理的思想在Sobel 算子［18］中也能夠看到。Sobel 算子包含兩組矩陣模板，分別用來檢測水平方向和豎直方向的邊緣。

1.2 通過若干匹配矩陣檢測短線段

通過若干矩陣檢測短線段可分為以下幾個步驟：

（1）針對尋找檢測框中的短線段，本文以其中一個檢測框（見圖2（a））為例進行說明。首先記錄原圖中直線與檢測框邊界的交點，左右兩個交點確定一條直線，圖2（a）檢測框的左邊界檢測到4 個交點，右邊界檢測到4 個交點，即可確定16 條短線段（見圖2（b））。

（2）如果左右兩點縱坐標的差大于檢測框?qū)挾?，則是一條傾向于豎直的直線，剔除該短線段。在這一步能夠排除大部分短線段，上一步的16 條短線段經(jīng)過這一步只剩下5 條可能的短線段（見圖2（c）），減少了很多后續(xù)計算量。

（3）目前需要判斷上一步的5 條短線段在原始圖像中是否存在。具體方法如下：預先構(gòu)造一個字典Map，字典中包含15 個短線段匹配矩陣，即圖3 中的15 幅短線段匹配二值圖。已知傾向水平短線段的左右端點坐標，即可在原圖像中框選需要檢測的短線段區(qū)域，得到矩陣M1（圖2 中框選部分）。將短線段左右端點的縱坐標之差作為鍵，從字典Map中取得一個短線段匹配矩陣M2（圖3 中框選部分）。將矩陣M1與矩陣M2點乘，得到結(jié)果矩陣M3。計算矩陣M3的各元素和Sum。如果Sum大于一個閾值，則可認為假設的短線段在原圖中存在。剔除Sum小于該閾值的短線段后得到3 條短線段（見圖2（d）），即該檢測框檢測到了3 條水平短線段。

Fig.2 Short line detection圖2 探測短線段

Fig.3 Binary graph matching short line segments圖3 匹配短線段二值圖

1.3 合并檢測框中的短線段得到直線

之前檢測到的短線段是零散的，每一條直線的各個短線段分散在不同檢測框中，需要將其合并起來得到一條直線。例如圖4（b）中的直線由4 條短線段組成，它們分別被4 個檢測框探測到，即圖4（a），下面是合并思路：從左向右遍歷未標記的短線段，以當前短線段L1第二個交點的縱坐標為索引值，在下一個檢測框的短線段集合中尋找下一條短線段L2。當短線段L1與短線段L2的角度差小于1 時，兩條短線段可合并為一條直線。當兩條短線段角度差大于1且小于30 時，兩條短線段可合并為一條曲線。

1.4 探測并補全斷裂的線段

由于本方法將偏向水平和偏向豎直的線段分開進行檢測，在進行曲線檢測時，那些傾角在45°和135°附近的線段會斷裂，例如圖1（b）、（c）中的圓被劃分為4 段曲線。因此，需要在線段端點附近尋找斷裂的線段，具體思想如下：圖5（a）中的L0為原曲線，圖5（b）為短線段合并后的線段，其中L1與L2之間是斷裂的，R5為L1所在方格，R2為L2所在方格，需要在R5的八鄰域方格內(nèi)尋找與L1相連的線段L2，判斷圖5（c）中的虛線是否為斷裂線段的方法為1.2 節(jié)中步驟（3）中的方法。圖5（d）表示通過逐次近似的方法擬合圖5（a）中曲線后的效果。

Fig.4 Merging short segments圖4 合并短線段

Fig.5 Line segment for detecting fracture圖5 斷裂線段探測

2 實驗

2.1 實驗設計

考慮到本文算法既能檢測邊緣圖中的直線，又能檢測曲線，針對這兩種情況應設計不同實驗進行分析。

為了驗證本算法檢測邊緣圖中直線的效果，本文采用案例檢驗和客觀評測系統(tǒng)兩種評測方法進行測試。首先選取兩幅圖像進行案例檢驗，分別是Lenna 圖和五角大樓。為了驗證該算法檢測邊緣圖中直線的效果，本文還將其與霍夫變換算法和LSD 算法進行比較。

案例檢驗屬于定性分析，對于復雜圖像，很難僅通過視覺感知對檢測結(jié)果進行比較［19］，而客觀評測系統(tǒng)將使用York 城市數(shù)據(jù)庫［20］評測本文算法，屬于定量評測方法。York 城市數(shù)據(jù)庫是一個包含102 張原始圖像的數(shù)據(jù)庫，而且每張圖像都人工標注了圖像中直線段的相關(guān)信息（包括直線段端點坐標）。之后Cho 等［15］花費大量時間對該數(shù)據(jù)庫進行了詳細的標注工作，能夠較為客觀地評價直線檢測算法效果。評價一條直線是否被正確檢測的標準如下：對于人工標注的直線段加粗一個像素進行處理（加粗一個像素表示可容忍的檢測誤差為一個像素），然后判斷檢測的直線段是否在該該加粗的直線段內(nèi)，判斷方法為1.2 節(jié)步驟（3）中的方法。由此可得到正確檢測的直線，繼而計算出誤檢和漏檢的直線段。

對于曲線檢測，本文采用案例檢驗方法進行評測，選取兩幅圖像處理領域的經(jīng)典標準圖片進行檢驗，分別為水果和帆船。

2.2 實驗分析

2.2.1 直線檢測（使用案例檢驗測試）

圖6 為Lenna 圖與五角大樓圖（彩圖掃OSID 碼可見），為了更清晰地觀察到結(jié)果，在原圖中截取了一部分作為局部放大圖，分別在圖中的第2 列和第4 列。其中圖6（a）為原圖，圖6（b）為預處理后的邊緣圖，圖6（c）為采用本文算法檢測的結(jié)果，圖6（d）為采用霍夫變換算法檢測的結(jié)果，圖6（e）為采用LSD 算法檢測的結(jié)果。表1、表2 為不同結(jié)果的對比。

Fig.6 Effect Comparison of different methods圖6 不同方法效果對比

Table 1 Comparison of different results of detecting the lines in the left figure of Fig.6（a）表1 圖6（a）左圖中的直線檢測結(jié)果對比

Table 2 Comparison of different results of detecting the straight line in the right figure of figure 6（a）表2 圖6（a）右圖中的直線檢測結(jié)果對比

比較本文方法與其他方法的檢測結(jié)果，從圖6 中可觀察到，霍夫變換在圖像邊緣密集（比如紋理）情況下的直線檢測效果并不好，常常是錯誤而雜亂的，具體表現(xiàn)在Lenna的頭發(fā)和眼睛上。霍夫變換還存在很多漏檢的直線，比如Lenna 的帽子邊緣沒有被檢測到，從圖6 中五角大樓的局部放大圖也可看出霍夫變換算法誤檢了許多短線段。LSD 算法的檢測效果不太穩(wěn)定，在Lenna 圖中，可明顯看到在帽頂處漏檢了一些直線段，由此造成圖像主體邊緣的不連續(xù)，同時對于五角大樓局部放大圖中的停車場也漏檢了許多短線段。由表1、表2 可知，相比霍夫變換算法和LSD 算法，本文方法誤檢和漏檢的情況較少。

2.2.2 直線檢測（使用客觀評測系統(tǒng)測試）

圖7（a）為York 城市數(shù)據(jù)庫中的一張原圖像，圖7（b）為邊緣圖像，圖7（c）為人工標注的直線段圖像。從圖7（d）中可以看到，霍夫變換方法得到的直線段在圖像中某些區(qū)域堆積在了一起，尤其是短線段。從圖7（e）中可以看到，LSD 方法存在明顯的誤檢直線，例如圖上方1/6 處有一條斜線被誤檢成了水平線。圖7（f）為本文方法檢測結(jié)果，相比霍夫變換方法，本文方法不會在線段密集部分誤檢率較高，也不會像LSD 方法那樣出現(xiàn)明顯錯誤。

Fig.7 Detection effects of different methods圖7 不同方法檢測效果

在Youk 城市數(shù)據(jù)庫中，平均每張圖片有680 條標注線段，102 張圖片的直線段總長度約為3 475 980 個像素。令TP為真陽性（正確檢測直線長度和），F(xiàn)P為假陽性（誤檢直線長度和），F(xiàn)N為假陰性（漏檢直線長度和），本文將根據(jù)以下4 個指標對不同方法進行評估：

（1）精度。即正確檢測直線占檢測到所有直線的比率，計算方法如下：

（2）召回率。即正確檢測直線占人工標注直線的比率，計算方法如下：

（3）IoU。即正確檢測直線與人工標注直線的交集比上它們的并集，計算方法如下：

（4）F值。即精度和召回率的調(diào)和平均數(shù)，本文設F 值中的β 值為1，計算方法如下：

根據(jù)表3 能從整體角度分析不同方法的檢測效果，可以看出本文方法的檢測精度高于霍夫變換方法和LSD 方法，而召回率、IoU和F值更是遠高于其他兩種方法，說明本文方法的檢測效果優(yōu)于傳統(tǒng)主流方法。

Table 3 Evaluation results of line segment detected by different methods表3 不同方法檢測直線段評估結(jié)果

2.2.3 曲線檢測

圖8 為水果和帆船（彩圖掃OSID 碼可見），其中第2 列與第4 列為局部放大圖。圖8（a）為原圖，圖8（b）為邊緣圖，圖8（c）為采用本文算法檢測的結(jié)果。

從圖8、表4 中可以看出，本文方法檢測曲線的效果也較好，采用本文方法可以檢測任意形狀的曲線，而傳統(tǒng)方法需要通過曲線解析式檢測曲線，本文方法突破了這一局限。

Fig.8 Curve detection effect of this method圖8 本文方法檢測曲線效果

Table 4 Comparison of different curve results表4 曲線檢測結(jié)果對比

3 結(jié)語

本文提出一種新的直線檢測方法，該方法采用分段檢測思想。將本文方法與其他直線檢測算法進行對比，并在包含York 城市數(shù)據(jù)庫的客觀評測系統(tǒng)中進行測試，結(jié)果表明，直線漏檢和誤檢的情況都較少，在邊緣較復雜的圖片檢測中依然表現(xiàn)穩(wěn)定，魯棒性較好。經(jīng)過案例檢驗測試，發(fā)現(xiàn)該算法在曲線檢測上也有良好效果。另外，本文檢測的曲線屬于一般性曲線，在現(xiàn)有基礎上，可考慮改進檢測曲線的方式，如在算法中引入特殊曲線（圓和橢圓等）的曲線解析式，進而使得該算法更加貼近實際應用。