基于JPEG2000的高速二进制算术编码器研究

基于JPEG2000的高速二进制算术编码器研究 西安电子科技大学 硕士学位论文基于JPEG2000的高速二进制算术编码器研究 姓名:曾伟 申请学位级别:硕士 专业:计算机应用技术 指导教师:刘凯 2011-01 摘要 摘要 新一代静止图像压缩 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ,,,,,,,,采用基于上下文自适应的二进制算术编码进行熵编码。算术编码具有卓越的编码性能，在大部分情况下其平均码长都能接近信源熵。然而，它的计算复杂度高，包含大量比特级操作和复杂逻辑控制。因此，如何提高算术编码器吞吐率成为 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与实现的瓶颈。 本文首先深入研究了二进制算术编码原理。然后， 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了,,,,,,,,中算术编码器(又称,,编码器)的处理过程，并对其中应用到的关键技术进行了阐述，包括基于状态迁移的概率估计、位填充和间隔位机制以及区间更新无乘法变形等。 在上述基础上，本文设计了双符号处理的高速,,编码器。首先，双符号处理时两个上下文有相同和不同两种情况。针对每种上下文情况，编码过程被分解为,个分支:处理双大概率符号(,,,,,,)、处理双小概率符号(,,,,,,)、大概率符号接小概率符号(,,,,,,)以及小概率符号接大概率符号(,,,,,,)。通过编码情况分解，符号间的数据相关性被分离，并发编码成为可能。然后，本文预测出双符号处理间隔区间划分情况共计,,种，并详细描述了区间更新过程。最后，归纳了双符号处理时码流输出情况。 本文用,语言分别实现了单、双符号处理的,,编码器。通过使用上下文判决样本进行编解码处理，校对两种编码器输出码字和编解码前后的判决数据，验证了编码器设计的正确性。然后，给出了双符号,,编码器的四级流水线,,,，结构。最后，本文对概率估计表进行优化，降低了存储需求。关键词:,,,,,,,, 二进制算术编码 ,,编码器,,, , ,,,,,,;, ,,,,,,;, ,,,,,,,, ;,,,,,,,,,, ,,,,,,,, ,,,,,, ;,,,,,,—,,,,,,,, ,,,,？ ,,,,,,,,,; ;,,,,,,,, ,,,,,,, ;,,,,,(,,,,,,,; ;,,,,, ,,, ,,;,,,,,, ;,,,,, ,,,,(,,,,,;,(，, ,,,,;,,,,，,,, ,,,,,,, ;,,, ,,,舒, ;,,, ,, ;,,,, ,, ,,, ,,,,;,?,,,,,,,(,,,,,,,，,, ,,, ,,,,;,,,,,,,,,,,, ;,,,,,,,,, ,,, ,,;,,,,, , ,,,,, ,,,,,, ,, ,,,,,,,,, ,,,,,,,,,, ,,, ,,;,,,,,, ;,,,,,, ,,,,;,(,,,,,,,,,，,,, ,, ,,,,,,, ,,, ,,,,,,,,,; ;,,,,?, ,,,,,曲,,,,,, ,,,,,,,,;, ,, ,,,,,, ,,, ,,,,,,,,,,,,,,( ,,,,,,,;,,,, ,,,,, ,,,,,,, ,,, ,,,,;,,,, ,, ,,,,叮,,,,,,,,,; ;,,,,, ,,,,,,,(,,,,，,,,,,,,,, ,,, ;,,,,, ,,,;,,, ,, ,, ;,,,, ,, ,,,,,,,,，,,, ,,,;,,,, ,,, ,,;,,,,,,,,,印,,,,, ,, ,, ;,,,,(,,,,, ,,;,,,,,,,,, ,,;,,,, ,,,,,,,,,够,,,,,,,,, ,,,,, ,, ,,,,,,,,,,,,,，,,, ,,,,,,, ,,, ,,,;,,, ,,;,,,,,，,,, ,,, ,,,,,,,, ,,,,,, ,,,,,,,,,,,,,,,;,,,,,( ,,,,, ,, ,,, ,, ,,,，,, ,,,,,, ,,,,,,,,,, ,,,,,,,,,,,,; ,,,;,,,,,, ,, ,,;,,,,(,,,,,，,,, ,,,,,,—,,,,,, ,,,;,,,,,, ,,, ,,, ,,,,, ,, ;,,,,,, ;,,,,，,, ,,, ,锄, ;,,,,,,,,，,, ,,, ,,,,,,,,, ;,,,,,,,(,,, ,,;, ;,,,，,,, ,,;,,,,, ,,,;,,, ,, ,,,,,, ,,,, ,,,, ,,,,,,,，,;,,,:,,,,,,,, ,,,,,, ,,,, ,,,,,,,,,,, ,,,,,,,(,,,,,,)，,,,,,,, ,,,, ,、,, ,,,,,,,,,,,,,,,, ,,,,,,,(,,,,,,)，,,,, , ,,,, ,,,,,,,,,,, ,,,,,, ,,,,,,, ,, , ,,,,,,,,,,,,,,,, ,,,,,,(,,,,,,),，,, , ,,,,,, ,,,,,,,,,,, ,,耐,,, ;,,,,;,,, ,,,, , ,,,,,,,,,,,,,,, ,,,,,, (,,,,, ,,)(,,,,,,,,,，,,,, ,,,,,,,,;, ,,,,,,,,,,,,, ,,, ,,,,,,,,,(,,,;,,,,,, ,,;,,,,, ,, ,,,,,,,,(,,,,，,, ,,,,,;, ,,,, ,,, ,,,,,,,, ,, ,,, ,,,,?,,,觚,, ,,,, ,, ,,,;,,,(,,, ,,,,,,,, ,,,,,, ,,,;,,, ,, ,,, ,,,,,,(,,,,,,,， 、,, ,,,,,,,,, ,;舶,, ,, ,, ,,,,锄,,,,,, ,,,,,,,,, ,, ,,, ;,,, ,, ,,,—,,,,,, ,,,;,,,,,,( ，, ,,,, ,印,,，,,,,,, ,,,, ,,,,,, ,,,,,, ,, ;,,,, ,, ,,,,,,,,,,, ,, ,,,伊,, , ,,,,,,;, ;,,,,,, ,,, ;,,,,, ,,, ,,;,,,,,，,,,, ;,,;, ,,, ,,,,,;,,,,，,(,色,,, ,,,,,, ,,,,,,, ,, ,,, ,,,,, ;,,,, ,,, ;,,,,,, ,,, ,,,, ,,,,,, ,,;,,,,, ,,,, ,,, ,,,, ,,,, ,,,, ,,,,, ,,,, ,,,,,, ,,;,,,,,(,,,,, ,,,,,, ,, ,,,,,,,,(,,,,，,,,, ,,,,, ,,,,,,,, , ,, ,,;,,,,?, ,,,， ,,,,;,,，。,(,,,,,,,，,, ,,,,,,,, ,,, ,,,,,,,,,,, ,,,,,,,,,, ,,,，,，,,, ,,, ,,,, ,, ,,,,,,;,,,,, ,,,,;,,( ,,,,,,,, ,,,,，, ,,,,,,,,,; ,,;,,,,, ,, ,,;,,,, ,,,， ,,,,,,,,: 第一章绪论 第一章绪论 随着多媒体和通信技术的快速发展，图像压缩方面的需求越来越高，这主要表现在:一方面信息总量急剧增大，人们的存储需求不断提高，各种存储介质容量不断扩大，而大量数据被压缩后，无疑将为我们节省更多存储成本;另一方面，通信技术尤其是网络通信的发展，给我们的生活、工作带来了诸多便利，时时刻刻海量的数据在网络中交换、传输，压缩编码技术的发展将使传输变得更加高效、快捷。因此，人们越来越重视图像压缩编码方面的研究工作。 ,(,熵编码 通常的图像数据和人类感觉存在着各种冗余【,】: ,)空间冗余，图像相邻象素之间存在关联。 ,) 时间冗余，图像序列不同帧之间具有相关性。 ,)频谱冗余，由不同彩色平面或频谱带的相关性造成。 ,)统计冗余，信号中有的字符出现频率高，可以采用较短的编码;有的信号特征有标度不变性或统计白相似性。 ,)视觉冗余，人眼对亮度变化比对色彩的变化更敏感、对高亮区的量化误差不敏感、视网膜分频道。 正是由于这些冗余信息的存在，给图像压缩编码很大的研究空间。本质上，编码与压缩就是对要处理的源数据按一定的规则进行变换和组合，从而达到以尽可能少的比特数(符号)来表示尽可能多的数据信息。 熵编码(,,,,,,, ,,;,,,,,)是一类利用数据统计信息进行压缩的无语义数据流无损编码。熵(,,,,,,,)是热力学中用来度量热力学系统无序性的一种物理量。香农(,,锄,,)于,,,,年在他所创建的信息论【,】中引进熵的概念，用来度量信息中所含的信息量，信息量定义为信源发出的所有信息中该信息出现概率的负对数，信息熵表示平均信息量，如式(,(,)所示: ,(,),一?厶(,),,,:厶(,) (,,,) ,,,, 其中，,表示随机变量，与之相对应的是所有可能输出的集合，定义为符号集彳,，随机变量的输出用,表示。厶(,),,(,,,)，表示输出概率函数。, 基于,,,,,,,,的高速二进制算术编码器研究 主要的熵编码方法【,】有:香农(范诺(,,,,?,,,(,,,,)编码、哈夫曼(,,,,嘧,,)编码、算术编码(,,,,,,,,,; ;,,,,,)、行程编码(，,,)和,,,编码。不同数据源适宜于不同的压缩编码方法。在图像压缩编 算术编码是一种重要的码中，熵编码得到了广泛的研究和使用。 ,(,算术编码 熵编码方法，基本思想是用【,，,)区间中一个宽度等于其出现概率的实数区间来表示一个符号，符号表中的所有符号刚好布满整个【,，,)区间(所有符号出现概率之和为,，不重不漏)。输入符号串(数据流)最终映射成【,， ,)区间中的一个实数值。 算术编码的发展历程可以追溯到,,,,年，当时,,,,?,,,在论文,,,中提出:一条,符号消息，可以通过先对符号的概率进行排序，再按照该顺序发送符号累计 ,,泌【,,发现,,锄,,的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 可以不通过概率排序，而概率来传输。,,,,年，,,,,, 以递归划分子区间的方式进行。,,锄,,和,,,,,编码存在无限精度运算的问题， 即随着编码消息长度的增加，递归运算需要的计算精度也随着增加。,,,,年，砥,,,,,,和,,,;,【,〕给出以适当近似来解决有限长精度问题的方案，提出了算术编码算法。,,,,年，硒,,,,,,和,,，,,,,,将算法系统化【,,并于,,,,年实现【,,,最后，砌,,,，,,,于,,,,【,】年完善并发布了算术编码算法。,,,,年，，,,公司对算术编码做了大量的研究【,，,们，并发表了著名的,编码器，随后又提出,,编码器(用于,,，,标准)和,,编码器(,,,,,,,,标准,,,，, ,,和,,，,,标准)。 算术编码性能优异，它与,,,,,,,,编码和行程编码不同，跳出了分组码的范 畴:从全序列出发，采用递推形式进行连续编码。它不是把单个信源符号映射成 一个码字，而是将整个输入符号序列映射为〔,，,)区间内的一个子区间，其长度等于 该序列的概率;再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出，从而达到高效编码的目的。不论是否为二元信源，也不论数据的概率分布 怎样，其平均码长都能逼近信源的熵。 ,(,研究背景及意义 随着图像编码技术不断发展，国际图像联合专家组(,,,,, ,,,,,,,,,,,; ,,,,,,,,,,,， ,,,,)于,,,,年,,月推出了新一代静止图像压缩标准,,,,,,,,,,,,。与传统的,,,,【,,,标准不同，,,,,,,,,基于离散小波变换(,,,;,,,, ,,,,,,, ,,,，,,,,肌，,,,)„,,。,引，采用当前最新的优化截取内嵌码块编码(,,,,,,,, ,,,;, ,,,,,, ,,,,,,,,,,,,, ,?,,;,,,,,，,,,,,)渺,, ,和高效算术编码，提供了卓越的压缩性能和一系列丰富功能，不仅可应用于传统,,,,市场，而且可以应用于视频医疗影像、无 第一章绪论 ,线通信、网络传输等新兴领域。由于采用了先进的编码技术，与,,,,相比，,,,,,,,,有很多优越性„,,出】，主要体现在以下方面: ,)良好的低比特率压缩性能。,,,,,,,,实现了低比特率性能的明显改善，其压缩效率比,,,,高约,,,。 ,)连续色调图像压缩和二值图像压缩。,,,,,,,,既能压缩连续色调自然图像，又能压缩二值图像。 ,,有损和无损压缩编码之间的兼容。 ,)渐进传送。不同于,,,,由上到下从左到右一块一块地慢慢传输，,,,,,,,,在传输时，可以按质量(像素精度)、分辨率、空间位置和图像分量,种渐进模式进行传输。 ,)码流的随机访问和处理。有些情况下，可定义图像中感兴趣区域(,,,,,,, ,,，,,,,,,,，,,，)，用低压缩比换高质量图像，而其他部分用高压缩比节省存储空间。 ,)很强的抗误码特性。,,,,,,,,在码流中添加同步标志增强了容错性。 由于,,,,,,,,的优良性能以及广阔应用前景，其硬件电路结构研究也成为一个热点。其中熵编码部分采用的二进制算术编码器——,,编码器设计就吸引了不少研究者【,孓,, ,。然而，算术编码计算复杂度高，包含大量比特级操作与复杂逻辑控制，如何提高编码器吞吐率(,,,,,曲,,,)成为研究中的重点。 本文工作受到了国家自然科学基金项目(,,,,,,,,)“高速图像编码中系数优化分配及相应算术熵编码结构研究”和中央高校基本科研业务费项目(,,,,,,,,,,,,,)“高速低存储图像算术熵编码多核处理体系结构研究”资助。 本文创新点在于:,)针对当前许多样本并行位平面编码器设计和算术编码器的吞吐率瓶颈问题，本文设计实现了双符号处理,,编码器软件，实现一次编码过程处理两个符号。在此基础上，给出了双符号,,编码器的硬件解决方案，一个时钟周期可以处理两个符号。,)本文对并行算术编码器的概率估计表进行了优化，编码器的存储需求被显著降低。以上工作对高速低存储算术编码器的应用研究有着重要意义。 ,(,论文组织 综合上面介绍，可以看出，算术编码具有卓越的编码压缩性能，且已经被众多图像和视频国际标准所采纳，,,,,,,,,中的,,编码器就是它们中的典型:另一方面，必须看到，算术编码计算复杂度高，它包含大量比特级操作以及复杂的控制，使得其吞吐率成为设计实现的瓶颈。因此，设计一款高吞吐率二进制算术编码器具有很大的应用价值和研究意义。 本文将对高速二进制算术编码器进行研究，接下来内容组织如下:, 基于,,,,,,,,的高速二进制算术编码器研究 第二章，首先介绍算术编码基本原理，然后重点描述二进制算术编码的若干技术细节。 第三章，给出,,,,,,,,中所采用的,,编码器概况，阐述其算法实现 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ，并就处理过程中的关键技术进行分析。 第四章，在分析,,,,,,,,中二进制算术编码器的基础上，首先，探讨并发符号编码的可能性。然后，设计双符号处理的,,编码器，详述其区间更新过程。最后，归纳双符号处理时码流输出情况。 第五章，用,语言实 现单、双符号处理的,,编码器，并进行编解码处理，验证设计的正确性。在软件设计的基础上，给出双上下文,,编码器的硬件结构。最后，对概率估计表进行优化，降低存储需求。 第六章，对本文研究工作进行总结，为下一步研究提出方向。 第二章算术编码原理 , 第二章算术编码原理 算术编码是从整个符号序列出发，采用递推形式进行连续编码的一种高压缩效率熵编码方法。下面首先介绍算术编码思想来源——,,,,,编码，及其固有的局限性。然后描述二进制算术编码算法及其技术细节，通过编码形式的变化，消除了,,,,,编码的局限性。 ,(, ,,,,,编码,(,(, ,,,,,编码方法 设,以,为无记忆平稳随机过程，五:。表示随机变量的前,个输出，那么该算法可以理解为将信源序列每一个这样长度为,的前缀和实数轴上一个区间相联系:〔已，巳，,),〔,，,)。因此，这个区间的长度为氏(,:。)，则,五)的累计概率分布吒可表示如下: ,一, 只(,，),?厶(倪，) (,?,)编码算法如下: ，,,,,,,,,,,,,，,,, ,,, ,,;, ,,,，,，… 口”，，,,厶(吒) ,,迭代更新区间上限, ？，。,巳，,最(吒) ,,迭代更新区间下限; 下面用一个具体实例来解释,,,,,编码算法。假设有一个两符号的信源 彳,,口，,)，其中各符号的概率分别为,(口),,(,,，,(,),,(,,。符号概率可以用〔,(,，,(,】之间的半开区间表示，如表,(,所示。 表,(, ,,,,,编码概率模型 ，,,,, ,,,,,, ,,,,曲,,时 ,口,,, , , , ,(,, 〔,(,,，,(,), 基于,(,, 〔,(,，,(,,) , ,,,,,,,,的高速二进制算术编码器研究 用上表的概率模型对信源序列“,,,,,”进行编码，区间演变过程如图,(,所示。黑色区间段表示信源符号落入区间。 口,,, ,, ,, ，， , ;，,万 , , ;,,, ? , ?一, ;。,可 ,,,,,,(,) ,,, (,, , , ，, , ，,一? ,,, (, , , ，, ,, ,,,,,,(,,,,) ,,,,,,(,,,,,) 图,(, ,,,,,骊哟不恧图 由于信源序列中第一个符号是,，编码符号,后区间首先被缩小到〔丢，,(,)，然后区间被细分为〔寺，考)、〔舌，,?,);当第二个符号,被编码时，区间缩小为〔专，舌)，然后区间被细分为〔丢，等)、【等，等);编码第三个符号,时，区间缩小为【等，擎)，这个区间随后被划分为两个子区间【竽，等)、〔等，半);编码第四个符号,时，区间缩小为〔等，半)，再把其细分成两个子区间〔等，等)、【等，等);信源序列最后一个符号是,，对应于这段信息的最后区间是【三竽，三箸)。 因为每一个不同矢量,。相对应区间,，;。，日。()的集合不连续，使得特定输出 ,:。可以用【,，,，,)内的任意数字来唯一识别。当任意一个信源符号序列到达 时，,,,,,编码就构造一个单一的码字，从而可以实现“增量解码”，即:给定任意 的,?【,，气，口。)，对每一个，,,,，,，(((，朋，，(?〔？，巳，,)，可以逐个对前缀‰:。进行解码，其优点是不需要延迟和用来保存巨大码字集合的存储器。我们可以用区间【等，等)中任意一个数值来作为信源序列“,,,,,，?的编码结果，假如我们选择 呈:笋作为序列“,,,,,，，的编码结果，下面同样用表,(,的概率模型对编码结果进行解码。 第二章算术编码原理 , 解码前首先初始化解码器区间为【,(,，,(,)，此区间被细分为〔,(,告)、【吉，,(,)两个子区间。因为解码器收到的编码结果是等，而这个值落入了区间〔丢，,(,)，所以 第一个解码出来的符号是,;然后区间弓，,(,)被细分为两个子区间〔丢，吾)、【丢，,(,)，等落入子区间【丢，?)，故第二个解码出来的符号是,;区间缩小为【丢，云)，并且被细分为,，等)、学，等)，等属于子区间号，擎)，解码器推断出下一个符号是,并且把区间号，等)细分为学，等)、【等，芋);由于等属于子区间【等，等)，所以解码出来第四个符号是,;区间进而缩小为【等，予并且被细分为〔等，等)、〔等，等)，因为编码结果为等，很自然的编码器推断出下 如果解码器预先知道信源而:。的位数厶，那么到这一步解码器就可以停止解码，否则，最直接的方法是需要提供一种发送长度信号机制。而,,,,,提出了特别的码字终止方法，使得不需要明确发送编码长度信号匕。由于;。?【,，,】，可表示为二进制小数形式:,(,,,,…，其中,表示二进制数。或,。设厶,厂,,,,土〕，,， “卅使得,一,?妻‰，设,为取靠中前,个小数位，并把,加到最低有效位位置而形 二成的量，即,,,一,,,,气，,,吒。 因为,，,一,?;册，,×,一,?,，口。，假定解码器接受到与,前厶位一致的任意一串二进制位，将这一串二进制位当作值为，,的二进制小数来处理，则可以得到,,,?,,云，,一,?,，口。，所以，，(?【气，;。，,)唯一确定确:。。这也说明，输出,:。可以用另外任意二进制位串的前厶位准确表示。,(,(, ,,,,,编码局限性 由上一节的编、解码过程注意到，在所有信源符号都被编码前，编码器不输出任何码流，因此解码器必须等到所有符号都被编码完成之后才能开始解码，这在一定程度上降低了解码效率;编码器输出码流是一个区间，而不是我们通常希, 基于,,,,,,,,的高速二进制算术编码器研究望得到的一个唯一编码结果;编、解码过程中区间更新时的乘法运算会耗费大量时间，影响算术编码在实时场合的应用:最重要的问题，,,,,,算术编码在输入符号不断增加时，所需要的数字精度越来越高，有限精度问题导致了,,,,,编码并不能实际应用。 ,(,二进制算术编码 由于,,,,,编码存在以上的局限性，使其难以实际运用。而二进制算术编码在它的基础上，做了进一步改进，解决了无限精度问题，并引入了区间更新无乘法变化形式、条件交换机制和自适应概率估计模型，达到了实用要求。,(,(,有限精度实现 在,,,,,编码中，对区间,，？，,)互〔,，,)下界和长度的更新遵循: ,，,,,厶(,) (,,,) 巳，,,巳，,最(毛) (,,,) 而为了实现有限精度的要求，算术编码放弃了上面理想的更新关系。假定: ,,,，,?,(疋(,) (,—,) 则与以的每一个可能输出相对应的子区间保持不连续，因此唯一解码可以得到保证。 设区间长度由,位整数,以及指数玩共同表示: ,,,一“(,刈,) (,(,) 量彳?。,,,?,是,位二进制小数，其形式为:彳?。,,(逛,，量吃是,的二 (?位进制小数前导,的个数，即 吒,,,唑,蛐 吒位 ， (,,,) 用,位整数乞近似表示所有概率，使得 厶(,)?,,?。,,一尸见，,?, (,(,) 区间长度由(,,,)式更新。具体处理算法如下: 丁卜,心，以，,卜吃 ‖，?,,一„?，一，是(?，尸)位二进制小数，厂?,彳,,?，,, ,,,, ,,,„?，尸一, ,,,?,三 , 第二章算术编码原理 , 钆，,卜吃，, (“避量 丁卜,, 轴谒髓 ,，，。,,,廿丁,, 对于区间下界巳，由于输出概率函数厶(,)是用,位二进制小数,?。近似表示，所以累计分布也用尸位二进制小数 .