基于函數(shù)尺度因子的有理分形插值及其應(yīng)用*

宋 剛, 楊曉梅, 姜 群, 包芳勛, 張云峰

(1. 山東大學(xué) 數(shù)學(xué)學(xué)院, 濟(jì)南 250100; 2. 山東財經(jīng)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 濟(jì)南 250014)

曲線造型技術(shù)在工業(yè)設(shè)計、航天技術(shù)、數(shù)字城市、媒體設(shè)計、醫(yī)學(xué)可視化等領(lǐng)域應(yīng)用廣泛. 但傳統(tǒng)的曲線插值方法, 如多項式插值、有理插值、樣條插值等, 通常都是生成光滑或分段光滑的曲線, 不適合從海岸線、云層和裂縫、巖石、雪花等實(shí)際現(xiàn)象中逼近或擬合高度不規(guī)則的數(shù)據(jù). 分形插值的概念由Barnsley[1]首次通過一個迭代函數(shù)系統(tǒng)(IFS)提出, 可擬合和逼近復(fù)雜真實(shí)現(xiàn)象中的不規(guī)則數(shù)據(jù). 目前對分形曲線的研究已有許多, 如： 文獻(xiàn)[2-5]討論了分形插值函數(shù)(FIFs)的構(gòu)造; 文獻(xiàn)[6-9]研究了FIFs的一些性質(zhì), 包括誤差、中心變差、曲線的光滑性、穩(wěn)定性和分形維數(shù)等; 文獻(xiàn)[10-12]進(jìn)一步將分形插值推廣到Hermite分形插值和樣條分形插值. 近年來, 傳統(tǒng)的多項式分形插值被拓展到有理的情形, 將形狀參數(shù)嵌入到IFS中[13-15].

上述研究所給出的單變量FIFs大多是由具有常數(shù)尺度因子的IFS生成, 因此所構(gòu)造的曲線有明顯的自相似特性, 這種分形插值方法很難精確擬合或逼近自相似性較弱的不規(guī)則數(shù)據(jù). 因此, 有必要研究具有可變尺度因子的FIFs, 但對該問題的研究目前報道較少. 文獻(xiàn)[16]研究了具有函數(shù)尺度因子的FIFs的一些分形特性, 包括光滑性、穩(wěn)定性和敏感性; 文獻(xiàn)[17]給出了具有可變參數(shù)的FIFs的顯式表示; 文獻(xiàn)[18]引入了一類具有可變參數(shù)的IFSs, 使得FIFs的生成靈活性更大; 文獻(xiàn)[19]使用具有函數(shù)尺度因子的有理IFS構(gòu)造了分形插值曲線, 估計了其計盒維數(shù). 上述研究都是基于多項式函數(shù)的具有函數(shù)尺度因子的IFSs.

研究表明, 有理函數(shù)比多項式函數(shù)能更有效、更靈活地描述復(fù)雜的實(shí)際現(xiàn)象. 本文首先利用傳統(tǒng)的帶有形狀參數(shù)的有理樣條插值方法, 構(gòu)造一類具有函數(shù)尺度因子的有理分形插值曲線; 其次研究有理FIFs的一些性質(zhì), 并估計有理分形曲線計盒維數(shù)的上下界; 最后通過數(shù)值算例驗證所給模型的有效性.

1 有理分形插值模型

1.1 有理分形插值模型的構(gòu)建

1.1.1 分形插值函數(shù)

設(shè)(xi,yi)為給定的一組數(shù)據(jù)點(diǎn), 滿足:

{(xi,yi)∈I×:i∈Λ*={0,1,…,N}},

其中I=[a,b]=[x0,xN]?. 設(shè)Ii=[xi,xi+1], 其中i∈Λ={0,1,…,N-1}. 令壓縮映射Li:I→Ii滿足:

其中0≤l<1. 令連續(xù)映射F=I×,Fi:F→滿足:

(1)

其中-1

定義函數(shù)ωi:F→F為

ωi(x,y)=(Li(x),Fi(x,y)),i∈Λ.

迭代函數(shù)系統(tǒng)(IFS){F;ωi:i∈Λ}生成唯一的吸引子, 它是連續(xù)函數(shù)f:I→的圖像, 稱函數(shù)f為一個FIF, 滿足f(xi)=yi(i∈Λ*), 并且

目前常用的FIFs基于以下IFS：

(2)

其中

參數(shù)si稱為尺度因子, 函數(shù)qi:I→(i∈Λ)是滿足條件(1)的連續(xù)函數(shù). Barnsley[1]證明了當(dāng)qi(x)=Pi°Li(x)-siBi(x)時, 對應(yīng)的FIFφ滿足φ(xi)=Pi(xi)(i∈Λ*), 這里Pi(x)和Bi(x)是連續(xù)函數(shù), 且Bi(x)滿足Bi(x0)=φ(x0),Bi(xN)=φ(xN).

下面利用數(shù)據(jù)集{(xi,yi):i=1,2,3,4,5}解釋迭代過程: 首先, 對于每個i(i=1,2,3,4), 壓縮映射Li(x)將區(qū)間[x1,x5]映射到子區(qū)間[xi,xi+1], 從而[xi,xi+1]獲得5個點(diǎn), 如圖1(A)所示. 其次, 每個子區(qū)間提供5個插值點(diǎn), 通過迭代方案(2)可以獲得對應(yīng)子區(qū)間插值曲線上的5個插值點(diǎn), 以區(qū)間[x2,x3]為例, 如圖1(B)所示. 因此, 第一次迭代后得到區(qū)間[x1,x5]上17個點(diǎn). 相同情形也會發(fā)生在更多的迭代中.

圖1 迭代系統(tǒng)Fig.1 Iterative system

1.1.2 有理分形插值曲線的構(gòu)造

設(shè){(xi,fi,di),i∈Λ*}為給定的一組數(shù)據(jù)集, 其中x0

(3)

其中

基于式(3)定義的有理函數(shù)插值性質(zhì), 有

從而

Vi=αifi+hidi,Wi=βifi+1-hidi+1.

類似式(3), 構(gòu)造擾動基函數(shù)Bi(x)為

(4)

其中

式(4)滿足

于是得

V1i=αif1+hNd1,W1i=βifN-hNdN.

下面考慮具有函數(shù)尺度因子的IFS:

(5)

其中si(x)是I上的Lipschitz函數(shù), 且

‖si‖∞=sup{|si(x)|:x∈I}<1.

可證明具有函數(shù)尺度因子的FIFs為

φ(Li(x))=si(x)φ(x)+Pi(Li(x))-si(x)Bi(x),x∈I,i∈Λ.

(6)

將式(6)改寫為

(7)

其中

注1如果對任意的i∈Λ, 尺度因子函數(shù)si(x)恒為0, 則RFIFs退化為經(jīng)典的有理插值函數(shù)Pi(x). 進(jìn)一步, 如果對任意i∈Λ, 尺度因子函數(shù)si(x)恒為0, 且αi=βi=3, 則有理RFIFs與C1Hermite插值一致. 表明在RFIFs中, 尺度因子的存在允許獲得不同于經(jīng)典插值的各種形式.

1.2 有理FIFs的性質(zhì)

插值函數(shù)(3),(4)由函數(shù)值和導(dǎo)數(shù)值表示, 為簡化, 可重寫為

Pi(Li(x))=ω1(θ,·i)fi+ω2(θ,·i)fi+1+ω3(θ,·i)hidi+ω4(θ,·i)hidi+1,

Bi(x)=ω1(θ,·i)f1+ω2(θ,·i)fN+ω3(θ,·i)hNd1+ω4(θ,·i)hNdN,

其中

{ωk(θ,·i)：k=1,2,3,4}為Pi(Li(x))和Bi(x)的基函數(shù), 滿足

ω1(θ,·i)+ω2(θ,·i)=1,ω3(θ,·i)-ω4(θ,·i)≤1.

1.2.1 穩(wěn)定性

穩(wěn)定性是評價插值函數(shù)質(zhì)量的重要指標(biāo), 其衡量插值數(shù)據(jù)的抗干擾能力.

其中

證明： 根據(jù)式(6), 有

進(jìn)一步, 得

同理, 有

由于上述不等式對于任何i∈Λ都成立, 因此

1.2.2 收斂性

圖10為兩種電流供電情況下振動加速度頻譜。對比正弦波供電,當(dāng)逆變器供電時,振動幅值整體增加。不同電流供電下振動加速度的最大幅值點(diǎn)均出現(xiàn)在8 500 Hz,9 533 Hz,10 700 Hz,11 400 Hz附近,接近模態(tài)分析結(jié)果中0階和8階固有頻率。開關(guān)頻率10 kHz附近振動加速度增加較大,究其原因是引入逆變器開關(guān)頻率的諧波電流加劇了高頻段的結(jié)構(gòu)共振。

在實(shí)際應(yīng)用中, 通常用誤差評價插值模型的精度. 誤差越小, 精度越高. 下面考慮RFIFφ(x)逼近原函數(shù)的有效性.

定理2設(shè)f為生成數(shù)據(jù)點(diǎn)的原始函數(shù){(xi,fi),i∈Λ*},φ(x)和Pi(x)是由式(7)和經(jīng)典有理三次插值函數(shù)構(gòu)造的RFIF, 則分別存在常數(shù)C和C*, 滿足下列條件：

1) 如果f∈C1(I), 則有

2) 如果f∈C2(I), 則有

其中

E(h)=‖f‖∞+hD1,E*(h)=F1+hND2,

證明： 由文獻(xiàn)[20]的結(jié)果, 可得

(8)

進(jìn)一步, 根據(jù)三角不等式, 有

‖f-φ‖∞≤‖f-Pi‖∞+‖Pi-φ‖∞.

(9)

因此, 只需討論式(9)右邊的第一項.

1) 如果f∈C1(I),x∈Ii, 則根據(jù)Peano-Kernel定理[21]得

2) 如果f∈C2(I), 根據(jù)文獻(xiàn)[22], 類似可得

‖f-φ‖∞≤C*h2‖f(2)‖∞,

(10)

其中

結(jié)合式(8),(9)及三角不等式, 可知2)成立.

1.2.3 計盒維數(shù)

曲線的分形維數(shù)是衡量曲線不規(guī)則性的一個指標(biāo), 其刻畫了曲線的粗糙程度. 本文基于盒子覆蓋法研究有理分形曲線的計盒維數(shù). 在分形幾何中, 計盒維數(shù)也稱為盒維數(shù), 是一種計算分形維數(shù)的方法. 計盒維數(shù)定義如下: 設(shè)F為定義在n上的任意非空有界子集,Nδ(F)為利用邊長為δ方塊覆蓋F集合的最小數(shù)目, 則F的計盒維數(shù)為

由式(7)定義的FIFφ(x)可知, 下列引理成立：

引理1設(shè)Rf[I]=sup{|f(x2)-f(x1)|:x1,x2∈I},φ(x)是由式(7)定義的FIF, 則

其中

N2=Lsi(N0+M0)+LPi,M0=max{|φ(x)|:x∈I},

Lsi和LPi分別是函數(shù)si(x)和Pi(x)的Lipschitz常數(shù). 下面考慮等距節(jié)點(diǎn)的情形, 即對于所有i∈Λ,hi=hi+1, 若令

定理3假設(shè)由式(5)定義的IFS吸引子G是連續(xù)函數(shù)φ(x)的圖, 將該函數(shù)對給定數(shù)據(jù)點(diǎn){(xi,yi):i∈Λ*}進(jìn)行插值, 插值點(diǎn)不共線, 且hi=hi+1(i∈Λ), 則G的計盒維數(shù)dimBG滿足下列條件:

證明: 當(dāng)?shù)到y(tǒng)迭代一次后, 在每個區(qū)間Ii(i∈Λ)內(nèi)均可得到(N+1)個新點(diǎn). 由假設(shè)可知, 在每個區(qū)間Ii上至少有3個點(diǎn)不共線. 設(shè)從三點(diǎn)之一的y軸方向到其余兩點(diǎn)的最大垂直距離為hi, 則根據(jù)引理1, 每個區(qū)間Ii內(nèi)的最大范圍為

定義非負(fù)向量H1,K,U1,E如下:

定義

Φ(c)=c1+c2+…+cn,c=(c1,c2,…,cn),

由于G是定義在I上連續(xù)函數(shù)的圖像, 因此用邊長為εr(εr<(b-a)/N)的正方形覆蓋Ii×∩G的最小正方形數(shù), 大于用邊長為hi的正方形覆蓋垂直線的最小正方形數(shù), 并且小于覆蓋矩形的最小正方形數(shù). 因此,

(11)

其中

因此, 有

(13)

因此,

因此,

注3當(dāng)函數(shù)尺度因子si(x)為常數(shù)si(對所有的i)時, 則吸引子G的計盒維數(shù)滿足下列條件：

1) 當(dāng)λ>1時, 有dimBG=1+logNλ；

2) 當(dāng)λ≤1時, 有dimBG=1.

1.3 數(shù)值算例

由式(7)定義的上述RFIFφ(x)包含原函數(shù)的導(dǎo)數(shù)值, 本文用算術(shù)平均法[23]估計導(dǎo)數(shù)值di(i∈Λ*):

其中Δi=(fi+1-fi)/hi,i∈Λ.

下面舉例證明所提出的RFIFs的近似有效性, 并說明有理分形曲線在特定函數(shù)插值數(shù)據(jù)擾動下的穩(wěn)定性.

例1考慮表1所列的插值數(shù)據(jù), 該數(shù)據(jù)是由函數(shù)f(x)=sinx(x∈[0.1,0.5]), 通過將其值近似到四位小數(shù)生成的. 表2是表1中數(shù)據(jù)的擾動.

表1 函數(shù)f(x)插值數(shù)據(jù)

表2 表1中數(shù)據(jù)的擾動數(shù)據(jù)

圖2 表3中不同函數(shù)尺度因子下的擾動誤差曲線Fig.2 Perturbation error curves with different function scaling factors in table 3

確定形狀參數(shù)

α1=α2=1,α3=0.002,α4=0.01,

β1=β2=0.8,β3=0.004,β4=0.04.

為證明函數(shù)尺度因子的有效性, 在插值數(shù)據(jù)的4個子區(qū)間選用不同的函數(shù)尺度因子, 列于表3. 圖2給出了不同函數(shù)尺度因子相應(yīng)的擾動誤差曲線, 表示插值數(shù)據(jù)擬合曲線與擾動數(shù)據(jù)擬合曲線之間的誤差曲線. 由圖2可見, 擾動誤差介于-3×10-3～5×10-3間. 結(jié)果表明, 本文構(gòu)造的有理分形插值曲線具有良好的抗干擾能力, 即對插值數(shù)據(jù)的擾動穩(wěn)定性很好.

表3 函數(shù)尺度因子在數(shù)值算例中的應(yīng)用

此外, 根據(jù)定理2選擇函數(shù)尺度因子, 分別在圖3中生成誤差曲線f(x)-φ(x), 表示原函數(shù)曲線與插值數(shù)據(jù)擬合曲線之間的誤差曲線. 由圖3可見, 誤差值介于-3×10-3～3×10-3間. 結(jié)果表明, 本文所提出的RFIFs對原函數(shù)f(x)具有較好的逼近結(jié)果.

例2用于曲線粗糙度分析的插值數(shù)據(jù)列于表4. 不同的函數(shù)尺度因子見表3.

表4 用于曲線粗糙度分析的插值數(shù)據(jù)

對于相同的插值數(shù)據(jù)和形狀參數(shù), 圖4為根據(jù)不同的函數(shù)尺度因子得到的分形插值曲線. 圖4驗證了函數(shù)尺度因子在有理IFS中的關(guān)鍵作用, 有理分形曲線在不同的函數(shù)尺度因子作用下具有不同的粗糙度.

圖3 表3中不同函數(shù)尺度因子下的誤差曲線Fig.3 Error curves with different function scaling factors in table 3

圖4 表3中不同函數(shù)尺度因子下的曲線粗糙度Fig.4 Roughness of curves with different function scaling factors in table 3

2 實(shí) 驗

2.1 Fibonacci螺旋曲線建模

下面利用本文提出的有理樣條分形插值模型重構(gòu)Fibonacci螺旋曲線. 圖5(A)為原始Fibonacci螺旋曲線; 圖5(B)為三次樣條插值結(jié)果； 圖5(C)為函數(shù)尺度因子多項式分形插值結(jié)果； 圖5(D)為常數(shù)尺度因子有理分形插值結(jié)果, 其中常數(shù)尺度因子為0.1； 圖5(E)為函數(shù)尺度因子有理分形插值結(jié)果.

圖5 Fibonacci螺旋曲線建模Fig.5 Fibonacci spiral curve modeling

由圖5可見, 本文提出的插值模型在Fibonacci螺旋曲線建模中效果較好. 下面給出定量分析數(shù)據(jù), 以進(jìn)一步對逼近效果進(jìn)行測評. 采用均方根誤差(root mean square error, RMSE)作為誤差分析指標(biāo), 能很好地反映測量的精密度. 計算可知： 三次樣條插值、函數(shù)尺度因子多項式分形插值、常數(shù)尺度因子有理分形插值、函數(shù)尺度因子有理分形插值的RMSE分別為0.000 8,0.000 5,0.000 5,0.000 4. 結(jié)果表明, 本文提出的函數(shù)尺度因子有理分形插值方法能精確擬合規(guī)則曲線.

2.2 物體輪廓曲線建模

下面利用本文提出的有理樣條分形插值模型重建物體的輪廓曲線. 以MPEG-7數(shù)據(jù)集中的甲殼蟲輪廓曲線為例進(jìn)行實(shí)驗, 該數(shù)據(jù)集在計算機(jī)視覺領(lǐng)域被廣泛應(yīng)用于形狀分析[24]. 圖6(A)為原始甲殼蟲曲線; 圖6(B)為三次樣條插值結(jié)果, 圖6(C)為函數(shù)尺度因子多項式分形插值結(jié)果； 圖6(D)為常數(shù)尺度因子有理分形插值結(jié)果, 其中常數(shù)尺度因子為0.4； 圖6(E)為函數(shù)尺度因子有理分形插值結(jié)果. 為更好地分析實(shí)驗結(jié)果, 用小矩形框顯示了局部細(xì)節(jié).

圖6 物體輪廓曲線建模Fig.6 Object contour curve modeling

由圖6可見： 與三次樣條插值方法相比, 本文模型能更有效地保留曲線的局部細(xì)節(jié)信息； 此外, 在函數(shù)尺度因子多項式分形插值與常數(shù)尺度因子有理分形插值的局部放大圖像中, 邊緣位置能觀察到尖銳的突起. 表明本文模型在曲線邊緣保持上表現(xiàn)出色, 能較好地保持原始曲線的局部細(xì)節(jié). 計算可知: 三次樣條插值、函數(shù)尺度因子多項式分形插值、常數(shù)尺度因子有理分形插值、函數(shù)尺度因子有理分形插值的RMSE分別為0.020 6,0.008 7,0.006 1,0.004 6. 結(jié)果表明, 本文提出的函數(shù)尺度因子有理分形插值方法對甲殼蟲輪廓曲線擬合的RMSE值最小, 表明該方法具有更強(qiáng)的逼近能力.

2.3 海岸線曲線建模

下面將本文提出的插值模型應(yīng)用于自然海岸線曲線建模, 該地形數(shù)據(jù)從國家海洋和大氣管理局(NOAA)獲取. 圖7(A)為原始海岸線曲線； 圖7(B)為三次樣條插值結(jié)果； 圖7(C)為函數(shù)尺度因子多項式分形插值結(jié)果； 圖7(D)為常數(shù)尺度因子有理分形插值結(jié)果, 其中常數(shù)尺度因子為0.2； 圖7(E)為函數(shù)尺度因子有理分形插值結(jié)果. 由圖7(B)可見, 三次樣條插值方法插值結(jié)果中曲線明顯失真; 由圖7(C),(D)可見, 局部放大區(qū)域中的邊緣位置出現(xiàn)冗余信息. 計算可知: 三次樣條插值、函數(shù)尺度因子多項式分形插值、常數(shù)尺度因子有理分形插值、函數(shù)尺度因子有理分形插值的RMSE分別為0.043 4,0.004 3,0.003 1,0.002 6. 結(jié)果表明, 本文提出的函數(shù)尺度因子有理分形插值方法的擬合效果在RMSE數(shù)值指標(biāo)上優(yōu)于其他曲線插值方法.

圖7 海岸線曲線建模Fig.7 Shoreline curve modeling

實(shí)驗結(jié)果表明, 本文提出的函數(shù)尺度因子有理樣條分形插值模型優(yōu)于其他對比方法, 更適用于重建真實(shí)數(shù)據(jù)與不規(guī)則數(shù)據(jù).

綜上可見, 本文構(gòu)造的有理分形插值不僅具有傳統(tǒng)有理樣條插值的優(yōu)點(diǎn), 而且能有效描述高度不規(guī)則的數(shù)據(jù). 表明具有函數(shù)尺度因子的有理分形曲線比經(jīng)典有理樣條曲線靈活性更高, 在處理實(shí)際問題中更有效.