分形圖像壓縮

摘要：歐氏幾何學不能處理自然界中非常復雜的形狀，這只能借助于分形幾何學。分形圖象壓縮就是利用分形幾何學的有關(guān)原理進行編碼，達到圖象壓縮之目的。

關(guān)鍵詞：分形 收縮仿射變換 迭代函數(shù)系統(tǒng)

1 分形的概念

分形（fractal）一詞是由分形理論的現(xiàn)代奠基人曼德爾布羅特在1975年造出來的，這個詞的拉丁詞根含義是“破碎的、分裂的”。分形幾何或分形理論研究的對象是那些很不規(guī)則而有自相似性的形狀。所謂很不規(guī)則是指粗糙、不光滑、破碎、扭曲、纏繞等特性。典型的代表是海岸線的形狀或者云彩、山峰、樹頁的形狀。傳統(tǒng)的鷗幾里德幾何處理的是直線、由直線段組成的多邊形、圓以及由不太復雜的函數(shù)定義的曲線。對于很不規(guī)則的形狀，傳統(tǒng)的幾何學就難以處理了。典型的例子如“不列顛的海岸線有多長”。若以傳統(tǒng)的方法測量，海岸線的長度將取決于所用量尺的長度。對較長的量尺，一些彎曲的細節(jié)就回被忽略，因而海岸線的長度就會較短；短的量尺可以量出一些細節(jié)，量出的海岸線就較長。如此推算下去，當量尺的長度很小時，由于海岸線的形狀極其復雜，量得的長度就會變得極大。

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

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

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

* 分形應有精細的結(jié)構(gòu),有任意小比例的細節(jié);

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

* 分行通常有某種自相似的形式,可能是近似的或是統(tǒng)計的;

* 其“分形維數(shù)"一般大于其拓撲維數(shù);

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

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

則有N = （ L/ε）d

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

d = lnN / ln（L/ε）

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

d = ln3 / ln2 = 1.58496

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

分形維數(shù)的定義還有許多種，它門之間不僅有性質(zhì)上的差別，而且對同一形態(tài)算出的維數(shù)也可能不同。在許多定義中，豪斯多夫維數(shù)在理論上可能是最重要的，可惜這種維數(shù)的計算十分困難，目前還無法用來描述自然界的復雜形態(tài)。

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

2 分形圖象壓縮

2．1 收縮仿射變換（Contractive Affine Transformation）

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

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

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

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

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

當然，上面各個變換W的系數(shù)應保證W是收縮仿射變換。
分形幾何學中有一個定理：每一個迭代函數(shù)系統(tǒng)都定義了一個唯一的分形圖形，這個分形圖形稱為該迭代函數(shù)系統(tǒng)的吸收子（attractor）。這個定理稱為收縮影射不動點原理。最典型的例子是一片蕨子葉卻所對應的迭代函數(shù)系統(tǒng)：

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

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

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

設(shè)原來墊子3各頂點的坐標分別為（x1,y1），（x2,y2），（x3,y3）。變換所得小墊子的3個頂點坐標為（x'1,y'1），（x'2,y'2），（x'3,y'3）。圖2.3(b)表示的是把原電子變?yōu)樯厦嫘|子的坐標。把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所示各坐標點的數(shù)值代如以上方程組，得到。同理，利用左下方墊子和右下方墊子可求出變換W2和W3的系數(shù)。分別為：

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

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

3 分形圖像壓縮的實例

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

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

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

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

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

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

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

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

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