第9章 图象的压缩编码,JPEG压缩编码标准.doc

第9章 图象的压缩编码，JPEG压缩编码标准
在介绍图象的压缩编码之前，先考虑一个问题：为什么要压缩？其实这个问题不用我回答，你也能想得到。因为图象信息的数据量实在是太惊人了。举一个例子就明白：一张A4(210mm×297mm) 幅面的照片，若用中等分辨率(300dpi)的扫描仪按真彩色扫描，其数据量为多少？让我们来计算一下：共有(300×210/25.4) ×(300×297/25.4)个象素，每个象素占3个字节，其数据量为26M字节，其数据量之大可见一斑了。
如今在Internet上，传统基于字符界面的应用逐渐被能够浏览图象信息的WWW(World Wide Web)方式所取代。WWW尽管漂亮，但是也带来了一个问题：图象信息的数据量太大了，本来就已经非常紧张的网络带宽变得更加不堪重负，使得World Wide Web变成了World Wide Wait。
总之，大数据量的图象信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。
压缩的理论基础是信息论。从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去掉确定的信息(可推知的)，也就是用一种更接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量(即不确定因素)。
压缩可分为两大类：第一类压缩过程是可逆的，也就是说，从压缩后的图象能够完全恢复出原来的图象，信息没有任何丢失，称为无损压缩；第二类压缩过程是不可逆的，无法完全恢复出原图象，信息有一定的丢失，称为有损压缩。选择哪一类压缩，要折衷考虑，尽管我们希望能够无损压缩，但是通常有损压缩的压缩比(即原图象占的字节数与压缩后图象占的字节数之比，压缩比越大，说明压缩效率越高)比无损压缩的高。
图象压缩一般通过改变图象的表示方式来达到，因此压缩和编码是分不开的。图象压缩的主要应用是图象信息的传输和存储，可广泛地应用于广播电视、电视会议、计算机通讯、传真、多媒体系统、医学图象、卫星图象等领域。
压缩编码的方法有很多，主要分成以下四大类：(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算法的大体思想。
值得注意的是，近些年来出现了很多新的压缩编码方法，如使用人工神经元网络(Artificial Neural Network，简称ANN)的压缩编码算法、分形(Fractl)、小波(Wavelet) 、基于对象(Object Based)的压缩编码算法、基于模型(Model –Based)的压缩编码算法(应用在MPEG4及未来的视频压缩编码标准中)。这些都超出了本书的范围。
本章的最后，我们将以JPEG压缩编码标准为例，看看上面的几种编码方法在实际的压缩编码中是怎样应用的。
9.1 哈夫曼编码
哈夫曼(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的根节点。
(5)              将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。
上面的例子用Huffman编码的过程如图9.1所示，其中圆圈中的数字是新节点产生的顺序。可见，我们上面给出的编码就是这么得到的。

图9.1     Huffman编码的示意图
产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。
源程序就不给出了，有兴趣的读者可以自己实现。
9.2 行程编码
行程编码(Run Length Coding)的原理也很简单：将一行中颜色值相同的相邻象素用一个计数值和该颜色值来代替。例如aaabccccccddeee可以表示为3a1b6c2d3e。如果一幅图象是由很多块颜色相同的大面积区域组成，那么采用行程编码的压缩效率是惊人的。然而，该算法也导致了一个致命弱点，如果图象中每两个相邻点的颜色都不同，用这种算法不但不能压缩，反而数据量增加一倍。所以现在单纯采用行程编码的压缩算法用得并不多，PCX文件算是其中的一种。
PCX文件最早是PC Paintbrush软件所采用的一种文件格式，由于压缩比不高，现在用的并不是很多了。它也是由头信息、调色板、实际的图象数据三个部分组成。其中头信息的结构为：
typedef struct{
               char manufacturer;
               char version;
               char encoding;
               char bits_per_pixel;
               WORD xmin,ymin;
               WORD xmax,ymax;
               WORD hres;
               WORD vres;
               char palette[48];
               char reserved;
               char colour_planes;
               WORD bytes_per_line;
               WORD palette_type;
               char filler[58];
      } PCXHEAD;
其中值得注意的是以下几个数据：manufacturer为PCX文件的标识，必须为0x0a；xmin为最小的x坐标，xmax最大的x坐标，所以图象的宽度为xmax-xmin+1，同样图象的高度为ymax-yin+1；bytes_per_line为每个编码行所占的字节数，下面将详细介绍。
PCX的调色板在文件的最后。以256色PCX文件为例，倒数第769个字节为颜色数的标识，256时该字节必须为12，剩下的768(256×3)为调色板的RGB值。
为了叙述方便，我们针对256色PCX文件，介绍一下它的解码过程。编码是解码的逆过程，有兴趣的读者可以试着自己来完成。
解码是以行为单位的，该行所占的字节数由bytes_per_line给定。为此，我们开一个大小为bytes_per_line的解码缓冲区。一开始，将缓冲区的所有内容清零。从文件中读出一个字节C，若C>0xc0，说明是行程(Run Length)信息，即C的低6位表示后面连续的字节个数(所以最多63个连续颜色相同的象素，若还有颜色相同的象素，将在下一个行程处理)，文件的下一个字节就是实际的图象数据(即该颜色在调色板中的索引值)。若C<0xc0，则表示C是实际的图象数据。如此反复，直到这bytes_per_line个字节处理完，这一行的解码完成。PCX就是有若干个这样的解码行组成。
下面是实现256色PCX文件解码的源程序，其中第二个函数对一行进行解码，应该把阅读的重点放在这个函数上。要注意的是，执行时文件C:\\test.pcx必须存在，而且是一个256色PCX文件。
unsigned int    PcxBytesPerLine;
BOOL LoadPcxFile (HWND hWnd,char *PcxFileName)
{
       FILE                                          *PCXfp;
       PCXHEAD                                 header;
     LOGPALETTE                       *pPal;
     HPALETTE                         hPrevPalette;
     HDC                              hDc;
       HLOCAL                          hPal;
       DWORD                              ImgSize;
       DWORD                    OffBits,BufSize;
       LPBITMAPINFOHEADER    lpImgData;    
       DWORD                   i;
       LONG                             x,y;
       int                           PcxTag;
       unsigned char                         LineBuffer[6400];
       LPSTR                            lpPtr;
       HFILE                     hfbmp;
if((PCXfp=fopen(PcxFileName,"rb"))==NULL){ //文件没有找到
MessageBox(hWnd,"File c:\\test.pcx not found!","Error Message",
MB_OK|MB_ICONEXCLAMATION);
return FALSE;
       }
       //读出头信息
     fread((char*)&header,1,sizeof(PCXHEAD),PCXfp);
     if(header.manufacturer!=0x0a){ //不是一个合法的PCX文件
MessageBox(hWnd,"Not a valid Pcx file!","Error Message",
MB_OK|MB_ICONEXCLAMATION);
fclose(PCXfp);
           return FALSE;
       }
       //将文件指针指向调色板开始处
       fseek(PCXfp,-769L,SEEK_END);
       //获取颜色数信息
       PcxTag=fgetc(PCXfp)&0xff;
       if(PcxTag!=12){ //非256色，返回
           MessageBox(hWnd,"Not a 256 colors Pcx file!","Error Message",
MB_OK|MB_ICONEXCLAMATION);
fclose(PCXfp);
              return FALSE;
       }
//创建新的BITMAPFILEHEADER和BITMAPINFOHEADER
       memset((char *)&bf,0,sizeof(BITMAPFILEHEADER));    
       memset((char *)&bi,0,sizeof(BITMAPINFOHEADER));
       //填写BITMAPINFOHEADER头信息
       bi.biSize=sizeofBITMAPINFOHEADER);
       //得到图象的宽和高
       bi.biWidth=header.xmax-header.xmin+1;
       bi.biHeight=header.ymax-header.ymin+1;
       bi.biPlanes=1;
       bi.biBitCount=8;
       bi.biCompression=BI_RGB;
       ImgWidth=bi.biWidth;
       ImgHeight=bi.biHeight;
       NumColors=256;
       LineBytes=(DWORD)WIDTHBYTES(bi.biWidth*bi.biBitCount);
       ImgSize=(DWORD)LineBytes*bi.biHeight;
       //填写BITMAPFILEHEADER头信息
       bf.bfType=0x4d42;
       bf.bfSize=sizeof(BITMAPFILEHEADER)+sizeof(BITMAPINFOHEADER)+
NumColors*sizeof(RGBQUAD)+ImgSize;
       bf.bfOffBits=(DWORD)(NumColors*sizeof(RGBQUAD)+
sizeof(BITMAPFILEHEADER)+sizeof(BITMAPINFOHEADER));
       //为新图分配缓冲区
       if((hImgData=GlobalAlloc(GHND,(DWORD)
(sizeof(BITMAPINFOHEADER)+
NumColors*sizeof(RGBQUAD)+ImgSize)))==NULL)
       {
MessageBox(hWnd,"Error alloc memory!","ErrorMessage",
MB_OK|MB_ICONEXCLAMATION);
           fclose(PCXfp);
              return FALSE;
       }
       lpImgData=(LPBITMAPINFOHEADER)GlobalLock(hImgData);
       //拷贝头信息
       memcpy(lpImgData,(char *)&bi,sizeof(BITMAPINFOHEADER));
       lpPtr=(char *)lpImgData+sizeof(BITMAPINFOHEADER);
       //为256色调色板分配内存
     hPal=LocalAlloc(LHND,sizeof(LOGPALETTE)+
NumColors* sizeof(PALETTEENTRY));
pPal =(LOGPALETTE *)LocalLock(hPal);
     pPal->palNumEntries =256;
       pPal->palVersion = 0x300;
       for (i = 0; i < 256; i++) {
              //读取调色板中的RGB值
            pPal->palPalEntry[i].peRed=(BYTE)fgetc(PCXfp);
              pPal->palPalEntry[i].peGreen=(BYTE)fgetc(PCXfp);
              pPal->palPalEntry[i].peBlue=(BYTE)fgetc(PCXfp);
              pPal->palPalEntry[i].peFlags=(BYTE)0;
              *(lpPtr++)=(unsigned char)pPal->palPalEntry[i].peBlue;
              *(lpPtr++)=(unsigned char)pPal->palPalEntry[i].peGreen;
              *(lpPtr++)=(unsigned char)pPal->palPalEntry[i].peRed;
              *(lpPtr++)=0;
       }
       //产生新的逻辑调色板
       hPalette=CreatePalette(pPal);
       LocalUnlock(hPal);
       LocalFree(hPal);
       hDc=GetDC(hWnd);
       if(hPalette){
hPrevPalette=SelectPalette(hDc,hPalette,FALSE);
              RealizePalette(hDc);
       }
       //解码行所占的字节数
       PcxBytesPerLine=(unsigned int)header.bytes_per_line;
       //将文件指针指向图象数据的开始处
       fseek(PCXfp,(LONG)sizeof(PCXHEAD),SEEK_SET);
       //缓冲区大小
OffBits=bf.bfOffBits-sizeof(BITMAPFILEHEADER);
//BufSize为缓冲区大小
       BufSize=OffBits+bi.biHeight*LineBytes;
       for(y=0;y         for(x=0;xgData,
DIB_RGB_COLORS);
       if(hPalette && hPrevPalette){
              SelectPalette(hDc,hPrevPalette,FALSE);
              RealizePalette(hDc);
       }
       hfbmp=_lcreat("c:\\pcx2bmp.bmp",0);
       _lwrite(hfbmp,(LPSTR)&bf,sizeof(BITMAPFILEHEADER));
       _lwrite(hfbmp,(LPSTR)lpImgData,BufSize);
       _lclose(hfbmp);
       fclose(PCXfp);
       //释放内存和资源
       ReleaseDC(hWnd,hDc);
       GlobalUnlock(hImgData);
       return TRUE;
}
//对每一行进行解码，结果存储到指针p指向的内存中
void ReadPcxLine(unsigned char *p,FILE *fp)
{
       unsigned int   n=0,i;
       char                     c;
       memset(p,0,PcxBytesPerLine);
       do{
              //读出一个字节
              c=fgetc(fp)&0xff;
if((c&0xc0)==0xc0){ //是个形成字节
//i为c的低六位
i=c&0x3f;
                     //下一个字节为实际的图象数据
                     c=fgetc(fp);
                     while(i--) p[n++]=c; //填充连续的i个字节到p中
              }
              else p[n++]=c; //否则是实际的图象数据，直接填入到p中
       }while (n这个数值还成原来的字符串。例如：用数值0x100代替字符串“abccddeee”，每当出现该字符串时，都用0x100代替，这样就起到了压缩的作用。至于0x100与字符串的对应关系则是在压缩过程中动态生成的，而且这种对应关系隐含在压缩数据中，随着解压缩的进行这张编码表会从压缩数据中逐步得到恢复，后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系，直到压缩文件结束为止。LZW是无损的。GIF文件采用了这种压缩算法。
要注意的是，LZW算法由Unisys公司在美国申请了专利，要使用它首先要获得该公司的认可。
9.4 JPEG压缩编码标准
JPEG是联合图象专家组(Joint Picture Expert Group)的英文缩写，是国际标准化组织(ISO)和CCITT联合制定的静态图象的压缩编码标准。和相同图象质量的其它常用文件格式(如GIF，TIFF，PCX)相比，JPEG是目前静态图象中压缩比最高的。我们给出具体的数据来对比一下。例图采用Windows95目录下的Clouds.bmp，原图大小为640*480，256色。用工具SEA(version1.3)将其分别转成24位色BMP、24位色JPEG、GIF(只能转成256色)压缩格式、24位色TIFF压缩格式、24位色TGA压缩格式。得到的文件大小(以字节为单位)分别为：921,654，17,707，177,152，923,044，768,136。可见JPEG比其它几种压缩比要高得多，而图象质量都差不多(JPEG处理的颜色只有真彩和灰度图)。
正是由于JPEG的高压缩比，使得它广泛地应用于多媒体和网络程序中，例如HTML语法中选用的图象格式之一就是JPEG(另一种是GIF)。这是显然的，因为网络的带宽非常宝贵，选用一种高压缩比的文件格式是十分必要的。
JPEG有几种模式，其中最常用的是基于DCT变换的顺序型模式，又称为基线系统(Baseline)，以下将针对这种格式进行讨论。
1.         JPEG的压缩原理
JPEG的压缩原理其实上面介绍的那些原理的综合，博采众家之长，这也正是JPEG有高压缩比的原因。其编码器的流程为：

图9.3     JPEG编码器流程
解码器基本上为上述过程的逆过程：

图9.4     解码器流程
8×8的图象经过DCT变换后，其低频分量都集中在左上角，高频分量分布在右下角(DCT变换实际上是空间域的低通滤波器)。由于该低频分量包含了图象的主要信息(如亮度)，而高频与之相比，就不那么重要了，所以我们可以忽略高频分量，从而达到压缩的目的。如何将高频分量去掉，这就要用到量化，它是产生信息损失的根源。这里的量化操作，就是将某一个值除以量化表中对应的值。由于量化表左上角的值较小，右上角的值较大，这样就起到了保持低频分量，抑制高频分量的目的。JPEG使用的颜色是YUV格式。我们提到过，Y分量代表了亮度信息，UV分量代表了色差信息。相比而言，Y分量更重要一些。我们可以对Y采用细量化，对UV采用粗量化，可进一步提高压缩比。所以上面所说的量化表通常有两张，一张是针对Y的；一张是针对UV的。
上面讲了，经过DCT变换后，低频分量集中在左上角，其中F(0，0)(即第一行第一列元素)代表了直流(DC)系数，即8×8子块的平均值，要对它单独编码。由于两个相邻的8×8子块的DC系数相差很小，所以对它们采用差分编码DPCM，可以提高压缩比，也就是说对相邻的子块DC系数的差值进行编码。8×8的其它63个元素是交流(AC)系数，采用行程编码。这里出现一个问题：这63个系数应该按照怎么样的顺序排列？为了保证低频分量先出现，高频分量后出现，以增加行程中连续“0”的个数，这63个元素采用了“之”字型(Zig-Zag)的排列方法，如图9.5所示。

图9.5     Zig-Zag
这63个AC系数行程编码的码字用两个字节表示，如图9.6所示。

图9.6     行程编码
上面，我们得到了DC码字和 AC行程码字。为了进一步提高压缩比，需要对其再进行熵编码，这里选用Huffman编码，分成两步：
(1)熵编码的中间格式表示
对于AC系数，有两个符号。符号1为行程和尺寸，即上面的(RunLength，Size)。(0，0)和(15，0)是两个比较特殊的情况。(0，0)表示块结束标志(EOB)，(15，0)表示ZRL，当行程长度超过15时，用增加ZRL的个数来解决，所以最多有三个ZRL(3×16+15=63)。符号2为幅度值(Amplitude)。
对于DC系数，也有两个符号。符号1为尺寸(Size)；符号2为幅度值(Amplitude)。
(2)熵编码
对于AC系数，符号1和符号2分别进行编码。零行程长度超过15个时，有一个符号(15，0)，块结束时只有一个符号(0，0)。
对符号1进行Hufffman编码(亮度，色差的Huffman码表不同)。对符号2进行变长整数VLI编码。举例来说：Size=6时，Amplitude的范围是-63~-32，以及32~63，对绝对值相同，符号相反的码字之间为反码关系。所以AC系数为32的码字为100000，33的码字为100001，-32的码字为011111，-33的码字为011110。符号2的码字紧接于符号1的码字之后。
对于DC系数，Y和UV的Huffman码表也不同。
掉了这么半天的书包，你可能已经晕了，呵呵。举个例子来说明上述过程就容易明白了。
下面为8×8的亮度(Y)图象子块经过量化后的系数。
15    0     -1    0     0     0     0     0
-2    -1    0     0     0     0     0     0
-1    -1    0     0     0     0     0     0
0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0
0     0     0     0     0     0     0     0
可见量化后只有左上角的几个点(低频分量)不为零，这样采用行程编码就很有效。
第一步，熵编码的中间格式表示：先看DC系数。假设前一个8×8子块DC系数的量化值为12，则本块DC系数与它的差为3，根据下表
Size                             Amplitude
0                                        0
1                                        –1,1
2                                        –3,-2,2,3
3                                        –7~-4，4~7
4                                        –15~-8，8~15
5                                        –31~-16，16~31
6                                        –63~-32，32~63
7                                        –127~-64，64~127
8                                        –255~-128，128~255
9                                        –511~-256，256~511
10                                       –1023~512，512~1023
11                                       –2047~-1024，1024~2047
查表得Size=2，Amplitude=3，所以DC中间格式为(2)(3)。
下面对AC系数编码。经过Zig-Zag扫描后，遇到的第一个非零系数为-2，其中遇到零的个数为1(即RunLength)，根据下面这张AC系数表：
Size                             Amplitude
1                                        –1,1
2                                        –3,-2,2,3
3                                        –7~-4，4~7
4                                        –15~-8，8~15
5                                        –31~-16，16~31
6                                        –63~-32，32~63
7                                        –127~-64，64~127
8                                        –255~-128，128~255
9                                        –511~-256，256~511
10                                       –1023~512，512~1