基于离散余弦变换DCT编码的数据压缩算法的研究与实现.doc

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 CompressionImage 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目 录摘要 IABSTRACT II第一章 绪 论 11.1 研究背景 11.2 目的意义 21.3 研究现状 41.4 内容概况 5第二章 图象压缩技术 62.1 图象压缩技术分类 62.2 常用图象压缩技术 72.3 图象压缩国际标准 92.4 图像压缩评价方法 10第三章 离散余弦变换DCT算法研究 133.1 DCT简介 133.2 DCT算法 143.2.1一维离散余弦变换 DCT-I 143.2.2二维离散余弦变换DCT-II 153.2.3多维离散余弦变换 163.3 DCT的快速算法FDCT 163.3.1 利用FFT来实现FDCT 163.3.2 查表法实现二维FDCT 173.4 DCT的图象压缩编码 203.4.1 DCT编码 203.4.2 系数量化 213.4.3 重建图象 22第四章 DCT图象压缩软件实现 234.1开发环境 234.2 实现功能 234.3 软件模块 234.4 模块实现 244.4.1 图象读取 244.4.2 DCT正变换 254.4.3 矩阵转置 274.4.4 压缩量化 274.4.5 DCT逆变换 294.4.6 程序流程图 304.5 界面设计 304.6 软件演示过程 334.7 结果分析 344.7.1 结果比较 344.7.2 结果分析 36第五章 结束语 385.1 总结 385.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，若以(512512)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可以支持很高的图像分辨率，常用的文件格式为l7282376或23042896。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.KLTKL变换称全离散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-Love 变换它具有最优的去相关性)的性能。而且实现起来较为简单，运算速度快。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) 实现有损图像压缩，重建图像质量达到人眼难以观察出来的要求。采用的是88像素自适应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格式有三个压缩标准，分别是MPEG1、MPEG2、和MPEG4，另外，MPEG-7与MPEG-21仍处在研发阶段。MPEG1：制定于1992年，它是针对1.5Mbps以下数据传输率的数字存储媒体运动图像及其伴音编码而设计的国际标准。也就是我们通常所见到的VCD制作格式。使用MPEG-1的压缩算法，可以把一部120分钟长的电影压缩到1.2GB左右大小。这种视频格式的文件扩展名包括.mpg、.mlv、.mpe、.mpeg及VCD光盘中的.dat文件等。MPEG2：制定于1994年，设计目标为高级工业标准的图像质量以及更高的传输率。这种格式主要应用在DVD/SVCD的制作(压缩)方面，同时在一些HDTV(高清晰电视广播)和一些高要求视频编辑、处理上面也有相当的应用。使用MPEG-2的压缩算法，可以把一部120分钟长的电影压缩到4到8GB的大小。这种视频格式的文件扩展名包括.mpg、.mpe、.mpeg、.m2v及DVD光盘上的.vob文件等。MPEG4：制定于1998年，MPEG4是为了播放流式媒体的高质量视频而专门设计的，它可利用很窄的带度，通过帧重建技术，压缩和传输数据，以求使用最少的数据获得最佳的图像质量。目前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年代是多媒体计算机时代，而多媒体计算机的关键技术是数据压缩技术。数据库也离不开数据压缩技术，数据压缩可节省存储空间并使输入输出达到高速化。数据压缩技术的重要作用在图像信息的压缩方面表现得尤为明显。一幅600400的彩色图像需要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-Love 变换它具有最优的去相关性)的性能，因此基于离散余弦变换（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-IIDCT-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的快速算法FDCT3.3.1 利用FFT来实现FDCTDCT变换是数字图像处理中重要的变换，很多重要的图像算法、图像应用都是基于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 子图像块进行处理,这样,每个