分形压缩编码

㈠ 属于无损压缩的编码方法是（ ）。

霍夫曼（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及未来的视频压缩编码标准中)。