Chapter07_图像压缩编码

图像压缩编码

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

图像压缩编码基础

图像压缩的基本概念

信息相关

在绝大多数图像的像素之间， 各像素行和帧之间存在着较强的相关性
从统计观点出发，就是每个像素的灰度值（或颜色值）总是和其周围的其它像素的灰度值（或颜色值）存在某种关系，应用某种编码方法减少这些相关性就可实现图像压缩

【引例】

上图的黑白像素序列共41位
新的编码只需21位：1，0101，1111，0111，1011，0011

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

信息冗余

从信息论的角度来看， 压缩就是去掉信息中的冗余。即保留确定信息，去掉可推知的确定信息，用一种更接近信息本质的描述来代替原有的冗余描述

图像数据存在的冗余可分为三类：
① 编码冗余；② 像素间的冗余；③ 心里视觉冗余

• 编码冗余

  由于大多数图像的直方图不是均匀(水平)的，所以图像中某个或某些灰度级会比其它灰度级具有更大的出现概率，如果对出现概率大和出现概率小的灰度级都分配相同的比特数，必定会产生编码冗余，即如果一个图像的灰度级编码，使用了多于实际需要的编码符号，就称该图像包含了编码冗余

  【例】

  

• 像素间的冗余

  所谓“像素间的冗余”，是指单个像素携带的信息相对较少，单一像素对于一幅图像的多数视觉贡献是多余的， 它的值可以通过与其相邻的像素的值来推断

  【例】

  

• 心里视觉冗余

  心里视觉冗余是指，在正常的视觉处理过程中那些不十分重要的信息，即一些信息在一般的视觉处理中，比其他信息的相对重要程度要小，这种信息就被称为视觉心理冗余

信源编码及其分类

• 信源编码的概念：图像压缩的目标是在满足一定的图像质量的条件下，用尽可能少的比特数来表示原图像，以减少图像的存储容量和提高图像的传输效率，在信息论中，把这种通过减少冗余数据来实现数据压缩的过程称为信源编码
• 信源编码的分类：无失真编码和有失真编码
  • 无失真压缩也称为无损压缩，是一种在不引入任何失真的条件下使表示图像的数据比特率为最小的压缩方法
  • 有失真压缩也称为有损压缩，是一种在一定比特率下获得最佳保真度，或在给定的保真度下获得最小比特率的压缩方法

图像编码模型

• 信道编码器和信道解码器是一种用来实现抗干扰、抗噪声的可靠数字通信技术措施，信道编码器是通过向信源编码数据中插入可控制的冗余数据来减少对信道噪声的影响的
• 信源编码器的作用就是减少或消除输入图像中的编码冗余

信源编码器模型

• 映射变换器（减少像素冗余）

  映射变换器将输入的图像数据转换为可以减少输入图像中像素间冗余的表示格式，其输出是比原始图像数据更适合于高效压缩的图像表示形式

  典型的映射变换包括：线性预测变换、酉变换、多分辨率变换等

• 量化器

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

  利用量化器对映射变换后的变换系数进行量化会导致部分信息的损失

• 符号编码器

  符号编码器的作用是对量化器输出的每一个符号分配一个码字或二进制比特流

  

  输入 X 称为信源符号集，集合中的每一个元素 $x_i$称为信源符号
  输出W 称为代码，集合中的每一个元素 $w_i$ 称为码字
  A 称为码元集，集合中的每一个元素 $a_j$ 称为码元

信源解码器模型

数字图像的信息熵

信源符号码字平均长度

设有信源符号集 X = { x 1 , x 2 , … , x n } X=\{ x_1,x_2 ,…,x_n \} X={x1​,x2​,…,xn​}，信源符号出现的概率为 { P ( x 1 ) , P ( x 2 ) ， … ， P ( x n ) } \{P(x_1),P(x_2)，…，P(x_n)\} {P(x1​),P(x2​)，…，P(xn​)} ，对 X 编码得到的代码为 W = { w 1 , w 2 , … ， w n } W=\{w_1,w_2,…，w_n\} W={w1​,w2​,…，wn​}，其中每个码字 $w_i$ 的比特数（长度）为 $L(x_i)$
则表示每个信源符号码字的平均长度（比特数）为：
$$\overline{L}=\sum _{i=1}^{n}P(x_i)\cdot l(x_i)$$

信息熵

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

信源的熵定义为：$H(X)=\sum _{i=1}^{n}P(x_i)\cdot lo{g}_{2}P(x_i)$ ，熵的单位是b/s，表示每个符号的比特数

【例1】设有一个随机变量 X 有8 种可能的状态 $x_i(i=1,2,...,8)$ ，每个状态都是等可能的，则该随机变量的熵为：
$$H(X)=\sum _{i=1}^8\frac{1}{8}\cdot lo{g}_2\frac{1}{8}=-8\times \frac{1}{8}lo{g}_2\frac{1}{8}=3bits$$
也就是说，为了把 X 的值传递给接收者，需要传输一个 3 比特的消息

【例2】设有一个随机变量X 有8 种可能的状态 { a , b , c , d , e , f , g , h } \{a,b,c,d,e,f,g,h\} {a,b,c,d,e,f,g,h}，每个状态各自的概率为 { 1 2 , 1 4 , 1 8 , 1 16 , 1 64 , 1 64 , 1 64 , 1 64 } \{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{64},\frac{1}{64},\frac{1}{64},\frac{1}{64}\} {21​,41​,81​,161​,641​,641​,641​,641​} ，这种情况下该随机变量的熵为：
$$H(X)=-\frac{1}{2}lo{g}_2\frac{1}{2}-\frac{1}{4}lo{g}_2\frac{1}{4}-\frac{1}{8}lo{g}_2\frac{1}{8}-\frac{1}{16}lo{g}_2\frac{1}{16}-4\times \frac{1}{64}lo{g}_2\frac{1}{64}\}=2bits$$
也就是说，随机变量非均匀分布时的熵，要比随机变量均匀分布时的熵小

信源符号码字的平均长度就与随机变量的熵相等，熵是编码所需比特数的下限

信息量

信息量是指从N个相等的可能事件中选出一个事件所需的信息度量或含量。假设 N 的大小为 2 的整次幂（比如 $N=2^n$ ），则信息量可表示为：
$$I(x)=lo{g}_{2}N=-lo{g}_2\frac{1}{N}=-lo{g}_{2}P(x)$$
每个信源符号的信息量实质上反映的是该信源符号的编码长度

变长编码

费诺码

费诺编码方法认为：在数字形式的码字中的 0 和 1 是相互独立的，因而其出现的概率也应是相等的（为0.5或接近 0.5），这样就可确保传输的每一位码含有 1 比特的信息量

假设输入的离散信源符号集为 X = { x 0 , x 1 , … , x n } X=\{x_0,x_1,…,x_n\} X={x0​,x1​,…,xn​}，其出现概率为 $P(x_i)$，欲求的费诺码为 W = { w 0 , w 1 , … , w n } W=\{w_0,w_1,…,w_n\} W={w0​,w1​,…,wn​}，则费诺码编码方法的步骤为：

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

【例】设有信源符号集 X = { x 1 , x 2 , … , x 8 } X=\{x_1,x_2,…,x_8\} X={x1​,x2​,…,x8​}，其概率分布为 $P(x_1)=0.25$，$P(x_2)=0.125$，$P(x_3)=0.0625$，$P(x_4)=0.25$，$P(x_5)=0.0625$，$P(x_6)=0.125$，$P(x_7)=0.0625$，$P(x_8)=0.0625$，求其费诺码 W = { w 1 , w 2 , w 3 , w 4 , w 5 , w 6 , w 7 , w 8 } W=\{w_1,w_2,w_3,w_4,w_5,w_6,w_7,w_8\} W={w1​,w2​,w3​,w4​,w5​,w6​,w7​,w8​}

【解】由题意可得：
$P(x_1)=0.25=\frac{1}{4}$，$P(x_2)=0.125=\frac{1}{8}$，
$P(x_3)=0.0625=\frac{1}{16}$，$P(x_4)=0.25=\frac{1}{4}$，
$P(x_7)=0.0625=\frac{1}{16}$，$P(x_6)=0.125=\frac{1}{8}$，
$P(x_7)=0.0625=\frac{1}{16}$，$P(x_8)=0.0625=\frac{1}{16}$

平均码字长度：
$$\begin{array}{rl}\overline{L}& ==\sum _{i=1}^{8}P(x_i)\cdot l(x_i)\\ & =\frac{1}{4}\times 2+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{8}\times 3+\frac{1}{16}\times 4+\frac{1}{16}\times 4+\frac{1}{16}\times 4+\frac{1}{16}\times 4\\ & =\frac{11}{4}(bit)\end{array}$$

霍夫曼编码

假设输入的离散信源符号集为 X = { x 0 , x 1 , … , x n } X=\{x_0,x_1,…,x_n\} X={x0​,x1​,…,xn​}，其出现概率为 $P(x_i)$，欲求的费诺码为 W = { w 0 , w 1 , … , w n } W=\{w_0,w_1,…,w_n\} W={w0​,w1​,…,wn​}，则霍夫曼编码方法的步骤为：

1. 统计信源（比如一幅图像）中的信源符号及每个信源符号出现的概率
   设经统计有 n 个信源符号 $x_i$（i=0, …,n），其出现概率为 $P(x_i)$
2. 把把信源符号 $x_i$ 和其概率 $P(x_i)$ ，依序按概率值的递减顺序从上到下依次排列
3. 把最末两个具有最小概率值的信源符号的概率值合并相加得到新的概率值
4. 给最末两个具有最小概率值的信源符号的上面的信源符号编码“0”，给下面的信源符号编码“1”
5. 如果最末两个信源符号的概率值合并相加后为 1.0，则转 7；否则继续下一步
6. 把合并相加得到的新概率值与其余概率值按递减顺序从上到下依次排列，并转 3
7. 寻找每一个信源符号到概率为 1.0 处的路径，并依次记录路径上的 “1” 和 “0” ，即可得到每个信源符号对应的二进制符号序列
8. 逆序逐位地写出每个信源符号对应的二进制符号序列，即可得到每个信源符号的霍夫曼编码

【例】设有信源符号集 X = { x 1 , x 2 , … , x 6 } X=\{x_1,x_2,…,x_6\} X={x1​,x2​,…,x6​}，其概率分布为 $P(x_1)=0.1$，$P(x_2)=0.3$，$P(x_3)=0.1$，$P(x_4)=0.4$，$P(x_5)=0.04$，$P(x_6)=0.06$，求其霍夫曼码 W = { w 1 , w 2 , w 3 , w 4 , w 5 , w 6 } W=\{w_1,w_2,w_3,w_4,w_5,w_6\} W={w1​,w2​,w3​,w4​,w5​,w6​}

依据步骤 7 ，可得信源符号及其对应的二进制符号序列为：
{ x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } \{x_1,x_2,x_3,x_4,x_5,x_6\} {x1​,x2​,x3​,x4​,x5​,x6​} ➡️ {110，00，0010，1，11010，01010}

根据步骤 8 ，将上述二进制符号序列逆序排列，即可得到霍夫曼编码为：
{011，00，0100，1，01011，01010}

平均码字长度：
$$\begin{array}{rl}\overline{L}& =\sum _{i=1}^{6}P(x_i)\cdot l(x_i)\\ & =0.1\times 3+0.3\times 2+0.1\times 4+0.4\times 1+0.04\times 5+0.06\times 5\\ & =2.2(bit)\end{array}$$
霍夫曼编码的优点：

• 当对独立信源符号进行编码时，霍夫曼编码可对每个信源符号产生可能是最少数量（最短）码元的码字
• 霍夫曼编码是所有变长编码中平均码长最短的。如果所有信源符号的概率都是2的指数，霍夫曼编码的平均长度将达到最低限，即信源的熵
• 对于二进制的霍夫曼编码，平均码字的平均长度满足关系： $H<\overline{L}<H+1$

位平面编码

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

位平面分解：对于一幅 N×N 的灰度图像，若每个像素用 m 位表示，就可以从每个像素的二进制表示中取出相同位置上的一位，这样就形成了一幅 N×N 的二值图像，称该二值图像为原灰度图像的一个位平面

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

格雷码

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

由于两个相邻值的格雷码之间只有一位是不同的，这样就可保持相邻像素间较强的相关性，所以一般采用格雷码（Gray）进行位平面分解编码
格雷码进行位平面分解编码的思想：如果用一个 m 位的灰度编码 $g_{m-1}\dots g_2{g}_1{g}_0$ 表示图像，那么图像中这个 m 位的灰度编码 $g_{m-1}\dots g_2{g}_1{g}_0$ 的所有 $g_i$ 就组成了第 i 个位平面二值图像

【举例】