3點Binary插值細分法的性質(zhì)以及應用

黃樹培， 鄭紅嬋， 閆飛一， 胡 韻

（西北工業(yè)大學應用數(shù)學系，陜西 西安 710129）

3點Binary插值細分法的性質(zhì)以及應用

黃樹培， 鄭紅嬋， 閆飛一， 胡 韻

（西北工業(yè)大學應用數(shù)學系，陜西 西安 710129）

為了使細分格式具有好的性質(zhì)：如光滑性、保凸性，提出了 3點 binary插值細分格式，然后分析了該細分格式的連續(xù)性、保凸性以及分形等性質(zhì)與參數(shù)之間的關系，最后給出了該細分格式性質(zhì)的一些應用。

插值細分格式; 連續(xù)性; 保凸性; 分形性質(zhì)

細分是一種有效的曲線曲面造型技術。由于具有算法簡單、易于實現(xiàn)等優(yōu)點，因此廣泛地應用于計算機圖形學、計算機輔助幾何設計、計算機動畫、逆向工程以及醫(yī)學圖像處理等領域。

細分格式根據(jù)極限曲線曲面是否經(jīng)過初始控制頂點，可分為插值細分格式和逼近細分格式。通常逼近細分格式生成的極限曲線更光滑，例如Siddiqi和Ahamd[1]提出了3點binary逼近細分格式，其極限曲線是 C2連續(xù)的；Siddiqi和Rehan[2]提出了一個改進的4點binary逼近細分格式，其極限曲線可以達到 C5連續(xù)。由于具有插值的性質(zhì)，因此在實際應用中插值細分格式比逼近細分格式更有吸引力。Dyn等[3]提出了 4點binary插值細分格式，其極限曲線是C1連續(xù)的；Weissman[4]提出了6點binary插值細分格式，其極限曲線可以達到 C2連續(xù)。在這基礎上，后來又出現(xiàn)了一些其他改進的binary插值細分格式如蔡志杰[5]，并分析了其光滑性等基本性質(zhì)。

Bézier方法是一種幾何造型方法，其優(yōu)點是具有保形性，但其缺點之一是不具有插值性質(zhì)，于是為了滿足插值性質(zhì)以及保形性質(zhì)，丁友東和華宣積[6]提出了一類保凸的非線性插值細分格式。

在分形理論中，分形的生成時非常重要的。有很多方法可以用來生成分形，例如，Bahar[7]利用函數(shù)迭代系統(tǒng)的方法；Prusinkiewicz和Lindenmayer[8]利用L系統(tǒng)的方法；齊東旭和戈建濤[9]利用細分的方法等。

在實際應用中有時要求極限曲線具有好的性質(zhì)：如光滑性、局部性和保凸性等。于是本文構造了一個3點binary插值細分格式，其極限曲線是 C1連續(xù)的。該細分格式具有好的性質(zhì)：局部性，3點細分格式的支撐寬度是 4，Dyn等[3]

中的4點插值細分格式是也 C1連續(xù)的，但其支撐寬度是6。保凸性：當給定的初始數(shù)據(jù)為嚴格凸時，3點binary插值細分格式的細分參數(shù)滿足一定條件時，極限曲線也是凸的。同時還可以發(fā)現(xiàn)細分曲線的形狀與細分參數(shù)有一定的關系，可以控制曲線的膨脹與收縮，而且當細分參數(shù)在一定的條件下時，細分格式可以產(chǎn)生分形曲線。

1 預備知識

其中 J0為初始有序控制頂點的有限下標集，設

為第k次細分后的有序控制頂點集， Jk為相應的有限下標集。均勻穩(wěn)定的binary細分法可表示為：

定義1 由 maskα 確定的多項式稱為細分法S的生成多項式。

定理1[10]若細分法S一致收斂，則其，滿足

細分法的收斂性與光滑性分析可歸結(jié)為向量值函數(shù)的分量的收斂性與光滑性分析，而每個分量是由同一細分法產(chǎn)生的標量函數(shù)，因此只需要對初始控制實數(shù)集進行分析。

定理2[10]設細分法S的滿足式(1)，則存在一個細分法 S1，滿足

S1稱為S的一階均差細分法,S稱為基細分法。 S的 n階均差細分法 Sn的 mask為則 其 生 成 多 項 式 為

定理3[10]細分法S一致收斂當且僅當細分法對任何初始數(shù)據(jù)一致收斂于0。

定理4[11]設細分法S的maskα滿足式(1)。若 存 在 正 整 數(shù)L及 實 數(shù) c, 0 ≤ c＜1,使則細分法S一致收斂。

根據(jù)定理1和定理4，當細分法S及其i階均差細分法 Si（i = 1,2,… ,n ）的 mask和分別滿足

2 3點Binary插值細分格式

下面給出單參數(shù)的3點binary插值細分格式：

經(jīng)過變形可化為：

其中，a為細分參數(shù)。

3 3點Binary插值細分格式的性質(zhì)

下面研究本文提出的3點binary插值細分格式的性質(zhì)：光滑性、保凸性以及分形性質(zhì)。

3.1 連續(xù)性

下面利用生成多項式的方法來分析 3點binary插值細分格式的連續(xù)性。

因為滿足式(1)，故有

因為 α（1）滿足式(2)，故有

實驗發(fā)現(xiàn)：當 a＜ 0時，極限曲線向外膨脹；當 a＞ 0時，極限曲線向內(nèi)收縮；當 a= 0時，極限曲線為初始控制多邊形。

3.2 保凸性

定理5 當初始數(shù)據(jù)是嚴格凸時，3點插值細分格式是保凸的。

利用二階差分定義：

得到相應的二階差分格式：

其中

證明由于而因此，當 a＜ 0時，＞ 0。

假設k時，命題成立。下面證明 k+1時，命題也成立。

因此，該細分格式對于嚴格的凸數(shù)據(jù)是保凸的。

3.3 分形性質(zhì)

即

相應的特征方程是：

即

相應的特征方程是：

由于初始條件

可知式(6)的特解為

其中

由式(7)可知，式(4)可化為

其特解為

其中

由于

其中

c1,c2同式(7)。

定理6 當0＜ a＜時，3點binary插值細分法的極限曲線是分形曲線。

證明當0＜ a＜時，由式(8)和式(9)歸納推理可知，經(jīng)k次細分后位于和之間的2k個小邊向量可表示為

其中， αij≠ 0,1 = 1,2,3。通過計算可知，當

4 數(shù)值算例

下面給出關于3點binary插值細分格式性質(zhì)的算例。

圖中的藍色實線表示初始控制多邊形，‘*’表示初始數(shù)據(jù)點，其他顏色的實線表示細分格式生成的極限曲線。

圖1 3點插值格式（綠線）與文獻[1]中的3點逼近格式（紅線）生成極限曲線的比較

圖2 細分參數(shù)a影響細分極限曲線

圖3中初始數(shù)據(jù)為 y-4= 16, y-3= 9, y-2=4, y-1= 1, y0= 0, y1= 1, y2= 4, y3= 9, y4= 16。品紅色實線表示 3點插值格式滿足保凸條件時細分八次的極限曲線；綠色實線表示細分格式不滿足保凸條件時細分八次的極限曲線。

圖3 細分格式滿足保凸條件和不滿足保凸條件

圖4 細分格式在a=時生成的分形曲線

從圖1中可以看出本文細分格式生成的插值細分曲線不具有幾何上的對稱性，但與逼近細分曲線比較起來具有保留初始數(shù)據(jù)的特點。從圖2和圖4可以看出細分曲線的形狀要受細分參數(shù)a的影響。而從圖3可以得出初始數(shù)據(jù)的性質(zhì)和細分參數(shù)a共同決定細分格式的保凸性。

5 結(jié) 論

本文提出了一個3點binary插值細分格式，分析了該細分格式的連續(xù)性、保凸性以及分形等性質(zhì)與細分參數(shù)之間的關系：

本文提出的細分格式為實際應用（如保凸性）以及快速生成分形曲線提供了一種方法。

[1] Siddiqi S S, Ahamd N. A new three point approximating C2subdivision scheme [J]. Applied Mathematics Letters, 2007, 20(6): 707-711.

[2] Siddiqi S S, Rehan K. Improved binary four point subdivision scheme and new corner cutting scheme [J]. Computers and Mathematics with Applications, 2010, 59(8): 2647-2657.

[3] Dyn N, Gregory J A, Levin D. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.

[4] Weissman A. A 6-point interpolatory subdivision scheme for curve design [D]. Tel-Aviv University, 1989.

[5] 蔡志杰. 變參數(shù)四點法的理論及其應用[J]. 數(shù)學年刊, 1995, 1(4) : 524-531.

[6] 丁友東, 華宣積. 一類非線性細分格式的保凸與分形性質(zhì)[J]. 軟件學報, 2000, 11(9) : 1263-1267.

[7] Bahar S. Chaotic orbits and bifurcation from a fixed point generated by an iterated function system [J]. Chaos, Solitions & Fractals, 1995, 5(6): 1001-1006.

[8] Prusinkiewicz P, Lindenmayer A. The algorithmic beauty of plants [M]. New York: Springer-Verlag, 1990.

[9] 齊東旭, 戈建濤. 點解序列與分形構造 Ⅰ[ J]. 北方工業(yè)大學學報, 1993, 5(3): 1-13.

[10] Dyn N. Subdivision schemes in computer-aided geometric design. Advances in Numerical Analysis(Light W, ed.)[M]. Clarendon Press, 1992: 36-104.

[11] Cavaretta A S, Dahmen W, Micchelli C A. Stationary subdivision [J]. Memoirs of the American Mathematical Society, 1991, (93): 1-186.

Properties and Applications of a 3-point Binary Interpolatory Subdivision Scheme

Huang Shupei, Zheng Hongchan, Yan Feiyi, Hu Yun
(Department of Applied Mathematics, Northwestern Polytechnical University, Xian Shaanxi 710129, China)

In order to make the subdivision scheme which has good properties, such as continuity, preserving-convexity, a 3-point binary interpolatory subdivision scheme is proposed. Then, the relationship between the properties including continuity, preserving-convexity and fractal property and the parameter are analyzed. Finally, some applications are given about the properties of the subdivision scheme.

interpolatory subdivision schemes; continuity; preserving-convexity; fractal property

TP 391

A

2095-302X (2014)01-0031-06

2013-05-07；定稿日期：2013-05-21

國家自然科學基金資助項目（61070233）

黃樹培（1987-），男，河南許昌人，在讀碩士研究生。主要研究方向為計算機輔助幾何設計、計算機圖形學。E-mail：hsp_0906@163.com