视频图像压缩算法的研究(毕业论文).doc

_精品资料本科毕业设计（论文）题目 视频图像压缩算法的研究 学 院 电气与自动化工程学院 年 级 2009 专 业 自动化 班 级 学 号 学生姓名 指导教师 职 称 论文提交日期 2013-5-17 常熟理工学院本科毕业设计(论文)诚信承诺书本人郑重声明： 所呈交的本科毕业设计(论文)，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。本人签名： 日期： 常熟理工学院本科毕业设计(论文)使用授权说明本人完全了解常熟理工学院有关收集、保留和使用毕业设计(论文)的规定，即：本科生在校期间进行毕业设计(论文)工作的知识产权单位属常熟理工学院。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许毕业设计(论文)被查阅和借阅；学校可以将毕业设计(论文)的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编毕业设计（论文），并且本人电子文档和纸质论文的内容相一致。保密的毕业设计(论文)在解密后遵守此规定。本人签名： 日期： 导师签名： 日期： 视频图像压缩算法的研究摘 要目前，视频监控已经进入高清时代，原有的视频压缩标准已经不能适应视频监控的发展了。MPEG-4视频压缩标准是一个适用于低传输速率应用的标准，它同时支持交互操作，并对错误易发环境具有较高的鲁棒性。其良好的交互性和高压缩率在视频监控领域发挥了巨大的作用。本文以视频监控为对象对视频图像压缩算法进行了研究。首先对监控系统的硬件进行设计，然后对视频压缩基础模型中各种关键算法进行了研究和比较。介绍了压缩算法在视频监控中的应用，并深入研究了视频压缩标准中的各种高级功能在视频监控中的实现。最后以Visual C+6.0为平台，设计了视频压缩系统，来实现采集图像的同时，实时进行压缩处理。对压缩率及压缩时间进行了分析，明确该设计的有效性和必要性。关键词： 视频监控 MPEG-4 视频压缩 视频流 VFWResearch on Video Image Compressing AlgorithmAbstractCurrently, video surveillance has entered the high-definition era, the original video compressing standard can not adapt to the development of video surveillance. MPEG-4 video compressing standard which is helpful to low bit rate applications, can provide alternation manipulation and has better channel error robustness. Good interactivity and high compression rate play a huge role in the field of video surveillance.The paper researches on video image compressing algorithm based on the video surveillance. Firstly, we design hardware of the monitoring system, then research and compare of various key algorithms of based model for video compression. This paper introduces the application of video compressing algorithms in video surveillance and application of various advanced features of video coding standard. Finally, we take Visual C+6.0 as the platform, design the video compressing system to realize the acquisition of images. At the same time, realize compression processing in real-time. We must analyze compression ratio and compression time, and clear the effectiveness and necessity of the design.Key Words：Video surveillance; MPEG-4; Video compress; Video stream; VFW目 录1. 绪论11.1 课题的研究背景及意义11.2 视频监控系统的研究现状11.3 本文主要研究目标与章节安排31.4 本章小结32. 视频监控系统的总体设计42.1 监控系统的总体设计42.2 摄像头的选择42.3 压缩系统52.4 网络连接52.5 本章小结53. 视频压缩算法的研究63.1 信息冗余63.2 混合的DPCM/DCT模型63.3 帧间预测83.4 基于块的运动估计与补偿103.5 运动估计算法113.5.1 块匹配的准则113.5.2 全搜索法123.5.3 三步法133.5.4 全搜索法和三步法的比较133.6 分块大小对残差图像的影响153.7 离散余弦变换173.8 量化183.9 熵编码203.9.1 霍夫曼编码203.9.2 算术编码213.9.3 霍夫曼编码与算术编码的比较213.10 本章小结224. 压缩算法在视频监控中的应用234.1 视频压缩在监控中的具体应用234.2 视频数据结构244.3 形状编码264.4 静态Sprite编码274.5 分级编码284.5.1 空域可分级编码284.5.2 时域可分级编码294.6 本章小结305. 视频图像压缩的实现315.1 视频压缩的实现方法的选择315.2 MFC的使用315.3 获取实时视频图像325.4 压缩结果分析345.5 本章小结366. 总结与展望37参考文献38致谢39精品资料_1. 绪论1.1 课题的研究背景及意义二十世纪五十年代，对于图像压缩编码的研究就已经开始，到目前为止已经有六十多年的发展历史。随着计算机网络技术和多媒体技术的不断发展，人们对于信息的需求越来越多，特别是多媒体技术已经渗透到人们生活的各个方面，成为了人们获取信息最重要的载体。人们希望通过各种各样的技术可以在任何时间任何地方快速方便地获取图像、声音和视频等各种多媒体信息。因此近年来多媒体信息的计算、存储和传输成为了研究的热点。视频编码作为多媒体技术中重要的环节，也得到了很快的发展，而且变得越来越重要。面对一个全新的多媒体时代，如何使用户可以进行更具灵活性和交互性的视频交流；如何在低比特率的情况下，充分利用带宽传输清晰的视频文件；庞大的数据在存储和传输过程中如何得到高效率的快速压缩将成为关键问题。MPEG-4 视频压缩标准是一个适用于低传输速率应用的方案，与MPEG-1 和MPEG-2 相比，MPEG-4 更注重多媒体系统的交互性和灵活性。这无疑将会给视频的高速传输、处理等方面带来更好的解决方法。1.2 视频监控系统的研究现状由于视频图像压缩技术应用广泛，所以一直都是人们研究的热点。在视频监控中，视频图像压缩技术同样又是必不可少的技术。可以说，视频监控技术和视频压缩技术的发展基本是同步和相适应的。监控图像技术的发展归纳起来大概可分为三个阶段：（1）模拟图像监控模拟图像监控被称为第一代监控技术。因为第一代技术并没有什么控制能力，准确的说应该叫“监视”。黑白图像的监控技术是伴随着摄像机和电视机的诞生而一起诞生的。由于当时技术限制，第一代技术被用在了很多场合。虽然它的功能较为单一，图像质量又较差，但是比较直观，人们还是投入了很多精力去完善它。当时的监控系统是采用的模拟信号方式传送。就是从每个摄像机的视频信号直接通过各自电缆传到中心控制室的多路切换器上，通过手动切换，每次只能看一个视频镜头。随着不断的发展，为了减少电缆，采用了模拟射频调制的方法。这种方法就是将不同的信号调制在不同的射频载波上，通过多路合成技术，送入一根电缆，传送到中心控制区。在控制中心，通过多路分解技术分解开来，再通过解调，还原各路视频信号。由于采用了调制技术，使的第一代监控技术的抗干扰能力增强，图像质量增加。（2）半数字图像监控进入二十世纪八十年代，随着数字技术的不断发展，图像监控也经历了一场技术革命。人们开始从模拟方式处理转向数字化处理方式。PC机逐渐被人们用来处理视频图像信号。通过视频采集卡将视频信号采集到计算机中，在显示器上显示出来，使视频图像的质量大大提高。通过计算机可以建立很好的人机交互界面，而且还具有很好的稳定性，但是其仍不能称为真正的数字图像监控技术。因为计算机在这个系统中只是充当着一个显示器的角色，其核心的切换和控制机制仍然是基于传统的单片机方式。导致已有的计算机无法满足多种设备的需求。另外，由于当时的计算机处理能力有限，很难在一台计算机上处理很多的视频图像信号，导致难以建立大型的监控系统。但是能将计算机引入视频监控中本身就是一个巨大的进步。（3）多媒体网络监控在实际的监控应用中，管理者已经不再满足于数据、图形和文字等信息。他们需要更多的信息来支持生产和管理。他们希望能够身临其境的了解生产现场的情况。随着视频编解码技术和网络技术的不断发展，视频监控也变得日益强大。多媒体网络监控不仅能够提供传统的数据、图形和文字信息，还能够提供更加清晰的视频图像，使生产更有效率。多媒体网络监控不仅可以建立生产系统的监控，而且还可以建立更大的系统，如城市监控系统、交通监控系统等。目前，视频监控被广泛应用于金融、交通、商业、乃至住宅和社区等很多领域。为这些领域和行业的安全和环境的监控起到了至关重要的作用。近10年，随着图像处理技术、计算机网络、自动化技术以及通信传输的发展，视频监控有了质的飞跃，已经全面进入了数字图像监控时代。 在数字视频监控中，H.261和MPEG-1还是主要的视频图像压缩标准，但是在实际应用中还是有一定的局限性。首先，它们的适应性相对较差，不能根据不同的网络环境自适应的调节传输率，在网络发生阻塞时，性能就会急剧下降；其次，它们在用户交互性方面也是比较差的。MPEG-4就能够很好的弥补以上不足，而且在监控应用中还具有一些独特优势。由于压缩比要比同质量的MPEG-1高出十多倍，因此可以在低比特率条件下传输，节约更多的存储空间和网络带宽。可以带来质量更高的图像，效果接近DVD。在网络传输时，如果发生误码或者丢包，MPEG-4所受的影响很小并且能够迅速恢复。因此，现在MPEG-4在视频监控中也开始发挥越来越大的作用。1.3 本文主要研究目标与章节安排本设计是一个基于DivX编码器的视频编码系统，实现视频图像的高压缩率编码和快速编码，并能够在视频监控中得到应用。具体包括：（1）视频监控系统简化的硬件设计。（2）按时域模型、空域模型和熵编码的顺序对视频编码各个关键算法做详细的研究并进行了比较。（3）阐述视频编码在监控中的应用，以及各种高级功能的实现。（4）利用Visual C+6.0中的MFC编写视频编码系统代码，实现实时的视频编码，并对各个关键数据进行分析。1.4 本章小结本章内容简单介绍了视频压缩的背景，介绍了视频监控的发展历史，从第一代模拟视频监控到现在网络监控，视频监控已取得巨大的进步，最后介绍了视频压缩算法在视频监控中的应用以及本设计的研究目标和主要内容。2. 视频监控系统的总体设计本设计主要是基于VC6.0中的MFC开发工具完成的。但是软件设计同样也是需要依赖于计算机的硬件系统来完成的。例如摄像头就是采用的笔记本电脑的摄像头，所以有必要对于基本的硬件进行设计。2.1 监控系统的总体设计本系统设计的硬件平台主要由三部分组成，前端的摄像头，计算机系统和远端的宿主机。系统工作的原理如图2.1所示。图2.1 系统工作原理计算机通过驱动程序，打开摄像头，开始抓取视频图像。视频图像通过计算机进行压缩后，通过网络发送到远处的宿主机，可以让人们在远处进行查看，实现实时的远程监控。2.2 摄像头的选择在本设计中利用驱动程序可以用来打开摄像头。而摄像头是可以选择的，可以使用计算机本身的摄像头或者是利用USB扩展的外围摄像头等。其中USB扩展的摄像头的工作原理：景物经过镜头（LENS）形成的光学图像投射到图像传感器的表面，转换为电信号，经过A/D转换（模数转换）后转换为数字图像信号，再传送到数字信号处理芯片（DSP）中进行处理，然后再通过USB接口传输到计算机中进行处理，在显示器上就可以看到图像了,摄像头的工作流程如图2.2所示。图2.2 USB摄像头工作流程图2.3 压缩系统至于摄像头驱动程序是有计算机所自带的8。视频采集算法是利用的微软所提供的强大的VFW库函数。VFW推出了一整套完整的视频采集、压缩、解压缩、回放和编辑的应用程序接口(API)，可以供程序员使用。计算机对于视频数据的压缩主要是依赖于强大的视频编码器（DivX视频编码器），此编码器对静态视频图像的压缩率非常高，动态图像稍低。但是DivX视频编码器在实时性的实现上非常的好，通常压缩一帧视频的时间基本都是在7ms以内，还是较快速的。2.4 网络连接对于一个完整的视频监控系统而言，有监控部分还必须具有宿主机，可以来看视频，视频需要通过网络来进行传输。可以用两台计算机直接相连来实现通信，也可以使用其他方法。两台计算机通过光纤进行通信如图2.3所示。图2.3 光纤通信示意图远程的计算机可以通过网络或其他的一些途径接收到视频信息，完成视频监控。2.5 本章小结这节主要介绍了视频监控的简单硬件。介绍了USB摄像头的选择和工作原理，并简介了压缩系统和网络的连接。3. 视频压缩算法的研究在视频监控中，视频压缩是非常重要的一个环节，也是与前几代监控技术的一个很大区别。压缩就是将大量的数据以较小的空间来存放的方法，视频压缩是降低数字视频序列比特数的过程。MPEG-4 视频压缩标准的核心与其他编码标准基本是相同的，本质上都是采用了在运动补偿后紧跟DCT变换，量化和熵编码的基于块的混合DPCM/DCT 模型。3.1 信息冗余在研究视频压缩前，我们必须要了解一个概念，即信息冗余。视频中的冗余主要有空间冗余、时间冗余、信息熵冗余和视觉冗余等几种。正是因为视频数据中存在着这些冗余信息，从而使数据压缩成为了可能。视频压缩主要利用视频图像的两个属性：时间相关性和空间相关性。帧内图的像素点与像素点之间，在亮度和色度上都存在着一定的相关性，这种相关性就是视频图像的空间相关性；在视频中，一个场景往往有若干个连续的视频帧构成，相邻的视频帧之间存在着一定的相关性，这种就是时间相关性。这两种相关性为视频图像带来了的很多冗余信息。视频压缩就是需要删除这些冗余信息，保留不相关的信息。一个好的压缩编码标准就是能够在不降低视频图像质量的前提下，使视频图像中的冗余信息降到最低。图3.1说明了时间和空间这两种相关性。图3.1 视频序列的时间冗余和空间冗余3.2 混合的DPCM/DCT模型自1990年以来发布的主要的视频编码标准基本都是基于统一的模型，包括运动补偿和估计，变换编码和熵编码。这种框架被称为混合的DPCM/DCT编码器。MPEG-4视频编码标准同样也是基于这样一个模型开发的。图3.2是简化的DPCM/DCT模型，从下图中我们可以看出DPCM/DCT视频编码器主要三个功能模块：时域模块、空域模块、熵编码器。 图3.2 DPCM/DCT视频编码模型时域模块的输入是未压缩的视频序列，通过利用相邻视频帧之间的相关性减小时域冗余。通过相邻帧对当前编码帧进行预测，并通过对预测误差进行补偿（运动补偿）来改善质量。时域模型的输出是残差帧以及一系列模型参数，如用来描述如何进行补偿的运动矢量。空域模块的输入是残差帧，利用残差帧内相邻像素间的相关性来减小空间冗余。首先对残差值进行变换，用频域内的变换系数表示。对变换系数进行量化，去除不重要的值，保留少量的重要系数，为残差帧提供精简表示。空域模型的输出是一系列量化后的变换系数。熵编码器就是对时域模型（运动矢量）和空域模型（量化系数）的参数进行压缩，去除了数据中的统计冗余，生成压缩码流。一个完整的视频编解码系统还必须具有视频解码系统，解码系统与编码系统类似，只是将编码的过程反过来，从传输的压缩比特流重建视频图像。图3.3 给出了DPCM/DCT 视频编码的详细框图。在3.3-3.9节中，按照时域模块（运动预测和补偿）、图像变换、量化、和熵编码的顺序，对这种编码模型的主要部分进行了深入地研究。图3.3 DPCM/DCT视频编码详细框图3.3 帧间预测预测编码是视频编码技术中非常重要的技术之一。预测编码可以在一副图像内进行（帧内预测编码），也可以在多个视频帧之间进行（帧间预测编码）。现在最常用的预测编码是差值脉冲编码调制法，简称DPCM。一个视频帧信号，设第个采样点的值为，是根据以前采样点的值对该点的预测值。实际值和预测值之间的差值，以下表示 （3-1）将此差值定义为预测误差，由于信号的相关性，所以这个预测误差是很小的。编码时，不是对采样值进行编码，而是对预测误差信号进行量化、编码、发送，由此而得名差值脉冲编码调制法。图3.4是DPCM编解码原理图。图3.4 DPCM编解码原理图上面所介绍的就是前向预测，图3.5至图3.7可以看看前向预测带来的残差的效果。图3.5（a）图3.6（b）图3.7 (c)a为参考帧，用b减去a得到残差图像c。分析c可以得出灰色部分占据大部分（灰色部分的能量较少），而白色和黑色还有不少（白色和黑色说明含有的能量较多）。对于这幅残差图，还含有很高的能量，还有较多的信息需要在后续的工作中通过运动估计和运动补偿来进行压缩。MPEG-4中还有一种双向预测法。双向预测是同时使用前向参考帧和后向参考帧进行预测。双向预测对于编码由物体运动引起暴露区域的图像是非常有效的。因为运动后所暴露出的区域原来是曾被物体遮盖住的区域，这些被遮盖的区域是无法从先前的参考帧中预测到的。但是可以从后向参考帧图像中预测，因此采用双向预测能大大地提高编码效率。另一方面，采用双向预测，计算复杂大大增加，同时需要有更多的存储器来存储参考帧图像，在视频实时通信应用中要有选择地使用。3.4 基于块的运动估计与补偿基于单个像素的帧间预测在实际操作中没有任何意义，因为不仅需要为每一个像素的预测误差分配比特，而且还要为每一个像素的运动矢量分配比特。不但起不到预测编码压缩数据的目的，甚至有可能比DPCM编码还要更多的比特。因此，在实际中应用更多的是基于块的运动补偿帧间预测编码。其原理如图3.8所示。图3.8 基于块的运动估计与补偿原理图基于块的运动补偿帧间预测编码主要包括以下四个部分：（1）块大小的选择一般来说，在以像素而不是以对象来描述图像或视频序列的编码技术中，块不是按照对象区域来划分的，而是按照给定的尺寸来确定的，如44块，88块或1616块。这种块的划分方法可能把一个运动物体的一部分划分到一个编码块中，其他部分划分到另一编码块中。块的大小对于预测编码的残差将会有很大的影响。（2）运动估计运动估计的目的在于计算出运动矢量。认为每一个宏块中的像素都是做同样的运动。然后在参考帧中按一定的判断准则寻找与编码块相匹配的宏块，就可以得到运动矢量，运动矢量会被发送到熵编码器中。（3）运动补偿由运动矢量建立当前预测编码块和重建帧预测块之间未知对应关系，从而建立了预测关系。图3.9是运动补偿的分类。图3.9 运动补偿分类（a）全局运动补偿 （b）基于像素的运动补偿（c）基于块的运动补偿 （d）基于区域的运动补偿（4）补偿后的预测误差编码对运动补偿后的预测误差信号变换。量化后进行熵编码，发送到信道上传输。值得注意的是，在计算运动估计和运动补偿时，是选择已编码的原始图像作为参考帧还是选择已编码图像的重建帧作为参考帧，结果稍有不同，但预测方法完全相同。3.5 运动估计算法现在的运动估计算法主要有像素递归法和块匹配法。像素递归法因为运算复杂，相对用的较少，基本都是在使用块匹配法。3.5.1 块匹配的准则目前衡量匹配好坏的准则由如下三种：（1）归一化互相关函数；（2）均方误差；（3）帧间绝对差。原则上采用三者之一均可以，其差别不大。（1）归一化互相关函数； （3-2）变化，不断计算，当相关函数达到最小值时，那么它的值就被认定为子块的水平和垂直位移值。由式3-2可知，其计算工作量很大，实际应用时常把式3-2简化为 （3-3）或者 （3-4）（2） 均方误差： （3-5）（3） 帧间绝对差： （3-6）不断变化，不断计算、或者等匹配准则，当匹配函数值达到最小值时，那么参考帧中的相应块就为最佳匹配块，为运动矢量。3.5.2 全搜索法全搜索法就是在搜索区域内搜索每一个像素点，其算法相对简单。按道理全搜索应该是效果最好的运动估计算法。搜索流程如图3.10所示。图3.10 全搜索法流程图3.5.3 三步法三步法是应用相当广泛的一种次优的运动估计搜索算法。三步法主要就是设定搜索区域后，逐步缩小搜索步长以接近目标位置。 图3.11表示了三步法的搜索，具体的过程如下：第一步：搜索中心设在块的中心，以搜索范围一半长度为步长，步长为4，搜索图3.11中标有“1”的九个位置，根据最小MAD值来确定下一步搜索区域的搜索中心。第二步：以第一步中求得的匹配点为中心，步长为2，搜索图3.11的八个标有“2”位置为中心的块与当前块进行匹配，根据最小的MAD值确定下一步搜索区域的搜索中心。第三步：以第二步中求得的最佳匹配点为中心，步长为1，将图3.11中的八个标有“3”位置为中心的块与当前块进行匹配，根据最小的MAD值确定所要找的最佳匹配点。它与当前块的中心的偏移量即为估计的运动矢量。图3.11 三步法示意图3.5.4 全搜索法和三步法的比较通常情况下，用全搜索法会得到最为理想的结果，但用时会较长。而利用三步法等快速算法可以节省用时，下面是两种算法的仿真比较。（1）全搜索仿真结果图3.12第一帧视频 图3.13第二帧视频图3.14 帧间残差（2）三步法仿真效果 图3.15 第一帧视频 图3.16 第二帧视频图3.17 帧间残差从全搜索法的帧间残差可以看出，效果很好，而三步法的帧间残差的效果同样也是可以的，两者的区别并不是很大。但是由于全搜索法需要为块中的每个像素都要进行匹配和赋予一个运动向量，所以导致运算量加大，运算时间较长，上面视频的搜索用时就是1.33s。而三步法只需要为一个整块赋予一个运动向量就行，所以运算时间较短，上幅图像搜索时用时0.87s，用时大为减少。在选择搜索算法时，既需要考虑搜索效果，同样也需要注意到用时的多少，特别是对一些实时性要求很高的标准。所以通常在选择搜索算法时会选择三步法等快速算法。3.6 分块大小对残差图像的影响分块大小对于图像残差的影响主要体现在块的大小对残差能量的影响和对计算速度的影响。从下面的图像与图3.7的对比中可以看出，经过运动估计和补偿的视频帧的能量已经减少了很多。通常情况下，块越小残差图像所含的能量就越小。从下面三幅图的对比中可以看出，44的残差图的能量最小。但是块越小将会在搜索时，搜索的块增多，导致计算量的增加。计算量的增加有可能造成得不偿失的现象，反而带来数据量的增加。所以我们在分块时，必须在残差能量和计算量之间做出平衡。一种解决方法是根据图像特性调整分块的大小，例如对平缓均匀的图像区域采用大尺寸分块，而对细节多，运动复杂的图像区域采用小尺寸分块。图3.18 44分块运动补偿的残差图像图3.19 88 分块运动补偿的残差图像图3.20 1616 分块运动补偿的残差图像3.7 离散余弦变换离散余弦变换就是将NN的残差图像X用变换矩阵A变换成NN的系数矩阵Y。NN样本块的正向DCT（FDCT）变换如下： (3-7)反向DCT（IDCT）如下： （3-8）其中X是样本矩阵，Y是变换后的系数矩阵，A是NN变换矩阵。A的各个元素如下： （3-9）其中：公式（37）和（38）也可以写成以下求和形式： （3-10） （3-11）图3.21 显示了从一幅图像中选取了一个44子块进行DCT变换的结果。图3.21 DCT变换过程（a）原图；（b）选取44大小子块；（c）DCT变换结果经变换后，最低频的就是DC系数，表示信号的平均值，其他不同频率相对应的称之为AC系数。其中DC系数对实际信号贡献最大，在重建图像时也最为重要，AC系数的高频部分逐渐趋于0。从图中我们可以看到，原来的16个像素值变成了16个DCT系数，并没有达到压缩的目的。当解码器采用部分变换系数重建图像时，我们就可以看到DCT变换带来的压缩效果了。如图3.22所示，当只解码一个DC系数得到a。解码两个重要的DC系数是b，解码五个重要DC系数的图像已开始接近原图像了。如果去掉一些不重要的系数，就可以用较少的变换系数来描述整个图像块，同时保证重建后的图像质量下降较小。图3.22 由不同数目DC系数重构的图像（a）由1个DC系数重构的图像；（b）由2个DC系数重构的图像；（c）由3个DC系数重构的图像；（d）由5个DC系数重构的图像；3.8 量化图像经过空域模块变换后，无论是离散余弦变换还是离散小波变换，输出的是包含少数非零和大量的零系数的稀疏矩阵。这些稀疏矩阵在存储和传输之前需要尽可能紧凑的编码。所以在熵编码之前必须进行重排序（把非零系数集中起来）并对零系数进行有效的表示。下面以DCT 变换后的系数矩阵为例说明这个过程。首先，DCT 系数的系数分布有一定的规律，图像或残差块的重要的DCT 系数一般位于DC（0，0）系数附近的低频区域。非零系数集中在左上角，其分布在水平方向和垂直方向大致是对称的。接下来要做的是对块中的DCT 系数进行重排序，把非零系数集中在一起，使剩下的零系数能更加有效的表示。最优的重排序路径（扫描顺序）依赖于非零的DCT 系数的分布。对一般的典型帧块，适合的扫描顺序是从左上角开始的Zigzag 扫描。按照图3.23的扫描顺序，所有的量化系数都被拷贝到一维数组。非零系数集中在数组的开始，其后跟着零序列。图3.23 Zigzag 扫描顺序重排序过程的输出是一个数组，这个数组在开始的头部集中了一个或多个非零系数，其后跟着一串零系数。大量的零系数应该使用更加紧凑的方式来表示。一般情况都是采用游程编码来实现的。用一系列的（run，lever）对来表示数组，其中run 表示非零系数前的零的个数，lever 表示非零系数的大小。例如：输入数组为：18，0，0，3，5，6，0，0，0，0，7编码输出值为（0，18），（2，3），（0，5），（0，6），（4，7）每个输出值（run，lever）对被熵编码器当作单独的符号进行编码。DCT系数的高频部分通常被量化为0，所以重排序的块通常都是以0 结束。一个特殊的情况需要表示块中最后的非零系数的位置。在所谓的“二维”游程编码中，除了每个runlever 对之外，还有一个单独的码符号：“last”，它表明了非零系数的结束。在“三维”runlever 编码中，每个符号用三个值编码，即run，lever 和last。在上面的例子中，如果7 是最后的非零系数，编码值为：（0，18，0）（2，3，0）（0，5，0）（0，6，0）（4，7，1）最后的1 表示这是块中的最后一个非零系数。3.9 熵编码3.9.1 霍夫曼编码 霍夫曼编码的理论依据是变字长VLC编码理论。就是给出现概率大的信号赋予短字长的输出码字，而给出现概率小的信号赋予码字长的二进制码字。霍夫曼编码的具体方法归纳如下：先将出现信号的概率按大小排队，把最小的两个概率相加得到新的概率，将新的概率和剩余的概率在重新进行排序，再将最小的两个概率相加，不断循环直到变成“1”。每次都需要为相加的两个概率赋值“1”和“0”，一直到最后变成“1”，按照编码顺序，将“1”和“0”按最低位到最高位排序，就是该信号的霍夫曼编码。假定以一幅2020像素的图像共有5个灰度级s1，s2，s3，s4，s5，它们在此图像中出现的概率依次为0.4，0.175，0.15，0.15，0.125。其霍夫曼编码过程如图3.24所示。图3.24 霍夫曼编码示意图在图3.24中，先逐步完成两个小概率的相加合并，然后反过来逐步向前进行编码，每一步有两个分支，各赋予一个二进制，这里对概率大的赋码字1，概率小的赋码字0。这样从右到左得到如表3.1的编码表。表3.1 霍夫曼编码表信源符号出现概率码字码长信源符号出现概率码字码长S10.401S40.151013S20.1751113S50.1251003S30.151103经霍夫曼编码后，其平均码长为 （3-12）其熵，由此可知，霍夫曼编码已经比较接近该图像的熵值了。3.9.2 算术编码理论上来讲，霍夫曼编码对信源数据编码可以获得最佳的编码效果，但是在实际应用中，由于计算存储和处理的最小单位是1个“比特”，因此在一些情况下，实际的压缩效果往往不能达到理论上的压缩比。为了解决计算机必须以整数位进行编码的问题，人们提出了算术编码。算术编码的算法思想如下：(1）对一组信源符号按照符号的概率从大到小排序，将0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。(2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。(3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。(4）最后的编码输出数就是编码好的数据。3.9.3 霍夫曼编码与算术编码的比较霍夫曼编码是一种不等长的最佳编码方法，这里的最佳是对相同概率分布的信源来说，他的平均码字长度比其他任何一种有效编码都短。但是存在两方面的不足之处，首先，霍夫曼编码需要知道信源的概率分布，这点通常是无法做到的。对于图像只能采用大量数据统计后得到的近似分布来代替，而实际编码的图像类型其系数分布总有差异，这导致应用时无法达到最佳性能。其次，分配给最大概率出现的信号符号最少也是1bit，不能分配比1bit更小的码字，限制了进一步降低码率14。算术编码也有两个明显的问题：一是编码时需要等所有的符号都输入到编码器之后，才能得到输出值；二是当要编码的输入信息符号越来越多或者需要解码的码流越来越长时，分割区间的长度会越来越小，要处理更长序列的信源或者更长的码流时，都必须要有任意精度的算术表示，这是不可能实现的。对于算术编码，不需要预先设置码本，另外可以自适应地改变信源统计而使用不同概率模型。但是其计算量要比霍夫曼编码大。在可接受的计算量要求下，算术编码比霍夫曼编码有更高的编码效率。3.10 本章小结本章主要介绍了视频压缩算法的基础模型-DPCM/DCT模型，对预测编码、运动估计与补偿、离散余弦变换和熵编码等各种基础算法进行了研究。并对一些算法进行了比较。4. 压缩算法在视频监控中的应用4.1 视频压缩在监控中的具体应用在进行编码软件设计时，必须要考虑到监控图像的特性和对实时性的要求，还需要考虑到网络的不稳定性。视频监控中的原始图像有一个显著的特点，即只有少数对象在运动，大部分的背景对象基本是静止不动的。因为MPEG-4编解码的基本单元都是基于是对象的，所以可以利用图像分割技术将运动物体对象和背景对象分割开。利用压缩比较高、损失较大的方法对背景对象进行编码，而运动物体对象就采用压缩比较低、损失较小的方法编码。在此基础上，我们采用MPEG-4中Sprite 编