基于整体特征的数字笔记中多通道信息融合方法

基于多层次信息的连续手写中文的自适应分割方法基于多层次信息的连续手写中文的自适应分割方法 Adaptive Character Extraction from Continuous Handwriting Chinese Text Based on Multilevel Constrains 张习文，高秀娟，戴国忠 Zhang Xiwen，Gao Xiujuan，Dai Guozhong 中国科学院软件研究所，人机交互技术与智能信息处理实验室，北京，100080 Laboratory of Human-Computer Interaction and Intelligent Information Processing, Institute of Software, the Chinese Academy of Sciences, Beijing 100080 摘要：摘要：单字提取是连续手写中文识别的前提。本文给出了一种基于多层次信息的自适应单字提取方法。 以候选单字个数与字宽度方差之比为处理满意度。以行笔划为处理单元，先根据候选单字最小包围矩形 的水平间距构建多层次树表示，然后对最满意层中的每个候选单字进行多层次分析和自适应处理。如果 候选单字的宽度大于或小于字宽度的较大值或较小值，则遍历其下层子节点或上层父节点，进行候选单 字的分裂或合并，选择提高满意度的候选单字，同时更新字宽度阈值。测试结果表明该方法对连续手写 中文具有较好的分割效果。 Abstract It is prerequisite to extract character from the continuous handwriting Chinese text for its recognition. The paper proposes a novel approach to adaptively extracting character from the continuous handwriting Chinese text based on multilevel constrains. It aims to extract more characters with smaller character width standard deviation. The segmentation is feed into strokes by line. A tree is constructed to represent the multilevel combination of a line of strokes according to gaps between strokes or candidate characters. The candidate characters shared the same level, with the most satisfactory candidate characters, are refined to be merged or split under constrains of candidate characters of their lower levels or upper levels in the stroke tree. If one candidate characters width exceeds or is less than the bigger character width threshold or the smaller one, the candidate character will be split or merged. The candidate characters are identified as the correct ones if they increase the satisfaction of the segmentation result. The character width thresholds are updated together with character extraction. Many applications show that the approach is effective and robust for character extraction from continuous handwriting Chinese text. 关键词：关键词：连续手写中文，单字提取，树表示 Keywords continuous handwriting Chinese text, character extraction, tree representation 中图法分类号：中图法分类号：TP391 作者简介： 张习文，生于1971年，男，辽宁大连人，副研究员，主要研究方向为连续手写中文处理、多通道融 合、模式识别等。 通讯地址：北京市海淀区中关村南四街四号，中科院软件所人机交互技术与智能信息处理实验室 4 号楼 305 室 邮编：100080 联系电话E-mail: zxwiel_ 高秀娟，生于1977年，女，河北遵化人，实习研究员，主要研究方向为笔交互、模式识别、人工智 2 能等。 戴国忠，生于1944年，男，江苏无锡人，研究员，博士生导师，主要研究领域为人机交互技术，计 算机图形学等。 1 引言引言 就文本输入计算机而言，手写输入比键盘输入更符合人的纸笔写作习惯，更能保证自然、流畅的连 续书写方式。电子笔等手写设备日趋成熟1，已经积累了大量亟待识别的手写字符。单字提取是连续手写 中文识别不可逾越的必要前提。根据错误提取的单字并不能够获得正确的单字识别结果。单字识别错误 可以通过识别结果上下文处理2，3得以自动校正，却无法修正单字提取错误。因此，为了获得更好的连续 手写中文识别，单字提取必须具有很高的正确率。 汉字可以分解为偏旁部首，而偏旁部首又可以分解为笔划。在构成偏旁部首时，笔划具有多种组成 关系，例如，孤立关系，交叉关系，相交关系，相连关系等。在构成汉字时，偏旁部首也有多种组成关 系，例如，上下关系，上中下关系，左右关系，左中右关系，半包围关系，全包围关系等。在手写汉字 中，笔划、偏旁部首存在一定的随意性，字宽度和字间距都会有所变化，单字的笔划、偏旁部首可能离 得较远，而邻接汉字则可能离得较近。中文不仅包括复杂的汉字，还包括标点、符号、数字、字母、单 词等。这些都给手写中文分割带来了很大困难。 现有单字提取方法对笔划多层次信息的利用还远远不够，使得处理结果难尽人意。一行笔划在字宽 度、字间距上分别具有较高的一致性。因此，本文以行笔划为处理单元。行笔划可以根据候选单字间距 构建多层次的树表示，单字提取与同层邻接候选单字、上下层相关候选单字都有关联。笔划树为单字提 取提供了多层次信息。因而，针对连续手写中文分割，本文提出了一种基于多层次信息的自适应单字提 取方法。 2 相关工作回顾相关工作回顾 连续手写中文是由手写笔划组成的。一个手写笔划可能包含多个汉字笔划。手写笔划是指手写笔从 落下到抬起所记录的点坐标和其它信息。同汉字相比，标点、符号、数字、字母包含很少的笔划，结构 简单。日文、朝鲜文虽然与汉字有较多相似之处，都是多笔划结构，但数量较少，结构较简单。根据利 用的信息，现有单字提取方法（包括汉字、日文、朝鲜文、单词、字母、数字等）可以分为三种： （1）基于候选单字间距的方法 C. Hong 等4先采用若干字间距阈值进行连续手写中文分割，获得多个分割结果，然后根据字间距方 差从中选取最佳两组结果，在不提高字间距方差的前提下，合并邻近的候选单字，分裂较宽的候选单字， 最后利用识别结果提取单字。候选单字间距是最小包围矩形的水平距离。Lin Yu Tseng 等5也采用了最小 包围矩形计算字间距，先根据汉字结构知识初步合并笔划，最后利用动态规划方法进一步合并候选单字。 该方法能够处理多数情况下的重叠、粘连单字，但有时难以正确提取偏旁部首距离较远的单字、离得较 近的邻接单字。赵宇明等6也采用了最小包围矩形计算字间距，根据汉字笔划的结构知识逐步合并笔划， 从而提取单个汉字。该方法也可以部分地解决粘连汉字的单字提取问题。后两种方法设置了较多经验阈 值，例如，字宽度阈值，两个最小包围矩形重叠部分与较小最小包围矩形面积之比的阈值，因而自适应 性较低。 （2）基于候选单字时间间隔和空间距离融合信息的方法 Patrick Chiu 等7为构建多行笔划的多层次树表示提出了笔划距离，它融合了笔划的时间间隔和空间 距离（包括 x、y 两个方向的距离） 。该方法逐步合并距离最近的候选单字，形成树的不同层。该文处理 日文和数字，只是给出了笔划的树表示，却没有涉及如何从中自动提取单字（数字、日文） 。 （3）基于识别结果的方法 C. Hong 等4先根据候选单字间距提取单字，然后再加上候选单字识别结果构建候选单字网格，最后 根据候选单字识别得分、语言模型得分从候选单字网格中搜索最佳路径，获取单字提取结果。该文并没 3 有给出语言模型得分计算方法和候选单字搜索方法。 上述第三种方法在单字提取中引入了候选单字识别结果信息，利用了候选单字识别得分和语言模型 得分，而这要求识别器、语言模型具有很高的性能，单字识别错误、句子理解误差都会造成单字提取错 误。该方法虽然利用了多个层次信息进行单字提取，但并不充分，只是构建了五个层次，对自适应性考 虑得也较少。其余方法只是利用了单层次信息进行单字提取。 由于汉字结构的复杂性、中文手写的随意性，仅根据单层次信息难以判定单字提取结果的正误，还 必须综合多层次信息。因此，本文提出了基于多层次信息的自适应单字提取方法。在单字提取中，将行 笔划构建为多层次树表示，单字提取不仅与同层邻接候选单字有关，而且与上下层相关候选单字也有关， 从而较大地提高了单字提取的正确率。 3 基于候选单字间距构建行笔划的多层次树表示基于候选单字间距构建行笔划的多层次树表示 时间上较近的笔划在空间上也较近。而空间上较近的笔划在时间上不一定较近。单字是要求其笔划 在空间上较近的，而不必是时间上较近。但笔划空间较近则隐含了时间较近。因此，本文只利用候选单 字空间间距进行单字提取。 如果某个笔划与下一个笔划的水平间距很大，接近于已有笔划的宽度，则该笔划为当前行的最后一 个笔划，从而可以提取该行笔划。 构建行笔划树表示是根据候选单字间距进行的。根据单字的空间表示方法，单字（笔划）间距计算 方法可以分为 4 种8：（1）单字最小包围矩形之间的水平距离， （2）单字凸包之间的距离， R DH CH D （3）单字笔划之间的水平距离， （4）单字笔划之间的距离。本文根据候选单字最小包围矩形 str DH str D 的水平间距构建行笔划的树表示，该间距具有较好的单字提取效果，3.2 节给出了选择依据。 3.1 构建行笔划的树表示构建行笔划的树表示 笔划树的初始层是由笔划构成的，是树的叶子节点。笔划树是自下而上构建的。笔划树的新一层是 根据最高层的最小字间距构建的。合并字间距不大于的邻接候选单字，生成笔划树的新节点， min G min G 形成笔划树的新一层。重复上述过程，直到最高层只有一个候选单字为止。该算法的具体步骤如下所示。 步骤 1. 每个笔划作为一个候选单字，构建笔划树的初始层。 步骤 2. 如果笔划树最高层只有一个候选单字，则转到步骤 7。 步骤 3. 计算笔划树最高层的最小字间距。 min G 步骤 4. 取出笔划树最高层的候选单字 i，以候选单字 i 生成笔划树节点，的层索引为笔划树的总层数。 i N i N 步骤 5. While(与的字间距不大于) 1i N i N min G 合并进，增加的子节点索引，并设定该子节点的父节点索引。 1i N i N i N i=i+1。 步骤 6. 返回步骤 3。 步骤 7. 结束行笔划树表示的构建。 图 1.a 为一行连续手写中文，包括汉字、标点。图 1.b 为该行笔划的多层次树表示。 a 一行连续手写中文 4 b 行笔划的多层次树表示 c 单字提取过程 d 待分裂子节点及其重组结果 e 单字提取结果 图 1 基于笔划树的单字提取 行笔划树包含了不同字间距的候选单字提取结果，也包含了邻接层候选单字之间的关联。根据笔划 树可以进行自下而上的层次关联，获得从笔划、偏旁部首到候选单字的合并；反之，也可以进行自上而 下的层次关联，获得从候选单字到偏旁部首、笔划的拆分。 3.2 字间距计算方法的选择字间距计算方法的选择 字间距计算方法直接影响单字提取的质量和速度。如果笔划树中不存在正确的单字，则仅依靠树遍 历是不能提取正确的单字。字间距计算方法决定了笔划树的候选单字总数和正确单字数，相同的 t N c N 正确单字计为一个。如果笔划树具有较少的候选单字和较多的正确单字，则表明所采用的字间距计算方 法具有较好的性能。因而，字间距计算方法优先级 。 tc NNP/ 大量实验数据表明单字最小包围矩形水平距离的字间距计算方法能够为本文所提出的单字提取方法 提供最好的树表示。表 1 给出了采用前述四种不同字间距计算方法构建图 1.a 笔划树的性能比较。 表 1 四种字间距计算方法构建笔划树的性能比较 候选单字总数正确单字总数优先级P R DH11290.080 CH D9370.075 str DH14290.063 str D14080.057 4 基于笔划树的自适应单字提取方法基于笔划树的自适应单字提取方法 在笔划树中，同一层、相邻层的候选单字相互关联，这为基于多层次信息的单字提取提供了良好的 5 环境支持。如果笔划树的某层具有较多的候选单字，而且字宽度方差也较小，则将该层作为初始的候选 单字提取结果。笔划树最低层是以原始笔划为候选单字，具有最多的候选单字，最高层只有一个候选单 字，并不存在字宽度方差，这两层都不可能成为树最佳层，因此不予以考虑。以候选单字个数与字)(lN 宽度方差之比为单字提取结果的处理满意度。笔划树中具有最大的层)(lE)(/ )()(lSlNlG)(lG 设为候选单字提取的最佳层。对笔划树的第层中的每个候选单字进行多层次分析和自适应处理。 max L max L 字宽度可以分为三类：较小值、正常值、较大值，根据字宽度的中值来确定。对单字提取结果的字 宽度进行由小到大的排序，从小于中值的字宽度中计算中值作为字宽度的较小值，从大于中值的字宽度 中计算中值作为字宽度的较大值。位于较小值和较大值之间的字宽度为正常值。具有正常值的候选单字 被认为是正确单字。对大于字宽度较大值的候选单字则遍历笔划树中其下层子节点，进行分裂处理。而 对小于字宽度较小值的候选单字则遍历笔划树中其上层父节点，进行合并处理，但不与已标记为正确的 单字进行合并。在进行候选单字的分裂或合并时，选择提高满意度的候选单字，同时更新字宽度阈值。 最后获得具有最大满意度的单字提取结果。基于笔划树的自适应单字提取算法的具体步骤如下。 步骤 1. 计算笔划树最佳层候选单字的字宽度较大值、较小值、满意度。 max W min WG 步骤 2. 取出笔划树最佳层中的树节点。 i N 步骤 3. 如果树节点的字宽度为正常值，则该候选单字为正确单字，返回步骤 2。 i N 步骤 4. 如果树节点的字宽度小于，则取出其上层父节点（没有合并正确单字） ，直到满意度不再提高为 i N min WG 止，以最后的父节点为单字提取结果，更新、，i=i+1，返回步骤 2。 min W max WG 步骤 5. 如果树节点的字宽度大于，则取出其下层子节点的重组结果，直到满意度不再提高为止，以最 i N max WG 后子节点的重组结果为单字提取结果，更新、，i=i+1，返回步骤 2。 min W max WG 步骤 6. 结束单字提取，获得具有最大满意度的单字提取结果。 子节点重组是从左到右依次进行的。第 3 层第 2、5、9 个候选单字的子节点及其重组结果如图 1.d 所 示。对每个待分裂候选单字选择具有最大满意度的子节点重组结果。第 2、5 个候选单字并没有进行分裂。 第 9 个候选单字的分裂为两个新的候选单字，为第 3 个子节点重组结果，前一个单字为第 1 个子节点， 而后一个单字为第 2、3 子节点的组合。 图 1.c 为图 1.b 所示笔划树的单字提取过程。行笔划树的第 3 层为最佳层。最佳层的第 1、7、8 个候 选单字的字宽度为正常值，采用虚线最小包围矩形表示。最佳层的第 3、4、6、10 个候选单字的字宽度 小于字宽度的较小值，其中第 3、4 个候选单字合并为第 4 层的第 3 个单字，第 6、10 个候选单字并没有 进行合并，分别确认为第 7 层第 3 个、第 8 层第 4 个单字。最佳层的第 2、5、9 个候选单字的字宽度大 于字宽度的较大阈值，进行子节点重组处理，第 2、5 个候选单字并没有进行分裂，第 9 个候选单字的子 节点重组为两个新的单字。图 1.e 为图 1.a 的单字提取结果，正确提取了全部的 10 个单字。 5 性能评析性能评析 基于上述所提出的方法，作者采用 VC+开发了一个软件原型系统。该原型系统运行于装有 Windows 2000 的 PC 上。下面根据大量连续手写中文的分割结果及其定量分析给出本文所提出方法的性能评析。 5.1 实验结果实验结果 连续手写中文是采用北京中文之星数码科技有限公司的声位笔进行手写输入的9。该笔的空间分辨率 是 100dpi，书写采样速度是 60 点/秒。图 2 是多行连续手写中文，采用矩形包围框表示提取的单字，单字 提取正确率为 100%。 图 2 连续手写中文的单字提取结果 6 在原型系统上对大量连续手写中文进行了单字提取测试。表 2 给出了部分处理结果，包括单字提取 的正确率、欠合并率、过合并率、处理速度。处理速度是在具有 CPU 1.4GHz、RAM 192M 的 PC 上测试 的。 表 2 自适应单字提取方法的性能 单字数正确率 处理速度 （字/秒） 欠合并率过合并率 1（图 1）10100%1000%0% 2（图 2）20100%1020%0% 32494%984%2% 42795%1053%2% 53392%976%2% 5.2 实验结果评析实验结果评析 较大的正确率、较小的欠合并率、较小的过合并率表示较好的单字提取质量，较小的处理速度表示 较好的单字提取效率。在表 2 中，最低正确率是 92%，最高欠合并率是 6%，最高过合并率是 2%，这表 明了本文所提出的方法具有较好的单字提取质量。单字提取速度是每秒 100 个字，一张 A4 纸上通常可以 写下 1000 个字，用 10 秒钟即可处理完毕。 根据实验结果评价，本文所提出方法之所以具有较高的单字提取正确率主要是因为其具有以下三个 处理策略： （1）采用了行笔划的多层次树表示，为正确单字提取提供了充分的候选单字。 （2）在提取单字时，不仅利用了同一层邻接候选单字的信息，而且也利用了上下层相关候选单字的 信息，具有很强的自适应性。 （3）不必使用单字识别结果，降低了计算复杂性以及单字识别误差、句子理解偏差的不利影响。 6 结束语结束语 本文给出了一种基于多层次信息的连续手写中文的自适应分割方法。该方法以行笔划为处理单元， 字间距、字宽度的局部一致性更有保证，具有较好的适应性和健壮性。根据字间距逐步构建笔划树的各 个层，使得笔划树充分涵盖了更多的正确单字。遍历笔划树提取单字，利用了多个层次信息，显著提高 了单字提取的正确率。 测试结果分析表明，作者所提出方法是有效的、健壮的，能够较好地实现连续手写中文分割，较大 地提高了单字提取的正确率。该方法还应进一步改善，减少反馈计算，提高单字提取的质量和速度。在 该方法处理结果基础上，结合识别结果修改单字提取结果会取得更好的效果，这部分工作正在顺利进行 之中。 致谢本文得到了国家自然科学基金（60033020）、863 项目(2001AA114170) 和 973 项目 （2002CB312103）的资助，在此表示感谢。 参考文献参考文献 1L. Schomaker. From handwriting analysis to pen-computer applicationsJ. Electronics & Communication Engineering Journal, 1998, 6: 94 102. 2徐志明, 王晓龙, 张凯, 关毅. 联机手写体汉字识别后处理技术的研究J. 计算机研究与发展， 1999，36（5）：608 612. 3李元祥, 丁晓青, 吴佑寿. 一种基于字词结合的汉字识别上下文处理新方法J. 计算机研究与发展， 2002，39（7）：838 842. 4C. Hong, G. Loudon, Y. Wu, and R. Zitserman. Segmentation and recognition o