（计算机应用技术专业论文）点云和网格模型的建立及形状分布检索算法研究.pdf

摘要 随着三维激光扫描仪等三维数据获取技术的发展，三维模型建模技术已成为研究热 点。基于点云和网格表示的三维模型广泛地应用于计算机辅助设计，虚拟现实，可视化 等领域。三维模型的特征提取是三维模型检索中的一个首要解决的问题和关键技术，直 接影响着三维模型检索的效果。本文以基于点云和网格表示的三维模型为研究对象，研 究了点云和网格模型建立的关键技术，针对网格模型特征提取，提出了改进的点云模型 简化算法和形状分布检索算法。本文主要研究内容概括如下： ( 1 ) 点云和网格模型的建立。以三维扫描获得的点云数据为基本输入，经过对点云 数据配准，去噪，修复等预处理，采用基于点云的表示，实现点云模型的建立；其次基 于点云数据的表示对表而进行网格重构来构造网格模型，生成的网格模型需要进行简化 来减少模型的存储量。 ( 2 ) 提出了一个基于k 邻域密度的点云简化的改进算法。该算法首先对k 邻域中点 到中心点的距离进行判断，距离大于平均距离的点则保留，否则采用法向量误差的方法 进行衡量是否删除点。该方法事先控制简化误差，在曲率变化大的地方不易改变模型的 形状。实验证明该方法对曲率人的模型进行简化后能够比较好的保留细节部分的信息。 ( 3 ) 提出了一种基于加强三维模型细节的形状分布检索算法。该算法首先将经过预 处理的模型分割为n 个子模块并分别进行特征提取，然后构造每个子模块的形状分布直 方图，通过比较予模块的相似度来计算模型的相似度。该算法相比形状分布算法比较准 确地计算m 了模型问的相似性，有效地提高了细节的分辨，解决了外形相近但细节不同 的问题。 ( 4 ) 结合三维模型建模实际需要，以v i s u a lc 什6 0 和o p e n g l 图形库为工具，设计 并实现了一个基了二点云和网格表示建立三维模型的原型系统。该系统实现了数据读取， 点云模型预处理，三维锓示，基于点云的网格重构，网格简化，网格模型的特征提取等 功能，并且操作简便，建立的模型效果较好。 本文得到8 6 3 国家重点基金项目( 2 0 0 8 a a 0 1 2 3 0 1 ) - - 三维模型快速建模和网络智能 检索技术”的支持。 关键词：点云模型，网格模型，特征提取，点云简化，形状分布算法 r e s e a r c ho np o i n tc l o u da n d g r i dm o d e lc o n s t r u c t i o na n d s h a p ed i s t r i b u t i o nr e t r i e v a l a b s t r a c t w i t ht h ed e v e l o po f3 dd a t aa c q u i s i t i o nt e c h n o l o g ys u c ha s3 dl a s e rs c a n n e r , t h es t u d yo f 3 dm o d e l i n gt e c h n o l o g yi sm o r ea n dm o r ei n t e r e s t e d 3 dm o d e lh a sv a r i e t y so fr e p r e s e n t a t i o n w a y s ，e s p e c i a l l y , 3dm o d e lb a s e do np o i n tc l o u da n dg r i di sw i d e l yu s e di nc o m p u t e r - a i d e d d e s i g n ，v i r t u a lr e a l i t y , v i s u a l i z a t i o na n do t h e rf i e l d s w h i l e ，t h e3 dm o d e lf e a t u r ee x t r a c t i o ni s b a s i cp r o b l e m sa n dk e y t e c h n o l o g i e sw h i c ht os o l v e3 dr e t r i e v et e c h n o l o g y , a n dt h e3 dm o d e l f e a t u r ee x t r a c t i o nh a v ead i r e c ti m p a c to n3 dm o d e lr e t r i e v a lr e s u l t sd i r e c t l y t h i st h e s i sf o c u s e so np o i n tc l o u da n dm e s ho f3 dm o d e l s ，w h i c hi n c u l d et h e r e p r e s e n t a t i o na n dm o d e l i n gt e c h n o l o g y , t h e 西dm o d e lo f 3 dm o d e lf e a t u r ee x t r a c t i o n t h e p o i n tc l o u ds i m p l i f i c a t i o na n ds h a p ed i s t r i b u t i o na l g o r i t h mi si m p r o v e di nt h i sp a p e r t h i s p a p e rm a i n l yi n c l u d ef o l l o wa s p e c t s ： ( 1 ) c o n s t r u c t i o no fp o i n tc l o u da n d 酣dm o d e l f i r s t ，w ei m p o r tt h ed a t ao fs a m p l i n g p o i n t so fr e a lo b j e c t ss u r f a c eb yu s i n g3 dl a s e rs c a n n e r , a n dp u tp o i n tc l o u dd a t ap r e p r o c e s s ， s u c ha sd a t ar e g i s t r a t i o n ，n o i s er e m o v a l ，r e p a i rp r e t r e a t m e n ta n ds oo n ；l a t e r l y i ta c h i e v ep o i n t c l o u dm o d e lb a s eo nt h er e p r e s e n t a t i o np o i n tc l o u d ；t h e n ，i tc o n s t r u c tt h eg r i dm o d e lb a s e d o np o h nc l o u dd a t aw h i c hr e c o n s t r u c t i o nt h es u r f a c em e s hm o d e l ，a n ds i m p l i f i e dt h es i z eo f g r i dm o d e li no r d e rt or e d u c et h em e m o r y ( 2 ) w ep r o p o s ean e ws i m p l i f i c a t i o na l g o r i t h mf o rp o i n tc l o u dm o d e l s ，w h i c hb a s e do nk n e i g h b o r h o o dd e n s i t ys i m p l i f i c a t i o na l g o r i t h m f i r s tt h ea l g o r i t h mj u d g et h ed i s t a n c ea b o u t p o i n to ft h ekn e i g h b o r h o o dt ot h ec e n t e r , i ft h ed i s t a n c el a r g e rt h a nt h ea v e r a g ed i s t a n c e ，t h e p o i n ti sr e t a i n e d o t h e r w i s e ，v e c t o re r r o rm e t h o di su s e dt om e a s u r ew h e t h e rd e l e t et h ep o i n t t h i sm e t h o dp r e c o n t r o lt h ee r r o rw h i c hi ss u i t a b l ef o rn o n u n i f o r m p o i n tc l o u dd a t a , e s p e c i a l l yi ti sn o te a s yt oc h a n g et h es h a p eo ft h em o d e li nl a r g ep a r t so ft h ec u r v a t u r e c h a n g e e x p e r i m e n ts h o w st h a tt h i sm e t h o dc a nk e e pt h ed e t a i l so fm o d e l si n f o r m a t i o nw h e n i ss i m p l i f i e dt oi nt h ec u r v a t u r eo ft h em o d e l ( 3 ) an e ws h a p ed i s t r i b u t i o nm e t h o dw a sp r o p o s e di ti sb a s e do ne n h a n c i n g3 dm o d e l d e t a i l f i r s t ，t h ep r e p r o c e s s e dm o d e lw a ss e g m e n t e di n t oas e to fb l o c k s ，s e c o n d ，t h e s eb l o c k s w e r ep r o c e s s e dt of e a t u r ee x t r a c t i o ns e p a r a t e l ya n dt h ef e a t u r eh i s t o g r a m sw e r ec o n s t r u c t e d f o re a c hb l o c k f i n a l l y , a c c o r d i n gt oc a l c u l a t i n gt h es i m i l a r i t yb e t w e e nb l o c k s ，t h es i m i l a r i t y o f3 dm o d e l sw a sa c h i e v e d t h i sm e t h o di sm o r ea c c u r a t e l yt oc o m p u t et h es i m i l a r i t y i i b e t w e e nm o d e l st h a ns h a p ed i s t r i b u t i o n a n dt h ed i s t i n g u i s h m e n to fd e t a i l si si n c r e a s e d i t r e s o l v e st h ep r o b l e mo ft h es i m i l a rs h a p eb u td i s s i m i l a rd e t a i l ( 4 ) b e s i d e st h e o r yr e s e a r c ha n dt h ep r a c t i c a ln e e d so f3 dm o d e l i n g ，w eb u l i tap o i n tc l o u d a n dg r i do f3 dm o d e lc o n s t r u c t i o ns y s t e m b yv i s u a lc + + 6 0a n do p e n g l3 dg r a p h i c s l i b r a r yf o rt h ee s t a b l i s h m e n t t h i ss y s t e ma c h i e v e dm a n yf u n c t i o n s ，s u c ha si m p o r t i n gd a t a , p r e p r o c e s s i n gp o i n t c l o u dd a t a , d i s p l a y i n g3 dm o d e l ，r e c o n s t r u c t i o n i n g p o 缸d a t a , s i m p l i f y i n gm e s ho f3 dm o d e l ，f e a t u r ee x t r a c t i o nf u n c t i o n sb a s e do nm e s ho f3 dm o d e la n d s oo n ，w h i c hh a v es i m p l eo p e r a t i o na n db u i l tb e t t e rm o d e l t h i sp a p e ri s s u p p o r t e db yn a t i o n a lh i g ht e c h n o l o g yr e s e a r c ha n dd e v e l o p m e n t p r o g r a m ( 8 6 3p r o g r a mn o 2 0 0 8 a a 0 1 2 3 0 11o f c h i n a k e y w o rd s ：p o i n tc l o u dm o d e l ，g r i dm o d e l ，f e a t u r ee x t r a c t i o n ，p o i n tc l o u ds i m p l i f i c a t i o n ， s h a p ed i s t r i b u t i o n i i l 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 墨差蓑妻蓑萎薹霎亍三整指导教师签名：_ 监 学位论文作者签名：赵丝垦指导教师签名： f 銎! j 堕蒌 砂f 。年f 月2 , oe l纠d 年6 月弘日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其它人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：哆皖 p o 年，月沙e l 西北丈学硕士学位论， 第一章绪论 1 1 选题背景及研究意义 近年来，三维模型已经成为继声音，图像，以及视频等传统多媒体之后的又一种形 式( 图1 ”。三维模型以更加生动，立体，丰富，全方位的物体的细节信息的表达运渐取 代传统的基于二维图像的表现方式，受到了研究者们的广泛的关注，且二维模型的应用 已经深入到人们生活的各个领域，例如采用三维数字扫描技术为基础的三维模型重建和 修复技术可以帮助历史文物返回原貌；以三维模型为主的游戏被深受r 大人们的喜爱； 基于三雏几何模型豹产品已经逐渐取代二维设计和常规的实验手段，在上业界获得广泛 应用；使用三维模型做出柬的影视特效，给人们带柬了不| | 司的视觉冲击，去年的欧美 片阿凡达在全球引起了臣大的轰动和成功，票房高达2 5 亿美元，可见人们的喜爱程度。 总之兰维模型已毵杠人们生活中的各种邻域产生了深远的影响，二维模型建模技术也 已经成为计算机研究t 作者们关心和关注的研究方向。 r “嘲蜘一- _ 竺譬 ? s j 、 i 。 警 r 1 _ _ 卜一r 一。1 。辋b = 图 图1 1 多媒体发展圈 曰前三维几何模犁有多种表现方式且一直在发展肖叶1 ，主要的表现形式包括：非均 匀有理b 样条曲面【n u r b s ) 、隐式曲哑、网格模型，点云模型，体素模型，解析模型， 其中隐函数| i i 面、参数曲面、细分曲面、多边形嘲格( m e s h ) 和点几何表示等称之为边界 表示法。箨类形状表示方法备有优缺点在不同的应用领域摹不同的表现形式备具有优 势，使得二二维几何模型的几种表现形式长期并存。本文重点研究点云模型和网格模型( 如 罔12 ) 。 * t 绪论 懑 叠。j 浮籍。 ( 酊几何模型( b ) 点云模型( 时阿格模型 图1 2 两种袁示的三维模型 由】。计算机图形学的迅速发展，激光三维数据采样技术日益完善以及硬件设备的价 格的下降，人们对三维模型建模的需求也是闩益增强。传统建模工具如a u t o c a d 3 d m a x ，m a y a 等，目前已经逐渐不能满足人们对复杂曲面物体的建模需要，斯不同于 传统的建模手段采用激光三维扫描仪柬获取物体的表面数据柬构造三维数字模型成为 当前最为合理和有效的方法。三维激光扫描技术可以直接得到真实物体表而的空间采样 点，利用点云数据可以重构出任意曲面这种建模方法速度快，精度商，真实感强，不 受表面复杂度影响，因此在很多邻域已经投入工程应用。 近年米构建三维模型主要采用对所研究的物体进行数据采样，使用三维扫描仪对 研究物体表面进行采样数据，但是有些场景生成的数据量是很惊人的，网格点的数目达 到了十亿的数量级。传统的方法是把采样点生成三角面片网格，但是传统的= 角而片网 辑不仅需要记录每个点的信息，而且还要记录点与点之问的拓扑关系，冈此消耗在每个 点的t 作时相对过大，这就使得现有的图形 作站无法实时显示这种规模的阿格，而由 于时问和空间的需求限制传统的网格简化疗法和渐进显示方法对规模超过几百万的网 格也不实用。 以点云数据表示的i 维模型作为一种新兴的表远方式成为了计算机图形学中的一 个新的热门研究领域。早在1 9 8 5 年l e v o y i i l 等人就提出了将点作为基本的绘制罔元，之 后研究以点为苯元的点i 模型的表示、处理、渲染、以及几何造型技术的学科被称为基 丁点的图形学( p b g ：p o i n t b a s e g r a g h y l 。 点百数据是通过二维 l 插技术莸取的模型表面的离散稠桁的采样点。基于点云表示 2 两北人学硕士学位论文 的模型不仅结构简单，而且不用记录点与点之间的拓扑关系，并可以表征出任意复杂的 物体表面，且精度比较高。以点云数据表示的模型可以满足细节层次绘制的需要，由于 细节层次绘制是从不同视点对模型进行多分辨率的要求，距离远的模型采用低分辨率， 近的则采用高分辨，满足此要求需要引入分层的数据结构，而三角网格之间的拓扑连接 信息不适合空间分层结构。由于三维激光扫描的数据量相当大，点云模型存在大量的冗 余数据，严重影响了后续的处理和造型，因此简化作为点云处理前的重要过程之一，在 基于点的图形学的研究都有着非常重要的意义。 目前三角形网格模型是三维模型中最常见的模型，以三角形网格表示也是三维模型 中最多的表现方式。三角形网格数学结构简单，其表示的模型可以在任意的角度观察， 方便编辑如变形，修改和裁剪等，且以点云和曲面表示的模型也可以根据一定原则转换 成为任意精度的三角网格模型，因此三角网格是一种非常灵活的表示形式。网格模型表 达了模型的表面的几何拓扑关系，和点云模型一样，任何三维几何模型在进行编辑，绘 制处理之前都要进行简化这个重要的步骤。网格模型通常由上万个甚至更多的多边形面 片组成，对多变形进行绘制，存储，运算需要大量的时间和内存。通常我们不需要网格 模型精细的显示，而且多变形网格经过简化后在远处能够很好的表征物体的形状，因此 简化后的网格模型可以更好的满足我们的实践要求。 三维模型的特征提取技术与描述研究如何从三维模型表达中提取能够反映高层语 义信息的特征表达。该技术早在多年前就已经被提出研究，但是由于当时一些相关技术 没有发展成熟，所以这项技术就停滞了。直n - 十世纪末，随着三维检索技术的出现， 三维模犁特征提取算法也成为了学者们研究的热门之一。三维模型特征特取是三维模犁 检索技术中最关键的一个步骤，它的好坏直接影响着模型检索的效率。三维模型存在多 种表示方式，如离散点云，多边形网格，体素，隐性函数等，但是目前还没有一种统一 的特征描述方法能适用于所有的三维模型表示方法。很多的模型特征提取算法只是针对 某种特定的模型表示方式。如2 0 0 1 年o s a d a f 2 】和s a u p e l 3 】等人所提出的特征提取算法 针对多边形网格表示的三维模型，m u k a i 4 】等人在2 0 0 2 年以c a d 模型作为研究对象提 出一种特征提取算法，s u n d a r 等人1 5 l 在2 0 0 3 年对体素表示的三维模型的特征提取进行 了研究，2 0 0 2 年o h b u c h i 6 1 等采用v r m l 模型作为研究对象。特征提取是i 维模型检 索l | 1 最关键的步骤，由于三维模型检索有着实际f 面广阔的戍用，吸引着越来越多的人加 入到对他的研究行列中。 3 第一章绪论 1 2 国内外现状 1 2 1 点云和网格模型的建立 ( 1 ) 点云曲面的表示 点云曲面的表示一方面为点云模型的处理和建模提供了基本的曲面结构，另一方面 使得计算机能够绘制出具有连续效果的点云模型。最简单的点云模型表示的方法是以单 个像素点表示的一个采样点，但是这种表示方法已经不能满足点云模型渲染的要求。 为了得到点云模型高质量的渲染效果，研究者提出了面向渲染的s p l a t s 表示的方式， z w i c k e r 最早提出了用于绘制目的s p l a t s 表示，s p l a t s 包含颜色，法向和形状因子等几何 信息，但是该种表示方式不能满足点云模型处理的需要，于是基于移动最d - - 乘表示 ( m l s ) 和p s s 的表示方法出现满足了这个需要，m l s 表示是通过加权最小= 二乘法逼 近给定邻域内的采样点构造局部曲面，连接每个点对应的局部曲面形成连续的表面模 型。该表示法由于绘制m l s 曲面需要大量的投影运算，效率比较低。 ( 2 ) 基于点云数据的曲面重构 通过对点云数据进行网格重构是建立三角形网格模型的方法之一，该方法的主要思 想是将模型表面的三维扫秒离散点进行三角化剖分，从而建立三角形网格曲面。点云的 表面重建算法的研究已经比较成熟，早在1 9 8 4 年b o i s s o n n a t 等人【9 】就提出了基于三维点 集的d e l a u n a y 三角剖分的重建表面算法，之后的研究算法则以d e l a u n a y 三角形剖分为 标准。 目前手要的三角化方法有：d e l a u n a y 三角化方法，直接三角化法，分段法，微切平 面逼近法。直接三角化法就是通过对将离散的三维数据点按一定的规则排序，然后经过 初始三角形选择，主三角性剂分，生成特征线，网格优化等步骤完成三角化。该方法是 算法简单，但计算量较大，对计算机的运算速度要求比较高；分段法首先是把数据分成 块，以什么样的原则对点云数据分块是算法的重点，然后对每个分块进行平面三角网格 剖分，最后采用三角网格融合等技术将网格片拼接成一体，从而实现对复杂曲面的i 角 网格剖分；1 9 9 2 年h o p p e 等人i io j 提出了一种基于离散点进行表面重建的算法，该算法 首先根据散乱点集建立点到未知的待重建曲面问的符号距离踊数，然后利用m c 算法输 出距离函数的乏角化模型，该方法取得了很好的重建效果；之后b a j a j 等人【l l 】在1 9 9 5 年改进了距离函数的构造方法，即采用口形状来构造：o b l o n s e k 和g u i d l l 2 】在1 9 9 8 年改 进并提出了一种快速的表面重建方法，缺点足对采样数据的质量有很高的要求，因此不 4 两北大学硕士学化论文 能广泛的应用。上述这些算法对散乱的点云集进行三角化时，虽然结果并不是最优的， 都有缺点，但是在构造模型的不同需求的情况下，具有较好的通用性。 ( 3 ) n 格模型的简化 随着三维数据采集设备和建模技术的飞速发展，三维模型的数据量也快速地增长， 这样给计算机处理，绘制带来了巨大的压力，因此几何模型的简化对于几何模型的存储， 传输和处理，特别是对实时绘制有着重要的意义。 简化技术从几何学的角度出发，在保证模型外形基本不变的前提下，降低模型表面 的分割精度，尽量减少其分割的多边形数目。根据这个目标三角网格模型简化算法分为 静态简化和动态简化两大类：静态简化法是根据一定的精简原则由复杂模型构造f j 简单 的模型用于绘制，它只考虑模型自身的信息，与视点无关，也不能恢复原模型的信息， 静态简化法包括顶点，边的删除法和边折叠法；动态简化法可以在不同的视点下生成所 需要的分辨率的近似模型，一般是通过一些简单的局部的几何变换来实现，从而生成具 有连续的不同分辨率的近似模型。 1 2 2 点云模型的简化 点云模型的数据量是非常惊人的，一般大小的物体扫描所获得的数据量达m 级， 这给计算机的存储及后续模型的处理带来了很大的影响，因此对简化是大规模点云模型 高效显示和处理的重要预处理手段。 简化也是网格模型研究的一个基本问题，研究们在网格研究中提出了多种网格简化 技术，而目前对点云的简化大多是直接将网格模型简化算法的推广到散乱点云数据中， 这样不失为一种合理的策略。p a u l y l 7 1 等将多边形网格模型中常用的启发式简化方法推广 到点云模型中，这三种方法包括：1 ) 聚类简化技术，其中包括从任意种子点开始自下而 上的区域增长聚类和以整个模型为根节点，自上而下构建二叉树层次空问分割聚类；2 ) 迭代( i t e r a t i v e ) 简化法，类似于多边形网格模型中的边收缩技术，将所有采用点编成点对 并存入一个优先队列后，每次将误差最小的点对简化成一个点，循环此过程直至满足指 定的简化标准；3 ) 基于粒子仿真简化方法( p a r t i c l es y s t e m ) ，首先从点云模犁卜随机采简 化目标的采样点，然后根据粒子系统的粒子间的互斥力确定这些采样点在点云模型所表 示曲面的最优位置，最后用移动最d , - 乘方法将采样点投影到点云模型所表示的曲而 上。在这些方法中，聚类方法的计算速度最快，但对应的简化误差最大。迭代简化方法 得到的几何误差在五种简化方法中最小，f h - 亡i 算时问相对较长。p a u l y 8 】等人通过估计局 部曲面变化度和利用二差矩阵米消除简化导致的近似误差，可在曲面的高曲率处分布更 5 第一帝绪论 多的采样点。之后提出了一种基于移动最小二乘曲面的简化曲面误差测量方法，可实现 基于点的多分辨率造型。自适应层次窄间分割算法是最快的简化算法，但缺点是简化结 果的几何误差较大。为了实现在变化的视点下显示不同的分布率，简化技术通常与层次 细节表示方法结合使用。 1 2 3 三维模型检索 随着三维模型技术的发展，三维模型的检索技术也根据检索方式的不同产生出不同 的三维模型检索，已有的检索技术分为三类：基于文本的三维模型检索，基于内容特征 提取的三维模型检索及基于语义特征的三维模型检索。 ( 1 ) 基于文本关键字的检索 目前许多三维模型免费下载的嗍站主要还是以文本关键字来检索，用户只要输入所 要查找的物体的文本描述就可以找出相应的三维模型，如3 d c a f e 三维模型库 ( h t t p ：3 d c a f e c o r n ) ，美国d e r e x e l 大学的c a d 数字图书馆( h t t p ：w w w d e s i g n r e p o s i t o r y o r g ) 等。利用关键字对文本搜索引擎已经被广泛的应用，如生活中已不可少的b a i d u ，g o o g l e 等，但是采用关键字对图像，三维模型搜索时会出现一些问题：( 1 ) 用户对想要搜索的模 型的描述带有主观性，片面性，无法正确的表达真正的需求；( 2 ) 复杂的模型无法使用短 短的几个关键词就能描述，往往模型的区别在于细节部分；( 3 ) 建立模型时定义关键字的 时候也有困难，不仅人工标注关键字十分费时费力，而且也带有个人的主观性。综上所 述，利用关键字检索三维模型的效率不高，因此发展基于内容的三维模型检索技术非常 重要和迫切。 ( 2 ) 基于语义标注的三维模型检索 基于语义标注的三维模型检索是提取关丁：文本的语义特征信息。目前，基于语义标 注的三维模型检索仍处于发展阶段，之前希腊i t i 学院和美国知耐基梅隆大学都对语义 检索进行相关的研究。s t r z a l k o w s k i 等在文献中提出了一种基于 自然语义的查询系统， 系统根据文本的语义信息进行检索。虽然基于内容和文本的检索被广泛的研究，但是仍 然存在一些缺点：基于内容的检索中需要人们提供检索样本，这样对用户来说造成了很 大的不便，而基于文本的检索则存在若干的i 、u j 题，模型有无标识，标识词的正确与否， 标识词表达得体与否等都直接影响着三维模型检索的效果。基于语义标注的三维模型检 索是结合了摹丁内容和文本关键洞检索方面的优点，检索将语义特征与模型内容特征融 合，有效地提高三维模型的检索效果，成为下一代i 维模型检索的关键研究内容。 ( 4 ) 基十内容特征提取的三维模型检索 6 两北入学顽士学化论文 目前三维模型检索研究的重点是基于内容的三维模型检索技术，现有多家研究机构 开发了基于内容的三维模型检索系统。最著名的普林斯顿大学开发的三维模型检索系 统，还有台湾大学，日本国立多媒体教育研究所，和德国莱比锡大学图形图像处理实验 室等开发的三维模型检索系统。该系统中内容特征提取技术是关键技术，决定了检索效 果的好坏。 基于内容特征提取技术是对三维模型提取出能够反映高层语义信息的特征表达。该 项技术虽然很早f i ；i 就被提出并研究，如s a d j a d i l l 3 1 b a l l a r d l l 4 1 r e e v e s l l 5 1 等，但是由于一 些相关的技术没有发展或没有出现所以一直没有被引起关注。直n - 十世纪末，三维模 型检索技术的飞速发展，带动了一大批学者相继开始研究三维模型特征提取技术，成为 了研究热点之一。三维模型存在多种表达方式，如离散点云，多边形网格，体素及隐形 曲面等，目前所研究的算法没有一种统一的特征描述方法适用于所有的三维模型表示， 大部分特征提取算法主要针对的某一种特定的三维模犁表示方式的模型。o s a d a 等人【2 j 提出的基于形状分布的算法应用于网格模型，s u n d a r t l 6 l 等研究对象是基于体素表示的三 维模型，c o m e y 17 1 ，m u k a i 【1 8 】等以c a d 模型作为研究对象，z h a n gb 9 1 和o h b u c h i 2 0 】等采 用v r m l 模型作为研究对象。三维模型表面比较复杂并且形状千变万化，因此目前对 模型特征提取的研究主要集中在对模型空间形状的特征描述和相似性匹配的研究上，对 于基于表面属性的特征提取目前国内外还没有研究。迄今为止，三维特征提取方法主要 分为三大类：统计特征提取方法；骨架提取方法；基于几何学的提取方法。 基于统计模型的特征提取方法 基于统计提取的特征提取算法是从统计的角度i l 发，对模型高层次意义的几何特征 进行统计。这些几何特征包括：模型表面任意两点的距离，角度，顶点的曲率分布，模 型各阶统计矩，模型顶点后的傅犟叶系数和球面调和系数等等。目前统计方法都是适用 于多边形网格模型，基于统计特征的方法，算法简单易懂，比较容易实现，但是由于统 计特征的原理是基于概率分布，因此往往带有4 i 确定性及随机性，只能在全局的范围内 表达模型的特征，不能反映出模型细节部分的特征，因此它适合模型的卡h 分类，建立分 类数据库。 o s a d a l 4 5 】等人提出了基于形状分布的算法，该算法分析出不同的几何形体表面顶点 的相互关系呈现出不同的的分布特征，并将这些形状分布特征转化为几何概率分布问 题，计算出几何概率分布图并采用相似度匹配进行区别模型。z h a n g 4 6 l 采用皋r 傅里叶 转换与矩的思想对模型进行特征描述，结合两种特征使得模型对边界变化及物体质量分 7 荔帝绪睦 布敏缚性高。z a h a r l 7 1 在假设模酗的质量分布均匀的条件f ，计算模型相对三个主轴的 惯性矩和模型表面顶点埘三个辛轴的分靠，该算法局限性比较大，实验表明对一些特征 对称的模型效果更好。 摹丁骨架的特征提取方法 所谓骨架是对模型的主要特征的一种直观描述，就像人体的骨髂框架一样，提取出 模型的关节点及拓扑结构。此方法既可| 三【对模型进行全局匹配，也可阻做局部匹配，并 且对模型几何变换圈旋转，缩放，平移等具有很好的鲁棒性，但是对原始模型的要求比 较高，适合于具有分支结构的模型。 在医学虚拟内窥镜手术中提取管状器官的中轴线c c e m e d i n e ) 对手术起到报鼋要 的导航作用。a m e n 乜【4 ”提出基于模型的v o r o n o i 图提取出模型的骨架。该算法描述了 模型的全局特征，但是具有v o m n o i 图计算本身所带的缺点，即计算v o r o n o i 图开销比 鞍大，相应所需的存储量也相当惊人，且v o r o n o i 罔本身的构造对哚音非常敏感。s t m d a r 】驯 等人提出了基于参数控制的瘦化算法( t h i n n i n ga l g o r i t h m ) ，该算法主要是计算出模型的 骨架图形作为模型的特征描述，( 如罔13 ) 且适合于基于体素表示的= 三维模型。 o c 图i j ：骨架特征提取示意图 基于几何学的特征提取方法 几何学是三雏模型重要的特征。基于儿十学的特征提取方法也有很多，s u z u k i “1 等 人提根据网格单元中的顶点数目划分为不同的等价类，然后将同等等价类进行归一化 顶点的个数作为特征向量。v r a n i c 等人【”韫出采用劓线( r a yb a s e d ) 柬作为特征描述，法 算法以坐标原点起始从空间方向做射线，将其与三角面片相交的点与坐标原点晟夫距离 做特征值。t a n g e l d e 等人i s 3 1 采用加权点集合( w e i 曲t e dp o i n 把s ”表示多面体模型的方法。 n o v o m i 5 4 提出采用模型的体积测定误差和申洲的偏移柬匹配物件凌方法小能考虑到 两个模犁的对称性，从而影响匹配的相似性。 1 3 本文的研究内容 本文的研究内容包括基丁点厶和刈格表示的鼍维模型的表4 ：，简化及基r 删格表示 8 两北人学硕士学位论文 的三维模型的形状分布检索算法，提出改进的点云简化算法和形状分布检索算法。本文 的研究内容主要包括： ( 1 ) 点云和网格模型的建立。首先以三维激光扫描获取的数据为输入，对导入的点 云数据实现配准，去噪，修复及简化等处理，将这些离散的采样点按一定的规则表示点 云模型的表面，通过对建立后的点云模型进行三角剖分，重新建立点云曲面的拓扑关系 得到网格模型，最后对生成的网格模型进行简化来减少模型的存储量。 ( 2 ) 提出了一种改进的点云模型简化算法。基于k 邻域密度的离散点云简化算法相 比增量聚类法考虑到了点云分布的密度问题，f h 缺点是在曲率大的地方容易丢失细节信 息，造成简化后的模型与原有模型不相似。本文提出了改进的基于k 邻域密度的简化算 法，首先对k 邻域中点到中心点的距离进行判断，距离大于平均距离的点则保留，而距 离小于平均距离的点，采用法向量误差的方法进行衡量是否删除点。该方法事先控制简 化误差，适合子非均匀点云数据，尤其在曲率变化大的地方不易改变模型的形状。 ( 3 ) 提出了一种基于形状分布的加强细节三维模型检索的算法。该算法在统计特征 的形状分布算法的基础上提出加强对模型细节的检索，从而提高对模型的检索精度。主 要思想是结合基于子块的三维模型检索的方法，对局部特征进行相似度比较，加强了对 细节差异的分辨，解决了形状分布算法对于外形相近但细节不同的i 维模型分辨率不足 的问题。 1 4 本文的章节安排 第一章绪论。分析了基于点云和网格表示的三维模型的建赢技术及i 维模型检索 算法的研究背景及意义，总结该领域的国内外研究现状，在此基础上，给出了本文的研 究路线及研究内容； 第二章点云和网格模型的建立。总结了建立点云和湖格模型的关键技术。该章为 第三章的研究和第六章系统的实现提供了技术基础； 第三章基于k 邻域密度简化的改进算法。对基于点云表示的模型简化算法进行深 入的研究和分析，在基于k 领域密度的简化算法上提出改进算法，该算法在模型曲率大 的地方能多保留点，曲率小的地方少保留点，冈此对曲率大的模犁进行简化后能够比较 好的保留细节部分的信息； 第四章基于加强细节检索的形状分布算法。本章首先总结了三维模型特征提取技 术，重点研究基于网格模型的特征提取技术，并提出一种基于加强细节检索的形状分布 算法。该算法首先将模型进行分块，然后分别对各个模块进行形状特征提取，通过采用 9 第一帝绪论 相似度匹配算法对该算法进行实验，结果证明采用该算法进行三维模型检索，加强了对 细节差异的分辨，解决了形状分布算法对于外形相近但细节不同的三维模型分辨率不足 的问题； 第五章系统实现。建立了基于点云网格模型的建立系统，并详细介绍了系统的功 能及实现方法，并对其开发和运行环境进行了说明； 第六章总结与展望。总结了本文的工作，并提出了未来的研究方向。 1 0 两北人学硕士学化论文 第二章点云和网格模型的建立 三维模型模型已成为继声音，图像和视频之后的一种重要的数字媒体。三维模型有 多种表现方式，即点云模型，网格模型，隐性曲面及体素模型等，其中基于点云表示的 三维模型结构简单，能够丰富地表达模型复杂的表面，而网格模型是目前三维模型最常 用的表达方式，且具有结构简洁，灵活和显示高效等优点，研究这两种表达方式的建立 技术具有重要的实践意义。 2 1 引言 在计算机图形学的研究中，把点作为图形元素已经有很长的历史了，早在1 9 7 4 年， c a t m u l l 注意到任何几何细分的极限就是点，然而点作为基本图形元素在很长一段时问内 没有受到重视。之后的1 9 8 3 年，r e e v e s 提出在计算机图形绘制时用3 d 离散采样点( 粒子) 作为基本绘制元素，附加存储一一些如颜色、密度、光照反射系数等信息。基于点的表示 不仅可以直接绘制三维扫描设备生成的无规则点云数据( 预处理之后) 还可以高效率绘 制高度复杂的物体模型。 基于点的数字几何处理技术包括三维扫描数据的获取和预处理，基于点的表示以及 点云模型的编辑，几何造型及渲染( 图2 1 ) 。本文重点研究点云模型的预处理及基于点的 表示技术和曲面重构。 旅丁 点的 绘制 图2 1 基于点的处理流程 2 2 点云模型的预处理技术 通过三维手 描设备获取的手j 描数据是一些散乱的点数据，这些数据散乱分布且包含 1 l 第_ 二章点i 和嘲格模型的建立 除模型之外的其他数据，不能直接形成模型，因此必须经过预处理才能用于日后点模型 的数字几何处理。点云模型的预处理是模型进行处理之前最重要的一步，它包括：配准， 去噪，补洞及简化等操作。 2 2 1 配准 根据上述介绍的激光扫描仪的原理，三维激光扫描仪是采用仪器内部设定的坐标系 统，利用激光脉冲来计算出扫描目标模型上每个点的三维坐标。由于所扫描的目标模型 有不同的视角，从某一个角度无法扫描到被遮挡的部分，所以无法一次完成采集点数据， 因此必须使用扫描仪在不同的角度多次进行扫描，从而得到了在不同角度的数据，但是 这些点数据不在同一个坐标下，因此必须将他们配准到同一个统一的坐标系下，这就是 配准需要做的工作。简而言之，数据配准就是将两个及两个可以上坐标系中的大容量三 维空间数据点集转换到统一坐标系下的总的数学计算过程。 三维数据配准主要有两种方法：一个是机器配准，它主要是与硬件有关，主要原理 是通过高精密的仪器来获得点的数据信息和它们之间的拓扑关系，并对点之间的关系进 行变换，从而来进行数据间的配准计算；另一个是自动配准，即软件配准，主要是根据 数据中的变换信息或在数据获耿的同时引入的其他信息来对三维数据进行配准计算，它 与硬件无关，目前该技术被广泛的研究。 在开始扫描的准备时期也可以使用标签法f 2 1 1 ，即在测量的物体上面贴上一些特征 点，平均的分散开，然后使用这些特征点进行定位。还有一种是通过提取轮廓曲线2 2 】 作为对齐的基准，缺点是要求点云要有比较明显的特征。经过这些方法对配准工作能起 到辅助作用，获得较好的效果。 2 0 世纪8 0 年代中期，有许多学者就开始大量研究点集数据的配准。b e s l 和m c k a y 2 3 1 提出了一种高层次的基于自由形态曲面的配准方法，也称迭代最近点法i c p ( i t e r a t i v e c l o s e s tp o i n t ) 。