(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf_第1页
(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf_第2页
(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf_第3页
(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf_第4页
(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf_第5页
已阅读5页,还剩52页未读, 继续免费阅读

(通信与信息系统专业论文)基于时域处理的时间序列压缩算法研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 高压缩比和高信噪比的数据压缩技术一直是人们在数据处理领域追求的目标 之一。经典的统计编码方法,如霍夫曼编码和算术编码,理论上可以应用于绝大 部分类型数据,但不能保证对任何类型的数据都能达到较高的压缩比。至今,人 们仍一直在努力寻找能应对各种数据分布特性的数据压缩算法。 本论文介绍了一种新型的数据压缩算法,这种算法能应用于多数时域数据序 列的压缩。在本算法中,首先使用a d p c m 数据压缩算法对输入的原始数据序列进 行处理,并得到由a d p c m 编解码产生的残差数据。接着对残差数据进行编码,编 码方法是基于l l o y d m a ) 【算法的最优化标量量化方法。由于对原始数据序列编码和 残差数据编码得到的码字都具有非均衡的概率分布,可以对a d p c m 码字和 l l o y d m a x 编码码字再进行熵编码,如霍夫曼编码,这样可以得到更高的压缩效果。 同时设计出一些特殊的处理方法,用以减小大幅度的残差数据。针对1 6 b i t 样点的 原始时域采样序列,本算法支持三种编码比特率:9 0 0 b 样点,8 o o b i t 样点和 7 2 5 b i t 样点。 测试和评估表明,针对不同数据分布类型的时域数据序列,在压缩比和信噪 比方面,本文设计的压缩算法都具有较高的性能;同时较低的计算复杂度也足以 满足硬件实现的需要。所以本算法具有很广的应用前景。另外本算法可以很容易 地扩展成无损压缩算法。 关键词:数据压缩信源编码时间序列压缩比信噪比 a bs t r a c t 1 1 1 ed a t ac o m p r e s s i o nt e c l l l l 0 1 0 9 yw i t l lh i 曲c o m p r e s s i o nr a t i o 锄dl l i 曲s n ri s o n eo ft a r g e t si n ( 1a :t ap r o c e s s i n g n l ec l a s s i c a l 删s t i cc o d i n gm e t h o d s ,s u c ha s h u f j 陆a nc o d i n g 锄d 从t l l i l l e t i cc o d i n g ,c a i lb e 印p l i e dt om o s tt ) r p e so fd a t a t l l e o r e t i c a l l y ,b u tt h el l i g h e rc o m p r e s s i o nr a t i oc 锄n o tb eg u a j l t e e df o ra i l yl 【i n d so f d a t a s of 缸,m l l c he f 王o nh a sb e e nm a d ef o rt h ed a t ac o m p r e s s i o nm e t h o d st od e a l 、n t l l d a t as o u r c e sm a th a v ev 撕o u sp r o b a b i l i t ) rd i s t r i b u t i o n s an e wd a _ t ac o m p r e s s i o na l g o r i t l l i i lw k c hc a l lb ew i d e l yu s e di nc o m p r e s s i o no f g e n e r a lt i m ed o m a i ns e q u e n c e si s 确舭e di i l 也et h e s i s i i l “sa l g o r i t h m ,n l e a d p c md a t ac o m p r e s s i o na l g o r i t l l i l li sf i r s tu t i l i z e dt oc o m p r e s st 1 1 ei n p u to r i g i n a l s e q u e n c e ,m e nt h er e s i d u a lp r o d u c e db ya d p c mc o d i n go ft h eo r i g i n a ls e q u e n c ei s e n c o d e db ym eo p t i i i l i z e ds c a l a rq u a n t i z a t i o nm 越n gu s eo ft h el l o y d - m a xa l g o 硎:l i l l s i n c et h ep f o b a b i l i t ) rd i s t r i b u t i o n so ft h ec o d e sr e s u l t i n gf b mt h eo r i g i n a ls e q u e n c e c o d i n ga i l di t sr e s i d u a lc o d i n ga r en o tu i l i f - o m ,t h ee n t r o p yc o d i n g ,s u c ha sh u f r m a n c o d i n g ,i sa p p l i e dt ot h ec o d e so fa d p c m a n dl l o y d m a xe n c o d i n g ,s 0a st og e tm o r e c o m p r e s s i o n 1 1 1o r d e rt or e d u c et l l eb i gv a l u e so c c u r i nt h er e s i d u a l ,s p e c i a lt 陀粕e n t m e t h o d sa r ed e s i g n e da n di m p l e m e n t e d f o rt h eo r i g i n a lt i m ed o m a i ns e q u e n c e s s a m p l e dw i t ha c c u r a c yo f1 6b i t s s 锄p l e ,恤e ec o d i n gb i tr a t e s ,i e 9 0 0b i t s s a m p l e , 8 0 0b i t s s a i i l p l ea n d7 2 5b i t s s 锄p l e ,a r ed e s i g n e da n ds u p p o r t e di nt h ea l g o r i t l m l t e s ta i l de v a l u a t i o nh a v es h o w nm a tt :h ep e 面n n a i l c e so fd e s i g n e da l g o r i t h m , i n c l u d i n gc o m p r e s s i o nr a t i oa i l ds n r ,a r eg o o df o rt h et i m ed o m a i ns e q u e n c e s t h a th a v e d i 虢r e n tp r o b a b i l i t ) ,d i s t r i b u t i o n ,a 1 1 dt h ec a l c u l a t i o nc o m p l e x 时o fm ea j g o r i t l l mi s l o w e re n o u g hf o rh a r d w a r ei m p l e m e n t a t i o n ,t h e r e f o r et h ea l g o r i t l l i i lc a nb eg e n e r a l l y u s e di nm a n y 印p l i c a t i o n s f u n h e m o r e ,t h i sa l g 嘶t 胁c a nb ee a s i l ya d o p t e df o r l o s s l e s sd a t ac o m p r e s s i o n k e y w o r d :d a t ac o m p r e s s i o n c o m p r e s s i o nr a t i o s o u r c ec o d i n gt i m es e q u e n c e s n r 第一章绪论 第一章绪论 1 1 数据压缩概述 人类社会已经进入信息时代。作为信息,它要求能够交流和传播。因此需要 将信息从一个地方传到另一个地方通信;或者将信息从现在传给将来存 储。不论是通信还是存储,作为信息的载体数据,都要占据一定的时空资源。 随着信息技术的发展,人们交流的频繁,有限的带宽和存储介质逐渐不能满足人 们的需求。如何更有效地利用现有资源来承载更多的信息,这就是数据压缩技术 所要解决的问题。 数据压缩,就是以尽可能少的数码表示信源所发的信号,减少容纳给定消息 集合或数据采样集合的信号空剐1 1 。所谓信号空间,即被压缩的对象,是指:物理 空间,如存储器,磁盘,光盘等存储介质;时间区间,如传输给定消息集合所需 要的时间;电磁频谱区域,如为传输给定消息集合所要求的带宽等。也就是说信 号空间是指某信号集合所占的空域,时域和频域空间。信号空间的这几种形式是 相互关联的:存储空间的减少意味着传输效率的提高和占用带宽的节省。这就是 说,只要采用某种方法来减少某一种信号空间,都能压缩数据。 采用数据压缩的必要性如何,具体地,从传输角度看:一路p a l 制彩色数字 电视,若采用3 倍副载频采样,每像素8 b i t 编码,数码率为i = 4 4 3 3 8 = 1 0 6 3 m b s ;而一路高清晰度电视h d t v ( h i 曲d e f i n i t i o nt e l e v i s i o n ,又称高分辨率电视) , 数码率高达i = 1 2 8 0 7 2 0 6 0 3 8 = 1 3 2 7m b s ,这是一般家用数字网络不能 达到的要求。从存储的角度看:为了记录一段3 分钟的音乐( 每秒采样4 4 1 0 0 次, 每个样点值用1 6 b i t 表示) ,所需要记录的数据量是1 6 4 4 1 0 0 6 0 x3 1 2 7m b i t 。 如果从互联网中以l o o k b i “s 的速度下载这段音乐,则需要2 2 分钟。 由此可见,如果不进行数据压缩,则无论传输和存储都很难实用化,而数据 压缩的好处在于: 1 较快地传输信源信息时间域的压缩; 2 在现有的通信网络上开通更多的并行业务,如传真、电话,电视等频 率域的压缩; 3 降低发射机功率能量域的压缩; 4 减少数据存储容量空间域的压缩。 也正是由于数据压缩技术给信息技术带来的巨大好处,数据压缩技术的发展 几乎与通信技术的发展是同时进行的。 18 4 3 年出现的莫尔斯( m o r s e ) 电报码是最原始的变长码压缩实例。1 9 3 9 年贝尔 2 基于时域处理的时间序列压缩算法研究 实验室( b e l ll a b ) 发明了通道声码器,成为第一个语音压缩系统。1 9 5 2 年霍夫曼( d a h u f r m a n ) 给出了最优变长码的构造方法。1 9 6 0 年马克斯( j m a x ) 发布了确知分布 信号的最佳标量量化方法。 但是对数据压缩的理论性研究还是从香农( c e s h 砌o n ) 开创的信息论的基 础上开始的。1 9 4 8 年香农的论文“通信的数学原理”中首次提到信息率失真函数 【2 】的概念。1 9 5 9 年他又进一步确立了率失真理论的概念,从而奠定了信源编码的 理论基础。 初期的数据压缩技术主要依据信息论理论,以减少数据流中相关数据冗余达 到压缩目的。随着科学技术发展和应用领域要求的不同,数据压缩技术关注的重 点和采用的方法逐渐多样化。 对于语言、音频、图片和视频信号的实用压缩技术研究,更多地得益于数字 信号处理,时间序列分析,参数估计,离散变换,模式识别,自适应技术以及感 知生理心理学的理论进展。由于对人的发生机理、听觉特性以及对语音信号本身 自回归模型研究较早,语音编码比图像编码更成熟,除音质要求较高者仍采用波 形编码外,低码率传输普遍采用了基于分析合成思想的各种编码器。 图像编码直接借鉴了许多语音压缩技术的成熟技术1 9 6 6 年奥尼尔对比分析了 d p c m 和p c m 并提出了用于电视的实验数据;1 9 6 9 年进行了线性预测编码的实 验。1 9 7 5 年以来有人通过测量电视图像中运动物体的位移来进行图像的帧间预测, 结果使码率进一步降低。这一方法不仅用于电视提高了图像质量,也可以用于可 视电话和会议电视。 现代电子技术的发展,使得原来只能以通用计算机仿真的技术方案已能用硬 件实现。1 9 8 0 年以来,国际标准化组织( i s o ) 、国际电工委员会( i e c ) 和国际电信联 盟( i t u ) 下属的国际电报电话咨询委员会( c c i t t ) 陆续完成了各种数据压缩与通信 的标准和建议。例如:在二值图像,传真机方面,有c c i t tt 4 【3 1 ,t 8 2 1 4 】及i s o 1 1 5 4 4 ( j b i g ) 【5 1 标准;在语音编码方面,有c c i t tg 7 2 6 【6 1 、g 7 2 8 【7 1 和g 7 2 9 嘲等; 在运动图像方面,有c c i t th 2 6 4 【9 j 及i s om p e g 4 【1 0 】标准等。 这些标准的建立为信源编码在各领域的发展提供了规范和参考。但这些标准 多集中于某些单一的领域,如语音编码,音频编码,图像编码和视频编码等。反 映当前对信源编码研究的局限性,即编解码方法在处理研究领域内的信号时能达 到较高的性能,但对于其它类型信号难以达到可接受的处理结果。本文针对这一 问题进行探讨和研究,进而提出一种解决方案,并对方案原理和性能进行介绍。 1 2 研究内容和主要成果 本文针对一般数据信源压缩编码的实际需求,设计了一种基于时域处理的数 第一章绪论 3 据压缩算法。期间进行的研究工作有: 查阅当前主要数据压缩算法的说明文献,研究各种数据压缩算法的基本原理。 其中包括无损压缩方法,如经典的统计编码方法;以及应用于有损压缩的预测编 码,变换编码等。在此基础上,为了有效地利用时域数据间的相关性,减少数据 冗余,选择预测编码作为算法研究基础。因此,重点分析1 1 u 的g 7 2 1 标准,提取 其中a d p c m ( a d a p t i v ed i 脏r e n t i a lp u l s ec o d em o d u l a t i o n ,自适应脉码调制) 算法 作为数据压缩处理的第一部分。为了提高算法精度,对a d p c m 处理后得到的残 差数据进行分析。由于残差数据多呈现近似高斯分布,且幅度较小,意味着多数 残差集中于较小的范围内,可以使用较少的比特资源对残差修正。同时,为了进 一步提高解码恢复数据的精度,将幅度较大的残差和幅度较小的残差分开处理。 残差处理方法采用标量量化,为了使量化失真最小,在量化表的生成上使用了 l l o y d m a x 算法。通过观察a d p c m 编码码字的分布,发现其码字分布极为不均 衡,因此在算法的后半部分引入熵编码环节对a d p c m 码字进行编码,进一步提 高了压缩比。由于残差量化码字分布较为无序,对其熵编码后压缩效果不明显, 因此残差量化码字的熵编码是根据编码效果选择性进行。最后,基于以上研究方 案,编程实现了压缩比为2 2 1 ,2 o o 和1 7 8 的编解码程序。 经测试表明,本课题研究算法在固定压缩比的条件下能达到较高的数据恢复 能力,保证即使对于数据相关性很弱的信号,也能在压缩比为2 的情况下使信噪比 保持在4 0 d b 附近。 1 3 论文结构安排 本文一共分为五章,具体安排如下: 第一章介绍数据压缩的定义和意义,概述数据压缩技术的发展状况,最后简述 了本论文研究的内容。 第二章介绍了当前数据压缩技术主要采用的编码方法,分析它们的特点和适用 范围,最后提出本研究课题所参考的编码方法。 第三章重点介绍了本课题研究的数据压缩算法的原理。章节分为编码和解码两 部分,其中对编码算法的原理和过程进行较为详细的介绍,解码部分主要是对编 码部分的逆过程。 第四章是对本课题研究的数据压缩算法性能的评估。首先介绍对数据压缩算法 进行性能评价的技术指标,接着给出本文介绍的数据压缩算法的性能测试结果, 同时将部分性能结果与当前存在的数据压缩算法性能结果进行比较。 第五章是对论文工作的总结,指出存在的问题并给出计划的解决方案。 4 基于时域处理的时间序列压缩算法研究 第二章数据压缩技术概述 5 第二章数据压缩技术概述 数据压缩技术发展至今,在不同数据处理领域采用的方法不尽相同。但在多 数情况下对数据信息进行的压缩技术都是依靠编解码的方式实现的。编解码的过 程可以抽象成如图2 1 所示的编码器和解码器的工作过程。 x = a = a 1 ,a m ) a 2 a l ,a i i l 图2 1 编解码器描述框图 ”,x m ) 其中编码器输入端输入信息的集合x 是由若干信号单元x i ( i _ 1 n ) 构成的, 输出集合c 称为码字( c o d e ) ,由码字单元c i ( i = l 1 1 ) 构成。a 是构成码字的符号集, 其元素a 称为码元或者符号( 如在二进制表示的码字中,符号集a 就包含两个码 元:o 和1 ) 。解码端输出恢复信息集合,由恢复信号单元x r i ( i _ 1 n ) 构成。 编解码的过程是:当编码器接收到一个信元x i 时,根据一定的对应规则f ( x ) ( 这种对应规则必须可逆) ,在符号集a 中找出若干对应的码元,并将找出的码元 排列成码字c i ,接着输出码字c i ,由码字序列c l ,c 2 ,c l l 构成编码比特流送入 解码器。当解码器接收到编码比特流后,根据对应规则f ( x ) 的逆过程以及符号集a 中的码元,分离出码字c i ,接着恢复出恢复信号的信元x r i ,组成恢复信号集合x r 。 现在数据压缩编码中使用的编码规则有很多,依据基于的原理不同可分为: 统计编码、预测编码,变换编码和分析综合编码。下面逐一进行简要介绍。 2 1 统计编码 对照图2 1 ,统计编码,是基于对需要进行编码的信元进行概率统计结果进行 的编码方法。其主要思想是依据信元在信息集合中出现的几率来分配码字。一般 地,对于出现次数较多的信元用较短的码字表示,对于出现次数较少的信元用较 长的码字表示。因此统计编码是一种变长编码。统计编码在构造码本时,希望能 先知道各信元出现的几率,进而给定码字的相对长度。作为变长编码,其译码的 过程比固定码长码字的译码要复杂:对于固定码长码字译码,只要正确识别出一 个码字就能译出后续的码字,而变长码字译码由于码字的长度不同,要正确识别 6 基于时域处理的时间序列压缩算法研究 出码字的起点,必须解决唯一可译性问题。 构造唯一可译的变长码首先要确定每个码字的长度,接着找出可用的码字。 信息论中变长编码定理解决了长度问题: 【定理2 1 】 变长编码定理】【1 1 】对于符号熵为h ( ) ( ) 的离散无记忆信源进行m 进制的不等长编码,一定存在一种无失真编码方法,其码字平均长度l 满足 器+ 1 ,器 ( 2 - 1 ) l o g ml o g m 、7 其中符号熵h ( x ) 定义为 日( x ) = 一p ( 薯) l o g p ( 薯) ( 2 - 2 ) p ( 鼍) 表示第i 个信元在输入信息集合中出现的概率。 码字平均码长定义为 ,= p ( t ) 厶 ( 2 3 ) 厶表示用以表示第i 个信元x i 的码字长度。 对于m 进制的不等长编码的编码速率定义为 r = ,l o g m( 2 _ 4 ) 则定理2 1 可改述为: 若日( x ) 天 日( x ) + l o g m ,就存在唯一可译的变长码:若r h ( x ) ,则不 存在唯一可译的变长码。 对于二进制编码,码字平均长度l = r 。只要对每个信元分配码字的长度后使 得平均码长符合定理2 1 即可确定按这种码字长度分配方法可分配出唯一可译码。 已知码字长度,如何确定码字构成。现在一般采用结合码树来生成异字头码的 方法。若码元有m 个,生成步骤是: ( 1 ) 从根结点开始生出m 枝; ( 2 ) 每一枝用一个码元表示; ( 3 ) 根据确定的码字长度在合适的节点上继续生枝,继续生枝的节点叫中间节 点,不再生枝的节点叫端节点; ( 4 ) 根据端节点到根结点的长度分配信元; ( 5 ) 从端节点到根结点沿途遇到的码元连成的符号就是位于该端节点的信元对 应的码字。 如m = 2 ,码元只有0 ,l 两种形式。若现在有三种信元符号a ,b ,c ,d ,出 第二章数据压缩技术概述 7 现的概率是p ( a ) = 1 2 ,p ( b ) = l 4 ,p ( c ) = 1 8 ,p ( d ) = 1 8 ,则符号熵为 何( x ) = ( 1 2 ) l 0 9 2 + ( 1 4 ) 1 0 9 ( 4 ) + 2 ( 1 8 ) l o g ( 8 ) = 1 7 5 ( 2 - 5 ) 设分配给a ,b ,c ,d 的码字长度分别是l a = l ,l b = 2 ,l c = 3 ,l d = 3 ,平 均码长是 ,= ( 1 2 ) l + ( 1 4 ) 2 + 2 ( 1 8 ) 3 = 1 7 5 ( 2 6 ) 码长符合要求,构造码树如图2 2 所示 根 1 1 01 1l 图2 2 码树构造图 由码树可知,信元a 的码字是0 ,信元b 的码字是l o ,信元c 的码字是1 1 0 , 信元d 的码字是ll1 。 基于信元统计特性构造变长码的方法还有很多,如h u m n a i l 编码【1 2 1 ,算术编 码【1 3 】等。 2 2 预测编码 预测编码是数据压缩技术的一个重要分支,其理论基础主要基于现代统计学 和控制论【l j 。预测编码基于的模型一般是符合某些条件的滤波器,根据数字信号处 理中的滤波理论设置滤波器参量,使滤波器的输出符合要求。预测编码的一般过 程是根据离散信号之间存在着一定关联性的特点,利用前面一个或多个信号预测 下一个信号,然后对实际值和预测值的差( 预测误差) 进行编码。如果预测比较 准确,误差就会很小。这样在同等精度要求的条件下,就可以用比较少的比特进 行编码,达到压缩的目的。 预测编码中典型的压缩方法有p c m ( p u l s ec o d em o d u l a t i o n ,脉冲编码调制) , d p c m ( d i 虢r e n t i a lp u l s ec o d em o d u l a t i o n ,差分脉冲编码调制) 和a d p c m ( a d a p t i v e d i 髓r e n t i a lp u l s ec o d em o d u l a t i o n ,自适应差分脉冲编码调制) 等,它们较适合于音 频、图像数据的压缩,因为这些数据由采样得到,相邻样值间的差值不会很大, 8 基于时域处理的时间序列压缩算法研究 可以用较少比特来表示。 这里简要介绍d p c m 工作过程。 + 图2 3d p c m 发送端框图 如图2 3 所示,d p c m 系统工作时,发送端先发送起始值x o ,接着在自身内部 一方面对原始信号数据进行预测得到预测值x e i 【,一方面发送量化后的预测误差e l 【 鲰= & 一x 气 ( 2 7 ) = g 扰口,? ( 弓& ) ( 2 - 8 ) 而预测值x e l ( 是由k 时刻前若干预测恢复值经过某种规则处理得到的,即 x 气= 厂( x 勺,x 巳+ l ,x q ) ( o , j j ) ( 2 - 9 ) 如图2 4 所示,接收端把接收到的量化后的预测误差e l 【与本地算出的预测值 x e l ( 相加,即得恢复信号x c k 。 图2 4 d p c m 接收端框图 如果不考虑数据传输错误,则恢复信号x c k 和原始信号x k 的误差为 e c k2 x k x c k = 五一( 碱+ ) = ( 磁一x 龟) 一气 第二章数据压缩技术概述 9 = 吼 ( 2 。l o ) 这表明整个d p c m 系统的误差是由发送端的预测误差量化器造成,如果去掉 量化器,使用某种方法直接发送预测误差e p l 【,则可以实现无损压缩。 d p c m 的优点是算法简单,容易硬件实现,缺点是对信道噪声很敏感,会产 生误差扩散。即采用它的编码方法如果传输码字时码字出错,对一维预测来说, 将使以后的各个恢复值都因此产生更大误差;而对二维预测,该码引起的误差还 将扩散到以下的各行。同时,d p c m 的压缩率也比较低。随着变换编码的广泛应 用,d p c m 的作用已很有限。 一 2 3 变换编码 变换编码不是直接对时域或空域信号进行编码,而是首先将时域或空域信号 映射变换到另一个正交矢量空间( 变换域或频域) ,产生一批变换系数,然后对 这些变换系数进行编码处理。在接收端先将码字解码,接着对解码出的变换系数 进行逆变换,获得恢复后的信号【1 4 】。变换编码主要由映射变换、量化及编码几部 分操作组成,其模型框图如图2 5 所示。 图2 5 变换编码模型框图 利用变换进行数据压缩的关键在于,对原始信号进行映射后产生变换系数, 对这些系数进行编码所需要的比特数比对原始信号进行编码所需要的比特数少, 达到数据压缩的目的。一般讲,原始信号变化越缓慢,数据间相关度越高,采用 变换方法压缩的效果越明显,这一点和预测编码相似。对于变换编码的原理说明, 可参考如下例子: 设有两个相邻的数据样本x 和y ,对每个样本都进行3 b i t 编码,则每个样本都 有8 种状态,而由x 和y 进行组合能有8 8 = 6 4 种可能性。如果直接记录x 和y 的组合就需要6 b i t 。现在将二者绘制在二维坐标中,由于x 和y 相邻,相关度较高, 差值小,所可能的位置关系如图2 6 中阴影部分所示 1 0 基于时域处理的时间序列压缩算法研究 图2 6 样点x ,y 分布图 可以看出,对于相关的样点,其相关度越高,在图中描绘出的阴影区越扁平, 相关度越低,样点的分布越分散,阴影区越显得方圆。 现在对x ,y 进行某种变换,反映在图像上相当于将坐标轴逆时针旋转4 5 度, 如图2 7 所示 ol23i z 图2 7 变换后x ,y 分布图 x 移动到x 1 轴处,y 轴移动到y 1 轴处。在新的坐标轴中,x 和y 的分布区, 8 7 6 5 4 3 2 l 0 h 第二章数据压缩技术概述 阴影部分在坐标轴上的投影部分发生了变化。阴影部分在x 1 轴上的投影远比在y l 轴上的投影长,这说明任凭x 1 轴上数据变化,y 1 轴上的数据变化范围很小,x l 和y 1 的相关性变低。数据的分布范围没有变化,意味着它们的方差仃2 没有变化, 即 + 盯;= 吒+ 略 ( 2 1 1 ) 但明显仃三仃三,信号的能量被集中到了x 1 轴的方向上,说明在经过变换 后,只要适当保留x 1 轴上的数据信息,减少y 1 轴上的数据信息,同样能保证保 留足够多的原始信号的信息。 一一一 所以,变化编码的基本思想是:经过多维坐标系中适当的旋转和变换,把原 来散布在坐标中各处的数据,集中到新坐标系中的少数坐标轴上,这样就可能使 用较少的编码位数表征原始信号,达到数据压缩的目的。 2 4 分析综合编码 这一类编码方法综合性很强,往往是多学科领域思想交叉研究的结果。总体 上没有固定算法方法,但从研究的过程看,一般是先根据需要将信源分解成一个 个更适合表达的“基础单元”,这种“基础单元”既可以是原始信源在时域或空 域的表达,也可以是经某种变换后得到的参数,接着只编码这些“基础单元”。 在解码端根据一定的规则构造出模型,按照与编码端对应的算法,依据接收到的 “基础单元 近似恢复信源信号。从现在看到的这类编码方法看,它们实现的都 是有损压缩,但如果这种对信源特征的提取是合理的,而在实际要求的情况下对 信源信号的重建又是成功的,那么这种合理的失真也是有意义的。 现在的分析综合编码主要有子带编码,小波编码i l5 j 和分形编码【l6 j 等。这里对 较为新颖的分形图像编码进行概述。 自然界中有许多不同的形状和结构,但仔细观察会发现这些形状和结构中会 有很多相似性,如雪花,蕨类植物的枝叶( 见图2 8 ) 等。分形编码就是基于这种 自相似性,即,无论几何尺度如何变化,景物任何一小部分的形状都与较大部分 形状相似。从图像压缩角度出发,就是要恰当地,最大限度地利用这种自相关性。 一些学者从方法论的角度出发,将分形视作一个过程,观察事物时从整体向 局部转化。以数字化图像为例,把原始图像分割成若干子图例1 7 j ,然后在为子图 像准备的分形库中寻找相似的子图。库中存放的是相对紧凑的称为迭代函数系统 ( 1 t e r a t e df u i l c t i o ns y s t e m ,i f s ) 代码的数字集合,这些代码将用于重现相近的分形 图。库的编目系统将看起来相似的图像存放得也较近,相邻的代码对应于相近的 分形图,这样,在库内自动搜索时能找到与给定目标图像最相近的分形图。现在 拼贴定理( c o l l a g en l e o r e l n ) 1 8 j 可以保证总能找到适宜的i f s 代码,并指出了寻找方 1 2 基于时域处理的时间序列压缩算法研究 法,这里就不做详细介绍了。 图2 8 雪花和蕨类植物枝叶图形 分形编码是有失真的,其失真度与压缩比紧密相关。对于一定的整体与局部 存在明显相似性的分形图像类,从图像整体上看,可以获得很高的压缩比。但如 果图像中不同部分间存在差异,压缩比就会较少很多。例如这种方法对于描述一 棵树的整体图像是相当出色的,但如果要求给出不同分支上树叶的精确排列次序 时,就需要相当大的存储量。因此,难以期望在保证很低的失真度条件下,对于 一切图像,分形图像编码都具有普遍适用的极高压缩比。 以上介绍的编码方法是对当前数据压缩方法的简要介绍,由于科技的不断发 展,数据压缩技术不断革新,不断有新的编码方法出现。特别是学科交叉,新思 想的引入,在不同领域使用的数据压缩算法基本都能达到较高的压缩性能。但这 种日趋的特殊化也使问题凸显:数据压缩算法的适用范围越来越小。即使能达到 很高的压缩比,但往往会引入较大的失真。为了尝试解决这个问题,本文在第三 章提出了一种基于时域处理的数据压缩算法,虽然达到的压缩比有限( 程序实现 的算法压缩比在1 8 到2 5 之间) ,但算法具有很强的普遍适用性,即使对近似于 白噪声的信号也能达到较高的信噪比( 一般保持在3 5 d b 以上) 。 第三章数据压缩算法设计 1 3 第三章数据压缩算法设计 研究过程中所针对的数据源多是数据间相关度低,数据动态幅度分布广的近 似噪声信号。原因是这类信号数据特性较难觉察,压缩难度大,根据这类信号设 计的压缩算法具有很强的数据适应性。同时,为了利用信源信号数据可能存在的 数据相关性,在设计上重点考虑2 2 节讲述的预测编码。 本章对研究的基于时域处理的数据压缩算法的原理进行介绍。章节分为编码 器和解码器两部分,在每部分中会按照功能的不同划分出若干模块,接着对模块 进行说明。在进行具体介绍前,先对部分名词进行说明: 1 自适应差分脉码调制( a d p c m ,a d a p t i v ed i 仃e r e n t i a lp u l s ec o d em o d u l a t i o n ) :一 种根据输入信号幅度大小来改变量化阶大小的波形编码技术,能根据输入信号 幅度的变化改变量化阶,使编码器估计单元得到的估计值尽可能接近数据真 值。 2 固定速率编码( c b r ,c o n s t a n tb i tr a t e ) :编码速率恒定,即任意时刻瞬时编码 速率与平均速率始终相同;换言之,在给定编码速率的前提下,每个编码帧 所用的比特数相同。 3 变比特率或变速率( v b r ,v 撕a b l eb i tr a t e ) :编码速率非恒定,即任意时刻瞬 时编码速率与长时平均速率未必相同;换言之,在此种编码模式下,每个编 码帧所用的比特数是由音频信号帧的特性决定的,因此每帧所用的比特数不一 定相同。 4 l 1 0 v d m a ) 【量化【2 0 】:一种标量量化方法,以一种根据量化数据范围变化而不 断均分量化区间的算法确定失真度最小的量化区间和量化电平。 5 h u 胁a i l 编码:一种无失真的不等长压缩编码方法,是一种常用的无损编码。 3 1 编码器算法原理 图3 1 给出了编码器的原理框图。原始数据s 输入到数据压缩编码模块进行数 据压缩和编码,并将得到的数据压缩编码码字s c 送给数据解码解压模块和数据熵 编码模块;数据解码解压模块根据得到的数据压缩编码码字s c 进行本地解码和解 压缩,得到原始数据s 的估值即解压数据s ;原始数据s 与解压数据s 相减得到 误差r 1 ;然后,误差压缩编码模块对误差r l 进行压缩和编码得到误差压缩编码码 字r l c ;数据熵编码模块和误差熵编码模块分别对数据压缩编码码字s c 和误差压 缩编码码字r l c 进行熵编码处理,分别得到数据熵编码码字s e 和误差熵编码码字 r l e ;最后,帧封装模块将数据熵编码码字s e 和误差压缩编码码字r l e 组合,再加 1 4 基于时域处理的时间序列压缩算法研究 上帧头信息h i ,得到完整的编码帧输出,形成编码比特流b l 。在实际实现的过程 中,对原始数据是分帧进行处理的,帧长取6 4 个样点。即每次取“个样点进入 编码器,编码得到比特流后再输入后面6 4 个样点。下面对图3 1 中出现的各个模 块进行说明。 帧头信息 3 1 1 数据压缩编码模块 图3 1 编码器原理框图 本算法基于时域处理方式,为了充分利用信号内部数据之间的相关性,在这 里引入预测编码的方式。采用的方法是在d p c m 基础上经过改进的a d p c m 编码 方法。a d p c m 是一种根据输入信号幅度大小来改变量化阶大小的波形编码技术, 它能根据输入信号幅度的变化改变量化阶,使编码器估计单元得到的估计值尽可 能接近数据真值。这种自适应的基本思想是让量化阶距与输入方差相对地保持恒 定,改善量化效果。对于输入方差的估值,根据采用方法的不同,可以分为两类: 一类是输入幅度或方差由输入本身估算,这种方案称为前馈自适应量化器( a q f ) ; 另一类是其阶距根据量化器输出来进行自适应调整,或等效地用输出码字进行自 适应调整,这类自适应量化方案称为反馈自适应量化器( a q b ) 。 在这里,数据压缩编码模块采用基于g 7 2 1 标准的a d p c m 算法,对输入方差 的估值采用反馈的方法,使用的自适应量化器是一个1 5 阶非均匀自适应量化器, 输出4 位二进制码i ( k ) ,其中一位表示符号,三位表示幅度。为了便于进行自适 应运算,引入了定标因子y ( k ) 。为了避免进行除法运算,转换成以2 为底的对数, 计算在对数域上进行。 下面对算法的细节进行介绍,同时可参照i t u 对g 7 2 1 标准的修订标准g 7 2 6 的说明文档。 图3 2 给出了a d p c m 的原理框图。原始信号s ( k ) 进入编码模块后先与预测信 第三章数据压缩算法设计 1 5 号s c ( k ) 做差得到差值信号d ( k ) ,d ( k ) 经过自适应量化器得到量化码字i ,i 作为 a d p c m 量化码字输出。同时,码字i 经自适应逆量化器得到恢复的差值信号d 。( k ) , 将恢复的差值信号d q ( k ) 送入自适应预测器,获得对下一原始数据的预测值s c ( k ) , 接着将预测值s c ( k ) 和d q ( k ) 相加得到重建信号s r ( k ) 。其中码字i 和恢复的差值信号 还会被用于进行自适应量化阶调节。对照图3 2 ,下面按照编码流程对a d p c m 算 法部分重点模块进行介绍。 原始信号 s a d p c m 差值信号 输出i ( k ) d 广 甚善藿h 皇茬鬈信号值il 量化器 定标因子 y ( k ) 自适应逆 量化器 恢复差值 d q ( k ) 自适应预 测器 平鬻子卜? 速度 因子 t ( k ) 图3 2a d p c m 编码原理框图 重建信号 s r ( k ) 中紧数 单频与瞬 变音检测 ( 1 ) 自适应量化器 如图3 2 所示,由原始信号s ( k ) 和预测信号s c ( k ) 做差得到差值信号d ( k ) 进入 自适应量化器。在量化器中还引入了定标因子y ( k ) ,它是一个会根据d ( k ) 波动而变 化的量。如果d ( k 1 ) 幅值较大,说明在k 1 时刻原始数据和预测数据差别较大,原 始信号可能发生波动,由于在这里采用后向自适应( 自适应由先前状态调整) , 这样使在k 时刻处理的定标因子y ( k ) 增大,接着将差值信号d ( k ) 和定标因子y ( k ) 相除,这样使得d ( k ) 和y ( k ) 的商保持在相对稳定的范围内。为了计算方便,实际 y ( k ) 是以以2 为底的对数形式表达,对d ( k ) 计算前也进行对数运算,这样除法运算转 化为减法运算。 经自适应量化器就可以获得a d p c m 码字输出,根据减法运算结果所在的范 围,分配码字,具体可见表3 1 。其中i ( k ) 代表码字,归一化量化器输入范围表示 编码器的量化范围,归一化量化器输出范围表示自适应逆量化时根据码字i ( k ) 恢复 的差值。当归一化输入值落入某一区间后,就输出对应的量化码字i i ( k ) i ,在这里i i ( k ) l 的范围是o 7 ,占用3 b i t ,结合l 0 9 2l d ( 七) 卜y ( 尼) 的差值的符号信息l b i t ,共4 b i t 1 6 基于时域处理的时间序列压缩算法研究 构成自适应量化码字。解码时先根据i i ( k ) i 在归一化量化器输出范围中确定幅值,再 根据符号信息确定差值的正负。 表3 1 自适应量化器量化表 归一化量化器输入范围 l j ( 七) l 归一化量化器输出范围 l o g :i d ( 七) l - y ( 尼)l o g :l 畋( 七) l _ y ( 七) 【3 1 2 ,+ 叫 73 3 2 【2 7 2 ,3 1 2 ) 62 9 l 【2 3 4 ,2 7 2 ) 52 5 2 【1 9 1 ,2 3 4 ) 42 1 3 【1 3 8 ,1 9 1 ) 31 6 6 【o 6 2 ,1 3 8 ) 21 0 5 【- 0 9 8 ,o 6 2 ) 1o 0 3 ( - ,- o 9 8 ) 0 - 0 0 ( 2 ) 自适应逆量化器 根据码字i ( k ) 和定标因子y ( k ) 恢复差值d ( k ) 的近似值d q ( k ) 。进行的是自适应量 化器的逆过程。 ( 3 ) 量化阶距自适应 这个模块计算定标因子y ( k ) ,所基于的原理是两种模式适应: 快变信号适应,主要针对出现较大波动的信号; 缓变信号适应,主要针对波动较小的信号。 定标因子y ( k ) 由两种适应方式综合确定。 对于快变信号适应的作用,可由快变因子y u ( k ) 反映。 咒( | j ) = ( 1 2 - 5 ) y ( 七) + 2 - 5 ,( 七) ( 3 一1 ) 对y u ( k ) 的幅度限制在1 0 6 虬( 后) 1 0 o o 。 w i ( k ) 】是和当前输出码字有关的函数,根据码字取不同的值,具体定义如表 3 2 所示 表3 2w 【i i ( k ) i 】取值表 | i ( k ) i 7 654 3 2lo w 【i i ( k ) | 】 7 0 1 32 2 1 91 2 3 87 0 04 0 02 5 61 1 30 7 5 缓变信号适应是由缓变因子y l ( k ) 表征,具体计算如式( 3 2 ) 第三章数据压缩算法设计 1 7 乃( 七) = ( 1 2 - 6 ) 乃( 尼一1 ) + 2 6 儿( 七) 接着,定标因子由快变和缓变因子构成 j ,( 后) = q ( 七) 儿( 七一1 ) + 1 一口,( 七) 乃( 七一1 ) 其中o q ( 七) 1 ,具体来由在速度控制自适应部分介绍。 ( 4 ) 速度控制自适应 在这个环节首先根据输出的码字i 计算两个平均度量值 一一西咒s ( 尼) = ( 1 2 _ 5 ) 批( 七一1 ) + 2 _ 5 ,【,( 后) 】 和 西竹,( 后) = ( 1 2 - 7 ) 西竹,( 七一1 ) + 2 - 7 ,【,( 七) 】 f i ( k ) 】也是根据输出码字进行取值的函数,具体关系如表3 3 所示 表3 3f i ( k ) 】取值表 ( 3 - 2 ) ( 3 - 3 ) ( 3 - 4 ) ( 3 - 5 ) l i ( k ) i 765432lo f 【i ( k ) 】 731110o0 d m s ( k ) 是和f i ( k ) 有关的短期平均值,d m l ( k ) 是和f i ( k ) 】有关的长期平均值。 根据这两个平均度量值,可定义变量印( k ) 印( 七) = ( 1 2

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论