CN100347723C - 基于几何代价与语义－识别代价结合的脱机手写汉字字符的切分方法 - Google Patents

Abstract

几何代价和语义-识别代价融合的脱机手写汉字切分方法，属于文字识别领域，其特征在于，首先通过对输入的脱机手写汉字的行图像进行分析，提取出笔段，将笔段合并成子字符块，同时给出子字符块合并的几何代价，由这些几何代价生成若干可能的候选切分方法，对每个方法用语言的二元语法模型进行评价，得到每种切分方式的语义-识别代价，最后综合几何与语义-识别代价给出最优的切分识别方案。本发明应用于手写信封地址的切分与识别上，其切分正确率可以达到93%，大大改进了传统切分方法的性能，对于其他语言文字或领域的切分问题也有一定的指导作用。

Description

基于几何代价与语义-识别代价结合的脱机手写汉字字符的切分方法

技术领域

基于几何代价与语义-识别代价结合的脱机手写汉字字符的切分方法属于字符识别领域。

背景技术

Optical Character Recognition(OCR)技术一直是模式识别中的热点问题，针对汉字识别的汉字OCR技术也有了二十余年的发展历史。脱机汉字的识别是指通过扫描仪、数码相机或者摄像头获取的汉字图像进行识别(图3)，脱机手写汉字的识别一直是一个难点。这是因为人的自然书写相对来说具有比较大的自由度，而且它不能像联机手写汉字那样提供更多额外的信息。

脱机汉字识别中涉及到一个关键的问题就是字符的切分，这是因为现行的分类器一般只是对单独图像做出识别和判决，它需要首先确定哪些部分是属于同一汉字的。对于人眼来说，将相邻汉字分开并不成为问题，但是对于机器来说，这并不是容易的。传统的切分技术基本上都依赖于几何特征作判决，一部分方法同时用到了识别器给出的置信度信息。

然而事实上从人类阅读的情况来看，仅仅依赖于以上的信息是不够的，大脑在完成把相邻汉字符图像分开的过程中更重要的是考虑相邻汉字结合的紧密程度，倾向于接受从语法和语义上更可以接受的切分结果。

汉字具有非常丰富的结构，其中相当一部分汉字具有左右的字体结构，在从左到右的书写习惯下，脱机汉字切分一个无法避免的问题就是左右结构的汉字常常被分开，例如“村庄”的“村”字切分成“木寸”，对于这样的切分，识别器也往往给出非常大的置信度，所以单纯依赖于分类器置信度的方法也是不可靠的。无论是利用几何代价的方法还是利用识别器置信度的方法，都忽视了汉字切分中实质上最有意义的特征——语义信息。

人们对于语言模型的研究已经有很长的时间，基于统计方法的统计语言模型在实践中取得明显的效果，特别是在语音识别和汉字识别的后处理技术中。主要是通过二元或者三元语法的隐马尔科夫模型(HMM)来进行识别和判决。

本发明主要利用了基于二元语法的隐马尔科夫模型来得到字符切分的语义-识别置信度，然后同时将字符切分的几何代价和字符识别的置信度信息三者结合起来，得到一个统一的切分识别代价，这一过程实际把字符的切分、识别和后处理三个过程有机地结合在一起，当切分方法决定之后字符的识别与后处理也同时完成了。实验证明，本发明是高速有效的。本发明同时提出了一种模型，统一了脱机手写汉字的切分、识别和后处理，这种汉字的切分思路是其他文献中没有出现的，具有一定的创新性。

发明内容

本发明的目的在于实现高准确率的脱机手写汉字字符切分。本方法的处理对象是输入的脱机手写汉字的行图像(图4给出了手写行图像获取的一般过程)，首先通过一些图像分析的方法，提取字符的笔段，然后由笔段合并为子字符，同时提取一系列的几何特征和参数进行评价，然后根据这些几何代价用K最短路径的优化方法寻找前K选几何代价最优的切分方式，然后对每种切分方式用基于二元语法的语言模型进行评价，得到相应的语义-识别置信度，然后将这两个代价结合得到最终的评价从而挑选出最有的字符切分方式。

本发明包含理论推导，参数估计，特征提取，候选集生成以及分类器判决这几个部分。

1理论部分

(1)基于统计语言模型的HMM语义-识别置信度

x₁x₂...x_n——行图像切分后的字符图像；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，这是一个识别核心的性能参数，因而是常数，而与输入字符图像无关；

c_i，j——由识别核心给出的第i个字符图像x_i的第j个候选识别结果(识别核心根据识别距离由小到大的升序排列识别候选字)；

一般汉字识别的后处理过程是要极大化在给定图像序列下的字符后验概率，使得满足后验概率最大化的字符串作为我们的识别字符串，即

利用Bayesian公式，我们有

$P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|x_1,x_2,...,x_n)=\frac{P(x_1,x_2,...,x_n|c_{1,k_1},c_{2,k_2},...,c_{n,k_n})P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n})}{P(x_1,x_2,...,x_n)}---\left(1\right)$

字符识别的后处理过程一般依据如下的假设来计算上式：

①由于在给定字符序列的条件下，字符图像出现概率是相对独立的，而且每幅图像只和它代表的字符有关，与其它字符没有关系，所以

$P(x_1,x_2,...,x_n|c_{1,k_1},c_{2,k_2},...,c_{n,k_n})=\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(x_i\right|c_{i,k_i})=\underset{i=1}{\overset{n}{\mathrm{\Π}}}\frac{P\left(c_{i,k_i}\right|x_i)P\left(x_i\right)}{P\left(c_{i,k_i}\right)}---\left(2\right)$

第二个等号根据的是Bayes公式。

②在不考虑语料库的情况下，各个汉字出现基本上是等概率的，因此认为各个字符出现的先验概率近似一致，即每个字符我们都认为它有等可能出现的概率；

③假定P(c_1，k1，c_2，k2，...，c_n，kn)满足二元语法模型，即仅仅是每个汉字的前一个汉字对于后一个汉字的出现有影响，那么

$P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n})=P\left(c_{1,k_1}\right)\underset{i=2}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})---\left(3\right)$

事实上从统计语言学的角度来说，采用三元语法模型更符合实际情况，对应的公式为

$P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n})=P\left(c_{1,k_1}\right)P\left(c_{2,k_2}\right|c_{1,k_1})\underset{i=3}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-2,k_{i-2}}{c}_{i-1,k_{i-1}})---\left(4\right)$

但是考虑到时间复杂度和空间复杂度，只取二元语法模型就足够了。

综合(1)(2)(3)，得到

$P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|x_1,x_2,...,x_n)=\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|x_i)\left(P\left(c_{1,k_1}\right)\underset{i=2}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})\right)\frac{\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(x_i\right)}{P(x_1,x_2,...,x_n)\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right)}$

根据假设②，并且注意到

和P(x₁，x₂，...，x_n)在字符图像序列给定的情况下是常数，那么上式说明 $P(c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|x_1,x_2,...,x_n)\∝\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|x_i)\left(P\left(c_{1,k_1}\right)\underset{i=2}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})\right)$ (“∝”符号表示“与……成正比”)。

OCR的后处理技术就是要在识别候选字集c_ij 1≤i≤n 1≤j≤N_Cand中挑选出最优的状态序列，所谓最优，就是极大化 它从某种程度上反映了识别的语义-识别置信度。

设 $k_1^{*}{k}_2^{*}...k_n^{*}=\underset{1\≤k_1,k_2,...,k_n\≤N_{\mathrm{Cand}}}{\arg \max }\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|x_i)\left(P\left(c_{1,k_1}\right)\underset{i=2}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})\right),$ 则可以挑出最优的候选字序列c_1，k1*c_2，k2*...c_n，kn*

这样就转化为HMM中的问题，如何在给定观测序列估计最优的状态序列，Viterbi方法是解决这个问题的经典算法，它的时间复杂度是O(nN_Cand ²)。N_Cand ²是识别候选字的个数，n是合并后的字符图像的块数。

Viterbi算法描述如下：

令Q[n][N_Cand]是一个二维数组，其中Q[t][j]保存了从第一个字符图像某个候选字到字节点c_t，j的最大可能候选字选择方式所具有的概率的对数值，不难看出1≤t≤n 1≤j≤N_Cand另外取一个二维指针数组Path[n][N_Cand]用于记录计算过程。初始化t＝1，1≤j≤N_Cand

Path[1][j]＝NULL

Q[1][j]＝logP(c_1，j)+log(c_1，j|x₁)

递归2≤t≤n，对1≤j≤N_Cand

$Q\left[t\right]\left[j\right]=\underset{1\≤l\≤N_{\mathrm{Cand}}}{\max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_{t,j}\right|c_{t-1,l})\}+\log P\left(c_{t,j}\right|x_t)$

$l^{*}=\underset{1\≤l\≤N_{\mathrm{Cand}}}{\arg \max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_{t,j}\right|c_{t-1,l})\}$

Path[t][j]指向字节点c_t-1，l*，即字节点c_t， j的父节点为c_t-1，l*终止t＝n $j^{*}=\underset{1\≤j\≤N_{\mathrm{Cand}}}{\arg \max }Q\left[n\right]\left[j\right],$ 最优字节点为c_n，j*。

回溯Path[n][j^*]所指的路径，输出路径上的每个字节点，得到最优状态序列作为我们的识别结果，同时得到最大可能路径的概率的对数值Q[n][j^*]。

(2)几何代价与HMM语义-识别代价的融合

s₁，s₂，...，s_l——子字符图像序列；

x₁，x₂，...，x_n——子字符图像合并后的字符图像序列；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，如前所述，是个常数；

c_i，j——山识别核心给出的第i个字符图像x_i的第j个候选识别结果(识别核心根据识别距离由小到大的升序排列识别候选字)；

与已知切分的识别后处理不同的是，我们需要极大化后验概率，也就是说在笔段合并结果给定情况下，极大化子字符合并方式和识别结果的后验概率P(x₁x₂...x_n，c_1，k1c_2，k2...c_n，kn|s₁s₂...s_l)

根据恒等式

$P(x_1{x}_2...x_n,c_{1,k_1}{c}_{2,k_2}...c_{n{,k}_n}|s_1{s}_2...s_l)=P(c_{1,k_1}{c}_{2{,k}_2}...c_{n,k_n}|x_1{x}_2...x_n,s_1{s}_2...s_l)P(x_1{x}_2...x_n|s_1{s}_2...s_l)$

当切分好图像给定后，识别过程只与切分好的图像x₁，x₂，...，x_n有关，与笔段合并结果无关，因此上式第一项的条件里面可以省略s₁s₂...s_l，简化为

$P(x_1{x}_2...x_n,c_{1,k_1}{c}_{2,k_2}...c_{n,k_n}|s_1{s}_2...s_l)=P(c_{1,k_1}{c}_{2,k_2}...c_{n,k_n}|x_1{x}_2...x_n)P(x_1{x}_2...x_n|s_1{s}_2...s_l)---\left(6\right)$

这样我们将我们需要极大化的后验概率分成两个部分，第一部分是我们前面提到的语义-识别置信度，后一部分就是子字符图像合并的几何代价，代入前面的(5)

$P(x_1{x}_2...x_n,c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|s_1{s}_2...s_l)$

$=\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|x_i)\left(P\left(c_{1,k_1}\right)\underset{i=2}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})\right)\frac{\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(x_i\right)}{P(x_1,x_2,...,x_n)\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(c_{i,k_i}\right)}P(x_1{x}_2...x_n|s_1{s}_2...s_l)---\left(7\right)$

我们将切分、识别和后处理融合在一个统一的模型下了。但是在实际操作中，因为不同的切分路径得到的字符图像的个数是不同的，而切分的字数越多，后验概率值往往越小，所以我们不能直接比较合并字数不同的切分路径的后验概率。为了消除因为合并字数不同带来的影响，我们取P(x₁x₂...x_n，c_1，k1，c_2，k2，...，c_n，kn|s₁s₂...s_l)的几何均值，即

作为我们的目标函数。

我们首先取(7)式的对数函数：

$\log P(x_1{x}_2...x_n,c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|s_1{s}_2...s_l)$

$=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(x_i\right)-\log P(x_1,x_2,...,x_n)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right)+\log P(x_1{x}_2...x_n|s_1{s}_2...s_l)$

$+\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|x_i)+\log P\left(c_{1,k_1}\right)+\underset{i=2}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})---\left(8\right)$

几何均值对应着(8)式的算术平均值，即将(8)式除以n作为我们的代价函数。

$\frac{1}{n}\log P(x_1{x}_2...x_n,c_{1,k_1},c_{2,k_2},...,c_{n,k_n}|s_1{s}_2...s_l)$

$=\frac{1}{n}(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(x_i\right)-\log P(x_1,x_2,...,x_n)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right))+\frac{1}{n}\log P(x_1{x}_2...x_n|s_1{s}_2...s_l)$

$+\frac{1}{n}(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|x_i)+\log P\left(c_{1,k_1}\right)+\underset{i=2}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}}))---\left(9\right)$

如何计算上式也不是容易的，我们需要进一步的近似来简化我们的模型。

对P(c_i，ki)，根据在汉字识别的后处理过程中的假设，在语料库未知的情况下，认为每个字在文本中出现的先验概率是一致的，即P(c_i，ki)是一个常数，从而

也是一个常数，对极大化过程无影响；

对于P(x₁，x₂，...，x_n)，它表示一列字符图像出现的概率，而字符图像的出现我们可以近似认为是一个独立的过程，前面一个字符图像出现对后面一个图像的出现基本没有影响，从而 $P(x_1,x_2,...,x_n)=\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(x_i\right).$

从而 $\frac{1}{n}\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(x_i\right)-\frac{1}{n}\log P(x_1,x_2,...,x_n)=\frac{1}{n}\log \frac{\underset{i=1}{\overset{n}{\mathrm{\Π}}}P\left(x_i\right)}{P(x_1,x_2,...,x_n)}=0$

综合上面的分析，我们将极大化(10)式简化为极大化

$T=\frac{1}{n}(\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|x_i)+\log P\left(c_{1,k_1}\right)+\underset{i=2}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}}))+\frac{1}{n}\log P(x_1{x}_2...x_n|s_1{s}_2...s_l)---\left(10\right)$

令

$\left\{\begin{array}{c}\stackrel{\‾}{H}=\frac{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|x_i)+\log P\left(c_{1,k_1}\right)+\underset{i=2}{\overset{n}{\mathrm{\Σ}}}\log P\left(c_{i,k_i}\right|c_{i-1,k_{i-1}})}{n}\\ \stackrel{\‾}{G}=\frac{\log P(x_1{x}_2...x_n|s_1{s}_2...s_l)}{n}\end{array}\right.$

所以，我们令T＝ H+ G，用T值作为我们判断最优切分的准则。其中 H可以认为是这种合并方式的平均语义-识别代价， G是这种合并方式对应的平均几何代价。

由于系统给出的几何代价是一种距离的度量，我们选用一个单调减函数来近似P(x₁x₂...x_n|s₁s₂...s_l)

$P(x_1{x}_2...x_n|s_1{s}_2...s_l)={\mathrm{\λe}}^{-\mathrm{\λ}(\frac{g}{\stackrel{\‾}{g}}-1)}---\left(11\right)$

其中λ是一个正的常数，g表示由子字符块s₁s₂...s_l合并为字符图像x₁x₂...x_n的几何代价，g表示子字符块s₁s₂...s_l所有可能的合并方式中最小的几何代价，则 $\stackrel{\‾}{G}=\frac{1}{n}\log \left(\mathrm{\λ}{e}^{-\mathrm{\λ}(\frac{g}{\stackrel{\‾}{g}}-1)}\right),$ 我们称它为归一化后的平均几何代价。

2参数估计

本算法在实现中需要估计一系列的参数。

首先我们需要为二元语法模型估计字符出现的先验概率和字符间的转移概率，为此目的我们必须收集与待切分的行图像涉及内容一致的语料库，这样才能有针对性地反映我们的语义约束条件，由不同领域预料计算出来的各个字出现的先验概率和字与字之间的转移概率是不同的。如果不能选择合适的预料库，那么系统的性能会受到比较大的影响。

例如如果需要切分的行图像是手写信封的地址，那么我们就必须收集地址数据库作为我们的语料样本。

声明如下的符号：

N_c——汉字c在语料样本中出现的次数；

N_c1c2——双字词c₁c₂在语料样本中出现的次数；

N——语料样本中的汉字总数；

P(c)——汉字c在语料样本中出现的概率；

P(c₂|c₁)——在语料样本中汉字c₁后面紧接着出现汉字c₂的概率；

P_smooth(·)——平滑处理后的概率；

M——语料样本中包含的不同汉字的个数，国家一级汉字标准包括了常用汉字3755个，我们简单地设M＝3755；

(1)估计字符的先验概率，也就是P(c)

计算每个汉字在语料库中出现的总次数N_c，并计算语料库中的汉字总数N，则

为对P(c)的估计。

(2)计算字符的转移概率

如果我们采用二元语法模型，由于 $P\left(c_2\right|c_1)=\frac{P\left(c_1{c}_2\right)}{P\left(c_1\right)},$ 那么我们首先计算c₁c₂这个词在语料库中出现的次数N_c1c2，然后用 作为对P(c₂|c₁)的估计。

(3)数据的平滑

这里面涉及到另外一个重要问题就是数据的平滑，因为不是所有的汉字都在我们的语料库中出现的。因此一部分字的先验概率和转移概率是无法计算的，在统计语言模型中，人们提出了各种方法用于数据的平滑。数据稀疏平滑处理的基本思想是当训练数据不充分时，采用某种方式对概率进行调整和修补，以得到更为精确的概率。因为(1)(2)对未出现事件的概率都低估成0，而所有事件概率之和总是1，所以它对出现过的事件给出过高的估计。因此，平滑的目标是通过将小概率(或零概率)调高一些，将大的概率调低一些，使得整体上的概率分布更均匀。平滑技术不仅解决了零概率问题，而且能够在整体上提高语言模型的性能。

平滑技术将n-gram的高阶模型与低阶模型相结合，包括了回退(back-off)和插值(interpolation)两种结合模式。

以二元语法为例，回退模式有如下形式：

$P_{\mathrm{smooth}}\left(c_2\right|c_1)=\left\{\begin{array}{cc}P\left(c_2\right|c_1)& \mathrm{if}{N}_{c_1{c}_2}>0\\ \mathrm{\γ}\left(c_1\right)P\left(c_2\right)& \mathrm{if}{N}_{c_1{c}_2}=0\end{array}\right.$

上式表明，若同现对c₁c₂在训练语料中出现过，则用P(c₂|c₁)来近似转移概率；否则，退回至低阶模型P(c₂)，γ(c₁)为归一化因子。

插值模式则是将高阶模型与低阶模型进行线性插值，有如下形式：

P_smooth(c₂|c₁)＝P(c₂|c₁)+γ(c₁)P(c₂)

插值模式与回退模式的区别在于：处理大于零的概率值时，前者利用了低阶模型的信息，而后者没有利用。两者的共同之处为：处理零概率时均利用了低阶模型的信息。由此可见，对低阶模型信息的利用是平滑技术的关键所在。

目前，常用的平滑方法有Jelinek-Mercer平滑、Katz平滑、绝对折扣平滑、Witten-Bell平滑、Kneser-Ney平滑等方法。各种平滑方法的性能随着训练语料规模的大小、n-gram模型的阶数、语料库的内容变化。其中，训练语料库规模对平滑技术性能的影响最大。

(4)字符置信度的估计

置信度反映识别的信息，即我们的识别结果究竟在多大程度上是可信的，这是我们在字符识别完成后需要做的工作。

x——待识别的字符图像；

c_j(x)——由识别核心给出的对图像x的第j个候选识别字(识别核心根据识别距离由小到大的升序排列识别候选字，因此c₁(x)就是图像x的首选识别候选字)；

d_j(x)——由识别核心给出的图像x的第j个候选识别字c_j(x)对应的识别距离，因此d₁(x)表示图像x的首选识别候选字对应的识别距离；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，该值为常数，只与识别核心本身有关；

P(c_j(x)|x)——图像x识别为c_j(x)的置信度，这是我们需要估计的对象。

一般分类器对图像x，给出它的识别候选字c₁(x)，c₂(x)，...，c_NCand(x)，同时给出相应的识别距离d₁(x)，d₂(x)，...，d_NCand(x)，如何计算P(c_j(x)|x)1≤j≤N_Cand是一个比较复杂的问题，可以考虑以下的几种办法，至于具体选用何种办法需要在计算的时间复杂度，空间复杂度和准确率方面做一个折中。

①距离经验公式

$P\left(c_j\left(x\right)\right|x)=\frac{1/d_j\left(x\right)}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\Σ}}}1/d_k\left(x\right)},1\≤j\≤N_{\mathrm{Cand}}$ 或者

$P\left(c_j\left(x\right)\right|x)=\frac{\frac{1}{d_j\left(x\right)-d_1\left(x\right)+1}}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\Σ}}}\frac{1}{d_k\left(x\right)-d_1\left(x\right)+1}},1\≤j\≤N_{\mathrm{Cand}}$ 或者

$P\left(c_j\left(x\right)\right|x)=\frac{1/d_j^2\left(x\right)}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\Σ}}}1/d_k^2\left(x\right)},1\≤j\≤N_{\mathrm{Cand}}$

②基于Gauss模型的置信度估计

$P\left(c_j\left(x\right)\right|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\mathrm{\θ}})}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\Σ}}}\exp (-\frac{d_k\left(x\right)}{\mathrm{\θ}})}$ (θ需要估计)

利用混淆矩阵可以修正估计的置信度(混淆矩阵与识别核心本身性能有关，需要估计)，修正置信度由 $P\left(c_j\left(x\right)\right|x)=\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\Σ}}}P\left(c_k\left(x\right)\right|x)P\left(c_j\left(x\right)\right|c_k\left(x\right))$ 得到。

如果我们按照上述方法估计置信度，就需要估计方差参数θ，和分类器的混淆矩阵。关于这部分内容将在本技术方案具体实施部分中介绍。一般说来，选择何种方法作为我们的分类器性能估计，需要综合考虑时间代价和存储空间代价来决定。

3特征提取

特征提取通过对行图像的图像分析，首先提取笔划参数，然后提取汉字的基本笔段，将基本笔划合并成各个子字符，同时给出几何代价的打分。

(1)行图像的参数提取阶段

这一阶段要提取三个参数

w_s——笔划宽度：

——字符平均宽度；

——字符平均高度；

①笔划宽度w_s提取

笔划宽度是指书写笔迹的宽度。首先，对文本行的水平黑像素游程进行直方图分析(水平黑游程是指横轴方向上黑象素连续占有的矩形区域，矩形的高为一个像素，宽即为水平黑游程的长度)，直方图的横轴表示水平黑游程长度，纵坐标表示具有此长度的水平黑游程个数。设直方图中对应游程个数最多的水平黑游程长度为p，对应游程个数为hist(p)，(即直方图的纵坐标最大值为hist(p)，它对应的横坐标为p)

则取 $w_s=\frac{(p-1)\×\mathrm{hist}(p-1)+p\×\mathrm{hist}\left(p\right)+(p+1)\×h(p+1)}{h(p-1)+h\left(p\right)+h(p+1)}.$

(图6给出了对图5(a)图像的直方图分析，其中p＝4，hist(p)＝690)

②字符平均宽度

的估计

字符平均宽度反映了文本行的书写风格，对字符切分有着直接的影响。首先对文本行图像作竖直方向的投影，得到投影图，此图的横坐标与文本行的横坐标一一对应，纵坐标的值为文本行中相应横坐标竖直方向上全部黑象素点的个数(图7给出了图5(a)的投影图)。对投影图水平坐标轴方向(纵坐标为0)作水平黑游程分析，并且计算全部水平黑游程的平均值，以此作为字符平均宽度的估计。对于文本行中的字符间距过小而造成字符间笔划的相互重叠的情况，可以在投影图y＝2w_s+1的水平方向上做黑游程统计，计算其平均值，可以得到较好的字符平均宽度

的估计。

(图8给出了对图5(b)竖直方向上的投影图，这就是粘连严重的情况)

③字符平均高度

的提取

字符平均高度的提取相对比较简单，只需将行图像在水平方向上平均分成若干等分(一般是五等分)，再对所有小图像的高度取平均即为字符的平均高度 (如图9)

(2)笔段提取阶段

笔段是指汉字中横竖撇捺四种基本元素，笔段提取可以有效地克服字符的粘连。笔段提取方法采用黑游程跟踪的方法，其思路是：首先在图像中寻找到一条水平黑游程，作为某一笔段的开始，然后对该水平黑游程从上向下逐行跟踪，直到跟踪结束，得到一笔段。

跟踪采用的思路：在当前水平黑游程的下一行，取包含当前黑游程所在水平位置且左右各偏移一个像素的水平范围，在此范围内找到所有的水平黑游程；然后根据笔段已有游程的平均宽度、以及由笔段已有游程拟和得到的笔段方向，选择某一水平黑游程加入到已有的笔段游程中，并更新原笔段的信息。我们将在具体实施中详细描述这个过程。

附图10和11是笔段提取的结果。

(3)笔段合并阶段

在笔段提取完成之后，还需要将笔段进一步合并。设R_i和R_j分别为两相邻笔段的外接矩形。(见附图12)

(x_i，1，y_i，1)——R_i的左上角点的坐标；

(x_i，2，y_i，2)——R_i的右下角点的坐标；

(x_j，1，y_j，1)——R_j的左上角点的坐标；

(x_j，2，y_j，2)——R_j的右下角点的坐标；

D_H(R_i，R_j)——R_i右侧和R_j左侧的水平距离(注意到D_H(R_i，R_j)值用正、负表示方向，在图12中R_i右边框的水平位置在R_j左边框的水平位置的右边，因此用负值表示；否则若R_i右边框的水平位置在R_j左边框的水平位置的左边，则用正值表示)；

D_V(R_i，R_j)——R_i底侧和R_j顶侧的垂直距离；(注意到D_V(R_i，R_j)值用正、负表示方向，在图12中R_i底侧框的垂直位置在R_j顶侧框的垂直位置的下面，因此用负值表示；否则若R_i底侧框的垂直位置在R_j顶侧框的垂直位置的上面，则用正值表示)；

width(R_i)——R_i的宽度；

width(R_j)——R_j的宽度；

我们按照下面的原则合并笔段：

①如果R_i和R_j满足在水平方向上，R_i包含R_j或者R_j包含R_i，则将笔段i，j合并；

②如果R_i和R_j满足：D_H(R_i，R_j)＜0(即R_i右边框在R_j左边框之右)，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_1$ 或 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_j\right)}>T_1,$ 则将笔段i，j合并，此处T₁为预定义门限，一般取0.7；

③如果R_i和R_j满足：D_H(R_i，R_j)＜0，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_2$ 且 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_j\right)}>T_2,$ 则将笔段i，j合并，此处T₂为预定义门限，一般取0.5；

算法将在具体实施阶段中描述，图13给出了图11的笔段合并结果

(4)子字符打分

我们把笔段合并的结果，从左向右排序记为：s₁，s₂，...，s_N，这就是我们笔段合并后的子字符图像，要完成切分，需要将这些子字符图像进行适当合并以完成切分操作。

按照下面的方式评估(s_k，s_k+1，...，s_k+nk-1)合并的几何代价。

w_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的宽度(图21)；

h_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的高度(图21)；

①字符宽度

设(s_k，s_k+1，...，s_k+nk-1)的宽度为w_k，文本行的字符平均宽度为

(如3-2步所求)，则 $S\left(w_k\right)=\left\{\begin{array}{cc}a{(\frac{w_k}{\stackrel{\‾}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\‾}{w_c}}>1\\ b{(\frac{w_k}{\stackrel{\‾}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\‾}{w_c}}\≤1\end{array}\right.$ 其中a，b均为预定义参数，我们取a＝100，b＝400。

②字符宽高比 $S\left(r\right)=\min \{c{(\frac{r}{\stackrel{\‾}{r}}-1)}^2,100\},$ 其中一般c＝100。

r为字符(s_k，s_k+1，...，s_k+nk-1)的宽高比， $r=\frac{w_k}{h_k};$

r为字符平均宽高比 $\stackrel{\‾}{r}=\frac{\stackrel{\‾}{w_c}}{\stackrel{\‾}{h_c}};$

为文本行字符平均宽度，采用前面行参数提取的估计值；

为文本行字符平均高度，采用前面行参数提取的估计值；

③字符内部子字符间的距离

字符内部子字符之间的距离反映了字符中各子字符之间的可结合的程度，一般的书写习惯是对于同一汉字内部的子字符具有相对较小的距离，而两个子字符如果不属于同一汉字，则其距离相对较大。

但是，仅仅采用上述子字符外接矩形距离量度不能完全反映子字符之间的亲合程度，必须采用更适宜的距离量度。有以下三种不同的距离量度：

i外接矩形框的水平距离：即子字符矩形框之间的水平距离(矩形框包围的区域可以有重叠)(如图14b)；

ii欧几里德距离：

两个像素点间的欧氏距离是说，如果像素点1的坐标为(x₁，y₁)像素点2的坐标为(x₂，y₂)，则这两个像素点间的欧式距离定义为

子字符A与子字符B间的欧几里德距离定义为A中全部黑像素点与B中全部黑像素点之间所有的欧式距离值的最小值。

iii平均游程距离；如图14(d)所示，我们计算两个子字符之间全部水平游程(白色游程)的长度的平均值作为我们的平均游程距离。

根据上述三种距离，我们定义(s_k，s_k+1，...，s_k+nk-1)的内部距离为 $d_{\mathrm{in}}=\frac{\underset{i=k}{\overset{i=k+n_k-1}{\mathrm{\Σ}}}{d}_{i,i+1}}{k},$ 其中子字符s_i与s_j的距离d_i，j定义为 $d_{i,j}=\underset{n}{\mathrm{\Σ}}{\mathrm{\γ}}_n{d}_{\mathrm{ij}}^n$ 即是上述三种距离的加权平均和，γ_n是加权系数，一般来说我们取γ_n都为1也就可以了。

定义内部距离分数为 $S\left(d_{\mathrm{in}}\right)=\left\{\begin{array}{cc}0& \mathrm{if}{d}_{\mathrm{in}}<0\\ 100& \mathrm{if}{d}_{\mathrm{in}}>\frac{w_k}{4}\mathrm{or}{d}_{\mathrm{in}}>\frac{\stackrel{\&OverBar;}{w_c}}{2}\\ \frac{400d_{\mathrm{in}}}{w_k}& \mathrm{otherwise}\end{array}\right.$

(图14(a)为原子字符图像，图14(b)为子字符间的外接矩形水平距离，图14(c)为子字符间欧几里德距离，图14(d)为游程距离)

④字符前后的距离

在一行手写文本中，一般字符内部子字符之间的距离要小于不同字符的子字符之间的距离，因此，我们对字符与其前后字符的子字符的距离进行了评估，并且给以打分。

假设字符(s_k，s_k+1，...，s_k+nk-1)与前后子字符之间的距离分别为D_L和D_R。

D_L——子字符s_k的外接矩形框与子字符s_k-1的外接矩形框之间的水平距离；

D_R——子字符s_k+nk-1的外接矩形框与子字符s_k+nk的外接矩形框之间的水平距离；

如果k＝1则D_L＝∞；如果k+n_k-1＝N，则D_R＝∞。最后取D＝min(D_L，D_R)。

对于字符前后距离的打分为S(D)，

$S\left(D\right)=\left\{\begin{array}{cc}100& \mathrm{if\; D}<-\stackrel{\&OverBar;}{w_c}\\ \frac{25\stackrel{\&OverBar;}{w_c}+100\stackrel{\&OverBar;}{D}-75D}{\stackrel{\&OverBar;}{D}+\stackrel{\&OverBar;}{w_c}}& \mathrm{if}-\stackrel{\&OverBar;}{w_c}\&le;D\&le;\stackrel{\&OverBar;}{D}\\ \frac{25(D_{\max }-D)}{D_{\max }-\stackrel{\&OverBar;}{D}}& \mathrm{if}\stackrel{\&OverBar;}{D}\&le;D\&le;D_{\max }\\ 0& \mathrm{if\; D}>D_{\max }\end{array}\right.$

其中 为文本行中字符的平均宽度，D和D_max分别为文本行中平均子字符外接矩形框之间的水平距离和最大子字符外接矩形框之间的水平距离。

⑤子字符的连通度估计

定义子字符s_i和子字符s_j的连通度C_ij为

字符(s_k，s_k+1，...，s_k+nk-1)的连通性由三个量来表示：

C_I——内部连通性；

C_L——左部连通性；

C_R——右部连通性；

其中内部连通性指的是字符内部子字符的连通程度；左部连通性和右部连通性指的是子字符s_k和子字符s_k-1，子字符s_k+nk-1与子字符s_k+nk之间的连通性；

$C_I=\left\{\begin{array}{cc}\frac{1}{n_k-1}\underset{i=k}{\overset{i=k+n_k-2}{\mathrm{\&Sigma;}}}{C}_{i,i+1}& n_k>1\\ 1& n_k=1\end{array}\right.$

$C_L=\left\{\begin{array}{cc}{C}_{k,k-1}& k>1\\ 1& k=1\end{array}\right.$

$C_R=\left\{\begin{array}{cc}{C}_{k+n_k-1,k+n_k}& k+n_k-1<N\\ 1& k+n_k-1=N\end{array}\right.$

连通度得分 $S\left(C\right)=100\&times;[1-\frac{1}{2}(1+C_I-\frac{C_R+C_L}{2})]$

整体的分数是以上五种分数的加权平均和 $S=\frac{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i{S}_i}{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i}.$

4候选集产生

对于目前的脱机汉字切分方法来说，利用几何方法基本上能够将粘连的汉字切开，但是切分后的单元是多于实际的汉字的数量的，这就需要我们对切分的部分进行合并，通过合适的合并算法得到最终的结果。传统的基于几何特征的切分方法往往就根据生成的几何代价由最短路径算法计算几何代价最小的切分方式，而从我们的观点认为几何代价并不是评价切分方式的最佳准则，单纯依赖于分类器置信度的方法也是不可靠的，必须要考虑上下文约束的关系，而反映语义约束关系的模型就是我们前面介绍的隐马尔科夫模型(HMM)。由于我们最后的结果是综合几何代价和语义-识别代价给出的，因此我们需要根据一定的准则产生一个切分方式的候选集，对候选集内的每个元素计算其对应的几何代价和语义-识别代价，综合得到最优切分结果。

对于已经切分好的N个子字符图像s₁，s₂，...，s_N，建立一个有向图(V，E)，其中节点数为N+1，标记为Node₁，Node₂，Node₃，...，Node_N+1，也即V＝{Node₁，Node₂，Node₃，...，Node_N+1}。对于任意的Node_i，存在从Node_i到Node_i+1，Node_i+2，Node_i+3，...的有向路径，其中路径Node_i→Node_i+j对应了从第i，i+1，...，i+j-1块子字符合并，也即合并子字符图像s_i，s_i+1，...，s_i+j-1，路径的代价就是此合并对应的几何代价。切分图每条由起点Node₁到终点Node_N+1的路径都对应了子字符图像s₁，s₂，...，s_N的一种合并方法，也就是对行图像的一种切分方式，因此我们称它为切分路径。如图20，对图16a给出的行图像提取笔画，合并子字符，图17a给出了对应的子字符块，图20给出了由此建立的切分图，可见每一条弧就代表了若干子字符的合并。

传统的方法直接搜索这个切分图(Segmentation Graph)从起点到终点的最优路径作为切分方式，而我们希望能搜索这个最优解附近的一个“邻域”，因为如果我们的几何代价函数能比较正确地反映各个子字符间的密合程度，即使最优几何代价的切分方式不是正确解，它也应该和正确切分差别不大，因此我们转向搜索切分图的次优路径。在次优路径给定的情况下，就提取基于二元语法模型的语义-识别置信度，用于“评价”我们的候选切分方式。

我们搜索次优路径的方法就是K最短路径算法，它可以对切分图计算出按路径总代价升序排列的前K选最优的切分路径(每条路径都是从起点Node₁到终点Node_N+1的)。

N_Node——图的节点数，N_Node＝N+1，N代表已经切分好的子字符图像的个数；

N_Edge——边的条数；

Start——起始节点(即为Node₁)；

Edge——终止节点(即为Node_N+1)；

K——需要计算的最优路径条数；

π^k(v)——从起点Start到节点v的路径总代价排第k的路径，其中v的取值集合为节点集Node₁，Node₂，Node₃，...，Node_N+1，所达路径代价按升序排列，因此π¹(v)就是从起点Start到端点v的最短路径，如果取v＝Node_N+1，那么π¹(Node_N+1)表示了从起点到终点的最短路径；

Γ^-1(v)——v的前趋节点的集合，即所有可能连接到v的节点的集合，对于任何u∈Γ^-1(v)，均存在路径u→v；

——两条路径的连接，其中a路径的终点是b路径的起始点，连接后的路径a□b以a路径的起点作为起点，b路径终点作为终点；

C[v]——节点v的候选路径集合；

然后按照下述步骤进行：

首先对于所有v∈V，计算π¹(v)，即分别计算从起点Start到各个节点的最短路径；

对于每个v∈V，用递归的方法计算π^k(v)，其中2≤k≤K。

如果π¹(v)，π²(v)，...，π^k-1(v)已经完成，下面介绍如何利用π¹(v)，π²(v)，...，π^k-1(v)计算π^k(v)。

如果k＝2，那么初始化候选路径集合C[v]，对v的前趋节点的集合Γ^-1(v)中的每一个元素u，找到从起点Start到节点u的最短路径，构造新的路径π¹(u)□v，添加到v的候选路径集合里，即C[v]←{π¹(u)□v|u∈Γ^-1(v)}；

如果k＞2，对路径π^k-1(v)，找到路径π^k-1(v)中v的前趋节点u₀，即路径π^k-1(v)通过节点u₀连到v。可以证明存在整数l，满足1≤l≤k-1，使得π^k-1(v)从起点Start到u₀时走过的路径与π^l(u₀)一致，也就是说π^k-1(v)恰好等于由路径π^l(u₀)的终点u₀连接到节点v，即π^k-1(v)＝π^l(u₀)□v。对这样的整数l我们再计算π^l+1(u₀)

然后我们从候选路径集合C[v]里面去掉路径π^l(u₀)□v，而把π^l+1(u₀)□v添加到候选路径集合C[v]里面。即令C[v]←{C[v]-{π^l(u₀)□v}}∪{π^l+1(u₀)□v}；则求C[v]中的最短路径，可以证明C[v]中的最短路径就是π^k(v)；

递归地用以上算法，就可以得到前K条最优切分路径，可以证明该算法在最坏情况下的时间复杂度是 其中N_Edge是弧的个数，N_Node是节点数。

5判决

我们对于输入的行图像，首先提取出各个子字符，并且给出相应的几何代价估计，再用4中的办法根据几何代价产生若干子字符的候选合并方案。

对于每个候选方案，我们用Viterbi算法计算每条子字符合并路径的语义-识别代价。

根据我们前面的推导，我们对每个行图像的前K条路径，分别计算每条路径的平均几何代价(归一化后的)G_k和平均语义-识别代价H_k，令T_k＝H_k+G_k，然后在候选路径中挑出T值最大的作为最终给出的切分方法，注意到在切分方法给出的同时，每个图像的识别结果与后处理的结果都已经同时给出。

附图说明

图1(a)：对“已给出字符正确切分的行图像样本库”，我们把它们分为两个部分，一部分作为训练样本用于计算参数，另一部分作为测试样本用于测试本发明所述方法的性能；

图1(b)：对“待切分对象涉及领域的语料库”，我们计算我们的语义约束关系，即字符出现的先验概率和字符间的转移概率(见具体实施方法的第2-1步)；

图1(c)：对“脱机手写汉字的单字图像样本库”，我们估计方差参数θ和混淆矩阵，用于我们估计各个识别字的识别置信度(见具体实施方法的第2-2-1和2-2-2步)；

图2(a)：计算几何代价与语义-识别代价融合的参数λ的过程(见具体实施方法的第9-1步)；

图2(b)：本发明所属方法实现对脱机手写汉字切分的过程；

图3：我们把手写汉字的文档通过扫描仪扫描进我们的计算机，以图像的方式存储；

图4：对于扫描进的文档图像，需要进行去噪声和二值化处理，由于本发明是以行图像为单位进行处理的，因此还需要对文档图像提取出其包含汉字的行，作为本发明的实施对象；

图5(a)：提取出的行图像的例子，字与字之间分离较好的情况；

图5(b)：提取出的行图像的例子，字与字之间粘连严重的情况；

图6：图6给出了对图5(a)图像的字符笔画宽度的直方图分析，其中长度为4的水平黑游程出现的个数最多，因此在具体实施方法的第3-1步p＝4，对应hist(p)＝690

图7：图7给出了对图5(a)图像黑色像素点竖直方向上的投影图(见具体实施方法的第3-2步)；

图8：图8给出了对图5(b)图像黑色像素点竖直方向上的投影图(见具体实施方法的第3-2步)；

图9：图9给出了具体实施方法的第3-3步字符平均高度

的估计过程；

图10和图11：图10和11是笔段提取的结果，每个小矩形包围的就是一个提取出的笔段，见具体实施方法的步骤四。

图12：R_i和R_j分别为两相邻笔段的外接矩形，图12标出了R_i右侧和R_j左侧的水平距离D_H(R_i，R_j)以及R_i底侧和R_j顶侧的垂直距离D_V(R_i，R_j)(见具体实施方法的步骤五)；

图13：图13给出了图11的笔段合并为子字符的结果(见具体实施方法的步骤五)；

图14(a)(b)(c)(d)：图14(a)为原子字符图像，图14(b)为子字符间的外接矩形水平距离，图14(c)为子字符间欧几里德距离，图14(d)为子字符之间的水平游程距离

图15：对字符前后的距离D的打分，D到S(D)的映射关系(见具体实施方法的第6-4步)；

图16(a)(b)(c)：从信封上提出的待切分的行图像；

图17(a)(b)(b)：图16(a)(b)(c)通过笔段提取和笔段合并后得到的子字符，每个子字符由一个外接矩形包围；

图18(a)(b)(c)：图17(a)(b)(b)根据几何代价评分，取其几何代价最优的子字符合并方式，合并子字符块后得到的结果；

图19(a)(b)(c)：图17(a)(b)(b)根据本申请所述方法合并子字符块后得到的结果；

图20：由图17(a)给出的子字符切分结果建立的切分图(见具体实施方法的第7-1步)；

图21：子字符合并的一般过程(见具体实施方法的步骤六)；

图22：图22解释了具体实施方法中步骤7-3的过程，这一步骤使得我们能够避免重复识别相同的字符图像；

具体实施方法

本发明的特征在于：它是借助图像采集设备和与其相连的计算机实现的，依次含有以下实现步骤：

步骤一：通过图像采集设备为下述目的采集足够的训练样本，建立相应的库

●脱机手写汉字的单字图像样本库；

●已给出字符正确切分的行图像样本库，见图1a，我们对已事先已经提取出的行图像样本标定它们的正确切分方式，然后把它们分为两个部分，一部分作为训练样本用于计算参数，另一部分作为测试样本用于测试本申请所述方法的性能；

●待切分对象涉及领域的语料库；

步骤二：参数估计

第2-1和2-2步是在给定的“待切分的行图像所涉及领域的语料库”上进行的，用于计算待切分的样本所涉及领域的语义约束关系(图1b)，我们声明如下符号代表的含义：

N_c——汉字c在语料样本中出现的次数；

N_c1c2——双字词c₁c₂在语料样本中出现的次数；

N——语料样本中的汉字总数；

P(c)——汉字c在语料样本中出现的概率；

P(c₂|c₁)——在语料样本中汉字c₁后面紧接着出现汉字c₂的概率；

P_smooth(·)——平滑处理后的概率；

M——语料样本中包含的不同汉字的个数，国家一级汉字标准包括了常用汉字3755个，我们可以简单地设M＝3755；

第2-1步：在语料样本上估计P(c)，也就是字符c出现的先验概率；另外还要估计字符间的转移概率，也就是P(c₂|c₁)：

2-1-1步： $P\left(c\right)=\frac{N_C}{N},$ N_c为计算得到的每个汉字在语料库中出现的总次数；

2-1-2步：对于二元语法模型， $P\left(c_2\right|c_1)=\frac{N_{c_1{c}_2}}{N_{c_1}},$ 其中N_c1c2为计算得到的c₁c₂这个词在语料库中出现的次数；

2-1-3步：我们采用了以下简单的处理方法来平滑数据，对于二元语法模型：

$P_{\mathrm{smooth}}\left(c_2\right|c_1)=\left\{\begin{array}{cc}P\left(c_2\right|c_1)& \mathrm{if}{N}_{c_1{c}_2}>0\\ \mathrm{\&epsiv;}& \mathrm{if}{N}_{c_1{c}_2}=0\mathrm{and}{N}_{c_2}=0\\ \frac{1}{M}& \mathrm{if}{N}_{c_1{c}_2}=0\mathrm{and}{N}_{c_2}>0\end{array}\right.$

其中ε是一个预先给定的很小的正数，取ε＝10^-9；

第2-2步是在“脱机手写汉字的单字图像样本库”中的单字手写汉字图象样本上计算的(图1c)，其中每个样本图像对应的正确字符是已知的，声明如下约定：

N_sample——脱机手写汉字图像样本库中图像样本的个数；

x_i——第i个样本图像；

d_j(x_i)——由识别核心给出的第i个样本图像x_i的第j个候选识别字对应的识别距离，识别核心按照识别距离的升序排列识别候选字，因此d₁(x_i)表示第i个样本图像x_i的首选识别候选字对应的识别距离；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，这是一个识别核心的性能参数，因而是常数，而与输入字符图像无关；

L_i——第i个字符图像x_i对应的正确汉字在字符图像的识别候选集中出现的序号，其中识别候选集按照识别距离的升序排列各个识别候选字；

第2-2-1步：计算脱机手写汉字识别核心对应的方差参数，用符号θ表示

首先，对在步骤一中谈到的“脱机手写汉字的单字图像样本库”的全部图像样本进行识别，对每个图像，得到N_Cand个识别候选字以及相应的识别距离；

根据识别核心提供的识别距离计算第i个样本图像x_i的首选字对应的识别距离d₁(x_i)与它的第j个识别字的识别距离之差，用y_ij表示，即令y_ij＝d_j(x_i)-d₁(x_i)，其次，极小化下式得到对参数θ的估计：

$E=\frac{1}{2N_{\mathrm{sample}}}\underset{i=1}{\overset{N_{\mathrm{sample}}}{\mathrm{\&Sigma;}}}\{\underset{j=2}{\overset{L_j}{\mathrm{\&Sigma;}}}{[\exp (-\frac{y_{\mathrm{ij}}}{\mathrm{\&theta;}})-1]}^2+\underset{j=L_i+1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{2y_{\mathrm{ij}}}{\mathrm{\&theta;}})\}$

具体的极小化方法可以采取穷举的办法，在0和100之间取10000个点，0.01，0.02，0.03，...，99.8，99.9，100，作为θ代入上式，取得其中对应E最小值的作为对θ的估计；

为了计算识别核心的混淆矩阵，我们声明如下约定：

ω^input(x)——图像x对应的真实类别；

c_j(x)——由识别核心给出的图像x的第j个候选识别结果，识别核心根据识别距离由小到大的升序排列识别候选字，因此c₁(x)就是图像x首选识别候选字；

{ω^input(x)＝ω}——对应的真实字符为ω的图像的样本集合；

#{ω^input(x)＝ω}——对应的真实字符为ω的图像样本的个数；

第2-2-2步：计算混淆矩阵

混淆矩阵是一个M×M的矩阵，其中M表示语料样本中包含了多少种不同的汉字，国家标准一级汉字字符集有3755个汉字，我们可设M＝3755；如果我们把所有汉字按任意选定的顺序排列，char₁，char₂，...，char_M，那么混淆矩阵的第α行第β列的元素就是P(char_β|char_α)，表示实际类别是char_α，但是却被识别核心识为char_β概率；

根据公式 $P\left({\mathrm{char}}_{\mathrm{\&beta;}}\right|{\mathrm{char}}_{\mathrm{\&alpha;}})=\frac{1}{\#\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right)={\mathrm{char}}_{\mathrm{\&alpha;}}\}}\underset{x\&Element;\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right)={\mathrm{char}}_{\mathrm{\&alpha;}}\}}{\mathrm{\&Sigma;}}\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P(c_j\left(x\right)={\mathrm{char}}_{\mathrm{\&beta;}}|x)$ 计算出与识别核心相关的混淆概率矩阵，其中#{ω^input(x)＝char_α}为对应于真实字符为char_α的图像样本的个数；

其中 $P(c_j\left(x\right)={\mathrm{char}}_{\mathrm{\&beta;}}|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\mathrm{\&theta;}})}{\underset{i=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{d_i\left(x\right)}{\mathrm{\&theta;}})},$ 它是识别核心给出的对图像x的识别结果为char_β的置信度；

$\underset{x\&Element;\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right)={\mathrm{char}}_{\mathrm{\&alpha;}}\}}{\mathrm{\&Sigma;}}\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P(c_j\left(x\right)={\mathrm{char}}_{\mathrm{\&beta;}}|x)$ 表示真实字符为char_α，但是识别候选字中包含了char_β的全部字符图像中关于char_β的识别置信度之和；

除了上述四个方面外，我们还需要估计几何代价与语义-识别代价融合的参数λ，它由行图像的训练样本计算而来(图2a)，我们放在最后一个部分来介绍如何估计参数λ；

步骤三：字符行图像参数提取

这一步完成对行图像参数的提取，包括笔划宽度、字符平均宽度和字符平均高度，涉及到如下的参数的估计：

w_s——笔划宽度；

——字符平均宽度；

——字符平均高度；

第3-1步：笔划宽度，即书写笔迹的宽度w_s估计

首先，对文本行的水平黑像素游程进行直方图分析，水平黑游程是指横轴方向上黑象素连续占有的矩形区域，矩形的高为一个像素，宽即为水平黑游程的长度，直方图的横轴表示水平黑游程长度，纵坐标表示具有此长度的水平黑游程个数；设直方图中对应游程个数最多的水平黑游程长度为p，对应游程个数为hist(p)，也就是说直方图的纵坐标最大值为hist(p)，它对应的横坐标为p，

则取 $w_s=\frac{(p-1)\&times;\mathrm{hist}(p-1)+p\&times;\mathrm{hist}\left(p\right)+(p+1)\&times;h(p+1)}{h(p-1)+h\left(p\right)+h(p+1)};$

(图6给出了对图5(a)图像的直方图分析，其中p＝4，hist(p)＝690)

第3-2步：平均字符宽度

的估计

字符平均宽度反映了文本行的书写风格，对字符切分有着直接的影响；首先对文本行图像作竖直方向的投影，得到投影图，此图的横坐标与文本行的横坐标一一对应，纵坐标的值为文本行中相应横坐标竖直方向上全部黑象素点的个数(图7给出了图5(a)的投影图)；对投影图水平坐标轴方向(纵坐标为0)作水平黑游程分析，并且计算全部水平黑游程的平均值，以此作为字符平均宽度的估计；对于文本行中的字符间距过小而造成字符间笔划的相互重叠的情况，可以在投影图y＝2w_s+1的水平方向上做黑游程统计，计算其平均值，可以得到较好的字符平均宽度

的估计；

(图8给出了对图5(b)竖直方向上的投影图，这就是粘连严重的情况)

第3-3步：字符平均高度

的估计

字符平均高度的提取相对比较简单，只需将行图像在水平方向上平均分成若干等分(一般是五等分)，再对所有小图像的高度取平均即为字符的平均高度

(如图9)

步骤四：笔段提取阶段

笔段是指汉字中横竖撇捺四种基本元素，笔段提取可以有效地克服字符的粘连；

笔段提取方法采用黑游程跟踪的方法，其思路是：首先在图像中寻找到一条水平黑游程，作为某一笔段的开始，然后对该水平黑游程从上向下逐行跟踪，直到跟踪结束，得到一笔段；

跟踪采用的思路：在当前水平黑游程的下一行的某个范围内，通常是当前水平黑游程所在位置左右各偏移若干像素(一般我们左右各偏移一个像素)，找到所有的水平黑游程，并且根据已有笔段的信息，如笔段已有游程的平均宽度、笔段已有游程的直线拟合得到的笔段方向等，选择某一水平黑游程加入到已有的笔段游程中，并更新原笔段的信息，我们来详细描述一下这个过程，它依次含有以下步骤：

第4-1步：按照由上到下的顺序扫描到一段水平黑象素游程时，如果它不在我们已有的各个笔段的黑游程记录中，那么把它作为某一新笔段的开始，同时把这段水平黑游程添加到新笔段的黑游程记录中；

第4-2步：对于最近添加到笔段记录中的黑游程，我们再在这个水平黑游程下一行包含此水平游程的水平位置，且左右各偏移一个象素开始搜索新的水平黑游程，如果有某个水平游程的黑色象素延伸到这个区域，则将此游程提取出来；如果没有黑游程出现在这个区域，那么此笔段提取结束，回到4-1步继续搜索新的笔段；

第4-3步：对于提取出的黑游程，我们考虑如何把它添加到笔段的黑游程记录中去。这里我们需要分两个情况讨论，一种情况是上一步提取出的水平黑游程仅有一个，那么进行4-3-1步；另一种情况是上一步提取出来的水平黑游程有两个或者两个以上，那么进行4-3-2步；

第4-3-1步：

如果我们仅提取出一个水平黑游程，

■如果这一笔段已有水平黑游程的平均宽度大于等于新的水平黑游程宽度的两倍，那么判断已达到笔段结束点，笔段提取结束；

■如果新的水平黑游程宽度大于等于这一笔段已有水平黑游程的平均宽度的三倍，则判断其是一个笔段交叉点，那么根据已有的这一笔段的水平黑游程信息预测笔段方向，然后再在预测的方向上左右各偏移笔段水平黑游程平均宽度的一半，作为新的笔段黑游程加入到记录中；

■如果新的水平黑游程宽度不满足上述两个前提，则判断它为合理的笔段黑游程，直接添加到笔段的水平黑游程记录中来；

第4-3-2步：

如果我们提取出两个或以上的水平黑游程，那么我们首先利用已有的笔段水平黑游程信息预测笔段的方向，然后提取在预测方向上的游程作为我们的候选水平黑游程，最后重复4-3-1的三个判断更新黑游程记录表；

步骤4-3-1和4-3-2采用的预测方法如下：对于笔段已经跟踪出来的所有水平黑游程分别求中点，然后按照最小二乘原则用线性函数拟合这些中点，同时根据拟合出的直线预测出笔段的方向；

第4-4步：判决笔段的属性

对于提取出的笔段，我们首先分别计算它的高度和宽度

■如果这一笔段所有水平黑游程的平均宽度大于给定的阈值(一般我们设为10个像素)，并且笔段宽度大于笔段高度，那么判断它为横笔划。

■我们设定一个小步长，用MinStepLength表示(一般我们取3像素)

◆计算第i行和第i+MinStepLength行这两行的水平黑游程中点(“+”表示加号)

■如果中点一致，那么角度累加器加上

■如果第i行中点横坐标大于第i+MinStepLength行中点的横坐标，那么角度累加器加上

■如果第i行中点横坐标小于第i+MinStepLength行中点横坐标，那么角度累加器加上

◆从每个笔段的第一行往下一直扫描到距离笔段高度为零处为MinStepLength行时，也即第(笔段高度-MinStepLength)行，将所有角度相加，求平均角度

■如果平均角度大于零且比预先设定的值α₁要小(一般设α₁为10度)，那么判断为竖笔划；

■如果平均角度大于上述的α₁且小于预先设定的值α₂(一般设α₂为88度)那么判断为撇笔划

■如果平均角度大于上述的α₂且小于预先设定的值α₃(一般设α₃为98度)那么判断为横笔划；

■如果平均角度大于上述的α₃且小于预先设定的值α₄(一般设α₄为176度)那么判断为捺笔划

■如果平均角度大于上述的α₄那么判断为竖笔划

如果没有新的游程被找到，则该笔段跟踪结束；如果没有新的笔段被找到，则笔段提取结束；在每一笔段被提取出来时，笔段的属性，即横竖撇捺即也被决定；

附图10和11是笔段提取的结果，每个小笔段都由一个小的矩形所包围

步骤五：笔段合并

在笔段提取完成之后，还需要将笔段进一步合并为子字符，设R_i和R_j分别为两相邻笔段的外接矩形：(见附图12)

(x_i，1，y_i，1)——R_i的左上角点的坐标；

(x_i，2，y_i，2)——R_i的右下角点的坐标；

(x_j，1，y_j，1)——R_j的左上角点的坐标；

(x_j，2，y_j，2)——R_j的右下角点的坐标；

D_H(R_i，R_j)——R_i右侧和R_j左侧的水平距离(注意到D_H(R_i，R_j)值用正、负表示方向，在图12中R_i右边框的水平位置在R_j左边框的水平位置的右边，因此用负值表示；否则若R_i右边框的水平位置在R_j左边框的水平位置的左边，则用正值表示)；

D_V(R_i，R_j)——R_i底侧和R_j顶侧的垂直距离；(注意到D_V(R_i，R_j)值用正、负表示方向，在图12中R_i底侧框的垂直位置在R_j顶侧框的垂直位置的下面，因此用负值表示；否则若R_i底侧框的垂直位置在R_j顶侧框的垂直位置的上面，则用正值表示)；

width(R_i)——R_i的宽度；

width(R_j)——R_j的宽度；

笔段合并按照下面三个原则进行：

(1)如果R_i和R_j满足在水平方向上，R_i包含R_j或者R_j包含R_i，则将笔段i，j合并；

(2)如果R_i和R_j满足：D_H(R_i，R_j)＜0(即R_i右边框在R_j左边框之右)，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_1$ 或 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_j\right)}>T_1,$ 则将笔段i，j合并，此处T₁为预定义门限，一般取0.7；

(3)如果R_i和R_j满足：D_H(R_i，R_j)＜0，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_2$ 且 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_j\right)}>T_2,$ 则将笔段i，j合并，此处T₂为预定义门限，一般取0.5；

笔段合并算法依次含有如下的步骤：

第5-1步：初始化，笔段按水平方向上的位置从左向右排序；

第5-2步：按照原则(1)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则转向第5-1步；否则转到第5-3步；

第5-3：按照原则(2)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则转向第5-1步；否则转到第5-4步；

3：按照原则(3)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则结束；

图13给出了图11的笔段合并结果

步骤六：字符合并的几何代价评估，包括六个子步骤：

我们把笔段合并的结果，从左向右排序记为：s₁，s₂，...，s_N，这就是我们笔段合并后的子字符图像，要完成切分，需要将这些子字符图像进行适当合并以完成切分操作，我们介绍一下子字符图像的合并过程，图21示范了这一过程：

我们用(s_k，s_k+1，...，s_k+nk-1)，表示由子字符图像s_k，s_k+1，...，s_k+nk-1合并而成的字符图像，我们按照下面的方式评估(s_k，s_k+1，...，s_k+nk-1)合并的几何代价：

w_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的宽度(图21)；

h_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的高度(图21)；

第6-1步：字符宽度w_k打分，用S(w_k)表示字符宽度得分

设(s_k，s_k+1，...，s_k+nk-1)的宽度为w_k，文本行的字符平均宽度为

(如3-2步所求)，则 $S\left(w_k\right)=\left\{\begin{array}{cc}a{(\frac{w_k}{\stackrel{\&OverBar;}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\&OverBar;}{w_c}}>1\\ b{(\frac{w_k}{\stackrel{\&OverBar;}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\&OverBar;}{w_c}}\&le;1\end{array}\right.$ 其中a，b均为预定义参数，我们取a＝100，b＝400；

第6-2步：字符宽高比r打分，用S(r)表示字符宽度得分 $S\left(r\right)=\min \{c{(\frac{r}{\stackrel{\&OverBar;}{r}}-1)}^2,100\},$ 其中一般c＝100；

r为字符(s_k，s_k+1，...，s_k+nk-1)的宽高比， $r=\frac{w_k}{h_k};$

r为字符平均宽高比 $\stackrel{\&OverBar;}{r}=\frac{\stackrel{\&OverBar;}{w_c}}{\stackrel{\&OverBar;}{h_c}};$

为文本行字符平均宽度，估计值(第3-2步)；

为文本行字符平均高度，估计值(第3-3步)；

第6-3步：字符内部子字符间的距离打分

i外接矩形框的水平距离：即子字符矩形框之间的水平距离(矩形框包围的区域可以有重叠)(如图14b)；

ii欧几里德距离：

两个像素点间的欧氏距离是说，如果像素点1的坐标为(x₁，y₁)像素点2的坐标为(x₂，y₂)，则这两个像素点间的欧式距离定义为

子字符A与子字符B间的欧几里德距离定义为A中全部黑像素点与B中全部黑像素点之间所有的欧式距离值的最小值；

iii平均游程距离：如图14(d)所示，我们计算两个子字符之间全部水平游程(白色游程)的长度的平均值作为我们的平均游程距离；

根据上述三种距离，我们定义(s_k，s_k+1，...，s_k+nk-1)的内部距离为 $d_{\mathrm{in}}=\frac{\underset{i=k}{\overset{i=k+n_k-1}{\mathrm{\&Sigma;}}}{d}_{i,i+1}}{k},$ 其中子字符s_i与s_j的距离d_i，j定义为 $d_{i,j}=\underset{n}{\mathrm{\&Sigma;}}{\mathrm{\&gamma;}}_n{d}_{\mathrm{ij}}^n$ 即是上述三种距离的加权平均和，γ_n是加权系数，一般来说我们取γ_n都为1也就可以了；

定义内部距离分数为 $S\left(d_{\mathrm{in}}\right)=\left\{\begin{array}{cc}0& \mathrm{if}{d}_{\mathrm{in}}<0\\ 100& \mathrm{if}{d}_{\mathrm{in}}>\frac{w_k}{4}\mathrm{or}{d}_{\mathrm{in}}>\frac{\stackrel{\&OverBar;}{w_c}}{2}\\ \frac{400d_{\mathrm{in}}}{w_k}& \mathrm{otherwise}\end{array}\right.$

(图14(a)为原子字符图像，图14(b)为子字符间的外接矩形水平距离，图14(c)为子字符间欧几里德距离，图14(d)为游程距离)

第6-4步：字符前后的距离打分，用S(D)表示

假设字符(s_k，s_k+1，...，s_k+nk-1)与前后子字符之间的距离分别为D_L和D_R；

D_L——于字符s_k的外接矩形框与子字符s_k-1的外接矩形框之间的水平距离(与步骤五中的定义一致)；

D_R——子字符s_k+nk-1的外接矩形框与子字符s_k+nk的外接矩形框之间的水平距离(与步骤五中的定义一致)；

如果k＝1则D_L＝∞；如果k+n_k-1＝N，则D_R＝∞，最后取D＝min(D_L，D_R)；

对于字符前后距离的打分为S(D)，

$S\left(D\right)=\left\{\begin{array}{cc}100& \mathrm{if\; D}<-\stackrel{\&OverBar;}{w_c}\\ \frac{25\stackrel{\&OverBar;}{w_c}+100\stackrel{\&OverBar;}{D}-75D}{\stackrel{\&OverBar;}{D}+\stackrel{\&OverBar;}{w_c}}& \mathrm{if}-\stackrel{\&OverBar;}{w_c}\&le;D\&le;\stackrel{\&OverBar;}{D}\\ \frac{25(D_{\max }-D)}{D_{\max }-\stackrel{\&OverBar;}{D}}& \mathrm{if}\stackrel{\&OverBar;}{D}\&le;D\&le;D_{\max }\\ 0& \mathrm{if\; D}>D_{\max }\end{array}\right.$

其中

为文本行中字符的平均宽度，D和D_max分别为文本行中平均子字符外接矩形框之间的水平距离和最大子字符外接矩形框之间的水平距离；

第6-5步：连通度打分，用S(C)表示

定义子字符s_i和子字符s_j的连通度C_ij为

字符(s_k，s_k+1，...，s_k+nk-1)的连通性由三个量来表示：

C_I——内部连通性；

C_L——左部连通性；

C_R——右部连通性；

其中内部连通性指的是字符内部子字符的连通程度；左部连通性和右部连通性指的是子字符s_k和子字符s_k-1，子字符s_k+nk-1与子字符s_k+nk之间的连通性；

$C_I=\left\{\begin{array}{cc}\frac{1}{n_k-1}\underset{i=k}{\overset{i=k+n_k-2}{\mathrm{\&Sigma;}}}{C}_{i,i+1}& n_k>1\\ 1& n_k=1\end{array}\right.$

$C_L=\left\{\begin{array}{cc}{C}_{k,k-1}& k>1\\ 1& k=1\end{array}\right.$

$C_R=\left\{\begin{array}{cc}{C}_{k+n_k-1,k+n_k}& k+n_k-1<N\\ 1& k+n_k-1=N\end{array}\right.$

连通度得分 $S\left(C\right)=100\&times;[1-\frac{1}{2}(1+C_I-\frac{C_R+C_L}{2})]$

第6-6步：计算总体分值作为几何代价

整体的分数是以上五种分数的加权平均和 $S=\frac{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i{S}_i}{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i},$ 一般我们取α₁＝5，α₂＝2，α₃＝3，α₄＝5，α₅＝2

步骤七：根据已经评价出来的几何代价计算前K条几何代价最优的切分方式

当进行完步骤六之后，我们把行图像切分成了一列子字符图像(见图17(a)(b)(c)，它给出了图16(a)(b)(c)行图像切分为子字符图像的结果，每个矩形框里面包含的就是一个子字符图像，这个矩形框就是子字符图像的外接矩形框)，同时给出了子字符块之间合并的几何代价，但是我们需要进一步把子字符图像合并为字符图像从而完成字符的切分；下面我们利用步骤六得到的子字符块合并的代价，生成一些可能的子字符合并方案(每个方案都对应行图像的一种切分结果)，我们在步骤八中评价这些方案，并给出最优方案；

第7-1步：切分图建立

对于已经切分好的N个子字符图像s₁，s₂，...，s_N，建立一个有向图(V，E)，其中节点数为N+1，标记为Node₁，Node₂，Node₃，...，Node_N+1，也即V＝{Node₁，Node₂，Node₃，...，Node_N+1}；对于任意的Node_i，存在从Node_i到Node_i+1，Node_i+2，Node_i+3，...的有向路径，其中路径Node_i→Node_i+j对应了从第i，i+1，...，i+j-1块子字符合并，也即合并子字符图像s_i，s_i+1，...，s_i+j-1，路径的代价就是此合并对应的几何代价；切分图每条由起点Node₁到终点Node_N+1的路径都对应了子字符图像s₁，s₂，...，s_N的一种合并方法，也就是对行图像的一种切分方式，因此我们称它为切分路径；

(见图20，对图16a给出的行图像提取笔画，合并子字符，图17a给出了对应的子字符块，图20给出了由此建立的切分图，可见每一条弧就代表了若干子字符的合并)

第7-2步：产生前K条几何代价最优的切分路径：

我们下面介绍如何计算切分图(V，E)中从起点Node₁到终点Node_N+1按代价的升序排列的前K条路径，这里每条路径都对应了行图像的一种切分方式，实际上就是子字符图像s₁，s₂，...，s_N一种合并方案，按照此方案合并子字符s₁，s₂，...，s_N，从而完成对行图像的切分；

算法的具体过程如下：

给定图(V，E)，设

N_Node——图的节点数，N_Node＝N+1，N代表已经切分好的子字符图像的个数；

N_Edge——边的条数；

Start——起始节点(即为Node₁)；

Edge——终止节点(即为Node_N+1)；

K——需要计算的最优路径条数；

π^k(v)——从起点Start到节点v(其中v可以取节点集Node₁，Node₂，Node₃，...，Node_N+1中任何一个节点)的路径总代价排第k的路径(路径代价按升序排列)，因此π¹(v)就是从起点Start到端点v的最短路径，如果取v＝Node_N+1，那么π¹(Node_N+1)表示了从起点到终点的最短路径；

Γ^-1(v)——v的前趋节点的集合，即所有可能连接到v的节点的集合，对于任何u∈Γ^-1(v)，均存在路径u→v；

——两条路径的连接，其中a路径的终点是b路径的起始点，连接后的路径a□b以a路径的起点作为起点，b路径终点作为终点；

C[v]——节点v的候选路径集合；

然后按照下述步骤进行：

第7-2-1步：首先对于所有v∈V，计算π¹(v)，即分别计算从起点Start到各个节点的最短路径；

第7-2-2步：对于每个v∈V，用递归的方法计算π^k(v)，其中2≤k≤K；

如果π¹(v)，π²(v)，...，π^k-1(v)已经完成，下面介绍如何利用π¹(v)，π²(v)，...，π^k-1(v)计算π^k(v)；

如果k＝2，那么初始化候选路径集合C[v]，对v的前趋节点的集合Γ^-1(v)中的每一个元素u，找到从起点Start到节点u的最短路径，构造新的路径π¹(u)□v，添加到v的候选路径集合里，即C[v]←{π¹(u)□v|u∈Γ^-1(v)}；

如果k＞2，对路径π^k-1(v)，找到路径π^k-1(v)中v的前趋节点u₀，即路径π^k-1(v)通过节点u₀连到v，可以证明存在整数l，满足1≤l≤k-1，使得π^k-1(v)从起点Start到u₀时走过的路径与π^l(u₀)一致，也就是说π^k-1(v)恰好等于由路径π^l(u₀)的终点u₀连接到节点v，即π^k-1(v)＝π^l(u₀)□v，对这样的整数l我们再计算π^l+1(u₀)(由于1≤l≤k-1，那么2≤l+1≤k，可以证明这一递归计算过程是可以实现的)

然后我们从候选路径集合C[v]里面去掉路径π^l(u₀)□v，而把π^l+1(u₀)□v添加到候选路径集合C[v]里面，即令C[v]←{C[v]-{π^l(u₀)□v}}∪{π^l+1(u₀)□v}；则求C[v]中的最短路径，可以证明C[v]中的最短路径就是π^k(v)；

递归地用以上算法，就可以得到前K条切分路径；

至于如何在实际应用中选择K值，需要在时间复杂度和准确度间做一个折中，事实上，我们在实践中并不需要找到完全正确的切分方式，次优的切分方式也能保证很高的字符识别率，我们一般取K＝200，更一般的情况下我们可以选择自适应的K值(一般选择K为子字符块数的10倍)；

由于我们的候选集是按照几何代价准则生成的，因此有效的几何代价函数能使我们的候选集尽量小，同时正确的切分方式出现在比较靠前的位置；

第7-3步：字符识别

事实上，产生K候选的时间消耗并不大，时间瓶颈在于分类器识别消耗的时间，因此上述算法在我们具体应用中可以采取进一步的优化措施，注意到这前K个候选切分方式中虽然整体的切分方法不同，但是每条切分路径都存在一些共有的切分方式，因此我们没有必要对每条路径都识别一遍，也不必全部重新计算置信度，采用如下的方法：

CharCandidatesSet——图像识别候选集，其中的每个元素都包含了N_Cand个识别候选字和N_Cand个对应的识别置信度；

CharCandidatesSetNum——图像识别候选集中元素的个数；

设子字符为s₁s₂...s_N，我们建立一个(N+1)×(N+1)的查询表LookupTable，LookupTable中的元素首先全部设为-1，清空图像识别候选集CharCandidatesSet，并令CharCandidatesSetNum＝0；

For 1≤k≤K

对第k个候选切分路径(几何代价按升序排列排在第k的候选切分路径)：

对s_ps_p+1...s_q(1≤p≤q≤N)这样的合并方式，查询LookupTable中的元素LookupTable(p，q+1)(表示查询表LookupTable中第p行第q+1列的元素)；

如果LookupTable(p，q+1)＝-1，那么说明这种合并还没有被识别过，对这种组合得到的图像进行识别，得到N_Cand个候选字，并且估计每个识别候选字的置信度(第8-1步)，然后把识别候选字及其对应的识别置信度整体作为一个元素添加到图像识别候选集CharCandidatesSet，然后令LookupTable(p，q+1)＝CharCandidatesSetNum，然后令让CharCandidatesSetNum增加1，也即CharCandidatesSetNum＝CharCandidatesSetNum+1；

如果LookupTable(p，q+1)≠-1，那么说明这种合并已被考虑过，不用再处理

End For

图22详细解释了7-3这一过程，这一过程带来的好处是避免了识别核心的重复工作，大大节约了时间；在后面的步骤中如果我们需要知道子字符块s_ps_p+1...s_q合并后的识别结果时，只要查询LookupTable的第p行第q+1列元素，就可以得到子字符块s_ps_p+1...s_q合并后的识别结果在CharCandidatesSet中的序号，从而找到在CharCandidatesSet对应位置中已经记录的子字符块s_ps_p+1...s_q合并后的识别结果及相应的置信度；

步骤八：依赖于前面给出的K条几何意义下最优的候选切分方案，根据二元语法模型给出每个子字符合并方案对应的语义-识别代价：

第8-1步：字符置信度估计

x——待识别的字符图像；

c_j(x)——由识别核心给出的对图像x的第j个候选识别字(识别核心根据识别距离由小到大的升序排列识别候选字，因此c₁(x)就是图像x的首选识别候选字)；

d_j(x)——由识别核心给出的图像x的第j个候选识别字c_j(x)对应的识别距离，因此d₁(x)表示图像x的首选识别候选字对应的识别距离；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，如前2-2步所述，该值为常数，只与识别核心本身有关；

P(c_j(x)|x)——图像x识别为c_j(x)的置信度，这是我们需要估计的对象；

对于7-3步得到的所有候选字，可以针对我们具体的需要选择下面两种不同的方法估计候选字的置信度：

①距离经验公式

$P\left(c_j\left(x\right)\right|x)=\frac{1/d_j\left(x\right)}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}1/d_k\left(x\right)},1\&le;j\&le;N_{\mathrm{Cand}}$ 或者

$P\left(c_j\left(x\right)\right|x)=\frac{\frac{1}{d_j\left(x\right)-d_1\left(x\right)+1}}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\frac{1}{d_k\left(x\right)-d_1\left(x\right)+1}},1\&le;j\&le;N_{\mathrm{Cand}}$ 或者

$P\left(c_j\left(x\right)\right|x)=\frac{1/d_j^2\left(x\right)}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}1/d_k^2\left(x\right)},1\&le;j\&le;N_{\mathrm{Cand}}$

②基于Gauss模型的置信度估计 $P\left(c_j\left(x\right)\right|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\mathrm{\&theta;}})}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{d_k\left(x\right)}{\mathrm{\&theta;}})}$ (θ就是我们前面2-2-1步计算出来的)利用前面计算的混淆矩阵可以修正估计的置信度(混淆矩阵由2-2-2计算得到)，修正置信度由 $P\left(c_j\left(x\right)\right|x)=\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P\left(c_k\left(x\right)\right|x)P\left(c_j\left(x\right)\right|c_k\left(x\right))$ 得到；

估计识别置信度可以根据需要灵活选择上面的方法，在本发明中，我们采用了基于Gauss模型的置信度估计方案；

第8-2步：基于二元语法的语义-识别置信代价计算

对于已经给出的K条行图像切分路径，对每条切分路径应用以下的方法计算其对应的平均语义-识别置信代价，声明如下符号及其意义：

n_k——按照第k条切分路径合并子字符图像，共得到n_k个合并后的字符图像；

image_k，t——按照第k条切分路径合并子字符图像后的第t个字符图像，其中1≤k≤K，1≤t≤n_k；

c_j(image_k，t)——识别核心给出的字符图像image_k，t的第j个识别候选字，其中1≤j≤N_Cand，1≤k≤K，1≤t≤n_k，P(c_j(image_k，t)|image_k，t)对应它的识别置信度；

由于字符图像的识别和置信度的估计已经在7-3步中完成，在此步骤中我们可以通过查询LookupTable的方法从CharcandidatesSet中得到我们需要的识别结果和置信度；

对第k条候选切分路径，1≤k≤K，使用下述的Vieterbi方法计算语义-识别代价：

令Q[n_k][N_Cand]是一个二维数组，其中Q[t][j]保存了从第一个字符图像某个候选字到字节点c_j(image_k，t)的最大可能候选字选择方式所具有的概率的对数值，另外取一个二维指针数组Path[n_k][N_Cand]用于记录计算过程；

初始化t＝1，1≤j≤N_Cand

Path[1][j]＝NULL

Q[1][j]＝logP(c_j(image_k，1))+log(c_j(image_k，1)|image_k，1)

递归2≤t≤n_k，对1≤j≤N_Cand计算Q[t][j]

$Q\left[t\right]\left[j\right]=\underset{1\&le;l\&le;N_{\mathrm{Cand}}}{\max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_j\left({\mathrm{image}}_{k,t}\right)\right|c_l\left({\mathrm{image}}_{k,t-1}\right))\}+\log P\left(c_j\left({\mathrm{image}}_{k,t}\right)\right|{\mathrm{image}}_{k,t})$

另外找到使得Q[t-1][l]+logP(c_j(image_k，t)|c_j(image_k，t-1))最大的l，记作l^*，即

$l^{*}=\underset{1\&le;l\&le;N_{\mathrm{Cand}}}{\arg \max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_j\left({\mathrm{image}}_{k,t}\right)\right|c_l\left({\mathrm{image}}_{k,t-1}\right))\}$

然后令Path[t][j]指向字节点c_l*(image_k，t-1)，即字节点c_j(image_k，t)的父节点为c_j*(image_k，t-1)

终止t＝n_k

最后找到j^*，使得 $j^{*}=\underset{1\&le;j\&le;N_{\mathrm{Cand}}}{\arg \max }Q\left[n_k\right]\left[j\right],$ 回溯Path[n_k][j^*]所指的路径，输出路径上的每个字节点，得到字符串即为我们的字符识别结果；在得到最优字符串的同时，我们也得到了最大可能路径的概率的对数值Q[n_k][j^*]，我们将这个值作为对这条切分路径的语义-识别代价估计，将这个值除以n_k，得到平均语义-识别代价 $H_k=\frac{Q\left[n_k\right]\left[j^{*}\right]}{n_k};$

步骤九：综合几何代价与语义代价给出最终结果

第9-1步：我们需要估计几何代价与语义-识别代价的融合参数λ：

融合参数λ的计算流程如图2a

声明如下约定：

N_L——已经给出子字符和正确子字符合并方式的行图像个数(即训练样本个数)；

n_i，k——第i个训练样本第k个候选切分方式对应的字符个数；

n_i，0——第i个训练样本正确切分得到字符个数；

g_i，k——第i个训练样本第k个候选切分路径对应的几何代价，则g_i，1表示第i个训练样本所有切分方式中几何代价的最小值；

G_i，k——第i个训练样本第k个候选切分方式对应的平均几何代价(归一化后的值)；

H_i，k——第i个训练样本第k个候选切分方式对应的平均语义-识别代价；

g_i，0——第i个训练样本完全正确切分对应的几何代价；

G_i，0——第i个训练样本完全正确切分对应的平均几何代价(归一化后的值)；

H_i，0——第i个训练样本完全正确切分对应的平均语义-识别代价；

我们挑选N_L个训练样本行图像(图1a)，对每个行图像按照从步骤三到步骤八的顺序进行处理，从而可以得到n_i，k，g_i，k，H_i，k 1≤i≤N_L，1≤k≤K；我们选用下面的方式对步骤六中评价的几何代价进行归一化，并求其平均值，即我们令 $G_{\mathrm{ik}}=\frac{1}{n_{i,k}}\log \left(\mathrm{\&lambda;}{e}^{-\mathrm{\&lambda;}(g_{i,k}/g_{i,1}-1)}\right),1\&le;i\&le;N_L,1\&le;k\&le;K,$ 类似地我们可以按照前面的步骤得到正确切分对应的几何代价归一化后的分数G_i，0 1≤i≤N_L和平均语义-识别代价(利用8-2步介绍的方法)H_i，0 1≤i≤N_L，记 $T_i^k\left(\mathrm{\&lambda;}\right)=H_{i,k}+G_{i,k},1\&le;k\&le;K,$ 然后记T_i ⁰(λ)为第i个样本完全正确切分对应的T值，即 $T_i^0\left(\mathrm{\&lambda;}\right)=H_{i,0}+G_{i,0};$

极小化 $N\left(\mathrm{\&lambda;}\right)=\underset{i=1}{\overset{N_L}{\mathrm{\&Sigma;}}}\#\{T_i^k\left(\mathrm{\&lambda;}\right)>T_i^0\left(\mathrm{\&lambda;}\right)|1\&le;k\&le;K\}$ 即得到对加权系数λ的估计；

其中 $\#\{T_i^k\left(\mathrm{\&lambda;}\right)>T_i^0\left(\mathrm{\&lambda;}\right)|1\&le;k\&le;K\}$ 表示在给定λ的情况下，第i个样本图像对应的K个候选切分路径中，T值比正确切分方式对应的T值还要大的候选路径的个数，极小化方法依然可以采用类似于极小化θ的尝试法；

第9-2步：根据融合参数λ计算最优的切分识别路径(图2b)

对一般待切分的样本行图像，我们依步骤三——步骤八，计算出K条候选切分路径，并计算出每条路径的平均识别-语义代价H_k 1≤k≤K，平均几何代价(归一化后的) $G_k=\frac{1}{n_k}\log \left(\mathrm{\&lambda;}{e}^{-\mathrm{\&lambda;}(g_k/g_1-1)}\right),1\&le;k\&le;K$ (其中g_k 1≤k≤K对应步骤六中得到的每条切分路径几何代价)，则综合的代价T_k＝H_k+G_k 1≤k≤K，取 $k^{*}=\underset{1\&le;k\&le;K}{\arg \max }{T}_k,$ 则第k^*个候选切分方式作为我们给出的最优切分。

本申请所述方法的实验结果

我们为试验准备如下的数据：

1、为了计算分类器的识别置信度，我们需要在已知类别的字符图像样本上计算参数θ，我们选用了由THOCR提供的50候选的汉字识别核心。样本也是由清华大学电子工程系智能图文处理实验室收集的手写汉字样本。

2、我们收集了大约四千幅信封的手写的信封图像样本，使用清华大学电子工程系智能图文实验室提供的CEARS程序处理了其中的一部分样本，提取信封地址的地址行(包含了地理地址和单位名称两个部分)，去除掉其中误提取地址行，得到了1141个实验样本作为我们的全部行图像，并事先由人工方式给出了每个行图像的正确字符切分方式，其中908挑出来作为训练样本计算参数λ，另外233个作为测试样本。

3、我们实现的是手写邮政地址行的切分，选用的是从中宇邮政信息公司购买的北京市邮政信息名址库，共有18万条名址信息，包括单位名称和物理地址，实际共有约37万个条目，作为我们训练的语料库。

然后按照我们上面所述的步骤二到步骤九进行，我们计算出θ＝2.322(第2-2-1步)，λ＝51.85(第9-1步)，识别核心输出待识别图像的前十个识别候选字(即N_cand＝10，第2-2步、第8-1步)。

我们比较两个指标R_L和R_C。

其中R_L表示行切分正确率，所谓行切分正确，是指这一行图像的每个字符都被正确切分，

R_C表示字切分正确率，是指单独一个字符被正确切分的比率，

试验结果如下(Intel Pentium4 2.8GHz 512MB RAM)

	正确切分的字数	正确切分的行数	正确切分字数的比例(％)	完全正确切分行占的比例(％)
					基于几何代价最小的路径切分	2,492	55	82.7	23.6
本文的切分	2,814	147	93.3	63.1

注：测试样本233个，共包括了3013个汉字。

每行平均处理时间小于300毫秒，这个时间里面包含了字符图像的合并，识别、后处理以及给出最优切分识别结果的全部时间。

对比传统只搜索几何代价最优的切分方式得到的结果(图18(a)(b)(c)给出了对图17(a)(b)(c)仅仅依赖于几何代价最优得到的切分结果，图19(a)(b)(c)给出了我们的方法给出的切分结果)，可见本发明提出的方法实现了高准确率的脱机手写汉字的切分。同时从时间指标上来看，本方法可以对手写文档图像进行实时的高效切分和识别。

当λ＝0即几何代价不纳入考虑的时候，单纯依赖语义信息不能得到最好的结果，这是因为我们的单字识别可以允许一定的噪声，因此某些情况下不一定非要在正确切分下才能得到正确的识别结果，而对于语义-识别代价接近的切分方式来说，就需要进一步比较它们的几何代价了。

结论

综上所述，本发明提出的基于几何代价和语义-识别代价融合的脱机手写汉字切分方法具有以下优点：

1)基于提取图像几何特征和图像的统计特征实现对脱机手写汉字的过切分，能够有效地克服手写汉字的粘连问题。

2)本发明采用的各个字符子字符的几何评估能较好地反映各个字符子字符间的亲密程度，为下一步的合并提供正确的依据。

3)本发明提出的用计算K最短路径给出切分候选的方法。传统方法只取几何代价最优的切分方式，不能保证最佳切分方式一定可以求得，K最短路径方法克服了传统方法的不足，扩大了搜索区域。

4)本发明提出了一个新的观点，认为语义-识别代价才是评价切分有效性的最有力准则，在这个基础上同时考虑切分的几何代价，给出切分方式。这使得我们实现的脱机手写汉字切分和识别的过程更接近于人类的认知过程。同时本发明给出的框架具有一定的指导意义，不论何种形式的几何代价或者语义代价均可以按照本发明提供的思路进行融合。

5)本发明具有很好的推广性，主要表现在：一方面可以由中文切分推广到英文(或者其他语言)的脱机手写字符的切分上(可能需要考虑高阶的语言模型)；另一方面本发明可以方便地应用到其他需要实现高效的脱机手写字符切分的领域，只需要事先对该领域的语料库计算相应的参数，代入我们模型的框架即可。

6)本发明对非本领域的文档有一定的拒绝作用，在针对地址行训练的Bi-gram模型，对于把姓名行错误提取成地址行的情况，可以发现这时的语义代价非常高，这使得我们能够正确地拒绝这样的错误提取行，使整个系统更具智能化。

本方法提出了汉字切分识别和后处理的统一模型，为脱机汉字的切分提出了一种新的思路。

Claims (1)

1、几何代价和语义-识别代价融合的脱机手写汉字切分方法，其特征在于：它是借助图像采集设备和与其相连的计算机实现的，依次含有以下步骤：

步骤一：通过图像采集设备为下述目的采集足够的训练样本，建立相应的库

●脱机手写汉字的单字图像样本库；

●已给出字符正确切分的行图像样本库：我们对已事先已经提取出的行图像样本标定它们的正确切分方式，然后把它们分为两个部分，一部分作为训练样本用于计算参数，另一部分作为测试样本用于测试本申请所述方法的性能；

待切分对象涉及领域的语料库；

步骤二：参数估计

第2-1和2-2步是在给定的“待切分的行图像所涉及领域的语料库”上进行的，用于计算待切分的样本所涉及领域的语义约束关系，我们声明如下符号代表的含义：

N_c——汉字c在语料样本中出现的次数；

N_c1c2——双字词c₁c₂在语料样本中出现的次数；

N——语料样本中的汉字总数；

P(c)——汉字c在语料样本中出现的概率；

P(c₂|c₁)——在语料样本中汉字c₁后面紧接着出现汉字c₂的概率；

P_smooth(·)——平滑处理后的概率；

M——语料样本中包含的不同汉字的个数；

第2-1步：在语料样本上估计P(c)，也就是字符c出现的先验概率；另外还要估计字符间的转移概率，也就是P(c₂|c₁)：

2-1-1步： $P\left(c\right)=\frac{N_c}{N},$ N_c为计算得到的每个汉字在语料库中出现的总次数；

2-1-2步：对于二元语法模型， $P\left(c_2\right|c_1)=\frac{N_{c_1{c}_2}}{N_{c_1}},$ 其中N_c1c2为计算得到的c₁c₂这个词在语料库中出现的次数；

2-1-3步：我们采用了以下简单的处理方法来平滑数据，对于二元语法模型：

$P_{\mathrm{smooth}}\left(c_2\right|c_1)=\left\{\begin{array}{cc}P\left(c_2\right|c_1)& \mathrm{if}{N}_{c_1{c}_2}>0\\ \mathrm{\&epsiv;}& \mathrm{if}{N}_{c_1{c}_2}=0\mathrm{and}{N}_{c_2}=0\\ \frac{1}{M}& \mathrm{if}{N}_{c_1{c}_2}=0\mathrm{and}{N}_{c_2}>0\end{array}\right.$

其中ε＝10^-9；

第2-2步是在“脱机手写汉字的单字图像样本库”中的单字手写汉字图象样本上计算的，其中每个样本图像对应的正确字符是已知的，声明如下约定：

N_sample——脱机手写汉字图像样本库中图像样本的个数；

x_i——第i个样本图像；

d_j(x_i)——由识别核心给出的第i个样本图像x_i.的第j个候选识别字对应的识别距离，识别核心按照识别距离的升序排列识别候选字，因此d₁(x_i)表示第i个样本图像x_i的首选识别候选字对应的识别距离；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，这是一个识别核心的性能参数，因而是常数，而与输入字符图像无关；

L_i——第i个字符图像x_i对应的正确汉字在字符图像的识别候选集中出现的序号，其中识别候选集按照识别距离的升序排列各个识别候选字；

2-2-1步：计算脱机手写汉字识别核心对应的方差参数，用符号θ表示

首先，对在步骤一中谈到的“脱机手写汉字的单字图像样本库”的全部图像样本进行识别，对每个图像，得到N_Cand个识别候选字以及相应的识别距离；

根据识别核心提供的识别距离计算第i个样本图像x_i的首选字对应的识别距离d₁(x_i)与它的第j个识别字的识别距离之差，用y_ij表示，即令y_ij＝d_j(x_i)-d₁(x_i)，其次，极小化下式得到对参数θ的估计：

$E=\frac{1}{2N_{\mathrm{sample}}}\underset{i=1}{\overset{N_{\mathrm{sample}}}{\mathrm{\&Sigma;}}}\{\underset{i=2}{\overset{L_i}{\mathrm{\&Sigma;}}}{[\exp (-\frac{y_{\mathrm{ij}}}{\mathrm{\&theta;}})-1]}^2+\underset{j=I_2+1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{2y_{\mathrm{ij}}}{\mathrm{\&theta;}})\}$

具体的极小化方法采取穷举的办法，在0和100之间取10000个点，0.01，0.02，0.03，…，99.8，99.9，100，作为θ代入上式，取得其中对应E最小值的作为对θ的估计；

为了计算识别核心的混淆矩阵，我们声明如下约定：

ω^input(x)——图像x对应的真实类别；

c_j(x)——由识别核心给出的图像x的第j个候选识别结果，识别核心根据识别距离由小到大的升序排列识别候选字，因此c₁(x)就是图像x首选识别候选字；

{ω^input(x)＝ω}——对应的真实字符为ω的图像的样本集合；

#{ω^input(x)＝ω}——对应的真实字符为ω的图像样本的个数；

2-2-2步：计算混淆矩阵

混淆矩阵是一个M×M的矩阵，其中M表示语料样本中包含了多少种不同的汉字；如果我们把所有汉字按任意选定的顺序排列，char₁，char₂，…，char_M，那么混淆矩阵的第α行第β列的元素就是P(char_β|char_α)，表示实际类别是char_α，但是却被识别核心识为char_β概率；

根据公式 $P\left({\mathrm{char}}_{\mathrm{\&beta;}}\right|{\mathrm{char}}_{\mathrm{\&alpha;}})=\frac{1}{\#\left\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right){=\mathrm{char}}_{\mathrm{\&alpha;}}\right\}}\underset{x\&Element;\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right)={\mathrm{char}}_{\mathrm{\&alpha;}}\}}{\mathrm{\&Sigma;}}\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P(c_j\left(x\right)={\mathrm{char}}_{\mathrm{\&beta;}}|x)$ 计算出与识别核心相关的混淆概率矩阵，其中#{ω^input(x)＝char_α}为对应于真实字符为char_α的图像样本的个数；

其中 $P(c_j\left(x\right)={\mathrm{char}}_{\mathrm{\&beta;}}|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\mathrm{\&theta;}})}{\underset{i=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{d_i\left(x\right)}{\mathrm{\&theta;}})},$ 它是识别核心给出的对图像x的识别结果为char_β的置信度；

$\underset{x\&Element;\{{\mathrm{\&omega;}}^{\mathrm{input}}\left(x\right)={\mathrm{char}}_{\mathrm{\&alpha;}}\}}{\mathrm{\&Sigma;}}\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P(c_j\left(x\right)=\mathrm{cha}{r}_{\mathrm{\&beta;}}|x)$ 表示真实字符为char_α，但是识别候选字中包含了char_β的全部字符图像中关于char_β的识别置信度之和；

除了上述四个方面外，我们还需要估计几何代价与语义-识别代价融合的参数λ，它由行图像的训练样本计算而来，我们放在最后一个部分来介绍如何估计参数λ；

步骤三：字符行图像参数提取

这一步完成对行图像参数的提取，包括笔划宽度、字符平均宽度和字符平均高度，涉及到如下的参数的估计：

w_s——笔划宽度；

——字符平均宽度：

——字符平均高度；

第3-1步：笔划宽度，即书写笔迹的宽度w_s估计

首先，对文本行的水平黑像素游程进行直方图分析，水平黑游程是指横轴方向上黑象素连续占有的矩形区域，矩形的高为一个像素，宽即为水平黑游程的长度，直方图的横轴表示水平黑游程长度，纵坐标表示具有此长度的水平黑游程个数；设直方图中对应游程个数最多的水平黑游程长度为p，对应游程个数为hist(p)，也就是说直方图的纵坐标最大值为hist(p)，它对应的横坐标为p，

则取 $w_s=\frac{(p-1)\&times;\mathrm{hist}(p-1)+p\&times;\mathrm{hist}\left(p\right)+(p+1)\&times;h(p+1)}{h(p-1)+h\left(p\right)+h(p+1)};$

第3-2步：平均字符宽度 的估计

字符平均宽度反映了文本行的书写风格，对字符切分有着直接的影响，首先对文本行图像作竖直方向的投影，得到投影图，此图的横坐标与文本行的横坐标一一对应，纵坐标的值为文本行中相应横坐标竖直方向上全部黑象素点的个数，对投影图水平坐标轴方向也就是纵坐标为0的方向作水平黑游程分析，并且计算全部水平黑游程的平均值，以此作为字符平均宽度的估计；对于文本行中的字符间距过小而造成字符间笔划的相互重叠的情况，在投影图y＝2w_s+1的水平方向上做黑游程统计，计算其平均值，得到较好的字符平均宽度

的估计；

第3-3步：字符平均高度

的估计

字符平均高度的提取相对比较简单，只需将行图像在水平方向上平均分成若干等分，一般取五等分，再对所有小图像的高度取平均即为字符的平均高度

步骤四：笔段提取阶段

笔段是指汉字中横竖撇捺四种基本元素，笔段提取有效地克服了字符的粘连；

笔段提取方法采用黑游程跟踪的方法，其思路是：首先在图像中寻找到一条水平黑游程，作为某一笔段的开始，然后对该水平黑游程从上向下逐行跟踪，直到跟踪结束，得到一笔段；

跟踪采用的思路：在当前水平黑游程的下一行，取包含当前黑游程所在水平位置且左右各偏移一个像素的水平范围，在此范围内找到所有的水平黑游程；然后根据笔段已有游程的平均宽度、以及由笔段已有游程拟和得到的笔段方向，选择某一水平黑游程加入到已有的笔段游程中，并更新原笔段的信息；我们来详细描述一下这个过程，它依次含有以下步骤：

第4-1步：按照由上到下的顺序扫描到一段水平黑象素游程时，如果它不在我们已有的各个笔段的黑游程记录中，那么把它作为某一新笔段的开始，同时把这段水平黑游程添加到新笔段的黑游程记录中；

第4-2步：对于最近添加到笔段记录中的黑游程，我们再在这个水平黑游程下一行包含此水平游程的水平位置，且左右各偏移一个象素开始搜索新的水平黑游程，如果有某个水平游程的黑色象素延伸到这个区域，则将此游程提取出来；如果没有黑游程出现在这个区域，那么此笔段提取结束，回到4-1步继续搜索新的笔段；

第4-3步：对于提取出的黑游程，我们考虑如何把它添加到笔段的黑游程记录中去：这里我们需要分两个情况讨论，一种情况是上一步提取出的水平黑游程仅有一个，那么进行4-3-1步；另一种情况是上一步提取出来的水平黑游程有两个或者两个以上，那么进行4-3-2步；

4-3-1步：

如果我们仅提取出一个水平黑游程，

■如果这一笔段已有水平黑游程的平均宽度大于等于新的水平黑游程宽度的两倍，那么判断已达到笔段结束点，笔段提取结束；

■如果新的水平黑游程宽度大于等于这一笔段已有水平黑游程的平均宽度的三倍，则判断其是一个笔段交叉点，那么根据已有的这一笔段的水平黑游程信息预测笔段方向，然后再在预测的方向上左右各偏移笔段水平黑游程平均宽度的一半，作为新的笔段黑游程加入到记录中；

■如果新的水平黑游程宽度不满足上述两个前提，则判断它为合理的笔段黑游程，直接添加到笔段的水平黑游程记录中来；

4-3-2步：

如果我们提取出两个或以上的水平黑游程，那么我们首先利用已有的笔段水平黑游程信息预测笔段的方向，然后提取在预测方向上的游程作为我们的候选水平黑游程，最后重复4-3-1的三个判断更新黑游程记录表；

步骤4-3-1和4-3-2采用的预测方法如下：对于笔段已经跟踪出来的所有水平黑游程分别求中点，然后按照最小二乘原则用线性函数拟合这些中点，同时根据拟合出的直线预测出笔段的方向；

第4-4步：判决笔段的属性：

对于提取出的笔段，我们首先分别计算它的高度和宽度

■如果这一笔段所有水平黑游程的平均宽度大于给定的阈值，并且笔段宽度大于笔段高度，那么判断它为横笔划；

■我们设定一个小步长，用MinStepLength表示，

◆计算第i行和第i+MinStepLength行这两行的水平黑游程中点，“+”表示加号

●如果中点一致，那么角度累加器加上

●如果第i行中点横坐标大于第i+MinStepLength行中点的横坐标，那么角度累加器加上

●如果第i行中点横坐标小于第i+MinStepLength行中点横坐标，那么角度累加器加上

◆从每个笔段的第一行往下一直扫描到距离笔段高度为零处的MinStepLength行时，将所有角度相加，求平均角度：

●如果平均角度大于零且比预先设定的值α₁要小，那么判断为竖笔划；

●如果平均角度大于上述的α₁且小于预先设定的值α₂那么判断为撇笔划；

●如果平均角度大于上述的α₂且小于预先设定的值α₃那么判断为横笔划；

●如果平均角度大于上述的α₃且小于预先设定的值α₄那么判断为捺笔划；

●如果平均角度大于上述的α₄那么判断为竖笔划；

如果没有新的游程被找到，则该笔段跟踪结束；如果没有新的笔段被找到，则笔段提取结束；在每一笔段被提取出来时，笔段的属性，即横竖撇捺即也被决定；

步骤五：笔段合并

在笔段提取完成之后，还需要将笔段进一步合并为子字符，设R_i和R_j分别为两相邻笔段的外接矩形；

(x_i，1，y_i，1)——R_i的左上角点的坐标；

(x_i，2，y_i，2)——R_i的右下角点的坐标；

(x_j，1，y_j，1)——R_j的左上角点的坐标；

(x_j，2，y_j，2)——R_j的右下角点的坐标；

D_H(R_i，R_j)——R_i右侧和R_j左侧的水平距离，D_H(R_i，R_j)值用正、负表示方向，R_i右边框的水平位置在R_j左边框的水平位置的右边，用负值表示；否则若R_i右边框的水平位置在R_j左边框的水平位置的左边，则用正值表示；

D_V(R_i，R_j)——R_i底侧和R_j顶侧的垂直距离，D_V(R_i，R_j)值用正、负表示方向，R_i底侧框的垂直位置在R_j顶侧框的垂直位置的下面，用负值表示；否则若R_i底侧框的垂直位置在R_j顶侧框的垂直位置的上面，则用正值表示；

width(R_i)——R_i的宽度；

width(R_j)——R_j的宽度；

笔段合并按照下面三个原则进行：

1)如果R_i和R_j满足在水平方向上，R_i包含R_j或者R_j包含R_i，则将笔段i，j合并；

2)如果R_i和R_j满足：D_H(R_i，R_j)＜0，也即R_i右边框在R_j左边框之右，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_1$ 或 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_1,$ 则将笔段i，j合并，此处T₁为预定义门限，一般取0.7；

3)如果R_i和R_j满足：D_H(R_i，R_j)＜0，并且有 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_2$ 且 $\frac{-D_H(R_i,R_j)}{\mathrm{width}\left(R_i\right)}>T_2,$ 则将笔段i，j合并，此处T₂为预定义门限，一般取0.5；

笔段合并算法依次含有如下的步骤：

第5-1步：初始化，笔段按水平方向上的位置从左向右排序；

第5-2步：按照原则(1)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则转向第5-1步；否则转到第5-3步；

第5-3步：按照原则(2)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则转向第5-1步；否则转到第5-4步；

第5-4步：按照原则(3)搜索所有需要合并的笔段，如搜索到满足条件的笔段则将它们合并，合并完则结束；

步骤六：字符合并的几何代价评估，包括六个子步骤

我们把笔段合并的结果，从左向右排序记为：s₁，s₂，...，s_N，这就是我们笔段合并后的子字符图像，要完成切分，需要将这些子字符图像进行适当合并以完成切分操作；

我们介绍一下子字符图像的合并过程；

我们用(s_k，s_k+1，...，s_k+nk-1)，表示由子字符图像s_k，s_k+1，...，s_k+nk-1合并而成的字符图像，我们按照下面的方式评估(s_k，s_k+1，...，s_k+nk-1)合并的几何代价：

w_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的宽度；

h_k——子字符图像s_k，s_k+1，...，s_k+nk-1合并后的字符图像(s_k，s_k+1，...，s_k+nk-1)的高度；

第6-1步：字符宽度w_k打分，用S(w_k)表示字符宽度得分

设(s_k，s_k+1，...，s_k+nk-1)的宽度为w_k，文本行的字符平均宽度为

，由3-2步得出，则 $S\left(w_k\right)=\left\{\begin{array}{cc}a{(\frac{w_k}{\stackrel{\&OverBar;}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\&OverBar;}{w_c}}>1\\ b{(\frac{w_k}{\stackrel{\&OverBar;}{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\stackrel{\&OverBar;}{w_c}}\&le;1\end{array}\right.$ 其中a，b均为预定义参数，一般我们取a＝100，b＝400；

第6-2步：字符宽高比r打分，用S(r)表示字符宽度得分 $S\left(r\right)=\min \{c{(\frac{r}{\stackrel{\&OverBar;}{r}}-1)}^2,100\},$ 其中一般取c＝100；

r为字符(s_k，s_k+1，...，s_k+nk-1)的宽高比， $r=\frac{w_k}{h_k};$

r为字符平均宽高比 $\stackrel{\&OverBar;}{r}=\frac{\stackrel{\&OverBar;}{w_c}}{\stackrel{\&OverBar;}{h_c}};$

为文本行字符平均宽度，估计方法见第3-2步；

为文本行字符平均高度，估计方法见第3-3步；

第6-3步：字符内部子字符间的距离打分

1)外接矩形框的水平距离：即子字符矩形框之间的水平距离，允许矩形框包围的区域有重叠：

2)欧几里德距离：两个像素点间的欧氏距离是说，如果像素点1的坐标为(x₁，y₁)像素点2的坐标为(x₂，y₂)，则这两个像素点间的欧式距离定义为 $\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2};$ 子字符A与子字符B间的欧几里德距离定义为A中全部黑像素点与B中全部黑像素点之间所有的欧式距离值的最小值；

3)平均游程距离：我们计算两个子字符之间全部水平白游程的长度的平均值作为我们的平均游程距离；

根据上述三种距离，我们定义(s_k，s_k+1，...，s_k+nk-1)的内部距离为 $d_{\mathrm{in}}=\frac{\underset{i=k}{\overset{i=k+n_k-1}{\mathrm{\&Sigma;}}}{d}_{i,i+1}}{k},$ 其中子字符s_i与s_j，的距离d_i，j定义为 $d_{i,j}=\underset{n}{\mathrm{\&Sigma;}}{d}_{\mathrm{ij}}^n$ 即是上述三种距离的平均和；

定义内部距离分数为 $S\left(d_{\mathrm{in}}\right)=\left\{\begin{array}{cc}0& \mathrm{if}{d}_{\mathrm{in}}<0\\ 100& \mathrm{if}{d}_{\mathrm{in}}>\frac{w_k}{4}\mathrm{or}{d}_{\mathrm{in}}>\frac{\stackrel{\&OverBar;}{w_c}}{2}\\ \frac{{400d}_{\mathrm{in}}}{w_k}& \mathrm{otherwise}\end{array}\right.$

第6-4步：字符前后的距离打分，用S(D)表示

假设字符(s_k，s_k+1，...，s_k+nk-1)与前后子字符之间的距离分别为D_L和D_R；

D_L——子字符s_k的外接矩形框与子字符s_k-1的外接矩形框之间的水平距离，与步骤五中的定义一致；

D_R——子字符s_k+nk-1的外接矩形框与子字符s_k+nk的外接矩形框之间的水平距离，与步骤五中的定义一致；

如果k＝1则D_L＝∞；如果k+n_k-1＝N，则D_R＝∞；最后取D＝min(D_L，D_R)；

对于字符前后距离的打分为S(D)，

$S\left(D\right)=\left\{\begin{array}{cc}100& \mathrm{ifD}<-\stackrel{\&OverBar;}{w_c}\\ \frac{25\stackrel{\&OverBar;}{w_c}+100\stackrel{\&OverBar;}{D}-75D}{\stackrel{\&OverBar;}{D}+\stackrel{\&OverBar;}{w_c}}& \mathrm{if}-\stackrel{\&OverBar;}{w_c}\&le;D\&le;\stackrel{\&OverBar;}{D}\\ \frac{25(D_{\max }-D)}{D_{\max }-\stackrel{\&OverBar;}{D}}& \mathrm{if}\stackrel{\&OverBar;}{D}\&le;D{\&le;D}_{\max }\\ 0& \mathrm{ifD}>D_{\max }\end{array}\right.$

其中

为文本行中字符的平均宽度， D和D_max分别为文本行中子字符外接矩形框之间的水平距离的平均值和子字符外接矩形框之间的水平距离的最大值；

第6-5步：连通度打分，用S(C)表示

定义子字符s_i和子字符s_j的连通度C_ij为

字符(s_k，s_k+1，...，s_k+nk-1)的连通性由三个量来表示：

C_I——内部连通性；

C_L——左部连通性；

C_R——右部连通性；

其中内部连通性指的是字符内部子字符的连通程度；左部连通性和右部连通性指的是子字符s_k和子字符s_k-1，子字符s_k+nk-1与子字符s_k+nk之间的连通性；

$C_l=\left\{\begin{array}{cc}\frac{1}{n_k-1}\underset{i=k}{\overset{i=k+n_k-2}{\mathrm{\&Sigma;}}}{C}_{i,i+1}& n_k>1\\ 1& n_k=1\end{array}\right.$

$C_L=\left\{\begin{array}{cc}{C}_{k,k-1}& k>1\\ 1& k=1\end{array}\right.$

$C_R=\left\{\begin{array}{cc}{C}_{k+n_k-1,k+n_k}& k+n_k-1<N\\ 1& k+n_k-1=N\end{array}\right.$

连通度得分 $S\left(C\right)=100\&times;[1-\frac{1}{2}(1+C_l-\frac{C_R+C_L}{2})];$

第6-6步：计算总体分值作为几何代价

整体的分数是以上五种分数的加权平均和 $S=\frac{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i{S}_i}{\underset{i}{\mathrm{\&Sigma;}}{\mathrm{\&alpha;}}_i},$ 其中α₁＝5，α₂＝2，α₃＝3，α₄＝5，α₅＝2；

步骤七：根据已经评价出来的几何代价计算前K条几何代价最优的切分方式

当进行完步骤六之后，我们把行图像切分成了一列子字符图像，同时给出了子字符块之间合并的几何代价，但是我们需要进一步把子字符图像合并为字符图像，从而完成字符的切分，下面我们利用步骤六得到的子字符块合并的代价，生成一些可能的子字符合并方案，每个方案都对应行图像的一种切分结果，我们在步骤八中评价这些方案，并给出最优方案；

第7-1步：切分图建立

对于已经切分好的N个子字符图像s₁，s₂，...，s_N，建立一个有向图(V，E)，其中节点数为N+1，标记为Node₁，Node₂，Node₃，…，Node_N+1，也即V＝{Node₁，Node₂，Node₃，...，Node_N+1}；对于任意的Node_i，存在从Node_i到Node_i+1，Node_i+2，Node_i+3，...的有向路径，其中路径Node_i→Node_i+j对应了从第i，i+1，...，i+j-1块子字符合并，也即合并子字符图像s_i，s_i+1，...，s_i+j-1，路径的代价就是此合并对应的几何代价；切分图每条由起点Node₁到终点Node_N+1的路径都对应了子字符图像s₁，s₂，...，s_N的一种合并方法，也就是对行图像的一种切分方式，因此我们称它为切分路径；

第7-2步：产生前K条几何代价最优的切分路径：

我们下面介绍如何计算切分图(V，E)中从起点Node₁到终点Node_N+1按代价的升序排列的前K条路径，这里每条路径都对应了行图像的一种切分方式，实际上就是子字符图像s₁，s₂，...，s_N一种合并方案，按照此方案合并子字符s₁，s₂，...，s_N，从而完成对行图像的切分；

算法的具体过程如下：

给定图(V，E)，设

N_Node——图的节点数，N_Node＝N+1，N代表已经切分好的子字符图像的个数；

N_Edge——边的条数；

Start——起始节点，即为Node₁；

Edge——终止节点，即为Node_N+1；

K——需要计算的最优路径条数；

π^k(v)——从起点Start到节点v的路径总代价排第k的路径，其中v的取值集合为节点集Node₁，Node₂，Node₃，...，Node_N+1，所达路径代价按升序排列，因此π¹(v)就是从起点Start到端点v的最短路径，如果取v＝Node_N+1，那么π¹(Node_N+1)表示了从起点到终点的最短路径；

Г^-1(v)——v的前趋节点的集合，即所有可能连接到v的节点的集合，对于任何u∈Г^-1(v)，均存在路径u→v；

□——两条路径的连接，其中a路径的终点是b路径的起始点，连接后的路径a□b以a路径的起点作为起点，b路径终点作为终点；

C[v]——节点v的候选路径集合；

然后按照下述步骤进行：

7-2-1步：首先对于所有v∈V，计算π¹(v)，即分别计算从起点Start到各个节点的最短路径；

7-2-2步：对于每个v∈V，如果π¹(v)，π²(v)，...，π^k-1(v)已经完成，下面介绍如何利用π¹(v)，π²(v)，...，π^k-1(v)计算π^k(v)，其中2≤k≤K；

如果k＝2，那么初始化候选路径集合C[v]，对v的前趋节点的集合Г^-1(v)中的每一个元素u，找到从起点Start到节点u的最短路径，构造新的路径π¹(u)□v，添加到v的候选路径集合里，即C[v]←{π¹(u)□v|u∈Г^-1(v)}；

如果k＞2，对路径π^k-1(v)，找到路径π^k-1(v)中v的前趋节点u₀，即路径π^k-1(v)通过节点u₀连到v，一定存在整数l，满足1≤l≤k-1，使得π^k-1(v)从起点Start到u₀时走过的路径与π^l(u₀)一致，也就是说π^k-1(v)恰好等于由路径π^l(u₀)的终点u₀连接到节点v，即π^k-1(v)＝π^l(u₀)□v，对这样的整数l，我们再计算π^l+1(u₀)；

然后我们从候选路径集合C[v]里面去掉路径π^l(u₀)□v，而把π^l+1(u₀)□v添加到候选路径集合C[v]里面，即令C[v]←{C[v]-{π^l(u₀)□v}}∪{π^l+1(u₀)□v}；则求C[v]中的最短路径，C[v]中的最短路径就是π^k(v)；

递归地用以上算法，就得到了前K条切分路径；

第7-3步：字符识别

CharCandidatesSet——图像识别候选集，其中的每个元素都包含了N_Cand个识别候选字和N_Cand个对应的识别置信度；

CharCandidatesSetNum——图像识别候选集中元素的个数；

设子字符为s₁s₂...s_N，我们建立一个(N+1)×(N+1)的查询表，即LookupTable，LookupTable中的元素首先全部设为-1，清空图像识别候选集，即CharCandidatesSet，并令CharCandidatesSetNum＝0；

For 1≤k≤K

对第k个候选切分路径，即几何代价按升序排列排在第k的候选切分路径，

对s_ps_p+1...s_q(1≤p≤q≤N)这样的合并方式，查询LookupTable中的元素LookupTable(p，q+1)，它表示查询表LookupTable中第p行第q+1列的元素；

如果LookupTable(p，q+1)＝-1，那么说明这种合并还没有被识别过，对这种组合得到的图像进行识别，得到N_Cand个候选字，并且估计每个识别候选字的置信度，见第8-1步，然后把识别候选字及其对应的识别置信度整体作为一个元素添加到图像识别候选集CharCandidatesSet，然后令LookupTable(p，q+1)＝CharCandidatesSetNum，同时让CharCandidatesSetNum增加1，也即CharCandidatesSetNum＝CharCandidatesSetNum+1；

如果LookupTable(p，q+1)≠-1，那么说明这种合并已被考虑过，不用再处理

End For

这一过程带来的好处是避免了识别核心的重复工作，大大节约了时间，在后面的步骤中如果我们需要知道子字符块s_ps_p+1...s_q合并后的识别结果时，只要查询LookupTable的第p行第q+1列元素，就得到子字符块s_ps_p+1...s_q合并后的识别结果在CharCandidatesSet中的序号，从而找到在CharCandidatesSet对应位置中已经记录的子字符块s_ps_p+1...s_q合并后的识别结果及相应的置信度；

步骤八：依赖于前面给出的K条几何意义下最优的候选切分方案，根据二元语法模型给出每个子字符合并方案对应的语义-识别代价：

第8-1步：字符置信度估计

x——待识别的字符图像；

c_j(x)——由识别核心给出的对图像x的第j个候选识别字，识别核心根据识别距离由小到大的升序排列识别候选字，因此c₁(x)就是图像x的首选识别候选字；

d_j(x)—由识别核心给出的图像x的第j个候选识别字c_j(x)对应的识别距离，因此d_j(x)表示图像x的首选识别候选字对应的识别距离；

N_Cand——识别核心对单字字符图像给出的识别候选字的个数，如前2-2步所述，该值为常数，只与识别核心本身有关；

P(c_j(x)|x)——图像x识别为c_j(x)的置信度，这是我们需要估计的对象；

对于7-3步得到的所有候选字，用基于Gauss模型的置信度估计方法估计候选字的置信度：

$P\left(c_j\left(x\right)\right|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\mathrm{\&theta;}})}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}\exp (-\frac{d_k\left(x\right)}{\mathrm{\&theta;}})},$ θ就是我们前面2-3步计算出来的；

利用前面计算的混淆矩阵修正估计的置信度，其中混淆矩阵由2-4计算得到，修正置信度由 $P\left(c_j\left(x\right)\right|x)=\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\mathrm{\&Sigma;}}}P\left(c_k\left(x\right)\right|x)P\left(c_j\left(x\right)\right|c_k\left(x\right))$ 得到；

第8-2步：基于二元语法的语义-识别置信代价计算

对于已经给出的K条行图像切分路径，对每条切分路径应用以下的方法计算其对应的平均语义-识别置信代价，声明如下符号及其意义：

n_k——按照第k条切分路径合并子字符图像，共得到n_k个合并后的字符图像；

image_k，t——按照第k条切分路径合并子字符图像后的第t个字符图像，其中1≤k≤K，1≤t≤n_k；

c_j(image_k，t)——识别核心给出的字符图像image_k，t的第j个识别候选字，其中1≤j≤N_Cand，1≤k≤K，1≤t≤n_k，P(c_j(image_k，t)|image_k，t)对应它的识别置信度；

由于字符图像的识别和置信度的估计已经在7-3步中完成，在此步骤中我们通过查询LookupTable的方法从CharcandidatesSet中得到我们需要的识别结果和置信度；

对第k条候选切分路径，1≤k≤K，使用下述的Vieterbi方法计算语义-识别代价：

令Q[n_k][N_Cand]是一个二维数组，其中Q[t][j]保存了从第一个字符图像某个候选字到字节点c_j(image_k，t)的最大可能候选字选择方式所具有的概率的对数值，另外取一个二维指针数组Path[n_k][N_Cand]用于记录计算过程；

初始化t＝1，1≤j≤N_Cand

Path[1][j]＝NULL，

Q[1][j]＝logP(c_j(image_k，1))+log(c_j(image_k，1)|image_k，1)，

递归2≤t≤n_k，对1≤j≤N_Cand计算Q[t][j]，

$Q\left[t\right]\left[j\right]=\underset{1\&le;l\&le;N_{\mathrm{Cand}}}{\max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_j\left(\mathrm{imag}{e}_{k,t}\right)\right|c_l\left({\mathrm{image}}_{k,t-1}\right))\}+\log P\left(c_j\left({\mathrm{image}}_{k,t}\right)\right|\mathrm{image})$

另外找到使得Q[t-1][l]+logP(c_j(image_k，t)|c_l(image_k，t-1))最大的l，记作l^*，即

$l^{*}=\underset{1\&le;l\&le;N_{\mathrm{Cand}}}{\arg \max }\left\{Q\right[t-1\left]\right[l]+\log P\left(c_j\left(\mathrm{imag}{e}_{k,t}\right)\right|c_l\left({\mathrm{image}}_{k,t-1}\right))\},$

然后令Path[t][j]指向字节点c_l*(image_k，t-1)，即字节点c_j(image_k，t)的父节点为c_i*(image_k，i-1)

终止t＝n_k′

最后找到j^*，使得 $j^{*}=\underset{1\&le;j\&le;N_{\mathrm{Cand}}}{\arg \max }Q\left[n_k\right]\left[j\right],$ 回溯Path[n_k][j^*]所指的路径，输出路径上的每个字节点，得到字符串即为我们的字符识别结果；在得到最优字符串的同时，我们也得到了最大可能路径的概率的对数值Q[n_k][j^*]，我们将这个值作为对这条切分路径的语义-识别代价估计，将这个值除以n_k，得到平均语义-识别代价 $H_k=\frac{Q\left[n_k\right]\left[j^{*}\right]}{n_k};$

步骤九：综合几何代价与语义代价给出最终结果

第9-1步：我们需要估计几何代价与语义-识别代价的融合参数λ

声明如下约定：

N_L——已经给出子字符和正确子字符合并方式的行图像个数，即训练样本个数；

n_i，k——第i个训练样本第k个候选切分方式对应的字符个数；

n_i，0——第i个训练样本正确切分得到字符个数；

g_i，k——第i个训练样本第k个候选切分路径对应的几何代价，则g_i，1表示第i个训练样本所有切分方式中几何代价的最小值；

G_i，k——第i个训练样本第k个候选切分方式对应的平均几何代价取归一化后的值；

H_i，k——第i个训练样本第k个候选切分方式对应的平均语义-识别代价；

g_i，0——第i个训练样本完全正确切分对应的几何代价；

G_i，0——第i个训练样本完全正确切分对应的平均几何代价取归一化后的值；

H_i，0——第i个训练样本完全正确切分对应的平均语义-识别代价；

我们挑选N_L个训练样本行图像，对每个行图像按照从步骤三到步骤八的顺序进行处理，从而得到n_i，k，g_i，k，H_i，k1≤i≤N_L，1≤k≤K；我们选用下面的方式对步骤六中评价的几何代价进行归一化，并求其平均值，即我们令 $G_{\mathrm{ik}}=\frac{1}{n_{i,k}}\log \left({\mathrm{\&lambda;e}}^{-\mathrm{\&lambda;}(g_{i,k}/g_{i,l}-1)}\right)$ 1≤i≤N_L，1≤k≤K；类似地我们按照前面的步骤得到正确切分对应的几何代价归一化后的分数G_i，01≤i≤N_L和平均语义-识别代价H_i，01≤i≤N_L；记 $T_i^k\left(\mathrm{\&lambda;}\right)=H_{i,k}+G_{i,k}$ 1≤k≤K，然后记T_i ⁰(λ)为第i个样本完全正确切分对应的T值，即 $T_i^0\left(\mathrm{\&lambda;}\right)=H_{i,0}+G_{i,0};$ 极小化 $N\left(\mathrm{\&lambda;}\right)=\underset{i=1}{\overset{N_L}{\mathrm{\&Sigma;}}}\#\{T_i^k\left(\mathrm{\&lambda;}\right)>T_i^0\left(\mathrm{\&lambda;}\right)|1\&le;k\&le;K\}$ 即得到对加权系数λ的估计；

其中 $\#\{T_i^k\left(\mathrm{\&lambda;}\right)>T_i^0\left(\mathrm{\&lambda;}\right)|1\&le;k\&le;K\}$ 表示在给定λ的情况下，第i个样本图像对应的K个候选切分路径中，T值比正确切分方式对应的T值还要大的候选路径的个数，极小化方法依然采用类似于极小化θ的尝试法；

第9-2步：根据融合参数λ计算最优的切分识别路径

对一般待切分的样本行图像，我们依步骤三——步骤八，计算出K条候选切分路径，并计算出每条路径的平均识别-语义代价H_k 1≤k≤K和归一化后的平均几何代价 $G_k=\frac{1}{n_k}\log \left({\mathrm{\&lambda;e}}^{-\mathrm{\&lambda;}(g_k/g_1-1)}\right)$ 1≤k≤K，其中g_k 1≤k≤K对应步骤六中得到的每条切分路径的几何代价，则综合的代价T_k＝H_k+G_k 1≤k≤K，取 $k^{*}=\underset{1\&le;k\&le;K}{\arg \max }{T}_k,$ 则第k^*个候选切分方式作为我们给出的最优切分。

Images