基于离散余弦变换DCT编码的数据压缩算法的研究与实现
With the great development of modern communications and information technology，digital information was explosive growth. In this process,data compression technology have been widely applied in various fields including scientific research，daily life and entertainment. As a main branch of data compression，the DCT（Discrete Cosine Transform）is regarded as one of the effective and efficient methods adopted in theoretical analysis. This paper is based on the DCT to study a small branch of the field of data compression — Image Compression
Image compression encoding is one of the key techniques in modern multimedia and communication field. DCT has been widely used in image compression and other fields due to its good energy compaction property and fast computation. DCT has been widely used in image compression and other fields due to its good energy compaction property and fast computation. In recent years, research on DCT analysis and processing operation has been very active. DCT is adopted in both JPEG (Joint Photography Experts Group) standard for still image compression and MPEG(Moving Picture Experts Group) standard for motion image compression, which has further promoted the development in DCT field.At the same time DCT based vector quantization image compression technique has been developed.
In this paper, a detailed study of image compression coding technology and DCT core algorithm; In addition I achieved the image compression based on DCT about the gray images in BMP(Bit map) under 8 compression ratios which using VC（Visual C++）language.
KEY WORDS data compression，image compression, discrete cosine transform, Joint Photography Experts Group, compression encoding
目录
摘要 I
ABSTRACT II
第一章绪论 1
1.1 研究背景 1
1.2 目的意义 2
1.3 研究现状 4
1.4 内容概况 5
第二章图象压缩技术 6
2.1 图象压缩技术分类 6
2.2 常用图象压缩技术 7
2.3 图象压缩国际标准 9
2.4 图像压缩评价方法 10
第三章离散余弦变换DCT算法研究 13
3.1 DCT简介 13
3.2 DCT算法 14
3.2.1一维离散余弦变换 DCT-I 14
3.2.2二维离散余弦变换DCT-II 15
3.2.3多维离散余弦变换 16
3.3 DCT的快速算法FDCT 16
3.3.1 利用FFT来实现FDCT 16
3.3.2 查表法实现二维FDCT 17
3.4 DCT的图象压缩编码 20
3.4.1 DCT编码 20
3.4.2 系数量化 21
3.4.3 重建图象 22
第四章 DCT图象压缩软件实现 23
4.1开发环境 23
4.2 实现功能 23
4.3 软件模块 23
4.4 模块实现 24
4.4.1 图象读取 24
4.4.2 DCT正变换 25
4.4.3 矩阵转置 27
4.4.4 压缩量化 27
4.4.5 DCT逆变换 29
4.4.6 程序流程图 30
4.5 界面设计 30
4.6 软件演示过程 33
4.7 结果分析 34
4.7.1 结果比较 34
4.7.2 结果分析 36
第五章结束语 38
5.1 总结 38
5.2 未来展望 38
参考文献 39
致谢 40
摘要
通讯与信息技术的发展突飞猛进，数字信息呈爆炸式增长。在这个过程中，数据压缩技术在人们的生活、工作与科研中扮演着必不可少的重要角色。作为数据压缩领域的一个重要分支，离散余弦变换（DCT）被理论上认为是一种很好的方法.本文正是基于DCT来研究数据压缩领域中的一个小的分支–图像压缩
图像压缩编码技术是现代多媒体及通信领域中的关键技术之一。离散余弦变换(DCT)由于其较好的能量压缩特性和快速算法，被广泛地应用在图像压缩等领域。近年来基于DCT变换分析、处理操作的研究十分活跃，特别是国际静态图像压缩标准JPEG和动态图像压缩标准MPEG中都采用了DCT变换，更加推动了这一领域的发展。因此基于DCT变换的图像编码压缩技术也同步发展起来。
本文详细研究了图像编码压缩技术和DCT的核心算法；并使用VC语言实现了对
BMP灰度图像在8种压缩比之下的基于DCT的图像压缩。
关键词数据压缩，图像压缩，离散余弦变换，JPEG 压缩编码
ABSTRACT
第一章绪论
1.1 研究背景
图像通信以其直观性、确切性、生动性的特点在多媒体通信中占有重要的地位。随着多媒体技术的发展，特别是Internet的发展，图像的实时传输日益成为计算机通信领域中倍受瞩目的问题[1]。大量图像的传输成为多媒体应用的瓶颈，因为图像和图像包含巨大数量的信息，其传输和存储需要很宽的带宽，这就需要昂贵的通信信道和硬件进行图像传输、存储和管理。以PAL制式为例，一幅图像包含720X578X24b it,一张容量为1.2M B的高密度软盘还存它不下，而实时图像每秒包含25帧图像，由此可以看出，数字化信息的数据量相当庞大，这么大的数据量无疑给存储器容量、通信干线信道传输率以及计算机处理速度都增加了极大的压力，单纯从扩大存储器容量和增加通信干线的比特率来解决这一问题是不现实的。数据压缩技术是行之有效的办法。
图像压缩一般通过改变图像的表示方式来达到，因此压缩和编码是分不开的。图像压缩不仅是必要的而且是可能的，因为图像数据是高度相关的，一幅图像的内部和图像序列中相邻的图像之间有着大量的冗余信息。这些冗余信息有时间冗余、空间冗余等，图像编码方法就是要尽可能的消除这些冗余信息，以降低表示图像所需的数据量。以静止图像画面为例，数字图像的灰度信号和色差信号在空域(x,y 坐标系)虽然属于一个随机场分布，但是它可以看成为一个平稳的马尔可夫场，即图像像素点在空域中的灰度值和色差信号值，除了边界轮廓外，都是缓慢变化。比如一幅人的头肩像图，背景、人脸、头发等处的灰度、颜色都是平缓改变。相邻像素的灰度和色差值比较接近，信息有较多的冗余。如何先排除冗余信息，再进行编码，使像素的平均比特数下降，以减少空域冗余进行数据压缩，这就是通常所说的图像图像的帧内编码。图像图像是沿时间轴方向的一个帧序列，其帧间图像的相关性也是很强的，通常采用运动估计和运动补偿的方法以减少时域的冗余信息，达到压缩图像数据的目的。
去掉图像中的各种冗余信息并不会影响人们对它们的识别和判断，因为人类的视觉系统是一种高度复杂的系统，它能从极为杂乱的图像中抽象出有意义的信息，并以非常精练的形式反映给大脑。人眼对图像中的不同部分的敏感程度是不同的，如果去除图像中对人眼不敏感或意义不大的部分，对图像的主观质量是不会有很大影响的。所以，允许图像编码有一定的失真也是图像可以压缩的一个重要原因。在许多应用场合，并不要求经压缩及复原以后的图像和原图完全相同，而允许有少量失真，只要这些失真并不被人眼所察觉，在许多情况下是完全可以接受的，这就给压缩比的提高提供了十分有利的条件。
此外，还可以利用先验知识实现图像编码。在某些特定的应用场合，编码对象的某些特性可预先知道。例如，在可视电话中，编码对象为人的头肩像，此时可以利用对编码对象的先验知识为编码对象建立模型，通过提取模型参数，对参数进行编码而不对图像直接进行编码，可以达到非常高的压缩比。
图像压缩技术无论是在民用上还是在军事上都有重要的应用价值。在民用上，若图像信号能以高压缩比在甚低比特下传输(小于64Kbps)，则人们在PSTN通信网、
移动通信网上即可实现图像通信，使通信网的频率利用率大大的提高，可以满足人们日益增长的多媒体业务的需求。在军事上的应用更为广泛，如前沿侦察、战场的可视电话、军事会议电视等。尤其在战争环境非常恶劣的条件下，信道容量很小，要实现图像通信，则需要更高压缩比的图像编码信号。
在实际应用中，图像编码技术研究有极其重大的理论意义和实用价值，它对促进多媒体通信的发展有非常重要的积极意义。采用先进的压缩编码算法将数字化的图像和音频信息的数据量压缩，既节省了存储空间，又提高了通信干线的传输效率，同时也使计算机实时处理和播放图像音频信息成为可能。
1.2 目的意义
数字化大潮中，数字图像传输的应用日趋广泛。数字图像通信有数字通信的一系列优点，如:可以中继传输和多次复制，不会造成噪声和非线性失真的累积:便于进行加密;便于用VLSI芯片实现，制作方便、成本低、可靠性高;便于和计算机联网等。但是在大规模的推广应用上却存在一定的障碍。这主要是因为数字图像的数据量非常巨大，若不经压缩，数字图像传输所需的高传输率和数字图像存贮所需的巨大容量将会让推广应用数字图像通信付出惊人的成本。以指纹库为例[2]，若以(512×512)xsbit的灰度图像来存贮一个手指的指纹，一个40万人的指纹库，每人十指，则共需I000GB 的存贮量。尽管随着技术的发展存储器件和信道的容量在逐渐增加，成本在逐渐降低，对存储容量和传输容量的压力有所缓解，但是真正使制约因素不再成为瓶颈的还是图像压缩编码技术的应用。图像压缩编码技术推动了各类图像通信系统的推广应用。它是各类图像信息传输、存贮产品的一项核心技术。
图像数据可以进行压缩有几方面的原因。首先，原始图像数据是高度相关的，存在很大的冗余度。数据冗余造成比特数浪费，消除这些冗余可以节约码字，也就达到了压缩的目的。大多数图像内相邻象素之间有较大的相关性，这称为空间冗余度。序列图像前后帧之间有较大的相关性，这称为时间冗余度。多光谱遥感图像各谱间有相关性，这称为频率域冗余度。其次，若用相同码长表示不同出现频率的符号也会造成比特数的浪费，这种浪费称为符号冗余度。如果采用可变长编码技术，对出现概率较高的符号用短码字表示，对出现概率低的符号用长码字就可以消除符号冗余度，从而节约码字。
允许图像编码有一定的失真也是图像可以压缩的一个重要原因。在许多应用场合，并不要求经压缩及复原以后的图像和原图完全相同，而允许有少量失真。只要这些失真并不被人所察觉，在许多情况下是完全可以接受的。这就给压缩比的提高提供了十分有利的条件。例如，人眼不能觉察亮度的细小变化。即存在视觉闭值，而且此闭值随着图像内容的变化而变化。在平坦区，闭值低，对失真敏感。在边缘和纹理区，对失真不敏感，这就是视觉掩盖效应。这种特性被广泛用来提高压缩比。
信息论的观点认为信源总是或多或少的含有这些自然冗余，这些冗余既来自信源本身的相关性，又来自信源概率分布的不均匀性[3]。图像作为信源，冗余大部分来自图像数据自身，小部分来自外界环境和主观因素。对于这些冗余，根据它对图像生成的影响程度来分，信息熵冗余和图像区域的相同性冗余是造成图像信息量大于其要表达的信息量的主要原因。图像压缩编码是在对数字图像进行大量统计分析，掌握和了解图像信息和统计特性的基础上，充分利用图像本身的相关性强的特点，寻求消除或减少相关性或改变图像信源概率分布不均匀性的方法，实现数据的压缩。换句话说就是以尽量少的比特数表征图像，同时保持复原图像
的质量，使它符合预定应用场合的要求。压缩数据量，提高比特有效性是图像压缩编码的首要目的。图像编码是一种信源编码，其信源是各种类型的图像信息。信息论发展中期，削斯特(Ksersern)通过实验方法，来估计自然图像的熵和冗余[4]。他使用了8幅不同的图像，每幅图像都是128 X 128个象素，每个象素为Obit(即16级灰度)。通过不断添加图像的重要信息部分，记录图像的失真程度，得出：
为编码效率: ，其中H(x)为原始图像的熵; 为实际编码的平均码长。熵就是每个符号的平均信息量。独立信源又叫无记忆信源，其特点是某个位置出现某符号的概率与其它位置上出现的符号概率无关。设信源的符号表为各符号出现的概率为，则此独立信源的熵为：
对图像压缩编码的研究属于信息论中信源编码范畴，其主要宗旨是利用图像信号的统计特性及人类视觉的生理及心理学特性对图像信号进行高效编码，并研究数据压缩技术，以解决数据量大的问题。一般来说，图像压缩编码的目的和意义就在于:
1、减少数据存储量。
2、降低数据率以减少传输带宽。
3、压缩信息量，便于特征抽取，为识别做准备.
1.3 研究现状
目前己成熟的压缩算法所达到的有效压缩比约为26倍，如果这个数字还能再提高三至四倍，则可以把电视信号经亚抽样及压缩挤入电话信道，其意义将十分巨大。然而这三至四倍的压缩比的提高(当然是在复原图像质量满足要求的前提下)难以用现有的技术框架实现，需要新的技术突破。目前己提出和正在进行研究的图像编码方法列举如下:
①多分辨率编码。最早提出的是金字塔编码，后来是子带编码(SubbandCoding)，现在是用小波变换进行图像编码。
②基于表面描述的编码方法(三角形逼近法)。
③模型编码。它可分为物体模型未知的物体基编码和物体模型已知的语义编码。
④利用人工神经网络的压缩编码。
⑤利用分形几何的图像编码(IFS).
⑥利用数学形态学的图像编码等等。
目前，从数据处理和数据压缩两方面来看，图像压缩处理技术的研究内容主要集中在:
1. 研究针对现有压缩算法已形成的大量压缩数据，如何克服压缩域的固有限制并充分挖掘压缩域的潜在优势，寻找与原始数据集分析处理操作相对应的对等(或近似对等)操作;
2. 设计新的图像压缩算法，该压缩算法应不仅能具有较高的压缩效率和重构质量，同时还能支持图像数据的分析处理以及检索等操作，即研究新的支持压缩域直接处理的图像压缩算法。
在多媒体系统中，图像信息占用相当大的存储空间，这对于计算机的存储、访问、处理以及在通信线路上的传输都带来巨大的负担。图像信息存在着大量的冗余，在多媒体技术中，图像压缩非常重要。图像压缩方法也可以分成两种类型：有损压缩和无损压缩
目前，基于DCT变换的分析、处理操作的研究都十分活跃。静止图像的压缩标准JPEG就采用了DCT变换，而大量的图像都采用国际标准进行压缩。
此外，国际标准化组织(ISO)对于二值图像制定了JBIG标准(Joint Bilevel Image Group)。JBIG可以支持很高的图像分辨率，常用的文件格式为l728×2376或2304×2896。JBIG采用累进操作方式，可以使具有不同分辨率的图像设备使用同一个压缩图像，可以方便地在一组图像中浏览，非常适于在分组网中传输。JBIG采用无损压缩技术，但它的压缩率比目前的传真标准(CCITTG3、G4标准)高得多.
1.4 内容概况
因为静态图像和预测误差信号两者具有非常高的空间冗余度，为降低空间冗余度最广泛地采用的频率域分解技术就是DCT。DCT将运动补偿误差或原画面信息块转换成代表不同频率分量的系数集。这有两个优点：其一，信号常将其能量的大部分集中于频率域的1个小范围内，这样一来，描述不重要的分量只需要很少的比特数；其二，频率域分解映射了人类视觉系统的处理过程，并允许后继的量化过程满足其灵敏度的要求。
本文研究了DCT的基本理论，介绍了DCT的应用，对各种变换编码的性能进行了逻辑上的分析比较。此外，本文着重研究DCT用于图像压缩的理论基础及基本算法，以及用其实现的图像压缩软件。
在文中：
第一章主要介绍了课题研究的背景、意义及现状。
第二章图像压缩算法和评价标准。
第三章介绍了变换编码和DCT的理论基础。
第四章研究了DCT用于图像压缩思想与设计方法。
第五章介绍了软件实现过程和结果分析实现。
最后是全文的总结
第二章图象压缩技术
2.1 图象压缩技术分类
图像压缩是数据压缩的一个小的分支，这里先简要介绍一下常用的数据压缩技术[5]有那些，在下表1.1中列出
表1.1常用的数据压缩技术
数据压缩无损压缩（熵编码）统计编码霍夫曼编码，游程编码，二进制编码等
算术编码
基于字典的编码，LZW编码等
其他编码完全可逆的小波分解+统计编码
有损压缩（熵压缩）特征提取分析/综合编码子带，小波，分形模型基等
量化其他
无记忆量化均匀量化，Max量化，压扩量化等
有记忆量化序列量化预测编码增量调制，线性预测，非线性预测，自适应预测，运动补偿预测等
其他方法序贯量化等
分组量化直接映射矢量量化，神经网络，方块截尾等
变换编码正交变换：KL，DCT，DFT，WHT等
非正交变换
其他函数变换等
如表1所示，众多的数据压缩技术按压缩的失真度可以分成两个主要类型:无损(lossless)压缩和有损(loss)压缩。
无损压缩是指对使用压缩后的数据进行重构，解压缩后得到的数据与原来的数据完全相同。无损压缩又可称作冗余度压缩、嫡编码、信息保持编码等，它主要用于要求重构的信号与原始信号完全一致的场合，在多媒体技术中一般用于文本、数据的压缩。许多实用的无损压缩技术可以归结成一大类统计编码方法，它们在一些有损压缩方法中也经常被用到。
有损压缩是指使用压缩后的数据进行重构，解压缩后得到的数据与原来的数据有所不同，但不会让人对原始资料表达的信息造成误解。有损压缩是有失真编码，是不可逆压缩，在信息论中又称为嫡压缩。有损压缩适用于重构信号不一定要和原始信号完全相同的场合。如图像、声音和动态图像等数据的压缩就可以采用有损压缩。
2.2 常用图象压缩技术
1.KLT
KL变换称全离散K-L变换。离散K-L变换~(DKLT)~是图像压缩和模式识别中常用的数学手段。它将图像看成是一些基本图像的线性组合，将原图像以基本图像的系数进行表达，有效的压缩了图像数据量，也以此提取图像的特征。但是在获取、传输得到的一幅图象中，总混杂有许多随机干扰因素，称为随机图象。K-L 变换是针对这类广泛的随机图象提出来的，当对图象施加了K-L变换以后，由变换结果而恢复的图像将是原图象在统计意义上的最佳逼近。
K-L变换的优点是相关性好在所与变换中最好，主要应用在数据压缩和图像旋转等方面，但是实现起来困难。
2.DCT
离散余弦变换（DCT-Discrete Cosine Transform），1974年由Ahmed和Rao提出，至今已有30年历史[6].此间,DCT编码已发展成为BMP、MPEG、H.26x等图像/图像编码标准中的核心.尽管Shapiro的EZW以及Said等人的SPIHT小波编码的成功应用,对传统的DCT编码提出了挑战,但Xiong等人利用嵌入式DCT块变换之间的直流相关性,以及对DCT后的系数进行策略性重组或层式DCT同样具有小波多分辨率图像的分解特性.此外,基于层次嵌入式DCT、形状自适应DCT、截短DCT、感兴趣区域支撑DCT以及形态DCT等改进形式的编码,都是将基于DCT 变换编码推向更高层次.就DCT改进的变换,以及DCT系数的应用,如利用DCT系数实现信息隐藏等,也使得基于常规的DCT变换编码有了更广阔的应用与发展空间。
DCT是一种空间变换，DCT变换的最大特点是对于一般的图像都能够将像块的能量集中于少数低频DCT系数上，这样就可能只编码和传输少数系数而不严重影响图像质量。DCT不能直接对图像产生压缩作用，但对图像的能量具有很好的集中效果，为压缩打下了基础。例如：一帧图像内容以不同的亮度和色度像素分布体现出来，而这些像素的分布依图像内容而变，毫无规律可言。但是通过离散余弦变换(DCT)，像素分布就有了规律。代表低频成份的量分布于左上角，而越高频率成份越向右下角分布。然后根据人眼视觉特性，去掉一些不影响图像基本内容的细节(高频分量)，从而达到压缩码率的目的。
类似于离散傅里叶变换(DFT for Discrete Fourier Transform),但是只使用实
数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)，在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型，其中4种是常见的)。最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。
离散余弦变换，尤其是它的第二种类型，经常被信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。这是由于离散余弦变换具有很强的”能量集中”特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程(Markov processes)的统计特性[7]时，离散余弦变换的去相关性接近于K-L变换(Karhunen-Loève 变换–它具有最优的去相关性)的性能。而且实现起来较为简单，运算速度快。
3.DFT
傅立叶变换变换的基本思想首先由法国学者傅里叶系统提出，所以以其名字来命名以示纪念。
概念讲解：离散傅立叶变换(DFT)
1.离散傅氏变换(DFT)
(1)正变换：
(2)反变换：
从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。
傅立叶变换属于调和分析的内容。”分析”二字，可以解释为深入的研究。从字面上来看，”分析”二字，实际就是”条分缕析”而已。它通过对函数的”条分缕析”来达到对复杂函数的深入理解和研究。从哲学上看，”分析主义”和”还原主义”，就是要通过对事物内部适当的分析达到增进对其本质理解的目的。比如近代原子论试图把世界上所有物质的本源分析为原子，而原子不过数百种而已，相对物质世界的无限丰富，这种分析和分类无疑为认识事物的各种性质提供了很好的手段。
在数学领域，也是这样，尽管最初傅立叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。”任意”的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类，这一想法跟化学上的原子论想法何其相似！奇妙的是,现代数学发现傅立叶变换具有非常好的性质,使得它如此的好用和有用,让人不得不感叹造物的神奇:
1. 傅立叶变换是线性算子,若赋予适当的范数,它还是酉算子;
2. 傅立叶变换的逆变换容易求出,而且形式与正变换非常类似;
3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;
4. 著名的卷积定理指出:傅立叶变换可以化复杂的卷积运算为简单的乘积运算,
从而提供了计算卷积的一种简单手段;
5. 离散形式的傅立叶变换可以利用数字计算机快速的算出(其算法称为快速傅立叶变换算法(FFT)).
正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。
2.3 图象压缩国际标准
1.PEG－静止图像压缩标准
国际标准化组织(ID)和国际电报电话咨询委员会(CCITT)联合成立的专家组JPEG(Joint Photographic Experts Group)经过五年艰苦细致地工作后，于1991年3月提出了ISO CDIO918号建议草案[8]:多灰度静止图像的数字压缩编码(通常简称为JPEG标准)。这是一个适用于彩色和单色多灰度或连续色调静止数字图像的压缩标准。它包括基于DPCM(差分脉冲编码调制、DCT(离散余弦变换)和Huffman编码的两个部分。JPEG标准实际上有三个范畴:
1.基本顺序过程Baseline Sequential processes) 实现有损图像压缩，重建图像质量达到人眼难以观察出来的要求。采用的是8×8像素自适应DCT算法、量化及Huffman型的墒编码器。
2.基于DCT的扩展过程(Extended DCT Based Process) 使用累进工作方式，采用自适应算术编码过程。
3.无失真过程(Losslesss Process)采用预测编码及Huffman编码(或算术编码)，可保证重建图像数据与原始图像数据完全相同。
其中的基本顺序过程是JPEG最基本的压缩过程:符合JPEG标准的硬软件编码/解码器都必须支持和实现这个过程。另两个过程是可选扩展，对一些特定的应用项目有很大实用价值。
2.MPEG-运动图象压缩标准
MPEG格式：它的英文全称为Moving Picture Expert Group，即运动图像专家组格式，家里常看的VCD、SVCD、DVD就是这种格式。MPEG文件格式是运动图像压缩算法的国际标准，它采用了有损压缩方法减少运动图像中的冗余信息，说的更加明白一点就是MPEG的压缩方法依据是相邻两幅画面绝大多数是相同的，把后续图像中和前面图像有冗余的部分去除，从而达到压缩的目的(其最大压缩比可达到200:1)。目前MPEG格式有三个压缩标准，分别是MPEG－1、MPEG－2、和MPEG－4，另外，MPEG-7与MPEG-21仍处在研发阶段。
MPEG－1：制定于1992年，它是针对1.5Mbps以下数据传输率的数字存储媒体运动图像及其伴音编码而设计的国际标准。也就是我们通常所见到的VCD制作格式。使用MPEG-1的压缩算法，可以把一部120分钟长的电影压缩到1.2GB左右大小。这种视频格式的文件扩展名包括.mpg、.mlv、.mpe、.mpeg及VCD光盘中的.dat文件等。
MPEG－2：制定于1994年，设计目标为高级工业标准的图像质量以及更高的传输率。这种格式主要应用在DVD/SVCD的制作(压缩)方面，同时在一些HDTV(高清晰电视广播)和一些高要求视频编辑、处理上面也有相当的应用。使用MPEG-2
的压缩算法，可以把一部120分钟长的电影压缩到4到8GB的大小。这种视频格式的文件扩展名包括.mpg、.mpe、.mpeg、.m2v及DVD光盘上的.vob文件等。MPEG－4：制定于1998年，MPEG－4是为了播放流式媒体的高质量视频而专门设计的，它可利用很窄的带度，通过帧重建技术，压缩和传输数据，以求使用最少的数据获得最佳的图像质量。目前MPEG-4最有吸引力的地方在于它能够保存接
近于DVD画质的小体积视频文件。另外，这种文件格式还包含了以前MPEG压缩标准所不具备的比特率的可伸缩性、动画精灵、交互性甚至版权保护等一些特殊功能。这种视频格式的文件扩展名包括.asf、.mov和DivX AVI等。
2.4 图像压缩评价方法
图像压缩技术的优劣主要是由压缩所能达到的压缩倍数、从压缩后的数据所恢复(重建)图像的质量和算法的复杂度、解码的速度等方面来衡量的。常用压缩比和计算复杂度来衡量算法性能。压缩比(CR)定义为原始数据量与压缩后量的比值，即:
压缩比=原始数据量/压缩后量 (2.12)
计算复杂度可以用算法处理一定量数据所需的基本运算次数来度量。如处理一帧有确定的分辨率和颜色数的图像所需的加法次数和乘法次数。
在传统的图像质量评价[9]方法中，有代表性的方法主要有两种:客观评价和主观评价。
1.主观评价
图像的最终接收者是人，因此，根据人的主观感觉对图像的优劣作出评定是重要的，也是目前国际上普遍采用的方法。主观评价的观察者可分为两类，一类是未受过训练，对图像质量评价并不内行的一般观众，这时得到的图像质量代表一般观众的平均感觉。另一类是专业人员，对图像质量的评价有丰富的经验，是训练有素的内行，他们能够对图象作出严格的判断，并能注意到图像某些细小的降质。主观评价大体上可分为两类:绝对评价和相对评价。在绝对评价中，观察者根据一些事先规定好的评价尺度或者自己的经验，对被评价的图像作出质量判断。绝对评价常用的评价尺度是”全优度尺度”，对质量的优劣以数字评分。表
2.1给出了图像质量的一种绝对评价。
表2.1图像质量的绝对评价
非常好的图象5分好的图象4分中等图象3分
差的图象2分非常差的图象1分
在相对评价中，由观察者将一批图像由好到坏进行分类，对图像进行互相比较后评出分数，相对评价常用”群优度尺度”，表2.2给出了图像质量的一种相对评价尺度。
表2.2图像质量的相对评价
一批中最好的图象7分好于该批平均水平的图象6分
稍好于该批平均水平的图象5分该批平均水平的图象4分
稍次于该批平均水平的图象3分次于该批平均水平的图象2分
一批中最差的图象1分
2.客观评价
客观评价是用恢复图像偏离原始图像的误差来衡量恢复图像的质量。客观的评价标准可以计算，并且有很多种。尽管人们希望它能和主观评价尽量一致，但目前还没有找到一种合乎主观评价的逼真公式。最常用的有均方误差(MSE)和峰值信噪比(PSNR)。
(1 ) 均方误差MSE
（2.13）
其中，是原始图像，表示复原图像
(2) 归一化均方误差
（2.14）
其中是原始图像，表示复原图像。M,N 分别为图像的总行数和总列数。
以上各式看起来直观、严格，但用它们求得的结果往往与人们主观视觉效果不一致。这是因为均方误差和峰值信噪比是从总体上反映原始图像和恢复图像的差别，并不能反映局部像点有较大灰度差别和较多像点有较小灰度差别等各种情况。显然，对图像中所有像点同样对待，不能反映人眼的视觉特性(HVS)。
通常，基于对随机误差进行统计平均的客观图像质量评价方法，没有考虑到人的视觉感知特性，而主观图像质量评价方法又往往受到观察者本身的知识背景、情绪以及疲劳程度等因素的影响，所得到的结果往往是值得怀疑的，因此，在实际的图像压缩算法设计中，往往同时使用主观评价和客观评价来综合的检验图像质量的好坏。
第三章离散余弦变换DCT算法研究
3.1 DCT简介
数据压缩是现代计算最重要的领域和工具之一。从获取数据到CD-ROM，从编码理论到图像处理，现代计算的许多层面都依赖于数据压缩。
90年代是多媒体计算机时代，而多媒体计算机的关键技术是数据压缩技术。数据库也离不开数据压缩技术，数据压缩可节省存储空间并使输入输出达到高速化。数据压缩技术的重要作用在图像信息的压缩方面表现得尤为明显。一幅600×400的彩色图像需要0.36MB的存储量。为了保证图像的播放质量，要求以每秒30幅的速度播放，1秒钟的活动图像需要10MB。１小时的连续活动图像，需要36000MB，这是难以实现的。因此，若存储大量的图像信息则必须大大提高系统的存储容量，例如采用大容量磁盘或光盘，但这仅仅是解决海量存储的一个办法。另一个办法是对图像信息进行压缩处理，因为图像数据具有可缩性，有大量所谓统计性质的多余度，从而产生生理视觉上的多余度，若去掉这部分图像数据并不影响视觉上的图像质量，甚至对图像的细节、实际的图像质量也无致命的影响，正因为如此，可以在允许保真度的条件下压缩待存储的图像数据，以大大节省存储空间，在图像传输时也大大减少信道的容量，光盘技术和数据压缩技术的发展为各种形态的大量传输提供了技术保证。CPU性能不断提高，也为数据压缩提供了有利条件。
1974年由Ahmed和Rao提出的离散余弦变换,至今已有30年历史.此间,DCT编码已发展成为BMP、MPEG、H.26x等图像/图像编码标准中的核心[10].尽管Shapiro 的EZW以及Said等人的SPIHT小波编码的成功应用,对传统的DCT编码提出了挑战,但Xiong等人利用嵌入式DCT块变换之间的直流相关性,以及对DCT后的系数进行策略性重组或层式DCT同样具有小波多分辨率图像的分解特性.此外,基于层次嵌入式DCT、形状自适应DCT、截短DCT、感兴趣区域支撑DCT以及形态DCT 等改进形式的编码,都是将基于DCT变换编码推向更高层次.就DCT改进的变换,以及DCT系数的应用,如利用DCT系数实现信息隐藏等,也使得基于常规的DCT 变换编码有了更广阔的应用与发展空间。
在信息世界迅猛发展的今天,人们对计算机实时处理图像信息的要求越来越高。如何在保证图像质量的前提下,同时兼顾实时性和高效性成了一个值得关注的问题。于是,对图像信息进行一定的压缩处理成为了一个不可或缺的环节。图像压缩是关于用最少的数据量来表示尽可能多的原图像的信息的一个过程。本文主要研究基于DCT 变换的有损压缩编码技术。离散余弦变换,简称DCT ,是一种实数
域变换,其变换核为余弦函数,计算速度快。DCT 除了具有一般的正交变换性质外,它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此,在对语音信号、图像信号的变换中,DCT 变换被认为是一种准最佳变换。近年颁布的一系列图像压缩编码的国际标准建议中,都把DCT 作为其中的一个基本处
理模块。而且对于具有一阶马尔柯夫过程的随机信号,DCT十分接近于Karhunen - Loeve 变换,也就是说它是一种最佳近似变换。
目前，离散余弦变换（DCT）是数字图像处理等许多领域的的重要数学工具，经常被信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。这是由于离散余弦变换具有很强的”能量集中”特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程(Markov processes)的统计特性时，离散余弦变换的去相关性接近于K-L变换(Karhunen-Loève 变换–它具有最优的去相关性)的性能，因此基于离散余弦变换（DCT）的图像压缩技术有着光明的前景
3.2 DCT算法
3.2.1一维离散余弦变换 DCT-I
正变换：
形式上来看，离散余弦变换一个线性的可逆函数 (其中 R 是实数集, 或者等价的说一个的方阵。离散余弦变换有几种变形的形式，它们都是根据下面的某一个公式把 n 个实数变换到另外n个实数的操作。
DCT-I
有些人认为应该将和乘以，相应的将和乘以。这样做的结果是这种 DCT-I 矩阵变为了正交矩阵(再乘一个系数的话), 但是这样就不能直接和一个实偶离散傅里叶变换对应了。
一个n = 5的对实数abcde的DCT-I型变换等价于一个8点的对实数abcdedcb(偶对称)的DFT变换，结果再除以2(对应的，DCT-II~DCT-IV相对等价的DFT有一个半个抽样的位移)。需要指出的是，DCT-I不适用于n < 2的情况(其它的DCT 类型都适用于所有的整数n)。
所以，DCT-I暗示的边界条件是: xk 相对于k = 0 点偶对称，并且相对于 k = n - 1 点偶对称; 对的情况也类似。
反变换
DCT-I的反变换是把DCT-I乘以系数。
3.2.2二维离散余弦变换DCT-II
正变换：
DCT-II大概是最常用的一种形式，通常直接被称为DCT。
有些人更进一步的将再乘以 (参见下面的DCT-III型的对应修改)。这将使得DCT-II成为正交矩阵 (再乘一个系数的话), 但是这样就不能直接和一个有半
个抽样位移的实偶离散傅里叶变换对应了。
所以，DCT-II暗示的边界条件是: xk 相对于点偶对称，并且相对于点偶对称; 对相对于m = 0 点偶对称，并且相对于 m = n 点奇对称。
反变换：
DCT-II的反变换是把DCT-II乘以系数2/n
基于DCT-II的常用性，下面再给出DCT-II的另一种变换形式：
数字图象f(u,v)可以看成一个u x v的矩阵，借助于二维DCT，可以将图象从空间域变换到DCT域（即KL平面）。以求和的形式定义的二维DCT为：
其IDCT为：
和离散傅里叶变换类似，变化前面的归一化系数仅仅是常规而已，改变这个系数并不改变变换的性质[11]。例如，有些人喜欢在DCT-II变换的前面乘以，这样反变换从形式上就和变换更相似，而不需要另外的归一化系数。
3.2.3多维离散余弦变换
多维离散余弦变换DCT一直是信号处理在视频和图像数据处理研究方面关注热点之一。当前的图像标准JPEG和视频编码标准MPEG、H系列都是以DCT为基础建立的，然而，这种变换涉及的结构复杂、计算量大，所以，为满足实时处理，需要研究好的计算方法。
近20年来，人们提出了许多DCT的计算方法。例如，有利用多项式变换和基于三角分解的二维DCT计算方法，以及基于递归和多项式变换的多维DCT计算方法，但在维数较大时，不适宜并行运算且难以保证计算精度。。
由清华大学戴琼海教授领导的课题组，在国家自然科学基金重点项目的资助下，针对上述问题进行研究，取得如下主要成果：
1、提出了一种新的基于矩阵Kronecker积因式分解的多维DCT快速方法。所用的规则结构有利于并行运算以及大规模集成电路VLSI的实现，保证计算精度。针对图像编码中的量化处理过程，提出了两种能减少计算的比例DCT的快速方法，使得图像编码效率进一步提高。
2、研究了在离散余弦变换域中进行块到相应子块的变换。图像和视频的处理涉及的数据块大小不同，为了在不同块之间进行快速数据转换，提出了三种变换：一是分别沿不同的维进行快速计算的行列方式，即，二是先恢复到时间域、再变换到频域的时频变换，第三种则是直接变换。其中，直接变换复杂度低、结构简单，是一种最理想的变换。以上研究为图像和视频的变换提供了重要理论依据。
3、提出了一种仅依赖快速离散余弦变换DCT的调制复重叠变换MCLT新方法。该方法在音频编码方面可以进行快速计算，有利于软件和硬件的实现，提高了编码效率。
该项研究系统地解决了多维离散余弦变换DCT的结构和计算方法问题，建立了相关理论基础，在国际重要杂志IEEE汇刊上发表文章5篇，申请发明专利6项，在国内外产生了一定影响。该成果可被应用于图像编码和音视频编码的建立，尤其是在标准转换、立体视频3DAV的研究中。
3.3 DCT的快速算法FDCT
3.3.1 利用FFT来实现FDCT
DCT变换是数字图像处理中重要的变换，很多重要的图像算法、图像应用都是基于DCT变换的，如JPEG图像编码方式。对于大尺寸的二维数值矩阵，倘若采用普通的DCT变换来进行，其所花费的时间将是让人难以忍受甚至无法达到实用。而要克服这一难点，DCT变换的快速算法无非是非常吸引人的。由于FFT算法的普便采用，直接利用FFT来实现DCT变换的快速算法相比来说就相对容易。FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散
傅立叶变换，可以说是进了一大步。
设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次”运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N2次运算。当N=1024点甚至更多的时候，需要
N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2（N/2）2=N+N2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种”一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
这种FDCT就是根据FFT的原理设计的算法，其理论思想完全一致。但是此种方法也有不足：计算过程会涉及到复数的运算。由于DCT变换前后的数据都是实数，计算过程中引入复数，而一对复数的加法相当于两对实数的加法，一对复数的乘法相当于四对实数的乘法和两对实数的加法，显然是增加了运算量，也给硬件存储提出了更高的要求。
3.3.2 查表法实现二维FDCT
我们知道,利用软件实现二维DCT 需要进行大量的矩阵运算和浮点运算,大量的乘法及加法运算严重影响了变换速度,为减少运算次数,缩短运算时间,人们作了不懈的努力,并提出了一些方法,但处理过程中数学运算仍然相当复杂。为此,本文提出一种有别于其它优化算法的快速二维DCT 实现方法,大大缩短了变换时间。将512 ×512 像素图像分解成4096 个8 ×8 子图像块进行处理,这样,每个子块用到的DCT 系数就是定值,用8bit 量化,将DCT 系数的乘积用一个表来表示,以后则可用查表代替复杂运算。利用查表法实现DCT 变换从理论上完全避免了乘法运算,即用存储容量换取了运算速度,降低了变换复杂性,而在目前硬件条件下,是完全可行的。
(1) 查表法[12]
二维正向DCT 定义如下:
数字图象f(u,v)可以看成一个u x v的矩阵，借助于二维DCT，可以将图象从空间域变换到DCT域（即KL平面）。
以求和的形式定义的二维DCT为：
IDCT为：
式中的f (x ,y) ,取值范围在0～255 之间,与DCT 系数相乘(对于每次变换来说,DCT系数为常数) ,将其结果构成一个表,系数表的数据个数为64 ×64 ×256 =1048576。若一个数据用4 字节的浮点数来表示,则一幅图像所占字节为4 ×1048576 = 4194304 ,约4M字节,明显太大。为此,下面给出减少存储空间的方法:通过对cos(2x + 1)uπ/16cos(2y + 1)vπ/16 分析,可以得到(2)
①若u = 0 ,v = 0 ,上式为1 ;
②若u = 0 ,v = 1 ,共8 个系数要计算:
cosπ/16,cos3π/16,cos5π/16,cos7π/16,cos9π/16,cos11π/16,cos13π
/16,cos15π/16?
③若u = 0 ,v = 7 ,8 个系数为:
cos7π/16,cos11π/16,cos3π/16,cos15π/16,cosπ/16,cos13π/16,cos5π
/16,cos9π/16
④若u = 1 ,v = 0 ,8 个系数为:
Cosπ/16,cos3π/16,cos5π/16,cos7π/16,cos9π/16,cos11π/16,cos13π
/16,cos15π/16?
⑤若u = 7 ,v = 7 ,公式(2) 有64 个系数,它们分别为:
cos7π/16,cos7π/16,cos11π/16,cos7π/16,?,cos9π/16,cos7π/16
cos7π/16,cos11π/16,cos11π/16,cosπ/16, ?,cos9π/16,cos11π/16
?
cos7π/16,cos9π/16,cos11π/16,cos9π/16, ?,cos9π/16,cos9π/16
若用cn*cm 表示cos (nπ/ 16) cos (mπ/ 16) (0 ≤n ,m≤15) ,其可能值将不超过nπ/ 16 , (n = 0 , ?,15) 的余弦值以及相互间乘积。若用C0 表示cos (0) ,C1 表示cos(π/ 16) , ?,C15 表示cos (15π/ 16) ,则式(2) 中所有可能值可用图1 表示,其中行、列均为C0 , ?,C15 ,矩阵各元素为行、列对应值的乘积。每个8 ×8 子块的三角函数乘积可排成如图1 所示的矩阵。
块1 块2
C0 C1 … C7 C8 C9 … C14 C15
C0 C0.C0 C0.C1 0.00 C0.C7 0.00 C0.C9 0.00 C0.C14 C0.C15
C1 C1.C0 C1.C1 0.00 C1.C7 0.00 C1.C9 0.00 C1.C14 C1.C15
C2 C2.C0 C2.C1 0.00 C2.C7 0.00 C2.C9 0.00 C2.C14 C2.C15
C3 C3.C0 C3.C1 0.00 C3.C7 0.00 C3.C9 0.00 C3.C14 C3.C15
C4 C4.C0 C4.C1 0.00 C4.C7 0.00 C4.C9 0.00 C4.C14 C4.C15
C5 C5.C0 C5.C1 0.00 C5.C7 0.00 C5.C9 0.00 C5.C14 C5.C15
C6 C6.C0 C6.C1 0.00 C6.C7 0.00 C6.C9 0.00 C6.C14 C6.C15
C7 C7.C0 C7.C1 0.00 C7.C7 0.00 C7.C9 0.00 C7.C14 C7.C15
C8 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
C9 C9.C0 C9.C1 0.00 C9.C7 0.00 C9.C9 0.00 C9.C14 C9.C15
C10 C10.C0 C10.C1 0.00 C10.C7 0.00 C10.C9 0.00 C10.C14 C10.C15
C11 C11.C0 C11.C1 0.00 C11.C7 0.00 C11.C9 0.00 C11.C14 C11.C15
C12 C12.C0 C12.C1 0.00 C12.C7 0.00 C12.C9 0.00 C12.C14 C12.C15
C13 C13.C0 C13.C1 0.00 C13.C7 0.00 C13.C9 0.00 C13.C14 C13.C15
C14 C14.C0 C14.C1 0.00 C14.C7 0.00 C14.C9 0.00 C14.C14 C14.C15
C15 C15.C0 C15.C1 0.00 C15.C7 0.00 C15.C9 0.00 C15.C14 C15.C15
块3 块4
图1 8 ×8 子块的余弦乘积值矩阵
由于三角函数值具有重复性和对称性,所以图1中,块1 ,2 分别与块3 ,4 值相同,且块1 与块2 三角对称,如图2。其中灰色部分为有用值,除去矩阵中重复的余弦乘积值,其系数个数减至72 个。所以,一个8×8 子块的系数表大小为72 ×4 ×256 = 73728 字节,256 是每个系数量化级数。将这72 个三角函数再乘上式(1) 中常数,建立一个DCT 系数表,以备查询
(2) 建立DCT 系数表
已经乘上常数1/ 4 的有用的72 个三角函数按图1中先后行顺序编排,每个系数分别乘上图像值f (x ,y) ,其值为0～255 ,并设为一组,共有72 ×256 个,其中,第i 组第j 个值= 第i 个三角系数×常数×j (0 ≤i ≤72 ,0≤j ≤255) 。这样就构成DCT 系数表COES ,其文件名为COES.DAT。
(3) 建立DCT 系数地址映射表
DCT 系数表建立后,不能直接查找,为此,我们建立了一个地址映射表,通过该表中地址,可以查找DCT系数表中相应系数。计算DCT 变换后的结果如下:
for (u = 0 ;u < 8 ;u + + )
for (v = 0 ;v < 8 ;v + + )
(3)
上式中共有64 个和项,COS 项随着u ,v 的确定而确定,这种关系称为映射。为此可建立一个地址映射表ADDRESS ,以文件ADDRESS.DAT 形式存储,其结构如图3 所示。
0 1 63 0 63 0 63 0
…………
u=0,v=0 u=0,v=1 u=0,v=2
图3 ADDRESS 结构图
表中共有64 ×64 = 4096 项,每项为整数,占两字节,共8192 字节,每64 项对应一组(u ,v) 值,从0 到63顺序编号,第0 项内容对应着f (0 ,0) 欲乘的三角函数在表COES 中所属一组起始位置,第1 项内容对应着f(0 ,1) 欲乘的三角函数在表COES 中所属一组起始位置,以此类推。计算时,先读入系数表COES. DAT 及地址映射表ADDRESS.DAT ,由u ,v 确定ADDRESS 中位置,依次取出后面64 个值,根据这些值找出COES 表中该系数组的起始位置,加上f (x ,y) 值,将这些数依次相加,就完
成了DCT 中某系数计算。此过程可用下式表示:
F(u ,v) = COES (ADDRESS (u ,v ,0) +f (0 ,0) ) + COES (ADDRESS (u ,
v ,0) +f (0 ,1) ) + ?+ COES (ADDRESS (u ,v ,63) +f (717) ) (4)
由于此种方法是将系数与图像所有可能值事先乘好放入表中,只要在运行时调入内存,再进行寻址取相加即可,几乎不进行乘法运算,所以与常规算法相比,速度得到较大提高。实际测试表明,查表法计算DCT所需时间是常规算法的48 %左右,并且查表法时间与变换对象个数成正比,这一点也优于其它方法。
3.4 DCT的图象压缩编码
3.4.1 DCT编码
任何连续的实对称函数的傅里叶变换中只含余弦项，因此余弦变换与傅里叶变换一样有明确的物理量意义。DCT是先将整体图像分成N×N像素块，然后对N×N 像素块逐一进行DCT变换。由于大多数图像的高频分量较小，相应于图像高频成分的系数经常为零，加上人眼对高频成分的失真不太敏感，所以可用更粗的量化，因此传送变换系数所用的数码率要大大小于传送图像像素所用的数码率。到达接收端后再通过反离散余弦变换回到样值，虽然会有一定的失真，但人眼是可以接受的。
一副原始输入图像经DCT 产生的输出矩阵有个特点:随着元素离DCT 系数越来越远,它的模就倾向于越来越小。这意味着通过DCT 来处理数据,已将图像的表示集中到输出矩阵的左上角的系数,而矩阵的右下部分系数几乎不包含有用信
息。
总之：DCT是先将整体图像分成N×N像素块，然后对N×N像素块逐一进行DCT 变换。由于大多数图像的高频分量较小，相应于图像高频成分的系数经常为零，加上人眼对高频成分的失真不太敏感，所以可用更粗的量化，因此传送变换系数所用的数码率要大大小于传送图像像素所用的数码率。到达接收端后再通过反离散余弦变换回到样值，虽然会有一定的失真，但人眼是可以接受的[11]。 N代表像素数，一般N=8，8×8的二维数据块经DCT后变成8×8个变换系数，这些系数都有明确的物理意义：U代表水平像素号，V代表垂直像素号。如当U=0，V=0时，F(0，0)是原 64个样值的平均，相当于直流分量，随着U、V值增加，相应系数分别代表逐步增加的水平空间频率分量和垂直空间频率分量的大小。
严格说DCT本身并不能进行码率压缩，因为64个样值仍然得到64个系数，如图4－2所示。这里给出了一个8×8像块的具体例子，经DCT变换后，比特数增加了。在这个例子中样值是8比特，从0~225得到的即直流分量的最大值是原来256的64/8倍，即0~2047，交流分量的范围是-1024~1023。只是在经过量化后，特别是按人眼的生理特征对低频分量和高频分量设置不同的量化，会使大多数高频分量的系数变为零[13]。一般说来，人眼对低频分量比较敏感，而对高频分量不太敏感。因此对低频分量采用较细的量化，而对高频分量采用较粗的量化。
3.4.2 系数量化
所谓量化，就是把经过抽样得到的瞬时值将其幅度离散，即用一组规定的电平，把瞬时抽样值用最接近的电平值来表示。量化时，把整个幅度划分为几个量化级（量化数据位数），把落入同一级的样本值归为一类，并给定一个量化值。量化级数越多，量化误差就越小，声音质量就越好。
在图象量化的过程中，先将图象从实域变换到频域，对于不同频率对应着不同的系数，把不同的系数按照一定的量化级取整变小，得到的新频域图就是经过压缩的图象的频域显示。量化的作用是在一定的主观保真图像质量的前提下,丢掉那些对视觉影响不大的信息,以获得较高的压缩比。然而,量化也是致使图像质量下降的最主要原因。
这里使用量化矩阵来实现量化。对于DCT输出矩阵中每一个元素,量化矩阵中的同一位置都有一个相应的量化值,范围是0～255。量化公式如下:
这里符号[ x ] 表示与x 最接近的整数。在DCT变换时使用量化矩阵很容易对图像的压缩质量进行控制,用户可根据具体的硬件存储容量和所需要的图像质量,选择合适的量化值。
3.4.3 重建图象
8 ×8 的矩阵进行系数量化后,DCT 系数会产生很多个为0 的值,而舍弃这些0 值,在解压缩图像时,并不会使画面质量显著下降,并且由经验可知,连续的0 值越多,编码效率越高。
因此,为积累图像中的0 值,首先采用游程编码算法(RLE ,Run - Length Encoding) 对量化后的交流系数进行压缩。其次,为了增加0 的游程长度,采用曲徊排序,即Z 型扫描对量化系数进行重新排序。最后的熵编码可采纳平均压缩比最高的Huffman编码。
第四章 DCT图象压缩软件实现
4.1开发环境
Visual C++是微软公司推出的软件开发工具，目前已经成为国内应用最广泛的高级程序设计语言之一。同其他软件开发工具相比，Visual C++具有以下优点：1.面向对象、可视化开发。提供了面向对象的应用程序框架MFC（Microsoft Foundation Class,微软基础类库），大大简化了程序员的编程工作，提高了模块的可重用性。Visual C++还提供了基于CASE技术的自动生成和维护工具–AppWizard、ClassWizard、Visual Studio、WizardBar等，帮助用户直观地、可视地设计程序的用户界面，方便地编写和管理各种类，维护程序源代码，从而提高了开发效率。
2.MFC类库已经成为事实上的工业标准类库，得到了众多软件开发商的支持。另外，由于许多的开发商都采用Visual C++进行软件开发，这样用Visual C++开发的程序就与其他应用软件有许多相似之处，易于学习和使用。
3. Visual C++封装了Windows的API（应用程序接口）函数、USER函数、KERNEL 函数、GDI函数，隐去了创建和维护窗口的许多复杂的例行工作，简化了程序。本软件就是利用了Visual C++的上述优点，实现了对BMP灰度图象的压缩。
4.2 实现功能
1. 可以对256*256的bmp灰度图像进行基于DCT的压缩；若打开的图像不是256*256的bmp图像，则会弹出对话框提示。
2. 可以选择8种压缩比（1：2，1：4，1：8，1：16，1：32，1：64，1：128，1：256）；
3. 可以在界面中对比显示压缩前与压缩后的图像；并显示其图象的大小。
4. 可以在界面中显示图象损失信息。在同一界面中跟原始图象和压缩图象进行比较。
4.3 软件模块
本程主界面模块由Visual C＋＋自动生成，在主界面模块中分别一一调用读取BMP灰度图模块、DCT正变换模块、量化模块、压缩比设置模块、DCT逆变换模块和矩阵转置模块，最后，调用图象显示模块，在界面中分别输出原始图象、压缩后的图象、图象损失信息以及压缩比和原始图象、压缩后图象的大小。
针对上图，这里仅讨论256*256 BMP灰度图像的压缩基本算法，图像压缩的目的在于以较少的数据来表示图像以节约存储费用，或者传输时间和费用。
4.4 模块实现
4.4.1 图象读取
此模块作用仅为实现256*256位图的读取。这里要注意的是，由于简化设计的考虑，设置的是仅对256*256的灰度位图读取。
首先分配内存空间（256*字节型数据所需要的大小）来存储图象：
Byte** ppbImage=(Byte**)malloc(256*sizeof(Byte*));//malloc
读入图象（256*256BMP灰度图）
ar.Read(&(MyBmp.Header),sizeof(BmpHeader));
if(CmpHeader()==0)
{ ar.Read(&(MyBmp.Palettes),sizeof(DWORD)*256);
ar.Read(&(MyBmp.Pix),sizeof(unsigned char)*256*256);
ReadOk=TRUE;
}
4.4.2 DCT正变换
DCT正变换是利用DCT算法将原始图象从实域变换到频域，这是实现图象压缩的第一步，也是关键一步。因为图象在实域内很难确定其数据的冗余值，所以量化过程无法实现。先将图象变换到频域这是为后面的实现量化做的一个关键的铺垫。
void CDCTDoc::DCT(double** array)
{
double buffer[256][256];
//先定义一个临时数组buffer[256][256]用来存放变换后的数据
int i,j,k;
for(i=0;i<=255;i++)
{ for(k=0;k<=255;k++)
{ buffer[k][i]=0;
for(j=0;j<=255;j++) //调用三个循环的套嵌结构来实现对数据的DCT正变换{ if(k==0)
buffer[k][i]+=array[j][i]/16;
// k==0时DCT正变换公式
else
buffer[k][i]+=array[j][i]*(double)cos((2*j+1)*pi*k/512)*cont;
// k>0时DCT正变换公式
}
}
}
for(i=0;i<=255;i++)
for(j=0;j<=255;j++)
array[i][j]=buffer[i][j]; //将变换后的频域值存放到数组array[i][j]中}
在对二维数组进行DCT运算时，为了运算的简便，根据二维DCT变换核可以分离的性质，将计算拆分为两个部分：先对二维数组进行行变换再调用矩阵转置模块将计算的值存储到该行中；然后同理对二维数组进行列变换。
DCT正变换流程图：
否
是
否
是
否
是
否
是
4.4.3 矩阵转置
因为在计算的过程中，对一行数据进行变换的结果是一组频域的列向量，而对一列数据变换时得到的是一组行向量。为了存储的方便，所以设置了一个转置模块。void CDCTDoc::transpose(double** array)
{
int i,j;
double buffer[256][256];
for(i=0;i<=255;i++)
for(j=0;j<=255;j++)
buffer[i][j]=array[j][i]; //将矩阵的行与列调换：
for(i=0;i<=255;i++)
for(j=0;j<=255;j++)
array[i][j]=buffer[i][j];
}
4.4.4 压缩量化
DCT按每一行和列变换后，产生的频域系数值便构成了一个2维坐标的频域图。由于能量主要集中在低频部分，就是说低频部分的系数值很大，主要集中在图的左上角，高频部分的系数值很小，一般分散在图象的右下角。
在量化时选择均匀量化，将系数值分解，便得到一个点阵图。图的左上角的点较为密集，右下角较为分散。取样的过程中就按照这一点阵图来取值。根据不同的压缩比，从左上到右下选取响应数量的值。
void CDCTDoc::compress(double** array)
{ int tmp = 256/comRate;//根据压缩比确定量化是的图象选择范围
int i,j;
for(i = tmp + 1; i < 256; i++)
{ for(j = tmp + 1;j < 256; j++)
{ array[i][j]=0;//将超过tmp范围的数值赋0值，即只选择了二维频域数组中0-tmp的数值；这便实现了量化
}
}
将压缩後的数据写文件：
FILE* fp;
fp = fopen(”compressed”, “wb”);
for(i = 0; i < tmp + 1; i++)
{ for(j = 0; j < tmp + 1; j++)
{ unsigned char tempdata = (Byte)array[i][j];
fwrite(&tempdata,sizeof(tempdata),1,fp);
}
}
fclose(fp);//关闭文件
}
在量化时就按不同的压缩比直接将相应高频的部分忽略不计。
if(rad1->GetCheck()==1)
{ comrate = 2;
图像压缩编码方法
图像压缩编码方法综述 概述： 近年来, 随着数字化信息时代的到来和多媒体计算机技术的发展, 使得人 们所面对的各种数据量剧增, 数据压缩技术的研究受到人们越来越多的重视。 图像压缩编码就是在满足一定保真度和图像质量的前提下，对图像数据进行变换、编码和压缩，去除多余的数据以减少表示数字图像时需要的数据量，便于 图像的存储和传输。即以较少的数据量有损或无损地表示原来的像素矩阵的技术,也称图像编码。 图像压缩编码原理： 图像数据的压缩机理来自两个方面:一是利用图像中存在大量冗余度可供压缩；二是利用人眼的视觉特性。 图像数据的冗余度又可以分为空间冗余、时间冗余、结构冗余、知识冗余 和视觉冗余几个方面。 空间冗余：在一幅图像中规则的物体和规则的背景具有很强的相关性。 时间冗余：电视图像序列中相邻两幅图像之间有较大的相关性。 结构冗余和知识冗余：图像从大面积上看常存在有纹理结构，称之为结构 冗余。 视觉冗余：人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像 的变化并不都能察觉出来。 人眼的视觉特性： 亮度辨别阈值：当景物的亮度在背景亮度基础上增加很少时，人眼是辨别 不出的，只有当亮度增加到某一数值时，人眼才能感觉其亮度有变化。人眼刚 刚能察觉的亮度变化值称为亮度辨别阈值。 视觉阈值：视觉阈值是指干扰或失真刚好可以被察觉的门限值，低于它就 察觉不出来，高于它才看得出来，这是一个统计值。 空间分辨力：空间分辨力是指对一幅图像相邻像素的灰度和细节的分辨力，视觉对于不同图像内容的分辨力不同。 掩盖效应：“掩盖效应”是指人眼对图像中量化误差的敏感程度，与图像 信号变化的剧烈程度有关。 图像压缩编码的分类： 根据编码过程中是否存在信息损耗可将图像编码分为: 无损压缩：又称为可逆编码(Reversible Coding)，解压缩时可完全回复原始数据而不引起任何失真； 有损压缩：又称不可逆压缩(Non-Reversible Coding)，不能完全恢复原始数据，一定的失真换来可观的压缩比。 根据编码原理可以将图像编码分为: 熵编码：熵编码是编码过程中按熵原理不丢失任何信息的编码。熵编码基
数据压缩,算法的综述
数据压缩算法的综述 S1******* 许申益 摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及其改进。 关键字：数据压缩；数据存储；计算机通讯；多媒体技术 1.引言 数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的成果。 本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法的基本思想设计了一个文件压缩器，用Java 语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。 2数据压缩算法的分类 一般可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做适应性（adaptive）方法，相应的，静态方法又叫做非适应性方法（non-adaptive）。 静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的
《数据压缩与编码》课程教学大纲1
《数据压缩与编码》课程教学大纲 课程类型:专业限选课课程代码: 课程学时: 46学分: 2 适用专业:电子信息工程专业 开课时间: 三年级二学期开课单位: 电气与电子工程学院 大纲执笔人: 吴德林大纲审定人:杨宁 一、课程性质、任务： 人类社会已进入信息时代，网络是信息时代的重要产物，大量数据的存贮、处理特别是传输，是影响网络系统效率的重要因素之一，数据压缩技术对提高网络通信能力和效率提供了有力的支持。课程的目的在于学习数据通信基本原理和了解数据通信网络。 通过本课程的学习，学生能够掌握数据压缩的基本知识、基本方法；掌握数据压缩技术及经典算法，包括信源的数字化方法、基本的统计编码方法、预测编码的理论与实现方法、HUFFMAN方法、算术编码方法、字典压缩技术、文本压缩技术、图像压缩技术；理解和实验基本图像JPEG压缩编码或EZW/SPIHT压缩编码。 二、课程教学内容 1）教学内容、目标与学时分配 (一)理论教学部分
2、实验要求指：必做或选做 2) 教学重点与难点 1、重点：数据压缩的基本概念、数据压缩的常用方法与算法，数据编码技术、图像压缩技术以及视频压缩技术。。 2、难点：视频压缩与小波分析技术 三、课程各教学环节的基本要求 1）课堂讲授： 多媒体、PPT课件 2）实验（实训、实习）：
3）作业： 问答题，计算题 4）课程设计： 5）考试 5.1 考试方法：（考试；考查；闭卷；开卷；其它方法） 闭卷考试 5.2 各章考题权重 第一章 5% 第二章 10% 第三章 10% 第四章 20% 第五章 20% 第六章. 20% 第七章 10% 第八章 5% 5.3 考试题型与比例 Eg：填空：20% ；判断题：10% ；单项选择：20% ；问答题：40%；分析题：10% 四、本课程与其他课程的联系 先修课程： 微机原理与程序设计、C 语言程序设计、数据结构、算法设计与分析。 五、建议教材及教学参考书 教材：吴乐南著：《数据压缩（第3版）》，电子工业出版社，2012年 参考书：魏江力．JPEG2000图像压缩基础、标准和实践．电子工业出版社，2004
常用工具软件 多媒体数据压缩及编码技术
常用工具软件多媒体数据压缩及编码技术 在计算机获取原始的声音、图形图像以及视频影像时，其数据量是十分庞大的。如果数据不进行压缩处理，存放该数据文件时将十分困难，并且即使存储下来也是比较浪费存储介质的。例如，一张600MB的光盘也只能存储几十秒的真彩视频影像。 因此，用户需要对所获取的声音、图形图像以及视频影像数据进行压缩。其压缩主要包含下列两种方法。 ●无损压缩 多媒体原始信源数据存在大量的冗余，如动态视频图像帧内像素之间的空间相关性和帧与帧之间的时间相关性都很大，故而原始信源数据有很多的冗余，采用去掉冗余的压缩方法。 ●有损压缩 利用人的视觉对于边缘急剧变化不敏感和对图像的亮度信息敏感、对颜色分辨率弱的特点以及听觉只能听到20Hz~20KHz等特征实现数据压缩，舍弃一些非主要的细节，从而使由压缩数据恢复的图像、声音仍有令人满意的质量的方法。 数据压缩技术的研究已经有许多年了，从PCM编码理论开始，到现在的ADPCM、JPEG、MPEG-1、MPEG-2、H.261等，已经产生了多种针对不同用途的压缩算法、实现手段和相关的数字硬件及软件。目前，被国际社会广泛认可和应用的通用压缩编码标准大致有如下4种。 ●H.261编码 由CCITT（国际电报电话咨询委员会）通过的用于音频视频服务的视频编码解码器（也称Px64标准），它使用两种类型的压缩：一帧中的有损压缩（基于DCT）和用于帧间压缩的无损编码，并在此基础上使编码器采用带有运动估计的DCT和DPCM（差分脉冲编码调制）的混合方式。这种标准与JPEG及MPEG标准间有明显的相似性，但关键区别是它是为动态使用设计的，并提供完全包含的组织和高水平的交互控制。 ●JPEG编码 JPEG（全称是Joint Photogragh Coding Experts Group（联合照片专家组））是一种基于DCT 的静止图像压缩和解压缩算法，它由ISO（国际标准化组织）和CCITT（国际电报电话咨询委员会）共同制定，并在1992年后被广泛采纳后成为国际标准。 它是把冗长的图像信号和其它类型的静止图像去掉，甚至可以减小到原图像的百分之一（压缩比100:1）。但是在这个级别上，图像的质量并不好；压缩比为20:1时，能看到图像稍微有点变化；当压缩比大于20:1时，一般来说图像质量开始变坏。 ●MPEG编码 MPEG是Moving Pictures Experts Group（动态图像专家组）的英文缩写，实际上是指一组由ITU和ISO制定发布的视频、音频、数据的压缩标准。它采用的是一种减少图像冗余信息的压缩算法，它提供的压缩比可以高达200:1，同时图像和音响的质量也非常高。现在通常有三个版本:MPEG-1、MPEG-2、MPEG-4以适用于不同带宽和数字影像质量的要求。它的三个最显著优点就是兼容性好、压缩比高（最高可达200:1)、数据失真小。 ●DVI编码 DVI视频图像的压缩算法的性能与MPEG-1相当，即图像质量可达到VHS的水平，压缩后的图像数据率约为1.5Mb/s。为了扩大DVI技术的应用，Intel公司最近又推出了DVI算法的软件解码算法，称为Indeo技术，它能将为压缩的数字视频文件压缩为五分之一到十分之一。
五种大数据压缩算法
?哈弗曼编码 A method for the construction of minimum-re-dundancy codes, 耿国华1数据结构1北京:高等教育出版社,2005:182—190 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997. 冯桂,林其伟,陈东华.信息论与编码技术[M].北京:清华大学出版社,2007. 刘大有,唐海鹰,孙舒杨,等.数据结构[M].北京:高等教育出版社,2001 ?压缩实现 速度要求 为了让它(huffman.cpp)快速运行，同时不使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩过程 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 其次，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父
信源编码(数据压缩)课程课后题与答案(第二章)
信源编码 Assignment of CH2 1、（a）画出一般通信系统结构的组成框图，并详细说明各部分的作用或功能； 信源信源编码信道编码调制 噪声信道传输 , 信宿信源解码信道解码解调 图1、一般数字通信系统框图 各部分功能： 1、信源和信宿：信源的作用是把消息转换成原始的电信号；信宿的作用是 把复原的电信号转换成相应的消息。 . 2、信源编码和信源解码：一是进行模/数转换，二是进行数据压缩，即设法降低信号的数码率；信源解码是信源编码的逆过程。 3、信道编码和信道解码：用于提高信道可靠性、减小噪声对信号传输的影响；信道解码是信道编码的反变换。 4、调制和解调：将信息调制为携带信息、适应在信道中传输的信号。数字 " 解调是数字调制的逆变换。 5、信道：通信的通道，是信号传输的媒介。 （b）画出一般接收机和发射机的组成框图，并分别说明信源编解码器和信道编 解码器的作用； … 高频振荡器高频放大调制高频功放天线
" 音频功放 信 号 图2、一般发射机框图（无线广播调幅发射机为例）
天线 信号放大器混频器解调器音频放大器 信 号 本地振荡器 图3、一般接收机框图（无线广播调幅发射机为例） 信源编解码器作用：它通过对信源的压缩、扰乱、加密等一系列处理，力求 用最少的数码最安全地传输最大的信息量。信源编解码主要解决传输的有效性问题。 信道编解码器作用：使数字信息在传输过程中不出错或少出错，而且做到自 动检错和尽量纠错。信道编解码主要解决传输的可靠性问题。 （c）信源编码器和解码器一般由几部分组成，画出其组成图并给以解释。 信源编码器 时频分析量化熵编码 信道传输 时频分析反量化熵解码 信源解码器 图 4、信源编解码器框图 时频分析部分：信源编码器对信源传送来的信号进行一定方法的时域频域分析，建立一个能够表达信号规律性的数学模型，从而得知信号中的相关性和多余度，分析出信号数据中可以剔除或减少的部分（比如人感知不到的高频率音频信号或者看不见的色彩信号等等），以决定对后续数据的比特分配、编码速率等处理问题。 量化部分：根据时频分析的结果，为了更加简洁地表达利用该模型的参数， 减少精度，采取相应量化方法对信号进行量化，减小信号的多余度和不相关性，
栅格数据存储压缩编码方法
栅格数据存储压缩编码方法 栅格数据存储压缩编码方法主要有：（1）.链式编码（2）.行程编码（3）.块式编码（4）.四叉树编码 （1）.链式编码：由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，南＝3，西＝2，北＝1等，还应确定某一点为原点。（2）.行程编码：只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数，即按（属性值，重复个数）编码 （3）.块式编码：块式编码是将行程编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。 （4）.四叉树编码而块状结构则用四叉树来描述，将图像区域按四个大小相同的象限四等分，每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，无论分割到哪一层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性时，则停止继续分割。否则就一直分割到单个像元为止。而块状结构则用四叉树来描述。按照象限递归分割的原则所分图像区域的栅格阵列应为 2n×2n（n为分割的层数）的形式。下面就着重介绍四叉树编码。 四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n×2n像元阵列的区域，逐步分解为包含单一类型的方形区域，最小的方形区域为一个栅格像元。图像区域划分的原则是将区域分为大小相同的象限，而每一个象限又可根据一定规则判断是否继续等分为次一层的四个象限。其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的几种地物时，则不再继续划分否则一直分到单个栅格像元为止。 所谓四叉树结构，即把整个2ｎ×2ｎ像元组成的阵列当作树的根结点，n 为极限分割次数，n＋1为四分树的最大高度或最大层数。每个结点有分别代表西北、东北、西南、东南四个象限的四个分支。四个分支中要么是树叶，要么是树叉。树叉、树叶用方框表示，它说明该四分之一范围全属多边形范围（黑色）或全不属多边形范围（空心四方块），因此不再划分这些分枝；树用圆圈表示，它说明该四分之一范围内，部分在多边形内，另一部分在多边形外，因而继续划分，直到变成树叶为止。 为了在计算机中既能以最小的冗余存储与图像对应的四叉树，又能方便地完成各种图形操作，专家们已提出多种编码方式。下面介绍美国马里兰大学地理信
数据压缩
一、名词解释 1、数据压缩：以最小的数码表示信源所发的信号，减少容纳给定消息集合或数据采样集合的信号空间。 2、数据压缩比：将压缩前每个信源符号（取样）的编码位数（mlog）与压缩后平均每符号的编码位数（l）之比，定义为数据压缩比。 3、均匀量化：把输入信号的取值域按等距离分割的量化称为均匀量化。 4、最优量化（MMSE准则）：使均方误差最小的编码器设计方法称为最小均方误差（MMSE）设计。以波形编码器的输入样值与波形解码器的输出样值之差的均方 误差作为信号质量的客观评判标准和MMSE的设计准则。（能使量化误差最小的所谓最佳量化器，应该是非均匀的。） 5、信息熵定义：信息量的概率平均值，即随机变量的数学期望值，叫做信息熵或者简称熵。 6、统计编码定义：主要利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配，叫做统计编码或概率匹配编码，统称熵编码。 7、变长编码：与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度码字来表示，这就叫做不等长编码或变长编码。 8、非续长码：若W中任一码字都不是另一个码字的字头，换句换说，任何一个码字都不是由另一个码字加上若干码元所构成，则W称为非续长码、异字头码或前缀码。 9、游程长度：是指字符（或信号采样值）构成的数据流中各字符重复出现而形成字符串的长度。 10、电视图像的取向：我国彩色电视制式采用逐行倒相的PAL-D制。 11、HVS的时间掩蔽特性：指随着时间变化频率的提高，人眼对细节分辨能力下降的特性。 12、HVS的空间掩蔽特性：指随着空间变化频率的提高，人眼对细节分辨能力下降的特性。 13、HVS的亮度掩蔽特性：指在背景较亮或较暗时，人眼对亮度不敏感的特性。 14、CIF格式：是常用的标准图像格式。是一种规范Y、Cb、Cr色差分量视频信号的像素分辨率的标准格式。像素。 15、SIF格式:是一种用于数字视频的存储和传输的视频格式。 16、压扩量化：由于低电平信号出现概率大、量化噪声小；高电平信号虽然量化噪声变大，但因为出现概率小，总的量化噪声还是变小了，从而提高量化信噪比。这种方法叫做压缩扩张量化。（压扩量化用一个非线性函数变换先将信号“压缩”后再均匀量化，它和非线性量化器完全等效。） 17、信号压缩系统的复杂度：指实现编解码算法所需的硬件设备量，典型地可用算法的运算量及需要的存储量来度量。 18、离散信源：被假设为由一系列随机变量所代表，往往用随机出现的符号表示，称输出这些符号集的源为信源，如果取值于某一离散集合，就叫做离散信源。 19、互信息量：对两个离散随机时间集X和Y，事件yj的出现给出关于xi的信息量，即为互信息量。 20、联合熵：两个变量X和 Y 的联合熵定义为：
多媒体数据处理中几种无损压缩算法的比较概要
119 摘要:为了使大容量的多媒体数据在网 络上有效的传输,必须对多媒体数据进行压缩。对多媒体数据压缩中的几种无损压缩方法进行了比较,并对每种方法用一个例子说明。 关键词:数据压缩;霍夫曼树;LZW;二 叉树 引言 随着网络发展的速度越来越快,视频, 音频的广泛应用使得大数据量的传输显得尤为重要,如何更快、更多、更好地传输与存储数据成为数据信息处理的首要问题。 在压缩算法中分为无损压缩和有损压 缩。相对于有损压缩来说,无损压缩的占用空间大,压缩比不高,但是它100%的保存了原始信息,没有任何信号丢失并且音质高,
不受信号源的影响,这点是有损压缩不可比拟的。而且随着时间的推移,限制无损格式的种种因素将逐渐被消除,比如说硬盘容量的急剧增长以及低廉的价格使得无损压缩格式的前景无比光明。 1、无损压缩的原理以及几种常见算法 本质上压缩数据是因为数据自身具有冗 余性。数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提 高传输效率和节约存储空间。 常见的无损压缩算法有,游长编码;香 浓-凡诺算法;霍夫曼算法;LZW算法;下面 详细介绍这些算法或编码步骤,并比较其优缺点。 2、游长编码 也叫行程编码,它是数据压缩中最简单 的一种方法。它的思想是:将图像一行中颜色值相同的相邻象素用一个计数值和该颜色值来代替。例如:aabbbccccdddddeeeeee对
其进行游长编码可得2a3b4c5d6e,可见其效 率很高。但它有两个致命缺点。 一:如果图象中每两个相邻点的颜色 都不同,用这种算法不但不能压缩,反而数 据量会增加,例如对abcdeabcde进行编码得 1a2b3c4d5e1a2b3c4d5e,可见数据量反而增 加了1倍。 二:容错性差。还是以aabbbccccddddde eeeee为例,如果在第二位a出错,例如丢失 了a,那么编码后结果为1a3b4c5d6e,虽然只 有一位发生了错误,但是在恢复数据时,将 和原始数据完全不同。 所以说游长编码在要压缩信息源中的符 号形成连续出现片段时才有效,并且它不是一种自适应的编码方式。 3、香浓-凡诺算法香浓-凡诺算法由贝尔实验室的Shannon 和MIT的Robert Fano开发的。它的编码步骤如下:一:根据符号出现的频率对符号进行排序二:递归的把符号分成两部分,每一部分中的符号具有相似的频率,直到所有的部分只有一个符号为止。这样,就得到一颗二叉树,我们把树中的左支赋为0,把树中的右支赋为1。那么从根节点到节点的路径即为它的编码。例如:对字符串abcccd编码。进行排序后为cabd。递归过程图1-图3。应当指出香浓-凡诺算法的编码结果并不是唯一的,例如在图1的时候可以交换左右子树的位置,在图3的时候也可以交换b,d的位置。香
数据快速压缩算法的C语言实现
价值工程 置，是一项十分有意义的工作。另外恶意代码的检测和分析是一个长期的过程，应对其新的特征和发展趋势作进一步研究，建立完善的分析库。 参考文献： [1]CNCERT/CC.https://www.wendangku.net/doc/0710668058.html,/publish/main/46/index.html. [2]LO R,LEVITTK,OL SSONN R.MFC:a malicious code filter [J].Computer and Security,1995,14(6):541-566. [3]KA SP ER SKY L.The evolution of technologies used to detect malicious code [M].Moscow:Kaspersky Lap,2007. [4]LC Briand,J Feng,Y Labiche.Experimenting with Genetic Algorithms and Coupling Measures to devise optimal integration test orders.Software Engineering with Computational Intelligence,Kluwer,2003. [5]Steven A.Hofmeyr,Stephanie Forrest,Anil Somayaji.Intrusion Detection using Sequences of System calls.Journal of Computer Security Vol,Jun.1998. [6]李华,刘智,覃征,张小松.基于行为分析和特征码的恶意代码检测技术[J].计算机应用研究，2011，28（3）：1127-1129. [7]刘威，刘鑫，杜振华.2010年我国恶意代码新特点的研究.第26次全国计算机安全学术交流会论文集，2011，（09）. [8]IDIKA N,MATHUR A P.A Survey of Malware Detection Techniques [R].Tehnical Report,Department of Computer Science,Purdue University,2007. 0引言 现有的压缩算法有很多种，但是都存在一定的局限性，比如：LZw [1]。主要是针对数据量较大的图像之类的进行压缩，不适合对简单报文的压缩。比如说，传输中有长度限制的数据，而实际传输的数据大于限制传输的数据长度，总体数据长度在100字节左右，此时使用一些流行算法反而达不到压缩的目的，甚至增大数据的长度。本文假设该批数据为纯数字数据，实现压缩并解压缩算法。 1数据压缩概念 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。常用的压缩方式[2,3]有统计编码、预测编码、变换编码和混合编码等。统计编码包含哈夫曼编码、算术编码、游程编码、字典编码等。 2常见几种压缩算法的比较2.1霍夫曼编码压缩[4]：也是一种常用的压缩方法。其基本原理是频繁使用的数据用较短的代码代替，很少使用 的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。 2.2LZW 压缩方法[5,6]：LZW 压缩技术比其它大多数压缩技术都复杂，压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串，如用数值0x100代替字符串ccddeee"这样每当出现该字符串时，都用0x100代替，起到了压缩的作用。 3简单报文数据压缩算法及实现 3.1算法的基本思想数字0-9在内存中占用的位最 大为4bit ， 而一个字节有8个bit ，显然一个字节至少可以保存两个数字，而一个字符型的数字在内存中是占用一个字节的，那么就可以实现2:1的压缩，压缩算法有几种，比如，一个自己的高四位保存一个数字，低四位保存另外一个数字，或者，一组数字字符可以转换为一个n 字节的数值。N 为C 语言某种数值类型的所占的字节长度，本文讨论后一种算法的实现。 3.2算法步骤 ①确定一种C 语言的数值类型。 —————————————————————— —作者简介：安建梅（1981-），女，山西忻州人，助理实验室，研究方 向为软件开发与软交换技术；季松华（1978-），男，江苏 南通人，高级软件工程师，研究方向为软件开发。 数据快速压缩算法的研究以及C 语言实现 The Study of Data Compression and Encryption Algorithm and Realization with C Language 安建梅①AN Jian-mei ；季松华②JI Song-hua （①重庆文理学院软件工程学院，永川402160；②中信网络科技股份有限公司，重庆400000）（①The Software Engineering Institute of Chongqing University of Arts and Sciences ，Chongqing 402160，China ； ②CITIC Application Service Provider Co.，Ltd.，Chongqing 400000，China ） 摘要：压缩算法有很多种，但是对需要压缩到一定长度的简单的报文进行处理时，现有的算法不仅达不到目的，并且变得复杂， 本文针对目前一些企业的需要，实现了对简单报文的压缩加密，此算法不仅可以快速对几十上百位的数据进行压缩，而且通过不断 的优化，解决了由于各种情况引发的解密错误，在解密的过程中不会出现任何差错。 Abstract:Although,there are many kinds of compression algorithm,the need for encryption and compression of a length of a simple message processing,the existing algorithm is not only counterproductive,but also complicated.To some enterprises need,this paper realizes the simple message of compression and encryption.This algorithm can not only fast for tens of hundreds of data compression,but also,solve the various conditions triggered by decryption errors through continuous optimization;therefore,the decryption process does not appear in any error. 关键词：压缩；解压缩；数字字符；简单报文Key words:compression ；decompression ；encryption ；message 中图分类号：TP39文献标识码：A 文章编号：1006-4311（2012）35-0192-02 ·192·
huffman编码译码实现文件的压缩与解压
数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日
目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16)
huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用hu ffm an编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。
多媒体数据压缩编码的国际标准
多媒体数据压缩编码的国际标准 国际标准化协会( ISO)，国际电子学委员会(IEC)，国际电信协会(ITU)等国际组织，于90年代领导制定了三个重要的多媒体国际标准，①JPEG标准，②H.261标准；③MPEG 标准。 我们在概述中只对这三个标准的制定做简单的介绍： 静态图像压缩编码的国际标准（JPEG）联合图像专家小组，多年来一直致力于标准化工作，他们开发研制出，连续色调、多级灰度、静止图像的数字图像压缩编码方法。这个压缩编码方法称为JPEG算法。JPEG算法被确定为JPEG国际标准，它是国际上，彩色、灰度、静止图像的第一个国际标准。JPEG标准是一个适用范围广泛的通用标准。它不仅适于静图像的压缩；电视图像序列的帧内图像的压缩编码，也常采用JPEG压缩标准。 在JPEG编码中用到了我们已学过的变换编码、预测编码和熵编码等原理和方法。这一章前面几节讲的内容是这一部分的基础。因此我们把重点放在JPEG的编码算法的具体实现上。 JPEG 标准定义了两种基本压缩算法：一是：基于DCT 变换有失真的压缩算法。二是：基于空间预测编码DPCM的无失真压缩算法。 我们将重点讲述基于DCT变换有失真的压缩算法。
1．基于离散余弦变换（DCT）的有失真压缩编码 （1）基于DCT的有失真编码处理过程图 基于DCT解码器处理步骤 首先来看"基于DCT的编码器处理步骤"图。从这幅图我们可以看出JPEG编码的处理过程，从总的来说是这样的：对于一幅图像首先将其分成许多个"8×8"的小块，也就是每个小块有8×8=64个像素；分成多少个小块要看图像的分辨率，分辨率高，分的块就多，分辨率小，分的块就少。然后对（每一个）8×8的块进行DCT变换（二维），经过DCT变换后就得到频域的64个离散余弦变换系数，得到64个离散余弦变换系数后，要对这64个系数进行量化，量化是根据"表说明"也就是量化表进行的，量化表是JPEG组织根据人的眼睛视觉特性规定好的，直接用量化表去除得到的64个系数就是量化，量化后得到的仍是一个（8×8）64的系数，而这一系数已是低频集中在左上角的一个8×8的系数了。最后再利用熵编码表对其进行熵编码，熵编码后的到的就是已压缩的图像数据。这是一个总的过程，我把刚才说的归纳如下：（2）基于DCT的有失真编码处理总过程：
数据压缩与编码技术
数据压缩与编码技术 ①多媒体数据压缩编码的种类 多媒体数据压缩方法根据不同的依据可产生不同的分类。通常根据压缩前后有无质量损失分为有失真（损）压缩编码和无失真（损）压缩编码。 无损压缩：利用信息相关性进行的数据压缩并不损失原信息的内容。是一种可逆压缩，即经过文件压缩后可以将原有的信息完整保留的一种数据压缩方式，如RLE压缩，huffman 压缩、算术压缩和字典压缩。 有损压缩：经压缩后不能将原来的文件信息完全保留的压缩，是不可逆压缩。如静态图像的JPEG压缩和动态图像的MPEG压缩等。有损压缩丢失的是对用户来说并不重要的、不敏感的、可以忽略的数据。 无论是有损压缩还是无损压缩，其作用都是将一个文件的数据容量减小，又基本保持原来文件的信息内容。压缩的反过程-----解压缩，将信息还原或基本还原。 压缩编码的方法有几十种之多，如预测编码、变换编码、量化与向量编码、信息熵编码、子带编码、结构编码、基于知识的编码等。其中比较常用的编码方法有预测编码、变换编码和统计编码。没有哪一种压缩算法绝对好，压缩效率高的算法，其具体的运算过程相对就复杂，即需要更长的时间进行转化编码操作。 图1.3 音频信号的压缩方法 ②多媒体数据压缩编码的国际标准 国际电活电报咨询委员会CCITT和ISO联合定的数字化图像压缩国际标淮，主要有三个标准：用于计算机静止图像压缩的JPEG、用于活动图像压缩的MPEG数字压缩技术和用于会议电视系统的H.261压缩编码。 （1）J PEG标准 联合图像专家小组，多年来一直致力于标准化工作，他们开发研制出，连续色调、多级灰度、静止图像的数字图像压缩编码方法。这个压缩编码方法称为JPEG（Joint Photographic Experts Group）算法。JPEG算法被确定为JPEG国际标准，它是国际上，彩色、灰度、静止图像的第一个国际标准。JPEG标准是一个适用范围广泛的通用标准。它不仅适于静图像的压缩；电视图像序列的帧内图像的压缩编码，也常采用JPEG压缩标准。采用JPEG标准可以得到不同压缩比的图像，在使图像质量得到保证的情况下，可以从每个像素24bit减到每个像素1bit甚至更小。
实时数据压缩算法(GE Historian Compression Methods)
申明：本文中思想及图片都是参照EVSystems（网址如下）说明文档，版权归其所有，鄙人只管翻译和归纳。要转载本文也请说明出处，谢谢！ https://www.wendangku.net/doc/0710668058.html, sfriedenthal@https://www.wendangku.net/doc/0710668058.html, 实时数据压缩算法（GE Historian Compression Methods） 一、GE Historian Compression Methods 1. CC：Collector Compression ‘X’表示丢弃的数，圆表示保留的数。 方法：选一个点为起始点，以此点为中心，在y轴方向规定一个‘Dead band’区域，在区域内的点丢弃，直到遇到一个不再区域内的点，该点作为新的起始点，从而设定新的‘Dead band’区域。 此方法的缺点是：不能丢弃‘保持斜率不变’的点，如图中‘Constant slope line’。 2. AC：Archive Compression（存档压缩） 此方法通过判断斜率区域来丢弃多余的点，可识别并丢弃‘保持斜率不变’的点，AC一般在CC之后使用。具体实现方法在下文中说明。 CC和AC组合实现实时数据压缩，统称为：GE Historian Compression Methods
二、OSI PI Swinging Door Comrpession（美国OSI公司：游泳门压缩） 方法：选一个点为起始点（存储点）如图中‘Archived Point’，图中‘New Point ’称为当前点。然后依次选取后面的点（做当前点）做平行四边形，如下图所示： 当产生的平行四边形不能容纳上个存储点到当前点之间的所有数据点时，即 有数据点落在当前平行四边形覆盖面积之外时，则将‘当前点’的前一个数据点保存，作为新的存储点，其他点舍弃。以此往复。如下图所示： 判断一个点是否在当前平行四边形覆盖面积之内的方法如下图（能看懂就不翻译了）： 该方法的缺点是：计算量大，CPU占时太多，程序实现复杂。 GE Historian Compression Methods和Swinging Door Comrpession不同之处在于:其丢弃点动作的触发条件不一样，它不计算一个点是否在平行四边形中，通过斜率范围来判断，即判断“存储点和但前点之间连线是否与他们中间各个点的dead band 线相交”，其判断方法及整体示意图如下两图所示：
数据压缩试题库
第一章 填空题： 1、信源编码主要解决传输的问题，信道编码主要解决传输的问题。 2、数据压缩的信号空间包括、、。 3、数据压缩按其压缩后是否产生失真可划分为 和两大类。 第二章 填空题： 1、脉冲编码调制包括、、三个步骤。 2、连续信号的多种离散表示法中，我们最常用的取样方法是。 3、若要将取样信号准确地恢复成原信号，取样频率必须满足定理。 4、黑白电视信号的带宽大约为5MHz，若按256级量化，则按奈奎斯特准则取样时的数据速率为。如果电视节目按25帧/s发送，则存储一帧黑白电视节目数据需内存容量。 5、量化器可分为和两大类。 6、量化器的工作特性可分为、、三个区域。 6、按照处理方法是否线性来判断，我们认为量化过程本身是。 7、我国数字电话网中压扩量化的对数函数采用曲线。 8、信号质量的主观度量方法中最常用的判决方法是。 9、对信号压缩系统的性能评价应从几个性能指标上综合评价，这些性能指标包括、、、。 简答题： 1、量化误差和噪声的本质区别是什么？ 2、简述压扩量化的工作过程？ 3、数据压缩中的“二次量化”是指什么？它和模数转换时的量化有什么区别？ 证明题：
1、试导出以均方误差最小定义的最佳量化方法中量化判决电平k d 和量化输出电平k y 的表达式。 2、证明M-L 量化器的最小量化误差为：{}{}∑-=+≤<-=1 012 2min J k k k k d x d p y x E ε 第三章 填空题： 1、离散无记忆平稳信源的冗余度隐含在 。 2、对于联合信源，其冗余度除了各自本身的冗余度外还隐含在 。 3、离散有记忆信源的的理论极限是 。 4、在限失真编码理论中，使限失真条件下比特数最少的编码称为 。 问答题： 1、什么是平均自信息量（信息熵），平均条件自信息量（条件熵）以及平均互信息量？它们之间有什么关系？ 2、简述率失真函数的基本含义，并指出它对信源编码的指导意义。 3、什么是最大离散熵？它对数据压缩有什么指导意义？ 证明题： 2、证明 ()()|H Y X H Y ≤，并简述它对数据压缩的意义。 3、证明：()()()Y |X H X H Y X I －＝；。 第四章 填空题： 1、统计编码主要是利用消息或消息序列 的分布特性，注重寻找 的最优匹配。 2、长度为L 1，L 2，…，L n 的m 进制唯一可译码存在的充分必要条件是 。
多媒体数据压缩编码的国际标准
第四章多媒体数据压缩编码技术 考核目的： 考核学生对多媒体数据压缩编码的基本原理和算法、数据压缩编码的分类和方法、多媒体数据压缩编码的国际标准等内容的理解和掌握。 考核的知识点： 什么是多媒体数据压缩、为什么信息能被压缩、常用的压缩编码和算法（统计编码、预测编码、变换编码）、多媒体数据压缩编码的国际标准JPEG、MPEG-1等内容。 考核要求： 掌握：数据压缩编码的方法、常用的压缩编码和算法、JPEG的原理和实现技术。 理解：量化的原理和量化器的设计、MPEG-1的原理和实现技术。 了解：其它的国际标准等。 4.1 多媒体数据压缩编码的重要性和分类 一．多媒体数据压缩编码的重要性 多媒体信息传送面临的最大难题是海量数据存储与传送电视信号数字化后的数据量问题，数据压缩是解决问题的重要途径。 二．多媒体数据压缩的可能性 1.空间冗余 2.时间冗余 3.信息熵冗余 ●信息量：指从N个相等的可能事件中选出一个事件所需要的信息度量和含量。 ●信息熵：指一团数据所带的信息量，平均信息量就是信息熵（entropy）。 4.结构冗余 图象有非常强的纹理结构。 5.知识冗余 图像的理解与某些基础知识有关。 6.视觉冗余 视觉冗余是非均匀、非线性的。 三．多媒体数据压缩方法的分类
1．按压缩方法分: (1). 有失真压缩 (2). 无失真压缩 2．编码算法原理分: （1）预测编码：PCM、DPCM、ADPCM等 （2）变换编码：傅里叶（DFT）、离散余弦（DCT）、离散正弦（DST）等 （3）统计编码：哈夫曼、算术等 （4）静图像编码：方块、逐渐浮现等 (5) 电视编码：幀内预测、幀间编码等 (6) 其他编码：矢量量化、子带编码等 4.2量化 一．量化原理 量化处理是使数据比特率下降的一个强有力的措施。 数据压缩编码中的量化处理，不是指A/D变换后的量化，而是指以PCM码作为输入，经正交变换、差分、或预测处理后，熵编码之前，对正交变换系数、差值或预测误差的量化处理。 量化输入值的动态范围很大，需要以多的比特数表示一个数值，量化输出只能取有限个整数，称作量化级，希望量化后的数值用较少的比特数便可表示。每个量化输入被强行归一到与其接近的某个输出，即量化到某个级。 量化处理总是把一批输入，量化到一个输出级上，所以量化处理是一个多对一的处理过程，是个不可逆过程，量化处理中有信息丢失，或者说，会引起量化误差（量化噪声）。 二．标量量化器的设计 1．量化器的设计要求 ●给定量化分层级数，满足量化误差最小。 ●限定量化误差，确定分层级数，满足以尽量小的平均比特数，表示量化输出。 三．量化方法： ●标量量化： 对于PCM数据，一个数一个数地进行量化叫标量量化。 分为：均匀量化、非均匀量化和自适应量化。 四．矢量量化