基于隐马尔可夫模型的3D手写识别方法

收稿日期:2011-12-15;修回日期:2012-02-01 基金项目:安徽省高等学校省级优秀青年人才基金资助项目(2012SQRL228) ;安徽高校 省级自然科学研究项目(KJ2012Z134) 作者简介:王琦进(1980-) ，男，安徽人，讲师，硕士，主要研究方向为模式识别与应用、Ad hoc 无线网络(qjwang118@ yahoo． com． cn) ;齐晓霞 (1980-) ，女，安徽人，讲师，硕士，主要研究方向为人工智能与模式识别;江义渊(1969-) ，男，台湾人，助理教授，博士(后) ，主要研究方向为模式识 别与智能系统;徐旺兴(1970-) ，男，台湾人，助理教授，博士，主要研究方向为模式识别与智能系统、计算机网络与通信． 基于隐马尔可夫模型的 3D手写识别方法* 王琦进1，齐晓霞1，江义渊2，徐旺兴2 (1．安徽新华学院 信息学院，合肥 230088;2．台湾万能科技大学 资讯工程系，台湾 中砺 32061) 摘 要:为实现便捷高效的人机交互，提高交互能力，在基于隐马尔可夫模型(HMM)的基础上，提出了一种新 的 3D手写识别方法。该方法使用带有三轴加速度传感器的手持设备去采集各种手写数据;使用插值及快速傅 里叶变换(FFT)滤波等方法对采集的数据进行预处理;使用隐马尔可夫模型对每个手写动作进行模型训练;使 用训练过的手写模型对采集的数据进行手写识别。数据测试结果表明，该方法在手持移动设备上数据分类的准 确性可达到 84． 5%。 关键词:手写识别;加速度传感器;隐马尔可夫模型;快速傅里叶变换 中图分类号:TP391. 4 文献标志码:A 文章编号:1001-3695(2012)09-3565-03 doi:10． 3969 / j． issn． 1001-3695． 2012． 09． 097 3D handwriting recognition method based on hidden Markov models WANG Qi-jin1，QI Xiao-xia1，CHIANG Yi-yuan2，HSU Wang-hsin2 (1． Collage of Information Engineering，Anhui Xinhua University，Hefei 230088，China;2． Dept． of Computer Science ＆ Information Engineer- ing，Vanung University，Chungli Taiwan 32061，China) Abstract:In order to achieve efficient and convenient human-computer interaction，improve interaction ability，this paper pro- posed a new 3D handwriting recognition method based on HMM． In this method，using of the tri-axis accelerometer mounted on a handheld device to collect various handwriting data;using of the interpolation and FFT filtering to preprocess the data;u- sing of the hidden Markov models to train every handwriting movement ;using of the trained HMM to carry out the handwriting recognition． Tested on the handwriting mobile device，the results show that the classification accuracy can reach 84． 5% ． Key words:handwriting recognition;accelerometers;HMM(hidden Markov models) ;FFT(fast Fourier transtorm) 手势识别是多通道人机交互领域的一个重要研究方向，其 本质是一种模式识别，属于多维模式识别和智能计算机接口的 范畴。近年来，随着移动传感设备的发展，手持移动设备也变 得越来越普及。人们希望借用其便携性，随时随地地做出一些 手势动作，实现人机交互。但由于手持移动设备在进行人机交 互过程中出现了交互效率低、自然性不好、用户认知负担过重 等问题，因此，如何研究出一种新兴的交互方法已成为人机交 互领域的研究热点之一。 目前针对手势识别系统的研究主要有两类:a)基于视频 (图形处理)的，b)基于传感器(加速度信号)的［1］。由于传感 器技术的快速发展，一种能够识别用户手势动作的交互技术已 经出现。其实，早在 20 世纪 90 年代初，有关科研人员就开始 了基于传感器的手势交互研究。IBM公司在 1996 年推出了一 种具有自动感知运动状态的运动感知设备，用于玩具和日常工 具中［2］;1998 年 Harrison 等人对使用传感器作为用户操作接 口的可行性进行了探讨;2000 年 Bartlett等人在 PDA上使用旋 转、倾斜等手写实现滚屏、选择等功能［3］;2001 年 Rekimoto［4］ 将传感器移植到可穿戴的输入设备上，完成各种交互;2004 年 Ikjin 和 Wonbae 研究了手持设备中的加速度信号的处理方 法［5］;2005 年 Kela 等人［6］定义了手写接口的基本概念， 了手写识别系统 Smart Design Studio;2006 年 Bake等人［7］探讨 了如何识别用户连续的动作和手势;2007 年 Ferscha 等人［8］将 手势的概念泛化，根据手势的语法规则分为原子手势和复杂手 势两种，并建立了手势库 Glib，可供基于加速度传感器的系统 使用。 对于如何使用加速度信号进行手势识别，有些文献也做了 介绍，但它们的大多数工作集中在识别简单或者相同的手势， 如简单的线性移动和变向以及阿拉伯数字等。Hsu 等人［9］尝 试了 LCS-SVM的方法对连续字母即英文单词进行识别，取得 了较好的效果，但该方法对单个字母的识别率相对较差。本文 在上述研究的基础上，在三维空间中针对 26 个英文字母提出 了一种基于隐马尔可夫模型的 3D 手写识别方法。隐马尔可 夫模型是语音识别领域中最成功的统计模型之一，但其在 3D 加速度传感领域中的手势识别还是一个崭新的研究方向。 1 隐马尔可夫模型及其学习算法 1. 1 隐马尔可夫模型 隐马尔可夫模型(HMM)是一种具有学习能力的统计模 型，该模型对时变、非平稳时间序列具有较好的效果，已被 第 29卷第 9期 2012年 9 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 29 No. 9 Sep． 2012 成功用于语音信号识别、故障检测等领域［10］。 HMM可以记为 λ =(N，M，A，B，π ) 简写为 λ =(A，B，π ) (1) 其中:N为隐藏状态数;M为每个状态下的观察序列长度;A为 状态转移概率矩阵，记为 A ={aij}，aij = P(qt + 1 = sj | qt = si) ，表 示从状态 si 转移到状态 sj 的概率;B 为观察值概率矩阵，记为 B = bj(k)= P(vk at t | qt = sj) ，表示在状态 si 时输出符号 vk 的 概率;π 为初始概率分布矢量，记为π ={πi}= P(i1 = i) ，表示 状态 i在初始时间 t = 1 时的概率。 从上述隐马尔可夫模型的定义以及给定的模型参数可以 看出，隐马尔可夫模型是一个数学上的双重随机过程，可以应 用于时变数据的建模工作。 1. 2 Baum-Welch算法 HMM模型的训练采用 Baum-Welch算法，它是一种基于期 望最大化的算法，根据最大似然准则(maximum likelihood，ML) 对模型参数进行迭代的重新估算，直至得到最大似然意义下的 最优模型参数值［11］。它通过估计模型参数 A、B 和π ，使模型 生成观察序列的概率 P(O | λ)最大化，以增强模型的预测 性能。 算法描述为:定义变量 ξt(i，j) ，ξt(i，j)表示在给定模型 λ 和观察序列 O的情况下，模型 t时刻处于状态 i，t + 1 时刻处于 状态 j的概率，即 ξt(i，j)= P(qt = i，qt + 1 = j | O，λ)。经过推导 ξt(i，j)可以表示为 αt(i)和 βt(j)的函数，即 ξt(i，j)= P(qt = i，qt + 1 = j O，λ)= P(qt = i，qt + 1 = j，O λ) P(O λ) = αt(i)aij bj(Ot + 1)βt + 1(j) ∑ N i = 1 ∑ N j = 1 αt(i)aij bj(Ot + 1)βt + 1(j) (2) 其中:αt(i)和 βt + 1(j)分别为前向变量和后向变量。 若 t时刻状态为 Si 的概率为 γt(i)=∑ N j = 1 ξt(i，j) (3) 则 Baum-Welch算法可表示为 珟πi = α1(i)β1(i) ∑ N j = 1 α1(j)β1(j) 珘αij = ∑ T － 1 t = 1 ξt(i，j) ∑ T － 1 t = 1 γt(i) = ∑ T － 1 t = 1 αt(i)aij bj(Ot + 1)βt + 1(j) ∑ T － 1 t = 1 ∑ N j = 1 αt(i)aij bj(Ot + 1)βt + 1(j) 珘β jk = ∑ T t = 1 OK = VK γt(j) ∑ T t = 1 γt(j) = ∑ T t = 1 αt(j)βt(j)δ(Ot，VK) ∑ T t = 1 αt(j)βt(j) (4) 1. 3 前向算法 前向算法可看成求一个隐马尔可夫模型与一个观察值序 列的匹配程度［12］。该算法从若干模型中选择最优的，进而得 到最匹配的序列模型。 算法描述为:定义前向变量 αt(i)= P(O1，O2，…，Ot，qt = si |λ) ，表示模型 λ下、在 t时刻，观察事件为 Ot、状态为 si 的概 率，则在 t + 1 时刻: αt + 1(j)= P(O1，O2，…，Ot + 1，qt + 1 = sj λ)= ∑ N i = 1 ai(i)a[ ]ij bj(Ot + 1) (5) 则前向算法为 初始: a1(i)= πi bi(O1) 1≤i≤N (6) 递归:αt + 1(j)= ∑ N i = 1 αt(i)a[ ]ij bj(Ot + 1) 1≤t≤N － 1，1≤j≤N (7) 终止: P(O λ)= ∑ n i = 1 αT(i) (8) 2 拟建的 3D 手写加速度识别系统 拟建的 3D手写加速度识别系统的流程如图 1 所示，它分 为数据训练(建模)流程和数据测试(识别)流程，主要由数据 采集、数据预处理、数据训练以及模式识别四部分构成。 2. 1 数据采集 实验使用HTC phone、iphone等带有内置加速度传感器的手 持设备进行数据采集，每隔约 18 ms采集一组数据，每个手写字 母的数据采集组数在 100 ～ 300 不等。传感单元以一定的频率 获取运动过程中 x、y、z三轴加速度值 ax、ay、az，并构成每一时刻 的运动加速度 Oi，记为 Oi =(ax，ay，az)。数据采集过程中，由于 个体差异，不同人执行同一个手势动作，其动作幅度和执行速度 有一定的差别，即使是同一个人多次执行同一动作也会有差异， 这样就造成了采样值的不确定性。本文对手势运动的速度和幅 度作了规定，同时要求同一人对相同采样对象进行数据采集，从 而保证手势动作执行的性。实验对 26 个大写字母“A ～ Z” 的手写数据进行了采集，每个字母采样 50次。 2. 2 数据预处理 2. 2. 1 插值法保持采样数据长度一致 在手写运动过程中，加速度值在 x、y、z三轴上具有沿时间 连续变化的属性。如果某次采样速度偏离正常值，便会造成采 样时间的快慢不同，导致数据长度的不同，从而使识别成功率 降低。同时由于 MATLAB 的 HMM toolbox 要求实验数据在长 度上保持一致，因此使用插值法来解决。为了不丢失采样数据 所携带的信息，实验没有选用求平均数据长度的方法，而是选 择一组采集数据中长度最长的一个，其余数据通过插值算法与 最长数据保持一致。 2. 2. 2 FFT滤波去杂讯 快速傅里叶变换(FFT)是离散傅里叶变换的快速算法，它 在数字信号处理、计算大整数乘法、求解偏微分方程等方面有 着广泛地应用。在利用 FFT进行滤波时，通常使用截止频，通 过设置一个高低通频率界限，从而起到滤波的效果。本实验使 用手持加速度设备进行数据采集，采集的数据即使在外界无动 作的情况下依然会产生很小的杂讯噪声，并且手写运动过程也 会不可避免地产生轻微抖动，产生杂讯。实验需要去掉的是不 ·6653· 计 算 机 应 用 研 究 第 29卷 足以表征手写信息的杂讯噪声，通过将频率域中的某些频率成 分幅值进行设置，然后运用 IFFT 变换到时间域从而达到滤波 的效果。图 2 所示为字母“F”在 x轴上使用 FFT及 IFFT做滤 波的过程。 如图 2(a)所示，由于采样过程中的轻微抖动，使得原始的 未经处理的数据的频率带有杂讯波，曲线呈锯齿状;如图 2(b) 所示，在经 FFT转换到频域图后，仍可以看到存在低能量的杂 讯波。实验经过多次测试，当频率成分幅值为 50 时进行杂讯 噪声的去除，效果最好(如图 2(c)所示)。图 2(d)与(a)相比， 经过 IFFT转换回时间域的频率曲线变的平滑，达到了滤波去 杂讯的效果。实验表明，进行 FFT后的手写识别率比未经 FFT 时要高 9． 3%。 2. 2. 3 状态数与观察值序列 根据隐马尔可夫模型的定义，在解决模式识别的问题中， 应首先确定模型的隐藏状态数 N。理论上讲，状态数越多越 好，这是因为随着状态数的增加，识别的错误率会降低到一个 很稳定的程度。然而由于训练样本是有限的，所以状态数不能 太大。如果实验中状态数 N 选取过大，则训练后很多状态在 参数模型的对应项中将变为 0 或非常接近于 0，成为冗余项， 通常实验中状态数按其复杂程度固定为 2 ～ 8 不等的数目。 每个状态下不同的观察值个数 O，观察值与要构建系统的 输出息息相关，这里的观察值就是手势运动过程中的加速度向 量，标记为 O ={a1，a2，…，an}。图 3、4 为一组字母“A ～ Z”在 手写过程中加速度观察值的量化过程。从图 3 的加速度分布 可以看出，图形的波峰与波谷处是手写运动过程中特征信息点 的位置，这些点的变化转移也是手势运动方向的变化转移过 程，通常伴随着大加速度值的产生。在图 4 的加速度直方图 中，加速度值“0”附近，堆集了大量的手写信息点，而这些点通 常不带有过多的特征信息，它只是手写过程中一个相对平稳的 过程，较少出现运动方向的变化转移。 2. 3 数据训练 使用观察值序列调整 HMM参数称为一个训练过程。训练 问题是一个非常重要的问题，因为它可以使模型参数最为理想 地适应所观察到的训练数据。数据在经过预处理并得到观察值 序列后，由 Baum-Welch算法训练出离散的 HMM数据模型。 实验在每个手写字母的 50 笔采样数据中随机抽取 40 笔 进行训练。由于训练对 x、y、z三轴加速度数据单独进行，因此 每个手写字母的数据模型均由 x、y、z 三轴单独模型所组成。 模型表示为 λs，t，s∈{A，B，C，…，Z}，t∈{x，y，z} (9) 其中:s表示 A ～ Z的 26 个大写字母，t表示 x、y、z三轴。 2. 4 模式识别 在完成数据训练并得到相应的 HMM模型后，利用每个字 母的剩余 10 组数据进行测试。本文把测试数据分别丢入每个 模型，通过得到的对数似然函数(log-likelihood，LL)值来判别 测试数据与统计模型的成功识别率。由于 x、y、z 三轴加速度 模型为单独训练，因此每个字母的对数似然函数值定义为 LL(s)= def LL(s，x)× LL(s，y)× LL(s，z) ，s∈{A，B，C，…，Z} (10) 实验依据 max(LL)对采样数据进行分类，如 LL(s = ‘M’) ，而 max(LL(s) )= LL(M) ，那么分类结果与数据出处相 吻合，识别成功。 3 实验结果 为了评价本文的手写识别模型，对 26 个大写字母，共 260 笔数据进行了测试。实验选用的状态数为 4，观察值个数为 8。 表 1 为字母识别成功率结果(由于篇幅限制，选择部分字母)。 表 1 字母测试的成功识别率(部分) /% 字母 A B C D E F G H I 识别率 50 80 100 100 40 80 100 90 80 字母 J K L M N … X Y Z 识别率 80 90 20 100 90 … 100 90 90 从表 1 的字母识别率可以看出，除个别字母的识别率较低 外，其他字母识别率均达 80%以上。其原因为:“L”(识别率为 20%)“U”(识别率为 30%)等个别字母识别率过低，从而影响 到总体识别率。个别字母由于在手写过程中动作幅度变化不 明显，没能产生足够的特征信息，因此识别率过低。实验对所 有测试数据进行逐一比对，总体识别成功率达 84. 5%。 4 结束语 本文提出了一种基于隐马尔可夫模型的 3D 手写加速度 识别系统。它以手势作为人机交互对象，根据手和胳膊的运动 轨迹(三维)找出其中的含义，从而实现了一种高效、自然的人 机交互手段。系统在实现过程中，首先使用带有加速度传感器 的手持设备进行数据采集;在获取了加速度值之后，再对数据 进行预处理;然后从同一动作的诸多加速度序列中选择若干序 列进行模型的构建;最后使用剩余序列对该模型进行测试，从 而达到手写识别的目的。实验结果表明，本文方法是有效的， 其分类精度可达 84. 5%。 在下一步工作中，将考虑使用精度更高的加速度传感设备 进行数据采集，以获得更加准确的 3D 手势运动信息，从而进 一步改善手写识别的效果。此外，使用连续型隐马尔可夫模型 以及隐马尔可夫模型与高斯混合模型相结合 (下转第 3570 页) ·7653·第 9 期 王琦进，等:基于隐马尔科夫模型的 3D手写识别方法 成扫描路长较长，加上层与层之间的准备工序时间 Ta，则实际 制作总耗时 T 也大为增加;而当切片厚度为 0. 3 mm 时，大斜 面处的阶梯效应有所增加，工艺总耗时则相应减少;切片厚度 为 0. 4 mm时，阶梯效应已经对表面质量产生实质性影响。 成品表面质量随着切片厚度的减小而提高，而工艺耗时则相 应增加，这是一对矛盾综合体。实际确定切片时，可根 据具体的工艺成本及表面质量要求进行合理选择。对于本 例，切片厚度 h≥0. 4 mm 时，阶梯效应对表面质量产生不可 忽视的影响，所制作的成品已无实际意义(除非另有其他特 殊目的)。综合考虑制作耗时及表面质量的情况下，可选取 h = 0. 3 mm的切片方案。如对表面质量要求特别高而对制作 耗时无太大要求的情况下，可选择切片厚度为 0. 2 mm 或更 小的切片方案。 表 1 重建参数及计算结果(Intel Core双核 2. 50 GHz /RAM 3 GB) H /mm h /mm n L /mm 重建耗时 / s 45 0． 2 225 36 662 180 0． 3 150 24 459 123 0． 4 113 18 390 94 3 结束语 在目前广泛应用的“3D打印”等立体制造技术领域中，3D 模型的离散切片是必不可少的前处理步骤，其切片方案直接影 响着后续的制造过程以及成品效果。而目前只能通过事后的 实际制造来对切片及工艺耗时进行评价。本文提出的评价方 法可对切片方案进行制造前的预测及评价。通过引入可视化 算法及路长计算技术，实现对立体制造的完全模拟，把成品事 先显示在计算机中，并对工艺耗时进行估算。上述两个方面的 指标为合理选取切片方案提供了依据。大量的实例应用验证 了本文所提算法的有效性及稳定性，能减少失败次数，控制开 发成本。 参考文献: ［1］ 赵吉宾，刘伟军． 快速成型技术中分层算法的研究与进展［J］． 计算机集成制造系统，2009，15(2) :209-220． ［2］ 王静亚，方亮，郝敬宾． STL模型特征面片自适应分层算法［J］． 计算机应用研究，2011，28(6) :2361-2364． ［3］ LEE K S，KIM S H． Non-uniform deformation of an STL model satis- fying error criteria［J］． Computer-Aided Design，2010，42(3) : 238-247． ［4］ QIU Yan-jie，ZHOU Xiong-hui，QIAN Xiao-ping． Direct slicing of cloud data with guaranteed topology for rapid prototyping［J］． The In- ternational Journal of Advanced Manufacturing Technology， 2011，53(1-4) :255-265． ［5］ 陈鹏飞，牟小云． 基于模型几何连续性的快速成形分层算法的改 进与实现［J］． 工程图学学报，2009，30(4) :198-203． ［6］ 龚奇伟，张李超，莫健华． STL模型自动镂空的算法与应用［J］． 计算机辅助设计与图形学学报，2007，19(1) :54-58． ［7］ 李阳，李辉． 基于形状相似性的快速成型扫描算法检索实例 ［J］． 计算机工程与设计，2009，30(21) :4998-5002． ［8］ 闫锋欣，侯增选，张定华，等． 基于压缩体素模型的快速成型直接 切片算法［J］． 计算机应用研究，2007，24(10) :246-248． ［9］ 王正友，黄林林，张国贤． 基于分层切片原理的三维雕刻算法 ［J］． 计算机应用，2011，31(2) :379-382． ［10］马巧梅，朱林泉．快速成型系统中自适应的直接切片算法的研究 ［J］． 计算机工程与设计，2009，29(8) :2075-2077． ［11］龚奇伟，张李超，莫健华． STL 模型自动镂空的算法与应用［J］． 计算机辅助设计与图形学学报，2007，19(1) :54-58． ［12］ ANCAU M，CAIZAR C． The computation of pareto-optimal set in multicriterial optimization of rapid prototyping processes［J］． Com- puters ＆ Industrial Engineering，2010，58(4) :696-708． ［13］钟山，杨永强． 快速成形数据处理的分层算法［J］． 计算机集成 制造系统，2011，17(6) :1195-1120． (上接第 3567 页)的方法也是笔者进一步的研究方向。 参考文献: ［1］ 徐光佑，陶霖密，史元春，等． 普适计算模式下的人机交互［J］． 计 算机学报，2007，30(7) :1041-1053． ［2］ BARTLETT J F． Rock‘n’scroll is here to stay［J］． IEEE Comput- er Graphics and Applications，2000，20(3) :40-45． ［3］ HINCKLEY K，PIERCE J，SINCLAIR M，et al． Sensing techniques for moblie interaction［C］/ /Proc of the 13th Annual ACM Symposium on User Interface Software and Technology． New York:ACM，2000: 91-100． ［4］ REKIMOTO J． GestureWrist and GesturePad:unobtrusive wearable interaction devices［C］/ /Proc of the 5th IEEE International Symposi- um on Wearable Computers． Washington DC:IEEE Computer Socie- ty，2001:21-27． ［5］ JANG I J，PARK W B． Signal processing of the accelerometer for ges- ture awareness on handheld devices［C］/ /Proc of the 12th IEEE In- ternational Workshop on Robot and Human Interactive Communica- tion． 2003:139-144． ［6］ KELA J，KORPIPAA P，MANTYJARVI J，et al． Accelerometer-based gesture control for a design environment［J］． Personal and Ubiqui- tous Computing，2005，10(5) :285-299． ［7］ BAEK J，YUN B J． A sequence-action recognition applying state ma- chine for user interface［J］． IEEE Trans on Consumer Electron- ics，2008，54(2) :715-726． ［8］ FERSCHA A，RESMRITA S． Gestural interaction in the pervasive computing landscape［J］． Elektrotechnik ＆ Informationstechnik， 2007，124(1) :17-25． ［9］ HSU Wang-hsin，CHIANG Yi-yuan，WU Jung-shyr． Integrating LCS and SVM for 3D handwriting recognition on handheld devices using accelerom- eters［J］． WSEAS Trans on Computers，2010，9(2):235-251． ［10］ RABINER L R，JUANG B R，JUANG B H． A tutorial on hidden Markov models and selected applications in speech recognition［J］． Proceeding of the IEEE，1989，77(2) :257-286． ［11］王西颖，戴国忠，张习文，等． 基于 HMM-FNN 模型的复杂动态手 势识别［J］．软件学报，2008，19(9) :2302-2312． ［12］王悦，岳玮宁，董士海，等．手持移动计算中的多通道交互［J］． 软 件学报，2005，16(1) :29-35． ·0753· 计 算 机 应 用 研 究 第 29卷