和小娟，羅 勇

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

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

和小娟，羅 勇

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

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

邊界鏈碼； 輪廓跟蹤； 識別

0 引言

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

1 邊界鏈碼

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

由鏈碼構(gòu)成輪廓時，先確定起點絕對坐標(biāo)，其余點用接續(xù)方向來代表偏移量.對于每一點只需一個方向數(shù)就可代替兩個坐標(biāo)值，因此采用鏈碼可有效減少邊界表示的數(shù)據(jù)量[6].如圖3所示的邊界，假設(shè)起始點a的坐標(biāo)為(4，0)，采用4-方向鏈碼表示區(qū)域邊界，鏈碼的掃描順序為abcdefgba，則以a(4，0)為起點的4-方向邊界鏈碼為：<212122330000>，(其中“<”和“>”分別是鏈碼段起始、結(jié)束標(biāo)志，中間數(shù)值表示鏈碼值).采用8-方向鏈碼表示區(qū)域邊界，鏈碼的掃描順序為acefgba，則以a(4，0)為起點的8-方向邊界鏈碼為：<3344660000>.可知4-方向鏈碼表示的圖像邊界與實際邊界存在差異，因此本文采用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)識別時，需跟蹤目標(biāo)物體輪廓.簡單的輪廓跟蹤過程為：先逐行逐列掃描圖像找到第一個像素值為1的點(目標(biāo)點)作為起始點S，假設(shè)當(dāng)前輪廓點為P，則在P的8鄰域中尋找目標(biāo)點T，如果T的4鄰域點的像素值不全為1，則T是輪廓點，否則不是輪廓點；如果T和S重合，則輪廓跟蹤結(jié)束，否則繼續(xù)尋找下一點.該算法需對每個輪廓點8鄰域內(nèi)所有點的4鄰域點進(jìn)行判別，計算量較大，影響跟蹤速度[7].因此，本文采用鏈碼跟蹤算法，提高跟蹤速度.

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

3 鏈碼特征的提取

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

3.1鏈碼總段數(shù)

該特征指簡化后鏈碼的子鏈碼個數(shù).經(jīng)過實驗分析總結(jié)，26個字母及10個數(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鏈碼段有無省略

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

3.3直線段鏈碼

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

3.4中間直線段鏈碼

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

3.5交叉點

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

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

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

4 分類器的設(shè)計

由第2節(jié)鏈碼跟蹤算法得到字母和數(shù)字的邊界鏈碼，根據(jù)第3節(jié)選取的鏈碼特征，本文設(shè)計一種多級分類器.首先根據(jù)鏈碼總段數(shù)進(jìn)行第一級分類，其下各級分類根據(jù)第一級分類的結(jié)果，綜合運用本文上述鏈碼特征即可將其分開.分類結(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ù)鏈碼段有無省略可分為4類：1-1為無省略，包括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個中間直線段鏈碼，包括字母C，O，Z；1-1-2為有2個中間直線段鏈碼，包括數(shù)字0，2，5.在1-1-1中字母C的中間直線段鏈碼的方向向上，字母O的中間直線段鏈碼的方向向下，字母Z的中間直線段鏈碼的方向向左.在1-1-2中，數(shù)字0的兩段中間直線段鏈碼方向為向上和向下；數(shù)字2的兩段中間直線段鏈碼方向為向左和向右上；數(shù)字5的兩段中間直線段鏈碼方向為向左和向下.在1-3中，字母I有1個中間直線段鏈碼，而字母L有2個中間直線段鏈碼.

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為無省略，包括字母G，Q，S和數(shù)字8.在2-1中根據(jù)中間直線段鏈碼的個數(shù)分為：2-1-1為0個，只有數(shù)字3；2-1-2為1個，包括數(shù)字6和字母T，其中，數(shù)字6為短中間直線段鏈碼，而字母T為長中間直線段鏈碼；2-1-3為2個，包括數(shù)字4和7，其中，數(shù)字4的兩段中間直線段鏈碼方向為向右和向上，而數(shù)字7的兩段中間直線段鏈碼方向為向左和向上.在2-2中根據(jù)直線段鏈碼個數(shù)分為：2-2-1為1個，只有字母U；2-2-2為0個，包括數(shù)字9和字母D.在2-2-1中，數(shù)字9的中間直線段鏈碼的方向向下，而字母D的中間直線段鏈碼的方向向上.在2-4中根據(jù)中間直線段鏈碼個數(shù)分為：2-4-1為1個，包括字母G、Q和數(shù)字8；2-4-2為0個，只有字母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無省略，只有字母J；3-5為省略段數(shù)大于5，只有字母W.在3-1中根據(jù)直線段鏈碼個數(shù)分為兩類：3-1-1為0個，包括字母P和R；3-1-2為1個，只有字母B.在3-2中根據(jù)直線段鏈碼個數(shù)分為兩類：3-2-1為1個，只有字母E；3-2-2為0個，包括字母N，X，A.在3-2-2中根據(jù)交叉點的個數(shù)分為：3-2-2-1為2個，包括字母N和X，其中字母N有中間直線段，字母X沒有；3-2-2-2為3個，只有字母A.

4.4四段鏈碼

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

5 實驗

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

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

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

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

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

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

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

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

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

表1 部分實驗結(jié)果

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

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

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

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

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

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

[7] 任民宏.輪廓跟蹤算法的改進(jìn)在字符識別技術(shù)中的應(yīng)用[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] 王萍，劉恒，狄光敏.基于簡約碼特性樹的字母和數(shù)字識別[J].天津大學(xué)學(xué)報：自然科學(xué)版，2008,41(6):667-672.

[10] 張顯全.一種用邊界細(xì)化漢字的方法[J].廣西師范大學(xué)學(xué)報：自然科學(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é)基金資助項目,編號2009B510015.

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