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

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

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

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

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

5、an提出的直線鏈 碼三條準(zhǔn)則的直線識(shí)別的算法。2對(duì)freeman編碼的改進(jìn)-新式dcc編碼一條離散曲線可以定義為z2域內(nèi)一組數(shù)量有限的連通點(diǎn)。因此，一條數(shù)字化二值曲線 可用方向鏈碼表示。如圖1所示，freeman鏈碼是相鄰兩像素連線的8種可能的方向值。一條 曲線按照如圖1所示被網(wǎng)格離散化后形成n個(gè)方向鏈碼，這個(gè)n個(gè)方向鏈碼組成了這條曲 線，此曲線鏈碼可表示為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等多方向曲線進(jìn)行 編碼。例如圖 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鏈碼對(duì)直線編碼并不是一種高效的方法。 “第一 freeman跟蹤方式?jīng)]有在最大程度上保證跟蹤鏈碼的直線性。第二，在直線相交處， 由于相交的點(diǎn)在第一次跟蹤的時(shí)候已經(jīng)被設(shè)為非邊緣點(diǎn)，因此第二條跟蹤的直線會(huì)被分割成 兩小段“31。因此，用freeman鏈碼對(duì)如圖3所示曲線進(jìn)行了編碼后，必須進(jìn)行角點(diǎn)檢測(cè)j 能將組成鏈碼的兩條直線

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、數(shù)）小丁 s的線段也會(huì)對(duì)pol算法的效果產(chǎn)生影響。通常付以通過合理選取s值來抑制干擾， 通常在線段鏈碼的精度較高時(shí)，pol算法可以取得令人滿意的效果。表1線段連接pol算法分析表檢測(cè)出的線段的條數(shù)26丁=3，11=4公式（1） s = 3公式（4）序號(hào)組號(hào)線段標(biāo)號(hào)同組線段標(biāo)號(hào)鏈碼串a(chǎn)in長(zhǎng)度n線段角度權(quán)旋轉(zhuǎn)坐標(biāo)x旋轉(zhuǎn)坐標(biāo)差值|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ù)裾，不茁要連接的線段標(biāo)號(hào)沒耔在農(nóng)中給

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

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