（通信与信息系统专业论文）数字图像监控系统解码芯片的设计及其fpga实现.pdf

中文摘要 随着多媒体通信技术的发展，人们不再满足单一文字或声音的传递，从普通 电话到视频电话，从s m s ( s h o r t m e s s a g i n gs e r v i c e ) 到e m s ( e 1 u h a n c e d m e s s a g e s e r v i c e ) 再到m m s ( m u l t i m e d i am e s s a g i n gs e r v i c e ) ，多媒体技术逐渐进入了千 家万户，而如何高效的处理多媒体信源让其更方便有效的存储和传输就成为了当 前的研究热点。 本文就多媒体信息的主体之一一图像信号的压缩和解压进行了分析，并结 合实际课题所设计的数字图像监控系统对其中的图像解码过程进行了软硬件的 实现。首先我们在a n a l o g d e v i c e 公司的a d s p 2 1 8 9 上进行了解码系统的验 证，就解码输出的质量进行了主观评价。通过软件仿真，我们还进一步得到了解 码过程中，哪些指令占用较多的指令执行时间，哪些指令会成为硬件实现时的瓶 颈。它为我们的f p g a 优化设计提供了理论上的依据。综合考虑设计方案的复杂 程度、系统规模、系统时延、器件成本等各项因素，通过对各种f p g a 器件性能 与开发工具的选择比较，决定选用a l t e r a 公司的f l e x i o k 器件来做最终的硬件 实现。它不仅为图像解码系统的a s i c 实现做了一定的理论分析和技术准备，也 为f p g a 技术在数字信号处理领域的应用开辟了新的研究方向。 在硬件设计过程中，根据f p g a 技术的优点，采用“自上而下”和“自下而 上”相结合的设计方法，将整个系统进行功能模块分割并分别实现。所有处理模 块均采用v e r i l i g 语言编写，对其中的主要模块都进行了优化设计。通过这些 优化不仅提高了解压性能，还减少了处理时间和所占用的硬件空间。最后通过仿 真表明了所实现的图像解码系统具有良好的性能，具有一定的使用价值。 关键词：图像编解码熵编码h u f f m a n 编码量化 现场可编程逻辑器件数字信号处理 a b s t r a c t w i t ht h ed e v e l o p i n go ft h em u l t i m e d i at e c h n o l o g y , p e o p l ew i l ln o ts a t i s f i e dw i t l l t h eb o r e dv o i c ea n dt e x to n l yt r a n s m i s s i o n f r o mt h et e l e p h o n et ov i d e op h o n e ，f r o m t h es m s ( s h o r t m e s s a g i n gs e r v i c e ) t oe m s ( e n h a n c e dm e s s a g es e r v i c e ) t om m s ( m u l t i m e d i a m e s s a g i n g s e r v i c e ) ，m u l t i m e d i at e c h n o l o g yc l o s et ot h ep e o p l e h o w e v e r ，h o wt om a k et h es o u r c eo ft h em u l t i m e d i ai n f o r m a t i o nm o r ee f f i c i e n ta n d c o n v e n i e n tt of a c i l i t a t et h es t o r a g ea n dt r a n s m i s s i o na t t r a c t se v e r y o n e e y e s i nt h i sp a p e rw e a n a l y z eh o w t oc o m p r e s sa n dd e c o m p r e s so n eo ft h em a i nb o d y i nm u l t i m e d i a i n f o r m a t i o n i m a g es i g n a l i nc o m b i n e w i t ho n e p r a c t i c a lp r o j e c t ，w h i c h i sa b o u tt h ed i g i t a ls i g n a lm o n i t o r i n gs y s t e m ，w er e a l i z et h ei m a g ed e c o m p r e s s i o np a r t i nb o t hs o f t w a r ea n dh a r d w a r e w es t a r t e df r o mt h ea d s p 2 1 8 9t o t e s to u r d e c o m p r e s s i o ns y s t e ma n dm a d eaj u d g m e n tp e r s o n a l l y t h r o u g ht h i sp r o c e s sw e f o u n dw h i c hi n s t r u c t i o n st a k et h em o s to ft h ep r o c e s s i n gt i m ea n dw h i c ho n e sw i l l b e c o m et h eb o t t l e n e c kw h e n i m p l i e d i nh a r d w a r e i tp r o v i d e sat h e o r e t i c a ls u p p o r tt o o u rf p g a i m p l i c a t i o n a f t e rc o m p a r i n gt h ep e r f o r m a n c eo f t h ef p g ad e v i c e sa n d t h ed e v e l o p i n gt o o l s ，w ed e c i d et ou s et h et e c h n o l o g yf r o ma l t e r aa n di t sf l e x1 0 k e d e v i c e sf o rt h e i rd e s i g nf l e x i b i l i t ya n d h i g hp e r f o r m a n c e w h a tw e d i dn o to n l yg i v ea t e c h n o l o g yp r e p a r a t i o nf o rt h ea s i ci m p r e c a t i o no ft h ed e c o d e r , b u ta l s os t e pt o a n e wd i r e c t i o nw h i c h u s i n g t h ef p g ai nt h ed i g i t a l - s i g n a l - p r o c e s s i n gf i e l d i nt h eh a r d w a r e d e s i g ns c h e m e ，w e c o m b i n e t h e “t o p - t o d o w n a n d d o w n - t o - t o p ”t e c h n i q u et od i v i d et h ew h o l ep a r ti n t os m a l lf u n c t i o n m o d u l e s a l lt h e m o d u l ew r o t ei nv e r i l o gh d l t h r o u 曲o p t i m i z i n gt h em a i np a r t so f p r o j e c t ，w ec a n n o to n l ye n h a n c et h ep e r f o r m a n c eb u ta l s or e d u c et h ep r o c e s s i n gt i m ea n dg a t e su s i n g i nt h ef p g a f i n a l l yw et e s t e dt h a to u ri m a g ed e c o m p r e s s i o ns y s t e mh a v eag o o d p e r f o r m a n c ea n d h a st h ep r a c t i c a lv a l u e s k e yw o r d si m a g ec o d i n ga n dd e c o d i n g e n t r o p yc o d i n g h u f f m a n c o d i n gq u a n t i z e r d c t f i e l dp r o g r a m m a b l el o g i cd e v i c e d i g i t a ls i g n a lp r o c e s s i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得岙盗盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：熹a 勇姥 签字日期： 勋3 年2 月2 6 日 学位论文版权使用授权书 本学位论文作者完全了解叁洼盘茔有关保留、使用学位论文的规定。 特授权墨鲞盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：炳勇踌翩签名：矧；考 签字日期：2 。叼年2 月2 f 日签字日期：办哆年土月“日 第一章绪论 1 1 图像通信 第一章绪论 图像通信是将图像、文字、图表等信息通过图像通信设备变换为电信号进行 传递，在接收端再把它们真实地再现出来的传送视觉信息的通信。图像通信随着 通信领域内的技术革命一综合业务数字网( i s d n ) 和宽带综合业务数字网 ( b i s d n ) i 盘运而生。它与目前广泛使用的声音通信方式不同，它所传递的不仅有 声音而且还有看得见的图像、文字、图表等静止图像或活动图像。具有通信效率 高、便于记忆、形象逼真、临场感强等特点。其传递的信息量远远超过其它通信 方式，扩大了通信范围。 图像信息采用如下几种通信方式进行传输：传真，可视电话，会议电视，电 缆( 包括医用电视，工业电视，教育电视) ，静止图像通信，图文电视，可视图 文，用户电报，智能用户电报，消息处理系统，高清晰度电视等。 图像通信是当今通信技术中发展菲常迅速的一个分支。数字微波，数字光纤， 卫星通信等新型宽带信道的出现，分组交换网的建立，微电子技术和多媒体技术 的飞速发展，都有力地推动了这门学科的发展。数字信号处理和数字图像压缩编 码技术产生了愈来愈多的新的图像通信方式。图像通信的范围在日益扩大，图像 传输的有效性和可靠性也在不断得到改善。 1 2 图像压缩编码的必要性和可能性 图像通信有数字和模拟两种。数字图像通信有数字通信的一系列优点，如： 可以中继传输和多次复制，不会造成噪声和非线性失真的积累；便于进行加密； 便于用v l s i 芯片实现；便于和计算机联网等。但是，数字图像的数据量非常巨 大，若不经压缩，数字图像传输所需要的高传输速率和数字图像存储所需要的巨 大容量将成为推广应用数字图像通信的最大障碍。这就是为什么要进行图像压缩 编码的根本原因。 图像压缩编码的目的是以尽量少的比特数表征图像，同时保持复原图像的质 量，使它符合预定应用场合的要求。压缩数据量。提高有效性是图像压缩编码的 首要目的。图像信息的压缩有模拟和数字两种方法，但是由于数字压缩方法具有 模拟压缩方法无可比拟的优越性，目前大多数系统都采用数字图像压缩方法，模 拟压缩方法将被逐渐淘汰。 数字图像的大数据量与信道容量有限的矛盾提出了数据压缩的必要性，而图 第一章绪论 像信源中的冗余和人眼特性以及对图像的某些特殊要求为图像的压缩提供了可 能性。首先，原始图像是高度相关的，存在很大的冗余度。数据冗余造成比特数 浪费，消除数据冗余可以节约码字。大多数图像的相邻像素间有较大的相关性， 这称为空间冗余度。序列图像前后帧之间有较大的相关性，这称为时间冗余度。 多光谱遥感图像各谱间有相关性，这称为频率域冗余度。其次，若用相同码长表 示不同出现概率的符号也会造成比特数的浪费，这称为符号冗余度。如果采用可 变长编码技术，对出现概率高的符号用短码字表示，概率低的符号用长码字，就 可消除符号冗余度，从而节约码字。允许图像编码有一定的失真也是图像可以压 缩的一个重要原因。在许多应用场合，并不要求经压缩及复原以后的图像和原图 完全相同，而允许有少量失真。只要这些失真并不被人眼所察觉，在许爹睛况下 是完全可以接受的。这就为压缩比的提高提供了十分有利的条件。图像质量允许 的损失越多，可以实现的压缩比就越大。这种有失真的编码称为限失真编码。 图像编码技术就是要把种种压缩的可能性变为现实。 1 3 图像压缩编码的一般框图 图像编码的过程可以概括成图1 1 所示的三个步骤，原始图像经映射变换后 的数据再经量化器和熵编码器成为码流输出。 原 图 复 图 图1 1图像编码的一般框图 映射变换 其目的是通过映射变换改变图像的特性，使之更有利于压缩编码。这样做一 般优于直接对原图进行量化编码。因为图像数据在相邻像素间有较大的相关性， 相邻像素灰度差总是分布在零附近。进一步的统计表明，差值信号的分布接近拉 普拉斯分布，其标准差比原始图像的标准差要小得多，因而对它进行量化编码所 需要的比特数就较少。如果采用更好的预测方法，如由空间相邻四像素点预测当 第一章绪论 前像素值( 帧内d p c m ) ，或用前一帧的像素值预测当前像素值( 帧间d p c m ) ， 可望得到更好的预测值，从而进一步提高压缩比。一个好的映射通过和适合的量 化器相配合，应能充分消除图像信源的各种冗余度。 量化器 在限失真编码中要对映射后的数据进行量化。若量化是对映射后的数据逐个 地进行的，则称标量量化。若量化是成组进行的，则称矢量量化。量化总会造成 某些信息丢失，形成失真，即量化失真或量化噪声。为使失真小，量化应该精细， 但压缩比就会降低，这是一对矛盾。应根据实际需求来选取适当的量化级数和量 化曲线来缓解这对矛盾。量化器的引入是图像编码产生失真的根源。 熵编码器 这一步是用来消除符号编码冗余度的。它一般不产生失真，理想的情况是使 编出码流的平均码长等于量化后数据的信息熵。常用的编码方法有许多种，例如 分组码有：行程码( r l c ) 和变长码( v l c ) ：不分组码有：算术码( a r i t h m e t i c c o d i n g ) 。 上述三个步骤之间是相互联系相互制约的。对有些编码方法，如预测编码或 变换编码，映射变换后数据量并没有减少，甚至因动态范围的加大而使数据量略 有增加。但它为后两步做了准备，使它们能有效发挥作用。而在模型编码中，经 映射变换后得到的模型参数，其数据量已经大大小于原始图像。 此外，如果码流在信道传输时产生误码，就会造成复原图像质量的下降。有 时一个比特的误码会造成一大片复原图像的错误，这种现象称误码扩散现象。按 信息论的观点，压缩得越多，冗余度越小的码流越难抵抗误码的影响。在实用的 图像编码算法中必须对误码扩散提出有效的制约对策。 1 4 本论文主要研究工作 8 0 年代以来，由于数字视频技术的发展，使得数字图像压缩在各个方面得 到广泛的应用。多媒体( m u l t i m e d i a ) 技术以最佳的方式把文字，图片，动画， 语言，音乐和影像等组合在一起，其渗透范围广泛，包括计算机语言、数据格式、 信号编码、传输方法、信息表示直至图像技术，通信设备和网络软硬件等，无处 不在。因此，许多标准化组织，技术委员会及工作组对多媒体技术很感兴趣，制 定了许多这方面的标准，例如：c c i r 6 0 1 ，h 2 6 1 ，h 2 6 2 ，h 2 6 3 ，j p e g 、m p e g 等系列标准。 第一章绪论 在本次的毕业设计中我们就参考上述标准完成了一个可应用于多种场合的 数字图像监控系统。该系统实现从摄像头捕捉图像源，然后对拍摄图像进行压缩， 最后将传输后的压缩图像在监视器上显示。其中的图像压缩过程如下：映射变换 部分主要采用了8 x 8 像素块的离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ，简称 d c t ) ，主要是利用来自摄像头的图像在空间域的相关性；然后在d c t 变换域中对 8x8 的d c t 变换系数进行量化，以充分利用人眼的视觉相关性：再采用h u f f m a n 变字长编码( v a r i a b l el e n g t hc o d i n g ，简称v l c ) 实现熵编码，输出压缩后的码流。 在接收端实现上述过程的逆过程。 随着日趋进步和完善的专用集成电路芯片( a s i c ) 设计技术，电子系统尤 其是数字电子系统的设计过程越来越倾向于采用计算机辅助的自动化设计。当前 的系统设计可以综合利用各种e d a 设计工具，按照用户需求，根据系统的行为 和功能要求，白上至下地逐层完成相应的描述、综合、优化、仿真与验证，直到 生成器件。为了便于尽快地在设计初期验证a s i c 的功能，缩短a s i c 的开发周 期，出现了现场可编程门阵列( f p g a ) 。f p g a 是可编程逻辑器件( p l d ) 的一 种，通常规模较大，它不仅适合于实现各种逻辑电路，而且在数字信号处理方面 有着广阔的应用前景。本文的主要工作就是在a l t e r a 公司的f l e x1 0 k 系列器件 上实现解码端的图像恢复过程。由于这种器件具有高密度、大规模、易于实现复 杂宏函数和存储器等特点，因此可以把一个子系统集成在单一芯片上，同时每个 f l e x 1 0 k 器件都包含一个由一系列嵌入式阵列块( e a b ) 组成的嵌入式阵列， 它可以用来实现各种复杂的逻辑功能以及r a m 、r o m 等存储器。在本文介绍的 设计方案中，即按照自上而下的设计方法，对图像解码器进行分析，进而进行逻 辑功能分割及模块划分，然后分别实现各子模块，并最终完成整个系统。在设计 过程中，利用了a l t e r a 公司的m a x + p l u s i i 开发平台，进行设计输入、编译、 仿真，最后验证了设计的正确性。通过系统波形仿真，证明了这种设计方案可以 满足设计要求，完成相应的译码性能，具有一定的实用价值。 本论文的结构如下： 第二章介绍了整个图像监控系统的解码结构以及其中的关键技术。 第三章介绍了a n a l o gd e v i c e 公司的a d s p 系统以及解码系统在d s p 系统上 的实现，对整体方案进行了验证。 第四章介绍了e d a ( 电子设计自动化) 技术以及f p g a ( 现场可编程门阵列) 器件的基本知识，根据我们所选取的解码算法在f p g a 实现各模块。 第五章对本设计进行仿真并对结果进行分析。 最后为结束语、致谢和参考文献。 本人论文完成的主要工作以及创新包括以下几项： 第一章绪论 学习了图像处理中各种经典处理算法，并根据我们的实际需求选 择了适合的压缩方案。 在v i s u a ld s p + + 2 0 环境下仿真验证了解码算法； 根据选择的方案对各个模块进行了硬件设计优化； 编写了v e r i l o gd h l 程序进行了f p g a 编程； 针对变长码的硬件实现特点对h u f f m a n 解码器进行了有别于传统 译码算法的改进，采用了新的存储结构，减少了对存储器的容量 要求，而且加快了译码速度，可以在一个时钟周期判定2 b i t s 数据， 提高了数据的吞吐率： 在i d c t 部分采用了流水线设计方法，加快了运算速度，而且使 各个逻辑函数时序严密配合，处理延时达到最小； 在量化器设计部分结合系数固定的特点简化了乘法器的设计。 ) q q 卵 第二章图像压缩编解码的基本原理和方案 第二章图像压缩编解码的基本原理和方案 图像编码技术应用面广泛，已研究出许多种压缩编码方法，各自基于不同的 思想和技术途径，适合于不同的应用场合，内容十分丰富。这里主要介绍一下图 像压缩编码的基本原理s h a n n o n 信息论，以及基本的图像压缩编码方法，如无失 真编码中的h u f f m a n 编码，算术编码，游程编码，限失真编码中的预测编码，变 换编码等。 2 1 图像数据压缩的信息论基础 在数据压缩技术中，s h a n n o n 信息论占有极为重要的位曼。它一方面给出了 数据压缩的理论极限，另一方面给出了数据压缩的技术途径。 一信息量与熵 通常信息源是由一系列符号构成的，假设一个信息源所产生的符号系列中的 符号取自一个有限符号集，符号集中的符号s i 发生的概率为p ( s i ) ，则其所携带的 信息量i 是如下定义的： ，= l o g ：) 一l 。g ( p ) ( 2 1 ) 如信息源中某一符号的出现概率大小不受前面符号出现与否的影响时，即信 息源所送出的符号相互独立，则该信息源称为离散无记忆信源，此时其信息量又 称自信息量。离散无记忆信源中一个符号所携带的平均信息量h 定义为 h = 一p ( s i ) l 0 9 2 【p ( s ) 】 ( 2 2 ) 平均信息量h 又称作信息熵。熵实际上是信源符号集中各符号所携带的信 息量的数学期望。s h a n n o n 信息论已经证明，熵是离散无记忆信源进行无失真编 码的极限，即对离散无记忆信源进行编码所能得到的平均码长的最小值不会低于 h 。 可以证明，信源的概率分布越均匀，其熵越大；反之，其熵越小。信源压缩 编码的目的之一就是在一定信源概率分布条件下，尽可能使编码平均码长接近信 源的熵，减少冗余。 二互信息量与条件熵 实际上信源往往并不是无记忆的，其前后出现的信源符号常常具有一定的相 6 第二章图像压缩编解码的基本原理和方案 关性。假定信源符号x 出现的概率为p ( x ) ，而信源符号y 出现后又出现符号x 的 条件概率为p ( x y ) ，则定义互信息量i ( x ，y ) 为 i ( x , y ) ：1 0 9 2 1 哗 ( 2 3 ) p t x ) 由此定义可知，互信息量小于或等于自信息量，即 i ( x ，y ) = l 0 9 2 p ( x y ) 一l 0 9 2 p ( x ) - l 0 9 2 p ( x ) = ，( x ) ( 2 4 ) 若信源符号x 和y 不论前后顺序同时出现的概率为p ( x ，y ) ，则定义其条件熵为 mm h ( x y ) = 一ep ( 一，y ，) l o g ：e ( x ，ly s ) j - i = 1 = h ( x ，y ) 一h ( y )( 2 5 ) mm 其中h ( x ，y ) = 一e ( x ，y i ) l o g p ( x 。- y ，) i = i = l 为信源符号x 和y 同时出现的联合熵。因此 h ( x ，y ) = h ( x l y ) + h ( y )( 2 6 ) 上式表明，如果信源符号x 和信源符号y 之间存在着一定的关联，那么当信 源符号y 出现，在解除了y 不肯定性的同时，也解除了部分x 的不肯定性。但此 时x 仍有部分的不肯定性，这正是h ( x i y ) 的含义。显然x 和y 的相关性越小，剩 余的不肯定性就越大。当x 和y 相互独立时，y 的出现丝毫不能解除x 的不肯定 性。此时联合熵变为2 个独立熵之和，从而达到它的最大值： h m a “x ，y ) 2 h ( x ) + h ( y )( 2 7 ) h 。( x ，y ) 与h ( x ，y ) 之差反映了此联合信源所含有的冗余。两信源间的相关性 越大，冗余也越大，因此数据压缩的基本途径之一就是去除联合信源中的各信源 间的相关性。 三率失真函数 在信息论中，率失真理论回答了有关失真度与信道容量之间的关系问题，为 限失真编码奠定了理论基础。率失真函数的定义如下：在传输中使信号的失真度 小于或等于某一值d 所必需的信道容量的最小值r ( d ) 称为信息速率失真函数， 或率失真函数。率失真函数定义了在给定失真度量条件下，信源编码所能达到的 比特率下限。 在图像处理与图像编码技术中，通常用均方误差作为图像失真的度量标准。 根据信息论的结论，在假设图像信源是正态分布的条件下，率失真函数为： 7 第二章图像压缩编解码的基本原理和方案 f 1盯2 r ( d ) ：j 2 l o g z 百 1 0 0 d 仃2 d 盯2 ( 2 8 ) 其中：d 为允许的均方误差失真，o 为信号的方差。 在图像编码中，r ( d ) 代表着在均方误差不大于d 时，传输一个像素的平均 比特数。该式还表明：如果d o - 2 ，即允许的失真比输入信号的方差还大，此 时r ( d ) = o ，信息传输已失去意义。另外由该式可见，所需传输信号的方差越小， 允许的失真越大，所需传输的比特率越低。可以证明的是：如果图像信号为非正 态分布，则r ( d ) 的数值只会比式( 2 8 ) 中到的数值更低，因为在一定的功率条 件下，正态分布时信源的熵最大。 率失真函数从理论上指明了方向，即在给定信号允许失真度的条件下，为了 减少图像传输的比特率，应尽量减小传输信号的方差。 2 2 无失真图像压缩编码 信源冗余来自信源本身的相关性和信源概率分布的不均匀性。无失真图像压 缩编码的基本原理就是去除图像信源在空间和时间上的相关性，去除图像信源像 素值的概率分布的不均匀性，使编码后的图像数据接近其信息熵而不产生失真。 因此，这种编码方法又称为熵编码。 无失真图像压缩编码的方法主要有：基于图像概率分布特性的h u f f m a n 编 码，算术编码和基于图像相关性的游程编码。 一霍夫曼( h u f f m a n ) 编码 在变字长编码中，对于出现概率大的信息符号编以字长短的码，对于概率小 的符号编以字长长的码，这称为变字长编码的最佳编码定理。 h u f f m a n 编码是根据可变长度最佳编码定理，应用h u f f m a n 算法得到的一种 编码方法，是h u f f r n a n 于1 9 5 2 年为压缩文本文件建立的。它是整数编码的一种 最佳码，即它的平均码长在具有相同输入概率的前提下，比其它任何一种唯一译 码都短。h u f f m a n 编码是图像压缩中最重要的一种编码方法之一。 其编码步骤如下： 将输入符号按出现的概率由大到小排列，排列相同概率的符号可以任意 颠倒排列位置，也就是说h u f f i a a n 编码并不唯一。 将最小的两个概率相加得到一个新的概率，再去掉那两个最小的概率， 形成一个新的概率集合。再按第步的方法重排。如此重复直到两个概率为 1 1 l 。 第二章图像压缩编解码的基本原理和方案 分配码字。码字分配从最后一步开始反向进行，对最后两个概率，一个 赋予0 码字，一个赋予“1 ”码字。 该编码结构实际上是一棵二叉树，码字都是从根出发排列的。概率大的符号 分配较短的码字，概率较小的符号分配较长的码字，从而提高其编码效率。 举例如下：假设一个文件中出现了8 种符号s 0 ，s 1 ，s 2 ，s 3 ，s 4 ，s 5 ，s 6 ， s 7 ，那么每种符号要编码，至少需要3 比特，假设编码成0 0 0 ，0 0 1 ，0 1 0 ，0 1 1 ， 1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 ( 称做码字) 。那么符号序列s o s l s 7 s o s l s 6 s 2 s 2 s 3 s 4 s 5 s o s 0 s 1 编码后变成 0 0 0 0 0 1 1 1 1 0 0 0 0 0 l l l 0 0 1 0 0 1 0 0 l l l 0 0 1 0 1 0 0 0 0 0 0 0 0 1 共用了4 2 比特。由于s o ，s 1 ，s 2 这三个符号出现的频率比较大，其它符号出 现的频率比较小，所以我们通过编码使得s o ，s 1 ，s 2 的码字短，其它符号的码 字长，这样就能够减少占用的比特数。 例如，我们采用这样的编码方案：s 0 到s 7 的码字分别0 1 ，1 1 ，1 0 1 ，0 0 0 0 ， 0 0 0 1 ，0 0 1 0 ，0 0 1 1 ，1 0 0 ，那么上述符号序列变成 0 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 共用了3 9 比特，尽管有些码字如s 3 ，s 4 ，s 5 ，s 6 变长了( 由3 位变成4 位) ， 但使用频繁的几个码字如s o ，s 1 变短了，所以实现了压缩。 在编码过程中必须保证不能出现一个码字和另一个的前几位相同的情况，比 如说，如果s o 的码字为o l ，s 2 的码字为0 1 1 ，那么当序列中出现0 1 l 时，就会 不知道是s 0 的码字后面跟了个1 ，还是完整的一个s 2 的码字。所以在具体的编 码算法中必须避免这种情况的出现。 结合上面的例子，我们可以得到一个具体的h u f f m a n 编码实现如图2 1 所示： l ，首先统计出每个符号出现的频率，上例中s o 到s 7 的出现频率分别为4 1 4 ， 3 1 4 。2 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ，1 1 4 ； 2 从左到右把上述频率按从小到大的顺序排列； 3 每一次选出最小的两个值，作为二叉树的两个叶节点，将它们的和作为根 节点，这两个叶节点不再参与比较。新的根节点参与下一次比较； 4 重复3 ，直到最后得到和为l 的根节点； 5 将形成的二叉树的左节点标0 ，右节点标1 。把从最上面的根节点到最下 面的叶子节点途中遇到的o ，1 序列串起来，就得到了各个符号的编码。 在图2 1 中圆圈中的数字是新节点产生的顺序。从图可以看出，不会出现任 何一个码字成为另一个码字的前缀。 产生h u f f m a n 编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原 始数据中每个值出现的频率，第二遍是建立h u f f m a n 树并进行编码，由于需要建 9 第二章图像压缩编解码的基本原理和方案 s 3。|五 蠕 s 7 s 2 s 锄 0 0 0 0 0 0 0 10 0 1 00 0 1 11 0 0 1 0 11 1 0 1 图2 1 h u 釜n a n 编码的示意图 立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效， 因而它得到广泛的应用。 二算术( a r i t h m e t i c ) 编码 算术编码是另一种利用信源编码概率分布特性，能够趋近熵极限的编码方 法。尽管它也是对出现概率大的符号采用短码，对出现概率小的符号采用长码， 但其编码原理与 - u 胁a n 编码却不相同，而且在信源概率分布比较均匀的情况下 其编码效率要高于f i u f f r n a n 编码。它和f i u f f m a n 编码的最大区别在于它不是使 用整数码。 算术编码的方法是将被编码的每一个信源消息按其概率大小表示成实数轴 0 1 之间的一个区域( 或称之区间) ，概率越大，所占间隔越大，表示这一间隔 所需的二进制分数值位数就越小：反之就越大。算术编码所产生的码字实际上就 是一个二进制分数值的指针，该指针指向所编符号对应的概率区间，该区间为半 开区间，包括左端点，不包括右端点。算术编码的规则如下： 在初始状态，编码指针c = o ，子区间长度l = 1 0 在编码状态，编码指针c = 原始码点c + 原子区间长度l x n 子区间长度l = 原子区间长度l xp i 其中p i 和p i 分别为所编符号对应的概率和累计概率 取最后一个被编码符号编码指针的二进制分数值作为对整个信源符号 编码集的编码结果。 1 0 第二章图像压缩编解码的基本原理和方案 三游程编码 由于图像中各像素之间一般都存在相关性，特别是由计算机生成的图像和大 部分二值图像，它们往往在某些区域具有相同的像素值。游程编码( r u n 1 e n g t h c o d i n g ) 是一种相对简单的编码技术，主要思想是将一个相同值的连续串用一个 代表串长和值的组合码字( r u n ，l e v e l ) 来代替。其中游程( r u n ) 表示系数系 列中连零系数的长度；量化电平( l e v e l ) 表示连零系数之后第一个非零系数的 值。h 2 6 1 建议中使用的游程编码就是上面所述的二维游程编码；h 2 6 3 建议对 此作了改进，使用的是三维游程编码( l a s t ，r u n ，l e v e l ) ，其中的l a s t 表示此 码字组合是否是本块中最后一个非零系数( “0 ”表示不是，“1 ”表示是) ，r u n 和l e v e l 含义和上面所说的相同。 游程编码一般不直接应用于多灰度图像编码，但比较适合于二值图像的编 码，如传真图像的编码等。为达到较好的压缩效果，游程编码经常和其他一些编 码方法混合使用。j p e g 、h 2 6 3 中游程编码和d c t 及h u f f m a n 方法一起使用， 对分块作完d c t 及量化后的频域图像数据作“z ”型扫描，然后作游程编码， 对游程编码的结果再做h u f f m a n 编码。 2 3 限失真图像压缩编码 无失真图像压缩编码主要是利用图像信源的概率分布特性，使编码后的图像 平均码长逼近信源熵。在大部分情况下这种压缩方法的压缩比是不大的，因此在 许多应用场合为了进一步压缩数据。允许解码后的图像相对原图像有一定的失 真。 率失真理论从理论上指出，在给定信号允许失真度的条件下，为了减少图像 传输的比特率，应尽量减小传输信号的方差。预测编码和变换编码正是根据这一 理论对原始图像进行压缩，使处理后的图像信号的方差减小，最终达到压缩编码 的目的。 一预测编码 对于绝大多数图像来说，在局部空问和时间上是高度相关的，因而可以在 己得到像素的基础上通过对当前像素的预测来减少图像的数据量。由条件熵的性 质可知，在已知x x m ，x m 的条件下确定的x i 的熵，其值总是比较小的。 这就意味着可利用x “，x i - 2 ，x i - m 来预测x i 的值，且预测值可能比较接近真 实值，而它们的差值d 。的方差比原始图像系列的方差要小。因此，传输它们的差 值就可用比较少的比特数。 第二章图像压缩编解码的基本原理和方案 预测编码是统计冗余数据压缩理论的重要分支之一，也称为差分脉冲调制 ( d p c m ) ，即可以在一帧图像内进行帧内预测编码，也可以在多帧图像内进行 帧间预测编码。预测编码的基本技术是信号的最佳预测和最佳量化，主要使用来 减少数据在时间和空间上的相关性。 帧内d p c m 帧内进行预测编码的理论根据是二维图像中像素间存在很强的相关性，因此 可用已知的前面几个像素值来预测当前像素值。这些像素可以是前几行的或前几 帧的，分别称为一维，二维和三维预测。然后对实际值与预测值的差值( 预测误 差) 进行量化和编码。帧内预测编码的优点是方法简单，硬件实现容易。其缺点 是对信道噪声以及误码很敏感，会产生误码扩散。同时帧内d p c m 压缩比较低， 通常为2 3 倍。随着变换编码的广泛应用，帧内d p c m 的作用已很有限。目前， 主要使用帧间d p c m 预测方法来压缩活动图像。 帧间d p c m 帧间预测编码的理论依据是视频信号的相邻帧间存在极强的相关性。利用这 种时间相关性来进行帧问编码，可获得比帧内d p c m 高得多的压缩比。目前， 帧间d p c m 广泛用于常规电视，高清晰度电视，会议电视和电视电话等视频信 号的压缩编码，如h 2 6 x 建议，m p e g 系列标准等。采用的预测方法有以下几种； 帧重复，对于静止或活动很慢的视频信号，可以少传些帧；域值法，即只传送 像素亮度的帧间差值超过某一域值的像素：帧内插，对活动缓慢的图像，可以使 用前后两帧图像进行内插以得到实际图像的预测图像，然后对实际帧与预测的差 值信号进行编码；运动补偿预测。 二变换编码 变换编码就是在图像传输时不直接传送图像在时间、空间中某种物理量的表 达，而是传送它的某种变换系数，接收端收到变换系数后，再进行反变换恢复图 像。变换编码与预测编码一样，都是利用去除信源序列的相关性来达到数据压缩 的目的。它们的区别在于，预测编码是在时间，空间域进行，而变换编码是在变 换域进行。 绝大部分图像信号在空间域中像素之间的相关性是很大的。它们经过正交变 换后，其能量主要集中在低频部分；而且经过正交变换后相关性大大降低。变换 编码的基本思路就是利用上述特点，在编码时略去某些能量很小的高频分量，或 在量化时对方差较小的分量分配以较少的比特数。另外，变换编码还可以根据人 眼对不同频率分量的敏感程度而对不同系数采用不同的量化台阶，以进一步提高 压缩比。 从均方误差最小和主观图像质量两个观点来看，最好的变换类型是离散 1 2 第二章图像压缩编解码的基本原理和方案 k l 变换，其变换后的系数间是互不相关的，而且能量高度集中在少数系数中。 但就其实现的成本与实时性来说，k - l 变换则是最困难的一种变换，它的理论价 值远高于其实际价值。 在图像压缩中，最常用的变换方法是d c t ，d c t 被认为是性能接近k l 变换的准最佳变换。d c t 变换具有以下特点： d c t 变换域稀疏矩阵能量高度集中在直流和低频区； d c t 的直流系数近似满足瑞利分布，交流系数近似满足拉普拉斯分布； d c t 系数基本不相关。 d c t 变换矩阵的大小可以从去除相关程度和实现难易程度等方面来综合 考虑，8 x8 通常被认为是一种较好的选择。其二维d c t 及i d c t 变换如下： 脚，= 扣川陲砉巾棚c o s 芋c o s 普竽】， 邝棚= 言壹壹c c ( v ) 脚，v ) c o s 譬警c o s 等竽u=0 v = 0 叶- u1 u 其中： c ( u ) = 去，u = 0 c ( u ) = l ，u 0 c ( v ) = 去，v = 0 c ( v ) = 1 ，v 0 在各种图像编码标准( h 2 6 x ，j p e g ，m p e g ) 中均使用了8 x8 d c t 变换 编码。二维d c t 及i d c t 的实现有很多种算法，其快速算法的基本思想是首先 将二维d c t 转化为一维d c t ，利用d c t 与d f t 的联系，使用蝶形结构的d f t 计算。 2 4 本设计方案 根据图像编码的基本理论，参照j p e g 标准，我们的数字图像监控系统采用 了如图2 2 所示的编解码方案。 一编码过程 来自摄像头的图像信号经过8 x8 分块后进入编码器进行d c t 变换。采用 d c t 主要出于以下几点考虑：d c t 是实域的运算，不同于d f t 是复数运算，应 而复杂度降低；d c t 变换矩阵的基向量很接近于托波列兹矩阵的特征向量，而 语音信号和图像信号的协方差矩阵都是托波列兹矩阵，这就是上节中提到的d c t 变换接近最佳变换( k l 变换) 的原因。k l 变换属于统计上的最佳变换，当统 第二章图像压缩编解码的基本原理和方案 编码部分 解码部分 图2 ，2 编解码框图 计特性不同时必须重新计算，而且没有快速算法。所以我们仍然采用d c t ；d c t 变换系数具有弱相关性，非相关的变换系数对压缩极为重要，因为可以单独处理 各系数而不损失压缩效率。 d c t 变换后其低频分量都集中在左上角，高频分量分布在右下角( d c t 变 换实际上是空间域的低通滤波器) 。由于低频分量包含了图象的主要信息( 如亮 度) ，而高频分量与低频分量相比，就可以忽略，从而可以达到压缩的目的。为 了去除高频分量，我们采用了量化器，它是产生信息损失的根源。这里的量化操 作，就是对d c t 系数除以相应8 8 量化表中的步长，对所得值四舍五入取整。 由于量化表左上角的值较小，右上角的值较大，这样就起到了保持低频分量，抑 制高频分量的目的。 压缩过程中使用的颜色是y u v 格式。y 分量代表了亮度信息，u v 分量代 表了色差信息。相比而言，y 分量更重要一些。我们可以对y 采用细量化，对 u v 采用粗量化，可进一步提高压缩比。所以上面所说的量化表有两张，一张是 针对y 的；张是针对u v 的。高频系数反映图象细节，因为人眼对高频系数 和色度不够敏感，所以这一步是通过心理视觉冗余度对图像数据进行压缩。 经过d c t 变换和量化后，低频分量集中在左上角，其中f ( 0 ，0 ) ( 即第一 行第一列元素) 代表了直流( d c ) 系数，即8 x8 子块的平均值，要对它单独编 码。由于两个相邻的8 x 8 子块的d c 系数相差很小，所以对它们采用差分编码 d p c m ，可以提高压缩比，也就是说对相邻的子块d c 系数的差值进行编码。8 x 8 的其它6 3 个元素是交流(