边界链码在字母与数字混合识别中的应用

和小娟，罗 勇

(郑州大学 电气工程学院 河南 郑州 450001)

边界链码在字母与数字混合识别中的应用

和小娟，罗 勇

(郑州大学 电气工程学院 河南 郑州 450001)

将链码技术应用到字母与数字的混合识别中，用链码跟踪其轮廓，提取形状特征.针对链码间的差异性，设计了多级分类器，获得了良好的分类器品质.方法简单有效、存储量小，具有实用性，可嵌入到车牌、图书索号识别等应用领域.

边界链码； 轮廓跟踪； 识别

0 引言

图像边缘作为图像的基本特征，是判别物体的重要依据[1].边缘中包含物体有价值的边界信息，可用于图像分析、滤波及目标识别.一系列边界点构成物体轮廓，轮廓在一定程度上可表示物体的形状.目前，对图像边界表示研究较多，如链码、Fourier级数、有向图等.由于链码能以较少的数据存储较多的信息，可实现图像数据的有效压缩，已成为图像边界表示广泛应用的方法之一[2].字母与数字识别属于图像识别范畴，广泛应用于车牌识别、图书索书号识别等领域.目前字符识别方法较多，如人工神经网络[3]、独立分量分析[4]、Hausdorff距离[5]等.人工神经网络识别的速度和准确性易受网络权重初值设置的影响.独立分量分析和Hausdorff距离分析的特征提取方法相对复杂.本文将链码技术应用到字母与数字识别中，跟踪字符轮廓，提取其链码特征，并设计多级分类器进行字符识别.该方法简单有效，具有良好的识别效果.

1 边界链码

链码是对区域边界点的一种编码表示方法.某一点的链码是指它相对于前一个轮廓点的方向编码.常用的有4-方向和8-方向链码.如图1和图2所示.4-方向链码是用中心像素指向其4个相邻点的方向进行定义，4个相邻方向用0～3表示，链码值加1，其所指方向按逆时针方向旋转90°，8-方向链码与此类似.

由链码构成轮廓时，先确定起点绝对坐标，其余点用接续方向来代表偏移量.对于每一点只需一个方向数就可代替两个坐标值，因此采用链码可有效减少边界表示的数据量[6].如图3所示的边界，假设起始点a的坐标为(4，0)，采用4-方向链码表示区域边界，链码的扫描顺序为abcdefgba，则以a(4，0)为起点的4-方向边界链码为：<212122330000>，(其中“<”和“>”分别是链码段起始、结束标志，中间数值表示链码值).采用8-方向链码表示区域边界，链码的扫描顺序为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

图像目标识别时，需跟踪目标物体轮廓.简单的轮廓跟踪过程为：先逐行逐列扫描图像找到第一个像素值为1的点(目标点)作为起始点S，假设当前轮廓点为P，则在P的8邻域中寻找目标点T，如果T的4邻域点的像素值不全为1，则T是轮廓点，否则不是轮廓点；如果T和S重合，则轮廓跟踪结束，否则继续寻找下一点.该算法需对每个轮廓点8邻域内所有点的4邻域点进行判别，计算量较大，影响跟踪速度[7].因此，本文采用链码跟踪算法，提高跟踪速度.

链码跟踪算法首先按行列扫描得到起始点，并将其作为当前点，然后按逆时针方向扫描其8邻域，一旦扫描到像素值为1的点则将当前点像素值置为0，同时将扫描到的点置为当前点，按同样规则继续扫描直到一条链码结束.接着重新扫描行列获得起始点，再按同样规则直到所有目标点跟踪结束，则整个轮廓跟踪结束.轮廓跟踪沿链码方向进行，下一跟踪点的取得依赖于上一轮廓点，从而避免了对所有像素点进行扫描，提高了轮廓跟踪的效率[8].链码跟踪算法流程如图4所示.

3 链码特征的提取

对链码跟踪算法获得的字母与数字链码进行实验与统计分析，可提取其形状特征.本文选择的链码特征包括：1)链码总段数；2)链码段有无省略； 3)直线段链码个数[9]；4)中间直线段链码个数、方向及长度[8]；5)交叉点个数等.

3.1链码总段数

该特征指简化后链码的子链码个数.经过实验分析总结，26个字母及10个数字的链码总段数可分为4类：一段(包括字母C，O，I，L，Z，V和数字0，1，2，5)，二段(包括字母D，Q，S，T，U，Y和数字3，4，6，7，8，9)，三段(包括A，B，E，H，J，N，P，R，X，W)，四段(包括F，K，M).

3.2链码段有无省略

由于印刷体端点有短 “枝节”，以及在图像预处理部分细化时会产生无关的短的“毛刺”或寄生成分[10]，因此链码跟踪时会产生比较短的链码段，而这并不影响目标识别.因此本文把小于5的子链码去除.如字母“A”的原始链码为“<0433223312322233221><44><4443212221><432221><4>”，原始链码有5段，去除小于5的两段子链码，得到简化链码为“<0433223312322233221><4443212221><432221>”.

3.3直线段链码

若子链码的链码值都相同即为直线段链码.如字母“U”的原始链码为“<0453><2222222222222><45444332222222222222210><3>”，其中，子链码“<2222222222222>”为直线段链码.

3.4中间直线段链码

链码段中连续超过5个且相同的链码值，本文称之为中间直线段链码.不同的链码值其方向也不同(数字0～7分别代表向右、右上、上、左上、左、左下、下、右下).如字母“C”的原始链码为“<05554444332322222222211110007776>”，其中有连续超过5个链码值为2的链码段，方向向上.规定连续超过5个但不超过10个的相同链码值的链码段为短中间直线链码段，而连续超过10个的相同链码值的链码段为长中间直线链码段.

3.5交叉点

根据链码跟踪算法，本文定义8-方向链码的交叉点为：在目标点的8个邻域内像素值为1的点大于等于3，且其中至少有3点两两之间夹角大于或等于90°，则该目标点为交叉点.如图5和图6所示，字母“A”中有3个交叉点a，b，c；字母“X”中有两个交叉点a，b.

图5 细化后的字母“A”Fig.5 The letter “A”after thinning

图6 细化后的字母“X”Fig.6 The letter “X”after thinning

4 分类器的设计

由第2节链码跟踪算法得到字母和数字的边界链码，根据第3节选取的链码特征，本文设计一种多级分类器.首先根据链码总段数进行第一级分类，其下各级分类根据第一级分类的结果，综合运用本文上述链码特征即可将其分开.分类结构如图7所示.

图7 分类结构示意图Fig.7 Diagram of the classification structure

4.1一段链码

一段链码有字母C，O，I，L，Z，V和数字0，1，2，5.根据链码段有无省略可分为4类：1-1为无省略，包括C，O，Z和0，2，5；1-2为省略一段链码，只有数字1；1-3为省略二段链码，包括字母I和L；1-4为省略段数大于5段，只有字母V.在1-1中，1-1-1为有1个中间直线段链码，包括字母C，O，Z；1-1-2为有2个中间直线段链码，包括数字0，2，5.在1-1-1中字母C的中间直线段链码的方向向上，字母O的中间直线段链码的方向向下，字母Z的中间直线段链码的方向向左.在1-1-2中，数字0的两段中间直线段链码方向为向上和向下；数字2的两段中间直线段链码方向为向左和向右上；数字5的两段中间直线段链码方向为向左和向下.在1-3中，字母I有1个中间直线段链码，而字母L有2个中间直线段链码.

4.2二段链码

二段链码有字母T，U，D，Y，G，Q，S和数字3，4，6，7，8，9.根据链码段省略情况分为4类：2-1为省略一段，包括字母T和数字3，4，6，7；2-2为省略二段，包括字母D、U和数字9；2-3为省略三段，只有字母Y；2-4为无省略，包括字母G，Q，S和数字8.在2-1中根据中间直线段链码的个数分为：2-1-1为0个，只有数字3；2-1-2为1个，包括数字6和字母T，其中，数字6为短中间直线段链码，而字母T为长中间直线段链码；2-1-3为2个，包括数字4和7，其中，数字4的两段中间直线段链码方向为向右和向上，而数字7的两段中间直线段链码方向为向左和向上.在2-2中根据直线段链码个数分为：2-2-1为1个，只有字母U；2-2-2为0个，包括数字9和字母D.在2-2-1中，数字9的中间直线段链码的方向向下，而字母D的中间直线段链码的方向向上.在2-4中根据中间直线段链码个数分为：2-4-1为1个，包括字母G、Q和数字8；2-4-2为0个，只有字母S.在2-4-1中，数字8的中间直线段链码方向向上，字母Q的第1段子链码存在方向向下的中间直线段链码，而字母G的第2段子链码存在方向向下的中间直线段链码.

4.3三段链码

三段链码有字母A，B，P，R，E，N，X，H，J，W.根据链码段省略情况分为5类：3-1为省略一段，包括字母P，R，B；3-2为省略二段，包括字母E，N，X和A；3-3为省略四段，只有字母H；3-4无省略，只有字母J；3-5为省略段数大于5，只有字母W.在3-1中根据直线段链码个数分为两类：3-1-1为0个，包括字母P和R；3-1-2为1个，只有字母B.在3-2中根据直线段链码个数分为两类：3-2-1为1个，只有字母E；3-2-2为0个，包括字母N，X，A.在3-2-2中根据交叉点的个数分为：3-2-2-1为2个，包括字母N和X，其中字母N有中间直线段，字母X没有；3-2-2-2为3个，只有字母A.

4.4四段链码

四段链码有字母F，K，M.根据有无直线段链码分为两类：4-1无直线段链码，只有字母F；4-2有一个直线段链码，包括字母K和M，其中，字母K有1个中间直线段链码，字母M有2个中间直线段链码.

5 实验

实验对象为画图板生成的字母和数字图片，根据本文设计的多级分类器，算法由matlab软件实现.图像预处理及链码跟踪轮廓的实现过程如下：

(1)首先对图片进行预处理.在matlab中调用im2bw函数实现图像的二值化，1表示前景，0表示背景.选用medfilt2函数实现中值滤波，在去噪的同时，能较好地保留边缘的锐度和图像的细节.调用bwmorph函数对图像进行细化处理，将目标细化为单像素宽度，能更好地显示其拓扑性质[11].最后将图像统一归一化为32×32.

(2)按从左到右、从上到下的顺序扫描得到轮廓跟踪的起始点，置链码开始标识符“<”，且以该起始点为当前点，转向(3)；若扫描不到轮廓点，则转向(5).

(3)按8-方向链码顺序扫描当前点的相邻8邻域，只要一遇到轮廓点，立即停止跟踪轮廓且记录下所跟踪到的方向链码值，转向(4)；若没有遇到轮廓点，则置链码跟踪结束标识符“>”，转向(2)重新扫描.

(4)用背景色(即0)填充当前点，再将跟踪到的新轮廓点置为当前点，转向(3).

(5)所有轮廓跟踪结束.

利用以上链码跟踪算法获得字符的原始链码，再对原始链码进行简化处理，然后提取链码特征，最后由分类器得到识别结果.部分实验结果见表1.

其中，字母U的原始链码为“<0453><2222222222222><45444332222222222222210><3>”，将小于5的子链码省略，得到简化链码为“<2222222222222><45444332222222222222210>”.由第3节可知，该链码体现的链码特征有：1)链码总段数为2；2)省略了2段子链码<0453>和<3>；3)1个直线段链码<2222222222222>；4)有方向向上的中间直线段链码<45444332222222222222210>.由第4节设计的分类器，得出识别结果为字母U.

轮廓特征是区别字母与数字的重要特征，利用边界链码可有效地表示字符的形状轮廓特征.本文基于边界链码实现字母与数字的混合识别，特征提取方法简单、存储量小、计算速度快.针对字符链码的差异，提取了5种链码分类特征，设计了多级分类器，获得了有效而准确的分类器品质.本文研究的链码特征提取方法直观且易于实现，可广泛应用于车牌、图书索号等字母与数字混合识别领域.

表1 部分实验结果

[1] 唐敏,姜灵敏,阳爱民. 一种基于区域模糊特征的图像检索方法[J].郑州大学学报:理学版，2007,39(2):122-126.

[2] 唐振军，张显全.图像边界的链码表示研究[J].微计算机信息，2005,11(3):105-107.

[3] 杨庆雄.基于神经网络的字符识别研究[J].信息技术，2005,29(4):92-96.

[4] 李旻，吴炜，杨晓敏,等.基于独立分量分析的车牌字符识别[J].四川大学学报:自然科学版,2006，43(6):1259-1263.

[5] 吴炜，余艳梅,刘大宇，等.一种基于Hausdorff距离的车牌字符识别算法[J].计算机应用研究,2004，21(2):258-260.

[6] 陈天华.数字图像处理[M]. 北京：清华大学出版社，2007:67-69.

[7] 任民宏.轮廓跟踪算法的改进在字符识别技术中的应用[J].计算机应用,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] 王萍，刘恒，狄光敏.基于简约码特性树的字母和数字识别[J].天津大学学报：自然科学版，2008,41(6):667-672.

[10] 张显全.一种用边界细化汉字的方法[J].广西师范大学学报：自然科学版，2001,19(1):55-57.

[11] 张汗灵.MATLAB在图像处理中的应用[M].北京：清华大学出版社，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

河南省自然科学基金资助项目,编号2009B510015.

和小娟(1984-),女,硕士研究生,主要从事图像处理与模式识别研究,E-mail:hexiaojuan456@163.com;通迅作者：罗勇(1977-),男,副教授,主要从事模式识别与图像处理、检测技术和智能仪表、单片机与嵌入式系统研究,E-mail:luoyong@zzu.edu.cn.