《数字图像处理：Matlab算法设计与解译》 课件 第7、8章-图像压缩编码、图像分割

第七章

图像压缩编码

从本质上讲，数字图像的压缩是指在满足一定的图像质量要求条件（比如保真度评分或信噪比值）下，通过寻求图像数据的更有效地表征形式，以便用最少的比特数表示图像或表示图像中所包含信息的技术。

寻求图像的有效表示方式即是寻求一种用更少的比特数表示图像的编码方法，从而达到表示同一图像所需数据更少（得到压缩）的目的。

因此压缩和编码是无法分开的统一体。7.1DCT变换

离散余弦变换：DiscreteCosineTransform，简写为DCT欧拉公式:

◆余弦函数的偶对称性，使DCT仅只有实数域变换结果，不再涉及复数运算，运算简单，费时少。

◆变换结果保持了变换域的频率特性。◆变换结果与人类视觉系统特性相适应。

◆得到了更加广泛的应用。

7.1.1一维DCT设f(x)为一实数离散序列，如图7.1(a)。F(x)0

1

2

…M-1…x(a）-(M-1)-1/2

-2-1/2-1-1/2-1/2

0

1/2

1+1/2

2+1/2

M-1+1/2……x(b）Fs(x)图7.1以x=0为中心的偶序列

将(a)延拓为偶对称序列，如图7.1(b)。

7.1.1一维DCT则有：显然，fs(x)是以x=0为中心的偶对称函数。-(M-1)-1/2

-2-1/2-1-1/2-1/2

0

1/2

1+1/2

2+1/2

M-1+1/2……x(b）Fs(x)（7.1）7.1.1一维DCT

对fs(x)求2M个点的一维离散傅里叶变换(DFT)，有用y=-x对上式的第1项作变量代换，并仍用x表示可得7.1.1一维DCT考虑到fs(x)为偶函数，即fs(x)=fs(-x)，并对式（如红线下公式）运用欧拉公式可得7.1.1一维DCT即由定义：用y=x-1/2对上式作变量代换：

也即，设y=x-1/2，则x=y+1/2，且x=(2y+1)/2这样，当x=1/2时，y=0；

当x=M-1+1/2时，y=M-1则有：再用x代替y得：（7.6）7.1.1一维DCT7.1.1一维DCT

(7.6)

对上式乘以K(u)，以便将其表示成归一正交矩阵形式，就可得f(x)的一维DCT为：

(7.7)其中

(7.78)7.1.1一维DCT

将式（7.8）代入式（7.7），可得到一种更直观地一维正DCT表示形式为：

(7.9)

(7.10)其中：F(u)是第u个余弦变换系数，u是广义频率变量，f(x)是时域上的M点实序列。u,x=0,1,2,…,M-1。7.1.1一维DCT

一维离散余弦变换的正变换核为

(7.11)

当显示坐标系的纵坐标(行方向)为u(u=0,1,2…,M-1)；横坐标(列方向)为v(v=0,1,2…,M-1)时:

把前面得到的各行向量拼起来：

01…M-1……就可得到：

(7.12)也即，对于一维DCT正变换核：

(7.11)

当显示坐标系的纵坐标(行方向)u（u=0,1,2…,M-1）；横坐标(列方向)为x（x=0,1,2…,M-1）时，式（7.11）可表示成

(7.12)7.1.1一维DCT同理可得，一维DCT反变换的定义式为：

(7.13)

x=0,1,…,M-1其中

(7.14)7.1.1一维DCT当M＝4时，根据式（7.12）:且当(纵坐标)u=0时：也即，F(0)=[0.50.50.50.5]当u=1时，可得一维DCT的正变换矩阵为：

(7.15)7.1.1一维DCT

同理，可得当M＝4时的一维反变换矩阵为：(7.16)

【例】计算一维离散余弦变换的正变换核矩阵值的matlab程序。clc;clearall;closeall;m=input('请输入一维信号的长度m=')%正整数fprintf('当M=%d',m);fprintf('时的一维离散余弦变换的正变换核矩阵P(');fprintf('%d',m);fprintf(',%d):\n',m);foru=0:m-1fprintf('[');forx=0:m-1ifu==0ku=1.0/sqrt(2.0);elseku=1.0;end

hxu=sqrt(2.0/double(m))*ku*cos((pi*(2.0*double(x)+1)*u)/(2.0*double(m)));fprintf('%f',hxu);endfprintf(']\n');end一、一维DCT【例】计算一维离散余弦变换的正变换核矩阵值的matlab程序。一、一维DCT7.1.2二维偶DCT基本思想：

把一个N×N的图像数据矩阵延拓成二维平面上的偶对称阵列。延拓方式有两种：

（1）围绕图像边缘（但不重叠）将其折叠成对称形式而得到的变换称为偶离散余弦变换；（2）通过重叠图像的第一列像素和第N-1行像素将其折叠成对称形式而得到的变换称为奇离散余弦变换。

为了简化起见，下面只介绍偶离散余弦变换。

7.1.2二维偶DCT设f(x,y)为一N×N的图像数据阵列，将f(x,y)围绕其左边缘和下边缘不重叠地折叠成偶对称图像,即下图。

YN-1–N(0,0)XN-1–N(-1,-1)并表示为：(7.17)

可见,2N×2N的新图像的对称中心位于图像中红色的细十字虚线的交叉处，也即位于(-1/2,-1/2)处。图7.37.1.2二维偶DCT对上述的新图像fs(x,y)取二维傅立叶变换可得：（7.18）由于fs(x,y)是实对称函数，欧拉展开式后的正弦项为零值，所以上式可简化成：（7.19）（7.20）由于该对称函数四个象限的变换结果完全相同，所以7.1.2二维偶DCT把上述变换矩阵定义成归一正交矩阵形式，可得fs(x,y)的二维DCT为：

(7.21)其中:(7.22)

(7.23)

二维离散余弦变换的正、反变换核是相同的、对称的、可分离的，即为：并记

(7.26)

7.1.2二维偶DCT7.1.2二维偶DCT

二维DCT的正、反变换的空间矢量表示形式为:

(7.27)(7.28)

其中：变换矩阵的形式为（横坐标为x，纵座标为u）

(7.29)

7.1.2二维偶DCTDCT变换的计算步骤：（1）把f(x，y)延拓成，长度为2N2N；（2）求的2N2N点DFT；（3）对u和v各项乘上对应的因子和；（4）取实部，并分别乘上因子；（5）取F(u，v)的前N项，即为f(x，y)的余弦变换。7.1.2二维偶DCT例：DCT变换的matlab编程。DCT变换的matlab程序较为复杂，详细地给出和解释DCT变换的matlab程序已经超出了本书的内容范围。

下面从说明相关概念出发，给出利用matlab的相关DCT变换函数实现的DCT变换matlab程序。%DCT变换matlab程序clc;clearall;closeall;img0=imread('d:\0_matlab图像课编程\girl.jpg');subplot(1,3,1);imshow(img0);title('原图像');

[h,w,color]=size(img0);if(color==3)%如果输入图像是彩色图像,将其转换成灰度图像

f_gray=rgb2gray(img0);else

f_gray=img0;end

dct_coef=dct2(f_gray);%计算DCT系数subplot(1,3,2);imshow(log(abs(dct_coef)),[]);title('DCT系数图像');

dct_coef(abs(dct_coef)<0.1)=0;%将DCT系数矩阵中小于0.1的值置为0f_dct=idct2(dct_coef);%进行DCT逆变换重建图像subplot(1,3,3);imshow(f_dct,[]);title('DCT变换解压缩图像');7.1.2二维偶DCT——DCT变换结果示例

（a）原图像（b）DCT换系数图像（c）DCT反变换重建图像

图7.4DCT变换验证结果图例7.1.2二维偶DCT——DCT变换结果示例7.1.2二维偶DCT——DCT变换结果示例7.1.3DCT变换的基函数与基图像如前所述，DCT正变换和反变换可描述为：

(7.30)(7.31)

其中：

正、反变换核H(x,y,u,v)也称为二维DCT变换的基函数或基图像。

式(7.31)中的F(u,v)称为变换系数。

7.1.3DCT变换的基函数与基图像7.1.3DCT变换的基函数与基图像

根据式（7.32）～式（7.34），当N=4时的二维DCT变换的基图像共有4×4=16个块，对应于H(x,y,u,v)中的（u,v）为(0，0)、（0，1），…，（3，3）的16种情况。

对于某个特定的u和v所对应的块，每个块包括4×4=16个元素（子方块），对应于（x,y）为（0，0）、（0，1）、（0，2）、（0，3）、（1，0），…，（3，3）的16种情况。7.1.3DCT变换的基函数与基图像所以当N=4时，二维DCT变换的基图像为：

V

0

123u0123图7.5N=4时的二维DCT变换基图像

【例】根据DCT正变换的基函数计算DCT变换的基图像Matlab程序。clc;clearall;closeall;m=4;%建立尺寸为4×4的DCT变换的基图像foru=0:3%u×v=4×4figure;%在4个figure上依次输出u=0、1、2和3的每个v的x×y=4×4的图像基

forv=0:3

forx=0:3%x×y=4×4

fory=0:3ifu==0ku=1.0/sqrt(2.0);%k(u)的值

elseku=1.0;endifv==0kv=1.0/sqrt(2.0);%k(v)的值

elsekv=1.0;end%计算Q(u,v,xy)，其中2m=2.0*4=8.0

quv(x+1,y+1)=0.5*ku*kv*cos(((2.0*x+1)*3.1415926*u)/8.0)*...cos(((2.0*y+1)*3.1415926*v)/8.0);

end

endsubplot(4,4,v+1);imshow(quv,[]);

endend三、DCT变换的基函数与基图像三、DCT变换的基函数与基图像

【例】根据DCT正变换的基函数计算DCT变换的基图像Matlab程序。7.1.3图像变换的基函数与基图像前述DCT的正、反变换的基函数和基图像的概念也适用于傅里叶变换，只是在傅里叶变换中，正变换核与反变换核是不相同的。7.2数字图像压缩编码基础

1.信息相关

在绝大多数图像的像素之间，各像素行和帧之间存在着较强的相关性。

从统计观点出发，就是每个像素的灰度值（或颜色值）总是和其周围的其它像素的灰度值（或颜色值）存在某种关系，应用某种编码方法减少这些相关性就可实现图像压缩。7.2.1图像压缩的基本概念7.2.1图像压缩的基本概念1.信息相关引例(图7.5)：

新的编码只需21位：1，0101，1111，0111，1011，0011

由此可见，利用图像中各像素之间存在的信息相关，可实现图像编码信息的压缩。

上图的黑白像素序列共41位，编码为：11111，000000000000000，1111111，00000000000，1115位15位7位11位3位7.2.1图像压缩的基本概念2.信息冗余从信息论的角度来看，压缩就是去掉信息中的冗余。即保留确定信息，去掉可推知的确定信息，用一种更接近信息本质的描述来代替原有的冗余描述。图像数据存在的冗余可分为三类：

（1）编码冗余；

（2）像素间的冗余；

（3）心里视觉冗余。

7.2.1图像压缩的基本概念2.信息冗余（续1）

（1）编码冗余由于大多数图像的直方图不是均匀(水平)的，所以图像中某个或某些灰度级会比其它灰度级具有更大的出现概率，如果对出现概率大和出现概率小的灰度级都分配相同的比特数，必定会产生编码冗余。

也即：如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余。7.2.1图像压缩的基本概念2.信息冗余（续2）

（2）像素间的冗余所谓“像素间的冗余”，是指单个像素携带的信息相对较少，单一像素对于一幅图像的多数视觉贡献是多余的，它的值可以通过与其相邻的像素的值来推断。7.2.1图像压缩的基本概念2.信息冗余（续3）

（3）心里视觉冗余心里视觉冗余是指，在正常的视觉处理过程中那些不十分重要的信息。

也即：一些信息在一般的视觉处理中，比其他信息的相对重要程度要小，这种信息就被称为视觉心理冗余。7.2.1图像压缩的基本概念2.信息冗余（续3）

（3）心里视觉冗余7.2.1图像压缩的基本概念3.信源编码及其分类

信源编码：图像压缩的目标是在满足一定的图像质量的条件下，用尽可能少的比特数来表示原图像，以减少图像的存储容量和提高图像的传输效率。

在信息论中，把这种通过减少冗余数据来实现数据压缩的过程称为信源编码。

7.2.1图像压缩的基本概念3.信源编码及其分类（续1）

信源编码的分类：无失真编码和有失真编码

◆无失真压缩也称为无损压缩，是一种在不引入任何失真的条件下使表示图像的数据比特率为最小的压缩方法。

◆有失真压缩也称为有损压缩，是一种在一定比特率下获得最佳保真度，或在给定的保真度下获得最小比特率的压缩方法。7.2.2图像编码模型

信源编码器信源解码器信道解码器信道信道编码器编码器解码器1.图像编码系统模型

图7.7图像编码系统模型7.2.2图像编码模型

2.信道编码器与信道解码器◆信道编码器和信道解码器是一种用来实现抗干扰、抗噪声的可靠数字通信技术措施。◆信道编码器是通过向信源编码数据中插入可控制的冗余数据来减少对信道噪声的影响的。

信源编码器信源解码器信道解码器信道信道编码器编码器解码器7.2.2图像编码模型

2.信道编码器与信道解码器（续1）汉明信道编码技术的基本原理：给被编码的数据后面补充足够的位数，以确保各个正确的码字之间的最小距离大于某个给定的值。

（7.35）7.2.2图像编码模型

2.信道编码器与信道解码器（续2）设一个4bit的二进制数为，当信道编码采用汉明编码时，对应的7位汉明码由下式确定：◆汉明编码的结果是一个偶数位编码。

7.2.2图像编码模型

2.信道编码器与信道解码器（续3）对汉明码的解码是通过对在编码时建立的偶校验的位串进行奇校验并检查校验字的值来实现的。（7.36）◆对于单个比特位的错误来说，是由一个非零的奇偶校验字给出。并且：2.信道编码器与信道解码器（续3）

当校验字的结果为零时，说明传输中没有错误，解码的二进制结果中的值，就是接收的传输结果。

当校验字的结果非零时，说明传输中有单比特位错误，信道解码器只需要将由校验字指出的出错的比特位的值进行翻转就可纠正传输中的单比特位错误，解码的二进制结果中的出错位翻转后的值（没有翻转的位，翻转的位），就是接收的传输结果。7.2.2图像编码模型

7.2.2图像编码模型

2.信道编码器与信道解码器（续4）例7.4

设信道编码器的输入=(0110)。（1）求信道编码器的输出码字值，若信道传输正确，请验证并说明奇校验结果正确。（2）若在传输过程中第6位的值传输错误，请验证并说明奇校验结果。7.2.2图像编码模型

2.信道编码器与信道解码器（续5）例7.4(1)已知

因为：◆所以：信道编码器输出的7个比特位为：7.2.2图像编码模型

2.信道编码器与信道解码器（续6）例7.1

（2）当传输正确时，解码器的输入应为：且：◆校验码全0，校验结果正确，说明无传输错误。正确值：7.2.2图像编码模型

2.信道编码器与信道解码器（续7）例7.1

（3）当传输不正确，且假设第6位传输错误时，解码器

的输入应为：且：◆校验码，说明第6位传输有错误。正确值：7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆在信息论中，把通过减少冗余来压缩数据的过程称为信源编码。◆信源编码器的作用就是减少或消除输入图像中的编码冗余。7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆信源编码器与信源解码器的应用模式信源编码器信源解码器信道解码器信道信道编码器编码器解码器7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆信源编码器模型：1）映射变换器{减少像素冗余}

映射变换器将输入的图像数据转换为可以减少输入图像中像素间冗余的表示格式，其输出是比原始图像数据更适合于高效压缩的图像表示形式。信道编码器或信道映射变换器符号编码器量化器图7.8信源编码器模型7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆信源编码器模型（续1）：◆典型的映射变换包括：（1）线性预测变换。如各种正交变换，应用差分映射图像编码的差分编码等预测编码；（2）酉变换。如可将图像能量集中到少数系数上的DCT变换；（3）多分辨率变换。如子带分解和小波变换等；（4）其它变换。如二值图像的游程编码等。信道编码器或信道映射变换器符号编码器量化器7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆信源编码器模型（续2）：2）量化器

量化器用于对映射变换（比如DCT变换）后的变换系数进行量化，以便产生表示被压缩图像的有限数量的符号。

利用量化器对映射变换后的变换系数进行量化会导致部分信息的损失。信道编码器或信道映射变换器符号编码器量化器7.2.2图像编码模型

3.信源编码器模型与信源解码器模型◆信源编码器模型（续3）：3）符号编码器

符号编码器的作用是对量化器输出的每一个符号分配一个码字或二进制比特流。信道编码器或信道映射变换器符号编码器量化器7.2.2图像编码模型

3.信源编码器模型与信源解码器模型3）符号编码器：符号编码器

输入X称为信源符号集，集合中的每一个元素xi称为信源符号。输出W称为代码，集合中的每一个元素wi称为码字。A称为码元集，集合中的每一个元素aj称为码元。图7.9信源符号编码器构成示意图7.2.2图像编码模型

3.信源编码器模型与信源解码器模型3）符号编码器：符号编码器符号编码器的功能：是用码元集A中的一组码元aj建立输入的信源符号xi与输出的码字wi之间的关系。也就是为信源符号集中的每一个元素xi分配一个用一组码元aj表示的码字wi。所有的码字wi都按规定的编码方式由aj来组成。7.2.2图像编码模型

3.信源编码器模型与信源解码器模型4）灰度图像的符号编码

也即，利用码元集A={0，1}，对灰度图像符号序列（也即，灰度级值0，1，…，255）的编码。

这个符号序列也即独立信源：X={,

,…,}

独立信源源符号集

中每个符号出现的概率：

P=7.2.2图像编码模型

3.信源编码器模型与信源解码器模型5）信源解码器模型信道编码器或信道符号解码器反向映射变换器反量化器7.2.3数字图像的信息熵

1.数字图像的信息熵

设有信源符号集X={x1,x2,…,xn}，信源符号出现的概率为{P(x1),P(x2)，…，P(xn)}。对X编码得到的代码为W={w1,w2,…，wn}，其中每个码字wi的比特数（长度）为l(xi)。则表示每个信源符号码字的平均长度（比特数）为（7.39）7.2.3数字图像的信息熵

2.信息熵与信源符号码字平均长度的关系

信息熵是一个系统信息含量的量化指标，通常用来作为系统优化的目标或者参数选择的判据。

信源的熵定义为其中，熵的单位是b/s，表示每个符号的比特数。（7.40）7.2.3数字图像的信息熵

例7.5

设有一个随机变量X有8种可能的状态

，每个状态都是等可能的，则该随机变量的熵为：

也就是说，为了把X的值传递给接收者，需要传输一个3比特的消息。（7.40）7.2.3数字图像的信息熵

例7.6

设有一个随机变量X有8种可能的状态{a,b,c,d,e,f,g,h}，每个状态各自的概率为{1/2,1/4,1/8,1/16,1/64,1/64,1/64,1/64}，这种情况下该随机变量的熵为：

也就是说，随机变量非均匀分布时的熵，要比随机变量均匀分布时的熵小。7.2.3数字图像的信息熵

基于以上的引例可知：

（1）可以利用非均匀分布的特点，使用尽可能短的编码来描述更可能的事件，使用更长的编码来描述不太可能的事件，就可以得到更短的平均编码长度。

比如：对于例7.6，可以使用编码串：0、10、110、1110、111100、111101、111110、111111来表示状态{a,b,c,d,e,f,g,h}。根据式（7.39），其需要传输的平均长度为7.2.3数字图像的信息熵

基于以上的引例可知：

（2）如果所有信源符号的概率都是2的指数，信源符号码字的平均长度就与随机变量的熵相等。熵是编码所需比特数的下限。例7.6

2.信息熵与信源符号码字平均长度的关系

在信息论中，信息量是指从N个相等的可能事件中选出一个事件所需的信息度量或含量。假设N的大小为2的整次幂（比如

），则信息量可表示为

将式（7.41）代入式（7.40）可得：

（7.41）（7.42）（7.40）7.2.3数字图像的信息熵

（7.42）7.2.3数字图像的信息熵

（7.39）7.2.3数字图像的信息熵

3.数字图像的信息熵

对于一幅灰度级值分布为X={0，1，…，L-1}，且其灰度级值出现的概率为P={，

，…

，}的数字图像，其信息熵定义为（7.43）7.3几种最基本的变长编码方法

变长编码的基本思想是用尽可能少的比特数表示出现概率尽可能大的灰度级，以实现数据的压缩编码。

由于利用这些编码方法得到的码字长度是不相等的，所以称为变长编码。

利用最基本的变长编码对图像进行的编码不会产生信息损失，所以这类编码方法也称为无误差编码方法，或无损编码方法。

7.3.1费诺码

费诺编码方法认为：在数字形式的码字中的0和1是相互独立的，因而其出现的概率也应是相等的（为0.5或接近0.5），这样就可确保传输的每一位码含有1比特的信息量。诺设输入的离散信源符号集为X={x0,x1,…,xn}，其出现概率为P(xi)，欲求的费诺码为W={w0,w1,…，wn}，则费诺码编码方法的步骤为：

费诺码编码方法的步骤：

（1）把输入的信源符号和其出现的概率按概率值的非递增顺序从上到下依次并列排列。（2）按概率之和相等或相近的原则把X分成两组，并给上面或概率之和较大的组赋值1，给下面或概率之和较小的组赋值0。（3）再按概率之和相等或相近的原则把现有的组分成两组，并给上面或概率之和较大的组赋值1，给下面或概率之和较小的组赋值0。（4）重复（3）的分组和赋值过程，直至每个组只有一个符号为止。（5）把对每个符号所赋的值依次排列，就可得到信源符号集X的费诺码。

例7.7设有信源符号集X={x1,x2,…,x8}，其概率分布为P(x1)=0.25，P(x2)=0.125，P(x3)=0.0625，P(x4)=0.25，P(x5)=0.0625，P(x6)=0.125，P(x7)=0.0625，P(x8)=0.0625，求其费诺码W={w1,w2,w3,w4,w5,w6,w7,w8}。

即有：P(x1)=0.25=1/4

P(x2)=0.125=1/8

P(x3)=0.0625=1/16

P(x4)=0.25=1/4

P(x5)=0.0625=1/16P(x6)=0.125=1/8P(x7)=0.0625=1/16P(x8)=0.0625=1/16

7.3.1费诺码

符号概率编码结果

1/41111/410101/810111/8100101/160100111/1601000101/16100011/160000007.3.1变长编码例7.7解：平均码字长度：

7.3.2霍夫曼编码设输入的离散信源符号集为X={x0,x1,…,xn}，其出现概率为P(xi)，欲求的霍夫曼编码为W={w0,w1,…，wn}。

1.

霍夫曼编码方法的步骤：

（1）统计信源（比如一幅图像）中的信源符号及每个信源符号出现的概率。设经统计有n个信源符号（i=0,…,n），其出现概率为

。（2）把把信源符号

和其概率

，依序按概率值的递减顺序从上到下依次排列。

（3）把最末两个具有最小概率值的信源符号的概率值合并相加得到新的概率值。（4）给最末两个具有最小概率值的信源符号的上面的信源符号编码“0”，给下面的信源符号编码“1”。（5）如果最末两个信源符号的概率值合并相加后为1.0，则转（7）；否则继续下一步。（6）把合并相加得到的新概率值与其余概率值按递减顺序从上到下依次排列，并转（3）。（7）寻找每一个信源符号到概率为1.0处的路径，并依次记录路径上的“1”和“0”，即可得到每个信源符号对应的二进制符号序列。（8）逆序逐位地写出每个信源符号对应的二进制符号序列，即可得到每个信源符号的霍夫曼编码。例7.8设有信源符号集X={x1,x2,x3,x4,x5,x6}，其概率分布分别为P(x1)=0.1，P(x2)=0.3，P(x3)=0.1，P(x4)=0.4，P(x5)=0.04，P(x6)=0.06，求其霍夫曼编码W={w1,w2,w3,w4,w5,w6}。

7.3.2霍夫曼编码

0

0.110

0.110

0.3100.410

1

0.060.04

0.40.40.40.40.6

0.30.30.30.3

0.10.1

0.2

0.10.1

例7.8解：编码过程为：

依据步骤（7），可得信源符号及其对应的二进制符号序列为：

根据步骤（8），将上述二进制符号序列逆序排列，即可得到霍夫曼编码为：W={011,00,0100,1,01010,01011}例7.87.3.2霍夫曼编码=0.1×3+0.3×2+0.1×4++0.4×1+0.04×5+0.06×5

=2.2（bit）

课堂练习：7.3.2霍夫曼编码

2.

利用霍夫曼编码进行压缩编码的方法

（1）创建霍夫曼编码表。比如，对于例7.5的霍夫曼编码

W={011,00,0100,1,01010,11010}可创建如下的霍夫曼编码表：7.3.2霍夫曼编码

2.

利用霍夫曼编码进行压缩编码的方法

（2）对信源符号进行编码，也即用码字代替信源符号。

按照例7.5中各信源符号的概率，设要压缩编码的信源符号流为：

则编码流就应为：01100000001000100111101010111100000001101011。

在信息接收端解码时，计科根据码字的长度（位数）信息，还原出原来的码值。7.3.2霍夫曼编码

3.

霍夫曼编码的优点◆当对独立信源符号进行编码时，霍夫曼编码可对每个信源符号产生可能是最少数量（最短）码元的码字。◆霍夫曼编码是所有变长编码中平均码长最短的。如果所有信源符号的概率都是2的指数，霍夫曼编码的平均长度将达到最低限，即信源的熵。◆对于二进制的霍夫曼编码，平均码字的平均长度满足关系：7.3.2霍夫曼编码【例】霍夫曼编码matlab程序。%1.输入信源符号集及其概率向量，并检查其值的合理性clc;clearall;closeall;symbol_S=input('请输入信源符号(单引号括住)集向量S=');P0=input('请输入信源符号集的概率向量P=');M=numel(symbol_S);N=numel(P0);if(M~=N)error('信源符号向量与信源符号概率向量元素个数不等！');%报错并退出endfori=1:1:Nif(P0(i)<=0)error('信源概率不能小于等于0！');%报错提示，并退出当前脚本程序

endend%2.建立各概率符号的位置索引矩阵index，以便于编码后从树根进行回朔[P,S_order]=sort(P0);%P为按升序排列的新向量，S_order为原向量P0中元素的序号Q=P;Index=zeros(N-1,N);%生成(N-1)*N的全零矩阵fori=1:N-1[Q,L]=sort(Q);Index(i,:)=[L(1:N-i+1),zeros(1,i-1)];Q=[Q(1)+Q(2),Q(3:N),1];%将Q中概率最小的两个元素合并end%3.根据以上建立的index矩阵进行回朔，获取信源编码fori=1:N-1%初始化一个由空格符组成的字符矩阵C,用于存放编码

C(i,1:N*N)=blanks(N*N);endC(N-1,N)='1';%给N-1行(最后一行)第1个元素赋1，存到C中第N-1行的N列位置C(N-1,2*N)='0';%给N-1行第2个元素赋0，存到C中第N-1行的2*N列位置fori=2:N-1%将index后一行中索引为1的编码码字填入到当前行的第1个编码位置

C(N-i,1:N-1)=C(N-i+1,N*(find(Index(N-i+1,:)==1))-...(N-2):N*(find(Index(N-i+1,:)==1)));C(N-i,N)='0';%C中第N-i行第2列的N-1个字符与第N-i行的第1个元素的前N-1个符号相同

C(N-i,N+1:2*N-1)=C(N-i,1:N-1);C(N-i,2*N)='1';forj=1:i-1%将index后１行中索引不为1的编码按左右顺序填入当前行的第3个位置开始的地方

C(N-i,(j+1)*N+1:(j+2)*N)=C(N-i+1,N*(find(Index(N-i+1,:)==j+1)-1)+...1:N*find(Index(N-i+1,:)==j+1));endend%4.形成最后的huffman编码,在H中fori=1:NH(i,1:N)=C(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);W_length(i)=length(find(abs(H(i,:))~=32));%计算每一个编码的长度end%5.将各信源符号的霍夫曼编码按输入信源符号顺序排列fori=1:Nforj=1:Nif(S_order(j)==i)H1(i,:)=H(j,:);continue;endendend%6.打印结果disp('信源符号概率对应的Huffman编码-')fori=1:Nfprintf('%s%f%s\n',symbol_S(i),P0(i),H1(i,:));endL=sum(P.*W_length);%计算平均码长fprintf('平均码字长度为：%f\n',L);【例】霍夫曼编码matlab程序。四、霍夫曼编码7.3.3几种接近最佳的变长编码输入输出Wi(信源符号i)二进制编码

B1码B2码二进制移位码00000C0C0000010001C1C0100120010C0C0C1001030011C0C1C1101140100C1C0C00C0010050101C1C1C00C0110160110C0C0C0C00C1011070111C0C0C1C00C1111100081000C0C1C0C01C0011100191001C0C1C1C01C01111010101010C1C0C0C01C10111011111011C1C0C1C01C11111100121100C1C1C0C10C00111101131101C1C1C1C10C01111110141110C0C0C0C0C10C10111111000151111C0C0C0C1C10C11111111001

表7.2

几种典型的变长变码7.3.3几种接近最佳的变长编码

1）B码

（1）B1码{自学}

（2）B2码{自学}

2）二进制移位码

{自学}7.3.4算术编码算术编码假设，对于一个独立信源来说，任一由信源符号组成的长度为N的序列的发生概率之和等于1。

根据信源符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好等于各符号序列的概率，这样每个子区间内的任意一个实数都可以用来表示对应的符号。

显然，一串符号序列发生的概率越大，对应的子区间就越宽，表达它所用的比特数就越少，因而相应的码字就越短。

1、算术编码过程（1）建立概率模型，即通过扫描统计，获得各信源符号的概率大小（2）编码过程，即扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。7.3.4算术编码

图7.15算术编码过程图示举例:设有一个四信源符号的五符号输入序列a1a2a2a3a4。（1）建立信源符号集的概率模型：通过扫描可知信源符号a1a2a3a4的出现概率依次为0.2、0.4、0.2和0.2。（2）编码方法：

编码序列

7.3.4算术编码（K=1，2，…，N）（7.47）

2、编码过程的数学描述设由M个信源符号X=x1x2…xm

组成的长度为N的输入符号序列中，各信源符号的概率分布为Pj（j=1,2,…，M；k=1,2,…,N；M≤N），[0，1）为对输入符号序列进行算术编码的初始区间，则对第k个输入符号进行算术编码的子分区间[Lk，Rk）定义为：

7.3.4算术编码7.4位平面编码

所谓位平面编码，就是将一幅灰度图像或彩色图像分解为多幅二值图像,然后对二值图像应用二值图像编码方法，以达到对多值图像编码的目的。

一幅m位的灰度级图像的灰度值可用多项式表示为：（7.49）其中，xi∈[0，1]。

也就是说，图像的同一个比特位的系数的集合就是一个二值图像，称为一个“位平面”。位平面编号从0开始，直到m-1。将m个位平面组合，显然又可以恢复原来的灰度图像。7.4.1位平面分解举例来说，对于一幅N×N的灰度图像，若每个像素用m位表示，就可以从每个像素的二进制表示中取出相同位置上的一位，这样就形成了一幅N×N的二值图像，称该二值图像为原灰度图像的一个位平面。

对于一幅256灰度级的图像来说，每个像素用一个8位的字节表示，该图像就可以分解成8个位平面，平面0由原图像中像素的最低位组成，平面1由原图像中像素的此低位组成，…，平面7由原图像中像素的最高位组成。7.4.1位平面分解原图像的一个像素对应8位位平面7(最高位)位平面0(最低位)01010101

85灰度图像图7.178位图像的位平面分解图示7.4.1位平面分解clc;clearall;closeall;img0=imread('d:\0_matlab图像课编程\star_img.jpg');subplot(3,3,1);imshow(img0);title('原图像');[h,w]=size(img0);fork=1:8fori=1:hforj=1:w%bitget函数先将img0(i,j)处灰度值分解为二进制串，然后取第k位的值

bit_mp(i,j)=bitget(img0(i,j),k);endendsubplot(3,3,k+1);imshow(bit_mp,[]);K1=num2str(k);mark=['第',K1,'个位平面'];title(mark);end五、位平面编码

【例】从灰度图像分解位平面图像的Matlab程序。【例】从灰度图像分解位平面图像的matlab程序。五、位平面编码

图7.19一幅8位图像及其该图像的8个位平面二值图像7.4.1位平面分解7.4.2位平面的格雷码分解编码多数图像中的大多数相邻像素值具有渐变的特征，但若采用二进制码进行位平面分解，就会导致各位平面中相关性的减小。比如，若灰度图像中的两个相邻像素是127和128，它们显然比较接近，但其二进制编码却分别为01111111和10000000也即,灰度图像中相邻像素间的很小变化，却引起了所有位平面值的突变，从而降低了位平面图像的相关性，也即降低了位平面图像的压缩效率。

由于两个相邻值的格雷码之间只有一位是不同的，这样就可保持相邻像素间较强的相关性，所以一般采用格雷码（Gray）进行位平面分解编码。7.4.2位平面的格雷码分解编码

采用格雷码进行位平面分解编码的思想是:如果用一个m位的灰度编码gm-1…g2g1g0表示图像，那么图像中这个m位的灰度编码gm-1…g2g1g0的所有gi就组成了第i个位平面二值图像。7.4.2位平面的格雷码分解编码（7.50）

设反映灰度值大小的m位二进制编码为xm-1…x2x1x0，与其对应的m位格雷码为gm-1…g2g1g0

，则有：7.4.2位平面的格雷码分解编码比如：127：01111111而对于：128：

10000000对应的格雷码为：00000000对应的格雷码为：10000000◆仅有一位不同。7.4.2位平面的格雷码分解编码7.5游程编码

◆一般把具有相同灰度值的一些像素组成的序列称为一个游程。

◆把取相同灰度值的若干连续像素点的数目称为游程长度，简称游长。

◆在黑白图像中，像素点为黑和白，或者说像素只取0和1两个灰度值，这样，就把连续白点和连续黑点的数目分别称为白长和黑长。

◆因为黑白图像像素点只取两个灰度值，所以与灰度图像相比，黑白图像相邻像素点的相关性更强，游程编码正好利用了这种相关性。

◆游程编码的基本思想是：只存储一个代表某个灰度值的码，后面是它的游程长度，这样同样的灰度值码就不必存储多次。

7.5游程编码——一维游程编码

在编码时，对每一行的第一个像素要有一个标志码，以区分该行是以白长开始还是以黑长开始，并给出其编码。对于后面的游长，只要给出相应游长的编码。

决定游程长度值最通常的约定是：（1）指定每一行第一个游程的值；（2）假设每一行从白色游程开始。如果该行是从黑色游程开始，则记这个游程长度为0。国际传真标准CCITTT.4（G3）采用的是一维游程编码。编码方法是：游长的霍夫曼编码分为形成码和终止码两种。对于位于0～63之间的游长，用单个的码字，即终止码表示；对于大于63的游长，用一个形成码和一个终止码的组合来表示。其中，形成码表示实际游长的64的最大倍数值，终止码表示其余小于64的差值。

7.5游程编码——一维游程编码

表7.4国际传真标准ITU（CCITTT.4G3）终止码表

游长白长码字黑长码字

000110101000011011110001110102011111310001041011011

5

1100

0011

6

1110

0010

┇

┇

┇63001101000000011001117.5游程编码——一维游程编码

表7.5国际传真标准ITU（CCITTT.4G3）形成码表

游长白长码字（码字）黑长码字

641101100000011111281001000011001000 192010111000011001001┇┇┇17280100110110000001100101

1729 00000001000（黑白码字开始相同）

185600000001100┇┇25600000000111117.5游程编码——一维游程编码

二维游程编码是一种基于相对地址编码原理的编码方法，通过对黑白过渡点（从白到黑，或从黑到白后的一个比特位置称为过渡点）相对于当前编码行中参考像素的位置进行编码，不仅利用了二值图像中每一行内相邻像素的相关性，而且也利用了当前编码行与参考行（前一行）的行间像素之间的相关性。7.5游程编码——二维游程编码

7.6变换编码

变换编码以信号处理中的正交变换的性质为理论基础，基本依据是：

（1）正交变换可保证变换前后信号的能量保持不变；

（2）正交变换具有减少原始信号中各分量的相关性及将信号的能量集中到少数系数上的功能。

所谓变换编码，是指以某种可逆的正交变换把给定的图像变换到另一个数据域（如频域），从而利用新的数据域的特点，用一组非相关数据（系数）来表示原图像，并以此来去除或减小图像在空间域中的相关性，将尽可能多的信息集中到尽可能少的变换系数上，使多数系数只携带尽可能少的信息，实现用较少的数据表示较大的图像数据信息，进而达到压缩数据的目的。7.6.1变换编码的过程◆变换编码过程由以下四步组成：（1）将待编码的N×N的图像分解成(N/n)2个大小为n×n的子图像。通常选取的子图像大小为8×8或16×16，即n等于８或16。（2）对每个子图像进行正交变换（如DCT变换等），得到各子图像的变换系数。这一步的实质是把空间域表示的图像转换成频率域表示的图像。（3）对变换系数进行量化。（4）使用霍夫曼变长编码或游程编码等无损编码器对量化的系数进行编码，得到压缩后的图像（数据）。图7.20变换编码系统框图压缩图像构造n×n个子图像系数量化器正变换符号编码器原始图像数据量化方案(量化函数或量化表)编码方案及表说明7.6.1变换编码的过程◆变换编码系统的实现：7.6.2子图像尺寸选择

◆子图像的大小与变换编码的误差和变换所需的计算量等有关。

◆在大多数应用中，把图像进一步分割成子图像块要求满足以下两个条件：一是相邻子图像块之间的相关性（冗余）要减少到某种可接受的程度；二是子图的长和宽应是2的整数次幂。◆最常采用的子图像尺寸为8×8和16×16。7.6.3变换的选择

1.变换系数

如7.1.3节所述，对于N×N的图像f(x,y)和该图像的二维正向离散变换T(u,v)，有：（7.51）(7.52)其中，H(x,y,u,v)称为变换核函数（正变换与反变换核函数相同），也称为基函数或基图像；式(7.52)中的T(u,v)称为变换系数。

7.6.3变换的选择

用n替换式(7.52)中的N，则一幅大小为n×n的子图像f(x,y)可以表示成它的二维变换的函数：

(7.53)

其中：反变换核函数h(x,y,u,v)只依赖于参数x，y，u，v；与f(x,y)和T(u,v)的值无关。

所以，h(x,y,u,v)可看作是由式(7.53)定义的子图像序列的一组基函数或基图像。

(7.54)7.6.3变换的选择

进一步将式(7.53)表示成：为：

其中，(7.55)显然，式(7.54)显式地将F定义成n2个n×n矩阵的线性组合，这些矩阵是式(7.53)的子图像序列的基函数或基图像，T(u,v)是变换系数。7.6.3变换的选择

2.图像的均方差如果把变换系数的模板函数定义为：

(7.56)(7.57)那么，的一个截断近似可定义为：

显然，利用的截断功能就可消除掉式(7.48)中对求和贡献最少的系数。7.6.3变换的选择

2.图像的均方差（续1）且子图像F和它的近似之间的均方误差为：(7.58)也即有：

(7.58)其中，是变换系数在(u,v)处的方差。

7.6.3变换的选择

(7.58)由式（7.56）和式（7.58）可知，当T(u,v)满足指定的截断准则时，的值为1，否则其值为0。所以总的均方差近似误差是所有截断的变换系数的方差之和。一个能把最多的信息集中到最少的系数上去的变换提供了最好的子图近似，因此所产生的重建误差最小。

(7.56)7.6.3变换的选择

◆由于DCT在信息集中能力和计算复杂性方面的综合优势已经取得了较多的应用。

◆对于大多数自然图像来说，DCT能将最多的信息分配在最少的系数之中，还能使被称为“分块噪声”的子图边缘可见的块效应达到最小。

◆变换编码通常采用的变换包括：DCT(离散余弦变换)、DFT（离散傅里叶变换）、WHT（沃尔什-哈达玛变换）和KLT（卡-洛变换）等实现。

3.几种变换的性能7.6.4变换系数的量化和编码1.区域编码

所谓区域编码，就是