多媒体技术及应用
JPEG图像压缩算法及其实现
罗群书
0411102班
2011211684
一、JEPG压缩算法（标准）
(一)JPEG压缩标准
JPEG(Joint Photographic Experts Group)是一个由ISO/IEC JTC1/SC2/WG8和CCITT VIII/NIC于1986年底联合组成的一个专家组，负责制定静态的数字图像数据压缩编码标准。迄今为止，该组织已经指定了3个静止图像编码标准，分别为JPEG、JPEG-LS和JPEG2000。这个专家组于1991年前后指定完毕第一个静止图像压缩标准JPEG标准，并且成为国际上通用的标准。JPEG标准是一个适用范围很广的静态图像数据压缩标准，既可用于灰度图像又可用于彩色图像。
JPEG专家组开发了两种基本的静止图像压缩算法，一种是采用以离散余弦变换(Discrete Cosine Transform, DCT)为基础的有损压缩算法，另一种是采用以预测技术为基础的无损压缩算法。使用无损压缩算法时，其压缩比比较低，但可保证图像不失真。使用有损压缩算法时，其算法实现较为复杂，但其压缩比大，按25：1压缩后还原得到的图像与原始图像相比较，非图像专家难于找出它们之间的区别，因此得到了广泛的应用。
JPEG有4种工作模式，分别为顺序编码，渐近编码，无失真编码和分层编码，他们有各自的应用场合，其中基于顺序编码工作模式的JPEG压缩系统也称为基本系统，该系统采用单遍扫描完成一个图像分量的编码，扫描次序从左到右、从上到下，基本系统要求图像像素的各个色彩分量都是8bit，并可通过量化线性地改变DCT系统的量化结果来调整图像质量和压缩比。下面介绍图像压缩采用基于DCT的顺序模式有损压缩算法，该算法下的JPEG压缩为基本系统。
(二)JPEG压缩基本系统编码器
JPEG压缩是有损压缩，它利用了人的视觉系统的特性，将量化和无损压缩编码相结合来去掉视觉的冗余信息和数据本身的冗余信息。基于基本系统的JPEG压缩编码器框图如图1所示，该编码器是对单个图像分量的处理，对于多个分量的图像，则首先应将图像多分量按照一定顺序和比例组成若干个最小压缩单元（MCU），然后同样按该编码器对每个MCU各个分量进行独立编码处理，最终图像压缩数据将由多个MCU压缩数据组成。
图1 JPEG压缩编码器结构框图
JPEG压缩主要步骤如下：
（1）图像压缩预处理；
（2）正向离散余弦变换（FDCT）；
（3）DCT系数量化；
（4）编码。
(三)图像压缩预处理
图像压缩前进行预处理，主要包括对原图像颜色空间转换、大小的调整和采样、整理MCU 单元。JPEG压缩的对象是基于YUV颜色空间，对于其他颜色空间的图像数据要先应用相应的转换公式转换到YUV颜色空间。
由于后续图像分块及整理MCU单元的需要，对于原图像宽度和长度应当扩展为8的整数倍，针对YUV411、YUV420等需要降采样处理的图像则要求扩展为16的整数倍，JPEG标准建议通过复制每有一个分量最右边的列和最下面的行来进行扩展。通过对原图像的降采样，将可以减少部分图像数据，增加压缩比，由于人眼对亮度信号Y比较敏感，而对色差信号UV不敏感，因此可以对原图像色度信号进行降采样处理，而人眼却基本感觉不到图像的变化，JPEG压缩常用可处理降采样处理格式为YUV422、YUV411和YUV420，本文采用YUV411格式，该格式为每个像素都提取Y分量，而UV分量在水平方向上每4个像素采样一次。JPEG压缩的最小单元为MCU，对于未降采样的图像数据（非交织数据），一个MCU就是一个数据单元，而对于降采样的图像数据（交织数据），一个MCU就是一系列在该扫描中由分量的采样因子定义的数据单元。本文采用YUV411格式，则一个MCU将由Y分量水平4个8×8图像块、水平一个U分量和一个V分量8×8图像块组成。基本系统将按照从上到下、从左到右的顺序将原图像整理为若干个MCU，后续JPEG压缩就是对每个MCU中各分量的图像块分别进行压缩，所有MCU的排列顺序就是最终图像压缩数据的排列顺序。
(四)正向离散余弦变换（FDCT）
对每个8×8图像块进行FDCT之前，采样值应该先进行幅度值的位移，使之成为一个有符号的数，方法是将采样值减去，其中P为采样的精度，本文P取8位，幅度位移为128，即将每个采样点像素值减去128后再进行FDCT，FDCT的数学表达式为：
8×8图像块经过FDCT变换后得到8×8的频率系数数组，该数组位置系数称为直流系数（DC），其他63个系数称为交流系数（AC）。直接应用公式（3-1）进行计算其计算量较大，许多文献提出了该公式的优化计算方法，以提高运算效率，比较常见的是将该公式分解为两个一维的FDCT进行计算，分解后的公式为：
(五)DCT系数的量化
经过FDCT变换后的频率系数是一些浮点数，需进行均匀量化为JPEG可编码的整数系数，每一个FDCT变换后的频率系统使用一个量化器，每个量化器的步长Q(u,v)可由指定量化表给定，本文使用的量化表采用JPEG标准推荐的两个量化表，分别用于亮度和色差信号。
通过线性地改变量化表各元素数值可以控制图像压缩后的质量和压缩比。可通过对量化表各元素乘一个调整因子fa来进行量化表元素数值调整，设所需图像质量系数为Q，则调整因子fa的计算表达式为：
查看图片
量化表各元素的新数值为：
查看图片
由于量化表为8位存储，计算的新数值应限制在1～255范围内。
量化后的DCT系数为：
查看图片
量化取整造成一定的数据精度损失，与原图像数据产生差异，这是造成JPEG图像压缩存在一定失真的主要原因。通过改变Q的数值可以控制图像压缩比，一般而言，对中等复杂程度的彩色图像，对基本系统每8bit像素压缩到0.75～2bit时，解码恢复后的图像质量较好，可以满足大部分场合的应用。
（六）霍夫曼（Huffman）编码
JPEG压缩最后一个步骤就是对量化后的频率系数进行编码处理，该编码的熵编码过程采用了Huffman编码，Huffman编码是一种基于概率统计的无损压缩技术，该算法首先统计信源出现的概率，再根据统计结果，出现概率高的符号使用短即时码表示，出现概率低的用长即时码表示，以达到压缩数据的目的。应用标准霍夫曼编码对图像进行编码时效率很高，但需要对原始图像扫描两遍来统计每个像素值出现的概率和建立霍夫曼树并编码，数据压缩速度很慢。实际应用中，为了提高处理速度，信源编码值通常根据信源查找相应的编码表得出。Huffman码表以一个16字节的列表（BITS）规定，它包括长度从1到16的每一种码长的码字的数目，在列表后面紧跟着另外一个由8bit符号值组成的列表（HUFFVAL），该列表每一项被赋予一个Huffman码字，应用这两个列表可以获取可供信源查找Huffman编码值的码表。在基本系统中，编码器最多在每个扫描中分别使用两个DC系数的Huffman码表和两个AC系数的Huffman码表（亮度分量和色度分量使用不同的Huffman码表），本文使用JPEG 推荐的4个Huffman码表，这4个表都来自对大量视频图像的统计平均，如果没有特别的要求，采用这4个码表就可以获得满意的压缩效果。
（七）DC编码
在对量化后的系数进行熵编码之前，量化的直流系数被取出单独进行处理，对其进行差分预测编码（DPCM）。DC系数为图像数据块的样本均值，包含了图像大部分的能量，数值也较大，通过差分预测编码可进一步去除数据块间平均值之间的相关性。DPCM以同一个分量的前一个子块的量化直流系数DCi-1作为当前直流分量的预测值，然后再对预测误差DIFF 进行Huffman编码。计算DIFF的表达式为：
查看图片
对DIFF的Huffman编码过程为：
（1）根据DIFF值查幅度值分类表3-1取得差值幅度类别号SSSS和DIFF值实际保存的二进制码流CODE(DIFF)；
查看图片
（2）根据标准DC系数Huffman码表计算得到的Huffman编码表查出SSSS值的Huffman 编码值HCODE（SSSS）；
（3）将SSSS的Huffman编码值和DIFF的实际保存值合并得到DC系数编码值HCODE（SSSS）CODE(DIFF)，完成DC系数的编码。
（八）AC编码
对量化后的63个AC系数可以观察到有许多系数值为零，首先通过对AC系数的之字形（Zig-Zag）扫描和0-RLE行程编码压缩掉这些0系数。按照如图3-2所示的扫描次序将二维
的AC系数按一维次序读出可将AC系数转换成Zig-Zag序列，该转换可以增加行程中连续的0系数值个数。
查看图
片
图2 Zig-Zag扫描次序
0-RLE行程编码依次遍历Zig-Zag序列，当遍历到不为零的系数VAL（AC）时，计算该系数前面零的个数NUM（ZERO），然后用（NUM(ZERO),VAL（AC））进行表示，两部分刚好占用一个byte（分别占用4bit），对整个序列应用该方式进行表示。如果最后一个非零的AC 系数不是序列的最后一个则在最后应加上结束标记EOB，EOB通常为（0，0）。当序列中包含16个连续的零时则用（15，0）进行表示，可用多个（15，0）来表示多个16个连续的零。
最后再对0-RLE行程编码后的序列以（NUM(ZERO),VAL（AC））为单元进行Huffman编码，编码过程如下：
（1）按序列顺序先后取出一个（NUM(ZERO),VAL（AC））单元，对VAL（AC）查幅度值分类表取得幅度类别号SSSS和VAL（AC）值实际保存的二进制码流CODE（VAL（AC））；
（2）再根据标准AC系数Huffman码表计算得到的Huffman编码表查出（NUM（ZERO），SSSS）的Huffman编码值HCODE（（NUM（ZERO），SSSS））；
（3）组合HCODE（（NUM（ZERO），SSSS））和CODE（VAL（AC））得到（NUM(ZERO),VAL （AC））单元的最后编码；
（4）重复步骤（1）、（2）、（3）对其他（NUM(ZERO),VAL（AC））单元进行编码完成AC 系数的编码。
（九）压缩数据BIT码流整理
将DC编码和AC编码的码流组合后便得到8×8图像块的JPEG压缩Bit码流，按照同样的步骤对每个MCU图像块进行编码，最后对压缩数据Bit码流以8位为单元进行存储，同时为了区别压缩数据与标记段（首字节为0xFF的段），当8位二进制码流值为0xFF时则在其后填充一个0x00字节。此外，为了得到整数字节的熵编码字段，编码结束区域不完整字节通过填充“1”比特来实现完整化，如果这种填充中产生0xFF字节，则也在其后填充一个0x00
字节。整理完毕后将得到图像最终的JPEG压缩数据。
二JPEG文件组织结构
应用JPEG压缩算法得到图像的压缩数据仅为JPEG文件的一部分，完整的JPEG文件由标记段和压缩数据两部分组成，标记段记录了JPEG图像的格式和解码信息。主要标记段的结构及其含义如下：
（1）SOI（start of image）:该标记段记录了JPEG文件的开始，标记段的两个字节为0xFFD8。
（2）APPn（application）:该标记段是JPEG保留给application使用的标记码，而JFIF将文件的相关信息定义在此标记中,标记段开始2个字节为0xFFE0～0xFFEF。
（3）COM（comment）:该标记段对JPEG图像帧进行注释，标记段开始2个字节为0xFFFE。
（4）DQT（define quantization table）：该标记段包含了JPEG编解码时使用的量化表，标记段开始2个字节为0xFFDB，标记段第5个字节(Pa,Ta)为量化表标号，基本系统中，Pa=0，Ta=0~1，第6个字节开始为量化表数值。亮度信号和色差信号的量化表用不同的标号来区分。
（5）DRI（define restart interval）：该标记段定义重入间隔的MCU的个数n，即每n个MCU后就插入一个重启标记0xFFDi（i=0,1...7），如此循环，数值n占用标记段的第5、6两个字节，标记段开始2个字节为0xFFDi。每个重启标记0xFFDi后，以0xFFDi后的MCU作为首个MCU，DC分量重新进行差分计算，应用MCU间隔重启的方式可降低JPEG解码的错误率。
（6）DHT（define Huffman table）：该标记段包含JPEG编解码时使用的Huffman码表，标记段开始2个字节为0xFFC4，标记段第5个字节(Tc,Th)中，Tc=0表示DC系数使用的Huffman 码表，Tc=1表示AC系数使用的Huffman码表，Tk=0,1,2, (Tc,Th)构成Huffman码表编号（最多4个编号）。第5个字节开始后的16个字节为Huffman码表16字节的列表（BITS），紧跟着k字节为Huffman码表8bit符号值列表(HUFFVAL)，k的数值等于16字节的列表（BITS）数值之和。
（7）SOF（start of frame）：该标记段包含了大部分JPEG图片的信息，标记段开始2个字节为0xFFC0，第5个字节表示基本系统，第6、7字节表示图像的高度，第8、9字节表示图像的宽度，第10个字节Nf=1,3，1表示图像为灰度图，3表示彩色图。剩下的字节定义了图像各信号分量的采样因子和所使用的量化表编号。
（8）SOS（start of scan）：该标记段也包含了丰富的信息，标记段开始2个字节为0xFFDA，第5个字节数值为图像扫描成分的个数，后面几个字节定义了各个成分所使用的Huffman 码表的编号，剩下几个字节于基本系统无关，数值为0。
（9）EOI（end of image）：在图像JPEG压缩数据后面插入该标记段表示JPEG文件的结束，标记段的两个字节为0xFFD9。
有些标记段对JPEG文件是必需的，有些则可以不插入，而且插入的标记段除了SOI和EOI 位置是固定的，其它标记段（在压缩数据前面）可以在任意位置。本文完整的JPEG文件组织结构为：SOI，APP0，DQT（编号00），DQT(编号01)，DHT(编号00)，DHT(编号10)，DHT(编号01)，DHT(编号11)，SOF，SOS，图像JPEG压缩数据，EOI。
三JPEG压缩效果
原图像（BMP格式）大小取320×240，压缩质量Q 分别取1，50，100。Q越小图像失真度越高
查看图片
图3 基本系统下不同Q值的压缩对比图