基于函數尺度因子的有理分形插值及其應用*

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

(1. 山東大學 數學學院, 濟南 250100; 2. 山東財經大學 計算機科學與技術學院, 濟南 250014)

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

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

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

1 有理分形插值模型

1.1 有理分形插值模型的構建

1.1.1 分形插值函數

設(xi,yi)為給定的一組數據點, 滿足:

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

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

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

(1)

其中-1

定義函數ωi:F→F為

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

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

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

(2)

其中

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

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

圖1 迭代系統Fig.1 Iterative system

1.1.2 有理分形插值曲線的構造

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

(3)

其中

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

從而

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

類似式(3), 構造擾動基函數Bi(x)為

(4)

其中

式(4)滿足

于是得

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

下面考慮具有函數尺度因子的IFS:

(5)

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

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

可證明具有函數尺度因子的FIFs為

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

(6)

將式(6)改寫為

(7)

其中

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

1.2 有理FIFs的性質

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

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)的基函數, 滿足

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

1.2.1 穩定性

穩定性是評價插值函數質量的重要指標, 其衡量插值數據的抗干擾能力.

其中

證明： 根據式(6), 有

進一步, 得

同理, 有

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

1.2.2 收斂性

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

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

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

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

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

其中

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

證明： 由文獻[20]的結果, 可得

(8)

進一步, 根據三角不等式, 有

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

(9)

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

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

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

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

(10)

其中

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

1.2.3 計盒維數

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

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

引理1設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分別是函數si(x)和Pi(x)的Lipschitz常數. 下面考慮等距節點的情形, 即對于所有i∈Λ,hi=hi+1, 若令

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

證明: 當迭代系統迭代一次后, 在每個區間Ii(i∈Λ)內均可得到(N+1)個新點. 由假設可知, 在每個區間Ii上至少有3個點不共線. 設從三點之一的y軸方向到其余兩點的最大垂直距離為hi, 則根據引理1, 每個區間Ii內的最大范圍為

定義非負向量H1,K,U1,E如下:

定義

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

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

(11)

其中

因此, 有

(13)

因此,

因此,

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

1) 當λ>1時, 有dimBG=1+logNλ；

2) 當λ≤1時, 有dimBG=1.

1.3 數值算例

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

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

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

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

表1 函數f(x)插值數據

表2 表1中數據的擾動數據

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

確定形狀參數

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

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

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

表3 函數尺度因子在數值算例中的應用

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

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

表4 用于曲線粗糙度分析的插值數據

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

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

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

2 實 驗

2.1 Fibonacci螺旋曲線建模

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

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

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

2.2 物體輪廓曲線建模

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

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

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

2.3 海岸線曲線建模

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

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

實驗結果表明, 本文提出的函數尺度因子有理樣條分形插值模型優于其他對比方法, 更適用于重建真實數據與不規則數據.

綜上可見, 本文構造的有理分形插值不僅具有傳統有理樣條插值的優點, 而且能有效描述高度不規則的數據. 表明具有函數尺度因子的有理分形曲線比經典有理樣條曲線靈活性更高, 在處理實際問題中更有效.