|
JPEG学习笔记 陈硕 chenshuo@chenshuo.com 2005年11月 JPEG静态图像压缩的基本(baseline)算法分4个步骤[1]：1.按8×8象素分块2.离散余弦变换(DCT)3.量化4.熵编码 如果图片是彩色的，那么通常在第一步同时做色彩空间变换（RGB→YCbCr）。编码算法的框图见图1。  图1-JPEG编码器框图[1] 解码算法是编码算法的逆过程，框图见图2。  图2-JPEG解码器框图[1] JPEG标准[2]中还定义了无损压缩算法，不过基本没人用。除了baseline方式，还有progressive方式和hierarchical方式，本文只谈baseline方式。 目录 1算法描述与比较............................ 3 1.1分块及预处理...............................31.2变换编码..................................31.3量化.....................................61.4 行程编码与熵编码............................. 7 2实现细节................................ 8 2.1 ijg-jpeg实现分析..............................92.1.1预处理...............................112.1.2色彩转换..............................132.1.3扩展边界..............................142.1.4下采样...............................152.1.5JPEG压缩.............................172.1.6DCT与量化............................182.1.7“之”字型扫描与熵编码......................202.1.8量化表的缩放........................... 232.2 pvrg-jpeg实现分析............................. 26 3MATLAB实现..............................284参考资料................................28 1.算法描述与比较 1.1分块及预处理 JPEG可以压缩连续色调的灰度图像或彩色图像。对于灰度图像，每个象素可以是8-bit或12-bit的灰度值。baseline模式只要求处理8-bit图像（某些医学影像是12-bit的）。对于彩色图像，原则上可以将每个色彩分量成分看作一幅灰度图像，再进行压缩。不过由于人眼对于亮度变化比色彩变化更敏感，因此通常把RGB彩色信号变换为亮度和色差信号，并对色差信号进行下采样(downsampling)，这样可以提高压缩率。具体来讲，如果输入图像用RGB色彩表示，那么要把它变换到YCbCr色彩空间。每个象素(R,G,B)对应的(Y,Cb,Cr)的计算公式[3]是： YCbCr??=??0.29900.58700.1140?0.1687?0.33130.50000.5000?0.4187?0.0813??·??RGB??+??0128128??其中R,G,B和Y,Cb,Cr都是8-bit无符号整数，范围从0到255。色彩变换基本不影响图像的质量，最多由于整数运算的截断会使解码的图像与原图有些微差别。对于N×M的图像，色彩变换的计算复杂度为O(MN)。 JPEG压缩编码的第一步是将输入图像按从左到右，从上到下的顺序分成8×8大小的块。编码器本质上是对一连串8×8大小的灰度图像进行编码。对于彩色图像，还涉及到各色彩分量的交织(interleaving)与下采样处理，这留在“实现细节”一节中讨论。 如果原图像的宽度或高度不是8的整数倍，需要对原图扩大一圈，让宽度和高度都是8的倍数，然后进行压缩。当然，在生成的JPEG文件中要记录原始图像的大小，并把解压缩的（大了一圈的）图像剪裁到原大小。图像的填补和分块伴随离散余弦变换一同进行，可不计复杂度。 1.2变换编码 JPEG是一种基于变换的图像压缩算法，它采用了离散余弦变换(DCT)。基于变换的一般编码系统[9,Chap.8]的框图见图3。  “变换”的基本思想是，找到一组基，让图像在这组基下能量集中（少量系数值较大，其余系数接近0）。为了达到分离能量的目的，“变换”一般应是正交的。变换必须是可逆的（否则无法解码），因此变换本身不能压缩信息。不过通过随后的“量化”步骤将影响不大的系数略去，即可达到压缩的目的。 适合图像压缩的变换有很多种[9,Chap.8]，例如Karhunen-Loève变换(KLT，即主成分分析)、离散傅立叶变换(DFT)、离散余弦变换(DCT)、Walsh-Hadamard变换(WHT)等等。 在数据压缩方面最佳的变换是Karhunen-Loève变换，但实际系统中一般不用它。原因有两点：1.KLT得到的基与输入数据相关，意味着除了需要把系数传给解码器，还需要把基传给解码器。而且每个分块的基往往是不同的！这使得压缩效果大打折扣。2.KLT需要计算协方差矩阵的特征向量，计算量相当大。 DFT、WHT、DCT的基是固定的，与输入无关。在与输入无关的各种变换中，非正弦变换（如WHT）最容易实现，正弦变换（如DFT和DCT）的信息压缩能力更接近最佳的KLT方法。DFT是酉空间的正交变换（系数是复数），DCT是欧式空间的正交变换（系数是实数），因此DFT的系数比DCT多一倍。不过实数的DFT的系数是共扼对称的，实际所需的存储空间与DCT一样。 图像压缩的质量与所用的变换有关，也与分块的大小有关，最常采用的分块尺寸为8×8和16×16。图4说明了分块尺寸对变换编码重构误差的影响[9,p.478]。这里先计算各个分块的变换，截取75%的系数，然后对截取后的数组进行反变换，最后计算重构出的图像的误差。  从图4可以看出，据重构误差比较，DCT比DFT和WHT要好。DCT优于DFT的另外一个原因是[9,p.477]，由于DFT的边缘振铃现象（Gibbs现象），相邻图像分块之间的边界变得可见。DCT减少了这种效应，一是它的固有周期比DFT长一倍，二是它的边界不间断，见图5的比较。  图5-一维DFT(a)和DCT(b)的固有周期 因此为了兼顾压缩效果和计算复杂度，JPEG采用8×8的2-DDCT作为其核心，该变换的定义是 F(u,v)=14C(u)C(v) 7??x=07??y=0 f(x,y)cos(2x+1)uπ16cos(2y+1)vπ16其中当u,v=0时C(u),C(v)=1 √2 ，否则C(u),C(v)=1。在计算DCT之前，要 把输入图像的象素值减去128，让它的取值范围从[0,255]移到[?128,127]。 每个8×8的分块经过DCT运算得到64个系数。其中F(0,0)称为直流系数，其余63个系数称为交流系数。在典型的连续色调图像中，相邻象素之间的差别往往不大。这意味着空间频率的幅值集中在低频部分。对典型的8×8图像分块而言，大多数空间频率幅值是0或接近0，在编码时可忽略。DCT本身并不降低图像的质量，最多由于整数运算的舍入误差导致重构的图像与原始图像略有差别。 如果直接采用前面的公式计算，每个DCT系数F(u,v)需要64次乘法，计算全部64个DCT系数需要64×64=4096次乘法。计算DCT是整个JPEG压缩过程中最耗时的一步，很多人研究快速算法[5,Item25]，也有人往CPU增加新指令，使之便于DCT运算。基本思路是把2-DDCT分解为1-DDCT，再利用余弦函数的对称性来减少计算量。每个分块的计算复杂度为O(1)。对于N×M的图像，共有 N8??×??M 8??个分块，因此DCT这一步的计算复杂度为O(MN)。 1.3量化 量化(quantization)是JPEG压缩过程中惟一会大幅损失信息的步骤。64个DCT系数会用8×8的量化表进行均匀量化，量化表中的每个元素是1到255之间的整数，表示对应的DCT系数的量化步长。量化的作用在于降低DCT系数的精度，从而达到更好的压缩率。量化是多对一映射，因此是有损的，它是基于变换的编码器中导致信息损失的主要步骤，也是用户惟一能参与控制压缩质量的步骤。 量化的过程是将每个DCT系数除以对应的量化步长，并四舍五入为整数： FQ (u,v)=round F(u,v)Q(u,v)?? 反量化(dequantization)是把量化后的系数乘以对应的量化步长： F (u,v)=FQ(u,v)·Q(u,v)随后?F (u,v)将作为IDCT的输入。量化表理论上应该根据输入图像确定，目标是在基本不影响图像的视觉效果的前提下，尽量提高压缩率。量化步长越大，压缩率越大，图像质量越低。JPEG标准的正文中并没有规定或推荐使用哪个量化表，不过在AnnexK中有一份量化表的例子（图6），适用于大多数中等质量的图片。对于超高质量和超低质量的图片，这份量化表不是最优的[5,Item75]。通常亮度分量和色差分量各有一张量化表，而且对色差分量的将忽略更多的高频成分。实际的JPEG实现都采用这一份量化表，因此压缩后的数据中无须包含量化表。如果把下表中的量化步长除以2，那么图像质量就接近完美了。   每个分块有64个系数需要量化，需用64次除法和取整操作，因此每个分块 的计算复杂度为O(1)。对于N×M的图像，共有??N8??×??M 8??个分块，因此量化 这一步的计算复杂度为O(MN)。 1.4行程编码与熵编码 JPEG压缩的最后一步是对量化后的系数进行熵编码。这一步采用通用的无损数据压缩技术，对图像质量没有影响。 在熵编码之前，需要把64个DCT系数转换为一串中间符号。其中直流系数和交流系数的编码方式不同。直流系数表示当前分块中64个象素的平均值，相邻分块的直流系数具有很强的相关性，因此在编码时只需记录与前一分块的直流系数的差值，即直流系数的“中间符号”采用差分脉冲编码(DPCM)，见图7(a)。 对63个交流系数用“之”字型扫描，让它变成一维数组，见图7(b)。这样做的目的是将低频系数放在前面，高频系数放在后面。因为高频系数中有很多0，为了节约空间，所以交流系数的“中间符号”用零行程码(ZeroRunLength)表示。  接下来对中间符号进行熵编码，这一步的目的是利用符号的统计特性，进一步提高压缩率。JPEG标准规定的熵编码方式有两种：Huffman编码和算术编码。这两种编码各有优劣，见图8  “正宗”的Huffman编码过程要对输入序列进行两遍扫描，第一遍统计各个符号出现的概率，构造Huffman树，得到码书(codebook)；第二遍用码书对符号进行编码。这么做的话，时间空间开销都较大。两遍扫描意味着要把整幅图像的“中间符号”都记录下来，不能“随到随编(on-the-?y)”。而且要把码书传给解码器，这会增加压缩文件的大小。 JPEG的实际实现一般支持两种Huffman方式，一种是前述的“正宗”Huffman编码（称为optimized方式），另一种则采用JPEG标准AnnexK中给出的缺省码书。采用缺省码书的好处是输入序列只用扫描一遍，空间和实际开销都较小；缺点是，由于码书不是根据当前图像的统计信息得到的，那么压缩率会比“正宗”Huffman编码低一些。不过由于Huffman编码对概率误差不敏感，因此实践中常常采用缺省码书进行编码（这样还能省下保存码书的空间）。 算术编码和Huffman编码都是变长码，符号出现概率越高，码字越短。不同之处在于，Huffman编码每个符号对应的码字是确定的，每个码字的bit数为整数。算术编码的基本思想是用一个精度足够高的属于[0,1)的实数来表示整个输入序列，输入序列中每个符号对应的码字是不确定的，总体上每个符号对应的码字长度等于其信息熵（均以bit计），码字平均长度可能是小数。算术编码的压缩率通常高于Huffman编码[11]。算术编码的另一个好处是，它很容易做成自适应的(adaptive)，因此只需扫描一遍输入序列，空间开销小很多。算术编码还有一个小问题，IBM掌握了一大堆与算术编码相关的专利[5,Item8]。要想实现JPEG中的算术编码，不可能绕过这些专利。 Huffman编码和算术编码在任何一本信息论[11]或数据压缩[12]教材中都能找到，其实现细节不是本文的重点。这两种编码方法的计算复杂度都和输入序列的长度成正比，每个分块最多有64个符号（符号数通常远小于此数，因为DCT系数当中有很多连续的0），因此每个分块的复杂度为O(1)。对于N×M的图像，熵编码的计算复杂度为O(MN)。 2.实现细节 我主要参考了两份JPEG实现，分别来自IndependentJPEGGroup(IJG)[7]和StanfordPortableVideoResearchGroup(PVRG)[8]，以下简称ijg-jpeg和pvrg-jpeg。这两份实现都采用C语言，版本号分别为version6b和v1.2.1，最后更新时间分别为1998年3月和1995年3月。 从总体上看，ijg-jpeg是具有工业强度的程序库，被广泛使用，久经考验；而pvrg-jpeg是实验性的库，主要用作研究。这两个库都很久没有更新了，因为JPEG标准已经出台10多年，库的功能都稳定了。从我阅读的体验看，ijg-jpeg的代码要复杂得多，也完善得多，代码行数几乎是pvrg-jpeg的三倍。ijg-jpeg代码中大量使用了函数指针，因此光阅读代码往往不知道它调用的到底是哪个函数，它这么做是为了使用上的灵活性，同一步骤有多种实现（对应多个函数），在运行时选择到底采用哪种实现，并把函数指针指向选定的函数。相比之下，pvrg-jpeg的代码要直接了当得多，结构也清晰得多。 我在VisualC++2005ExpressEdition中为两个程序库分别建立了调试环境，通过单步跟踪确定ijg-jpeg到底调用哪个函数，在代码中标注出来，并归纳成图表。以下主要分析ijg-jpeg，适当辅以pvrg-jpeg。这两个函数库大体上都可分为编码器和解码器两部分。 2.1ijg-jpeg实现分析 下面以ijg-jpeg自带的testimg.bmp的压缩过程（Huffman编码使用缺省码书）为例，介绍编码器工作流程。ijg-jpeg编码的总体流程为：1.预处理 (a)色彩空间转换(b)边界扩展(c)下采样2.JPEG压缩 (a)DCT(b)量化 (c)“之”字型扫描(d)熵编码 编码主循环为：从输入文件读入一行行象素，送到编码器中缓存起来，编码器凑够8行就进行一次压缩。  以上代码片段来自ijg-jpeg中cjpeg.c文件的第579行至590行，位于函数main()中（后略）。第584行的src_mgr->get_pixel_rows是函数指针，根据输入图像文件类型的不同指向不同的文件读取函数。该函数的作用是读取一行象素，象素的RGB值保存在数组src_mgr->buffer中，供jpeg_write_scanlines()使用。  而jpeg_write_scanlines()把实际工作都交给cinfo->main->process_data处理，这个函数指针只会指向process_data_simple_main()。 从这个函数可以看出，每读入一行象素，就进行一次预处理（第122行），放入缓冲区。如果缓冲区中的数据不够8行则返回（第131行），否则就进行压缩（第135行）。 第122行的cinfo->prep->pre_process_data指向pre_process_data()。第135行的cinfo->coef->compress_data指向compress_data()。process_data_simple_main()的函数调用关系为（红色方块为函数指针，椭圆为普通函数）： 预处理 预处理在pre_process_data()中进行，主要做色彩转换、边界扩展、下采样，它的函数调用关系为： 这个函数中只做了下边界扩展expand_bottom_edge()，而右边界扩展留在下采样时进行。 第145行的cinfo->cconvert->color_convert指向rgb_ycc_convert()。第163行的cinfo->downsample->downsample指向sep_downsample()。色彩转换 RGB→YCbCr的色彩转换由rgb_ycc_convert()负责，转换公式在第3页给出。这里为了加快速度，预先把乘积算出来存入9张表中“rgb_ycc_start()”，在转换时只用查表操作。 扩展边界 在ijg-jpeg的具体实现中，它先扩展每一行的右边界“expand_right_edge()”，让行的长度（也就是图像的宽度）等于8的倍数。然后在图像底部填充一些行，扩展其下边界“expand_bottom_edge()”，让整个图像的高度是8的倍数。这样得到扩展之后的图像，它的宽度和高度都是8的倍数，便于分块。 下采样 下采样的工作由sep_downsample()分派给别的函数来做，第127行用到的downsample->methods[]是函数指针数组，指向各分量所用的下采样函数。 亮度分量无需下采样，于是调用fullsize_downsample()。色差分量有4:1:1和4:2:2两种下采样方式，分别对应h2v2_downsample()和h2v1_downsample()。这里实际调用的是h2v2_downsample()。 fullsize_downsample()只是简单地将输入拷贝到输出，并做右边界扩展。 h2v2_downsample()把输入图像分量按2×2分块，计算每块样本的平均值，送到输出中（第272行）。这样得到的样本数为原来的1/4。 设输入为N×M的RGB图像，共有3MN个输入样本；经过色彩转换后，Y、Cr、Cb分量各有MN个样本；再经过下采样，Y分量有MN个样本，Cr、Cb分量各有大约 N2 · M2个样本。输出样本总数约为32MN，是输入的一半。 预处理中的每一个步骤的计算复杂度都与输入样本的个数成正比，对于N×M的图像，预处理的计算复杂度为O(MN)。 PEG压缩 预处理之后，JPEG压缩由compress_data()实现。它调用forward_DCT()做离散余弦变换和量化。它在调用forward_DCT()之前，会对各色彩分量进行交织。所谓“交织”，就是说不是压缩完Y分量再压缩Cr和Cb分量，而是每次从Y分量中选几个块，和Cr、Cb中选出的分块组成MCU(MinimumCodedUnit，最小编码单元)。然后对MCU中的分块进行DCT，再以MCU为单位进行熵编码。交织的主要目的是为了在解码时能一边解压一边显示（或进行后续处理），而不用等整幅图片都解压完才显示。（光解出Y分量和Cr分量是无法显示的。） compress_data()然后调用encode_mcu_huff()对一个MCU进行Huffman编码。后者会对MCU中的各个分块调用encode_one_block()，由它来进行Huffman编码，这个函数还顺便进行“之”字型扫描。 compress_data()的函数调用关系为： 第177行的cinfo->fdct->forward_DCT指向forward_DCT()。第204行的cinfo->entropy->encode_mcu指向encode_mcu_huff()。DCT与量化 forward_DCT把DCT运算交给do_dct所指向的函数来做（第224行），它自己只做量化，这个函数的调用频率非常高，所以写得很紧凑。 量化是整个JPEG压缩中惟一用到除法的地方，而各种机器的整数除法略有区别，因此需要特殊对待，代码中的注释说得很清楚了。通常C语言中的整数除法是向下取整，并非四舍五入，因此第253行和第257行先给被除数加上除数的一半，这样就能实现四舍五入。 第224行的do_dct指向快速DCT的具体实现，ijg-jpeg提供有C.Loef?er、A.Ligtenberg、G.Moschytz等的实现（jpeg_fdct_islow）和Arai、Agui、Nakajima等的实现（jpeg_fdct_ifast）。这里实际调用的是jpeg_fdct_islow。这两份实现都是就地(in-place)计算的，代码从略。 forward_DCT()的运行时间为常数，它被调用的次数等于输入图像的分块数。对于N×M的图像，DCT的计算复杂度为O(MN)。 在执行完forward_DCT之后，就该做熵编码了。 之”字型扫描与熵编码 compress_data()在第204行通过函数指针encode_mcu调用encode_mcu_huff()进行Huffman编码。encode_mcu_huff()对MCU中的各个分块调用encode_one_block()，“之”字型扫描和Huffman编码的具体工作由后者完成。 录 1 算法描述与比较 3 1.1 分块及预处理 3 1.2 变换编码 3 1.3 量化 6 1.4 行程编码与熵编码 7 2 实现细节 8 2.1 ijg-jpeg 实现分析 9 2.1.1 预处理 11 2.1.2 色彩转换 13 2.1.3 扩展边界 14 2.1.4 下采样 15 2.1.5 JPEG 压缩 17 2.1.6 DCT 与量化 18 2.1.7 “ 之 ” 字型扫描与熵编码 20 2.1.8 量化表的缩放 23 2.2 pvrg-jpeg 实现分析 26 3 M ATLAB 实现 28 4 参考资料 28 |
|
|
