第5章分形圖像編碼5.1基本理論5.2分形圖像壓縮編碼的研究發(fā)展5.3一種幾何形狀比例可變的分形圖像壓縮編碼方法5.4一種基于局部極大模和分形的混合編碼方法

5.1基本理論

1.迭代函數(shù)系統(tǒng)(IFS，IteratedFunctionSystem)

定義1設(shè)(X，d)是完備度量空間，d(,)是X中的度量，w：X→X是基本空間(X，d)上的一個(gè)映射，如果存在一個(gè)正的常數(shù)c<1，使

d(w(x)，w(y))≤c·d(x，y) (5-1)

則稱w為(X，d)上的壓縮映射，c稱為壓縮因子。

這里w：X→X是基本空間(X，d)的一個(gè)壓縮映射，包括在X的子集一個(gè)壓縮映射。這個(gè)式為：

定義2完備的度量空間(X，d)以及n個(gè)壓縮映射w：X→X(其壓縮因子分別為c1，c2，…，cn)一起，組成一個(gè)迭代函數(shù)，簡(jiǎn)稱IFS，記作{X：w1，w2，…，wn}，c=max(c1，c2，…，cn)稱為IFS的壓縮因子，考慮(T(x)，h)上有n個(gè)壓縮映射{wi：T(x)→T(x)，i=1，2，…，n}，定義一個(gè)新的映射W：T(X)→T(x)，即

則W是壓縮映射，且壓縮因子c=max(c1，c2，…，cn)，即(5-3)(5-2)

定理1(壓縮映射的不動(dòng)點(diǎn)定理)設(shè){X：w1，w2，…，wn}是(X，d)上的IFS，則

(1)由下式定義的變換W：T(X)→T(X)，即

是完備度量空間(T(x)，h)上的壓縮映射，其壓縮因子也是c，即

h(W(A)，W(B))≤c·h(A，B) (5-4)

(2)壓縮變換W存在唯一的不動(dòng)點(diǎn)

∈T(X)，滿足(5-5)而且不動(dòng)點(diǎn)可以通過(guò)迭代而得到，即

其中，W0(B)=W(B)，Wn(B)=W(Wn－1(B))。

在IFS中也稱為吸引子。在迭代函數(shù)(IFS)中，要求映射wi(i=1，2，…，w)是壓縮的，通常采用仿射變換。在二維情況下，這種映射成為(5-7)(5-6)其中，ai、bi、ci、di、ei和fi是實(shí)數(shù)，定義域?yàn)槎S的。對(duì)于三維情況(圖像為灰度圖)，這種仿射變換wi成為

其中，a1，1，i、a1，2，i、a1，3，i、a2，1，i、a2，2，i、a2，3，i、a3，1，i、a3，2，i、a3，3，i、b1，i、b2，i和b3，i是實(shí)數(shù)，I(x，y)表示在位置(x，y)點(diǎn)的灰度值。對(duì)于圖像來(lái)說(shuō)，分形編碼是由分形的參數(shù)構(gòu)成的，其中有n個(gè)wi變換的參數(shù)。這些變換的線性部分是壓縮的，這些分形變換就是壓縮的。(5-8)例如一個(gè)二維的IFS由如下三個(gè)仿射變換組成：顯然，這三個(gè)變換都是壓縮的，每次迭代后的新的圖形都是縮小的，初始圖的迭代極限將為一個(gè)點(diǎn)，所以，對(duì)于無(wú)論怎樣的初始圖形，反復(fù)迭代后將得到同樣的極限圖形，即吸引子。吸引子只取決于仿射變換W，而與初始圖形無(wú)關(guān)。

一般地，完全由一組仿射變換W迭代出圖像，與初始圖像是相互獨(dú)立的。因此，給出的完全表示和仿射變換W的參數(shù)就是圖像的編碼。這些由圖5.1可以看出。圖5.1三個(gè)變換對(duì)蘋(píng)果和任意形狀的作用

2.拼貼定理(CollageTheorem)

一個(gè)IFS就是一組壓縮映射，令 ，由不動(dòng)點(diǎn)定理，它確定一個(gè)唯一的吸引子。由于具有唯一性，因此它完全由W所確定?，F(xiàn)在提出它的逆問(wèn)題，假設(shè)我們給定某個(gè)集L，能否找到一個(gè)IFS，使它的吸引子恰為L(zhǎng)？對(duì)此，到目前證明是非常困難的。

有一些(數(shù)學(xué))研究結(jié)果表明：用傅立葉變換、小波變換、矩陣方法、混沌最優(yōu)、遺傳算法、小波變換與矩陣方法、模糊集等其他工具找到這個(gè)逆問(wèn)題的精確數(shù)學(xué)解，到目前為止是不可能的。壓縮映射的不動(dòng)點(diǎn)定理告訴我們，不動(dòng)點(diǎn)A是從復(fù)制它的自身的變換W(A)構(gòu)造出的，所以我們?nèi)〗o定的集L，對(duì)它壓縮變換，然后把它們粘貼在一起以便重構(gòu)L。不動(dòng)點(diǎn)的唯一性是重要的，因?yàn)榧俣ńo出L而找到W(或者假定給出W，我們找到集L)使L=W(L)，則一定有L=A，即L就是W的吸引子。但是拼貼定理提供了解決逆問(wèn)題的基本解，即使我們拼貼得不能使之精確地符合要求，但在原始集L和粘貼后的“拼貼”W(L)之間能較好地符合，吸引子A將十分接近于L。

定理2(拼貼定理CollageTheorem)設(shè)(X，d)是完備的度量空間，給定集合L∈T(X)和數(shù)ε>0，如能選到一個(gè)IFS{X：w1，w2，…，wn；c}(0≤c<1)使

則

其中，h為豪斯多夫距離，而是該IFS的吸引子。(5-9)(5-10)由拼貼定理可知，為了使逼近L，必須使 足夠精確地逼近L。因此，盡可能地接近L，才能更好地逼近L。

根據(jù)wi，我們有

因此，L劃分Li，使 ，以至Li滿足仿射變換wi得到

Li=wi(L)(5-11)如果h(L，W(L))為eE，即稱之為編碼誤差或拼貼誤差， 用eD表示，稱之為解碼誤差，則根據(jù)拼貼定理，得到

此式根據(jù)編碼誤差給出了解碼誤差的上限值。(5-12)

3.(帶映射)局部迭代函數(shù)系統(tǒng)(LIFS)

現(xiàn)在怎樣對(duì)現(xiàn)實(shí)生活中的圖像(例如圖5.2(a)所示的少女Lena像的原始圖像)用分形原理進(jìn)行壓縮呢？雖然沒(méi)有整體與局部的自相似性，但經(jīng)驗(yàn)顯示，現(xiàn)實(shí)生活中的圖像卻存在局部之間的自相似性，如圖5.2(b)所示，從Lena像上取出的一些部分具有不同比例的自相似性：她肩上一部分與其重疊的一個(gè)小部分幾乎是相同的，鏡子里帽子的像的一部分與她的帽子的一部分是相似的?？梢?jiàn)局部自相似與圖5.2表示的自相似的不同之處在于現(xiàn)在的圖像是由本身的許多“部分”在適當(dāng)變換下復(fù)制構(gòu)成的，這些“部分”并不是它們自身在仿射變換下的恒等復(fù)制品，而是有誤差的，這樣就構(gòu)成了局部迭代函數(shù)系統(tǒng)，它完全是IFS方法的推廣，即每個(gè)變換wi的定義域僅為X的一部分Di變換。圖5.2Lena圖像及某些相似的“部分”

定義3設(shè)(X，d)是完備度量空間，Di

X(其中i=1，2，…，n)，局部迭代函數(shù)系統(tǒng)(LIFS，LocaliteratedFunctionSystem)就是下列壓縮映射集：

{ui：Di→X，(i=1，2，…，n)}

(5-13)

若圖像為灰度圖像，則f(x，y)稱為每個(gè)點(diǎn)(x，y)上的灰度值。一般情況下，把(x，y)區(qū)域劃分為許多塊，把(x，y)區(qū)域劃分為不可重疊的Range塊Ri和可以重疊的Domain塊Di，Domain塊的邊長(zhǎng)都大于Range塊。仿射變換wi作用于Di上，逼近于Ri上的灰度值而得到近似的wi(f)，它們之間有如下的關(guān)系：∩

如圖5.3所示。(5-14)圖5.3局部仿射變換示意圖 5.2分形圖像壓縮編碼的研究發(fā)展

1.基本方法

在1989年和1990年之間，Jacquin提出了全自動(dòng)的分形圖像壓縮方法。該方法以局部的仿射變換代替全局的仿射變換。仿射變換以下式表示：

而(5-15)(5-16)每一Ri均為一正方形式，而x，y的原點(diǎn)是Domain塊的中心點(diǎn)，a=0.5且pi，0<1。從上式可以看出，帶有灰度的圖像包含兩種變換：一種是在R2上的壓縮變換wi，i=1，2，…，n，它將圖像劃分的Domain塊變換到覆蓋整個(gè)圖像的Range塊；另一種是在R+上的灰度變換，它將圖像灰度函數(shù)f(x，y)通過(guò)線性變換與一些相應(yīng)Range塊的灰度函數(shù)匹配，求最佳pi，0、bi和ci，如圖5.4所示。圖5.4

Range塊劃分及其尋找最佳匹配的Domain具體步驟如下：

(1)將一幅2N×2N圖像A分割為互不重疊的Range塊Ri，大小為2R×2R。對(duì)每個(gè)Ri搜索最佳Dj。將圖像A分割為可以重疊的Domain塊Dj，大小為2R+1×2R+1，且Domain塊的個(gè)數(shù)為(2N－2R+1+1)2。

(2)搜索與其自相似的Domain塊Dj，作平均抽樣、反射-旋轉(zhuǎn)操作。每個(gè)Dj都有八種反射-旋轉(zhuǎn)情況，如圖5.5所示。通過(guò)平均抽樣后Domain塊與Range塊有相同的尺寸。圖5.5八種反射-旋轉(zhuǎn)示意圖

(3)如果縮小和旋轉(zhuǎn)后的Domain塊和Range塊中各像素的灰度值分別為a1，a2，…，am和b1，b2，…，bm，m=2R，則采用最小二乘法求pi，0和pi，1。

要使dp最小，應(yīng)改變pi，0和pi，1，使

，得(5-17)

且當(dāng) 時(shí)，pi，0=0。

此時(shí)，有(5-18)

(4)對(duì)每一個(gè)Range塊Ri，改變Domain塊方位和旋轉(zhuǎn)情況，找到一個(gè)最優(yōu)匹配映射Domain塊Dj，使得dp最小，若pi，0>1，則放棄且繼續(xù)搜索，否則記錄Dj的方位、旋轉(zhuǎn)、pi，0和pi，1。

(5)對(duì)所有Range塊都尋找其對(duì)應(yīng)的最佳的Domain塊，使圖像A上的每一Range塊Ri，都用其Domain塊來(lái)覆蓋，就完成了一整幅圖像的編碼。

圖5.6表示對(duì)一個(gè)512×512的Lena圖像進(jìn)行解碼迭代的過(guò)程，經(jīng)過(guò)8次迭代，完全可達(dá)到不動(dòng)點(diǎn)，即可認(rèn)為分形編碼的恢復(fù)圖像。圖5.6

512×512的Lena圖像分形解碼過(guò)程分別為0、1、2、3、4、8次迭代

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

1991年，簡(jiǎn)庫(kù)恩和弗歇爾等提出了改進(jìn)的仿射變換為

在一般情況下，該法與Jacquin提出的方法相同，只是增加了兩個(gè)映射參數(shù)di和ei。用D為Domain塊在子塊范圍內(nèi)搜索來(lái)確定,即di、ei確定；a1，1，i、a1，2，i、a2，1，i和a2，2，i與基本方法的參數(shù)相同，表示幾何收縮映射和八種反射-旋轉(zhuǎn)操作。該法將Domain塊縮小成與Range塊相同的尺寸，用(5-19)最小二乘法逼近Range塊求得pi，0、pi，1、di和ei，根據(jù)最佳匹配原理，尋找最佳匹配的Domain塊的方位、旋轉(zhuǎn)、pi，0、pi，1、di和ei。采用此方法對(duì)標(biāo)準(zhǔn)的512×512Lena圖像進(jìn)行編碼，當(dāng)壓縮比為0.5bpp時(shí)，峰值信噪比為30.8dB。

1992年，Monro和Dudbridge提出把圖像分割成許多小方塊子圖且每塊子圖單獨(dú)采用IFS，但是整幅圖像的IFS不能建立，這相當(dāng)于局部的IFS，對(duì)于子圖的Domain塊是預(yù)先決定的且又包含Range塊。

Fisher、Monro和Dudbridge等人研究了Range塊的劃分方法，如自適應(yīng)四叉樹(shù)法、自適應(yīng)HV分塊法和自適應(yīng)三角形分塊法等，并且比較了它們的壓縮效果。實(shí)驗(yàn)結(jié)果表明：自適應(yīng)HV分塊法比自適應(yīng)四叉樹(shù)法的壓縮效果要好，但該方法比較復(fù)雜；自適應(yīng)三角形分塊法的壓縮效果最好，但也是最復(fù)雜的方法，是目前改進(jìn)分形編碼的研究方向之一。

1993年，GharaviAlkhansaric和Huang將Jacquin方法拓寬，用一組固定基塊(FBB，F(xiàn)ixedBasisBlock)和一組與固定基塊無(wú)關(guān)、與圖像有關(guān)的基塊(IDBB，Image-DependedntBasisBlock)的線性組合來(lái)逼近Range塊。其中，F(xiàn)BB由設(shè)計(jì)者選定，是與圖像無(wú)關(guān)的基塊集，彼此相互正交；IDBB之間彼此近似正交，這類基塊要通過(guò)多種運(yùn)算從圖像中求出。這種方法中的FBB和IDBB的線性組合的系數(shù)較多，而且必須記錄這些系數(shù)。采用這種方法對(duì)標(biāo)準(zhǔn)的512×512Lena圖像進(jìn)行編碼，其壓縮比為0.53bpp時(shí)峰值信噪比為32.0dB。

Thomas和Deravi在Jacquin方法中使用相關(guān)自由的形狀，對(duì)標(biāo)準(zhǔn)的512×512Lena圖像進(jìn)行編碼，獲得壓縮比為0.30bpp時(shí)峰值信噪比為27.7dB。雖然壓縮效果得到了提高，但恢復(fù)的圖像效果不佳。

簡(jiǎn)庫(kù)恩和弗歇爾在分形圖像編碼中，引入不迭代解碼算法，即自適應(yīng)碼本聚類(AdaptiveCodebookClustering)方法,可將編碼速度提高許多，但算法復(fù)雜，對(duì)標(biāo)準(zhǔn)的512×512Lena圖像編碼在0.5bpp上可獲得峰值信噪比為32.1dB。

Vines和Hayes將搜索區(qū)域限定為離被編碼的Range塊最近的256個(gè)Domain塊，采用多級(jí)分塊法，對(duì)512×512Lena圖像編碼，可獲得壓縮比為0.47bpp峰值信噪比為31.5dB。

1993年之前，大部分發(fā)表的分形編碼論文主要集中在分形變換上。為了產(chǎn)生非常有效的算法，大部分專家將注意力集中于分形編碼用熵編碼和如何對(duì)分形變換參數(shù)用熵編碼來(lái)建立最佳模型。

1994年，Barthel等人提出以分形為主的DCT補(bǔ)償編碼混合方法，該法優(yōu)于單純的分形編碼方法。由于DCT本身具有較快的編碼速度，加上分形本身具有高的壓縮比，可以通過(guò)調(diào)節(jié)四叉樹(shù)法分割閾值和DCT量化得到比較好的綜合效果。此方法雖然沒(méi)有單純DCT法快，但是比單純的分形編碼方法要快得多。此方法對(duì)512×512Lena圖像編碼在壓縮比為0.35bpp時(shí)可獲得峰值信噪比為35dB。

Gharavi-Alkhansarico和Huang提出了一般圖像分塊編碼方法，即將分塊變換、矢量量化和基于分形編碼方法聯(lián)合起來(lái)。利用這種方法，圖像中的每一個(gè)Range塊都采用一個(gè)或多個(gè)塊的線性組合來(lái)逼近，而這些塊是從盡可能大的塊庫(kù)中選取的，塊庫(kù)中的塊不一定正交。在視頻編碼情況下，DPCM的塊預(yù)測(cè)方法和與塊運(yùn)動(dòng)補(bǔ)償法類似的自適應(yīng)塊預(yù)測(cè)方法，也是此算法的特例。他們提出，分形圖像解碼器的迭代性能是與編碼器非因果有關(guān)的，采用一個(gè)因果的編碼器導(dǎo)致一個(gè)非迭代的解碼器，這個(gè)解碼器只需要一次迭代就收斂。

1994年和1995年，Rinaldo和Calvagon最早提出了基于小波變換分形圖像壓縮方法，Davia、Walle、Krapnik和Simon等人后續(xù)借助小波變換開(kāi)展了一些分形圖像編碼方法的研究。一種方法是知道Range塊的均值和樹(shù)變換參數(shù)，在解碼時(shí)用低頻系數(shù)預(yù)測(cè)高頻系數(shù)。另一種方法是結(jié)合零樹(shù)編碼、尺度編碼和借助各種最佳方法的技巧與分形編碼的混合編碼方法。利用小波域的分形編碼，可得到高質(zhì)量、高壓縮比的結(jié)果，對(duì)512×512Lena圖像編碼，在壓縮比為0.26bpp和0.08bpp時(shí)分別得到了32.78dB和27.5dB的峰值信噪比。

1996年，Saupe提出了最佳Domain塊在Range塊最鄰近區(qū)域的特征向量里的尋找范圍。實(shí)驗(yàn)結(jié)果表明：此方法在相同的壓縮比情況下，不僅沒(méi)有使峰值信噪比下降，還略有提高，而且節(jié)省了大量時(shí)間。對(duì)512×512Lena圖像編碼在壓縮比為0.931bpp時(shí)，峰值信噪比為36.27dB，且時(shí)間花費(fèi)了1分10秒，與傳統(tǒng)分形編碼方法對(duì)比，速度提高了6.6倍。

1997年，Thao對(duì)Domain塊搜索區(qū)域限定方法進(jìn)行了改進(jìn)，根據(jù)統(tǒng)計(jì)Range塊最匹配Domain塊的規(guī)律，在距Range塊最近的81個(gè)Domain塊中尋找最佳匹配塊。雖然解碼圖像略有下降，但編碼速度大大地提高了，用稍微犧牲一點(diǎn)峰值信噪比值的代價(jià)，換取了編碼速度的提高。

1997年，Au和Liou等提出了基于DCT變換的分形編碼方法。為了減小分形編碼的復(fù)雜度，采用DCT變換系數(shù)求解出最優(yōu)壓縮因子和亮度差值。根據(jù)DCT變換的特點(diǎn)，減小分形編碼的計(jì)算量，采用少量DCT變換的系數(shù)參與仿射變換。實(shí)驗(yàn)結(jié)果表明：在相同條件下，此方法只用視覺(jué)效果的稍微下降就可以換來(lái)分形編碼的大量計(jì)算減少。

1998年，Hartenstein和Saup提出了在分形編碼過(guò)程中區(qū)域合并增長(zhǎng)方法。根據(jù)拼貼誤差大小、劃分邊界Euclidean長(zhǎng)度大小，來(lái)決定區(qū)域合并大小。初步測(cè)試表明，編碼代價(jià)估計(jì)器對(duì)一系列分形編碼非常重要。

1999年，Saup和Raouf等提出在分形編碼中基于最佳的壓縮比-失真度值的分層分割法，來(lái)解決分形編碼的bit分配問(wèn)題。此方法對(duì)512×512Lena圖像編碼，在壓縮比為0.7bpp和0.26bpp時(shí)，峰值信噪比分別可達(dá)到35.17dB和32.13dB。

2001年，Tong和Pi提出一種自適應(yīng)搜索方法，減小了分形編碼計(jì)算的復(fù)雜度。此方法采用改進(jìn)的仿射變換，排除大量不適合的Domain塊，對(duì)512×512的Lena圖像編碼在壓縮比為0.60bpp時(shí)，采用四叉樹(shù)法分塊，使用奔騰II233MHz計(jì)算機(jī)只需要125秒就可獲得峰值信噪比為33.37dB。

3.分形圖像編碼存在的問(wèn)題

目前，分形圖像編碼方法仍處在研究階段，離實(shí)用化還有相當(dāng)大的距離，分形圖像編碼方法還有許多問(wèn)題有待解決，其中主要問(wèn)題之一就是：給定一幅圖像f，如何找到映射W，使它的吸引子 。這是尚未解決的問(wèn)題，因此分形編碼只能應(yīng)用于有損壓縮。它的缺陷是編碼的速度。分形圖像編碼就是用仿射變換來(lái)消除圖像中不同尺度的塊與塊之間的自相似性冗余的，而編碼所花費(fèi)的時(shí)間主要是最佳匹配Domain塊的搜索時(shí)間。雖然許多文獻(xiàn)提出了改進(jìn)搜索方法，也提高了編碼效率，但是如何找到最佳匹配的Domain塊搜索策略，至今仍未解決，使得搜索具有一定的盲目性。另一方面，圖像局部的自相似性的區(qū)域如何劃分，至今沒(méi)有依據(jù)。盲目的劃分是導(dǎo)致搜索速度下降和壓縮比減小的重要原因之一。

5.3一種幾何形狀比例可變的

1.幾何形狀比例可變的思想

在二維二值圖形中，IFS系統(tǒng)的a都是小于1的實(shí)數(shù)，如康托集， ，楓葉的仿射變換a<1的實(shí)數(shù)，壓縮比可以達(dá)到成千上萬(wàn)倍，比目前現(xiàn)有的任何圖像壓縮方法的壓縮比高得多。我們可以借鑒此思想，應(yīng)用到自然的圖像壓縮中。在分形圖像壓縮中，局部仿射變換包括兩個(gè)部分：一個(gè)是平面仿射變換，在R2上的壓縮變換，由公式(5-14)表示，相當(dāng)于二維的IFS系統(tǒng)；另一個(gè)是灰度仿射變換，決定逼近圖像的程度。一般情況下，采用平面仿射變換的固定a=0.5,這給分形壓縮帶來(lái)了一定的局限性，必然會(huì)影響分形壓縮的效果。雖然平面仿射變換的系數(shù)a只決定Range塊與Domain塊面積比和Domain塊的旋轉(zhuǎn)和反射，但它的大小變化必然會(huì)影響灰度仿射變換的逼近程度。借用二維的IFS的思想，放寬a的要求，即把a(bǔ)變成可變化的，可提高分形壓縮效果。從圖5.2(b)可以明顯地看出，Lena圖像上取出的一些部分都具有自相似性，但它們的面積大小之比不是2∶1，說(shuō)明平面仿射變換的系數(shù)a可變的思想是可行的。我們從下面數(shù)據(jù)來(lái)分析：Lena圖像大小為256×256×8bit，Range塊分割為8×8像素的非重疊子圖，而Domain塊分成兩種情況，即一種為幾何形狀比例為2∶1，即16×16像素可重疊的方塊，另一種為幾何形狀比例為3∶2，即12×12像素可重疊的方塊，分別尋找子圖分形結(jié)構(gòu)。我們從中列舉一段子圖對(duì)應(yīng)不同Domain塊的情況，如表5.1所示。表5.1兩種分形幾何形狀比例Domain塊對(duì)應(yīng)Range塊的最佳匹配參數(shù)情況

Domain塊匹配的優(yōu)劣主要看測(cè)度的大小，即Domain塊逼近Range塊的程度，測(cè)度越大，逼近程度越差。從整個(gè)數(shù)據(jù)來(lái)看，最佳匹配12×12的Domain塊與子圖的相似性比最佳匹配16×16的Domain塊與子圖的相似性要好一些，但是同時(shí)還有一些16×16的Domain塊比12×12的Domain塊與Range塊的吻合程度好。顯然，幾何形狀比例值不同，也可改變Domain塊的位置、壓縮因子、偏差和旋轉(zhuǎn)值，必然影響Domain塊逼近Range塊的程度。因此，分形圖像壓縮必須考慮幾何形狀比例，幾何形狀比例越大，其恢復(fù)圖像的迭代過(guò)程收斂得越快。所以，必須根據(jù)情況，選擇合適的分形幾何形狀比例值。

2.分形幾何形狀比例值變換

一幅圖像的一個(gè)分形仿射變換表達(dá)公式如下：wi決定Domain塊Dj映射到Range塊Ri上的關(guān)系，包含兩者的位置、壓縮因子、偏差方向和幾何形狀比例。這里a不是0.5，而是小于1的實(shí)數(shù)，但是平面仿射變換把Domain塊映射成Range塊的大小并且映射的Range塊的像素有值，因此，a為有理數(shù)。為了便于平面仿射變換(即平均抽樣)計(jì)算，給出4種a的不同的值。計(jì)算原則為平均抽樣的像素灰度大小根據(jù)占有的原Domain塊的每個(gè)像素灰度乘以比例之和來(lái)縮小，而比例是根據(jù)平均抽樣的每個(gè)像素在Domain塊的占有位置和Domain塊的每個(gè)像素的面積大小得到的。因此，選用四種不同幾何形狀比例值和八種旋轉(zhuǎn)方向來(lái)擬合實(shí)際的a1，1，i、a1，2，i、a2，1，i和a2，2，i值。設(shè)Range塊和Domain塊大小分別為B×B和D×D，給出Domain塊的平均抽樣值變換如下(m'為表示變換值，m為Domain塊的灰度的實(shí)際大小)。

(1)當(dāng)D=2B時(shí)，Domain塊的平均抽樣值為：

(2)當(dāng)4D=7B時(shí)，最小Range塊為4×4，對(duì)應(yīng)最小的Domain塊為7×7，Domain塊的平均抽樣值為：

(3)當(dāng)2D=3B時(shí)，最小Range塊為2×2，對(duì)應(yīng)最小的Domain塊為3×3，Domain塊的平均抽樣值為：

(4)當(dāng)4D=5B時(shí)，最小Range塊為4×4，對(duì)應(yīng)最小的Domain塊為5×5，Domain塊的平均抽樣值為：以上(1)到(4)中所有變換式的選用條件是：Range塊大小必須為它們最小Range塊的整數(shù)倍。顯然，(1)到(4)中的幾何形狀比例變換要求最小的Range塊的大小為4×4。

3. 自適應(yīng)的四叉樹(shù)分形的多種幾何形狀比例編碼方法

考慮到分形圖像編碼的質(zhì)量和壓縮比，采用了幾何形狀比例與自適應(yīng)的四叉樹(shù)分形編碼。為了降低分形編碼時(shí)搜索的復(fù)雜度，搜索的范圍暫時(shí)定為Range塊附近區(qū)域的Domain塊。設(shè)幾何形狀比例為2∶1、7∶4、3∶2和5∶4，按大小排列，分為四檔。2Rmax、2Rmin分別為最大Range塊邊長(zhǎng)和最小Range塊邊長(zhǎng)。具體步驟如下：

(1)設(shè)定搜索范圍為W×W，允許匹配誤差為ε，把圖像A分割為不重疊的2Rmax×2Rmax的Range塊Ri，選用最大幾何形狀比例檔為2∶1，在Range塊周圍分割可以重疊的Domain塊。

(2)搜索Range塊Ri的最佳匹配映射，以Ri位置為起點(diǎn)，在W×W范圍內(nèi)尋找Ri相匹配的Domain塊。

(3)如果匹配的誤差小于ε，則記錄最佳匹配的參數(shù)，否則，轉(zhuǎn)至步驟(4)。

(4)如果分形幾何形狀比例不是最小檔，把幾何形狀比例值減小一檔，在Range塊周圍分割可以重疊的Domain塊，轉(zhuǎn)至步驟(2)，否則轉(zhuǎn)至步驟(5)。

(5)如果誤差大于ε，則把Range塊Ri一分為四，幾何形狀比例升為最大檔，在新的Range塊R'i周圍分割可以重疊的Domain塊，轉(zhuǎn)至步驟(2)。

(6)重復(fù)步驟(2)、(4)和(5)直到所有大小的Range塊與相適應(yīng)的Domain塊之間的匹配誤差小于ε為止。

4.實(shí)驗(yàn)結(jié)果與結(jié)論

依照上述方法，我們做了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)對(duì)象是256×256×8bit的Lena灰度圖像，計(jì)算過(guò)程在奔騰Ⅲ200微機(jī)上完成。

1)分形單獨(dú)幾何形狀比例四叉樹(shù)編碼

編碼時(shí)，首先設(shè)Lena灰度圖像的Domain塊與Range塊之間匹配的允許誤差為7。2Rmax=16和2Rmin=4分別為最大Range塊邊長(zhǎng)和最小Range塊邊長(zhǎng)。在Range塊的δ鄰域?qū)ふ?，得到原始圖像的編碼。分別應(yīng)用D=2B、4D=7B、2D=3B、4D=5B四種固定分形幾何形狀比例進(jìn)行四叉樹(shù)編碼，結(jié)果如表5.2所示。

由表5.2可知，隨著幾何形狀比例值的下降，峰值信噪比(PSRN)提高，壓縮比增大，但是圖像的恢復(fù)時(shí)間增長(zhǎng)，圖像的主觀質(zhì)量略有下降。表5.2分形單獨(dú)幾何形狀比例四叉樹(shù)編碼結(jié)果

2)多種分形幾何形狀比例四叉樹(shù)編碼

用本小節(jié)第2部分中的四種分形幾何形狀比例按本節(jié)第3部分中所述的步驟去做，對(duì)Lena圖像進(jìn)行編碼，得到的結(jié)果為壓縮比是0.376bpp，PSRN為33.4dB，時(shí)間為564s。雖然壓縮比比幾何形狀比例小的略有下降，但是，此方法的匹配精度高，恢復(fù)圖像時(shí)間短。這五種情況如圖5.7所示。

分開(kāi)編碼理論作為一種新的分形圖像壓縮方法，它的獨(dú)特思想豐富了圖像壓縮編碼的研究?jī)?nèi)容，但是還有待進(jìn)一步完善，如怎樣在保證恢復(fù)圖像質(zhì)量的同時(shí)提高其壓縮比，這都需要在今后的工作中研究探索。圖5.7幾種分形圖像壓縮編碼

5.4一種基于局部極大模和

分形的混合編碼方法

1.局部極大模方法

給出一幅圖信號(hào)f(x，y)∈R，若要求圖像小波變換局部模極大值，則首先必須知道二維的小波基，一般二進(jìn)制的二維小波基是3個(gè)，而這里小波基是2個(gè)，并且是滿足圖像邊緣檢測(cè)關(guān)系的，它的形式為(5-20)式中，ψ(x)為二次樣條小波基，ξ(y)為KroneckerDelta函數(shù)。據(jù)此可對(duì)應(yīng)地得出二維離散小波變換算術(shù)式：

逆變換算法為：(5-21)(5-22)

K、L、H和G參數(shù)如表5.3所示。表5.3

K、L、H和G濾波器參數(shù)在尺度2j時(shí)，二維小波變換的模和水平的夾角分別為

由于M2jf(x，y)局部模極