SlideShare a Scribd company logo
1 of 10
Download to read offline
*



            基于拟合函数的二值图像矢量化识别算法
                                             彭立勋,皮德常+
                    (南京航空航天大学信息科学与技术学院,南京,江苏,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
好的识别出汉字的特征分布,但是由于特征值的分布通常不是某种简单的统计分布,如果
没有简单的方法描述这些概率密度函数,则表示所有的汉字的各维特征的概率密度函数需
要的存储空间将是实用系统所不能承受的。   并且这两种方法都不能很好的将复杂图形分类,
       [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
定义 6笔画集(SKS,Strokes Set):
     由可识别符号集中所有笔画所构成的集合,称为笔画集。
   定义:SKS={SK1,SK2,…,SKi,…,SKn},n 是笔画的数量。
   其中:i,n∈Z+。
   例如:汉字由“横”“竖”“撇”等一系列基本笔画的集合构成。

  定义 7符号向量(SV,Symbol Vector):
    由 n 个笔画元素构成的可以表示一个待识别或可识别符号的向量称为符号向量。    必
要时可包含一个图像元素记录符号的图像信息以便更精确地识别。
  定义:SV=(SK1,SK2,…,Ski,…,SKn),n 是构成这个符号的笔画数。
  其中:i,n∈Z+。
  例如:汉字“十”,由一个汉字笔画集中的“横”笔画和一个“竖”笔画组成,因而
“十”这个符号由 (横,竖)这个向量构成。

   定义 8符号集(SVS,Symbol Vector Set):
     由所有可识别符号向量构成的集合称为符号集。
   定义:SVS={SV1,SV2,…,SVi,…,SVn},n 是可识别符号向量的数量。
   其中:i,n∈Z+。

   定义 9知识库(KB,Knowledge Base):
     由笔画集模板和符号集模板所组成的模板库称为知识库。
   定义:KB=<SKS,SVS>

   定义 10相似度(Smlt,Similarity):
     待识别样本与知识库中符号集模板的相似程度称为相似度。


3. 数据结构组织
typedef struct
{
     int x,y;
}Point_Type; //点的类型定义
typedef queue<Point_Type> Queue_Type; //队列
typedef bool*           Cov_Type;   //覆盖表的类型定义
typedef bool                Flag_Type; //拟合类型标志位的类型定义
typedef vector<Point_Type> LS_Type;    //线段的类型定义
typedef vector<LS_Type> LSS_Type;      //线段集的类型定义
typedef Point_Type          LC_Type;   //特征点的类型定义
typedef vector<LC_Type> LCS_Type; //特征点集的类型定义
typedef struct
{
     Flag_Type     Flag;    //线段是 Y(X)型-0 还是 X(Y)型-1 的标记
     vector<double>A;       //线段的拟合函数系数向量


                                                           3
long           Length; //线段的长度,可选
     Point_Type Start;      //线段的起点,可选
     LS_Type        LS;     //线段的点集,可选
     LCS_Type       LCS;    //线段的特征点集,可选
}BFV_Type; //最佳拟合向量的类型定义
typedef struct
{
     set<BFV_Type> BFVS;           //构成笔画的最佳拟合向量
     int                 Num;      //笔画的编号
     string              Name;     //笔画的名称
} SK_Type;
typedef set<SK_Type>        SKS_Type; //笔画集的类型定义
typedef struct
{
     vector<SK_Type> SKV;//构成符号向量的笔画向量集
     bool       Is_Order    //笔画是否有序
     int        Num;        //符号的编号
     string     Name;       //符号的名称
     Bitmap Pic;            //符号的图像,可选
}SV_Type; //符号向量
typedef set<SV> SVS_Type; //符号集的类型定义
typedef struct{
     SKS_Type       SKS;    //知识库的笔画集模板库
     SVS_Type       SVS;    //知识库的符号集模板库
}KB_Type; //知识库的类型定义



4. 相关处理方法
  处理 1干扰处理方法:
  A. 二值化处理
  本算法只能处理二值化的图像,所以待识别图形只能是二值化的。 图像的二值化处理算
法已经非常成熟,本文不再赘述。
  B. 笔迹提取
  当线条粗度不为 1 像素时,那么就必须提取样本的笔迹(骨干),再用本文的算法进
行识别。关于笔迹提取的算法已经较为成熟,不再赘述。
  C. 线条消抖
  因为由于某些原因可能导致获取到的线段存在抖动,例如硬件设备的延迟、 开发环境自
身缺陷等等,都可能会导致线段拆分把抖动的部分拆分成一条线段。
  本文给出一种的消抖方法:在笔迹中随机抽取一定密度的点,用直线连接最近的并且
距离不超过一个阈值的相邻点,一般情况下密度和阈值设置合理新得到的图像可以有效的
消除相当一部分抖动,对可获取点输入顺序的联机输入尤其有效。另外引文[4]中的轮廓矢
量化算法部分也是一种较好的消除抖动的方法。
  D. 断点连接
  当进行离线识别时,可能因为各种原因导致图像不清晰。 因为算法的准确性依赖于线段


                                                   4
的正确拆分,因而图像中的原本是一条线的部分出现了断点可以导致识别准确性的大幅下
降。
   相关处理方法有不少文章予以了讨论,本文给出一种断点连接方法:类似线条消抖的
处理方法,在笔迹中随机抽取一定密度的点,用直线连接最近的并且距离不超过一个阈值
的相邻点,一般情况下密度和阈值设置合理新得到的图像中可以消除图像不清晰带来的断
点。

  处理 2线段拆分的处理方法
  A. 联机识别:
  (1) 初始化两个覆盖表 CovX 和 CovY ,分别用于记录 X 轴和 Y 轴的被覆盖情况,并
      将所有项置为 False(表示都未被覆盖)。
  (2) 建立两个空队列 QueueX 和 QueueY,分别用于压入按 Y(X)方式记录和按 X(Y)方
      式记录的点序列。
  (3) 每当获取一个点 (Xi,Yi)时,分别判断在 CovX 和 CovY 的 Xi 位置和 Yi 位置是否为
      False。 CovX 的 Xi 位置为 False,则将(Xi,Yi)压入 QueueX 并在 CovX 的 Xi 位置写
            若
      入 True。 则若 CovY 的 Yi 位置为 False 则将(Xi,Yi)压入 QueueY 并在 CovY 的 Yi 位置
      写入   True。循环这个过程,直到遇到其中一个 Cov 表冲突(即对应位置为 True 的
      Xi 或 Yi 位置已经为 True),则进入(4);当点全部处理完时则进入(5)。
  (4) 如果有一个 Cov 表冲突,则将对应的 Queue 中的元素全部出队列清空并且将 Cov
      表复位;另一个 Cov 表继续进行(3)中的操作,直到也出现冲突,则将对应 Queue
      全部出队列到线段 LS[j],清空 Cov 表。例如,读入 (Xi,Yi),但 CovX 的 Xi 位置为
      True,则将 QueueX 清空,CovX 复位为 False,同时继续按(3)的方法操作 CovY 和
      QueueY , 直 到 CovY 也 出 现 冲 突 , 则 将 QueueX 中 的 元 素 出 队 列 存 储 到
      LS[j],CovY 复位为 False。j=j+1,重新进入(3)。
  (5) 如果是一条线画完,则进入(1)拆分下一条;如果没有点可以获取了,程序段结束。
  B. 离线识别:
  (1) 按照从左向右,从上到下的扫描方法,只要扫描到一个点,就用这个点用类似种
      子填充法的方法扩散,把能连通的线段全部连通,然后用联机识别的方法生成
      LS,转(2)。
  (2) 每取走一条线段,判断这条线段是否与其他线段交叉,如果不交叉则从图中删掉
      这条线段,如有交叉则补上交叉点,转(1),直到图中没有点了为止。

   处理 3特征点选取的处理方法
   线段的起点(X1,Y1)和终点(Xn,Yn)应当被选取,其余的点应当以一定规则从线段的各个
部分取,例如每隔(n+1) div m 个点取一个特征点,应保证特征点能较好的描述原线段的轮
廓。

   处理 4最佳拟合函数的处理方法
   A. 最佳拟合函数中阶数 n 的取值方法:
   n 从 1 开始拟合,求出 R2(拟合相似度),每当 n+1 可以使 R2 增加一个阈值 α,例如
α=5%,则取 n+1 为当前的 n,再次进行判断,直到 n+1 阶拟合不能使 R2 增加 α 为止。
   B. 最佳拟合函数中系数 Ai 的取值方法:
   对于系数 Ai,如果 Ai 的绝对值小于一个阈值 β,例如 β=1E-3,那么测试去掉 Ai*Xi 项
后,R2 会不会减小一个阈值 γ,例如 γ=5%,如果不会减小 γ 那么多,就去掉 Ai*Xi 项(把


                                                                     5
Ai 赋值为 0)。即用尽可能低阶尽可能少的项的表达式表示出尽可能高的拟合度。
     例如,图 1 中的线段,取如下一组特征点,阈值 α=5% : LCS={(0,0),(1,1),(2,3),(3,6),
(4,10), (5,15),(6,20),(7,28),(8,34),(9,45),(10,55),(11,66),(12,79),(13,90),(14,104)}




                   图 1. 红色为线段,蓝色为一阶拟合,绿色为二阶拟合

  当 n=1 时,进行一阶拟合得拟合函数为 Y1=7.439*X-22.58,R2=0.936。
  当 n=2 时,进行二阶拟合得拟合函数为 Y2=0.504*X2-0.626*X+0.272,R2=0.999。
  可见,当 n 由 1 增加到 2 时,R2 增加了(0.999-0.936)/0.936=6.7%,大于阈值 5%,那么
当前最优拟合函数为 Y2=0.504*X2-0.626*X+0.272。




           图 2. 红色为线段,蓝色为一阶拟合,绿色为二阶拟合,黑色为三阶拟合

   当 n=3 时,进行三阶拟合得拟合函数为 Y3=8E-05*X3+0.502*X2+0.252,R2=0.999。
   可见当 n 由 2 增加为 3 时,R2 几乎没有增加,小于阈值 5%,那么最优拟合函数则确定
为 Y2=0.504*X2-0.626*X+0.272。

    处理 5最佳拟合向量的处理方法


                                                                                   6
当有需要时,例如长度不同也要识别为不同的图形的时候,或者线段的长度在全局所
占的比例不同会影响识别结果时,可以在拟合向量中增加一个长度元素,记录下线段长度。
当算法仅作为一个图像矢量化算法时,还可以再加上一个起点元素,记录线段的起点。                由这
些元素就可以通过最佳拟合向量还原图形。
  例如,图 2 中的最佳拟合函数 Y2=0.504*X2-0.626*X+0.272 的拟合向量不考虑可选部分
是一个 3+1 维向量 BFV=(0,0.504,0.626,0.272)。

  处理 6笔画拆分处理方法
  对可识别符号集的笔画拆分,需要以程序处理方便容易辨别为原则,而不是一定按照
平时某种习惯的处理。
  例如,对“马”这个字,汉字笔画是“┐,ㄅ,ー”,但是为了方便处理,应该把“
┐”拆为“横”“竖”两笔,“ㄅ”拆为“竖”“横”“竖”,“提”这一部分可以忽略 ;
于是方便程序处理的拆分方案是“横”“竖”“竖”“横”“竖”“横”,假设“横”的
标记是 1,“竖”的标记是 2,则生成的笔画序列是(1,2,2,1,2,1)。

  处理 7相似度的处理方法
  首先需要根据图形拆分出的各个最佳拟合向量,在知识库的笔画集里查找最匹配的笔
画,生成符号向量。
  然后利用符号向量在知识库的符号集里查找最匹配的符号,如果笔画有序的则查找笔
画和顺序都匹配,如果无序则查找笔画的数量和类型不考虑顺序能匹配。
  如果既不能找到笔画数相同的也不能找到所用笔画完全相同的,则用最接近匹配原则,
找最接近的符号。 对于笔画有序的字符向量,则取各个位按顺序能匹配到正确笔画数量最多
的字符;如果笔画无序的,则取所有笔画中能匹配到所用笔画最多的字符。 然后根据需要,
可以取出字符向量的图像,用图像进行对比确认结果。


5. 算法描述
5.1.语言描述:
S1: 建立知识库;
S2: 读入样本;
S3: 分析样本
    (1) 从图形中拆分出笔画的图案;
    (2) 将拆分出的笔画图案进行分析归类到笔画集中最匹配的笔画;
    (3) 根据有序无序的情况生成识别的符号序列;
S4: 识别样本
    (1) 根据有序无序情况在知识库找最匹配的若干个模板;
    (2) 提取这若干个模板的图案和样本进行匹配;
    (3) 将图案最匹配的那个样本最为识别结果;
    (4) 根据用户需要决定是否将新样本存为模板;
S5: 输出结果。

5.2. 相关参数描述:
     (1) LSS_Type   LSS;   //线段集类型
     (2) LCS_Type   LCS;   //线段特征点集的序列类型


                                                      7
(3) SVS_Type   SVS;   //符号序列类型
       (4) SV_Type    SV;    //符号向量类型
       (5) KB_Type    KB;    //知识库类型

5.3. 相关操作函数注解:
     bool     CreatKB();           //创建知识库
     bool     LoadKB(KB_Type);     //载入知识库
     bool     StoreKB(SV_Type);    //更新知识库
     Bitmap   ReadSV();            //读入一个待识别样本
     LSS_Type GetLSS(Bitmap);      //拆分线段
     LCS_Type GetLCS(LS_Type);     //生成线段特征点集
     BFV_Type GetBFV(LCS_Type); //根据特征点集拟合多项式生成最佳拟合向量
     bool     AnalysisSV(SV_Type); //分析一个符号向量
     SK_Type  MatchingSK(BFV_Type);     //用最佳符号向量匹配笔画
     SVS_Type MatchingTP(SV_Type);      //用符号向量匹配模板
     SVS_Type MatchingSKV(SV_Type.SKV); //按符号向量的笔画向量匹配
     SVS_Type MatchingPIC(SV_Type.Pic, SVS_Type); //按符号图像的匹配

5.4.执行过程:
S1. KB = CreatKB()或 LoadKB(KB); //建立知识库或载入知识库
S2. SV.Pic = ReadSV();
S3. AnalysisSV (SV)         //分析样本
    Begin
        LSS = GetLSS(SV.Pic); //将图像拆分成笔画集
        For i: = 1 To LSS.size() Do
        Begin
             //生成特征点集合
             LCS = GetLCS(LSS[i]);
             //生成最佳拟合向量写入符号向量
             SV.SKV[i].BFV.add(GetBFV(LCS));
             //用拟合向量匹配笔画写入符号向量
             SV.SKV[i] = MatchingSK(SV.SKV[i].BFV);
        End
        return SUCCESS;
     End
S4. SVS = MatchingTP(SV);        //匹配模板,SVS[1]为最可能的识别结果
    Begin
        //按向量匹配得若干个符号向量
        SVS = MatchingSV(SV.SKV);
        //如果需要,比较样本的图像和每个可能的符号的图像进行匹配
        SVS = MatchingPIC(SV.Pic);
        If(用户需要更新知识库)
        Then
             StoreKB(SV);


                                                               8
return SVS;
    End
S5. Write(SVS[0]);    //输出最匹配的结果

6. 算法实现
    我们在 PC 上实现了上述算法,并且可根据实际情况对参数做出修改来适应具体情况,
执行效率可控性强,由于最终是对字串进行匹配,因而可以通过添加索引等方式提高效率。
适用范围广,无论是手写或打印体,只要根据实际情况设置参数和处理方式,就可以适应
具体情况。
    算法可以进行相应的改进 ,如使它能够处理非正向输入的符号,例如汉字,输入时不是
正向写的,有一些倾斜,直接拟合然后跟知识库对比是很可能会出错的。    可以采用对拟合函
数多项式进行坐标旋转,用函数的方法,尝试下旋转一定角度后进行识别,如果匹配率大
大增加,则说明旋转是有效地。    本算法可处理很多特殊的符号,不限于数字、字母、汉字等。
图 3 和图 4 分别给出了识别手写汉字“嚷”和五线谱低音符的运行效果。




                    图 3. 联机识别手写运行效果
      (左上图:手写样本,右上图:特征点采集,左下图:消抖处理,右下图:线段拆分处理)




                                                 9
(图 4. 联机识别手写五线谱低音符运行效果)
(左上图:手写样本,右上图:特征点采集,左下图:消抖处理,右下图:线段拆分处理)



7. 结论
  本文提出一种基于拟合函数的图形识别算法,并通过识别手写汉字和音乐符号来验证
了该算法的有效性,通过将图形拟合成多个多项式,与模板库中的样本进行比较分析提取
出相似度最高的模板作为识别的结果。按本文所采用的识别方法要求手写的字符是标准的方
向,对于非正向输入以及向量表示差异不大的符号进行识别时有误差,因此该系统需要进
一步的提高,使之实用性更广。

参考文献
[1] Pu Y, Shi Z1 A natural learning algorithm based on Hough transform for text lines extraction
    in handwritten documents [C] Proceedings of the 6th International Workshop on Frontiers in
    Handwriting Recognition , Taejon , 1998 : 637 - 646
[2] 高学,金连文,尹俊.一种基于笔画密度的弹性网格特征提取方法[J].模式识别与人工智能,
    2002,15(3):351-354.
[3] 蔺 志 青 , 郭 军 . 贝 叶 斯 分 类 器 在 手 写 汉 字 识 别 中 的 应 用 [J]. 电 子 学 报 , 2002, 30(12):
    1804-1807
[4] 沈立,张晨曦.黑白图像的矢量化[J].计算机辅助设计与图形学学报.2000,12(3): 170-173
[5] 张力 , 点阵汉字转换成矢量汉字的笔迹定向跟踪法 [J]. 计算机辅助设计与图形学学报 .
    1990,2(1): 31-33
[6] 敖翔,戴国忠,王宏安.基于感知的多方向在线手写笔迹文本行提取[J]. 计算机辅助设计与
    图形学学报. 2007, 19(1): 14-19




                                                                                             10

More Related Content

Viewers also liked

2014 Social Media Forecasts From The Experts
2014 Social Media Forecasts From The Experts2014 Social Media Forecasts From The Experts
2014 Social Media Forecasts From The ExpertsHeidi Cohen
 
2014 Content Marketing Forecasts
2014 Content Marketing Forecasts2014 Content Marketing Forecasts
2014 Content Marketing ForecastsHeidi Cohen
 
30 07 13 legionella
30 07 13 legionella30 07 13 legionella
30 07 13 legionellaAlan Bassett
 
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"Randolph Preisinger-Kleine
 
H &amp; S Reform Progress October 11
H &amp; S Reform  Progress October 11H &amp; S Reform  Progress October 11
H &amp; S Reform Progress October 11Alan Bassett
 
How To Be A Twitter Spammer
How To Be A Twitter SpammerHow To Be A Twitter Spammer
How To Be A Twitter SpammerJosh Peters
 
Agency Workers Regulations - Contractors
Agency Workers Regulations - ContractorsAgency Workers Regulations - Contractors
Agency Workers Regulations - ContractorsAlan Bassett
 
Gin WheelFailure - Nasc
Gin WheelFailure - NascGin WheelFailure - Nasc
Gin WheelFailure - NascAlan Bassett
 
Sociala medier - den nya webbplatsen?
Sociala medier - den nya webbplatsen?Sociala medier - den nya webbplatsen?
Sociala medier - den nya webbplatsen?Tobias Franzén
 
تعلم الألمانية بدون معلم Meeeroo
تعلم الألمانية بدون معلم Meeerooتعلم الألمانية بدون معلم Meeeroo
تعلم الألمانية بدون معلم Meeerooramadansadek
 
Bios 275 Cody Kreager
Bios 275 Cody KreagerBios 275 Cody Kreager
Bios 275 Cody Kreagerguest108a43
 
Neomax It Specialist[1]
Neomax It Specialist[1]Neomax It Specialist[1]
Neomax It Specialist[1]lindabond
 
Windows Server 2008 R2 Bdm Overview Rtm 2
Windows Server 2008 R2 Bdm Overview Rtm 2Windows Server 2008 R2 Bdm Overview Rtm 2
Windows Server 2008 R2 Bdm Overview Rtm 2Anh Vu Pham
 
Social media marknadsföring - restaurang- och matbranschen
Social media marknadsföring - restaurang- och matbranschenSocial media marknadsföring - restaurang- och matbranschen
Social media marknadsföring - restaurang- och matbranschenTobias Franzén
 
Social Media for public administrations: opportunities and challenges
Social Media for public administrations: opportunities and challengesSocial Media for public administrations: opportunities and challenges
Social Media for public administrations: opportunities and challengesAlessandro Lovari
 

Viewers also liked (19)

2014 Social Media Forecasts From The Experts
2014 Social Media Forecasts From The Experts2014 Social Media Forecasts From The Experts
2014 Social Media Forecasts From The Experts
 
2014 Content Marketing Forecasts
2014 Content Marketing Forecasts2014 Content Marketing Forecasts
2014 Content Marketing Forecasts
 
30 07 13 legionella
30 07 13 legionella30 07 13 legionella
30 07 13 legionella
 
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"
R3L+ Overview of Grundtvig project "Quality Framework For Learning Regions"
 
Kelly Ruggles
Kelly RugglesKelly Ruggles
Kelly Ruggles
 
H &amp; S Reform Progress October 11
H &amp; S Reform  Progress October 11H &amp; S Reform  Progress October 11
H &amp; S Reform Progress October 11
 
How To Be A Twitter Spammer
How To Be A Twitter SpammerHow To Be A Twitter Spammer
How To Be A Twitter Spammer
 
Agency Workers Regulations - Contractors
Agency Workers Regulations - ContractorsAgency Workers Regulations - Contractors
Agency Workers Regulations - Contractors
 
Gin WheelFailure - Nasc
Gin WheelFailure - NascGin WheelFailure - Nasc
Gin WheelFailure - Nasc
 
EMSS Scheme
EMSS SchemeEMSS Scheme
EMSS Scheme
 
Sociala medier - den nya webbplatsen?
Sociala medier - den nya webbplatsen?Sociala medier - den nya webbplatsen?
Sociala medier - den nya webbplatsen?
 
تعلم الألمانية بدون معلم Meeeroo
تعلم الألمانية بدون معلم Meeerooتعلم الألمانية بدون معلم Meeeroo
تعلم الألمانية بدون معلم Meeeroo
 
Bios 275 Cody Kreager
Bios 275 Cody KreagerBios 275 Cody Kreager
Bios 275 Cody Kreager
 
Neomax It Specialist[1]
Neomax It Specialist[1]Neomax It Specialist[1]
Neomax It Specialist[1]
 
Windows Server 2008 R2 Bdm Overview Rtm 2
Windows Server 2008 R2 Bdm Overview Rtm 2Windows Server 2008 R2 Bdm Overview Rtm 2
Windows Server 2008 R2 Bdm Overview Rtm 2
 
Careers 2 0 balica
Careers 2 0 balicaCareers 2 0 balica
Careers 2 0 balica
 
Development Area
Development AreaDevelopment Area
Development Area
 
Social media marknadsföring - restaurang- och matbranschen
Social media marknadsföring - restaurang- och matbranschenSocial media marknadsföring - restaurang- och matbranschen
Social media marknadsföring - restaurang- och matbranschen
 
Social Media for public administrations: opportunities and challenges
Social Media for public administrations: opportunities and challengesSocial Media for public administrations: opportunities and challenges
Social Media for public administrations: opportunities and challenges
 

Similar to 一种基于拟合函数的图形识别算法

Tdxgongshi
TdxgongshiTdxgongshi
Tdxgongshiairsina
 
Image Stitching Method
Image Stitching MethodImage Stitching Method
Image Stitching Methodwuyanna
 
07 陣列與字串
07 陣列與字串07 陣列與字串
07 陣列與字串shademoon
 
Learning to Rank: An Introduction to LambdaMART
Learning to Rank: An Introduction to LambdaMARTLearning to Rank: An Introduction to LambdaMART
Learning to Rank: An Introduction to LambdaMARTJulian Qian
 
第1章 Matlab操作基础
第1章  Matlab操作基础第1章  Matlab操作基础
第1章 Matlab操作基础eterou
 
从零推导支持向量机(SVM).pdf
从零推导支持向量机(SVM).pdf从零推导支持向量机(SVM).pdf
从零推导支持向量机(SVM).pdfxuepengzhou
 
Cypher 查询语言
Cypher 查询语言Cypher 查询语言
Cypher 查询语言zernel
 
基本遗传算法
 基本遗传算法 基本遗传算法
基本遗传算法sixu05202004
 
机器学习V10baochang svm
机器学习V10baochang svm机器学习V10baochang svm
机器学习V10baochang svmShocky1
 
Opencv Stitching_detailed algorithm introduction
Opencv Stitching_detailed algorithm introductionOpencv Stitching_detailed algorithm introduction
Opencv Stitching_detailed algorithm introductionwilliam zhang
 
C 02 c语言的基本数据类型与表达式
C 02 c语言的基本数据类型与表达式C 02 c语言的基本数据类型与表达式
C 02 c语言的基本数据类型与表达式1138177709
 
系統程式 -- 第 8 章 編譯器
系統程式 -- 第 8 章 編譯器系統程式 -- 第 8 章 編譯器
系統程式 -- 第 8 章 編譯器鍾誠 陳鍾誠
 
建造与理解-用Python实现深度学习框架
建造与理解-用Python实现深度学习框架建造与理解-用Python实现深度学习框架
建造与理解-用Python实现深度学习框架ZhenChen57
 
離散數學 賈蓉生
離散數學 賈蓉生離散數學 賈蓉生
離散數學 賈蓉生Peter Yen
 
ncuma_pylab.pptx
ncuma_pylab.pptxncuma_pylab.pptx
ncuma_pylab.pptxNCU MCL
 
Excel函數進階班(北市政府公訓處) 2
Excel函數進階班(北市政府公訓處) 2Excel函數進階班(北市政府公訓處) 2
Excel函數進階班(北市政府公訓處) 2terry28853669
 

Similar to 一种基于拟合函数的图形识别算法 (20)

浅析Flash特效开发 陈勇
浅析Flash特效开发 陈勇浅析Flash特效开发 陈勇
浅析Flash特效开发 陈勇
 
Tdxgongshi
TdxgongshiTdxgongshi
Tdxgongshi
 
Image Stitching Method
Image Stitching MethodImage Stitching Method
Image Stitching Method
 
07 陣列與字串
07 陣列與字串07 陣列與字串
07 陣列與字串
 
Learning to Rank: An Introduction to LambdaMART
Learning to Rank: An Introduction to LambdaMARTLearning to Rank: An Introduction to LambdaMART
Learning to Rank: An Introduction to LambdaMART
 
第1章 Matlab操作基础
第1章  Matlab操作基础第1章  Matlab操作基础
第1章 Matlab操作基础
 
从零推导支持向量机(SVM).pdf
从零推导支持向量机(SVM).pdf从零推导支持向量机(SVM).pdf
从零推导支持向量机(SVM).pdf
 
Cypher 查询语言
Cypher 查询语言Cypher 查询语言
Cypher 查询语言
 
第三章
第三章第三章
第三章
 
基本遗传算法
 基本遗传算法 基本遗传算法
基本遗传算法
 
机器学习V10baochang svm
机器学习V10baochang svm机器学习V10baochang svm
机器学习V10baochang svm
 
Opencv Stitching_detailed algorithm introduction
Opencv Stitching_detailed algorithm introductionOpencv Stitching_detailed algorithm introduction
Opencv Stitching_detailed algorithm introduction
 
C 02 c语言的基本数据类型与表达式
C 02 c语言的基本数据类型与表达式C 02 c语言的基本数据类型与表达式
C 02 c语言的基本数据类型与表达式
 
系統程式 -- 第 8 章 編譯器
系統程式 -- 第 8 章 編譯器系統程式 -- 第 8 章 編譯器
系統程式 -- 第 8 章 編譯器
 
建造与理解-用Python实现深度学习框架
建造与理解-用Python实现深度学习框架建造与理解-用Python实现深度学习框架
建造与理解-用Python实现深度学习框架
 
12
1212
12
 
離散數學 賈蓉生
離散數學 賈蓉生離散數學 賈蓉生
離散數學 賈蓉生
 
ncuma_pylab.pptx
ncuma_pylab.pptxncuma_pylab.pptx
ncuma_pylab.pptx
 
jasmine入门指南
jasmine入门指南jasmine入门指南
jasmine入门指南
 
Excel函數進階班(北市政府公訓處) 2
Excel函數進階班(北市政府公訓處) 2Excel函數進階班(北市政府公訓處) 2
Excel函數進階班(北市政府公訓處) 2
 

More from Lixun Peng

Double Sync Replication
Double Sync ReplicationDouble Sync Replication
Double Sync ReplicationLixun Peng
 
MySQL新技术探索与实践
MySQL新技术探索与实践MySQL新技术探索与实践
MySQL新技术探索与实践Lixun Peng
 
阿里云RDS for MySQL的若干优化
阿里云RDS for MySQL的若干优化阿里云RDS for MySQL的若干优化
阿里云RDS for MySQL的若干优化Lixun Peng
 
DoubleBinlog方案
DoubleBinlog方案DoubleBinlog方案
DoubleBinlog方案Lixun Peng
 
Alibaba patches in MariaDB
Alibaba patches in MariaDBAlibaba patches in MariaDB
Alibaba patches in MariaDBLixun Peng
 
MySQL优化、新特性和新架构 彭立勋
MySQL优化、新特性和新架构 彭立勋MySQL优化、新特性和新架构 彭立勋
MySQL优化、新特性和新架构 彭立勋Lixun Peng
 
对MySQL应用的一些总结
对MySQL应用的一些总结对MySQL应用的一些总结
对MySQL应用的一些总结Lixun Peng
 
对MySQL的一些改进想法和实现
对MySQL的一些改进想法和实现对MySQL的一些改进想法和实现
对MySQL的一些改进想法和实现Lixun Peng
 
MySQL多机房容灾设计(with Multi-Master)
MySQL多机房容灾设计(with Multi-Master)MySQL多机房容灾设计(with Multi-Master)
MySQL多机房容灾设计(with Multi-Master)Lixun Peng
 
Performance of fractal tree databases
Performance of fractal tree databasesPerformance of fractal tree databases
Performance of fractal tree databasesLixun Peng
 
MySQL新技术探索与实践
MySQL新技术探索与实践MySQL新技术探索与实践
MySQL新技术探索与实践Lixun Peng
 
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复MySQL源码分析.03.InnoDB 物理文件格式与数据恢复
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复Lixun Peng
 
MySQL源码分析.02.Handler API
MySQL源码分析.02.Handler APIMySQL源码分析.02.Handler API
MySQL源码分析.02.Handler APILixun Peng
 
MySQL源码分析.01.代码结构与基本流程
MySQL源码分析.01.代码结构与基本流程MySQL源码分析.01.代码结构与基本流程
MySQL源码分析.01.代码结构与基本流程Lixun Peng
 
内部MySQL培训.3.基本原理
内部MySQL培训.3.基本原理内部MySQL培训.3.基本原理
内部MySQL培训.3.基本原理Lixun Peng
 
内部MySQL培训.2.高级应用
内部MySQL培训.2.高级应用内部MySQL培训.2.高级应用
内部MySQL培训.2.高级应用Lixun Peng
 
内部MySQL培训.1.基础技能
内部MySQL培训.1.基础技能内部MySQL培训.1.基础技能
内部MySQL培训.1.基础技能Lixun Peng
 
对简易几何机械化证明的进一步研究
对简易几何机械化证明的进一步研究对简易几何机械化证明的进一步研究
对简易几何机械化证明的进一步研究Lixun Peng
 
A binary graphics recognition algorithm based on fitting function
A binary graphics recognition algorithm based on fitting functionA binary graphics recognition algorithm based on fitting function
A binary graphics recognition algorithm based on fitting functionLixun Peng
 

More from Lixun Peng (20)

Double Sync Replication
Double Sync ReplicationDouble Sync Replication
Double Sync Replication
 
MySQL新技术探索与实践
MySQL新技术探索与实践MySQL新技术探索与实践
MySQL新技术探索与实践
 
阿里云RDS for MySQL的若干优化
阿里云RDS for MySQL的若干优化阿里云RDS for MySQL的若干优化
阿里云RDS for MySQL的若干优化
 
DoubleBinlog方案
DoubleBinlog方案DoubleBinlog方案
DoubleBinlog方案
 
Alibaba patches in MariaDB
Alibaba patches in MariaDBAlibaba patches in MariaDB
Alibaba patches in MariaDB
 
Time Machine
Time MachineTime Machine
Time Machine
 
MySQL优化、新特性和新架构 彭立勋
MySQL优化、新特性和新架构 彭立勋MySQL优化、新特性和新架构 彭立勋
MySQL优化、新特性和新架构 彭立勋
 
对MySQL应用的一些总结
对MySQL应用的一些总结对MySQL应用的一些总结
对MySQL应用的一些总结
 
对MySQL的一些改进想法和实现
对MySQL的一些改进想法和实现对MySQL的一些改进想法和实现
对MySQL的一些改进想法和实现
 
MySQL多机房容灾设计(with Multi-Master)
MySQL多机房容灾设计(with Multi-Master)MySQL多机房容灾设计(with Multi-Master)
MySQL多机房容灾设计(with Multi-Master)
 
Performance of fractal tree databases
Performance of fractal tree databasesPerformance of fractal tree databases
Performance of fractal tree databases
 
MySQL新技术探索与实践
MySQL新技术探索与实践MySQL新技术探索与实践
MySQL新技术探索与实践
 
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复MySQL源码分析.03.InnoDB 物理文件格式与数据恢复
MySQL源码分析.03.InnoDB 物理文件格式与数据恢复
 
MySQL源码分析.02.Handler API
MySQL源码分析.02.Handler APIMySQL源码分析.02.Handler API
MySQL源码分析.02.Handler API
 
MySQL源码分析.01.代码结构与基本流程
MySQL源码分析.01.代码结构与基本流程MySQL源码分析.01.代码结构与基本流程
MySQL源码分析.01.代码结构与基本流程
 
内部MySQL培训.3.基本原理
内部MySQL培训.3.基本原理内部MySQL培训.3.基本原理
内部MySQL培训.3.基本原理
 
内部MySQL培训.2.高级应用
内部MySQL培训.2.高级应用内部MySQL培训.2.高级应用
内部MySQL培训.2.高级应用
 
内部MySQL培训.1.基础技能
内部MySQL培训.1.基础技能内部MySQL培训.1.基础技能
内部MySQL培训.1.基础技能
 
对简易几何机械化证明的进一步研究
对简易几何机械化证明的进一步研究对简易几何机械化证明的进一步研究
对简易几何机械化证明的进一步研究
 
A binary graphics recognition algorithm based on fitting function
A binary graphics recognition algorithm based on fitting functionA binary graphics recognition algorithm based on fitting function
A binary graphics recognition algorithm based on fitting function
 

Recently uploaded

我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】
我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】
我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】黑客 接单【TG/微信qoqoqdqd】
 
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5ssuser4cf6f01
 
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docxAnonymous0fCNL9T0
 
1111111111一年级音乐教育全年教学计划 2024_25 (1).docx
1111111111一年级音乐教育全年教学计划 2024_25 (1).docx1111111111一年级音乐教育全年教学计划 2024_25 (1).docx
1111111111一年级音乐教育全年教学计划 2024_25 (1).docxLUCHENSOONMoe
 
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docxLUCHENSOONMoe
 
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...黑客 接单【TG/微信qoqoqdqd】
 

Recently uploaded (6)

我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】
我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】
我可是超级厉害的黑客,轻轻一戳就能入侵一个大学网站修改成绩单呢!👍【微信tytyqqww】
 
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5
Rancangan Pengajaran Tahunan Bahasa Cina TAHUN 5
 
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx
6年级美术全年教学计划 Semakan KSSR Pendidikan Seni Visual Tahun 6.docx
 
1111111111一年级音乐教育全年教学计划 2024_25 (1).docx
1111111111一年级音乐教育全年教学计划 2024_25 (1).docx1111111111一年级音乐教育全年教学计划 2024_25 (1).docx
1111111111一年级音乐教育全年教学计划 2024_25 (1).docx
 
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx
二年级音乐教育全年教学计vv二年级音乐教育全年教学计划 2024_25.docx
 
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...
最近找了黑客修改成绩,真的成功了!黑客修改成绩,黑客改成绩,入侵教务系统,国外大学成绩修改 破解教务系统,改GPA分数黑客入侵教务系统黑客修改大学成绩改分...
 

一种基于拟合函数的图形识别算法

  • 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
  • 3. 定义 6笔画集(SKS,Strokes Set): 由可识别符号集中所有笔画所构成的集合,称为笔画集。 定义:SKS={SK1,SK2,…,SKi,…,SKn},n 是笔画的数量。 其中:i,n∈Z+。 例如:汉字由“横”“竖”“撇”等一系列基本笔画的集合构成。 定义 7符号向量(SV,Symbol Vector): 由 n 个笔画元素构成的可以表示一个待识别或可识别符号的向量称为符号向量。 必 要时可包含一个图像元素记录符号的图像信息以便更精确地识别。 定义:SV=(SK1,SK2,…,Ski,…,SKn),n 是构成这个符号的笔画数。 其中:i,n∈Z+。 例如:汉字“十”,由一个汉字笔画集中的“横”笔画和一个“竖”笔画组成,因而 “十”这个符号由 (横,竖)这个向量构成。 定义 8符号集(SVS,Symbol Vector Set): 由所有可识别符号向量构成的集合称为符号集。 定义:SVS={SV1,SV2,…,SVi,…,SVn},n 是可识别符号向量的数量。 其中:i,n∈Z+。 定义 9知识库(KB,Knowledge Base): 由笔画集模板和符号集模板所组成的模板库称为知识库。 定义:KB=<SKS,SVS> 定义 10相似度(Smlt,Similarity): 待识别样本与知识库中符号集模板的相似程度称为相似度。 3. 数据结构组织 typedef struct { int x,y; }Point_Type; //点的类型定义 typedef queue<Point_Type> Queue_Type; //队列 typedef bool* Cov_Type; //覆盖表的类型定义 typedef bool Flag_Type; //拟合类型标志位的类型定义 typedef vector<Point_Type> LS_Type; //线段的类型定义 typedef vector<LS_Type> LSS_Type; //线段集的类型定义 typedef Point_Type LC_Type; //特征点的类型定义 typedef vector<LC_Type> LCS_Type; //特征点集的类型定义 typedef struct { Flag_Type Flag; //线段是 Y(X)型-0 还是 X(Y)型-1 的标记 vector<double>A; //线段的拟合函数系数向量 3
  • 4. long Length; //线段的长度,可选 Point_Type Start; //线段的起点,可选 LS_Type LS; //线段的点集,可选 LCS_Type LCS; //线段的特征点集,可选 }BFV_Type; //最佳拟合向量的类型定义 typedef struct { set<BFV_Type> BFVS; //构成笔画的最佳拟合向量 int Num; //笔画的编号 string Name; //笔画的名称 } SK_Type; typedef set<SK_Type> SKS_Type; //笔画集的类型定义 typedef struct { vector<SK_Type> SKV;//构成符号向量的笔画向量集 bool Is_Order //笔画是否有序 int Num; //符号的编号 string Name; //符号的名称 Bitmap Pic; //符号的图像,可选 }SV_Type; //符号向量 typedef set<SV> SVS_Type; //符号集的类型定义 typedef struct{ SKS_Type SKS; //知识库的笔画集模板库 SVS_Type SVS; //知识库的符号集模板库 }KB_Type; //知识库的类型定义 4. 相关处理方法 处理 1干扰处理方法: A. 二值化处理 本算法只能处理二值化的图像,所以待识别图形只能是二值化的。 图像的二值化处理算 法已经非常成熟,本文不再赘述。 B. 笔迹提取 当线条粗度不为 1 像素时,那么就必须提取样本的笔迹(骨干),再用本文的算法进 行识别。关于笔迹提取的算法已经较为成熟,不再赘述。 C. 线条消抖 因为由于某些原因可能导致获取到的线段存在抖动,例如硬件设备的延迟、 开发环境自 身缺陷等等,都可能会导致线段拆分把抖动的部分拆分成一条线段。 本文给出一种的消抖方法:在笔迹中随机抽取一定密度的点,用直线连接最近的并且 距离不超过一个阈值的相邻点,一般情况下密度和阈值设置合理新得到的图像可以有效的 消除相当一部分抖动,对可获取点输入顺序的联机输入尤其有效。另外引文[4]中的轮廓矢 量化算法部分也是一种较好的消除抖动的方法。 D. 断点连接 当进行离线识别时,可能因为各种原因导致图像不清晰。 因为算法的准确性依赖于线段 4
  • 5. 的正确拆分,因而图像中的原本是一条线的部分出现了断点可以导致识别准确性的大幅下 降。 相关处理方法有不少文章予以了讨论,本文给出一种断点连接方法:类似线条消抖的 处理方法,在笔迹中随机抽取一定密度的点,用直线连接最近的并且距离不超过一个阈值 的相邻点,一般情况下密度和阈值设置合理新得到的图像中可以消除图像不清晰带来的断 点。 处理 2线段拆分的处理方法 A. 联机识别: (1) 初始化两个覆盖表 CovX 和 CovY ,分别用于记录 X 轴和 Y 轴的被覆盖情况,并 将所有项置为 False(表示都未被覆盖)。 (2) 建立两个空队列 QueueX 和 QueueY,分别用于压入按 Y(X)方式记录和按 X(Y)方 式记录的点序列。 (3) 每当获取一个点 (Xi,Yi)时,分别判断在 CovX 和 CovY 的 Xi 位置和 Yi 位置是否为 False。 CovX 的 Xi 位置为 False,则将(Xi,Yi)压入 QueueX 并在 CovX 的 Xi 位置写 若 入 True。 则若 CovY 的 Yi 位置为 False 则将(Xi,Yi)压入 QueueY 并在 CovY 的 Yi 位置 写入 True。循环这个过程,直到遇到其中一个 Cov 表冲突(即对应位置为 True 的 Xi 或 Yi 位置已经为 True),则进入(4);当点全部处理完时则进入(5)。 (4) 如果有一个 Cov 表冲突,则将对应的 Queue 中的元素全部出队列清空并且将 Cov 表复位;另一个 Cov 表继续进行(3)中的操作,直到也出现冲突,则将对应 Queue 全部出队列到线段 LS[j],清空 Cov 表。例如,读入 (Xi,Yi),但 CovX 的 Xi 位置为 True,则将 QueueX 清空,CovX 复位为 False,同时继续按(3)的方法操作 CovY 和 QueueY , 直 到 CovY 也 出 现 冲 突 , 则 将 QueueX 中 的 元 素 出 队 列 存 储 到 LS[j],CovY 复位为 False。j=j+1,重新进入(3)。 (5) 如果是一条线画完,则进入(1)拆分下一条;如果没有点可以获取了,程序段结束。 B. 离线识别: (1) 按照从左向右,从上到下的扫描方法,只要扫描到一个点,就用这个点用类似种 子填充法的方法扩散,把能连通的线段全部连通,然后用联机识别的方法生成 LS,转(2)。 (2) 每取走一条线段,判断这条线段是否与其他线段交叉,如果不交叉则从图中删掉 这条线段,如有交叉则补上交叉点,转(1),直到图中没有点了为止。 处理 3特征点选取的处理方法 线段的起点(X1,Y1)和终点(Xn,Yn)应当被选取,其余的点应当以一定规则从线段的各个 部分取,例如每隔(n+1) div m 个点取一个特征点,应保证特征点能较好的描述原线段的轮 廓。 处理 4最佳拟合函数的处理方法 A. 最佳拟合函数中阶数 n 的取值方法: n 从 1 开始拟合,求出 R2(拟合相似度),每当 n+1 可以使 R2 增加一个阈值 α,例如 α=5%,则取 n+1 为当前的 n,再次进行判断,直到 n+1 阶拟合不能使 R2 增加 α 为止。 B. 最佳拟合函数中系数 Ai 的取值方法: 对于系数 Ai,如果 Ai 的绝对值小于一个阈值 β,例如 β=1E-3,那么测试去掉 Ai*Xi 项 后,R2 会不会减小一个阈值 γ,例如 γ=5%,如果不会减小 γ 那么多,就去掉 Ai*Xi 项(把 5
  • 6. Ai 赋值为 0)。即用尽可能低阶尽可能少的项的表达式表示出尽可能高的拟合度。 例如,图 1 中的线段,取如下一组特征点,阈值 α=5% : LCS={(0,0),(1,1),(2,3),(3,6), (4,10), (5,15),(6,20),(7,28),(8,34),(9,45),(10,55),(11,66),(12,79),(13,90),(14,104)} 图 1. 红色为线段,蓝色为一阶拟合,绿色为二阶拟合 当 n=1 时,进行一阶拟合得拟合函数为 Y1=7.439*X-22.58,R2=0.936。 当 n=2 时,进行二阶拟合得拟合函数为 Y2=0.504*X2-0.626*X+0.272,R2=0.999。 可见,当 n 由 1 增加到 2 时,R2 增加了(0.999-0.936)/0.936=6.7%,大于阈值 5%,那么 当前最优拟合函数为 Y2=0.504*X2-0.626*X+0.272。 图 2. 红色为线段,蓝色为一阶拟合,绿色为二阶拟合,黑色为三阶拟合 当 n=3 时,进行三阶拟合得拟合函数为 Y3=8E-05*X3+0.502*X2+0.252,R2=0.999。 可见当 n 由 2 增加为 3 时,R2 几乎没有增加,小于阈值 5%,那么最优拟合函数则确定 为 Y2=0.504*X2-0.626*X+0.272。 处理 5最佳拟合向量的处理方法 6
  • 7. 当有需要时,例如长度不同也要识别为不同的图形的时候,或者线段的长度在全局所 占的比例不同会影响识别结果时,可以在拟合向量中增加一个长度元素,记录下线段长度。 当算法仅作为一个图像矢量化算法时,还可以再加上一个起点元素,记录线段的起点。 由这 些元素就可以通过最佳拟合向量还原图形。 例如,图 2 中的最佳拟合函数 Y2=0.504*X2-0.626*X+0.272 的拟合向量不考虑可选部分 是一个 3+1 维向量 BFV=(0,0.504,0.626,0.272)。 处理 6笔画拆分处理方法 对可识别符号集的笔画拆分,需要以程序处理方便容易辨别为原则,而不是一定按照 平时某种习惯的处理。 例如,对“马”这个字,汉字笔画是“┐,ㄅ,ー”,但是为了方便处理,应该把“ ┐”拆为“横”“竖”两笔,“ㄅ”拆为“竖”“横”“竖”,“提”这一部分可以忽略 ; 于是方便程序处理的拆分方案是“横”“竖”“竖”“横”“竖”“横”,假设“横”的 标记是 1,“竖”的标记是 2,则生成的笔画序列是(1,2,2,1,2,1)。 处理 7相似度的处理方法 首先需要根据图形拆分出的各个最佳拟合向量,在知识库的笔画集里查找最匹配的笔 画,生成符号向量。 然后利用符号向量在知识库的符号集里查找最匹配的符号,如果笔画有序的则查找笔 画和顺序都匹配,如果无序则查找笔画的数量和类型不考虑顺序能匹配。 如果既不能找到笔画数相同的也不能找到所用笔画完全相同的,则用最接近匹配原则, 找最接近的符号。 对于笔画有序的字符向量,则取各个位按顺序能匹配到正确笔画数量最多 的字符;如果笔画无序的,则取所有笔画中能匹配到所用笔画最多的字符。 然后根据需要, 可以取出字符向量的图像,用图像进行对比确认结果。 5. 算法描述 5.1.语言描述: S1: 建立知识库; S2: 读入样本; S3: 分析样本 (1) 从图形中拆分出笔画的图案; (2) 将拆分出的笔画图案进行分析归类到笔画集中最匹配的笔画; (3) 根据有序无序的情况生成识别的符号序列; S4: 识别样本 (1) 根据有序无序情况在知识库找最匹配的若干个模板; (2) 提取这若干个模板的图案和样本进行匹配; (3) 将图案最匹配的那个样本最为识别结果; (4) 根据用户需要决定是否将新样本存为模板; S5: 输出结果。 5.2. 相关参数描述: (1) LSS_Type LSS; //线段集类型 (2) LCS_Type LCS; //线段特征点集的序列类型 7
  • 8. (3) SVS_Type SVS; //符号序列类型 (4) SV_Type SV; //符号向量类型 (5) KB_Type KB; //知识库类型 5.3. 相关操作函数注解: bool CreatKB(); //创建知识库 bool LoadKB(KB_Type); //载入知识库 bool StoreKB(SV_Type); //更新知识库 Bitmap ReadSV(); //读入一个待识别样本 LSS_Type GetLSS(Bitmap); //拆分线段 LCS_Type GetLCS(LS_Type); //生成线段特征点集 BFV_Type GetBFV(LCS_Type); //根据特征点集拟合多项式生成最佳拟合向量 bool AnalysisSV(SV_Type); //分析一个符号向量 SK_Type MatchingSK(BFV_Type); //用最佳符号向量匹配笔画 SVS_Type MatchingTP(SV_Type); //用符号向量匹配模板 SVS_Type MatchingSKV(SV_Type.SKV); //按符号向量的笔画向量匹配 SVS_Type MatchingPIC(SV_Type.Pic, SVS_Type); //按符号图像的匹配 5.4.执行过程: S1. KB = CreatKB()或 LoadKB(KB); //建立知识库或载入知识库 S2. SV.Pic = ReadSV(); S3. AnalysisSV (SV) //分析样本 Begin LSS = GetLSS(SV.Pic); //将图像拆分成笔画集 For i: = 1 To LSS.size() Do Begin //生成特征点集合 LCS = GetLCS(LSS[i]); //生成最佳拟合向量写入符号向量 SV.SKV[i].BFV.add(GetBFV(LCS)); //用拟合向量匹配笔画写入符号向量 SV.SKV[i] = MatchingSK(SV.SKV[i].BFV); End return SUCCESS; End S4. SVS = MatchingTP(SV); //匹配模板,SVS[1]为最可能的识别结果 Begin //按向量匹配得若干个符号向量 SVS = MatchingSV(SV.SKV); //如果需要,比较样本的图像和每个可能的符号的图像进行匹配 SVS = MatchingPIC(SV.Pic); If(用户需要更新知识库) Then StoreKB(SV); 8
  • 9. return SVS; End S5. Write(SVS[0]); //输出最匹配的结果 6. 算法实现 我们在 PC 上实现了上述算法,并且可根据实际情况对参数做出修改来适应具体情况, 执行效率可控性强,由于最终是对字串进行匹配,因而可以通过添加索引等方式提高效率。 适用范围广,无论是手写或打印体,只要根据实际情况设置参数和处理方式,就可以适应 具体情况。 算法可以进行相应的改进 ,如使它能够处理非正向输入的符号,例如汉字,输入时不是 正向写的,有一些倾斜,直接拟合然后跟知识库对比是很可能会出错的。 可以采用对拟合函 数多项式进行坐标旋转,用函数的方法,尝试下旋转一定角度后进行识别,如果匹配率大 大增加,则说明旋转是有效地。 本算法可处理很多特殊的符号,不限于数字、字母、汉字等。 图 3 和图 4 分别给出了识别手写汉字“嚷”和五线谱低音符的运行效果。 图 3. 联机识别手写运行效果 (左上图:手写样本,右上图:特征点采集,左下图:消抖处理,右下图:线段拆分处理) 9
  • 10. (图 4. 联机识别手写五线谱低音符运行效果) (左上图:手写样本,右上图:特征点采集,左下图:消抖处理,右下图:线段拆分处理) 7. 结论 本文提出一种基于拟合函数的图形识别算法,并通过识别手写汉字和音乐符号来验证 了该算法的有效性,通过将图形拟合成多个多项式,与模板库中的样本进行比较分析提取 出相似度最高的模板作为识别的结果。按本文所采用的识别方法要求手写的字符是标准的方 向,对于非正向输入以及向量表示差异不大的符号进行识别时有误差,因此该系统需要进 一步的提高,使之实用性更广。 参考文献 [1] Pu Y, Shi Z1 A natural learning algorithm based on Hough transform for text lines extraction in handwritten documents [C] Proceedings of the 6th International Workshop on Frontiers in Handwriting Recognition , Taejon , 1998 : 637 - 646 [2] 高学,金连文,尹俊.一种基于笔画密度的弹性网格特征提取方法[J].模式识别与人工智能, 2002,15(3):351-354. [3] 蔺 志 青 , 郭 军 . 贝 叶 斯 分 类 器 在 手 写 汉 字 识 别 中 的 应 用 [J]. 电 子 学 报 , 2002, 30(12): 1804-1807 [4] 沈立,张晨曦.黑白图像的矢量化[J].计算机辅助设计与图形学学报.2000,12(3): 170-173 [5] 张力 , 点阵汉字转换成矢量汉字的笔迹定向跟踪法 [J]. 计算机辅助设计与图形学学报 . 1990,2(1): 31-33 [6] 敖翔,戴国忠,王宏安.基于感知的多方向在线手写笔迹文本行提取[J]. 计算机辅助设计与 图形学学报. 2007, 19(1): 14-19 10