和小娟，羅 勇

(鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001)

邊界鏈碼在字母與數(shù)字混合識(shí)別中的應(yīng)用

和小娟，羅 勇

(鄭州大學(xué) 電氣工程學(xué)院 河南 鄭州 450001)

將鏈碼技術(shù)應(yīng)用到字母與數(shù)字的混合識(shí)別中，用鏈碼跟蹤其輪廓，提取形狀特征.針對(duì)鏈碼間的差異性，設(shè)計(jì)了多級(jí)分類器，獲得了良好的分類器品質(zhì).方法簡(jiǎn)單有效、存儲(chǔ)量小，具有實(shí)用性，可嵌入到車牌、圖書(shū)索號(hào)識(shí)別等應(yīng)用領(lǐng)域.

邊界鏈碼； 輪廓跟蹤； 識(shí)別

0 引言

圖像邊緣作為圖像的基本特征，是判別物體的重要依據(jù)[1].邊緣中包含物體有價(jià)值的邊界信息，可用于圖像分析、濾波及目標(biāo)識(shí)別.一系列邊界點(diǎn)構(gòu)成物體輪廓，輪廓在一定程度上可表示物體的形狀.目前，對(duì)圖像邊界表示研究較多，如鏈碼、Fourier級(jí)數(shù)、有向圖等.由于鏈碼能以較少的數(shù)據(jù)存儲(chǔ)較多的信息，可實(shí)現(xiàn)圖像數(shù)據(jù)的有效壓縮，已成為圖像邊界表示廣泛應(yīng)用的方法之一[2].字母與數(shù)字識(shí)別屬于圖像識(shí)別范疇，廣泛應(yīng)用于車牌識(shí)別、圖書(shū)索書(shū)號(hào)識(shí)別等領(lǐng)域.目前字符識(shí)別方法較多，如人工神經(jīng)網(wǎng)絡(luò)[3]、獨(dú)立分量分析[4]、Hausdorff距離[5]等.人工神經(jīng)網(wǎng)絡(luò)識(shí)別的速度和準(zhǔn)確性易受網(wǎng)絡(luò)權(quán)重初值設(shè)置的影響.獨(dú)立分量分析和Hausdorff距離分析的特征提取方法相對(duì)復(fù)雜.本文將鏈碼技術(shù)應(yīng)用到字母與數(shù)字識(shí)別中，跟蹤字符輪廓，提取其鏈碼特征，并設(shè)計(jì)多級(jí)分類器進(jìn)行字符識(shí)別.該方法簡(jiǎn)單有效，具有良好的識(shí)別效果.

1 邊界鏈碼

鏈碼是對(duì)區(qū)域邊界點(diǎn)的一種編碼表示方法.某一點(diǎn)的鏈碼是指它相對(duì)于前一個(gè)輪廓點(diǎn)的方向編碼.常用的有4-方向和8-方向鏈碼.如圖1和圖2所示.4-方向鏈碼是用中心像素指向其4個(gè)相鄰點(diǎn)的方向進(jìn)行定義，4個(gè)相鄰方向用0～3表示，鏈碼值加1，其所指方向按逆時(shí)針?lè)较蛐D(zhuǎn)90°，8-方向鏈碼與此類似.

由鏈碼構(gòu)成輪廓時(shí)，先確定起點(diǎn)絕對(duì)坐標(biāo)，其余點(diǎn)用接續(xù)方向來(lái)代表偏移量.對(duì)于每一點(diǎn)只需一個(gè)方向數(shù)就可代替兩個(gè)坐標(biāo)值，因此采用鏈碼可有效減少邊界表示的數(shù)據(jù)量[6].如圖3所示的邊界，假設(shè)起始點(diǎn)a的坐標(biāo)為(4，0)，采用4-方向鏈碼表示區(qū)域邊界，鏈碼的掃描順序?yàn)閍bcdefgba，則以a(4，0)為起點(diǎn)的4-方向邊界鏈碼為：<212122330000>，(其中“<”和“>”分別是鏈碼段起始、結(jié)束標(biāo)志，中間數(shù)值表示鏈碼值).采用8-方向鏈碼表示區(qū)域邊界，鏈碼的掃描順序?yàn)閍cefgba，則以a(4，0)為起點(diǎn)的8-方向邊界鏈碼為：<3344660000>.可知4-方向鏈碼表示的圖像邊界與實(shí)際邊界存在差異，因此本文采用8-方向鏈碼表示字符的邊界特征.

圖1 4-方向鏈碼Fig.1 4-direction of chain code

圖2 8-方向鏈碼Fig.2 8-direction of chain code

圖3 邊界鏈碼編碼Fig.3 Boundary chain coding

2 輪廓跟蹤算法

圖4 鏈碼跟蹤算法流程圖Fig.4 Flow chart of chain code tracking algorithm

圖像目標(biāo)識(shí)別時(shí)，需跟蹤目標(biāo)物體輪廓.簡(jiǎn)單的輪廓跟蹤過(guò)程為：先逐行逐列掃描圖像找到第一個(gè)像素值為1的點(diǎn)(目標(biāo)點(diǎn))作為起始點(diǎn)S，假設(shè)當(dāng)前輪廓點(diǎn)為P，則在P的8鄰域中尋找目標(biāo)點(diǎn)T，如果T的4鄰域點(diǎn)的像素值不全為1，則T是輪廓點(diǎn)，否則不是輪廓點(diǎn)；如果T和S重合，則輪廓跟蹤結(jié)束，否則繼續(xù)尋找下一點(diǎn).該算法需對(duì)每個(gè)輪廓點(diǎn)8鄰域內(nèi)所有點(diǎn)的4鄰域點(diǎn)進(jìn)行判別，計(jì)算量較大，影響跟蹤速度[7].因此，本文采用鏈碼跟蹤算法，提高跟蹤速度.

鏈碼跟蹤算法首先按行列掃描得到起始點(diǎn)，并將其作為當(dāng)前點(diǎn)，然后按逆時(shí)針?lè)较驋呙杵?鄰域，一旦掃描到像素值為1的點(diǎn)則將當(dāng)前點(diǎn)像素值置為0，同時(shí)將掃描到的點(diǎn)置為當(dāng)前點(diǎn)，按同樣規(guī)則繼續(xù)掃描直到一條鏈碼結(jié)束.接著重新掃描行列獲得起始點(diǎn)，再按同樣規(guī)則直到所有目標(biāo)點(diǎn)跟蹤結(jié)束，則整個(gè)輪廓跟蹤結(jié)束.輪廓跟蹤沿鏈碼方向進(jìn)行，下一跟蹤點(diǎn)的取得依賴于上一輪廓點(diǎn)，從而避免了對(duì)所有像素點(diǎn)進(jìn)行掃描，提高了輪廓跟蹤的效率[8].鏈碼跟蹤算法流程如圖4所示.

3 鏈碼特征的提取

對(duì)鏈碼跟蹤算法獲得的字母與數(shù)字鏈碼進(jìn)行實(shí)驗(yàn)與統(tǒng)計(jì)分析，可提取其形狀特征.本文選擇的鏈碼特征包括：1)鏈碼總段數(shù)；2)鏈碼段有無(wú)省略； 3)直線段鏈碼個(gè)數(shù)[9]；4)中間直線段鏈碼個(gè)數(shù)、方向及長(zhǎng)度[8]；5)交叉點(diǎn)個(gè)數(shù)等.

3.1鏈碼總段數(shù)

該特征指簡(jiǎn)化后鏈碼的子鏈碼個(gè)數(shù).經(jīng)過(guò)實(shí)驗(yàn)分析總結(jié)，26個(gè)字母及10個(gè)數(shù)字的鏈碼總段數(shù)可分為4類：一段(包括字母C，O，I，L，Z，V和數(shù)字0，1，2，5)，二段(包括字母D，Q，S，T，U，Y和數(shù)字3，4，6，7，8，9)，三段(包括A，B，E，H，J，N，P，R，X，W)，四段(包括F，K，M).

3.2鏈碼段有無(wú)省略

由于印刷體端點(diǎn)有短 “枝節(jié)”，以及在圖像預(yù)處理部分細(xì)化時(shí)會(huì)產(chǎn)生無(wú)關(guān)的短的“毛刺”或寄生成分[10]，因此鏈碼跟蹤時(shí)會(huì)產(chǎn)生比較短的鏈碼段，而這并不影響目標(biāo)識(shí)別.因此本文把小于5的子鏈碼去除.如字母“A”的原始鏈碼為“<0433223312322233221><44><4443212221><432221><4>”，原始鏈碼有5段，去除小于5的兩段子鏈碼，得到簡(jiǎn)化鏈碼為“<0433223312322233221><4443212221><432221>”.

3.3直線段鏈碼

若子鏈碼的鏈碼值都相同即為直線段鏈碼.如字母“U”的原始鏈碼為“<0453><2222222222222><45444332222222222222210><3>”，其中，子鏈碼“<2222222222222>”為直線段鏈碼.

3.4中間直線段鏈碼

鏈碼段中連續(xù)超過(guò)5個(gè)且相同的鏈碼值，本文稱之為中間直線段鏈碼.不同的鏈碼值其方向也不同(數(shù)字0～7分別代表向右、右上、上、左上、左、左下、下、右下).如字母“C”的原始鏈碼為“<05554444332322222222211110007776>”，其中有連續(xù)超過(guò)5個(gè)鏈碼值為2的鏈碼段，方向向上.規(guī)定連續(xù)超過(guò)5個(gè)但不超過(guò)10個(gè)的相同鏈碼值的鏈碼段為短中間直線鏈碼段，而連續(xù)超過(guò)10個(gè)的相同鏈碼值的鏈碼段為長(zhǎng)中間直線鏈碼段.

3.5交叉點(diǎn)

根據(jù)鏈碼跟蹤算法，本文定義8-方向鏈碼的交叉點(diǎn)為：在目標(biāo)點(diǎn)的8個(gè)鄰域內(nèi)像素值為1的點(diǎn)大于等于3，且其中至少有3點(diǎn)兩兩之間夾角大于或等于90°，則該目標(biāo)點(diǎn)為交叉點(diǎn).如圖5和圖6所示，字母“A”中有3個(gè)交叉點(diǎn)a，b，c；字母“X”中有兩個(gè)交叉點(diǎn)a，b.

圖5 細(xì)化后的字母“A”Fig.5 The letter “A”after thinning

圖6 細(xì)化后的字母“X”Fig.6 The letter “X”after thinning

4 分類器的設(shè)計(jì)

由第2節(jié)鏈碼跟蹤算法得到字母和數(shù)字的邊界鏈碼，根據(jù)第3節(jié)選取的鏈碼特征，本文設(shè)計(jì)一種多級(jí)分類器.首先根據(jù)鏈碼總段數(shù)進(jìn)行第一級(jí)分類，其下各級(jí)分類根據(jù)第一級(jí)分類的結(jié)果，綜合運(yùn)用本文上述鏈碼特征即可將其分開(kāi).分類結(jié)構(gòu)如圖7所示.

圖7 分類結(jié)構(gòu)示意圖Fig.7 Diagram of the classification structure

4.1一段鏈碼

一段鏈碼有字母C，O，I，L，Z，V和數(shù)字0，1，2，5.根據(jù)鏈碼段有無(wú)省略可分為4類：1-1為無(wú)省略，包括C，O，Z和0，2，5；1-2為省略一段鏈碼，只有數(shù)字1；1-3為省略二段鏈碼，包括字母I和L；1-4為省略段數(shù)大于5段，只有字母V.在1-1中，1-1-1為有1個(gè)中間直線段鏈碼，包括字母C，O，Z；1-1-2為有2個(gè)中間直線段鏈碼，包括數(shù)字0，2，5.在1-1-1中字母C的中間直線段鏈碼的方向向上，字母O的中間直線段鏈碼的方向向下，字母Z的中間直線段鏈碼的方向向左.在1-1-2中，數(shù)字0的兩段中間直線段鏈碼方向?yàn)橄蛏虾拖蛳?；?shù)字2的兩段中間直線段鏈碼方向?yàn)橄蜃蠛拖蛴疑希粩?shù)字5的兩段中間直線段鏈碼方向?yàn)橄蜃蠛拖蛳?在1-3中，字母I有1個(gè)中間直線段鏈碼，而字母L有2個(gè)中間直線段鏈碼.

4.2二段鏈碼

二段鏈碼有字母T，U，D，Y，G，Q，S和數(shù)字3，4，6，7，8，9.根據(jù)鏈碼段省略情況分為4類：2-1為省略一段，包括字母T和數(shù)字3，4，6，7；2-2為省略二段，包括字母D、U和數(shù)字9；2-3為省略三段，只有字母Y；2-4為無(wú)省略，包括字母G，Q，S和數(shù)字8.在2-1中根據(jù)中間直線段鏈碼的個(gè)數(shù)分為：2-1-1為0個(gè)，只有數(shù)字3；2-1-2為1個(gè)，包括數(shù)字6和字母T，其中，數(shù)字6為短中間直線段鏈碼，而字母T為長(zhǎng)中間直線段鏈碼；2-1-3為2個(gè)，包括數(shù)字4和7，其中，數(shù)字4的兩段中間直線段鏈碼方向?yàn)橄蛴液拖蛏?，而?shù)字7的兩段中間直線段鏈碼方向?yàn)橄蜃蠛拖蛏?在2-2中根據(jù)直線段鏈碼個(gè)數(shù)分為：2-2-1為1個(gè)，只有字母U；2-2-2為0個(gè)，包括數(shù)字9和字母D.在2-2-1中，數(shù)字9的中間直線段鏈碼的方向向下，而字母D的中間直線段鏈碼的方向向上.在2-4中根據(jù)中間直線段鏈碼個(gè)數(shù)分為：2-4-1為1個(gè)，包括字母G、Q和數(shù)字8；2-4-2為0個(gè)，只有字母S.在2-4-1中，數(shù)字8的中間直線段鏈碼方向向上，字母Q的第1段子鏈碼存在方向向下的中間直線段鏈碼，而字母G的第2段子鏈碼存在方向向下的中間直線段鏈碼.

4.3三段鏈碼

三段鏈碼有字母A，B，P，R，E，N，X，H，J，W.根據(jù)鏈碼段省略情況分為5類：3-1為省略一段，包括字母P，R，B；3-2為省略二段，包括字母E，N，X和A；3-3為省略四段，只有字母H；3-4無(wú)省略，只有字母J；3-5為省略段數(shù)大于5，只有字母W.在3-1中根據(jù)直線段鏈碼個(gè)數(shù)分為兩類：3-1-1為0個(gè)，包括字母P和R；3-1-2為1個(gè)，只有字母B.在3-2中根據(jù)直線段鏈碼個(gè)數(shù)分為兩類：3-2-1為1個(gè)，只有字母E；3-2-2為0個(gè)，包括字母N，X，A.在3-2-2中根據(jù)交叉點(diǎn)的個(gè)數(shù)分為：3-2-2-1為2個(gè)，包括字母N和X，其中字母N有中間直線段，字母X沒(méi)有；3-2-2-2為3個(gè)，只有字母A.

4.4四段鏈碼

四段鏈碼有字母F，K，M.根據(jù)有無(wú)直線段鏈碼分為兩類：4-1無(wú)直線段鏈碼，只有字母F；4-2有一個(gè)直線段鏈碼，包括字母K和M，其中，字母K有1個(gè)中間直線段鏈碼，字母M有2個(gè)中間直線段鏈碼.

5 實(shí)驗(yàn)

實(shí)驗(yàn)對(duì)象為畫(huà)圖板生成的字母和數(shù)字圖片，根據(jù)本文設(shè)計(jì)的多級(jí)分類器，算法由matlab軟件實(shí)現(xiàn).圖像預(yù)處理及鏈碼跟蹤輪廓的實(shí)現(xiàn)過(guò)程如下：

(1)首先對(duì)圖片進(jìn)行預(yù)處理.在matlab中調(diào)用im2bw函數(shù)實(shí)現(xiàn)圖像的二值化，1表示前景，0表示背景.選用medfilt2函數(shù)實(shí)現(xiàn)中值濾波，在去噪的同時(shí)，能較好地保留邊緣的銳度和圖像的細(xì)節(jié).調(diào)用bwmorph函數(shù)對(duì)圖像進(jìn)行細(xì)化處理，將目標(biāo)細(xì)化為單像素寬度，能更好地顯示其拓?fù)湫再|(zhì)[11].最后將圖像統(tǒng)一歸一化為32×32.

(2)按從左到右、從上到下的順序掃描得到輪廓跟蹤的起始點(diǎn)，置鏈碼開(kāi)始標(biāo)識(shí)符“<”，且以該起始點(diǎn)為當(dāng)前點(diǎn)，轉(zhuǎn)向(3)；若掃描不到輪廓點(diǎn)，則轉(zhuǎn)向(5).

(3)按8-方向鏈碼順序掃描當(dāng)前點(diǎn)的相鄰8鄰域，只要一遇到輪廓點(diǎn)，立即停止跟蹤輪廓且記錄下所跟蹤到的方向鏈碼值，轉(zhuǎn)向(4)；若沒(méi)有遇到輪廓點(diǎn)，則置鏈碼跟蹤結(jié)束標(biāo)識(shí)符“>”，轉(zhuǎn)向(2)重新掃描.

(4)用背景色(即0)填充當(dāng)前點(diǎn)，再將跟蹤到的新輪廓點(diǎn)置為當(dāng)前點(diǎn)，轉(zhuǎn)向(3).

(5)所有輪廓跟蹤結(jié)束.

利用以上鏈碼跟蹤算法獲得字符的原始鏈碼，再對(duì)原始鏈碼進(jìn)行簡(jiǎn)化處理，然后提取鏈碼特征，最后由分類器得到識(shí)別結(jié)果.部分實(shí)驗(yàn)結(jié)果見(jiàn)表1.

其中，字母U的原始鏈碼為“<0453><2222222222222><45444332222222222222210><3>”，將小于5的子鏈碼省略，得到簡(jiǎn)化鏈碼為“<2222222222222><45444332222222222222210>”.由第3節(jié)可知，該鏈碼體現(xiàn)的鏈碼特征有：1)鏈碼總段數(shù)為2；2)省略了2段子鏈碼<0453>和<3>；3)1個(gè)直線段鏈碼<2222222222222>；4)有方向向上的中間直線段鏈碼<45444332222222222222210>.由第4節(jié)設(shè)計(jì)的分類器，得出識(shí)別結(jié)果為字母U.

輪廓特征是區(qū)別字母與數(shù)字的重要特征，利用邊界鏈碼可有效地表示字符的形狀輪廓特征.本文基于邊界鏈碼實(shí)現(xiàn)字母與數(shù)字的混合識(shí)別，特征提取方法簡(jiǎn)單、存儲(chǔ)量小、計(jì)算速度快.針對(duì)字符鏈碼的差異，提取了5種鏈碼分類特征，設(shè)計(jì)了多級(jí)分類器，獲得了有效而準(zhǔn)確的分類器品質(zhì).本文研究的鏈碼特征提取方法直觀且易于實(shí)現(xiàn)，可廣泛應(yīng)用于車牌、圖書(shū)索號(hào)等字母與數(shù)字混合識(shí)別領(lǐng)域.

表1 部分實(shí)驗(yàn)結(jié)果

[1] 唐敏,姜靈敏,陽(yáng)愛(ài)民. 一種基于區(qū)域模糊特征的圖像檢索方法[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版，2007,39(2):122-126.

[2] 唐振軍，張顯全.圖像邊界的鏈碼表示研究[J].微計(jì)算機(jī)信息，2005,11(3):105-107.

[3] 楊慶雄.基于神經(jīng)網(wǎng)絡(luò)的字符識(shí)別研究[J].信息技術(shù)，2005,29(4):92-96.

[4] 李旻，吳煒，楊曉敏,等.基于獨(dú)立分量分析的車牌字符識(shí)別[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版,2006，43(6):1259-1263.

[5] 吳煒，余艷梅,劉大宇，等.一種基于Hausdorff距離的車牌字符識(shí)別算法[J].計(jì)算機(jī)應(yīng)用研究,2004，21(2):258-260.

[6] 陳天華.數(shù)字圖像處理[M]. 北京：清華大學(xué)出版社，2007:67-69.

[7] 任民宏.輪廓跟蹤算法的改進(jìn)在字符識(shí)別技術(shù)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2006,26(10):2378-2382.

[8] Sun Yongxiang, Zhang Chengming.Shape feature extraction of fruit image based on chain code[C].Proceedings of the 2007 International Conference on Wavelet Analysis and Pattern Pecognition, San Francisco, 2007: 2-4.

[9] 王萍，劉恒，狄光敏.基于簡(jiǎn)約碼特性樹(shù)的字母和數(shù)字識(shí)別[J].天津大學(xué)學(xué)報(bào)：自然科學(xué)版，2008,41(6):667-672.

[10] 張顯全.一種用邊界細(xì)化漢字的方法[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2001,19(1):55-57.

[11] 張汗靈.MATLAB在圖像處理中的應(yīng)用[M].北京：清華大學(xué)出版社，2008:83-85.

ApplicationofBoundaryChainCodetoLettersandNumbersMixedRecognition

HE Xiao-juan, LUO Yong

(SchoolofElectricalEngineering,ZhengzhouUniversity,Zhengzhou450001，China)

The technology of the chain code was used to recognite letters and numbers,with a chain code to keep track of their contours and extract their shape features.Using the differences between their chain code,a multi-stage classifier was designed.And a good quality of the classifier was obtained.This method was simple and effective,and the storage capacity was small.It also provided an effective method to the license plate and call number recognition.

boundary chain code; contour tracking; recognition

TP 391.4

A

1671-6841(2011)03-0103-05

2010-03-02

河南省自然科學(xué)基金資助項(xiàng)目,編號(hào)2009B510015.

和小娟(1984-),女,碩士研究生,主要從事圖像處理與模式識(shí)別研究,E-mail:hexiaojuan456@163.com;通迅作者：羅勇(1977-),男,副教授,主要從事模式識(shí)別與圖像處理、檢測(cè)技術(shù)和智能儀表、單片機(jī)與嵌入式系統(tǒng)研究,E-mail:luoyong@zzu.edu.cn.