一種改進(jìn)的直線檢測(cè)算法

朱書華

（國(guó)家知識(shí)產(chǎn)權(quán)局專利局專利審查協(xié)作廣東中心，廣東 廣州 510530）

0 引言

直線段、曲線段和角點(diǎn)是組成物體的最基本的幾何特征，它們是對(duì)目標(biāo)物體進(jìn)行高層研究的基礎(chǔ)，從圖像中準(zhǔn)確識(shí)別這些特征是計(jì)算機(jī)視覺(jué)領(lǐng)域的重要研究?jī)?nèi)容之一，對(duì)智能交通、數(shù)字地圖的更新和城市交通狀況監(jiān)測(cè)具有重要意義[1-3]。

經(jīng)典的直線檢測(cè)算法由霍夫變換(Hough Transform)來(lái)實(shí)現(xiàn)。Hough變換是由Paul Hough提出的，其最初是用來(lái)檢測(cè)圖像中的直線的一種方法[4]。由于Hough變換是通過(guò)在兩個(gè)笛卡爾坐標(biāo)系之間的變換來(lái)進(jìn)行直線檢測(cè)的，所以當(dāng)直線的斜率趨向于無(wú)窮大時(shí)，用該方法來(lái)檢測(cè)直線就帶來(lái)了一定的困難。

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

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

從目前的研究現(xiàn)狀來(lái)看，現(xiàn)有的上述算法對(duì)直線的檢測(cè)存在困難，據(jù)此，本文提出了一種直線檢測(cè)改進(jìn)算法，對(duì)邊緣檢測(cè)的圖像進(jìn)行線段拆分，基于協(xié)方差矩陣特征根初步檢測(cè)出直線、圓、曲線，并基于各個(gè)像素點(diǎn)的方向變化而將初步檢測(cè)出的曲線進(jìn)行進(jìn)一步檢測(cè)獲得其含有的直線部分，通過(guò)結(jié)合初步檢測(cè)的直線和曲線中檢測(cè)的直線部分實(shí)現(xiàn)直線檢測(cè)。

1 算法模型

1.1 線段拆分

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

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

圖1 3×3鄰域內(nèi)的交叉點(diǎn)結(jié)構(gòu)

考察E(x,y)中某邊緣像素P的3×3鄰域，像素點(diǎn)序號(hào)如圖1(a)所示。設(shè)x(i),i=1,…,9表示P的3×3鄰域內(nèi)的像素值(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)]，如果其滿足：

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

其中，mi表示組成線段Ci的像素點(diǎn)數(shù)，其中，(xij,yij)表示第i條線段上第j個(gè)像素點(diǎn)的坐標(biāo)，Ci上每個(gè)點(diǎn)的值為1。其對(duì)Canny邊緣檢測(cè)之后的圖像進(jìn)行邊緣拆分，其線段拆分之后的結(jié)果如圖2(d)所示。

圖2 端點(diǎn)和交叉點(diǎn)結(jié)果圖

1.2 基于協(xié)方差矩陣特征根的線段形狀初步檢測(cè)

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

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

即曲線在一點(diǎn)的鄰近結(jié)構(gòu)有三種可能：二次拋物線，三次拋物線和直線。對(duì)于數(shù)字圖像而言，局部范圍內(nèi)很難區(qū)分三次拋物線和直線，因此可忽略三次拋物線的情況，即在數(shù)字圖像中，考慮曲線在一點(diǎn)的鄰近結(jié)構(gòu)只有二次拋物線和直線這兩種可能。

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

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

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

（1）基于協(xié)方差矩陣最小特征根λ2檢測(cè)直線

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

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

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

1.3 曲線中直線部分的進(jìn)一步檢測(cè)

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

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

如果dis(i)＜Tdis(Tdis為預(yù)設(shè)閾值)，則認(rèn)定該像素點(diǎn)i屬于直線部分，統(tǒng)計(jì)所有滿足條件的像素點(diǎn)的坐標(biāo)構(gòu)成新的直線集合Ldir，記為檢測(cè)出的直線部分。

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

為了驗(yàn)證本文算法對(duì)直線識(shí)別的有效性，我們選取了三類圖像進(jìn)行試驗(yàn)，并分別將直線檢測(cè)的結(jié)果與三種經(jīng)典算法：Hough變換直線檢測(cè)、相位編組、最小特征根算法[8]進(jìn)行對(duì)比，其中三類圖像分別為人工合成圖像、含有曲線的建筑物圖像、含有圓的道路指標(biāo)圖像。

2.1 人工合成圖像

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

圖3 人工合成圖像檢測(cè)結(jié)果

圖4 建筑物圖像檢測(cè)結(jié)果

2.2 含有曲線的建筑物圖像

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

2.3 道路指標(biāo)圖像

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

圖5 道路指標(biāo)圖像檢測(cè)結(jié)果

3 結(jié)論

提出了一種直線檢測(cè)的改進(jìn)算法，該算法包括線段拆分、初步檢測(cè)和曲線的進(jìn)一步直線部分細(xì)分，相比傳統(tǒng)的直線檢測(cè)算法，本算法可以在較準(zhǔn)確檢測(cè)直線的同時(shí)，有效地去除邊緣圖像中的曲線和圓。

[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.