第二章 图像压缩理论基础及开发流程
2.1 图像压缩
压缩的理论基础是信息论。从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去掉确定的信息(可推知的)，也就是用一种更接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量(即不确定因素)。
压缩可分为两大类：第一类压缩过程是可逆的，也就是说，从压缩后的图象能够完全恢复出原来的图象，信息没有任何丢失，称为无损压缩；第二类压缩过程是不可逆的，无法完全恢复出原图象，信息有一定的丢失，称为有损压缩。选择哪一类压缩，要折中考虑，尽管我们希望能够无损压缩，但是通常有损压缩的压缩比(即原图象占的字节数与压缩后图象占的字节数之比，压缩比越大，说明压缩效率越高)比无损压缩的高。
图象压缩一般通过改变图象的表示方式来达到，因此压缩和编码是分不开的。图象压缩的主要应用是图象信息的传输和存储，可广泛地应用于广播电视、电视会议、计算机通讯、传真、多媒体系统、医学图象、卫星图象等领域。
压缩编码的方法有很多，主要分成以下四大类：(1)象素编码；(2)预测编码；(3)变换编码；(4)其它方法。
所谓象素编码是指，编码时对每个象素单独处理，不考虑象素之间的相关性。在象素编码中常用的几种方法有：(1)脉冲编码调制(Pulse Code Modulation，简称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 Modulation，简称DM)；微分预测编码(Differential Pulse Code Modulation，DPCM)，具体的细节在此就不详述了。
所谓变换编码是指将给定的图象变换到另一个数据域(如频域)上，使得大量的信息能用较少的数据来表示，从而达到压缩的目的。变换编码有很多，如(1)离散傅立叶变换(Discrete Fourier Transform，简称DFT)；(2)离散余弦变换(Discrete Cosine Transform，简称DCT)；(3)离散哈达玛变换(Discrete Hadamard Transform，简称DHT)。
其它的编码方法也有很多，如混合编码(Hybird Coding)、矢量量化(Vector Quantize，VQ) 、LZW算法。在这里，我们只介绍LZW算法的大体思想。
2.2 JPEG
JPEG是第一个被广泛接受的单色和彩色静止图像压缩标准，它的名字源于“Joint Photographic Experts Group(联合图像专家组)”，它是由ISO/和CCITT协同工作的机构，这个机构的工作成果是ISO的国际标准ISO/IEC10918-1（连续色调静止图像的数字压缩和编码，digital compression and coding of continuous tone still images）和ITU-T的建议T.81。JPEG标准草案于1991年公布，1992年正式批准为国际标准，以后这个工作组的进一步增强和扩展形成了ISO 10918-3和ITU-T建议T.81。
JPEG是一种采用预测编码(DPCM)、离散余弦变换(DCT)以及熵编码，以去除冗余的图像和彩色数据的有损压缩格式，能够将图像压缩在很小的储存空间，图像中重复或不重要的资料会被丢失，因此容易造成图像数据的损伤。尤其是使用过高的压缩比例，将使最终解压缩后恢复的图像质量明显降低，如果追求高品质图像，不宜采用过高压缩比例。但是JPEG压缩技术十分先进，它用有损压缩方式去除冗余的图像数据，在获得极高的压缩率的同时能展现十分丰富生动的图像，也即可以用最少的磁盘空间得到较好的图像品质。而且 JPEG是一种很灵活的格式，具有调节图像质量的功能，允许用不同的压缩比例对文件进行压缩，支持多种压缩级别，压缩比率通常在10：1到40：1之间，压缩比越大，品质就越低；相反地，压缩比越小，品质就越好。比如可以把1．37Mb的BMP位图文件压缩至20．3KB。当然也可以在图像质量和文件尺寸之间找到平衡点。JPEG格式压缩的主要是高频信息，对色彩的信息保留较好，适合应用于互联网，可减少图像的传输时间，可以支持24bit真彩色，也普遍应用于需要连续色调的图像。
2.3 离散余弦变换
Ahmed 等人于70年代提出的离散余弦变换（DCT-Discrete Cosine Transform）压缩算法，降低视频信号的空间冗余度。
DCT将运动补偿误差或原画面信息块转换成代表不同频率分量的系数集，这有两个优点：其一，信号常将其能量的大部分集中于频率域的1个小范围内，这样一来，描述不重要的分量只需要很少的比特数；其二，频率域分解映射了人类视觉系统的处理过程，并允许后继的 量化过程满足其灵敏度的要求。
视频信号的频谱线在0-6MHz范围内，而且1幅视频图像内包含的大多数为低频频谱线，只在占图像区域比例很低的图像边缘的视频信号中才含有高频的谱线。因此，在视频信号数字处理时，可根据频谱因素分配比特数：对包含信息量大的低频谱区域分配较多的比特数，对包含信息量低的高频 谱区域分配较少的比特数，而图像质量并没有可察觉的损伤，达到码率压缩的目的。然而，这一切要在低熵(Entropy)值的情况下，才能达到有效的编码。能否对一串数据进行有效的编码，取决于每个数据出现的概率。每个数据出现的概率差别大，就表明熵值低， 可以对该串数据进行高效编码。反之，出现的概率差别小，熵值高，则不能进行高效编码。视频信号的数字化是在规定的取样频率下由A/D转换器对视频电平转换而来的，每个像素的视频信号幅度随着每层的时间而周期性地变化。每个像素的平均信息量的总和为总平均信息量，即熵值。由于每个视频电平发生几乎具有相等的概率，所以视频信号的熵值很高。 熵值是一个定义码率压缩率的参数，视频图像的压缩率依赖于视频信号的熵值，在多数情况下视频信号为高熵值，要进行高效编码，就要将高熵值变为低熵值。怎样变成低熵值呢？这就需要分析视频频谱的特点。大多数情况下，视频频谱的幅度随着频率的升高而降低。其中 低频频谱在几乎相等的概率下获得0到最高的电平。与此相对照，高频频谱通常得到的是低电平及稀少的高电平。显然，低频频谱具有较高的熵值，高频频谱具有较低的熵值。据此，可对视频的低频分量和高频分量分别处理，获得高频的压缩值。
由上可见，码率压缩基于变换编码和熵值编码两种算法。前者用于降低熵值，后者将数据变为可降低比特数的有效编码方式。在MPEG标准中，变换编码采用的是DCT，变换过程本身虽然并不产生码率压缩作用，但是变换后的频率系数却非常有利于码率压缩。 实际上压缩数字视频信号的整个过程分为块取样、DCT、量化、编码4个主要过程进行-----首先在时间域将原始图像分成N(水平)×N（垂直）取样块，根据需要可选择4×4、4×8、8×8、8×16、16×16等块，这些取样的像素块代表了原图像帧各像素的灰度值，其范围在139-163之间，并依序送入DCT编码器，以便将取样块由时间域转换为频率域的DCT系数块。DCT系统的转换分别在每个取样块中进行，这些块中每个取样是数字化后的值，表示一场中对应像素的视频信号幅度值。
离散余弦变换DCT（Discrete Cosine Transform）是数码率压缩需要常用的一个变换编码方法。任何连续的实对称函数的付立叶变换中只含余弦项，因此余弦变换与付立叶变换一样有明确的物理意义。DCT是先将整体图像分成N*N像素块，然后对N*N像素块逐一进行DCT变换。由于大多数图像的高频分量较小，相应于图像高频分量的系数经常为零，加上人眼对高频成分的失真不太敏感，所以可用更粗的量化。因此，传送变换系数的数码率要大大小于传送图像像素所用的数码率。到达接收端后通过反离散余弦变换回到样值，虽然会有一定的失真，但人眼是可以接受的。
2.4 图像的量化
图像的量化就是将取样后图像的每个样点的取值范围分成若干区间，并仅用一个数值代表每个区间中的所有取值。
量化时，量化值与实际值会产生误差，这种误差称为量化误差或量化噪声。可用信噪比来度量，但量化噪声与一般噪声是有区别的：
1)量化噪声由输入信号引起，可根据输入信号推测出来，而一般噪声与输入信号无任何直接关系。
2)量化误差是量化器高阶非线性失真的产物，是高阶非线性的特例。
量化分为标量量化和矢量量化。
在JPEG中将浮点型数表示的变换结果用标量量化后的整型数表示，随之而引起的误差在经过反向离散余弦变换而传递到图像，由于人眼对对这个误差几乎是察觉不到的，所以量化的过程是可行的。同时，为了达到更高的压缩比，又尽可能地保持原来图像的质量，JPEG通过多次实验，结合人眼的视觉特性，有针对性地设计相应的量化表。这种针对性是指对在图像中占有较大能量的低频成分，赋予较小的量化间隔和较多的比特以较为精确地表示原来的系数值，这样以达到尽量保持原始图像的视觉效果的前提下，获得较高的压缩比。
为了达到压缩数据的目的，对DCT系数需作量化处理。量化的作用是在保持一定质量前提下，丢弃图像中对视觉效果影响不大的信息。量化是多对一映射，是造成DCT编码信息损失的根源。JPEG标准中采用线性均匀量化器，量化过程为对64个DCT系数除以量化步长并四舍五入取整，量化步长由量化表决定。量化表元素因DCT系数位置和彩色分量的不同而取不同值。量化表为8x8矩阵，与DCT变换系数一一对应。量化表一般由用户规定JPEG标准中给出了参考值，并作为编码器的一个输入。量化表中元素为1到255之间的任意整数，规定了其所对应DCT系数的量化步长。DCT变换系数除以量化表中对应位置的量化步长，并去掉小数部分，其他变为零，从而达到了压缩的目的。
在JPEG量化过程中，量化表中的某个对应值用于相对应的系数值进行量化处理。量化过程就是简单地将变换系数除以量化阶后再取整。如果用C(k，1)表示量化后的系数，量化处理
从灵活性的角度出发，JPEG从没有规定量化表，仅是推荐了亮度和灰度两个量化表。根据具体要求可以构造专用的量化表，所推荐的量化表是针对灰度为8的图像源。使用该量化表，图像可达到失真不明显的主观质量。因此，只要线性地改变量化表中的量化阶就可控制重建图像质量以及相应的压缩比，在JPEG中通过调整一个公共因子来实现。
量化后的DCT变换值，低能量区域被量化成零，而高能量区域即低频区则保留下来，这样只要将保留下的低频值进行编码，就可以在允许误差的条件下存储图像的重要信息以用来还原图像。
量化是对经过FDCT变换后的频率系数进行量化,量化的目的是减小非“0”系数的幅度以及增加“0”值系数的数目,量化是图像质量下降的最主要原因。
2.5 游程编码
游程编码又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码。对于二值图有效。
行程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。 例如：5555557777733322221111111 行程编码为：（5，6）（7，5）（3，3）（2，4）（l，7）。可见，行程编码的位数远远少于原始字符串的位数。
在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字符串代替这些连续符号，可大幅度减少数据量。
行程编码分为定长行程编码和不定长行程编码两种类型。
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
2.6 哈夫曼编码
哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3比特。假设编码成000，001，010，011，100，101，110，111(称做码字)。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001，共享了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成011110001110011101101000000010010010111，共享了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。
上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。我们给出的编码能够保证这一点。
下面给出具体的Huffman编码算法。
(1) 首先统计出每个符号出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。
(2) 从左到右把上述频率按从小到大的顺序排列。
(3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。
(4) 重复(3)，直到最后得到和为1的根节点。
将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。
上面的例子用Huffman编码的过程如图9。1所示，其中圆圈中的数字是新节点产生的顺序。可见，我们上面给出的编码就是这么得到的。
目录
摘要 I
Abstract II
第一章 绪论 1
1.1 研究的动机和目的 1
1.2 研究的背景 1
1.3 研究内容 2
1.4 系统原理 2
1.4.1 色彩模型 2
1.4.2 DCT (离散余弦变换) 3
1.4.3排列 DCT 结果 4
1.4.4 量化 4
1.4.5 huffman 编码 5
1.5 可行性研究 7
1.5.1经济可行性 7
1.5.2 技术可行性 7
1.5.3 运行可行性 7
第二章 图像压缩理论基础及开发流程 8
2.1 图像压缩 8
2.2 JPEG 9
2.3 离散余弦变换 9
2.4 图像的量化 10
2.5 游程编码 12
2.6 哈夫曼编码 12
2.7 系统开发理论流程 14
2.7.1 颜色转换及采样 14
2.7.2 二维DCT变换 14
2.7.3 量化 14
2.7.4 游程编码，ZIGZAG扫描 15
2.7.5 哈夫曼编码 15
第三章 需求分析 16
3.1 需求分析的任务 16
3.2 系统功能分析 16
3.3 系统需求分析的步骤 16
3.4 系统功能模块设计 16
第四章 总体设计 17
4.1 系统设计的原则 17
4.2 设计目标 17
4.3 系统开发平台 17
4.3.1 软件配置 17
4.3.2 硬件配置 18
4.4 系统开发方法及技术路线 18
第五章 详细设计 20
5.1 代码设计 20
5.1.1 程序列表 21
5.2 公共模块(Module)设计 25
5.3 各模块的功能介绍 25
5.3.1各菜单功能 25
5.4 软件演示 25
第六章 测试与维护 30
6.1 测试 30
6.2 维护 30
总结 31
参考文献 32
致谢 33
附录 用户手册 34
1.1 系统概述 34
1.2 运行环境 34
1.3 使用说明 34
1.4 系统的遗留问题 34 致谢
此次毕业设计是在XX老师精心指导和其它同学的帮助下完成的。从硬件的设计到软件的编写，调试无不浸透着王老师的心血和其它同学的努力。在这几个月的时间里，老师不仅以她严谨的科学态度、广博的学识，而且以她宽厚待人、真诚正直的品德对学生言传身教，这些都将使我受益终身。借此机会，我向老师表示最崇高的敬意和衷心的感谢。论文的完成过程中得到了计算机系教研室其它老师广大同学无私地帮助，在此对他们表示感谢。
最后，衷心感谢各位专家在百忙之中对论文给予评审。由于作者水平和时间的限制，文中难免有不足，疏漏甚至错误之处，恳请给予批评指正，以便在今后的学习中进一步修正和完善，谢谢!!
附录 用户手册
1.1 系统概述
本系统研究JPEG的编码和解码过程。该程序的编码部分能把一张BMP格式的图象进行JEPG编码，压缩成以二进制形式保存的文件。
1.2 运行环境
1）软件配置
操作系统：Windows 2000 Sever或更高；
开发平台：Visual studio 2005。
2）硬件配置
CPU：PⅡ266或更高；
内存：64MB以上
硬盘：2G以上
显示器：VGA或更高；
1.3 使用说明
本系统可以读取*.bmp文档，然后另存为*.jpg文档。对于*.bmp文档进行按照JPG标准进行图像压缩。图像的压缩比可以调节（0%-100%）。压缩后即可保存为JPG文档。本系统支持读取*.bmp和*.jpg文档，并可以进行打印设置，打印。
1.4 系统的遗留问题
本系统没有通过相应的解码程序把图象解压缩出来，解码是编码的逆过程，由于时间紧迫没有完善此功能。系统菜单栏上存在的复制、剪贴和粘贴功能由于现在的系统不可以对图像进行编辑，所以没有开发。
| 
