基于新式方向鏈碼的直線檢查算法

1、基于改進freeman方向鏈碼的道路邊界檢測算法摘要：本文提出了一種適合于直線檢測的新式的dcc鏈碼方法，克服了采川傳統(tǒng) freeman鏈碼在直線檢測上的不足，簡化了直線鏈碼方向標注方法，同時dcc編碼的引入 也把基于聚類的方法的直線檢測巾四個過程簡化為三個過程。同時，本文基于dcc鏈碼編 碼方法，提出了利用鏈碼判別直線的新判據(jù)，最后提出了 pol方法進行線段的連接，實驗 結(jié)果表明了算法的有效性。關(guān)鍵字：圖像識別直線檢測freeman鏈碼線段檢測1引言直線檢測也是閣像處理的重要p、j容之一。直線檢側(cè)是在邊緣檢測的基礎(chǔ)上將離散的邊緣 點直線化并對直線的參數(shù)進行估計的過程?，F(xiàn)有的直線檢測算法可以分

2、為兩人類基于霍夫變 換的方法和基于聚類的方法?；诨舴蜃儞Q的方法已有大量文獻進行了探討，本文不再進行介紹?；诰垲惖姆椒ㄖ?線通過對直線段或邊界鏈碼段的跟蹤、刪減、合并得到檢測結(jié)果。一般而言，該方法的主要 分為邊緣鏈碼檢測、角點檢側(cè)、直線鏈碼識別、直線連接等四個過程2?！边@類方法的主要 優(yōu)點是計算不sz雜，適用于實時處理，可以檢測局部直線段。不足之處在于邊緣跟蹤不能處 理有間斷的直線，因此該算法的性能在很大程度上受邊緣檢測算法的制約”31。本文提出的算法屬于聚類的方法。聚類的方法檢測直線大多采川freeman鏈碼編碼并進 行直線特性的判別，國內(nèi)外的學者提出了很多算法。文獻【1】文獻【2】提出了

3、基于freeman 直線判別準則的bl算法，但是算法為了提高精度而引入了復雜的判裾，并且其直線連接算 法的判據(jù)也不嚴密，其缺點在文獻【7】中有所分析。文獻【3】對鏈碼的跟蹤方法進行了改 進，從而更加效地對直線進行編碼，但米對freeman編碼本身進行改進，其直線檢測和直線 連接沿已有的方法，未提出自己的新方法。文獻【4】對freeman編碼進行了改進，采用 了更精確的16鄰域編碼，對點的鏈碼編碼方式也進行了改進，鏈碼的編碼是相對于基準點 的方向而非相對于鄰近點的方向，并據(jù)此提出直線判裾，但是16方向的鏈碼增加了鄰域搜 索的時間，并且其采用的直線判斷的方法的容錯性也不強。文獻【5】基于freem

4、an提出的關(guān) 于數(shù)字直線的準則和數(shù)字直線的特征，提出一種以線段元為基本單位進行直線的構(gòu)造并檢測 出圖像屮物體邊界屮的直線的算法.文獻【6】給出了一種基于直線鏈碼的freeman吳定 理的增量式直線鏈碼識別算法。文獻【7】對文獻【2】中bl算法進行了改進，提出了一個 新的基于鏈碼的最小直線段長度和最小直線段近似度識別直線的方法。文獻【8】對直線檢 測的一些步驟進行了改進，引入分層并行迭代式處理結(jié)構(gòu)，提山了高效實用的并行直線段檢測 ©法.文獻【9】文獻【10】提出一種利用兩條動態(tài)調(diào)整的直線邊界構(gòu)造像素通行區(qū)的方法進 行直線檢測，并進行了詳盡的實驗分析。文獻【11】提出了一種基于freem

5、an提出的直線鏈 碼三條準則的直線識別的算法。2對freeman編碼的改進-新式dcc編碼一條離散曲線可以定義為z2域內(nèi)一組數(shù)量有限的連通點。因此，一條數(shù)字化二值曲線 可用方向鏈碼表示。如圖1所示，freeman鏈碼是相鄰兩像素連線的8種可能的方向值。一條 曲線按照如圖1所示被網(wǎng)格離散化后形成n個方向鏈碼，這個n個方向鏈碼組成了這條曲 線，此曲線鏈碼可表示為ain，其中ai=0,l，2,3,4,5,6,7，i為像素的索引值，ai表示由像素i指 向像素i+1的方向鏈碼。圖1 freeman的8鄰域鏈碼圖2本文提出的5鄰域dcc鏈碼圖3 freeman方式的編碼 圖4本文提出dcc方式的編碼fre

6、eman鏈碼是一種全方向的編碼方法，因此freeman鏈碼能夠?qū)A等多方向曲線進行 編碼。例如圖 3 巾曲線的 freeman 鏈碼就是ail4= 2, 2，1, 2，1, 1，1，0，7，6，6，6, 7, 0，其中ai=0,l，2,3,4,5,6,7。但是利用freeman鏈碼對直線編碼并不是一種高效的方法。 “第一 freeman跟蹤方式?jīng)]有在最大程度上保證跟蹤鏈碼的直線性。第二，在直線相交處， 由于相交的點在第一次跟蹤的時候已經(jīng)被設(shè)為非邊緣點，因此第二條跟蹤的直線會被分割成 兩小段“31。因此，用freeman鏈碼對如圖3所示曲線進行了編碼后，必須進行角點檢測j 能將組成鏈碼的兩條直線

7、段分開，這就增加了直線檢測的步驟（耑要進行角點檢測），從而 增加了直線檢測的復雜度和運算時間。由于直線是一種特殊的曲線，具有很強的方向性，因而采用freeman鏈碼的8鄰域全方 向編碼對直線來說是一種冗余編碼，這就給我們針對直線對艽進行改進提供了可能。本文提 山了一種新式的單方向鏈碼dcc （direction chain code）編碼方法可以克服freeman鏈碼 的缺點，這種dcc鏈碼尤其適用于對直線進行編碼，其dcc鏈碼的單方向性決定了其不 能對圓進行編碼。這種鏈碼方法基于以下基本思想，直線是一種特殊的曲線，方向性強，因 而利用一種單方向的鏈碼可以對其進行更加有效的編碼?？梢宰C明，對一

8、幅m行n列的閣 像，按照先行后列的順序，以圖2所示的dcc鏈碼編碼方法進行對圖像進行處理，可以對 圖像中的所有的曲線進行編碼而不會有遺漏。需要指山的是，在dcc編碼方式下，對一幅 圖像的曲線進行編碼時，編碼算法遍歷圖像的順序和方向并非是任意的。在dcc編碼的方 式下，編碼算法遍歷圖像的順序和方向必須是由上到下，先行后列。從圖2可以看出，因為 dcc鏈碼不能對當前點（閣2屮的黑圓點）的上方點進行編碼，因此編碼算法要求由上到下進 行編碼。此外，如果編碼算法按照由上到下，先列后行的順序執(zhí)行，同樣不能對一幅閣像屮 的所有曲線進行編碼，在這種情況下，只有一部分的直線可以被編碼，如圖7和圖8所示。圖5是一

9、幅待編碼的原圖像，圖6到圖8分別是編碼算法采用不同的遍歷順序得到的 dcc編碼的直線。圖6中編碼算法的遍歷順序是由上到下，先行后列（按列值升序遍歷和 按列值降序遍歷結(jié)果一致），可以看出，圖像中全部曲線都得到了編碼。圖7中編碼算法的 遍歷順序是由上到下，先列后行（自左向右或者列值增大的方向），只有右半部圖像得到了 編碼。圖8中編碼算法的遍歷順序是由上到下，先列后行（自右向左或者列值減小的方向）， 只有左半部圖像得到了編碼。通過實驗發(fā)現(xiàn)，和采川freeman鏈碼不同，采川dcc鏈碼進行編碼，對編碼算法的遍歷順序必須是巾上到下，先行后列圖7圖8此外，dcc鏈碼還帶來了兩個好處。第一，dcc鏈碼提商了

10、直線的編碼效率，直線鏈碼的編碼方式變得簡單，dcc鏈碼縮 小了臨近點的搜索空間。通常，需要進行搜索的鄰近點的數(shù)h由8個（8鄰域空間）減少到 了 5個（5鄰域空間）。事實上，如果以當前點的前繼點的鏈碼方向為先驗條件，對鄰近點 的搜索可以更加有針對性，耑要搜索的鄰域空間內(nèi)的鄰近點可以進一步減小到12個，例如 前一點的編碼為1或0時，搜索算法將優(yōu)先搜索1和0這兩個數(shù)值所代表的方向，提高了 一次搜索的成功率。相對于采用freeman鏈碼，dcc鏈碼方法在很大程度上縮小了點的鄰 域的搜索空間，降低了對直線進行鏈碼編碼的時間。第二，采用dcc鏈碼對曲線進行編碼不會形成回路，dcc鏈碼的單方向性的特點決定

11、了這種編碼方式僅能夠?qū)η瘦^小的曲線進行編碼，曲率較大的曲線在這種編碼方式下將被 拆分成為兩段曲線。例如freeman鏈碼允汴對圖3中的曲線按圖中箭頭方向進行編碼，但是 采用dcc鏈碼對閣3進行編碼時，閣3屮的曲線將被打斷為如閣4所示的兩條曲線。巾此 可以看出，采用dcc鏈碼編碼方式帶來了另一個優(yōu)點，即不需要對采用fnxman鏈碼編碼 的曲線進行曲線的角點檢測，然后再利用角點檢測確定的曲線角點將該曲線鏈碼打斷。因此 dcc鏈碼編碼方式簡化；r基于鏈碼的直線的檢測步驟，使直線檢測由叫個步驟減少為直線 編碼，直線判斷，直線連接三個步驟，相對于傳統(tǒng)方法來說是一個較大改進。下而給出本文采用的直線編碼算

12、法的步驟. a 以二值閣像左上角的點為起點，按照先行后列進行搜索。b 搜索數(shù)值為1且米被訪問過的點，將該點訪問標記置位，不再重復搜索，設(shè)置該點 為當前點，轉(zhuǎn)c。當所有的點搜索完畢時算法停止。c 以當前點之前的dcc編碼為先驗條件，搜索當前點的近鄰點（adjacent point,以下 用ap表示）。若搜索成功，將該點訪問標記置位，不再重復搜索，轉(zhuǎn)d。若搜索失 敗，轉(zhuǎn)b。d 對搜索到的ap的方向（adjacent point direction,以下用apd表示）按照圖2所示進 行標記，設(shè)置搜索到的ap為當前點，轉(zhuǎn)c。經(jīng)過算法處理之后，圖4中的直線會被劃分為兩條直線，左邊一條的鏈碼按照本文提出

13、的方法，其dcc鏈碼為ai4=-l，-2，-l，0;右邊曲線的dcc鏈碼為ai7=2,2,l，2,2，l,l。如 圖3所示的曲線沒有dcc編碼，其將被拆分成如圖4所示的兩條鏈碼。3直線檢測的dcc累加和方法對曲線進行了編碼之后，需要利用鏈碼進行直線識別。1970年，freeman提出了直線鏈 碼必須滿足的三條準則n21，許多學者提山的直線檢測的方法都基于freeman提出的直線判 別準則。文獻【2】提出的bl算法根據(jù)“對于一段直線段，它在鏈碼上表現(xiàn)為在一定范圍內(nèi)只 出現(xiàn)一個方向或兩個方向交替出現(xiàn)“這一特征判斷鏈碼串的是否為直線。文獻【9】提出了通 過鏈碼方叫直方閣判斷直線鏈碼的方法。文獻【1】

14、在文獻【9】的基礎(chǔ)之上對直線檢測的判 據(jù)進行了擴展。本文提山了基于dcc鏈碼的累加和方法,算法根據(jù)直線段的方向性強的特點，利用dcc 鏈碼中提供的方向信息，進行直線的檢測。該算法的基本思想如下：直線上的任意一點pi (>n，其中n為直線上點的總數(shù))來說，其前n個點方向鏈碼ai的累積和f(i)和后n個點的 方向鏈碼ai的累積和g(i)相差不超過一個設(shè)定的直線檢測閾值t,見公式(1)。對以dcc鏈碼編碼的直線鏈碼ain(n為直線鏈碼的k度)，當且僅當其直線鏈碼aij n滿足下列公式吋成立：.n-n其中： taii=n 代.nai(1)直線檢測的閾值i點前n個點的鏈碼7/向和i點后n個點的鏈碼

15、方句和直線點的方昀鏈碼在這個直線判斷準則中，有兩個重要參數(shù)t和方向鏈碼的累計點數(shù)n。這兩個參數(shù)決定 了算法對直線鏈碼的檢測精度。t越大檢測的精度越低，n越小檢測的精度越低。合理設(shè)定 這兩個參數(shù)值就可以對以dcc鏈碼編碼的曲線的進行直線檢測，當t較小時，對直線檢測 比較嚴格，直線的鏈碼要在很大程度上符合freeman鏈碼準則。當t較大時，直線檢測的 容錯性較強，但是誤判的可能性也相應(yīng)增大。當n較小時其檢測精度較低，當n較大時其檢 測的精度較高，但是運算量相應(yīng)增大，該算法進行的是累加運算，因此運算量的增大是與n 的大小成線性關(guān)系，其算法復雜度是o(n)，其巾n是鏈碼的長度。關(guān)于參數(shù)t和n對直線檢

16、測算法的影響將在實驗驗證部分給出詳細的討論。依據(jù)公式(1)給出的直線判裾，設(shè)計直線的檢測算法如下：比較鏈碼氐度和給定值r的大小，舍棄長度小于鏈碼長度小于r(r > 2n，其屮n的意義 同方程(1)的直線，對大于r的鏈碼轉(zhuǎn)b按方程(1)對鏈碼序列進行檢驗。輸出符合條件的直線。重復步驟a和步驟b，直到所有的鏈碼序列處理完畢。閣10是一幅372x227道路閣像，采用不同的邊緣檢測算法其直線識別的效果分別顯示 在圖11和圖12中。4線段連接算法線段的連接是基于聚類的直線識別的重要步驟，線段連接的主要任務(wù)是把隔斷的同一條 直線上的線段連接起來，以得到對目標直線的更好的估計。很多的線段的連接算法匕經(jīng)

17、被提 出來，這些算法利用一些直線的兒何特性進行線段連接，例如兩線段的角度相近，兩線段間 的距離相近等等，似是許多連接算法的判據(jù)準則相當復雜。如文獻【1】采用了三條線段判 別準則。文獻【2】采用了兩條準則。如文獻【8】則采用了 5個約朿來判斷直線。本文采用了不同的方法，不需要引入復雜的直線連接判據(jù)，原理簡單，方法簡潔。其基 本思想是：對處于同一條直線上的兩條線段或多條線段而言，沿其所屬的直線方昀投影，則 所有線段在投影方向上就重合到一點。利用這種方法，就可以將第3步識別出來的同一條直 線上的線段連接起來。本文稱這種方法為投影連接方法(projection of line ) pol。圖8具體而言

18、，在圖8中，01為線段l1與豎直方向的夾角，01可以通過線段l1的兩個端 點坐標(xl，yl)和(x2，y2)用公式(2)計算出來。同理可以計算出線段l2與豎直方向的夾角020 = arcsin(x2 -%, /扣' x2)2 +(乃一y2)2 )(2)利用公式(3)和夾角01可以將線段l1上任意點旋轉(zhuǎn)到豎直方向，此時點(xl，yl)旋轉(zhuǎn)到點 (xl,yl)o同理可以得到線段l2上點(x3,y3)之后的旋轉(zhuǎn)點(x3，y3)。需要說明的是，pol方法不要求對線段鏈碼的每一個點坐標都進行旋轉(zhuǎn)變挽，這是沒 有必要的，在同一線段上的點的旋轉(zhuǎn)后的坐標x必定相同。以圖8為例，選定l1上點(xl，y

19、l) 旋轉(zhuǎn)得到(x1，y1),選定l2上的點(x3，y3)旋轉(zhuǎn)得到(x3，y3)。則處在同一直線上的兩條線段 l1和l2的點的旋轉(zhuǎn)后的坐標xi和x3必滿足以下判據(jù)：|x-x3|<s(4)其中：x,，x3分別是線段l,和線段l2選定點的投影坐標 s 是容許的旋轉(zhuǎn)坐標誤差公式(4)中有一個重要的檢測參數(shù)s,有必要加以說明。在平面幾何中，同一條直線上的 兩條線段如圖8巾的l1和l2上任意點的旋轉(zhuǎn)后的平標xi和x3(或者y1和y3,取決于旋 轉(zhuǎn)的方向)相等，即s等于0。但是在數(shù)字圖像中，點的概念和平面幾何不同，數(shù)字圖像中 的點是有大小的，數(shù)字閣像屮的任意點的坐標是并且只能是整數(shù)，而在平而兒何屮點

20、是無大 小的，其點的坐標可以是小數(shù)也可以是整數(shù)。可以證明，在平面兒何屮利用公式(2)和公式(3) 計算得到xi和x3的差值是零即s等于0,但是在數(shù)字圖像中s并不等于0?？梢岳米R別 出來的線段鏈碼精確地計算出旋轉(zhuǎn)角度的0，但是從嚴格意義上說，0并不等于線段所屬的 直線的角度e，而只是一定概率意義上的近似，近似的程度取決于線段鏈碼的精度，因此 圖8中利用公式（3）計算出來的線段l1的角度01和線段l2的角度02往往不相等，即 ei#g2#e。通常利用鏈碼較短的線段計算出來的角度e對0的估計精度較差。這就可能造成 兩條或者多條處于同一條直線上的線段采川pol方法進行線段連接時產(chǎn)生錯誤，圖12中編

21、號為11, 16, 17的連接錯誤了說明了這點。由于利用線段e對其所屬的直線角度0的估計 存在不精確性，利用e對線段上選取的點進行旋轉(zhuǎn)后的坐標xi和x3（或者y1和y3,取決 于旋轉(zhuǎn)的方向）并不完全相等。因此在pol方法中，引入了參數(shù)s來量度這種不精確性，或 者說參數(shù)s是對這種不精確性的一種估計。由于s的引入，使pol方法可以應(yīng)用到數(shù)字圖 像中，但是也帶來了如何確定合理s值的悶題。對s的取值，通?？梢匀≈?3個像素點。 本文的實驗部分對其取不同的值時給出了實驗的結(jié)果作為參考。在第2步利用dcc鏈碼編碼過程中，對組成曲線段的每個點的坐標（xi，yi）、dcc 鏈碼ai、曲線段長度信息l進行了記錄

22、，在第3步中對鏈碼進行了檢測，得到一系列符合 檢測條件的線段。利用這些信息，pol算法的步驟如下：利用線段兩端點的坐標，計算線段的角度0.如圖8所示 利用0對選定的點坐標（x,y）進行旋轉(zhuǎn)變換得到（xl,yl）對第三步檢測出的所有的其余線段執(zhí)行步驟a和步驟b,直到所有的線段處理完畢。對c中處理完畢的線段按照公式（2）進行直線連接判斷，輸出連接之后的直線。雖然平面幾何的理論可以證明pol方法的精確性和可靠性，但是在數(shù)字圖像中，pol 方法往往不能取得理論意義上的效果，原因己經(jīng)在上文屮進行了分析。這種直線投影方法在 相隔較近的兩條相鄰的線段的連接中，尚存在不完善的地方。下表（表1）是對進行圖12線

23、段連接的部分統(tǒng)計數(shù)據(jù)，表中第三列的線段標號對應(yīng)圖 12中的線段標號。組號相同的線段位于一條直線上，例如線段標號是22和13的兩條線段 處于同一條直線上，劃為一組，其組號為1。表中的數(shù)據(jù)可以看出，pol算法對組號是1， 2, 3, 4的線段組進行了正確的連接。但是組號5, 6的兩組直線沒有正確連接，這從圖12 屮也可以看到。由于鏈碼識別出的線段的不精確性，同屬于組號6的直線的線段9和線段 17的角度e分別是-18.4349和-15.8262,同樣屬于組號5的直線的線段11和線段16和21 的角度0分別是-18.0343和-15.8262和-14.8265,角度的不精確性同時，線段間距離（像素點

24、數(shù)）小丁 s的線段也會對pol算法的效果產(chǎn)生影響。通常付以通過合理選取s值來抑制干擾， 通常在線段鏈碼的精度較高時，pol算法可以取得令人滿意的效果。表1線段連接pol算法分析表檢測出的線段的條數(shù)26丁=3，11=4公式（1） s = 3公式（4）序號組號線段標號同組線段標號鏈碼串a(chǎn)in長度n線段角度權(quán)旋轉(zhuǎn)坐標x旋轉(zhuǎn)坐標差值|xrxd11221394-12.724476.33612132289-12.183777.54281.00673157,2028-14.5345144.231542715,2037-14.0362145.76391.53245207，15129-13.1906148.33

25、962.57576351881-16.0399211.x3177185174-15.507213.3061.474384232527-17.1027226.74029252328-16.5044228.0874134721051116,2144-18.0343249.084111691740-18.4349253.29844.21431252111,16109-16.0154254.511.2116131611,2169-14.8265258.13873.6287146179128-15.8262258.1820.0433備注:農(nóng)中只給出了滯要連接的線段的數(shù)裾，不茁要連接的線段標號沒耔在農(nóng)中給

26、出，數(shù)據(jù)按照旋轉(zhuǎn)坐標x升序排列4實驗驗證4.1邊緣檢測的效果直線檢測算法依賴于邊緣檢測的效果，圖10和圖11分別是采川canny邊緣檢測算法和 sobel邊緣檢測算法取得的直線檢測效果，川'以看到采用canny邊緣檢測算法的得到更精確 的檢測結(jié)果。由第2部分給出的直線編碼算法可知，本文采用的是遍歷圖像的每一個點的編 碼算法，因此本文提出的算法的運算時間與邊緣檢測算法無關(guān)，只與圖像的尺寸有關(guān)。圖9原圖像圖10直線提取結(jié)果（canny邊緣檢測）圖11直線提収結(jié)果（sobel邊緣檢測）圖12線段連接結(jié)果4.2算法的強健性t面的各種圖像圖形識別一個例子用來測試算法的有效性和強健性。5結(jié)論本文對

27、直線識別的聚類方法進行了研究，提出了一種不同于freeman編碼的適合直線 編碼的dcc編碼方法，對其性質(zhì)特點進行了簡要探討。利用dcc編碼的特點把基于聚類 的直線識別的卩4個步驟，簡化為三個步驟，提出了簡單有效的基于dcc編碼的新式直線檢 測方法。通過合理沒定參數(shù)，取得了穩(wěn)定和強健的直線識別效果。在此基礎(chǔ)之上，本文還提 出了 pol方法對同一條直線上的線段進行了連接，對pol方法的數(shù)學依據(jù)和其特點進行了 討論。本文還給出了整套方法的實驗效果，對基于聚類的直線識別具有的一定的貢獻。參考文獻1 魯光泉，許洪國，李一兵基于鏈碼檢測的直線段檢測方法計算機工程第32卷第14期2006年7月2 史冊，徐勝榮，荊仁杰等實時圖像處理中一種快速的直線檢測算法浙江大學學報（工學版 199933（5）3 裘鎮(zhèn)宇，危輝基于freeman鏈碼的邊緣