代数双曲B样条基的几乎严格全正性.pdf

第2 6 卷第2 期计算机辅助设计与图形学学报v 0 1 2 6N o 2 2 0 1 4 年2 月J o u r n a lo fC o m p u t e r - A i d e dD e s i g n & C o m p u t e rG r a p h i c sF e b 2 0 1 4 代数双曲B 样条基的几乎严格全正性 魏炜立，汪国昭 ( 浙江大学数学系杭州3 1 0 0 2 7 ) ( m i l e i r 1 6 3 c o m ) 摘要：样条基的几乎严格全正性和曲线插值适定性关系密切，是几何造型中一个基本且重要的问题文中证明了 代数双曲B 样条基具有几乎严格全正性：首先引入代数双曲B 样条函数，通过嵌入节点算法推导出函数的零点数和 变差数之间的关系；进一步，利用数学归纳法证明了该基具有几乎严格全正性文中的证明方法直观且具有几何性， 为造型中使用代数双曲B 样条基奠定了更为完备的理论基础 关键词：嵌入节点算法；几乎严格全正性；系数变差；代数双曲B 样条基 中图法分类号：T P 3 9 1 7 2 A l m O s tS t r i c t l yT o t a lP o s i t i V i t yo fA H B S p l i n eB a s e s W e iW e i I ia n dW a n gG u o z h a o ( D P 户r f m P ”f 盯 妇f P m n f i f 5 ，Z 巧如”gU n i 口P r s i f y ，H n n g z o “ 3 l 0 0 2 7 ) A b s t r a c t ：A 1 m o s ts t r i c t l yt o t a lp o s i t i v i t yi sh i g h l yr e l a t e dw i t ht h ep o i s e d n e s so fc u r v ei n t e r p o l a t i o n p r o b l e m I ti sl i v i n gab a s i cs t a t u si nt h eb a s e st h e o r y A g e o m e t r i c a la p p r o a c hi sp r o p o s e dt op r o v et h e c o l l e c t i o nm a t r i c e so fA HB s p l i n eb a s e sa r ea l m o s ts t r i c t l yt o t a l l yp o s i t i v em a t r i c e s F i r s t l y ，A H B s p l i n ef u n c t i o ni si n t r o d u c e d U s i n gk n o ti n s e r t e da l g o r i t h m ，t h er e l a t i o n s h i pb e t w e e nt h en u m b e ro f z e r op o i n t sa n dt h en u m b e ro fc o e f f i c i e n tv a r i a t i o n sc a nb ed e d u c e d F i n a l l y ，u s i n gm a t h e m a t i c a l i n d u c t i o n ，a l m o s ts t r i c t l yt o t a lp o s i t i v i t yo fA HB s p “n eb a s e sc a nb ep r o v e d T h ea p p r o a c hi s i n t u i t i v ea n dg e o m e t r i c a l K e yw o r d s ：k n o ti n s e r t e da l g o r i t h m ；a l m o s ts t r i c t l yt o t a lp o s i t i v i t y ；c o e f f i c i e n tv a r i a t i o n ；A HB s p l i n e b a s e s 曲线曲面造型是计算机图形学的重要课题有 理& z i e r 基和N U R B S 基虽然已成为C A G D 系统 中曲线曲面的标准表示形式，但它们无法精确表示 C A D C A M 系统中经常用到的一些特殊的曲线曲 面，如摆线、螺旋线等超越曲线为克服这些缺点，文 献 1 在空间5 p 口九 s i n h ，c o s h ，1 ，一2 ，卵3 上构造了代数双曲( a l g e b r a i c h y p e r b o l i c ，A H ) B 样 条基，它具有与非均匀B 样条基非常一致的基本性 质；同时，除了可以表示通常的多项式曲线曲面外， 其还可以精确表示所有的超越曲线曲面，具有极强 的造型能力 保形性与全正性有着十分密切的关系在从新 的空间构造参数曲线时，都要在该空间中去寻找一 组类似于雎z i e r 基的一组基，这是因为类B 6 z i e r 基具有最优保形性，也就是说，由其构造的参数曲线 最相似于其控制顶点文献 2 中通过嵌入节点算 法，采用具有几何特征的方法证明了非均匀代数双 曲三角B 样条基具有全正性，该方法可以推广到 A HB 样条基进一步，几乎严格全正性是更加完备 的性质，d eB o o r 等 3 发现B 样条的配置矩阵具有 几乎严格全正性；之后，文献 4 利用拉格朗日插值 中的S c h o e n b e r g W h i t n e y 性质证明了B 样条具有 收稿日期：2 0 1 3o 卜0 4 ；修回日期：2 0 1 30 60 7 基金项目：国家自然科学基金( 6 1 2 7 2 3 0 0 ，6 0 9 3 3 0 0 8 ) 魏炜立( 1 9 8 7 ) ，女，博士。主要研究 方向为图像处理、c A G D ；汪国昭( 1 9 4 4 一) ，男，教授，博士生导师，主要研究方向为c A G D 、医学图像处理 万方数据 第2 期魏炜立，等：代数双曲B 样条基的几乎严格全正性 几乎严格全正性，并在文献 5 中进一步分析了具有 该类型矩阵的其他特性；而在A H 空间中，并没有 类似的性质可以推广这个证明由此可见，对于这一 结论的严格证明具有必要性和重要性本文从一种 完全不同于文献 4 的思路出发，引入A HB 样条函 数，利用嵌入节点算法推导出函数零点数和系数变 差数之问的关系，直观地证明了A HB 样条基具有 几乎严格全正性从而完善了A HB 样条基的性质， 为其在几何造型中的使用奠定了更为坚实的基础 1A HB 样条基和A HB 样条函数 1 1A HB 样条基的构造 文献 1 中给出了空间B T 一s 户彻 s i n h ， 性质2 局部支撑性N m ( ) 一O ，( f i ，) 性质3 设r m a x ( s ：i 一m 如果r 愚一2 ， 那么 f 1 ，歹一i 一1 N ( 。) 一 【o ，J i 一1 性质4 在节点序列T 中，如果岛一川一一， f 汁，一一：+ 。那么区间 i ，汁。 内的A HB 样条基 将退化为A HB z i e r 基，同时B m ( 。) 一B m ( l _ 1 ) 一 o 图2 所示为A H 雎z i e r 基 图2A HB z i e r 基 c o s h ，1 ，矿_ 3 ) ，是3 上，忌阶的A HB 样条基 的构造方法设节点序列T 一( ：) 兰，其中。， 1 3A HB 样条函数 首先在T 上定义一簇初始函数 N 埘( f ) 一 s i n h ( 一，) i n h ( l 十1 一i ) s i n h ( 件2 一，) i n h ( 汁2 一l + 1 ) ，其他 。 ：+ l ，。+ 1 。+ 2 则是阶A HB 样条基可由积分形式递归定义为 N m ( ) 一l( 艿姒1N 1 ( s ) 一 辩1 卜l N 刖卜l ( s ) ) d s ； 其中， 文；一( j “舢t ) 一 当N ( ) 一。时，约定文。N m ( ) 一o ，且满足 卜以山珧一 则 N m ( f ) ) 善。构成了亿 T 上的一组A HB 样条 基图1 所示为3 次A HB 样条基 图13 次A HB 样条基 1 2A HB 样条基的性质 A HB 样条基具有和B 样条基几乎一致的基本 性质，如文献 1 中所描述，列举如下： 性质1 连续性N m ( ) 在i 处志一1 一砖阶连 续可导，其中r ；为，在节点序列T 中出现的次数 本文考虑一组志阶的A HB 样条，设该组基的 个数为咒，记为 N ，。( z ) ，N ：。( z ) ，N 卅( z ) ) 为 了后续证明中的需要，定义A HB 样条函数及其系 数变差 r r 一1 定义1 设厂( z ) 一c ，N 卅( z ) ，r 1 ，优o ， j = r m + r l 咒，则厂( z ) 称为A HB 样条函数，其定义 域记为J 熙， c ，c 川，c ，+ 。一。) 为系数 定义2 序列 c r ，f r + l ，c ，+ 。1 ) 中，若o G + 1 o ，r i ，+ m 一2 ，则记该序列中有一个变差对于 ， r 一1 厂( z ) 一c ，N ( z ) ，剔除 c r ，钳1 ，”，钳一) 中 J = r 等于。的系数之后得到一组新的序列，该序列中所 有的变差数称为厂( z ) 的系数变差数，记作S 一( c ， f r + 1 ，f r + 研一1 ) 例如，S 一( 1 ，一3 ，o ，6 ，一5 ，7 ) 一4 ，S ( 4 ，0 ，0 ， 0 ，7 ，一5 ，0 ，4 ) 一2 由定义2 可以推断，如果一组系数被分为两部 分，那么系数变差数则不会增加 2 嵌入节点算法及性质 2 1 嵌入节点算法 嵌人节点算法是C A G D 中一个非常重要的算 法，文献 1 中已经证明，A HB 样条基在嵌人节点 后，可使用嵌入节点算法表示新、旧基之间的关系， 它表示为在节点序列T 中新嵌人一个节点t i “ H 1 ，得到一个新的节点序列 妇；同时，N m ( ) 和 万方数据 2 6 0 计算机辅助设计与图形学学报第2 6 卷 州鼍( ) 分别对应为T 和T 上的A HB 样条基那 么，原系数可以用新系数的线性组合的形式表示为 N 卅( ) 一a N 臻( ) + 岛+ 1 女N ；挈。，。( ) 当0 r 忌时， f 1 ，i 一是 t 一 辩H ，卜岣 卜r + ， l O ，J i r + 1 f 1 ，歹i 一走+ 1 肌一 粒肌卜抖1 心一+ 2 1 0 ，J i r + 2 当r 志时， f 1 ，歹i 一走 a 2 i 一是 f 0 ，歹i 一是+ 1 角女一 i 一是+ 1 和 岛z 一 ，歹i s i n h ( “一i ) 面五而厂2 ，歹i + 1 ，歹i i n h ( i + 1 一“) 丽瓦而厂2 5 ，歹i + 1 这里r 是甜在原节点序列中的节点重数，如果： “ 荆，那么r O 图3 所示为在嵌入新的节点前后，某段区间上 基的变化 图3 嵌入节点算法不意图 2 2 嵌入节点算法的性质 因为钆。+ & ，。一1 ，那么在不断嵌入节点的过程 中，可以将嵌入节点前后的A HB 样条基的关系 记为 N j ：2 ( f ) 一口卅N ；譬1 3 ( f ) + ( 1 一口卅) N ；# ：2 ( ) ( 1 ) 其中， N 燃( f ) ) 表示对原基 N ( ) ) 执行了z 次嵌 人节点算法之后得到的一组新的基对于整组基来 说，其关系可以用矩阵的形式表示为 N 慰( z ) N ；