（计算数学专业论文）基于最优化方法的图形图像若干问题的研究.pdf

基于最优化方法的 图形图像若干问题的研究 专业 学位申请人 指导教师 摘要 计算数学 覃廉 关履泰教授 本文主要研究图形图像处理中的几个问题 包括大规模散乱数据曲面造型 曲线曲面的降阶逼近 极小曲面造型 带约束条件的插值和光顺问题以及图像去 噪 总体思路是将图形图像处理中的几个问题转化为最优化问题 然后求解该问 题的最优解 主要工作包括 利用矩形域参数自然样条最优插值 挖补技术与带连续样条边界条件的散乱 数据参数最优插值 提出一种用参数样条挖补的方法进行大规模散乱数据曲 面造型的方法 它具有某种能量极小性质 参数曲面内部 4 连续 挖补矩 形边界分别为c 州 和p 连续 晟后就常见的m n 2 时的双三次样条 给 出一些数值算例 说明该算法简单易行 效果良好 提出一种b 样条曲线曲面降阶的快速算法 可以实现b 样条曲线曲面一次降 多阶 降阶后的b 样条曲线曲面具有全局最优性质 算法将问题转化为二次 规划问题求解 只需要求解一个稀疏线性方程组 然后进行解的存在性分析 和误差分析 提出一种有理曲线曲面降阶的快速算法 将n u r b s 曲线曲面和有理b e z i e r 曲线曲面放到齐次坐标空间中处理 在齐次坐标空间中求它们的最佳降阶逼 近 然后再转化到仿射坐标空间 将n u r b s 曲线曲面和有理b e z i e r 曲线曲 面降阶问题转化为二次规划问题 并进行误差分析 讨论任意区域上的参数极小曲面的近似求解问题 首先构造出以给定的 n u r b s 曲线为边界的n u r b s 曲面族 然后在该曲面族中寻找极小曲面的 最佳逼近 算法基于信赖域方法求解 迭代速度快 具有全局收敛性 针对凸插值 凸光顺和保形插值等带约束条件的插值和光顺问题 提出一种 i h 改进的信赖域方法 约束插值和光顺问题可归结为求解半光滑非线性方程 组 利用半光滑方程组的广义雅可比矩阵 并采用半光滑方程组的平方自然 残余量作为价值函数 此外 利用关履泰 1 9 8 3 关于凸集上样条函数的性质 改进信赖域方法 以加速信赖域方法的迭代 证明了约束插值和光顺问题的 信赖域方法的局部收敛性和全局收敛性 提出一种基于数字全变差图像分割的图像去噪方法 首先根据图像的局部数 字全变差将图像分割成边缘区域和平坦区域 然后对应不同的区域应用不同 的滤波器 在尽可能过滤掉图像噪声的同时保留大多数的边缘特征 关键词 大规模散乱数据插值 曲线曲面降阶 极小曲面 约束插值逼近 图像 去噪 i v s t u d i e so ns e v e r a lg r a p h i c sa n di m a g ep r o c e s s i n g t o p i c sb a s e d o i lo p t i m i z a t i o nm e t h o d m a j o r c o m p u t a t i o n a lm a t h e m a t i c s n a m e q i n l i a n s u p e r v i s o r p r o f e s s o rg u a nl u t a i a b s t r a c t i nt h i sd i s s e r t a t i o n s e v e r a lg r a p h i c sa n di m a g ep r o c e s s i n gt o p i c sa r es t u d i e d i n c l u d i n gl a r g es c a l es c a t t e r e dd a t as u r f a c ed e s i g n a p p r o x i m a t ed e g r e er e d u c t i o n o fc u r v e sa n ds u r f a c e s m i n i m a ls u r f a c e sd e s i g n c o n s t r a i n e di n t e r p o l a t i o na n d s m o o t h i n gp r o b l e m s i m a g ed e n o i s i n g t h em a i ni d e ai st h a ta l lt h e s ep r o b l e m sa r e t r a n s f e r r e dt o o p t i m i z a t i o np r o b l e m s a n ds o l v e db ym e t h o do fo p t i m i z a t i o n c o m p u t i n g o u rr e s e a r c h e sa r ea sf o l l o w u s i n gm u l t i v a r i a t eo p t i m a li n t e r p o l a t i o nt os c a t t e r e dd a t at h r o u g h o u tar e c t a n g l e w i t hc o n t i n u o u sb o u n d a r yc o n d i t i o n s c o n n e c t e dw i t ht e n s o rp r o d u c tp a r a m e t r i c s p l i n ei n t e r p o l a t i o n b y f i l l i n gh o l e t h o u g h t af i l l i n gh o l e si n t e r p o l a t i o nm e t h o d f o rl a r g es c a t t e r e dd a t as u r f a c ed e s i g ni sp r o p o s e d t h ec o r r e s p o n d i n gs u r f a c eo f t 1 1 i sm e t h o db e l o n g st oc m 4i nt h ei n t e r i o r a n d f i l l e dh o l e s b o u n d a r yi nt h e r e c t a n g l eb e l o n g st o a n de r e s p e c t i v e l y f i n a l l ys o m en u m e r i c a le x a m p l e s f o rm n 2b i c u b i cs p l i n e sa r eg i v e nt os h o wt h a tt h em e t h o di se a s ya n d a p p l i c a b l e b a s e do no p t i m i z a t i o nt e c h n i q u e ac o n v e n i e n ta l g o r i t h mf o rd e g r e er e d u c t i o no f b s p l i n ec h i v e sa n ds i l l f a c e si sp r e s e n t e d m u l t i d e g r e er e d u c t i o no fb s p l i n e c u l v ea n ds u r f a c ei sa c h i e v e db ys o l v i n gs y s t e m so f1 i n e a re q u a t i o n s t h e a l g o r i t h mc o m p l e x i t ya n dt h ea p p r o x i m a t i o nr e s u l to ft h ea l g o r i t h ma r eb e t t e r t h a nc o n v e n t i o n a la l g o r i t h m i nt h ee n dt h ee x i s t e n c eo fs o l u t i o na n dt h ee r r o ra r e a n a l y z e d b a s e do nh o m o g e n e o u sc o o r d i n a t e s ac o n v e n i e n ta l g o r i t h mf o ra p p r o x i m a t e d e g r e er e d u c t i o no f n u r b sa n dr a t i o n a lb e z i e rc u r v e sa n ds u r f a c e si sp r e s e n t e d i nh o m o g e n e o u sc o o r d i n a t e s t h ed i f f e r e n c eo f 廿1 e1 0 wd e g r e ec u r v e s u r f a c ea n d h i 曲d e g r e e c u r v e s u r f a c ei sm i n i m i z e d t h e p r o b l e m o fa p p r o x i m a t e m u l t i d e g r e er e d u c t i o no fr a t i o n a l c u r v e sa n ds u r f a c e si st r a n s f o r m e di n t o q u a d r a t i cp r o g r a m m i n g e r r o re s t i m a t ei sp r e s e n t e d e x p e r i m e n t a lr e s u l t ss h o w t h ee f f i c i e n c eo f t h i sa l g o r i t h m t h ep r o b l e mo fa p p r o x i m a t i o nt ot h ep a r a m e t e r i z e dm i n i m a ls u r f a c eb o u n d e db y n u r b sc u r v e si si n v e s t i g a t e d a tf i r s t t h es u r f a c e sb o u n d e db yag i v e n 瓜b s c u r v ea r ed e s i g n e d n l e nf m do u tt h eb e s ta p p r o x i m a t i o no ft h em i n i m a ls u r f a c e a m o n gt h o s es u r f a c e s n i ea l g o r i t h mp r e s e n t e di sb a s e do nt r u s t r e g i o na l g o r i t h m w i t hg l o b a lc o n v e r g e n e e n u m e r i c a le x a m p l e si l l u s t r a t et h eg o o dr e s u l t s at r u s tr e g i o na l g o r i t h mi sp r e s e n t e dt os o l v et h ec o n s t r a i n e di n t e r p o l a t i o na n d v s m o o t h i n gp r o b l e m ss u c h a sc o n v e xi n t e r p o l a t i o n c o n v e xs m o o t h i n ga n d s h a p e p r e s e r v i n gi n t e r p o l a t i o n a nt h e s ep r o b l e m sc a l lb er e d u c e d t os e m i s m o o t h n o n l i n e a rs y s t e m s w ju s eag e n e r a l i z e dj a c o b i a no ft h ef u n c t i o ni n v o l v e di n s e m i s m o o t he q u a t i o na n da d o p tt h es q u a r e dn a t u r a lr e s i d u a lo ft h es e m i s m o o t h e q u a t i o na sam e r i tf l m c t i o n f u r t h e r m o r e w ei m p r o v et h et r u s ti e g i o nm e t h o db y u t i l i z i n gt h ep r o p e r t i e so f t h es p l i n eo nac o n v e xs e t g u a nl u t a i 1 9 8 3 t os p e e d u pt h ei t e r a t i o no ft h et r u s tr e g i o nm e t h o d t h el o c a la n dg l o b a lc o n v e r g e n c eo f t h et r u s tr e g i o nm e t h o di nc o n s t r a i n e di n t e r p o l a t i o na n ds m o o t h i n gp r o b l e m si s p r o v e d a tt h ee n d s o m en u m e r i c a le x a m p l e sa r ep r e s e n t e d t op r o p o s a la ni m a g ed e n o i s i n gm e t h o db a s e do ni m a g es e g m e n t a t i o nb yd i g i t a l t o t a lv a r i a t i o n s e g m e n ta ni m a g ei n t os e v e r a la r e a sb yt o t a lv a r i a t i o n t h e n d e n o i s et h ed i f i e t e n ta r e a su s i n gd i f i e r e n ts t r a t e g i e s c o m p a r e d w i t ht 1 1 e c o n v e n t i o n a ld e n o i s i n gm e t h o du s i n gs i n g l es t r a t e g y t h em e t h o dg i v e ss u p e r i o r p e r f o r m a n c e k e yw o r d s l a r g es c a l es c a t t e r e dd a t ai n t e r p o l a t i o n d e g r e er e d u c t i o no fc u r v e sa n d s u r f a c e s m i n i m a ls u r f a c e c o n s t r a i n e di n t e r p o l a t i o n a p p r o x i m a t i o n i m a g e d e n o i s i n g v i 中山大学博士学位论文 第一章绪论 曲线曲面造型是计算机辅助几何设计 c o m p m e ra i d e dg e o m e t r i cd e s i g n 简 称c a g d 的一项重要和基本的内容 c a g d 源于飞机 船舶 汽车的外形放样 工艺 2 0 世纪6 0 年代 法国雷诺 r e n a u l t 汽车公司工程师eb e z i e r 以及美国波 音公司的s c o o n s 建立了几何外形表示的基本理论 即b e z i e r 曲面以及c o o n s 曲面 自7 0 年代以来 计算机辅助几何设计技术得到了迅猛的发展 出现了有 理b e z i e r 曲线 曲面 b 样条曲面 非均匀有理b 样条 代数曲面 隐式曲面 细分曲面等一系列曲面表示形式 人们还提出了插值 拼接 拟台 求交 过渡 编辑修改等各种各样的几何操作与运算 所有这些构成了c a g d 这门学科的核 心内容 同时 c a g d 的应用也不断扩大到机械 建筑 电子线路 服装 动画 等 并向其他领域深入发展 近年来 最优化理论方面的研究快速发展 各种解决最优化问题的数值计算 方法日渐成熟 这给其他领域的研究工作提供了强有力的工具 大量原先无法解 决或结果不理想的问题 可以借助最优化方法这个工具来解决 本文研究了图形图像处理中的几个问题 都是c a g d 领域中的热点问题 具 有很强的应用背景 总体思路是将这些问题转化为最优化问题 然后求解该问题 的最优解 借助最优化计算方法 获得了比较好的结果 下面先对本文涉及的最 优化方法和几个c a g d 方面的问题的研究背景 现状进行综述 1 1 最优化方法综述 最优化理论与方法是一门应用性很强的学科 它研究某些数学问题的最优 解 随着计算机的高速发展和优化计算方法的进步 规模越来越大的优化问题也 可以进行求解 最优化在航空航天 生命科学 水利科学 地球科学 工程技术 等自然科学领域和经济金融等社会科学领域也发挥着越来越重要的作用 它的研 究和发展一直得到广泛的关注 最优化问题的一般形式为 1 r a i n 厂 膏 s 1 x x 中山大学博士学位论文 其中x e r 为决策变量 f x 为目标函数 x r 为约束集或可行域 如果 约束集x r 则上述问题称为无约束优化问题 否则 称为约束优化问题 通常记为 m i n z s j q x 0 i e 仁 x 0 i 1 这里e 和 分别是等式约束和不等式约束的指标集 c 0 是约束函数 刺于 无约束最优化问题 已经提出了很多成熟的数值计算方法 如最速下降法 牛顿 法 共扼梯度法 拟牛顿法等 对于约束优化问题 也有不少计算方法 如二次 规划法 罚函数法 序列二次规划法 可行方向法 信赖域法等 信赖域方法是近二十多年来发展起来的一类重要的数值计算方法 受到了非 线性优化界非常的重视 特别是近几年 一直是非线性优化研究的热点 目前 信赖域方法已经和传统的线搜索方法并列为非线性规划的两类主要的数值方法 信赖域方法的研究起始于p o w e l l 的研究工作 后来人们发现信赖域方法的基 本技巧在一定意义下等价于求解非线性最小二乘的l e v e n b e r g m a r q u a d t 方法 信 赖域方法的构造和逼近是密切相关的 给出一个当前迭代点靴 构造一个近似于 原问题的逼近模型 由于该模型主要是基于原问题在 的信息 故有理由认为 此模型仅在x k 附近可以很好地描述原问题 所以 人们仅在x 附近的某一邻域 内求解逼近模型的最优点 该邻域被称为信赖域 它常是以x 为中心的广义球 信赖域的大小通过迭代逐步调节 一般说来 如果当前迭代模型较好的逼近原问 题 则信赖域可扩大 否则信赖域应缩小 信赖域方法的关键组成部分是如何求得信赖域试探步以及怎样决定试探步 是否可被接受 试探步一般足一子问题的解 所以如何求得信赖域试探步实质上 归结于予问题的构造 决定试探步是否可被接受通常是利用某一价值函数 看试 探步能否使价值函数下降 对于无约束优化问题 价值函数显然就是目标函数 对于约束优化问题 价值函数常常是一罚函数 信赖域方法有两个很好的性质 一是它有很好的可靠性和强适性 另一个是 它有很好的收敛性 这也正是它备受关注的主要原因 中山大学博士学位论文 1 2 大规模散乱数据曲面造型 在许多科学和工程应用领域中 经常会遇到问题 怎样根据一些已知的比较 稀疏的不规则位置上的测量结果设计 个曲面拟合他们 这就是散乱数据的曲 面造型问题 散乱数据有3 个主要来源 1 物理量的测量数据 2 科学实验所 得数据 3 科学计算或工程计算结果 在气候测量 地震检测 石油勘探 海 底地形图绘制 物理或化学实验 有限元方法求解偏微分方程时的输出数据等均 经常出现 2 3 4 随着科技的飞速发展 各种仪器与方法均有很大改进 由此得到的数据越来 越多 达到数万 数十万甚至数百万 出现大规模散乱数据的插值问题 一般认为较早用于大规模散乱数据曲面造型的方法是s h e p a r d 方法 它是一 个与距离成反比的加权方法 它有在插值点附近会出现平台 精度较差 函数重 建质量较差和计算量大等缺点 但由于算法简单而且能解决大规模的问题 仍在 发挥作用 而且不少改进方法的研究仍在进行中 4 5 6 7 各种各样的对多元散乱数据的插值方法先后提出 都有一定的效果 例如 光滑余因子方法 3 b o x 样条 b 网 顶点样条 多项式自然样条 三角网最优 插值 甚至早一点的薄板样条 1 3 4 8 9 a 样条函数是分段 片 多项式函数 它是一类 半解析 逼近工具 它既保持 了多项式的某些优点 如计算简单 又具有局部支撑的性质 具有相当的灵活 性 至今 样条函数仍然是曲面拟合最为常用的工具 c k c h u i 与关履泰针对 格子点情形进行比较 结果表明样条函数方法比径向函数方法逼近的效果要好得 多 多元样条函数的研究自上世纪六十年代d e b o o r 等引入张量积样条而使之可 以应用于实际以来 进展较快 j d u c h o n 提出的薄板样条是一元样条到多元样 条真正的非张量积形式的推广 它是基于构造再生核的方法 但对于一般的泛函 要构造再生核是比较困难的 1 9 8 5 年 李岳生利用带广义约束条件的变分方法 解决了任意散乱布点的多元插值问题 建立了散乱数据样条拟合的理论框架 l o 之后 李岳生 关履泰 胡日章 黎罗罗等又在矩形域 圆域 三角形域 l 型域以及更为广泛的情形采用不同的方法对散乱数据插值和光顺进行了深入 系统的研究 1 1 1 2 1 3 1 4 1 9 8 9 年 关履泰 李岳生 1 5 1 6 研究了广义混合样条函数空间矩形域带连 中山大学博士学位论文 续边界条件和离散边界条件的多元散乱数据最优插值问题 可以用闭形式解决 并且提出二元希尔伯特空间多项式插值自然样条的概念 1 9 8 8 年 胡日章给出 了矩形域上散乱数据的连续边界条件光顺逼近解的特征性质 证明了解的存在唯 一性和最优逼近性质 1 9 8 6 年 关履泰在李岳生1 9 8 5 年工作基础上 基于希尔 伯特空间样条函数理沦 考虑了矩形域内不精确散乱数据的多元最优拟合 带连 续边界条件 1 7 给出了解的存在唯一性 特征及构造方法 后来 关履泰 1 8 在1 9 9 3 年基于希尔伯特空问样条插值理论 给出了矩形域上散乱数据的二元多 项式自然样条插值 光顺或广义插值方法 样条函数的基底由单边基给出 这对 理论分析是很有用的 c k c h u i 和关履泰在 1 8 中 把二元的结果全面推向一 般多元情形 得出较为一般区域的多元多项式插值自然样条的显函数表示格式 1 9 9 4 年关履泰 1 9 研究散i l w 元多项式自然样条的极小性质与定义区域 把自然 样条推广到半任意区域与无穷区域 1 9 9 3 年 韩国强 2 0 研究了这类型的低次样 条误差估计及其收敛性 1 9 9 4 年 胡日章 毛明志 2 1 对l 型域上散乱数据逼近 问题作了深入的研究 从变分出发将插值与光顺作为某泛函极小问题来研究 从 而导出解的结构和求解格式 1 9 9 7 年 关履泰 2 2 研究了类似b 样条的局部支撑 函数 给出二元多项式自然样条的新基底 它可r h 元多项式白然样条空间的单 边基线性表出 并且具有最小局部支撑性 这对实际计算是很有意义的 2 0 0 3 年 有关这种局部支撑基的性质及插值自然样条的算法在 2 3 中发表 而对平面 线上分布的大规模散乱数据也提出适用的局部基自然样条插值 2 4 这些方法中许多具有能量极小的性质 避免插值点附近出现平台现象 重建 质量较好 但是如果数据规模超过2 0 0 实现起来就出现困难 更不要说解决数 据规模超过一万的大规模散乱数据曲面造型了 近年对大规模的f 6 题出现了较多的工作 细分算法 2 8 成为一个热点 还有 层次b 样条方法 2 6 2 7 径向基函数方法 5 2 8 有限元方法 2 9 一迭代方 法 3 0 1 等 但是他们都没有能量极小的性质 曲面的各种连续连接条件的研究足曲面造型的一个重要课题 文献 3 1 给出 4 十 挖补 插补的曲面连续连接方法 类似的研究近期在国内得到重视 3 2 3 3 1 杜佶等 3 2 1 提出一种对三角网格曲面中孑l 洞的修补算法 在对孔洞多边形进行填 补后 使用径向基函数建立孔洞曲面的隐式方程 然后把新增加的三角片顶点映 4 中山大学博士学位论文 射到曲面上 陈志杨等 3 3 提出 种具有自适应特性的数据补测算法 通过引入 平均误差及平均曲率影响因子 自动计算出补测空洞的影响区域 进而利用影响 区域内的数据构造连续曲面并计算出空洞内的数据点 1 3 曲线曲面降阶方法 在当前的计算机辅助设计 制造 c a d c a m 系统中 非均匀有理b 样条 n u r b s 表示已成为当今自由曲线曲面表示的工业标准 然而不同的c a d 设计 系统中所具体采用的多项式基的类型是多样的 如b e m s t e i n b e z i e r s c h o e n b e r g b 样条 h e r m i t e c o o n s 等单调基函数 因此 不同的公司往往采用不同的设计系 统 以汽车工业为例 美国通用汽车公司使用g o r d o n 曲面 福特公司使用c o o n s 曲面 而m e r c e d e s 公司使用双三次样条曲面 随着大量造型系统的涌现 c a d c a m 系统之间曲线曲面几何描述信息的数据交换日益频繁 特别对于存在 有多个不同造型系统的大型工业组织 不同部门之间经常需要进行数据交换 人 们开始认识到需要为产品数据制定一些文件规范 近十多年来各国制定了许多 c a d 系统数据通讯标准 如美国国家标准局和一些工业部门开发的1 g e s 法国 航空航天业制定的s e t 德国汽车制造业制定的德国国家标准v d a v d m a f s 和美国空军组织制定的p d d i 等 1 9 8 8 年国际标准化组织i s o 建立了制定产品 模型数据交换标准s t e p s t a n d a r df o rt h ee x c h a n g eo fp r o d u c tm o d e ld a t a s t e p 制定过程需涉及大量的产品数据交换技术 而降阶处理是其中相当重要的研究课 题 曲线 曲面 的降阶处理是指对于一给定次数的曲线 曲面 找到另外一条片 或多条片更低次数的同类型曲线 曲面 来逼近它 并使误差保持在预先给定的范 围内 通常对于多个系统中不同类型的 但次数相同的基之间 可通过基转换矩 阵来实现数据交换 然而不同的c a d 系统中多项式最高次数的限制范围和要求 是不同的 可从3 次到2 0 次不等 则此时需要将高次表示逼近转化为低次表示 而且在实际中许多c a d c a m 系统考虑到有效性 往往只限于处理低次曲线 因而为了实现不同阶数的曲线曲面的数据转换 必须对高次曲线曲面进行降阶处 理 另一方面 工业产品f 如汽车车身 叶片等 的模型设计及仿制过程中对离散 数据进行拟合逼近时 往往产生高阶的曲线和曲面表示 这同时导致大量几何数 据信息的存储 在几何造型中 曲面片求交产生的交线及t r i m m e d 裁剪 边界曲 中i j 大学博士学位沦文 线也会产生高次的曲线表示 为尽量减少信息数据存储量 就需要对高次曲线进 行降阶处理 同时在曲线的光顺 3 4 处理过程中 也经常需要进行降阶处理 成敏 3 5 对2 0 0 4 年以前国内外曲线曲面的降阶逼近研究进行了综述 结合 3 5 的内容 下面分别对b e z i e r 曲线曲面降阶 b 样条曲线曲面降阶 有理曲线曲面 降阶的研究方法进行介绍 并分别对其优缺点进行分析比较 1 3 1b e z i e r 曲线降阶 在c a d c a m 系统的几何造型设计中 b e z i e r 曲线是其中最广为使用的曲线 类型 已有许多学者对b e z i e r 曲线的降阶进行了研究 b e z i e r 曲线的降阶方法主 要可分为两大类 一是基于几何信息的离散化方法 这类方法主要着眼于原曲线 的控制顶点和导矢等几何信息 利用插值 凸线性组合等技巧 通过b e z i e r 曲线 的升阶反过程 3 6 3 7 近似转化 38 3 9 约束优化 4 0 4 1 和控制顶点扰动 4 2 1 1 4 3 等方法来进行降阶 二是基于基转换的代数方法 这类方法主要着眼于 原曲线在不同的范数空间 三 4 4 1 1 4 5 4 6 1 l 2 4 7 4 8 下的函数逼近性质 对曲 线降阶的最佳一致逼近和最小二乘逼近进行讨论 并通过基之间的转换来进行降 阶 以上各种降阶方法每次均只能降一阶 若需降多阶 则须采用逐次降阶 b o g a c k i 等 4 9 使用矩阵形式来表示b e m s t e i n 基与c h e b y s h e v 基的转换 并一次 截断多项 来对b e z i e r 曲线进行降多阶逼近 陈国栋等 5 0 利用广义逆矩阵王坐论 提出了一种降阶算法 可一次降多阶 为保持原曲线端点的几何信息 陈国栋 5 1 给出了一满足端点插值条件的b e z i e r 曲线最佳最d 乘逼近降多阶逼近算法 结 合升阶反过程和j o c o b i 多项式逼近来进行降阶 所得降阶曲线首末端点可分别达 到任意阶插值 并且可一次降多阶 梁秀霞 5 2 提出了 种端点插值的b e z i e r 曲 线降阶的方法 利用b e z i e r 曲线升阶公式产生端点插值降阶的约束条件 新的 b e z i e r 曲线通过极小化降阶前和降阶后两曲线的一阶导矢之差的平方的积分产 生 从而把新旧控制点之m 应满足的关系归结为一个导致线性方程组的目标函 数 通过求解线性方程组求出降阶曲线的控制点 实现了一次降多阶逼近 此外 白宝 n 5 3 1 提出了一种自适应降阶方法 该方法的特色为依照拐点 曲率极大点的优先次序选择分割点 除了具有传统方法的端点插值和g 一连续 中山大学博士学位论文 的特点外 还具有得到的二次b 6 z i e r 曲线段数较少的优点 1 3 2b e z i e r 曲面降阶 对于b e z i e r 曲面的降阶 d a n n e b e r g 3 8 h o s c h e k 3 9 l a n c h a n c e 4 5 e e k 4 6 陈国栋等i s 4 将b e z i e r 曲线降阶方法推广到了张量积曲面的降阶 胡事民将 b e z i e r 曲线的控制顶点优化扰动方法应用于三角域 5 5 及矩形域曲面 5 6 的降阶 周登文 5 7 基于厶范数 给出基于曲面间体积极小的约束优化算法 将b e z i e r 曲面的降阶问题转变为线性方程组的求解 并给出降阶逼近问题解的存在性证 明 还对逼近误差进行了分析 并利用曲面离散算法减少降阶逼近误差 郭清伟 5 8 根据原张量积b e z i e r 曲面与降多阶张量积b e z i e r 曲面在最小二乘 范数下的距离函数在单位正方形 0 1 木 0 1 上取最小值 得到张量积b e z i e r 曲面 降多阶逼近的方法 在降多阶过程中 分别考虑了带角点高阶插值条件和不带角 点插值条件的情形 1 3 3b 样条曲线降阶 由于b 样条曲线的降阶比较复杂 因此这方面的降阶方法不是很多 1 9 9 5 年p i e g l 和t i l l e r 5 9 给出了b 样条曲线的一种降阶方法 先在各奇点处将原b 样 条曲线分解成一系列的b e z i e r 曲线段 再对每段b e z i e r 曲线采用类似于f o r r e s t 的基于升阶反过程的降阶方法进行降阶 最后将降阶后的所有b e z i e r 曲线段重新 拼接成b 样条曲线 并去除不必要的节点 该算法降阶后的b e z i e r 曲线段之间 可保持 i n 2 1 阶连续 具有较明显的几何直观性 但计算误差较大 1 9 9 8 年 w o l t e r s 等 6 0 基于b 样条曲线升阶的b l o s s o m 算法 先对b 样条曲线分段用最 小二乘法进行降阶 然后再对所产生的多组控制顶点进行加权组合 对b 样条 曲线进行降阶处理和光顺设计 另一类方法是基于控制点扰动的降阶方法 6 1 6 2 6 3 6 4 此类方法通过极 小化扰动项用退化b 样条曲线逼近原曲线 2 0 0 0 年秦开怀等 6 1 根据b 样条升 阶恒等式导出了b 样条曲线退化的条件 并通过控制顶点扰动和约束优化方法 给出了b 样条曲线的 个降阶算法 该算法可结合节点插入技术 将降阶后的 误差控制在给定的误差范围内 雍俊海 6 2 给出均匀b 样条曲线退化的充要条 中山大学博 七学位论文 件 证明了满足退化条件的k 阶均匀b 样条曲线可以表示为 k 1 阶均匀b 样条 曲线 并给出相应的表示方法 并利用约束优化方法 提出均匀b 样条曲线的 一种降阶方法 潘日晶 6 4 直接给出了b 样条曲线的降阶公式 在用约束优化方 法求出可降阶的近似曲线后 就可直接用降阶公式求出降阶曲线 但这种基于用退化b 样条曲线逼近原曲线的方法被证明是不好的 文献 6 5 1 指出了这类方法的弊端 证明了 如果一条k 阶b 样条曲线可精确地降阶n k 1 阶b 样条曲线 则原k 阶b 样条曲线实际上是一条整体的 k 2 次多项式曲线 经过扰动约束后生成的退化 k 1 次b 样条曲线实际上是一条 k 2 次多项式曲线 如果给定的原k 阶b 样条曲线不能被一条 k 2 次多项式曲线很好的逼近 经过扰 动约束后生成的k 阶b 样条曲线和原k 阶b 样条曲线之间的误差就很大 无沦 是理论还是在实际应用中 合理的做法一般是用分段定义的曲线去逼近一条形状 复杂的整体曲线 而基于扰动约束的b 样条曲线降阶算法则正好相反 用一条 整体曲线去逼近分段定义的曲线 这在大多数情况下难以给出理想的结果 文中 提出了一种采用最佳平方逼近技术对b 样条曲线做降阶运算的方法 但只给出 了基本思路 没有给出具体的算法和误差分析 1 3 4 有理曲线降阶 有理b e z i e r 曲线降阶因有理表示具有较大的自由度且可精确表示圆锥曲线 在如今的工业标准s t e p 中己包括有理曲线和曲面 在c a d 系统中已被大量的 使用 然而由于有理表示的复杂性 直接对其进行降阶处理相当困难 1 9 9 3 年s e d e r b e r g 和常庚哲 6 6 通过最佳线性公因子给山了有理平面b e z i e r 曲线的一种降阶方法 指出可以对没有公因子的一组多项式 x 0 y f w f n r b 进行一个微小摄动s x t s r f 使得 x 毛 f y f e a t w f 毛 f 有公因子 t a 且最终转化为多变量的管道问 题 结合c h e b y s h e v 多项式求解此管道问题 进一步可求得有理降阶逼近曲线 陈发来 6 7 矛1 j 用移位的c h e b y s h e v 多项式 给出了保端点的摄动 即使得 t 口 e x b g d s 6 c w a s 6 0 则当多项式基函数是b e m s t e i n 基 中山大学博士学位论文 时 用羔w t 器6 筹篇来代替筹器 就实现了保糕插值脯理 十w f 似 f w f 以r 曲线降阶逼近 由于门次曲线降阶逼近所需摄动向量的极小模当区间对分时近似 缩小到1 2 因此该降阶方法具有较好的降阶逼近效果 但计算较为繁琐 无法 一次降多阶 康宝生 6 8 刊哿有理b e z i e r 曲线降阶问题直接转化为非线性规化问题 并采用遗传算法求解 降阶效果比较好 但一般来说 非线性规化问题的求解是 非常费时的 当有理b e z i e r 曲线的控制点比较多时 计算速度比较慢 对于n u r b s 曲线降阶问题 成敏 6 9 应用n u r b s 曲线的显式矩阵表示以及 c h e b y s h e v 多项式理论进行处理 实现了n u r b s 曲线的一次降多阶 该方法对 单段n u r b s 曲线段降阶效果比较好 但对整条曲线的降阶处理方法是 先分段 处理 再将降阶后的各曲线段相同位置上的控制点和权因子进行平均 从而得到 近似最优的降阶逼近曲线 显然 该方法得到的并不是全局最优的降阶逼近曲线 1 4 极小曲面造型 极小曲面问题是微分几何领域中一个古老而活跃的问题 7 0 该问题最早由 l a g r a n g e 提出 l a g r a n g e 给出了极小曲面方程即所谓的e u l e r l a g r a n g e 方程 后 来 由于p l a t e a u 在极小曲面方面的研究 人们的注意力开始转移到的p l a t e a u 问 题上来 即给定一条闭的可求长的空问j o r d a n 曲线 寻找以这条空间曲线为边 界的具有极小面积的曲面 极小曲面以平均曲率恒为0 作为特征 因此除了在有 限个点以外 极小曲面的g a u s s 曲率恒为负 所以 极小曲面具有很多优良的性 质 其结构稳定 自然光顺 在建筑设计 飞机轮船制造 分子化学 晶体学等 各个领域都有很重要的应用 在微分几何学中 极小曲面的研究已十分成熟 如何把极小曲面引入c a g d 领域 是一个极有价值的课题 e n n e p e r 曲面是一个著名的三次参数多项式极小 曲面的例子 金文标 7 1 1 使用e n n e p e r 曲面进行房顶曲面设计的研究 满家巨 7 2 证明了实际上e n n e p e r 曲面是唯一的一类三次参数多项式极小曲面 还给出了一 个参数多项式曲面表示极小曲面的充分条件 金文标 7 3 提出一种几何构造法 得到了一类三次多项式形式的负高斯曲率极小曲面 将其表示为三次b b 曲面 并将其用到房顶曲面设计当中 满家巨 7 2 1 讨论参数多项式极小曲面 证明了只 9 中山大学博士学位论文 存在一类三次等温参数极小曲面 并研究了这类曲面的一些基本性质 虽然这些 多项式极小曲面可以适用于c a d c a g d 系统 但它们的自由度太少 不便于控 制 在实际应用中极不方便 所以研究具有给定边界的极小曲面 对于将极小曲 面引入c a d c a g d 系统具有积极的意义 给定边界的极小曲面方程是一个非线性的二阶椭圆型方程 一般没有解析 解 这给极小曲面在c a d c a g d 领域的应用带来极大的困难 参数p l a t e a u 问 题就是要寻找具有给定边界的曲而面积极小的参数曲面 d o u g l a s 和r a d o 将问 题转化为在等温参数或称共形参数化下 d 试c h l e t 能量极小的问题 p l a t e a u 问 题的解具有如下性质 1 的各个坐标分量函数是q 上的调和函数 2 v 是等温参数 即满足工 工一工 工 工 工 0 因此 参数极小曲面问题实际上是在满足给定边界条件下 曲面参数化的最优化 问题 有许多文章研究参数p l a t e a u 问题的数值解 7 4 7 5 7 6 7 7 7 8 7 9 对于形如z 芎肛 力的极小曲面问题 就是求解二阶非线性椭圆偏微分方程的 问题 c o n c u s 8 0 讨论了极小曲面方程的差分求解方法 但计算量太大 满家巨 在文献 8 1 1 中使用有限元方法 利用一个近似的线性化策略 给出了求解方法 在文献 8 2 中 满家巨基于非线性约束优化方法和有限元方法 在算法中使用数 值延拓 使非线性问题的初值选择问题自动化 同时 使用线性化策略对非线性 问题进行线性化 用b e z i e r 曲面和b 样条曲面来近似逼近极小曲面 给出了矩 形域上极小曲面的b e z i e r 曲面和b 样条曲面的近似解 使用b 样条曲面近似极 小曲面 对于将极小曲面引入c a d c a g d 系统具有非常重要的意义 文献 8 2 1 在这方面做了很有意义的工作 但该方法只能处理矩形域上函数形式的极小曲面 问题 对于任意区域上的极小曲面 以及参数极小曲面问题 都无法处理 因此 有很大的局限性 1 5 带约束条件的插值和光顺问题 对于模型设计而言 大量地用到插值法或逼近法 如果我们考察一下实际的 i 业产品的模型设计过程就不难发现 许多产品 例如汽车外型设计 船体设计 与放样 飞机机身 机舱及机翼的设计 甚至刀片 刀架 鞋模等的造型设计以 1 0 中山大学博士学位论文 及服装设计 都对曲线曲面有特定的形状要求 常见的有保凸 保凹 保形等要 求 此外 在自然科学和社会科学等领域也有不少问题需要用到曲线曲面的插值 和逼近 在某些情况下 根据先验知识 拟合的曲线曲面要求是凸或凹的 这样 寻找既能很好拟合给定数据点 又能保持一定约束要求的曲线曲面就成为近年来 数值逼近方面的研究热点之一 当人们用计算机来处理这些曲线曲面时 就要考虑用一种方便并且效果较好 的方法 选用的方法不仅要能够快速实现插值和逼近 还要能满足现实问题中对 曲线曲面的形状进行灵活控制的要求 从上世纪八十年代开始 很多人尝试从约束最优化问题的角度来考虑曲线曲 面的保形插值和逼近问题 1 9 8 0 年h o m u n g 最先提出带二阶导数约束的最佳插 值问题的解是三次样条 8 3 后来l l i e v 和p o l l u l 1 9 8 4 8 4 1 1 8 5 m i c c h e l l i s m i t h s w e t i t s 和w a r