图像压缩算法

1、算法设计与分析课程报告姓名:文亮学号:201322220254学院:信息与软件工程学院老师:屈老师;王老师算法实现与应用算法设计与分析课程报告一. 基本要求 1. 题目 : 图像压缩 2. 问题描述掌握基于 DCT 变换的图像压缩的基本原理及其实现步骤;对同一幅原 始图像进行压缩,进一步掌握 DCT 和图像压缩。3. 算法基本思想图像数据压缩的目的是在满足一定图像质量的条件下,用尽可能少的比特数 来表示原始图像, 以提高图像传输的效率和减少图像存储的容量, 在信息论中称 为信源编码。 图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图 像数据量的技术, 压缩过程就是编码过程, 解压缩过

2、程就是解码过程。 压缩技术 分为无损压缩和有损压缩两大类, 前者在解码时可以精确地恢复原图像, 没有任 何损失;后者在解码时只能近似原图像,不能无失真地恢复原图像。假设有一个无记忆的信源 , 它产生的消息为 Ni a i 1, 其出现的概率是已 知的 , 记为 (i a p 。则其信息量定义为 :(i i a p a log -=I由此可见一个消息出现的可能性越小, 其信息量就越多, 其出现对信息的贡 献量越大,反之亦然。信源的平均信息量称为“熵” (entropy ,可以表示为:(=-=HNi i i Ni i i a p a p a p I a p 11log对上式取以 2为底的对数时,单

3、位为比特(bits :(=-=HNi i i a p a p 1log根据香农(Shannon 无噪声编码定理,对于熵为 H 的信号源,对其进行无失真编码所可能达到的最低比特数为, 这里为一任意小的正数, 因此可能达到的 最大压缩比为:H+H=BB C max 其中 B 是原始图像的平均比特率。在图像压缩中,压缩比是一个重要的衡量指标。可以定义压缩比为:H=B C 其中 B :原始数据的平均压缩比; H :压缩数据的平均比特率 图像压缩的基本模型图像编码包括两个阶段, 前一个阶段就是利用预测模型或正交模型对图 像信号进行变换;后一个阶段是利用已变换信号的统计特性,对其分配适当 的代码来进行编码

4、传输。编码器与解码器的结构分别如图 (a、 (b。 图(a 编码器结构 图(b 解码器结构在发送端, 输入的原始图像首先经过 DCT 变换后, 其低频分量都集中在左上 角,高频分量分布在右下角(DCT 变换实际上是空间域的低通滤波器 。由于该 低频分量包含了图像的主要信息, 而高频分量与之相比就不那么重要了, 所以可 以忽略高频分量, 从而达到压缩的目的。 将高频分量去掉就要用到量化, 这是产 生信息损失的根源。“量化”的主要任务是用有限个离散电平来近似表达已抽取出的信息。在此 采用均匀量化,通过改变程序中的量化因子 Q 的值以得到不同压缩比的图像。Huffman 编码时,首先对经 DCT 变

5、换及量化后的图像收据扫描一遍,计算出各种 像素出现的概率;然后按概率的大小指定不同长度的唯一码字,由此得到一张 Huffman 表。编码后的图像记录的是每个像素的码字,而码字与量化后像素值的 对应关系记录在码表中。 生成的一维字符矩阵即为实际中要传输的序列, 压缩后 的图像数据在信道中进行传输。在接收端,接收到的压缩图像数据首先经过 Huffman 译码,通过搜索已生成 的 Huffman 表, 根据码字与量化后像素值的对应关系, 搜索出与码字对应的像素 值, 并转换为二维矩阵。 反量化时将以上二维矩阵中的每一个像素值乘以量化因 子 Q 。最后通过 DCT 反变换得到重建图像。离散余弦变换 (

6、DCT当前处于信息高速流通时代,要求在保证质量的前提下,以较小的空间存储 图像和较小的比特率传输图像, 这就需要采用各种图像压缩编码技术来实现。 DCT 变换是最小均方误差条件得出的次最佳正交变换, 且已经获得广泛的应用, 并已 经成为许多图像编码国际标准的核心。 离散余弦变换的变换核是余弦函数, 计算 速度较快,有利于图像压缩和其他处理。在大多数情况下, DCT 用于图像的压缩 操作中。 JPEG 图像格式的压缩算法采用的是 DCT 。二.算法实现程序源代码function b = blkproc(varargina, block, border, fun, params, padval =

7、 parse_inputs(varargin:; ma,na = size(a;mpad = rem(ma,block(1; if mpad>0, mpad = block(1-mpad; endnpad = rem(na,block(2; if npad>0, npad = block(2-npad; endif (isa(a, 'uint8' if (padval = 1aa = repmat(uint8(1, ma+mpad+2*border(1,na+npad+2*border(2;elseaa = repmat(uint8(0, ma+mpad+2*bor

8、der(1,na+npad+2*border(2;endelseif isa(a, 'uint16' if (padval = 1aa = repmat(uint16(1, ma+mpad+2*border(1,na+npad+2*border(2;elseaa = repmat(uint16(0, ma+mpad+2*border(1,na+npad+2*border(2;endelseif (padval = 1aa = ones(ma+mpad+2*border(1,na+npad+2*border(2;elseaa = zeros(ma+mpad+2*border(1,

9、na+npad+2*border(2;endendaa(border(1+(1:ma,border(2+(1:na = a;m = block(1 + 2*border(1;n = block(2 + 2*border(2;mblocks = (ma+mpad/block(1;nblocks = (na+npad/block(2;arows = 1:m; acols = 1:n;x = aa(arows, acols;firstBlock = feval(fun,x,params:;if (isempty(firstBlockstyle = 'e' ;b = ;elseif (

10、all(size(firstBlock = size(xstyle = 's' ; % sameif (isa(firstBlock, 'uint8' b = repmat(uint8(0, ma+mpad, na+npad;elseif (isa(firstBlock, 'uint16' b = repmat(uint16(0, ma+mpad, na+npad;elseb = zeros(ma+mpad, na+npad;endbrows = 1:block(1;bcols = 1:block(2;mb = block(1;nb = bloc

11、k(2;xrows = brows + border(1;xcols = bcols + border(2;b(brows, bcols = firstBlock(xrows, xcols;elseif (all(size(firstBlock = (size(x-2*borderstyle = 'b' ; % borderif (isa(firstBlock, 'uint8' b = repmat(uint8(0, ma+mpad, na+npad;elseif (isa(firstBlock, 'uint16' b = repmat(uint

12、16(0, ma+mpad, na+npad;elseb = zeros(ma+mpad, na+npad;endbrows = 1:block(1;bcols = 1:block(2;b(brows, bcols = firstBlock;mb = block(1;nb = block(2;elsestyle = 'd' ; % differentP,Q = size(firstBlock;brows = 1:P;bcols = 1:Q;mb = P;nb = Q;if (isa(firstBlock, 'uint8' b = repmat(uint8(0,

13、mblocks*P, nblocks*Q;elseif (isa(firstBlock, 'uint16' b = repmat(uint16(0, mblocks*P, nblocks*Q;elseb = zeros(mblocks*P, nblocks*Q;endb(brows, bcols = firstBlock;endrr,cc = meshgrid(0:(mblocks-1, 0:(nblocks-1;rr = rr(:;cc = cc(:;mma = block(1;nna = block(2;for k = 2:length(rrx = aa(rr(k*mma+

14、arows,cc(k*nna+acols;c = feval(fun,x,params:;if (style = 's' b(rr(k*mb+brows,cc(k*nb+bcols = c(xrows,xcols; elseif (style = 'b' b(rr(k*mb+brows,cc(k*nb+bcols = c;elseif (style = 'd' b(rr(k*mb+brows,cc(k*nb+bcols = c;endendif (style = 's' | (style = 'b' b = b(1

15、:ma,1:na;endfunction a, block, border, fun, params, padval = parse_inputs(varargin iptchecknargin(2,Inf,nargin,mfilename;switch nargincase 3% BLKPROC(A, m n, 'fun'a = varargin1;block = varargin2;border = 0 0;fun = fcnchk(varargin3;params = cell(0,0;padval = 0;case 4if (strcmp(varargin2, '

16、;indexed' % BLKPROC(X, 'indexed', m n, 'fun'a = varargin1;block = varargin3;border = 0 0;fun = fcnchk(varargin4;params = cell(0,0;padval = 1;elseparams = varargin(4;fun,msg = fcnchk(varargin3, length(params;if isempty(msg% BLKPROC(A, m n, 'fun', P1a = varargin1;block = va

17、rargin2;border = 0 0;padval = 0;else% BLKPROC(A, m n, mb nb, 'fun'a = varargin1;block = varargin2;border = varargin3;fun = fcnchk(varargin4;params = cell(0,0;padval = 0;endendotherwiseif (strcmp(varargin2, 'indexed' params = varargin(5:end;fun,msg = fcnchk(varargin4,length(params;if

18、isempty(msg% BLKPROC(A, 'indexed', m n, 'fun', P1, .a = varargin1;block = varargin3;border = 0 0;padval = 1;else% BLKPROC(A, 'indexed', m n, mb nb, 'fun', P1, .a = varargin1;block = varargin3;border = varargin4;params = varargin(6:end;fun = fcnchk(varargin5,length(par

19、ams;padval = 1;endelseparams = varargin(4:end;fun,msg = fcnchk(varargin3,length(params;if isempty(msg% BLKPROC(A, m n, 'fun', P1, .a = varargin1;block = varargin2;border = 0 0;padval = 0;else% BLKPROC(A, m n, mb nb, 'fun', P1, .a = varargin1;block = varargin2;border = varargin3;param

20、s = varargin(5:end;fun = fcnchk(varargin4, length(params;padval = 0;endendendif (islogical(a | isa(a,'uint8' | isa(a, 'uint16' padval = 0;endclearclcI=imread('C:Userslenovo.lenovo-PCDesktop²âÊÔͼ.jpg' I=rgb2gray(I;I=im2double(I;T=dctmtx(8;B=blkproc(I,8 8,'P1*x*P2',T,T'mask = 1 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00