（应用数学专业论文）图像插值与离散曲面去噪.pdf

捕要 摘要 图像插值和离散曲面去噪是计算机图形图像学中最基本的研究内容。图像插 值在数字图像处理中占有重要的地位，而离散曲面去噪则在数字几何处理领域中 有着广泛的应用，它是数字几何处理能够更加准确和有效进行的基础。本文主要 针对这两方面进行研究，提出了新的算法，分别是基于细分的图像插值算法和网 格( 点云) 的非收缩保特征去噪算法。 本文首先将基于法向的曲线细分技术应用到图像插值中，提出了一种基于细 分的图像插值算法，该算法无须建立中间连续图像模型，能自适应插值，而且插 值系数可为任意正实数。应用该算法，插值后边界清晰，自然，忠实地反映了原 始图像的面貌。相比传统的插值算法，边界处理效果好，线性复杂度且易于实现。 j 司时本文对离散曲面去噪技术作了研究，引入了在网格曲面处理中的齐次重 心坐标，对于网格中的任意顶点，都能用它的邻近顶点和邻近面片的加权齐次中 心表示。基于齐次重心坐标，定义了新的网格项点几何变量一一锐度因子。应用 齐次中心坐标和锐度因子技术，提出了一种新的网格曲面去噪方法。网格顶点可 由可变法向光顺和锐度因子去噪来还原和滤波，锐度因子能起到保持尖锐特征和 局部光顺几何信息的作用。同时，新的滤波算法在锐度因子为零时退化为传统的 滤波算法。本文算法不仅可以保持几何特征并避免局部收缩，而且复杂度低易于 实现。 关键词：图像插值，细分，齐次重心坐标，锐度因子，可变法向光顺，去噪 英文摘要 a b s t r a c t i m a g ei n t e r p o l a t i o na n dd i s c r e t es u r f a c es m o o t h i n ga r ef u n d a m e n t a lo p e r a t i o n s i n c o m p u t e rg r a p h i c sa n di m a g ep r o c e s s i n g i m a g ei n t e r p o l a t i o nc a nb eu s e dt o i m p r o v et h eq u a l i t yo fa ni m a g ea n dn o i s er e m o v i n gf o rad i s c r e t es u r f a c ew i l lh e l pt o s m o o t ht h es u r f a c e m o r e o v e r , d i s c r e t es u r f a c es m o o t h i n gw i l li m p r o v et h ee f f i c i e n c y o f m a n yo t h e ro p e r a t i o n sf o rd i g i t a lg e o m e t r yp r o c e s s i n g i nt h i st h e s i s ，w ep r o p o s en e w a l g o r i t h m sf o ri m a g ei n t e r p o l a t i o na n dd i s c r e t es u r f a c es m o o t h i n g ： 1 as u b d i v i s i o na p p r o a c ht oi m a g e i n t e r p o l a t i o n 2 s h r i n k a g ef r e em e s ha n dp o i n ts u r f a c es m o o t h i n gw i t hf e a t u r ep r e s e r v a t i o n w ep r o p o s ean o v e lm e t h o df o ri m a g ei n t e r p o l a t i o nb ye x t e n d i n gn o r m a lb a s e d s u b d i v i s i o ns c h e m ef o rc u r v ea n ds u r f a c ed e s i g n i m a g e sw i l lb ez o o m e di nb y i n t e r p o l a t o r ys u b d i v i s i o na n dn oi n t e r m e d i a t ec o n t i n u o u ss u r f a c em o d e ls h o u l db e e s t a b l i s h e d w i t hp r o p e rc h o i c e so ft h es u b d i v i s i o np a r a m e t e r s ，i m a g e sc a nb e i n t e r p o l a t e dw i t ha n yp o s i t i v er e a ls c a l ew h i l ee d g e sa n db o r d e r sw i t h i ni m a g e sc a nb e k e p tw e l l e x a m p l e sa n dc o m p a r i s o n sw i t hs o m eo t h e ri m a g ei n t e r p o l a t i o nm e t h o d s s h o wt h a tt h ea d v a n t a g e so f t h en e wi m a g ei n t e r p o l a t i o na l g o r i t h ml i ea ti t sc l e a r a n c e ， e f f i c i e n c ya n ds i m p l i c i t y w ei n t r o d u c e h o m o g e n e o u sb a r y c e n t r i c c o o r d i n a t e sf o rd i s c r e t es u r f a c e p r o c e s s i n g ，a n da n yv e r t e xc a nb ee x p r e s s e da sah o m o g e n e o u sw e i g h t i n gc e n t e l o fi t s n e i g h b o r i n gv e r t e x e sa n dn e i g h b o r i n gp l a n e s b a s e do nh o m o g e n e o u sb a r y c e n t r i c c o o r d i n a t e s ，an e wg e o m e t r i cv a r i a b l e ，s h a r p n e s sf a c t o r , i sd e f m e df o rm e a s u r i n g s h a r p n e s so fi n d e p e n d e n tv e r t e x e s w i t ht h et e c h n i q u eo fh o m o g e n e o u sb a r y c e n t r i c c o o r d i n a t e sa n ds h a r p n e s sf a c t o r , an e w f i l t e r i n ga l g o r i t h mi sd e v e l o p e d a l lv e r t e x e s c a nb er e s t o r e do rf i l t e r e db yv a r i a t i o n a ln o r m a ls m o o t h i n ga n ds h a r p n e s sf a c t o r d e n o i s i n g t h i sn e wf i l t e r i n ga l g o r i t h mw i l lr e d u c et os o m et r a d i t i o n a lm e s h s m o o t h i n gm e t h o d sw h e na l ls h a r p n e s sf a c t o r sv a n i s h n o to n l yc a nt h i sf i l t e r i n g m e t h o dp r e s e r v ef e a t u r e sa n db ef r e eo fl o c a ls h r i n k a g e ，i ta l s ob e n e f i t st h ep r o p e r t i e s i t 英文捕要 o f s i m p l i c i t ya n de f f i c i e n c y k e yw o r d s ：i m a g ei n t e r p o l a t i o n ，s u b d i v i s i o n ，h o m o g e n e o u sb a r y c e n t r i cc o o r d i n a t e s ， s h a r p n e s sf a c t o r s ，v a r i a t i o n a ln o r m a ls m o o t h i n g ，s m o o t h i n g i i t 第一章绪论 第一章绪论 1 1 图像插值的研究背景 人类主要通过视觉获取外界的信息，这使得图像在历史进程中扮演了一个很 重要的角色。早期的图像以书法和绘画的形式出现：工业革命后出现了照片和电 影等娱乐技术。随着图像数据大量涌现，逐渐形成了“图像处理”这门学科。 图像处理主要包括：图像的采集与量化：图像的增强；彩色图像处理技术：图像 分割；编码与压缩：恢复与重建；特征与识别；数字图像变形技术等多个方面。 随着计算机技术的高速发展，图像插值已经成为计算机图形学和图像处理的 重要组成部分 l g s 9 9 1 。所谓图像插值就是根据原始低分辨率图像数据生成更高 分辨率的图像数据 g u 9 6 】。这可分为两类问题：图像内的插值( 图像放大) ； 图像间的插值( 医学切片序列成像) 。从数据来说，图像插值使得图像数据有 少变多；从视觉上说，图像插值则使得原始图像更为清晰和易辨。图像插值作为 图像处理中的图像重采样过程的丰要部分，广泛用于改善图像质量、进行有损压 缩等等，因而图像插值在医学图像处理中占据着特殊位置 l g s 9 9 1 。 数字图像处理涉及到社会生活的很多领域，而图像插值技术作为其中的基本 内容，它在医学，军事以及工业等领域有着相当广泛的应用 l y w 0 3 】，随着手机 摄像、网络视频等新兴技术的广泛应用，研究新的图像插值算法有其必要性。 1 2 图像插值技术的发展 早期，多项式插值和样条插值技术是图像插值领域最被j “泛应用的 m a e 8 8 。 从图像采样时所依赖的模型看，这些技术实质上是对图像建立了连续数学模型， 然后按照插值系数重采样新的格点，得到日标数字图像。m a e l a n d 等将数字图像 的像素值插成三次样条或是其他样条，再根据插值要求进行重采样，构建新的数 字图像 m a e 8 8 ：胡敏等提出了以二元向量有理插值为基础实现图像缩放 【h t l 0 4 。此外，早期经典的最近邻域，双线性插值，双三次插值等还广泛应用 于a d o b ep h o t o s h o p 和g i m p 等商用软件中。虽然这类技术具有生成速度快的优 图像插值与离散曲面去噪 点，但却会产生明显的锯齿和模糊。 为了加强锐度、突出边界，出现了很多针对性算法。比较有代表性的有两类： 非物体边界导向的图像模型；基于物体边界的图像模型。第一类算法多数是对多 项式图像模型的改进，能达到突出边界的目的。r a m p o n i 引入可变距离的概念， 动态地调整双三次插值，从而解决图像曲线边界的锯齿现象e r a m 9 9 1 。c h u l h e e 等将b 样条技术应用于图像插值 c e u 9 8 。e 1 k h a m y 等基于三次插值算法，使 得插值误差在均方误差意义下最小 e m d 0 4 。第二类算法则根据初始图像中物体 边界信息进行插值。a l l e b a c h 以边界为导向，利用迭代逐步修正边界锯齿现象 a w 9 6 。j e n s e n 等针对低分辨率图像中每个格点建立的邻域，将其映射到最佳 连续空问，重采样得到目标图像 j a 9 5 。l i 等利用局部邻域的统计和边界信息对 图像进行插值 l 0 0 1 。h w a n g 等根据局部梯度信息，对双线性和双三次插值进 行修1 正 h l 0 4 。m u r e s a n 等基于最佳还原理论，自适应地进行图像插值i m p 0 4 。 虽然第二类方法能得到明晰的边界但是它们多数会要求对边界给出阈值，对于 不| - j 的边界阈值有不同的效果。 以上方法大都先给出离散数字图像的连续模型，然后重采样得到结果。考虑 到图像插值前后离散性的特点，研究一种由离散到离散，无须建立中问连续插值 算法显得非常合适。 1 3 离散曲面去噪技术的研究背景 随着计算机图形图像、c a d 工业设计、逆向工程、影视娱乐等等的发展， 计算机对于图形显示的真实性、实时性和交瓦性要求日益增强，关于三维数字数 据的研究越来越受到大家的关注。近年来，随着数学、计算机等学科的发展，几 何设计模型变得越来越复杂，数据量也随之大量增加，传统的几何设计造型方法 已经不能很好地胜任。于是，工业应用中3 d 几何扫描仪开始大量使用，这为获 取具有高度真实感的三维模型提供了有效的解决途径。 从数字建模的方法来看，主要分为连续造型和离散造型两种。前者，通过传 统的曲线曲面几何造型技术对三维模型直接进行设计，并把模型表示为点、线、 面的形式，在工程应用中，体现为c a d 组件造型、建筑设计等。每个部分都用 曲面片表示，该方法的优点：可对未知物体比如，机械零件和建筑物等的设计加 第一章绪论 入个性的创意；虽然该类方法已经非常成熟，但是还有很多不足：在曲面构造和 拼接上存在很大困难。同时，简单的曲线曲面所表示的物体也很难反映原模型的 细节特征。相比这些困难，后者有其巨大优势。离散造型技术从数据获取上分， 主要有两类：基于图像的造型；基于三维扫描仪造型。前者，通过照相机 获取单张或多张照片，然后基于这些照片重建物体的三维几何信息。实践结果显 示：基于图像的造型方法对于规则物体，特别是大型的简单的建筑物，能很好的 获取和估计其几何结构，在工程中具有很大的应用范围，随着图像插值、图像配 准、基于图像的绘制等技术的发展和完善，人们已经能够得到很好的场景设计和 显示的效果。但对于具有丰富表面细节特征和几何信息的物体，该类方法无法精 确重建几何。后者，利用激光测距三维扫描仪来精确表示三维数模型的表面和内 部数据点的举标，然后根据离散点集，运用曲面重建、网格三角化、特征检测、 点云处理等技术间接或直接地对三维数字模型进行处理，达到获取几何信息和重 建几何的目的。随着三维扫描仪硬件设备和软件的迅速发展，该方法具有广阔的 应用前景。 特别在逆向工程技术( r e v e r e e n g i n e e r i n g ) 中，运用三坐标测量法、激光扫描 法、工业c t 、核磁共振法和层去图像法等技术获取三维数据点，然后根据测量 数据得到原始物体的模型，已经是比较成熟的方法。例如，在医学领域，人体内 脏器官表面的三维数据点可以由c t 切片或核磁共振来得到，然后根据所得信息， 通过m a r c h i n gc u b e 等方法恢复原始物体的几何模型( 这种构造曲面的方法称为 曲面重建) ；在工程应用中，我们可以直接绘制三维模型，更常用的方法则是根 据实物转化为c a d 模型。 三维几何数据采集后，必须对它进一步处理才能被应用到其它领域，这称为 数字几何处理( d g p ) 。它主要分为以下两个方面：将三维数据参数化，然后通 过重采样、信号处理等技术，实现数字几何处理：基于微分几何理论，三维数 据是连续曲面的离散表示，将曲面上的几何量推广到离散情况，直接对三维数据 本身进行处理。前者的处理效果很大程度取决于数据参数化技术；后者的关键则 是如何估计离散数据的几何量。至此，我们可以将数字几何处理过程分为如下几 个步骤：数据获取和表示、光顺去噪、参数化和曲面重建、离散几何量的估计、 模型压缩和变形等等。从整个过程可以发现，光顺去噪是后续的数字几何处理能 图像插值与离散曲面去噪 够更加准确和有效地进行的保障和基础，因此必须事先进行光顺去噪处理。 另一方面，随着计算机图形，计算机视觉，以及c a d 工程应用中3 d 几何 扫描仪的大量使用，网格模型变得越来越复杂，与此同时，r u s i n k i e w i c z 和l e v o y 等发现即便是最高精度的3 d 扫描仪，由于测量环境、镜面反射和操作不当等凶 素，使得生成的网格数据模型难免存在噪声 r h l 0 2 ，l p c 0 0 1 。因此，在网格进行 数字几何处理之前，对其进行去噪和光顺显得非常必要。 在讨论本文研究内容前，先明确两个概念。噪声和特征：在信号处理理论 中，噪声被认为是随机的高频信号，本文认为网格上的局部扰动是噪声，而具有 整体形状和局部连续性的信息则是特征；曲线曲面的光顺和去噪：奉文认为通 过调整顶点数据，使得处理对象显得曲率变化比较均匀，1 司时保持对象特征便是 曲线曲面的光顺和去噪。 光顺和去嗓的数据对象一般为点云数据，或是经过三角化后的网格。光顺和 去噪的目的如上所述为：在消除点云或三角网格数据的局部扰动和噪声的同时， 保持网格( 点云) 模型的拓扑信息和几何特征不变，例如保证光顺后模型尖锐特 征等。相比图像去噪和信号去噪，三维数据的去噪算法更关注模型本身的几何特 征。根据特征保持性可以分为各向同性算法和各向异性算法，从算法结果角度分 析，各向同性的算法可以产生相对比较光顺的结果，但是很难保持特征，而且还 伴随着收缩的问题；各向异性的算法，基本能做到保持模型特征，但是无法避免 防止收缩的问题，或者就是简单地通过整体或局部调整顶点避免体积的变化，这 样又会带来不必要的变形。 通过上面的论述，我们可以明确一点，离散曲面光顺和去噪的两个难点就是 保持特征和防止收缩变形。本文的一部分主要工作就是引入了齐次重心坐标概 念，基于此提出离散曲面的保特征非收缩的去噪算法，基本上解决了离散曲面去 噪中的两个难题。本文所指的离散曲面，就是三角网格模型或是点云模型。 1 4 离散曲面去噪技术的发展 离散曲面去噪按照模型来分可以分成网格去噪和点云去噪，由于网格实际就 是带拓扑关系的点云模型，所以点云上很多方法都是网格上的推广。因此，本节 将重点介绍网格去噪的相关工作，同时简单介绍点云去噪算法的发展。 第一章绪论 早期网格去噪算法是由传统信号处理技术推广而得。t a u b i n 将信号处理的知 识引入到网格，通过对l a p l a c i a n 算子的线性逼近，提出各向同性的快速光顺网 格的算法 t a u 9 5 1 ，并减少了网格去噪后的收缩变形幅度，结果说明信号处理算 法对于网格处理是非常有效的。d e s b r u n 通过隐式曲面光顺得到鲁棒的滤波算法， 还提出了离散网格平均曲率流算法，让顶点在法向上以平均曲率值的速度移动， 实现网格光j i 顷 d m s 9 9 。曲率均匀法的目标是减少网格项点间的曲率变化，以平 均后的曲率与原曲率之间的差值来确定顶点的调整量，该方法计算速度较快，但 容易导致网格趋于球面。另_ 种网格处理算法是由g u s k o v 提出的基于多变量有 限差分的松弛算法 g s s 9 9 1 。k o b b e l t 和s c h n e i d e r 等采用平均曲率的高阶或内在 l a p l a c i a n 算子进行网格曲面光顺 k c v 9 8 ，s k 0 1 ，r m s 0 1 。除了l a p l a c i a n 算予， p e n g 和a l e x a 也将w e i n e r 滤波算法推广到网格处理中 p s z 0 1 ，a l e 0 2 。 虽然l a p l a c i a n 算子光顺技术能有效处理数据量较大的网格曲面，但是它会 过度光顺尖锐特征和高频率噪声。而图像滤波的相关文献中指山基于各向异性的 算法能很好地保持特征 p m 9 0 ，s c m 9 1 。因此，近几年各向异性的网格滤波算法 成为热点。为了保持网格尖锐特征，c l a r e n z 和b a n 等在滤波前计算每个顶点 的主曲率，根据所得结果进行各向异性的滤波 c d r 0 0 ，t a u 0 1 ，b x 0 3 。h i l d e b r a n d t 和p o l t h i e r 给出了网格上的离散曲率公式，然后通过滤波后的曲率来得到去噪的 顶点 h p 0 4 1 。除了直接对网格顶点滤波的算法，t a s d i z e n 和s h e n 等先对法向进 行滤波，然后修正网格，使其符合滤波后的法i 句 t w b 0 3 ，s b 0 4 1 。各向异性的方 法虽然能保持特征，但是具有局部收缩和高计算量的缺点。 所谓收缩，在图像上来说就是灰度值趋向一致；而对于曲面来，收缩则是指 通过多次迭代后，去噪曲面最终趋向一个点 w a n 0 5 1 。这样的去噪结果会给工程 虑用中带来很大的麻烦，所以近年来为了处理收缩问题，山现了一些全局或局部 保体积的滤波算法。d e s b n m 通过均匀地缩放网格曲面达到保体积的目的 d m s 9 9 】。h u b e l ie ta l 和l i u e ta 1 则通过改变邻近顶点位置保持局部体积 h g 0 1 ， l b s 0 2 。然而，网格曲面收缩并不是均匀产牛的，所以第一类算法还会使网格 变形。第二类方法，理论上有效地保证光顺过程中某些几何度量的变形最小化。 但是它求解过程复杂、计算量大、速度慢，同时还会降低光顺的质量，经过多次 迭代滤波后还会导致变形。 图像插值与离散曲面去噪 本文算法和双边滤波算法具有密切的联系。双边滤波是一种将定义域滤波和 值域滤波相结合的非线性滤波算法 t m 9 8 ，在更高维空间上同样适用 b a r 0 2 。 双边网格滤波本质上是：光顺邻近顶点到当前顶点切平面的偏移量 f d c 0 3 1 ，或 者光顺当前顶点到邻近顶点切平面的偏移量 j d d 0 3 。和其他各向异性的方法一 样，双边网格滤波算法也有收缩的问题。基于齐次重心牮标理论，使用可变法向 光顺，双边网格光顺是本文算法的一个特殊情况。当所有锐度因子为零时，本文 算法退化为双边网格光顺。 1 点云滤波算法有很大一部分根据网格上的工作得到。p a u l y 将l a p l a c i a n 算 子结合点云简化，然后对点云重采样得到光顺的顶点 p k g 0 2 a 。p o l t h i e r 通过 w e i n g a r t e n 映射定义点云的方向曲率和主曲率，根据所得曲率的值修改各向同性 的l a p l a i c i a n 滤波算法，得到新的各向异性方法 l p 0 5 。不过此类算法还是会产 生收缩的问题。 有别于网格，无拓扑连接关系是点云的特点。因此出现了m l s f m o v i n gl e a s t s q u a r e ) 的方法，该方法作为定义连续和光顺点云曲面被广泛用于点云的显示和造 型 l e v 0 4 ，a b c 0 3 ，通过m l s 逼近点云，w e y d c he t a 1 根据所得到的投影顶 点，对原始点向投影点进行移动，完成对点云的光顺。但是此类方法往往计算量 比较大 w p k 0 4 1 。 区别于以上方法，还有一类方法主要关注点云法向的预测和光顺。凶为在点 模型显示中的效果取决于法向。j o n e s 运用双边滤波算法预测光顺顶点位置，然 后根据所得结果反求顶点法i 向 j d z 0 4 。h u 重建顶点的多层多边形环邻域，然后 利用双边滤波器进行法向估计，达到光顺的目的 i - i p o s 。虽然这类方法能得到很 好的效果，但是顶点位置没有改变，应用中存在局限。 结合本文网格滤波的新算法，基于齐次重心坐标理论，提出点云的可变法向 光顺，得到了新的保特征非收缩的点云滤波算法。 1 5 本文主要工作 本文的主要研究内容有两部分组成：基于细分的图像插值算法：离散曲 面( 网格、点云) 去噪光顺算法。结合现有的研究成果，针对其不足之处，本文 提山了新的图像插值算法以及网格( 点云) 去噪算法。本文各章节内容安排如下： 第一章绪论 第一章，分两部分介绍了图像插值和离散曲面去噪技术的研究背景和主 要方法，对近年来提出的图像插值技术和去噪光顺方法进行了分析和比 较，给出了这些方法的基本原理及它们各自的优缺点，最后结合作者在 本领域的研究工作，对相关研究重点作一些分析。 第二章，首先简单介绍基于法向的曲线细分算法，然后根据该算法的原 理，提出一种利用曲线曲面的细分插值技术直接进行图像插值的算法， 该算法的一个基本出发点是由离散到离散，无须建立中问连续插值模 型。提出了保细节的基于细分的图像插值算法。并与现存的经典算法做 了比较，效果较好。 第三章，主要介绍离散数据齐次重心坐标理论。通过与离散曲面上的离 散几何量( 法向量、曲率等) 的比较，证明齐次重心坐标所定义的锐度 因子相比传统几何量更能反映局部区域内的几何属性。并给出了网格和 点云上的局部锐度因子的定义。 第四章，基于齐次重心坐标理论和锐度凼子，给出了保特征非收缩的网 格去噪算法。该算法基本同时解决了保特征和非收缩的两个问题。在特 殊情况下，该算法可以退化为f l e i s h m a ne ta 1 提出的双边滤波算法或是 l a p l a e i a n 去噪算法。 第五章，基于齐次重心坐标理论和锐度凶子，将第四章中的网格去噪算 法推广到了点云模型，提出了点云的保特征非收缩算法。该算法基本同 时解决了保特征和非收缩的两个问题。在特殊情况下，该算法可以退化 为f l e i s h m a ne ta 1 提出的双边滤波算法或是l a p l a c i a n 去噪算法。 在最后一章中，对本文研究内容做了总结，并对该领域今后的研究工作 和研究趋势作一个展望。 图像插值与离散曲面去噪 第二章基于细分的图像插值算法 2 1 算法背景 现存的图像插值算法一般都给出离散数字图像的连续模型，然后经过重采样 得到结果。考虑到图像插值前后离散性的特点，本文研究一种利用曲线曲面的细 分插值技术直接进行图像插值的算法，该算法的一个基本出发点是由离散到离 散，无须建立中问连续插值模型。将图像数据理解为规则的网格曲面，则图像插 值问题便可转化为该规则网格的细分插值问题。然而图像插值与曲线曲面细分也 存在着几方面区别：一是图像插值一般要求任意倍数而细分插值往往是整数倍或 几种固定格式；二是细分插值时往往考虑极限曲线曲面的收敛性与光滑性而图像 插值时更希望能保持图像边界特征。 针对图像插值与曲线曲面细分之间存在的异同点，本文采用几何插值细分格 式 y a n 0 5 ，y a n 0 6 进行图像插值。几何插值细分在构造光滑曲线曲面时可以避免 传统线性细分方法所引起的几何变形，得到扭曲小的曲线曲面。另外，本文通过 对几何插值细分中位置参数和光滑参数的自适应选取不仅可以得到任意倍数的 图像插值同时还可以清晰地保持了原始图像中的边界信息。下节本文介绍基于法 向的曲线插值细分算法 y a n 0 5 ，y a h 0 6 1 。 2 2 基于法向的曲线插值细分算法 曲线插值细分是计算机辅助几何设计领域中非常有效的形状设计技术，对于 曲线插值细分，在每次细分中计算所得的新顶点将被加入到原控制多边形中，所 产生的极限曲线将通过控制多边形所有顶点。y a n g 引入顶点法向，细分时动态 计算新顶点的偏移量，给出了基于法向的曲线插值细分算法，选取合适的参数， 极限曲线具有g 1 连续性 y a n 0 6 。 设控制顶点序列为 ，则基于法向曲线插值细分的具体公式如下： r 第二章基于细分的图像插值 i 旌? l2 岔 1 p 黜；( 卜s ? ) p 三。+ s 槲+ v ? 这里o 乞s ? 1 一岛 l ，v ? 为相对于边或的位移偏量。在给出v ? 之前，先 给出每个顶点的单位法向群，如图2 1 所示。设以。，和p ：，是彼此不重合的 三个连续的顶点，则p ：处的单位法向取为与匈乞p ? 藏，的角平分线平行，且所有 法向位于曲线同一侧。定义处的切向z 。如下： 耻隔， 这野2 赫一2 龋硼= ( 札驯，那吲处的靴法 向一? = ( 一彳，彳x ) 现在，给出边正。的位移偏量v ? 的定义。如图2 2 所示， p 。= ( 1 一s ? ) p 乜+ s ? p ；，位移偏量v ? 表示： 口= 甜( 笱畦。+ 矿) 这里硝- - 一一i - ，( 以，一p ，) ，= 群( 一n ) ，o - 0 ，o 且= ，= 1 。 这里 t 。孓y 。 。 。 p ，。 。 图3 1 齐次重心坐标 为了求解，将等式( 3 2 ) 写成如下形式： f h ( p ) = p 7 ( ：暑q ) p + p 7 ( 以倒m - i 。 t 4 ) p r 3r 、 = p r q p q = 1oo o10 00l x ? 一y 一z q = i 。- 1 墨q + 地。m - i o o t 哆 凶为矩阵q 和彳j 彳，都是对称矩阵，所以q 也是对称矩阵。则q 可表示为如下形 式： q = 吼l吼2 q l zq 2 2 q 】3口2 3 吼4窜2 4 9 1 3吼4 q 1 3 吼4 q 3 3q h 9 3 49 4 4 对函数o ( p ) 求各偏导，可以得到如下等式 i 十 _ 啊，听，i 第三章齐次重心坐标 o f = n 一( p ) = 9 1 1 x + 9 1 2 y + 吼3 z 十吼4 i ! ! 至! 堕：g ：，+ g ：，+ g ：，：+ g 。 i ! ! ! ： 堕：吼，z + g ：，y + g ，：+ q 。 求解方程p 7 q p = r a i n 等价于求解如下线性方程组 必：o 暇 型：o 胛 o f n ( p ) ：0 0 2 ( 3 4 ) 因此，齐次加权中心吼的笛卡尔坐标可以通过求解得到，具体表达式如下： 瓣q 1 2 新引 c ss ， 得到点面集合的齐次加权中心后，就可以给出从加权中心出发指向各个点和 定理3 1 ：令吼是点集只( j = 0 1 ，一1 ) 和平面集口，( ，= o 1 ，m 一1 ) 的齐次加权 中心，记= p ，一以，= ( - a j q 。) ，则有： ：b _ + 总：o = o 证明：显然和分别是从齐次加权中心吼出发指向只和疗，的向量。因为，q 。 是点集p ，( f _ 0 1 ，一1 ) 和平面集疗，( j = o ，1 ，m 一1 ) 的齐次加权中心，所以 ，y 。，：。便是线性方程( 3 4 ) 的解。则有： o = 3 f f n ( q ) = 一；：t + 以：r ，巳4 吼 。= 掣= n 一_ + 以。m - i 。o 饥 ( 3 6 ) o = 丁o f h ( q n ) 咱一暑+ 以舢mi ，i a s 吼 图像插值与离散曲面去噪 把上式用向量形式表示可得： 奈( 吼咱) + “m 。- 1 0 ( 爿，吼) ，= o 这便证明了以上结论。口 根据定理3 1 的结论，定义齐次重心坐标如下： 定义3 1 ：如果存在s i o ( i = 0 , 1 ，i 一1 ) ，t o ( i = o ，l ，m - 1 ) ，t h 0 满足 ：= l ，m 。- i o = 1 且9 。i = 0 s i l + 以：o = o ，则s 如= o ，l ，i 1 ) ， f ，( f = 0 , 1 ，m 1 ) ，i t h 便称为q 。相对于p ，( f o ，l ，l 1 ) 和乃( ，= 0 , 1 ，聊一1 ) 的 齐次重心举标。 这里的参数地调节邻近顶点和邻近平面对于齐次加权中心的影响大小。特别 地，当地= 0 时，齐次加权中心吼退化到点集的中心吼，当1 2 h 趋于无穷大时，吼 逼近平面彳，p = 0 ( j = o 1 ，一1 ) 的广义交点。通过定理3 1 的证明，还可以 得到以下结论： 定理3 2 ：令以= = 4 吼t m ，b ：z ip s ，p ，一吼，则有胁一。一b = o 口 3 2 离散凸曲面几何 这部分将重点介绍离散凸曲面顶点的齐次重心坐标的表示方法，基于此还将 在下节中定义离散顶点的锐度因子。 从微分几何的角度来看，在非平面上的点q 根据它的高斯曲率吒可以分成三 类情况。如果k q 0 ，则点g 处的两个主曲率同号。本文称后两种情况在 点q 处是局部凸曲面。 第三章齐次重心坐标 ( a ) 网格的顶点情况 ( b ) 点云的情况 图3 2 顶点的邻近顶点和切平面 本文假设网格曲面由原始曲面通过足够密度地采样而得，这样每个顶点处是 否为凸可以明确得到。对于网格，顶点的邻近顶点和平面的选择方法很多，这里 可以选取第一圈邻接点作为邻近顶点( 或是当前点包围球中的点) ，选取第一圈 三角形的邻接三角形为邻近平面，如图3 2 a 所示；对于点云，选取当前点包围球 中的点作为邻近顶点，邻近平面则选取部分邻近顶点的切平面( 第五章中给出切 平面的定义) ，如图3 2 1 0 所示。对于在局部n l 网格和点云上的顶点有如下结论， 这里我们证明网格顶点的情况： 定理3 3 ：设q 是局部凸网格上的顶点，它的邻近顶点和邻近平面分别为 乃( f = 0 ，l ，l - 1 ) 和口，( = o ，l ，m - 1 ) ，则存在一组大于零的系数使得q 为 b ( f = o 1 ，一1 ) 和疗j ( ，= 0 1 ，m 一1 ) 的齐次加权中心。 证明：假设n q 是点q 处曲面指向凸方向的法向，以是点q 处的切平面，则所有 点吼都在切平面的下面或一侧。取位于切平面以下的平面曩，且满足 2 3 图像插值与离散曲面去噪 以死。q 处的法线和直线q p ，与平面曩的交点分别为4 ，声。( i ；o ，1 ，l 一1 ) 。此 外，声满足p 。一qc i ( p ，一q ) ，这里c f 0 ，4 位于平面矾上的凸多边形b o b ，p 内部。那么存在一组正系数缸使得，口= ：6 f 卢，且厶一一j ：。l - i b 。= l 。这样q 到毒的 向量可以表示为：4 一q = e i - 。b , q ( p ；一q ) 。令吼= g + ( o g ) ：缸t ，则