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

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

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

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

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

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

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

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

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

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

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

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

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

1 預(yù)備知識

其中 J0為初始有序控制頂點的有限下標(biāo)集，設(shè)

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

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

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

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

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

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

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

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

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

2 3點Binary插值細(xì)分格式

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

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

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

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

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

3.1 連續(xù)性

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

因為滿足式(1)，故有

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

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

3.2 保凸性

定理5 當(dāng)初始數(shù)據(jù)是嚴(yán)格凸時，3點插值細(xì)分格式是保凸的。

利用二階差分定義：

得到相應(yīng)的二階差分格式：

其中

證明由于而因此，當(dāng) a＜ 0時，＞ 0。

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

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

3.3 分形性質(zhì)

即

相應(yīng)的特征方程是：

即

相應(yīng)的特征方程是：

由于初始條件

可知式(6)的特解為

其中

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

其特解為

其中

由于

其中

c1,c2同式(7)。

定理6 當(dāng)0＜ a＜時，3點binary插值細(xì)分法的極限曲線是分形曲線。

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

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

4 數(shù)值算例

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

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

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

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

圖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點插值格式滿足保凸條件時細(xì)分八次的極限曲線；綠色實線表示細(xì)分格式不滿足保凸條件時細(xì)分八次的極限曲線。

圖3 細(xì)分格式滿足保凸條件和不滿足保凸條件

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

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

5 結(jié) 論

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

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

[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ù)四點法的理論及其應(yīng)用[J]. 數(shù)學(xué)年刊, 1995, 1(4) : 524-531.

[6] 丁友東, 華宣積. 一類非線性細(xì)分格式的保凸與分形性質(zhì)[J]. 軟件學(xué)報, 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] 齊東旭, 戈建濤. 點解序列與分形構(gòu)造 Ⅰ[ J]. 北方工業(yè)大學(xué)學(xué)報, 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

國家自然科學(xué)基金資助項目（61070233）

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