（控制理论与控制工程专业论文）运动目标轨迹分类与识别研究.pdf

两北j ：业大学硕十学位论文摘要 摘要 运动目标轨迹分类与识别是运动分析中的基本问题，它的功能是解释所监 视场景中发生的事件，对所监视场景中运动目标轨迹的行为模式进行分析与识 别，智能地做出自动分类；由当前目标所处的状态对将要发生的事件进行预测， 根据要求对异常事件进行报警，从而达到安全监控的目的。本文对运动目标轨 迹分类与识别作了较深入的研究，主要工作如下： 1 提出了一种新的真实场景中运动目标轨迹有效性判断的方法。在目标躁 踪过程中由于刮风等的影响而使一些轨迹受噪声严重干扰，本文基于轨 迹长度、轨迹上点坐标值的方差以及运动目标相邻两帧运动方向的角度， 对真实场景中跟踪到的轨迹预处理，进行有效性判断从而获得有效的轨 迹，为进一步轨迹分类提供样本。 2 应用k 均值自动聚类算法，提出了一种新的基于轨迹空间相似距离的轨 迹分类算法，对以上获得的有效轨迹进行分类。结果表明该算法分类效 果较好，最后获得两个真实场景中6 类轨迹共3 0 5 个轨迹样本，为进。一 步的轨迹识别奠定基础。 3 深入研究了隐马尔可夫模型的三大经典算法，指出了隐马尔可夫模型算 法在应用中的一些问题，及针对这些问题所提出的改进方法。 4 引入改进的隐马尔可夫模型算法进行轨迹识别。针对轨迹的复杂程度对 各个轨迹模式类建立相应的隐马尔可夫模型，利用训练样本训练模型得 到可靠的模型参数，计算测试样本对于各个模型的最大似然概率，选驭 最大概率值对应的轨迹模式类作为轨迹识别的结果，对两种场景中聚类 后的轨迹进行训练与识别，实验结果表明：识别率分别达到8 7 7 6 和 9 4j 9 。 关键词：轨迹分类与识别，有效性判断，k 均值，自动聚类，隐马尔可夫模型 州北i 业人学硕十学位论文 a b s t r a c t a b s t r a c t t r a j e c t o r yc l a s s i f i c a t i o na n dr e c o g n i t i o no ft h em o v i n go b j e c t sa r et h eb a s i c p r o b l e mo ft h em o v e m e n ta n a l y s i s i t sf u n c t i o n sa r ea sf o l l o w s ：i n t e r p r e t i n gw h a th a s h a p p e n e di ns u r v e i l l a n c es c e n e s ，a n a l y z i n ga n dr e c o g n i z i n gt h et r a j e c t o r ya c t i v i t y p a t t e r n so f t h eo b j e c t si nr e a ls c e n e s ，c l a s s i f y i n gt h e ma u t o m a t i c a l l ya n di n t e l l i g e n t l y a n dw h a tw i l lh a p p e ni sp r e d i c t e da c c o r d i n gt ot h ec u r r e n ts t a t e so ft h eo b j e c t ， a l a r m sa r es e n tf o r t h ea b n o r m a la c t i v i t yi ng o o dt i m e i nt h ee n dt h es a f e t y s u r v e i l l a n c ec a nb er e a l i z e d i nt h i st h e s i s ，t h e t r a j e c t o r y c l a s s i f i c a t i o na n d r e c o g n i t i o na r es t u d i e di nd e t a i l t h em a i n c o n t r i b u t i o n sa r ea sf o l l o w s ： 1 d u et os o m et r a j e c t o r i e sa r ei n t e r f e r e db a d l yb yt h en o i s e ss u c ha sw i n de t c d u r i n gt h et r a c k i n go fo b j e c t s ，an o v e lm e t h o dt h a tc a l lj u d g et h et r a j e c t o r i e s s v a l i d i t yi sp r e s e n t e d t h r o u g ha n a l y z i n gt h el e n g t h ，v a r i a n c eo ft h ec o o r d i n a t e s a n do r i e n t a t i o nc o d eo ft h e t r a j e c t o r i e sb e t w e e nt w on e i g h b o u rf r a m e s ， p r e p r o c e s st h e ma n dg e tt h ev a l i do n e sa ss a m p l e sf o rf u r t h e rs t u d y 2 、u s i n gkm e a n sw h i c hc a na u t o m a t i c a l l yc l u s t e rt r a j e c t o r i e s ，an e wa l g o r i t h m b a s e do nt r a j e c t o r ys p a c es i m i l a r i t yd i s t a n c ei sp r e s e n t e d ，a n di t i sa p p l i e dt o c l a s s i f yt r a j e c t o r y t h er e s u l t sa r es a t i s f i e d f i n a l l y , 3 0 5t r a j e c t o r ys a m p l e so f6 c l a s s e sa r eo b t a i n e d ，a n di t l a y s ag o o df o u n d a t i o nf o rf u r t h e r t r a j e c t o r y r e c o g n i t i o n 3 am o r ed e t a i l e ds t u d y i n go f3c l a s s i ca l g o r i t h m so nh m mi sm a d e ，s o m e q u e s t i o n s i n a p p l i c a t i o na r ep o i n t e d ，a n dt h ec o r r e s p o n d i n gi m p r o v e m e n t m e t h o d sa r eg i v e nf o rt h e m 4 u s i n gh m m t ot r a j e c t o r y r e c o g n i t i o ni si n t r o d u c e d f i r s t l y , a i m i n ga tt h e c o m p l e xd e g r e eo ft h et r a j e c t o r i e s ，t h em o d e la r eb u i l tf o re v e r yt r a j e c t o r y p a t t e r n ，a n dt h et r a i n i n gs a m p l e sa r eu s e dt og e tt h ec r e d i b l ep a r a m e t e r so ft h e m o d e l ，f i n a l l y , t h em a x i m u ml i k e l i h o o dp r o b a b i l i t yo ft e s t s a m p l e s a r e c o m p u t e dt oa 1 1o ft h et r a i n e dm o d e l t h em a x i m u mv a l u ei ss a v e da n dt h e c o r r e s p o n d i n gm o d e li st h er e c o g n i t i o nr e s u l t t h e nt r a i na n dr e c o g n i z et h e s a m p l e sc l u s t e r e d ，a n dr e c o g n i t i o nr a t er e a c h8 7 7 6 a n d9 4 19 r e s p e c t i v e l y k e y w o r d s ：t r a j e c t o r yc l a s s i f i c a t i o na n dr e c o g n i t i o n ，v a l i d i t yj u d g i n g ，km e a n s ， a u t o m a t i cc l u s t e r i n g ，h i d d e nm a r k o vm o d e l ( h m m ) 第一章绪论 1 1 研究背景及意义 第一章绪论 目前，真实场景的智能监控( s m a r ts u r v e i l l a n c e ) 【j 是计算机视觉领域一个 新兴的研究方向，它是从摄像机摄取的图像序列中检测、识别、跟踪目标并对 其行为进行理解。这里所指的“智能”含义是指系统能够监视一定场所中人的 活动，并对其行为进行分析和识别，跟踪可疑行为( 如经常在重要地点徘徊等 行为) 从而采取相应的报警措施。通常把报警系统设置于银行、机场、车站、 码头、超市、办公大楼、住宅小区等地，以实现对这些场所的智能监控。智能 视觉监控就是要用计算机视觉的方法，在不需要人为干预的情况下，通过对摄 像机拍录的图像序列进行自动分析，实现对动态场景中目标的定位、识别和跟 踪，并在此基础上分析和判断目标的行为，从而做到既能完成日常管理又能在 异常情况发生时及时做出反应。、 对于智能监控系统( 区别于传统意义上的监控系统，它具有智能性。简单 而言，不仅用摄像机代替人眼，而且用计算机代替人、协助人，来完成监视或控 制任务。) 丽言，一般涉及到运动检测、运动目标分类、运动目标的跟踪以及所 监视场景中目标行为的理解与描述等几个过程口】。其中，运动检测、目标分类、 人的跟踪属于视觉中的低级和中级处理部分( l o w 1 e v e la n di n t e r m e d i a t e 1 e v e l v i s i o n ) ，而行为理熊和描述则属于高级处理( h i g h l e v e lv i s i o n ) 。运动检测、运 动目标分类与跟踪是视觉峪控中研究较多的三个问题，而行为理解与描述则是 近年来被广泛关注的研究热点，它是指对目标的运动模式进行分析和识别，并 用自然语言等加以描述。目标运动轨迹 3 1 分类和异常行为检测便是其中的一部 分。轨迹的分类是运动分析中的基本问题，它的最终目的就是为了解释监视场 景中所发生的事件，对监控系统所监视的真实场景中的行为轨迹模式进行分析 和识别，做出智能的自动的分类，以便检测出异常行为f 4 “j ，根据要求对异常事 件及可疑事件进行报警，并能由当前目标所处的状态对将要发生的事件进行预 测，从而达到安全监控的目的。 智能监控系统的需求主要来自那些对安全要求敏感的场合1 7 , 8 】，如银行、商 雨，i t ：f 业大掌硕十学位论文第一章绪论 店、停牟场、军事基地等。我们所需要的监控系统能够每天连续2 4 小时的实时 监视，并自动分析摄像机捕捉的图像数据，当盗窃发生或发现到具有异常行为 的可疑运动目标时，系统向保卫人员准确及时地发出警报，从而避免犯罪的发 生，而目前监控系统没有达到很好的效果：在访问控制场合，可以利用人脸或 者步态的跟踪识别技术以便确定来人是否具有进入该安全领域的权力；另外， 人体运动分析在自动售货机、a t m 、交通管理、公共场所行人的拥挤状态分析 及商店中消费者流量统计等监控方面也有着相应的应用f ”】。 由于基于目标的运动分析和事件识别的智能监控在经济、军事等具有对安 全要求敏感的场合具有广泛的应用前景和潜在的经济价值，从而激发了国内外 广大科研_ t 作者及相关商家的浓厚兴趣，尤其在美、英等国已经开展了大量相 关项目的研究”“。 1 2 轨迹分类的方法 目前，视觉监控越来越受到国内外很多学者的密切注意。国际上一些权威 期刊如i j c v ( i n t e r n a t i o n a lj o u r n a lo fc o m p u t e rv i s i o n ) ，p a m i ( 1 e e et r a n so n p a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ) ，i v c ( 1 m a g ea r i dv i s i o nc o m p u t e r ) f 1 1 重 要的学术会议如i c c v ( i n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t e rv i s i o n ) 等，相继刊登 了大量有关智能视觉监控领域内的最新研究成果，将智能监控中的运动目标检 测跟踪和事件识别作为主题内容之一，为该领域的研究人员提供了更多的交流 机会。美国、英国等国家已经开展了大量相关项目的研究。到目前为止，在视 觉监控相关领域内做出了比较突出的贡献的研究组有： ( 1 ) 英国雷丁大学计算机系的v i e w s 项目组； ( 2 ) 德国卡尔斯鲁厄大学计算机系h h n a g e l 博士领导的研究组； ( 3 ) 美国伯克利大学计算机系的r o a d w a t c h 项目组； ( 4 ) 美国卡内基梅隆大学和马里兰大学等参加的v s a m 项目组： ( 5 ) 美国康奈尔大学计算机系d a n i e lh u t t e n l o c h e r 教授领导的研究组： ( 6 ) 加拿大英属哥伦比亚大学计算机系d a v i dl o w e 教授领导的研究组等。 近年来，公共场所的智能监控【1 3 j 己成为全世界关注的热点问题之一。智能 j 瞌控系统成功之处之一在于其有能力实时的识别 1 4 1 并分类人的行为轨迹模式， 分类币常和异常的轨迹，并检测异常行为，以便解释所监视场景中所发生的事 件根据预先设定的要求对异常事件进行报警，并能根据对运动目标所处的状 曲北r 。业人学硕士学位论文 第一章绪论 态或者位置预测即将要发生的事件，减少危险事件的发生。 目前轨迹分类的典型方法主要有以下几种。 1 2 1 隐马尔可夫模型( h m m ) 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，h m m ) 【l ”】是一种很成熟的匹 配时变数据的技术，它是随机状态机器。h m m 的使用涉及至l j i j j l 练和分类两个 阶段，训练阶段包括指定一个隐马尔可夫模型的隐状态个数，并且优化相应的 状态转移和输出概率以便产生的输出符号与在特定的运动类别之内所观察到的 图像特征相匹配。对于每一个轨迹模式类别，训练一个h m m 。匹配阶段涉及 到一个特定的h m m 可能产生相应于所观察图像特征的测试符号序列的概率计 算。 k ak e u n gl e e m a o l i ny ua n dy a n g s h e n gx u ”j 提出一种分离轨迹的局部的 和整体的信息，利用两种专门的学习机制进行处理，并考虑了人的轨迹的时间 利顺序特性。在整体轨迹相似性估计中研究了一种基于h m m 的相似性度量 ( s i m i l a r i t ym e a s u r e ) 来比较不同轨迹间的相似程度。 1 2 2 动态时间规整( d t w ) 动态时间规整( d y n a m i ct i m ew a r p p i n g ，d t w ) 卅是t a k a h a s h i 在1 9 9 2 年提出的，它是一种基于刚问轴的动态操作技术，适用于时间可变的问题中， 早期被应用于语音识别中，近几年被应用于匹配人的运动模式和动态手势的轨 迹识别等中，具有概念简单、算法鲁棒等优点。在测试模式和参考模式之间容 y i ：充分的弹性从而实现正确的分类。但它不能操作一些未定义的模式。 1 2 3 神经网络( n n ) 神经网络( n e u r a ln e t w o r k ，n n ) 在处理很大数据样本集时非常有用，它 也是目前匹配时变数据的方法之一，如g u o l 2 等用其分析人的运动模式， r o s e n b l u m l 2 1 j 等使用径向基函数网络从运动中识别人的情感。g zs u n ，h h c h e n e t c 2 2 1 提出一种时间规整周期神经网络( t i m ew a r p i n gr e c u r r e n tn e u r a l n e t w o n s ，t w r n n ) 模型来处理时间规整连续信号并进行轨迹分类，这种模型 很容易学会轨迹的特点。在j o h n s o na n dt t o g g i ”】研究的系统中，神经网络用于 学习观察到的典型轨迹的概率密度函数，但是它只能在整个轨迹给出后分类出 3 曲j 匕i 业人学硕士学位论文 第一章绪论 所观察到的轨迹。而不能用于动念模式的识别，因此有人提出采用n n 和h m m 相结合的方法以弥补其不足。 除了上面这几种方法之外，2 0 0 4 年k ak e u n gl e e ，m a o l i ny ua n dy a n g s h e n 2 x u 4 1 又研究出一种智能视觉监控系统，这种系统能够自动分析人的行走轨迹。 它是一种基于最长普通子序列( l o n g e s tc o m m o ns u b s e q u e n c e ，l c s s ) 的方法， 分析己观察到的待分类轨迹的整体特性。为了正确决定分类边界，他们采取融 合支持向量回归( s u r p p o r tv e c t o rr e g r e s s i o n ) 和多层神经网络( c a s c a d en e u r a l n e t w o r k s ) 的方法以建立匹配的边界。f o r e s t ia n dr o l l l 2 5 锄究了个利用二值 神经树的能够定位、跟踪和分类危险事件的系统，其中采用p a r a m e t r i cb e z i e r 曲线估计待分类的目标轨迹：o w e n sa n dh u n t e r 2 6 1 运用一种基于自组织映射 ( s e l f - o r g a n i s i n gm a p p i n g ，s o m ) 的方法进行轨迹分类。这两种系统利用一种 单一的学习机制来处理局部的和整体的轨迹信扈。i v a n o ce ta 1 吲研究的视频监 控系统能跟踪一个场景中车和人的运动，但它不分析轨迹的具体形状，而只是 给出轨迹的起点和终点。s u p r i y ar a oa n dp s s a t r y 【5 1 于2 0 0 3 年提出了在视频序 列中使用学习概率密度进行异常行为检测的方法。他们研究了用随机模型描述 场景t ，的正常行为。给定t f 常行为的视频序列，通过学习概率模型描述场景中 的l f 常行为。对于任意的新的视频序列，利用己学习的概率模型提取并估计运 动轨迹，以识别他们是否正常。他们还采用通用的基于模型的方法来描述单独 目标的运动。模型参数用最火似然框架估计出来。其中的模型是基于独立模板 的模型( i n d e p e n d e n tp r o t o t y p eb a s e dm o d e l ，i p m ) 和基于马尔可夫模型的模型 ( m a r k o v i a np r o t o t y p eb a s e dm o d e l ，m p m ) ，并采用马尔可夫性假设获得较好 的实验结果。n i u ，w e i ，l o n ge t e 于2 0 0 4 年提出一种改善鲁棒性的行为检测 方法，通过提供智能控制，建立了帧差分和特征相关的检测算法。 目前我围在这方面的研究近几年才丌展起来的。由s t e v ej m a y b a n k 和中 科院自动化研究所所长谭钦牛组织的i e e e 视觉监控专题讨论会也已经成功地 举办了三届。( h t t p ：，w a v w s i n o s u r v e i l l a n c e c o m x s h s h t m ) 中国科学院自动化研究所模式识别国家重点实验室已经成立智能视觉监控 石j 究组，丌展这方面研究的目标是实现一个动态场景集成分析演示系统并最终 推向实用。西北工业大学控制与信息研究所依据在视频处理、多目标跟踪、多 传感器信息融合多年的研究经验，自主创新研发的实时智能视频监控与预警系 统，山潘泉教授、杨涛和李静博士等负责开发，系统由通用的p c 机和视频分 析软件组成，在w i n d o w s 平台运行。高度智能化和强大的实时视频分析能力是 该系统的特色，与传统的视频监控系统相比，该系统能够应对真实环境的各种 曲北业人学硕士学位论文第一章绪论 变化，在固定或移动载台上精确、实时、稳定地检测和跟踪监控现场感兴趣目 标、适时地进行目标分类，并对异常情况自动报警；智能化的报警控制，大沤 围监控区域电子地图显示，快速、高效的视频检索，极大的方便了用户的操作。 然而，该领域的轨迹分析方面的研究尚处于起始阶段。 1 3 轨迹识别的难点 尽管目前轨迹分类和异常行为检测已经取得了一定的成果，但是下述几个 方面仍是今后的研究难点问题，迫切需要引起广大科研工作者的高度关注。 1 3 1 轨迹的有效性判断 在目标跟踪阶段，我们获得了很多运动目标在真实场景中的行为轨迹。其 中有的轨迹是我们感兴趣的目标的轨迹，有跟踪完整的和不完整的：另一方面， 也有我们不感兴趣的目标的轨迹，这可能是由于失跟、误跟、遮挡或者噪声干 扰等造成的。在研究特定场景中运动目标的行为轨迹分类与识别前，我们必须 先判定哪些是我们所需要的轨迹。 1 3 2 轨迹的相似生度量 【_ i = | 于真实场景中跟踪的目标的轨迹有的是有规律的，而有的却杂乱无章， 而且，各个运动目标的速度在各个时刻不都相同，跟踪的帧数和跟踪时间长短 也不相等，轨迹上坐标点数不存在一一对应的关系，因此我们在进行轨迹相似 性度量的时候不能用简单的欧氏距离束度量。而轨迹间的相似性度量的准确与 否将直接影响我们轨迹模式分类及异常行为检测的结果正确率的高低。因此， 研究中准确度量轨迹相似性将是一个不可忽视的问题。 13 3 正常轨迹的建模 真实场景中的正常轨迹有很多类别，虽然他们都属于正常的行为轨迹，但 是他们都对应于不同的模型。因此，在进行h m m 训练的时候，我们必须建立 各种可能的f 常行为轨迹的模型以避免在识别分类过程中遇到从没学习过的模 5 曲，i l1 一业人学硕士学位论文 第一章绪论 型但却属于f 常行为轨迹。这就需要大量的训练数据。尽管这样会增加分类的 准确性，但同时也使得计算量加大。这也是研究中的一个难点。 1 4 轨迹识别的发展趋势 综合国内外的研究现状总结得到，轨迹识别与分类的发展趋势主要有以下 两个。 1 4 1 目标运动轨迹分析与生物特征识别相结合 在视觉监控系统及其他一些场合中，目标运动轨迹分析与其生物特征识别 结合的研究同益显得重要【2 i 。在近距离的监视中，不仅仅需要机器知道人是否 存在，人的位置和行为，而且还要利用人脸等生物特征识别技术来识别目标行 为及表情的类别，达到更安全的监控效果。 1 4 2 行为理解和描述 运动目标的行为理解和描述1 2 l 是科研工作者需要引起高度注意并且很具有 挑战性的研究方向，因为分析和理解运动目标的行为，以及和其他目标的交互 关系，是观察运动目标的最终目的之。其难点就是特征选择和机器学习。近 些年来，这方面的研究虽然有一定的进展，但仍处于初步阶段，所以，仍需要 寻找和丌发新的技术，以便在提高行为识别性能的同时，还能有效地降低计算 的复杂度。另外，如何借助先进的计算视觉方法和人工智能领域的成果，将现 有的简单的行为识别与语义理解推广到更为复杂场景下的自然语言描述，是将 计算机视觉低、中层次的处理推向更高层抽象思维的关键问题。 1 5 论文安排 本文受困家自然科学基会( 编号：6 0 3 7 2 0 8 5 ) 和陕西省科学技术研究发展 计划项目( 攻关项目) ( 编号：2 0 0 3 k 0 6 一g 1 5 ) 的资助，对轨迹的预处理，轨迹的 自动聚类以及轨迹的识别作了较深入的研究，主要内容安排如下： 第一章介绍了课题的研究背景及意义，轨迹识别的方法，阐述了其技术难 阳北i 。业大学硕十学位论文第一章绪论 点及可能的发展趋势，最后提出了本课题的研究目的、内容和方向； 第二章主要介绍了k 均值聚类的思想，轨迹聚类时距离的计算及h m m 的 定义，详细阐述了轨迹识别中h m m 的工作过程、基本原理，以及h m m 的三 大经典算法，指出了h m m 算法在应用中的一些问题，以及针对这些问题各位 学者所提出的改进方法： 第三章提出了一种新的轨迹有效性判断方法，主要是从轨迹长度、轨迹上 点坐标值的方差，以及目标相邻两帧运动方向角度这三方面做预处理以获得有 效轨迹样本，在此基础上提出一种新的基于k 均值的轨迹自动聚类算法，对两 个真实场景中运动目标的轨迹进行聚类，获得有效轨迹样本，为进一步的轨迹 识别奠定基础； 第四章提出了利用改进的h m m 算法进行轨迹识别。针对轨迹的复杂程度 建立相应的隐马尔可夫模型，利用训练样本训练模型得到可靠的模型参数，计 算测试样本对于各个模型的最大似然概率，选取最大概率值对应的轨迹模式类 作为轨迹识别的结果，实验对两个真实场景中的6 种轨迹进行了训i 练与识别， 分别达到较高的平均识别率8 77 6 和9 4 】9 。 第五章总结本文工作及对未来工作的展望。 1 6 本章小结 真实场景中运动目标轨迹的识别是把从场景内获取的轨迹信息经过智能化 的处理后传递给监控者，实现对既定场景的有效管理。本章介绍了课题的研究 背景及意义，轨迹分类与识别的方法，朝述了其技术难点和发展趋势，最后提 出了本课题的研究目的、内容和方向。 西j ei 业人学硕十学化论文 第二章k 均值聚娄及h 删基本理论 2 1 引言 第二章k 均值聚类及h m m 基本理论 聚类分析【2 。q 】是按照“物以类聚”的思想，对未知类别的样本，根据样本 之州的相似程度来分类，相似程度大的样本归为一类，不相似的归为另外的类 别。 在模式空间s 中，假没给定而，x 2 ，x ，聚类的定义是：按照相互之问相 似的程度找到相应模式s ，s 一，s 。，使各个，i = l ，2 ，归入到其中某一 类，而不会同时属于两个类别，也就是s u s 2 u s k = s 且sn s ，= o ，v i j ， 其中u 和n 分别表示并集和交集。 聚类分析是一种强有力的数据分类工具。不受某些先验知识的限制，用这 种分类方法要得到满意的结果，最基本的要求是模式空间应有聚类性质。聚类 应满足以下的三个要点： ( 1 ) 选定某种距离度量作为样本问的相似性度量； ( 2 ) 确定某个评价聚类结果质量的准则函数； ( 3 ) 给定某个幻始分类，然后用迭代算法找出使准则函数取极值的最好聚 类结果。 k 均值聚类算法足其中一种典型的聚类算法，迭代过程中，k 个均值会不 断变化，以使得一个平方误差准则函数最小化。从这个算法得到的结果既可咀 作为最终答案，也可以作为进一步计算的初始值。 在一些与时间相关的问题中，即某过程随着时间而进行，我们会说在t 时刻 发生的事件要受r 一1 时刻发生的事件的直接影响。在处理这些问题时，h m m 获 得了很好的应用1 3 2 , 3 3 1 ，例如在运动目标的轨迹洪别与分类、手势识别及语音识 别中等等。h m m 具有一组已经设置好的参数，它们可以最好地解释特定类别 中的样本。在应用中，一个测试样本被归类为能产生最大后验概率的那个类别， 也就是说，这个类别的模型最好地解释了这个测试样本。而有关它的理论基础， 却是在1 9 7 0 年前后由b a u m 等人建立起来的随后由c m u 的b a k e r 和i b m 的 j e l i n e k 等人将其应用到语音识别之叶，。山于b e l l 实验室r a b i n e r 等人在8 0 年 阳北f 业人学硕十学位论文 第一：章k 均值聚类及m i m 基本理论 代中期对h m m 的深入浅出的介绍，才逐渐使h m m 为世界各国从事语音处理 的研究人员所了解和熟悉，进而成为公认的一个研究热点。 本章主要介绍k 均值聚类算法及h m m 的基本理论、经典算法及其改进。 首先介绍k 均值聚类算法，然后从m a r k o v 链着手，介绍h m m 的基本概念， 从分析有关h m m 概念的实例，从而引出h m m 的定义及描述h m m 的参数。 接着阐述h m m 的工作过程、原理及h m m 的3 个经典算法：前向- 后向算法 ( f o r w a r d s b a c k w a r d sa l g o r i t h m ) 、v i t e r b i 算法和b a u m w e l c h 算法。这些算法 在后面的轨述分类与识别中反复用到。最后介绍了h m m 算法在实际应用中的 一些问题及改进方法，包括：初始模型的选取：用多个观察值序列训练模型参 数；为解决计算中的下溢问题而对算法加入比例因子的处理过程等等。 2 2 轨迹之间距离的度量 在聚类之荫首先选定某种距离度量列1 作为样本问的相似性度量。本文在对 轨迹进行聚类时选取h a u s d o r f f 距离【3 5 j 来度量轨迹之间的相似性。轨迹聚类的 目的是为了进一步准确地轨迹识别与分类1 1 0 垅】。针对轨迹序列长度不固定的特 点，本文采用基于h a u s d o r f f 距离的k 均值算法对轨迹聚类。 2 2 1h a u s d o r f f 距离 h a u s d o r f f 距离是描述两组点榘z 间相似栏度的一种厦量，它是两个点集 之问距离的一种定义形式：假设有两组集合爿= n ， ，b = 6 l ， ，则 这两个点集之间的h a u s d o r f f 距离定义为： x ( a ，b ) = m a x ( ( 爿，b ) ，a ( 口，爿) ) 、( 2 1 ) 其中， 自( 彳，古) = 呀r a 。i n a b l f ( 2 2 ) h ( b ，爿) = m 。a x m 。i ，ni b 一口i ( 2 3 ) 是点集a 和点集b 间的距离范式。这里，式( 2 一1 ) 称为双向h a u s d o r f f 距离，是h a u s d o r f f 距离的最基本形式；式( 2 2 ) 和式( 2 - 3 ) 中的h ( a ，b 1 和 苎i ! 些人学堕十学位论文 第一章k 均值聚类及h m m 基本理论 h ( b ，4 ) 分别称为从集合爿到集合口和从集合b 到集合a 的单向e a u s d o r f f 距 离。即h ( a ，b ) 实际上首先对点集a 中的每个点q 到距离此点最近的集合b 中点 b ，2 _ 1 日j 的距离怯一6 ，i l 进行排序，然后取该距离中的最大值作为h ( a ，剐的值。 ( 日，a ) 同理可得。由式( 2 一1 ) 可知，双向h a u s d o r f f 距离h ( a ，b ) 是单向距 离 ( 爿，8 ) 和办( 占，a ) 两者中的较大者，它度量了两个点集之日的最大不匹配程 唐。 2 2 ，2 轨迹之间的距离 给定两条轨迹彳和b ，其中轨迹a _ l 确- n h a ，轨迹b 上有m 个点，仿照 h a u s d o r f f 距离可类推得到它们之间的空间相似距离d 1 1 2 1 定义为： 。( 爿，口) = m 。i n ，j ( 2 4 ) 其中， d 旷署譬旧r a i n ，。( d 。) ( 2 5 ) 础m a x 。一r a i n ，( d 。) ( 2 6 ) 这罩d 。是一条轨迹上的第f 个点到另一条轨迹上的第个点之间的欧氏距离。 b j 见，如果轨迹a 和口越相似，则他们之间的距离就越小，反之则越大。具体 将在第三章详细介绍。 2 3h m m 简介 231 m a r k o v 链 l a r k o v 链是a r k o v 随机过程的特殊情况，即m a r k 。v 链是状态和时间参数 都离散的y l a r k o v 过程，从数学上，可以给出如下定义： 随机序列。，在任一时刻 ，它可以处在状态岛，民，且它在m + 时 堕：生! 些尘兰硕士学何论文第二章k 均值聚娄及 删基本理论 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 = = = = ! = = = = = = = = ! ! ! ! ! ! ! 一 ； 幺所处的状态为+ 。的概率，只与它在聊时刻的状态有关，而与时刻以前 i x m + t 。q w + t x 。2q 。，x 。一t 2q 。一，x 1 = 吼、= p t x 。+ k = q 。d x 。= q 。、 q 一，吼，。( 岛，岛，)( 2 7 ) 则称置，为m a r k o v 链，并且称 p ，( ，+ t ) = p ( + 。= qj = e ) ，i - i ， 为正整数( 2 8 ) 为女步转移概率，当弓( ，+ a ) 与无关时，称这个 j l a r k o v 链为齐次m a r k 。 乞( m ，m + 女) = 只( 女) ( 2 - 9 ) 本文若无特别申明，m a r k o v 链就是指齐次m a r k o v 链。当女：1 时，只( 1 ) 称为步转移概率，简称为转移概率，记为，所有转移概率“。 ( 1 ，n ) 可以构成一个转移概率矩阵，即 爿篙蚓 = i 1 = i ( 2 一1 2 ) 由于女步转移概率0 ( 女) 可由转移概率得到，因此，描述m a c k o v 链的最 重要参数就是转移概率矩阵a 。但a 矩阵还决定不了初始分布，即由a 求不出 吼2 e 的概率，这样，完全描述i a r k o v 链，除a 矩阵之外，还必须引进初始概 率矢量口= ( r r i ，万。) ，其巾 一= p ( q l = 晓) ，1 r ( 2 1 3 ) 显然有 1 1 阳，i t1 业人。丫1 硕士学何论文第二章k 均值聚类及h m m 基本理论 0 蔓厅1 z = 1 ( 2 一1 4 ) ( 2 一1 5 ) 实际中，m a r k o v 链的每一状态可以对应于可观测到的物理事件。比如天气预 测中的雨、晴、雪等，那么，这时它可称之为天气预报的m a r k o v 链模型。根据 该模型，可以算出各种天气( 状态) 在某一时刻出现的概率。 几种典型的m a r k o v 链如图2 1 所示。m a r k o v 链由口、a 描述，显然，不 同的口、a ，决定了不同的m a r k o v 链形状。它们各具特色。图2 一l ( a ) 所示 m a r k o v 链从任一状态出发，在下一时刻可到达任一状态，对应于a 矩阵中的元 索没有零值。图2 1 ( b ) 所示m a r k o v 链则有些不同，比如，从状态j 出发， 卜一时刻不可能到达状态4 ，也就是说，a 矩阵中含有零元素。图2 1 ( c ) 和 2 一l ( d ) 是两种特殊的m a r k o v 链，其特点为：必定从状态l 出发，沿状态序列 号增加的方向转移，最终停在状态d 。 ( a ) a 矩阵没有零值的m a r k o v 链( b ) a 矩阵有零值的m a r k o v 链 即嘏一 咛一们 、c 、：三一：! ! 一备。 一一7 忖寸啪一丫 ( c ) 有跳转左一右形式的m a r k o v 链 ( d ) 无跳转左一右形式的m a r k o v 链 图2 一l各种形式的m a r k o v 链 f ig t l f e21d if f e r e n tk i n d so fm a r k o vc h a i “ 硝el ：业人学硕士学弦论文 第。章k 均值聚类及h 删基本理论 2 3 2h m m 基本概念 h m m 是在m a r k o v 链的基础之上发展起来的。由于实际问题比m a r k o v 链模 型所描述的更为复杂，观察到的事件并不是与状态一一对应，而是通过一组概 率分布相联系，这样的模型就称为h 。它是一个双重随机过程，其中之一是 m a r k o v 链，这是基本随机过程，它描述状态的转移。另一个随机过程描述状态 和观察值之问的统计对应关系。这样站在观察者的角度，只能看到观察值，不 像m a r k o v 链模型中的观察值和状态一一对应，因此，不能直接看到状态，而是 通过一个随机过程去感知状态的存在及其特性。因而称之为“隐”马尔可夫模 型，即h m m 。下面是一个著名的说明h m m 概念的例子一球和缸( b a l la n du r n ) 实验。 如图2 2 所示，假设有n 个缸，每个缸中装有m 种颜色的彩球，球的颜色 由一组概率分布描述如图2 - 2 所示。实验是这样进行的，根据某个初始概率 分布，随机地选择n 个缸中的一个，例如第i 个缸，再根据这个缸中彩色球颜色 的概率分布，随机地选择一个球，记下球的颜色，记为0 1 再把球放回缸中， 又根据拙述缸的转移的概率分相，随机选择下一个缸，例如，第，个缸，再从 缸中随机选一个球，记下球的颜色，汜为d ，等等，一直进行下去。假设得到 了一个描述球的颜色的序列为：q ，q ，0 。由于这是观察到的事件因而 称之为观察值序列。但缸之间的转移以及每次选取的缸被隐藏起来了，并不能 直接观察到。而且，从每个缸中选取球的颜色并不是与缸一一对应的，而是由 该缸中彩球颜色概率分布随机决定的。此外，每次选取哪个缸则由一组转移概 率所决定。 有了前面讨论的m a r k o v 链以及球和缸实验，就可以给出h m m 的定义，或者 晚，个h m m 可以由下列五个参数描述： a ：模型中m a r k o v 链状态数目。记n 个状念为q ，氏，已，时刻 m a r k o v 链所处状态为吼，显然吼( 岛，民) 。在球和缸实验中的缸就相当于 状态。 b m ：每个状态对应的可能的观察值数目。记 个观察值为p ，其中 q ( k ，k ，) 。在球与缸实验中所选彩球的颜色就是观察值。 13 柏北l ：业j 、学硕十学位论文第一二章k 均值聚类及h m m 基本理论 c 厅：初始状态概率矢量，= ( 一，z 。) ，其中 z 。= e ( q ，= 只) ，1 i n 在球与缸实验中指开始时选取某个缸的概率。 d 彳：状态转移概率矩阵，a = ( q ) 。，其中 = p ( 玑+ = qi 吼= 舅) ，l - p ( d l 五) ，即由重估公式得到的模 型川七五在表示观察值序列o 方面要好。 在实际的轨迹模型训练中，特征参数的离散处理一般采用大量的样本进行 矢量量化的方法，最后用得到的量化指数来代替实际的特征参数。在样本数量 不足的情况下，量化处理不仅会导致很大的量化误差，而且会使参数估计结果 的稳健性下降。因此有必要讨论观察矢量取连续值的情形。 如果o 具有连续分布，那么b 不再是一个矩阵，而是一组观察值概率密度 函数：b ； 6 ，( 。) 。最常用的办法是把观察矢量的概率密度函数拟合成若干高 斯函数的线性组合。设0 为待拟合的观察矢量，则输出概率密度函数为： 6 ，( d ) = 兰c 胛n ( 0 ，。，。) ，l ，s ( 2 - 4 4 ) 概率密度函数中参数及其代表的含义描述如表2 - 1 所示。其中c 。满足约 束条件c ，。o ，兰c ，。：1 ，因此p ，( d ) 扣：l 。q ( d ) 决定于c ，。，。，因 此 表2 一l 概率密度函数中参数描述 参数含义 d观察矢量 m每个状态包含的高斯单元个数 c j 。第个状态第m 个混合高斯单元的权系数 n代表正态高斯概率密度函数 棚第j 个状态第m 个混合高斯单元的均值矢量 第j 个状态第m 个混合高斯单元的协方差矩阵 更新t ( d ) 也就是更新这三个参数。概率密度函数中参数的重估”1 公式为式 曲北1 ：业人学硕士学位论文第二章k 均值聚类及h 洲基本理论 ( 2 - 4 6 ) ( 24 8j ，其中一( ，m ) 为某个观察序列在，时刻处于状态的对于第 个混