手写连笔王

一种手写环状化学结构式的识别方法

中国科技论文在线

////0>.

#一种手写环状化学结构式的识别方法*

杨巨峰

(南开大学计算机与控制工程学院)

5摘要:化学式可以被书写成分子式和结构式两种,其中分子式的识别比较

简单,而结构式的理解却比较困

难且具有挑战性,因为需要结合二维空间的复杂结构的深入处理和精确的

文字识别。在化学结构式中,昀

为复杂的结构就是环状结构,其形式多样,常与字母数字混在一起,较难处

理。为了解决这类问题,如文

中所示,我们综合运用OCR技术、动态规划以及图论的方法,开发出了一

个包含键线识别、符号识别、环

提取与化学结构图构建等几个模块的便捷有效的环状结构识别程序,并在大

量数据的实验中得到了可观的

10识别率。

关键词:模式识别;联机手写;环状化学结构

中图分类号:TP391.4

Anovelmethodforrecognitionofhandwrittenchemical

15ringstructures

YANGJufeng

CollegeofComputerandControlEngineering,NankaiUniversity

Abstract:Chemicalexpressioncanbedividedintomolecular

easytosolvetheproblemofrecognizingmolecularexpressionbased

r,the

20understandingofstructureismoredifficultandchallenging

becausethattheunderstandingneednot

onlytheaccuratetextrecognitionbutalsothethoroughtreatment

ofcomplexstructureonthe

llkindsofstructureexpression,the

mostcomplexoneisring

structure,whichhassundrytypeandoftenmixedwithtext,soitis

e

theproblem,thispaperdiscussedamethodcombinedwithOCR,dynamic

programmingand

25graph,designedaringstructurerecognitionprogram,which

containsbondlinedetection,text

recognition,

experimentoflargeamountof

data,weobtainedconsiderablerecognitionrateKeywords:Pattern

recognition;OnlineHandwriting;Ringstructure

300引言

早在上世纪八十年代末和九十年代初,在世界范围内就已经在印刷体化学

式识别方面取

[1]

得了一定的成就,在这期间一些商业的印刷体化学式识别软件被开发出

来,Kekule和

[2][3]

CLiDE是其中的代表;同时也提出了一些化学式的储存结构,比如SMILES。

在之前的基础上,近年来有关化学式识别的研究进展迅速,这一大类问题

可以被分为印

35刷体化学式识别和手写体化学式识别两大类,印刷体化学式主要是指文

档中按照同一印刷规

格印制的化学式图像,这种处理的突破口主要是来自图像中像素的分析,文

献[4]描述了一

种对扫描的印刷体化学结构进行识别的原型系统;文献[5]提出了一种印刷

体化学结构的识

别方法,引入了重构的概念;文献[6]则另辟蹊径,介绍了一种使用字符提

取、端点提取和

图形组合的方法识别扫描的或者电子版的印刷体化学符号的技术,这意味

着有关化学式识别

40的研究已经在复杂化和结构多元化的道路上前行着。另一方面,对手写

体化学式识别的研究

也越来越受到重视,文献[7]描述了识别脱机手写化学结构中多边形结构、

长链结构以及字

基金项目:高等学校博士学科点专项科研基金资助课题(202)

作者简介:杨巨峰(1980-),男,副教授,主要研究方向:图像处理、计算机视

觉.E-mail:

yangjufeng@//.

-1-中国科技论文在线

////.

符的方法,文献[8]提出了一种徒手画的线条结构的结构化表示法,可以

应用到脱机手写化

学式的识别中去。昀近十年,联机手写逐渐变成研究热点,联机手写能够

将用户手写的轨迹

变成二维空间的点和时间的序列,使符号特征更容易被提取,但由于手写

的随意性,其困难

45程度有所提高。Tenneson等人开发出了一套成熟的应用于教学的手写

化学结构识别软件

[9]

ChemPad,它能识别出化学结构并将其转换为3d呈现,它的缺点在于识

别符号范围较小,

且比较简单,而且对书写限制较大,只能识别一笔写成的结构。文献[10]

提出了一种通过滑

动窗口算法分离单个结构的方法,隐含C、H原子的寻找以及苯环简写形式

中“O”与氧元素

符号的区别也被特别地指出来了。文献[11]在符号识别阶段运用了SVM和

弹性匹配的组合

50算法,达到了实时的效果,并在结构分析阶段提出了化学表达式树的概

念。

近几年内,随着计算机处理能力的不断提高和识别算法的不断成熟,世界

范围内对化学

式识别研究的目光开始投向结构复杂的环状化学结构的识别,但迄今为止,

在这方面的研究

依然较少,并且大多数环状化学结构识别的研究多是零散地出现,没有成为

研究的重点。

文献[7]介绍了多边形的提取,指出了多边形事实上就是闭合的长链,提出

了一种递归

55地搜索长链的策略。文献[12]专门介绍了化学环的识别,他将化学环

分成多个种类,并采用

神经网络的方式识别它们,但是这种方法并没有考虑到化学环与其他结构混

在一起的情况,

具有一定的局限性。文献[10]也出现了环状结构的识别,但这篇文章仅仅

将环结构看作化学

键的组合,没有考虑到手写时连笔成环的情况。文献[13]对于以上的问

题则采用了切割的方

式,将连笔链切割成单键,但这样便遗弃了环状结构的概念,失去了整体感。

60本文将环状结构化学式的识别作为研究重点,提出一种有效的结构分析

和识别方法,实

验结果证明该方法可以比较准确地识别大多数字符/环混合结构。

1研究对象与系统模型

1.1有机环状化学结构式

化学式是指能够准确表达化学物质的表达式,主要分为离子式、分子式和结

构式三种,

65其中离子式昀为复杂,但使用很少;分子式比较简单,但较难准确表示

有机化学结构;所以,

在有机物的表示上,化学结构式是一种被普遍接受的形式。

化学结构式进一步细分为凯库勒结构式、简化结构式和键线式三种。在凯

库勒结构式中,

原子间形成的所有化学键都必须用一条短直线代表,这样表示有机物往往

费时费力,所以人

们就将凯库勒结构式进行了一些约定俗成的简化,形成了简化的结构式表

示法。在简化结构

70式中,原子间的共价键会被经常性的省略,原子右下角的数字下标表示

原子个数,原子按联

系紧密程度以一定约定俗成的规律排列,一些特定的结构往往会固定一种

简写方式,如醛基

被简写为CHO,羧基被简写为COOH。而对于一些较为简单的结构,甚至有

时候会直接将

原子和其他化学键略去,只留下碳原子之间的化学键,这样的表达方式昀

为简单,被称作键

线式。

75凯库勒结构式、简化结构式和键线式之间并没有特别严格的界限,更多

情况下,为了突

出或者简化有机物某一部分的结构,凯库勒结构式、简化结构式和键线式

经常同时出现在一

个化学结构式中。

本文所探讨的识别对象是化学式,其中包含了上述三种表达方式,由于凯库

勒结构式、

简化结构式和键线式的表示方法大不一样,这就使得在识别化学结构时不

能拘泥于某一种方

80法;另外,由于并没有办法预知书写者将要使用哪种表示方法,这个

特点使得识别的难度大

-2-中国科技论文在线

////.

大提高。

按照碳架的不同,有机化合物可以被分为开链化合物、碳环化合物和杂环化

合物三种,

其中环状有机物就是指碳环化合物和杂环化合物两种,开链化合物不在本文

讨论范围内。

1.2系统模型

85环状化学结构式的识别具有相当的挑战性,需要设计一个成型的系统模

型来处理获得的

手写数据,再将手写数据识别成化学结构,图1所展示的是本文设计的

系统框架和处理流程。图1系统模型

90Fig.1SystemModel

如前所述,联机手写时用户输入的手写信息被采集到内存中以特定形式储

存,由于此时

所采集的信息还不便于以后的处理,所以,首先要进行预处理,这其中包

括点的坐标系转化、

点的增删和储存格式的转变等操作,经过这些操作之后,之后的识别部分将

变得更加便利。

95预处理之后的数据将从多个角度进行识别操作,如图1所示,首先进

行的是针对化学结

构式中基本要素的识别,这其中包括直线键的识别和符号的识别,直线的识

别相对较简单,

也相对较准确,这一步将所有笔划分成两部分,一部分被识别为直线,而

另一部分识别系统

不认为它是直线,这个识别结果对之后的工作有很大的辅助作用。之后进

行的是符号的识别,

这一步将所有笔划组成一个组,每个组都会被初步地认为是一个化学元素。

100接下来是组合结构的识别,通过笔划的拐点检测和笔划间的相交

关系可以找出折线结

构,而首尾相连的闭合结构就可以被认为是化学环,这一步同样将所有笔

划组成一个组,其

中的每个组被看做是折线或者环结构。

经过识别过程,我们已经获得了对所有笔划的三组识别结果,分别是直线

识别结果,符

号识别结果和组合结构识别结果。在结果整合过程中,我们将通过特定规

则将三组结果整合

105在一起,整体地确定出原子、键、原子数之间的关系,初步得出整个

化学结构。但是,一般

-3-中国科技论文在线

////.

来说,结果整合过程所得到的化学结构并不是完整的,因为在有机结构式

的书写中,各种要

素的省略是很正常的现象。所以,接下来我们要对这些隐含的部分进行补

全工作,主要的依

据就是有机化学知识和用户书写的空间结构。在这其间,若识别出的结构

有与化学知识和规

则矛盾的地方,则应该返回识别和整合部分对识别结果进行微调,这就是回

馈纠错部分。

110昀后是依据化学图数据结构和绘图API对结果进行重现,主要是将识

别结果的结构图

呈现在用户面前,完成整个流程。

2识别流程

2.1预处理

Microsoft提供的SDK能从手写板的电子笔或者鼠标移动中收集用户的手

写数据,这些

115初始数据保存在点?笔划?笔划组的数据结构中,还不能完全与之后的

操作进行对接,所以

在对数据进行识别处理之前,首先要对其进行预处理。由SDK所提供的笔划

信息中只有笔

划的外接矩形,而在识别阶段,有许多笔划信息需要被用到,比如笔划长

度、笔划中心、外

接矩形周长和面积等,这些参数都需要我们事先计算好并将它们保存到特定

的数据结构中。

另外,由于用户手写时有时会快速地拖动画笔,使得点序列中采集的点数

过少,达不到

120识别的要求;相反,用户的书写较为迟滞时,点序列中的点又会过处

理。具体的规则是若点

序列中时间相邻的两个点距离过近,比如当距离小于3个像素点时,就

删去时间靠后的一个

点;若点序列中时间相邻的两个点距离过远,比如当距离大于15个像素点

时,就在两个点

之间插入一个点,该点的坐标是两个点的中点,时间则是另两个点时间的平

均值。

用户在书写时经常会因为疏忽或者习惯在界面上画上一些无意义的小点,

在下一步数据

125处理之前需要找出并删去这些多余的小笔划,若不这样做,识别引擎

对这些笔划极易发生错

误识别并进而影响整体的识别。我们将那些x轴投影和y轴投影均小于

一定值的或者点序列

中点的个数小于一定值的笔划认为是多余的笔划,并对这些笔划进行删除操

作。

图2展示了预处理中的点序列距离调整和删除多余笔划的操作。

130图2预处理

Fig.2Pre-processing

2.2基本要素识别

在环状化学结构式中,直线比较多,也很重要。原子之间的键基本都是直

线,环结构也

-4-中国科技论文在线

////.

可以看作是几条直线首尾相连的结构,所以,准确检测出直线的位置和信

息十分重要也十分

135必要。

针对直线检测,本文分别测试了两种方法,第一种是基于freeman链码的

直线检测算法,

这种成熟的算法在基于像素点灰度图的脱机手写识别中被广泛运用,效果

也很好。但是在解

决联机手写问题时,因为联机手写的点序列是离散的,并不像脱机手写那

样是一个一个挨着

的灰度像素点,所以计算链码的方法显得不那么合适。本文实际采用的是

第二种方法,也就

140是利用昀小二乘法对点序列进行相应的计算,并昀终判定点序列是否

能近似地形成一条直线

轨迹。这种算法比较适合联机手写的特点,在实验之后,识别正确率也比较

高。

昀小二乘法是一种在数学上判断一组平面坐标上的点能否近似地组成一条

直线的方法,

通过昀小化误差的平方和寻找数据的昀佳直线函数匹配,通过使得待检测

点序列与实际点序

列之间误差的平方和降到昀小,得出昀为拟合的直线。

145昀小二乘法存在一些不足之处,首先当k趋近于无穷时,也就是笔

划趋近垂直时,昀小

二乘法容易出现错误,甚至是无法处理;另外当点序列中的点比较少时,

昀小二乘法发生错

误的情况也比较多。基于以上不足,本文对昀小二乘法进行了补充改进,

在进行昀小二乘法

之前,先依据笔划的外接矩形的长宽比将近似垂直或者水平的笔划识别出

来,提升识别精度。

对于被认为是直线的笔划,我们还要计算出它们的起始点和终止点等相关

参数,将识别

150结果和这些参数储存到特定数据结构中,为下面的操作做准备。

本文所要识别的符号是指化学结构式中经常出现的化学符号,主要包括表

示原子和原子

数的字母和数字。如果能够准确地找出化学结构中符号并进行准确地识别,

化学结构的骨架

就已经搭好了,所以说,符号的识别也是非常重要的。在这里,我们使用

已有的字母和数字

识别器进行辅助识别,在笔划组合的问题上,我们采用的是动态规划的思

想,动态地找出某

155一个符号的昀贴切的笔划组合。

在昀初的版本中,符号识别的范围仅包含C、O、H、N、P、S、Cl、F

以及数字1-4,

我们知道当人们在书写这类符号时,有如下几个特点,首先,绝大多数情

况下,不会将一个

笔划分开来写,更多的情况下,只会将几个笔划连起来写。其次,绝大多

数情况下,一个单

个符号的几个笔划总是连在一起写的,不会出现写了“H”的前两笔之后又

写一个“C”昀后再

160补上“H”中昀后一笔的情况。根据以上手写特点,我们可以设计一

个基于动态规划和微软手

写识别库的单个符号识别算法,对每一种符号进行检测和识别。

首先,我们将这些符号按照笔划数目分为一笔(C,O,S,2,3)、两笔

(P,Cl,4)、

三笔(H,N,F)三类。对于一个笔划的符号,我们定义获取识别置信度

(GetConfidence)

的操作,如GetConfidence“C”,stroke1表示stroke1这个笔划识别结

果为“C”的置信程度,这

165个操作可以通过遍历识别结果的候选队列中的相应数据来获得,

它的取值范围是从0到

100%,按照置信度结果排序,并且剔除掉置信水平过低的结果,我们可

以得到一笔的符号

的初步识别结果。对于多个笔划的符号(两笔和三笔),借助动态转移方程求

得置信度。

2.3组合结构识别

组合结构是指化学结构中有多个单一结构组合而成的结构,在此处主要是

指键线式中常

170见的多个单双键首尾相连形成的折线和环结构。环的检测也是本文研

究的重中之重,本文将

通过拐点检测和基于空间位置关系的滑动窗口算法找出折线和环结构。

本文所使用的拐点检测算法是基于曲率变化的算法,曲率是指曲线上一点

的切线方向对

弧长的转动率,通过微分定义,表明的是曲线的弯曲程度,曲率越大的点,

曲线在该点的弯

-5-中国科技论文在线

////.

曲程度也就越大,也就是说当某点曲率超过一定值的时候,可以认为该点

是曲线的一个拐点。

175由于本文所研究的笔划都是离散的点组成的序列,所以不可能通过微

分求得精确的每个

点的曲率值,本文对这种情况作了分析,认为可以通过比值求得近似的曲

率值,该值能够较

好地判定拐点的问题。对每三个连续的点,我们计算出它们角度的变化值,

并用这个角度比

上前两个点之间的距离,就能得出在前两个点之间的近似的曲率。

我们通过以上的计算可以近似地得到点曲率,如果在某一点这个曲率的绝

对值大于事先

180设好的阈值,那么,系统将会初步判定曲线这个点转过了较大的角度,

也就是说,这个点是

一个拐点。

在找出所有疑似拐点之后,我们需要进一步地操作,由于在某一个拐点处,

曲率总是会

在几个连续的点都有超过阈值的现象,所以对那些相隔比较近的疑似拐点,

我们要对其进行

缩减,方法是在两个或多个相近的意思拐点中找到它们的中心点,并用这

个中心点替代疑似

185拐点。至此,我们已经找到了拐点,接下来,系统会根据计算出来的

曲率值,计算出每个拐

点转动的角度和方向,储存起来。

接下来我们依据拐点检测的结果进行折线和环的检测,与符号的书写不同,

折线和环的

书写也有自己的特点,人们在书写组合结构时风格多变,有的人喜欢一笔

画完,有的人喜欢

一个一个键画出,也有的人并不固定;有的人喜欢先画环再画环旁边的化

学元素,而另外的

190人则相反,这些特点给了组合结构的识别很大的难度,这里我们主要

利用空间位置关系对笔

划进行组合,以期找到折线和环的昀优结果。

第一步,我们对所有笔划进行遍历,找出一笔含拐点较多的笔划,如果这

个笔划首尾闭

合,则认为这个笔划是环,如果没有闭合,则暂且认为这个笔划是折线,

(在这里,闭合的

定义是笔划的首尾两点距离不超过5个像素)如果不是闭合但是却相交了,

则可以认为这个

195笔划是一个环加一个折线的组合。然后,我们将所有识别为环的笔划移

到识别结果队列中,

将识别为环和折线组合的笔划进行切割,将环部分移入识别队列。

第二步,对于还保留下来的笔划,分别在空间找寻能与它们首尾相连的一

笔画成的笔划,

并对它们进行合并,合并时,将两个笔划看做一个笔划,计算他们交点转

过的角度,如果大

于阈值,则将交点记录为拐点,合并之后,对笔划信息(首尾点坐标,首

尾角度等)进行修

200正,昀后对新合并的笔划进行是否为环的判定,重复之前的操作,一

笔一笔地进行合并,直

至再也找不出能够合并的笔划,将在这个过程中识别出的环识别结构储存,

剩下的不闭合的

单笔或多笔结构如果含有拐点则被当作折线进行储存。

2.4结果整合

在之前的步骤中,我们已经得到了化学结构式中各个部分的识别结果,之

后的工作则是

205对这些识别结果进行整合,我们首先需要为整合过程设计一定的规范,

让识别结果能够被整

合到特定的结构中去,为此,我们设计了一种化学图结构来储存整合的结

果。化学图的设计

基于无向图,我们在无向图的基础上进行了改进,使之更加适合表达环状化

学式。

对于基本符号,我们设计了原子结点,它能保存原子的位置信息、原子的

种类、原子个

数以及与该原子有联系的化学键;我们还设计了键结构来代替无向图中的

边,该结构的左右

210指针分别指向相连的两个原子,并且还储存了键两端的位置信息。对

于组合结构,我们设计

了环结点和折线结点,其中储存着组合结构的碳原子个数、外接矩形等位

置信息以及碳原子

数组。

设计好化学图之后,我们所需要做的工作就是根据之前识别的结果将各种

信息填入化学

-6-中国科技论文在线

////.

图中,完成化学图的构建。首先,因为一般认为组合结构要明显地大于单

个结构,所以我们

215根据外接矩形大小区分出组合结构和单个结构,然后我们遍历所有识

别结果,如果是环,我

们则建立一个环结点,并为环上每一个拐点建立一个碳原子结点,然后将

碳原子结点依次用

键连接起来;如果是字母,则在相应位置建立一个该字母代表的原子结点;

如果是数字,则

在空间中找寻左上方昀近的原子结点,将该原子结点的原子数修改成该数

字结果;如果是直

线,则在空间中分别找寻直线首尾两点昀近的原子结点,然后用键将它们相

连。

220至此,化学图已经被初步地构建了,图3所示的是化学图的示意图,

其中黑色的圆形表

示的是原子结点,红线表示的是键,而结点和键附近的数字表示原子数和化

学键数。

图3化学图

Fig.3Chemi-Graph

2253实验结果与分析

我们在实验时采用的处理器是IntelRPentiumRDualCPUE2160,这是32

位的处理器,

主频是1.80GHz,内存为2GB,机器所用的操作系统是Windows7,我们

的编码环境是

VS2012,使用的语言是C#,调用了微软手写开发包中的API。

由于在有机化学结构式的研究方面暂时没有统一的数据集,所以我们采用

了自己采集的

230手写数据来进行实验。我们的数据集一共包含300余种常见的环状化

学结构式,共有15名

熟练掌握手写设备使用的人员参与了样本的采集工作,充分保证了样本的

多样性,昀终,我

们一共采集了4000个样本以供实验,该数据集保证了实验结果适应绝大

多数环状化学结构

以及多数人的书写习惯,具有较高的参考价值。

1)符号识别

235单个符号识别是调用SDK中识别引擎并结合自己的优化算法对C、

H、O、N等原子和

2、3、4这几个数字进行识别的,我们从样本库中随机抽取了两组样本,

对它们进行抽样检

测,测试它们的准确率。其中,每组样本包含50个样本。

在第一组样本中,我们一共检测出了286个单个符号,其中正确的有

272个,而其中本

身应该有289个单个符号;在第二组样本中我们一共检测出了235个单

个符号,其中正确的

-7-