（机械制造及其自动化专业论文）基于逆向工程的牙齿三维数据建模技术.pdf

哈尔滨工业大学丁：学硕士学位论文 摘要 近年来，快速成形( r a p i dp r o t o t y p i n g ，简称r p ) 技术和逆向工程 ( r e v e r s ee n g i n e e r i n g ，简称r e ) 技术得到了迅速的发展与结合，并广泛地应 用于医疗领域之中。其中在牙齿治疗方面，取得了很多的研究成果。 本课题通过对牙齿c t 图片的研究，旨在建立一种行之有效的建模方 法，能够完成由c t 图片提取数据构建牙列与牙套三维模型，并应用于隐形 牙齿矫治器的研制。 隐形牙齿矫治器采用不同于传统牙齿矫治器的原理，由透明材料制成， 不使用托槽和弓丝，并且为系列矫治装置，通过不断的小范围内牙齿移动来 达到牙齿的矫治目的。和传统固定矫治器相比，具有美观、卫生、舒适、方 便等特点。 本文针对c t 图片的特点，研究了如何从c t 图片中提取牙列层切面数 据：根据元胞自动机原理，提出一种算法，对数据进行轮廓提取：利用空间 相邻性排序算法，对轮廓数据进行排序；利用三次样条插值法，对数据进行 插值。然后讨论了造型软件的选择；调节点云方向、统一起始点位置、选择 控制点、选择曲线阶次、选择段数，创建轮廓线；选择自由曲线，构建牙列 模型；根据牙列模型，设定参数，构建牙套模型。最后利用立体光固化技术 ( s t e r e o l i t h o g r a p h ya p p a r a t u s ，简称s l a ) 进行牙套模型加工的工艺实验，找 到了一组相对合适的加工工艺参数，加工出牙套模型样件。该模型反映了牙 齿的形状，并具有一定的矫正功能。 关键词隐形；牙齿矫治：逆向工程；c t ：建模 坠堡堡三些奎兰三耋堡圭兰堡篁兰 a b s t r a c t i nr e c e n ty e a r s ，r a p i dp r o t o t y p i n g ( s h o r tf o rr p ) t e c h n o l o g ya n dr e v e r s e e n g i n e e r i n g ( s h o r tf o rr e ) t e c h n o l o g yo b t a i n e dt h er a p i dd e v e l o p m e n ta n dt h e u n i o n ，a n dh a v eb e e nw i d es p r e a d l ya p p l i e di nt h em e d i c a lt r e a t m e n t i nt h ea r e a o ft h et e e t ht r e a m e n t ，t h e yh a v eo b t a i n e dm a n yr e s e a r c hr e s u l t s t h i st h e s i s ，t h r o u g ht h er e s e a r c ho ft h et e e t hc tp i c t u r e ，i sf o rt h ep u r p o s e t 。oe s t a b l i s ho n ee f f e c t i v e m o d e l i n g m e t h o dw h i c hc a nc o n s t r u c tt h r e e - d i m e n s i o n a lm o d e lo ft h ed e n t u r ea n dt h et e e t hs o c k e tb yw i t h d r a w i n gt h ed a t ao f c t , t oa p p l yt ot h er e s e a c ho f t h ec o n c e a l e dt e e t hc o a c t i n ge q u i p m e n t t h ec o n c e a l e dt e e t hc o r r e c t i n ge q u i t m e n ta d o p t sd i f f e r e n tp r i n c i p l ef r o m t h et r a d i t i o n a lt e e t hc o r r e c t i n ge q u i p m e n ti ti sm a d eb yt h et r a n s p a r e n tm a t e r i a l i td o e sn o tu s et h eh o l d i n gp a r ta n dt h et i n s e lt h r o u g ht h eu n c e a s i n gs m a l ls c o p e m o v i n g ，i tc a l la c h i e v et h eg o a lo ft h et e e t hc o r r e c t i o n c o m p a r e dw i t ht r a d i t i o n a l f i x e d l yc o r r e c t i n g ，i th a st h ec h a r a c t e r i s t i co ft h eh e a l t h ，a r t i s t i c l y ，c o m f o r t a b l e ， c o n v e n i e n ta n ds oo n i nt h ev i e wo ft h ec h a r a c t e r i s t i co ft h ec tp i c t u r e ，t h i st h e s i ss t u d i e sh o wt o w i t h d r a wt h el e v e ls e c t i o nd a t af r o mt h et e e t hc tp i c t u r e a c c o r d i n gt ot h e c e l l u l a ra u t o m a t ap r i n c i p l e ，i tp r o p o s e so n ea l g o r i t h mw h i c he a r r i n go nt h e r u c t i o nt ow i t h d r a wt h ed a t ao fo u t l i n e u s i n gt h es p a t i a ln e i g h b o r i n gs o r t a l g o r i t h m ，i tc a r r i e so nt h ea r r a n g e m e n tt ot h eo u t l i n ed a t a u s i n gt h r i c es p l i n e i n t e r p o l a t i o n s ，i t c a r r i e so nt h ei n t e r p o l a t i o nt ot h ed a t a t h e ni td i s c u s s e st h e c h o i c eo fm o d e l i n gs o f t w a r e ，a d j u s t st h ep o i n tc l o u dd i r e c t i o n ，u n i f o r m ss t a r t i n g p i n t s ，c h o o s e st h ec o n t r o l l i n gp o i n t s ，c h o o s e st h ec u r v es t e po r d e r ，c h o o s e s s e c t i o nn u m b e r ，c o n s t r u c t sc o n t o u rl i n e sc h o o s e st h ef r e ec u r v e ，c o n s t r u c t st h e d e n t u r em o d e l ，t h r o u g ht h ed e n t u r em o d e l ，e n a c t m e n t sp a r a m e t e r s ，c o n s t r u c t st h e t e e t hs o c k e tm o d e l f i n a l l yu s e st h es t e r e o l i t h o g r a p h ya p p a r a t u st e c h n o l o g y , i t c a r r i e so nt h et e e t hs o c k e t m o d e lp r o c e s s i n g ，f i n d sag r o u po fr e l a t i v e l y a p p r o p r i a t ep r o c e s s i n g sc r a f tp a r a m e t e r s ，p r o c e s s e st h et e e t hs o c k e tm o d e l t h i s m o d e lr e f l e c t sm ef o mo f m et e e m h a v ec e r t a i nc o r r e c t 品n 血n c t i o n s k e y w o r d s c o n c e a l e d ，t e e t hc o r r e c t i n g ，r e ，c t , m o d e l i r g 1 i 堕堑堡三些查兰王耋堡圭兰堡篁塞 1 1 课题背景 第1 章绪论 近年来，快速成形技术和逆向工程技术得到了迅速的发展与结合，并在 生物医疗领域得到了广泛的应用，正在给人类带来巨大的利益。国内外许多 学者致力于该领域的研究，并在很多方面取得了研究成果，如牙齿疾病医疗 和牙齿矫正、医学器官模型的快速制作、骨骼手术移植和破损修复等i l “】。 有关快速成形和逆向工程技术在牙齿治疗和矫正方面的应用研究，在国内外 已经有所开展，并取得了很多的研究成果。 在牙齿治疗方面，目前研究较多的主要是基于逆向工程的牙颌模型、牙 冠模型的三维建模，以用于牙齿修复。现已经能够较为准确的制造出牙颌、 牙冠、牙体和牙列的三维实物模型，为病牙的修补和替换等工作提供了非常 直观有效的模型参考和研究手段【3 “。 在牙齿矫正方面，隐形牙齿矫治器是近年来非常显著的研究成果。不同 于传统的金属固定矫治器，隐形矫治器由透明材料制成，不使用托槽和弓 丝，并且为系列矫治装置，不同的阶段佩戴不同的型号，通过不断的小范围 牙移动达到牙齿的矫治目的。和传统固定矫治器相比，它具有以下优点：( 1 ) 美观。矫治器为透明材料，对成年患者和某些有心理负担患者或特殊职业患 者尤其适用。( 2 ) 卫生。可自行取戴，患者口腔卫生和健康得到保证。( 3 ) 舒 适。矫治器紧贴牙齿，并和牙齿保持一致形态，没有金属矫治器和会属线所 引起的口腔磨损和不适，不刺激口腔软硬组织，患者口感舒适。( 4 ) 方便。 采用一系列预制的矫治器进行矫形，替代了传统的金属矫治器和金属线，减 少了病人去医院进行调校的次数。另外矫治器不影响患者的饮食。因此，隐 形牙齿矫治器的研制将为广大正畸患者带来切实的利益，并促进牙科产业的 发展会产生很大的经济效益和社会效益1 5 】。 2 0 世纪7 0 年代初，法国牙医f r a n c o i sd u r e t 教授就将c a d c a m 技术 引入口腔固定修复体的设计与制造中来，现在美国、德国、日本等国家出现 了实用化的c a d c a m 口腔修复系统【6 “j 。国内的研究起步较晚，目前还处 于初期的探讨阶段，而快速成形技术在牙齿治疗中的应用只报道有应用快速 成形法制作磨牙树脂全冠，关于快速成形技术牙齿矫治器制作方面还未见报 道。美国硅谷于1 9 9 7 年创建了利用快速成形制作隐形牙齿矫治器( i n v i s a l i g n ) 的技术，于1 9 9 8 年投放市场并应用临床。隐形矫治技术己在美国获得了4 项专利，并有5 1 项专利正在申请。隐形矫治器的设计和制作系统最近在美 国获得了两项行业奖5 1 。 1 2 逆向工程概述 在产品开发和制造过程中，计算机几何造型技术已得到了广泛的使用， 但仍有许多产品最初并不是由计算机辅助设计( c a d ) 模型描述的，设计和制 造者面对的是实物样件。为了利用先进制造技术，需要通过一定途径将实物 样件转化为c a d 模型。这种从实物样件获取产品数学模型的技术，已发展 为c a d c a m 系统中的一个相对独立的研究领域，即逆向工程，或称反向 工程、反求工程等p “1j 。 逆向工程可以简单的理解为根据实物模型测得的数据，构造c a d 模 型，继而进行分析制造【i 。广义的产品“逆向工程”包括形状( 几何1 反求和 材料反求等诸多方面，而如何重建产品实物的c a d 模型是反求工程的关键 技术，在这一意义下，“逆向工程”可定义为：将实物转变为c a d 模型相 关的数字化技术和几何模型重建技术的总称】。 逆向工程是缩短产品开发周期的一种有效途径，特别是形状复杂的物体 或自由曲面组成的物体，例如：流线型物体、人体器官、雕塑品、模具等。 具体应用可以分为以下几类：( 1 ) 起源于物理模型的新零件的设计；( 2 ) 对无 法得到图纸的现有零件的复制；( 3 ) 磨损或损坏物体的还原；( 4 ) 对现有产品 的局部修改；( 5 ) 产品的检测【l ”。 逆向工程基本工作流程如图1 1 所示【i ，大体可以分为以下四个步骤： 数据采集、数据预处理、数据分割、曲面重构建模。 1 2 1 数据采集 近十年来，随着传感技术、控制技术、图像处理和计算机视觉等相关技 术的发展，出现了各种各样的样件表面的几何数据获取方法，主要分为破坏 性测量法和非破坏性测量法【”q 酊。 破坏性测量主要是自动断层扫描法，该技术采用逐层去除材料与逐层扫 描相结合的方法，其特点是可以测量内轮廓数据，而且测量精度高，片层最 小可达0 0 1 m m 样品 3 d 数据；i c a d 轮廓测量旧啊1 处理 1 曲面建构 量产_ j 模具 复制 j 成型 l 模鼽工卜1n 施 r p 快速成型广 生成 s t l 文件 外形 修饰 图1 - 1 逆向t 程流程图 、f i g 1 1t h ef l o wc h a r to f r e 非破坏性测量分为接触式测量和非接触式测量，目前最常用的接触式测 量系统是三坐标测量仪( c o o r d i n a t em e a s u r e m e n tm a c h i n a ，简称c m m ) 。其 优点是不受物体表面颜色及光照的限制；对物体边界也能产生准确的测量结 果。缺点是由于测头的限制，可能丢失某些测头不可到达的细节数据；不可 测量某些测头不可触及的软材料；另外，测量速度受到机构运动的限制。 非接触式测量分为主动式测量和被动式测量。被动式测量目前很少在反 向工程中使用。主动式系统有专门仪器产生测量光源或声源，被动式测量则 没有。最常用主动式测量是激光三角形测量法，基本原理是利用激光源投射 到被测表面，反射光在图象传感器上成像，按照预设的三角形光路原理得到 被测点的位置坐标。光源形状可以是光束、光带、多条皮带，依次具有更高 的速度。与三坐标测量仪相比，其特点是可以实现高速测量。其缺点是对于 表面粗糙度、漫反射率敏感；存在阴影效应( 由物体间或物体各部分遮挡产 生) 。另一种常用的激光测量法是光栅法。其优点是测量范围大、速度高、 成本低、易于实现。缺点是精度不高，一般只能测量起伏不大的表面7 ) 。 计算机断层扫描( c o m p u t e rt o m o g r a p h y ，简称c t ) 技术最具代表的是基 于x 射线的c t 扫描机，它是以测量物体对x 射线的衰减系数为基础，用 数学方法经过计算机处理而重建断层图像。这种方法最早是应用于医疗领 域，目前已经开始用于工业领域( 所谓“工业c t ”) ，特别针对中空物体的 无损三维测量。这种方法是目前最先进的非接触式的检测方法，它古丁对物体 的内部形状、壁厚，尤其是内部构造进行测量，可以获得内外轮廓的数据， 且不破坏工件。但它存在空间分辨率较低，获得数据需要较长的积分时间， 兰玺鎏三些查兰三兰堡圭兰堡堡兰 重建图像计算量大、造价高，只能获得一定厚度截面的平均轮廓，精度不高 等缺点1 13 1 。 1 2 2 数据预处理 随着三维形状测量技术的发展，数据量越来越大，一般是大规模散乱数 据点，亦称为“点云”。如何压缩测量数据，准确地再现被测曲面，已成为 反求技术中的关键问题。采用动态扫描测量方式，不可避免地要受到随机干 扰信号的影响，造成曲线的不平滑。因此必须对密集采样数据进行预处理。 预处理工作包括数据平滑、排除噪声数据和异常数据、压缩和归并冗余 数据、遗失点补齐、数据分割、多次测量数据及图像的数据定位对齐和对称 零件的对称基准重建。数据平滑通常采用标准高斯、平均或中值滤波算法， 高斯滤波能较好地保持原数据的形貌，中值滤波消除数据毛刺的效果较好， 应用时可根据数据质量和建模方法灵活选择滤波算法。数据精简是减少数据 “点云”中存在的大量冗余数据，主要针对激光测量产生的“点云”数据， 不同类型的“点云”可采取不同的精简方式，如散乱点可选择随机采样、均 匀网格、三角网格方法；扫描线和多边形点云可采用等间距缩减、倍率缩 减、等量缩减、弦高差等方法；网格化点云可采用等分布密度法和最小包围 区域法等。数据平滑和精简存在的问题是有时会丢失有用的数据信息，特别 是尖锐角、棱线以及曲率变化大的区域的数据1 1 9 。 1 2 3数据分割 数据分割是根据组成复杂曲面的曲面片的类型，将“点云”数据分割成 同类曲面片的数据子集，使测量数据分类转变为造型数据，方法是根据每一 个自然曲面，将测量点分割同时并决定每一个点集属于哪一种曲面，有基于 边和基于面的2 种基本分割方法【2 0 】。 ( 1 ) 基于边的方法首先是从数据点集中，根据组成曲面片的边界轮廓特 征、2 个曲面片之间的相交、过渡特征，以及形状表面曲面片之间存在的棱 线或脊线特征，确定出相同类型曲面片的边界点，连接边界点形成边界 环，判断点集是处于环内还是环外，实现数据分割。基于边的技术必须考 虑寻找边界特征点，主要是由数据点集计算局部曲面片的法矢量或者高阶 导数，通过法矢的突然变化和高阶导数的不连续来判断一个点是否是边 点。 哈尔滨工业大学t 学额士学位论文 ( 2 ) 基于面的技术是确定哪些点属于某个瞌面，这种方法和曲面的拟合 结合在一起，在处理过程中，这种方法同时完成了曲面的拟合。因此，基于 面的方法是数据分割中具有发展前途的技术。 1 2 4 曲面重构建模 目前，在反求工程中，主要有两种曲面构造方案：以b 样条或n u r b s 曲面为基础的曲面构造方案和以三角b e z i e r 曲面为基础的曲面构造方案。 ( 1 ) b 样条及n u r b s 曲面b 样条及n u r b s 曲面表示是c a d c a m 系统 中广泛采用的曲面表示方法，这类曲面可以应用四边参数曲面片插值、拉 伸、旋转、放样、蒙皮、扫描、混合和四边界方法构造，也称矩形域的参数 曲面或四边曲面，这两类曲面已形成有一套完整的曲面延伸、求交、裁减、 变换、光滑拼接及曲面光顺等算法。 ( 2 ) 三角曲面三角曲面也称三边曲面，三角曲面由于其构造灵活、边界 适应性好，具有构造复杂形状的潜力，是解决异形曲面建模的有效方法。但 由于三角曲面模型和通用c a d c a m 系统的曲面模型不兼容，使得它和 c a d c a m 系统的数据通讯和图形交换难以实现。此外，有关三角b e z i e r 曲 面的一些计算方法的研究也还不太成熟( 如三角曲面之间的求交、三角曲面 的裁减等) ，这些因素限制了它在工业制造领域中的实际应用。 曲面重构以后，通过c a d 软件，实现曲面的拼接，完成物体的三维数 据模型的建立1 2 1 4 。 1 2 5 逆向工程应用软件的研究现状 目前，国外开发的商用逆向工程造型软件已经有许多种。较早是一些商 品化的c a d c a m 软件集成进专用的逆向模块，如p r o e n g i n e e r 的s c a n t o o l s 模块、u g 的点云处理、曲线及曲面拟合功能和s t r i m l o o 的点处 理加工、自动生成曲面和简单的边界识别等功能。一在此基础上，由于市场需 求的增长，有限的功能模块已不能满足数据处理、造型等逆向技术的要求， 后期发展形成了专用的逆向软件。目前面市的产品类型已达数十种之多，较 具代表性的有s d r c 公司的i m a g e w a r e s u r f a c e r 、r a i n d r o p g e o m a g i c 公司的 g e o m a g i c 、p a r h f o r m 公司的p a r a f o r m 、u g s 公司的0 u i c k s h a p e 、p t c 公司 的i c e m s u r f 、d e l c a m 公司的c o p y c a d 软件，m d t v 公司的 s u r f a c e r e c o n s t r u c t i o n 以及a l i a s w a v e f r o n t 公司的s u r f a c e s t u d i o 等。 卜沭软 件共同的特点是具备多种数据处理及分割方法，具有部分规则特征识别，自 动曲面拟台，强大的曲线、面编辑处理和模型评估检查的功能，不同格式的 数据转换接口。如果是c a d c a m 软件公司开发的产品，还可以和各自的 c a d c a m 母体软件实现无缝集成，并利用其提供的强大功能支持，形成技 术和市场优势，其中i m a g e w a r e s u r f a c e r 和p a r a f o r m 系列软件代表了逆向工 程技术的最新进展 9 - - l o 。 与国外相比，国内研究起步晚、经费投入少，限制了高水平研究的开 展，创新性的研究不多，在世界学术领域，还没有形成较大的影响力。已知 的较早从事逆向工程研究的单位多为高等院校，较有代表性的有西安交通大 学c i m s 中心的面向c m m 的逆向工程测量方法和基于线结构光视觉传感器 的光学坐标测量机的研究、上海交通大学国家工程模具中心的集成系统和自 动建模技术、浙江大学生产工程研究所的三角面片建模、南京航空航天大学 c a d c a m 工程研究中心的基于海量散乱点三角网格面重建和自动建模方 法、华中科技大学的曲面测量与重建和西北工业大学的数据点处理、建模 等，为数不多的论文散见于计算机应用、机械工程等类学位论文、会议及杂 志上。在应用研究上，除一些实验室的小型软件外，自主开发的商用逆向软 件仅有浙江大学生产工程研究所的反求工程c a d 软件r e s o f t 和西北工 业大学的实物测量造型系统n p u s r m s 。由于缺乏自主的c a d c a m 软件 的支撑，以及逆向工程的上游测试设各和下游应用( c a d c a e c a m ) 基本为 国外产品，使得国产软件产品在设备接口、数据转换和应用上一真滞后于相 关产品，开发的软件显得势单力薄，与国外软件相比处于明显的竞争上的劣 势。 1 3 课题研究目的及意义 将逆向工程技术应用于医学领域，最基本的思想就是利用从研究对象上 提取出的数据信息，建立医学模型。其中c t 技术是提取人体组织数据的一 个非常重要，并且经常使用的手段。本课题通过对牙齿c t 图片的研究，旨 在建立一种行之有效的建模方法，能够利用由c t 图片提取出数据，构建牙 列与牙套三维模型，并应用于隐形牙齿矫治器的研制。另外，力求该建模方 法能够成为逆向制造业中一种新的、有特点的建模方法，丰富逆向制造业技 术。 堕堡堡三些查兰三耋璧圭兰竺鎏圣 1 4 课题研究内容 本课题研究方向为利用逆向工程技术建立复杂人体曲面的数字与实物模 型。具体研究内容如下： ( 1 ) 牙列模型边缘轮廓数据的提取。 ( 2 ) 边缘轮廓数据的排序、插值。 ( 3 ) 牙列与牙套重构建模。将每层牙列边缘轮廓数据拟合为曲线，通过 每层曲线之间的连接，生成牙列三维数据模型。以牙列模型为基础，通过运 算，生成牙套三维数据模型。 ( 4 ) 进行牙列与牙套的树脂模型加工工艺实验。 哈尔滨工业大学工学硕士学位论文 第2 章牙列轮廓数据提取与处理 2 1由c t 图片提取牙列数据 2 1 1c t 成像原理 18 9 5 年伦琴发现了x 射线，这一罩程碑式的发现促使医学成像技术飞 速发展，彻底地改变了医学诊断技术的面貌，在人类医学保健和研究开发领 域引发了一场革命。c t 是依据通过检测x 射线经过人体后衰减对比度差异 原理f 即不同组织具有不同的c t 值1 进行工作的。 目前c t 扫描己广泛地应用于医学诊断、假体设计、工业检测和三维数 字化，比较先进的一种c t 扫描是螺旋式c t 扫描，其原理如图2 1 所示 忙”。用这种扫描机对实体( 如人体) 扫描时，实体在一个门架中连续地向荫缓 慢移动，装于架上的x 射线管和检测系统围绕实体连续转动并采集数据， 这两种运动之间的相互配合关系是：x 射线管和检测系统每转动3 6 0 0 ，实 体向i i 移动一个切片层厚。由c t 扫描得到的原始数据呈截面c t 图像格 式，每一幅c t 图像包含被测对象的内、外结构的截面几何信息【2 “。 黼 il 】 i i 1 。i 。 i _ ，、，一 1 硼 ： 图2 - 1 螺旋式c t 扫描原理图 f i g 2 一lh e l i xc o m p u t e dt o m o g r a p h yw o r kt h e o r y c t 值是组织的衰减系数与水的衰减系数的比值： 组织的c t 值= 丛_ 二型! 1 0 0 0 ( 2 1 ) 。 哈尔滨工业大学工学硕士学位论文 式中“组织的衰减系数 儿水的衰减系数。 c t 值的单位是h u ( h o u n s f i e l du r l i t ) ，每变化一个亨氏单位h u ，相当于 0 1 衰减系数的变化。目前人体组织的c t 值界限可划分为4 0 0 0 个分度f 灰 度) ，即1 0 0 0 + 3 0 0 0 ，上界为骨的c t 值，下界为空气的c t 值，而人体中 密度不同的各种组织的c t 值则居于1 0 0 0 + 3 0 0 0 h u 的4 0 0 0 个分度之间。 c t 图像的优点是对比灵敏度高，可以区别衰减系数差异为0 5 的组织，已 成为临床医学中不可或缺的无创诊断手段。 2 1 2牙列数据的提取 因人体不同组织器官具有不同的密度，在c t 图像上直观的表现为不同 的灰度级，所以可以对其进行分类显示。图2 2 是一幅头颅骨骼c t 图像切 片，可以明显区分出软组织和骨骼部分。当然并不是任意c t 图像的信息区 别都是这样容易的，对一些既有软组织又含有多种不同部位骨骼的c t 图 像，对所需骨骼信息的识别可在医生的指导配合下进行。 图2 - 25 1 2 5 1 2 标准c t 图像 f i g 2 25 1 2 x 5 1 2s t a n d a r dc ti m a g e 骨骼c t 中软组织与骨质具有不同的密度且差别较大，在图像中表现为 哈尔滨工业大学工学硕士学位论文 占据相差较大的灰度值范围，其中骨骼的灰度主要集中在1 0 0 0 1 2 5 5 h u ， 其他组织的灰度集中在8 0 1 5 0 h u 2 7 2 8 j 。 m i m i c s 软件是由比利时m a t e r i f l i s e 公司开发的运行在w i n d o w s 环境下 的高度集成的二维图像处理软件，主要用于处理断层扫描数据。可以将一组 c t 图片通过格式转换存入m i m i c s ，对该组图片进行一系列操作，图2 3 就 是一张经过格式转换后存入m i m i c s 的头部骨骼c t 图片。 从图2 3 中可以看出，该层c t 图片中有牙齿骨骼、脊椎骨格、软组 织、c t 机工作台等的图像，而我们所需要的只是牙齿骨骼的图像，这就需 要将牙齿骨骼图像单独提取出来。在m i m i c s 中，提供了一个这样的编辑工 具，可以人工去除不需要的组织，也可以添加辅助结构。在添加轮廓或删除 组织的过程中，也可能需要对已经添加或删除的组织重新修改，因为原图像 信息反映的是原组织结构的真实信息，而添加的辅助结构破坏了这种真实结 构信息，这样区别交互过程中添加或删除的信息也是很重要的，同样在 m i m i c s 中也保留了这种信息，交互过程中的信息用不同的颜色显示，确保 原来组织信息不会丢失。在交互过程中，可以选择只显示需要的轮廓信息， 其余不需要的信息可以设置成黑色背景，保证了操作的方便和准确。图2 4 即为人工提取出的牙齿骨骼c t 图像，可见脊椎骨格、软组织、c t 机工作 台等的图像已经被删除。 图2 - 3 存入m i m i c s 的头部骨骼c t 图片 f i g 2 3c ti m a g eo f t h eh e a db o n e si nm i m i c s 堕奎鎏三些銮耋三兰竺圭兰堡丝圣 图2 1 4 牙列骨骼c t 图片 f i g 2 4c ti m a g eo f 也et e e t hb o n e s 将牙齿骨骼c t 图像提取出来之后，m i m i c s 提供了一个功能，可以将 图片上的图像以t x t 文本格式输出，通过该功能即可提取到每层牙列骨骼 的层切面数据。t x t 文本格式输出主要为坐标点的形式，它记录了点在空 间中的位置，包括x 、y 、z 三个坐标方向的坐标值，此外还包括了空间中 点坐标对应的次度阈值。以下就是文本格式输出的数据的一部分。 + 8 3 6 7 4 0 0 e + 0 0 1 ，+ 2 5 0 2 4 0 0 e + 0 0 1 ，+ 8 7 0 9 9 8 8 e + 0 0 1 ，+ 117 1 + 8 1 7 1 9 0 0 e + 0 0 1 ，+ 2 4 6 3 3 0 0 e + o o l ，+ 8 7 0 9 9 8 8 e + 0 0 1 ，+ 1 2 2 4 + 8 2 1 1 0 0 0 e + 0 0 l ，+ 2 4 6 3 3 0 0 e + 0 0 1 ，+ 8 7 0 9 9 8 8 e + 0 0 i ， + 1 3 0 6 + 93 0 5 8 0 0 e + 0 0 1 ，+ 1 6 8 1 3 0 0 e + 0 0 1 ，+ 8 8 0 9 9 8 8 e + 0 0 1 ，+ 8 0 + 9 3 4 4 9 0 0 e + 0 0 1 ，+ 1 6 8 1 3 0 0 e + 0 0 1 ，十8 8 0 9 9 8 8 e + 0 0 1 ， + 7 7 + 9 3 8 4 0 0 0 e + 0 0 l ，+ 1 6 8 1 3 0 0 e + 0 0 1 ，+ 8 8 0 9 9 8 8 e + 0 0 1 ，+ 7 6 + 1 1 4 5 6 3 0 e + 0 0 2 ，+ 2 0 7 2 3 0 0 e + 0 0 1 ，+ 8 9 0 9 9 8 8 e + 0 0 1 ，+ 1 0 4 6 + 1 1 4 9 5 4 0 e + 0 0 2 ，+ 2 0 7 2 3 0 0 e + 0 0 l ，+ 8 9 0 9 9 8 8 e + 0 0 l ，+ 7 6 7 + 1 15 3 4 5 0 e + 0 0 2 ， + 2 0 7 2 3 0 0 e + 0 0 1 ，+ 8 9 0 9 9 8 8 e + 0 0l ，+ 518 前三项为数据点的x 、y 、z 三个坐标方向的坐标值，最后一项为坐标 点对应的灰度阈值。可以通过z 方向坐标值的不同，将每层c t 图片区分开 来，单独纪录。 哈尔滨工业大学工学硕士学位论文 2 2牙列轮廓数据提取 经过数据提取后，得到了牙列骨骼的层切面数据。图2 5 即为一层牙列 骨骼的层切面数据。但我们所需要的，是每层牙列骨骼的轮廓数据，在图 2 5 中以- 号显示者，然后通过每层之间数据点的相连，层与层之间的相 连，构成整个牙列的表面轮廓面。图2 - 5 中以o 显示的数据，对于我们来 说是多余的，需要将其删除。 图2 - 5 牙列骨骼层切面数据 f i g 2 - 5l a y e rd a t a so f t h e t e e t hb o n e s 2 2 1元胞自动机理论 元胞自动机( c e l l u l a ra u t o m a t a ，简称c a ) ，是一个时间和空问都离散的 动力系统。散布在规则格网( l a t t i c eg r i d ) 中的每一元胞( c e l l ) 取有限的离散 状态，遵循同样的作用规则，依据确定的局部规则作同步更新。火量元胞通 过简单的相互作用而构成动念系统的演化。不同于一般的动力学模型，元胞 自动机不是由严格定义的物理方程或函数确定，而是用系列横型构造的舰 则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此，元 胞自动机是。类模型的总称，或者说是个方法框架。其特点是时间、空 间、状态都离散，每个变量只取有限多个状态，且其状念改变的规则在时恻 和空间上都是尚部的口。 元胞自动机最基本的组成包括元胞、元胞空问、邻居及规则四部分。简 单讲，元胞自动机可以视为由个元胞空间和定义于该空间的变换函数所组 成，如图2 - 6 所示。 ， 图2 - 6 元胞自动机的组成 f i g 2 - 6t h ec o m p o s i n g so f c a ( 1 ) 元胞元脆又可称为单元，或基元，是元胞自动机的最基本的组成部 分。元胞分布在离散的维、二维或多维欧几晕德空间的品格点上。 ( 2 ) 元胞空间元胞所分市在的空间网点集合就是这里的元胞空间。理论 上，它可以是任意维数的欧几单德空间规则划分。目前研究多集中在。维 和一维元胞自动机上。= 二维元胞空问通常以四方网格形式进行划分，其优 点是直观而简单，而且特别适合于在现有计算机环境下进行表达显示。 ( 3 ) 规则根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动 力学函数，简单讲，就是个状态转移函数。 ( 4 ) 邻居在一维元胞自动机中，通常以半径来确定邻居，一个元胞距离 内的所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复 杂，冯。诺依曼( v o n n e u m a n n ) 经过研究，给出了冯诺依曼型厄胞邻居模 型。个元胞的上、下、左、右相邻四个元胞为浚元胞的邻居。这卑邻居 半径r 为1 ，相当于图像处理中的四邻域、四方向。其邻居定义如下： n = v i v i x ，v i v ) l l v i x - v 。i + i v , y - v o 。f l ，( v i x ，v i v ) z ) ( 2 2 ) 武中v 。、，v i y 邻居元胞的行列坐标值； v o x 中心元胞的行列坐标值； 此时，对1 ：四方网格，在维数为d 时，一个元胞的邻居个数为2 d ，图 固驴固 哈尔滨工业大学工学硕士学位论文 2 7 为冯诺依曼型元脆邻居图，黑色元胞为中心元胞，灰色元胞为其邻居 它们的状态起来计算中心元胞在下一时刻的状态【3 0 】。 图2 7 冯诺依曼型元胞邻居模型 f i g 2 - 7c e l l u l a rn e i g h b o u rm o d e lo fv o n n e u m a n n 2 2 2 轮廓数据提取算法 根据元胞自动机理论，并结合冯一诺依曼型元胞邻居模型，提出了一种 轮廓数据提取算法：将含有数据的元胞置为1 ，将不含数据的元胞置为0 。 根据冯一诺依曼型元胞邻居模型，将每一个元胞的四个邻居的值相加，如果 加和大于0 小于4 ，则该元胞内所含的数据为轮廓数据；如果加和等于“ 则该元胞内所含的数据为内部数据：如果加和等于0 ，则该元胞内不含有数 据。 | 1 i 1a1 i l 0 0c o 0 a ) 内部算子b ) 轮廓算子c ) 外部算子 图2 - 8 算法算子 f i g ，2 8a t i t h m e t i co p e r a t o r s 图2 8 即为算法的三种算子。其中a ) 为内部算子，c ) 为外部算子，这两 种算子是唯一的，即分别只有一个。b ) 为边缘算子，形式不唯一，一共有 1 4 个。 应用m a t l a b 语言将上述算法实现，便可将图2 5 中以表示的轮廓数 据点提取出来如图2 - 9 所示。 哈尔滨工业大学工学硕士学位论文 2 3牙列轮廓数据排序 图2 - 9 轮廓数据 f i g 2 - 9o u t l i n ed a t a s 经过上述轮廓提取算法提取出的数据点，是以从左到右，从上到下的规 则排列顺序的。按照这样的顺序连接这些数据点时，无法还原轮廓的真实形 状。由于每个轮廓的真实形状是一条有向的封闭曲线，所以必须将数据点按 照轮廓线的走向进行排序。 2 3 1空间相邻性排序算法 针对数据点的分布情况，采用了空间相邻性排序算法，也称为最近点对 排序法【3 ”。该排序过程实际上是一个搜索的过程，即在原始的边缘数据中 选定一个特定的起始点，然后从此起始点开始在原始数据存储区中遍历搜 索，选出离该起始点距离最近的一个点，并把起始点数据划入新的结果数据 区。然后以剐刚选出的点作为起始点，再次在原始数据存储区中遍历搜索， 选出与该点距离最近的点，并把该点划入新的结果数据区。依次搜索，当搜 索完成以后，新的结果数据区内存储的将是一列空间排列有序的轮廓数据。 2 3 2 算法分析 实现该算法时，有两个关键点需要注意。一个是起始点，另一个是相邻 哈尔滨工业大学工学硕士学位论文 性。如果能找到有效的起始点及相邻性判断算法，则问题得以解决。 首先是找寻搜索起始点。直接内插细分的边缘数据的第一点不能作为起 始点，因为它并不代表在某一空间取向上的目标轮廓的实际起始点，依目标 空间取向定，它可能是目标轮廓上的任何一点，在很特殊情况下可作为搜索 起始点，但般情况下是不能以其为空间趋向排序起始点的。 通过分析，有四种轮廓点可能是搜索起始点：一是x 值为最小的点，二 是x 为最大的点，三是y 为最小的点，最后是y 为最大的点。若目标是一直 线或封闭曲线时，则四个点均可作为起始点，但若目标轮廓是一不封闭的曲 线，则四个点就可能不都是空间位置起始点，但是至少有两个点是，其中一 个是由x 的最小或最大决定的，而另一个则由y 的最小或最大决定。由于我 们的目标轮廓是一条封闭曲线，并且只需要一个搜索起始点，故我们只选定 了由x 的最小或最大决定起始点和由y 最小或最大决定起始点两种情况之 一。至于究竟选择哪一种情况，则根据每层数据的具体情况和如何处理方便 来决定。 搜索的过程是相邻性判断的过程，这里采用两点距离最小为最近的原则 进行搜索，搜索算法如下： ( 1 ) 以起始点为准在所有轮廓数据中找寻其相邻点； ( 2 ) 将起始点之相邻点作为节点链入结果数据链表，计数指针加1 ； ( 3 ) 起始点更新为旧起始点的相邻点： ( 4 ) 删除原始数链表中为旧起始点相邻点的节点； ( 5 ) 判断计数指针是否等于所有的原始边缘数据点数； ( 6 ) 若上述判断相等则退出程序，否则重复前五个步骤。 具体程序实现时，是以相邻性为依据的，空间相邻是指两点之间距离最 近。利用大家所熟知的平面上两点距离的公式，先搜索起始点的相邻点，连 入结果链表，再去掉原始链表中起始点相邻点之节点，并把起始点的相邻点 作为新的起始点，继续搜索下去，直到所有数据全部排完为止。 2 4 牙列轮廓数据插值 用有限逼近无穷，用简单逼近复杂，即近似替代，是计算数学构造算法 的重要思想方法。应用这一方法构造函数近似表达式的问题，就属函数逼近 问题。解决函数逼近问题的方法有多种，其中较常用的方法是插值法。对于 轮廓曲线的插值算法的研究，就是将通过图像处理并经过涮选得到的插值基 哈尔滨工业大学工学硕士学位论文 点用一种较为简单且符合工程要求的函数形式表达出来1 3 ”。 在提取牙列轮廓数据的过程中，是按照一定的步长，也即取值间隔来在 牙列轮廓线上提取数据的，显然这不能够将轮廓数据完全提取出来。这样就 会带来一系列的相关问题：有的特征点由于在取值间隔之间，就会被遗漏； 有的点由于数据间隔较大，在连线时易出现剧烈弯折的现象，这些都会在还 原牙列轮廓线时造成牙列轮廓的失真。这就需要对提取出来的轮廓线数据进 行插值，以尽可能的减少失真现象，真实的还原牙列轮廓。 2 4 1轮廓曲线的插值算法 近年来，对人体骨骼等组织进行造型时所采用的插值算法主要有如下几 种算法。这些算法都是比较基础、经典的插值算法，但应用在人体骨骼造型 方面。却很简单适用，效果也很好。 ( 1 ) n 次拉格郎日插值多项式两个一次多项式的线形组合仍是一个一次 多项式。将求一次插值多项式的思想推广到一般就有： p n ( x ) = ：l ，( x ) y i ( 2 3 ) ，：万 p n ( x ) 为原f i x ) 的1 1 次拉格郎日插值多项式，并通常记为l n ( x ) ， 厶2 喜若翻( 2 - 4 ) 其中 c 讲，+ l ( z ) = ( x x o ) ( x x 1 ) ( x - - x n )( 2 - 5 ) l ( x ) ( i = o ，1 ，n ) 称为n 次插值基数。 拉格郎日插值多项式具有含义直观、形式对称的优点，对于形状无突 变的对象尤为适用。但这种插值多项式中的插值基函数依赖于全部基点，当 需增加插值基点时，原已算出的所有的 ( 工) 都要重新计算，对公式的计算必 须