馮 凱，王 琦，于水源

（1.中國傳媒大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院；2.智能融媒體教育部重點(diǎn)實(shí)驗(yàn)室，北京 100024）

0 引言

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

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

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

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

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

1 直線檢測算法

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

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

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

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

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

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

Fig.1 Image segmentation圖1 切分圖像

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

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

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

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

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

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

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

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

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

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

1.4 探測并補(bǔ)全斷裂的線段

由于本方法將偏向水平和偏向豎直的線段分開進(jìn)行檢測，在進(jìn)行曲線檢測時(shí)，那些傾角在45°和135°附近的線段會(huì)斷裂，例如圖1（b）、（c）中的圓被劃分為4 段曲線。因此，需要在線段端點(diǎn)附近尋找斷裂的線段，具體思想如下：圖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 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)計(jì)

考慮到本文算法既能檢測邊緣圖中的直線，又能檢測曲線，針對這兩種情況應(yīng)設(shè)計(jì)不同實(shí)驗(yàn)進(jìn)行分析。

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

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

對于曲線檢測，本文采用案例檢驗(yàn)方法進(jìn)行評(píng)測，選取兩幅圖像處理領(lǐng)域的經(jīng)典標(biāo)準(zhǔn)圖片進(jìn)行檢驗(yàn)，分別為水果和帆船。

2.2 實(shí)驗(yàn)分析

2.2.1 直線檢測（使用案例檢驗(yàn)測試）

圖6 為Lenna 圖與五角大樓圖（彩圖掃OSID 碼可見），為了更清晰地觀察到結(jié)果，在原圖中截取了一部分作為局部放大圖，分別在圖中的第2 列和第4 列。其中圖6（a）為原圖，圖6（b）為預(yù)處理后的邊緣圖，圖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 中可觀察到，霍夫變換在圖像邊緣密集（比如紋理）情況下的直線檢測效果并不好，常常是錯(cuò)誤而雜亂的，具體表現(xiàn)在Lenna的頭發(fā)和眼睛上?；舴蜃儞Q還存在很多漏檢的直線，比如Lenna 的帽子邊緣沒有被檢測到，從圖6 中五角大樓的局部放大圖也可看出霍夫變換算法誤檢了許多短線段。LSD 算法的檢測效果不太穩(wěn)定，在Lenna 圖中，可明顯看到在帽頂處漏檢了一些直線段，由此造成圖像主體邊緣的不連續(xù)，同時(shí)對于五角大樓局部放大圖中的停車場也漏檢了許多短線段。由表1、表2 可知，相比霍夫變換算法和LSD 算法，本文方法誤檢和漏檢的情況較少。

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

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

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

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

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

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

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

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

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

Table 3 Evaluation results of line segment detected by different methods表3 不同方法檢測直線段評(píng)估結(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é)語

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