文档介绍：《算法设计与分析》课程报告
姓名:文亮
学号:201322220254
学院:信息与软件工程学院
老师:屈老师;王老师
算法实现与应用——《算法设计与分析》课程报告
基本要求
题目: 图像压缩
问题描述
掌握基于DCT变换的图像压缩的基本原理及其实现步骤;对同一幅原
始图像进行压缩,进一步掌握DCT和图像压缩。
算法基本思想
图像数据压缩的目的是在满足一定图像质量的条件下,用尽可能少的比特数来表示原始图像,以提高图像传输的效率和减少图像存储的容量,在信息论中称为信源编码。图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图像数据量的技术,压缩过程就是编码过程,解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类,前者在解码时可以精确地恢复原图像,没有任何损失;后者在解码时只能近似原图像,不能无失真地恢复原图像。
假设有一个无记忆的信源,它产生的消息为,其出现的概率是已知的,记为。则其信息量定义为:
由此可见一个消息出现的可能性越小,其信息量就越多,其出现对信息的贡献量越大,反之亦然。
信源的平均信息量称为“熵”(entropy),可以表示为:
对上式取以2为底的对数时,单位为比特(bits):
根据香农(Shannon)无噪声编码定理,对于熵为H的信号源,对其进行无失真编码所可能达到的最低比特数为,这里为一任意小的正数,因此可能达到的
最大压缩比为:
       其中B是原始图像的平均比特率。
在图像压缩中,压缩比是一个重要的衡量指标。可以定义压缩比为:
其中B:原始数据的平均压缩比;H:压缩数据的平均比特率
图像压缩的基本模型
图像编码包括两个阶段,前一个阶段就是利用预测模型或正交模型对图像信号进行变换;后一个阶段是利用已变换信号的统计特性,对其分配适当的代码来进行编码传输。
编码器与解码器的结构分别如图(a)、(b)。
压缩图像数据
原始图像数据
Huffman编码
量化器
DCT变换
图(a) 编码器结构
量化器
(逆)
重建图像数据
逆DCT变换
Huffman译码
压缩图像数据
图(b) 解码器结构
在发送端,输入的原始图像首先经过DCT变换后,其低频分量都集中在左上角,高频分量分布在右下角(DCT变换实际上是空间域的低通滤波器)。由于该低频分量包含了图像的主要信息,而高频分量与之相比就不那么重要了,所以可以忽略高频分量,从而达到压缩的目的。将高频分量去掉就要用到量化,这是产生信息损失的根源。
“量化”的主要任务是用有限个离散电平来近似表达已抽取出的信息。在此采用均匀量化,通过改变程序中的量化因子Q的值以得到不同压缩比的图像。Huffman编码时,首先对经DCT变换及量化后的图像收据扫描一遍,计算出各种像素出现的概率;然后按概率的大小指定不同长度的唯一码字,由此得到一张Huffman表。编码后的图像记录的是每个像素的码字,而码字与量化后像素值的对应关系记录在码表中。生成的一维字符矩阵即为实际中要传输的序列,压缩后的图像数据在信道中进行传输。
在接收端,接收到的压缩图像数据首先经过Huffman译码,通过搜索已生成的Huffman表,根据码字与量化后像素值的对应关系,搜索出与码字对应的像素值,并转换为二维矩阵。反量化时将以上二维矩阵中的每一个像素值乘以量化因子Q。最后通过DCT反变换得到重建图像。
离散余弦变换(DCT)
当前处于信息高速流通时代,要求在保证质量的前提下,以较小的空间存储图像和较小的比特率传输图像,这就需要采用各种图像压缩编码技术来实现。DCT变换是最小均方误差条件得出的次最佳正交变换,且已经获得广泛的应用,并已经成为许多图像编码国际标准的核心。离散余弦变换的变换核是余弦函数,计算速度较快,有利于图像压缩和其他处理。在大多数情况下,DCT用于图像的压缩操作中。JPEG图像格式的压缩算法采用的是DCT。
程序源代码
function b = blkproc(varargin)
[a, block, border, fun, params, padval] = parse_inputs(varargin{:}); [ma,na] = size(a);
mpad = rem(ma,block(1)); if mpad>0, mpad = block(1)-mpad; end
npad = rem(na,block(2)); if npad>0, npad = block(2)-npad; end
if (isa(a, 'uint8'))
if (padval == 1)
aa = repmat(uint8(1), ma+mpad+2*border(1),na+np