（计算数学专业论文）具有不同拓扑结构的平面云点曲线重建算法研究与实现.pdf

摘要 数字图像处理技术是随着人类文明的发展逐渐形成的- r - j 学科，而曲线、曲面重建又 是数字图像处理的一个重要分支，也是逆向工程的两个主要问题传统的曲面重建方法， 是按点一线一面的重建顺序来获得重建曲面【1 l ，先由点定义出一组特征线，然后再由这 些特征线构造曲面因此，曲线重建在曲面重建问题中也扮演着重要的角色 本文针对散乱点平面曲线重建这一问题，在场表示的曲线重建算法的基础上，对于 具有复杂拓扑结构的平面云点，给出了人工交互和自适应两种构造初始曲线的方法并通 过大量的实验表明由这两种方法构造的初始曲线，经过场函数迭代，都可以得到满意的重 建效果全文的主要内容如下， 第一节我们首先综述了曲线重建的基本知识，论述了到目前为止国内外学者在曲线 重建方面的研究成果，并在此基础上引出了本文的研究课题第二节简单论述了场表示 的曲线重建算法的原理，场函数的构造准则以及由初始曲线获得重建曲线的迭代方法第 三节我们给出了初始曲线的选取准则，指出人工选择的初始曲线，应尽量接近原始数据点 集，反映出该点集的大致拓扑结构第四节我们给出了自适应选取初始曲线的算法步骤， 并指出用这种方法得到的初始曲线，经过迭代，可以获得与人工选择的初始曲线一样的重 建效果 关键词：曲线重建，逆向工程，平面云点，场函数；初始曲线 a b s t r a c t t h ed i g i t a li m a g ep r o c e s s i n gt e c h n o l o g yi sas u b j e c tw h i c hg r a d u a f i yf o r m sa l o n gw i t h h u m a nc i v i l i z a t i o nd e v e l o p m e n t ，w h i l ec u r v ea n ds u r f a c er e c o n s t r u c t i o na r et h ei m p o r t a n t b r a n c h e so fd i g i t a li m a g ep r o c e s s i n ga n da r et w om a i nq u e s t i o n sa b o u tr e v e r s ei n g i n e e r i n g t h et r a d i t i o n a ls u r f a c er e c o n s t r u c t i o no b t a i n sr e c o n s t r u c t i o ns u r f a c ea c c o r d i n gt ot h es p o t l i n e s u r f a c eo r d e r 1 ，a tf i r s tw ed e f i n eag r o u po fc h a r a c t e r i s t i c sl i n e sb yt h es p o t sa n d t h e ns t r u c t u r es u r f a c eb yt h ec h a r a c t e r i s t i c sf i n e s t h e r e f o r e ，c u r v er e c o n s t r u c t i o na c t sa n i m p o r t a n tr o l ei nt h es u r f a c er e c o n s t r u c t i o n t h i sp a p e rc e n t e r so nt h ei s s u eo fc n r v er e c o n s t r u c t i o nf r o mt h eu n o r g a n i z e dp o i n t s ， u n d e rt h ee x p r e s s i o nc u r v er e c o n s t r u c t i o na l g o r i t h mf o u n d a t i o n r e g a r d i n gt ot h ep l a n e c l o u dw i t hc o m p l e xt o p o l o g y , w ei n t r o d u c et h em e t h o do fm a n - p o w e ra n da u t o - a d a p t e d t os t r u c t u r et h ei n i t i a lc u r v e a n di ti n d i c a t e st h ei n i t i a lc l l r v ef r o mt w ok i n d so fm e t h o d s w i t hm a s s i v ee x p e r i m e n t s ，w em a yo b t a i ns a t i s f a c t i o nr e c o n s t r u c t i o ne f f e c ta f t e rf u n c t i o n i t e r a t i o n t h i sp a p e ri n c l u d e sa sf o l l o w s ： t h ef i r s ts e c t i o n ，w es u m m a r i z ec a l v er e c o n s t r u c t i o ne l e m e n t a r yk n o w l e d g e ，a n d e l a b o r a t et h ed o m e s t i ca n df o r e i g ns c h o l a r si nt h ec u r v er e c o n s t r u c t i o nr e s e a r c hs of a r ，t h e n d r a wo u tt h i sp a p e rr e s e a r c h t h e6 e c o n ds e c t i o nw ec o n c e r nw i t ht h ea l g o r i t h mp r i n c i p l e o ft h ef i e l de x p r e s s i o nc u r v er e c o n s t r u c t i o na n dt h ef i e l df u n c t i o ns t r u c t u r ec r i t e r i o na n d t h ei t e r a t i o nm e t h o do fr e c o n s t r u c t i o nc u r v eb yi n i t i a lc u r v e a n di nt h et h i r ds e c t i o n w ei n t r o d u c et h es e l e c t i o nc r i t e r i o no fi n i t i a lc u r v e ，a n dp o i n to u tt h a ta r t i f i c i a l l ye l e c t i n g t h ei n i t i a lc n r v es h o u l da p p r o a c ht h ep r i m a r yd a t as e to fp o i n t sa 8f a ra 8p o s s i b l e ，i tc a n r e f l e c tt h ea p p r o x i m a t et o p o l o g yo ft h es e to fp o i n t s t h ef o u r t hs e c t i o n ，w ei n t r o d u c et h e a l g o r i t h ms t e po fa u t o - a d a p t e ds e l e c t i o ni n i t i a lc u r v e ，t h e nw ep o i n to u tt h eo p t i o ni n i t i a l c u r v ew i t ht h i sm e t h o d ，w ec a no b t a i nt h es a m er e c o n s t r u c t i o ne f f e c tw i t ht h em a n u a l s e l e c t i o ni n i t i a lc n r v ea f t e rp r o c e s s i n gi t e r a t i o n k e yw o r d s ：c u r v er e c o n s t r u c t i o n ，r e v e r s ei n g i n e e r i n g ，p l a n ec l o u d e dp o i n ts e t ，f i e l d f u n c t i o n i n i t i a lc u r v e l l 第一节绪论 随着计算机技术的普及与进步，计算机数字图像处理近年来也得到了迅猛的发展， 而图像中的目标识别与测量是图像处理与分析的重要任务，通过现有的图像分割技术得 到的目标边缘常常是不连续的曲线段或分片曲面，甚至是无序的离散点集利用这些离散 点集构造目标的连续边界是目标测量的基础【1 9 】另外，从点集出发进行曲线、曲面重 建在计算机制图和计算几何等方面也得到了广泛的研究在图像分析、医学图像、逆向工 程和计算机视觉中都有着广泛的应用 1 1曲线重建的基本知识 逆向工程的一个主要任务就是由物理模型重建出几何表示模型，其中包括数据采集， 预处理、曲面拟合和建立c a d 模型四个步骤【2 】，其核心问题是如何从采样点出发重建 出曲线、曲面模型如果所需要重建曲线的点集采样于某实际物体的特征线，或者是该物 体的截面线，那么特征线或截面线重建往往也是曲面重建的必要步骤和前提条件又如在 计算机视觉中，通常要考察如何从图像或扫描获得的离散数据点重建几何模型，以利于形 状分析和识别逆向工程和计算机视觉都要求由已知采样点集拟合出一条或多条曲线，反 映出该点集的形状和走向，这就是常说的曲线重建 1 2曲线重建的分类 关于散乱点集的曲线重建，根据采样点集的性质可分为有序离散点集的重建和无序 离散点集的重建 1 2 1 有序离散点集的曲线重建 所谓有序离散点集的曲线重建是指给出依次采样于某条已知曲线上的一系列采样 点，如何构造出一条曲线依次通过或近似通过这些采样点，作为原始曲线的逼近 关于有序离散点集的曲线重建，已经有了许多成熟的研究，m c a l l i s t e r 用二次样条曲 线进行插值得到重建算法【3 】f c i t s c h 和c l a r s o n ，b u t l a n d 等人给出了用分段三次由线 】 进行插值的曲线重建【4 ，5 】l a v e r y 在2 0 0 0 年给出了一种用三次光滑l 1 样条多尺度地 保形拟合数据点集进行曲线重建【6 】e d m o n d 和s y l v a i n 着重研究了基于v o r o n o i 图和 d e l a u n a y ( 德洛奈) 三角剖分得曲线重建算法，对点集的d e l a u n a y 三角剖分进行网格插 值，快速准确的得到重建曲线【7 】 1 2 2 无序离散点集的曲线重建 在逆向工程中，一个更常见的问题是无序离散点集的曲线重建由于数据采样方式 的不同，使得到的采样点没有一定的组织形式，而是一组无序的离散数据点云，而且不可 避免的带有噪音我们无法也不需要找出一条曲线通过所有的采样点，只需根据该点集的 分布拟合出一条反映原始数据点云的形状与走向的曲线，作为重建曲线对于无序数据点 的曲线重建，近年来已逐步受到人们的重视，到目前为止，现有的工作大致分为四类： ( 1 ) 回归或最小二乘拟合的方法：如l e v i n l 8 ，l e e 9 】等利用移动最小平方法( m o v i n g l e a s t s q u a r e ) ，对原始点集进行两次最小二乘回归，调整数据点的位置，细化点云，重建 出曲线同时最小生成树的引入，解决了当两组点集相距过近无法正确重建出曲线的问 题 ( 2 ) 由相应的曲线模型出发直接进行重建：f a n g 给出了一种基于弹力模型的无序点 曲线重建算法，通过模拟曲线的受力情况，构造一组能量函数，将曲线重建问题转化为关 于能量函数的极值问题 1 0 】t a u b i n 利用隐式曲线模型，把已知数据点作为约束条件， 直接求解曲线参数，得到重建曲线 1 1 】 ( 3 ) 采用图像细化的方法实现曲线重建；如p o t t m a n n 将原始的数据点投影到平面网 格上以生成二值图像，然后借助于图像细化的算法得到重建曲线【1 2 】g o s h t a s b y 先由 离散点集构造出一势函数并生成灰度图像，运用离散梯度算法对点集进行分块并确定出各 点的参数值，最后用高斯有理曲线( r a t i o n a lg a s s i a nc u r v e ) 对原始点集进行曲线拟合， 得到重建曲线f 1 3 】 ( 4 ) 采用抽取骨架法进行曲线重建：物体的骨架就是位于物体内部的并能体现其形 状特征的简化图形a h u j a 等人讨论了对于给定的采样于区域边界上的一族数据点，如 何通过构造潜在的势函数，抽取出区域骨架的方法a m e n t a 等人提出了基于p 骨架于 v o r o n o i 图的c u r s t 算法，给出了对于足够密的采样于某条平面曲线上的一族采样点，如 何用多边形曲线来逼近原始曲线 1 4 】。 2 1 3本文产生的背景 逆向工程是随着计算机技术的发展和成熟以及数据测量技术的进步而迅速发展起来 的一门新兴学科它的出现，改变了原来c a d 系统中从图纸到实物的设计模式，为产品 的迅速开发以及快速原型化设计提供了一条新的途径 曲线、曲面重建是逆向工程中两个重要问题，从已知采样数据点出发构造物体的几 何模型是对物体进行分析、计算，和测绘的根据，对于无序带噪音数据点的曲线重建，近 年来已逐步受到人们的重视，提出了许多种曲线重建算法 文献【1 6 】中，钟纲给出了利用场函数表示的曲线重建算法假定每个采样点都带有 单位电荷，相应地由此构造了一个反映平面点集分布稠密程度的场函数，以场函数脊线在 平面上的投影曲线作为重建曲线该方法理论上非常简单，关键是在初始曲线的选取上 文章中，对于闭曲线采用最小包围盒作为初始曲线的迭代次数多、速度慢对于开曲线必 须人工指定初始曲线，且重建出的曲线可能会是双边曲线而对于多连通曲线，需要根据 点集的连通性将它分成若干个p 连通子集，然后对每个子集进行重建但是这样做会对 点集的分布状况造成破坏，使得场函数不能真实的反映整体点集的分布情况对于自交曲 线或具有复杂结构数据点集的曲线，需要进行较多的人工干预，而且重建效果不很理想 这就给我们提出了这样的问题，如何能在不对原始点集进行分块的前提下，选择恰当的初 始衄线，以加速迭代，并能得到高质量的重建曲线 1 4本文的主要工作 本文的第二节中，我们首先对基于场函数表示的曲线重建算法作了简要的介绍然 后在第三、四节中，对于具有任何复杂拓扑结构的平面点云，不需要将它分成若干个连通 子集，分别用人工交互和自适应这两种方法选取适当的初始曲线，以减少迭代次数，加速 迭代同时通过大量的实验来说明这种选取初始曲线的方法，对于具有任何复杂拓扑结构 的平面曲线的重建都可以得到满意效果 3 第二节曲线重建原理及算法 前面我们已经指出，曲线重建是逆向工程的核一5 - 问题，对于无序数据点集的曲线重 建，到目前为止已经有了许多成熟的算法我们这里先介绍一下场表示的曲线的重建算 法首先假定每个采样点都带有单位电荷，相应的由此构造一个反映平面点集形状与分布 稠密程度的场函数，以场函数脊线在平面上的投影作为重建曲线为得到脊线的投影曲 线，我们可先在平面上选取一条适当的初始曲线，令初始曲线沿场函数的梯度方向运动， 其极限位置便为重建曲线因此初始曲线的选取是曲线重建中至关重要的一步，选取质量 高的初始曲线，可以使得曲线重建的效果非常好下面我们先简要讨论一下场表示的曲线 重建原理及算法 2 1曲线重建的原理 2 1 1 记号和定义 数据点集；s = k ：( 鼢，玑) ) 盘1 为已知平面上的一组离散的带误差的无序采样数 据点 点的邻域：p 为点集s 中的任意一点，定义点p 的p 一邻域为 ( p ) = qld ( p i q ) p ，q r 2 ) 点集的邻域；点集s 的p 一邻域为( s p ) = u p ( p ) 采样密度：s 为一组采样数据点，若存在一个最小的正数p ，使得s 中的任一点的 p 一邻域中都含有s 中的其他数据点，则称s 的采样密度为p p 一道路连通：a ，b 为点集s 中的任意两点，如果存在s 中的一组点列岛，p 1 ，r ， 满足d ( b ，只+ 1 ) p ，a = 0 ，n 一1 ) 且昂= a ，r = b ，则称a ，b 两点p 一道路连 通；若点集s 中任意两点都是p 一道路连通的，则称点集s 是p 一连通的 p 一连通子集：p 为点集s 中的任意一点，称s 的包含p 的p 一连通子集为 q = qf 尸，q 两点p 一道路连通，q s ，也称之为p 一连通分支当s 只有一个户连 通子集时，s 是p 一连通的 4 2 1 2 算法的基本思想 设点集s = kj ( 救，玑) ) 盘1 为平面上的一组采样数据点，采样密度为p 我们将s 中的每一点k 视为一个带单位电荷的粒子，若限制在平面上考虑，这样的带电粒子便可 形成一个电场，即平面上每一点都对应着一电场强度，并且电场强度的大小随着距点k 距离的增加而衰弱所有带电粒子共同作用构成整个电场，我们取该电场分布中场强最大 的曲线作为重建曲线为了便于重建与计算，对于每一点k ，我们定义该点对应的场分 布函数为仇) 这里我们称g , i x ) 为基函数，应满足以下条件 i 鲰( x ) = 1 d ( x ，k ) p 寺俄( x ) 1 p d ( x ，k ) p + 5 1 2 1 ) l 历( x ) = 嘉 d ( x ，k ) = p + e 【0 1x ( 墨p ) 【，( x ) k ，因而场函数( x ) 值的大小反映了x 附近点集分布的稠密程度 对于平面上的任意一点) 乇，若场函数，在该点的梯度为零，则称j 而为，的局 部极值点对于平面上的一条曲线，y ( 8 ) ，若该曲线上任意一点的法向与场函数，在该点 的梯度方向垂直，即v f ( t i s ) ) ( 7 ( s ) ) = 0 时，其中n ( i s ) ) 为曲线- y ( s ) 的法向，此 5 时称( - y ，( 7 ) ) 为场函数的一条脊线事实上，当s 为曲线，y ( 8 ) 的弧长参数时，我们有 k b ( s ) ) = 象7 ( s ) ，这里后是曲率，则脊线的投影曲线应满足方程 v m ( s ) ) 。面a - 7 ( 8 ) = o ( 2 2 ) 2 1 3 基函数的选择 在算法的设计过程中，需要构造一组基函数满足条件( 2 1 ) ，这里，对于已知的数据 点集s ，采样密度为p ，构造一组基函数如下； 舭，_ 斋戮2 其中d ( x ，k ) 为x 到点的欧氏距离，n 为点集s 中点的个数 当然，满足条件( 2 1 ) 的基函数可以是多种多样的，我们也可以构造如下的基函数： 皿c x ，= 1 一半。x ，一曲：妻：篆；三： 通过大量的实例分析，比较不同的基函数下得到的重建曲线，我们发现，只要构造 的基函数满足条件( 2 1 ) ，得到重建曲线虽然在细节上有所不同，但都可以得到满意的效 果本文中，我们将从第一个基函数出发，得到相应的场分布函数，并由此生成重建曲线 2 2曲线重建算法 2 2 1 构造曲线运动方程式 方程( 2 2 ) 一般没有显式解，这里我们给出一种数值求解方法，考虑到1 ( s ) 为脊线 的投影曲线，为求得1 ( 8 ) ，选取一条适当的初始曲线r ( s 0 ) ，初始曲线上每一点沿场函 数，的梯度方向前进，在时刻t 得到曲线r ( s ，t ) ，表示成参数形式为 r ( s ，t ) = 【x ( s ，t ) ，耖( s ，) ) 其中8 为弧长参数，t 为时间参数，记场函数y ( z ，y ) 的梯度方向为 v f ( x ，y ) = ( ，z ( z ，可) ，厶( z ，可) ) 6 我们希望对于给定的初始曲线r o ) ，随着时间的推移，它沿场函数梯度方向运动 得到极限曲线r ( s ，+ o o ) 是场函数的某条脊线，并以此作为重建曲线我们知道，对于平 面上任意一点，场函数在该点的梯度方向是函数值增加最快的方向因此，为了使得极限 曲线r o ) 上各点场函数值，( “s ) ) 在曲线r ( s ) 的法线方向上取得极大值，我们以曲线 r ( s ，t ) 上各点处的梯度方向作为下一时刻的前进方向，从而得到曲线r ( s ，t ) 随着时间变 化所满足的方程为 掣= v f ( r 啪 ( 2 3 ) 令曲线r ( s ，t ) 沿着该方程定义的方向运动，当运动曲线落在点集s 的p 一邻域内且近似 是场函数的脊线时，则以此作为重建曲线 2 2 2 方程的离散迭代及收敛准则 设r o 为初始曲线，对于初始曲线的选取方法我们将在下面两节中详细讨论假设p 为方程经过k 次迭代后得到的曲线，将其离散表示为r 。： 璐，砰，f 敬 根据方程 ( 2 3 ) ，由点磷可得 亩；= 辟+ 矗i 罟乡蹁 ；= 。，t ， 其中v f ( 只) 是场函数在只点的梯度方向，h 为固定迭代步长由于曲线沿场函数的梯 度方向运动，所以曲线r 上的场函数值应越来越大如果存在i 使得f ( o 。) ，( 礞) ，说 明对于点只而言，步长选择过大，q 位于曲线的另一侧，此时应缩短步长，重新迭代 若对于足够小的步长，仍有f ( q t ) 1 ，且对于某足够小的给定误差 e ，有v f ( 辟“) 2 ( 礤+ 1 ) e ，其中2 ( 礞+ 1 ) 表示点砖+ 1 处的二阶差分，这说明曲 7 线r + 1 落在点集s 的p 一邻域内且近似是场函数，的一条脊线在平面上的投影，此时迭 代过程结束，r o + 1 就是最终的重建曲线 2 2 3 算法步骤 由前面的分析和讨论，我们给出曲线重建的算法步骤： ( 1 ) 对于给定的数据点集s ，构造场分布函数，( z ，y ) ； ( 2 ) 根据场分布函数，( z ，y ) 建立曲线运动方程( 2 3 ) ； ( 3 ) 对于给定的点集s ，选取适当的初始曲线r ( 8 ，0 ) ； ( 4 ) 让曲线f ( s ，0 ) 沿着( 2 3 ) 定义的方向运动，最终得到的收敛曲线即为重建曲线 8 第三节人工选择初始曲线及重建效果 3 1初始曲线的选取准则 当点集s 的拓扑结构比较复杂时，初始曲线选择的好坏将会对重建曲线的准确性产 生影响，人工选取初始曲线时，应选取尽量接近原始数据点集的曲线作为初始曲线 下面是几种不合理的选取方法，我们选取初始曲线时，应尽量避免这样的情况。 ( 1 ) 用曲线的中轴【1 5 】或中轴的一部分作为初始曲线，如图： 、 7 ，i ； ； 、一 “。、一一p + | 。；、。? ， 。、，； ，二：；二：一 。“、 ， j ? 。 图( 3 1 ) 中轴作为初始曲线 此时，可能出现v f ( r ( 8 ，o ) ) = 0 ，即r ( 8 ，o ) 上的点为，的局部极小值点，r ( s ，0 ) 的 运动方向不确定，从而无法准确地得到重建曲线 9 ( 2 ) 对于开曲线或自交曲线用包围盒作为初始曲线，如图： 图( 3 2 ) 包围盒作为初始曲线 若用这样的初始曲线沿场函数的梯度方向运动，得到的重建曲线可能为双边曲线，或 者在自交点处误差较大，使得重建的曲线不能反映出点集自交的性质 1 0 ( 3 ) 不连通曲线仅用一条简单的连通益线作为初始曲线，如图： 图( 3 3 ) 用一条简单曲线作为多连通曲线的初始曲线 此时可能有一部分曲线不能重建，并且重建的曲线上会出现多余的曲线段，重建曲线 不能准确的反映原始点集拓扑结构 总之，人工选择初始曲线时，应尽量选择接近原始数据点集的曲线作为初始曲线， 这样重建的曲线就能真实的反映原始点集的形状和走向 3 2实例与比较 应用场函数表示的曲线重建算法，我们人土选择初始曲线， 线，星形线以及多连通曲线进行了重建，都得到了满意的效果 下面我们对这几种类型的云点人工选择初始曲线进行重建， 建进行比较，看一下它们的重建效果 例1 简单云点的曲线重建 对于简单曲线，自交曲 与文献【1 6 】中的曲线重 下图分别是本文人工选择初始曲线和用最小包围盒作为初始曲线以及它们的重建效 果从图中可以看出，对于筒单的云点，人工选择的接近于原始数据点集的初始曲线，和 用最小包围盒作为初始曲线的重建曲线没有太大的区别 图( 3 4 ) 平面点云及它们的初始曲线 图( 3 5 ) 二者的重建曲线 例2 闭自交点云的曲线重建 对于闭自交点云，文献f 1 6 】用点云的最小包围盒作为初始曲线，得到的重建曲线在 自交点处误差较大，不能很好的反映点云自交的性质，下图为从双纽线上经过带噪音的抽 样后得到的无序离散点集前面的左图是人工选择的初始曲线，右图是用最小包围盒作为 初始曲线后面两图是它们的重建曲线，从图中可以看出，用最小包围盒作为初始曲线得 到的重建曲线自交性不明显 1 2 一一 图( 3 6 ) 双纽线点云的初始曲线 一一 图( 3 7 ) 二者的重建曲线 例3 星形点集和多连通点集的曲线重建 对于星形点集和多连通点集，我们分别选择接近原始数据点集的初始曲线，和用包 围盒作为初始曲线，但端点作为插值节点，使要重建的曲线通过指定的插值点，得出重建 曲线下面左图是人工选择的初始曲线以及它的重建曲线，右图是包围盒作为初始曲线， 但端点作为插值节点得出的重建曲线从图中可以看出，右图出现了明显的双边曲线，左 图的重建效果好于右图 1 3 图( 3 8 ) 两种方法构造的星形点集的初始蛆线 图( 3 9 ) 二者的重建效果 图( 3 1 0 ) 两种方法构造的多连通点集的初始曲线 1 4 图( 3 1 1 ) 二者的重建效果 例4 不连通点云的曲线重建 对于不连通平面云点的曲线重建，我们不需要根据点集的连通性将它分成若干个连 通子集，而是直接对整个点云选择初始曲线进行重建，这时由于点集的不连通性，初始曲 线需要由几段组成，下图为不连通点云的初始曲线以及它的重建效果，这里初始曲线由两 条折线段组成 图( 3 1 2 ) 初始曲线由两段组成 1 5 图( 3 1 3 ) 重建曲线 通过上面的实验我们看到，人工选择初始曲线时，只要选择的初始曲线接近原始数据 点集，最终得到的重建曲线都能真实的反映数据点集的拓扑结构和形状 1 6 第四节自适应选择初始曲线及重建效果 上一节我们讨论了人工选择初始曲线所得的重建曲线我们看出，只要选取的初始曲 线接近于原始数据点集，都可以得到满意的效果但还是加入了人工交互的因素，这一节我 们讨论如何根据点集自身的性质自适应地选择适当的初始曲线，并由它进行曲线的重建 4 1初始曲线的构造方法 对于平面上的一组数据点集，首先对平面进行网格化，设网格的长度和宽度均为h 若数据点所含的嗓音为均匀噪音，通过大量的实验可知，h 通常的取值范围为8 1 2 个像 素得到的初始曲线比较好计算每个网格所含数据点的个数，对于给定的阈值。若网格 中所含数据点的个数小于f ，则认为该网格中不含数据点反之，则认为网格中含有数据 点如图( 4 1 ) ： 图( 4 1 ) 网格图 阴影网格为含有数据点的网格，记录所有含数据点网格的位置，计算每个含数据点的网格 中，所有数据点位置的平均值，作为我们细化后的点p ，细化后的点我们称为网格点， 这里，首先给出网格点的度的概念 定义：对于平面上任意两个网格点。( z t ，z z ) ，y ( y l ，y 2 ) ，定义z ，鲈闻的距离为d ( 盘，y ) = m 口z ( i z 一y ，i ，i x 2 一，2 i ) ，对于平面上的网格点p ，p 的m 一邻域为q ： qd ( 只q ) 1 7 m h ，q r 2 ，则p 的1 一邻域内所含网格点的个数称为点p 的度。 即点p 的度是p 所在网格的周围八个相邻的网格中，所含数据点网格的个数由度 的定义可知，p 的度8 对于细化后的点集p ，我们采用跟踪算法，得出相应的初始曲线，并由此重建曲线， 下面给出构造初始曲线的具体算法： 4 1 1 选取初始点q o 在细化后的网格点中，计算各个点p 的度数从其中的一点出发，如果能找到一个 1 一度点，则把此点作为初始点q o 否则，重新循环，寻找度数为2 的点，以第一次找到 的2 一度点作为初始点q o 如果所有网格点的度都超过了2 ，则说明细化的效果不好， 应调整h 的大小，重新细化 4 1 2 由已知点列 q o ，q 1 ，q k 寻找第后+ 1 个点q + 1 ，并由此构造初始曲线 由于q o 的度大于0 ，说明q o 的1 一邻域内一定存在网格点，选取其中的一个作为 q l ，把骗，q 1 的度都降1 假设我们已经得到点列 q 0 ，q 1 ，q k ，下面选取q k + l ， 对于当前点仉，取向量u = q 一饥一l ，v 为矿沿逆时针方向旋转9 0 0 的向量以q 为坐标原点，以y 为坐标轴建立局部坐标系，如图： l i 。 8 f 若仉的l 一邻域内存在网格点p k ，且磊磊与u 的夹角小于9 0 。，则取r 作为 q 。+ 。否则，扩大搜索范围，在q t 的2 一邻域内寻找一个网格点r ，使得弓蕊与u 的 夹角小于9 0 。如果仉的2 一邻域内还不存在满足条件的点r ，那么我们再扩大一次 搜索范围，在q 的3 一邻域内寻找r ，此时丽五与u 的夹角可以大于9 0 。，这说明 曲线可能在鼠附近的曲率较大，或者在q 附近存在尖点，取r 作为饥+ 1 注意，上 1 8 面所取的p k 不能与仉一1 重合，即我们不能走回头路找到q k + 1 后，把仇，q k + l 的度 都降1 若我们搜索到一个网格点q 。，把q 。的度降1 后变为了0 ，则说明此段曲线已 经搜索完毕，或者搜索到的网格点又回到了q o ，即q 。= q o ，则说明这段要重建的曲线 为闭曲线如果搜索得到某个网格点q 。后，有d ( q o ，q 。) 2 ，则有可能曲线在采样时 出现了缺损部分，出现了数据点丢失的情况此时，直接取q 。= q o ，使曲线闭合顺次 连接q 0 ，q 1 ，q 。作为一段初始曲线2 1 接下来判断所有的个网格点中，是否还存 在度大于0 的点，如果存在的话，在所有度大于0 的点中，再寻找度最小的点作为初始点 q o ，用同样的方法得到一段初始曲线f 2 这样的过程一直重复下去，直到所有的网格点 的度都降为0 将所有的曲线z l ，f 2 ，l m 作为整个平面云点的初始曲线如果我们得到 的初始曲线中，有一段曲线如所含的网格点少于3 ，则说明这部分噪音干扰比较大，为 了不对重建的效果产生影响，应将这段曲线直接去掉，令l i = 0 4 1 3 初始曲线与重建曲线 前面我们给出了初始曲线的构造方法，我们看到由此构造的初始曲线也反映了该点 集的大致拓扑结构，但不能用它直接来代替重建曲线因为重建曲线是场强最大的点形成 的曲线，而我们构造的初始曲线只是由点集的中轴点列跟踪得到的曲线，与要重建的曲线 之间还存在很大的误差，因此需要用此曲线沿着场函数梯度的方向运动，得到最终的收敛 曲线为重建曲线 4 2实例与比较 前面我们给出了平面云点初始曲线的构造方法，下面对于复杂拓扑结构的平面云点， 我们用上述方法构造它们的初始曲线，由此进行曲线的重建并与上节人工选择初始曲线 的重建效果进行对比，我们可以看到，用这种方法重建的曲线，能够得到与上节一样的重 建效果但这里减少了交互的因素 例1 双纽线的重建 在上一节中，我们用人工选择初始曲线的方法对双纽线进行了重建这里我们用自 适应选择初始曲线的方法再对双纽线进行重建下面左图为用上述方法取h = 9 构造的 初始曲线，右图为重建的曲线。从下图可以看出，这种方法能够得到几乎与人工选择初始 1 9 一c ) p = 1 ，g = 3 图( 4 2 ) 双纽线的初始曲线及它的重建曲线 曲线同样的重建效果 例2 不连通曲线的重建 不连通平面云点的曲线重建，上节的例4 我们用人工选择初始曲线的方法得到了它 的重建曲线，这里我们用自适应选择初始曲线的方法再对它进行重建下面左图为用上述 方法取h = 1 2 构造的初始曲线，右图是取h = 1 0 构造的初始曲线，后面两个为重建曲 线 二，c r ，- 一 图( 4 3 ) 用自适应方法选择的初始曲线 p = 3 g = 1 ，_ _ h 日，_ - _ a _ ，一 图( 4 4 ) 它们的重建曲线 p = 2 ，e = 1 例3 更复杂结构的曲线重建 对于更复杂拓扑结构的平面点云，我们同样可以甩上述算法得到它们的初始曲线， 下面两图是取h = 8 得到的初始曲线，后面两图是它们的重建曲线 图( 4 5 ) 更复杂平面点云的初始曲线 2 1 叠由 o l p = 5 = 1 图( 4 6 ) 重建曲线 p = 3 e = 1 后记；本文主要讨论了场函数表示的曲线重建算法步骤，以及人工选择初始曲线的方 法和i 刍适应选择初始曲线的算法并用大量的实验表明，对于具有任何复杂拓扑结构的平 面云点，用这两种方法得到的初始曲线，经过迭代，都能得到高质量的重建曲线在自适 应构造初始曲线的过程中，h 的大小是由实验得出的能否根据点集自身的性质自动确定 h 的大小，以及这种方法能否推广到三维空间曲线的重建将是我们下一步考虑的问题 参考文献 【l 】1 n s s a p i d i s ，p j b e s l d i r e c tc o n s t r u c t i o no fp o l y n o m i a ls u r f a c e sf r o md e n s er a n gi m a g e s t h r o u g e sr e g i o ng r o w i n g a c mt r a n s a c t i o no ng r a p h i c s ，1 9 9 5 ，1 4 ( 2 ) ：1 7 1 2 0 0 【2 】v d r a d yt ，m a r t i nrr ，c o xj r e v e r s ee n g i n e e r i n go fg e o m e t r i cm o d e l s - a ni n t r o d u c t i o n c o m p u t e r a i d e dd e s i g n ，1 9 9 7 ，2 9 ( 4 ) ：2 5 5 - 2 6 8 【3 | d f m c a l l i s t e r ，j a r o u l i e r a n a l g o r i t h m f o r c o m p u t i n g a s h a p e p r e s e r v i g s c i l l a t o r y q u a d r a t i c s p l i n e a c mt r a n s a c t i o n so nm a t h e m a t i c a ls o f t w a r e ，1 9 9 1 ，7 ：3 3 1 3 4 7 1 4 f n f r i t s c h ，r e c a r l s o n m o n o y o n ep i e c e w i s ec u b i ci n t e r p o l a i o n s i a mj o u r n a l o fn u m e r i a l a n a l y s m ，1 9 8 0 ，1 7 ，2 3 8 - 2 4 6 【5 】f n f r i t s c h ，j b u t a n d am e t h o df o rc o n s t r u c t i n gl o c a lm o n o t o n ep i e c e w i s ec u b i ci n t e r p o - l a t e s s i a mj o u r n a lo fs c i e n t i f i ca n ds t a t i s t i c a lc o m p u t i n g ，1 9 8 4 ，5 ，3 0 3 - 3 0 4 1 6 】j e l a v e r y s h a p e - p r e s e r v i n g ，m u l t i s c a l ef i t t i n go fu n i v a r i a t ed a t ab yc u b i cl 1s m o o t h i n g s p l i n e s c o m p u t e ra i d e dg e o m e t r i cd e s i g n 2 0 0 0 1 7 ：7 1 5 - 7 2 7 【7 】b e d m o n d ，p s y l v a i n c u r v ea n ds u r f a c er e c o n s t r u c t i o nf r o mr e g u l a ra n dn o n - r e g u l a rp o i n t s e t s 2 0 0 0i e e e 8 】d l e v i n t h ea p p r o x i m a t i o np o w e ro fm o v i n gl e a s t s q u a r e s m a t h m a t h i c so fc o m p u t a t i o n ， 1 9 9 8 ，6 7 ( 2 2 4 ) ：1 5 1 7 - 1 5 3 1 ( 9 】i l e e c u r v er e c o n s t r u c t i o nf r o mu n r e g n l a rp o i n t s c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，2 0 0 0 ， 1 7 ( 2 ) ：1 6 1 1 7 7 【1 0 l f a n g ，d c g o s s a r d m u l t i d i m e n s i o n a lc u r v ef i t t i n g t ou n o r g a n i z e dd a t dp o i n t sb yn o n l i n e a r m i n i m i z a t i o n c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，1 9 9 5 ，2 7 ( 1 ) ：4 8 - 5 8 【1 1 jg t a u b i n ，r r o n f a r d i m p l i c i a lm o d e l sf o ra d a p t i v ec l n t er e c o n s t r u c t i o n ：i e e et r a n s a c t i o n s o np a t t e r n