分形壓縮編碼

㈠ 屬於無損壓縮的編碼方法是（ ）。

霍夫曼（Huffman）編碼原理
霍夫曼（Huffman）編碼是1952年為文本文件而建立，是一種統計編碼。屬於無損壓縮編碼。
霍夫曼編碼的碼長是變化的，對於出現頻率高的信息，編碼的長度較短；而對於出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小於實際信息的符號長度。

在這個上面看到的..應該是選 D 統計編碼

㈡ 分形編碼的分形編碼的特點

壓縮比高，壓縮後的文件容量與圖像像素數無關，在壓縮時時間長但解壓縮速度快

㈢ 分形編碼的分形編解碼過程

分形編碼壓縮的步驟： 第一步：把圖像劃分為互不重疊的、任意大小的的D分區； 第二步：劃定一些可以相互重疊的、比D分區大的R分區； 第三步：為每個D分區選定仿射變換表。 分形編碼解壓步驟： 首先從文件中讀取D分區劃分方式的信息和仿射變換系數等數據； 然後劃定兩個同樣大小的緩沖區給D圖像和R圖像，並把R初始化到任一初始階段； 根據仿射變換系數把其相應的R分區做仿射變換，並用變換後的數據取代該D分區的原有數據； 對D中所有的D分區都進行上述操作，全部完成後就形成一個新的D圖像； 再把新D圖像的內容拷貝到R中，把新R當作D，D當作R，重復操作（迭代）。

㈣ 矢量量化編碼方法和分形編碼方法各有什麼特點

矢量量化（VQ —Vector Quantization）是70年代後期發展起來的一種數據壓縮技術基本思想：將若干個標量數據組構成一個矢量，然後在矢量空間給以整體量化，從而壓縮了數據而不損失多少信息。

分形編碼的特點
壓縮比高，壓縮後的文件容量與圖像像素數無關，在壓縮時時間長但解壓縮速度快

㈤ 離散餘弦變換和分形編碼圖像壓縮演算法的性能比較

目前，分形編碼還未完全實用化 ，其主要困難在於傳統空域的分形壓縮有很多瓶頸 ，例如，運算復雜度太大、收斂過程較難預測和控制、高壓縮倍率時的塊狀效應等 。盡管自動圖像壓縮演算法的改進工作 已持續 了十幾年 ，但編碼時間、壓縮 比以及壓縮效果仍不夠理想 ，遠沒有達到分形本身應該達到的效果，因而 ，在當前 圖像壓縮編碼 中還不 佔主 導地位。為了能真正發揮分形高壓縮 比的潛力，必須尋求 IFS碼演算法 的突破，找到編碼實現的快速演算法 ，或者對分形塊壓縮方法作出重大改進，否則分形圖像壓縮技術很難與成熟的JPEG和 MPEG競爭。

離散餘弦變換，尤其是它的第二種類型，經常被信號處理和圖像處理使用，用於對信號和圖像(包括靜止圖像和運動圖像)進行有損數據壓縮。這是由於離散餘弦變換具有很強的"能量集中"特性:大多數的自然信號(包括聲音和圖像)的能量都集中在離散餘弦變換後的低頻部分，而且當信號具有接近馬爾科夫過程(Markov processes)的統計特性時，離散餘弦變換的去相關性接近於K-L變換(Karhunen-Loève 變換--它具有最優的去相關性)的性能。
例如，在靜止圖像編碼標准JPEG中，在運動圖像編碼標准MJPEG和MPEG的各個標准中都使用了離散餘弦變換。在這些標准制中都使用了二維的第二種類型離散餘弦變換，並將結果進行量化之後進行熵編碼。這時對應第二種類型離散餘弦變換中的n通常是8，並用該公式對每個8x8塊的每行進行變換，然後每列進行變換。得到的是一個8x8的變換系數矩陣。其中(0,0)位置的元素就是直流分量，矩陣中的其他元素根據其位置表示不同頻率的交流分類。

㈥ 分形壓縮的介紹

分形壓縮（en:Fractal compression）。特別適合壓縮自然景觀的圖片，依賴於特定的圖像及同一副圖像的一部分與其他部分的相似程度。Michael Barnsley在1987年提出分形壓縮技術，最廣為人知的具有實際用處的分形壓縮演算法是由Barnsley和Alan Sloan提出的。所有的這些演算法都是基於使用疊函數系統的分形變換。

㈦ 分形圖像壓縮的壓縮比怎麼求

分形圖像壓縮作為一種新的壓縮方法,因其具有壓縮比高、解碼速度快、解碼圖像與解析度無關等優點,十餘年來引起了眾多學者的關注和研究。但是,這種方法存在一個最大的問題:編碼時間過長,主要是因為編碼時定義域塊的搜索量非常可觀。這實際上已成為了該方法走向高效能實用化的最主要障礙,因此分形編碼加速方法已成為了近些年來分形壓縮的一個研究熱點。目前許多分形編碼加速方法或者以犧牲解碼圖像質量為代價,或者加速效果不明顯。本文提出了一種混合的快速分形編碼方法,將分形編碼的父塊庫看作向量空間,通過正交特徵量化將子塊和父塊的匹配轉化為歐式空間的最小距離問題,在分類的基礎上,將向量子空間建立成kd-tree,匹配問題進一步轉化為在樹結構上的最近鄰居查找問題,再引入(1+ε)最近鄰居查找進一步加速,可達到實時編碼。試驗結果表明,同以往的方法相比,本方法在基本保證解碼質量的基礎上,可以極大地提高分形編碼速度。同不加速分形編碼相比,混合方法帶旋轉反射變換編碼速度可以提高66倍,不帶旋轉反射變換可以提高653倍。 紋理是圖像處理,圖像真實感造型領域的很重要的概念,其自身有很多獨特的性質使其可獲得高壓縮比。將紋理看成是圖像本身的局部性質,就可將紋理壓縮與傳統壓縮方法結合起來彌補後者的不足。成熟的紋理壓縮方法都是基於硬體的,紋理壓縮的高壓縮比潛力並沒有充分被發揮出來。矢量量化技術的碼書訓練原理與紋理的紋元重復特性剛好一致,並且紋理合成方法的成熟發展為紋理的純演算法壓縮提供了方向。本文提出了新的紋理壓縮方法,將紋理進行采樣,用矢量量化技術從中訓練出碼書,與傳統矢量量化不同,不再進行鍵集編碼,而是以碼書作為編碼結果,這就是高壓縮比的關鍵,以此碼書作為紋理合成的「樣圖」,利用紋理合成技術作為解碼過程。如果是塊采樣,則用基於塊的紋理合成,如果是象素采樣,則用基於象素的紋理合成。試驗結果表明本方法保證解碼質量的基礎上可以獲得很高的壓縮比,而且可以根據圖像的質量控制壓縮比,由於紋理合成的優勢,還可以解碼出任意尺寸的圖像,在保證逼真度的基礎上,可以獲得32:1或更高的壓縮比。

㈧ 大哥您好，我是上次向您求助怎樣用分形進行圖像壓縮的，我是做這個畢設的。。。

A METHOD OF IMAGE COMPRESSION BASED ON FRACTAL DIMENTION

WUZiwen
(Department of computer science, Fujian Teachers UniversityFuzhou 350007)

WUPenghuiZHENGBaoyu
(Nanjing University of Post and CommunicationNanjing 210003)

AbstractIn this paper, we put forward a new method of image compression based on fractal dimension and combined DCT with fractal encoding. Experiments show that compared to basic automatic fractal coding approach, the new method can get higher compression ratio、higher PSNR and quicker computation speed.
Key wordsFractalFractal dimensionIFS DCT

1引言

在計算機圖形學領域中關於曲線和曲面的研究已相對成熟，人們先後提出了象B樣條曲線/曲面、Bezier曲線/曲面等既有堅實理論基礎又有實用價值的圖形、圖象處理方法.然而，這些幾何模型在處理大自然為數眾多的景象，如海岸線、地貌、 雲、樹木等方面時，卻顯得不盡人意，乃至無能為力，這主要的原因是因為計算幾何學研究的是「規則」的幾何形體，或近似幾何形體.法國數學家Benoit B. Mandelbort 以不規則圖形為研究對象，於一九七五年提出了分形幾何的概念，創立了分形幾何學理論.他提出了用分形維數這一度量概念來描述自然現象的不規則程度.而圖象的最終目的是供人去觀察的，考慮到人的視覺系統的固有特性，比如對某些頻率分量比對其他的敏感些，因此，對不敏感部分可以粗略編碼，重構的解碼圖象也不會有接受不了的質量損失，所以在編碼系統中考慮到人的視覺特性將有利於提高壓縮比.基於分割的圖象編碼就是這樣一種技術，它根據視覺特徵，使用一些分割方法把圖象分成若干類區域，對不同類的區域採用不同的編碼策略.本文採用基於分形維數的方法進行圖象分割，把圖象分成具有明顯分形特徵和分形特徵相對不明顯的兩類區域，對具有明顯分形特徵的區域使用基於迭代函數系統（IFS）的分形圖象壓縮編碼方法，而分形特徵相對不明顯的區域施以DCT壓縮編碼.這種基於視覺特性的分形維數分割的圖象壓縮方法可以獲得相當高的壓縮比.

2分形維數
分形的本質是「自相似」.分形表示無規則、非規整現象，但絕不是絕對的無規則，而是具有自相似性.實際的自然景物一般不具嚴格的自相似性，而通常具有統計意義上的自相似性，Pentland 證明了自然界的大多數表面是空間各向同性的分形，且這些表面所映射成的灰度強度分布場也具有分形特徵.這樣，我們可以通過對表面的圖象數據分析得出自然界存在的物體的分形特性.
分形維數是分數維，是對分形的一種描述和量度.即是對「不規整」的、支離破碎的片斷集合的定量描述.
分數維的產生，拓寬了數學維數的領域.以往用整數維的傳統方法難以測定和描述的某些自然界的景物，可以用分數維來定量描述.當然，自然界千姿百態，並非一切復雜的自然現象都可以用分數維這一個尺度來量度，正如一切自然現象絕不可能都是分形結構一樣，但是，由於分形維數直觀上與物體表面的粗糙程度相吻合，而自然界中的不同紋理粗糙度有很大的差別，因此，分形維數可以作為區別不同圖象區域的分形特性的有效參數，從而可依據分形維數將圖象區域分類，進而對不同類別的圖象區域採用不同的壓縮編碼方案.

3圖象中分數維的提取
維數在數學上可用多種方法來定義.Hausdorff利用集的復蓋來定義測度的思想，定義了以他名字命名的測度和維數，盡管Hausdorff維數對任何集都有定義，然而這種維數在理論上的意義遠大於實際應用，對於一個分形集合，計算其Hausdorff 維數一般是相當困難的.實際上我們最為常用的分數維定義有自相似維、Holomogrov容量維、盒子維等.
雖然一個真實空間中的分形表面映射到圖象的灰值表示的過程從數學上說還沒有完全解決，但是圖象的灰值表面最終總可以用相關於分形表面法線上及入射光之間角度的一個函數表示，所以，美國的A.P.Pentland假定，如果一個物體的表面是分形的，則由它產生的圖象灰度表面也具有分形的性質，反之亦然.因此，我們可以從灰值圖象中提取分數維.
本文採用盒子維的方法從圖象中提取分數維——分形維數.盒子維是迄今在各學科領域中應用得最為廣泛的一種維數.這主要是因為它非常容易由計算機求得.
盒子維方法是把二維平面中的方格推廣到小立方體時得到的.令N(r)表示邊長為r×r×r的包含所要估計的圖象區域的最少立方體個數，在這里可以把灰值圖象想像成一個在三維空間中的分形曲面.所要估計的圖象區域的分數維D將由下式決定：
N(r)*rD=C
其中C為常數，兩邊同取對數有：
logN(r)=-Dlogr+logC
設某個圖象區域的面積為A，r×r為一個單位面積，r可變大小，令

其中Ii(i=1,2,3,4)表示相應點的灰值大小，int表示取整.n(r)即是包含該單位面積上灰度所要的r×r×r的立方體個數.
區域A中的每個單位面積，均做同樣的計算，可以得到n1(r),n2(r),…,求其均值，以E(n(r))表示，則有：

現在改變r的大小，可以求出相應的各個N(r)，再用線性回歸等求出logN(r)相對於logr的斜率，也就是該圖象區域的分數維——盒子維.
我們在對圖象提取盒子維時，一般是按圖象分塊進行的，即設定一個窗口，尺寸大小一般選成8×8或16×16等，提取的是窗口區域的分數維，窗口的移動是從左到右，從上而下，每次移動的步長取窗口的邊長.

4基本的自動分形圖象壓縮演算法

由Jacquin於1990年提出的基於迭代函數系統（IFS）的分塊分形圖象壓縮演算法首先實現了基本的自動分形圖象編碼方法.編碼時，首先將原始圖象分割成互不重疊的小方塊Range塊（調節小方塊的大小可改變壓縮比及重建圖象的質量），分形編碼的過程就是在同一圖象內找到能夠最佳匹配每一個Range塊的大一些的方塊Domain塊，Domain塊與Range塊的尺度比稱為尺度壓縮因子，一般說來，Range塊小，則壓縮比小，但重建圖象的信噪比高，Range塊大，則相反.匹配的過程包括幾何變換和灰度變換.
對原始圖象分割的每一Range 塊，求出它的最佳匹配塊，記錄Domain塊的起始位置代碼、灰度變換系數以及幾何對稱變換矩陣的序號，即得到所求的壓縮編碼.
解碼時，以任一圖象為初始圖象，根據所有記錄的每一Range塊所對應的Domain 塊的起始位置代碼、灰度變換系數以及幾何對稱變換矩陣的序號，作相應的映射，迭代收斂的結果即為重建圖象.〔5〕

5基於分形維數的圖象壓縮編碼

Mandelbrot 曾定義：若一個集合的Hausdorff維數嚴格地大於它的拓撲維數，那麼該集合就稱為分形集.Hausdorff維是一種分數維，當然，從今天看這種定義有不令人滿意的地方，它排除一些明顯應當是分形的集合.但是，把Hausdorff維數嚴格大於拓撲維數作為分形集的充分條件，則是沒有爭辨的.當我們在同一圖象的不同區域求得分數維以後，就可以基於此進行分類.有時可能在某些區域得到的分數維會低於相應的拓撲維等.這在物理上是不可能成立的，它說明了分形的模型在這些處是不合適的，而此處一般是多類物質的交界處，即圖象的邊緣分界處.本文對把圖象表面看作三維空間的曲面，對相應的灰值圖象進行分塊提取分形維數——盒子維，當盒子維嚴格大於拓撲維數3時，則認為這些圖象塊具有較典型的分形特徵，採用基於分形的圖象壓縮編碼，即採用基於迭代函數系統（IFS）的分塊圖象壓縮編碼，盡可能提高壓縮比.而對盒子維小於或等於拓撲維數3的圖象塊，則認為這些塊的分形特徵不明顯或不具有分形特徵，即分形模型在這類塊是不合適的，因而採用DCT變換壓縮編碼方案，以保證圖象的壓縮質量.編碼部分具體步驟如下：
* 將原圖象分割成16×16大小的方塊，用上面介紹的方法計算每個方塊的分形維數.
* 經實驗表明，設定閥值t = 3，將每一個方塊的分形維數與t相比較，若嚴格大則認為該塊具備較明顯的分形特徵，適合採用基於分形的圖象壓縮方法，採用前面介紹的基本分形圖象壓縮演算法，並將其標志為1.否則就認為該塊所具備的分形特徵不明顯，在這里我們採用基於DCT（離散餘弦變換）的JPEG壓縮方法，即將圖象方塊經過DCT變換，再量化，最後進行無失真的熵編碼（這里我們採用Huffman編碼），並將其標志為0.
* 經過圖象方塊的分類，得到原圖象的方塊分類標志點陣圖，連同得到的IFS代碼、JPEG壓縮代碼合成最後的壓縮數據流.
解碼部分的具體步驟如下：
任意給定一幅圖象，根據方塊分類標志點陣圖，對標志為1的方塊，用相應的IFS 代碼進行迭代得到最終的收斂塊，將之覆蓋原圖象的相應塊.對標志為0的方塊，用相應的JPEG壓縮代碼經過JPEG解壓縮演算法進行解碼，得到的解碼塊覆蓋原圖象的相應塊.

6實驗結果

表1實驗結果的比較

編碼方法 壓縮比 峰值信噪比
PSNR（db) 運算時間(h)
基本的自動分形
圖象壓縮方法 20.51 27.4 2.5
基於分形維數的
圖象壓縮方法 45.36 29.7 0.8

* 福建省自然科學基金資助項目.吳子文，副教授，主要研究方向為計算幾何和計算機輔助設計等.吳鵬暉，碩士研究生，研究方向為數字信號處理及傳輸技術、多媒體信息處理技術等.鄭寶玉，教授、博士生導師，主要研究方向為數字信號處理及傳輸技術、多媒體信息處理技術等.

作者單位：吳子文福建師范大學計算機科學系福州 350007
吳鵬暉鄭寶玉南京郵電學院信息工程系南京 210003

參考文獻

〔1〕Barnsley.M F.Hurd I.P. Fractal image compression.Wellesley：AK Peters,1992
〔2〕Jacquin A E．Fractal image coding based on a theory of iterated contractive image transformations.In：Proc SPIE's Visual Communications and Image Processing,1990
〔3〕曾文曲等．分形理論與分形的計算機模擬．沈陽.東北大學出版社.1993
〔4〕王東生等．混沌、分形及其應用．合肥.中國科學技術大學出版社.1995
〔5〕吳子文等．一種雙二次插值與IFS相結合的圖象壓縮新方法．小型微型計算機系統．1998,4

㈨ 分形編碼的發展過程

圖像壓縮已研究了幾十年，提出了諸如DPCM、DCT、VQ等壓縮方法，並已出台了基於DCT等技術的國際壓縮標准，如JPEG、MPEG、H.261等。人們逐漸發現了這些方法的許多缺點：比如高壓縮比時圖像出現嚴重的方塊效應、人眼視覺系統的特性不易被引入到壓縮演算法中，等等。人們認為目前有三種方法屬於第二代圖像編碼方法：基於分割的壓縮方案、基於模型的壓縮方案及基於分形的壓縮方案。
分形圖像編碼是目前較有發展前途的圖像編碼方法之一, 也是目前研究較為廣泛的編碼方法之一。對其研究已有近十年的歷史，其間，人們發現了它所具有的許多優點：比如，它突破以往熵壓縮編碼的界限，在編碼過程中，採用了類似描述的方法，而解碼是通過迭代完成的，且具有解析度無關的解碼特性等。
分形圖像編碼的思想最早由Barnsley和Sloan引入，將原始圖像表示為圖像空間中一系列壓縮映射的吸引子。在此基礎上，Jacquin設計了第一個實用的基於方塊分割的分形圖像編碼器，他首先將原始圖像分割為值域子塊和定義域子塊，對於每一個值域子塊，尋找一個定義域子塊和仿射變換（包括幾何變換、對比度放縮和亮度平移），使變換後的定義域子塊最佳逼近值域子塊。隨後Fisher等提出了四象限樹編碼方案，採用有效的分類技術，極大的提高了編碼性能。隨著幾十種新演算法和改進方案的問世，分形圖像編碼目前已形成了三個主要發展方向：加快分形的編解碼速度、提高分形編碼質量、分形序列圖像編碼。

㈩ 壓縮編碼

在介紹圖象的壓縮編碼之前，先考慮一個問題：為什麼要壓縮？其實這個問題不用我回答，你也能想得到。因為圖象信息的數據量實在是太驚人了。舉一個例子就明白：一張A4(210mm×297mm) 幅面的照片，若用中等解析度(300dpi)的掃描儀按真彩色掃描，其數據量為多少？讓我們來計算一下：共有(300×210/25.4) ×(300×297/25.4)個象素，每個象素佔3個位元組，其數據量為26M位元組，其數據量之大可見一斑了。

如今在Internet上，傳統基於字元界面的應用逐漸被能夠瀏覽圖象信息的WWW(World Wide Web)方式所取代。WWW盡管漂亮，但是也帶來了一個問題：圖象信息的數據量太大了，本來就已經非常緊張的網路帶寬變得更加不堪重負，使得World Wide Web變成了World Wide Wait。

總之，大數據量的圖象信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現實的，這時就要考慮壓縮。

壓縮的理論基礎是資訊理論。從資訊理論的角度來看，壓縮就是去掉信息中的冗餘，即保留不確定的信息，去掉確定的信息(可推知的)，也就是用一種更接近信息本質的描述來代替原有冗餘的描述。這個本質的東西就是信息量(即不確定因素)。

壓縮可分為兩大類：第一類壓縮過程是可逆的，也就是說，從壓縮後的圖象能夠完全恢復出原來的圖象，信息沒有任何丟失，稱為無損壓縮；第二類壓縮過程是不可逆的，無法完全恢復出原圖象，信息有一定的丟失，稱為有損壓縮。選擇哪一類壓縮，要折衷考慮，盡管我們希望能夠無損壓縮，但是通常有損壓縮的壓縮比(即原圖象占的位元組數與壓縮後圖象占的位元組數之比，壓縮比越大，說明壓縮效率越高)比無損壓縮的高。

圖象壓縮一般通過改變圖象的表示方式來達到，因此壓縮和編碼是分不開的。圖象壓縮的主要應用是圖象信息的傳輸和存儲，可廣泛地應用於廣播電視、電視會議、計算機通訊、傳真、多媒體系統、醫學圖象、衛星圖象等領域。

壓縮編碼的方法有很多，主要分成以下四大類：(1)象素編碼；(2)預測編碼；(3)變換編碼；(4)其它方法。

所謂象素編碼是指，編碼時對每個象素單獨處理，不考慮象素之間的相關性。在象素編碼中常用的幾種方法有：(1)脈沖編碼調制(Pulse Code Molation，簡稱PCM)；(2)熵編碼(Entropy Coding)；(3)行程編碼(Run Length Coding)；(4)位平面編碼(Bit Plane Coding)。其中我們要介紹的是熵編碼中的哈夫曼(Huffman)編碼和行程編碼(以讀取.PCX文件為例)。

所謂預測編碼是指，去除相鄰象素之間的相關性和冗餘性，只對新的信息進行編碼。舉個簡單的例子，因為象素的灰度是連續的，所以在一片區域中，相鄰象素之間灰度值的差別可能很小。如果我們只記錄第一個象素的灰度，其它象素的灰度都用它與前一個象素灰度之差來表示，就能起到壓縮的目的。如248，2，1，0，1，3，實際上這6個象素的灰度是248，250，251，251，252，255。表示250需要8個比特，而表示2隻需要兩個比特，這樣就實現了壓縮。

常用的預測編碼有Δ調制(Delta Molation，簡稱DM)；微分預測編碼(Differential Pulse Code Molation，DPCM)，具體的細節在此就不詳述了。

所謂變換編碼是指，將給定的圖象變換到另一個數據域(如頻域)上，使得大量的信息能用較少的數據來表示，從而達到壓縮的目的。變換編碼有很多，如(1)離散傅立葉變換(Discrete Fourier Transform，簡稱DFT)；(2)離散餘弦變換(Discrete Cosine Transform，簡稱DCT)；(3)離散哈達瑪變換(Discrete Hadamard Transform，簡稱DHT)。

其它的編碼方法也有很多，如混合編碼(Hybird Coding)、矢量量化(Vector Quantize，VQ) 、LZW演算法。在這里，我們只介紹LZW演算法的大體思想。

值得注意的是，近些年來出現了很多新的壓縮編碼方法，如使用人工神經元網路(Artificial Neural Network，簡稱ANN)的壓縮編碼演算法、分形(Fractl)、小波(Wavelet) 、基於對象(Object Based)的壓縮編碼演算法、基於模型(Model –Based)的壓縮編碼演算法(應用在MPEG4及未來的視頻壓縮編碼標准中)。