摘要：研究了分形編碼過(guò)程中值域塊與定義域塊相似程度的分布特點(diǎn)，提出利用代間差分遺傳算法優(yōu)化其編碼速度。實(shí)驗(yàn)結(jié)果證明了該方法的有效性。關(guān)鍵詞：圖像壓縮 分形編碼 遺傳算法 分形圖像壓縮技術(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)一了步。Janquin方式雖然解決了Barnsley的子圖分割問(wèn)題，但是搜索最佳匹配塊的計(jì)算量是十分可觀的。為了減小計(jì)算量，從90年代起又有許多改進(jìn)方法被提出，例如分類(lèi)搜索法、四叉樹(shù)搜索法等。這些方法雖然在一定程度上節(jié)約了搜索時(shí)間，但仍需進(jìn)一步減小編碼所需要的時(shí)間。 遺傳算法是人類(lèi)在自然進(jìn)化的啟發(fā)下發(fā)展的一種隨機(jī)搜索算法，在大計(jì)算量面前具有快速自尋優(yōu)的能力。目前人們已經(jīng)開(kāi)始利用遺傳算法對(duì)分形編碼的編碼速度進(jìn)行優(yōu)化。本文為了進(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è)值域塊Ri的最優(yōu)匹配定義域就是：在f映射下，定義域塊和值域塊使（1）式最小。利用Janquin方法進(jìn)行編碼，為了找到具有最小誤差Err的定義域塊，即最優(yōu)匹配定義域塊，每一個(gè)值域塊Ri需要匹配的定義域塊數(shù)為（假設(shè)圖像、定義域塊以及值域塊都是正方形）： Num=(圖像大小-定義域塊大小+1)2%26;#215;仿射變換種數(shù) 例如，對(duì)于一個(gè)大小為256%26;#215;256的圖像，如果選取值域塊為16%26;#215;16，定義塊為32%26;#215;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)，提出了帶有代間差分雜交算子的遺傳算法。 遺傳算法中的雜交算子是一類(lèi)非常重要的算子，雜交算子的性以也直接影響整個(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è)體將以更高的概率向量?jī)?yōu)解靠近。本文在不產(chǎn)生混淆的情況下，把采用代間差分雜交算子的遺傳算法稱(chēng)為代間差分遺傳算法。 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ù)變化，即在最大相似塊附近的定義域塊，（5） 其與值域塊的相似度是逐漸變化的。 圖1是Lena圖像和Tree圖像中某一值域塊與所有定義域塊相似度分布的情況，值域塊分8%26;#215;8和16%26;#215;16兩種情況隨機(jī)選取，相似度由（2）式確定： ada=1/Err (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）式確定。 代間差分雜交算子可以表示為： 其中[%26;#183;]表示取整函數(shù)，α、β、λ為小于1的正常數(shù)。xnbest、xn-1best分別是第n代和n-1代中適應(yīng)度最好的個(gè)體。又按下式計(jì)算個(gè)體x： 即在新種群產(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)存匹配，其內(nèi)存指針?lè)謩e用pt-1,p+1表示； t=1;隨機(jī)初始化種群pt-1,pt,pt+1； 計(jì)算pt-1,pt中個(gè)體的適應(yīng)值；] while(不滿足終止條件)do { 根據(jù)個(gè)體的適應(yīng)值及選擇策略，計(jì)算丙代種群pt-1,pt內(nèi)個(gè)體的選擇概率pi; 復(fù)制pt中適應(yīng)值最好的個(gè)體到pt+1中； while(pt+1中的個(gè)體全部被更新)do { 從pt-1,pt中隨機(jī)選擇一個(gè)個(gè)體，按雜交概率用代間差分雜交算子產(chǎn)生新個(gè)體； 按變異概率用變異算子作用新個(gè)體； } 計(jì)算pt+1中個(gè)體的適應(yīng)值； 按（3）式計(jì)算xi并計(jì)算xi的適應(yīng)值，從Pi+1中隨機(jī)選擇x(t+1)l; 如果xi的適應(yīng)值比x(t+1)l好，則把xi復(fù)制到x(t+1)l在Pt+1中的位置；否則保持不變； pTmp=pt-1; pt-1=pt; pt=pTmp; t=t+1; } }4 實(shí)驗(yàn)結(jié)果 為了驗(yàn)證代間差分遺傳算法在分形編碼中的有效性，利用常規(guī)遺傳算法和代間差分遺傳算法同時(shí)對(duì)Janquin編碼方法進(jìn)行優(yōu)化，并比較優(yōu)化結(jié)果。 需要特別指出的是，本文僅僅對(duì)anquin編碼方法的優(yōu)化進(jìn)行了說(shuō)明。實(shí)際上，代間差分遺傳算法同樣適用于其他改進(jìn)的分形編碼算法，例如四叉樹(shù)搜索法等。 本文中兩種算法采用的參數(shù)如下：種群數(shù)目為50，雜交概率為0.8，遺傳概率為0.1，變異概率為0.1。 代間差分雜交算子的參數(shù)為： 用于其他改進(jìn)的分形編碼算法，例如四叉樹(shù)搜索法等。 本文中兩種算法采用的參數(shù)如下：種群數(shù)目為50，雜交概率為0.8，遺傳概率為0.1，變異概率為0.1。 代間差分雜交算子的參數(shù)為： α=1, β=0.2, λ=0.8。 以256%26;#215;256的灰度Lena圖像為例進(jìn)行實(shí)驗(yàn)，值域塊為8%26;#215;8，定義域塊為16%26;#215;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所示。其中最后一欄表示利用anquin方法解碼圖像的PSNR。 表1 實(shí)驗(yàn)結(jié)果 　4 6 12 16 20 J GA 22 23.5 25.4 26.1 26.4 28.2 IDGA 22.4 24 26.5 27 27.8 對(duì)表1進(jìn)行分析可以知道，由于代間差分遺傳算法充分利用了值域塊相似度的分布特點(diǎn)，在相同的進(jìn)化代數(shù)下，代間差分遺傳算法得到的PSNR比常規(guī)遺傳算法的PSNR大，說(shuō)明對(duì)分形編碼進(jìn)行優(yōu)化計(jì)算時(shí)，前者比后者具有更高的收斂速度。