基于固定碼本的分形圖像編碼算法

袁宗文 魯業(yè)頻 楊漢生

（巢湖學(xué)院機(jī)械與電子工程學(xué)院，安徽 巢湖 238000）

基于固定碼本的分形圖像編碼算法

袁宗文 魯業(yè)頻 楊漢生

（巢湖學(xué)院機(jī)械與電子工程學(xué)院，安徽 巢湖 238000）

傳統(tǒng)的分形圖像編碼根據(jù)圖像內(nèi)部的跨尺度自相似性，求解壓縮仿射變換，完成圖像編碼，這種來(lái)自于自身的編碼碼本不一定是最佳的，而且編碼時(shí)間通常較長(zhǎng)。根據(jù)圖像之間存在著相似性，構(gòu)造一個(gè)適應(yīng)性更強(qiáng)的固定編碼碼本，其它任何圖像分形編碼的值域塊只在這個(gè)固定碼本中搜索其最佳匹配塊，并且省去等距變換，此外，解碼也無(wú)需迭代。實(shí)驗(yàn)結(jié)果表明，在圖像質(zhì)量略有下降情況下，該算法較基本分形圖像編碼算法顯著地提高了編碼和解碼的速度，而且算法簡(jiǎn)單，容易實(shí)現(xiàn)。如果對(duì)這種固定碼本加以更好的適應(yīng)性改造，將會(huì)進(jìn)一步提高解碼圖像的質(zhì)量。

分形；固定碼本；快速分形編碼；相似性；最佳匹配；非迭代

引言

分形圖像編碼是比較有前途的第二代圖像編碼技術(shù)，其較高的率失真性能、分辨率無(wú)關(guān)性、迭代解碼的新穎思想正受到人們廣泛關(guān)注。1988年M.F.Barnsley提出了迭代函數(shù)系統(tǒng)［1］（IFS），并應(yīng)用到圖像壓縮編碼中，取得了極高的壓縮比，但該方法需要人機(jī)交互，對(duì)操作者要求較高，無(wú)法實(shí)用。1990年A.E. Jacquin提出了基于分塊的分形圖像壓縮方案［2］，在方案中，首先將圖像劃分為許多互不重疊的值域塊，然后對(duì)每個(gè)值域塊，按照仿射變換在原始圖像的緊縮圖像中尋找最相似的部分，這些操作可由計(jì)算機(jī)自動(dòng)完成，它為分形圖像編碼帶來(lái)了一次大的飛躍。然而分形圖像編碼與其他編碼技術(shù)（DCT編碼，小波編碼）［3-6］相比在編碼階段耗費(fèi)時(shí)間過(guò)長(zhǎng)，因此近二十年來(lái)，許多學(xué)者發(fā)表了大量的論文，主要是討論如何加快編碼速度［7-13］。但在所有這些文獻(xiàn)中，他們使用的編碼碼本（定義域塊集）都是來(lái)自于待編碼圖像本身，因?yàn)榉中尉幋a主要思想是基于圖像的自相似性以及不動(dòng)點(diǎn)定理、拼貼定理的數(shù)學(xué)原理［1，2］，不動(dòng)點(diǎn)定理能夠保證解碼圖像穩(wěn)定，拼貼定理給出了解碼圖像與原圖像誤差的上限。但是我們有理由相信，跨圖像的相似性也是普遍存在的，也就是說(shuō)我們可以設(shè)計(jì)一個(gè)不依賴于待編碼圖像的碼本，讓待編碼圖像的值域塊在這樣的碼本內(nèi)尋找它的最佳匹配塊，當(dāng)然這種固定碼本應(yīng)有足夠的適應(yīng)性，以適應(yīng)不同的圖像，本文正是基于這種想法做了一些探討與實(shí)驗(yàn)。為了更好地闡述這種固定碼本分形編碼的做法，有必要首先簡(jiǎn)要介紹基本分形編碼的數(shù)學(xué)原理和算法。

1 基本分形編碼的數(shù)學(xué)原理

1.1 壓縮映射定理

令ω：X→X為度量空間（X，d）上的變換，若存在一個(gè)常數(shù)0≤s＜1，使得

則稱ω為壓縮映射，s為壓縮因子。

1.2 迭代函數(shù)系統(tǒng)

一個(gè)迭代函數(shù)系統(tǒng)（IFS）包括一個(gè)完備度量空間，以及一系列定義于該空間上的壓縮映射ωn：X→X，壓縮因子分別為sn，n=1，2…，N。定義分形空間（H（X），dH）上的變換：W：H（X）→H（X）

1.3 拼貼定理

在分形空間（H（X），dH）中，設(shè)W：H（X）→H（X）是其上的壓縮因子為s的壓縮映射，A是該壓縮映射的不動(dòng)點(diǎn)（吸引子），則?C∈H（X），有

因?yàn)樵诰幋a階段，已經(jīng)求出W使得待編碼圖像C與W（C）非?？拷?，所以根據(jù)拼貼定理，迭代解碼的不動(dòng)點(diǎn)圖像A應(yīng)與原圖像C接近。

2 基本分形編碼算法［2］［14］

2.1 編碼

2.2 解碼

3 固定碼本編碼算法

3.1 固定碼本的構(gòu)造

圖像的跨尺度相似性不僅存在于圖像內(nèi)部，也存在于圖像之間，為了兼顧各種圖像的可能邊緣結(jié)構(gòu)和灰度變化信息，如果能構(gòu)造一個(gè)包含了各種圖像的邊緣結(jié)構(gòu)和灰度變化信息的圖像模板，就能夠?qū)θ我鈭D像做到最佳匹配，但實(shí)際上這種圖像模板很難構(gòu)造，即使圖像內(nèi)部也難以存在跨尺度下的完全相似。需要強(qiáng)調(diào)的是圖像塊不能匹配自身，這樣做毫無(wú)意義。我們簡(jiǎn)單地構(gòu)造了一幅圖像模板，如圖1所示，該圖看起來(lái)只是簡(jiǎn)單的幾個(gè)線條，但是它包含了很多邊緣結(jié)構(gòu)，如各種弧形邊緣、直角形邊緣，以及它們的等距變換和亮度變換，包含等距變換的好處是在搜索最佳匹配時(shí)可以省掉等距變換，從而加快編碼速度。另外還要考慮到各種圖像灰度變化的比例不同，一個(gè)可行做法是構(gòu)造圖像模板時(shí)，在多個(gè)不同部分使得灰度交錯(cuò)變化，這樣可以更加準(zhǔn)確地實(shí)現(xiàn)灰度上的匹配。對(duì)于任何一個(gè)待編碼圖像，只要做到子塊形狀和灰度上足夠匹配，就會(huì)得到較高的解碼圖像質(zhì)量。構(gòu)造圖1所示的圖像模板充分地考慮了這些特點(diǎn)。

圖1 生成固定碼本的圖像模板

3.2 算法分析

圖像編碼：

第一步：將大小為N×N的原始圖像C分割為互不重疊的大小為B×B的值域塊Ri，即

第二步：用B×B的截取窗以δ為滑動(dòng)步長(zhǎng)從大小為N/2×N/2的圖1模板中，截取定義域塊Dj，并構(gòu)成固定碼本

圖像解碼：

該算法除了碼本不是來(lái)自待編碼圖像外還有幾個(gè)重要特點(diǎn)：1）編碼階段無(wú)需等距變換，這樣可加快編碼速度；2）對(duì)比度因子s無(wú)需限定為，這樣可提高解碼圖像質(zhì)量；3）解碼階段無(wú)需迭代，這樣可加快解碼速度；4）編解碼的定義域塊均來(lái)自同一固定碼本，且該固定碼本無(wú)需傳輸，這樣可提高傳輸效率。

4 實(shí)驗(yàn)結(jié)果分析

我們首先測(cè)試基本分形算法和固定碼本算法對(duì)幾幅不同測(cè)試圖像編碼時(shí)所產(chǎn)生的匹配誤差。實(shí)驗(yàn)中測(cè)試圖像都是512×512灰度圖像，R塊都是8×8分割，滑動(dòng)步長(zhǎng)δ都是16，結(jié)果如圖2所示。

圖2 不同編碼方式產(chǎn)生的匹配誤差比較

從圖2中可以看出，不管是選擇哪種碼本，匹配的誤差主要還是圖像的邊緣和細(xì)節(jié)部分；圖（b）是從圖像本身產(chǎn)生的碼本中搜索匹配塊產(chǎn)生的誤差，圖（c）都是從固定碼本中搜索匹配塊產(chǎn)生的誤差，可以看出兩種算法產(chǎn)生的匹配誤差主觀質(zhì)量相近。

表1進(jìn)一步對(duì)兩種不同編碼算法的性能進(jìn)行了比較，仿真的平臺(tái)是：Windows操作系統(tǒng)、3.2GHz的CPU主頻、3GB物理內(nèi)存，所有算法由MATLAB7.9軟件實(shí)現(xiàn)。

表1 兩種不同算法的性能比較

從表1中可以看出，固定碼本算法的編碼速度較基本算法平均加快8.7倍，解碼速度平均加快14.7倍，峰值信噪比PSNR平均下降1.14dB。另外，固定碼本算法由于沒(méi)有進(jìn)行等距變換，較基本分形算法的分形碼少了一個(gè)等距變換參數(shù)t，只有三種參數(shù)，所以壓縮比較基本算法提高25%。值得一提的是，固定碼本算法已經(jīng)不屬于嚴(yán)格意義上的分形圖像編碼了，對(duì)比度因子s沒(méi)有做的限制，解碼時(shí)也沒(méi)有迭代解碼，實(shí)際上該算法沒(méi)有求解壓縮映射，從而不動(dòng)點(diǎn)定理、拼貼定理也就不復(fù)存在。因?yàn)闆](méi)有了基本分形算法中的拼貼定理（式（5）所示）的保證，固定碼本算法是不可進(jìn)行迭代解碼的。圖3（a）是固定碼本算法通過(guò)迭代10次得到的Lena圖像，圖3（b）是該算法沒(méi)有迭代解碼得到的Lena圖像。

圖3 迭代解碼對(duì)固定碼本算法的影響

5 總結(jié)

本文根據(jù)圖像相似性的普遍存在性，對(duì)基本分形的碼本構(gòu)成進(jìn)行了改進(jìn)，構(gòu)造了一個(gè)不依賴于待編碼圖像的固定碼本，作為任何圖像分形編碼的共同碼本。實(shí)驗(yàn)結(jié)果表明該固定碼本算法較基本分形編碼算法，在略微犧牲了一點(diǎn)圖像質(zhì)量（1.14dB）的代價(jià)下，較為顯著地提高了編碼速度（8.7倍）和解碼速度（14.7倍），而且該算法簡(jiǎn)單，特別是解碼無(wú)需迭代，因此具有一定的應(yīng)用價(jià)值。

本文構(gòu)造的碼本顯然不是最好的，固定碼本算法的難點(diǎn)在于怎樣更好地構(gòu)造一個(gè)不依賴于任何待編碼圖像的固定碼本，即如何構(gòu)造一個(gè)最具適應(yīng)性的碼本，目前這方面還缺少系統(tǒng)的理論分析和相關(guān)結(jié)論，只能通過(guò)實(shí)驗(yàn)不斷地改進(jìn)，所以這些問(wèn)題都有待進(jìn)一步的研究。

［1］Barnsley M.F..Fractal everywhere［M］.Academic Press，1988：375-377.

［2］A.E.Jacquin.Image coding based on a fractal theory of iterated contractive image transformations［J］.IEEE Trans.Image Process，1992，（1）：18-30.

［3］Yao Zhao，Baozong Yuan.Image compression using fractals and discrete cosine transform［J］.Electronics Letters，1994，（6）：474-475.

［4］K.U.Barthel，et al.A new image coding technique unifying fractal and transform coding［J］.Proc.of ICIP，1994，（3）.

［5］Alex Pentland，Bradley Horowitz.A practical approach to fractal-based image compression［J］.IEEE Computer society，Mar.，1991：176-185.

［6］G.M.Davis.A wavelet-based analysis of fractal image compression［J］.IEEE Transaction on Image Processing，F(xiàn)ebruary，1988，（2）：141-154.

［7］Fisher Y.，Jacobs E.W.，Boss R.D..Image compression：a study of the iterated transform method［J］.Signal Processing，1992，（3）：251-263.

［8］Hurtgen B.，Stiller C..Fast hierarchical codebook search for fractal coding of still image［C］.Berlin，Germany，1993：397-408.

［9］Martio P.，Michele N..Speed up in fractal image coding：comparison of methods［J］.IEEE Trans.on Image Processing，2000，（6）：1002-1009.

［10］Y.H.Moon，H.S.Kim and J.H.Kim.A Fast Fractal Decoding Algorithm Based on the Selection of an Initial Image［J］. IEEE Trans.Image Process，2000，（5）：941-945.

［11］C.He，S.X.Yang and X.Y.Huang.Variance-based accelerating scheme for fractal image encoding［J］.IEE Electronics Letters，2004，（2）：115-116.

［12］C.Lai，K.Lam and W.Siu.Improved searching scheme for fractal image coding［J］.IEE Electronics Letters，2002，（25）：1653-2654.

［13］C.Lai，K.Lam and W.Siu.A fast fractal image coding based on kick-out and zero contrast conditions［J］.IEEE Transactions on Image Processing，2003，（11）：1398-1403.

［14］何傳江.分形圖像編碼技術(shù)的算法研究［D］.重慶：重慶大學(xué)，2004：105-108.

ON THE ALGORITHM OF FRACTAL IMAGE CODING BASED ON FIXED CODEBOOK

YUAN Zong-wen LU Ye-pin YANG Han-sheng
（College of Mechanical&Electronic Engineering，Chaohu College，Chaohu Anhui 238000）

The traditional fractal image coding is based on the self-similarity across different scales of the image inside，solves the compression affine transformation and completes the image coding.The codebook from the image itself is not necessarily the best，and the encoding time is usually longer.According to the existence of similarities between the images，we construct an adaptable codebook in which the best matching block can only be searched for by the range block of any image fractal coding，and isometric transformation is omitted.In addition，there is no need to iterate the decoded image.Experimental results show that in the case of a slight decrease in image quality，the algorithm has better performance than basic fractal image coding and improves the encoding and decoding speed，and the algorithm is simple and easy to implement.If the fixed codebook improves through a better adaptation，it will enhance the quality of the decoded image.

fractal；fixed codebook；fast fractal coding；similarities；best matching；non-iterative

陳小舉

TP391

A

1672-2868（2015）03-0078-06

2015-02-05

安徽省高等學(xué)校自然科學(xué)研究項(xiàng)目基金支持（項(xiàng)目編號(hào)：KJ2011B103）

袁宗文（1978-），男，安徽含山人。巢湖學(xué)院，講師，碩士。研究方向：多媒體信息處理、數(shù)字電視技術(shù)。