1. *
基于拟合函数的二值图像矢量化识别算法
彭立勋,皮德常+
(南京航空航天大学信息科学与技术学院,南京,江苏,210016)
摘要 :图像识别是从一幅打印或者手写图像中识别出其中特定的图形。当图形不规则
且复杂时,要求识别函数能较准确的将图形归到正确的分类之中,同时还需要有较高的执
行效率,识别它们将会变得非常复杂。 本文提出了一种基于拟合函数的图形识别方法,通过
将待识别的图形拟合为多个多项式函数来表示,然后与模板库中的样本拟合函数进行对比 ,
分析方差,取出相似度最高的模板作为识别结果。经过实际的测试表明该算法是有效的。
关键字 :模式识别;图形;图像;拟合;多项式
Binary image vectorization recognition algorithm based on
the fitting function
Lixun Peng and Dechang Pi
College of Information Science and Technology, Nanjing University of Aeronautics and Astronautics,
Nanjing, Jiangsu, 210016, China
Abstract: The propose of graphics recognition identifies specific graphics from hand-written or
printed images. Because of requiring recognition function which can make the graphics classified
accurately and high efficiency, it is complicated to recognize irregular and perplexed graphics. In
this paper a graphics recognition method based on fitting function is proposed. The idea is that
using some polynomial denoted recognized graphics, then compared with sample fitting function
in the template, the maximum similarity template was extracted as identification results through
analyzing variance. Experiments show that the algorithm is effective through the real test.
Keywords: Pattern Recognition; graphics; images; fitting; polynomial
1. 引言
现在一般的图形识别算法是基于对待识别图形的点阵分析,对构成图形的线条较复杂
的图形进行识别有很大的局限性,例如对汉字有专门的汉字识别方法,对字母有专门的字
母识别方法,即使用同一类算法思想也是需要不同的程序来实现 [1,2]。尤其将多种类型符号
混在一起时,大部分算法都很难识别出来。如果是手写输入,识别的难度就更大[3,4]。
现有的通用图形识别算法,例如模板匹配算法,一般用训练样本特征的平均值来描述,
分类器根据输入样本特征与各个文字的参照特征的距离进行识别。 由于汉字存在各种各样字
体,手写汉字中还存在各种各样的变形,因此文件的任何特征都存在一个分布空间。 只有把
这些分布考虑进去,才能更精确地进行分类识别,因此只用特征平均值来描述特征是不够
的。贝叶斯分类算法则是采用一种用分段线性函数描述汉字特征的概率密度函数方法,能很
* 本文受国家 863 项目(2007AA01Z404)和 2007 年江苏省高等教育教改立项研究课题(编号 64)资助。
作者简介:+彭立勋,学生。皮德常, 博士, 副教授.
1
2. 好的识别出汉字的特征分布,但是由于特征值的分布通常不是某种简单的统计分布,如果
没有简单的方法描述这些概率密度函数,则表示所有的汉字的各维特征的概率密度函数需
要的存储空间将是实用系统所不能承受的。 并且这两种方法都不能很好的将复杂图形分类,
[5,6]
执行的效率很低 。
本文提出了一种基于对构成图形的线条进行拟合,生成拟合函数的识别算法,对各种
复杂图形转化为多项式函数进行描述,然后通过分析拟合函数系数与模板库的标准函数的
相似度进行识别。 这种识别方法与目前现有识别方法有所不同。据文献查新所知,我们还没
有见到基于这种识别方法的研究报道。 同时此算法还内含了一种二值化图形矢量化的方法。
2. 相关定义
定义 1线段(LS,Line Segment)与线段集(LSS,Line Segment Set):
一段连续的,由若干个点构成,可以被拟合的点序列称为 线段(可以为曲线段或
直线段),由线段组成的序列称为线段集。
定义: LS=((X1,Y1),(X2,Y2),...,(Xi,Yi),...,(Xn,Yn)),n 为点的数量。
LSS=(LS1,LS2,..LSi,...,LSm),m 为线段的数量。
其中: Xi、Yi∈Z,LS∈LSS,i、n、m∈Z+,|Xi-Xi-1|<=1,|Yi-Yi-1|<=1。
定义 2特征点(LC,Line Character points)与特征点集(LCS,Line Character points Set):
对于一条由 n 个点构成的线段 LS,选取其中 m 个点进行拟合,每个被选取的点称
为线段 LS 的特征点,由这 m 个特征点组成的序列称为特征点集。
定义: LC∈LS。
LCS={LC1,LC2,...,LCi,…,LCm},m 为特征点的数量。
其中: LCi∈LS,0≤i≤m≤n。
定义 3最佳拟合函数(BFF,Best- Fitting Function):
利用一条线段 LS 的一个特征点集 LCS 对线段进行拟合得到的 n 阶多项式 Y(X)或
X(Y)称为这条线段的拟合函数,其中最优的拟合函数称为最佳拟合函数。
定义: BFF(X)=An*Xn+An-1*Xn-1+…+A0*X0,Flag 标志位 0。
BFF(Y)=An*Yn+An-1*Yn-1+…+A0*Y0,Flag 标志位 1.
其中: Ai∈R,i、n∈Z+。
定义 4最佳拟合向量(BFV,Best-Fitting Vector):
最佳拟合函的系数 Ai 和 Y(X)型或 X(Y)型的标志位 Flag 组成的向量称为最佳拟合
向量。
定义:BFV=(Flag,An,An-1,…,Ai,…A0)。
其中:Ai∈R,i、n∈Z+。
定义 5笔画(SK,Strokes):
由一些具有类似属性的最佳拟合向量组成的集合称为 笔画,是可识别符号集中的
元素所能被分割的最小单位。
定义:SK={BFV1,BFV2,…,BFVi,…,BFVn},n 是笔画的模板样本数。
其中:i,n∈Z+。
例如:汉字中所有的与 X 轴近似平行的拟合向量构成的集合定义为“横”这个笔画。
2