chapter9 图像的压缩编码.docx
《chapter9 图像的压缩编码.docx》由会员分享，可在线阅读，更多相关《chapter9 图像的压缩编码.docx（28页珍藏版）》请在冰点文库上搜索。
chapter9图像的压缩编码
第九讲图象的压缩编码，JPEG压缩编码标准
在介绍图象的压缩编码之前，先考虑一个问题：
为什么要压缩？
其实这个问题不用我回答，你也能想得到。
因为图象信息的数据量实在是太惊人了。
举一个例子就明白了，一张A4（210mm*297mm）幅面的照片，若用中等分辨率（300dpi）的扫描仪按真彩扫描，其数据量为多少？
让我们来计算一下：
共有（300*210/25.4）*（300*297/25.4）个像素，每个像素占3个字节,其数据量为26M字节，其数据量之大可见一斑了。
如今在Internet上，传统基于字符界面的应用逐渐被能够浏览图象信息的WWW（WorldWideWeb）方式所取代。
WWW尽管漂亮，但是也带来了一个问题：
图象信息的数据量太大了，本来就已经非常紧张的网络带宽变得更加不堪重负，使得WorldWideWeb变成了WorldWideWait。
总之，大数据量的图象信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。
单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。
压缩的理论基础是信息论。
从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去掉确定的信息（可推知的），也就是用一种更接近信息本质的描述来代替原有冗余的描述。
这个本质的东西就是信息量（即不确定因素）。
压缩可分为两大类，第一类压缩过程是可逆的，也就是说，从压缩后的图象能够完全恢复出原来的图象，信息没有任何丢失，称为无损压缩；第二类压缩过程是不可逆的，无法完全恢复出原图象，信息有一定的丢失，成为有损压缩。
选择哪一类压缩，要折中考虑，尽管我们希望能够无损压缩，但是通常有损压缩的压缩比（即原图象占的字节数与压缩后图象占的字节数之比，压缩比越大，说明压缩效率越高）比无损压缩的高。
图象压缩一般是通过改变图象的表示方式来达到，因此压缩和编码是分不开的。
图象压缩的主要应用是图象信息的传输和存储，可广泛地应用于广播电视，电视会议，计算机通讯，
传真，多媒体系统，医学图象，卫星图象等领域。
压缩编码的方法有很多，主要分成以下4大类：
1.像素编码；2.预测编码；3.变换编码；4.其它方法。
所谓像素编码是指，编码时对每个像素单独处理，不考虑像素之间的相关性。
在像素编码中常用的几种方法有：
1.脉冲编码调制（PulseCodeModulation，PCM）;2.熵编码（EntropyCoding）；3.行程编码（RunLengthCoding）；4.位平面编码（BitPlaneCoding）。
这里面，我们要介绍的是熵编码中的哈夫曼（Huffman）编码，行程编码（以读取.PCX文件为例）。
所谓预测编码是指，去掉相邻像素之间的相关性和冗余性，只对新的信息进行编码。
举个简单的例子，因为像素的灰度是连续的，所以在一片区域中，相邻像素之间灰度值的差别可能很小。
如果我们只记录第一个像素的灰度，其它像素的灰度都用它与前一个像素灰度之差来表示，就能起到压缩的目的。
如248，2，1，0，1，3，实际上这6个像素的灰度是248，250，251，251，252，255。
表示250需要8个比特，而表示2只需要两个比特，这样就实现了压缩。
常用的预测编码有Δ调制（DeltaModulation，简称DM）；微分预测编码（DifferentialPulseCodeModulation，DPCM），具体的细节，我们就不详述了。
所谓变换编码是指，将给定的图象变换到另一个数据域（如频域）上，使得大量的信息能用较少的数据来表示，从而达到压缩的目的。
变换编码有很多，如1.离散傅立叶变换（DiscreteFourierTransform，DFT）；2.离散余弦变换（DiscreteCosineTransform，DCT）；3.离散哈达玛变换（DiscreteHadamardTransform，DHT）。
其它的编码方法也有很多，如混合编码（HybirdCoding），矢量量化（VectorQuantize，VQ），LZW算法。
在这里，我们只介绍LZW算法的大体思想。
值得注意的是，近些年来出现了很多新的压缩编码方法，如使用人工神经元网络（ArtificialNeuralNetwork，ANN）的压缩编码算法；分形（Fractl）；小波（Wavelet）；基于对象（Object–Based）的压缩编码算法；基于模型（Model–Based）的压缩编码算法（应用在MPEG4及未来的视频压缩编码标准中）。
这些都超出了本讲座的范围。
本讲的最后，我们将以JPEG压缩编码标准为例，看看上面的几种编码方法在实际的压缩编码中是怎样应用的。
1.哈夫曼（Huffman）编码
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编码的过程如下图所示，其中圆圈中的数字是新节点产生的顺序。
可见，我们上面给出的编码就是这么得到的。
图1.Huffman编码的示意图
产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。
源程序就不给出了，有兴趣的读者可以自己实现。
2.行程编码（RunLengthCoding）
行程编码的原理也很简单：
将一行中颜色值相同的相邻像素用一个计数值和该颜色值来代替。
例如:
aaabccccccddeee可以表示为3a1b6c2d3e。
如果一幅图象是由很多块颜色相同的大面积区域组成，那么采用行程编码的压缩效率是惊人的。
然而，该算法也导致了一个致命弱点，如果图象中每两个相邻点的颜色都不同，用这种算法不但不能压缩，反而数据量增加一倍。
所以现在单纯采用行程编码的压缩算法用得并不多，PCX文件算是其中的一种.
PCX文件最早是PCPaintbrush软件所采用的一种文件格式，由于压缩比不高，现在用的并不是很多了。
它也是由头信息，调色板，实际的图象数据三个部分组成。
其中头信息的结构为：
typedefstruct{
charmanufacturer;
charversion;
charencoding;
charbits_per_pixel;
WORDxmin,ymin;
WORDxmax,ymax;
WORDhres;
WORDvres;
charpalette[48];
charreserved;
charcolour_planes;
WORDbytes_per_line;
WORDpalette_type;
charfiller[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，说明是行程（RunLength）信息，即C的低6位表示后面连续的字节个数（所以最多63个连续颜色相同的像素，若还有颜色相同的像素，将在下一个行程处理），文件的下一个字节就是实际的图象数据（即该颜色在调色板中的索引值）；若C<0xc0，则表示C是实际的图象数据。
如此反复，直到这bytes_per_line个字节处理完，这一行的解码完成。
PCX就是有若干个这样的解码行组成。
下面就是实现256色PCX文件解码的源程序，其中第二个函数对一行进行解码，应该把阅读的重点放在这个函数上。
要注意的是，执行时，文件C:
\\test.pcx必须存在，而且是一个256色PCX文件。
unsignedintPcxBytesPerLine;
BOOLLoadPcxFile（HWNDhWnd,char*PcxFileName）
{
FILE*PCXfp;
PCXHEADheader;
LOGPALETTE*pPal;
HPALETTEhPrevPalette;
HDChDc;
HLOCALhPal;
DWORDImgSize;
DWORDOffBits,BufSize;
LPBITMAPINFOHEADERlpImgData;
DWORDi;
LONGx,y;
intPcxTag;
unsignedcharLineBuffer[6400];
LPSTRlpPtr;
HFILEhfbmp;
if（（PCXfp=fopen（PcxFileName,"rb"））==NULL）{//文件没有找到
MessageBox（hWnd,"Filec:
\\test.pcxnotfound!
","ErrorMessage",MB_OK|
MB_ICONEXCLAMATION）;
returnFALSE;
}
//读出头信息
fread（（char*）&header,1,sizeof（PCXHEAD）,PCXfp）;
if（header.manufacturer!
=0x0a）{//不是一个合法的PCX文件
MessageBox（hWnd,"NotavalidPcxfile!
","ErrorMessage",MB_OK|MB_ICONEXCLAMATION）;
fclose（PCXfp）;
returnFALSE;
}
//将文件指针指向调色板开始处
fseek（PCXfp,-769L,SEEK_END）;
//获取颜色数信息
PcxTag=fgetc（PCXfp）&0xff;
if（PcxTag!
=12）{//非256色，返回
MessageBox（hWnd,"Nota256colorsPcxfile!
","ErrorMessage",MB_OK|
MB_ICONEXCLAMATION）;
fclose（PCXfp）;
returnFALSE;
}
//创建新的BITMAPFILEHEADER和BITMAPINFOHEADER
memset（（char*）&bf,0,sizeof（BITMAPFILEHEADER））;
memset（（char*）&bi,0,sizeof（BITMAPINFOHEADER））;
//填写BITMAPINFOHEADER头信息
bi.biSize=sizeof（BITMAPINFOHEADER）;
//得到图象的宽和高
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,"Errorallocmemory!
","ErrorMessage",MB_OK|
MB_ICONEXCLAMATION）;
fclose（PCXfp）;
returnFALSE;
}
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++）=（unsignedchar）pPal->palPalEntry[i].peBlue;
*（lpPtr++）=（unsignedchar）pPal->palPalEntry[i].peGreen;
*（lpPtr++）=（unsignedchar）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=（unsignedint）header.bytes_per_line;
//将文件指针指向图象数据的开始处
fseek（PCXfp,（LONG）sizeof（PCXHEAD）,SEEK_SET）;
//缓冲区大小
BufSize=bf.bfSize-sizeof（BITMAPFILEHEADER）;
for（y=0;y//指向新图中相应的位置
lpPtr=（char*）lpImgData+BufSize-LineBytes-y*LineBytes;
//解码该行，放在数组LineBuffer中
ReadPcxLine（LineBuffer,PCXfp）;
for（x=0;x*（lpPtr++）=LineBuffer[x];//将该行存储到位图数据中
}
//创建新的位图
hBitmap=CreateDIBitmap（hDc,（LPBITMAPINFOHEADER）lpImgData,（LONG）CBM_INIT,
（LPSTR）lpImgData+sizeof（BITMAPINFOHEADER）+NumColors*sizeof（RGBQUAD）,
（LPBITMAPINFO）lpImgData,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）;
returnTRUE;
}
//对每一行进行解码，结果存储到指针p指向的内存中
voidReadPcxLine（unsignedchar*p,FILE*fp）
{
unsignedintn=0,i;
charc;
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中
}
elsep[n++]=c;//否则是实际的图象数据，直接填入到p中
}while（n}
一幅的PCX文件格式的图象解码后如下图所示，上面是法国著名影星阿佳妮.伊莎贝拉。
图2.一幅PCX文件格式的图象
3.LZW算法的大体思想
LZW是一种比较复杂的压缩算法，其压缩效率也比较高。
我们在这里只介绍一下它的基本原理：
LZW把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串。
例如：
用数值0x100代替字符串“abccddeee”，每当出现该字符串时，都用0x100代替，这样就起到了压缩的作用。
至于0x100与字符串的对应关系则是在压缩过程中动态生成的，而且这种对应关系隐含在压缩数据中，随着解压缩的进行,这张编码表会从压缩数据中逐步得到恢复，后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系，直到压缩文件结束为止。
LZW是无损的。
GIF文件采用了这种压缩算法。
要注意的是，LZW算法由Unisys公司在美国申请了专利，要使用它首先要获得该公司的认可。
4.JPEG压缩编码标准
JPEG是联合图象专家组（JointPictureExpertGroup）的英文缩写，是国际标准化组织（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变换的顺序型模式，又称为
升级会员 