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

陳顯峰 ，劉超慧

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

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

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

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

1.1 直線夾角的計算方法

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

圖1 平面3點與它們確定的直線的關系

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

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

1.2 直線檢測算法

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

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

(1)建立包含所有邊緣數據的空間點集P。

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

(2)如果 f≥Tf，程序結束，從數據空間 P中隨機選取3個點 pi、pj、pk，同時將這3個點從空間去除。

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

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

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

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

2 實驗結果與分析

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

表1 本文算法與Hough變換耗時比較

實驗結果表明：

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

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

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

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

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

[2]姚敏.數字圖像處理[M].長沙：機械工業出版社，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].電子測量與儀器學報，2008，22(6)：70-74.

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

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