An Overview of the Tesseract OCR Engine译文
Abstract
Tesseract OCR引擎以及UNLV OCR精度第四次年度测试中的HP Research Prototype [1]在全面的概述中进行了描述。 重点放在OCR引擎中新颖或至少不寻常的方面，特别包括线路查找，特征/分类方法和自适应分类器。
1. Introduction – Motivation and History(介绍 - 动机和历史)
Tesseract是一个开源的OCR引擎，在1984年至1994年期间在惠普开发。像超级新星一样，1995年的UNLV OCR精度年度测试从无处出现，它的结果闪耀着光芒，然后消失了 回到它所开发的同一种隐秘外衣之下。 现在，这是第一次可以揭示架构和算法的细节。
Tesseract最初是作为布里斯托尔惠普实验室的博士研究项目[2]开展的，并且作为惠普平板扫描仪系列的一个可能的软件和/或硬件附加产品而获得了发展势头。 当时的商业OCR引擎处于起步阶段，并且除了最佳质量的印刷品之外的任何事情都失败了，这一事实提供了动力。
在惠普实验室布里斯托尔和惠普在科罗拉多州的扫描仪部门之间进行的一项联合项目之后，Tesseract在商用发动机上的精度明显领先，但并未成为产品。 惠普实验室布里斯托尔作为OCR压缩研究的下一阶段发展。 工作重点更多地放在提高拒绝效率上，而不是基础级别的准确性。 在这个项目结束时，到1994年底，发展完全停止。 该发动机被送到UNLV进行1995年的OCR精度年度测试[1]，在那里它证明了它对当时商用发动机的价值。 2005年底，惠普发布了Tesseract开源软件。 它现在可以在http://code.google.com/p/tesseract-ocr上找到。
2. Architecture
由于惠普自主开发了用于产品的页面布局分析技术（因此未公开发布），Tesseract从未需要自己的页面布局分析。 因此，Tesseract假定它的输入是一个二进制图像，并且具有可选的多边形文本区域。
加工遵循传统的一步一步的流程，但其中一些阶段在他们的一天是不寻常的，甚至现在可能仍然如此。 第一步是连接组件分析，其中存储组件的轮廓。 这在当时是一个计算上昂贵的设计决策，但具有显着的优势：通过检查轮廓的嵌套以及子孙轮廓的数量，检测反向文本并将其识别为黑色很简单 - 白色文本。 Tesseract可能是第一款能够轻松处理白底黑字文本的OCR引擎。 在这个阶段，轮廓被聚集在一起，纯粹是通过嵌套到Blob中。
斑点被组织成文本行，并分析线条和区域的固定间距或比例文本。 根据字符间距的种类，文本行被分为不同的单词。 固定间距文本立即被字符单元切碎。 比例文本使用有限空间和模糊空间分解成单词。
识别然后作为一个双向过程进行。 在第一遍中，尝试依次识别每个单词。 每个令人满意的词都作为训练数据传递给自适应分类器。 自适应分类器则有机会更准确地识别页面下方的文本。
由于自适应分类器可能已经学到了一些有用的信息，不足以在页面顶部附近做出贡献，因此会在页面上运行第二遍，其中再次识别未被足够识别的单词。
最后阶段解决模糊空间，并检查x高度的替代假设以找到小写字母文本。
3. Line and Word Finding
3.1. Line Finding
线条查找算法是以前发布的Tesseract的少数几个部分之一[3]。 线条查找算法的设计使得可以识别偏斜的页面而不必去偏斜，从而节省图像质量的损失。 该过程的关键部分是blob过滤和线路构建。
假设页面布局分析已经提供了大致均匀文本大小的文本区域，则简单百分比高度过滤器可以去除掉铅笔和垂直触摸字符。 高度的中位数接近区域中的文字大小，因此过滤小于中位高度的一部分的斑点是安全的，最有可能是标点符号，变音符号和噪音。
过滤后的斑点更可能适合非重叠，平行但斜线的模型。 通过x坐标对斑点进行排序和处理，可以将斑点分配到唯一的文本行，同时跟踪页面上的斜率，极大地减少在出现歪斜时分配给不正确文本行的危险。 一旦将过滤后的斑点分配给线条，则使用最小二乘法拟合中值[4]来估计基线，并将过滤出的斑点拟合回合适的线条中。
线条创建过程的最后一步是将至少水平重叠一半的斑点合并，并将变音标记与正确的基础合并在一起，并正确地关联某些损坏字符的部分。
3.2. Baseline Fitting
一旦找到文本行，使用二次样条更精确地拟合基线。 这是OCR系统的另一个首例，它使Tesseract能够处理弯曲基线的页面[5]，这是扫描中常见的工件，而不仅仅是书籍装订。
基线是通过将斑点分成几组进行拟合的，对于原始直线基线合理连续的位移。 通过最小二乘拟合将二次样条拟合到人口最多的分区（假定为基线）。 二次样条的优点是这种计算相当稳定，但缺点是当需要多个样条节段时会出现不连续性。 更传统的立方样条[6]可能会更好。
图1显示了具有拟合基线，下行线，平均线和上行线的文本行的示例。 所有这些线都是“平行的”（y分离在整个长度上是一个常数）并略微弯曲。 上行线是青色（打印为浅灰色），其上方的黑线实际上是直线。 仔细检查显示青色/灰色线相对于其上方的黑色直线是弯曲的。
3.3. Fixed Pitch Detection and Chopping
Tesseract测试文本行以确定它们是否为固定音高。 在它找到固定音高文本的地方，Tesseract使用音高将这些词切成字符，并在这些词上禁用斩波器和关联器以用于词语识别步骤。 图2显示了一个固定间距词的典型例子。
3.4. Proportional Word Finding
非固定间距或成比例的文本间距是非常不平凡的任务。 图3显示了一些典型问题。 “11.9％”的十位和单位之间的差距与一般空间的尺寸相似，并且肯定大于“erated”和“junk”之间的空白区域。 'of'和'financial'的边框之间没有横向差距。 Tesseract通过测量基线和平均线之间有限垂直范围内的间隙来解决大部分这些问题。 在这个阶段接近阈值的空间变得模糊，以便在字识别之后做出最终决定。
4.Word Recognition
任何字符识别引擎的识别过程的一部分是确定一个单词应该如何分割成字符。 线搜索的初始分割输出首先被分类。 其余的单词识别步骤仅适用于非固定音高文本。
4.1 Chopping Joined Characters
虽然一个单词（见第6节）的结果不令人满意，但Tesseract试图通过从字符分类器中以最差的置信度切断blob来改进结果。 候选斩波点可以从轮廓的多边形近似[2]的凹顶点中找到，并且可以具有相反的另一个凹顶点或线段。 最多可能需要3对砍点才能成功地将加入的字符与ASCII集分开。
图4显示了一组带有箭头的候选斩波点，所选择的斩波作为跨过轮廓的'r'接触'm'的线。 印章按优先顺序执行。 任何不能提高结果可信度的印记都会被撤销，但是并未完全丢弃，因此如果需要的话，印章可以在以后由关联者重新使用。
4.2. Associating Broken Characters
当可能的印章已经用完时，如果这个词还不够好，它会被提供给关联者。 关联器将最大切碎斑点的可能组合的分割图的A *（最优先）搜索变为候选字符。 它没有实际构建分割图，而是维护访问状态的散列表。 A *搜索通过从优先级队列提取候选新状态并通过对未分类片段组合进行分类来评估它们。
有人可能会认为，这种完全切断然后联合的方法充其量是低效的，最坏的情况下可能会错过重要的印章，而且很可能是这种情况。 其优点是斩 - 后关联方案简化了维护完整分割图所需的数据结构。
当A *细分搜索在1989年左右首次实现时，Tesseract对破碎字符的准确性远远领先于当时的商业引擎。 图5是一个典型的例子。 这一成功的关键在于角色分类器，它可以轻松识别破碎的角色。
5.Static Character Classifier
5.1Features
Tesseract的早期版本使用了从Shillman等人的工作中发展出来的拓扑特征。人。 [7-8]正如Bokser [9]所描述的那样，尽管与字体和大小无关，但这些功能对于现实生活中的图像中发现的问题并不稳健。 一个中间想法涉及使用多边形近似的部分作为特征，但是这种方法对于受损字符也不稳健。 例如，在图6（a）中，轴的右侧是两个主要部分，但在图6（b）中仅有一个单一部分。
突破性的解决方案是这样的想法，即未知中的特征不需要与训练数据中的特征相同。在训练过程中，多边形近似[2]的片段用于特征，但是在识别中，从轮廓中提取小的固定长度的特征（以标准化单位），并且与聚类原型特征多对一匹配的训练数据。在图6（c）中，粗短线是从未知中提取的特征，细长线是用作原型的多边形近似的聚类片段。一个桥接这两块的原型是完全无法比拟的。一方面和两方面的三个特征是无与伦比的，但除此之外，每个原型和每个特征都很匹配。这个例子表明，匹配大型原型的小特征的这个过程很容易能够应对损坏图像的识别。它的主要问题是计算未知和原型之间距离的计算成本非常高。
从未知中提取的特征因此是三维的（x，y位置，角度），典型地具有50-100个特征，并且原型特征是4维（x，y，位置，角度，长度） 通常具有原型配置中的10-20个特征。
5.2. Classification
分类过程分两步进行。 在第一步中，类修剪器创建一个未知可能匹配的字符类的名单。 每个特征从粗略量化的三维查找表中获取它可能匹配的类的位向量，并且位向量在所有特征上求和。 具有最高计数的类（在纠正预期特征数之后）成为下一步的短名单。
未知的每个特征都会查找它可能匹配的给定类原型的位向量，然后计算它们之间的实际相似度。 每个原型字符类用逻辑和积表达式表示，每个术语称为配置，因此距离计算过程记录每个配置中每个特征以及每个原型的总体相似性证据。 根据总和特征和原型证据计算出的最佳组合距离是该类所有存储配置中最好的。
5.3. Training Data
由于分类器能够容易识别损坏的字符，所以分类器没有受到损坏字符的训练。 事实上，这个分类器仅仅从8种字体的94个字符中抽取了20个样本进行了训练，这些样式是一个单一的大小，但是具有4个属性（正常，粗体，斜体，粗体斜体），共计60160个训练样本。这是一个重要的 与其他已发布的分类器（如拥有超过一百万个样本的Calera分类器[9]）和具有1175000个训练样本的Baird 100字体分类器[10]相比。
6. Linguistic Analysis
Tesseract包含相对较少的语言分析。 每当单词识别模块正在考虑一个新的分词时，语言模块（错名为permuter）会在以下每个类别中选择最佳可用单词串：*频繁词，*词典词，*数字词，**单词词 ，顶部小写字母（带有可选的初始上限），*分类器选择字。 给定分段的最终决定就是总距离评级最低的单词，其中上述每个类别乘以不同的常数。
来自不同分段的单词可能具有不同数量的字符。 即使在分类器声称产生概率的情况下，很难直接比较这些词，而Tesseract并不这样做。 这个问题在Tesseract中通过为每个字符分类生成两个数字来解决。 第一个称为置信度，是与原型的归一化距离减去。 这使得它成为一个“信心”，因为更大的数字更好，但仍然是距离，距离越远，距离越远。 称为等级的第二个输出将来自原型的归一化距离乘以未知字符中的总轮廓长度。 单词中的字符评分可以有意义地相加，因为单词内所有字符的总长度总是相同的。
7. Adaptive Classifier
有人提出[11]并证明[12] OCR引擎可以从使用自适应分类器中受益。 由于静态分类器必须善于推广到任何类型的字体，因此其区分不同字符之间或字符与非字符之间的能力被削弱。 因此，通过静态分类器的输出进行训练的字体更敏感的自适应分类器通常[13]用于在每个文档中获得更大的区分度，其中字体的数量有限。
Tesseract不使用模板分类器，但使用与静态分类器相同的特征和分类器。 除了训练数据之外，静态分类器和自适应分类器之间的唯一显着差异是自适应分类器使用各向同性基线/ x高度归一化，而静态分类器通过质心（第一时刻）对位置和第二 各向异性尺寸标准化的时刻。
基线/ x高度标准化使区分大写和小写字符以及提高对噪点的免疫力变得更容易。 字符矩归一化的主要好处是去除字体宽高比和一定程度的字体笔画宽度。 它还使得子和上标识别更简单，但需要额外的分类器功能来区分一些大写和小写字符。 图7显示了基线/ x高度归一化形式和矩归一化形式的3个字母的示例。
8. Results
Tesseract被纳入第四届UNLV年度OCR精度测试[1]，如“HP Labs OCR”，但代码自那时以来发生了很大变化，包括转换为Unicode和再培训。 表1比较了Tesseract最新版本（显示为2.0）和原始1995年结果（显示为HP）的结果。 显示了1995年测试中使用的所有四个300DPI二元测试组以及错误数量（Errs），百分比错误率（％Err）和相对于1995年结果的百分比变化（％变化） 字符错误和非停止字错误。 [1]更多最新结果位于http://code.google.com/p/tesseract-ocr。
9. Conclusion and Further Work
在休眠10年以上之后，Tesseract现在在精度方面落后于领先的商业引擎。 它的关键优势可能是它不寻常的功能选择。 它的关键弱点可能是它使用多边形逼近作为分类器的输入，而不是原始轮廓。 随着国际化的完成，通过明智地添加基于隐马尔科夫模型的特征n-gram模型，以及可能改进的斩波器，准确度可能会显着提高。
10.Acknowledgements
作者要感谢John Burns和Tom Nartker为使Tesseract开源，UNLV的ISRI小组分享他们的工具和数据，以及Luc Vincent，Igor Krivokon，Dar-Shyang Lee和Thomas Kielbus所作的努力。 他们对本文内容的评论。
原文: https://github.com/tesseract-ocr/docs/blob/master/tesseracticdar2007.pdf
该译文仅供大家学习交流.译文有很多翻译不好地方希望大家一起改进.欢迎改进转载.