Ch8 图像压缩

8.1 8.2名词解释(基本含义)，海明码

8.3五大概念理解(自&互信息、信道容量、熵)，物理意义

8.4 8.5 霍夫曼编码+LZW编码+无损编码有损编码看作业题

[TOC]

基础知识(Basis of Image Compression)

图像压缩要解决的问题是：尽量减少表示数字图像所需的数据量。减少数据量的基本原理是去除冗余数据。

“数据压缩”这个术语指的是减少表示给定信息量所需的数据量。必须明确区分数据和信息。

数据是传递信息的手段。由于能够使用各种数量的数据来表示相同的信息量，因此说包含无关或重复信息的表示中含有冗余数据。数据冗余是数字图像压缩中的主要问题，它是一个可以用数学量化的实体。

如果\(n_1\)和\(n_2\)分别表示两个表示相同信息的数据集中的信息单元数量，那么第一个数据集（用\(n_1\)表示）的相对数据冗余度\(R_D\)可以定义为: \[ R_D = 1-\frac{1}{C_R},\quad C_R=\frac{n_1}{n_2} \] \(C_R\)被称为压缩率。

当\(n_1=n_2\)时，\(C_R = 1\)，\(R_D=0\)，这意味着第一个数据集相对于第二个数据集没有冗余数据。
当\(n_2\le n_1\)时，意味着有显著的压缩和高冗余度。
当\(n_2\ge n_1\)时，表明第二个数据集中包含的数据量远远超过原始表达的数据量。

在数字图像压缩中，\(n_1\)通常是将图像表示为一个二维灰度值阵列所属需要的比特数。二维灰度矩阵是我们查看和解释图像的首选方式，但是当其变成紧凑的图像表示时，这些格式并不是最优的。二维灰度阵列能被识别和利用的主要三种数据冗余：

编码冗余	空间和时间冗余	无关信息
编码：表示信息主体or事件集合的符号系统。	空间相关：多数二维灰度值阵列中，每个像素与相邻像素相似。	含有被人类视觉系统所忽略或与期望用途无关的信息。
码字：每条信息被赋予的一系列编码符号。	在相关像素表示中，信息被不必要重复。	消除这种信息会导致定量信息的丢失，这种信息的去除称为量化。
码字长度：每个码字中符号的数量。	时间相关：相邻帧中的像素相似。	---
多数的二维灰度值阵列中，用于表示灰度的8bit编码所包含的bit数，要比表示灰度所需的bit多。	e.g. 视频序列	---

符号：指字母、数字、bit等。

编码冗余

假设一个在区间\([0,1]\)内的离散随机变量\(r_k\)表示图像的灰度级，每个灰度级出现的概率为: \[ p_r(r_k)=\frac{n_k}{MN}, k = 0,1,\cdots,L - 1 \] 如果\(l(r_k)\)表示用于表示每个\(r_k\)的比特数，那么表示每个像素所需的平均比特数为: \[ \begin{align}L_{avg}&=\sum_{k = 0}^{L - 1}l(r_k)p_r(r_k)\\ &=\sum_{k = 0}^{L - 1}l(r_k)\frac{n_k}{MN}\\ MNL_{avg}&=\sum_{k = 0}^{L - 1}l(r_k) n_k \end{align} \] 对大小为\(M\times N\)的图像进行编码所需的比特数为\(MNL_{avg}\)。

例：变长编码的计算

code1使用 8 bit编码：\(L_{avg}=8\)

code2使用变长编码(根据出现概率编码)： \[ L_{avg}=0.25*2+0.47+0.25*3+0.03*3=1.81\\ MNL_{avg}=256*256*1.81\\ C=\frac{8}{1.81}=4.42\\ R=1-\frac 1{C}=1-\frac{1}{4.42}=0.774 \] 因此冗余77.4%。

空间冗余

考虑图 (a)和图 (b)所示的图像。如图(c)和图(d)所示,这些图像实质上有同样的直方图。同时要注意,这两幅直方图都是具有三个波峰的,表明灰度级存在三个主要的值域。

因为这些图像中的灰度级的出现概率不是等可能性的,所以可以使用变长编码减少由于对像素进行统一长度的编码或自然二进制编码带来的编码冗余。

然而,编码处理不会改变图像的像素之间相关性的级别。换句话说,用于表示每幅图像的灰度级的编码与像素之间的相关性无关。这些相关来自于图像中对象之间的结构或几何关系。

图(e)和(f)分别展示了沿每幅图像的一条线计算出的自相关系数。 \[ \gamma(\Delta n)=\frac{A(\Delta n)}{A(0)}\\ A(\Delta n)=\frac{1}{N-\Delta n}\sum_{y = 0}^{N - 1-\Delta n}f(x,y)f(x,y+\Delta n) \]

保真度准则

删除"无关视觉"信息会损失真实或定量的图像信息。由于出现信息损失，因此需要一种方法来量化损失。

评价标准:

客观保真度准则

主观保真度准则

例：客观保真度准则

对于任意的\(x\)和\(y\)值，\(f(x,y)\)与\(\hat{f}(x,y)\)之间的误差\(e(x,y)\)可定义为: \[ e(x,y)=\hat{f}(x,y) - f(x,y) \] 这样两幅图像之间的总误差为: \[ \sum_{x = 0}^{M - 1}\sum_{y = 0}^{N - 1}[\hat{f}(x,y) - f(x,y)] \] \(f(x,y)\)与\(\hat{f}(x,y)\)之间的均方根误差\(e_{rms}\)则是该平方误差的平方根: \[ e_{rms}=\left[\frac{1}{MN}\sum_{x = 0}^{M - 1}\sum_{y = 0}^{N - 1}[\hat{f}(x,y) - f(x,y)]^{2}\right]^{1/2} \]

图像压缩模型(Image Compression Model)

一个压缩系统由两个不同的结构块组成：一个编码器和一个解码器。图像\(f(x,y)\)输入系统后得到输出图像\(\hat f(x,y)\)。一般来说，\(\hat{f}(x,y)\)可能是也可能不是\(f(x,y)\)的精确副本：

如果是，该系统是无误差或信息保留的；
如果不是，重建图像中会存在一定程度的失真。

图中所示的编码器和解码器都由两个相对独立的功能或子块组成：source/channel(信源/信道) ,encoder/decoder(编码/解码)

信源编/解码器(The Source Encoder and Decoder)

信源编码器负责减少或消除输入图像中的任何编码、像素间或心理视觉冗余。

信源编码器: 映射器、量化器和符号编码器
信源解码器: 符号解码器和逆映射器

信道编/解码器(The Channel Encoder and Decoder)

信道编码器和解码器旨在通过在源编码数据中插入受控形式的冗余来减少信道噪声的影响。由于信源编码器的输出几乎没有冗余，没有这种“受控冗余”，它将对传输噪声高度敏感。

汉明码(Hamming encoder and decoder)

汉明编码器和解码器是在被编码数据中加入足够的比特，以确保有效码字之间必须有最少数量的比特变化(码字间变化的位数最小)。

7位汉明(7,4)码字 ：

将3位冗余码加到4位字中，使任意两个有效码字间的距离为3，则所有的1 bit错误可以检测并纠正。 \[ \begin{align} h_1=b_3\oplus b_2\oplus b_0\quad\quad &h_3=b_3\\ h_2=b_3\oplus b_1\oplus b_0\quad\quad& h_5=b_2\\ h_4=b_2\oplus b_1\oplus b_0\quad\quad &h_6=b_1\\ &h_7=b_0 \end{align} \] 为将汉明码解码，信道解码器必须为先前设立的偶校验的各个字段进行奇校验并检查译码值。1bit错误由非零奇偶校验字\(c_4c_2c_1\)给出，其中： \[ c_1=h_1\oplus h_3\oplus h_5\oplus h_7\\ c_2=h_2\oplus h_3\oplus h_6\oplus h_7\\ c_4=h_4\oplus h_5\oplus h_6\oplus h_7 \] 如果找到一个非零值，则解码器就只需简单地在校验字指出地位置补充码字比特。

信息论要素(Elements of Information Theory)

信息论的基本前提是信息的产生可以被建模为一个概率过程，并且可以以符合直觉的方式进行度量。一个以概率\(P(E)\)发生的随机事件\(E\)被认为包含\(I(E)\)单位的信息。 \[ I(E)=\log\frac{1}{P(E)}=-\log P(E) \] 这个量\(I(E)\)通常被称为\(E\)的自信息。公式中对数的底数决定了用于度量信息的单位。如果使用以\(m\)为底的对数，度量结果的单位被称为\(m\)元单元。如果选择底数为2，得到的信息单位被称为比特。

信息信道(The Information Channel)

当自信息在信息源与信息用户之间传送时，称信息源与信息用户之间通过信息信道相连。信息信道时连接信源和用户的物理媒介。

假设图中的信息源从一个有限或可数无限的可能符号集中生成一个随机符号序列。信源的输出是离散的随机变量。

信源符号集\(\{a_1,a_2,\cdots,a_J\}\)被称为源字母表\(A\)，集合中的元素被称为符号或字母。信源产生符号\(a_j\)的概率是\(P(a_j)\)，并且： \[ \sum_{j = 1}^{J}P(a_j)=1 \] 一个\(J\times1\)向量\(\mathbf{z}=[P(a_1),P(a_2),\cdots,P(a_J)]^T\)通常被用来表示所有信源符号概率\(\{P(a_1),P(a_2),\cdots,P(a_J)\}\)。有限总体集合\((A,\mathbf{z})\)完整地描述了信息源。

离散信源产生符号\(a_j\)的概率是\(P(a_j)\)。产生单一信源符号所产生的自信息是\(I(a_j)=-\log P(a_j)\)。

如果产生\(k\)个信源符号，根据大数定律，对于足够大的\(k\)，符号\(a_j\)（平均而言）将被输出\(kP(a_j)\)次。因此，从\(k\)次输出中获得的平均自信息是: \[ -kP(a_1)\log P(a_1)-kP(a_2)\log P(a_2)-\cdots -kP(a_J)\log P(a_J)\\ or \quad-k\sum_{j = 1}^{J}P(a_j)\log P(a_j) \]

每个信源输出的平均信息，记为\(H(\mathbf{z})\)： \[ H(\mathbf{z})=-k\sum_{j = 1}^{J}P(a_j)\log P(a_j) \]

这个量被称为信源的不确定性或熵。它定义了通过观察单个信源输出所获得的平均信息量。随着其值的增加，与信源相关的不确定性和信息量也增加。如果信源符号具有相同的概率，熵或不确定性达到最大值，并且信源在每个信源符号上提供最大可能的平均信息量。

因为我们在图中将信道的输入建模为离散随机变量，传递到信道输出的信息也是离散随机变量\(B:\{b_1,b_2,\cdots,b_K\}\)。信息用户接收到符号\(b_k\)的概率是\(P(b_k)\)。有限集\((B,\mathbf{v})\)，其中\(\mathbf{v}=[P(b_1),P(b_2),\cdots,P(b_K)]^T\)，完整地描述了信道输出，从而也描述了用户接收到的信息。

给定信道输出的概率\(P(b_k)\)和信源的概率分布\(\mathbf{z}\)通过以下表达式相关联： \[ P(b_k)=\sum_{j = 1}^{J}P(b_k|a_j)P(a_j) \] 其中\(P(b_k|a_j)\)是在信源符号\(a_j\)产生的条件下，输出符号\(b_k\)被接收的条件概率。

这些条件概率排列成一个\(K×J\)矩阵\(Q\)： \[ Q = \begin{pmatrix} P(b_1|a_1) & P(b_1|a_2) & \cdots & P(b_1|a_J) \\ P(b_2|a_1) & P(b_2|a_2) & \cdots & P(b_2|a_J) \\ \vdots & \vdots & \ddots & \vdots \\ P(b_K|a_1) & P(b_K|a_2) & \cdots & P(b_K|a_J) \end{pmatrix} \] 完整输出字母表的概率分布可以由\(\mathbf{v}=Q\mathbf{z}\)计算得出。

矩阵\(Q\)，其元素\(q_{kj}=P(b_k|a_j)\)，被称为前向信道传输矩阵或简称为信道矩阵。

为决定\(Q\)的信道容量，比如在信息用户观察某一特定输出\(b_k\)的假设下，先计算信息源的熵。每个\(b_k\)都有一个条件熵函数，这个条件熵函数，记为\(H(\mathbf{z}|b_k)\)，可以写成： \[ H(\mathbf{z}|b_k)=-\sum_{j = 1}^{J}P(a_j|b_k)\log P(a_j|b_k) \] \(P(a_j|b_k)\)是在用户接收到\(b_k\)的条件下，符号\(a_j\)由信源发送的概率。这个表达式在所有\(b_k\)上的期望值是： \[ \begin{align}H(\mathbf{z}|\mathbf{v})&=\sum_{k = 1}^{K}H(\mathbf{z}|b_k)P(b_k)\\ &=-\sum_{j = 1}^{J}\sum_{k = 1}^{K}P(a_j,b_k)\log P(a_j|b_k)\end{align} \] \(P(a_j,b_k)\)是\(a_j\)和\(b_k\)的联合概率。也就是说，\(P(a_j,b_k)\)是\(a_j\)被发送且\(b_k\)被接收的概率。

\(H(\mathbf{z}|\mathbf{v})\)被称为\(\mathbf{z}\)相对于\(\mathbf{v}\)的疑义度(条件信息量总平均值)：表示在观察到由其产生的输出符号的情况下，一个信源符号的平均信息量。

\(H(\mathbf{z})\)是一个信源符号的平均信息，假设不了解输出符号的情况，那么\(H(\mathbf{z})\)与\(H(\mathbf{z}|\mathbf{v})\)的差是在观察到单个输出符号时接收到的平均信息。这个差，记为\(I(\mathbf{z},\mathbf{v})\)，被称为\(\mathbf{z}\)和\(\mathbf{v}\)的互信息： \[ \begin{align}I(\mathbf{z},\mathbf{v})&=H(\mathbf{z})-H(\mathbf{z}|\mathbf{v})\\ &=\sum_{j = 1}^{J}\sum_{k = 1}^{K}P(a_j,b_k)\log\frac{P(a_j,b_k)}{P(a_j)P(b_k)}\\ &=\sum_{j = 1}^{J}\sum_{k = 1}^{K}P(a_j)q_{kj}\log\frac{q_{kj}}{\sum_{i = 1}^{J}P(a_i)q_{ki}} \end{align} \] 记\(P(a_j)=P(a_j,b_1)+P(a_j,b_2)+\cdots +P(a_j,b_K)\)，得到上式。

观察信息信道的单个输出时接收到的平均信息量是输入或信源符号概率向量\(\mathbf{z}\)和信道矩阵\(Q\)的函数。\(I(\mathbf{z},\mathbf{v})\)的最小可能值为零，当输入和输出符号在统计上独立时会出现这种情况，此时\(P(a_j,b_k)=P(a_j)P(b_k),\log 1 =0\)。在向量\(\mathbf{z}\)中所有可能的信源概率选择上，\(I(\mathbf{z},\mathbf{v})\)的最大值是由信道矩阵\(Q\)描述的信道容量\(C\)，即: \[ C=\max_{\mathbf{z}}[I(\mathbf{z},\mathbf{v})] \] 信道容量定义了信息能够可靠地通过信道传输的最大速率。此外，信道的容量不依赖于信源的输入概率(即如何使用信道)，而是仅由定义信道的条件概率函数决定。

无误差压缩(Error-Free Compression)

本节重点介绍经典的、主要的无误差压缩策略，通常能提供 2 到 10 的压缩率。而且，它们对二进制图像和灰度图像同样适用。

无误差压缩技术通常由两个相对独立的操作组成：

设计一种图像的替代表示法，以减少像素间的冗余；
对这种表示进行编码以消除编码冗余。

变长编码(Variable-Length Coding)

无误差图像压缩的最简单方法就是减少仅有的编码冗余。编码冗余通常存在于图像灰度级的自然二进制编码过程中。这样做需要变长编码结构,它可把最短的码字赋予出现概率最大的灰度级对于构造这样的码字,这里分析几种最佳的和接近最佳的编码技术。这些技术都是使用信息论的语言进行表达的。实际上,信源符号既可能是图像灰度级,也可能是灰度级映射操作的输出如素差异或行程宽度等)。

哈夫曼编码(Huffman coding)

算术编码(Arithmetic coding)

算术编码只为整个信源符号序列分配一个算术码字，这个码字定义了一个位于[0,1]之间的实数区间。当信息符号(消息)中的符号增多、用于表示消息的区间变小，而表示该区间所需的信息单元(bit)数量变大。

LZW编码(LZW Coding)

LZW编码处理空间冗余。不需要被编码符号中出现的概率的先验知识。

LZW编码对信源符号的变长序列分配定长码字。

比特平面编码(Bit-Plane Coding)

原理：将一副多灰度级图像分解为一系列二值图像，并采用以下两种二值压缩方法之一来压缩每幅图像。

m-bit单色图像的灰度表示： \[ a_{m-1}2^{m-1}+a_{m-2}2^{m-2}+\dots+a_{1}2^{1}+a_02^0 \] 将该多项式的m个系数分为m个1-bit平面。最低有效bit平面式手机每个像素\(a_0\)比特生成的，而最高有效bit平面包含\(a_{m-1}\)bit或系数。

另外一种分解方法：（这种方法可以减少小灰度级变化的影响）是首先用一个\(m\)位的格雷码（Gray code）来表示图像，其中: \[ g_{i}=a_{i}\oplus a_{i + 1}, \quad 0\leq i\leq m - 2\\ g_{m - 1}=a_{m - 1} \] 127:0100 0000, 128: 1100 0000

无损预测编码(Lossless Predictive Coding)

无损预测编码基于通过提取和编码每个像素中的新信息来消除紧密相邻像素间的冗余。像素的新信息定义为该像素实际值与预测值之间的差值。

预测误差使用变长码进行编码： \[ e_n = f_n - \hat{f}_n\\ f_n = e_n + \hat{f}_n \] 解码器从接收到的变长码字中重构\(e_n\)并执行逆操作。在大多数情况下，预测是由\(m\)个先前像素的线性组合形成的，即：
\[ \hat{f}_n = \text{round}\left[\sum_{i = 1}^{m} a_i f_{n - i}\right] \] 在其他情况下，\(n\)被用作图像空间坐标和/或图像时间序列中的帧编号（在图像时间序列中）的索引： \[ \begin{align} \hat{f}(x,y) &= \text{round}\left[\sum_{i = 1}^{m} a_i f(x,y - i)\right]\\ &= \text{round}[a f(x,y - 1)] \end{align} \]

有损压缩(Lossy Compression)

与前文所述的无损方法不同，有损编码基于以降低重建图像的精度为代价来换取更高的压缩率。
如果能够容忍由此产生的失真（这种失真可能肉眼可见也可能不可见），那么压缩率的提升可能会非常显著。
许多有损编码技术能够从被压缩超过100:1的数据中重现可识别的单色图像，并且在10:1到50:1的压缩率下得到与原图几乎无法区分的图像。然而，单色图像的无损编码很少能使数据减少超过3:1。

有损压缩编码(Lossy Predictive Coding)

在无损预测编码的模型中加入量化器，并研究由此产生的重建精度和压缩性能之间的权衡关系。 \[ \dot{f}_n = \dot{e}_n + \hat{f}_n \] 大多数预测编码应用中使用的最优预测器能使编码器的均方预测误差最小： \[ E\{e_n^2\} = E\{[f_n - \hat{f}_n]^2\} \] 前提是: \[ \dot{f}_n = \dot{e}_n + \hat{f}_n \approx e_n + \hat{f}_n = f_n\\ \hat{f}_n = \sum_{i = 1}^{m} \alpha_i f_{n - i} \] 在这些条件下，最优预测器的设计问题就简化为选择\(m\)个预测系数，使以下表达式最小： \[ E\{e_n^2\} = E\left\{\left[f_n - \sum_{i = 1}^{m} \alpha_i f_{n - i}\right]^2\right\} \] 对上述等式关于每个系数求导，令导数为零，并在假设\(f_n\)均值为零且方差为\(\sigma^2\)的条件下求解由此产生的联立方程组，得到: \[ \alpha = R^{-1}r\\ R = \begin{bmatrix} E\{f_{n - 1}f_{n - 1}\} & \cdots & E\{f_{n - 1}f_{n - m}\}\\ \vdots & \ddots & \vdots\\ E\{f_{n - m}f_{n - 1}\} & \cdots & E\{f_{n - m}f_{n - m}\} \end{bmatrix}, r = \begin{bmatrix} E\{f_n f_{n - 1}\}\\ \vdots\\ E\{f_n f_{n - m}\} \end{bmatrix} ,\alpha = \begin{bmatrix} \alpha_1\\ \vdots\\ \alpha_m \end{bmatrix} \] 其中\(R^{-1}\)是\(m\times m\)自相关矩阵的逆. \(r\)和\(\alpha\)是\(m\)元素向量。

因此，对于任何输入图像，使式\(E\{e_n^2\}\)最小的系数可以通过一系列基本矩阵运算确定。

使用这些最优系数产生的预测误差方差为: \[ \sigma_{e}^2 = \sigma^2 - \alpha^T r = \sigma^2 - \sum_{i = 1}^{m} E\{f_n f_{n - i}\}\alpha_i \] 通常要求预测系数\(\alpha\)的总和小于或等于1，即: \[ \sum_{i = 1}^{m} \alpha_i \leq 1 \] 做出这一限制是为了确保预测器的输出落在允许的灰度级范围内，并减少传输噪声的影响，传输噪声在重建图像中通常表现为水平条纹。

总结

信息信道时连接信源和用户的物理媒介。

信道容量定义了信息能够可靠地通过信道传输的最大速率。 \[ C=\max_{\mathbf{z}}[I(\mathbf{z},\mathbf{v})] \]

图像处理-Ch7-图像压缩