几何代价和语义－识别代价融合的脱机手写汉字切分方法

摘要

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

主权项

1、几何代价和语义-识别代价融合的脱机手写汉字切分方法，其特征在于：它是借助图像采集设备和与其相连的计算机实现的，依次含有以下步骤：步骤一：通过图像采集设备为下述目的采集足够的训练样本，建立相应的库●脱机手写汉字的单字图像样本库；●已给出字符正确切分的行图像样本库：我们对已事先已经提取出的行图像样本标定它们的正确切分方式，然后把它们分为两个部分，一部分作为训练样本用于计算参数，另一部分作为测试样本用于测试本申请所述方法的性能；待切分对象涉及领域的语料库；步骤二：参数估计第2-1和2-2步是在给定的“待切分的行图像所涉及领域的语料库”上进行的，用于计算待切分的样本所涉及领域的语义约束关系，我们声明如下符号代表的含义：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_1\right|c_2)=\left\{\begin{array}{cc}P\left(c_2\right|c_1)& \mathrm{if}{N}_{c_1{c}_2}>0\\ ϵ& \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}}}{\Sigma }}\{\underset{i=1}{\overset{L_i}{\Sigma }}{[\exp (-\frac{y_{\mathrm{ij}}}{\theta })-1]}^2-\underset{j=L_i+1}{\overset{N_{\mathrm{Cand}}}{\Sigma }}\exp (-\frac{2y_{\mathrm{ij}}}{\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_α，但是却被识别核心识为cha_rβ概率；根据公式 $P\left(\mathrm{cha}{r}_{\beta }\right|{\mathrm{char}}_{\alpha })=\frac{1}{\#\{{\omega }^{\mathrm{input}}\left(x\right)=\mathrm{cha}{r}_{\alpha }\}}\underset{x\in \{{\omega }^{\mathrm{input}}\left(x\right)=\mathrm{cha}{r}_{\alpha }\}}{\Sigma }\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\Sigma }}P(c_j\left(x\right)=\mathrm{cha}{r}_{\beta }|x)$计算出与识别核心相关的混淆概率矩阵，其中#{ω^input(x)＝char_α}为对应于真实字符为char_α的图像样本的个数；其中 $P(c_j\left(x\right)=\mathrm{cha}{r}_{\beta }|x)=\frac{\exp (-\frac{d_j\left(x\right)}{\theta })}{\underset{i=1}{\overset{N_{\mathrm{Cand}}}{\Sigma }}\exp (-\frac{d_i\left(x\right)}{\theta })},$它是识别核心给出的对图像x的识别结果为char_β的置信度； $\underset{x\in \{{\omega }^{\mathrm{input}}\left(x\right)=\mathrm{cha}{r}_{\alpha }}{\Sigma }\underset{j=1}{\overset{N_{\mathrm{Cand}}}{\Sigma }}P(c_j\left(x\right)=\mathrm{cha}{r}_{\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_i)——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_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步；第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}{\overline{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\overline{w_c}}>1\\ b{(\frac{w_k}{\overline{w_c}}-1)}^2& \mathrm{if}\frac{w_k}{\overline{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}{\bar{r}}-1)}^2,100\},$其中一般取c＝100；r为字符(s_k，s_k+1，...，s_k+nk-1)的宽高比， $r=\frac{w_k}{h_k};$r为字符平均宽高比 $\bar{r}=\frac{\overline{w_c}}{\overline{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}{\Sigma }}{d}_{i,i+1}}{k},$其中子字符s_i与s_j的距离d_i，j定义为 $d_{i,j}=\underset{n}{\Sigma }{\gamma }_n{d}_{\mathrm{ij}}^n$即是上述三种距离的加权平均和，γ_n是加权系数，一般来说我们取γ_n都为1；定义内部距离分数为 $S\left(d_{\mathrm{in}}\right)=\left\{\begin{array}{c}0\mathrm{if}{d}_{\mathrm{in}}<0\\ 100\mathrm{if}{d}_{\mathrm{in}}>\frac{w_k}{4}\mathrm{or}{d}_{\mathrm{in}}>\frac{\overline{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}{c}100\mathrm{ifD}<-\overline{w_c}\\ \frac{25\overline{w_c}+100\bar{D}-75D}{\bar{D}+\overline{w_c}}\mathrm{if}-\overline{w_c}\le D\le \bar{D}\\ \frac{25(D_{\max }-D)}{D_{\max }-\bar{D}}\mathrm{if}\bar{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_I=\left\{\begin{array}{cc}\frac{1}{n_k-1}\underset{i=k}{\overset{i=k+n_k-2}{\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}{\Sigma }{\alpha }_i{S}_i}{\underset{i}{\Sigma {\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₁(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)}{\theta })}{\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\Sigma }}\exp (-\frac{d_k\left(x\right)}{\theta })},$θ就是我们前面2-3步计算出来的；利用前面计算的混淆矩阵修正估计的置信度，其中混淆矩阵由2-4计算得到，修正置信度由 $P\left(c_j\left(x\right)\right|x)=\underset{k=1}{\overset{N_{\mathrm{Cand}}}{\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_CandPath[1][j]＝NULL，Q[1][j]＝log P(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{imag}{e}_{k,t-1}\right))\}+\log P\left(c_j\left(\mathrm{imag}{e}_{k,t}\right)\right|\mathrm{imag}{e}_k$另外找到使得Q[t-1][l]+log P(c_j(image_k，t)|cl(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{imag}{e}_{k,t-1}\right))\},$然后令Path[t][j]指向字节点c_1*(image_k，t-1)，即字节点c_j(image_k，t)的父节点为c_l*(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步：我们需要估计几何代价与语义-识别代价的融合参数λ声明如下约定：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，k 1≤i≤N_L，1≤k≤K；我们选用下面的方式对步骤六中评价的几何代价进行归一化，并求其平均值，即我们令 $G_{\mathrm{ik}}=\frac{1}{n_{i,k}}\log \left(\lambda e^{-\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和平均语义-识别代价H_i，0 1≤i≤N_L；记 $T_i^k\left(\lambda \right)=H_{i,k}+G_{i,k},1\le k\le K,$然后记T_i^0*(λ)为第i个样本完全正确切分对应的T值，即 $T_i^0\left(\lambda \right)=H_{i,0}+G_{i,0};$极小化 $N\left(\lambda \right)=\underset{i=1}{\overset{N_L}{\Sigma }}\#\{T_i^k\left(\lambda \right)>T_i^0\left(\lambda \right)|1\le k\le K\}$即得到对加权系数λ的估计；其中#{T_i^k(λ)＞T_i⁰(λ)|1≤k≤K}表示在给定λ的情况下，第i个样本图像对应的K个候选切分路径中，T值比正确切分方式对应的T值还要大的候选路径的个数，极小化方法依然采用类似于极小化θ的尝试法：第9-2步：根据融合参数λ计算最优的切分识别路径对一般待切分的样本行图像，我们依步骤三——步骤八，计算出K条候选切分路径，并计算出每条路径的平均识别-语义代价H_k 1≤k≤K和归一化后的平均几何代价 $G_k=\frac{1}{n}\log \left(\lambda e^{-\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^*个候选切分方式作为我们给出的最优切分。