HC-05-DigitalPen_Paper 第五讲基于笔的交互界面技术.ppt

第五讲基于笔的交互界面技术,目录,数字墨水数码笔【手写】汉字识别技术,手写板,手写屏,电子白板,掌上电脑,TabletPC,数码笔,纸笔式交互设备,数字墨水技术,数字墨水技术DigitalInk,微软亚洲研究院多通道用户界面组发明负责人：王坚借鉴了学术界多年来在“手写识别”方面所取得的研究成果的同时，超越了“手写识别”技术的许多局限，更加人性化！数字墨水分析技术可以对记录下来的“数字墨水”进行结构化和深度分析其分析目的不是要去解决“写的是什么字”，而是要解决用户在写什么是字还是“涂鸦”以及是如何写的可用作文字识别、图形绘制的输入,数字墨水技术,数字墨水可以用墨水格式保存，将手写的笔迹以墨水的形式保存，不会丢失任何信息用户不再需要利用其它的Windows应用程序，来把手绘、手写的笔迹转换为别的格式来保存、发送和编辑由于Windows平台将“数字墨水”定义为“基本数据类型”之一，这就如同文本得到操作系统这一级别上的支持一样，数字墨水在不同应用软件之间的交换变得非常容易数字墨水技术已作为产品，结合在微软的TabletPC操作系统中，产生了很大的社会影响。它还将继续发展，有可能成为新一代优秀的自然交互设备,数字墨水技术,数字墨水的处理包括了数字墨水的表示、压缩和显示墨水智能分析技术墨水标记和注解技术墨水的智能操作墨水存储和搜索数字墨水与数码笔数字墨水+平板电脑数码笔+数码纸,示例,示例,示例,示例,示例,数码纸笔技术,ANOTO数码纸笔技术简介,瑞典Anoto公司、Ericsson和TimeManager公司共同研发，其功能是：物理书写与数字书写同时完成纸上留下笔迹（真实墨水）书写轨迹被同时数字化，可以存储到计算机中,课堂讨论,这么酷的东东该如何实现？,提示,轨迹是什么？坐标的序列不同的点要有不同的坐标如何区分不同的点？所以，要对“纸”做特殊的处理！,ANOTO数码纸笔技术简介,瑞典Anoto公司、Ericsson和TimeManager公司共同研发Anoto技术主要有三个组成部分数码笔数码纸Anoto软件平台,数码纸,数码纸是通过在普通纸上印刷“点阵”及其他图文内容产生的用户在使用数码纸时，也只需和使用普通纸产品一样书写即可,数码纸原理,与普通纸不同之处，就是数码纸有“点阵”。“点阵”由一些非常细小的点，按照特殊算法规则排列的组成。点阵的作用是提供给数码笔一个坐标参数信息，保证数码笔在数码上书写时，能够准确的记录书写的笔迹。,Anoto点阵坐标编码,是Anoto基本专利技术的核心理论技术该坐标是由许多细小的点阵组成，每个点有上下左右4个可以选择的位置，将36个点按6X6的形式排列就组成一个点阵，每一个点阵代表一个信息单位，36个点就有436种排列组合方式，也就有47万亿亿种排列形式，即一个Anoto点阵可以代表047万亿亿之间的任意数字当设定点与点之间隙为0.3mm时、一个Anoto点阵就可形成1.8mmX1.8mm见方的正方形面积，由47万亿亿个6X6点阵组成的总面积就可以覆盖整个地球表面，而任意一点的绝对坐标都不会发生重叠现象。,数码笔,数码笔只是对笔尖所经过的点的信息进行提取、存储和发送的设备，并不对信息进行处理数码笔内存储的信息包括点阵的坐标、书写速度、时间以及压力等信息，基本组成结构笔芯高速摄像机压力感应器处理器存储器电池通讯单元：蓝牙,数码笔的基本工作原理,Anoto数码笔应用,汉字识别技术OCR,汉字/字符识别分类,文字识别,联机手写识别,脱机手写识别,印刷体识别,手写体识别,信号采集方式,脱机识别扫描仪或者摄像设备将纸张颜色数字化数字图像信号联机手写识别手写屏，手写输入板在书写时，笔在板上的运动轨迹（在板上的坐标）被转化为一系列的电信号，电信号可以串行地进入到计算机中，可以比较容易地抽取笔划和笔顺的信息,汉字/字符识别分类,技术难度比较印刷体识别最容易最容易，已经有了大量实际应用，图书馆数字化联机手写体识别较容易相对容易，PDA等的推广，大量应用脱机手写体识别最困难脱机手写体数字的识别已有实际应用外，比如邮政编码的自动识别汉字等文字的脱机手写体识别还处在实验室阶段,提纲,背景介绍印刷体汉字识别联机手写汉字识别,OCR技术介绍提纲,背景简介一般流程常用方法,问题描述,图像(像素矩阵),汉字OCR技术发展历史,西文OCR技术研究始于50年代OpticalCharacterRecognition(OCR)字符识别一直是模式识别的重要研究内容之一几乎所有的早期PR研究者都进行过字符识别的研究汉字OCR技术印刷体汉字的识别最早可以追溯到60年代1966年，IBM公司的Casey和Nagy发表了第一篇关于印刷体汉字识别的论文，在这篇论文中他们利用简单的模板匹配法识别了1,000个印刷体汉字,汉字OCR技术发展历史,70年代以来，日本人做了许多工作日本的常用汉字有2000个左右1977年东芝综合研究所研制了可以识别2000个汉字的单体印刷汉字识别系统80年代初期，日本武藏野电气研究所研制的可以识别2300个多体汉字的印刷体汉字识别系统，代表了当时汉字识别的最高水平日本的三洋、松下、理光和富士等公司也有其研制的印刷汉字识别系统简评这些系统在方法上，大都采用基于KL数字变换的匹配方案，使用了大量专用硬件，其设备有的相当于小型机甚至大型机，价格极其昂贵，没有得到广泛应用,汉字OCR技术发展历史,我国研究简况我国自70年代后期开始字符识别方面的研究80年代以后，台湾和香港发展的也很快发展历程70年代末期到80年代末期算法和方案探索：单体汉字识别90年代初期由实验室走向市场，初步实用90年代后期混排多语言混排文本：如中英文多字体混排文本：如：宋，楷体，）多字号混排文本：不同大小,当前进展状态,2000年后识别率、鲁棒性的提高单纯OCR文档分析多语混排，多字号，多字体版面分析文本的结构表格，图像（如插图），公式摄像设备（非扫描仪）思考：有什么用？名片手机摄像通讯录报纸、路标手机摄像自动翻译,国内主要研究机构/人物,汉王科技中科院自动化所（刘迎建）1985年刘迎建开发出国内第一个联机手写汉字识别系统，并获国家发明专利。1993年初，在中科院自动化研究所的支持下创办了中国汉王科技公司，出任总经理中科院计算所智能计算机研究中心（刘昌平）1965年出生，博士，1999年之前在中科院计算所智能计算机研究中心工作，从事OCR研究。1999年加盟自动化所，现任自动化所研究员、博士生导师其他清华大学电子系图像所北京信息工程学院沈阳自动化研究所,OCR技术介绍提纲,背景简介一般流程常用方法,OCR基本原理,你,(啊)(阿)(埃)(挨)(哎)(唉).(你).(蕞),Max,FFFFFFFF,OCR技术一般流程,输入材料,流程简介,1.图像获取将文本转换为图象点阵扫描仪(Scanner)其它光电扫描设备摄象机，传真机不同获取设备的差异扫描仪：最优摄像机：识别难度大,流程简介,2.图像预处理滤除干扰噪声倾斜校正各种滤波处理,输入材料,流程简介,3.版面分析完成对于文本图象的总体分析区分出文本段落及排版顺序，图象、表格的区域对于文本区域将进行识别处理对于表格区域进行专用的表格分析及识别处理对于图象区域进行压缩或简单存储。,输入材料,流程简介,4.行、字切分将大幅的图象先切割为行从图象行中分离出单个字符,流程简介,5.特征提取模式表示问题整个环节中最重要的一环，提取的特征的稳定性及有效性，直接决定了识别的性能从单个字符图象上提取统计特征或结构特征包括细化(Thinning)，归一化等步骤,OCR技术一般流程,输入材料,流程简介,6.文字识别模式识别研究范畴从学习得到的特征库中找到与待识字符相似度最高的字符类,流程简介,7.后处理利用词频、语义、语法规则或语料库等先验的语言模型对识别结果进行校正的过程,OCR技术介绍提纲,背景简介一般流程常用方法,汉字识别方法分类,基于句法/结构模式识别的OCR方法基于统计模式识别的OCR方法基于结构+统计混合的OCR方法,基于句法的汉字识别,早期汉字识别研究的主要方法其主要出发点是汉字的组成结构汉字图形结构复杂，但规律性强，含丰富的结构信息从汉字的构成上讲笔划(横竖撇点折)偏旁部首字由这些基元及其相互关系完全可以精确地对汉字加以描述类比类比文章结构单字词短语句子篇章，按语法规律组成识别过程：编译理论中的句法分析,基于句法的汉字识别,训练过程建立所有汉字的解析图描述定义基本单元基本单元之间的拓扑结构,字,偏旁部首,基本笔划(横竖撇点折),标,汉字的解析图表示示例,基于句法的汉字识别,识别过程图像获取预处理二值化，细化基元提取基本笔画提取偏旁部首提取解析图表示,尔,你,基于句法的汉字识别,相似度计算方法句法分析过程Top-down：能走多远图匹配过程拓扑相似性节点相似性,基于句法的汉字识别,优点理论上比较漂亮，对字体变化的适应性强，区分相似字能力强缺点描述复杂，匹配过程复杂度也高抗干扰能力差，结构基元提取困难，导致推理过程难以进行实用中，文本图象中存在着各种干扰，如倾斜，扭曲，断裂，粘连，纸张上的污点，对比度差等等,汉字识别方法分类,基于句法/结构模式识别的OCR方法基于统计模式识别的OCR方法基于结构+统计混合的OCR方法,基于统计的汉字识别方法,基本思路将字符点阵看作一个整体，其所用的特征是从这个整体上经过大量的统计而得到的缺点细分能力较弱，区分相似字的能力差一些优点抗干扰性强，尤其适用于有污染的数据匹配与分类的算法简单，易于实现,基于统计的汉字识别方法,图像预处理特征提取分类器设计,特征设计,设计什么样的特征？,常用的统计特征,直接图像特征变换特征投影直方图几何描绘子笔划密度特征外围特征,微结构特征特征点特征粗网格特征,1.直接图像特征,实际上并不需要特征提取过程，字符的图象直接作为特征与字典中的模板相比，相似度最高的模板类即为识别结果,相似度=0.9,相似度=0.2,1.直接图像特征(续),优点简单易行，可以并行处理缺点不同大小、不同字体需要大量模板对于倾斜、笔划变粗变细均无良好的适应能力,2.变换特征,字符图象进行某种数学变换二值类变换，如Walsh,Hardama变换更复杂的变换，如KL,Fourier变换,余弦变换(DCT)优点变换后的特征的维数通常会降低，更紧凑，利于分类缺点多数变换不是旋转不变的，因此对于倾斜变形字符的识别会有较大的偏差有些最优变换特征的运算复杂度较高，如：K-L变换在最小均方误差意义下是最优的变换，但是运算量大,3.投影直方图,利用字符图象在特定方向的投影作为特征通常使用水平及垂直方向缺点该方法对倾斜旋转非常敏感，细分能力差,图,差,4.笔划密度特征,笔划密度特征提取从不同方向扫描文字，计算和笔划相交的次数，形成笔划密度特征通常取水平、垂直和两对角线四个扫描方向，每个方向取若干个区域得到若干特征,4.笔划密度特征(续),优点这种特征描述了汉字的各部分笔划的疏密程度在图象质量可以保证的情况下，这种特征相当稳定缺点在字符内部笔划粘连时误差较大,5.粗外围特征(续),抽取特征时,先把文字分为n*n份(一般n=8)从文字四边各向对边扫描，计算最初与文字相碰的非文字部分面积与全部面积之比作为一次粗外围特征，共有4xn个再将第二次与文字线相碰的非文字部分面积与全部面积之比作为二次粗外围特征，也有4xn个。这样形成8n维的特征向量一次粗外围反映了文字的外轮廓，二次粗外围在某种程度上反映了文字的内部结构,示例:从左边扫描,5.粗外围特征,优点汉字的轮廓包含了丰富的特征即使在字符内部笔划粘连的情况下，轮廓部分的信息也还是比较完整的缺点不具备细分能力这种特征非常适合于作为粗分类的特征,6.粗网格特征,把文字分为n*n份，n通常为8取每份的白点数对整个文字白点数的比例形成nxn维特征向量,(1/53,3/53,7/53,3/53)(6/53,3/53,2/53,2/53)(4/53,2/53,6/53,5/53)(4/53,0/53,5/53,0/53),4x4特征,提纲,背景介绍印刷体汉字识别联机手写汉字识别,参考文献,Authors:Cheng-LinLiu*,StefanJaeger+,andMasakiNakagawa+*CentralResearchLaboratory,Hitachi,Ltd.,+TokyoUniversityofAgricultureandTechnology,Title:OnlineRecognitionofChineseCharacters:TheState-of-the-Art.Source:IEEETrans.onPatternAnalysisandMachineintelligence.26(2),2004.2,提纲,概况系统流程技术介绍性能评估发展趋势,需求,日益增长的在线手写识别需求Onlinehand-writtingrecognition笔式计算应用增多新型笔式输入设备汉字识别比西文识别更有挑战性OnlineChinesecharacterrecognition(OLCCR)更多的类别数，更多的变化不同的书写体：楷书，(行楷)，行书，(行草)，草书本文对1990年代之后技术进展进行回顾,大的技术趋势,与此前(1980年代)的技术相比，1990年代之后技术进一步放松约束，先前技术局限于标准笔顺，标准笔划数standardstrokeorders，strokenumbers孤立汉字识别（isolatedcharactersonly）从楷书识别行书识别shiftedfromregularscripttofluentscript,联机手写的优势,【与脱机手写相比】具有笔划时间信息空间形状信息良好的可交互性用户可以修正错误可适应性系统适应：根据用户修正的错误进行学习用户适应：可以改变书写习惯,典型应用,各类电子填表短消息编写PDA/手机计算机辅助教学/教育手写文档检索数字墨水特别是对大字母表语言输入中文等亚洲字母表,汉字,地球上超过1/4的人使用汉字三个字符集简体中文繁体中文日本汉字（JapaneseKanji),汉字字符集,简体中文（大陆，新加坡，香港）GB2312-80一级汉字：3755个二级汉字：6763个（含一级）台湾地区5401个繁体字日本JISLevel-12965个汉字JISLevel-23390个汉字互不重叠,汉字特性,字形特征象形表意文字（ideograph）由直线、曲线等线条组成有子结构字根：字根编码可以减少模型数，加快识别速度手写体类型楷书：Regularscript行书：Fluentscript草书：Cursivescript,State-of-the-art,1990s以来的研究重点放松强加给书写人的各种约束单字书写（不能连书）尽可能与标准楷体一致主要难题笔顺、笔划数的差异研究目标变迁从楷书到行书：笔顺、笔划数的更大变化当前进展当前系统对楷体的识别率非常高：98%行书识别仍然没有完全解决草书的识别还有很长的路要走,State-of-the-art,识别方法基于笔划分析的结构方法结构(structural)方法：strokeanalysis笔顺无关的结构方法：stroke-orderfree笔顺依赖的结构方法：stroke-orderdependent基于整体形状的统计方法统计方法：statisticalmethods自然是与笔顺无关的（stroke-orderindependence）从应用角度书写人依赖系统：更容易一些书写人无关系统：更有挑战性,提纲,概况系统流程技术方法性能评估发展趋势,OLCCR实用系统流程图,分割时域形状歧义处理候选字符模式识别结果修正模式描述-特征提取统计：特征向量结构：基元层次图,预处理方法降噪,噪声来源书写时手的“飘忽”移动数字化的不准确性降噪方法平滑，滤波，野点校正(断)笔画连接,预处理方法降维,降维轨迹线等距重采样（equidistancesampling）重采样以使得相邻点距离相等简单，但维度降低不大特征点检测（lineapproximation）检测：角点，笔划端点角点检测典型方法曲率法估计每个点的曲率，保留那些高曲率点多项式近似递归的寻找具有最大“点弦距离”的顶点,预处理方法归一化,将字符轨迹归一到一个标准尺寸线性归一化方法1：平移和尺度变换方法2：距归一化一阶中心矩固定为标准框的中心二阶矩则固定为某标准值非线性归一化根据线密度分布重新分配轨迹点坐标，以使得笔画空间分布均匀(equalizingthestrokespacing),提纲,概况系统流程技术方法性能评估发展趋势,汉字识别技术介绍,模式表示汉字分类模型学习与适应上下文处理,表示方法分类,1、结构表示法结构树/关系属性图表示2、统计表示法特征向量模型（/参数）数据库包含分类参数3、混合表示法HMM,结构表示法,五个层次的结构上层由下层的“基元”构成特征点=线段两个特征点决定一个线段笔划编码笔划模型笔划类型HMM通常用来建模笔划或子笔划关系结构汉字或字根模型建模笔划之间的结构关系层次结构模型数据库的层级结构：共享大量字根，建立所有字符的的表示模型输入模式的层级结构：以字根为基元的关系结构,区分几个概念,输入模式Inputpattern参考模型字符原型：CharacterPrototype参考模型：Referencemodel模型数据库ModelDatabase,采样点表示,直接采用“重采样的轨迹点序列”作为表示方法输入模式：重采样点序列字符原型：重采样点序列比对方法对点序列进行对齐，然后通过点距离计算笔划之间的距离即可,特征点/线段表示,特征点表示特征点的序列特征点!=采样点可以与采用特征点序列、笔划编码、层级结构表示的字符原型作匹配线段表示可以与采用线段或者更高层结构表示的字符原型作匹配目前已被广泛采用的表示方法,笔划编码表示,笔划编码笔划可以归类为若干“类别”每个类别分配一个码字/Index横-1，竖-2，撇-3，折-4，点-5每个笔划编码对应一个参考模型/原型或者一组规则（描述该笔划）字符模型笔划编码的序列，e.g.木：1235or以笔划编码为基元的关系结构识别通过有限自动机等方法在输入模式中进行笔划模型匹配来检测笔划,关系表示,关系结构将字符的构成基元（笔划或线段）及其关系进行建模属性关系图(AttributedRelationalGraph,ARG)节点表示基元弧（连接）表示基元之间的关系,ARG示例,示例X交叉（intersection）T端线T连接（end-to-lineadjacency）L端端连接（end-to-endadjacency）P位置关系positionalrelation,Wherearewe?,结构统计混合,木：横竖撇点1235,HierarchicalStructure,ARG的缺点,1、参考模型的基元和关系编码需要小心的处理，以容忍输入模式的形状变异解决策略模糊ARG多属性关系编码：节点/弧2、难以提取可靠的笔划基元及其关系解决策略用容易检测的线段(小笔划、而不是笔划)作为基元,层次结构化表示,StructuredRepresentation汉字天然的“层级结构”汉字字根笔划子笔划采样点结构化表示的主要特点共享字根/笔划模型通过动态的重组字根/笔划模型来构造汉字优点节省了大量模型的存储空间数百个字根数千个汉字,结构化表示,结构化表示的模型数据库组织方法查找表(lookuptable)树结构网络结构识别策略从输入模式中提取字根/笔划，然后遍历整个汉字结构模型数据库不同变种使用线段、小笔划来代替字根或笔划,网络结构示例,网络中的每条路径对应一个汉字以字根为基元,表示方法分类,1、结构表示法结构树/图表示2、统计表示法特征向量模型（/参数）数据库包含分类参数3、统计-结构混合表示法HMM,统计-结构表示法,结构表示的概率化原理上，任何结构表示模型都可以通过使用概率密度函数(PDFs)取代基元(节点)和关系(连接)的属性来获得其统计-结构表示概率模型，例如：笔划和关系属性的均值和方差特征点/笔划属性分布的高斯函数模型HMM:HiddenMarkovModels隐马尔科夫模型,HMM,HMM有向图通过概率描述节点及其节点跳转应用情况1970年代语音识别1980年代西文字符识别1990年代汉字识别,HMM,HMM可以用来为子笔划、笔划、字根或整个字符，建立他们的点或线段的序列模型,、,0.8,0.2,0.2,0.8,0.8,0.8,0.2,0.2,0.2,HMM,基于字符的HMM(为每个字符建一个HMM)问题：笔划顺序依赖的模型解决：多个模型来覆盖不同的笔顺/形状变异基于笔划/子笔划的HMM可以层级的建立字符模型笔顺差异可以使用一个差异网络来表示,表示方法分类,1、结构表示法结构树/图表示2、统计表示法特征向量模型（/参数）数据库包含分类参数3、混合表示法HMM,统计特征表示,统计模型输入模式特征向量数据库中包含分类参数，可以通过标准的统计技术进行估计特征向量将轨迹2D静态图像提取Offline特征优点特征向量与笔顺/笔划数无关，可以容忍笔顺/笔画数的较大差异缺点丢失了笔顺/笔划信息，可能导致精度下降写完后才能识别，难以实现边写边提示,Wherearewe?,结构统计混合,木：横竖撇点1235,汉字识别技术介绍,模式表示汉字分类方法模型学习与适应上下文处理,问题的提出,问题汉字模式类别众多，如何进行快速识别？可能的解决方法体现方法论上的一些重要理念,啊阿吖呵.国.张郑,国,解决方法,快速分类的基本思路快速分类器快速排除大量不易混淆的类别快速选择出少量可能的候选解决方法粗分类细分类,由粗到细,CoarsetoFine,粗分类方法之一,分组法类集合划分法Classsetpartitioning所有汉字划分为若干分组方法论上体现了一个重要理念军事上：分割包围，各个击破,分而治之,DivideandConquer,分组模式,无重叠严格划分每个字只能被划分到一个组缺点决策过程一旦出错，难以挽救有重叠软划分每个字可被划分到多个组优点降低风险,如何分组？,问题在什么时候进行分组？分类器设计阶段or识别阶段？在分类器设计阶段进行汉字分组分组方法聚类或者根据先验知识进行划分分组依据总体字符结构基本笔划子结构笔划序列统计特征神经网络分类器,粗分类方法之二,候选汉字动态选择法Dynamiccandidateselection基本思路快速选择出最相似的or快速排除不可能的候选相当于动态分组在识别阶段分成两组候选组+不可能组,国困回网田用.人已上,国,算法流程,输入模式首先与全部汉字快速匹配采用简单特征、简单分类器根据相似度（匹配分值）进行排序选择相似度最大的若干个候选字进行细分类,如何实现快速匹配？,快速匹配方法【相似度计算方法】简单的结构特征或者统计特征笔划数或者线段数、外围特征等匹配方法串匹配，结构特征投票法，特征向量匹配等特征匹配街区距离，欧式距离等可以快速计算的方法结构匹配字根检测，快速排除不包含字根的汉字,如何适应联机手写特点？,问题适合联机手写汉字识别的粗分类方法？思考题如何分组适合联机手写汉字识别的特点？笔划数分组是否合适？笔划、笔顺相关是否合适？什么样的快速候选字动态选择适合汉字识别？笔划数分组是否合适？笔划、笔顺相关是否合适？适于边写边提示的应用模式,细分类方法,结构匹配法Structuralmatching对应：结构表示概率匹配法Probabilisticmatching对应：统计结构表示统计分类法Statisticalclassification对应：统计表示法,结构匹配法,基本过程输入模式与候选汉字的结构模型逐一匹配输出具有最小匹配距离的汉字类别即可两类策略分级匹配形变方法四种方法动态规划笔划对应关系匹配基于知识的匹配,结构匹配法分级匹配策略,优点可以进一步提高速度笔划编码/字根模型共享，可使用决策树加速识别过程字根/笔划一旦检测出来，汉字识别就变成了遍历一棵树的某条路径缺点输入模式笔划/字根的检测并非易事解决确定性遍历度量路径的似然性,堆,结构匹配法形变策略,基于笔划对应关系，计算“输入模式和原型”之间的“形变向量场（DVF）”汉字原型通过局部仿射变换(LocalAffineTransform)来适应输入模式形变程度决定相似度,动,输入,细分类方法结构匹配法,基本过程输入模式与候选汉字的结构模型逐一匹配输出具有最小匹配距离的汉字类别即可两类策略分级匹配形变方法四种方法动态规划笔划对应关系匹配基于知识的匹配,结构匹配方法,四类方法动态规划DP(dynamicprogramming)动态规划针对有序的序列进行，依赖于笔顺笔划对应Strokecorrespondence笔划vs.笔划，不考虑笔划间的关系关系匹配RelationalMatching考虑笔划间的关系基于知识的匹配Knowledge-basedMatching,1.动态规划(DP)匹配方法,基本思路通过最小化编辑(Levinstein)距离来寻求两个符号串(基元序列)中的符号(基元)的对应基元：采样点，小笔段，笔划，字根最小化的编辑距离即可作为二个串的距离/匹配度,编辑距离,基本思路计算从原串(s)转换到目标串(t)所需要的最少的插入、删除和替换的数目问题描述设S1和S2是两个字符串。要用最少的字符操作将字符串S1转换为字符串S2。这里的字符操作包括：(1)删除一个字符(2)插入一个字符(3)替换一个字符。定义将字符串S1转换为字符串S2的所用的最少的字符串操作数称作字符串S1到S2的编辑距离，记为d(S1,S2),示例,一,|,一,一,一,|,、,一,汉字原型笔划序列,输入模式笔划序列,一,|,一,输入模式笔划序列,一,|,一,一,输入模式笔划序列,、,动态规划(DP)匹配方法,DP匹配属成熟技术，但其性能依赖于基元选择采样点，小笔段，笔划，字根点序列的DP匹配也称为动态时间规正(Dynamictimewarping)基元之间距离度量0/1？概率？笔划顺序变化多个Prototype？,2.笔划对应,任务输入模式与字符原型匹配距离计算方法首先做笔划对应笔划距离之和笔划对应也可以采用DP完成,一,|,一,一,一,|,、,一,汉字原型笔划序列,输入模式笔划序列,D=d1+d2+d3+d4+d5+d6+d7+d8+d9,3.关系匹配RelationalMatching,任务关系表示的匹配图匹配问题形式化在关系（relationship）约束下搜索两个集合中的元素之间的对应关系问题求解可以被形式化为“一致标定(consistentlabeling)”问题，通过人工智能中的启发式搜索(heuristicsearch)或者松弛标定等方法解决松弛标定(RelaxationLabeling)计算效率高而启发式搜索则更灵活，可以很容易的结合不同的知识源和约束条件,关系匹配,属性关系图ARG的匹配A*搜索算法松弛标定应用于字符识别或者字根检测优点笔划顺序无关DP是笔划相关的关系约束提高了匹配精度笔划对应不考虑笔划之间的关系缺点计算效率低于DP和笔划对应等,4.基于知识的匹配,含义利用汉字结构和书写方式的先验知识作为启发信息或者作为约束，用以减少搜索知识结构知识：上下，左右，内外预先指定（字根/单字）笔顺、笔划数的允许变化范围笔划顺序的统计比如某个笔划之后很少出现另外一个笔划之类优点知识规则的有效利用可以减少搜索有利于区分相似的字符，从而提高精度缺点知识库的建立和组织并不容易而且费时,细分类方法,结构匹配法Structuralmatching对应：结构表示概率匹配法Probabilisticmatching对应：统计结构表示统计分类法Statisticalclassification对应：统计表示法,概率匹配,对应于统计-结构表示法简单属性属性概率模型(容忍基元/关系差异)距离/相似度计算笔划原型建模为(高斯)概率密度函数形成笔划类型概率表输入模式字符模型之间的相似度计算首先通过属性串匹配或者启发式搜索将输入模式的特征点或线段组织为“笔划”，并给出相似概率计算字符模型中所需的全部“笔划”的联合概率,基于HMM的识别,任务将观测序列（特征点或线段）解码为最可能的状态序列（HMM：有向图）状态=笔划或字根或字根方法Viterbi译码,木,又,寸,细分类方法,结构匹配法Structuralmatching对应：结构表示概率匹配法Probabilisticmatching对应：统计结构表示统计分类法Statisticalclassification对应：统计表示法,统计分类法,二次项分类器quadraticclassifiers子空间法subspacemethod每个汉字一个子空间多相似度量multiplesimilaritymeasure改进的二次判别函数modifiedquadraticdiscriminantfunction(MQDF)假设每个汉字类别是多元高斯函数缺点计算和存储需求大替代算法直接计算特征向量之间的欧式距离多原型：每个汉字多个原型，可以通过LVQ等聚类算法得到,神经网络法,可以用应用较少不算太成功,技术介绍,模式表示汉字分类模型学习与适应上下文处理,模型学习,概念模型库：每个字符的模型统计方法参数：原型特征向量，子空间，连接权值(ANN)可以通过经典的、成熟的统计学习的方法得到结构匹配结构化的字符/字根模型说明有些早期的系统会避免模型学习问题手工建模基于先验知识仔细设计的原型字符/字根模式配合在线更新式的模型学习：调整参数,模型学习与适应,常用方法原型学习HMM学习多原型学习结构化的学习StructuredLearning书写人适应WriterAdaptation,平均原型学习,学习目标建立每个字符/字根表示的“均值”和“方差”点序列，特征点，ARG几种学习模式批处理增量式学习在线学习,多原型学习,问题笔划原型/字根原型/字符原型单原型不能很好的覆盖各种可能的情况e.g.笔顺相关的识别方法：覆盖笔顺的差异多原型产生方法聚类算法批处理方式统计表示：成熟的统计聚类算法（特征向量）结构表示：聚类算法需要采用结构匹配代替传统聚类算法中的距离计算方法在线/增量式学习Online/incrementallearning初始单一原型新模式距离原型超过阈值增加一个原型,HMM学习,需要学习的参数初始概率，跳转概率，发射概率学习方法Baum-Welchalgorithm(EM过程)离散HMM状态可以人工划分或有外在的物理含义(e.g.笔划、字根）概率频数代替,结构化的学习,针对结构化的模型数据库关键是“共享”字根的学习问题这部分研究还不够深入例子将字根描述为一个矩形框内的线段在构造字符模型时，将其字根原型进行变换(缩放到实际大小，修改长宽比)在匹配输入模式时，一旦匹配上一个字根，则对该字根进行变形到字根“矩形框”，调整原有的字根模型,书写人适应,书写人适应的必要性书写习惯书写环境的变化适应模式批处理方式在线学习为什么需要通用模型？特定人训练数据严重不足,书写人无关的通用模型（多人数据训练结果）,特定书写人书写样本,特定书写人的字符模型,书写人适应,适应方法增加新的原型将输入模式增加为新原型，如果其k-NN原型中有一个属于错误类别将输入模式增加为新原型，如果其正确类别不在候选类别列表的第一位停用歧义原型Deactivateconfusingprototypes如果两个原型与输入模式相近，但不属同一类别，则将这两个原型停用改造现有原型当输入模式与最近原型有细微差别时，可适当修改该最近原型,输入模式,正确类别,错误类别,技术介绍,模式表示汉字分类模型学习与适应上下文处理,上下文处理,必要性和重要性语言上下文为识别提供了更多的约束例如：处埋处理字符的几何特征对分割有帮助位置，大小，长宽比提供了丰富的信息特别：分割与识别的互动难题：连写导致很难得到完全无歧义的分割,语言模型,n-1阶马尔科夫语言模型也称为n元语言模型p(W)=i=1dp(wi|wi-n+1,wi-1),d=|W|d：句子中的字/词个数二元语言模型BigramN=2，往前看一个字/词，e.g.“汉字识别”p(W)=i=1dp(wi|wi-1),d=|W|三元语言模型TrigramN=3