《数据压缩与信源编码》实验指导书

《数据压缩与信源编码》实验指导书适用专业:信息工程课程代码:6088619总学时:40总学分:2.5编写单位:电气与电子信息学院编写人:李斌审核人:审批人:批准时间:2015年11月10日《数据压缩与信源编码》实验指导书-1-目录实验一码书的设计和使用…………………………………2实验二基于DCT变换的图像压缩技术……………………8实验三基于小波变换的图像压缩技术…………………15《数据压缩与信源编码》实验指导书-2-实验一码书的设计和使用一、实验目的采用矢量量化算法（LBG）获得图像压缩所需要的码书，通过码书实现图像压缩编码。二、实验内容对给定的一幅图像进行码书设计、编码和解码。三、实验仪器、设备及材料操作系统：Windowsxp；软件：MATLAB四、实验原理要想得到好的性能编码，仅采用标量量化是不可能的。当把多个信源符号联合起来形成多维矢量，再对矢量进行标量量化时自由度将更大，同样的失真下，量化基数可进一步减少，码率可进一步压缩。这种量化叫矢量量化。一种有效和直观的矢量量化码书设计算法——LBG算法(也叫GLA算法)是由Linde、Buzo和Gray于1980年首先提出来的。该算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件，且是Lloyd算法在矢量空间的推广，其特点为物理概念清晰、算法理论严密及算法实现容易。设训练矢量集为110,,,MxxxX，待产生的码书为110,,,NyyyC，其中)1(10,,,kiiiixxxx，)1(10,,,kjjjjyyyy，10,10NjMi，则码书设计过程就是需求把训练矢量集X分成N个子集)1,,1,0(NjSj的一种最佳聚类方案，而子集jS的质心矢量jy作为码字。假设平方误差测度用来表征训练矢量ix和码字jy之间的失真，即：102)(),(kljliljiyxyxd则码书设计的准则可用下列数学形式表达：最小化1010),(),,(NjMijiijyxdwCXWf约束条件101Njijw，10Mi其中W为NM矩阵，其元素满足：《数据压缩与信源编码》实验指导书-3-01ijwjijiSxSx矩阵W可看作训练矢量的聚类结果。根据W，可计算码字：101MiiijjjxwSy其中jS代表子集jS中训练矢量的数目，或者说是矩阵W第1j行)1,,1,0,(Miwij中非零元素的数目。针对训练矢量集为110,,,MxxxX，其LBG算法的具体步骤如下：步骤1：给定初始码书)0(1)0(1)0(0)0(,,,NyyyC，令迭代次数0n，平均失真)1(D，给定相对误差门限)10(。步骤2：用码书)(nC中的各码字作为质心，根据最佳划分原则把训练矢量集X划分为N个胞腔)(1)(1)(0)(,,,nNnnnSSSS，)(niS满足XvyvdyvdvSnjNjnini),,(min),(|)(10)()(步骤3：计算平均失真10)(10)(),(min1MinjiNjnyxdMD判断相对误差是否满足)()()1(/)(nnnDDD若满足，则停止算法，码书)(nC就是所求的码书。否则，转步骤4。步骤4：根据最佳码书条件，计算各胞腔的质心，即)()()1(1niSvninivSy由这N个新质心1,,1,0,)1(Niyni形成新码书)(nC，置1nn，转步骤2。五、实验步骤1.码书的设计clearall;data=imread('cameraman.tif');%调入原始图像《数据压缩与信源编码》实验指导书-4-data=double(data)/255;%归一化[m,n]=size(data);%求出图像的行数和列数figure(1)subplot(1,2,1);imshow(data);%显示原始图像title('原始图像')subplot(1,2,2);imhist(data);title('直方图')siz_word=4;%设置码字的大小siz_book=512;%设置码书的大小data1=zeros(m*n,1);fori=1:mforj=1:ndata1((i-1)*n+j)=data(i,j);endendM1=floor(m*n/siz_word);r=mod(m*n,siz_word);ifr0M1=M1+1;enddata2=zeros(M1,siz_word);《数据压缩与信源编码》实验指导书-5-l=1;A=zeros(siz_word,1);r=1;fori=1:m*nA(r)=data1(i);ifr==siz_worddata2(l,:)=A;l=l+1;r=1;elser=r+1;endendcode_book=zeros(siz_book,siz_word);2．编码%LBG算法开始%初始化码书l=1;《数据压缩与信源编码》实验指导书-6-r=1;A=zeros(siz_word,1);fori=1:siz_book*siz_wordA(r)=data1(i);ifr==siz_wordcode_book(l,:)=A;l=l+1;r=1;elser=r+1;endendMIU=zeros(M1,siz_book);t=1;whilet==1fori=1:M1B=zeros(siz_word,1);B=data2(i,:);A=zeros(siz_word,1);A=code_book(1,:);tep=0.0;forl=1:siz_word《数据压缩与信源编码》实验指导书-7-tep=tep+(A(l)-B(l))^2;endr=1;forj=2:siz_bookA=code_book(j,:);temp=sum((A-B).^2);iftemptepr=j;tep=temp;endendMIU(i,r)=1.0;endt=0;code_book1=zeros(siz_book,siz_word);forj=1:siz_bookforl=1:siz_wordtep=0.0;fori=1:M1code_book1(j,l)=code_book1(j,l)+MIU(i,j)*data2(i,l);tep=tep+MIU(i,j);endiftep0《数据压缩与信源编码》实验指导书-8-code_book1(j,l)=code_book1(j,l)/tep;elsecode_book1(j,l)=0.0;endendendtep=0.0;forj=1:siz_bookforl=1:siz_wordtep=tep+(code_book1(j,l)-code_book(j,l))^2;endendiftep/siz_book0.000001t=0;endcode_book=code_book1;end3.解码%编码后图像恢复过程data3=zeros(M1,siz_word);fori=1:M1《数据压缩与信源编码》实验指导书-9-forj=1:siz_bookifMIU(i,j)==1t=j;endenddata3(i,:)=code_book(t,:);enddata5=zeros(m,n);fori=1:mforj=1:ntep=(i-1)*n+j;i1=floor(tep/siz_word);ifi1==0i1=1;endj1=mod(tep,siz_word);ifj1==0j1=siz_word;enddata5(i,j)=floor(data3(i1,j1)*255);endendfigure(2)《数据压缩与信源编码》实验指导书-10-imshow(uint8(data5));%显示恢复图像title('矢量量化编码后恢复的图像')六、实验注意事项认真听指导教师的讲解，按照要求一步一步做实验。实验完成后，写出规范的实验报告。七、思考题1.码书的大小对图像编码、解码的影响？2.码字的大小对图像编码、解码的影响？《数据压缩与信源编码》实验指导书-11-实验二基于DCT变换的图像压缩技术一、实验目的利用离散余弦变换进行图像压缩。二、实验内容对给定的一幅图像进行分块变换，将变换得到的DCT系数进行编码、传输和解码。三、实验仪器、设备及材料操作系统：Windowsxp；软件：MATLAB四、实验原理1.DCT变换离散余弦变换(DCT)是一种与离散傅立叶变换紧密相关的正交变换,8×8的二维离散余弦变换可以将图像的空间表达式转换到频率域,只用少量的数据点来表达图像,用f(x,y)表示8×8的图像块象素值,F(u,v)表示二维离散余弦变换后的值,具体表达式如下:(4.1)其反变换如下式:(4.2)其中,(4.3)二维离散余弦变换核具有可分离性,即可以先对每行进行一维离散余弦变换,70701612cos1612cos,41,xyvuvyuxyxfCCvuF70701612cos1612cos,41,xyvuvuvyuxyxFCCCCyxF其他情况当10u22vCCvu《数据压缩与信源编码》实验指导书-12-再对每列进行一维离散余弦变换,因此,二维离散余弦变换可表示为:(4.4)(4.5)如果直接按照公式计算,其计算量很大,所以,实际应用中普遍采用快速傅立叶变换(FFT)算法来实现离散余弦变换的快速算法。2.量化编码数据压缩中的量化处理,不是对A/D转换量化,而是对正交变换后的数据进行量化处理,量化输入值的动态范围很大,而量化的输出只能取有限个整数,量化后的数值用较少的比特数便可表示。量化处理总是把一批输入量化到一个输出级上,这样降低了数值的精度,但减少了数据量。DCT的输出系数中,左上角的数据表示低频分量,人眼比较敏感,应该用较高的精度来表示,而右下角的数据可以用较低的精度来表示,因此,我们可以定义一个量化表对不同的数据采用不同的量化等级,这个量化表可以根据期望的压缩比进行调整,一般来说,量化表元素值越大压缩比越大,当然图像失真度也越大。3.“Z”字型扫描量化后的数据本来已经可以直接进行游程编码,但为了提高游程编码的效率,我们必须尽量增加零游程的长度。基于量化后系数的排列特征,采用“Z”字型扫描能有效增加零游程的长度。“Z”字型扫描轨迹如图2.2所示:701612cos,21,xuuxvxGCvuF701612cos,21,yuuxvxGCvuG《数据压缩与信源编码》实验指导书-13-4.哈夫曼(Huffman)编码及解码哈夫曼编码是1952年由Huffman提出的编码方法,基本思想是根据源数据符合出现的概率大小进行编码,出现概率大的符号分配越短的码字,出现概率越小的符号分配越长的码字,从而达到用尽量少的比特数表示数据源,标准哈夫曼编码步骤如下:(1)统计数据源符号出现的概率,得到不同概率的信息符号;(2)将数据源符号按概率递减顺序排列;(3)把两个最小概率相加作为新符号的概率,并按(2)重排;(4)重复(1)、(2),直到概率为1;(5)在每次合并信源时,将合并的信源分别赋“0”和“1”;(6)寻找从每一信源符号到概率为1处的路径,记录路径上的“0”和“1”;(7)从树根开始写出每一符号的“0”、“1”。用标准哈夫曼编码对图像进行编码时效率很高,但需要对原始图像扫描两遍,第一遍要精确统计出每个像素值出现的概率,第二遍是建立哈夫曼树并编码,数据压缩和解压速度较慢,因此,出现了一种改良的哈夫曼编码,它的变长码字不是实时产生而是一个固定的表,在编码和解码过程中不用计算符号概率和排序,直接查表得到,但这个表必须经过大量的统计工作并精心设计才能达到较高的编码效率。在静态图像压缩国际标准(JPEG标准)中,专家组已经