摘要：近10年來 ,基于分形的圖像壓縮技術(shù)發(fā)展很快。分形圖像壓縮技術(shù)具有極高的壓縮比、快速的解壓縮速度 ,在圖像通信、多媒體、互聯(lián)網(wǎng)中得到了廣泛的應(yīng)用。分形幾何理論研究的是很不規(guī)則的如粗糙、不光滑、破碎、扭曲、纏繞等且有自相似性的形狀。分形具有精細(xì)的結(jié)構(gòu) ,有任意小比例的細(xì)節(jié) ,其局部和整體都不能用傳統(tǒng)的幾何語言來描述 ,通常有某種自相似的形式 ,其“分形維數(shù) "一般大于其拓?fù)渚S數(shù) ,能以非常簡(jiǎn)單的方法定義 ,由迭代方法產(chǎn)生。

　　1 分形的概念

　　分形，是以非整數(shù)維形式充填空間的形態(tài)特征。分形可以說是來自于一種思維上的理論存在。1973年，曼德勃羅（B.B.Mandelbrot）在法蘭西學(xué)院講課時(shí)，首次提出了分維和分形幾何的設(shè)想。分形（Fractal）一詞，是曼德勃羅創(chuàng)造出來的，其原意具有不規(guī)則、支離破碎等意義，分形幾何學(xué)是一門以非規(guī)則幾何形態(tài)為研究對(duì)象的幾何學(xué)。由于不規(guī)則現(xiàn)象在自然界是普遍存在的，因此分形幾何又稱為描述大自然的幾何學(xué)。分形幾何建立以后，很快就引起了許多學(xué)科的關(guān)注，這是由于它不僅在理論上，而且在實(shí)用上都具有重要價(jià)值。

　　看看由瑞典數(shù)學(xué)家科和在1904年設(shè)計(jì)的一段曲線：在單位長(zhǎng)度的直線段E0中間，以邊長(zhǎng)為1/3 E0的等邊三角形的兩邊去代替E0中間的1/3，得到E1（見圖1.1）。對(duì)E1的每條線段重復(fù)上述做法又得到E2，對(duì)E2的每段又重復(fù)，如此下去得到的極限曲線就是科和曲線。顯然，科和曲線處處是尖點(diǎn)，因而處處沒有切線；它的長(zhǎng)度也不難證明是無窮的，因而傳統(tǒng)的幾何方法對(duì)科和曲線很難處理。

　　波蘭數(shù)學(xué)家謝爾品斯基從平面二維圖形出發(fā)，用重復(fù)某一過程的辦法形成的曲線也是分形曲線的典型例子。如謝爾品斯基墊，它以一個(gè)三角形作為源圖形，以源三角形的1/4大小的倒三角形作為生成元。不斷重復(fù)上述步驟得到的極限曲線就稱為謝爾品斯基墊（見圖1.2）。

　　分形理論和應(yīng)用發(fā)展很快，但至今還沒有關(guān)于什么是分形的統(tǒng)一定義。一般公認(rèn)法爾科納對(duì)分形定義的描述比較合理：

　　分形應(yīng)有精細(xì)的結(jié)構(gòu)，有任意小比例的細(xì)節(jié)；

　　它是如此的不規(guī)則，以至其局部和整體都不能用傳統(tǒng)的幾何語言來描述；

　　分行通常有某種自相似的形式，可能是近似的或是統(tǒng)計(jì)的；

　　其“分形維數(shù)"一般大于其拓?fù)渚S數(shù)；

　　分形通常能以非常簡(jiǎn)單的方法定義，由迭代方法產(chǎn)生。

　　從科和曲線或謝爾品斯基墊的例子中不難看到以上特點(diǎn)，但“分形維數(shù)”值得一提?！胺中尉S數(shù)”是一個(gè)表征分形復(fù)雜或粗糙程度的量，在歐氏幾何中，維數(shù)總是取整數(shù)，直線是一維，平面是二維，立體是三維。推廣過程如下。在圖1.3中，以尺寸為ε的量尺測(cè)量大小為L(zhǎng)的物體，量得的個(gè)數(shù)記為N，

　　則有N = （ L/ε）d

　　其中d就是維數(shù)，從圖中可以看出，d分別為1，2，3。也可以認(rèn)為：

　　d = lnN / ln（L/ε）

　　把這種方法推廣到謝爾品斯基墊上，不難得到它的維數(shù)d為：

　　d = ln3 / ln2 = 1.58496

　　用類似的方法可以求得科和曲線的維數(shù)d = ln4 / ln3。需要指出，這種維數(shù)稱為相似維數(shù)，它適用于有嚴(yán)格自相似的分形集合。

　　建立了分形維數(shù)的概念，就可以理解為什么用傳統(tǒng)的幾何方法去度量不列顛海岸線或者科和曲線的長(zhǎng)度時(shí)，得不到準(zhǔn)確結(jié)果。對(duì)待這些曲線，要先計(jì)算其分形維數(shù)，只有在相同維數(shù)下度量才有意義。

　　2 分形圖象壓縮

　　2.1 收縮仿射變換（Contractive Affine Transformation）

　　如果1個(gè)平面圖形上的各點(diǎn)經(jīng)過線性變換

    后，圖形上各點(diǎn)的距離比原有的距離要小，那么就稱這種變換是收縮仿射變換。這個(gè)變換的a，b，…，f是變換矩陣的系數(shù)。比如，一個(gè)變換為：

　　用它對(duì)圖2.1（a）的圖F各點(diǎn)進(jìn)行變換，變換后得到W（F）（見圖2.1（b））。其形狀與原圖形F相似，但各點(diǎn)的距離縮短。顯然，如果對(duì)一個(gè)圖形反復(fù)施加收縮仿射變換，即對(duì)W（F）再行變換得到W2（F），對(duì)W2（F）又施行變換得到W3（F）……，其迭代的結(jié)果將使原來圖形收縮為一個(gè)點(diǎn)。

　　收縮仿射變換原理：在有限維的情況，每個(gè)仿射變換可以由一個(gè)矩陣A和一個(gè)向量雙仿射變換b給出，它可以寫作A和一個(gè)附加的列b。一個(gè)仿射變換對(duì)應(yīng)于一個(gè)矩陣和一個(gè)向量的乘法，而仿射變換的復(fù)合對(duì)應(yīng)于普通的矩陣乘法，只要加入一個(gè)額外的行到矩陣的底下，這一行全部是0除了右邊是一個(gè)1，而列向量的底下要加上一個(gè)1。

　　AffineTransform類描述了一種二維仿射變換的功能，它是一種二維坐標(biāo)到二維坐標(biāo)之間的線性變換，保持二維圖形的“平直性”（譯注： straightness，即變換后直線還是直線不會(huì)打彎，圓弧還是圓弧）和“平行性”（譯注：parallelness，其實(shí)是指保二維圖形間的相對(duì)位置關(guān)系不變，平行線還是平行線，相交直線的交角不變。大二學(xué)過的復(fù)變，“保形變換/保角變換”都還記得吧，數(shù)學(xué)就是王道啊?。?。仿射變換可以通過一系列的原子變換的復(fù)合來實(shí)現(xiàn)，包括：平移（Translation）、縮放（Scale）、翻轉(zhuǎn)（Flip）、旋轉(zhuǎn)（Rotation）和錯(cuò)切（Shear）。

　　2.2 迭代函數(shù)系統(tǒng)（Iterated Function System）

　　人們把若干個(gè)收縮仿射變換的組合稱為迭代函數(shù)系統(tǒng)（IFS），即：

　　當(dāng)然，上面各個(gè)變換W的系數(shù)應(yīng)保證W是收縮仿射變換。

　　分形幾何學(xué)中有一個(gè)定理：每一個(gè)迭代函數(shù)系統(tǒng)都定義了一個(gè)的分形圖形，這個(gè)分形圖形稱為該迭代函數(shù)系統(tǒng)的吸收子（attractor）。這個(gè)定理稱為收縮影射不動(dòng)點(diǎn)原理。典型的例子是一片蕨子葉卻所對(duì)應(yīng)的迭代函數(shù)系統(tǒng)：

　　它所定義的蕨子葉如圖2.2所示。從這個(gè)例子可看出，要產(chǎn)生一個(gè)復(fù)雜的圖形需要得數(shù)據(jù)并不多。蕨子葉對(duì)應(yīng)的迭代函數(shù)系統(tǒng)只有24個(gè)系數(shù)。如果以8比特代表一個(gè)系數(shù)，那么192比特就可以代表一片蕨子葉?？梢妷嚎s比是很大的。分形圖象壓縮的提出者之一邦利斯曾經(jīng)揚(yáng)言，他實(shí)現(xiàn)過10000:1的壓縮。是否夸大不得而知，但分形壓縮很有潛力卻是無疑的。

　　2.3 采用迭代函數(shù)系統(tǒng)的圖像壓縮方法

　　從蕨子葉的例子可看出，迭代函數(shù)系統(tǒng)用不多的系數(shù)就可以代表一幅圖像，從而得到很大的壓縮比。但在實(shí)用時(shí)，如何尋找一的圖像的迭代函數(shù)系統(tǒng)呢？目前有兩個(gè)辦法；一是基于圖像的自相似性，直接計(jì)算迭代函數(shù)系統(tǒng)各收縮仿射變換的系數(shù)、二是把圖像分割成教小的部分，然后從迭代函數(shù)系統(tǒng)庫(kù)中查找這些小部分所對(duì)應(yīng)的迭代函數(shù)系統(tǒng)。圖2.3（a）是一個(gè)謝爾品斯基墊，可以看出，整個(gè)墊子是由上、左下、右下3個(gè)較小的墊子組成。每個(gè)較小的墊子是由原來的墊子經(jīng)收縮仿射變換得來的。如果能分別找出把原圖形變成3個(gè)小圖形的收縮放射變換，那么，整個(gè)迭代函數(shù)系統(tǒng)就定下來了。

　　通過迭代，可以發(fā)現(xiàn)有向一個(gè)單一點(diǎn)收縮和會(huì)聚的一個(gè)集合。在這種情況下，會(huì)聚到的這個(gè)點(diǎn)叫做吸引不動(dòng)點(diǎn)。反過來說，迭代也可以表現(xiàn)得從一個(gè)單一點(diǎn)發(fā)散；這種情況叫不穩(wěn)定不動(dòng)點(diǎn)。

　　當(dāng)軌道的點(diǎn)會(huì)聚于一個(gè)或多個(gè)極限的時(shí)候，軌道的會(huì)聚點(diǎn)的集合叫做極限集合或 ω-極限集合。引和排斥的想法類似推廣；依據(jù)在迭代下小鄰域行為，可把迭代分類為穩(wěn)定集合和不穩(wěn)定集合。其他極限行為也有可能；

　　設(shè)原來墊子3各頂點(diǎn)的坐標(biāo)分別為（x1,y1），（x2,y2），（x3,y3）。變換所得小墊子的3個(gè)頂點(diǎn)坐標(biāo)為（x'1,y'1），（x'2,y'2），（x'3,y'3）。圖2.3（b）表示的是把原電子變?yōu)樯厦嫘|子的坐標(biāo)。把W1的變換式：

　　展開：

　　x'1=a1x1+b1y1+e1

　　y'1=c1x1+d1y1+f1

　　x'2=a1x2+b1y2+e1

　　y'2=c1x2+d1y2+f1

　　x'3=a1x3+b1y3+e1

　　y'3=c1x3+d1y3+f1

　　解這組方程得到變換W1的各系數(shù)。以圖1.7所示各坐標(biāo)點(diǎn)的數(shù)值代如以上方程組，得到。同理，利用左下方墊子和右下方墊子可求出變換W2和W3的系數(shù)。分別為：

　　a2=d2=0.5,b2=c2=e2=f2=0,a3=d3=0.5,b3=c3=f3=0,e3=1.

　　直接計(jì)算迭代函數(shù)系統(tǒng)各變換矩陣系數(shù)的方法只能用于那些局部與整體有自相似特性的圖像，而許多圖像是難以用上述辦法尋找迭代函數(shù)系統(tǒng)的。但若能把整個(gè)圖像分割成小片，而這些小片圖像的迭代函數(shù)系統(tǒng)是已知的，同樣也可以實(shí)現(xiàn)圖像的壓縮。辦法就是事先建立一個(gè)分形庫(kù)，原圖像分割的小片可按庫(kù)的目錄去尋找相應(yīng)的迭代函數(shù)系統(tǒng)。當(dāng)然，如何自動(dòng)把圖像合理地分割成小片，分形圖形如何適當(dāng)?shù)胤糯蟆⒖s小或旋轉(zhuǎn)以使之與目標(biāo)盡可能的重合等，都還有大量的工作要做。

　　3 分形圖像壓縮的實(shí)例

　　利用分形幾何方法進(jìn)行圖像壓縮的歷史比傳統(tǒng)方法要短的多，因此相對(duì)也沒有傳統(tǒng)方法那么成熟。目前，盡管還不如傳統(tǒng)方法那樣已經(jīng)有了對(duì)活動(dòng)圖像進(jìn)行圖像壓縮的軟件、硬件，但對(duì)單幅圖像的分形壓縮方法已經(jīng)出現(xiàn)了商品化得計(jì)算機(jī)軟件。提供這種軟件的公司是美國(guó)迭代系統(tǒng)公司（Iterated System Inc.）。他們提供的軟件名叫SuperBase Fractal Picture Linkers，這是一個(gè)配合SuperBase數(shù)據(jù)庫(kù)系統(tǒng)的軟件。它可以把畫面進(jìn)行壓縮，得到的圖形文件稱為分形圖像格式（Fractal Image Format，F(xiàn)IF），也可以把FIF文件解壓成原有圖像。

　　對(duì)程序開發(fā)人員，迭代系統(tǒng)公司還有POEM Colorbox Ⅲ和POEM Videobox等軟件，前者使開發(fā)人員能夠在微軟視窗下把FIF文件集成到普通應(yīng)用軟件內(nèi)，后者則可對(duì)MS-DOS上運(yùn)行的應(yīng)用軟件中的圖像進(jìn)行壓縮或解壓。

　　4 分形圖像壓縮有待研究的問題

　　分形圖像壓縮是有失真的，失真量大小與壓縮比密切相關(guān)。盡管分形圖像壓縮有巨大的潛力，但要把這種潛力釋放出來，還有許多問題有待進(jìn)一步的研究，主要表現(xiàn)在：

　　普遍性問題。對(duì)于一定的整體與局部存在明顯相似性或仿射性的分形圖像類，分形圖像壓縮方法的壓縮比極高，但難以期望在很低的失真條件下，對(duì)一切分形圖像壓縮都具有極高的壓縮比，只能在壓縮比與失真度之間加以平衡。

　　就目前分形壓縮技術(shù)而言，其編碼時(shí)間比較長(zhǎng)。因此，需要開發(fā)編碼時(shí)間短、效率高的分形壓縮算法。

　　理論上，有關(guān)自動(dòng)壓縮原理與算法，失真測(cè)度或相似性準(zhǔn)則等有待繼續(xù)深入研究。

　　實(shí)用化編碼方法與硬件實(shí)現(xiàn)。

　　總之，分形理論用于圖像壓縮之所以有效，是因?yàn)樽匀唤缰衅毡榇嬖谥中挝矬w，它們表面上具有非常復(fù)雜的統(tǒng)計(jì)特性和視覺特性，但信息量卻很少，可用幾條簡(jiǎn)單的確定規(guī)則迭代出來。傳統(tǒng)的建立于信息論之上的圖像壓縮技術(shù)幾乎不能壓縮這類圖像。而使用分形編碼，只需對(duì)少數(shù)幾條變換規(guī)則進(jìn)行編碼，即可以獲得非常高的壓縮比。但另一方面，由于自然界的景物千差萬別，因此分形壓縮尚有許多問題有待人們深入研究。