一種改進的直線檢測算法

朱書華

（國家知識產權局專利局專利審查協作廣東中心，廣東 廣州 510530）

0 引言

直線段、曲線段和角點是組成物體的最基本的幾何特征，它們是對目標物體進行高層研究的基礎，從圖像中準確識別這些特征是計算機視覺領域的重要研究內容之一，對智能交通、數字地圖的更新和城市交通狀況監測具有重要意義[1-3]。

經典的直線檢測算法由霍夫變換(Hough Transform)來實現。Hough變換是由Paul Hough提出的，其最初是用來檢測圖像中的直線的一種方法[4]。由于Hough變換是通過在兩個笛卡爾坐標系之間的變換來進行直線檢測的，所以當直線的斜率趨向于無窮大時，用該方法來檢測直線就帶來了一定的困難。

基于相位編組檢測直線是另一種檢測直線的方法，相位編組是由Brian Burn J[5]在1986年提出的，由P.Kahn做了全面的改進。該算法涉及到兩個概念，即邊緣支持區和梯度相位。邊緣支持區是由梯度方向相同的相鄰像素點組成。在像素的鄰域范圍內，其灰度變化最大的方向即為梯度相位。相位編組檢測直線的原理即是基于梯度方向一致性。該算法將提取直線簡化為鏈接和分組兩個過程，同時該方法還可以計算出直線的寬度、長度等。Hough變換實質上也涉及到了邊緣的相位問題，但是在Hough中，只有幅值大的邊緣才能被檢測出來，而相位編組算法則在提取直線的過程中不受對比度、局部寬度等的影響。

基于主成分分析(Principal components analysis，PCA)或基于協方差矩陣最小特征根檢測直線的方法是近幾年提出的一種新的檢測直線的方法。該方法利用了直線的連續性，它以邊界上的一點和包含該點的一段連續邊界為對象來研究，首先構造協方差矩陣，并計算最小特征根，如果其最小特征根小于預先設定的閾值，則表示此段邊界為直線[6]。2004年，Guru提出了基于最小特征根檢測直線的方法[7]，該方法由于計算簡單、高效，因此得到了廣泛的應用。但是由于此方法在檢測過程中，使用傳統的局部窗口進行檢測，因此會出現將平滑曲線誤判為直線的問題，且對噪聲也較敏感。2006年，Yun-Seok Lee等人對該方法進行了改進[8]，該方法通過將邊緣圖像的像素點分為行像素圖和列像素圖，從而避免了局部窗口產生噪聲的影響，且在時間上也有了大大的提高，但是當兩直線相交形成的角度比較大時，用此方法就會出現嚴重的漏檢情況，且還會把部分光滑曲線檢測為直線。引入鏈碼算法可以較好的解決此問題，但是由于鏈碼算法易受噪聲的影響，且加入鏈碼后，檢測直線所有的時間較長。

從目前的研究現狀來看，現有的上述算法對直線的檢測存在困難，據此，本文提出了一種直線檢測改進算法，對邊緣檢測的圖像進行線段拆分，基于協方差矩陣特征根初步檢測出直線、圓、曲線，并基于各個像素點的方向變化而將初步檢測出的曲線進行進一步檢測獲得其含有的直線部分，通過結合初步檢測的直線和曲線中檢測的直線部分實現直線檢測。

1 算法模型

1.1 線段拆分

自然場景中的線段端點通常有兩種情況：（1）兩向交點：線段與另一條曲線或直線的交點；（2）多向交點：線段與其它兩條或兩條以上曲線或直線的交點。根據線與線相交的仿射不變性，自然場景映射為數字圖像后，端點將仍然存在，并且大部分兩向交點會映射成為角點，多向交點會映射成為交叉點?；诖耍B續邊緣終點、交叉點和角點必然是最有可能構成線段端點的特征。

因此，從線段入手，通過對線段分解及每條線段的方向變化來對物體的特征識別進行研究，其中包括對物體的直線段，平滑曲線識別。為了提取準確的直線，本文采用能夠連接局部弱邊緣的Canny算子對源圖像進行邊緣檢測，設其邊緣圖像為E，E中邊緣具有單像素寬度，對邊緣圖像E進行線段拆分，其具體過程如下所示。

圖1 3×3鄰域內的交叉點結構

考察E(x,y)中某邊緣像素P的3×3鄰域，像素點序號如圖1(a)所示。設x(i),i=1,…,9表示P的3×3鄰域內的像素值(0或1)，定義：a=[x(1),x(2),x(3),x(6),x(9),x(8),x(7),x(4)]，b=[x(2),x(3),x(6),x(9),x(8),x(7),x(4),x(1)]，如果其滿足：

則為交叉點，如圖1(b)所示，對經過Canny邊緣檢測之后的圖像E，依據式（1），對E進行交叉點檢測，如果某邊緣像素滿足式（1）中條件，則將該像素賦值為0。重復檢測，直到E中不存在交叉點。其具體實例如圖2所示，其中2(a)是源圖像，圖2(b)是Canny邊緣檢測的圖像，其交叉點和端點如圖2(c)所示，其中十字交叉點表示線段的端點，圓圈表示三叉交點，其中不同的顏色代表了各個不同的拆分出來的線段。依據上述規則，檢測E中的交叉點，如果某邊緣像素滿足式（1）中條件，則將該像素賦值為0。重復檢測，直到E中不存在交叉點，此時定義不含交叉點的邊緣圖像為Ed：

其中，mi表示組成線段Ci的像素點數，其中，(xij,yij)表示第i條線段上第j個像素點的坐標，Ci上每個點的值為1。其對Canny邊緣檢測之后的圖像進行邊緣拆分，其線段拆分之后的結果如圖2(d)所示。

圖2 端點和交叉點結果圖

1.2 基于協方差矩陣特征根的線段形狀初步檢測

經過邊緣分解，Ed中包含若干條獨立且連續的線段Ci，其形狀可能是曲線、圓或直線。根據微分幾何定理，以弧長表示C2類平面曲線Ci:r=r(s)，則Ci在一點pj=r(s0)的鄰近結構利用泰勒公式展開后，結合伏雷內公式，可得：

式（3）中，α,β 為平面曲線基本向量，κ 為曲率，ε1,ε2為微小量，Δs為局部曲線弧長，取r(s0)為直角坐標系原點，以α,β為坐標系基向量，在r(s0)點鄰近，曲線的近似方程為：

即曲線在一點的鄰近結構有三種可能：二次拋物線，三次拋物線和直線。對于數字圖像而言，局部范圍內很難區分三次拋物線和直線，因此可忽略三次拋物線的情況，即在數字圖像中，考慮曲線在一點的鄰近結構只有二次拋物線和直線這兩種可能。

對 Ci={pj=(xij,yij),j=1,…,mi},i=1,…,n，取 pj=(xij,yij)左右 4 相鄰點組成局部支持集Cij={pj｜i-4≤j≤i+4}。根據協方差矩陣檢測直線的原理[7-8]，定義向量 x1=[xi(j-4),…,xij,…,xi(j+4)]，x2=[yi(j-4),…,yij,…,yi(j+4)]，如果設輸入矩陣為X={x1,x2},xi∈Rn,(i=1,2)，則有協方差矩陣：

對 CX進行特征根分解，可得 p 特征向量和兩個特征值 λ1,λ2(λ1＞λ2)：

其中，特征向量p1代表數據X主方向，p2⊥p1，兩個特征值λ1,λ2分別代表數據X在方向p1和p2上的方差。從微分幾何的觀點，可認為p1，p2是平面曲線 Ci在點 pj=(xij,yij)的伏雷內標架，p1=α,p2=β。

（1）基于協方差矩陣最小特征根λ2檢測直線

由文獻[8]可知：如果由 Cij={pj｜i-4≤j≤i+4}定義的 CX計算所得的最小特征值λ2=0，則Cij上的點滿足直線方程，且最小特征根的值越接近于0，表示像素點的共線性越好。因此，當λ2為0時，檢測為直線。

（2）基于協方差矩陣兩特征根比值λ1/λ2檢測圓和曲線

由文獻[9]可知，如果支持集中的邊界像素點共圓，則其兩特征根滿足關系式 λ1=λ2。 因此，當兩特征根 λ1/λ2的比值等于1時，檢測為圓。協方差矩陣的兩個特征值λ1/λ2的比值大小反映了線段的彎曲程度，比值越小，即其值越接近1，其彎曲越大，等于1時表示的是圓；反之，比值越大彎曲越小，當λ2為0時，比值為+∞，表示的是直線。

1.3 曲線中直線部分的進一步檢測

對于前述初步檢測出的直線、圓、曲線，其中曲線還可能含有直線部分，對此，可利用曲線中的方向變化檢測出曲線中的直線部分，從而細分出曲線中的直線部分，并結合前述初步檢測的直線實現直線檢測。設待檢測的連續邊緣為Ci(1≤i≤n)，統計曲線上各像素點的方向值dir，得到局部直線方向直方圖，設定如果某一方向值dir出現的次數大于預設閾值Tdis，則對這些像素點進行最小二乘直線擬合，求解最小化問題：

求得式（13）的參數ka和ba后，再考慮Ci上其他點到擬合直線的距離誤差值：

如果dis(i)＜Tdis(Tdis為預設閾值)，則認定該像素點i屬于直線部分，統計所有滿足條件的像素點的坐標構成新的直線集合Ldir，記為檢測出的直線部分。

2 實驗結果與分析

為了驗證本文算法對直線識別的有效性，我們選取了三類圖像進行試驗，并分別將直線檢測的結果與三種經典算法：Hough變換直線檢測、相位編組、最小特征根算法[8]進行對比，其中三類圖像分別為人工合成圖像、含有曲線的建筑物圖像、含有圓的道路指標圖像。

2.1 人工合成圖像

圖3(a)為源圖，圖3(b)是Canny邊緣檢測的圖像，圖3(c)是Hough變換直線檢測結果，圖3(d)是相位編組檢測結果，圖3(e)是最小特征根檢測結果，圖3(f)是本文算法檢測結果。對比圖3(c)-(f)與邊緣檢測得到的圖3(b)中右上角的圓、橢圓、矩形檢測結果可以發現，本文算法直線檢測效果最好，成功去除了圓和橢圓，Hough變換和相位編組檢測結果均不能去除圓和橢圓，最小特征根直線檢測僅去除了橢圓的一部分。

圖3 人工合成圖像檢測結果

圖4 建筑物圖像檢測結果

2.2 含有曲線的建筑物圖像

圖4為含有曲線的建筑物圖像檢測結果，通過圖4(c)-(f)與邊緣檢測得到的圖4(b)比較，可以發現：本文算法檢測效果最好，較成功地去除了右下角草坪的大圓弧，Hough變換和相位編組均將弧當作部分直線，最小特征根法在去除弧的效果上也沒有本文算法理想。

2.3 道路指標圖像

圖5為道路指標圖像檢測結果，通過圖5(c)-(f)與邊緣檢測得到的圖5(b)比較，可以發現，本文算法在檢測過程中能成功的去除圓，且對于檢測出的直線，本文算法能較好的將檢測出的各個直線段斷開，方便了后續各個直線段的擬合。

圖5 道路指標圖像檢測結果

3 結論

提出了一種直線檢測的改進算法，該算法包括線段拆分、初步檢測和曲線的進一步直線部分細分，相比傳統的直線檢測算法，本算法可以在較準確檢測直線的同時，有效地去除邊緣圖像中的曲線和圓。

[1]Li Q F,Shi J F,Li C.Fast Line Detection Method for Railroad Switch Machine Monitoring System [C]//International Conference on Image Analysis and Signal Processing,2009:61-64.

[2]Ding Weili,Wang Wenfeng,Zhang Xuguang et al..Extracting straight lines from building image based on orientation image[J].Acta Optica Sinica,2010,30(10):2904-2910.

[3]Chen G,Li L,Ma J W,A Gradient BYY.Harmony Learning Algorithm for Straight Line Detection[J].Lecture Notes in Computer Science,2008,5263:618-626.

[4]Hough P V C.Method and Means for Recognizing Complex Patterns[P].US Patent,No 3069654,1962,2.

[5]Brian,Burns J,Hanson A R et al..Extracting Straight Lines[J].IEEE Transactions on Pattern Analysis and Machine Intelligent,1986,8(4):425-455.

[6]Kuang Ping,Zhu Qingxin,Chen Xudong.Line Detection Algorithm Based on the Smallest Eigenvalue Analysis[J].Journal of Electronic Measurement and Instrument,2007,21(3):33-38.

[7]Guru D S,Shekar B H,Nagabhushan P.A Simple and Robust Line Detection Algorithm Based on Small Eigenvalue Analysis[J].Pattern Recognition Letters,2004,25(1):1-13.

[8]Lee Y S,Koo H S,Jeong C S.A Straight Line Detection using Principal Component Analysis[J].Pattern Recognition Letters,2006,27(4):1744-1754.

[9]Tsai D M,Hou H T,Su H J.Boundary-based Corner Detection using Eigenvalues of Covariance Matrices[J].Pattern Recognition Letters,1999,20(1):31-40.