【正文】 畢業(yè)設(shè)計 (論文 ) 大學(xué)本科學(xué)生畢業(yè)設(shè)計 — 分形圖像壓縮的算法 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 2 中文摘要 分形圖像編碼方法是近十年來誕生并發(fā)展起來的一種新型圖像壓縮方法，它將圖像編碼為一組收縮映射，由這組收縮映射的不動點近似待編碼對象。借助自可變換性特征有效地消除了圖像表達上的數(shù)據(jù)冗余，具有編碼效率高、與分辨率無關(guān)、解碼算法簡單等潛在優(yōu)勢，已成為當(dāng)今國際上圖像編碼領(lǐng)域中令人矚目的研究方向。 本課題旨在以分塊迭代函數(shù)系統(tǒng)為基礎(chǔ)，研究分形圖像編碼的理論、方法和實現(xiàn)技術(shù)，探討其工作機理，評價其能 力，彌補其缺陷，設(shè)計并實現(xiàn)高效的圖像壓縮 /解壓算法，為多媒體智能軟件系統(tǒng)提供有效的工具。 本文闡述了分形理論應(yīng)用在圖像壓縮領(lǐng)域的基本原理和實現(xiàn)該算法的關(guān)鍵技術(shù)，介紹了具有代表性的各種圖像壓縮的新方法，闡明了各個方法的優(yōu)劣，最后簡要總結(jié)了分形圖像壓縮的改進方法以及未來的發(fā)展趨勢 關(guān)鍵詞 : 圖像壓縮 ,分形 ,算法 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 3 ABSTRACT Fractal image coding, which is also called attractor image coding, is a emergent method of image pression during the last decade. It codes images as contraction maps of which the fixed points approximate to the images. Redundancy in images are efficiently exploited via the selftransformability on the blockwise basis. Owing to its high pression ratio, good image quality, and resolutionindependence of the decoded image, fractal image coding has been attracting much attention, and being considered to be promising in the realm of image pression This paper aims at giving a preheresearch on the theory, methodology, and implementation techniques of fractal image coding under the iterated function systems, developing a set of efficient coding/decoding algorithms to support multimedia software applications. This paper expounds the basic principle of the application of fractal in the image pression field theory and key technology of this algorithm,this paper introduces all kinds oftypical new method of image pared the advantages and disadvantages of every method ,and finally summarized the improvement and the future development trend of the fractal image pression method. Keywords: Image Compressing， Fractal， algorithm 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 4 目 錄 第一章 緒論 .......................................... 6 第二章 分形圖像編碼的相關(guān)介紹 .......................................................... 7 一、 分形圖像編碼的基本原理 ........................... 7 二、分形圖像編碼的實現(xiàn)步驟 ............................ 9 （一）編碼主要步驟 ................................. 9 （二）解碼主要步驟 ................................ 11 三、分形圖像壓縮的發(fā)展方向 ........................... 11 （一）加快分形的編碼速度 .......................... 11 （二）提高分形編碼質(zhì)量 ............................ 12 （三）分形序列圖像編碼 ............................ 12 第三章 分形與其他技術(shù)相結(jié) 合的改進方案 ....................................... 13 一、 提高壓縮比和編碼效果常用的改進方法 ............... 13 （一）改進分割的方法 .............................. 13 （二）改進覆蓋式方法 .............................. 13 （三）提高顯示效果的后處理法 ...................... 14 二、 DCT 與分形混合編碼 ............................... 14 三、 小波分形混合圖像編碼 ............................ 15 四、 提高編碼和解碼速度的方法 ........................ 16 （一）提高編碼速度 ................................ 16 （二）提高解碼速度 ................................ 16 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 5 第四章 仿真實驗 .................................................................................. 17 一、 分型圖像壓縮流程圖 .............................. 17 二、實驗環(huán)境與所需步驟 ............................... 18 （一）實驗環(huán)境： .................................. 18 （二）仿真步驟： .................................. 18 三、實驗程序 ......................................... 18 五、仿真結(jié)果 ......................................... 22 第五章 結(jié)論 ............................................................................................ 24 參考文獻 ................................................................................................. 25 附 錄 ....................................................................................................... 26 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 6 第一章 緒論 十多年前 ,在計算機圖形學(xué)中分形技術(shù)被用來模擬自然景象 ,其中最常用的思想便是迭代函數(shù)系統(tǒng) (IFS)和遞歸迭代函數(shù)系統(tǒng) (RIFS)。 Barnsley 首先看到迭代函數(shù)系統(tǒng)對模擬自然景象 (如云圖、樹和葉子 )的潛力。 IFS 方法在數(shù)字圖像壓縮理論和應(yīng)用上得到越來越多的關(guān)注 ,成為當(dāng)今圖像壓縮領(lǐng)域中最新的方法之一 . Barnsley和 Sloan 指出，分形圖像壓縮技術(shù)能獲得很高的壓縮比。 Jacquin 首先實現(xiàn)了完全自動的分形壓縮編碼算法，給分形圖像壓縮技術(shù)帶來突破性進展。分形圖像壓縮技術(shù)是在此算法基礎(chǔ)上逐漸發(fā)展 ,成為當(dāng)今圖像壓縮的一 個新領(lǐng)域。 “分形”一詞譯于英文 Fractal，系分形理論的創(chuàng)始人曼德爾布羅特（ ）于 1975 年由拉丁語 Frangere 一詞創(chuàng)造而成，詞本身具有“破碎”和“不規(guī)則”兩個含義，主要是給自然界中存在的大量的不規(guī)則的支離破碎的復(fù)雜圖形的命名。 1982 年 Mandelbrot 用創(chuàng)造性的思維形成了以分?jǐn)?shù)維、自相似性及無限可分為特點的、以迭代計算來描述的分形集合概念。從圖像處理的角度而言，在許多自然圖像中確實存在某種形式的分形子相似性，這就自然地產(chǎn)生了把分形概念用于圖像編碼的思 想。 1988 年 Barnsley 首先利用圖像整體與局部的自相似性，提出了一種應(yīng)用迭代函數(shù)系統(tǒng)理論實現(xiàn)的分形圖像壓縮編碼。 1990 年 Jacquin 創(chuàng)造性地利用圖像塊之間的相似性，提出了一種可由計算機完全自動實現(xiàn)的分形圖像編碼算法，為分形圖像編碼的研究帶來了一次質(zhì)的飛躍，使利用分形編碼進行圖像壓縮的方法開始進入實用階段。 1992 年底，美國微軟公司成功研制了一張“ Microsoft Encarta”光盤 .它僅用600Mbytes，就存貯了大量的文字?jǐn)?shù)據(jù)、長達 7h 的聲像資料、 100 部動畫片、 800張彩色地圖和 1000 幅逼真的風(fēng)景照片。這張光盤的研制采用了分形圖像壓縮技術(shù)。此技術(shù)以迭代函數(shù)系統(tǒng)為基礎(chǔ) ,采用了與常規(guī)技術(shù)不同的思想 ,能達到很好的壓縮效果，目前 ,這一技術(shù)已引起了學(xué)者們的濃厚興趣與深入研究 ,顯示了廣闊的應(yīng)用前景。 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 7 第二章 分形圖像編碼的相關(guān)介紹 分形編碼算法是一種有損圖像壓縮技術(shù)。它是圖像壓縮的重要數(shù)學(xué)工具，有著廣闊的應(yīng)用前景。分形圖像壓縮是以迭代函數(shù)系統(tǒng)（ IFS）為理論基礎(chǔ)，即用自然景物的自相似性來進行數(shù)據(jù)壓縮。分形圖像壓縮算法具有高壓縮比、任意尺度下的重構(gòu)、快速編碼等優(yōu)越性。此項研究 由 于 1988 年首先提出，他成功地給予迭代函數(shù)系統(tǒng)的分形圖像壓縮應(yīng)用于計算機圖形學(xué)上，對航空圖像進行壓縮編碼，并獲得了 1000： 1 的壓縮比。但其算法有很大的局限性，最主要的缺陷就是編碼過程需要人工干預(yù)。 一、 分形圖像編碼的基本原理 分形壓縮的基本原理是利用分形幾何中的自相似性原理來進行圖象壓縮。所謂自相似性就是指無論幾何尺度如何變化，景物的任何一小部分的形狀都與較大部分的形狀極其相似。分形用于圖像編碼，總的來說可以分為兩大類。一類可稱作分形模型圖像壓縮編碼，即事先對一類景物建立分形模型 。編碼時針對具體事物提取必要的分形參數(shù)，編碼傳送，實現(xiàn)壓縮；另一類可稱為 IFS分形圖像壓縮編碼，即利用迭代，得到原始圖像的一個近似。后一種實現(xiàn)方法簡單，應(yīng)用較為廣泛。目前 ,圖像壓縮方法已有近百種 ,但是 ,壓縮效果、壓縮比以及編碼、解碼時間還不能滿足當(dāng)前信息時代的要求。傳統(tǒng)的壓縮算法一般已經(jīng)成了定式 ,發(fā)展?jié)摿Σ淮?,而分形圖像壓縮的思想新穎 ,潛力很大 ,在 (人工干預(yù)條件下 )壓縮比達到10000： 1時 ,解碼圖像還有很好的視覺效果 ,是一個很有發(fā)展前途的壓縮方法。 到目前為止，用數(shù)學(xué)系統(tǒng)去解析地研究分形最成功的是函數(shù)迭 代系統(tǒng)（ Iterated Function System,簡稱 IFS），它既包含了確定性過程又包含了隨機過程。 對現(xiàn)實世界中的圖像集合引入 Hausdorff度量，使其形成一個完備的度量空間，它的每個點既表示一幅圖像，又是歐氏空間的一個緊子集。 ? Hausdorff 距離空間該距離空間被認(rèn)為是分形所在的空間，而分形之間的距離也正是由這種 Hausdorff距離度量的。 ? 仿射變換 定義： 一個變換 w:R2— R2 的形式為： 大學(xué)本科學(xué)生畢業(yè)設(shè)計（論文） 8 w(x1,x2) = (ax1+bx2+e, cx1+dx2+f) 其中 a,b,c,d,e,f均為實數(shù)，則稱 w 為二維仿射變換，在直角坐標(biāo)系中，我們可以寫成如下形式： （ 1） 實際上這是一種最廣泛的線性變換 ,設(shè)矩陣 （ 2） 則 A 的意義可分解為旋轉(zhuǎn) ,伸縮 ,扭曲 ,反演等。 (3) 如果已知原圖及其變換圖我們可以求出其中的仿射變換系數(shù)，這只要確定原圖上三點和變換圖上三點即可，