Historical Review of OCR Research and Development
本文从历史的角度对OCR系统的研究和发展进行了思考。本文主要分为两个部分：OCR系统的研究与发展，以及商用OCR的历史发展。研发部分进一步研究了模板匹配和结构分析两种方法。研究表明，这两种方法越来越接近，似乎它们趋向于合并成一条大河。另一方面，商业产品可以分为三代，每一代都选择了一些具有代表性的OCR系统，并对其进行了详细的描述。本文还对近年来在OCR中应用的专家系统、神经网络等技术进行了评述，并提出了一些有待解决的问题。最后，我们对这个迷人的领域的未来趋势提出了我们的看法和希望。
科学技术的历史并不像一条笔直的运河，而是像一条蜿蜒曲折的蜿蜒曲折。 我们将不仅描述干流，还将描述由此产生的影响，例如当弯道改变方向后，牛轭湖就会产生。OCR的研究历史与语音识别一样，在模式识别领域中的研究历史比较悠久。在模式识别研究的早期，几乎所有人都选择了OCR这一主题。其中一个原因是文字处理起来非常方便，而且被认为是一个容易解决的问题。然而，出乎许多人的意料，在经过了一些初步的容易的进展之后，解决这个问题的巨大困难浮出水面。因此，人们对模式识别领域的许多课题都产生了兴趣，例如图像理解和三维物体识别。当然，这类研究有实际需求。一个新的领域总是给它的开拓者带来好处，但是对这些模式识别课题的研究似乎面临着一个强大的障碍。从这个意义上说，OCR的主题并不是特别的，而是普遍的，因为它包含了模式识别的基本问题，而这些问题是所有其他主题所共有的。从这个意义上说，我们尽可能从一个普遍的角度来写它的历史。事实上，这个问题是最深刻的，我们在写这本专著的时候就意识到了这一点。
另一方面，研究离不开工程应用。幸运的是，尽管文字处理器很流行，但OCR的市场需求非常强劲。例如，日本有十几家领先的公司正在销售或准备销售手写汉字读取器。到目前为止，这些复杂的机器还没有普及，但是可以肯定的是，如果价格和性能能够满足用户的要求，这些机器将作为一种非常自然的人机界面广泛应用于办公室。OCR知识的积累正在缩小用户和制造商之间的差距，这也得益于计算机技术的快速发展。
这一历史回顾大致分为三个部分。
第一部分是序曲。第二部分和第三部分分别是本文的主体部分，即研究和成果。
研究部分不仅有其自身存在的权利，而且为产品部分提供了准备，使读者在技术开发方面更容易、更深入地了解产品。研究部分又分为模板匹配和结构分析两种方法。本文表明这两种方法是收敛的。也就是说，模板匹配方法一直在吸收结构分析技术，现在这两种方法似乎正处于融合的边缘。
另一方面，我们将商业产品分为三代，每一代都选择具有代表性的OCR并对其进行详细描述。最后对专家系统和神经网络在OCR中的应用进行了评述。
这种描述可能偏向于日本的研发，但它反映了这样一个事实，即OCR的研发在日本尤其活跃和繁荣。多年来，位于茨城的电工实验室（ETL）在日本OCR技术的发展中起着关键作用。另一个原因是许多重要文件没有翻译成英文，因此我们认为这是一个向国际社会介绍其中一些文件的好机会。尽管如此，在撰写本文的过程中，我们发现了一些非常有用的参考书和评论论文，among them the books by Ullman [1], Sakai and Nagao [2], Pavlidis [3], and Mori and Sakakura book [4] and papers by Suen et al. [5], Schurman [6], and Couindan and Shivaprasad [7]. 其他书籍和评论论文都在适当的地方被参考，但是很难阅读所有与该主题相关的众多论文。因此，我们避免了传记式的描述，而是进行了大量的研究。在这里，我们没有提及文档分析和草书识别这两个非常重要的研究领域，因为本期的其他论文也参考了它们。然而，我们可能错过了一些重要的论文或专利。实际上，我们发现了一些新的论文，它们对准备这篇论文非常有用。我们非常感谢读者对本文的批评，并希望能对研究人员在OCR技术上的进步有所帮助。
1929年，陶舍克[8]在德国获得了OCR专利，1933年Handel[9]在美国也取得了同样的专利。这是我们所知的OCR概念的第一个概念。当时有些人梦想有一台能读字符和数字的机器。这一直是一个梦想，直到1950年代计算机时代到来。然而，我们认为他们的基本思想值得一提，因为它仍然存在。从这个意义上说，我们介绍了陶谢克的专利。其原理是模板/掩模匹配。这反映了当时采用光学和机械模板匹配的技术。通过机械掩模的光被光电探测器捕获并进行机械扫描。当精确匹配发生时，光无法到达探测器，因此机器可以识别打印在纸上的字符。
从数学上讲，这个原理就是叠加公理，它首先被欧几里得描述为第一卷元素中的第七公理。然而，对于人类来说，E在模式意义上与E具有相同的含义。因此，它们的等价原则是什么？到目前为止，还没有一个通用的解决方案，但它是模式识别的主要和核心问题。第七条公理是形状等价的第一条原则。我们稍后再讨论这个问题。我们将看到，叠加原理已经通过采用更先进的硬件技术，如阴极射线管和模拟电路来实现。实际上，这部原著是OCR技术主流的源头。“模板匹配法”是广义的叠加原理。
1951年，我开始在美国商业统计局工作。就硬件而言，电子技术是计算机时代的基础。
首先，电子技术使工程师们将OCR视为可能的现实。
然而，在硬件的数量和复杂性方面有很大的局限性。
通过将二维信息投影到一维信息中，基本上降低了复杂度。这种方法是由Kelner和Glauberman[lo]在1956年使用磁移位寄存器来实现的。适当放置的输入字符通过狭缝从上到下垂直扫描，打印输入纸上的反射光通过狭缝传输到光电探测器。这是一个简单的计算，只使用代数加法来获得一个与分割输入字符的狭缝内黑色部分的面积成比例的值。然后将采样值发送到寄存器，将模拟值转换为数字值。模板匹配是通过取每个采样值与相应的模板值之间的差值之和来完成的，每个值都是标准化的。这台机器没有商业化。
这里我们注意到匹配过程中的一个非常重要的点，即注册的一般问题。模板匹配过程大致可分为两个过程，即在上述两种情况下，将输入形状叠加在模板上，测量输入形状与模板的重合度。投影可以水平或垂直进行，这使得叠加过程在一个方向上保持不变。图1清楚地说明了这一点。当狭缝足够长以覆盖输入数字时，.I’轴上投影的黑色区域的值没有变化，即使数字垂直移动。然而，我们需要检测输入数字的起点和终点，以便根据相应的模板注册它。这很容易做到，因为数字都是简单连接的，相邻数字之间的每个间隔都有足够的空间。实际上，投影技术已经被广泛地应用于文档的输入字符串和图像区域的分割，这种处理在OCR术语中被称为预处理。
上面提到的两个主题告诉我们，字符本质上包含二维信息。如果我们想把维数降到1，那么我们必须扭曲字符的形状，这样机器才能识别它。对于具有少量字符的数字，可以允许这种失真。从这个意义上讲，尽管银行广泛使用MICR，但它的应用非常有限。然而，从人机界面的角度来看，它自然有一个大问题。于是人们开始处理二维信息。
当查看二维信息时，使用光学技术执行模板匹配似乎很自然。
实际上，汉南[11]（RCA集团）在1962年结合了电子学和光学技术制作了一个非常复杂的OCR。当时RCA拥有世界上最先进的电子管技术，在OCR的研究工作中得到了充分的应用。Hannan的论文总结如下：“综上所述，该程序的测试结果证明，RCA光学掩模匹配技术能够可靠地识别出完整的英语和俄语字体的所有字符（需要91个通道）。”但是，基于该技术的商用RCA OCR尚未发布公告。这项伟大的试验在没有继任者的情况下结束了。
计算机的出现在硬件和算法方面影响了OCR的设计，这是很自然的。介绍了一种逻辑模板匹配方法。最简单的方法叫做窥视孔法。我们假设所有的输入都是二进制的。二值化是OCR技术中一个重要的预处理方法。理想情况下，输入字符有两个密度级别，即黑色和白色，通常分别用1和0表示。然而，实际数据并不总是如此。我们稍后再讨论这个问题。这里我们注意到二值化不是一件容易处理的事情。
设想一个二维存储平面，在该平面上按照某种规则存储和注册二进制输入字符，字符位于右上角，如图2所示。显然，对于一个笔划大小和宽度恒定的理想角色来说，黑色部分总是黑色的，白色背景也是如此。然后为黑白区域选择适当的像素，使得所选像素能够区分输入字符和属于其他类的字符。在图2中，可以很容易地构造所谓的逻辑匹配方案，即所谓的窥视孔方法。
1957年，第一家基于光电技术的光电公司（OCR）被称为Photron公司。所读的字符是由收银机打印的数字。阅读速度为120字/秒（chs），非常高。这是由于使用了简单的逻辑操作。窥视孔的总数为100个，远大于理想的[log2^10]=4，这是获得稳定的真实数据识别所需的。
在ETL，Iijima等人[13]于1958年根据相同的方案设计了OCR。然而，与ERA相比，采用三级逻辑的设计更加系统化，因此效率更高。可识别的字符为72个字母数字；使用10x12网格。在10个像素特征下，共使用44个窥视孔。使用了ETL Mark IV计算机的逻辑电路。实际上OCR是当时ETL计划的一个更大系统的一个组件。它是机器翻译的输入设备。
自相关：如前所述，二维模板匹配在配准中有一个弱点。研究人员意识到了这一点，并开始设计新的方法，这些方法是移动不变的。两种方法特别引起了人们的注意。一种是基于自相关法，另一种是基于矩量法。后者是非常有野心的，目标是位移和旋转不变性，稍后将与傅立叶级数一起讨论，后者也是一种位移不变性的方法。
自相关法的精确公式很容易推导出来，因此可以在硬件制作之前进行仿真。这种方法现在已经司空见惯了。这是第一次可以采取这种方法。例如，在1958年，IBM7090发布了。这台功能强大的计算机很快就在某些研究中心出现了。IBM的Horowitz和Shelton[14]在1961年对自相关方法进行了非常广泛的研究。他们提出了一个非常大的专用移位寄存器机，以准确和快速地计算自相关。同年，佐藤等人。[15] 对日本政府的无线电波研究实验室进行了非常系统的自相关模拟方法。不幸的是，结果令人失望。当用最大输出值标准化时，“R”和“B”之间的差值仅为0.4%。此外，字符对“K”和“R”、“A”和“V”以及“U”和“D”之间的差异小于1%。
模板匹配的原理实际上只适用于印刷体字符的识别。
然而，我们还有另一组手写体需要考虑。手写体字符的形状变化很大，很难为其创建模板。将一种所谓的结构分析方法应用于手写体字符识别。
然而，在OCR开发的早期阶段，我们注意到除了模板匹配之外，还考虑了一些非常原始的方法。这些方法的弱点是由于当时的硬件资源有限。我们将这些方法包括在结构分析方法中，如下小节所述。
然而，这些方法在概念上标志着逻辑模板匹配的延续。实际上，与上述描述相反，这些简单的方法被应用于样式化的字体，而有些方法被应用于约束手写字符的识别。
在结构分析方法的情况下，没有数学原理。相反，这仍然是一个开放的问题，没有迹象表明它将在不久的将来得到解决。因此，我们的直觉是解决这个问题最可靠的武器。然而，似乎有一些非正式的策略可以用于结构分析。首先，我们给出了一个非常一般和基本的构想。由于一个结构可以分解为多个部分，因此可以通过这些部分的特征和这些部分之间的关系来描述它。接下来的问题是如何选择特征和它们之间的关系，使描述给每个字符一个清晰的识别。因此，特征提取成为模式识别研究的关键。
1） 狭缝/笔划分析
具体描述将沿着这条线给出。已经有人提到，窥视孔法被认为是一种模板匹配方法。现在我们尝试将其扩展到结构分析方法。窥视孔并不总是局限于一个像素。相反，它可以扩展成狭缝或窗口，从而不必固定在二维平面上的特定位置。两个像素之间的逻辑关系可以扩展为它们之间的一般关系。上述描述在图3中示出。
也许最简单的例子就是所谓的交叉计数技术，在这种技术中，扫描线被视为狭缝。狭缝的数量是它的特征。Rohland[16]在1954年提出了这种技术，其中主要使用垂直扫描。1961年，Weeks[17]以一种更简单的方式使用了这种方法。该方法在四个方向上进行扫描，即垂直、水平和两个正交对角线，每个方向用六条等距平行线覆盖一个字符。交叉计数，定义为六个光栅中每一个与黑色相交的次数。然而，三个或更多的交叉计数被视为三个，因此0、1、2和3的计数是可能的。因此，输入字符被编码成6×6~=4 1 44位二进制模式，用于基于统计决策方法的识别。统计决策方法是模式识别的重要理论方法。然而，这已经被合理地证明了，因此我们建议读者参考杜达和哈特的优秀著作[18]，海莱曼的论文[19]，特别是纳吉关于OCR的论文[20]。
这里我们从数学意义上对上述方案进行了严格的描述。狭缝通常是凸区域，在每个区域内我们可以检测到拓扑和几何特征。连接部件和黑色区域是典型特征。前者只是交叉计数，后者是黑色部分的长度或宽度。这些特征是作为狭缝形状、尺寸和位置的函数给出的。在上述情况下，由于简单的扫描机制，狭缝由一条直线简单地给出。然而，我们不必局限于这种扫描方法。
实际上，1956年的约翰逊[21]和1957年的戴蒙德[22]使用了探空仪作为狭缝，如图4所示。对于数字，似乎有两个基本点，它们是围绕着写的。因此，以两点为中心跨过一些探头/狭缝是非常有效的。这样我们就可以计算出每个狭缝中的交叉次数，并在此基础上很容易区分数字。通过给每个探空仪分配权重，这个方案会变得更加困难，这是Kamensky[23]所做的。然而，两点方案一般不适用于许多字符，因此Glucksman[24]考虑了一个更一般的方案，不涉及特定的点，这将在后面提到。
到目前为止，人们只描述狭缝内的拓扑特征，但几何特征得到了广泛的应用。特别是，我们注意到，所谓的runlength编码是非常典型的，是狭缝分析的一个特例。实际上，游程编码被认为是更高级结构分析的第一步，我们将对此进行详细讨论。这里，介绍狭缝几何特征的一个非常简单的版本。假设存在一条基线，例如左/右垂直线。几何特征是从基线到第一个黑色像素的距离。例如，如果狭缝是从字符的上到下扫描的，那么我们有一个单值函数，这很容易分析。在这种情况下，它是一个凸函数。1959年，道尔采用了这种方法。这种方法很容易扩展，稍后将讨论。
最后，作为切片行程分析方法推广的一个例子，我们可以介绍一个基于与扫描速度无关的异步读取方法的原型。这项工作由Sakai等人[26]于1963年开始。而在狭缝式的字型分析中，采用的是非常有效的字型分析方法。一些公司为OCR设计了特殊的字体，这样他们就可以利用狭缝结构分析，这将在下一节中介绍。
2 ) 模板匹配与结构分析的混合:
到目前为止，我们将识别方法大致分为两类，即模板匹配和结构分析。然而，两者之间有一个中间类。一般来说，在这些识别方法的空间中很难划出一个清晰的界限来划分类。无论如何。这种趋势是自然的，因为这两种方法都有各自的优势。例如，模板匹配对位置变化非常敏感，但是在全局匹配的意义上它可能非常强。另一方面，结构分析具有检测字符局部笔划特征的优点。所谓的分区特征方法由此诞生。其基本思想是将像素匹配松散化，取而代之的是子区域匹配，匹配对象是子区域内的局部特征。具体地说，作为第一步，输入字符被设置到一个大致划分为子区域的帧中，在每个子区域中检测一些局部特征。因此，对模板匹配位置的敏感性变得松散，因为所关心的是特定特征是否位于某些子区域内。
例如，假设一个输入字符被压缩到一个15x15数组中，其中5x5像素被作为一个子区域。因此，将阵列大致划分为一个3x3的阵列，每个阵列都检测出垂直、水平和两个正交对角线方向四种方向特征。因此，输入字符被编码成3×3×4＝36位的模式。这是2^15 X l5二进制模式的巨大缩减。这个例子是真实的，英国专利被授予NEC（27）的研究人员。蒙森也提出了类似的想法[28]。在Greanias等人[29]的研究中，我们也可以找到类似的想法，一个著名的OCR，IBM1287，就是基于此而建立的。本机还具有结构分析法的典型特点，即轮廓跟踪法，因此将在后面详细介绍。
在开始阶段，人们认为开发OCR是很容易的，而一种非常严格的阅读机器预计将在20世纪50年代引入。粗略地说，1950年代和60年代初，即试一试的时代，是研究人员设想一个理想的OCR的时期，尽管他们知道问题的难度很大。实际上，这是人工智能研究领域普遍存在的一种普遍现象。因此，一些人求助于基础研究，工程师们采取了比以往任何时候都更系统的方法。这种趋势在模板匹配和结构分析方法中都可以看到。很自然地，很难划出一条线来区分这些研究成果，包括时间和语义。例如，基础研究是在20世纪50年代末进行的，稍后将看到，对自相关方法的研究可以视为基础研究。
模式识别的数据种类繁多。在这个意义上，字符数据是唯一的特定数据。数字图像，例如气泡室照片，代表另一组数据。在这些数据中，图像描述是非常重要的，并且优先于识别。有些人认为字符识别不是很有趣，因为它的主要目的是类识别，因此这种方法过于工程化，不科学。那时候可能是真的，但这是一个误会。当我们想进一步研究时，对人物形状的描述是非常重要的。所以基础研究是必要的，并且已经完成了。
1 ) 信息论的应用:
在逻辑模板匹配（IBM在OCR系统中采用的一种方法）中，逻辑函数的构造相当繁琐。自然而然，关于自动生成判别逻辑函数的研究工作开始于ibmwatson实验室。Kamentsky和Liu[30]，[31]基于信息论给出了这样一个方案。他们给出了随机选择的逻辑函数f的判别力的度量。它的结构是f（z L s。Y、 ，其中：E。r j。J、 、是随机选择的值为I或0的像素。函数f具有典型形式。我们做了大量的实验，这个方案似乎很有前途。他们的计划是通过引入距离的概念来阐述的。因此，在功能强大的IBM计算机上实现了判别函数的自动设计系统。IBM的工程师们预见到了该程序的强大功能，并将其应用到OCR设计中。我们稍后将继续这个故事，这将提供一个教训。
2 ) 标准化:
李吉马通过自己和小组的实验，认识到模板匹配方法中规范化的重要性。因此，他认为他们应该对这个问题进行基础研究。他写了一系列关于模式识别基础研究的论文，大致分为两部分。一个是1962年的模式规范化理论[32]，另一个是1963年的特征提取理论I331。二者都非常重要，对模式识别的研究和OCR的发展都产生了很大的影响，特别是在日本。
这里我们介绍了归一化的理论以及Iijima小组所做的相关工作。实际上，模糊的概念最早是由他的工作引入模式识别研究的，而在西方，模糊的概念被广泛地归因于Marr[34]。Iizima的想法源于他对视觉观察系统建模的研究。根据his的视觉系统模型，必须引入模糊，并重点研究了位移和模糊的归一化问题。
他为观测系统设置了合理的条件，证明了变换的数学形式必须是信号f（：t’）与高斯核的卷积。这是一个模糊的转变。在研究的第一阶段，他们试图恢复观察系统的模糊效果，即模糊的标准化[35]。然而，通过OCR的实验研究，Iijima得到了模糊输入字符而不是恢复模糊效果的想法。Iijima和Yamazakii已经沿着这条线进行了研究[36]。从那时起，模糊处理在日本已经成为一种著名的预处理技术。
基于这一理论，Iijima提倡模式识别的模拟方法。实际上，他通过引入时间导出了恢复位移的偏微分和积分方程[37]。这是一个动态方程，它的形式是由f（r.t）的平均值控制的。这个方程实际上是在一个只有五个输入端的硬件系统上实现的，并且已经证实了这个方程确实可以很好地工作[38]。他们把这类方程称为一个全局关联和相依的网络。然而，实施费用太高，因此采取了另一种办法。
从数学上讲，规范化可以看作是一个线性算子。另一方面，数据是以离散形式给出的。因此，算子必须用矩阵来表示，算子的期望性质是由一组适当的特征函数上的特征值分布给出的，这些特征函数在Hilbert空间中构成了一个子空间。基于这个思想，Mori用d给出了一个位移矩阵，其中（1）取任何实值，比如0.5[39]。在那个时候，这种移位滤波器是有意义的，因为拥有一个分辨率合理的视网膜（2-D传感器）是非常昂贵的。实际上他们设计了一个9×9的视网膜。然而，使用模拟电路实现上述滤波器仍然存在问题，因为到运算放大器的扇入数太大。因此，他建议使用一个更简单的近似系统，如下所示[40]：
其中A是移位滤波器矩阵，E和P分别是单位矩阵和循环矩阵。
循环矩阵可以看作是循环边界条件下向量的移位算子（见[41]）。然而，为了制造滤波器，我们需要一个可变电阻元件，因此他建议使用场效应晶体管。专用场效应晶体管是由三菱公司制造的，福纳库波实现了该系统，相当有效[42]。
在这些公式背后，我们认真考虑了这样一个事实：即使连续函数是以离散形式出现的，我们也应该处理它们。从这个意义上讲，Mori把这些函数称为背景函数。因此，当我们将一个输入模式置换0.3个单位时，背景函数看起来是真实的。从这个意义上说，它不仅仅是一种插值技术。空间网络就是这个方法的名字，它是由小川和井川庆（431）在理论上发展起来的。目前，由于计算机技术的高度发展，这种方法在实践中得以存在。例如，一个字符用一个连续函数表示，曲率的精确公式可以很容易地从连续函数中计算出来，该函数通常是一个样条函数[44]。
另一方面，Amari引入了另一种标准化的观点，即作为特征提取后可以完成的过程[45]。他研究了这种格式成立的条件，假设线性特征提取，并证明了对于仿射变换，矩特征具有所谓的容许性质。这意味着规范化可以在特征空间上进行。从实际的角度来看，这一思想为规范化提供了一个非常重要的见解，我们不必坚持使用矩特征。
3 ) Karhunen-Loeve扩展:
Iijima的第二篇论文致力于特征提取的理论，基于对给定的规范化模式集的考虑，用
D={h（z.（r）}，其中（I）是单个图案的指定/索引编号，我们应该为图案表示空间的坐标系选择基本函数。更具体地说，他构造了以下函数
(函数映射到实际值):
5 ) 特征匹配:
从数学上讲，线性空间中的匹配等价于两个向量之间的相关内积。到目前为止，我们已经了解了模板匹配的隐含含义。现在我们试着把计划扩大一点。也就是说，向量的每个元素不能被约束为标量值，但它可以是一个向量。换言之，每个元素可以有一个结构，即，一个局部特征，例如方向或梯度。但是，我们注意到结构元素可以用向量表示。因此，展开意味着构造一个高维向量，并用高维向量做一个普通的内积。从这个意义上讲，数学形式没有变化，但元素的语义发生了变化。
实际上，这种扩张在1965年的早期阶段就被斯宾拉德（spinlad）[69]所做过。如后所述，他提取了原始笔划特征，然后试图同时匹配笔划的排列方式及其属性。笔划的方向被量化为8，笔划中心的位置也被量化为16，以观察整个笔划组的重心，例如N（北）和NE（东北）。因此，构建了一个8x16矩阵，并且在矩阵的每个条目处设置了一个3x3子矩阵，其中行是到重心的量化距离，列是量化的笔划长度。因此，元素总数为8x16~3x3=1152。因此，我们构建了1152个维向量，并测量了每个类别对应的未知输入向量和每个模板向量之间的相关性。上面的操作有点机械地扩展了相关性，但我们将“相关性”与其数学形式分开来考虑。
二维平面上的相关可以传达这样一个想法，即进行面对面的匹配。然而，这只是一种错觉。但总结一下这些并不重要。另一方面，二维平面有其自然拓扑结构，即其上的每个点都有其邻域。模糊预处理可以解释为一种将具有相关性的相邻系统合并的技术。二维网格平面的简化也是这样一种技术。上述预处理是最低级别的，也是基本的。更高一级的是梯度，例如，一个3x3邻域系统被包括在向量的一个元素中[70]。现在我们介绍安田所做的基于这一原则的工作[71]。他尝试了一种手写字符的单掩码识别系统，其中每个类的每个掩码的构造如下：
特征匹配仍然对笔划位置敏感。
从这个意义上说，为实现正常化作出了相当大的努力。然而，所谓的线性归一化是不够的，所谓的非线性归一化已经被使用[72]-[74]。其基本思想是测量线条/笔画的繁忙程度，并重新定位笔划，以便根据测量结果使忙碌程度变得一致。Tskumo等人。对标准化方法进行了有趣的比较研究。
6 ) 非线性模板匹配:
我们在子空间中构造了一个模板，而不是一个子空间的模板。在特征匹配中，我们在特征平面上构造了一个非常模糊的模板，这意味着它隐式地创建了多个属于同一类的模板。现在我们引入另一种方法来显式地生成一组模板并与之匹配，这是Sakoe[75]在1974年完成的。首先，他假设一个字符由向量的和/串联组成。我们可以很容易地将这种形状形式化为
7 ) 图形匹配
图形匹配是一种非常有用的技术，可以应用于模式识别领域的各个领域甚至其他领域。笔划段及其关系用严格数学意义上的图形表示。因此，图同构和子图同构提供了一个基本的匹配理论[81]，实际上它们是在节点数较少的情况下使用的。否则，它仍然存在复杂性的问题。Ambler等人从更实际的角度给出了严格和一般的形式化。[82]。有一些算法可以机械地寻找集团，但这通常是NP完全的。因此，考虑了一种实用的方法，即Rosenfeld等人发明的松弛法[83]。这是戴维斯首次应用于形状匹配[84]。松弛法源于Waltz的工作[85]，即所谓的块世界理解中，在标记问题中对不相容的候选标记进行剪除的滤波算法。这里我们只做了一个历史性的介绍，由于篇幅有限，而且图形匹配并不是特定的字符识别。我们推荐民谣和布朗的好书[86]，以及[3]。我们注意到图形匹配和DP匹配一样是一种独立的匹配算法。然而，为了方便起见，这两种匹配技术被包含在模板匹配方法中。
我们快速回顾了狭缝/笔划分析方法，它们构成了一套最简单的结构分析方法。这些方法的一个共同特点是它们只能部分地观察字符。由于当时硬件的使用有限，研究人员试图尽可能简单地为阅读机构建算法。因此，只检测字符的部分特征并使用简单的关系。这种趋势与模板匹配完全相同。然而，如前所述，字符信息本质上是二维的。因此，我们需要看一个角色的完整结构。事实上，研究人员从痛苦的经历中意识到了这一点。
有几种观点可以系统地看待一个角色的完整结构。这些分类如下：
在这些观点中，细化线分析的研究最为深入。当然，这是一个非常重要的方法，并在此基础上建立了许多OCR系统。这种分析方法在抽象性方面比其他分析方法都要高，除了体分解。除了体分解适用于一般形状外，体分解可被视为与细化线分析处于同一水平。在OCR中，体分解被认为克服了细化线技术的一些缺陷。当我们讨论1980年时，我们将描述这些主题。
人类将角色视为线状物体。这种观点是最直观的，至少对成年人来说是这样。这里需要严格定义“类线”。线的一个众所周知的定义是欧几里得的，它没有宽度。在数字图像表示中，我们自然不能接受这样的定义。所以一个一位的宽度是必要的，一条线的连通性需要定义。规则的网格平面是不均匀的。这种数字平面几何概念的基本定义是由Rosenfeld和Pfaltz[87]于1966年在他们划时代的论文中首次给出的。
我们将不讨论这个问题，尽管这是非常重要的，并为间伐过程提供了基础。相反，我们将证明，当用抽象的眼睛看一个角色时，分析一个角色的结构并不难。1960年，谢尔曼（Sherman）[88]认为字符是由抽象的线条组成的，并构造了一个图形。在他的图中，他忽略了一个有两条出线的节点（节点度数为2）。因此，特征节点有端点、分支点、交叉点等。邻接矩阵表示这些关系，但过于松散以至于许多不同的字符类属于一个类。例如，数字都放在同一个类中。然而，这种拓扑视图非常重要，因为它可以吸收字符形状的可怕变化。
按照这一思路，飞利浦的Beun[89]对无约束数字做了一个实验。他使用其他特征，如节点位置关系，来解析退化类。实验结果正确识别率为91.7%，替代率为2.6%。他在论文中说：“根据个人经验，我们知道在这样的实验中欺骗自己和他人是多么容易。”这句话意味着两件事。首先，说明了进行无约束字符识别的困难。当时，研究人员并没有意识到这一事实，但有少数工程师意识到了这一点。谢尔曼的雄心勃勃表明了这一点。随着经验的积累，人们逐渐变得保守。现在我们大致有三类手工印刷品，即无约束类、松散约束类和约束类。在第二代OCR中，为了便于机器识别，考虑了多种规则，最合理的目标是松散约束类。这是因为人们不喜欢被束缚，更喜欢拥有自由。然而，过多的自由会引起人们的困惑，Suen[90]通过心理学实验揭示了这一点。另一方面，我们需要一些共同的数据来比较研究人员的实验结果。因此，到目前为止已经制作了几个数据集。参见Suen等人的论文[5]。
现在我们将描述一个非常重要的预处理，称为细化。虽然可以将其视为预处理，但应将其视为不仅仅是预处理。无论如何，它需要获得抽象的行。实际上是贝恩干的[89]。一条观察到的线的宽度通常大于一个像素的宽度。因此，在保持一定约束的情况下，从两侧腐蚀管线，使管线不致断裂和缩短。
Kirsch[91]在1957年提出了细化的概念，McCormick[92]和Narashihmhan[93]编写了描述气泡室图像的程序。对于医学图像应用，Rutovitz[94]尝试过，Deutch[95]也尝试过字符识别。然而，Hilditch[96]在1969年给出了第一个系统而严格的算法。从那时起，已经提出了30多种细化算法，其中一些由Tamura[97]进行了比较。然而，众所周知，对于包含锐角和/或交点的实线，我们无法获得完全抽象的直线。这是一个无法避免的基本问题，因为使用的是本地操作。因此，对于它的实际应用，做了一些后处理。由于这是一个迭代过程，因此非常耗时。然而，细化是OCR技术中的一个基本预处理，也是识别图形的一个基本预处理，这在许多OCR系统中得到了广泛的应用。对此的研究还在继续。
现在我们来分析细化处理后的一组线条。如上所述，分析分为两部分。假设线集是一个图，一种方法是检测节点奇异点，另一种方法是描述边缘弧。对于这两个目的，3x3 windowimask已经被广泛使用。虽然检测简单和局部的线段相对容易，但要获得更多的全局线段却不那么容易。我们将在下面进一步讨论这一点。
关于弧的描述，有一种简单的技术，叫做链编码或Freeman代码，由Freeman[98]开发。它也基于3x3窗口。我们可以在一条直线上的任何一点设置一个3x3的窗口，如图7（a）所示。我们假设二值图像是从左到下扫描的。扫描最终会遇到一个黑色像素。然后线编码开始，沿着线，从中心观察相邻点，我们可以唯一地确定下一个移动像素，如图所示。八个这样的局部方向被编码，如图7（b）所示。例如，该行的代码为221100。这种编码方案自然适用于轮廓跟踪，并得到广泛应用。从某种意义上说，这是游程编码的对应部分，游程编码用于对整个平面图像进行编码。这两个阶段都是描述形状的第一步，从中我们需要更全面地描述形状。对于上面的例子，读者可以很容易地猜测，在查看链代码时存在一个角落。
考虑到工作完成的时间，Grimsdale等人[99]的工作是令人惊讶的基本和有价值的。这是第一篇系统地研究体分解的论文。整体分解的概念直观清晰；例如，字母“L”可被视为由垂直线和水平线组成。这种分解可以看作是主成分分析在模板匹配中的对应。然而，从理论的角度来处理这个问题是非常困难的。所以他们实际上是从游程编码开始分解的。当满足一定条件时，分析并连接连续的黑运行。否则，将生成字符的新部分段。
就算法而言，他们的方法相当实用。首先，他们考虑了噪音、破裂的阴影和孤立的小水滴。二是对旋转问题给出了一些证明。在找到字符中的每个段之后，就完成了对字符的最终描述。这包括两个部分：第一部分是每个线段的属性描述，即长度、坡度和曲率；第二部分是描述各个线段之间的关系，即关节表。在这个阶段，合并是为了合并重叠的片段。因此，可以看出，结构分析的基本过程，如特征增长，即宏观过程和合并，都被清楚地提到。然而，在他们的电脑里，4K指令自然要花60秒。所以他们的工作最终以基础研究告终。
格里姆代尔等人当时的工作太复杂了。因此，Spinrad[69]考虑了一种更面向工程的方法。他的方法非常简单，可以看作是狭缝法的一个应用。它由一个框架上的八个有方向的狭缝组成，在这个狭缝内设置了一个人物形象。例如，一个垂直的狭缝在画面上从左到右移动，然后对于字母“D”，在某个移动时，狭缝与“D”图像的垂直笔划相交，因此，我们可以检测到它的垂直笔划。另一方面，在分类方面，他的方法一般是基于特征匹配的，这已经被描述过了。
斯宾拉德之后，帕夫利迪斯[100]从理论的角度扩展了他的方法。他提出了第k个积分投影。所有的黑色扫描都可以用数字标记，例如，从左边开始：1、2、3等等。第k个积分投影就是第k个标记的黑色游程的和。投影法具有很强的抗噪声能力，即字符图像边界的粗糙性。在罗马字母数字的情况下，它不是那么有效，但是对于汉字来说，投影/轮廓的扩展在汉字OCR中是非常重要和广泛的。帕夫利迪斯继续严格地研究体分解。如前所述，体分解的抽象程度高于边界/轮廓分解。因此，如果我们成功地做到了这一点，我们就可以得到一个非常简单而有力的形状描述。帕夫利迪斯在其代表性的调查论文[101]中指出了这个问题：因此，无论形式主义如何，我们都面临着将S（“欧几里得平面的不规则”形子集）分割成某种“规则”形子集的任务。
这是模式识别中的一个基本问题。规律性很难证明，即使某些理论是可能的。然而，我们需要一些来自一般战略纲领的指导。我们从论文中得到一些部分：它们必须符合我们对“复杂”图片中“更简单”组成部分的直观概念，并具有明确的数学特征。这是一个非常重要的意见，应该适用于任何类型的形状分解。沿着这条思路，他提出了凸分解，但它有点僵化。一些研究人员对这个分解问题提出了质疑。这项工作仍在继续，但仍在基础研究领域。关于“规律性”，另见西蒙在本期文章。
河流跟随的概念似乎是由拉比诺[102]在1962年首次描述的。他用“观察鸟”这个词来描述曲线跟踪电路。然而，在同一年，Sublette和Tults[103]在RCA审查中报告了完全相同的想法，其中一种更具体的形式和标记技术被充分用于跟踪河流。佩罗托[104]在1963年对河流跟随进行了严格的描述，但他并不了解先行者。无论如何，Rabinow和Perotto打算为手写字符制作一个阅读系统，Sublette等人。构建了多字体字符读取软件系统。一个共同点是他们的目标字符集是丰富的变化，这反映了流跟踪的性质。另一个有趣的方面是，RCA对OCR系统采取了双向策略：一个是前面提到的面向硬件的方法；另一个是数字/软件方法。由于当时计算机的使用速度很慢，所以前者的速度很慢。很难测试他们的系统。
在演示流跟踪之前，请注意二维平面上的描述顺序。虽然我们可以获取平面上的任何坐标，但人类似乎在不知不觉中几乎不需要坐标。坐标系对于字符识别尤其重要。换言之，人类在飞机上采取自然的秩序，比如从上到下、从右到左。这种顺序对于描述形状非常重要。
图8显示了Perotto给出的一个例子，它使用了上面提到的顺序。光栅扫描的顺序是从上到下，从右到左。假设一个狭缝从右向左移动。首先，狭缝中没有黑色成分（b成分），它被标记为P，作为原理的缩写。存储位置坐标（中心点）。遵循b部分。再一次，两个b分量出现在狭缝中，都与先前检测到的b分量相连。然后状态被标记为D，表示2阶分支。下面是两个b组件。一个新的黑色组件立即出现在狭缝中，它被标记为P，它的坐标被存储起来。因此，下面是三个b组件。其中一个状态被标记为合并状态，位于状态的左边。最后，我们在狭缝中没有发现更多的b组分，从而结束了b组分的后续处理。根据两个P的坐标，第一个和第二个P分别标记为P2和P1。因此，如图8的底部所示，标记“6”。标签的顺序很重要，它反映了开头指定的顺序。
从历史上讲，第一个轮廓跟踪机制是通过使用一个叫做飞点扫描仪的模拟设备来实现的。这是由Greanias er al.[29]开发的，在ibm1287ocr系统中得到了充分的应用。
光束运动在黑色区域内衰减，这样光束就画出一条穿过边界的摆线。当时，它非常快速灵活。此外，它还可以吸收边界的粗糙度。另一方面，it5计算机的速度非常慢，并且受到边界噪声的影响。我们已经提到了使用链编码的基于计算机的轮廓跟踪机制。其他方法也曾被考虑过，但它已成为一种标准方法，尽管读者应注意一些病理病例。读者可以参考帕夫利迪斯的书[114]。
ibm1287是一个非常优秀的OCR系统，但它最终被一个除了输入输出系统和光机械系统之外的全计算机系统所取代，以及面向电子的大趋势。网格平面上的粗糙度是轮廓跟踪的首要问题。开发了一些平滑技术。3x3窗口平均化过程就是其中之一。Freeman[116]和Gallus等人[117]对轮廓曲线进行了直接平均。后者是前者的扩展，都采用链编码，并在链编码的基础上定义局部曲率。它们理论上很有趣，但由于篇幅的原因，这里省略了。
第二个问题是沿轮廓线的特征选择。第三个问题是如何分割轮廓。第三个问题是前面提到的最困难和最根本的问题。然而，我们可以通过引入字符图像大小的标准化和对图像压缩或扩展的帧进行分区来避免分割问题。这是一种特殊的方法。我们以前介绍过区域特征方法。这是基于一个轮廓被分割，强迫它进入子区域，例如，3x4像素。轮廓跟踪的方向作为特征。因此，所有特征都描述方向和位置，即轮廓是什么方向，3x4子区域的哪个分区是轮廓。从起始位置开始，沿着轮廓顺序检查这些特征。具体描述见下文。然而，我们注意到，当考虑到字符的较大形状变化/失真时，这种规范化并不总是有效的
因此，分割问题一直受到人们的重视。简单的想法是使用曲率最大值点，这是由著名的心理学证据Attneave[118]加速的。尽管已经做了很多工作，但第一个可靠的技术是由罗森菲尔德和约翰斯顿[1191]提出的。曲率在解析上是由一个局部导数函数给出的，但实际上它具有Freeman提出的全局性质。弗里曼和戴维斯对此进行了广泛的研究[120]。角点特征起着至关重要的作用。例如，有时区分“0”和“D”以及“5”和“S”，因此在这方面花了大量的精力。
然而，所开发的方法并不总是给出稳定和一致的结果。因此，另一种方法是基于一个非常强的多边形近似。从理论上讲，上述两种方法是密切相关的[122]。因此，在多边形近似方法上也做了大量的工作。这里我们给出了一些具有代表性的作品（拉默[123]、帕夫利迪斯和霍洛维茨[124]）。特别是，帕夫利迪斯等人的工作是非常一般的。它不受连接的约束。在这个意义上，它给出了一个符合人类直觉的全局近似值。其他多边形近似算法可以在[3]和[4]中找到。
事实上，Pavlidis和Ali试验了由Munson编写的IEEE数据库1.2.2的第一个文件中的无限制手写数字。输入图像被合理地近似为多边形，即不太细也不太粗。因此，很容易检测出全局凸度和凹度，这是非常重要的特征。当然，孔也是如此，并且在轮廓跟踪过程中很容易获得。取得了合理的识别效果。然而，估计结果有点困难，因为蒙森的数据是如此的草率和小。
背景分析的基本思想是由Steinbuch[125]在1957年提出的。他假设一个由电荷引起的势场，其分布与字符图像的密度分布相同。Kazmierczak[126]提出了一种简化方案，其中对电位梯度进行了编码。
如前所述，独立于他们，没有任何物理类比，格鲁克斯曼采取了一种背景分析的方法。他的方法被认为是sonding方法的扩展，其中背景的每个像素、四个定向的SONDE沿x和y轴分布。更具体地说，每个背景像素都有一个四位数的代码。这可能是二进制、三元或高阶代码。图11中示出了一个例子，其中背景区域主要被分割成七个子区域。四角区域有一个更复杂的配置，但这是没有意义的，所以使用二进制代码。因此，这些次区域被有效地合并在一起。但是，没有尝试显式的区域描述。利用特征向量进行分类，特征向量的每一个元素都是若干个三值编码像素。使用了背景特征的直方图，三值编码。理论上，特征向量有81个维度，但在实践中有30个足够了。对9种字体、52种大小写字母进行了实验。样本总数为26643个，在当时是一个很大的数字。数据集由IBM沃森研究实验室的Casey提供。正确识别率为96.8%，拒识率为0.3%，误分类率为2.9%。
我们继续历史，转向算法。SRI的Munson[127]，[28]提出了一种有趣的方法，也是基于使用轮廓跟踪的背景分析。跟踪字符图像的边界，并将一些点标记为极值点。利用这些极值点，构造凸壳，并将与边界和凸壳相邻的连接区域检测为凹陷区域，如图12[128]所示。在跟踪边界时检测到外壳。然而，关于极值点的检测，只给出了一个简单的程序。这个过程包括用右手系统顺时针追踪边界。搜索右转的点，并用一条直线连接连续的极值点，使其位于图像内部。
这种方法是局部的，会产生许多极值点，因此必须提供一些滤波技术来寻找全局极值点。没有做进一步的结构分析，凹性和封闭性都被用作特征向量的组成部分。这是根据什么分类的，如格鲁克斯曼的情况。其他部分是轮廓和“刺”，一种笔划。在手工打印的46字符FORTRAN字母表上进行了实验，测试数据的正确读取率为97%，错误率为3%。未指定数据大小。比较Glucksman和Munson的方法是很有趣的，前者只使用背景特征，而后者作为方法的一部分。两个实验都获得了较高的识别率。我们注意到Glucksman的三值编码隐含地反映了凹度和孔洞之间的关系，但是
在蒙森的案例中，背景特征被单独使用。
描述了OCR系统的研究与开发流程，包括模板匹配和结构分析两大分支。我们发现这两个分支已经发展成为一种具体的OCR技术，并且正在合并成为一个广泛的流，它构成了模式识别技术的重要组成部分。另一方面，我们追求商业OCR的发展，并将其分为三代。我们还详细介绍了一些具有代表性的OCR，从学术和工业的角度来展示OCR的历史发展。
我们描述了许多方法，其中有些方法相互关联，有些方法或多或少独立。重要的一点是，我们应该使这些方法在精确科学的意义上更加精确，而不仅仅是经验知识的积累。上面的陈述与形状模型有很大关系，在这个模型中，我们需要建立一个精确而灵活的形状数学模型，包括一个噪声模型，它可以独立于形状，但本质上与给定的形状相关。以上两种说法可能存在“鸡与蛋”的关系，但要建立科学的形状识别技术，就必须同时解决这两个问题。基于这些努力，我们将能够制造一台机器，在形状识别方面接近人类的表现。
显然，为了制造这样一台机器，应该把迄今为止提到的一些方法结合起来。将整合多种方法和互补算法。每种方法的性能和字符的模型将由阅读机知道。另一方面，一种新的方法仍然很自然，由于现代计算机技术的迅速发展，我们可以将我们的创作空间扩展到更复杂的方法上，例如形态学方法，它融合了人类的专业知识和直接使用多级图像。
在实践中，机器获得用户的信任是非常重要的。如果一个认真的用户把一个字符写得很好，那么机器就必须用低成本的机器软件以100%的准确率读取它。这意味着我们应该指定OCR的性能。到目前为止，规范还很宽松。它有时不能给用户任何信心。然而，这不是一件容易的事，事实上，它与上述问题有很大关系。在实践中，它也与手工印刷中字符形状的标准化有关。人们对诸如“0”和“D”这样的令人困惑的形状不太敏感，因此工程师应该指出这些问题，以便用户了解真实情况。当然，这样一个标准将不会受到太多限制，但更精确的意义是，它指出了人类自然欣赏的“关键特征”。在这方面，有小学教师的合作是非常有益的，以帮助儿童养成良好的习惯，书写正确和清晰的字符，并特别注意他们的特点。
OCR的研发也正朝着“单词识别”的方向发展，使用诸如地址和姓名等上下文知识。事实上，邮政地址和姓名识别机的发展已经是一种趋势。这就必然导致OCR的研发转向文档分析，而文档分析是OCR的一个组成部分。因此，OCR的研发将使其应用范围扩大到一个整体的文档阅读器，这对该领域的研究人员提出了最大的挑战。
历史告诉我们，OCR技术是由许多研究者经过很长一段时间建立起来的，隐含着类似于一个世界性的人类研究网络。在这样一个无形的论坛上，人们纷纷努力，以“竞争与合作”来推进研究工作。在这个意义上，正在组织国际会议和讲习班，以促进该地区的增长。例如，笔迹识别前沿国际研讨会和文件分析与识别国际会议将在学术和实践领域发挥关键作用。