（计算机科学与技术专业论文）基于关系匹配的并行部件化人体识别.pdf

摘要 人体识别是三维识别的研究热点，如何准确、快速地识别人体是 个非常有意义的研究课题。部件化人体识别被广泛应用于生产过程、 视觉导航、虚拟现实等领域，是一种高效实用的人体识别方案。本文 针对基于关系匹配的并行部件化人体识别方法进行研究，其目的是为 了准确、快速地识别人体。 本文针对部件化人体识别以及人体的关节特征，在深入分析关系 匹配基本原理的基础上，把人体的姿态属性融入到结构误差中，利用 最小结构误差匹配来进行部件化人体识别。同时，提出了人体躯干约 束的剪枝搜索策略并运用于部件化人体的解释树搜索中。人体躯干约 束的剪枝搜索策略能够在复杂场景中解释树规模很庞大的情况下减 少搜索耗时，提高搜索效率。为了提高部件化人体识别效率，本文将 并行搜索树的思想运用于解释树搜索中，研究了并行搜索树的分支 间、节点间以及层间的并行性机制，设计了基于部件集划分的并行搜 索树，形成了并行部件化人体识别，减少了解释树的构造和访问时间， 从而提高了人体识别效率。 本课题还开发了一个完整的部件化人体识别实验平台，将最小结 构误差匹配以及并行搜索树的思想运用于实验平台中，进行了一系列 的仿真实验并将实验结果进行了比较与分析。实验表明，基于关系匹 配的并行部件化人体识别方法能准确、快速地识别出场景中的人体。 关键词人体识别，关系匹配，最小结构误差，躯干约束，并行搜索 树 a bs t i 认c t h u m a nb o d y r e c o g n i t i o n i sa h o t s p o t i n t h r e e d i m e n s i o n a l r e c o g n i t i o n h o wt or e c o g n i z et h eh u m a nb o d ya c c u r a t e l ya n dq u i c k l yi s as i g n if i c a n tp r o b l e m p a r t l e v e lh u m a nb o d yr e c o g n i t i o ni sw i d e l yu s e d i np r o d u c t i o np r o c e s s ，v i s u a ln a v i g a t i o na n dv i r t u a lr e a l i t ya n ds oo n i t s a p r a c t i c a la n de f f i c i e n ts c h e m eo fh u m a nb o d yr e c o g n i t i o n i nt h i sp a p e r w ec a r r i e do nr e s e a r c h e sf o rt h em e t h o do fp a r a l l e l p a r t l e v e lh u m a n b o d yr e c o g n i t i o nb a s e do nr e l a t i o n a lm a t c h i n g a n da l lo fo u re f f o r t sa r e t or e c o g n i z et h eh u m a nb o d ya c c u r a t e l ya n dq u i c k l y a i m i n ga tp a r t l e v e lh u m a nb o d yr e c o g n i t i o na n dt h ec h a r a c t e r i s t i c s o fh u m a nj o i n t ，t h i sp a p e rd e e p l ya n a l y z e dt h ep r i n c i p l eo fr e l a t i o n a l m a t c h i n ga n dc o m b i n e ds t r u c t u r a le r r o r sw i t ht h eg e s t u r eo fh u m a ns oa s t or e c o g n i z et h ep a r t l e v e lh u m a nb o d y b yu s i n gm i n i m a ls t r u c t u r a le r r o r s m a t c h i n g a tt h es a m et i m e ，ah u m a nt r u n kr e s t r i c t i o ns t r a t e g yw a s p r o p o s e d ，w h i c hi su s e di ni n t e r p r e t a t i o nt r e es e a r c hi np a r t 1 e v e lh u m a n b o d yr e c o g n i t i o n w h e nt h es c e n ei sv e r yc o m p l e x ，t h es c a l eo f i n t e r p r e t a t i o nt r e ew i l lb ev e r yl a r g ea n dt h i ss t r a t e g yc a nr e d u c et h et i m e s p e n ti ns e a r c ha n di m p r o v et h es e a r c he f f i c i e n c y i no r d e rt oi m p r o v et h e e f f i c i e n c yo fh u m a nb o d yr e c o g n i t i o n ，w eu s e dt h ei d e ao fp a r a l l e ls e a r c h t r e ei nt h ei n t e r p r e t a t i o nt r e es e a r c h ，a n da n a l y z e dt h ep a r a l l e l i s ma m o n g b r a n c h e s ，n o d e sa n dl a y e r s ，a n dd e s i g n e dp a r a l l e ls e a r c ht r e eb a s e do n p a r ts e td i v i s i o n t h em e t h o do fp a r a l l e lr e c o g n i t i o no fh u m a nb o d yw a s b u i l t ，w h i c hc a nr e d u c et h et i m es p e n ti nc o n s t r u c t i n ga n da c c e s s i n g i n t e r p r e t a t i o nt r e e s ot h i sm e t h o dp r o m p t e dt h ee f f i c i e n c yo fh u m a n b o d yr e c o g n i t i o n i na d d i t i o n ，w ee x p l o i t e dac o m p l e t ee x p e r i m e n t a lp l a t f o r mu s e df o r c a r r y i n go u te x p e r i m e n t so fp a n l e v e lh u m a nb o d yr e c o g n i t i o n w eu s e d t h ep r i n c i p l eo fm i n i m a ls t r u c t u r a le r r o r s m a t c h i n ga n dp a r a l l e ls e a r c h t r e ei n t ot h ed e s i g no ft h ep l a t f o r m ，a n de x e c u t e das e r i e so fs i m u l a t i o n e x p e r i m e n t s ，t h er e s u l t so fw h i c hw e r ea n a l y z e da n dc o m p a r e d t h o s e e x p e r i m e n t ss h o w e db e a e ra c c u r a c ya n de f f i c i e n c yi nr e c o g n i t i o no f u p a r t - l e v e lh u m a nb o d y k e yw o r d sh u m a nb o d yr e c o g n i t i o n ，r e l a t i o n a lm a t c h i n g ，m i n i m a l s t r u c t u r a le r r o r s ，h u m a nt r u n kr e s t r i c t i o n ，p a r a l l e ls e a r c ht r e e l i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单 位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均 已在论文中作了明确的说明。 作者签名：l 套淬日期：j 垃手- 年月丑日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其 它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到 中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：4 蝌导师签名丝日期：珥年上月皿日 硕士学位论文 第一章绪论 第一章绪论 出于工业和医疗等领域大量现实应用的需要，如今三维物体识别己成为一个 非常活跃的研究领域，三维物体识别广泛应用于计算机视觉导航。、机器人避 障u 。、自动装配等视觉识别系统中，如人脸识别h 1 、目标跟踪川等。 三维物体识别通常包括两个阶段的处理，首先获得场景物体的数据，然后将 场景物体与数据库中存储的目标物体相匹配。具体来说，三维物体识别系统必须 解决如下几个问题旧。：1 获取场景物体的原始数据。2 三维物体模型构建方法。 3 怎样描述原始数据和物体模型。4 场景物体跟目标物体之间的匹配方法。由 于匹配策略是在识别系统运行时执行的，因此它必须解决数据和模型描述之间的 二义性。一旦正确的匹配己确定，则根据物体模型即可将己定位物体的方向和变 换计算出来，最终完成物体识别的任务。 在基于部件的三维物体识别系统中，一个物体被分割成若干基元部件u 1 ，这 些基元本身不能提供描述整个物体形状的特征属性，它们按一定的相关性组合起 来描述整个物体的形状，这种相关性成为了基于部件的视觉系统中识别目标的重 要依据。部件识别的匹配策略主要有功能模型匹配和关系模型匹配旧。功能模型 匹配是一种基于知识相关的匹配策略，功能模型匹配必需预先定义与知识基元有 关的功能属性，不适用于未知环境。关系模型匹配是一种基元间拓扑结构关系特 征匹配策略，将识别看成从模型结构中识别与目标物体一致的关系结构特征，它 不仅适应于用基元部件来描述物体和工作场景的目标识别，同时还具备可以对物 体动态结构识别的能力”。 部件化人体识别是三维物体识别的一种特殊应用，可以使用于安全监控、虚 拟现实、人机交互等许多领域。基于关系匹配的部件化人体识别的过程也分 为两个阶段：首先，用超二次曲面作为基元部件对通过深度传感器采集到的工作 场景三维云点数据场进行建模与分割，得到场景部件关系模型。：然后，将场 景部件关系模型与目标人体关系模型进行关系匹配，从而达到人体识别的目的。 本文在关系匹配与部件化物体识别技术的基础上采用了“基于关系匹配的部 件化人体识别”方法，分析与探索了部件化人体识别，具有一定的实际意义。 1 1 三维物体识别技术研究与应用 三维物体识别一直是计算机视觉领域最热门的研究方向之一，它是以物体表 面朝向的三维信息来识别完整的三维物体模型。三维物体识别技术发展非常迅 硕士学位论文 第一章绪论 速，相关的三维物体识别方法种类繁多，应用的领域也十分广泛。在具体的应用 中，如何根据应用的需要以及原始数据与信息的情况选择一种合适的三维识别方 法是十分重要的。 1 1 1 三维物体识别技术发展历程 总的来说，三维物体识别方法主要有以下几种：基于模型的物体识别u 纠( 广 义柱法、图结构法、曲面法等) 、基于特征矢量表示的物体识别u 副( 统计识别 法、神经网络法等) 和基于知识的物体识别1 ( 模糊数学法、模糊神经网络法) 等。 具体来说，三维物体识别方法主要方法有：假设验证法、解释树、基于图的 识别方法、霍夫姿态聚类、几何哈希表、迭代模型拟合技术以及基于神经网络的 匹配方法。这些识别方法的不同之处不仅在于使用不同的物体表达方法，而且也 在于如何完成场景特征和模型特征之间的匹配、如何从场景模型特征匹配中得到 一致性分配和如何一致性分配中得到姿态估计。在一个系统中通常会联合使用多 种匹配方法。 1 假设验证法 将假设的物体模型特征和部分场景特征联合起来得到一个非线性方程，然后 通过解此非线性方程，以得到平均误差最小的解，并将这个解作为从物体参考坐 标系到场景参考坐标系的变换。验证的过程是将假设模型的特征映射到场景中， 再利用原始的场景图像来检查这些映射后的特征是否正确，从而确定假设的正确 性。1 。假设验证法面临的问题有两个：其一是在场景复杂的情况下，由于生成 的假设很多，因而验证计算的花费会很大；另一个是数据中存在的噪声误差 会传播给姿态估计，会降低验证阶段的准确性。1 9 9 9 年，f r e d e r i cj u d e 提出 了一种快速、鲁棒的假设验证法，但是计算过程复杂很费时“。现在这种假设 验证法常与其它匹配方法相结合来完成识别工作，如王新华曾使用假设验证法与 特征关系图相结合来进行三维物体识别。 2 解释树法 解释树中的节点常用于表示目标部件和场景部件间可能的匹配，解释树的根 节点到叶节点的每条通路都表示相关问题的一个可能解。这种方法主要是为了找 到目标部件和场景部件间的一致性分配。构造解释树时可以利用剪枝策略来减少 解释树的规模。利用递归回溯方法很容易设计出解释树。g r i m s o n 很好地研究并 公式化了解释树的方法，他在假设了一些条件后，得到的解释树搜索复杂度为o ( n 2 ) 引，这种复杂度只是针对单物体场景而言，当场景中具有多个物体时，复杂 度会呈指数上升。j a k ak r i v i c 运用解释树实现了物体的识别与跟踪。 3 基于图的识别方法 2 硕士学位论文 第一章绪论 特征关系图中的节点对应于场景和模型中的主要特征，而节点之间的弧则表 示两个特征之间的关系。这里，场景和模型物体都用a r g 图来描述，且它们之 间的匹配均使用图论的匹配技术。k a o 等使用超级关系图( s u p e rr e l a t i o n a lg r a p h ， s r g ) 来识别边界表达的三维物体“，且s r g 是一种无向图，图中的节点代表 一个面，其节点之间有两种连接，分别对应它们定义的两种面与面之间的关系， 这种基于图的识别方法的主要困难在于难以处理物体遮挡问题和图匹配的大运 算量问题。 4 霍夫姿态聚类 该方法也称作广义霍夫变换，它是根据局部几何约束( 例如角度和距离度量) 来减少不正确的匹配，即先从每一个成功的匹配计算出一个几何变换，然后将其 存储成霍夫空间( 变换参数空间) 的一个点并进行累加“。在霍夫空间中最大的 聚类点就确定了场景中物体姿态的一致假设。g r i m s o n 和h u t t e n l o c h e r 曾分析了 霍夫聚类的敏感性瞄，他们认为在霍夫累加器中最大误差与场景中物体的杂乱 程度无关，且参数空间中误差极大值出现的概率依赖于传感器噪声、遮挡和量化 效果。 5 几何哈希表 也称索引表( i n d e x i n g ) 法，这种方法是将搜索空间设定为由待匹配特征作为 索引值组成的查找表，该表中还包含对应物体模型的索引值，这样确定特征相关 和数据库搜索过程则转变成表查找的过程。不同几何哈希表法的区别在于表中索 引值类型和表的排列方法的不同。f l y n n 和j a i n 将表面与表面间的约束关系作为 索引键值1 1 ，而y i 和c h e l b e r g 则使用局部表面组作为索引值。1 。 6 迭代模型拟合技术 这类方法的一个明显特征是在计算上的迭代过程。当三维物体用参数进行表 达描述，并在该参数既能确定形状也能确定物体姿态的情况下，可以使用迭代模 型拟合的方法。此时，物体识别和姿态估计可简化成估算图像数据中的模型( 姿 态) 参数，且可与存储的模型参数表达相匹配，即通过迭代的方法解一个非线性 方程并选择与场景有最小平方和误差的解作为估计参数m 。如b e s l 提出了最邻 近点匹配算法，其目的是为了找到两幅深度图之间的变换关系m “，通过迭代的 方法找到平均平方误差最小的变换。该法也称作i c p 算法( i t e r a t i v ec l o s e s t p o i n t ) ，后来该法广泛地应用到3 d 物体识别中怕。 7 基于神经网络的匹配方法 神经网络有很好的分类能力和并行处理能力，与传统的方法相比，基于神经 网络的识别方法具有能并行运算、处理速度高和鲁棒性好等优点。有些研究人员 将其运用到3 d 物体识别中。如c h e n 和l i n 曾使用个单层h o p f i e l d 网络来识 硕士学位论文第一章绪论 别c s g 法表达的3 d 物体，但该系统只能识别表面为平面的物体和单物体； 又如z h a 等同样也使用单层h o p f i e l d 网络完成识别工作，他的方法是将物体 模型表示成基于表面片的描述并定义了能量函数，其最小化时的网络节点状态即 为识别结果。 1 1 2 三维物体识别的应用领域 三维物体识别可以广泛应用于工业和医疗等领域： 1 人脸识别 人脸识别研究可以追溯到2 0 世纪初，经过研究人员的不懈努力，基于图像 的二维人脸识别技术日趋成熟，在一定约束条件下已取得较好的识别结果卜”。 然而，研究实验表明，光照、姿态、化妆、表情、年龄等变化显著地降低了二维 人脸识别算法的性能卜”1 。近年来，学术界开始探索如何利用人脸的三维信息提 高系统的识别性能，如美国f b i 、n i s t 等多个部门联合资助发起的“人脸识别 大挑战计划”k 。1 。 一般而言，三维人脸识别是指将采集获得的待识别对象的脸部三维形状数据 作为识别依据，与库中已知身份的脸部三维形状数据进行匹配，然后得出待识别 对象身份的过程。三维人脸识别是相对基于图像( 及视频) 的人脸识别而言的，而 后者所使用的数据是二维的图像，其本质是三维物体在二维平面上的投影，是三 维信息在二维空间中的简约。 2 机器人导航 机器人导航是计算机视觉中的一个重要研究领域，它一般通过摄像机捕获图 像，然后对图像进行数字图像处理并提取数据信息，接下来将获得的数据信息与 数据库中的数据匹配，匹配成功后再计算物体的位置。如，美国n a s a j p l 开发 的r o c k y 7 火星探测移动机器人卜”。，在其后部、前部及桅杆上都安装了一对黑自 c c d 摄像机，另外，在桅杆上还安装了一个用于近距离成像的摄像机。借助于 这些视觉系统，r o c k y 7 可以进行障碍检测、自身车辆检查、挖掘倾倒核查等任 务。 3 指纹识别 随着社会的不断发展，科技的不断进步，传统的保护措施在现代的科技面前 存在很大的隐患，因而需要更高效更可靠的身份识别技术。指纹识别作为生物识 别技术中的一种，克服了可盗用、可假冒、可破解的弱点，具有唯一性和不可复 制性。指纹识别优于其他的生物识别技术，因为它历史悠久，发展得较为完善， 并且成本较其它识别技术来说相对较低。 另外，三维物体识别还可以应用于机器人工件抓取任务、自动检测、装配任 务以及医学图像分析，如，可以对医学显微图像进行处理和分析，能有效地协助 4 硕士学位论文第一章绪论 诊断诸如癌症和肿瘤等多种病症3 刨。 1 2 部件化人体识别方法研究与应用 人体识别具有很高的实用价值，因而一直是研究热点。部件化人体识别技术 属于三维识别的研究范畴，它是将人体看成是由若干个部件组成，然后运用三维 物体识别的技术来进行部件化人体识别。 1 2 1 部件化人体识别的常用方法 人体识别的方法很多，王芹、王然冉等提出了“关于人体部位识别的一种模 糊算法”，这种算法利用了“星形骨架法”，通过检测运动对象的外部边界来产生 一个星形的骨架卜”。并采用a p a r ( a n t ip a r a l l e ll i n e ) 来描述构成人体区域的子区域， a p a r 定义为一个细长的区域，人体可以由多个a p a r 区域组成，通过对人体区域 的轮廓特征分析，人体的a p a r 之间通常由轮廓线上的特征拐点分隔，且每个a p a r 由连接特征拐点间的线段围成，通过求特征拐点确定a p a r 区域。通过逐步识别 人体的各个部位来进行人体识别。曹丹华等在a n t o n i om i c i l o t t a 算法的基础上提 出了一种“c o a r s e a c c u r a t e ”双步头部提取算法。，该算法主要是为了精确定位 头部的位置，当人体完成转身等工作头部偏离躯干中线时，依然可以准确定位头 部。而对于人体肢体的提取则采用最小负曲率点n c m ( n e g a t i v ec u r v a t u r em i n i m a ) 搜索法，该算法采用一种球棒模型，将人体划分为l3 个关节和1 1 个肢体部分， 其中1 3 个关节包括：头部、两个肩部、两个肘关节、双手、两个胯关节、两个 膝盖关节以及双脚；11 个肢体包括：躯干、肩膀、前臂、上臂、胯部、大腿和 小腿。 j a k ak r i v i c 等提出了一种部件化物体识别的方法卜”1 ，将一个三维物体看成是 由多个部件组成，这些部件都是采用超二次曲面描述，通过调整超二次曲面的形 状参数与尺寸参数就可以比较精确的描述三维物体的部件。他们利用解释树搜索 策略来寻找目标物体关系模型到场景关系模型的最佳映射，同时还提出了识别的 过程中利用超二次曲面的特征属性约束来进行解释树的剪枝。为了验证这种方法 的有效性，他将部件化物体识别的方法运用于人体识别中，成功的识别出了场景 中的人体，从而证实了这种方法的有效性。 本文采用的基于关系匹配的部件化人体识别参考了j a k ak r i v i c 的方法，并在 他的方法之上进行了改进与完善，同时还将并行算法的思想融合到了部件化人体 识别过程中。 硕士学位论文第一章绪论 1 2 2 部件化人体识别的应用领域 部件化人体识别的应用领域非常广泛，涉及的领域如下： 1 智能监控 在银行、海关、超市、码头等重要场所，监视这些场所中人的活动，对其行 为进行分析，跟踪可疑行为，采取相应的报警措施，比如在十字路口监控来往的 人群与车辆h 。此外，当人员受困时可以用机器人去寻找受困人员并进行营救。 如，有人员被困在非常危险的地方，救援人员进入会有生命危险，这时可以用能 识别出人体的机器人进行营救。 2 虚拟现实 虚拟现实技术是以计算机技术为平台，利用虚拟现实硬件、软件资源，实现 一种极其复杂的人与计算机之间的交互和沟通过程。利用虚拟现实技术为人类创 建一个虚拟空间，并向参与者提供视觉、听觉、触觉、嗅觉、导航漫游等身临其 境的感受，使参与者能够与虚拟现实环境中的三维实体进行交互和感知，亲身体 验在虚拟现实世界遨游的神秘、浩瀚感受。虚拟现实技术以传统计算机为依托， 以虚拟现实软件为基础，构造出大众化的虚拟现实三维立体场景，实现了虚拟现 实硬件零投入，即只需投入软件产品，同样可以达到虚拟现实的动态交互效果。 可以利用虚拟现实跟踪现实世界人的姿态，从而创建一个虚拟的场景，实现 人与这个虚拟世界的交互，虚拟现实的应用涉及视频游戏、虚拟摄影棚、角色动 画、远程会议等等。 3 人机交互 人机交互是研究人和计算机以及它们二者之间的相互影响的领域。人机交互 功能主要靠输入输出设备和相应的软件来完成。人机交互部分的主要作用是控制 人机交互设备的运行以及理解并执行通过人机交互设备传来的命令和要求。早期 的人机交互设备是键盘和显示器，操作员通过键盘打入命令，操作系统接到命令 后立即执行并将结果通过显示器显示出来。随着计算机技术和模式识别的发展， 如语音识别、汉字识别等输入设备的发展，操作员和计算机在类似于自然语言或 受限制的自然语言这一级上进行交互成为可能。此外，通过图形进行人机交互也 吸引着人们去进行研究。这样，在人机交互领域，可以通过对用户手势的识别来 代替传统的鼠标和键盘，实现人机之间的智能交互，可以通过人脸的表情来判断 人的情绪。 4 运动分析 用于各种体育项目中，分析运动员的各项技术参数，以提高运动员的训练水 平，也可以用于体育舞蹈动作的分析，体育比赛的自动裁判，以及临床矫形术的 研究。 6 硕士学位论文第一章绪论 1 3 课题来源及研究意义 本课题来源于湖南省科技计划项目( 2 0 0 7 f j 3 0 6 9 ) “面向深度图像的三维建 模与识别软件平台研制”，是这个项目的重要组成部分，主要研究三维物体识别 技术。“面向深度图像的三维建模与识别软件平台研制”由三维建模和三维识别 两部分组成。首先由传感器获得三维物体数据，然后对这些数据进行三维建模， 采用超二次曲面进行三维建模，建模后再进行三维识别。部件化人体识别属于三 维识别的研究范畴。 部件化人体识别可以使用于安全监控、虚拟现实、人机交互等许多领域，为 了准确、快速的识别人体，我们采用了一个基于关系匹配的部件化人体识别方案。 在这个方案中，人体被看成是由一系列的部件组成，各部件之间由关节相连，具 有确定的连接关系。部件化人体识别利用超二次曲面作为部件对场景和人体进行 分割。，再利用部件关系模型的匹配策略从场景中识别出人体部件。关系模型匹 配是种基于拓扑结构关系特征的匹配策略，它利用部件之间的关系来寻找场景 部件集跟目标部件集之间的最佳映射，可以用来对人体的动态结构进行识别。要 提高识别准确率的关键在于如何找到一种最佳匹配，这就要求当存在多种可能匹 配时能够对这些匹配的优劣进行度量，从中筛选出最好的匹配。由于人体关节多、 自由度大，是典型的关节性物体，因此我们将整个人体看成是一个关节性物体来 进行识别。本文将人体躯干所特有的多关系特性与解释树搜索相结合，从场景关 系模型中找出与目标人体关系模型具有最小结构误差的关系匹配，同时采用角度 约束来识别人体关节，通过改进和优化关系匹配，达到了对人体进行准确识别的 目的。 一系列的仿真实验证明了基于关系匹配的部件化人体识别的实用价值，在部 件化人体识别的基础之上本文还继续研究了并行部件化人体识别，将并行算法的 思想与部件化人体识别相结合，提高了人体识别的效率。基于关系匹配的部件化 人体识别能够有效的识别场景中的人体，具有很重要的研究意义。 1 4 本文的主要工作 本文首先分析了国内外三维物体识别技术的研究现状，根据各种三维物体识 别技术的适用范围再结合部件化人体识别的特点，选择了关系匹配作为部件化人 体识别的匹配策略。关系匹配中最常见的方法是一致性分配，这种一致性分配的 前提是场景模型和目标模型之间不存在关系误差，是一种近乎完美的匹配。但在 实际应用中，场景模型和目标模型之间的误差是不可避免的，因此一致性分配的 实用价值有限。本文在一致性分配的基础上进行了改进，采用最小结构误差匹配 7 硕士学位论文第一章绪论 来进行部件化人体识别。结构误差是衡量匹配优劣的标准，考虑到模型之间不但 存在关系数的差别，而且部件之间的夹角也存在差异，因此，本文将结构误差分 为关系误差与角度误差两部分，并详细阐述了关系误差与角度误差的计算方法， 然后设计了人体结构误差的计算公式。最后通过3 组实验，证明了人体结构误差 的有效性，同时也说明了基于关系匹配的部件化人体识别的可行性。 考虑到当场景很复杂时，识别的进度比较缓慢，本文认真调研了并行算法 的思想，重点分析了并行搜索树算法的3 种并行机制，将并行搜索树算法运用于 部件化人体识别并提出了基于部件集划分的并行搜索树。在基于部件集划分的并 行搜索树中充分利用了分支问的并行、层间的并行以及节点间的并行，根据并行 算法的思想将目标人体部件集划分为若干个子集，进而将一棵并行搜索树分解成 若干个部分，这些部分之间可以并行构造与遍历，这样就可以实现并行部件化人 体识别。本文将基于部件集划分的并行搜索树运用于部件化人体识别，通过3 组实验，比较分析了采用并行搜索树与不采用并行搜索树时的时间，从而说明了 并行搜索树的实际意义。 最后，针对本文提出的算法的不足，提出了下一步的工作以及改进思想。 1 5 本文的内容组织安排 本文在对国内外三维物体识别技术做了充分调研的基础上选择采用基于关 系匹配的部件化人体识别，全面深入地讨论了关系匹配的理论原理，并将关系匹 配应用于部件化人体识别过程中，成功的识别出了场景中的人体。同时，为了提 高识别的效率，本文又将并行算法的相关思想应用于部件化人体识别，形成了并 行部件化人体识别。全文共包括六个章节。 第一章绪论，主要内容包括课题的研究背景与目标、研究意义及目的，重点 讨论了国内外三维物体识别技术的现状以及应用领域、部件化人体识别的常用方 法。 第二章部件化物体识别，这是本文的核心基础理论。首先介绍了物体部件化 描述的几种方式，重点讲解了超二次曲面。接着介绍了部件化物体识别的基本方 法，主要是关系模型匹配以及功能模型匹配。最后介绍了关系匹配的基本原理、 一致性分配的基本原理以及解释树的基本原理，在介绍解释树时提及到了解释树 的多种剪枝策略，这些剪枝策略是用来对解释树进行剪枝，减小解释树的规模， 提高解释树搜索效率。 第三章最小结构误差部件化人体识别，介绍了部件化人体识别方案以及最小 结构误差匹配策略，阐述了人体关系匹配中的关系误差与角度误差，设计了人体 结构误差的计算方法。为了提高识别的效率，此章提出了人体躯干约束，将人体 8 硕士学位论文第一章绪论 躯干约束运用于解释树的剪枝策略中。最后，详细说明了匹配算法的设计与实现， 并通过3 组实验来证明最小结构误差部件化人体识别的有效性。 第四章并行部件化人体识别，将并行算法的思想运用于部件化人体识别中， 首先分析了并行算法的基本原理、并行搜索树的基本原理，在并行算法和并行搜 索树的基础上提出了基于部件集划分的并行搜索树，接下来结合部件化人体识别 的特点详细阐述了人体部件集的划分、基于部件集划分的并行搜索树的构造过程 以及算法设计，最后将基于部件集划分的并行搜索树应用于部件化人体识别，并 通过3 组实验比较了并行算法与串行的效率。 第五章实验平台介绍，简要介绍了实验平台的5 个最重要的模块：数据导入 模块、表的类别划分模块、场景展示模块以及人体识别模块，对于每个模块的介 绍都配有相应的示意图。 第六章结束语，对论文的研究工作进行了总结，同时也提出了下一步的研究 工作，并且对部件化人体识别进行了展望，提出了部件化人体识别无论在过去还 是将来都具有非常重要的研究意义。 9 硕士学位论文第二章部件化物体识别 第二章部件化物体识别 无论是计算机视觉还是计算机图形学都要用到3 d 目标的模型，在计算机图 形学中，目标必须用便于绘制和显示的结构表示出来。最常见的结构是3 d 网格 结构，它是由3 d 点和连接这些点的边构成的多边形集合。对于计算机视觉来说， 目标表示必须符合目标识别的要求，这就意味着目标表示和从图像中抽取的特征 之间必须有一定的对应关系。计算机视觉中，最简单的是线框模型，这种模型在 今天仍然很流行。但也有其他一些模型能更精确的表示曲面甚至任意表面的目标 数据。将物体用3 d 模型描述出来后，就可以采用部件化物体识别策略来进行部 件化物体识别。 在本章中我们将重点介绍用于物体部件化描述的超二次曲面以及广义圆柱 体，功能模型匹配和关系模型匹配这2 种匹配策略。 2 1 物体部件化描述 在本节中我们将会分析物体部件化描述最常用的两种方式：超二次曲面以及 广义圆柱体。通过对比不难发现，所有的超二次曲面具有统一的表达式，改变尺 寸参数就可以调节超二次曲面的大小，改变形状参数就可以调节超二次曲面的形 状，所以只需改变超二次曲面的形状参数与尺寸参数就可以用来描述不同的三维 模型，也就是说超二次曲面最关键的信息是形状参数与尺寸参数，即 卧口，、a 3 、参、己这5 个参数，因此保存一个超二次曲面时只需保存这5 个参数 即可，数据量非常小。使用超二次曲面最主要的好处是可以使用相同的基元对模 型数据与测量数据进行描述，超二次曲面可以模拟大约8 5 的人造目标“。用 超二次曲面描述部件时，我们只需用5 个参数就可以将一个部件描述出来，数据 量小节省了存储空间。如果用广义圆柱体描述，不同的形状有不同的方程表达式， 这样就给处理带来了麻烦，并且数据的存储也会浪费很多的空间，因此本文选用 了超二次曲面来描述人体部件。 2 1 1 超二次曲面部件化描述 超二次曲面模型最初是用在计算机图形学方面，后来经p e n t l a n d 引入到计算 机视觉领域。超二次曲面能够通过变形形成目标模型。数学上，超二次曲面构成 形状的参数化族。一个超二次曲面可以被定义成如下三维矢量形式4 1 i ： l o 硕士学位论文 第二章部件化物体识别 ( 2 1 ) 参数a l ，幻、分别为超二次曲面在x 、y 、z 坐标轴的缩放比例，是超二次 曲面的尺寸参数；亡，、毒? 用来控制超二次曲面的形状，是形状参数。 将表达式( 2 一1 ) 经过变换之后可以得到超二次曲面的方程n ： 胁谢卜 通过调整超二次曲面的尺寸参数与形状参数，我们可以得到一系列不同的超 二次曲面。图2 - 1 是通过改变尺寸参数，图2 - 2 是改变形状参数。 固固固修 图2 - 1 改变尺寸参数的超二次曲面 向十 超二次曲面的体积计算公式如下3 9 1 ： y 地隅呜点钗粤加l 坝争，华) ( 2 2 ) b ( ) ：掣 ( 2 - 3 ) 丫( 冬) 氧+ 1 ) 丫( 冬) 姒华) 矿= 2 以l 口2 口3 缶受母蒜2 1 + , x 幸糟 丫( 1 ，i + 1 )丫( 詈+ 等# ) = 2 a 2 口3 缶乞 丫( 每m ( 卣+ 1 ) 丫( 冬m ( 华) 二 木 二二 丫( 主川) “1 鹄 p 函数的求值在m a t l a b 中很容易实现，它对应于m a t l a b 中的g a m m a 函数， 缈 缈 0 功们咖 f f 副 耐耐甜 口 口 口 = x y z 硕士学位论文 第二章部件化物体识别 这样用m a t l a b 求超二次曲面的体积可以通过如下代码实现： v = 2 母口1 宰a 2 a 3 卡卣宰磊 g a n a m a ( 每- ) * g a t o m a ( 卣+ 1 ) g a r o m a ( - 鲁- ) * g a m m a ( 华) - 书 兰l一 g a ( 1 ) g 一缸1 + 劲 从上式可以看出，超二次曲面的体积只与a 。、a 2 、a 3 、异参这5 个参数有 关。 在绘制超二次曲面时，除了a i 、a 2 、a 3 、异岛这5 个参数，还应该加入平移 与旋转参数，平移参数用来将原始的超二次曲面沿x 、y 、z 轴方向平移一定的 距离；而旋转参数是将原始的超二次曲面绕x 、y 、z 轴旋转一定的角度。 2 1 2 广义圆柱体部件化描述 广义圆柱体是一种体积基元，用一条空间曲线轴和轴上各点处的截面函数进 行定义。截面沿轴向密排形成旋转体。例如，一般圆柱体是广义圆柱体，它的轴 是直线段，截面是半径恒定的圆；圆锥体是广义圆柱体，它的轴是直线段，截面 是圆，其半径从轴的一个端点从o 开始增长，在另一端点达到最大值；长方体是 个广义圆柱体，它的轴是直线段，截面是相同的矩形；圆环体是广义圆柱体，它 的轴是圆，截面是相同的圆“1 。 一个物体的广义圆柱体模型，包括广义圆柱体描述、广义圆柱体间的空间关 系以及物体的全局特性。圆柱体可以用轴长度、平均截面宽度、两底面之比以及 锥角进行描述。连接关系最常见的空间关系。除了端点连接关系外，圆柱体之间 也可能连在一起，使得一个圆柱体的端点成为另一个圆柱体的内部点。在这种情 况下，可以用连接参数来描述这种连接关系，如圆柱体相接触的位置、倾角以及 描述一个绕另一个旋转的环绕角。目标的全局特性可能包括圆柱体块数、细长圆 柱体块数和连接对称性。也可以用分层的广义圆柱体模型，其中在不同层次上表 示不同细节的模型。例如，可把人体粗略建模为棒状图，由表示头部、躯干、手 臂和腿部的圆柱体组成。在下一层，躯干可能分为脖子和躯干部分；手臂可能分 为3 个圆柱体，分别表示上臂、前臂和手：腿也类似。再下一层，手可以分为手 掌和五指，继续分化，手指可以分为三节，当然拇指是两节。 三维广义圆柱体投影到图像中会产生两种不同的二维效果，即条带和椭圆。 条带是广义圆柱体的投影，椭圆是广义圆柱体的端面的投影1 4 列。当然端面不一 定是圆，所以投影也不一定是椭圆。某些广义圆柱体是完全对称的，所以没有长 短之分。对于这种情况，现有算法能够从建模目标的图像中寻找条带。 1 2 硕士学位论文第二章部件化物体识别 2 2 部件化物体识别基本方法分析 讨论了部件化物体描述方式之后，这一节主要分析部件化物体识别的两种常 用方法。在识别的过程中究竟选用哪种识别方法应该根据不同的实际情况以及识 别的目的来决定。识别目标的目的可能是为了检查、抓取或避让。对于检查，至 少要查看目标的部分细节，模型和测量精度必须足够高。抓取物体则有不同的要 求，抓取任务不仅需要粗略的模型几何知识，还要考虑平衡、力度以及目标在工 作空间中的可接近性。对于路径上的障碍物，机器人识别的目的是为了避让，这 时只需要识别出目标大致的尺寸、形状和位置即可。 本节主要分析了功能模型匹配和关系模型匹配这2 种部件化物体识别策略。 功能模型匹配是一种基于知识相关的匹配策略，功能模型匹配必需预先定义与知 识基元有关的功能属性，不适用于未知环境。关系模型匹配是一种基元间拓扑结 构关系特征匹配策略，将识别看成从模型结构中识别与目标物体一致的关系结构 特征，它不仅适应于用基元部件来描述物体和工作场景的目标识别，同时还具备 可以对物体动态结构识别的能力。 2 2 1 关系模型 三维目标识别可利用关系模型。三维关系模型由3 d 基元和空间关系组成， 基元可以是体积( 如几何体、超二次曲面、广义圆柱体等) 、表面( 如平面、圆 柱面等) 和具有某种特征空间直线或曲线：空间关系可以是基元体积的连接关系、 表面间邻接关系、直线或曲线间的平行或共线关系等h 。这样3 d 目标识别就可 以利用关系模型来进行。 一个物体的关系模型可以描述为d = ( p ，r ) ，p = ( p ，n ) 为基元部件集， r = ( ，) 为尸上的关系集，关系描述定义了物体的拓扑特性，它通常作为物 体识别系统的基础部分。 经过建模与分割后所得到的超二次曲面场景可以表达成一个关系模型，因而 可以通过关系匹配来对图像进行理解。图2 - 3 是一个人体，这个人体可以表达成 一个关系模型，其中： p = ( p l ，p 2 ，p 3 ，p 4 ，p 5 ，p 6 ，p 7 ，p s ，p 9 ，p l o ) 、 r = ( p 1 p 2 ) ，( p 2 ，p 7 ) ，( p 2 ，风) ，( p 2 ，见) ，( p 2 ，胁) ， ( p 7 ，岛) ，( 风，p l o ) ，( p 3 ，p 5 ) ，( p 4 ，风) p 是人体的部件集，图2 - 3 把人体划分为1 0 个部件：p ，为头部，刃为躯干， p 7 与p s 为胳膊、p 9 与p ，d 为手臂，p 3 与p 4 为大腿，p 5 与肌为小腿a 尺为人体各 部件之间的关系集，头部与躯干之间、躯干与胳膊之间、躯干与大腿之间、胳膊 硕士学位论文第二章部件化物体识别 与手臂之间、大腿与小腿之间都存在关系。 p l o 图2 3 关系模型示例图 关系模型匹配采用相关距离匹配技术_ ”“，用相关距离匹配技术来计算两个 关系模型的相似程度。 在关系模型匹配中还可以使用相关索引。将未知图像与可能很大的目标视 图数据库进行匹配，生成关于哪些目标存在于图像中的一组假设，提高匹配效率。 2 2 2 功能模型 基于功能的目标识别方法视图通过目标的功能来定义目标的类别，例如，一 把椅子是某种东西，人可以坐在上面，椅子可能有很多不同的关系结构，只要满 足一组功能约束，那么它就是椅子。 基于功能模型的目标识别，首先由s t a r k 和b o w y e r 在他们的g r u f f ( g e n e r i c o b j e c tr e c o g n i t i o nu s i n gf o r ma n df u n c t i o n ) 系统中使用”。，g r u f f 包含三级知 识： 1 所有目标的类别层次都在知识库中。 2 根据功能属性对类别进行定义。 3 知识基元是功能定义的基础。 知识基元是一个参数化过程，它实现了几何、物理学或因果关系的基本概念。 知识基元把3 d 形状描述的一部分作为输入，返回一个值，该值表示基元在多大 程度上满足某种需求。功能目标类别的定义规定了它必须有的与知识基元有关的 功能属性。例如椅子必须为坐在其上的人提供稳定的支持和可坐的表面。汤碗必 须为