分形圖像壓縮技術(shù)是利用數(shù)字圖像本身固有的自相似性,，在分形理論的指導(dǎo)下,，把圖像數(shù)據(jù)轉(zhuǎn)變?yōu)橄嚓P(guān)的分形參數(shù),，從而達(dá)到對(duì)數(shù)據(jù)進(jìn)行壓縮的目的,。在一些情況下分形壓縮可以達(dá)到非常高的壓縮比，因此這是一種極具發(fā)展?jié)摿Φ膱D像壓縮技術(shù),。
　　分形圖像壓縮的概念首先由Barnsley提出,，但是Barnsely基于IFS的分形壓縮方法在實(shí)施時(shí)需要人機(jī)交互，無(wú)法實(shí)現(xiàn)自動(dòng)化的壓縮過(guò)程,。1990年,，Janquin利用局部仿射變換代替全局仿射變換而提出了一種全自動(dòng)的分形圖像壓縮方法，使這種圖像壓縮技術(shù)向?qū)嵱没~進(jìn)了一步^[1],。Janquin方法雖然解決了Barnsley的子圖分割問(wèn)題,，但是搜索最佳匹配塊的計(jì)算量是十分可觀的。為了減小計(jì)算量,，從90年代起又有許多改進(jìn)方法被提出,，例如分類搜索法,、四叉樹(shù)搜索法等,。這些方法雖然在一定程度上節(jié)約了搜索時(shí)間，但仍需進(jìn)一步減小編碼所需要的時(shí)間[2～3],。
　　遺傳算法是人類在自然進(jìn)化的啟發(fā)下發(fā)展的一種隨機(jī)搜索算法,，在大計(jì)算量面前具有快速自尋優(yōu)的能力。目前人們已經(jīng)開(kāi)始利用遺傳算法對(duì)分形編碼的編碼速度進(jìn)行優(yōu)化^[4～5],。本文為了進(jìn)一步提高分形壓縮的編碼速度,，深入研究了每個(gè)值域塊、所有定義域塊與其相似程度的分布特點(diǎn)，推導(dǎo)了適用于分形編碼的代間差分遺傳算法,；然后利用代間差分遺傳算法優(yōu)化分形編碼,。實(shí)驗(yàn)表明代間差分遺傳算法較普通遺傳算法具有更快的收斂速度。
1 分形圖像壓縮的基本原理
　　分形理論是現(xiàn)代非線性科學(xué)中一門(mén)非?；钴S且應(yīng)用十分廣泛的學(xué)科,，特別隨著計(jì)算機(jī)技術(shù)的發(fā)展，分形思想和方法在模式識(shí)別,、自然圖像的模擬,、信號(hào)處理等各個(gè)領(lǐng)域都取得了巨大的成功。
　　分形編碼的主要過(guò)程如下：首先將圖像I分割成互不相交的值域塊{Ri},，對(duì)每個(gè)值域塊,，在整個(gè)圖像范圍尋找其在壓縮、仿射變換下的最佳匹配定義域塊Di,，記錄下該定義域塊和所采用的變換,，完成了一個(gè)子塊的編碼；對(duì)于所有值域塊{Ri}重復(fù)上述過(guò)程分別尋找各自的最優(yōu)匹配定義域塊,，即完成整幅圖像的編碼,。
　　在仿射變換下，定義域和值域的誤差可由下式確定：
　　
　　所謂某個(gè)值域塊R_i的最優(yōu)匹配定義域塊就是：在f映射下,，定義域塊和值域塊使(1)式最小,。利用Janquin方法進(jìn)行編碼，為了找到具有最小誤差Err的定義域塊,，即最優(yōu)匹配定義域塊,，每一個(gè)值域塊R_i需要匹配的定義域塊數(shù)為(假設(shè)圖像、定義域塊以及值域塊都是正方形)：
　　Num＝(圖像大?。x域塊大?。?)²×仿射變換種數(shù)
　　例如，對(duì)于一個(gè)大小為256×256的圖像,，如果選取值域塊為16×16,，定義塊為32×32，則每個(gè)值域塊要搜索的定義域塊為50625,?？梢?jiàn)該匹配過(guò)程的計(jì)算量非常大。
2 代間差分遺傳算法的基本思想
　　遺傳算法是一種具有內(nèi)在并行性的優(yōu)化算法,，本文試圖利用遺傳算法的優(yōu)化能力改善編碼過(guò)程,。同時(shí)針對(duì)分形編碼過(guò)程的特點(diǎn)，為了提高算法的收斂速度,，對(duì)遺傳算法進(jìn)行了改進(jìn),，提出了帶有代間差分雜交算子" title="雜交算子">雜交算子的遺傳算法^[6],。
　　遺傳算法中的雜交算子是一類非常重要的算子，雜交算子的性能也直接影響整個(gè)算法的收斂速度,。本文提出的代間差分雜交算子其思想為：遺傳算法是根據(jù)自然界中生物進(jìn)化,、適者生存的思想而發(fā)展的一種優(yōu)化算法；隨著種群進(jìn)化代數(shù)的增加,，在選擇算子等的作用下,，種群的平均適應(yīng)值將以大概率增加。這樣有理由假定種群的適應(yīng)值將隨著進(jìn)化代數(shù)的增加而單調(diào)增加,，從相鄰兩代種群中隨機(jī)選擇一個(gè)個(gè)體,，則兩個(gè)個(gè)體的差以一定概率代表了種群適應(yīng)值增加的方向，也就是所希望的進(jìn)化方向,。因此可以利用相鄰兩代種群中個(gè)體的差來(lái)構(gòu)成新的雜交算子,，以產(chǎn)生新的個(gè)體，該新個(gè)體將以更高的概率向最優(yōu)解靠近,。
　　本文在不產(chǎn)生混淆的情況下,，把采用代間差分雜交算子的遺傳算法稱為代間差分遺傳算法。
3 基于代間差分遺傳算法的快速分形壓縮算法
3.1 分形編碼中值域塊與定義域塊相似度分布特點(diǎn)
　　筆者經(jīng)過(guò)大量的研究發(fā)現(xiàn),，在分形編碼的過(guò)程中某一值域塊與所有定義域塊的相似程度分布具有以下特點(diǎn)：
　　(1)該分布是一個(gè)多極值的函數(shù),，因此尋找某一值域塊的最佳匹配定義域塊的過(guò)程實(shí)際上是求解一個(gè)多極值函數(shù)的最大值問(wèn)題；
　　(2)分布函數(shù)的取值在每一個(gè)極值附近連續(xù)變化,，即在最大相似塊附近的定義域塊,，其與值域塊的相似度是逐漸變化的。
　　圖1是Lena圖像和Tree圖像中某一值域塊與所有定義域塊相似度分布的情況,，值域塊分8×8和16×16兩種情況隨機(jī)選取,，相似度由(2)式確定：
　　
　　其中，Err由(1)式確定,。
　　相似度的分布由圖1(b),、(c)和圖1(e)、(f)給出,，可以看到,，相似度的分布符合上述兩個(gè)特點(diǎn)。

3.2 構(gòu)造代間差分雜交算子
　　由于分形編碼中值域塊與定義域塊相似度分布具有以上特點(diǎn),，使得代間差分遺傳算法的思想在這里適用,，因此可以利用代間差分遺傳算法優(yōu)化分形編碼過(guò)程。下面構(gòu)造可用于分形編碼過(guò)程的代間差分雜交算子,。
　　本文要進(jìn)行搜索的空間由圖像定義域塊的全體構(gòu)成,，對(duì)于每個(gè)定義塊可以用左上角像素點(diǎn)的坐標(biāo)表示,，則對(duì)應(yīng)的遺傳算法中的一個(gè)個(gè)體可以表示為:x=(x,，y),。種群中個(gè)體的適應(yīng)度由(3)式確定。
　　代間差分雜交算子可以表示為：

　　即在新種群產(chǎn)生后,，又進(jìn)行如下操作：從新種群中隨機(jī)選擇一個(gè)個(gè)體,，如果該個(gè)體適應(yīng)度比x好，則保持不變,，否則用x代替該個(gè)體,。(4)式中α、λ的取值可以與(3)式相同也可以不同,，本文中取值相同,。
3.3 代間差分遺傳算法的實(shí)現(xiàn)
　　設(shè)種群的規(guī)模為N，則代間差分遺傳算法的基本結(jié)構(gòu)為：
　　{
　　分配三代進(jìn)化種群的內(nèi)存區(qū)域,其內(nèi)存指針?lè)謩e用p_t-1,，p_t,，p_t+1表示；
　　t=1; 隨機(jī)初始化種群p_t-1,，p_t,，p_t+1；
　　計(jì)算p_t-1,，p_t中個(gè)體的適應(yīng)值,；
　　while(不滿足終止條件)do
　　{
　　根據(jù)個(gè)體的適應(yīng)值及選擇策略，計(jì)算兩代種群p_t-1,，p_t內(nèi)個(gè)體的選擇概率p_i;
　　復(fù)制p_t中適應(yīng)值最好的個(gè)體到p_t+1中,；
　　while(p_t+1中的個(gè)體全部被更新)do
　　{
　　從p_t-1，p_t中隨機(jī)選擇一個(gè)個(gè)體,，按雜交概率用代間差分雜交算子產(chǎn)生新個(gè)體,；
　　按變異概率用變異算子作用新個(gè)體；
　　}
　　計(jì)算p_t+1中個(gè)體的適應(yīng)值,；
　　按(3)式計(jì)算x_i并計(jì)算x_i的適應(yīng)值,，從p_t+1中隨機(jī)選擇;
　　如果xi的適應(yīng)值比好，則把x_i復(fù)制到在p_t+1中的位置,；否則保持不變,；
　　pTmp=p_t-1;
　　p_t-1=p_t;
　　p_t=p_t+1;
　　p_t+1=pTmp;
　　t=t+1;
　　}
}
4 實(shí)驗(yàn)結(jié)果
　　為了驗(yàn)證代間差分遺傳算法在分形編碼中的有效性，利用常規(guī)遺傳算法和代間差分遺傳算法同時(shí)對(duì)Janquin編碼方法進(jìn)行優(yōu)化,，并比較優(yōu)化結(jié)果,。
　　需要特別指出的是，本文僅僅對(duì)Janquin編碼方法的優(yōu)化進(jìn)行了說(shuō)明,。實(shí)際上,，代間差分遺傳算法同樣適用于其他改進(jìn)的分形編碼算法，例如四叉樹(shù)搜索法等,。
　　本文中兩種算法采用的參數(shù)如下：種群數(shù)目為50,，雜交概率為0.8,，遺傳概率為0.1，變異概率為0.1,。
　　代間差分雜交算子的參數(shù)為：
　　α=1,，β=0.2,λ=0.8。
　　以256×256的灰度Lena圖像為例進(jìn)行實(shí)驗(yàn),，值域塊為8×8,，定義域塊為16×16。分別利用遺傳算法和代間差分遺傳算法對(duì)編碼過(guò)程進(jìn)行優(yōu)化,，然后利用相同的解碼算法迭代10次進(jìn)行解碼,，圖2中給出了部分解碼的結(jié)果。

　　其中(a)是Lena原圖,，(b)是直接利用Janquin編碼方法得到結(jié)果,。
　　在進(jìn)行實(shí)驗(yàn)時(shí)，觀察在相同的進(jìn)化代數(shù)的條件下,，解碼圖像的PSNR的變化情況,。由于遺傳算法是一種隨機(jī)優(yōu)化算法，所以在同一個(gè)進(jìn)化代數(shù)利用兩種優(yōu)化算法分別進(jìn)行10計(jì)算,，并計(jì)算解碼圖像的平均PSNR,，如表1所示。其中最后一欄表示利用Janquin方法解碼圖像的PSNR,。