陳顯峰 ，劉超慧

(1.太原理工大學(xué) 理學(xué)院，山西 太原 030024；2.鄭州航空工業(yè)管理學(xué)院 計(jì)算機(jī)科學(xué)與應(yīng)用系，河南 鄭州 450015)

在圖像處理中，直線的提取有著極其重要地位和廣泛的用途。直線檢測的結(jié)果直接決定了對所處理圖像的準(zhǔn)確認(rèn)識。在各種直線檢測方法中，基于Hough變換的方法已經(jīng)形成了一個重要的分支。針對基于Hough變換方法計(jì)算量大、內(nèi)存占用多、比較耗時(shí)等缺點(diǎn)，已提出了許多改進(jìn)措施。如使用邊緣點(diǎn)處的梯度方向，可以減少可投票的參數(shù)點(diǎn)數(shù)量，并在一定程度上抑制了虛假的直線參數(shù)峰值；徐剛鋒等人提出的RLD則是利用點(diǎn)到直線的距離來提高直線檢測速度。

RLD雖然是一個有效的直線檢測算法，但在實(shí)際圖像處理中，常會因所選取3點(diǎn)的位置關(guān)系造成直線誤檢或漏檢。本文的算法與RLD算法思想相同，不同之處在于不是以點(diǎn)到直線的距離而是以直線夾角來判斷3點(diǎn)是否共線，不但解決了基于Hough變換方法從圖像空間轉(zhuǎn)化到參數(shù)空間引起的耗時(shí)、所需存儲空間大等問題，也彌補(bǔ)了RLD存在的不足。

1 基于夾角的直線檢測算法

1.1 直線夾角的計(jì)算方法

如圖 1(a)所示，平面 3點(diǎn) A、B、C確定 3條直線 L1、L2、L3。如果用點(diǎn)到直線的距離來判斷3點(diǎn)共線，在由點(diǎn)確定的2條直線不變的情況下，距離值隨第3點(diǎn)在直線上的位置不同而有較大變化，因而無法選擇固定距離閾值進(jìn)行3點(diǎn)共線的判定，如圖 1(b)所示，第 3點(diǎn)在 S處和T處到直線L1的距離是不同的，從而判定結(jié)果也可能不同，即用點(diǎn)到直線的距離來判斷3點(diǎn)共線缺乏不變性。本文選用基于直線夾角進(jìn)行3點(diǎn)共線的判斷方法，克服了點(diǎn)到直線的距離判斷方法的缺點(diǎn)，可以獲得固定的閾值，適用范圍廣泛。

圖1 平面3點(diǎn)與它們確定的直線的關(guān)系

假設(shè)由 A(x1，y1)、B(x2，y2)、C(x3，y3)3 點(diǎn)確定 3 條直線 L1、L2、L3 兩兩之間的夾角分別為 θ1、θ2和 θ3，對 θ1有：

在實(shí)際圖像處理過程中，由于成像噪聲、像素點(diǎn)坐標(biāo)取樣誤差以及特征點(diǎn)檢測誤差的影響，3條直線的夾角通常不為零，必須先根據(jù)實(shí)際情況，確定1個合適的值作為夾角閾值。 只要 θ1、θ2和 θ3中有 1個小于閾值，就可以判定3點(diǎn)共線。

1.2 直線檢測算法

假設(shè)所選3點(diǎn)共線，且3點(diǎn)所在的直線用y=ax+b表示，該直線只是圖像中可能存在的直線，要想確定它是否真實(shí)存在還要進(jìn)一步用點(diǎn)的累加來判斷，如對應(yīng)累加器的值大于所給定的閾值，則判定該直線存在，并將該直線上的所有點(diǎn)從由圖像邊緣點(diǎn)構(gòu)成的數(shù)據(jù)空間中刪除，以減小判斷下一條直線的計(jì)算量；否則判定這條直線不存在。

具體直線檢測算法步驟如下：

(1)建立包含所有邊緣數(shù)據(jù)的空間點(diǎn)集P。

初始化失敗累加器f=0，設(shè)置門限Tf為最大容許的失敗次數(shù)，θT、Ts分別表示夾角閾值和峰值門限。

(2)如果 f≥Tf，程序結(jié)束，從數(shù)據(jù)空間 P中隨機(jī)選取3個點(diǎn) pi、pj、pk，同時(shí)將這3個點(diǎn)從空間去除。

(3)3點(diǎn)中的任意2點(diǎn)確定1條直線，根據(jù)式(1)計(jì)算3 條直線兩兩之間的夾角 θi、θj和 θk。

(4)若 θi≤θT或 θj≤θT或 θk≤θT，則 判 定 3 點(diǎn) 共 線 ，并求該直線的方程，繼續(xù)下一步；否則，f=f+1，將 pi、pj、pk放回?cái)?shù)據(jù)空間，返回第(2)步。

(5)初始化累加器S=0，將P中剩余的每 1點(diǎn)分別代入該直線方程，若滿足該方程，則將此點(diǎn)從數(shù)據(jù)空間去除，相應(yīng)的累加器S加1，直到所有的邊緣點(diǎn)都檢測完畢。

(6)如果S＞Ts，則認(rèn)為該直線存在，將該直線上的所有點(diǎn)從P中刪除。返回第(2)步。

2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證新算法的性能，在MATLAB平臺下，對大量的圖像進(jìn)行了仿真實(shí)驗(yàn)。圖2、圖3和表1分別給出了其中的部分實(shí)驗(yàn)結(jié)果。圖2為本文算法下對加入噪聲的圖片進(jìn)行直線提取的結(jié)果，圖3為公路實(shí)況圖在基于Hough變換方法、RLD算法和本文算法下的直線提取結(jié)果，3種算法的處理時(shí)間如表1所示。

表1 本文算法與Hough變換耗時(shí)比較

實(shí)驗(yàn)結(jié)果表明：

(1)圖2結(jié)果證明本文算法可行，且抗噪性能好，提取直線的分辨率高。

(2)從圖3可以看出，利用3種直線提取算法進(jìn)行直線檢測得到的結(jié)果大致相同，僅直線位置和運(yùn)行時(shí)間有微小變化。對比其結(jié)果：Hough變換雖能從全局圖像中提取直線，卻不能確切得到直線端點(diǎn)和長度，且容易將不構(gòu)成實(shí)際直線的邊緣點(diǎn)投票決定成偽直線；RLD算法由于其判斷3點(diǎn)共線方法存在的缺陷，容易檢測不到圖像中實(shí)際存在的直線；本文算法能準(zhǔn)確地提取出圖片中存在的直線。

(3)由表1可知，由于RLD算法和本文算法不用將圖像邊緣點(diǎn)映射到另外一個參數(shù)空間進(jìn)行累加、判斷，因而其處理速度明顯優(yōu)于Hough變換。

本文提出了一種基于夾角的直線檢測算法，通過在數(shù)據(jù)空間任意選取3個點(diǎn)，運(yùn)用直線夾角來判斷3點(diǎn)是否共線，然后再通過累加邊緣點(diǎn)來進(jìn)一步判定這條直線的真實(shí)性。不但解決了Hough變換存在的耗時(shí)、運(yùn)行速度慢、只能處理一些比較簡單的圖像等問題，也彌補(bǔ)了RLD容易少檢直線的不足，而且驗(yàn)證了本算法具有較高的直線檢出率和檢測速度，是一種有效的直線檢測算法，適用于各種圖像的直線檢測。

[1]ILLINGWORTH J.A survey of the hough transform[J].Computer Vision Graphics and Image Processing，1988，44(1)：87-116.

[2]姚敏.數(shù)字圖像處理[M].長沙：機(jī)械工業(yè)出版社，2006.

[3]XU L， OJA E， KULTANAN P.A new curve method：randomized Hough transform(RHT)[J].Pattern Recognition Letters， 1990，11(2)：331-338.

[4]郭斯羽，孔亞廣，張熙芳.基于局部連通性和 PCA的直線檢測Hough算法[J].電子測量與儀器學(xué)報(bào)，2008，22(6)：70-74.

[5]朱芳芳，顧宏斌，孫謹(jǐn).一種改進(jìn)的 Hough變換直線檢測算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(5)：19-22.

[6]賈云俠，祁飛，江友誼，等.一類參數(shù)空間利用率最優(yōu)的直線檢測方法[J].紅外與激光工程，2009，38(4)：742-747.