（信号与信息处理专业论文）三维人脸识别中三维数据对应关系的研究.pdf

摘要 摘要 基于生物特征的认证技术近年来发展迅速，计算机人脸识别技术 是其中最为活跃最具有挑战性的领域之一一。通常采用的人脸识别技术 都是针对人脸二维图像的，随着三维数据的获取技术的发展，有很多 研究者已经开始尝试利用三维深度图像，进行三维人脸识别的研究。 而三维人脸识别的研究中又集中于三维数据的校准问题，校准后数据 的特征提取问题以及计算量问题的研究。三维数据校准是进行三维人 脸识别的预处理步骤，其处理结果的好坏直接影响着三维人脸识别的 后续步骤，本文主要任务是找到三维扫描仪得到的两个或多个真实的 人脸数据之间的点与点之间的对应关系，从而便于人脸识别后续工作 的展开。本文的主要成果包括： 1 认真研究了基于i c p 的立体匹配算法的原理，对该原理给 出了简要的证明，并分析总结了基于i c p 的立体匹配算法的每一个步 骤的可改进处。 2 针对i c p 算法的不足之处，提出了s o f t a s s i g n i c p 算法。 并结合b i r k h o f f - v o n n e u m a n n 伯考夹，冯纽曼定理和线性规划问题的相 关定理对s o f t a s s z g n 算法的可行性进行了理论上的论证。分析了 s o f t a s s i g n i c p 计算量问题，并且针对这个问题，提出了双向 s o f t a s s i g n i c p 算法和r b f - s o f t a s s i g n i c p 算法，并给出了这 些算法的详细步骤。 3 建立了一个系统，该系统主要用于三维数据间对应关系的求取， 并且该系统能够详细反映实验的全过程，便于不同算法之间的比较。 关键词：人脸识别 立体匹配最近迭代点 s o f t a s s i g n 径向基插值线性规划 北京交通大学硕士学位论文 a b s t r a c t t h e t e c h n o l o g yo fb i o l o g i cr e c o g n i t i o ni sd e v e l o p i n gm o r ea n dn l o r e q u i c k l y a n df a c er e c o g n i t i o ni s a r ti m p o r t a n tf i e l di nt h er e s e a r c h m a n y r e s e a r c h e r sh a v ed o n eal o to fw o r ka b o u tt h e2 - df a c er e c o g n i t i o n w i t h t h ed e v e l o p m e n to ft h ee q u i p m e n tw h i c hi su s e dt og e tt h e3 - dd a t a ，m o r e a n dm o r er e s e a r c ha b o u t3 - df a c e r e c o g n i t i o na p p e a r e d ，i n c l u d i n g3 d c o r r e s p o n d e n c e ，g e t t i n gt h e3 - df e a t u r e ，t h ec o m p u t a t i o nc o m p l e x i t ya n d s oo n t h i st h e s i sf o c u s e do nt h er e s e a r c ha b o u t3 dc o h e s p o n d e n c e t h e w o r kw h a tw eh a v ed o n ew i l lb el i s t e da sf o l l o w i n g ： 1m u c hr e s e a r c ha b o u tt h ei t e r a t i v ec l o s e s tp c i n ta l g o r i t h m ，w h i c hi st h e m o s t p o p u l a rm e t h o do fs o l v i n gt h e3 dc o r r e s p o n d e n c ep r o b l e m ，h a v e b e e nd o n e 2 a c c o r d i n gt o t h ed e f i c i e n c yo fi c pa l g o r i t h man e wm e t h o dw h i c h i n c l u d e st h es o f t a s s i g n t e c h n o l o g yi sd e s c r i b e di nt h i st h e s i sa n d i nt h i st h e s i s ，t h ef e a s i b i l i t yo f a p p l y i n gs o f t a s s i g nt e c h n o l o g yt o i c p a l g o r i t h mh a sb e e na p p r o v e d t h ec o m p u t a t i o nc o m p l e x i t yo fi c p a l g o r i t h m a l s oh a sb e e n d i s c u s s e d an e wm e t h o dn a m e d r b f _ s o f t a s s i g n i c pi s p r o p o s e d t os o l v et h e p r o b l e m o f c o m p u t a t i o nc o m p l e x i t y 3 c o n s t r u c t i n g a s y s t e mt od e s c r i b et h ee x p e r i m e n tp r o g r e s s a n di nt h e s y s t e m ，t h ep r o g r e s sc a l lb es e e ni nd e t a i l i no r d e rt o c o m p a r et h e d i f f e r e n ta l g o r i t h m s k e y w o r d s ：f a c e r e c o g n i t i o n 3 d c o r r e s p o n d e n c e i t e r a t i v ec l o s e s t p o i n ts o f t a s s i g n r b f l i n e a rp r o g r a m m i n g 独创性声明 y 7 4 1 9 4 9 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：在枞 日期：旦年土月旦日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息、技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名：壅整 日期：旦年三月旦日 一堡垄 一 1 综述 1 1 选题意义及背景 1 1 1 人脸识剔背景f f l 基于生物特征的认证技术近年来发展迅速，计算机人脸识别技术 是其中最为活跃最具有挑战性的领域之一。它结合了认知科学、神经 心理学、图像处理、计算机图形学、机器视觉和模式识别等多个研究 领域，研究成果有着广阔的应用前景。 人脸识别能够用于身份识别，主要因为人的面貌属于人本身固有 的生物特征，这种特征具有不可复制，难以伪造的特点，弥补了密码、 签字、口令、证件等传统手段容易泄密、遗忘的缺点。理论上，人的 生物特征只要具有唯性和相对稳定性，都可以作为身份识别的依 据。而人的面貌特征是众多生物特征中比较方便获取的，可以在非接 触、不侵犯隐私条件下得到待识别人的特征，更易为人们接受，也更 为实用。 本文是在国家自然基金及9 7 3 项目基金的支持下开展工作的。 1 1 2 选遂意义 通常人脸识别的研究是针对二维静态图像或者二维视频序列的。 由于其数据获取方便、成本低并且计算复杂度小，二维人脸识别技术 得到了很大的发展。但是，基于二维图片的人脸识别技术同时也面临 着许多很难解决的问题。首先是姿态问题，实际应用中不可能精确的 捕捉每个待识别人的正面像，如何从二维图像得到其三维姿态也是一 个大问题。第二是光照问题，不同的光照条件下得到的图像有很大的 北京交通大学硕士学位论文 区别。另外，面貌、表情也影响着识别结果。 产生这些问题的主要原因是由于人的面貌特征本身是三维的，而 照片是对三维面貌进行投影的结果，投影的过程必然会损失一部分信 息。虽然可以采用多幅照片或者利用人脸面貌规则，根据图像中的光 照及阴影情况恢复三维信息，但由于目前认知科学和心理学尚未对人 的视觉机理有突破性的理解，所引入的人脸知识规则有很大的局限 性，限制了识别算法的精确度和准确度。针对这些问题，近段时间以 来，国际上已经有很多研究机构开始尝试基于三维的人脸识别的研 究，但还处于一个起步阶段，研究还不是很广泛，应用于实际的系统 几乎还没有。 由于三维人脸识别主要是弥补二维人脸识别在姿态，光照方面的 问题。而姿态主要要解决的问题是找到不同姿态的三维数据之间的对 应关系，从而便于特征提取等后续步骤的进行。根据上述情况，本课 题侧重于不同姿态的人脸三维数据之间的匹配问题的研究，并且探讨 相关应用系统的设计。 1 2 人脸识别技术的发展与现状 1 2 1 人脸识别技术的发展 入脸识别真正始于7 0 年代，经过三十多年的发展，结合了认知 科学、心理学、生理学、计算机、模式识别等相关领域的研究成果， 在9 0 年代达到了研究的高峰，目前已经形成了一些实用的产品，并 形成了规模巨大的产业。 人脸识别技术的发展主要分为三个阶段 一、7 0 年代初主要集中于研究进行人脸识别所需的面部特征，这 2 一阶段并没有彻底解决人脸的描述问题，后续有很多人继续研究这一 人脸识别的基本问题。但是直到现在，这个问题也没有得到彻底的解 决。 二、人机交互式识另十阶毂，这一阶段产生了入脸识别的基本方法， 形成了较为系统的体系。已经有基于特征和基于统计的方法之分。主 要有0 0 d s t i o n ，h a r m o n 和l e s k 用几何特征参数来表示人脸正面图像。 鼬v a 和k o b a y a s h i 则采用了统计识别方法，用欧氏距离来表征人脸。 t k a n a d n a g a o ) 戳t 了个高速且有一定知识导引的半自动回溯识 别系统，创造性她运用积分投影法计算出一组脸部特征参数，再利用 模式分类技术与标准人脸相匹配。总的来说，需要利用操作员的某些 先验知识，仍然摆脱不了人的干预l l l 。 三、真正的桃器自动识别阶段。近十余年来，随着高速度性能计 算机的发展，机器入视觉的研究，人脸模式识别方法有了较大的突破， 提出了多种机器全自动识别系统构架，并且出现了许多新的发展方 向。 1 2 2 三维人脸识嬲的研究现状 目前，由于三维数据的获取方式越来越便捷( 如三维激光扫描技 术、c t 成像技术、结构光方法等) ，获取设备越来越廉价，使得图形 技术的应用变为可能，有很多研究者已经开始尝试利用三维深度图 像，进行三维人脸识别的研究。三维人脸识g b 最初是从几何方法发展 而来的，出发点是希望利用三维的处理技术，解决传统二维照片识别 中因为人脸的姿态、光照等对识别造成的干扰问题，在三维的基础上 进行特征的提取和识别将有更丰富灵活的信息可以利用。 北京交通大学硕士学位论文 目前三维人脸识别技术的研究主要分为如下几个方面： 三维数据的校准问题；即三维数据之间的匹配问题。 校准后数据的特征提取问题；目前主要的特征提取方法有分析 三维人脸曲面的曲率等几何特征，对人脸曲面进行凹凸区域的 分割，正侧面轮廓边缘的提取等。最早对三维图像人脸识别的 研究有l a p r e s t e 提出的基于轮廓线的方法，通过对人脸面貌曲 率的分析，提取轮廓线上的特征点，利用轮廓线作为特征进行 识别，l e e & m i l i o s 从人脸面貌深度图像中抽取凸区域，这些凸 区域形成了特征集，计算出所有凸区域相关的扩展高斯图，两 幅面貌特征的匹配就是利用这些扩展高斯图像进行的 计算量问题，由于三维数据数据量大，汁算复杂，难以满足实 时相应的要求，因此如何降低算法的复杂度，减少计算量也是 目前集中研究的问题。 1 2 3 三维数据匹配问题的研究现状【3 9 1 三维数据匹配的方法根据用以匹配的原始材料，可以分为三大类： 基于区域的匹配，基于特征的匹配，基于相位的匹配。这三类算法因 匹配基元的不同，它们判断对应点匹配的理论依据也有所不同，同时 匹配基元的稳定性、致密性和歧义性程度直接决定了各类算法的基本 特性。另一方面，对于不同的匹配基元相似性撄度的算法模型可以是 通用的，比如都可以用距离测度来进行匹配度量，各类匹配算法中也 不乏一些共有的约束条件，比如m a r t 立体视觉计算理论中提出的唯 一性、相容性和连续程约束。必须充分分析各类算法的个性和共性， 依靠科学的评价手段阻综合的观点进行算法设计，推出更佳的理论模 4 型。 基于区域的匹配是指给定同一场景的两幅图像，粗尺度上凰像对 间的相似性程潼更为接近。如果将图像对空间量化为许多图像块 任意一图像块看上去将魄量化前与对应图像块更为相似。因此， 基于区域的图像匹配将图像对量化为许多图像块或改变图像对的 尺度大小而确定对应的区域。区域匹配以基准图的待匹配点为中 心龟8 建一个窗口，用邻域像素的灰度值分布来表征该像素，然后 在对准图中寻找这么一个像素，以其为中心创建同样的一个窗口， 并将其邻域像素媳氇分布来表征它，两者间的相似性必须满足一 定的阈值条件。基于区域的匹配，根据所选用的区域又可以分为 基于一般亮度域的匹配和基于变换域的匹配。 区域匹配算法一般适用于满足以下条件的立体视觉问题： 光源可理想化为无穷远处豹点光源。场景中的物体表面为完全漫 反射。图像对之间的几何畸变和辐射畸变( 或不一致的程度) 很小。 区域匹配算法的实质是利用了局部窗口之间灰度信息的相关程 度，它在地势平坦而纹理丰富的地方可以达到比较高的精度，并 且能取得致密的视差场。此外，匹配的理论精度还可预先算出。 但是，区域匹配选取一定大小窗口内的灰度分布特性作为匹配基 元决定了该算法具有以下缺陷： 1 对仿射畸变和辐射畸变较敏感。 f 2 1 匹配窗大小难选择窗口选择过大，在高度间断处会出现误匹 配，选择过小，区域内的灰度分布特性未得以充分展现。 r 3 ：) 计算量大，速度慢 针对以上缺陷，不断地有改进算法出现，下面归纳出一些主 北京交通大学硕士学位论文 要算法以供借鉴【3 9 l ： 处理仿射畸变和辐射畸变： ( 1 ) 采用互补策略将不同类型的匹配算法结合使用。m o r i 从包含边缘特征的区域获得高置信度的匹配结果，然后内插产生 视差图。i l a n n a h 将兴趣算子、多分辨率尺度结构、区域相关结合 在一起，充分利用了特征匹配的鲁棒性和区域匹配的致密性。 ( 2 ) 直接估计仿射变换矩阵。o t t o 等的最小二乘法根据最小均方误 差准则迭代求解仿射变换矩阵，经重采样计算搜索区对应点的坐 标。 改善匹配窗口不易选择的缺陷：利用单个的深度数值描述有 限区域的深度信息的量化过程必定导致局部误差为解决此类间 题，区域匹配通常借助于窗口形状技术来改善视差不连续处的域 匹配，使得定位的准确性不再受到区域量化的影响。k a n a d e o 和 k u t o m i ”l 根据局部灰度变化以及局部视差变化的统计分析，自适 应地调整匹配窗口的大小。该算法能够较有效地处理视差突变区 域，通过迭代还可达到子像素精度。r o s e n h o l m 4 1 】等提出关联窗1 1 1 1 法解决平滑区域和重复纹理区域的匹配问题它是在表面连续性约 束条件下同时进行多个窗口的匹配，这种方法更充分地利用了先 验知识和图像中的结构信息。 快速算法的设计：搜索空间较大是导致区域匹配计算速度慢 的主要原因。粗一精匹配策略能大大地减少搜索空间的大小。对 于将区域互相关系数作为相似性测度的匹配算法，与匹配窗口大 小无关的快速互相关运算能显著地提高运算速度。为进一步缩小 搜索空间，s a m 在采用粗一精匹配策略的同时，将图像按照视差的 不同范围分割成多个子图像，然后在子图像上运用快速互相关运 算，该快速算法对于视差变化显著的图像对十分适用。 基于特征的匹露是为使匹配过程满足一定抗噪能力且减少歧义性 问题丽提出孵。般地，用于匹配的特征应满足以下特性：唯一 性、再现性、具有物理意义。作为匹配基元的特征分为局部特征 和全局特征两大类。局部特征包括点、边缘、线段、小面或局部 能量。全局特征包括多边形和图像结构等。基于特征的匹配一般 含有特征提取t 和定位、特征描述、特征匹配三个步骤。面向点， 线，面和局部能趋等局部特征提取的算法很多。全局特征的定义 和提取跟具体应用有关，如用于人脸匹配的三角形网格结构就是 全局特征的一种。 在基于特征的：匹配中，也可从另一个侧面进行分类，大致分 为基于数据本质特征的匹配和基于几何特征的匹配f 3 j 。 在许多方面特征匹配处理立体视觉问题十分健壮特征匹配 基元包含了令九满意的统计特性以及算法编程上的灵活性。算法 的许多约束条件均能清楚地应用于数据结构，而数据结构的规则 性使得特征匹配适用于硬件设计。其中基于线段的特征匹配算法 将场景模型描绘成相互联结的边缘线段，而非区域匹配中的平面 模型，因此能缀好地处理一些几何畸变问题。此外，特征匹配不 直接依赖于灰度，具有较强的抗干扰性，而且计算量小，速度快。 由于边缘特征往往出现在视差不连续的区域。特征匹配较易处理 立体视觉匹配中的视差不连续问题。同样地，特征匹配算法也存 在着些不足： ( 1 ) 特征在图像中的稀疏性决定特征匹配只能得到稀疏的视差场 北京交通大学硕士学位论文 要获得密集的视差场必须辅以插值过程，而为了保证插值点的精 确度插值过程往往较为复杂。 ( 2 ) 特征的提取和定位过程直接影响特征匹配结果的精确度。为克 服以上缺陷，近年来有不少改进的特征匹配算法出现，这里归结 如下： ( t ) 互补策略可以克服特征匹配视差场的稀疏性以及精确插值的 复杂过程。k o n r a d 以区域匹配结果内插特征匹配结果得到致密的 视差场。c e i g e c 等利用视差空间图技术求取视差，将特征匹配结 果作为匹配路径的一个全局约束，而特征之间的匹配通过动态规 划算法实现。 ( 2 ) 利用统一的对高频噪声不敏感的模型提取和定位特征。一般的 特征匹配中必须首先建立提取特征的先验摸型，这样只能检测出 单一类型的特征。为检测出不同类型的特征并摒弃 建立先验模型的步骤，m i c h a e l 蛾4 4 j 等用局部能量法统一定位多方 向的亚像素特征，这种非梯度算子不会放大高频噪声而引起特征 的虚假定位。 相位匹配基于这么个假定，即认为像对中对应点的局部相位是 相等的。根握傅立叶平移定理，信号在空间域上的平移产生频率 域上成比例的相位平移。频率域信号分析在数学表达上更有助于 区域分析。继区域匹配和特征匹配后，k u g l i n 和h i n e s 4 3 】等提出了 第三种立体视觉匹配算法一相位匹配考虑傅利叶交换的空间支 撑为无限，一般地，相位匹配方法对带通滤波信号的相位信息进 行处理而得到像对间的视差。最常用的相位匹配方法有相位相关 法和相位差一频率法。 在相位匹配的滤波过程中，满足一定条件的带通滤波器均可 采用。目前，大多学者都选择比加窗傅立时变换核更可靠的、符 合a 眼视觉生理特征的g a b o r 变换核。但是，对于方差固定的 g , a b o r 函数，其伸缩平移系在相空间中的分辨率是固定韵，因此， 有些学者采用以双正交小波基为变换核的相位匹配算法。 相位匹配与前醺两种传缆方法相比，其匹配基元相位 本身反映的就是信号韵结构信息，对图像的高频噪声有很好的抑 制作用。相位匹配适于并行处理，对几何畸变和辐射骑变有很好 的抵抗能力，能获得亚像素级精度的致密视差。但是，当局部结 构存在的假设不成立时，相位匹配算法因带通输出信号的幅度太 低而失去有效性，也就是通常提到的相位奇点问题。此外，相位 匹配算法的收敛范厨与带通滤波器的波长有关，通常要考虑相位 卷绕，随视差范围的增大，其精确性会有所下降。 在已有的研究成果中，有几中比较典型的方法，这些方法对 三维数据匹配问题的研究有着很重要的作用，下面将对这些方法 作简要的介绍【3 m 。 i c p m e r a t i v ec l o s e s tp o i n t ) ；迭代最近点 i c p 算法是由b e s l 和m c k a y 针对三维形状的匹配提出的，它已成 为个比较流行韵求解三维数据匹配问题的工具，并且在后面的 研究中得到了一定的扩展。i c p 的基本思想是采用待匹配集合的 子集，在迭代过程中求取一个最优变换，求取子集间点与点之间 的对应关系。在辅助其它方法，求得整个集合上的对应关系。i c p 算法属于基于特征的匹配方法，算法中用来计算对应关系的子集 可看作待匹配集合的特征子集。i c p 算法采用的是刚体变换的模 北京交通大学硕士学位论文 型，其主要优点是不用在迭代过程前估计确定的对应关系，而是 在迭代过程中选取最近点的子集，估计变换，将变换应用于原始 的待匹怒集合，_ 并且t c p 算法虽然采用、的是网体变换模型，但是 它能够运用于具有较小非刚体变换的三维数据匹配中。当然，由 于i c p 算法属于基于特征的匹配算法，它也存在着基于特征匹配 算法的不足，本文正是从这些不足出发，来研究改善i c p 算法的。 h o m o t h e t i cm o t i o n - n c a 变换 相似变换能够代表表面的均匀扩张或者收缩，其扩张或收缩由其 拉伸因子锣来袁征，因此相似变换能够近似代表非刚体变换。最 优拉伸因子日可在变换前由领域的高斯曲率求得，并且，可由得 到的拉伸因子口计算所求对应关系的错误率，具体求解过程见文 献1 3 1 l 。 a m i n i 算法 3 3 j a m i n i 和d u n c a n 主要采用t h i n p l a t e 模型，基本思想是求取 t h i n p l a t e 变换的最优参数，这些最优参数使形变能量最小，形变 能量定义如下： m = 旯 “茁，) 。一( r 1 ) 。) 2 + ( ( r ：) 。一( r 2 ) 女) 2 + c 等一每，2 + c 筹一暑，2 + c 每一2 ， 这里盯。，r ：是主曲率。 经过计算有使式e 。：fr a i n 。最小的参数即为晟优参数。 一e ， w a n g 算法【3 4 】 综述 w a n g 算法是由w a n g 等提出的，主要用于解决大脑图像1 匹配的问 题。算法将歇氏距离和微分几何信息组合在一起。算法与前面提 到的算法不同，它不要求三维数据，而是从二维图像中来估计数 据的对应关系。 w a n g 算法采用的错误函数为 e ：= d - , t l q f q 欧氏距离d 。定义为 d 口= 1 十、f o 。一书+ ( y 。- y + ( z 一z 单位法向量匹配尺度定义为n j ， “口；2 一& ，n ， 特征匹配尺度厶基于曲率，只应用于大脑图像的匹配。 w a n g 算法即是用三个匹配尺度来衡量匹配质量，从而找到最 优对应关系。 1 2 4 三维物体的表示方式 三维人脸数据是三维物体的一种，不同的表示方式对应不同的处 理方法，下面将简要介绍现有的三维物体表示方法，并且给出本文采 用的三维物体表示方式。 1 2 4 1 基于数学描述的表示方法 3 8 1 由于基于数学描述的表示方法对物体的几何描述是完全的，整个 物体都能被完整地描述，因此物体的任何一个姿态都能通过模型的一 个特定角度表示出来。 北京交通大学硕士学位论文 参数模型参数模型被广泛应用于计算机辅助的生产设计以及其他 物体建模系统中，参数模型有以下几个特点： 数学上的描述是完整的 采样比较容易 便于设计 能够用于表示具有复杂几何结构的物体 通常，用于表示三维表珂的参数模型为 p 。厂 ，v ) 1 s 心4 蹉剖 函数厂 ，v ) 堪，v ) ，h ( u ，v ) 以0 ，v ) 为自变量，不失一般性， ，v ) 定义 域为 0 , 1 x 【0 , 1 】 最常用的参数公式为非均匀有理b 榉条，描述如下 s ( u ，p ) 一b ? ，“ ) m 。( v ) i j 这里。( “) 和 f 。j ( v ) 是b 样条基函数，序号为女和l ，b ? ，是控制点的 齐次坐标。自然二次曲面( 例如球面，柱面，锥面等) 都能够用参数 模型表示，齐次坐标使对这些陆面的描述很灵活a 这种描述方式已经被用于计算机视觉系统，但是b e s l 3 5 时也解 释了参数模型没有被广泛采用的原因一很难用由参数矩形定义的曲 面去表述物体表面上特定的区域。并且，齐次控制点既不容易得到也 不是唯一的。 隐函数曲面曲面能够被隐台定义于一个函数等式，中： s ； l 茗，y ，z m ， ，y ，z ) ；o 如果f 是多项式并且由单个曲面采样得到的样本集已知，那么就可由 这些已知的样本去估计多项式的系数。这种方法已经被应用于解决图 像分割和图像识别的预处理问题。 超元组超元组s ( n ，口) 定义如下： s r 叩，盯，2 囊圣】2 s ( x ，y ，z ) = 口1c o s 6 ( r ) c o s 。向) a 2c o s “( 叩) s i n 。( 珂) 口3s i n “( 叩) 孔氕 一i 5 叩墨i ，“s 8 螂 p 影卜i z ，z i i ( 三) i + ( 上) ii 1 + ( 一， 【q j = 0 p e n t l a n d 【3 6 和s o l i n a , b a j c s y ： 3 7 】曾将锥化，缠绕，弯曲的形变加在超 元组模型上来表示各种非规则物体。 超元组模型已被用于识别一组数量较多的物体，并且被用于表示 合成部分，但是超元组模型不能有效地表示非规则物体表面上的形状 变化。 多边形网面 多边形网面模型定义为o = cp ，v ， 北京交通大学硕士学位论文 这里= 饥，v 。 为数量为n 。的三维顶点集合，v = 口。，y 。，z ，) 7 p 一 n ，p 。 为数量为n ，的多边形集合，每个多边形由若干个三维 顶点组成p ；= 以。，u 。 ，若对所有的i 都有n v ：= 3 ，那么就是三角形 网面模型。 物体三维形状模型的更一般表示是多边形网面表示，其中应用最 为普遍的是三角形网面表示。一个物体三维形状数据通常有两种途径 得封：一种是根据实际物体的几何形状通过计算机辅助设计( c a d ) 方 法建立，这种方法对于规则形状的物体建模非常有效；对于形状非常 复杂的物体，则可以利用测距成像或立体成像系统来获取，然后再用 三角形网面表示出来。 多边形网面在计算机图形学上已有很长的历史，并且近来在计算 机视觉领域有着越来越广泛的应用。其应用之所以越来越广泛主要是 由于计算机存储能力，处理速度的提高以及稠密排列传感器的广泛应 用。并且多边形网面模型能够在任意要求精度忠实的表现出具有复杂 结构的物体。 本文处理的数据是从三维扫描仪中得到的稠密排列数据，采用三 角形曲面模型描述。 1 2 4 2 基于体积描述的表示方法1 4 1 三维物体可以用该物体所占三维空问的非重叠子区域来表示，即 空间占有量。一般非重叠子区域可以分为标准和非标准两大类。标准 子区域是指正方体，长方体等基本体素，利用这种体素构造物体的方 法称为体素表示。非标准子区域是指三维物体本身具有的特定的体积 单元，利用这种体元构成的三维物体表示称之为单元分解表示方法。 1 4 综述 单元分解将三维物体分割成更小的单元，单元与单元之闻不菇享体 积，将相邻单元之阊韵这种关系称为准不连接，唯一的运算是粘接。 空问占有量表示方法包含了物体的详细描述，这是一种低层次的 描述。这种类型的表示必须经过处理才能得到物体的特定特征，以使 得假设生成过程成为可能。 1 3 谋题研究内容 论文主要任务是针对三维扫描仪得到两个或多个真实的人脸数 据，找到它们之间的点与点之间的对应关系。本文的结构安排如下： 第一章综述 本章奔绍论文的研究背景和研究目标。首先简要介绍了人脸识别 提出的背景及相关的研究发展，目前的工作和研究领域。然后介绍了 三维人脸识别的相关研究发展情况，目前的工作和研究领域。然后详 细介绍了三维人脸识别中逛配阔题的相关的研究发展，目前的工作和 研究领域，现在存在的问题，匹配的分类及优缺点，最后一部分介绍 了论文的工作和结构安排。 第二章基于i c p 的三维数据匹配 i e p 是一种基于几何特征匹配的算法。本章首先介绍了基于 几何特征匹配的原理和实现步骤。然后详细介绍了基于i c p 的立体匹 配算法的原理和实现步骤，并且对基于i c p 的立体匹配算法的原理给 出了简要的证明。最后总结了基于i c p 的立体匹配算法的每一个步骤 的可改进处及其相关改进算法。 北京交通大学硕士学位论文 第三章基于s o f t a s s i g n i c p 的三维数据匹配 s o f t a s s i g n 的基本思想是由r a n g a r a j a n 等在1 9 9 8 年提出 的 2 1 ，主要用于各类匹配问题中点与点之间对应关系的求解过程的 优化，最优解结果的改善以及对o u t l i e r 的处理。本章首先介绍了 s o f r r a s s i g n 算法的基本思想，并结合b i r k h o f f - v o nn e u m a n n 伯考夫 冯纽曼定理对s o f t a s s i g n 算法的可行- 陆进行了理论上的论证。然 后介绍了s o f l l a s s i g n 算法的具体步骤。然后开始详细介绍本文提 出的i c p 中s o f t a s s i g n 思想的应用一先对s o f l 、a s s i g n 应用于i c p 算法的可行性进行了理论上的证明，然后详细介绍了本文提出的 s o f t a s s i g n i c p 算法的具体步骤。最后分析了s o f t a s s i g n i c p 计算量问题，并且针对这个问题，提出了双向s o 阿a s s i g n i c p 算法 和r b f s o f t a s s i g n i c p 算法，并给出了这些算法的详细步骤。 第四章实验结果分析 本章首先给出了实验得到的数据，包括i c p 算法， s o f t a s s i g n i c p 算法，r b f 调整脸部网格模型算法， r b f s o f t a s s l g n i c p 算法的实验结果。并且根据这些实验结果作了 数据上和理论上的分析。 第五章实验系统的实现 前几章给出了本系统所使用的各种算法。本章主要介绍整个三三维 人脸识别中立体匹配系统的实现方法，包括其实现的软件平台，硬件 平台，三维数据的输入格式以及算法实现的具体步骤。并且本章最后 给出了立体匹配系统的运行方式，使用说明等相关文档。 1 6 综述 第六章结束语 本章将对本论文的工作做出总结，并指出尚未解决的问题和今后 的研究方向。 北京交通大学硕士学位论文 2 基于i c p 的三维数据匹配 c p 是一种基于几何特征匹配的算法。本章首先介绍了基于 几何特征匹配的原理和实现步骤。然后详细介绍了基于i c p 的立 体匹配算法的原理和实现步骤，并且对基于i c p 的立体匹配算法 的原理给出了简要的证明。最后总结了基于i c p 的立体匹配算法 的每一个步骤的可改进处及其相关改进算法。 2 1 i c p 基本原理 2 1 1 基于几何特征的匹配 i c p 是一种基于几何特征匹配的算法。本节首先简要介绍一 下基于几何特征的匹配问题。基于几何特征的匹配实质上是在待 比较的两个数据集中找到一种对应关系，这种对应关系使两个数 据集间的“距离”最小，这里的距离可以是人为定义的某种距离。 定义如下： 。 定义两个点的集合，p = 切， 有j v 。个点，x ； t ) 有。个点， 寻找一个刚体变换，使得式( 2 1 ) 最小 。( r 力= 寺誊i i r * p i + t - y ；| 12 = 万1 著n i k r p i + t ) 一c ( p 。) | | 2 ( 2 1 ) 这里r 是刚体变化中的旋转矩阵，t 是刚体变换中的位移矩阵， n 为p 与x 之间的配对数。 c ：p x l 却： j d 。) p ，y ：= c ( p 。) x( 2 2 ) 2 1 1 1 基于几何特征的迭代匹配 自1 9 9 2 年以来，已经有几位学者开始研究基于几何特征匹配 1 8 基于i c p 晦三雏数据匹配 的解决算澍哪5 3 1 6 j ，他们采用的方法都比较相似，算法的主要思想 是：如果待匹配的两个数据集已经经过了粗匹配，即第一个数据 集里点与其在第二个数据集里鲍黠应点比较靠近，那么就能找到 一种变抉使它们更加接近，接着再在这个基础上重复不断的进行 上述过程，匹配结果就会越来越好。 因此，在每一次迭代过程中，寻找使式( 2 1 ) 最小的变换都会 进行一次，式( 2 1 瞰写为 e 【雹，。卜万1 善n 她( 砌。+ r ) + t x - c ( n 州2 ( 2 3 ) k 为迭代次数，鹾优变换矩阵( r ，t ) ，经过数次迭代得到，迭代 过程如下： r = r r k ( 2 4 ) f = t + “ 而基于几何特征的迭代匹配的各种算法的差异主要在于怎样 确立点与点之间的最近关系。例如b e s l 采用欧氏距离来衡量点与 点之间的距离nt h e n 采甩法向量等【6 1 。 2 i 1 2 粗匹配 如2 1 1 1 所述，基于几何特征的迭代匹配收敛( 即能够找到 最优变换矩阵) 的条件是，待匹配的两个数据集己经经过了粗匹 配。因此必须使两个数据集在进行基于几何特征匹配迭代以前， 达到粗匹配，以满足收敛条件。已经有很多学者在这个问题上进 行了比较深入的研究，s t e i n 采用高级特征进行粗匹配f7 1 ， 3 d s e a n n e r 采用硬件辅助的方法进行粗匹配( 8 1 ，j o h n s o n 采用方向 特征进行租匹配哆b e m a r d i n i ，采用对其激光点投影的方法进行粗 匹配f 1 0 1 。 北京交通大学硕士学位论文 2 1 2 基本i c p 迭代最近点基本原理 i c p 算法是种基于几何特征的迭代匹配算法，它能够较好 解决满足粗匹配条件的匹配问题。i c p 是一种在迭代中求取点与 点对应的优化算法，其迭代的过程实际上是最优解的求取过程。 下面介绍i c p 算法的步骤： 输入：两个点的集合，p ；侈，) 有，个点，x ；饥 有虬个 点 输出：找到个最优化解矗，t ，使得忙+ p + f x l 的值最小 s t e p l 初始化七= o ，r ；p ，t = ( o ，o ，0 ) ( 2 5 ) s t e p 2 第k 次迭代： 计算p 上每个点在x 上对应的最近点 采用欧氏距离：d ( p ，盖) = 妒一x i | 2 ( 2 6 ) 定义砭； y 。 为最；扫。 的最近点 y m2c ( 只，t ) 4 x l 卿d ( p 琳，z ) ( 2 7 ) 计算r 。，t 。，使得 吼= 古勃r k * p i , o + t t - y i k 1 2 眨s ， 最小 将得到的r 。，f 。应用于晶，得到 尸；r t8 只o + t ( 2 9 ) 如果达到迭代次数或者达到迭代终止标准，则终止迭代， 2 0 基于i c p 的三维数据匹配 否则继续迭代 下图为i c p 算法的流程示意凰 x，x，pkx ，p ￥ 幽2 1 i c p 算继流程图 2 1 3 基本i c p 收敛性证明 i c p 算法总是单调收敛于局部最小，证明如下： 对于任意一次迭代( 不妨设为第k 次迭代) ，数据集只和k 之 间的均方差被定义为d 。， 小击弘厂蚝。| 2 c z 加， d 。最小化后，均方差 = 寿弧f f l , o + t t h 胛= 古n ；叫巾 根据i c p 定义有吼s d 。又因为y m + j 是n n 的最近点，所以 l i p 。ry l , k + l j l 2 l i p 耻厂y l , kl 2 i ；k ， ( 2 1 2 ) 北京交通大学硕士学位论文 因此以。se 。，又因为为均方差，所以对任意k ，芑0 ，综上 所述，对任意k 有如下结论： 0s p k “s d e “墨p s d 2 1 3 ) 得证t c p 单调收敛于局部最小。 2 1 4 基本i c p 的缺点 未经改进的i c p 主要存在三大问题：对于在另一个数据集中 找不到匹配点的数据点，i c p 表现出来的鲁棒性较差，t c p 尤其 对于噪声数据非常敏感；计算速度较慢，在i c p 的迭代过程中， 最近点的查找需要大量的计算，因此计算速度较慢，如何提高i c p 的计算速度，一直以来也是研究人员关心的问题。另外针对人脸 识别，由于入脸是一个三维的非刚体，i c p 中采用的刚体变换在 某些情况下将不能很好的发挥作用。 2 1 5 基本i c p 中最优变换矩阵的计算 每次迭代( 不妨设为第k 次) 都对应一组最佳变换矩阵 ( r ，f 。) ，因此最佳变换矩阵的计算每次迭代都将进行一次，即对 等式( 2 8 ) 中矩阵( r 。，t 。) 的计算。主流算法共有三种，这四种算 法在本质上都是相同的，都是用最小二乘的思想来求取矩阵r + 和 f 。它们的区别仅在于两点：旋转矩阵r 。的不同表示方法和数学 计算过程采用不同的数值计算方法f 1 1 1 。，下面将详细介绍三种主 流算法的原理和实现的具体步骤。 一：基于s v d 奇异值分解的最佳变换矩阵的计算： 基于i c p 的三维数据匹配 旋转矩阵的表示： 采用3 3 的单位正交矩阵来表示旋转矩阵风。 旋转耀阵的计算过程： 输入：i 丙4 a 的集合，p = 伽i 有_ ，个点，并= 瓴 有。个 点 s t e p l ：定义： 三；三每。 n 白 i 一1 挚p 。 n 台1 茁c 盏石r 一石 一 f 2 1 4 ) p c , 2p i p 这样，等式( 2 8 ) 可以表示为： ? 小抹南。 均 2 蓍魄7 一p 疆t ，一2 x 。r r p j s t e p 2 ：定义：h = p q z 。，7 ，对矩阵进行s v d 分解 i 一1 h = u 氏y t s t e p 3 ：计算最优矩阵r = 阿7 位移矩阵t 的计算 t 女= z r 女p 二、基于正交分解的最佳变换矩阵的计算 旋转矩阵的表示： 采用3 3 的单位正交矩阵来表示旋转矩阵r 。 ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 1 北京交通大学硕士学位论文 旋转矩阵的计算过程： 输入：两个点的集合，p = 扫0 有。个点，x = 扛；) 有。个点 s t e p l ：定义： 12 专芎t 石t 2 x f 一一 。：，。， p 2 专p 以z 邓c 叩 这样，等式( 2 固可以表示为； s t e p 2 ：求取式f 2 2 0 1 的最小值等价于求取式( 2 2 0 ) 最后一项 的最大值，也就等价于求取t r a c e ( rm ) 的最大值。定义 m = h 7 t 罗z t p ： ( 2 2 1 ) “1 1 s t e p 3 ：计算最优矩阵 假设m 是非奇异的，那么m 可以被分解为 m = u s ( 2 二zj 这里 u 。m s ，s ：7 m ) ( 2 2 3 ) 并且u 为正交矩阵 当t r a c e ( rm ) 最大时 函圳再u l ur 】+ 箦t + 筹， 皿z 4 ， 加 0 p r 脏 h 艮 一 硝 ，既 b 以 剖引一 = r 工 ) i 0 眠。喀 基于i c p 的三缝数据匹配 这里轨 和岳， 为矩阵膳7 吖的特征值以及对应的特征向量 三、基于四元数的最佳变换矩阵韵计算 1 q 四元数是一个四元矢量罐；( 吼，q ，孽：，q 3 ) ，可用来表示坐标轴 x 2 + y 2+z2 + 2 = 1 ( 2 2 6 ) 靠+ 口i 2 + 鼋；+ 鼋3 2 ；1( 2 2 7 ) 每一个单位四元数和其反极点一q 。( 一q 。，q 1 , - q 2 , - q ，) 都表示三 f q ；+ q ? + q ；+ g ； 2 ( q q2 一q o q 3 ) 2 ( q l q ) + q o q ：) 1 尺( q ) ：jz ( q ，q ：+ q 。q ，) q ；一q + q ；一日； 2 ( g ：q ，一g 。g ，) l ( 2 2 8 ) z ( q 、9 3 一q o q ：) z q 2