（应用数学专业论文）基于统计学的三维模型检索算法.pdf

摘要 三维模型在虚拟手术、分子生物、文物保护、计算机辅助设计等众多领域都扮演着 非常重要的角色。上个世纪9 0 年代以来，随着这些领域的快速发展以及网络三维模型 海量数据库的扩充和三维物体扫描技术的成熟，导致了三维模型数量的急剧增加，人们 迫切需要从众多的三维模型中准确地找到自己所需要的模型，因此三维模型检索越来越 受到研究人员的重视。本文在对前人关于三维模型检索的工作进行系统研究的基础之 上，提出了两种新的基于统计学的三维模型检索算法。本文所做的工作如下： ( 1 ) 总结与分析了三维模型检索的研究现状、相关技术。 ( 2 ) 实现了两个前人的基于统计学的三维模型检索算法：o s a d a 提出的形状分布的 检索算法和a n k e r s t 提出的对模型切分后生成直方图的检索算法。 ( 3 ) 提出了一种新的基于统计学的三维模型检索算法：基于相对角度直方图匹配的 检索算法。该算法仅仅通过统计模型表面点上每一个点与其他所有点之间的角度关系作 为模型的特征量用于模型的检索，不需要考虑模型三角面片的相关信息。 ( 4 ) 由于相对角度直方图需要考虑模型上每一个点与其他所有点之间的角度关系， 导致了每一个模型所形成的直方图的维数较大，所以基于降维的考虑又提出了一种基于 聚类分析的检索算法。该算法大大的降低了模型的特征量维数，从而降低了算法的时间 复杂度，加快了模型检索的速度。 ( 5 ) 总结了算法性能评价的相关标准，并且从实验结果与算法性能来看，本文提出 的两种三维模型的检索算法对于大多数模型来说在检索效果与算法性能上都比o s a d a 提 出的形状分布的检索算法和a n k e r s t 提出的对模型切分后生成直方图的检索算法要好。 关键词 三维模型检索，特征提取，相对角度直方图，聚类分析，最佳聚类数 a b s t r a c t 3 dm o d e lr e t r i e v a lp l a y sav e r yi m p o r t a n tr o l ei ns om a n yf i e l d ss u c ha sv i r t u a ls u r g e r y , m o l e c u l a rb i o l o g y , h e r i t a g ep r o t e c t i o n ，c o m p u t e ra i d e dd e s i g n s i n c et h e9 0 s ，w i t ht h er a p i d d e v e l o p m e n to ft h e s ef i e l d sa sw e l la st h ee x p a n s i o no fm a s s i v ed a t a b a s eo fw e b3 dm o d e l a n dt h es c a n n i n gt e c h n o l o g ym a t u r i t yo ft h r e e d i m e n s i o n a lo b j e c t s ，t h e q u a n t i t i e so f3 d m o d e l sa r es h a r p l yi n c r e a s e d ，i t su r g e n tn e e df o rp e o p l et oa c c u r a t e l yf i n dt h e i ro w n r e q u i r e d m o d e lf r o mal a r g en u m b e ro f3 dm o d e l s s o3 dm o d e lr e t r i e v a lb e c o m e sm o r ea n dm o r e i m p o r t a n c et or e s e a r c h e r s b a s e do nt h es y s t e m a t i cs t u d ya b o u tt h ep r e v i o u sw o r ko f3 dm o d e l r e t r i e v a l ，t h i sp a p e rp r e s e n t st w on e wk i n d so f3 dm o d e lr e t r i e v a la l g o r i t h mb a s e do n s t a t i s t i c s t h ew o r kd o n eo ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) t h e3 dm o d e lr e t r i e v a l sr e s e a r c hs t a t u sa n dr e l a t e dt e c h n o l o g i e sa r es u m m a r i z e da n d a n a l y z e d ( 2 ) t w op r e v i o u s3 dm o d e lr e t r i e v a la l g o r i t h m sb a s e do ns t a t i s t i c sa r er e a l i z e d ：t h ea l g o r i t h mo fs h a p ed i s t r i b u t i o nw h i c hw a sp r e s e n t e db yo s a d aa n dt h ea l g o r i t h mo ft h em o d e l c u t t i n gg e n e r a t e dh i s t o g r a mw h i c hw a sp r e s e n t e db ya n k e r s t ( 3 ) an e w3 dm o d e lr e t r i e v a la l g o r i t h mb a s e do ns t a t i s t i c si sp r e s e n t e d ：t h er e t r i e v a l a l g o r i t h mb a s e do nt h er e l a t i v ea n g l eh i s t o g r a mm a t c h i n g t h ea l g o r i t h ms i m p l yn e e dt o s t a t i s t i ct h ea n g l e sr e l a t i o n s h i po fe a c hm o d e lp o i n to fm o d e l ss u r f a c ep o i n tw i t ha l lo t h e r p o i n t sa sm o d e l sf e a t u r e sf o rt h em o d e lr e t r i e v a l ，i tn e e d sn o tt oc o n s i d e rt h em o d e l sr e l a t e d i n f o r m a t i o no f t r i a n g l e ( 4 ) an e wr e t r i e v a la l g o r i t h mo fc l u s t e ra n a l y s i sb a s e do nd i m e n s i o nr e d u c t i o ni nt h i sp a p e r i sp r e s e n t e da st h eh i s t o g r a mo fr e l a t i v ea n g l en e e d st oc o n s i d e r a t ea n g l e sr e l a t i o no fa l l p o i n t s ，w h i c hh a sl e a dt ol a r g ed i m e n s i o no fh i s t o g r a mg e n e r a t e df o re a c hm o d e l t h i s a l g o r i t h mg r e a t l yr e d u c e st h ec h a r a c t e r i s t i ci n d e xd i m e n s i o no fm o d e l ，t h u sr e d u c i n g a l g o r i t h mt i m ec o m p l e x i t ya n da c c e l e r a t i n gt h es p e e do fm o d e lr e t r i e v a l ( 5 ) t h er e l e v a n ts t a n d a r d so ft h ea l g o r i t h mp e r f o r m a n c ee v a l u a t i o na r ec o n c l u d e d ，a n d f r o mt h ee x p e r i m e n t a lr e s u l t sa n dt h ea l g o r i t h mp e r f o r m a n c e ，t w ok i n d so f3 dm o d e lr e t r i e v a l a l g o r i t h mw h i c ha r ep r e s e n t e db yt h i sp a p e rh a v eb e t t e rt h a nt h ea l g o r i t h mo fs h a p e d i s t r i b u t i o nw h i c hw a sp r e s e n t e db yo s a d aa n dt h ea l g o r i t h mo ft h em o d e lc u t t i n gg e n e r a t e d h i s t o g r a mw h i c hw a sp r e s e n t e db ya n k e r s t f o rt h em o s tm o d e l s k e y w o r d s 3 dm o d e lr e t r i e v a l ，f e a t u r ee x t r a c t i o n ，t h eh i s t o g r a mo fr e l a t i v er n g l e ，c l u s t e ra n a l y s i s ， t h eb e s tc l u s t e rn u m b e r i l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：牡：l 一指导教师签名： 矿| 年6 只似bz 炒v - 7 年6 只p 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：闻州 杪1 年莎月尸日 西北大学硕十学位论文 1 1 研究背景与相关知识 第一章绪论 上个世纪7 0 年代以来，多媒体数据已经经历了3 次革新：声音、图像和视频。从9 0 年代中后期开始，我们又迎来了第4 种数字化媒体三维几何模型。每一次多媒体数 据革新都是由不断增长的数据获取能力、计算机运算能力、计算机存储能力和传输带宽 引发的。尽管几何造型技术已经发展了多年，但手工制造几何模型的繁琐过程大大阻碍 了三维几何模型的应用。近几年来，得益于各种低档和高档三维扫描仪提供的三维几何 获取能力的大大发展，把现实世界中的物体数字化成三维几何模型已经不再困难。最著 名的例子是s t a n f o r d 大学的d i g i t a lm i c h e l a n g e l op r o j e c t ，该项目通过一整套三维扫描硬件 和三维重建软件系统完成了一些大型雕塑的数字化过程，生成的最复杂的三维模型包括 2 0 亿个多边形和7 0 0 0 幅彩色图像。另外，计算机运算能力和存储能力的大大提高以及各 种图形加速卡的出现使得在个人计算机上处理三维几何数据变得很容易。 三维模型在虚拟手术、分子生物、文物保护、计算机辅助设计等很多领域都扮演着 重要角色，这些领域的快速发展导致了在近些年内三维模型数量的急剧增加，尤其是如 今的i n t e r n e t 提供的三维模型海量数据库和三维物体扫描技术的成熟，导致了各类三维 模型数量的急剧增加，使人们迫切需要对三维模型进行有效的检索，因此三维模型检索 越来越受到研究人员的重视。三维模型检索的思想起源于三维模式识别，三维模型匹配 以及基于内容的图像检索。1 9 9 7 - 1 9 9 8 年，p a q u s t 、r i o u x t l 2 】等最早对基于内容的三维 模型检索技术进行研究，自1 9 9 9 年以后美国、德国、日本等国的研究人员相继投身于这 个研究领域，提出了许多新的检索技术，并且开发了一些基于内容的三维模型检索实验 系统。但是总的来说，目前对三维模型检索技术的研究还处于起步阶段，许多问题有待 进一步研究解决。 三维模型检索技术可以分为基于文本的检索和基于内容的检索。虽然基于文本的检 索技术非常成熟应用也很广泛，但是基于文本的检索技术大多并不太适用于三维模型的 检索，因为基于文本的检索技术的主要手段是目录浏览和文本关键字检索这两种，其不 足之处不仅在于仅仅使用几个关键字难以充分地描述复杂的三维模型及其相关场景，而 且关键字的选取还由于某些原因使其具有一定的片面性和主观性，导致其在三维模型上 第一章绪论 的检索效率与可靠性都较低；基于内容的三维模型检索技术首先是从三维模型自身大量 的数据中提取出三维模型的某种特征，以此建立起三维模型相应的多维信息检索索引， 然后在其特征空间中计算待检索三维模型与所有目标三维模型之间的相似程度，从而达 到对三维模型数据库进行检索的目的。基于内容的三维模型检索是通过对人类视觉感知 的相似性匹配来检索所要寻找的模型，相比基于文本的检索技术来说这更接近于人们在 实际生活中靠视觉印象来分辨物体是否相似的方式。因此基于内容的三维模型检索系统 更胜一筹。 基于内容的三维模型检索的关键技术主要包括【3 】：模型坐标的标准化与预处理，特 征提取及索引，相似性匹配以及检索界面四个部分，其中的核心技术是通过某种算法提 取模型的某种特征来表示三维模型，该特征需要具有平移、旋转、缩放的不变性，然后 通过对提取出的特征量的处理来实现对三维模型的检索。下图给出了一个典型的基于内 容的三维模型检索技术的系统框架【4 】。 副瓣 转匿撵取 爱索喇 搠融麓彩罄翻肆嘲 - 。：。- 。l 文奉1 ) 键字1 二维持薤i 。 i 维特舀 。 剃嬲甲峄掣 籀户币蠖逛虱氢壹 撩霉绉累籍出 图l 三维模型检索的系统框架 基于内容的三维模型检索技术主要可以分为三大类：基于形状的检索技术，基于拓 扑结构的检索技术，基于图象比较的检索技术。其中基于形状的检索技术是当前研究的 主流，基于形状的检索技术的优点是对模型整体形状进行比较，忽略细节上的不同，比 较接近人的视觉识别。根据使用方法的不同，基于形状的检索技术主要分为空域检索技 术和频域检索技术1 6 】。 空域检索技术是一种最直接的检索技术，它主要又可分为：基于统计学的，基于视 2 西北大学硕士学位论文 觉的，基于几何形状的算法。基于统计学的算法是通过统计数据来描述模型的形状特征， 它着重模型的整体形状特征，忽略模型的局部特征，比较符合人类的视觉感知；基于视 觉的描述算法的关键是怎样用二维图形来描述三维模型；基于几何形状的算法通过模型 的几何特征作为模型的全局特征描述算子。当前国内外对检索算法主要的研究成果有 o s a d a 7 8 1 提出的形状分布的检索算法，c h e n l 9 】的基于视觉的l f d 检索算法，k o l o n i a s 1 0 】 基于几何形状和表面颜色、材质的检索算法，o h b u c h i 1 1 d 2 】定义的形状函数构造直方图 的检索算法，a n k e r s t t l 3 】提出的对模型切分后生成直方图的检索算法等等。 。 本文用于比较的两个基于统计学的三维模型检索算法是：o s a d a t 7 - s 】提出的形状分布 的检索算法和采取a 1 k e r s t 【1 3 】提出的的三种模型切分方式中最好的一种切分方式组 合切分生成直方图的检索算法。 1 2 本文的核心工作 基于统计学的三维模型检索算法一般对模型的要求不高，计算起来不复杂，且算法 易于理解，并且具有很好的几何不变特性，其忽略三维模型的局部特征，适合于对三维 模型进行全局匹配。本文的核心工作是在文 1 6 】关于三维匹配点算法研究的基础之上提 出了一种新的基于统计学的三维模型检索的算法：基于相对角度直方图匹配的检索算 法，在此基础之上本文又提出了另一种新的基于统计学的三维模型检索的算法：基于聚 类分析的检索算法。 基于相对角度直方图匹配的检索算法的基本思路是：首先计算表面所有点相对于模 型的主成份标架的相对角度分布作为点匹配的主要依据，随后将相对角直方图的分布作 为模型的全局几何特征量用于三维模型的检索。由于角度分布的几何特性，使得角度特 征量具有较好的平移不变性、旋转不变性、缩放不变性；该算法的另一个特点是：有时 用户希望检索到的模型可能没有被排在检索结果的前几位，在传统方法中只能对模型进 行一次检索，而在该算法中可以通过对角度更进一步细化分区，使得算法对于模型的形 状更加敏感。 但是由于基于相对角度直方图对于每一个模型来说需要考虑模型上每一个点与其 它所有的点之间的角度关系，那么必然导致对于每一个模型来说所形成的直方图的维数 较大，所以基于降维的考虑本文又提出了一种基于聚类分析的检索算法，其基本思路是： 3 第一章绪论 首先对模型的表面点进行聚娄，随后再将表面点中聚于同一类的点所对应的相对角直方 图中的行作为同一类，然后对每一个类中所有的行取算术平均值，这样会使得之前在同 一个类的多条信息只需要这样聚类后的一条信息就能表示了，将采取聚类后的每条信息 结合在起构成一个新的直方图，最后将此直方图作为模型的特征量用于模型的检索。 虽然聚类后的检索效果有点不如聚类之前，但是由于聚类使得模型特征量的维数下降的 很快，这样不仅减少了模型特征量在计算机中的存储空间，而且大大的降低了算法的时 间复杂度，从而使得模型检索的速度得到了大幅地提高。 本文所有的算法与程序都是本人用m a t l a b 71 编写的，并且都在m a t l a b 71 下调试运 行成功。本文使用的三维模型检索系统的界面是本校信息科学与技术学院的老师所设计 开发的，下图是该i 维模型检索系统的主界面。 霸网国圆 匮 医i 匮l 纛l 医i 黑 图2 模型检索主界面 1 3 本文的内容安排 本文总共分为四章，具体内容安排如下 第_ 章：首先介绍了研究背景与相关知识，然后介绍了本文的核心工作和内容安捧。 第二章：详细地介绍了本文所设计的第一个三维模型检索算法：基于相对角度直方 图匹配的检索算法。 第三章：详细地介绍了本文所设计的另一个三维模型检索算法：基于聚类分析的检 医一医i医一匮愿一 两北大学硕上学位论文 索算法。 第四章：介绍了算法性能评价的相关标准，并对本文所采用的标准进行了详细的叙 述，用其对文中提到的四种算法进行了比较，从实验结果与算法性能来看本文提出的两 种三维模型的检索算法对于大多数模型来说在检索效果与算法性能上都比o s a d a 提出的 形状分布的检索算法和a n k e r s t 提出的对模型切分后生成直方图的检索算法要好。 结论与展望：对本文的主要贡献与创新点进行了总结，并对需要进一步研究的问题 进行了展望。 第二章基于相对角度直方图匹配的检索算法 2 1 引言 第二章基于相对角度直方图匹配的检索算法 本章提出了一种新的基于统计学的三维模型检索算法：基于相对角度直方图匹配的 检索算法。该算法仅仅需要提取模型表面点上每一个点与其他所有点之间的角度关系来 作为模型的特征量，由于角度自身的特殊性，使得提取的模型特征量充分满足了模型特 征提取时要求的：平移不变性，旋转不变性，缩放不变性，具有较高的噪声鲁棒性。 2 2 模型的相对角度与相对角度直方图 2 2 1 模型相对角度的定义 冯筠教授于2 0 0 7 年提出模型的相对角度分布特征量【1 6 1 ，并将其应用于特征点的匹 配，本章的工作是将模型的相对角度分布的概念应用于三维模型的检索。下面是对模型 相对角度定义的简述： 模型r 由一个顶点集v 和一个路径集尸所表示，其中s 为模型点的个数，f 为模型 面的个数。设u 是模型的第f 个顶点，其中叶矿，( 1 f s ) ；p l ( v t 。，飞) 是模型表面的 第，条路径，其中p t p ( 1 ，f ) ，在三维欧氏空间中，顶点的坐标为b = ( x i ， ，乙) ， 记模型的质心为d ，则o = ( 二1 ，) s 通过坐标的平移，可以把原坐标系的原点平移到 模型的质心0 ，把u 看作一个三维随机变量，那么由此平移变换会形成一个正定协方差 矩阵，记为c 定义1 设 如丸0 为c 的特征值，e i ，p 2 ，e 疗为其对应的标准正交特征 向量，则称e ，为原顶点集y 的第f 个主轴向量( 简称主轴) ，汪1 ，n 。 计算丑，i = 1 ，2 ，3 ，及其对应的标准正交特征向量q ，扛1 , 2 ，3 记e = ( e le ：，巳) ，从而有 6 两北大学硕士学位论文 令u = e 。( y o ) ，则 e ：r ? ： f 00 c o v t v , , u a v 心碣她。= 忙等 于是c o v ( u ) = e c e 这里采用前三个主轴去构建此三维模型的相对参考标架，即通过使用e l ，e 2 ，e 3 作为 新的坐标轴来构建起三维模型的相对坐标系，并且新坐标系的原心位于此三维模型的质 心。 定义2 设模型表面的顶点u 与顶点_ 所形成的向量与第一主轴之间的相对夹角 为： o j ( v f ) = a l c c o s 其中- _ - i t = _ 一_ ，反为第一主轴，为点乘，| y - f 为向量的长度，瞄i 为第一主轴 的长度。 记u 与组成的平面分别为i - i 。：，记u 与组成的平面分别为f i 。，从而可以通 过这些平面来确定相对角度的符号，显然对于n 。：，1 7 。，来说分别有e 3 ( 坼一d ) = 0 ， 乞。( 一o ) - - 0 从而顶点坼与顶点所形成的向量与第一主轴之间的夹角经过变换后的 定义如下： 7 一、， 寸u | t u 一iijiii 斗堕 ，。l # $ 基于相对角度直方目的检索算# q “一0 o 岛“一0 o 5 “一0 = 0 ，q “0 s o 通过上面的定义将顶点e 与顶点n 所形成的向量与第一主轴之问的夹角值由【0 ，口 扩展为【一f ， 为了把角度扩展到【o ，2 z 】上，本文定义顶点q 与顶点叶之问的角度为： = 2 a - + o l 笞黼 由于对于角度来说具有平移，旋转，缩放的不变性，所以经过上面的转换后，对于 此模型的相对参考标架而言，其具有平移，旋转，缩放的不变性。相对于其它的几何属 性来说，这是角度自身所具有的特性。 2 22 模型相对角度直方图 本文将p a n g s 的角度区间 o ，2 口 划分为k 个等同的区日j ，通过定义2 的角度定义的 计算可以得到对于每一个顶点来说它和其余所有的点与第一主轴的角度值，这些角度值 都会落到这k 个等分区间的某些区问内，从而对于每一十模型的每一个顶点来说都有一 个由这样的角度值所形成的直方图，将该模型的所有顶点的直方图组合起来形成的新的 直方图作为该模型的特征量，此时可以把一个模型如上生成的角度苴方图看作是此模型 的概率分布。由此不难看出p a n g s 。的概率分布表明了一个模型的每一个顶点和其余所 有点的空间关系。这样，通过顶点的相同分布曲线可以描述出模型的形状性质。下图足 几个不同三维模型发其对应的相对角度直方图。 西北 学砸十学位论文 2 3 相似度计算 图3 模型及其相对角度直方圈 通过比较两个模型的相对角度直方图的相似性来判断两个模型是否相似，即计算两 个模型的相似度。 设为第一个模型的相对角度直方图，y 为第二个模型的相对角度直方图，x 。表 示第一个模型的相对角度直方图中娃在第f 行第，列的值，匕表示第二个模型的相对角 度直方图中处在第f 行第，列的值， ，分别表示两个模型点的个数。 计算相对角度直方图相似度的步骤：( 直方图所采用的角度值等分k 为3 6 ) 1 ) 对两个模型相对角度直方图的数据进行归一，夸，= 肖，m ，= n ，则 置，的值均介于。到1 之间； 2 ) 计算第一个模型相对角度直方圈的每珩与蔸二个模型相对角度直方图的所有 山一山一幽 第二章基于相对角度直方目配椅素算法 行之间的距离，采用绝对值距离翟。i ，i ，一，f 分别是第个模型与第二个模型相 对角度直方图中的任意一行； 3 ) 对于第一个模型相对角度直方图中的每一行采用上面的距离公式来计算它与第 二个模型相对角度直方图所有行之间的距离中的最小值，记为m i n 阮j ，1 s i m ： 4 ) 计算以上所有最小值的平均值，印d 喈= r 二用加仁l 肿f ： 5 ) 计算第一个模型与第二个模型的相似度s i m = ，一a v e 2 。 s i m 越大说明两个模型的相似程度越高。 下图是个三维的车模型m 1 5 1 7 与其余所有三维模型的相似度前1 8 位的结果图。 图4 车模型佃1 5 1 7 ) 与其它所有模型的相似度前1 8 位 下国显示的是上面的车模型根据相似度计算的结果的部分检索结果及其相应的相 对角度直方图。 币面口 西北人学硕0 学位论空 车( m 1 5 1 7 )与车( m 15 1 7 ) 最相似的模型 第一个不是车的模型 圜5 相对角度直方图算法下的一个模型的部分检索结果及其直方图 24 本章小结 本章提出了一种新的基于统计学的三维模型检索算法：基于相对角度直方图匹配的 检索算法。首先给出了模型相对角度的定义，然后介绍了模型相对角度直方图的构成， 并且列出了部分模型的相埘角度直方图，最后给出了进行模型相似性匹配时相似度计算 的详细步骤。从相似度结果来看该算法具有较好的检索效率和精度，相对角度分布作为 特征量能较好的描述模型的几何形状，但是由于该算法对于每一个点来说都需要考虑到 与其他所有点的关系，因此导致模l g 在该算法下形成的特征量维数较大，模型榆索的速 度较慢，从而我们需要通过一些方法来对模型特征量的维数进行降维，以加快模型检索 的速度。 第三章基于聚类分析的榆索算法 3 1 引言 第三章基于聚类分析的检索算法 由上一章可知虽然相对角度直方图作为模型的特征量能较好的描述模型的几何形 状，但是由于该算法所对应的模型特征量维数较大，使得模型的检索速度相对较慢，本 章利用多元统计分析中聚类分析方面的知识来对模型特征量的维数进行降维，以加快模 型的检索速度。 3 2 聚类分析概述 人类认识事物、认识世界的一种重要方法就是将世界上的事物进行分类从中发现规 律，所以分类学很早就成为人类认识世界的一门基础学科。近几十年来，随着科学技术 的迅猛发展，人类对社会和自然的认识不断深化，观测手段日益精确化、数字化，分类 的要求越来越高、越来越细，以至于有时候只凭经验和专业知识不能进行精确分类。从 而数学这个有力的工具被引进分类学中，形成了数值分类学，后来多元统计分析方法也 被用于分类学而逐步形成了聚类分析这一方法。 聚类分析是把某种性质比较相近的事物归为一类，同时把性质不相近的事物归为不 同的类的一种方法。其基本思想是在样本之间定义距离，在变量与变量之间定义相似系 数，距离或相似系数代表样品或变量之间的相似程度。按照相似程度的大小，将样本( 或 变量) 逐一归类，关系密切的类聚集到一个小的分类单位，然后逐步放大，直到所有的 样本( 或变量) 都聚集完毕，使得在同一类内的样本( 或变量) 具有较高的相似度，而 在不同类内的样本( 或变量) 具有较低的相似度，是否相似的度量是根据样本( 或变量) 自身描述属性的值来确定的。由于聚类时事先并不知道样本( 或变量) 的相关类信息， 需要以某种度量方式为标准来将所有的样本( 或变量) 划分到各个类中，因此聚类分析 又称为无监督的学习。聚类分析的目的就是获得能够反映维空间中的所有样本( 或变 量) 最本质的“类”的性质。这一步除了集合的知识外不需要考虑任何的领域知识，也 就是不需要考虑样本( 或变量) 在其领域中的特定含义。数学方法的聚类是建立在各个 事物关于其性质变量的测量数据基础之上的，即利用这些数据的内在联系和规律来进行 1 2 两北大学硕十学位论文 分类。目前关于聚类的方法有很多，比如：系统聚类，k 一均值聚类，快速聚类、图论 聚类法等。 下面介绍聚类分析中涉及到的相似系数和距离的定义。 3 2 1 相似系数 当对朋个变量进行聚类时，用相似系数来衡量变量之间的相似程度。一般若勺表示 变量置，x j 之间的相似系数，需要满足： 1 ) m 1 且珞= l ： 2 ) r o = 1 置= c x j ( c 0 ) ： 3 ) 吩= 0 勺的绝对值越接近1 ，说明变量五，的关联性越大。 设变量墨的观测值为( 而，而一，矗，) r ，变量一的观测值为( 而，吃，嘞) r ，则变量 置，的相似系数为： 白2 ( 一i ) ( 砑一动 k = l 其中i = 丢喜，_ - - = i 1 荟 3 2 2 距离 设力个样本的多元观测数据为： 置= ( x i l ，薯2 ，) ，i = 1 , 2 ，n 这时每个样本可以看成m 维空间中的一个点，刀个样本组成m 维空间中的珂个点， 使用点与点之间的距离来衡量各样本之间的相似程度。 设露( 五，一) 是样本五，之间的距离，一般要求它满足以下条件： 第三章基于聚类分析的检索算法 1 ) d ( 置，一) 0 ，且d ( 墨，) = 0 营置= 一： 2 ) d ( 五，一) = d ( ，置) ： 3 ) d ( 置，x j ) d ( 置，x t ) + d ( x t ，爿- ) 下面介绍几种聚类分析中常用的距离： 1 )m i n k o w s k i 距离 d ( 置，x j ) ：( 兰1 一l p ) l p 当p = 1 时d ( 置，t ) = i 靠一b i 称为绝对值距离。 2 ) 欧氏距离 几一 d ( 五，) = ( 矗- x j t ) 2 yt = l 3 ) 切比雪夫距离 d 嶙i ，x j 卜m l 堑a s x p l x j t x 口 k 一均值聚类算法是一种被广泛应用于科学研究和现实生活中的经典聚类算法，该 算法的优点是简单、易行、高效、时间复杂度为d ( 胛) ，并且适应于处理大规模的数据集。 本文所采用的聚类方法就是k 一均值聚类法。 3 3 尽均值聚类的算法描述 k 一均值聚类法又称k m e a n s 聚类法。假设= f i n 个样本而，现将n 个样本划分为 k 类，分别用墨，托表示令m 是第f 类置中的样本数目，是这些样本的均值即第 f 类五的聚类中心，函数d ( 一，) 为聚类时样本与一之间的距离，k 一均值聚类法的 步骤如下： 1 ) 随机选择k 个样本作为初始聚类中心记为：m a ，m k ： 1 4 西北大学硕上学位论文 2 ) 如果d ( ，所p ) d ( 一，m ，) ，l p k ，i = l ，后，则分配誓到第p 类中： 3 ) 重新计算每个聚类的中心：m j = ( 碱x ) j ，i = 1 ，k ： 4 ) 重复步骤2 ) 和3 ) 直到m ，i = 1 ，k 不再变化 3 4 确定最佳的聚类数 3 4 1k m e a n s 函数的用法 m a t l a b 的统计工具箱中实现上述聚类法的函数是k m e a n s ，在应用k m e a n s 时需要用 到函数s i l h o u e t t e ，它们俩的调用语法如下： i d x = k m e a n s ( x , c l u n u m , d i s t a n c e ，c i t y 夕，s i l h = s i l h o u e t t e ( x , i d x , c i t y 夕 其中参数x 为模型的数据矩阵，c l u b u m 为聚类数目，d i s t a n c e 与c i t y 表示所采用 的聚类距离公式为绝对值公式，返回值i d x 是一个n x ，的向量，包含了x 中每个变量的 类的编号，s i l h 是一个n x j 的向量，包含了每一类中各点之间的相关程度，如果是正数 说明此点在其所在类中与其余点是正相关，如果是负数则是负向关，即此点与本类其余 点的相关性还没有与别的类中的点的相关性强。 3 4 2 最佳聚类数的选择 对于k 一均值聚类法来说，最关键的是如何选择好聚类数k 来实现对样本的最佳聚 类，本文选择m a t l a b 的统计工具箱提供的s i l h o u e t t e 函数来确定最佳的聚类数。根据 s i l h o u e t t e 函数的返回值s i l h 的信息，本文选择在聚类范围中正相关性最强的那一类作为 此次聚类中最佳的聚类，具体算法的概述如下： 1 ) 选定初始聚类的最小聚类数和最大聚类数，分别记为m i n 和m a x ； 2 ) 记下每次从最小聚类数到最大聚类数之间循环聚类时s i l h 中所有元素值的 和，记为：j f 碱，f = m i n , ，m a x ； 3 ) 取s 诹，f = m i n ，m a x 中的最大值所对应的f 值，即为该模型的最佳聚类数。 采用此算法对于每个模型来说它的最佳聚类数都是由计算机根据每个模型的特征 1 5 第i 章基于幕英分析的检索算 击 来自动选择的。下图为本文数据库中车模型m 1 5 2 0 根据上述算法确定的最佳聚类数时 s i l h o u e t t e 值的情况与模型的聚类平面截图。 模型m 1 5 2 0 最佳聚类数为4 时的s i l h o u e t t e 值最佳聚类数为4 时的聚类平面截图 圈6 模型m 1 5 2 0 量佳聚共羲时的s i l h o u e t t e 值与其聚类平面蕾圈 3 5 两种不同的聚类途径 对于每个模型来说它的原始的数据点与结果直方图的维数都很大，并且从这两个出 发都能达到对模型的特征量进行聚类，所以本节从这两种不同的途径出发来对模型的特 征量进行降维，第一种聚类途径是对图像模型的原始数据点聚类后，然后将聚类的结果 映射到模型的相对角度结果直方国中，采取一定的措施来达到对模型特征量的降维，第 二种聚类途径是对图像模型的相对角度结果直方图直接聚类，然后采取一定的方法来达 到对模型特征量的降维，虽后对采取这两种途径降维后的结果进行了比较。 3 51 第一种聚类途径 1 ) x 为模型的原始数据矩阵，采用上述的最佳聚类数确定的方法，可以得到原始数 据聚类的最佳聚类数b e s tc l u ； 2 ) 利用i d x = h n e a n s ( x , be s t 出 a i s t a n c e , c i t y j ，可以得到对于原始数据在最佳聚 。1。 目n 太学砸十学位论立 类数时每个变量的类编导 3 ) 将原始数据中的第，个点与模型的直方崮中的第i 行一一对应，这样就可以将2 1 中的每个变量的类编号对应到模型的直方图中作为相麻的行的编号： 4 ) 将3 ) 中行编号相刷的直方圈的行中元素对应相加再除以对应相同编号的总数， 作为这个编号所代表的类的直方图； 5 ) 将由4 ) 形成的b e s t 幽t 行直方图作为该模型新的的直方图将陵卣方图作为模 型新的特征摄。 采用上述方式对其中的两个模型的聚类结粜( 平面图) 如f ： ( a ) 人脸模型原始数据浆娄结果 ( b ) 车模型原始数据聚类结果 图7 第一种聚英造径结果圈 352 第二种聚类途径 i ) 为模型的结果直方图矩阵，采用上述的最佳聚类数确定的方法，可以得到结果 直方图聚类的最佳聚类数b e s tc l u ： 2 ) 运用i d x = k m e a n s ( x , , be s t _ c l u , d l s t a n c e , c i t yj ，可以得到对于结果直方图在最佳 f * 三章基f 聚擞分析的检索算 聚类数时每行的类的编号 3 1 将2 t 行编 q - 相n 的直方图的行中兀素对应相加冉除以对应相同编号的总数 作为这个编号所代表的类的直方图； 4 ) 将由3 1 形成的b e s tc l u 行的直方图作为该模珏! 新的直方图，将该直方圈作为模 型新的特征量。 因为之前我们关于主轴的选取和角度正负的判断使得以结果直方图聚类时模型是 先被分为两半以后再分别在这两半上进行聚类。此时采用上述方式对其中的两个模型的 壤类结果( 平面图) 如下 ( a ) 人腑模型直方图聚类结果 ( b ) 车模型直方圈聚类结果 圈8 第二种聚曩途径结果田 353 聚类前后的结果直方图比较 对于模型来说我们需要，解一下其聚类前后的结果直方幽的形态变化情况，下图展 示了一个模型的聚类前后结果直方圈，其中包括两种不同途径的聚类结果直方图，可以 看出采取第一种聚类途径所形成的模型结果直方蹦的形态更接近与模型聚类前的结果 l n 北大学l 位镕女 直方图的形态 分j 出留! 幽蚓 模型聚类前第种聚类途径第二，种聚类逢释 图9 聚粪前后模型的结果直方图 3 6 相似度计算 通过比较两个模型聚类后的直方图之间的距离来判断两个模型是否相似。假设x ，r 分别为两个模型果类后的结果直方图矩阵，以，分别为矩阵中的元素，则计算聚类后 直方图相似度的步骤为： 1 ) 耐两个模型聚类后的结果直方图中的数据进行归一，令x ，= 。m ，巧= n 其中m ，v 分别是两个模型点的个数，则x 。，巧的值均介于0 到1 之间； 2 ) 计算第一个模型聚类后的直方图巾每行与第二个模型的集类后的直方图中所 有行之间的距离，采用绝对值距离羔。j ，一巧，i ，f 分别是第一个模型，第二个模型中 聚类后的直方图中的任意一行： 3 ) 对于第一个模型蒙类后的直方图中的每行采用上面的距离公式来计算它与第 = 个模型聚类后的直方剧中的所有行距离中的最小值，记为埘加p l j ，l ! i ! b e s tm ，其 中b e s tm 为第一个模型的最佳聚类数； 4 ) 计算以上所有最小值的平均值，日f la v g = r 等m i n ( x , ) ) b e s tm ； 5 ) 计算第一个模型与第二个模型的相似度s i m = 1 一a v g 2 。 s i m 越大说明两个模型的相似程度越高。 f 图足一个三维的车模型m 1 5 1 7 在采取第一种聚类途径的情况下与其余所有的三 第三章基于集类分析检索算法 维模型的相似度前1 8 位的结果图。 圈1 0 寨类后车援型( m 1 5 1 7 ) 与其它所有模型的相似度前t 8 位 37 聚类效果比较 通过对所有模型的试验可知，采取第一种聚类途径算法即先对原始数据聚类( r a c l 算法的性能比采取第二种聚类途径算法即对相对角度结果直方图聚类f r a h c l 算法的性 能要好，f 图是本文选择的其中一类采取两种聚类途径后检索结果最为接近的模型对于 两种聚类途径算法采取算法性能评价标准中的p r e c i f i o n - r e c f l l 曲线比较图( 关于该曲线 将在下一章进行介绍) ，从p r e c i s i o n - r e c a u 曲线比较图来看第一种聚类途径算法的性能 比第二种聚类途径算法的性能要好。 圈1 1 两种方式聚类结果的p r e c i s i o n - r e c a l l 曲线 两北大学硕十学位论文 3 8 本章小结 本章对聚类分析做了简单的介绍，详细介绍了聚类分析中的k 一均值聚类法，并对 在此聚类法的基础上如何确定模型最佳的聚类数进行了描述，然后将此聚类法应用到了 本文的三维模型检索中，并对不同的聚类途径和聚类前后模型的检索结果进行了比较， 从聚类前后直方图的相似程度与算法性能的好坏程度两方面来看，得出了对图像模型的 原始数据聚类这个途径所取得的结果较为理想。采取聚类后模型的特征量维数得到了降 低，这样不仅会使得模型在数据库中存储的信息量大量减少，从而节省了计算机的存储 空间，而且对于采取聚类的算法相比于基于相对角度匹配的算法来说，前者的算法时间 复杂度会比后者的降低很多，从而会加快模型的检索速度。通过第一种聚类途径算法下 的相似度结果可以看出采取此方法聚类后的算法的检索效果是令人满意的，也就是说该 检索算法是可行的。 2 1 第阴章实验结果的比较与分析 4 1 引言 第四章实验结果的比较与分析 前面分别介绍