分形圖像壓縮
摘要:歐氏幾何學(xué)不能處理自然界中非常復(fù)雜的形狀,這只能借助于分形幾何學(xué)。分形圖象壓縮就是利用分形幾何學(xué)的有關(guān)原理進(jìn)行編碼,達(dá)到圖象壓縮之目的。
本文引用地址:http://butianyuan.cn/article/242229.htm關(guān)鍵詞:分形 收縮仿射變換 迭代函數(shù)系統(tǒng)
1 分形的概念
分形(fractal)一詞是由分形理論的現(xiàn)代奠基人曼德爾布羅特在1975年造出來(lái)的,這個(gè)詞的拉丁詞根含義是“破碎的、分裂的”。分形幾何或分形理論研究的對(duì)象是那些很不規(guī)則而有自相似性的形狀。所謂很不規(guī)則是指粗糙、不光滑、破碎、扭曲、纏繞等特性。典型的代表是海岸線的形狀或者云彩、山峰、樹頁(yè)的形狀。傳統(tǒng)的鷗幾里德幾何處理的是直線、由直線段組成的多邊形、圓以及由不太復(fù)雜的函數(shù)定義的曲線。對(duì)于很不規(guī)則的形狀,傳統(tǒng)的幾何學(xué)就難以處理了。典型的例子如“不列顛的海岸線有多長(zhǎng)”。若以傳統(tǒng)的方法測(cè)量,海岸線的長(zhǎng)度將取決于所用量尺的長(zhǎng)度。對(duì)較長(zhǎng)的量尺,一些彎曲的細(xì)節(jié)就回被忽略,因而海岸線的長(zhǎng)度就會(huì)較短;短的量尺可以量出一些細(xì)節(jié),量出的海岸線就較長(zhǎng)。如此推算下去,當(dāng)量尺的長(zhǎng)度很小時(shí),由于海岸線的形狀極其復(fù)雜,量得的長(zhǎng)度就會(huì)變得極大。
看看由瑞典數(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),因而處處沒(méi)有切線;它的長(zhǎng)度也不難證明是無(wú)窮的,因而傳統(tǒng)的幾何方法對(duì)科和曲線很難處理。
波蘭數(shù)學(xué)家謝爾品斯基從平面二維圖形出發(fā),用重復(fù)某一過(guò)程的辦法形成的曲線也是分形曲線的典型例子。如謝爾品斯基墊,它以一個(gè)三角形作為源圖形,以源三角形的1/4大小的倒三角形作為生成元。在源三角形中除去生成元,然后在剩下的3個(gè)三角形中重復(fù)這一步驟,得到9個(gè)更小的三角形,不斷重復(fù)上述步驟得到的極限曲線就稱為謝爾品斯基墊(見圖1.2)。
分形理論和應(yīng)用發(fā)展很快,但至今還沒(méi)有關(guān)于什么是分形的統(tǒng)一定義.一般公認(rèn)法爾科納對(duì)分形定義的描述比較合理:
* 分形應(yīng)有精細(xì)的結(jié)構(gòu),有任意小比例的細(xì)節(jié);
* 它是如此的不規(guī)則,以至其局部和整體都不能用傳統(tǒng)的幾何語(yǔ)言來(lái)描述;
* 分行通常有某種自相似的形式,可能是近似的或是統(tǒng)計(jì)的;
* 其“分形維數(shù)"一般大于其拓?fù)渚S數(shù);
* 分形通常能以非常簡(jiǎn)單的方法定義,由迭代方法產(chǎn)生。
從科和曲線或謝爾品斯基墊的例子中不難看到以上特點(diǎn),但“分形維數(shù)”值得一提。“分形維數(shù)”是一個(gè)表征分形復(fù)雜或粗糙程度的量,在歐氏幾何中,維數(shù)總是取整數(shù),直線是一維,平面是二維,立體是三維。把歐氏維數(shù)的概念推廣,得到的就是分形維數(shù)定義之一的相似維數(shù)。推廣過(guò)程如下。在圖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ù)的定義還有許多種,它門之間不僅有性質(zhì)上的差別,而且對(duì)同一形態(tài)算出的維數(shù)也可能不同。在許多定義中,豪斯多夫維數(shù)在理論上可能是最重要的,可惜這種維數(shù)的計(jì)算十分困難,目前還無(wú)法用來(lái)描述自然界的復(fù)雜形態(tài)。
建立了分形維數(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)過(guò)線性變換
后,圖形上各點(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é)果將使原來(lái)圖形收縮為一個(gè)點(diǎn)。
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)過(guò)10000:1的壓縮。是否夸大不得而知,但分形壓縮很有潛力卻是無(wú)疑的。
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)。前一種方法適合于那些自相似性很強(qiáng)的圖形。此處以謝爾品斯基墊為例加以說(shuō)明。圖2.3(a)是一個(gè)謝爾品斯基墊,可以看出,整個(gè)墊子是由上、左下、右下3個(gè)較小的墊子組成。每個(gè)較小的墊子是由原來(lái)的墊子經(jīng)收縮仿射變換得來(lái)的。如果能分別找出把原圖形變成3個(gè)小圖形的收縮放射變換,那么,整個(gè)迭代函數(shù)系統(tǒng)就定下來(lái)了。
設(shè)原來(lái)墊子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ù)(這個(gè)庫(kù)里只需存儲(chǔ)分形相應(yīng)的迭代函數(shù)系統(tǒng)代碼),原圖像分割的小片可按庫(kù)的目錄去尋找相應(yīng)的迭代函數(shù)系統(tǒng)。當(dāng)然,如何自動(dòng)把圖像合理地分割成小片,分形圖形如何適當(dāng)?shù)胤糯?、縮小或旋轉(zhuǎn)以使之與目標(biāo)盡可能的重合等,都還有大量的工作要做。
3 分形圖像壓縮的實(shí)例
利用分形幾何方法進(jìn)行圖像壓縮的歷史比傳統(tǒng)方法要短的多,因此相對(duì)也沒(méi)有傳統(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 分形圖像壓縮有待研究的問(wèn)題
分形圖像壓縮是有失真的,失真量大小與壓縮比密切相關(guān)。盡管分形圖像壓縮有巨大的潛力,但要把這種潛力釋放出來(lái),還有許多問(wèn)題有待進(jìn)一步的研究,主要表現(xiàn)在:
* 普遍性問(wè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ì)特性和視覺(jué)特性,但信息量卻很少,可用幾條簡(jiǎn)單的確定規(guī)則迭代出來(lái)。傳統(tǒng)的建立于信息論之上的圖像壓縮技術(shù)幾乎不能壓縮這類圖像。而使用分形編碼,只需對(duì)少數(shù)幾條變換規(guī)則進(jìn)行編碼,即可以獲得非常高的壓縮比。但另一方面,由于自然界的景物千差萬(wàn)別,因此分形壓縮尚有許多問(wèn)題有待人們深入研究。
評(píng)論