《毕业论文算术编码算法及其应用（含外文翻译） .doc》由会员分享，可在线阅读，更多相关《毕业论文算术编码算法及其应用（含外文翻译） .doc（62页珍藏版）》请在三一办公上搜索。
1、 题目： 算术编码算法及其应用 学 院 信息科学与工程学院 专 业 电子信息工程 年 级 2009级 学 号 0915212003 姓 名 李文玉 指导老师 周林 2013年05月摘 要在现今的电子信息技术领域，由于需要处理的数字化的信息（尤其是多媒体信息）通常会特别庞大，如果不对其进行有效压缩就难以得到实际应用，数据压缩的目的即是通过有效减少数据文件的冗余信息而使数据文件可以以更快的速度传输或在更少的空间储存。因此数据压缩技术已成为当今数字通信、存储和多媒体娱乐的一项关键的共性技术。本文由香农熵理论和统计编码的原理开始，逐步展开对基于算术编码的数据、图像压缩的研究与应用的讨论：从算术编码的产
2、生条件、原理、以及研究算术编码的目的意义等，到具体算术编码方案的分析比较以及其MATLAB语言的实现方案，有重点的对算术编码的编码过程进行了分析和阐述。最后通过对算术算法特点和应用方向的研究，阐明其编码原理及其在图像、数据压缩领域不可取代的地位及在处理流片段数据所具有的在压缩比和灵活性方面的优势，展示出算术编码的强大生命力和独特优势。利用MATLAB软件对仿真程序进行了调试，验证算术编码对数据压缩的可行性。利用Visual C+软件进行仿真，应用自适应算术编码压缩图像，验证了自适应算术编码压缩图像的可行性。关键词: 算术编码算法；图像、数据压缩；MATLAB仿真ABSTRACT Nowaday
3、s, as the digital information (especially the multimedia information) becomes more voluminous in the telegraphy field, the information should be compressed availably. the purpose of data compression is by effectively reducing the redundant information data file and data file to speed faster transmis
4、sion or storage in less space. Therefore, the data compression technology has become a key common technology in the digital communication, storage and multimedia entertainment.From Shannon entropy theory and the statistics coding theory, this paper sets forth the research and application of the data
5、 compression which based on Arithmetic Coding, including the arithmetic coding producing conditions,the theory, and research the having conditions and the purpose of arithmetic coding and then the research of the specific implementation plan with MATLAB language of arithmetic coding. Against the poi
6、nt of arithmetic coding, this paper analysis and expounds its coding process about it . Finally，through the study of arithmetic algorithm characteristics and application direction, advantage and clarify the position can not be replaced in the image, data compression field and in terms of the compres
7、sion ratio and flexibility in dealing with data stream segments, showing a strong vitality and unique advantage of arithmetic coding. The simulation program was debugged using MATLAB software, verify the feasibility of arithmetic coding for data compression.Simulation using Visual C+ software，applic
8、ation of adaptive arithmetic coding for image compression，and verifies the feasibility of adaptive arithmetic coding image compression. Keywords: arithmetic coding algorithm,image data compression,MATLAB simulation目 录第1章 绪 论11.1 算术编码研究的意义及目的11.2 算术编码算法的发展历程11.3 算术编码国内外研究现状和发展趋势21.4 毕业设计的内容3第2章 算术编码算
9、法52.1 信息冗余和信息熵的概念52.2 算术编码算法基本原理52.3 算术编码的编码过程62.4 算术编码的特点8第3章 基于算术编码的MATLAB实现93.1 MATLAB7.1仿真程序实现93.1.1 运行环境说明93.1.2 MATLAB7.1的简介93.2 基于算术编码算法的MATLAB仿真103.3 二元序列算术编码算法的MATLAB实现13第4章 基于算术编码压缩的应用154.1 数据压缩174.2 基于改进的算术编码算法的应用174.2.1 WNC算法算术编码174.2.2 基于算术编码算法的数据压缩MATLAB实现18第5章 自适应算术编码的图像压缩215.1 图像压缩21
10、5.2 自适应算术编码的图像压缩215.2.1 自适应算术编码215.2.2 程序运行结果显示:225.3 图像数据压缩的意义24结论与展望25参 考 文 献27致 谢29附录A 源程序31附录B 外文参考文献45第1章 绪 论1.1 算术编码研究的意义及目的随着多媒体和互联网技术的不断发展，数据压缩技术获得了空前的进步，数码相机、数码摄像机等手持式设备的普及应用，要求图像数据压缩技术能够在够高的压缩比下实现较好的图像质量，以满足存储空间有限条件下的海量数据压缩问题。各种媒体信息（特别是图像和动态视频）数据量非常之大，就要求与之相应的有较好的压缩技术。而算术编码作为一种高效的数据编码方法在文本
11、，图像，音频等压缩中有广泛的应用。所以，研究算术编码有非常好的前景与实用价值。不论是活动图像还是静止图像，采用算术编码得到的码流都比用霍夫曼编码得到的码流要短，编码效率高。但是到目前为止，算术编码还没有完全取代霍夫曼编码。在许多图像压缩编码标准里，算术编码仅是一个选项。这除了知识产权方面的原因外，算术编码复杂度较高，不论是软件还是硬件实现起来都比较困难是一个主要因素。可以预见，随着超大规模集成电路技术的发展，高速高性能处理器的大量涌现，复杂度较高的算法也有可能实时实现。另一方面，快速的算术编码算法也不断被发现提出，比如IBM公司的Qcoder，PaulGHoward等提出的准算术编码器等。这些
12、快速算法以损失一定的编码效率为代价，采用近似的方法，加快了编码速度。此外，更加有效的概率估计模型的提出也会进一步提高算术编码的效率。随着以上几方面的的进展，算术编码在图像压缩编码内的应用将会越来越广，它比著名的Huffman编码效率提高5%10左右，最终必将取代霍夫曼编码方法。所以，研究算术编码以更好的利用它是非常必要的。1.2 算术编码算法的发展历程1948年，Shannon（香农）在提出信息熵理论的同时，也给出了一种简单的编码方法Shannon编码。Shannon提出将信源符号依其出现的概率进行降序排列，用符号序列累计概率的二进制作为对信源的编码，并从理论上论证的了它的优越性1。1952年
13、，R.M.Fano（法诺）又进一步提出了Fano编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。1968年前后，P.Elias（伊莱亚斯）发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1976年，J.Rissanen（瑞萨尼恩）提出了一种可以成功地逼近信息熵极限的编码方法算术编码。1979年，瑞萨尼恩和兰顿（G.G.Langdon）一起将算术编码系统化，并于1981年实现了二进制编码。1982年，Rissanen和G.G.Langdon一
14、起改进了算术编码。之后，人们又将算术编码与J.G.Cleary和I.H.Witten于1984年提出的部分匹配预测模型（PPM）相结合，开发出了压缩效果近乎完美的算法。1987年，威滕（Witten）等人发表了一个实用的算术编码程序。同期，IBM公司发表了著名的Q编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了广泛的注意。1.3 算术编码国内外研究现状和发展趋势随着计算机技术的发展，图像编码与压缩技术的研究受到人们越来越多的关注。编码在数字化过程中占有非常重要的地位。在满足一定图像质量要求的前提下，能获得减少数据量的编码成为编码压缩。研究最佳的编码压缩的数学模型和方法是
15、人们追求的目标。由于算术编码技术不像哈弗曼编码方法那样要求将每个信源符号都编码成整数个二进制比特，所以这种技术达到了无噪声编码准则所设定的界限。因此，在JEPG压缩标准的改进版本中（如JEPG2000）已经采用算术编码来代替哈弗曼编码了。 数字视频技术广泛应用于通信、计算机、广播电视等领域，带来了会议电视、可视电话、数字电视和媒体存储等一系列应用，促使了许多视频编码标准的产生2。ITU-T与ISO/IEC是制定视频编码标准的两大组织，ITU-T的标准包括H.261、H.263、H.264，主要应用于实时视频通信领域，如会议电视；MPEG系列标准是由ISO/IEC制定的，主要应用于视频存储（DV
16、D）、广播电视、因特网或无线网上的流媒体等。目前，H.261与H.263在视频通信中广泛应用，成熟的产品已经很多。H.263与H.261相比，增加了若干选项，提供了更灵活的编码方式-算术编码算法，压缩效率大大提高，更适应网络传输。H.264标准的推出，是视频编码标准的一次重要进步，它与现有的MPEG-2、MPEG-4 SP及H.263相比，具有明显的优越性，特别是在编码效率上的提高，使之能用于许多新的领域。尽管H.264的算法复杂度是现有编码压缩标准的4倍以上，随着集成电路技术的快速发展，H.264的应用将成为现实。两个组织也共同制定了一些标准，H.262标准等同于MPEG-2的视频编码标准，
17、而最新的H.264标准则被纳入MPEG-4的第10部分。H.264是由ISO/IEC与ITU-T组成的联合视频组（JVT）制定的新一代视频压缩编码标准3。H.264标准采用的熵编码有两种：一种是基于内容的自适应变长编码（CAVLC）与统一的变长编码（UVLC）结合；另一种是基于内容的自适应二进制算术编码（CABAC）。CAVLC与CABAC根据相临块的情况进行当前块的编码，以达到更好的编码效率。CABAC比CAVLC压缩效率高，但要复杂一些。H.264的主要优点如下：在相同的重建图像质量下，H.264比H.263+和MPEG-4（SP）减小50%码率。在编/解码器中采用复杂度可分级设计，在图像
18、质量和编码处理之间可分级，以适应不同复杂度的应用。除上述ITU-T的视频压缩标准外，还有一些标准也比较流行，如MPEG-4、AVS、WM9 也称为MPEG-4 AVC，而目前业内所说的MPEG-4一般是指SP（简级）或ASP（先进的简级），主要针对低码率应用，如因特网上的流媒体、无线网的视频传输及视频存储等，其核心类似于H.263。MPEG-4 ASP较SP增加了一些技术，主要有：1/4象素精度的运动估计、B帧、全局运动矢量（GMV），因而压缩效率得以提高。AVS是由我国自主制定的音/视频编码技术标准，主要面向高清晰度电视、高密度光存储媒体等应用。AVS标准以当前国际上最先进的MPEG-4 A
19、VC/H.264框架为基础，强调自主知识产权，同时充分考虑了实现的复杂度。相对于H.264，AVS的主要特点有：（1）88的整数变换与64级量化；（2）亮度和色度帧内预测都是以88块为单位，亮度块采用5种预测模式，色度块采用4种预测模式；（3）采用1616、168、816和88 4种块模式进行运动补偿；（4）在1/4象素运动估计方面，采用不同的四抽头滤波器进行半象素插值和1/4象素插值；（5）P帧可以利用最多2帧的前向参考帧，而B帧采用前后各一个参考帧。Window Meida 9（WM9）是微软公司开发的新一代数字媒体技术。一些测试表明，WM9的视频压缩效率比MPEG-2、MPEG-4 SP
20、及H.263高很多，而与H.264的压缩效率相当。1.4 毕业设计的内容 （1）了解算术编码算法的研究现状和发展趋势，研究意义及目的； （2）掌握算术编码算法的原理及其编码过程，并应用MATIAB实现其编码； （3）通过MATLAB编程，应用算术编码算法对二值序列的编码，实现其码字的输出； （4）应用算术编码算法对数据进行编码，实现数据的压缩； （5）应用自适应算术编码对图像进行编码，应用VC程序实现图像的压缩。第2章 算术编码算法2.1 信息冗余和信息熵的概念 在信息论中，信息冗余是传输消息所用数据位的数目与消息中所包含的实际信息的数据位的数目的差值。数据压缩是一种用来消除不需要的冗余的方法
21、，校验是在经过有限信道容量的噪声信道中通信，为了进行错误校正而增加冗余的方法。图像压缩的基本理论起源于1948 年Shannon划时代的论文“通信的数学理论（ A Mathematical Theory of Communication ）”，该论文提出，任何信息都存在冗余，冗余大小与信息中每个符号（数字、字母或单词）的出现概率或者说不确定性有关。 Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”，并给出了计算信息熵的数学表达式。 H(x)=EI()=E = -(i=1,2,.n) （2.1.1）其中，x表示随机变量，与之相对应的是所有可能输出的集合，定义为符
22、号集,随机变量的输出用x表示。P(x)表示输出概率函数。变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大4。熵的一个重要价值在于它定义了一个关于编码性能的根本界限。这在Shannon的“无噪生信源编码定理”中第一次得到阐述。这个定理的本质是：随机过程的熵率提供了对它的每一个输出进行编码所花费的平均位数的下界，而且当编码方案的复杂度允许无限制增长时，可以任意逼近这个下界。基于这个理论框架，产生了很多种不同的熵编码方法。例如：算术编码、哈弗曼编码、LZW编码等等。2.2 算术编码算法基本原理算术编码是一种无失真的编码方法，能有效地压缩信源冗余度，使编成的码率趋于信源的熵，它是无损压
23、缩的一种5。算术编码的基本原理是：根据信源可能发现的不同符号序列的概率，把 0，1)区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。本文主要是以静态算术编码算法为例。在自适应算术编码中，自适应算术编码在对符号序列进行扫描的过程中，可一次完成两个过程，即根据恰当的
24、概率估计模型和当前符号序列中各符号出现的频率，自适应地调整各符号的概率估计值，同时完成编码。信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。尽管从编码效率上看不如已知概率表的情况，但正是由于算术编码自适应的调整对个符号概率的估计值，这点比哈弗曼编码相比，具有实时性好、灵活性高、适应性强等特点，在图像压缩、视频图像编码等领域都得到了广泛的应用。2.3 算术编码的编码过
25、程算术编码在图像数据压缩标准（如JPEG，JBIG）中扮演了重要的角色6。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。 以信号s=bcbabbadca为例介绍，其中信源符号集为a,b,c,d。1、统计信源符号出现的概率，将0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔，如图2.3.1所示：abcd0.30.40.2
26、0.1 0 0.3 0.7 0.9 1 图2.3.1 信源符号比例间隔划分在这里引入累计概率密度函数来描述信源符号在分析区间的上界： CDF（)= (2.3.1)其中表示第i个信源符号，p()表示xi的概率。则有：CDF(a) = 0.3 CDF(b) =CDF(a) +P(b)=0.3+0.4=0.7 CDF(c) = CDF(b)+P(c)=0.7+0.2=0.9 CDF(d) =CDF(c) +P(d)=0.9+0.1=12、读入信源,找到其在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。若=b,则其所在的比例间隔为CDF(a)和CDF(b)之间的区域，如图2.3.2所示：abc
27、d0.30.40.20.1 0 0.3 0.7 0.9 1 0 0.3 0.7 0.9 1 图2.3.2 信元所在区间示意3、仍然按照信源符号的概率序列在当前分析区间划分比例间隔，然后重复第二步，直到所有的信元输入完毕为止。如图2.3.3所示：abcd0.30.40.20.1 0 0.3 0.7 0.9 1 0.3 b 0.7 0.58 c 0.66 0.604 b 0.636 0.604 a 0.6136 0.60688 b 0.61072 0.608032 b 0.609568 0.608032 a 0.6084928 0.60844672 d 0.6084928 0.608478976
28、c 0.608488192 图2.3.3 算术编码过程4、以最后的当前分析区间内的任意一个数作为编码输出。例如本例就可以选择0.608478976和0.6084817408之间的一个小数0.6084798作为信号的编码输出。2.4 算术编码的特点算术编码的优点：（1）不必预先定义概率模型，自适应模式具有独特的优点； （2）信源符号概率接近时，建议使用算术编码，这种情况下其效率高于霍夫曼编码； （3）算术编码绕过了用一个特定的代码替代一个输入符号的想法，用一个浮点输出数值代替一个流的输入符号，较长的复杂的消息输出的数值中就需要更多的位数；（4）算术编码实现方法复杂一些，但JPEG成员对多幅图像的
29、测试结果表明，算术编码比霍夫曼编码提高了10%左右的效率，因此在 JPEG 扩展系统中用算术编码取代霍夫曼编码7。算术编码虽然具有其独特的优点，但我们仍需要注意下面几个问题：（1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。（2）算术编码器对整个消息只产生一个码字，这个码字是在间隔0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。（3）算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。 算术编码随着序列长度的增加，相应子区间的宽度
30、也不断缩小，要表示这段子区间所需精度，直观地说就是比特数也不断增加。这不但要占用相当大的存储空间，还增加了编码延时，这对实时系统是十分不利的。为了解决这些难点，针对不同的应用方向，人们对传统的算术编码方法进行了改进，在保证足够精度的前提下，提高了编码速度。基于算术编码算法人们提出了二进制自适应的算术编码以及MQ算术编码器，分别在软件及硬件上提高编码的效率。 第3章 基于算术编码的MATLAB实现3.1 MATLAB7.1仿真程序实现 3.1.1 运行环境说明CPU： 酷睿i3 内存： 4GB DDRAM操作系统： Windows 7运行软件： 官方正式版matlab7.1 3.1.2 MATL
31、AB7.1的简介MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。MATLAB由一系列工具组成。这些工具方便用户使用MATLAB的函数和文件，其中许多工具采用的是图形用户界面。包括MATLAB桌面和命令窗口、历史命令窗口、编辑
32、器和调试器、路径搜索和用于用户浏览帮助、工作空间、文件的浏览器。随着MATLAB的商业化以及软件本身的不断升级，MATLAB的用户界面也越来越精致，更加接近Windows的标准界面，人机交互性更强，操作更简单。而且新版本的MATLAB提供了完整的联机查询、帮助系统，极大的方便了用户的使用。简单的编程环境提供了比较完备的调试系统，程序不必经过编译就可以直接运行，而且能够及时地报告出现的错误及进行出错原因分析。MATLAB7.1版本是在2005年更新的，本文主要应用MATLAB7.1中发布的影像处理工具箱中的相关函数和命令来实现基于算术编码实现图像压缩理论算法的仿真。MATLAB7.1是一套功能十
33、分强大的工程计算及数据分析应用软件,广泛应用于工业、电子、控制、信号及图像处理等各领域。MATLAB7.1本身除了提供强大的图形绘制和输出功能外,同时还发布了影像处理工具箱(Image Processing Toolbox),专门用于图像的处理.在通常情况下，可以用它来代替底层编程语言，如C和C+ 。在计算要求相同的情况下，使用MATLAB的编程工作量会大大减少。3.2 基于算术编码算法的MATLAB仿真算术编码是一种无损数据压缩，也是一种熵编码的方法。和其他熵编码方法的不同之处在于，其他熵编码方法通常是把输入的信号分割为信源符号，然后对每个符号进行编码，而算术编码算法是直接把输入的信号编码为
34、01之间的小数8。算术编码的编码过程可用下面的例子加以解释。假设一则消息“static_tree”具有如下的概率分布： 字符 概率 - （space） 0.1 a 0.1 e 0.3 r 0.1 s 0.1 t 0.3主程序：clear allclcformat long;symbol = _aerst;pr = 0.1 0.1 0.3 0.1 0.1 0.3;seqin = state_tree;symlen=length(seqin);codeword = arencode(symbol, pr, seqin);seqout = ardecode(symbol, pr, codeword,
35、 10);1、编码过程 一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以，这里所用的6个字符被分配的范围（range）如下： 字符 概率 范围 (space) 0.1 0r0.1 a 0.1 0.1r0.2 e 0.3 0.2r0.5 r 0.1 0.5r0.6 s 0.1 0.6r0.7 t 0.3 0.7r0.6,0.7）(3)对第二个字符t编码，使用的新生范围为0.6,0.7），因为t的low_range=0.7,high_range=1.0,因此下一个low,high分别为 Low=0.6+0.1
36、0.70.67 High=0.6+0.11.00.70 Range=0.7-0.67=0.03 t将0.6,0.7）=0.67,0.70）(4)对第三个字符a编码，在新生成的0.67,0.70）中进行分割，因为a的low_range=0.10,high_range=0.2,因此下一个low,high分别为 Low=0.67+0.030.10.673 High=0.67+0.030.20.676 Range=0.676-0.673=0.003 a将0.67,0.70）=0.673,0.676）(5)对第四个字符t编码，在新生成的0.673,0.676）上进行分割。因为t的low_range=0.
37、70,high_range=1.0,则下一个low,high分别为 Low=0.673+0.0030.70.6751 High=0.673+0.0031.00.676 Range=0.0009 t将0.673,0.676）=0.6751,0.676） 同理得到下面各字符e,s,t,r,e,e编码所得到的范围分别为0.67528,0.67555），0.67528,0.675307），0.675 298 9,0.675 307），0.675 302 95,0.675 303 76），0.675 303 112,0.675 303 355），0.675 303 160 6,0.675 303 233
38、 5）算术编码的部分程序：function arcode = arencode(symbol, pr, seqin)%算术编码%输出：码串%输入：symbol：字符行向量% pr：字符出现概率% seqin：待编码字符串 high_range = ;for k = 1: length(pr), high_range = high_range sum(pr(1: k);endlow_range = 0 high_range(1: length(pr) - 1);sbidx = zeros(size(seqin);for i = 1: length(seqin), sbidx(i) = find(symbol = seqin(i);endlow = 0; high = 1;for i = 1: length(seqin), range = high - low; high = low + range * high_range(sbidx(i); low = low + range * low_range(sbidx(i);endarcode = low;2、 解码过程
