利用代間差分遺傳算法優(yōu)化分形圖像編碼速度

摘要：研究了分形編碼過程中值域塊與定義域塊相似程度的分布特點(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)化的壓縮過程。1990年，Janquin利用局部仿射變換代替全局仿射變換而提出了一種全自動(dòng)的分形圖像壓縮方法，使這種圖像壓縮技術(shù)向?qū)嵱没~進(jìn)一了步。Janquin方式雖然解決了Barnsley的子圖分割問題，但是搜索最佳匹配塊的計(jì)算量是十分可觀的。為了減小計(jì)算量，從90年代起又有許多改進(jìn)方法被提出，例如分類搜索法、四叉樹搜索法等。這些方法雖然在一定程度上節(jié)約了搜索時(shí)間，但仍需進(jìn)一步減小編碼所需要的時(shí)間。 遺傳算法是人類在自然進(jìn)化的啟發(fā)下發(fā)展的一種隨機(jī)搜索算法，在大計(jì)算量面前具有快速自尋優(yōu)的能力。目前人們已經(jīng)開始利用遺傳算法對(duì)分形編碼的編碼速度進(jìn)行優(yōu)化。本文為了進(jìn)一步提高分形壓縮的編碼速度，深入研究了每個(gè)值域塊、所有定義域塊與其相似程度的分布特點(diǎn)，推導(dǎo)了適用于分形編碼的代間差分遺傳算法；然后利用代間差分遺傳算法優(yōu)化分形編碼。實(shí)驗(yàn)表明代間差分遺傳算法較變通遺傳算法具有更快的收斂速度。 1 分形圖像壓縮的基本原理 分形理論是現(xiàn)代非線性科學(xué)中一門非?；钴S且應(yīng)用十分廣泛的學(xué)科，特別隨著計(jì)算機(jī)技術(shù)的發(fā)展，分形思想和方法在模式識(shí)別、自然圖像的模擬、信號(hào)處理等各個(gè)領(lǐng)域都取得了巨大的成功。 分形編碼的主要過程如下：首先將圖像I分割成互不相交的值域塊{Ri}，對(duì)每個(gè)值域塊，在整個(gè)圖像范圍尋找其在壓縮、仿射變換下的最佳匹配定義域塊Di,記錄下該定義域塊和所采用的變換，完成了一個(gè)子塊的編碼；對(duì)于所有值域塊{Ri}重復(fù)上述過程分別尋找各自的最優(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?？梢娫撈ヅ溥^程的計(jì)算量非常大。 2 代間差分遺傳算法的基本思想 遺傳算法是一種具有內(nèi)在并行性的優(yōu)化算法，本文試圖利用遺傳算法的優(yōu)化能力改善編碼過程。同時(shí)針對(duì)分形編碼過程的特點(diǎn)，為了提高算法的收斂速度，對(duì)遺傳算法進(jìn)行了改進(jìn)，提出了帶有代間差分雜交算子的遺傳算法。 遺傳算法中的雜交算子是一類非常重要的算子，雜交算子的性以也直接影響整個(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è)體的差來構(gòu)成新的雜交算子，以產(chǎn)生新的個(gè)體，該新個(gè)體將以更高的概率向量?jī)?yōu)解靠近。本文在不產(chǎn)生混淆的情況下，把采用代間差分雜交算子的遺傳算法稱為代間差分遺傳算法。 3 基于代間差分遺傳算法的快速分形壓縮算法 3．1 分形編碼中值域塊與定義域塊相似度分布特點(diǎn) 筆者經(jīng)過大量的研究發(fā)現(xiàn)，在分形編碼的過程中某一值域塊與所有定義域塊的相似程度分布具有以下特點(diǎn)： （1） 該分布是一個(gè)多極值的函數(shù)，因此尋找某一值域塊的最佳匹配定義域塊的過程實(shí)際上是求解一個(gè)多極值函數(shù)的最大值問題； （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)化分形編碼過程。下面構(gòu)造可用于分形編碼過程的代間差分雜交算子。 本文要進(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)存指針分別用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)行了說明。實(shí)際上，代間差分遺傳算法同樣適用于其他改進(jìn)的分形編碼算法，例如四叉樹搜索法等。 本文中兩種算法采用的參數(shù)如下：種群數(shù)目為50，雜交概率為0.8，遺傳概率為0.1，變異概率為0.1。 代間差分雜交算子的參數(shù)為： 用于其他改進(jìn)的分形編碼算法，例如四叉樹搜索法等。 本文中兩種算法采用的參數(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ì)編碼過程進(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大，說明對(duì)分形編碼進(jìn)行優(yōu)化計(jì)算時(shí)，前者比后者具有更高的收斂速度。