wanghaisheng
commented
8 years ago 2.2 免切割的 OCR
Nagy在Nag92中呼吁做版面分析的人放弃孤立的字符识别，使用整体式方法，在识别过程中更多的使用语境信息。这种方法在识别单个字符时，不仅仅根据字符自身的特征，同时也考虑字符出现的上下文。
在整体式的方法中，会从整字、字的部分、ligatures中提取具有分辨能力的特征。然后用这些特征来训练出一个(HMM或者ANN)分类器来识别整字。免切割的方法通常也称之为整体识别( integrated seg- mentation/recognition)或者隐式识别( implicit recognition)技术。这类方法在文本行上做字符定位和识别，避免了单字、单字符的切割.
比较有名的免切割算法就是基于 HMM 的，在很长的时间里都是最主流的 OCR 方法 。2.2.1 章 详细描述了此类方法。 最新的是利用 RNN+ CTC 来实现免切割的。2.2.2介绍了这类方法。
2.2.1 基于HMM的OCR方法
Hidden Markov Models (HMM) 是随机模型，基础过程是由 Markov Property(the current state of the process is independent of its previous states) 控制的 . 对于免切割的 OCR ，每个字符、字或者ligature 都是由图2.3张的所示的固定数量的状态来建模的。
纵贯文本行会有一个固定大小的窗体。 通过对这个窗体提取特征，将这个特征向量与状态通过独立的概率关联起来，称之为输出概率( emission probability).在训练过程中，会学习到文本行中的每个字符、字或者ligature的状态转移概率，然后表示成转移矩阵(transition matrix). 前向-后向算法 forward-backward [Rab89] 将输出与标记数据对齐。 HMM Toolkit [YY94] 是在多个场景中应用 HMM 的一个工具。与 HMM 方法论、基础算法相关的信息可查阅[Rab89]. 过去的十多年里，基于HMM 的免切割方法仍然是语音处理、手写体识别中的主导性方法 。 在印刷体的 OCR 中也有应用，比如 [MSLB98, EM08, HHK08].
2.2.2 序列学习的方法
在序列学习[Gra12]中，在整个序列中而不是单个组件上进行有监督学习。输入和输出都是序列，分类器的任务就在于完成序列与序列的映射。RNN 是众多 序列学习任务所采用的核心分类器。隐层神经元间的反馈机制使得其能够记住序列的语境，因此能够学习到较长的语境信息。然而实际应用中并不能记住非常长的语境信息。主要问题在于使用了梯度下降的学习，当错误信号传播回来会更新内部权重链接。
[HS97, BSF94]中证明 一阶梯度值 要么指数级增长引发梯度爆炸，要么消失后带来梯度消失问题。这就使得 RNN 训练过程很漫长 不实用。RNN的训练问题已经被Hochreiter and Schmidhuber [HS97]解决，通过在隐层中将传统的激活单元替换成记忆cell，也就是 Long Short-Term Memory (LSTM), 从而能够较长时间的保持梯度值。
但是，神经网络需要切割好的输入，这样才能学习到输入与目标的关系. This requirement of input segmentation renders them unsuitable to learn the complete sequences. 在基于 LSTM 的序列学习任务中，CTC算法，类似于 HMM 的前向-后向算法用于将神经网络的输出与对应标签进行对齐。这类学习算法的输出是离散式的标签序列。对于文本识别类任务，标签也就是字符串。 图2.4是一个说明。
2.1 基于分割的OCR segmentation -based OCR 一般而言，需要将待识别的内容分割成区块/文本块，然后把文本块分割成文本行text line，然后再分割成单词，再到单个字符。字符识别器会逐个识别分割好的字符。
第一步：确定用于最后识别阶段所用的组件。严重依赖从文本中提取单个字符。 Tesseract是基于分割的OCR的经典系统，在这种模式下，对于印刷体和手写字符串分割 有很多方法，在文章CL96,Lu95，SSR10提到。 这类方法又可以分为两大类：
除了直接匹配图片之外，还有一种基于特征的模板匹配。首先保存好模板的特征而非图片本身。对于一个要查询的图片，抽取同样的特征，然后与存储的特征来进行匹配
在实际应用中，基于模板的匹配方法受限于图片噪声、字体多样性、touching characters 粘连字符等原因。因此，要么设计更高效的字符分割方法，要么使用诸如HMM RNN 类似HMM的输入输出对齐方法
这种方法适用于无法实现字符分割的场景。比如存在粘连字符。通过不完美的分割，可以得到字符的候选字符。然后对候选字符使用如N近邻、决策树、贝叶斯、神经网络等标准模式识别方法来识别。如果候选字符低于分类器的置信度则丢弃该字符。使用启发式方法来寻找字符在实际中不是很有用。可能会存在不完整的字符、字体等等情况导致字符分割不准确。比如‘m’ can be segmented into ‘nn’ or ‘rn’ or ‘d’ can be confused with ‘cl’.可以通过语言模型来在所有可能的候选字符中做出更准确的决定。
可以通过如下方法来确定两个字符的边界 (i) projection-based methods, where the segmenting point is found by a vertical project pro le, (ii) feature-based methods, where certain features are used to identify the character’s approximate boundary, or (iii) skeleton analysis- based methods, where a character’s thinned version is used to determine the dividing point.
2.1.1 基于模板匹配的 OCR
Tauscheck’s [Tau29] 的 OCR 专利就是基于模板匹配的。但不像现在模式匹配中用到的模板匹配算法，模板是机械式的。当光电传感器中的光没有打到检测器时就认为匹配到了。事实上，早期很多OCR系统都是基于这种类似的机械式的机制。[Han62, ERA57, IOK63].随着计算机技术的普及，模板匹配算法开始演变成基于软件的方式。在基于软件的 OCR 模板匹配流程中，先提取出单个的字符，然后将其与该字符所有可能存在的模板进行匹配(图2.1所示)。
这些模板也就是每个字符的不同类型的代表性原型。匹配过程是在像素到像素级中完成的，当匹配到的位点超过某个设定好的阈值时我们认为匹配成功。实际中所采用的基本的相似度度量方法是cross-correlation function交叉相关函数，见下面的公式
The above-mentioned process is closely related to the process of using a convolution mask1(1the cross-correlation of two functions f(x) and g(x) is equal to convolution of f(x) and g(-x)), that is, the template of a specific character.
除了直接对图片进行匹配之外，基于特征的模板匹配也是很出名的。在此类方法中，首先存储的是模板的特征而不是图片本身。对于要查询的图片，提取一些特征，然后将其与库里面的特征进行比对。实操中，模板匹配方法受制于图片噪音、字体的多样性、字符的黏连等。因此，后面才想出了要么如何高效切割字符，要么采用整体式的识别等更加复杂的方法，比如 HMMs or RNNs with HMM-或者其他输入输出对齐的方法。
2.1.2 过分切割的方法
当实在没法实现字符的正确切割时采用Over Segmentation的方法。可能会用在文档中有字符黏连的情况。相较于完美的字符切割，通过不那么完美的切割点找到候选字符，
利用标准的模式识别方法如最近邻分类、决策树、贝叶斯分类或神经网络等对候选字符进行识别。如果分类器的置信度低于某个阈值，舍弃掉这个候选字符。但实际工作中这种试探性的方法对于在候选字符中找出正确的那个并不实用。可能会出现不完整的字符、字体等多种结果。可能会对一些字符出现过分切割的情况。比如 ‘m’ 可能会切割成 ‘nn’ or ‘rn’ ，‘d’ 可能会成 ‘cl’. 要从这些候选字符中识别有一种比较好的方法 是利用语言模型在所有可能的候选字符中找出正确的那个。在语言模型构建阶段，出现在某些字符组合中的成本可以用来估计是不是最佳的结果。
有很多方法用于确定两个字符最适宜的界限 [MWW13]. 两个相近字符切割点可以利用下面的方法来定位： i) 基于投影的方法 利用垂直投影 vertical project profile, (ii) 基于特征的方法, 利用某些特征来区分字符的界限 (iii) 基于结构分析的方法，利用 character’s thinned version 确定切割点