化学表达式的识别方法
王科俊，袁翠玲，刘昱
(哈尔滨工程大学 自动化学院，黑龙江 哈尔滨，150001)
摘要：对近年来国内外出现的化学表达式识别技术和方法进行了简单介绍和系统分类，分析了各种方法的优缺点，阐明了化学表达式识别技术所面临的挑战，并对未来化学表达式识别技术的发展方向进行了展望。
关键词：公式识别；化学表达式；联机识别；脱机识别
中图分类号：TG146.21 文献标志码：A 文章编号：1672-7207(2011)S1-0765-05
Recognition techniques of chemical formula
WANG Ke-jun, YUAN Cui-ling, LIU Yu
(School of Automation, Harbin Engineering University, Harbin 150001, China)
Abstract: A brief survey and a systematic classification of most recent techniques and approaches of chemical expression recognition are present. In addition, a comparison is made to find the strength and weakness of each approach. With the comparison result, the main challenges of chemical expression recognition are listed. Finally, a conclusion is made and some possible aspects of future development of chemical expression recognition are proposed.
Key words: formula recognition; chemical expression; on-line recognition; off-line recognition
化学表达式和数学公式一样，是自然科学领域广泛应用的一种表达式。针对化学表达式(结构)识别的研究始于20世纪80年代末，至今已有20年。1990至1996年，国外一些学者[1-4]以重用化学科技文献中的公式信息为目的，重点研究了印刷体化学文档中表达式的识别和理解方法。以Journal of Chemical Information and Computer Sciences为代表的杂志刊登了相关成果，其中的一些成功申请了美国专利。1997至2004年，相关研究较少，属于化学表达式识别研究的一个空白期。一方面由于化学表达式识别属模式识别的一个新兴范畴，相关领域对其需求不是很大；另一方面，对关键问题的处理方法无法达到很好的效果，使其发展陷入瓶颈期。2005年至今，德国和墨西哥的一些学者[5-8]继续保持了对印刷体化学公式识别的关注并发表了相关研究成果。随着笔式人机交互技术日趋成熟，国内一些研究人员[9-12]更多地将关注点转向了联机手写识别领域。目前，针对数学公式处理的研究已经趋于成熟，市场上也出现了相关产品，但是专门针对化学表达式识别的研究还远未成熟。
化学表达式识别从识别过程来说可分为联机识别(on-line)和脱机识别(off-line)，从识别对象来说又分为手写体识别和印刷体识别。联机化学表达式识别是指在数据板上手动输入化学表达式，由计算机进行实时识别处理。脱机化学表达式识别是指对一个预先排版好的文档进行处理，其识别包含化学表达式的定位和分析。脱机识别相对于联机识别来说，难度更大，因为联机识别拥有更多信息，如笔划顺序、点坐标的时间信息等。因此，联机识别技术常应用于手写体字符识别，而脱机识别技术则更多应用于印刷体字符识别。化学表达式从属性上可分为无机化学表达式和有机化学表达式。常见的无机化学表达式与数学公式类似，是一些字母、数字及简单的数学运算符的组合；而有机化学表达式除含有字母、数字外，还常有苯环、化学键等多种分子结构式。因而，针对无机化学表达式的识别可沿用数学公式识别技术，而有机化学表达式因其结构特性则要单独考虑，本文所说的化学表达式识别更多地是针对有机化学表达式而言的。
1 联机化学表达式的识别方法
联机化学表达式识别的研究对象是具有时序特征的笔迹序列，以点集形式记录了字符书写时各笔画的轨迹和起止。目前对联机化学表达式的识别研究方法较为单一，主要集中于基于笔画等时序信息，通过与模板样本匹配进行识别的方法。
姜映映等[9]提出了一个联机的手写化学表达式切分识别算法。其基本思想是：对最近输入的6个笔划进行切分，从中选择最有可能的切分结果，已经被接受的切分中的笔划不再参与切分。由于这种方法采用局部优化的方式，只需要对6个笔划进行切分，充分利用了化学领域知识，因此可以较好地满足在线识别的实时性要求。该算法被应用于一个基于语音和笔输入的多通道化学公式编辑系统中。YANG Ju-feng等[10]提出了一种基于SVM + HMM 的两级分类机制识别独立化学符号的在线手写识别方法。此算法从物质层和符号层入手识别，然后以公式的语义和语法规则协助理解用户的书写原意。他们为每个符号样本创建一个马尔科夫模型，并提取其11维的局部特征(标准化的垂直位置、标准化水平位置、位置一阶导数、位置二阶导数、弯曲、书写方向、宽高比，线性等)，该方法为联机手写化学公式重现和重用打下了基础。不足的是，基于联机手写的化学表达式识别问题面临许多困难[12-15]，主要有：
(1) 样本库的建立标准不一致工作量大。手写体化学表达式图形随意性很大，很难用科学的方法对它们加以描述，也很难提出合理的、可操作的规范对它们加以刻画，因此不同的研究人员制定的标准和要求也不尽相同。另外，样本库需人工建立，这样不仅工作量过大，也不便于库的维护，比如新规则的添加和已有规则的修正。
(2) 符号类别数大、相似符号多。化学符号识别是一个大规模的模式分类问题。可以说，符号数量大是造成化学表达式识别困难的最主要原因之一。同时，在化学符号集合中存在大量的相似符号组，如无机符号“C”、“c”、“(”，“O”、“o”、“0”，之间难以区分，有机环结构中存在更多相似形状。这些相似符号的存在，严重干扰了化学符号的分类处理。
(3) 结构复杂、存在二义性。化学表达式结构复杂，字符在不同位置代表着不同含义。化学表达式分为一维表达式、二维表达式和图形化表达式。特别是有机化学领域，物质通常由多个环、键、原子单元按不同的规则组合而成，很难通过简单的规律发现它们的相互关系。化学表达式中还存在二义性情况，如找到了一个符号“=”，需要判断它是一个化学公式生成符还是有机结构中的一条双键。
(4) 风格不一、书写随意。对于同一个化学符号，不同的人可能有不同的书写方法：笔划书写顺序不一致、书写速度有快有慢、一些直线型笔划经常变形和扭曲、笔划间的相对位置不确定、符号间的距离也大小不一、字符贴靠和重叠现象严重等等，这使得机器识别的难度加大。
2 脱机化学表达式的识别方法
脱机化学表达式的识别主要分为手写体和印刷体2个方向，它们的工作原理相似，识别系统的构成也大体上相同。但手写体的字形变化大，识别更为困难。在早年的研究中，一些研究人员针对化学手稿的计算机复现问题提出了基于手写体化学表达式识别的方法，但随着科技的进步，手写体文档已逐步被印刷体文档所取代，因而研究的焦点也转向了印刷体化学表达式识别。
2.1 脱机手写体化学表达式的识别
如何有效地解决手写体化学表达式的变形问题是脱机手写体化学表达式识别的核心问题之一[16]。解决这个问题有2思路，一是在“预处理”的环节中采取“矫形”措施，使化学表达式变得较为工整。另一种途径是精心选择识别特征，使同一种化学表达式不同样本之间的特征差别尽量小；而不同化学表达式之间的特征差别则尽量大，这与对印刷体化学表达式识别的要求是相同的。
Contreras等[1]提出了数字化分子结构识别。他们将处理流程划分为扫描、图形识别、字符识别、显示等4个模块。所有操作都是在二值图像上进行的，其技术路线是：化学键的外边界和内边界被区别对待并标注各自的顶点，在化学键的延伸方向上定位那些非线状的独立连通体为原子符号。识别这些字符后进一步定位各个子图中的环和多键。在Casey等[3]的研究中，他们利用尺寸和空间特征定位化学表达式，随后在一个中间的向量化阶段将线条和其他符号区分开。线条信息被映射到表征原子连接关系的结构式中，而原子符号通过化学图像规则和光学字符识别技术进行确认。最后，识别结果被输出到传统化学软件以供存储、检索、发布和建模之用。其中有机环符号提取是基于连通体的外接多边形和若干域值进行的。也就是说，对于连通体用外接凸起多边形替代外接矩形特征。这种多边形的边符合一定规范：如两两平行，使得所围有效面积尽量小并且尽量勾勒出连通体的外形等。识别阶段先寻找各种特征点构成特征向量，特征点包括：端点、多线交叉点、环结点、连接点；然后，根据不同单元所含向量的个数和关系识别图形结构。1994年，在前期工作的基础上，他们将研究成果连同程序代码申请了专利。Ramel等[17]提出一种识别手写化学式中图形的方法，并在300 dpi分辨率的小型离线设备中获得了93%的准确率。系统包含2步处理：文档全局感知和图形实体抽取。文档全局感知阶段包含图像的结构化重现功能并且赋予初始图像中所有形状精确的描述，具体处理步骤是识别手写文本、定位多重连接、多边形和相互关系，最后将获得的结果保存为向量形式。这个重现过程包含了图像理解各环节所需的大多数资源。图像理解过程则使用重现过程中得到的知识来替代原始图像进行工作。
2.2 脱机印刷体化学表达式识别
2.2.1 预处理
通常获得的待识别表达式图片大多含有噪声，而且没有进行过二值化、细化、归一化等处理，如果直接进行识别难度较大。因此，首先需要进行图像预处理的工作，其中二值化和图像矫正可以使用公式识别的方法。由于纸质文档的印刷质量、纸张的光洁程度、扫描仪的分辨率、二值化等因素的影响，扫描得到的图像中字符可能是粘连的。因此，粘连字符的分割是预处理过程中重要的一步[18]，以下介绍几种经典的粘连字符的分割方法：
(1) 基于细化的算法。文献[6]使用了一种基于背景细化的切分算法，作者观察到细化后的背景能够提供构造切分路径的有用信息，即背景上的特征点往往指向粘连位置或是可以成为切分路径的起始点。该算法分为几个步骤：细化背景，在细化后的背景上提取特征点，包括叉点、端点和角点；构造候选切分路径，即通过搜索来连接背景上的一些特征点，从而构成从图像的顶部延伸到底部的所有路径；对候选路径进行评价，选择最佳切分路径。
(2) 基于结构特征的算法。在文献[19]中，特征点被具体化为重要轮廓点，包含拐角点、局部极小点、局部极大点和延伸凹角处的直笔画得到的潜在路径退出点算法，从这些特征点中选择一对作为切分路径的进入点和退出点。选择时考虑的因素有：局部极小-极大点对优先；拐角点优先；点间的距离；轮廓变化的剧烈程度；极小-极大点对间的水平距离；一个极值点到另一个极值点的距离和离图像左边最远的 距离。
(3) 储水区算法。文献[20]使用储水区的概念来切分粘连字符。储水区被定义为从粘连字符上方和下方倒入水而形成的储水区域，并根据其位置分为：上储水区、中储水区和底储水区。储水区算法可以根据储水区域的大小和位置确定字符的粘连位置，并通过分析储水区的边界、粘连位置和粘连字符的形态特征来确定最佳切分点，结合结构形态特征构造出切分路径。
2.2.2 化学表达式特征的提取
在印刷体文档中的化学表达式一般以2种情况存在：内嵌公式行和独立公式行。因为化学表达式与普通文字的区别很大，要想正确处理表达式，就必须先从原始的文档图像中找到化学表达式所在的区域。化学表达式与普通文本间的差异见表1。
表1 化学表达式与普通文本的差异
Table 1 Differences between chemical expression and ordinary text
Contreras等[1]从二值图像的左上方开始，由左至右逐行扫描，扫描到第1个像素点后对其标记，之后采用逆时针的搜索算法搜素图像轮廓，直到回到起始像素点后停止。每个轮廓像素点的坐标会以2?n的矩阵形式保存，这里n表示轮廓线上像素点的个数。作者选取了300 dpi的扫描设备，若n＞300，则判断图形为化学结构图；若n≤300，则判断为一般字符做后续处理。
McDaniel等[2]采用一种全局搜索法——测试所有可能存在化学键的特征子集即寻找虚线和楔形线(V形线)。通常来讲，此方法能识别出至少由2条线段构成的虚线。这其中包括大多数两线中一线联接到其他节点的情况。通过寻找这2类图形并把它们转换成单独的部分，从而代替不相关的矩阵，这样可以简化后期处理过程。
2.2.3 化学表达式字符的识别
公式中的单字符及字符串可采用常用的字符识别方法进行处理。经过多年的研究，人们已经提出了许多符号特征，并将其归纳为局部特征、全局特征，结构特征、统计特征等类别[21]。以下介绍2种字符识别中常见的算法，即基于统计特征的字符识别及基于结构特征的字符识别等。
(1) 基于统计特征字符识别。Contreras等[1]介绍了他们的程序，所有操作都是在二值图像上进行的。其技术路线是：化学键的外边界和内边界被区别对待并标注各自的顶点，在化学键的延伸方向上定位那些非线状的独立连通体为原子符号。识别这些字符后进一步定位各个子图中的环和多键。他们还提供了文本切分和识别的流程，不考虑一些特殊情况，单字符识别率达到了99%。McDaniel等[2]尝试使用Zernike矩阵、傅里叶描述、Gabor变换、坐标变换和Hought变换来解决字符的旋转变形和尺寸变换问题。引入尺寸不变性可以削减固有OCR中的特征维度，规范化后的字符会通过多层神经网络来进行分类，OCR系统最后的识别率在96%左右。
(2) 基于结构特征字符的识别。Algorri等[5]提出的字符和符号的辨识由支持向量机算法来完成。OCR能将由字符组成的化学成分分类，并去除那些模块结构构成的部分。每当正确识别相关部分失败时，支持向量机算法可以动态地增加训练集，从而避免分类错误的反复出现。此算法可以训练OCR来辨识不同尺寸、字体的字母、数字以及符号，甚至有些是旋转变形的。
2.2.4 化学表达式结构分析模块
在处理印刷体化学表达式中，符号识别和结构分析两者的关系可概括为以下3点：(l)结构分析模块负责将一条完整公式划分为若干独立的符号并交给识别模块处理；(2)识别结果作为公式辨识的基础供分析和理解模块调用；(3)公式的版面结构和语法关系是检查和校验符号识别结果的依据。
利用投影法对图像点阵区进行X轴和Y轴方向上的投影，得到横向和纵向的采样点的统计直方图。字符点阵区域在直方图上呈现出波峰状，而字符间的空隙在直方图上呈现出波谷状。如果符号间没有发生粘连，则间隔区域在垂直投影方向上具有非常小的厚度，处理时可将局部极小投影值点作为候选切分点。该算法速度快，实现简单；但有如下不足：只适应很少粘连的情况，1个断裂的字符会被切分成几个字符，不适应字符交叠的情况，所以该算法比较适合于粗切分。
ZHANG等[11]以字符属性作为表达式版面结构分析的起点，定义公式中与被分析字符具有逻辑关系的下一个字符可能出现的范围为“域”的概念。将字符域分为上部域、下部域、上标域、下标域、包含域、后继域的同时，也将字符划分为g，e，d，r，o，n这6种类型。
2.2.5 识别结果的输出
识别结果的输出是决定化学表达式复用的关键。Filippov等[7]通过C++语言编写程序，将最后的识别结果以SMILES或SDF格式的分子结构图表示。其中，SDF文件格式是最常见的化学分子文件格式，可以用DS ViewerPro软件打开。SMILES(简化分子线性输入规范)是一种用ASCII字符串明确描述分子结构的规范，它可以被大多数分子编辑软件导入并转换成二维图形或分子的三维模型。
与之类似，Algorri等[5]也选用了标准SDF格式的化学表格文件，它包含了输入图像中所有描述分子的化学信息。SDF文件可以输入给大多数化学软件，并且可以比较容易地从文档内容中直接提取图像，便于满足广泛的应用和需求。Casey等[3]选取了MDL MOLFILE作为化学图形表示格式，他们书写了几种转换程序以便于将MOLFILE作为输入格式提供给其他应用。
3 总结与展望
首先对化学表达式的定义及分类进行了系统介绍，随后又对近年来涌现的各种解决化学表达式识别的方法进行分类，详细分析了各种算法并归纳总结了它们的优缺点，以便读者进一步了解化学表达式识别问题的研究进展。最后，分节介绍了联机化学表达式与脱机化学表达式的识别方法及具体识别流程，并指出了其适用范围。目前，化学表达式识别仍然面临着很多挑战，比如，手写体中的“连笔”、相似符号的处理、二义性的判断等问题以及印刷体中特征库的建立、纠错与后处理等问题，都亟待解决。这些问题的存在, 使得对化学表达式识别方法的研究还任重而道远，未来化学表达式识别研究也将围绕着这些问题展开。相信随着公式识别、图像处理等相关学科的向前发展，化学表达式识别问题也将逐步得到解决。
参考文献：
[1] Contreras M L, Allendes C, Alvarez L T, et al. Computational percepion and recognition of digitized molecular structures[J]. Journal of Chemical Information & Computer Sciences, 1990, 30(3): 302-307.
[2] McDaniel J R, Balmuth J R. Kekule: OCR-optical chemical (structure) recognition[J]. Journal of Chemical Information & Computer Sciences, 1992, 32: 373-378.
[3] Casey R, Boyer S, Healy P, Miller A, et al. Optical recognition of chemical graphics[C]//IEEE ICDAR. Tsukuba Science City: IEEE, 1993: 627-631.
[4] Ibison P, Jacquot M, Kam F, et al. Chemical literature data extraction: The CLIDE project[J]. Journal of Chemical Information & Computer Sciences, 1993, 33: 338-344.
[5] Algorri M E, Zimmermann M, Christoph M, et al. Reconstruction of chemical molecules from images[C]//IEEE EMBS. Lyon: IEEE, 2007: 23-26.
[6] Algorri M E, Zimmermann M, Apitius M H, et al. Automatic recognition of chemical images[C]//Eighth Mexican International Conference on Current Trends in Computer Science. Michoacan, 2007: 41.
[7] Filippov I V, Nicklaus M C. Optical structure recognition software to recover chemical information: OSRA, an open source solution[J]. Journal of Chemical Information & Computer Sciences, 2009, 49: 740-743.
[8] Valko A T, Johnson A P. CLiDE Pro: The latest generation of CLiDE, a tool for optical chemical structure recognition[J]. Journal of Chemical Information & Modeling, 2009, 49: 780-787.
[9] 姜映映, 王绪刚, 敖翔, 等. 手写化学公式的在线切分识别[C]//第二届中国人机交互学术会议论文集. 杭州, 2006: 111-116.
JIANG Ying-ying, WANG Xu-gang, AO Xiang, et al. Online recognition of handwritten chemical formula[C]//CHCI’06. Hangzhou, 2006: 111-116.
[10] YANG Ju-feng, SHI Guang-shun, WANG Qing-ren. Recognition of on-line handwritten chemical expression[C]//Proceedings of International Joint Conference on Neuralnetworks. Beijing, 2008: 2360-2365.
[11] ZHANG Yang, SHI Guang-shun, YANG Ju-feng. HMM-based online recognition of handwritten chemical symbols[C]//10th International Conference on Document Analysis and Recognition. 2009.
[12] 杨巨峰. 联机手写化学公式处理关键问题研究[D]. 天津: 南开大学, 2009: 14-15.
YANG Ju-feng. The key issues dealing with the chemical formula of online handwritten[D]. Tianjin: Nankai University, 2009: 14-15.
[13] 高学. 基于运动图像的手写汉字识别研究[D]. 广州: 华南理工大学, 2003.
GAO Xue. Research on video based handwritten Chinese character recognition[D]. Guangzhou: South China University of Technology, 2003.
[14] 单宏浩. 基于笔输入的数学公式编辑器[D]. 北京: 中国科学院软件研究所, 2001.
SHAN Hong-hao. Pen-based mathematical formula editor[D]. Beijing: Chinese Academy of Sciences, 2001.
[15] 冯海波, 田丰, 奕尚敏, 等. 交互技术在手写公式编辑中的应用[J]. 计算机辅助设计与图形学学报, 2003, 15(11): 1437-l442.
FENG Hai-bo, TIAN Feng, YI Shang-min, et al. Application of interactive techniques to handwritten mathematics editing[J]. Journal of Computer Aided Design & Computer Graphics, 2003, 15(11): 1437-l442.
[16] 吴佑寿. 教电脑识字——浅谈汉字识别[R]. 北京: 清华大学出版社, 2006: 43-44.
WU You-shou. Teach computer literacy—Discussion Chinese character recognition[M]. Beijing: Tsinghua University Press, 2006: 43-44.
[17] Ramel J, Boissier G, Emptoz H. Automatic reading of handwritten chemical formulas from a structural representation of the image[C]//IEEE ICDAR. Bangalore, 1999: 83-86.
[18] 吴俊飞. 基于特征字符的印刷体公式识别研究[D].哈尔滨: 哈尔滨工程大学, 2006: 29-32.
WU Jun-fei. Study on recognition of printed mathematical expression based on characteristic character[D]. Harbin: Harbin Engineering University, 2006: 29-32.
[19] Strathy N W, Suen C Y, Kryzak A. Segmentation of handwritten digitsusing contour features[C]//IEEE ICDAR. Tsukuba Science City: IEEE, 1993: 577- 580.
[20] Palu, Belad A, Choisy C. Touching numeral segmentation using water reservoir concept[J]. Pattern Recognition Letters, 2003, 24: 261-272.
[21] Rusu A, Govindaraju V. A flexible recognition engine for complex on-line handwritten character recognition[C]// Proceedings of the 8th International Conference on Document Analysis and Recognition. Seoul: IEEE, 2005: 967-970.
(编辑 杨华)
收稿日期：2011-04-15；修回日期：2011-06-15
通信作者：王科俊(1962-)，男，吉林省吉林人，教授，博士生导师，从事生物特征识别与智能监控、神经网络、计算生物信息学等研究；电话：13936459728；E-mail：wangkejun@hrbeu.edu.cn
