【正文】 我們可以列出以下方程： a*x1+b*y1+e=r1 （ 4） a*x2+b*y2+e=r2 （ 5） a*x3+b*y3+e=r3 （ 6） c*x1+d*y1+f=s1 （ 7） c*x2+d*y2+f=s2 （ 8） c*x3+d*y3+f=s3 （ 9） 由以上六方程可求出 a、 b、 c、 d、 e、 f。分形圖像壓縮的理論基礎(chǔ)是迭代函數(shù)系統(tǒng)（ IFS）定理、收縮映像定理和拼貼定理。一個(gè)迭代函數(shù)系統(tǒng)由一個(gè)完備的度量空間和其上的一組收縮映像組成。 ? 收縮映像定理 函數(shù)空間中的每一個(gè)收斂映像都有一個(gè)固定點(diǎn)，使函數(shù)空間中的每一個(gè)點(diǎn)經(jīng)過這個(gè)收縮映像的連續(xù)作用后．形成的點(diǎn)列收斂于這個(gè)固定點(diǎn)。 大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 9 ? 迭代函數(shù)系統(tǒng)定理 每個(gè)迭代函數(shù)系統(tǒng)都可以構(gòu)成函數(shù)空間中的一個(gè)收縮映射。于是，我們得到結(jié)論 ,每個(gè)迭代函數(shù)系統(tǒng)都決定一幅圖像。一般我們用仿射 變換來表示這些映射。 ? 拼貼定理 給定一幅圖像 I，可以選擇 N個(gè)收縮映像，這幅圖像經(jīng)過 N 個(gè)變換得到 N 個(gè)象集．每個(gè)象集都是一塊小圖像。如果這 N 個(gè)小圖像拼貼起來的圖像與圖像 I 之間的距離任意小，則這 N 個(gè)收縮映像構(gòu)成的迭代函數(shù)系統(tǒng)所決定的圖像就任意地接近圖像 I。這就告訴了我們尋找迭代函數(shù)系統(tǒng)的方法。 二、分形圖像編碼的實(shí)現(xiàn)步驟 整個(gè)圖像壓縮的過程可以分成兩大部分，一是編碼過程，一是解碼過程。在分形壓縮中，前者主要基于拼貼定理，這個(gè)過程中要考慮圖像的灰度分布，以及概率求取的策略。后者主要是隨機(jī)迭代問題 。 （一）編碼 主要步驟 這可以借助于傳統(tǒng)的圖像處理技術(shù)，如邊緣檢測(cè)，頻譜分析，紋理分析等，當(dāng)然也可以使用分?jǐn)?shù)維的方法。分割出的每部分可以是一棵樹，一片云等；也可能稍微復(fù)雜一些，如一片海景，它包括泡沫、礁石、霧震等；一般這每一部分都有比較直觀的自相似性特征。 每一部分求其 IFS編碼，這就要借助拼貼定理了，同時(shí)也是人要參與的地方，在這個(gè)過程中有一些必須注意的地方。 1）每一塊的“拷貝”必須小于原塊，這是為了保證仿射變換的收縮性，至于每個(gè)拷貝的大小要根據(jù)各塊圖像的性質(zhì)來確 定。 2）用于拼貼的每個(gè)拷貝之間最好為不相連或緊相鄰的。而不要重疊或者有空缺。這一點(diǎn)對(duì)概率的確定很重要，它影響到重構(gòu)圖像的不變測(cè)度。所以對(duì)有重疊或空缺時(shí)，這部分的“質(zhì)量”在計(jì)算中不能復(fù)用或者簡(jiǎn)單地丟棄，并最終要保證 的成立。 大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 10 拼貼的過程不僅要保證吸引子的形狀，也要考慮到每塊區(qū)域灰度分布的情況，拼貼結(jié)束時(shí)要求出各個(gè) pi， Barnsley等人采取的方法仍然是下式： （ 10） 其中 Tm表示某一分割后的圖像塊，這種方法有較快的計(jì)算速度，這種定義實(shí)際上是建立在均勻測(cè)度的假設(shè)上的，即吸 引子上相同大小的區(qū)域有相同的“質(zhì)量”。但是這在對(duì)實(shí)際的灰值圖像處理過程中并不總是成立的，往往是經(jīng)過某個(gè)仿射變換后的區(qū)域可能面積很大，但包含的總的灰度能量可能很??；反之某些小區(qū)域卻有較大的灰度能量。 為此，一般的方法是對(duì)灰度能量多的區(qū)域干脆多重疊幾個(gè)相同的仿射變換。這在解碼的過程中可能造成的一個(gè)結(jié)果是重構(gòu)圖中存在偽灰度現(xiàn)象；同時(shí)在隨機(jī)迭代重構(gòu)時(shí)總的步數(shù)也沒有確定地給出，只能“足夠大”，最后再把灰度歸一化到［ 0， 255］。為此，我們?cè)谄促N的過程中重新定義了概率的求取，令圖像塊 Tm能量為 Qm： （ 11） f（ i， j）表示點(diǎn)（ i,j）處的圖像灰度 ,則可定義概率： (12) 其中分子表示 Tm 經(jīng) wi 變換后區(qū)域中的能量。這時(shí)的 pi應(yīng)該說可以很好地反映出了圖像內(nèi)部灰度分配的信息，它還可以指導(dǎo)圖像重構(gòu)，即對(duì)每一圖像塊重構(gòu)時(shí)總的隨機(jī)迭代次數(shù)就可以設(shè)為該塊的總能量 Qm,而每一次迭代生成點(diǎn)的灰度能量為為 1個(gè)單位。此時(shí)概率 pi 計(jì)算稍微比前一種方法麻煩些，在計(jì)算中可以用 wi(Tm)與 Tm 的邏輯與來獲得 wi(Tm)區(qū)域的能量。 大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 11 （二）解碼主要步驟 分形的解碼步驟很簡(jiǎn)單，可以用任意的圖像作為初始圖像，經(jīng)過存儲(chǔ)的相應(yīng)的迭 代函數(shù)的若干次迭代就可以準(zhǔn)確的恢復(fù)原圖 。 三、分形圖像壓縮的發(fā)展方向 在 1990年， Jaquin提出了基于塊的分形圖像壓縮算法。雖然該算法的壓縮比低于 ,但是他的編碼過程可自動(dòng)進(jìn)行。因此此算法已經(jīng)成為這一研究方向的典型代表。 Jacquin發(fā)展了 IFS理論，提出了局部迭代函數(shù)理論（ PIFS），他在此理論基礎(chǔ)上提出了一種基于方塊劃分的分形圖像壓縮方案，在其方案中首先將原始圖像劃分為固定大小的方塊，然后對(duì)每一塊，通過反射變換在原始圖像的緊縮圖像中尋找最相似的部分。這些操作可由計(jì)算機(jī)自動(dòng)完成， 他為分形圖像壓縮的研究帶來了一次質(zhì)的飛躍。 Jacquin提出的方案為分形壓縮編碼的研究注入了生機(jī)和活力，使分形編碼成為目前編碼研究的熱點(diǎn)。目前分形編碼方案大致有三個(gè)發(fā)展方向：加快分形的編解碼速度、提高分形的編碼質(zhì)量、基于 分形序列圖像的編碼 。 （一）加快分形的編碼速度 編碼速度慢一直是分形編碼實(shí)用化的最大障礙，下面分析 Jacquin編碼方案的計(jì)算復(fù)雜度。對(duì)于一個(gè) C C大小的圖像，假設(shè)值域子塊大小為 K K,定義域子塊大小為 2 K 2K,則該圖像共有 C2/K2個(gè)值域子塊，（ CK+1） 2個(gè)定義域子塊。在 Jacquin的方案中，一個(gè)值域子塊和一個(gè)定義與子塊之間的相似性的計(jì)算量與 K2成正比，而對(duì)于每一個(gè)值域子塊，編碼計(jì)算量與（ CK+1） 2/K2呈線性關(guān)系，所以，對(duì)于一幅圖像來說，其編碼復(fù)雜度與（ CK+1） 2* K2*C2/ K2=（ CK+1） 2*C2成正比，因此，分形編碼的計(jì)算復(fù)雜度為 O(C4)。所以，減少搜索、加快編碼速度是研究的熱點(diǎn)之一。 Jacquin根據(jù)子塊的復(fù)雜度將其分成四類，對(duì)每個(gè)值域子塊，僅在其同類的定義域子塊中進(jìn)行搜索； 的匹配過程， 其搜索匹配時(shí)間按指數(shù)級(jí)增長(zhǎng)； Jacquin方案中使用的分類器替換成模糊分類器，并使用遺傳算法進(jìn)行優(yōu)化，該算法比未分類的編碼方大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 12 案快 40%左右； ，如果兩子塊的自身方差相差太遠(yuǎn)，則這兩個(gè)子塊不可能相似，由此可去除許多不必要的匹配過程，提高壓縮速度 10倍以上； Min Xue等將傳統(tǒng)編碼方案中每個(gè)值域子塊匹配的串行操作轉(zhuǎn)換為并行操作，計(jì)算復(fù)雜度下降，縮短了壓縮的時(shí)間。 （二）提高分形編碼質(zhì)量 目前，提高分形編碼質(zhì)量的方法有三種：采用混合 編碼方案、改進(jìn)分割方案、改進(jìn)灰度逼近能力等。提高編碼質(zhì)量的方法是對(duì)傳統(tǒng)的分割方法進(jìn)行改進(jìn)。Jacquin使用兩次分割，在提高編碼質(zhì)量的同時(shí)，又避免壓縮比下降太多。隨后又有許多學(xué)者對(duì)上述方法繼續(xù)進(jìn)行改進(jìn)，提出了四象限的劃分方法，是分形壓縮的質(zhì)量和壓縮速度有了較大的提高，是目前較為實(shí)用的壓縮方法。目前國內(nèi)外研究者還提出了基于區(qū)域的分割方案。在分形編碼中常用的灰度逼近式為 w(z)=s*z+t,可把灰度逼近式變?yōu)?w(z)=t(z),t(z)可為任意形式，可以為二次以上的多項(xiàng)式，有效提高了編碼效果，改進(jìn)圖像質(zhì)量。 （三）分形序列圖像編碼 在實(shí)際應(yīng)用中，序列圖像較靜態(tài)圖像有著更廣闊的應(yīng)用，而且由于時(shí)間維的引入，編碼方法也有新的變化 [5]，因此，序列圖像編碼是圖像編碼研究的熱點(diǎn)之一。 1994年，加拿大學(xué)者 Lazar等人發(fā)表了一篇論文，加入了時(shí)間維，將 Jacquin的分形編碼從二維變換直接推廣到三維，并直接借用靜態(tài)圖像的分形編碼方案，但這樣沒有充分利用楨間的相似性，壓縮性能不佳。此后，又有人提出了自矢量量化的序列圖像編碼方案，但圖像恢復(fù)質(zhì)量、壓縮比及編碼實(shí)時(shí)上仍不是很理想。因此分形序列圖像編碼是當(dāng)今分形壓縮編碼的一個(gè) 重要方向 。 大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 13 第三章 分形與其他技術(shù)相結(jié)合的改進(jìn)方案 分形圖像壓縮編碼的應(yīng)用已經(jīng)深入到人類活動(dòng)的各個(gè)方面，并已取得了令人矚目的成果。分形圖像壓縮既考慮局部與局部，又考慮局部與整體之間的相關(guān)性，適合于自相似或自仿射的圖像壓縮；分形圖像壓縮解碼時(shí)能放大到任意大的尺寸，且保持精細(xì)的結(jié)構(gòu)；在高壓縮比的情況下，分形圖像壓縮自動(dòng)編碼能有很高的信噪比和很好的視覺效果。但是對(duì)于編碼雖然有許多的改進(jìn)措施，但是搜索匹配時(shí)間過長(zhǎng)還是不能滿足許多實(shí)際的需要，基于此，近兩年來 , 很多學(xué)者和專家把分形與其它的技術(shù)和工具、方法混合 編碼取得了很好的效果。常用的混合方案有與小波變換結(jié)合編碼、與 DCT 變換結(jié)合編碼、與加權(quán)有限自動(dòng)機(jī)結(jié)合編碼、與向量量化結(jié)合編碼、與遺傳算法結(jié)合編碼、與 FFT 算法結(jié)合編碼、與非線性模型結(jié)合編碼、與算術(shù)結(jié)合編碼。近 10 年來 ,人們對(duì)于自適應(yīng)塊狀分形編碼進(jìn)行了不懈的研究 ,提出了以上若干改進(jìn)算法 ,這些算法在不影響視覺效果的條件下 ,大大減少了編碼時(shí)間。而且在高壓縮比和解碼圖像任意放大方面 ,比現(xiàn)有的靜態(tài)圖像國際壓縮標(biāo)準(zhǔn) JPEG 好得多 ,已經(jīng)開始顯露出它的優(yōu)勢(shì)。分形圖像編碼方法的實(shí)際應(yīng)用也初見端倪 ,如分形圖像壓縮解碼速度很快 ,當(dāng)前已經(jīng)適合于一次寫入、多次讀出的文檔 。 一、 提高壓縮比和編碼效果常用的改進(jìn)方法 （一）改進(jìn)分割的方法 有基本四叉樹分割法、基于 HV分割法。這兩種分割方法都是將圖像分割成矩形。而圖像塊的相似性未必都落在矩形內(nèi)。代替水平或垂直剖分而采用的分割方法有基于三角形分割法、基于六邊形分割法、基于邊界分割法、基于菱形分割法、基于多邊形分割法。 （二）改進(jìn)覆蓋式方法 覆蓋式方法有快速覆蓋式分形壓縮方法和四叉樹重組 QR算法兩種它們都是采用通過合并值域塊來提高壓縮比。前者要求合并后不一定規(guī)則 ,后者合并后則是 規(guī)大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 14 則的。 （三）提高顯示效果的后處理法 分形圖像壓縮對(duì)值域塊獨(dú)立編碼 ,這不能保證塊與塊之間的連接是光滑的 ,常有塊效應(yīng)出現(xiàn) ,人的眼睛對(duì)此比較敏感。消除塊效應(yīng)的一個(gè)常用方法是后處理 ,一般采用加權(quán)平均法 。 二、 DCT 與分形混合編碼 自從分形圖像壓縮作為一種實(shí)用的方法由 Jacquin首次提出以來，大多數(shù)關(guān)于分形圖像壓縮的研究都集中在時(shí)間域進(jìn)行，為了提高編碼性能，一些變換域變換編碼方法相繼由 Barthel等提出。 其中離散 余弦變換 (Discrete consine transformationg),余弦調(diào)制濾 波器組（ Cosine modulated filter banks）和小波變換等應(yīng)用最為廣泛，小波變換與分形的結(jié)合在上面已經(jīng)作了簡(jiǎn)要地介紹。在這里我們介紹一下 DCT與分形的混合編碼方案。 分形圖像編碼的原理是要尋找一組收斂的仿射變換來重建圖像，利用同一圖像中一部分描述另外一部分，即利用圖形的自相似性來減少圖像的冗余度。頻域變換的一個(gè)突出優(yōu)點(diǎn)就是他的能量緊湊特性，一幅圖像經(jīng)過頻域變換后，總能量沒有變化，但能量的分布卻發(fā)生了變化。能量將集中在它的低頻部分，而高頻部分所占的能量非常少，能量的這種分布對(duì)分形壓縮十 分有利，因?yàn)榉中螆D像壓縮的主要過程是對(duì)同樣大小的圖像塊進(jìn)行能量匹配，經(jīng)過頻域變換后，高頻部分在能量匹配過程中產(chǎn)生的誤差很小，基本可以忽略不計(jì)，這就等于減少了匹配塊的大小，從而減小了匹配誤差。 去相關(guān)能力最強(qiáng)的是 KL變換，但由于其難以實(shí)現(xiàn)，人們轉(zhuǎn)而尋找能實(shí)時(shí)處理的次最佳變換，離散余弦變換就是其中的一種。近年來的研究表明，離散余弦變換是一種最接近最佳的正交變換，性能接近 KL變換。 主要編碼步驟： （ 1）設(shè)原圖像的大小為 N*N，首先把它劃分為（ N/8） 2塊大小為 8*8的區(qū)塊（ range block） ,對(duì) 所有的作 DCT變換，得到一個(gè) N*N的區(qū)圖像（ rang image） 。 接著，將原圖像在劃分為（ N/16） 2塊 16*16的域塊（ Domain block） ， 對(duì)所有的域塊作 DCT變換，然后再經(jīng)過變換后的 16*16圖像塊中取出他的左上角 8*8的塊，這些塊按照原圖的順序組成一個(gè)域塊庫。之所以只取圖像左上角是因?yàn)橛驂K在經(jīng)過變換后，大學(xué)本科學(xué)生畢業(yè)設(shè)計(jì)（論文） 15 主要信息都保存在低頻區(qū)，對(duì)應(yīng)于圖像塊的左上角，而高頻區(qū)所占的能量相對(duì)較少，在以后的匹配中，起的作用很小。因此，在構(gòu)成域塊時(shí)，我們只取左上角與區(qū)塊同樣大小的一部分。 (2)接下來則是利用圖像的 自相似性進(jìn)行分形壓縮，其實(shí)質(zhì)是尋找一組仿射變換，即塊匹配過程。它與時(shí)域的塊匹配過程完全相同。但由于圖像經(jīng)過頻域變換后，具有與時(shí)域不同的特點(diǎn)，因此在具體的實(shí)現(xiàn)方法上存在著一些差別。首先：圖像在經(jīng)過 DCT變換后 ,能量集中到低頻部分，特別是它的直流分量，占據(jù)了整幅圖像能量的很大一部分，這就使得我們必須對(duì)它們單獨(dú)處理，而不把它帶入塊匹配的過程中。在匹配過程中，均值分量也就不再需要。在 DCT域分形編碼中，我們是將這些直流分量直接作差分之后再進(jìn)行量化、熵編碼。這樣做不僅減少了塊匹配的誤差，而且在解碼時(shí)，在第一次迭代過程 中，就可以得到直流分量，從而加快了解碼的收斂速度。其次，圖像塊在經(jīng)過 DCT變換后，能量分布具有一定的規(guī)律，不同于在時(shí)域中的雜亂無章的分布，因此在塊匹配過程中，旋轉(zhuǎn)所帶來的性能上的改進(jìn)將變得非常小，與此同時(shí)，它卻增加了所需的比特?cái)?shù)，降低了壓縮比。所以我