CN100562885C - 搜索、识别和定位墨水中的术语的方法、装置 - Google Patents

Abstract

一种用于在至少一组墨水数据(101)中搜索由至少一个字符组成的至少一个术语的方法。根据本发明，所述方法有利地包括转换操作，该转换操作用于将所述墨水数据(101)转换(112，113)成中间格式的中间数据(102)，所述中间格式为至少一个分割图的形式，所述分割图的每个节点包括至少一个墨水段，所述至少一个墨水段与和识别单元的对应的至少一个假定相关联；和在所述中间数据上完成的用于搜索所述术语的搜索操作(106)，所述转换操作在所述一组数据存储期间只此一次地完成且所述搜索操作(106)能够在任何时间完成。

Description

搜索、识别和定位墨水中的术语的方法、装置

技术领域

本发明的技术领域是搜索和识别以数字格式存储的文件中的术语。

尤其是，本发明涉及搜索文件中的信息，所述文件称为墨水文件，即，手写准备且预先以这种格式直接存储在例如文件信息系统中。本发明还能够应用于其他类型的文件，例如口述文件。

背景技术

由于桌上型计算机以及所有其他类型的大部分可移动的终端的计算和/或备份能力的显著提高，所述终端例如为个人数字助理(或PDA)、笔记本计算机、移动电话等，在不需要预先将数据和/或文件转换成任何标准的计算机格式的情况下，已经变得能够以它们原始手写格式直接获取和存储数据和/或文件。

然而，一旦已经获取和存储了这种墨水文件，处理墨水文件所包含的数据和/或手写信息要求使用特定和复杂的工具。这些工具通常能够使存储的数据或信息转换成属于词典(或专门词汇)的元素，且能够在墨水文件中搜索所转换的词、短语或注释。

现有技术的解决方案

由此，使得能够将序列语言(sequential language)，典型地为语音或笔迹，转换成数据处理系统能够理解的元素串的系统是已知的，所述元素以ASCII，ISO-Latin-1或UNICODE类型的格式被编码。

现有技术中的系统中，能够将以它们原始手写格式输入的墨水文件直接备份到例如计算机硬盘驱动器上的系统也是已知的。

在一个或多个所存储的墨水文件中搜索数据和/或信息要求将包含在请求中的正在被搜索的数据与来自所存储的墨水文件的数据进行比较的能力。在这方面，先前已经提出了几种解决方案：

-当请求也以手写格式输入时，将存储的墨水数据与请求的内容进行比较；

-将存储的墨水数据与以文本格式(例如ASCII)输入的并转换成手写体的请求的内容进行比较；

-将转换成文本格式(例如ASCII)的所存储的墨水数据与本身为文本格式的请求的内容进行比较。

当然，前两种方案在它们对处理器(CPU)和内存施加的负载方面而言是繁重和苛求的。它们不能够在合理的时间段内进行有效的处理。第三种方案通常在词典的协助下采取到字符的预先转换。由此，由于转换限于一种语言且限于实际存在于词典的术语，因此带来了偏差。

搜索处理的一个困难主要在于在存储的文件中搜索的数据与在查询语言中使用的数据的属性并不总是相同。

因此，重要的是，所利用的技术能够描绘出这种不同种类的数据之间的关联，所述关联包括与搜索功能相关，所述搜索功能是用于在所存储的墨水文件的一部分或全部墨水文件中识别所搜索的数据的功能。

这种识别系统是已知的，所述识别系统通常基于复杂的计算机处理，另一方面要求显著的处理能力，所述能力在处理器(CPU)和内存负载方面是高要求的。

因此，现有技术的大多数识别系统使用一个或多个处理，其中包括：

-墨水数据到字符级别格式(ASCII等)的转换，所述字符级别格式能够由计算机终端直接解释；

-字符格式的数据和通常采取词典形式的数据模型之间的比较；

由此，现有技术的这些识别系统的第一个缺点，涉及在其包含的词的数量和含义方面，使用具有通常固定和有限的内容的词典的必要性。

另外，这种词典的使用在搜索结果方面需承担显著的限制，这个结果必然依赖于词典的语言、全面性和范围。为此，现有技术的识别技术至少在某些情况下返回普通的结果，且它们不能够搜索固有名称、公司名称、或任何其他已经被写入墨水文件中、在搜索中被考虑但没有出现在词典中的字符或符号串。

另外，在识别阶段使用词典通常在处理请求和将搜索结果返回给用户的过程中产生相对长的响应时间。

为了克服上述缺点，现有技术的某些其他技术基于使用索引方法，索引方法的主要作用是预组织其中必须应用搜索的墨水文件中包含的数据和/或信息。然而，另一方面，在搜索环境中使用这种索引方法要求墨水文件的内容预先已经进行了至少部分识别处理。

为了这个目的，并且为了减少总的搜索时间，一些技术提出了执行所存储的墨水文件的内容的初步识别，然后将这个识别的结果存储在例如计算机或服务器的硬盘驱动器上，且最后不在所存储的墨水文件的原始内容上而是在执行的初步识别的结果上进行搜索，如美国专利申请文件No.：US2003101163。

在这些已知的技术中，在词级别排他地执行索引，且置信度评分被分配给每个词，以便评估搜索的词与索引的词中的一个词对应或不对应的概率。

尽管改进了用于处理搜索和/或用于识别处理的响应时间，现有技术中的这些技术被证明在识别质量方面是令人失望的。另外，在搜索能力方面它们是有限的。为了说明，对于这些技术，事实上不可能搜索可能没有进入词典的词，其中所述词典是已经用在识别预先存储的文件的词典。这同样适用于搜索首字母缩写词、商标、固有名称和没有预先在词典中定义的字符和/或符号的任何其他缩写或串。

因此，现有技术中的这些已知技术的优点严格地局限于在预先存储和被词典编纂的文件中进行搜索，这是用于在墨水文件中搜索和识别的系统的自然和广泛使用的方式，例如用于查询公司文件数据库、文件系统等的目的。

最后，由于它们强加的词汇方案，这些搜索和识别系统的另一个缺点涉及它们不能够减轻对文件内容的改变，所述改变可能在文件被存储时就发生，或减轻对用户作出请求的输入的错误和/或近似。事实上，一旦用户将包含拼写错误或击键错误的词输入它们的请求中，搜索和识别系统将不返回任何结果，相反，它可能返回接近的结果。

总之，现有技术中的已知搜索和/或识别技术大体具有五种类型的缺点：

1、与墨水文件的词分割相关的问题，所述词分割的使用易于在搜索阶段导致错误。

2、与索引文档的全面性的缺乏相关的问题，所述索引文档的全面性的缺乏是由于将数据转换成属于词典的元素造成的，索引文档的全面性的缺乏能够产生其中用户搜索请求不能够被识别的情形，用户搜索请求不能够被识别例如是由于拼写或击键错误造成的，或由于输入固有名称或公司名称或首字母缩写词造成的；

3、拙劣地执行墨水文件的识别的特有问题，这造成产生有缺陷的索引文档，所述有缺陷的索引文档的使用容易在搜索被拙劣识别的词的阶段导致错误；

4、与用户请求有关的问题，其使得不可能克服语言限制，相反用户请求必须以与词典的语言相同的语言输入。因此，基于用户请求发出的任何搜索都将不能够由识别系统处理，所述用户请求不遵循与索引文档的语言限制相同的语言限制。最后这个问题可能会构成一个对用于在墨水文件中搜索和识别的系统的更自然和广泛使用的主要障碍；

5、与能够执行更高级搜索的不可能性相关的问题，其中更高级搜索基于以更高阶语言输入的规则表达式类型的请求而被执行，例如用于更完全地使请求的内容形式化，搜索的处理从所述请求能够可以完成的更快，同时为用户提供在返回结果方面更高程度的质量。

另外，需要注意的是，通常，上述列出的缺点同样适用于语音识别。在语音识别的情况下，“术语”也能够与声音、音节等对应。

初步定义

在本说明书的余下部分中，下面的术语应被认为具有下面定义的含义：

-字符：字符应理解为意指字母、数字、用在文字构成中的标点符号或空格，单元书写标记(例如在ASCII字符或符号的意义上)。

-术语：术语应理解为意指包含至少一个手写字符和/或符号或打字文本、具有或不具有任何特定含义的任何序列或串。

-墨水段：墨水段限定了由两个连续相邻的分割点定界限的字符轮廓的任何部分，所述两个连续相邻的分割点布置在所述字符的轮廓上(203至206)。

-识别单元：其被定义为能够在其上完成搜索的最低级别元素。在这个描述的范围内，这样认为的识别单元是字符。很好理解，为识别单元考虑的粒度的级别能够以不同方式选择。

-分割图：由多个节点组成的图，每个节点包含能够属于一段数据的至少一个墨水段。所述分割图的每个节点能够在上游和/或下游与分割图的其他节点相连，从而可以在包含在相互连接的节点中的每个节点内的墨水段之间建立上升和/或下降的可能的关系。

-字符假设：其被定义为与分割图的节点相关联的墨水段组(209)。

-字符候选：其被定义为与分割图的节点相关联的墨水段组与字符之间的对应(或对应性)的假定(211)。

发明内容

特别地，本发明的目的旨在克服现有技术中的这些缺点。

更具体地，本发明的一个目的旨在提出一种用于在墨水文件中但不限于墨水文件中搜索和识别术语的技术，该技术在计算机和/或任何其他固定或移动终端上具有快速的执行时间。

本发明的另一目的是提出一种技术，该技术使得能够根据先前的定义大体上增加搜索和识别术语的任何序列的可能性，无论所述术语的序列具有含义或不具有含义。

本发明的附加的目的旨在提出一种技术，该技术使得能够在不使用有限内容的词典的情况下工作。

本发明的另一目的是提出一种技术，该技术不受任何语言限制。

当然，本发明的再一目的旨在提出一种技术，即使在所存储的墨水文件中出现可能错误，或者在用户输入搜索请求的内容期间，该技术都能够确保非常好的搜索和/或识别结果。

本发明的目的还在于提出一种在执行方面简单且成本合理的技术。

本发明的本质特征

本发明的这些目的和下面将变得明显的其他目的借助于在下面用于在至少一组墨水数据中搜索至少一个术语的方法实现，其中所述至少一个术语由至少一个字符组成。根据本发明，这种有利的方法包括用于将墨水数据转换成至少一个分割图形式的中间格式的中间数据的转换操作，所述分割图中的一个分割图的每个节点包括至少一个墨水段，所述至少一个墨水段与和识别单元对应的至少一个假定相关联；在中间数据上完成的用于搜索所述术语的搜索操作，所述转换操作在数据组之一的存储期间只此一次地(once and for all)完成，而搜索操作能够在任何时间完成。

转换操作有利地包括下列步骤：

-将所述数据组分割成至少一个墨水段，每个墨水段由两个连续相邻的分割点限定界限；

-构造分割图，所述分割图由通过分支相连的节点组成，分割图的每个节点包括至少一个墨水段且分割图的每个分支连接第一节点和第二节点以便限定包含在第一节点中的至少一个段和包含在第二节点中的至少一个段之间的邻接关系；

-将至少一个节点与和识别单元对应的至少一个预定假定关联；

-将至少一个置信度评分与和识别单元对应的每一个假定相关联；

-基于置信度评分对和识别单元对应的假定进行分类。

搜索操作优选包括下列步骤：

-获得包括正被搜索的术语的输入请求；

-将输入请求的内容转换成适于中间格式的至少一个请求自动机；

-搜索所述术语和所述中间数据的至少一个元素之间的至少一个对应；

-呈现和/或传送至少一个搜索结果。

与和识别单元对应的假定相关联的置信度评分优选存储在与所述分割图对应的所述节点中。

转换操作优选包括初步操作，所述初步操作用于通过控制和/或校正属于下列群组的参数中的至少一个参数，来规格化形成原始墨水数据的字符的轮廓，以便提供规格化的墨水数据组，所述群组包括：

-相对于至少一个参考方向的倾斜值；

-相对于至少一个给定轴线的旋转系数；

-线粗；

-相对于至少两个参考线的字符高度和/或宽度。

转换步骤优选包括用于修剪分割图的分支的步骤，所述分割图的节点包含具有低置信度评分的与识别单元对应的假定。

对于分割图的每个节点，分类步骤还有利地具有与按照递减置信度评分顺序预定的识别单元对应的假定的列表。

分类步骤还优选地通过比较置信度评分和预定的阈值执行对和识别单元对应的最可能假定执行过滤。

分类操作优选地基于下列学习技术之一：

-Kohonen神经网络；

-支持向量机；

-核方法；

-模糊逻辑系统；

-隐马尔可夫模型；

-神经网络。

转换操作有利地包括存储步骤并且确保下列信息中的至少一些信息的存储：

-一组节点；

-每个节点的、与识别单元对应的假定的列表；

-用于与每个节点的、与识别单元对应的假定中的每一个假定的置信度评分；

-每个节点在所存储的原始墨水数据组中的位置，所述位置由至少一个分割点限定；

-关于节点与分离两个墨水段的空格相邻的事实的信息。

分割点优选根据属于下面群组的至少一个标准确定，所述群组包括：

-相对于参考线确定的极值和/或最小值；

-拐点；

-递增曲线开始；

-递减曲线开始；

-由于书写装置的升高导致的停止点；

-用于书写装置的固定点；

-相交线。

搜索的术语有利地属于包括至少一个打字的或手写的文本字符的群组。

请求自动机优选是属于包括至少一个有限状态自动机的群组的类型。

在至少一个自动机内，转换步骤优选至少包括下列步骤：

-将请求的内容切割成属于下面的群组的识别单元，所述群组至少包括：

音节；

O音形；

O字素；

O字符；

-将每个识别单元存储在请求自动机的状态中。

在优选的实施例中，识别单元是字符。

因此请求自动机的每个状态包括来自于输入请求的字符，且请求自动机的每个分支将第一状态与第二状态连接，所述第一状态和第二状态限定包含在第一和第二状态中的识别单元之间的上升/下降的关系。

搜索操作有利地包括建立包含在请求自动机的每个状态中的每个字符与分割图的至少一个节点匹配，以便识别分割图的具有与字符对应的最高概率的节点。

同样，有利的是，在搜索操作期间，在分割图和请求自动机中的进程同时发生，从而当能够建立分割图的第一节点和包含在请求自动机的第一状态中的第一字符之间的对应时，选择从请求自动机的第一状态直接下降的第二状态，且在分割图中确定节点，该节点从第一节点直接下降且具有与第二字符对应的最高概率。

建立分割图和请求自动机之间的对应优选使用最大似然格点，所述最大似然格点包括沿X轴的墨水段的分割图，和沿Y轴的请求自动机。

因此，有利地通过计算分配给分割图的节点的置信度评分和分配给自动机的状态之间的过渡圆弧的置信度评分的总和，确定分割图路径和具有状态的最小成本自动机的路径。

用于呈现和/或传送至少一个搜索结果的步骤优选地进一步返回用于墨水数据组的一段识别信息，所述墨水数据组包括搜索的术语的至少一个出现和/或用于这些墨水数据组内的每个出现的一段位置信息。

本发明还有利地涉及计算机程序，该计算机程序包括程序代码指令，当所述程序在计算机上运行时，所述程序代码指令执行用于在原始墨水数据组中搜索至少一个术语的上述方法的步骤，所述术语是用户输入请求的输入信号的形式。

本发明还优选地涉及一种用于在至少一组墨水数据内搜索至少一个术语的设备，所述术语由包括至少一个字符。根据本发明，这样的设备有利地包括用于搜索术语的装置，所述搜索在中间数据上完成，所述中间数据由用于将墨水数据转换成至少一个分割图形式的中间数据的装置预先以中间格式存储在存储装置内，所述分割图之一的每个节点包括与至少一个和识别单元对应的至少一个假定相关联的至少一个墨水段。

根据本发明的装置有利地属于下面的群组，所述群组至少包括：

-桌上型计算机或膝上型计算机；

-个人数字助理；

-笔记本式计算机；

-移动电信终端；

-多媒体信息站；

-数字笔；

本发明还涉及一种用于转换用于在至少一组墨水数据中搜索包含至少一个字符的至少一个术语的墨水数据的设备。根据本发明，这样的转换设备优选包括用于将墨水数据转换成至少一个分割图形式的中间格式的中间数据的装置，所述分割图之一的每个节点包括至少一个墨水段，所述至少一个墨水段与同识别单元对应的至少一个假定相关联，从而对术语的搜索在中间数据上完成。所述转换在数据组之一的存储期间只此一次地完成而搜索能够在任何时间完成。

最后，本发明有利地涉及规则表达语言，所述规则表达语言用于以制定表达搜索来自一组以中间数据格式存储的墨水文件组中的搜索请求。根据本发明，这种语言可以请求自动机的形式转换，根据上述方法的步骤，当程序在计算机上运行时，所述请求自动机能够在执行用于在墨水数据组中搜索至少一个术语的方法的步骤期间直接被使用。

附图说明

本发明的其他特征和优点在阅读了下面优选实施例的描述情况下和根据附图将变得更加明显，所述实施例不是限制性的而是用于说明目的，其中：

图1是根据本发明的搜索方法的不同步骤的流程图，且相对于所述搜索方法进一步规定了执行这些不同步骤的相应装置的元件；

图2示出了通过将所述墨水数据转换成中间格式的中间数据的操作而执行的不同步骤；

图3描述了在建立分割图和请求自动机之间的对应期间使用的最大似然格点的原理；

图4示出了根据本发明的请求自动机的表示；

图5是获得用于类型“CALIFORNIA”和“SAN FRANCISCO”的请求的自动机的示例性表示。

具体实施方式

下面描述的实施例涉及搜索墨水文件中的术语。

由此，本发明的原理基于新颖的和创造性的搜索和/或识别书写(且更广泛为术语)的方案，该方案使用将搜索必须在其中完成的墨水数据转换成至少一个分割图形式的中间格式的中间数据的转换操作。

所述分割图之一的每个节点包括从墨水数据提取的至少一个墨水段，所述至少一个墨水段与至少一个字符候选相关联。根据本发明，用于搜索和/或识别术语的搜索操作不再在原始数据上完成，而是动态地根据中间数据完成。转换操作在存储数据组之一时只此一次地(onceand for all)完成，而搜索操作由此能够在任何时间完成。当然，如果文件被修改，必须完成新的转换(和新的存储)。

如图1所示，在此优选实施例中，根据本发明的搜索和/或识别方法包括下列步骤：

A：只此一次地(once and for all)

-在其中必须执行搜索和识别书写的墨水文件或数据101初步转换100成例如在数据库系统中存储的中间格式102。在输入112，转换操作获取原始文件或数据101以便处理它们并将它们转换113成中间格式文件102中；和

-存储中间格式文件；

B.对于每个搜索和/或识别：

-从输入界面104输入用户请求103；

-以请求自动机的形式111转换105此用户请求，其中执行用于在转换和存储的墨水文件和/或数据102内进行搜索和/或识别的步骤106而直接采用所述请求自动机的形式；

-格式化107搜索和/或识别结果，识别结果由转换请求105的内容直接影响或定向108；

-直接以在所存储墨水文件中搜索和识别的术语列表的形式或以定位和加亮显示所搜索的术语的一个或多个出现的形式，将结果109呈现110给用户。

这些不同的步骤能够由计算机程序115实施和/或执行，所述计算机程序集成有用于其操作的搜索和/或识别引擎，所述搜索和/或识别引擎的作用主要在于一方面执行用于以请求自动机的形式转换105用户输入的请求的步骤，另一方面执行用于在转换和存储的墨水文件和/或数据102内进行搜索和识别114的步骤106，但所述搜索和/或识别引擎的作用并不限于此。

在搜索引擎116级别，在结果109通过用户界面104呈现给用户之前，能够执行为搜索和识别书写而获得的结果109的处理107。

在本发明的此优选实施例中，用于将墨水文件101转换成以至少一个分割图形式存储的中间格式102的步骤100本身包括将被执行的一组预定操作，如图2所示：

-将墨水数据组切割202成所述墨水数据组200内的至少一个墨水段203，204，所述墨水段203，204中的每一个都由两个连续相邻的分割点205，206定界限；

-构造207分割图208，所述分割图208由通过分支210相连的节点209构成。分割图208的每个节点209包括所产生的至少一个墨水段203，204且连接第一节点209和第二节点209的每一个墨水段分支210限定了包含在第一节点中的至少一个段和包含在第二节点中的至少一个段之间的邻接关系，以便形成所述段的至少一个序列208。根据分割图的定义，在此我们记得，在本发明的优选实施例中，字符的假定限定了与分割图的节点相关联的一组墨水段；

-至少一个预定字符候选212与至少一个节点205，206相关联，以及至少一个置信度评分与每个所述假定202，206相关联211。另外，在实践中，规定本发明中的含义中的置信度评分在本发明的含义内是指墨水段、或几个墨水段的组合与预定字符精确对应的概率。

在此我们还记得，在本发明的此优选实施例中，识别单元与字符对应，且与字符对应的假定与字符候选对应(见第3段的定义)。

-基于相关联的置信度评分213分类214对应212的假定。

因此图2中详细给出的转换步骤的结果是生成包含搜索可以基于的所有分割图的文件或数据库215。

用于转换数据或墨水文件的这个步骤的原理性优点之一在于能够基于用于识别书写的处理，使用来自于其预处理的信息增强后者。

根据本发明的这个方案的另一个优点涉及其提供了仅不得不在转换的墨水文件上完成一个部分识别操作的可能性。这个部分识别操作与完整的识别操作相反，所述完整的识别操作必须通过评估字符关于语境(其他字符和/或相邻的词)的似然性，考虑识别字符的语言元素(词典，语言模型)。另一方面，在本发明框架内提出的方案能够完全克服任何词典或语言限制。进一步能够完成搜索和识别阶段上游的最大数量的处理操作，目的是在搜索期间获得计算时间，由此获得用于将搜索结果返回给用户的响应时间，这个时间必须尽可能地短，即最大值时的数量级为几百毫秒到两三秒。

最后，此方案使得能够促进在数据或文件内的快速搜索且没有预先识别。

为了完成用于转换原始墨水数据或文件101的这个步骤，对于包含在此数据或这些文件内的每个字符，完成用于分割202成多个段的第一操作。

这样的分割步骤能够在不同级别完成：例如，短语到词，词到字符，和字符到墨水段。根据被分析的书写样式(草书，大写字母，或孤立的字符)，该步骤也能够不同。

在本发明的优选实施例中，在字符级别完成分割。然后，这包括在字符级别直接完成分割。然而，重要的是强调这不必然意味着分割必须在所讨论的字符上一个接一个地完成，否则这将要求用于初步检测文本或手写书写中的单独字符的附加的和昂贵的步骤，即使存在用于那样目的的技术。

相反，在这里提倡的方案中，分割可以既在字符上又在字符的一部分上以相似的方式完成，或者甚至在一组相互连接的字符的全部或一部分上完成。重要的是，搜索和/或识别引擎116能够限定一定数量的分割点(“分割节(segmentation cut)”)，所述分割点必须用作用于在段上或由此确定的段的组合上形成字符的假定的基础。

为了完成用于切割或分割墨水数据或文件101的步骤202，其中搜索和识别将不得不以所述墨水数据或文件为基础，可以考虑几种类型的准则。作为说明性和非限制性示例，引用下面的准则：

-相对于竖轴的手写中的极值和最小值的确定；

-字符或手写字符组中的明显的曲率或拐点的检测；

-递增曲线开始(increasing slop-start)的检测；

-递减曲线(decreasing slop-start)开始的检测；

-由于书写装置的升高导致的停止点的检测；

-用于书写装置的固定点的检测；

-相交点的检测。

该第一切割操作的结果导致生成一组墨水段，所述墨水段将用于确定字符的假定，由此确定的每个墨水段由两个连续相邻的分割点定界限。

如果必要，在本发明可选的优选实施例中，根据搜索和识别结果所要求的质量级别，预处理201可以应用于墨水以便规格化墨水并且由此使其不可变化且独立于初始书写样式。

此规格化201能够通过玩弄手写轮廓相对于大体垂直的参考物的倾斜度(“倾斜校正”)，书写相对于旋转轴线的旋转，或书写的高度完成，书写的高度能够带回到被分离开预定距离的参考线216之间。清楚的是，此规格化步骤201可以基于这里没有列出的任何其它规格化准则。

另外，用于构造分割图的步骤207所具有的主要作用，是以墨水段序列的形式关联或合并墨水段，目的在于确定字符的相应假定。

在执行此步骤207中，将作出墨水段可能是给定字符212的概率213的估计，由所述概率213和所述给定字符212的组合构成字符候选211。然后，通过将墨水段与紧随其后的墨水段相关联，对于这个相同的段重复操作，目的在于使分割图内将被调查的路径最佳化。这样，上升/下降的关系被限定在由此确定的相同字符序列的段之间。这里我们记得，根据第3段的定义，字符211的假定包括一到N(N大于零)个连续的墨水段，分割图的每个节点包含字符的一个假定。

在用于构造分割图的步骤的最后，对于将在其内完成搜索的手写文件，得到字符211的全部确定的可能的假定。

另外，在用于构造分割图的步骤的最后也可以是，字符211的某些假定具有非常低的置信度评分，或者处于小于预定阈值的非常小的值，从而与字符211的假定相关联的墨水段与给定的字符212对应或属于给定的字符212。

为此，在执行用于创建分割图的步骤的过程期间或在执行用于创立分割图的步骤之后，可以执行附加的处理，所述附加的处理包括：修剪其分支，所述分支与具有非常低的概率的假定相对应。这种附加步骤的优点尤其涉及优化在墨水中进行搜索和识别，因为将被测试的字符的假定数量将不十分重要，由于将被调查的分割图路径将具有最佳的深度，其另一个积极的结果是显著降低全部响应时间，且无需改变将返回给用户的结果质量。

此分割图208是通过字符分类步骤214处理的下一个目标，对于与分割图208的每个节点209相对应的字符211的每个假定，利用特征提取方法214计算字符分类步骤214，一组评分213指示假定实际上是一个字符而不是另一个字符的概率。

为了非限制性目的，这个分类步骤可以基于下面装置中的至少一个：

-Kohonen神经网络；

-支持向量机；

-核方法；

-模糊逻辑系统；

-隐马尔可夫模型；

-神经网络。

与每个节点对应的每个字符的每个假定的这种分类结果能够以最佳字符候选212的列表(或“头等列表(top list)”)的形式表现，所述字符候选212按照递减的置信度评分213排队，每个候选实际上被分配给一个置信度评分。

在字符级别上的该识别步骤之后，识别系统为每个假定字符提供不同的候选。在此阶段，一旦这些候选中的一些候选具有低于预定阈值的置信度评分或相反具有高于预定阈值的置信度评分，所述一些候选能够拒绝或被证实有效。很好理解的是，使得能够保留或拒绝候选的这个阈值可以由用户例如基于他们在按照他们请求的结果方面希望获得的搜索和/或识别的相关性的级别而被配置。

从这些不同操作201、202、207、211、214的执行导出的结果以中间格式例如存储在数据库215内。存储执行用于转换原始墨水数据的步骤100，113的全部或部分结果的主要优点涉及能够保存最大量的关于原始数据的信息以便能够在质量方面完成最佳识别且具有最小误差的可能性。为了非限制性说明目的，在用于转换墨水文件或数据的步骤100、113完成时，下面的信息将被存储在数据库或文档215内：

-一组所述节点；

-每个所述节点的所述字符候选的列表；

-每个节点的每个字符候选的置信度评分；

-每个所述节点在所存储的原始墨水数据组中的位置，所述位置由至少一个分割点限定；

-关于节点与分离两个墨水文件的空格相邻的事实的信息。

因此，实际的搜索和识别步骤是以此字符分割图为基础完成的，以便最佳地确定墨水的哪些部分与词对应，与表达对应或与搜索的术语对应。这里我们记得，术语应理解为意指字符、符号、标点元素等的任何序列或串，无论它是否具有任何特定的含义或不具有特定的含义。

一旦其中搜索将不得不在墨水数据或文件中完成的用于转换墨水数据或文件的初步步骤100，113已经完成，则能够执行用于在这个墨水数据或者这些墨水文件中搜索的用户请求。

再次强调的是，转换步骤在存储在文档或数据库215内时只次一次地完成。在每次进行墨水数据的修改或添加新墨水数据时，初步转换步骤100，113将再次运行，从而搜索能够考虑添加的和/或修改的数据。

用于对用户的请求进行编码的处理在本发明的框架内执行且旨在将搜索请求转换成能够更容易地由根据本发明的方法执行的格式。

在本发明的此实施例的描述中，将认为请求是以文本格式(例如ASCII)输入。

如先前提到的，本发明提出将识别处理分成两部分：将墨水数据转换成分割图形式的中间格式的第一部分，和与实际搜索对应的第二部分。

与现有技术的已知系统相反，这两个步骤有意地被分开，用于准备所有的上游操作，所述操作将是必要的且对于所有可能的后续用户请求是共用的。

实际上，每次用户作出请求103时，生成相应的请求自动机105。此有限状态请求自动机105将起到语言模型的作用，所述语言模型能够在搜索期间影响识别概率。

由于在转换步骤112，113期间保留的与墨水相关的信息仅包含具有它们的字符候选212和它们各自的评分213的字符的假定，生成的请求自动机将用于定向在识别时的搜索的结果109。

在本发明含义内的搜索和识别由此由请求103强烈地定向，字符211的假定根据旨在明确地在转换的墨水数据或文件的文档内发现对请求作出响应的墨水部分的限制，被重新解释。

请求自动机形式的请求的制定不但使得能够克服传统词典带来的语言限制，而且能够完成更多的高级搜索。在使用用于完成高级搜索的自动机的示例中，下面的内容能够被提及：

-搜索任何连续字符(固有名称、公司名称，首字母缩略词等)；

-考虑大小写(大写/小写)；

-逻辑运算符的使用(布尔逻辑体系[AND(和)，OR(或)，NOT(非)]等；

-搜索常规表达。

总之，是图1中的搜索模块106通过浏览请求自动机，通过分割图尝试在墨水中的搜索必须在其内完成的墨水文件中发现具有对应的元素。

为了使搜索模块106的操作最佳化且为了改善将被返回到用户的搜索结果的相关性，后者可以在它们的请求内使用逻辑运算符(例如OR(或)，AND(和)，ANDNOT(和非)NOT(非)等)。

下面提供的是搜索模块106对这些逻辑运算符的使用和考虑的例子：如果用户将术语“CALIFORNIA AND NOT SAN FRANCISCO”输入它们的请求，请求自动机将把用户的请求转换成“CALIFORNIA”OR “SAN FRANCISCO”，从而搜索模块106将同意搜索两个搜索词中每一个的全部出现。

由此形成的请求自动机因此能够被同化到语言模型，在结果的相关性方面，使得能够将请求的处理最优化且能够改善搜索质量。

尤其是，当搜索必须同时应用到几个墨水文件时，搜索模块106的贡献更加重要和显著。

在请求中使用逻辑运算符能够在搜索阶段进行精细过滤，且由此使得在文档相对于用户请求的内容的相关性的评估中，分配更好的确定全面评分。

为了确定返回到用户的结果，分配给每个文件的评分考虑构成请求的术语的例证的数量和质量。在上面提及的示例中，与其中仅确定至少一个出现“California”的文件相比，字符串“san francisco”在也包含“california”的文件中的肯定出现将不利于与所述文件相关联的最终评分。

在这种情况下，对用户请求进行编码将旨在在搜索结束与结果传送到用户之间限定用于列出搜索结果的过滤和规则，所述编码可以在用于编辑搜索结果的步骤被激活。

图4和图5示出了使得能够呈现这种语言的请求自动机。在完成快速搜索的预期中，不考虑识别请求周围的文本的结果。在用户制定请求之前或之后，请求周围的文本语言模型通过识别任何连续的字符的可能性被近似化，所述连续的字符在图4和图5中分别标记为*40和50。以新颖和创造性的方式，与根据现有技术中已知技术的传统识别操作相比，其中所述已知的技术基于或使用通常固定的和/或不可扩展的词典，这样的方案使得能够显著地改善返回到用户的结果的处理时间和质量。

在输入用户请求时必须插入附加标记(bonus)42，52，以便诱使识别器从自动机浏览实际上与请求41，51的内容对应的路径，而不是与标记为*40和50的未限定的文本相对应的路径。事实上，如果必要，能够使得识别任何连续的字符的文本模型能够识别请求的术语。

通过添加该附加标记42，52，识别器浏览请求的自动机的一个路径而不是浏览另一个路径的动机被加强。附加标记42，52能够由用户用参数表示且以检测敏感性阈值的形式提供。附加标记越高，请求的检测越容易，相反，识别质量降低的越多。作为补充和非限制性示例，高附加标记的添加将具有增加错误检测或错误接受的风险的趋势。由此，用于术语“CALIFORNIA”的高附加标记的分配也可以在出现类型“CARORLINA”的附近发生。

相反，具有非常低的值的附加标记将造成检测缺陷。作为简单的说明示例，设定为零的附加标记将必然地引起发布零搜索结果，因为对于识别器而言不存在浏览请求自动机的一个路径而不是浏览另一个路径的动机。

由此，搜索完全由请求自动机定向，这与用户请求被编码时创建的语言模型类似。

相应地，搜索引擎116不具有识别墨水文件的全部元素的目的。这将限于搜索示例，对于所述示例，在用于以分割图的形式转换墨水数据的阶段期间保留的概率对于寻求的目标最强。

为了便于这种方案的实施，使用动态规划(DP)。这使得能够动态地完成分割图的节点和请求自动机的节点之间的比较。

此动态比较在于既在分割图中又在请求自动机中搜索最佳路径。对于这种匹配共同使用的表示是最大似然格点，如图3所示。

最佳路径被定义为具有最小成本的路径。路径的成本等于在分割图中与其相关联的节点的成本以及自动机中可能的弧形的成本总和。如果识别系统提供了概率，这些概率能够由函数(-log)转换成成本。

最佳路径被显示在格点上且示出墨水的哪一部分与语言模型的哪一部分对应。尤其是，现在可以在存储的墨水中定位使用者在它们的请求中制定的术语的出现。

如图3所示，在X轴上，格点接收分割图在转换步骤期间添加的补充信息，且在Y轴上，接收在用于编码后者的步骤期间产生的请求自动机。

结果编辑器107也能够在搜索引擎116级别上实施。其功能是基于输入到用户请求中的信息，分类和过滤从识别和搜索操作导出的结果。

在这个处理阶段，搜索(或墨水书写识别)部分被完成。在其输出，搜索模块106将提供搜索的术语在墨水中出现的位置以及用于这些出现中的每一个出现的相关联的置信度评分。

在其中用户的请求由将被搜索的几个术语，例如“San Francisco””和“California”构成的假设中，搜索将通过考虑两个术语“SanFrancisco”和“California”的单个和唯一的请求自动机完成。

结果编辑器107将接收结果数据并且通过阈值完成对评分的分类操作，超过该阈值数据将不被保留。通过基于获得的评分建立分级，可以提供全部的结果。

几个系列的评分将被提供且由结果编辑器107组合，结果编辑器107的功能在于提供与使用者的初始请求，例如“San Francisco”和“California”实际对应的响应。

非常明显，根据本发明的方法和设备使得能够完成在一个或多个手写文件的墨水中进行搜索。

当在单个墨水文件上完成搜索时，搜索结果以搜索的术语在单个文件页面上出现的位置的形式返回给用户。这里，搜索被定向到请求的目标，用户希望找出文件中墨水的位置。然后，置信度评分被分配给每个出现。

当搜索在几个墨水文件上完成时，搜索的结果以包含搜索的术语的文件的顺序列表的形式返回给用户。这里，搜索被定向到其中搜索的术语和其评分一起被找出的文件。由此，置信度评分被分配给每个文件。

在每种情况下，都可能通过以实质的方式示出搜索目标的位置而提供它。

换言之，且有利地，一方面，本发明使得能够解决其中必须通过识别完成搜索的墨水文件的词分割方面常规遇到的问题。

本发明还能够在每个处理或执行的搜索请求正被完成时进行所存储的墨水文件的动态分割。

有利地，与现有技术中存在的解决方案相反，这样新颖和创造性的方案进一步允许搜索不必要识别的词，且更通常而言，进一步允许搜索具有或不具有含义的字符和/或符号的任何串或序列，通过扩展包括搜索任何类型的非拉丁书写字符或符号(例如中文或日文)。这个非常有趣的结果是通过包含在所存储的墨水文件中的术语的特定切割获得，其中所述特定切割不是在句子、词或字符级别，而是仅在至少一个字符的一部分的较低级别上进行的。

这个方案进一步使得能够克服任何语言上的限制。

根据本发明的方案，实施所存储墨水文件的动态分割能够容易的通过动态规划进行。其还能够进一步使得考虑更为复杂和更为全面的所存储的墨水文件中的搜索请求，且没有使用预定的、固定和非适应性的和/或非扩展性的词典的任何限制。

在这个意义上，使得能够克服通常与必须能够区分大写或小写字符相关联的限制。

一个附加的优点涉及能够使用形构化语言模型(formalisedlanguage model)的可能性，所述形构化语言模型能够使得用户请求内容的输入和考虑最佳化，作为积极的考虑，能够使得返回结果优化，所述返回的结果通常证明更为全面且质量更好。

重要的是强调根据本发明的这种方案使得能够显著地限制与墨水识别相关联的错误，因为墨水识别通过被搜索的请求内容直接定向。由此，在这个方案与现有技术中的已知技术完全相反的意义上而言，它是具有新颖性和具有创造性的，其中对于现有技术中的已知技术，识别操作独立于请求的内容进行。

本发明采用的方案一方面有利地提高了识别操作的质量，另一方面促进了能够请求在所存储的墨水文件中搜索的术语、词或句子的精确和真实的定位。这个定位能够通过下划线、超文本链接转换或通过任何其它能够将焦点施加到搜索和实际识别的术语、直接施加到所存储的墨水文件的内容上来完成。由此，当搜索到的术语的多个示例已经在一个或多个墨水文件中检测到时，几个焦点能够施加到文本上。

根据本发明的这种方案还大体上促进对于搜索请求的处理时间减小，识别步骤现在以不会令用户感到厌烦的非常有限的时间段内完成。

另外，能够注意到，由于搜索与预处理分离，在某些情况下，这两个操作能够通过分离和可能远程的装置完成。尤其是，通过局域网或因特网可访问的远程服务器能够确保预处理和存储。然后，请求在终端(计算机，PDA等)上作出且由服务器处理。

如已经描述的，本发明不限于提出的实施例，而是适用于其他源数据格式，尤其是语音数据的发现应用，所述语音数据能够以相同的方式转换成假定图形式的中间格式。因此，处理也是类似的。

Claims (22)

1、一种用于在至少一组墨水数据(101)中搜索由至少一个字符组成的至少一个术语的方法，其中所述搜索方法包括：

转换操作(107)，该转换操作用于将所述墨水数据转换(112，113)成至少一个分割图形式的中间格式的中间数据(102)，所述分割图中的一个分割图的每个节点包括至少一个墨水段，所述至少一个墨水段与和识别单元对应的至少一个假定相关联；以及

在所述中间数据上完成的用于搜索所述术语的搜索操作(106)，

所述转换操作在所述数据组之一的存储期间只此一次地完成，而所述搜索操作(106)能够在任何时间完成，并且所述转换操作包括下列步骤：

-将所述数据组分割成至少一个墨水段，所述墨水段中的每一个由两个连续相邻的分割点限定界限；

-构造分割图，所述分割图由通过分支相连的节点组成，所述分割图的每个节点包括至少一个所述墨水段并且所述分割图的每个分支连接第一节点和第二节点以便限定包含在所述第一节点中的至少一个段与包含在所述第二节点中的至少一个段之间的邻接关系。

2、根据权利要求1所述的搜索方法，其中所述转换操作还包括下列步骤：

-将每个所述节点与和识别单元对应的至少一个预定假定相关联；

-将至少一个置信度评分与和识别单元对应的每个所述假定相关联；和

-基于所述置信度评分对和识别单元对应的所述假定进行分类。

3、根据权利要求1所述的搜索方法，其中所述搜索操作包括下列步骤：

-获得包括正被搜索的所述术语的输入请求；

-将所述输入请求的内容转换成适于所述中间格式的至少一个请求自动机；

-搜索所述术语与所述中间数据的至少一个元素之间的至少一个对应；

-呈现和/或传送至少一个搜索结果。

4、根据权利要求3所述的搜索方法，其中所述与和识别单元对应的假定相关联的置信度评分存储在与所述分割图对应的所述节点中。

5、根据权利要求1所述的搜索方法，其中所述转换操作包括初步操作，所述初步操作用于通过控制和/或校正属于下面的群组的至少一个参数来规格化形成所述原始墨水数据的所述字符的轮廓，以便提供规格化的墨水数据组，所述群组包括：

-相对于至少一个参考方向的倾斜值；

-相对于至少一个给定轴线的旋转系数；

-线粗细；

-相对于至少两个参考线的字符高度和/或宽度。

6、根据权利要求1所述的搜索方法，其中所述转换步骤包括用于修剪所述分割图的分支的步骤，其中所述分割图的节点包含和具有低置信度评分的与识别单元对应的假定。

7、根据权利要求2所述的搜索方法，其中所述分类步骤对于所述分割图的每个节点具有按照递减置信度评分顺序的所述节点与预定识别单元对应的所述假定的列表。

8、根据权利要求7所述的搜索方法，其中所述分类步骤通过比较所述置信度评分和预定的阈值，对所述对应的最可能假定执行过滤。

9、根据权利要求2所述的搜索方法，其中所述分类操作基于下列技术中的至少一个：

-Kohonen神经网络；

-支持向量机；

-核方法；

-模糊逻辑系统；

-隐马尔可夫模型；

-神经网络。

10、根据权利要求1所述的搜索方法，其中所述转换操作包括存储步骤且确保下列信息中的至少一些信息的存储：

-一组所述节点；

-每个所述节点的、与识别单元对应的所述假定的列表；

-用于与每个节点的、与识别单元对应的每个假定的置信度评分；

-每个所述节点在所存储的原始墨水数据组中的位置，所述位置由至少一个分割点限定；

-关于节点与分离两个墨水段的空格相邻的事实的信息。

11、根据权利要求2所述的搜索方法，其中所述分割点根据属于下面群组的至少一个准则确定：

-相对于参考线确定的极值和最小值；

-拐点；

-递增曲线开始；

-递减曲线开始；

-由于书写装置的升高导致的停止点；

-用于书写装置的固定点；

-相交线。

12、根据权利要求1所述的搜索方法，其中所述搜索的术语属于包括至少一个打字字符或手写文本的群组。

13、根据权利要求3所述的搜索方法，其中所述请求自动机是属于包括至少一个有限状态自动机的群组的类型。

14、根据权利要求3所述的搜索方法，其中所述用于转换成至少一个自动机的步骤至少包括下列步骤：

-将请求的内容切割成识别单元，所述识别单元属于包括至少下面内容的群组：

音节；

音素；

字形；

字符；

-将每个识别单元存储在请求自动机的状态中，从而所述请求自动机的每个状态包含所述输入请求的识别单元，且从而连接第一状态和第二状态的所述请求自动机的每个分支限定包含在所述第一和第二状态中的所述识别单元之间的上升/下降关系。

15、根据权利要求14所述的搜索方法，其中所述搜索操作包括建立包含在所述请求自动机的每个所述状态中的每个所述识别单元与所述分割图的至少一个节点的对应，以便识别具有与所述识别单元对应的最高概率的、所述分割图的节点。

16、根据权利要求14所述的搜索方法，其中在所述搜索操作期间，在所述分割图中和在所述请求自动机中的进程同时发生，从而当能够建立所述分割图的第一节点和包含在所述请求自动机的第一状态中的第一字符之间的对应时，选择从所述请求自动机的所述第一状态直接下降的第二状态，且在分割图中确定节点，该节点从所述第一节点直接下降且具有与所述第二识别单元对应的最高概率。

17、根据权利要求16所述的搜索方法，其中所述建立所述分割图和所述请求自动机之间的对应使用最大似然格点，所述最大似然格点包括在X轴上的所述墨水段的所述分割图，和在Y轴上的所述请求自动机。

18、根据权利要求16所述的搜索方法，其中通过计算分配给所述分割图的所述节点的置信度评分和分配给所述自动机的所述状态之间的过渡圆弧的置信度评分的总和，确定所述分割图和具有最小成本的状态的所述自动机的路径。

19、根据权利要求1所述的搜索方法，其中所述呈现和/或传送至少一个搜索结果的步骤进一步返回用于在所述墨水数据组之一内识别的每个出现的位置信息和/或用于所述墨水数据组的识别信息。

20、一种用于在至少一组墨水数据中搜索由至少一个字符组成的至少一个术语的搜索设备，其中所述搜索设备包括：

用于通过将所述墨水数据转换成至少一个分割图形式的中间格式的中间数据而搜索所述术语的装置，其中所述搜索在预先存储在存储装置中的中间数据上完成，所述分割图的每个节点包括至少一个与和识别单元对应的至少一个假定相关联的墨水段，并且所述转换包括：

-将所述数据组分割成至少一个墨水段，所述墨水段中的每一个由两个连续相邻的分割点限定界限；

-构造分割图，所述分割图由通过分支相连的节点组成，所述分割图的每个节点包括至少一个所述墨水段并且所述分割图的每个分支连接第一节点和第二节点以便限定包含在所述第一节点中的至少一个段与包含在所述第二节点中的至少一个段之间的邻接关系。

21、根据权利要求20所述的搜索设备，其中所述搜索设备属于至少包括下面内容的群组：

-桌上型或膝上型计算机；

-个人数字助理；

-笔记本式计算机；

-移动电信终端；

-多媒体信息站；以及

-数字笔。

22、一种用于转换用于在至少一组墨水数据中搜索由至少一个字符组成的至少一个术语的墨水数据的设备，其中所述设备包括用于将所述墨水数据转换成至少一个分割图形式的中间格式的中间数据的转换装置，所述分割图的每个节点包括至少一个墨水段，所述至少一个墨水段与和识别单元对应的至少一个假定相关联，从而所述术语的搜索在所述中间数据上完成，所述转换在所述数据组之一的存储期间只此一次地完成，而所述搜索能够在任何时间完成，并且所述转换装置包括：

-将所述数据组分割成至少一个墨水段的装置，所述墨水段中的每一个由两个连续相邻的分割点限定界限；

-构造分割图的装置，所述分割图由通过分支相连的节点组成，所述分割图的每个节点包括至少一个所述墨水段并且所述分割图的每个分支连接第一节点和第二节点以便限定包含在所述第一节点中的至少一个段与包含在所述第二节点中的至少一个段之间的邻接关系。

Images