分形理論幻燈片

分形理論及其在信號(hào)處理中的應(yīng)用分形理論簡(jiǎn)介分形理論在圖象壓縮中的應(yīng)用經(jīng)典分形圖像壓縮的工作過(guò)程分形圖像壓縮的改進(jìn)方法分形圖像編碼的發(fā)展趨勢(shì)分形圖像壓縮有待研究的問題一、什么是分形？1、問題的引入－－英國(guó)的海岸線有多長(zhǎng)2、歐氏幾何的局限性－－歐氏幾何主要是基于中小尺度上的點(diǎn)、線、面之間的關(guān)系3、分形----自然幾何分形理論簡(jiǎn)介分形理論簡(jiǎn)介二、分形的發(fā)展萌芽：1919年以前形成與發(fā)展：1919-1975年不斷完善和廣泛應(yīng)用：1975年以后

*分形(fractal)由曼德勃羅特(B.B.Mandelbrot)在1975年首次提出，其含義是“不規(guī)則的、分?jǐn)?shù)的、支離破碎的”物體。分形理論簡(jiǎn)介三、分形的定義

（1）滿足Dim(A)>dim(A)的集合A，稱為分形集其中:Dim(A)為集合A的Hausdoff維數(shù)（或分維數(shù)）,dim(A)為其拓?fù)渚S數(shù)。一般說(shuō)來(lái)，Dim(A)不是整數(shù)，而是分?jǐn)?shù)。

（2）部分與整體以某種形式相似的形，稱為分形

分形理論簡(jiǎn)介

圖1所示為Koch曲線，將線段等分為三段，中間一段以兩段等長(zhǎng)線段構(gòu)成的凸折線代替，此過(guò)程無(wú)限地重復(fù)下去，即可構(gòu)成Koch曲線。圖3表示了其動(dòng)態(tài)形成過(guò)程圖1

Korch曲線動(dòng)態(tài)形成過(guò)程

分形理論簡(jiǎn)介四、分形的特點(diǎn)

(1)分形的最基本特征是所謂的“自相似性”。如圖1(2)該集有精細(xì)結(jié)構(gòu)，即在任意小的比例尺度內(nèi)包含整體。如圖2(3)通常分形集的“分形維數(shù)”比它的拓?fù)渚S數(shù)要大；－－－說(shuō)明了分形的復(fù)雜性(4)許多情況下，分形集是非常簡(jiǎn)單的，或者是遞歸的。－－－說(shuō)明了分形的生成機(jī)制－－－自相似性是分形的靈魂它使得分形的任何一個(gè)片段都包含了整個(gè)分形的信息分形理論簡(jiǎn)介五、分形的應(yīng)用范圍分形觀念的引入并非僅是一個(gè)描述手法上的改變，從根本上講分形反映了自然界中某些規(guī)律性的東西近年來(lái)，分形理論已經(jīng)應(yīng)用于自然科學(xué)、工程技術(shù)、以及經(jīng)濟(jì)學(xué)和藝術(shù)等領(lǐng)域。本章僅就分形理論在信號(hào)處理方面的應(yīng)用作一簡(jiǎn)要介紹，重點(diǎn)講解分形理論在圖象處理中的應(yīng)用分形的維數(shù)－－分維的概念以Korch曲線為例korch曲線的維數(shù)＝1.2618分形的維數(shù)－－分維的概念分形理論把維數(shù)視為分?jǐn)?shù)設(shè)一條直線分為N段，每一個(gè)都按照一個(gè)比例系數(shù)r減小，有：Nr=1。對(duì)一個(gè)正方形來(lái)說(shuō)，也分成幾個(gè)小的正方形，也讓每一正方形的每邊的縮放比例為r。有：Nr2=1。設(shè)一個(gè)d維物體分為N等份，每一份的縮放比例是r，二者的關(guān)系是Nrd=1。分維數(shù)d=(logN)/(log(1/r))。

其中，d即所求物體的維數(shù)，N為將物體劃分的份數(shù)，r為每次縮放的比例。

分形的維數(shù)－－分維的概念例：Korch曲線的維數(shù)N=4和r=1/3d=(log4)/(log3)≈1.261859507143

分形理論在圖象壓縮中的應(yīng)用為什么分形方法可以用于圖像壓縮；用分形方法進(jìn)行圖像壓縮的基本思路分形理論在圖象壓縮中的應(yīng)用為什么分形理論能用于圖象壓縮∵分形圖像由某種變換生成，可以把圖像看作某種變換反復(fù)迭代的產(chǎn)物∴只需存儲(chǔ)的有關(guān)這些變換過(guò)程的信息，而不是存儲(chǔ)靜止的圖形的像素信息。∴只要抓住了變換過(guò)程，圖形就可以準(zhǔn)確地再現(xiàn)出來(lái)，而不必去存儲(chǔ)大量的像素信息。分形理論在圖象壓縮中的應(yīng)用分形理論在圖象壓縮中的應(yīng)用為什么分形理論能用于圖象壓縮例：考慮中分辯率(640×480)下，全屏顯示(FullScreen)，真彩色(TrueColor24位)，全動(dòng)作(FullMotion，25-30幀／秒)的圖象序列，播放1秒鐘的視頻畫面數(shù)據(jù)量為：

640×480×3×30=27,648,000字節(jié)若：降低彩色性逼真要求，量化為8位灰度，每秒顯示25幀，640×480×25=7,680,000字節(jié)分形理論在圖象壓縮中的應(yīng)用為什么分形理論能用于圖象壓縮圖象壓縮：指在沒有明顯失真的前提下，將圖象的位圖信息轉(zhuǎn)變成另外一種能將數(shù)據(jù)量縮減的表達(dá)形式。首先，盡管圖象中數(shù)據(jù)量很大，但數(shù)據(jù)之間不是完全獨(dú)立的，圖象中存在著各種各樣的相關(guān)性或冗余信息。即一部分?jǐn)?shù)據(jù)可以由另一部分?jǐn)?shù)據(jù)完全推算出來(lái)。其次，大部分圖象視頻信號(hào)的最終接收者都是人眼，人眼對(duì)圖象中的不同部分的敏感程度是不同的。分形理論在圖象壓縮中的應(yīng)用用分形方法進(jìn)行圖象壓縮的基本思路迭代函數(shù)系統(tǒng)，其實(shí)是一組壓縮仿射變換。每個(gè)壓縮仿射變換W形如下：

，是點(diǎn)的坐標(biāo)，是變換常數(shù)，表示點(diǎn)X和Y的距離S是小于1的正常數(shù)，稱為壓縮因子分形理論在圖象壓縮中的應(yīng)用（1）收縮仿射變換（ContractiveAffineTransformation）如果1個(gè)平面圖形上的各點(diǎn)經(jīng)過(guò)線性變換后，圖形上各點(diǎn)的距離比原有的距離要小，那么就稱這種變換是收縮仿射變換。這個(gè)變換的a，b，…，f是變換矩陣的系數(shù)。用它對(duì)某圖的圖F各點(diǎn)進(jìn)行變換,變換后得到W(F)，但各點(diǎn)的距離縮短。顯然，如果對(duì)一個(gè)圖形反復(fù)施加收縮仿射變換，即對(duì)W(F)再行變換得到W2（F），對(duì)W2（F）又施行變換得到W3（F）……，其迭代的結(jié)果將使原來(lái)圖形收縮為一個(gè)點(diǎn)。

分形理論在圖象壓縮中的應(yīng)用（2）迭代函數(shù)系統(tǒng)人們把若干個(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)原理。分形理論在圖象壓縮中的應(yīng)用例：蕨樹葉的迭代函數(shù)系統(tǒng)：

蕨樹葉對(duì)應(yīng)的迭代函數(shù)系統(tǒng)只有24個(gè)系數(shù)a1,b1,c1…..,若以8bit代表一個(gè)系數(shù)，那么192bit就可以代表一片蕨子葉。分形理論在圖象壓縮中的應(yīng)用（3）尋找迭代函數(shù)系統(tǒng)方法基于圖像的自相似性，直接計(jì)算迭代函數(shù)系統(tǒng)各收縮仿射變換的系數(shù)---適合于自相似性很強(qiáng)的圖形把圖像分割成較小的部分，然后從迭代函數(shù)系統(tǒng)庫(kù)中查找這些小部分所對(duì)應(yīng)的迭代函數(shù)系統(tǒng)。如圖5所示是一個(gè)謝爾品斯基墊分形理論在圖象壓縮中的應(yīng)用由圖5可以看出，整個(gè)墊子是由上、左下、右下3個(gè)較小的墊子組成。每個(gè)較小的墊子是由原來(lái)的墊子經(jīng)收縮仿射變換得來(lái)的。如果能分別找出把原圖形變成3個(gè)小圖形的收縮放射變換，那么，整個(gè)迭代函數(shù)系統(tǒng)就定下來(lái)了。圖55.2分形理論在圖象壓縮中的應(yīng)用下圖表示的是把原墊子變?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ù)。同理，利用左下方墊子和右下方墊子可求出變換W2和W3的系數(shù)。分別為：

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

分形理論在圖象壓縮中的應(yīng)用分形圖像壓縮的本質(zhì)是由于現(xiàn)實(shí)圖像中具有高度的仿射冗余度。即圖像中含有許多自我參考物，它有很多部分是自相似的，經(jīng)過(guò)適當(dāng)變換(變形、旋轉(zhuǎn)、平移）。各區(qū)域可以互相表達(dá)。所以，可以設(shè)法找出構(gòu)成圖像的各種分形結(jié)構(gòu)，從而求出產(chǎn)生該圖像的各種分形仿射變換表達(dá)式。經(jīng)典分形圖像壓縮的工作過(guò)程

編碼過(guò)程編碼過(guò)程的第一步是對(duì)圖像進(jìn)行分割,將圖像劃分為任意形狀,大小相等且互不重疊的R塊,即值域塊。再把圖形劃分為大一些且可以有重疊區(qū)域的D塊,即定義域。對(duì)圖像作這樣分塊的目的是為了在D塊和R塊之間,構(gòu)造一組收縮映射,這個(gè)映射通常為仿射變換。

編碼過(guò)程實(shí)質(zhì)：為某一R塊尋找與之最相近的經(jīng)變換的D塊,而IFS即為相應(yīng)的變換參數(shù),然后再對(duì)這些參數(shù)進(jìn)行編碼,以提高壓縮比。經(jīng)典分形圖像壓縮的工作過(guò)程

解碼過(guò)程

解碼過(guò)程是一個(gè)迭代過(guò)程。由譯碼恢復(fù)的IFS代碼對(duì)任意一幅初始圖像進(jìn)行迭代,直到前后兩次迭代結(jié)果變化很小時(shí)解碼結(jié)束,這時(shí)生成一幅與原始圖像十分相似但并非原圖拷貝的圖像,

∴這類壓縮屬于有損壓縮經(jīng)典分形圖像壓縮的工作過(guò)程分形圖像編碼理論基礎(chǔ)

★收縮映射定理：函數(shù)空間中的每個(gè)收斂映射都有一個(gè)固定點(diǎn)，使函數(shù)空間中的每個(gè)點(diǎn)經(jīng)過(guò)這個(gè)收縮映射的連續(xù)作用后形成的點(diǎn)收斂于這個(gè)固定點(diǎn)?！锏瘮?shù)系統(tǒng)定理：每個(gè)迭代函數(shù)系統(tǒng)都可以構(gòu)成函數(shù)空間中的一個(gè)收縮映射。

結(jié)論：每個(gè)迭代函數(shù)系統(tǒng)都決定一幅圖像經(jīng)典分形圖像壓縮的工作過(guò)程分形圖像編碼理論基礎(chǔ)反之：給定一幅圖像，能否找到一迭代函數(shù)系統(tǒng)使該系統(tǒng)正好能決定給定的圖像？★拼貼定理：給定一幅圖像a，可以選擇N個(gè)收縮映射，這幅圖像經(jīng)過(guò)N個(gè)變換得到N個(gè)象集.每個(gè)象集都是一塊小圖像。如果這N個(gè)小圖像拼貼起來(lái)的圖像與圖像a之間的距離任意小則這N個(gè)收縮映射構(gòu)成的迭代函數(shù)系統(tǒng)所決定的圖像就任意地接近圖橡a。

拼貼定理告訴我們尋找迭代函數(shù)系統(tǒng)的方法。

經(jīng)典分形圖像壓縮的工作過(guò)程分形圖像編碼方法

分形圖像編碼的過(guò)程是依據(jù)拼貼定理，通過(guò)繪定的圖像，尋找一組收縮映射，使其組成的迭代函數(shù)系統(tǒng)的吸引子逼近給定圖像，然后記錄下相應(yīng)參數(shù)。解碼過(guò)程是由相應(yīng)參數(shù)確定迭代函數(shù)系統(tǒng)，并根據(jù)迭代函數(shù)系統(tǒng)定理，經(jīng)過(guò)迭代生成圖像。分形圖像壓縮的改進(jìn)方法

1．提高壓縮比和編碼效果

★改進(jìn)分割的方法：有基本四叉樹分割法、基于HV分割法。這兩種分割方法都是將圖像分割成矩形。而圖像塊的相似性未必都落在矩形內(nèi)。代替水平或垂直剖分而采用的分割方法有基于三角形分割法、基于六邊形分割法、基于邊界分割法、基于菱形分割法、基于多邊形分割法。

。

★覆蓋式方法：覆蓋式方法有快速覆蓋式分形壓縮方法和四叉樹重組QR算法兩種。它們都是采用通過(guò)合并值域塊來(lái)提高壓縮比。

★提高顯示效果的后處理法：分形圖像壓縮對(duì)值域塊獨(dú)立編碼，這不能保證塊與塊之間的連接最光滑的，常有塊效應(yīng)出現(xiàn)，人的眼睛對(duì)此比較敏感。消除塊效應(yīng)的一個(gè)常用方法是后處理。一般采用2:1加權(quán)平均或3:2:1加權(quán)不均法。

分形圖像壓縮的改進(jìn)方法

2.提高編碼速度

編碼過(guò)程中最耗時(shí)的是搜索最佳匹配的定義域，要提高編碼速度，就必須縮小搜索范圍，且保證最佳匹配落在該范圍之內(nèi)。其改進(jìn)方法有：★分類法：在匹配之前按照?qǐng)D像的特征如中值、方差、力矩和其他感知或統(tǒng)計(jì)的幾何特征，將定義域和值域塊進(jìn)行分類，匹配時(shí)只在同一類中進(jìn)行搜索比較。這樣在不降低圖像質(zhì)量的前提下，大大提高了編碼速度。

常用的分類方法有：基于明暗度的定向分類、基于空域特征的分類、基于相對(duì)矩的分類、基于小波的分類、基于人類視覺系統(tǒng)(HVS)分類、基于模糊分類、原形的分類、自適應(yīng)碼本簇化的分類、向量量化的分類?！锼阉鞣ǎ浩ヅ渌阉骱臅r(shí)最長(zhǎng)

常用的加速搜索方法有，局部搜索法、提取特征追蹤法、基于方差搜索法等分形圖像壓縮的改進(jìn)方法

3、提高解碼速度

常用的加速方法有：金字塔式解碼器、去均值解碼算法、非迭代算法、BCC和ICC算法。

4．分形與其他工具相結(jié)合的圖像壓縮新方法

常用的混合編碼方案有：與小波變換結(jié)合編碼、與DCT變換結(jié)合編碼、與加權(quán)有限自動(dòng)機(jī)結(jié)合編碼、與向量量化結(jié)合編碼、與遺傳算法結(jié)合編碼、與FFT算法結(jié)合編碼、與非線性模型結(jié)合編碼、與算術(shù)結(jié)合編碼。

分形圖像編碼的發(fā)展趨勢(shì)

分形圖像壓縮方法的優(yōu)勢(shì)和巨大潛力:

★自然界中存在大量的自相似或自仿射的幾何形狀?！锓中螆D像壓縮能獲得相當(dāng)高的壓縮比和很好的壓縮效果。

★分形解碼時(shí)能放大到任意大的尺寸，且保持精細(xì)的結(jié)構(gòu)。

★在高壓縮比的情況下，分形圖像壓縮自動(dòng)編碼能有很高的信噪比和很好的視覺效果，這是其他方法不能相比的。

分形圖像編碼的發(fā)展趨勢(shì)1)進(jìn)一步降低分形編碼的計(jì)算復(fù)雜度。2)視頻圖像的分形編碼。3)極低碼率視頻信號(hào)的分形編碼及圖像質(zhì)量的改善。4)分形視