Outline
• Introduction
• Fundamentals
• Coding, interpixel and psychovisual redundancies • Fidelity criteria
• Image compression model
• Source encoder and decoder
• Channel encoder and decoder
• Lossless compression
• Huffman encoding
• Lossless predictive coding
• Lossy compression
• Lossy predictive coding
• Transform coding
• JPEG
=========== =========== ===========一条分割线 =================================
Introduction 介绍
每天都有大量的信息以数字方式存储和传输。由于这些在线信息大多是图形化或图形化的，因此存储和通信的需求是巨大的。当需要大量存储或大量通信时，图像压缩变得非常重要。图像压缩减少了表示信息所需的数据量（删除冗余数据）。
图像压缩有两种类型：无损和有损。
- 无损：允许在不丢失信息的情况下压缩和解压缩图像。
- 有损：提供更高级别的数据缩减，但结果是原始图像的不完美再现。
=========== =========== ===========一条分割线 =================================
1.Fundamentals基础
冗余数据包含的东西要么不提供相关信息，要么只是重申已知的信息。
压缩率compression ratio
定义两个数据X1,X2，X2这里应该是X1被压缩后的数据集， n 1 , n 2 n_1,n_2 n1,n2分别是他们的信息承载单元information-carrying units的数目，（其实这个具体是什么我也还没弄懂）。现在我们 C R , R D C_R,R_D CR,RD如下图。
如果 n 1 , n 2 n_1,n_2 n1,n2相等，显然 R D = 0 R_D = 0 RD=0，表示没有冗余信息，也就是说X1和X2数据集包含信息是一样的。
另外如果 n 2 n_2 n2很小，说明压缩的很多，也就是说明X1原数据集的冗余信息很多。
反之同理。
2、三种冗余
2.1、 Coding Redundancy 编码冗余
图像在计算机中存储和网络传输中都是以二进制编码形式存在的，不同的编码方式对于同一张图片将会产生不同的编码长度，相同的编码方式对于不同照片所产生的冗余率也是不同的，这将会产生编码冗余。大部分编码都是存在冗余的，所以需要根据实际选择合适的编码方式尽可能降低冗余率。
code1 就是2^n = L 比如8种灰度3bit
code2 :“编码长度与灰度概率成反比” code2实际上是霍夫曼编码，然后算他的平均编码位数：用每个灰度的编码位数*它的灰度概率，比如0.19x2+0.25x2+…=average bit
那么压缩率：
那么这样就实现了数据压缩。
2.2 Interpixel Redundancy像素间冗余
像素间冗余是一种与像素间相关性有直接联系的数据冗余。
对于一张静态图片，存在空间冗余（几何冗余）：
同一景物表面上采样点的颜色之间通常存在着空间相关性，相邻各点的取值往往相近或者相同，这就是空间冗余。例如，图像中有一片连续的区域，这个区域的像素都是相同的颜色，那么空间冗余就产生了。
对于连续图片或视频，还会存在时间冗余（帧间冗余），大部分相邻图片间的对应点像素都是缓慢过度的。
看图1图2，长宽度分辨率都一样，但是很显然图2有大片的相同像素点，也就是空间冗余。
处理技术 : DCT（Discrete Cosine Transform，离散余弦变换）它将空间域上的图像变换到频率域上进行处理。后面会有详细介绍。
例子：比如一张灰度图，因为灰度图会有很多连续的同值像素，所以不如沿着每一条扫描线来进行统计。
比如沿着扫描线：
意思是沿着扫描线时，每改变一次灰度就记录下来，并且统计出这一次改变前，总共跑过多少一样的灰度，得到一组（灰度值，这条线出现次数）的映射。
比如这张图的第100行线，统计出的：(1,63)(0,87)(1,37)(0,5)(1,4)(0,556)(1,62)(0,210)
那么对于二值图来说，只有0和1两种灰度，只需要1bit就可以表示。由于counter中有556，那么需要2^10，也就是10bit表示run length。又因为有8组pair，所以总共需要88bit表示这条线。比原本的1024bit要好很多。
5、6讲的是，因为原图高度343，所以原本是需要1024343bit，采用了这种映射方法之后，只需要11统计出的组数=12166（这是统计后的结果），那么最终压缩率就大大了2.63.
2.3 Psychovisual Redundancy心理视觉冗余
视觉冗余是相对于人眼的视觉特性而言的，人类的视觉系统并不能对图像画面的任何变化都能感觉到，通常情况下具有以下特点：
对亮度的变化敏感，对色度的变化相对不敏感。
对静止图像敏感，对运动图像相对不敏感。
对图像的水平线条和竖直线条敏感，对斜线相对不敏感。
对整体结构敏感，对内部细节相对不敏感。
对低频信号敏感，对高频信号相对不敏感（如：对边沿或者突变附近的细节不敏感）。
因此，包含在色度信号、运动图像、图像高频信号中的一些数据，相对于人眼而言，并不能对增加图像的清晰度作出贡献，被人眼视为多余的，这就是视觉冗余。
简单概括就是人眼的概括能力很强，找轮廓能力很强，定量定点不怎么关注，细节变化不关注。这是不是很容易就想到了该死的傅里叶变换？人眼最爱关注那些高频信息。
所以也就是可以降低他们的分辨率。当然这个过程不可逆。
3.The Source Encoder and Decoder
3.1. The source encoder:
能够消除上述3种冗余，可以用 fidelity criteria评估，由三个独立操作组成：
the mapper, the quantiser, and the symbol encoder.
1） The mapper 映射器
它将输入数据转换成一种（通常是非视觉的）格式，旨在减少输入图像中的像素间冗余，例如，行程编码或基于变换系数的压缩。
The mapper: it transforms input data into a (usually nonvisual) format designed to reduce interpixel redundancies in the input image,
e.g., run-length coding, or compression based on transform
coefficients.
2）The quantiser 量化器
量化器：它降低了精度，输出符合一些预先设定的保真度标准，并可用于减少心理视觉冗余，例如IGS量化**（不可逆操作）。**
The quantiser: it reduces the accuracy of the mapper’s
output in accordance with some pre-established fidelity criterion, and can be used to reduce psychovisual redundancy, e.g., IGS quantisation (irreversible operation).
3）symbol coder 符号编码器
The symbol coder: it creates a fixed-length code or variable-length code to represent the quantiser output and maps the output in accordance with the code.
对于source decorder，包含了symbol decoder and an inverse mapper.
3.2 The Channel Encoder and Decoder
1.由于source encoder的输出包含很少的冗余，所以它对传输噪声非常敏感。
2.it reduces or eliminates the impact of channel noise by inserting a controlled form of redundancy加粗样式 into the source encoded data.
3.汉明指出，如果在一个4位字上加上3位冗余，所有的单位错误都能被检测到并纠正——7位汉明（7,4）码字。
4. The 7-bit Hamming (7,4) code word h1 h2 h3…h7 with 7 bits.
5. 假设一个四位二值编码b3b2b1b0
6. 加了冗余之后形成的hamming码和原编码的关系：
where ⊕ represents the exclusive OR operation.（异或运算）
————————————————————————————
第1位校验码位于新的编码的第1位(2 ^(1-1) == 1)（汉明码从1位开始），计算1,3,5,7,9,11,13,15,…位的异或，填入新的编码的第1位。
第2位校验码位于新的编码的第2位(2 ^(2-1) == 2)，计算2,3,6,7,10,11,14,15,…位的异或，填入新的编码的第2位。
第3位校验码位于新的编码的第4位(2 ^(3-1) == 4)，计算4,5,6,7,12,13,14,15,20,21,22,23,…位的异或，填入新的编码的第4位。
第4位校验码位于新的编码的第8位(2 ^(4-1) == 8)，计算8-15,24-31,40-47,…位的异或，填入新的编码的第8位。
第5位校验码位于新的编码的第16位(2 ^(5-1) == 16)，计算16-31,48-63,80-95,…位的异或，填入新的编码的第16位。
————————————————————————————
汉明码编码实例
————————————————————————————
以10101编码为例，创建一个汉明码编码的空间，并且把源码填入编码的对应位中中，_ _ 1 _ 0 10 _ 1，并留出校验码位（校验位先设为0）。（因为2^4 - 1>= 5+4 && 2^3 - 1 < 5+ 3所以需要4位校验码）
计算校验码的第1位（1,3,5,7,9进行异或）: 结果为0，所以汉明码第2^0位为0，结果为0 _ 1 _ 0 10 _ 1
计算校验码的第2位（2,3,6,7进行异或）: 结果为0，所以汉明码第2^1位为0，结果为001 _ 0 10 _ 1
计算校验码的第3位（4,5,6,7进行异或）: 结果为1，所以汉明码第2^2位为0，结果为0011 0 10 _ 1
计算校验码的第4位（8, 9进行异或）: 结果为0，所以汉明码第2^3位为1，结果为0011 0101 1
所以最终编码为001101011.
————————————————————————————
4 Lossless Compression
4.1 Error free compression无差错压缩
再很多情况下，是要求无差错压缩的，比如商业、医疗等等。
这个时候，压缩比为2到10。
有两个一般操作：
a、 减少像素间冗余
b、 消除编码冗余。
a. reduce interpixel redundancy
b. eliminate coding redundancy.
也就是不准有量化器阶段。（因为：Quantizer reduces the accuracy of the mapper’s output ）
由此，我们引入了霍夫曼编码
4.2 Huffman coding
核心：将尽可能短的代码字分配给最可能的灰色级别。
首先将图像拥有的所有灰度级计算其密度，然后把最小的两片叶子加起来变成一个节点，然后再把最小两片的叶子（也算新的节点）加起来变成一个节点…反复进行变成一个二叉树。
越是后面被操作的灰度，说明他密度越大，从树根往下的编码长度也就越短。
例子：
Need to store symbol table along with compressed data
需要存储符号表和压缩数据！
4.3 Lossless predictive coding
1、无损预测编码是通过对每个像素中的新信息进行编码来减少密集像素的像素间冗余。
2、什么是新信息：该像素的实际值和预测值之间的差异。
3、整个系统由编码器和解码器组成。它由一个预测器组成，它根据过去的一些值生成预测值。
纵向的上一个灰度级预测下一个灰度级
4、Encoder：
定义误差：原来的减去预测的
5、Decoder:
a、 它由一个预测器组成，它与编码过程中的预测器完全相同。
b、 通过将发送的预测误差值en和预测值相加来生成图像值。
由于无法计算前m个像素，因此可能需要使用其他压缩方法对这些像素进行编码。这可以看作是这种压缩方案的开销。
4.4 Lossless predictive coding (Example)
比如将 α \alpha α 参数设置为1，预测邻接像素距离m设置成1（这一点不是很确定），最后的效果↓↓
- Uncompressed image: mean = 128, SD = 47.44
- Compressed image (prediction error): mean = 0, SD = 4.12
-
The variance of the prediction errors is much smaller than
the variance of the grey levels in the original image.
-
Average lengths for the original image and the prediction
error image are 8 bits and 3.96 bits respectively, e.g.,
variable length coding or Huffman coding can be used.
- The compression ratio is about 2:1.
——————————————————————————————————————————
5、Lossy Compression有损压缩
- •影响准确性——That is, we will allow for “error” and distortion
- 换取更大的压缩率—— If the resulting distortion can be tolerated, then we can gain substantial compression
- 利用心理-视觉冗余——（不可逆）•我们的眼睛对高频不太敏感 ，我们是否可以“丢弃”一些细节，使处理后的图像看起来与原始图像相似？
•与无损的主要区别
•引入“量化”
•量化将值映射到有限范围内•量化越多
•更多压缩
•（以及更多失真）
误差会被量化到一个限制范围之内。
★★★★★★★★★★★★
5.2Predictive vs. Transform coding
Predictive coding
•在预测编码中，已发送或可用的信息用于预测未来值，并对差异进行编码。由于这是在图像或空间域中完成的，所以实现起来相对简单，并且容易适应局部图像特性。（adapted to local image characteristics.）
Transform coding
•另一方面，变换编码首先使用一些众所周知的变换将图像从其空间域表示转换为不同类型的表示，然后对变换后的值（系数）进行编码。与预测方法相比，这种方法提供了更大的数据压缩，尽管代价是更大的计算量。（provides greater data compression at the expense of greater computation.）
————————————————————————————————————————————
6.Transform coding
预测编码直接作用于pixel
而transform ：
•使用可逆线性变换（例如傅里叶变换（FT））reversible, linear transform
•将像素映射到新系数（例如，以FT为单位，将空间信息映射为频率信息）
•量化系数
•进一步压缩（行程长度编码、可变长度编码）
• Uses a reversible, linear transform (Fourier Transform (FT) for example)
• Maps the pixels to new coefficients (e.g., in FT, maps spatial information to frequency information)
• Quantises the coefficients
• Compresses these further (Run Length Encoding, Variable Length Coding)
Typical Transform Coding Scheme
6.1核心idea：
• Transform pixels to a new “space”
• The new space provides a more compact representation of the information, or packs as much information as possible into the smaller number of transform coefficients.
• Signal Power “Packing”
• As such, compression is achieved during the quantisation of the transformed coefficients.
•新空间提供了更紧凑的信息表示，或将尽可能多的信息打包到较小数量的变换系数中。
•因此，压缩是在转换系数的量化期间实现的。
•6.2离散余弦变换（DCT）
• Like FT
• But, no imaginary component
• DCT shown to have better power “packing” abilities over DFT
Discrete Cosine Transform (Forward DCT)
后项
与FFT变换同时使用正弦和余弦函数来表达信号不同，DCT只使用余弦函数来表达信号。DCT变换有多个版本，有一种常用的DCT实现过程是这样的：对一个长度为129（0到128）的信号进行DCT变换。首先，复制点127到点1，使整个信号变为：
0, 1, 2, …, 127, 128, 127, …, 2, 1
这串长度为256的时间域信号经过FFT变换后会生成一个长度为129的信号。生成的信号长度之所以129,而不是256,是因为时间域的信号对称，根据二元性（duality），对应的频率域信号的虚数部分全部为0。也就是说，我们输入的长度为129的时间域信号经过DCT变换后，产生一个长度为129的频率域信号，并且频率域完全由余弦函数组成。
在图像处理中，每副图像都会被切成8×8的小块，块的大小可以是任意，只是因为历史原因人们习惯于切为8×8的块。二维的图像处理与一维的信号处理原理是一致的。
FFT会丢失一些真实的数组。
7.JPEG Compression
7.1
编码
解码
2. 具体过程：（这里仅以编码为例，解码过程为其逆过程）
A. 将原始图像分为88的小块, 每个block里有64pixels：
B. 将图像中每个88的block进行DCT变换：
和FFT一样，DCT也是将信号从时域到频域的变换，不同的是DCT中变换结果没有复数，全是实数。每88个original pixels都变成了另外88个数字，变换后的每一个数都是由original 64 data通过basis function组合而得的，如下图所示为DCT谱中6个元素的由来。
将低频部分集中在每个8*8块的左上角， 高频部分在右下角，所谓JPEG的有损压缩，损的是量化过程中的高频部分。 为什么呢？因为有这样一个前提：低频部分比高频部分要重要得多，romove 50%的高频信息可能对于编码信息只损失了5%。
在MATLAB中运用一行代码
dctB = dct2(B,8,8)
C. 量化：
所谓量化就是用像素值÷量化表对应值所得的结果。由于量化表左上角的值较小，右上角的值较大，这样就起到了保持低频分量，抑制高频分量的目的。JPEG使用的颜色是YUV格式。我们提到过，Y分量代表了亮度信息，UV分量代表了色差信息。相比而言，Y分量更重要一些。我们可以对Y采用细量化，对UV采用粗量化，可进一步提高压缩比。所以上面所说的量化表通常有两张，一张是针对Y的；一张是针对UV的。
比如左边那个量化表，最右下角的高频÷16，这样原先DCT后[-127,127]的范围就变成了[-7,7]，固然减少了码字（从8位减至4位）。
另一类是8×8块的其它63个子块，即交流(AC)系数，采用行程编码（游程编码Run-length encode,RLE）。这里出现一个问题：这63个系数应该按照怎么样的顺序排列？为了保证低频分量先出现，高频分量后出现，以增加行程中连续“0”的个数，这63个元素采用了“之”字型(Zig-Zag)的排列方法，如下图所示。
7.2
JPEG “Quality”
如果用过Photoshop的话会知道在最后导出jpeg时会选择图像质量0-12
•JPEG在压缩时使用术语“质量”
•不同的质量因素对应不同的量化表
•较低的质量对应于量化表中的较大值
•质量100%是T（u，v）1的量化表
•round过程中丢失了一些信息