規(guī)范精度維數(shù)及其收斂性

賈 亮,魏麗娜,盛中平

(東北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,長春 130024)

1 分形的拼貼分解與拼貼逼近

在分形幾何中,分形維數(shù)[1]是一般圖像的重要數(shù)字特征,應(yīng)用廣泛[2-9]. 對于非自相似的一般圖像,通常采用Hausdorff維數(shù)與盒維數(shù)刻畫. Hausdorff維數(shù)是基于可數(shù)覆蓋和測度而引入的,盒維數(shù)則是基于有限覆蓋和容度而引進的. 因此,盒維數(shù)在實際估算中更方便可行,也是模式識別的數(shù)學(xué)工具之一[2-8].

一般情況下,分形的拼貼分解與拼貼逼近由問題的實際背景確定.

其中：Fi稱為分形F的第i個組合體;Ei稱為分形F的第i個逼近體. 也稱分形組合體Fi的逼近體為Ei.

例如,記區(qū)間 [a,b]生成的三分Cantor集為F. 設(shè)

E1=[a,a+(b-a)/3],E2=[a+2(b-a)/3,b],F1=F∩E1,F2=F∩E2,

則F=F1∪F2為F拼貼分解,F≈E1∪E2為F拼貼逼近.

若取基準體F0=F,基準逼近體E0=E1∪E2,則基本尺度L=b-a,基容數(shù)

c=V/V0=Vol(E1∪E2)/Vol(E0)=1；

若取基準體F0=F1,基準逼近體E0=E1,則基本尺度L=(b-a)/3,基容數(shù)

c=V/V0=Vol(E1∪E2)/Vol(E0)=2.

2 規(guī)范精度維數(shù)與校正精度維數(shù)

盒維數(shù)的計算,通常利用某類盒覆蓋實現(xiàn). 如利用網(wǎng)方體覆蓋計算盒維數(shù)是一種最常用的方法. 下面先對盒覆蓋的盒長和盒子數(shù)進行規(guī)范化處理.

1)r=δ/L(關(guān)于基本尺度的相對盒長)稱為分形F關(guān)于盒覆蓋的微精度. 此時,也稱該盒覆蓋為F的一個r-精度盒覆蓋;記基本尺度相對于盒長數(shù)為ν=L/δ,ν稱為分形F對于盒覆蓋的基線數(shù).

2) 在以δ(≤L)為盒長的盒覆蓋下,記N為覆蓋分形F的最少盒子數(shù),N稱為F在r-精度盒覆蓋下的微盒數(shù)；記Ni為覆蓋分形F的第i個組合體Fi的最少盒子數(shù),Ni稱為F在r-精度盒覆蓋下的第i個微盒數(shù);記N0為覆蓋分形基準體F0的最少盒子數(shù),N0稱為F在r-精度盒覆蓋下的基盒數(shù);記F相對于F0的平均微盒數(shù)N*=N/c,N*稱為分形F在r-精度盒覆蓋下的規(guī)范微盒數(shù).

對于三分Cantor集,可用其生成步驟中產(chǎn)生的閉區(qū)間作為盒覆蓋. 當(dāng)基準體F0=F時,取盒覆蓋的盒長δ=(b-a)/3k,則微精度r=δ/L=1/3k,基線數(shù)ν=L/δ=3k；基盒數(shù)N0=2k,微盒數(shù)N=2k；規(guī)范微盒數(shù)N*=N/c=2k. 當(dāng)基準體F0=F1時,取盒長δ=(b-a)/3k,則微精度r=δ/L=1/3k-1,基線數(shù)ν=L/δ=3k-1；基盒數(shù)N0=2k-1,微盒數(shù)N=2k；規(guī)范微盒數(shù)N*=N/c=2k-1.

下面引入盒維數(shù)的兩種近似形式. 當(dāng)分形F存在盒維數(shù)(設(shè)為d)時,記c0=N0/νd,c0稱為r-精度(r=1/ν)基自容數(shù). 進而N0=c0νd. 由于基容數(shù)c可視為分形F包含基準體F0的個數(shù),因此逼近分形F總的盒子數(shù)可以近似地視為cN0=cc0νd=cc0(L/δ)d=cc0r-d. 又在微盒數(shù)及拼貼逼近的意義下可知,總的盒子數(shù)即為微盒數(shù)N. 從而有N≈cN0=cc0νd=cc0(L/δ)d=cc0r-d,進而可得

N*=N/c≈N0=c0(L/δ)d,N*≈c0νd,N*≈c0r-d.

于是lnN*≈lnc0-dlnr,因此

d≈(lnN*-lnc0)/(-lnr)=lnN*/lnν-lnc0/lnν.

特別地,當(dāng)r→0時,ν→∞,而基自容數(shù)c0是常數(shù). 故當(dāng)r非常小時或者c0趨近于1時,近似有d≈-lnN*/lnr=lnN*/lnν.

當(dāng)微精度r不變時,顯然基自容數(shù)c0=N0/νd=N0/r-d是只與分形的基準體F0相關(guān)的常數(shù),從而lnc0/lnν也是僅與分形的基準體F0相關(guān)的常數(shù). 當(dāng)做聚類分析時,要用同一個基準體(對于不同的分形),此時諸lnN*/lnν相當(dāng)于該相應(yīng)維數(shù)d的一個平行移動,即lnN*/lnν=d+lnc0/lnν. 因此,把維數(shù)lnN*/lnν作為聚類分析的一種特征(當(dāng)微精度r不變時),而且可以進一步校正為lnN*/lnν-lnc0/lnν.

1)dr(F)?-lnN*/lnr=(lnN-lnc)/(lnL-lnδ),dr=dr(F)稱為有界集F在該r-精度盒覆蓋下的r-精度維數(shù),也稱為規(guī)范精度維數(shù).

3 規(guī)范精度維數(shù)的收斂性

規(guī)范精度維數(shù)和校正精度維數(shù)都是與盒覆蓋和盒覆蓋精度相關(guān)的一種數(shù)字特征,二者均可用于快速分類. 在數(shù)值上,校正精度維數(shù)更接近于盒維數(shù),是盒維數(shù)很好的逼近.

證明：已知給定 Rn中的集合F(有界集),用邊長為δ的空間網(wǎng)方體盒覆蓋,設(shè)其微盒數(shù)為N. 記F0的基容數(shù)為c(常數(shù)),基本尺度為L(常數(shù)),則微精度r=δ/L,規(guī)范盒數(shù)N*=N/c. 又因為

當(dāng)分形存在盒維數(shù)時,由盒維數(shù)的定義可得

證畢.

定理1表明,在規(guī)范精度維數(shù)中當(dāng)δ→0時,lnc和lnL可忽略不計,進而得到盒維數(shù)的形式. 但在實際計算中,取極限是不能實現(xiàn)的,因此,規(guī)范盒維數(shù)中l(wèi)nc和lnL的影響不可忽略.

[1] Falconer K. Fractal Geometry: Mathematical Foundations and Applications [M]. New York: John Wiley &Sons,1990: 36-69.

[2] Hyde J,Laschos V. On the Box Dimensions of Graphs of Typical Continuous Functions [J]. J Math Anal Appl,2012,391(2): 567-581.

[3] LI Jian,DU Qian,SUN Cai-xin. An Improved Box-Counting Method for Image Fractal Dimension Estimation [J]. Pattern Recognition,2009,42(11): 2460-2469.

[4] Kruger A. Implementation of a Fast Box-Counting Algorithm [J]. Computer Physics Communications,1996,98(1/2): 224-234.

[5] TIAN Cheng-tai,WANG Jun,BU Hong-gang. Comparison of Fabric Defect Detection by Orginal and Simplified Box-Dimesion Feature Vectors [J]. Journal of Donghua University: Natural Science,2011,37(5): 579-585. (田承泰,汪軍,步紅剛. 簡化前后的盒維數(shù)用于織物疵點檢測的對比 [J]. 東華大學(xué)學(xué)報: 自然科學(xué)版,2011,37(5): 579-585.)

[7] ZHANG Ai-hua,LIAO Gong-fu. Hausdorff Dimension and Measure of Allows Kneading Sequences to Unimodal Mapping [J]. Journal of Jilin University: Science Edition,2005,43(1): 45-46. (張愛華,廖公夫. 單峰映射允許搓揉序列的Hausdorff維數(shù)和測度 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版,2005,43(1): 45-46.)

[8] ZHAO Hai-ying,FENG Yue-ping,PENG Hong. Content-Based Xinjiang Folk Art Patterns Classification Using Fractal Dimension and SVM [J]. Journal of Jilin University: Science Edition,2011,49(2): 299-303. (趙海英,馮月萍,彭宏. 基于分形維數(shù)和SVM的新疆民間藝術(shù)圖案分類 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版,2011,49(2): 299-303.)

[9] WEI Li-na. Fractal Dimension and Its Normalized Treatment for Application [D]. Changchun: Northeast Normal University,2007. (魏麗娜. 分形的維數(shù)特征及其在應(yīng)用中的規(guī)范化處理 [D]. 長春: 東北師范大學(xué),2007.)