隐马尔可夫模型在脱机手写数字识别中的应用

The Application of Hidden Markov Models in Offline Handwriting Digital Recognition

摘要: 本文主要用隐Markov模型(HMM)来研究脱机手写数字识别。本文的内容分为三个部分，第一个部分是介绍HMM的基本理论；第二部分是介绍数字图片的预处理和特征提取，这部分属于图像处理方向，并且在手写体数字识别中很重要，特别是提取一个稳定而有效的特征决定着识别是否成功；第三部分是具体地实现这一识别过程，并且用Matlab实现了一个脱机手写数字识别系统。

Abstract: In this paper, we use hidden Markov models (HMM) to study the off-line handwritten numeral recognition. This paper can generally be divided into three parts: the first part introduces the basic theory of HMM; the second part introduces the digital image preprocessing and feature extraction, and this part belongs to image processing, and it is very important in the handwriting recognition, and especially extracting a stable and effective feature determines the successful recognition; the third part implements recognition process, and we use Matlab to obtain an off-line handwriting recognition system.

1. 引言

隐Markov模型(Hidden Markov Models，简称为HMM)是一种统计模型，今天正在手写体识别和语音识别等各个领域中获得广泛的应用。而有关它的理论基础，却是在1970年前后由Baum等人建立起来的，随后由CMU(卡内基·梅隆大学)的Jim and Janet Baker (贝克夫妇，李开复的师兄师姐)和IBM的Fred Jelinek分别独立地提出用HMM来识别语音，语音识别的错误率相比人工智能和模式匹配等方法降低了三倍(从30%到10%)。八十年代李开复博士坚持采用HMM的框架，成功地开发了世界上第一个大词汇量连续语音识别系统Sphinx。由于Bell实验室Rabiner等人在80年代中期对HMM的深入浅出的介绍，才逐渐使HMM为世界各国从事语音处理的研究人员所了解和熟悉，进而成为公认的一个研究热点。

HMM在语音识别中的成功应用 [1] ，使得人们将HMM引入到手写识别中来 [2] [3] [4] [5] 。目前，利用HMM进行脱机手写字符识别是脱机手写字符研究的一个热点的方向。此外，HMM在人脸识别和图像分割等模式识别领域有成功的应用。

2. 隐Markov模型的基本理论

2.1. Markov链

马尔可夫链，因安德烈·马尔可得名，是指数学中具有马尔可夫性质的离散事件随机过程。该过程中，在给定当前知识或信息的情况下，过去(即当前以前的历史状态)对于预测将来(即当前以后的未来状态)是无关的。

这一类随机过程，它具有所谓的“无后效性(Markov性)”，即要确定过程的将来的状态，知道它此刻的情况就足够了，并不需要对它以往状况的认识，这类过程称为Markov过程。而Markov链是Markov过程的特殊情况，即Markov链是状态和时间参数都离散的Markov过程。从数学上，可以给出如下定义：

随机过程 $\left\{X_n,n=1,2,\cdots \right\}$ ，在任一时刻n，它可以处在状态 $S_1,S_2,\cdots ,S_N$ ，且它在 $n+1$ 时刻所处的状态为 $q_{n+1}$ 的概率，只与它在n时刻的状态 $q_n$ 有关，而与n时刻以前它所处状态无关，即有：

$\begin{array}{l}P\left(X_{n+1}=q_{n+1}|X_n=q_n,X_{n-1}=q_{n-1},\cdots ,X_1=q_1\right)\\ =P\left(X_{n+1}=q_{n+1}|X_n=q_n\right)\end{array}$

其中， $q_1,q_2,\cdots ,q_n,q_{n+1}\in \left(S_1,S_2,\cdots ,S_N\right)$ 。

则称 $\left\{X_n,n=1,2,\cdots \right\}$ 为Markov链，并且称条件概率 $P\left(X_{n+1}=q_{n+1}|X_n=q_n\right)$ 为一步转移概率，当这个转移概率只与状态 $q_n,q_{n+1}$ 的具体取值有关，而与时刻n无关，称这个Markov链为齐次Markov链，在本文中，讨论的Markov链都是齐次的。

当 $q_n,q_{n+1}$ 分别取值 $S_i,S_j$ 时，记 $a_{ij}=P\left(X_{n+1}=S_j|X_n=S_i\right)$ ，则 $a_{ij},1\le i,j\le N$ 可以构成一个转移概率矩阵，即

$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1N}\\ a_{21}& a_{22}& \cdots & a_{2N}\\ ⋮& ⋮& \ddots & ⋮\\ a_{N1}& a_{N2}& \cdots & a_{NN}\end{array}\right)$

对于上面的矩阵显然有 $0\le a_{ij}\le 1$ ， ${\displaystyle \underset{j=1}{\overset{N}{\sum }}{a}_{ij}}=1$ 。

描述Markov链的最重要参数就是转移概率矩阵A，但A还决定不了初始分步，即由A求不出 $q_1=S_i$ 概率，这样，完全描述Markov链，除了A矩阵之外，还必须引进初始概率向量 $\pi =\left({\pi }_1,{\pi }_2,\cdots ,{\pi }_N\right)$ ，其中

显然有 $0\le {\pi }_i\le 1$ ， ${\displaystyle \underset{i=1}{\overset{N}{\sum }}{\pi }_i}=1$ 。

2.2. 隐Markov模型的定义

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列(state sequence);每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列(observation sequence)。序列的每一个位置又可以看作是一个时刻。

隐Markov模型是在Markov链的基础上发展起来的。由于实际问题比Markov链模型所描述的更为复杂，观察到的事件并不是与状态一一对应，而是通过一组概率分布相联系，这样的模型就称为隐Markov模型，它是一个双重随机过程，其中之一是齐次Markov链，这是基本随机过程，它描述状态的转移。另一个随机过程描述状态和观测值之间的统计对应关系。这样，站在观察者的角度，只能看到观察值，不像Markov链模型的观察值和状态一一对应，因此，不能直接看到状态，而是通过一个随机过程感知状态的存在及其特性。因而称之为“隐Markov模型”，即HMM。

2.3. 维特比算法与隐Markov模型

维特比算法(Viterbi)针对HMM中的解码或者预测问题，寻找最可能的隐藏状态序列：对于一个特殊的隐马尔可夫模型及一个相应的观察序列，找到生成此序列最可能的隐藏状态序列。

在利用Viterbi算法进行识别的过程中，其每步所得到的概率的具体值是没有意义的，而且计算出的概率值总是很小很小的，另外我们所需要的只是各模型对该观察序列的概率值之间的相对大小，因此，在计算过程中，将每步得到的概率值取对数，简化计算，即：

定义

${\delta }_t\left(i\right)=\underset{i_1,i_2,\cdots ,i_{t-1}}{\max }\log P\left(q_1=S_{i_1},q_2=S_{i_2},\cdots ,q_{t-1}=S_{i_{t-1}},q_t=S_i,O_1{O}_2\cdots O_t|\lambda \right)$

那么，初始化式变为

${\delta }_t\left(i\right)=\log {\pi }_i+\log b_i\left(O_1\right),1\le i\le N$

递归运算式变为

${\delta }_t\left(j\right)=\underset{1\le i\le N}{\max }\left[{\delta }_{t-1}\left(i\right)+\log a_{ij}\right]+\log \left[b_j\left(O_t\right)\right]$

终止式变为

$\log P^{*}=\underset{1\le i\le N}{\max }\left[{\delta }_T\left(i\right)\right]$

3. 数字图片的预处理与特征提取

3.1. 数字图片的预处理

所有的模式识别包含三个步骤：预处理、特征提取、分类识别。其中第一步预处理的好坏将直接影响到后续步骤。一般情况下，预处理有如下过程：二值化、平滑去噪、字符切割、归一化、倾斜校正、细化。

1) 二值化：对于字符识别，图片的彩色信息作用不大，相反还会增加算法复杂度，因此必须首先把图片转化成灰度图。本文采用的是Otsu提出的最大类间方差方法进行二值化，该方法的优点就是计算简单，稳定有效。

2) 平滑去噪：噪声去除已经成为图像处理及其重要的步骤，然而现在还没有一个通用的滤波去噪方法对所有的图片适用，一般的图像预处理必须根据实际情况选择不同的滤波去噪方法进行比较，最后得出最佳的滤波去噪方法 [6] 。

3) 字符切割：通常获取的图片除字符外，有较大的空白区，这对我们的研究没有任何价值，而且造成存储和时间资源浪费。为此，需要通过字符提取，去除空白区，提取有用的字符区。

4) 归一化：归一化的目的是将字符图片转化成一个标准尺寸，以便获取固定维度的特征向量，同时减少间类字符的变化对识别的影响，改善分类精度。

5) 倾斜校正：倾斜校正首先要确定倾斜角，然后再进行旋转。确定倾斜角有Hough变换法、Radon变换法，矩方法等。本文采用的是Radon变换法。Radon变换法是基于投影的矫正方法，利用图像水平方向和垂直方向的投影特征来进行倾斜判断。主要用到投影的方差和均方差、投影特征矢量、梯度方向场等统计特性。

6) 细化：不同的书写工具会造成笔画宽度不一样，所以这必将影响有些的特征提取。字符细化是通过一定的处理算法将字符重要的像素点保留下来，去除无关紧要的点，得到字符笔化骨架的技术 [7] 。

3.2. 特征提取

对数字识别特征提取有多种方法，本论文采用的方法是先提取数字的轮廓特征，然后对图像进行裁剪之后按黑像素占总像素的比率提取出特征值。把每个数字图形定义成一个N * N (5 * 5)的模板，将每个样品的长度和宽度N等分，平均有N * N个等分，对每一等分进行像素个数统计，除以每一份的面积总数即得特征值。具体步骤如下：

1) 调入样本图片，找出图片中数字的上、下、左、右边界。对图像进行裁剪处理。

2) 将数字区域平均分成5 * 5的小区域。

3) 计算5 * 5的每个小区域中黑像素所占比例，第一行的5个比例值保存到特征的前5个，第二行对应着特征的6~10，如此保存样本的特征值。本论文提取每个数字25个样本的特征值之后，把它们保存在结构体Mytemplet里，构成了特征库。

下面以0为例看一下求取特征值的方法，首先把图像按边缘裁剪放缩后，然后分成5 × 5的小区域(见图1)，然后计算出每个小区域中黑像素所占的比例，存储之后即为0的一个样本特征值(见表1)。

4. 识别过程

4.1. HMM的脱机手写数字识别的一般过程

本文主要是应用HMM来对0~9这10个阿拉伯数字识别，首先我们要利用一组已知的手写样本来分别训练数字0~9的HMM，即 ${\lambda }_0,{\lambda }_1,\cdots ,{\lambda }_9$ 。然后对于一个待识别的数字样本，先要对其预处理，然后提取一组特征 $O_1{O}_2\cdots O_T$ ，把它作为HMM的观察值序列，再用Viterbi算法分别计算它与求出来的10个HMM的匹配率，匹配率最高对应的数字即为该样本识别结果。

4.2. 脱机手写数字识别系统设计

我们将HMM的相关算法如Viterbi算法等用Matlab语言写出来，参考了Kevin Murphy在网站 [8] 上的HMM工具箱。在Matlab R2016a中设计这一脱机手写数字识别系统，最后用Matlab设计出了图形用户界面GUI(见图2)。

Figure 1. Number 0

图1. 数字0

Table 1. Eigenvalues of the number 0

表1. 数字0的特征值

Figure 2. GUI

图2. 图形用户界面

Table 2. System resulting data of standard experiment

表2. 标准试验系统结果数据

系统具体功能：每导入一张外部图片，点击开始识别按钮即可识别图片中的手写数字，系统会输出识别结果。

4.3. 识别系统试验结果

多次试验结果表明，该识别系统识别率较高(见表2)。

5. 结束语

本文基于HMM理论设计了一个脱机手写数字识别系统。设计过程中采用二值化、平滑去噪、字符切割、归一化、倾斜校正、细化等进行图片预处理。对数字识别特征提取有多种方法，本论文采用的方法是先提取数字的轮廓特征，然后对图像进行裁剪之后按黑像素占总像素的比率提取出特征值，最后用Viterbi算法计算匹配率实现数字识别。经过多次试验表明，对于书写较为工整的孤立数字，系统识别率较高。本文的结论初步说明了，类似于HMM在语音识别中的成功运用，把HMM应用到脱机手写体识别中是可以的。

基金项目

安徽省教育厅重点项目(KJ2017A851)。