实验三图像编码一、实验内容:用Matlab语言、C语言或C++语言编制图像处理软件，对某幅图像进行时域和频域的编码压缩。

二、实验目的和意义:1. 掌握哈夫曼编码、香农-范诺编码、行程编码2．了解图像压缩国际标准三、实验原理与主要框架:3.1实验所用编程环境:Visual C++6.0（简称VC）3.2实验处理的对象:256色的BMP(BIT MAP )格式图像BMP(BIT MAP )位图的文件结构:(如图3.1)图3.1 位图的文件结构具体组成图:单色DIB 有2个表项16色DIB 有16个表项或更少 256色DIB 有256个表项或更少 真彩色DIB 没有调色板每个表项长度为4字节（32位） 像素按照每行每列的顺序排列每一行的字节数必须是4的整数倍biSize biWidth biHeight biPlanes biBitCount biCompression biSizeImagebiXPelsPerMeter biYPelsPerMeter biClrUsedbiClrImportantbfType=”BM ” bfSizebfReserved1 bfReserved2 bfOffBits BITMAPFILEHEADER位图文件头 （只用于BMP 文件）BITMAPINFOHEADER位图信息头Palette 调色板DIB Pixels DIB 图像数据3.3 数字图像基本概念数字图像是连续图像(,)f x y 的一种近似表示，通常用由采样点的值所组成的矩阵来表示：(0,0)(0,1)...(0,1)(1,0)(1,1)...(1,1).........(1,0)(1,1)...(1,1)f f f M f f f M f N f N f N M -⎡⎤⎢⎥-⎢⎥⎢⎥⎢⎥----⎣⎦每一个采样单元叫做一个像素(pixel )，上式(2.1)中，M 、N 分别为数字图像在横(行)、纵(列)方向上的像素总数。

在计算机内通常用二维数组来表示数字图像的矩阵，把像素按不同的方式进行组织或存储，就得到不同的图像格式，把图像数据存成文件就得到图像文件。

图像文件按其数字图像格式的不同一般具有不同的扩展名。

最常见的图像格式是位图格式，其文件名以BMP 为扩展名。

图像数字化的精度包括两部分，即分辨率和颜色深度。

分辨率指图像数字化的空间精细度，有显示分辨率和图像分辨率两种。

数字图像的颜色深度表示每一像素的颜色值所占的二进制位数。

颜色深度越大则能表示的颜色数目越多。

颜色深度的不同，就产生不同种类的图像文件，在计算机中常使用图像文件的类型有单色图像、灰度图像、伪彩色图像和24位真彩色图像。

它们之间的关系取决于数字图像采用的颜色表示法。

常用的颜色表示法有RGB、CMYK、HSL和YUV等。

数字图像的数据容量非常庞大，如以24位真彩色表示像素为640*480的数字图像，所需要的数据量为900KB，所以需要对数字图像进行数据压缩。

数据压缩包括数据压缩编码和压缩数据解码两个过程。

图像压缩的基本原则包括：（1）编码重复压缩：按照编码重复的概率大小做压缩编码，压缩重复概率大的编码，可以节省一些存储空间。

（2）像素间重复压缩：前后像素间存在的某种程度的相关，如存在相同的背景图像等，简化编码以节省空间。

（3）视觉重复压缩：由于入眼的生理构造，就算在像素之间少了几个像素，眼睛也看不出来。

但是，只是在某些情况中才可以允许这种失真性较大的应用。

主要的数字图像压缩标准是JPEG(Joint Picture Expert Group)标准。

数字图像的采集设备主要有扫描仪、数字相机和图像采集卡等。

通过对数字图像进行一定的处理，即图像处理，可在一定程度上改善图像的分辨质量和形成特殊的视觉效果。

数字图像处理由数字图像处理系统完成，其结构主要包括图像采集系统、计算机图像处理系统和图像输出系统三部分。

3.4图像的编码图像的编码包括图像的离哈夫曼编码、香农-范诺编码、行程编码，基本框架(如图3.2)和图像编码菜单设计图(如图3.3)如下：图3.2 图像编码流程图图3.3 bmp图像编码菜单设计图四、数字图像编码技术:4.1 哈夫曼编码根据信息论中信源编码理论，当平均码长R大于等于图像熵H时，总可设计出一种无失真编码。

当平均码长大于图像熵时，表明该编码方法效率很低；当平均码长等于或很接近于（但不大于）图像熵时，称此编码方法为最佳编码，此时不会引起图像失真；当平均码长小于图像熵时，压缩比较高，但会引起图像失真。

在变长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，但其平均码字长度为最小，这就是变长最佳编码定理。

变长最佳编码定理是哈夫曼编码的理论基础。

4.1.1 哈夫曼编码基本原理哈夫曼（Huffman ）编码是一种常用的压缩编码方法，是Huffman 于1952年为压缩文本文件建立的，是一种效率比较高的变长无失真信源编码方法。

它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。

由于哈夫曼编码是以信源概率分布为基础的，但一般情况下无法事先知道信源的概率分布，因而通常采用对大量数据进行统计后得到的近似分布来代替，这样会导致实际应用时哈夫曼编码无法达到最佳性能。

4.1.2 哈夫曼编码步骤下面来介绍哈夫曼编码方法：（1）将输入的符号（图像中的灰度级）i a 按出现概率()i P a 由小到大排列，即()()()...i j k P a P a P a ≤≤（2）将最小的两个()i P a 相加，形成一个新的概率集合（此时压缩了一个()i P a ），再按（1）重复直到只剩下两个概率为止。

下图给出了一个实际信源符号的缩减过程。

表3.1 哈夫曼编码中的信源符号缩减过程从最后的两概率值开始逐步向前给符号分配码字长，每一步有两个分支，以相同的规则各赋予一个二进制码。

编码过程如表3.2所示。

同时也可以计算与编码性能相关的几个参数： （1）信源的熵721()()log () 2.325i i i H A P a P a -=-=∑(3.1)（2）哈夫曼编码的平均码字长71()()30.1610.430.12...40.06 2.380a v g i i i L l a p a -==⨯+⨯+⨯++⨯=∑ (3.2)（3）哈夫曼编码的效率() 2.3250.9772.328a v g H A L η=== (3.3)4.1.3 哈夫曼编码特点用哈夫曼编码方法压缩图像数据，对于不同的图像，其压缩效果和压缩效率是不同的。

当各符号出现概率不同时，编码效率较高。

而当各符号出现的概率相等时，实际上此时的哈夫曼编码就已退化成等长编码，编码效率较低。

对灰度图像的无损压缩算法采用哈夫曼编码，即对原图像实行直接的编码，该算法在恢复图像的质量上是极好的。

但由于该算法对原图像直接使用不等长编码压缩，但没有处理图像各个像素间的相关性，从而使压缩效率并不是很高,因此必须结合其它的压缩方法同时使用以达到更高的压缩比。

4.2 香农-范诺编码香农-范诺(Shannon-Fannon)编码也是一种常见的可变字长编码。

与哈夫曼编码相似，当信源符号出现时的概率正好为2-i 时，采用香农-范诺编码同样能达到100%的编码效果。

4.2.1 香农-范诺编码基本原理香农-范诺编码的理论基础是符号的码字长度Ni 完全由该符号出现的概率来决定，即 -logDPi ≤Ni ≤-logDPi+1，式中D 为编码所用的数制。

4.2.2 香农-范诺编码步骤（1）将信源符号X i 按其出现概率P i 从小到大排序：1211211...;......n nn x x x X P P P P P P ⎧⎫=≤≤≤⎨⎬⎩⎭(3.3)（2）将X 分成两个子集1212121112............k k k n k k k n x x x x x x X X P P P P P P ++++⎧⎫⎧⎫==⎨⎬⎨⎬⎩⎭⎩⎭(3.4)并且保证11k niji j k P P --+≈∑∑成立或差不多成立。

在本图像压缩编码设计中是按前一个子集大于等于总和的一半来计算的。

（3）给两个子集赋不同的码元值，如X1中的符号赋“1”，X2中的符号就赋“0”。

（4）重复（2）、（3），即对每个子集再一分为二，并分别赋予不同码元值，直到每个子集仅含一个信源符号为止。

下面通过哈夫曼编码中用过的同样例子，说明上述编码过程。

将信源54731620.020.040.060.120.160.20.4a a a a a a a A ⎧⎫=⎨⎬⎩⎭(3.5)记为：123450.20.40.06x x x x x x X ⎧⎫=⎨⎬⎩⎭ (3.6)则其编码过程如表3.3所示。

4.2.3 香农-范诺编码特点采用以上算法用VC 具体实现对某一图像进行编码，同时对编码的有关评估参数如图像熵值、平均码长、编码效率进行计算。

为了便于编码的显示设计了编码显示对话框，在其中进行编码运算并实现码字的显示。

4.3 行程编码行程编码又称行程长度编码(Run Length Encoding, RLE)，是一种熵编码，其编码原理相当简单，即将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。

RLE 压缩编码尤其适用于计算机生成的图形图像，对减少存储容量很有效果。

4.3.1行程编码基本原理行程编码分为定长和不定长编码两种。

定长编码是指编码的行程长度所用的二进制位数固定，而变长形成编码是指对不同范围的行程长度使用不同位数的二进制进行编码。

使用变长行程编码需要增加标志位来表明所使用的二进制位数。

为了达到较好的压缩效果，一般不单独采用行程编码，而是和其他编码方法结合使用。

例如，在JPEG中，就综合使用了行程编码、DCT、量化编码以及哈夫曼编码，先对图像作分块处理，再对这些分块图像进行离散余弦变换(DCT)，对变换后的频域数据进行量化并作Z字形扫描，接着对扫描结果作行程编码，对行程编码后的结果在作哈哈夫曼编码。

4.3.2行程编码步骤PCX文件分为文件头和图像压缩数据两个部分。

如果是256色图像，则还有一个256色调色板存于文件尾部。

文件头全长128字节，包含了图像的大小和颜色以及PCX文件的版本标志等信息。

其中头信息的具体结构为：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-ymin+1；bits_per_pixel为每个编码行所占的字节数。