冈萨雷斯笔记(五)-图像压缩

储存一个图像最简单的方法是把每一个像素的灰度值保存在一个二维矩阵中,对于一个尺寸为M*N的图像,需要MN个字节来存储,若图像尺寸为1920-1200,那么需要2.2MB的空间来存储该图像,但是实际上我们从网络上下载的图片并没有这么大,一个同样尺寸的jpg彩色图像只有700KB左右,很明显图片经过了一定方式的压缩才将大小缩小了几倍,下面就来介绍一些图像压缩的方法。

首先要明确数据冗余是图像压缩的主要问题。可以说压缩的本质就是将信息的数据用最精简且无丢失的方式存储为更少的数据。在图像压缩中,可以确定的三种基本的数据冗余为:

  1. 编码冗余
  2. 像素间冗余
  3. 心理视觉冗余

无损压缩

顾名思义,无损压缩指的是压缩后的数据可以还原成原图像,当然无损压缩的压缩率不会很大。

变长编码–消除编码冗余

  • 霍夫曼编码: 霍夫曼编码是消除编码冗余的最常用技术,它被应用于jpeg图像格式中,因为我比较了解且上机的时候编写过,在此不作介绍,请参见:http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html。简而言之,霍夫曼编码就是让出现概率大的数据编码短,概率小的数据编码长些。
  • 算术编码: 它与霍夫曼编码存在根本上的不同,霍夫曼编码是分别对每个灰度数据进行编码,而算术编码是对序列进行编码,通俗地说,霍夫曼编码可以跳跃的编码,而算术编码必须是连续的进行。让我们用一个例子来说明算术编码的方法:一串字符由ABC三种字符表示,假设对BCCB这串字符进行编码,取区间[0,1],将其等分为三份,0-0.3333表示字符A的区间,0.3333-0.6667表示字符B的区间,0.6667-1代表字符C的区间,待编码的字符串第一位为B因此取0.3333-0.6667的区间,下图中采用自适应算术编码,因此在编码过程中数据的概率分布是未知的,按照正常的思路,应该是出现概率越高的字符编码区间越大,所以对第二个字符C编码是,A B C的编码区间分配权重改变,B的权重加1,即得到图中分割的子区间,对后面字符的编码以此类推。如果编码前已经获取了各个符号的概率,可以直接按照概率大小分割子区间,无需动态改变分割权值。

机智地去MATLAB帮助文档中搜索,发现两种编码的函数早已备好了。

[dict,avglen] = huffmandict(symbols,p); %生成霍夫曼编码的字典,symbols为需要编码的数据,p为各个数据出现的概率,均为一维向量 
comp = huffmanenco(sig,dict); % 对sig这一串进行编码,dict是已生成的字典
dhsig = huffmandeco(comp,dict); %对编码后的串comp进行解码,dict是编码时使用的字典

code = arithenco(seg,counts); % 对一维向量seg进行算术编码,一维向量counts表示seg中的字符按照字典序排列出现的个数
%(或者是把seg作为一个串的子集的大集合的各字符个数)
dseq = arithdeco(code,counts,len); % 将编码后的code还原为尺寸为len的一维向量,counts与上述含义相同

行程编码

也称为游程编码,在此方式下每两个字节组成一个信息单元。第一个字节给出其后面相连的像素的个数。第二个字节给出这些像素使用的字典中的键。例如:信息单元03 04,03表示其后的像素个数是3个,04表示这些像素使用的是颜色索引表中的第五项的值。压缩数据展开后就是04 04 04 (来自度娘)上学期编过的游程编码是数字加个数,也是差不多;对图像来说,也就是将一大串只含0和1的位进行编码。

在图像压缩中,常常对经过行程编码后的串用其他变长编码的压缩方法进一步压缩。行程编码被证明是最好的位平面图像的编码方法(位平面图是将图像的八位按位分离成八张二值图像)。

LZW编码–消除像素间冗余

这种编码方式也需要创建一个字典,但是这个字典是在压缩过程中动态生成的,因此可能会出现字典溢出的情况。LZW算法中有几个比较重要的概念:字符,字符串,字典,它把数据流看成一个字符序列,并将字符序列组织成一系列的字符串,并给每个字符串一个编码,最后存储的就是字符串的编码,这样就节省了空间。让我们用一个简单的例子来解释这种编码方式:待编码的串为012011201 初始条件下的字典含有三个键值对{0:0,1:1,2:2}

当前识别序列        被处理的字符        编码输出        字典位置        字典条目
                    0                            0            
    0                1                0            3                0-1
    1                2                1            4                1-2
    2                0                2            5                2-0
    0                1                            3    
    0-1                1                3            6                0-1-1
    1                2                            4
    1-2                0                4            7                1-2-0
    0                1                            3        
    1                                3

压缩后输出为012343,六位字符,编码前的串为9位字符,压缩比率为1.5:1 。解压就是一个查字典的过程,不再详述。

无损预测编码

这种方法通过对每个像素相对于前一个的新增信息进行提取和编码,消除空间上较为接近像素之间的冗余信息。预测编码是指将原始图像数据输入预测器,原图像数据与对应的预测后图像的数据作差分,将这个差值利用变长编码进行压缩。预测器设定的越准确,压缩比率越高。

无损预测编码自然是解压后可以完全还原到原图像的编码方式。

有损压缩

实现无损编码当然是更好的,但是有时候图像经有损压缩后也能达到要求,而压缩比率高于无损压缩,相当于加快了图像传输速度。

有损预测编码

在无损预测编码中差分在某一范围内是可以随意取值的,如果这一范围的编码取值是5个二进制位,那么每一个像素数据要占据5位的空间,有损预测编码是将这一范围大大缩小,最简单的德尔塔调制每一个像素只占一位的空间,差分是一个自定义的常量q,若下一像素比前一像素值大,则编码为1,小则为0,解码时在前一个像素的基础上加或减q即可。也可以根据需要设计最佳量化函数,既保证单位编码长度小,又能够达到可观的压缩质量。

Thank you for every coin~