Huffman编码器毕业论文

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。 因此，大家都会发现，理解甚至修改这个编码都是很容易的。 背景 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 编码使用 我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。 bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); 要点说明 速度 为了让它()快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 然后，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 现在，构造哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。 // parent node pNode = &nodes[nParentNode++]; // pop first child pNode->pLeft = PopNode(pNodes, nBackNode--, false); // pop second child pNode->pRight = PopNode(pNodes, nBackNode--, true); // adjust parent of the two poped nodes pNode->pLeft->pParent = pNode->pRight->pParent = pNode; // adjust parent frequency pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。 接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中： int nDesIndex = 0; // loop to write codes for(nCount = 0; nCount < nSrcLen; nCount++) { *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; } (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位. 注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0; DWORD nCode; while(nDesIndex < nDesLen) { nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; }

本文作者王军先生，电子科技大学通信与信息工程学院通信抗干扰技术重点实验室助教、硕士；吴军蹄女士，通信与信息工程学院教授。3 视频压缩标准视频编码标准主要由ITU-T和ISO/IEC开发。前者已经发布了视频会议标准、 、 ，并且准备进行远期编码标准的开发，以期望获得更大的编码效率。ISO/IEC的标准系列是大家熟悉的MPEG家族。包括：(1)MPEG-1(1988～1992)，可以提供最高达的数字视频，只支持逐行扫描；(2)MPEG-2(1990～1994)，支持的带宽范围从2Mbps到超过20Mbps，MPEG-2后向兼容MPEG-1，但增加了对隔行扫描的支持，并有更大的伸缩性和灵活性；(3)MPEG-4(1994～1998)，支持逐行扫描和隔行扫描，是基于视频对象的编码标准，通过对象识别提供了空间的可伸缩性；(4)MPEG-7(1996～2000)，是多媒体内容描述接口，与前述标准集中在音频/视频内容的编码和表示不同，它集中在对多媒体内容的描述。除了上述通用标准外，还存在很多专用格式，比较流行的有：C-Cube的M-JPEG、Intel的IVI(tm)(Indeo Video Interactive)、Apple的QuickTime(tm)、Microsoft的 Media Player(tm)和RealNetworks的RealPlayer(tm)。二 数字视频传输根据承载网络的变化和视频服务的区别，可以将数字视频的传输分为四类：数字电视、宽带视频通信、Internet视频流通信、蜂窝移动视频通信。虽然这四种通信体系下对视频通信的协议和服务有不同的要求，但对于实时应用下述几点是必须满足的：(1)传输必须限制在一定时限内完成；(2)必须对端到端的抖动建议限制；(3)必须有相应的同步机制；(4)在分组网络中应当有较高的优先级。1 数字电视广播欧洲走在了全球DVB开发最前面，将其采纳为数字电视DTV的标准；在美国，ATSC采用了HDTV；在亚太地区，日本采用了基于DVB和ATSC的ISDB-T，澳大利亚采用了DVB，韩国则采用了ATSC标准，我国也在制定数字电视的标准，并进行了现场试验。下面我们以欧洲的DTV标准为主分别介绍DTV系统规范和传输技术。系统规范根据传输系统的不同，DTV系统分为三类：陆基系统 DTV-T、卫星系统 DTV-S、有线系统 DTV-C。这三类DTV系统虽然各有不同，但也有公共的特性，MPEG-2视频和音频编码系统是所有DTV系统的基础。系统采用MPEG-2将数据压缩并组装成分组，称为净荷。对净荷采用Reed-Solomon前向纠错编码，降低信号传输中引入的误码。卫星系统采用单载波信号，采用外部编码的同时，内部加入了打孔卷积编码，从而又增加了一层误码纠错能力，根据带宽的变化和采用的特定设备，编码数据是可调整的，信号采用QPSK方式调制。陆基系统联合使用码正交频分复用 COFDM或者QPSK或QAM进行射频调制，采用了和卫星系统相似的打孔卷积编码。有线系统采用了QAM调制方案，不需要附加的内部编码来降低误码，系统优化采用64-QAM。b. DTV系统传输结构DTV系统广播和接收的基本结构由三个子系统构成：(1)信源编码和压缩子系统，通过ADC接受模拟视频和音频信号并将其转换成数字比特流，然后通过MPEG-2进行压缩，并加入控制和辅助数据；(2)服务复用和传递子系统，复用将视频和音频及辅助数据流联合构成长188字节的分组，并加上标记，分组构成单个数据流，采用MPEG-2传递系统语法控制这些复用任务；(3)传输子系统，包括对复用数据流的信道编码和调制。2 宽带视频通信这里讨论的宽带视频通信主要是指基于宽带核心网络和宽带接入技术的MPEG-2视频通信。为了满足实时视频通信对带宽的需求，核心网络通常采用宽带光纤网络，可以是ATM或者基于MPLS的宽带IP与ATM的结合，最后一公里的宽带接入的方法有光纤到户、光纤到楼双绞线到户及ADSL，最近也提出了宽带无线接入技术。通常，来自多个链路的数据业务在数字用户线路接入复用器(DSLAM)汇总。DSLAM将ATM业务路由到家中的ADSL接收器单元，同时，滤掉低频段的旧电话业务POTS 。在MPEG-2视频的情形下，ATM边界设备减轻信元的时延抖动的能力至关重要。ATM必须应付数据传输的需要并提供管理每个视频流的功能，特别要满足按序提取视频分组的要求。为了补偿网络传输延时，ATM网络边界设备必须精心设计以处理MPEG交换和抖动管理。本地MPEG-2视频流通过数字视频广播异步串行接口传输。ATM边界设备将MPEG-2多节目传输流(MPTS)或单节目传输流(SPTS)拆解到节目层并最终到分组标记(PID)层。在PID层，不同的节目流可以重新排序并复用进另外的MPTS。在ATM边界接收端，另外的边界设备管理ATM信元流，并重构SPTS或MPTS。本地的服务分布网络负责在本地的UTP网络分发视频内容。功能强大的MPEG-2压缩算法结合智能的ATM边界设备允许最后接入利用DSL技术作为视频分发的接入机制。（未完待续）相关信息：1.前言数字视频产品需求近些年出现猛增。主流应用包括视频通信、安全监控与工业自动化，而最热门的要算娱乐应用，如 DVD、HDTV、卫星电视、高清 (HD) 机顶盒、因特网视频流、数码相机与 HD 摄像机、视频光盘库 (video jukebox)、高端显示器（LCD、等离子显示器、DLP）以及个人摄像机等。众多精彩的新应用目前也处于设计或前期部署中，例如针对家庭与手持设备及地面／卫星标准（DVB-T、DVB-H、DMB）的高清 DVD（蓝光／HD-DVD）和数字视频广播、高清视频电话、数码相机以及 IP 机顶盒。由于手持终端计算能力的提高以及电池技术与高速无线连接的发展，最终产品的移动性与集成性也在不断提高。视频压缩是所有令人振奋的、新型视频产品的重要动力。压缩－解压（编解码）算法可以实现数字视频的存储与传输。典型的编解码器要么采用行业标准，如 MPEG2、MPEG4、 与 AVS，要么采用专有算法，如 On2、Real Video、Nancy与Windows Media Video (WMV) 等。WMV 是个例外——它最初是微软公司的专有算法，而现在则以 VC-1 的新名称在业界实现了标准化。编解码技术在过去十年中不断改进。最新的编解码技术（ 与 VC-1）代表着第三代视频压缩技术。这两种编解码技术利用如可编程 DSP 与ASIC 等低成本 IC 的处理能力，都能够达到极高的压缩比。不过，为具体应用选择正确的编解码器并优化其实时处理仍然是一项巨大的挑战。最佳的设计必须权衡压缩效率及可用的计算能力。此外，如何在计算能力有限的情况下获得最佳压缩效率也是一门大学问。在本文中，我们首先概述视频编码的主要概念，同时介绍传统压缩标准。然后我们重点介绍其中包括 、WMV9/VC-1与AVS 等在内的最新编解码技术的功能，此外，还将深入探讨压缩能力与复杂性之间的权衡。最后，讨论市场中可能会影响主流视频编解码器未来的实时处理与主要趋势。数字视频的主要挑战在于原始或未压缩的视频需要存储或传输大量数据。例如，标准清晰度的 NTSC 视频的数字化一般是每秒 30 帧速率，采用 4:2:2 YcrCb 及 720(480，其要求超过 165Mbps 的数据速率。保存 90 分钟的视频需要 110GB 空间，或者说超过标准 DVD-R 存储容量的 25 倍。即使是视频流应用中常用的低分辨率视频（如：CIF：352x288 4:2:0、30 帧/秒）也需要超过 的数据速率，这是 ADSL 或 3G 无线等宽带网络速度的许多倍。目前的宽带网可提供 1～10Mbps 的持续传输能力。显然数字视频的存储或传输需要采用压缩技术。视频压缩的目的是对数字视频进行编码——在保持视频质量的同时占用尽可能少的空间。编解码技术理论依据为信息理论的数学原理。不过，开发实用的编解码技术需要艺术性的精心考虑。3. 压缩权衡在选择数字视频系统的编解码技术时需要考虑诸多因素。主要因素包括应用的视频质量要求、传输通道或存储介质所处的环境（速度、时延、错误特征）以及源内容的格式。同样重要的还有预期分辨率、目标比特率、色彩深度、每秒帧数以及内容和显示是逐行扫描还是隔行扫描。压缩通常需要在应用的视频质量要求与其他需求之间做出取舍。首先，用途是存储还是单播、多播、双向通信或广播？对于存储应用，到底有多少可用的存储容量以及存储时间需要多久？对于存储之外的应用，最高比特率是多少？对于双向视频通信，时延容差或容许的端到端系统延迟是多少？如果不是双向通信，内容需要在脱机状态提前完成编码还是需要实时编码？网络或存储介质的容错能力如何？根据基本目标应用，不同压缩标准以不同方式处理这些问题的权衡。另一方面是需要权衡编解码实时处理的成本。如 或 WMV9/VC-1等能够实现较高压缩比的新算法需要更高的处理能力，这会影响编解码器件的成本、系统功耗以及系统内存。4. 标准化机构在视频编解码技术定义方面有两大标准机构。国际电信联盟 (ITU) 致力于电信应用，已经开发了用于低比特率视频电话的 标准，其中包括 、、 与 ；国际标准化组织 (ISO) 主要针对消费类应用，已经针对运动图像压缩定义了 MPEG 标准。MPEG 标准包括 MPEG1、MPEG2 与 MPEG4。图 1 说明了视频编解码标准的发展历程。MPEG 与 ISO 根据基本目标应用往往做出稍有不同的取舍。有时它们也会开展合作，如：联合视频小组 (JVT)，该小组定义了 编解码技术，这种技术在 MPEG 系列中又被称为 MPEG4-Part 10 或 MPEG4 高级视频编解码 (AVC)。我们在本文中将这种联合标准称为 。同样， 对应 MPEG2，而 基本规范类 (Baseline Profile) 技术在原理方面与 MPEG4 简单类 (Simple Profile) 编解码技术存在较多重复。标准对编解码技术的普及至关重要。出于规模经济原因，用户根据可承受的标准寻找相应产品。由于能够保障厂商之间的互操作性，业界乐意在标准方面进行投资。而由于自己的内容可以获得较长的生命周期及广泛的需求，内容提供商也对标准青睐有加。尽管几乎所有视频标准都是针对少数特定应用的，但是在能够适用的情况下，它们在其他应用中也能发挥优势。图1：ITU 与 MPEG 标准的发展历程 [10]为了实现更好的压缩及获得新的市场机遇，ITU 与 MPEG 一直在不断发展压缩技术和开发新标准。中国最近开发了一种称为 AVS 的国家视频编码标准，我们在后面也会做一介绍。目前正在开发的标准包括 ITU/MPEG 联合可扩展视频编码 (Joint Scalable Video Coding)（对 H264/ AVC 的修订）和MPEG 多视角视频编码 (Multi-view Video Coding)。另外，为了满足新的应用需求，现有标准也在不断发展。例如， 最近定义了一种称为高精度拓展 (Fidelity Range Extensions) 的新模式，以满足新的市场需求，如专业数字编辑、HD-DVD 与无损编码等。除了 ITU 与 ISO 开发的行业标准以外，还出现了几种专用于因特网流媒体应用、广受欢迎的专有解决方案，其中包括 Real Networks Real Video (RV10)、Microsoft Windows Media Video 9 (WMV9) 系列、ON2 VP6 以及 Nancy。由于这些格式在内容中得到了广泛应用，因此专有编解码技术可以成为业界标准。2003 年 9 月，微软公司向电影与电视工程师学会 (SMPTE) 提议在该机构的支持下实现 WMV9 位流与语法的标准化。该提议得到了采纳，现在 WMV9 已经被 SMPTE 作为 VC-1 实现标准化。5. 视频编码原理我们感兴趣的所有视频标准都采用基于模块的处理方式。每个宏模块一般包含 4 个 8(8 的光度块和 2 个 8(8 的色度块（4:2:0 色度格式）。视频编码基于运动补偿预测（MC），变换与量化及熵编码。图 2 说明的是一种典型的、基于运动补偿的视频编解码技术。在运动补偿中，通过预测与最新编码的（"参考"）视频帧处于同一区域的视频帧中各宏模块的像素来实现压缩。例如，背景区域通常在各帧之间保持不变，因此不需要在每个帧中重新传输。运动估计 (ME) 是确定当前帧——即与它最相似的参考帧的 16(16 区域中每个 MB 的过程。ME 通常是视频压缩中最消耗性能的功能。有关当前帧中各模块最相似区域相对位置的信息（"运动矢量"）被发送至解码器。MC 之后的残差部分分为 8(8 的模块，各模块综合利用变换编码、量化编码与可变长度编码技术进行编码。变换编码（如：离散余弦变换或 DCT）利用残差信号中的空间冗余。量化编码可以消除感知冗余 (perceptual redundancy) 并且降低编码残差信号所需要的数据量。可变长度编码利用残差系数的统计性质。通过 MC 进行的冗余消除过程在解码器中以相反过程进行，来自参考帧的预测数据与编码后的残差数据结合在一起产生对原始视频帧的再现 。图 2：标准运动补偿视频编码在视频编解码器中，单个帧可以采用三个模式中的一个进行编码 —— 即 I、P 或 B 帧模式（见图 3）。几个称为 Intra (I) 的帧单独编码，无需参考任何其他帧（无运动补偿）。某些帧可以利用 MC 编码，以前一个帧为参考（前向预测）。这些帧称为预测帧 (P)。B 帧或双向预测帧通过之前的帧以及当前帧的后续帧进行预测。B 帧的优势是能够匹配堵塞在采用前向预测的上一帧中的背景区域。双向预测通过平衡前向及后向预测可以降低噪声。在编码器中采用这种功能会要求更多处理量，因为必须同时针对前向及后向预测执行 ME，而这会明显使运动估计计算需求加倍。为了保存两个参考帧，编码器与解码器都需要更多内存。B 帧工具需要更复杂的数据流，因为相对采集及显示顺序而言，帧不按顺序解码。这个特点会增加时延，因此不适合实时性较高的应用。B 帧不用于预测，因此可以针对某些应用进行取舍。例如，在低帧速应用中可以跳过它们而不会影响随后 I 与 P 帧的解码。图3：I、P 与 B 帧间预测图示6. 传统视频编码标准 编制的 [2] 标准是第一个主流视频压缩标准。它主要针对双工视频会议应用，是为支持 40kpbs～2Mbps 的 ISDN 网络而设计的。 支持 352(288 (CIF) 及 176(144 (QCIF) 分辨率，色度分辨率二次采样为 4:2:0。由于可视电话需要同步实时编解码，因此复杂性设计得较低。由于主要用于对延迟敏感的双向视频，因此 仅允许采用 I 与 P 帧，而不允许 B 帧。 采用基于块的 DCT 进行残差信号的变换编码。DCT 把像素的每个 8(8 块映射到频域，产生 64 个频率成分（第一个系数称为 DC，其他的称为 AC）。为了量化 DCT 系数， 在所有 AC 系数中采用固定的线性量化。量化后的系数进行行程编码，其可以按非零系数描述量化的频率，后面跟随一串零系数，在最后一个非零值之后以块代码结束。最后，可变长度编码 (Huffman) 将运行级别对 (run-level pair) 转换成可变长度编码 (VLC)，其比特长度已针对典型概率分布进行过优化。基于标准块的编码最终产生模块化视频。 标准利用环路滤波避免这种现象。在模块边缘采用的简单 2D FIR 滤波器用于平滑参考帧中的量化效应。必须同时在编码器及解码器中精确地对每个比特应用上述滤波。MPEG-1MPEG-1[3] 是 ISO 开发的第一个视频压缩算法。主要应用是数字媒体上动态图像与音频的存储与检索，如速率为 、采用 SIF 分辨率（352(240 - 或者 352(288 - 25 fps）的VCD。MPEG-1 与 相似，不过编码器一般需要更高的性能，以便支持电影内容的较高运动性而不是典型的可视电话功能。与 相比，MPEG1 允许采用 B 帧。另外它还采用自适应感知量化，也就是说，对每个频段采用单独的量化比例因子（或等步长），以便优化人们的视觉感受。MPEG-1 仅支持逐行视频，因此新标准——MPEG2 已经开始做出努力，同时支持分辨率及比特率更高的逐行与隔行视频。MPEG-2/[4] 专门针对数字电视而开发，很快成为了迄今最成功的视频压缩标准。MPEG-2 既能够满足标准逐行视频的需求（其中视频序列由一系列按一定时间间隔采集的帧构成），又能够满足电视领域常用的隔行视频的需求。隔行视频交替采集及显示图像中两组交替的像素（每组称为一个场）。这种方式尤其适合电视显示器的物理特性。MPEG2 支持标准的电视分辨率，其中包括：针对美国和日本采用的 NTSC 制式隔行 720(480 分辨率，每秒 60 场，以及欧洲和其他国家采用的PAL 制式的 720(576 分辨率，每秒 50 场。MPEG-2 建立在 MPEG-1 基础之上，并具备扩展功能，能支持隔行视频及更宽的运动补偿范围。由于高分辨率视频是非常重要的应用，因此 MPEG-2 支持的搜索范围远远大于 MPEG-1。与之前的标准相比，它显著提高了运动估计的性能要求，并充分利用更宽搜索范围与更高分辨率优势的编码器需要比 和 MPEG-1 高得多的处理能力。MPEG2 中的隔行编码工具包含优化运动补偿的能力，同时支持基于场和基于帧的预测，而且同时支持基于场和基于帧的 DCT/IDCT。MPEG-2 在 30:1 左右的压缩比时运行良好。MPEG-2 在 4-8Mbps 时达到的质量适合消费类视频应用，因此它很快在许多应用中得到普及，如：数字卫星电视、数字有线电视、DVD 以及后来的高清电视等。另外，MPEG-2 增加了分级视频编码工具，以支持多层视频编码，即：时域分级、空域分级、SNR 分级以及数据分割。尽管 MPEG-2 中针对分级视频应用定义了相关类别 (profile)，不过支持单层编码的主类 (Main Profile) 是当今大众市场中得到广泛应用的唯一 MPEG-2 类。MPEG-2 通常称为 MPEG-2 主类。MPEG-2 解码最初对于通用处理器及 DSP 具有很高的处理要求。优化的固定功能 MPEG-2 解码器开发已问世，由于使用量较高，成本已逐渐降低。MPEG2 证明低成本芯片解决方案的供应是视频编解码标准成功和普及的关键。[5] 在 之后得到开发，主要是为了以更低的比特率实现更高的质量。其主要目标之一是基于普通 电话调制解调器的视频。目标分辨率是 SQCIF (128(96)～CIF (352(288)。其基本原理与 大同小异。 的运动矢量在两个方向上允许是 1/2 的倍数（“半像素”），参考图像以数字方式内插到更高的分辨率。这种方法可以提高 MC 精度及压缩比。MV 可采用更大的范围。为不同方案提供许多新的选项，包括：* 4 个运动矢量——每个块采用一个运动矢量，而非整个 MB 采用单个运动矢量。* 3D VLC：Huffman 编码——将块结束 (EOB) 指示符与每个运行级别对结合在一起。这种功能主要用于低比特率，这时大多时候只有一、两个编码系数。尽管存在这些功能，但是仍然很难在普通电话线上实现理想的视频质量，而且目前基于标准调制解调器的可视电话仍然是一个难题。不过，由于 一般情况下可提供优于 的效率，它成为了电视会议首选的算法，但是，为了兼容旧系统，仍然需要支持 。 逐渐发展成为了 ，其增加了可选的附件，为提高压缩并实现分组网的鲁棒性提供支持。 及其附件构成了 MPEG-4 中许多编码工具的核心。MPEG-4MPEG-4[6] 由 ISO 提出，以延续 MPEG-2 的成功。一些早期的目标包括：提高容错能力以支持无线网、对低比特率应用进行更好的支持、实现各种新工具以支持图形对象及视频之间的融合。大部分图形功能并未在产品中受到重视，相关实施主要集中在改善低比特率压缩及提高容错性上。.MPEG-4 简化类 (SP) 以为基础，为改善压缩增加了新的工具，包括：* 无限制的运动矢量：支持对象部分超出帧边界时的预测。* 可变块大小运动补偿：可以在 16(16 或 8(8 粒度下进行运动补偿。* 上下文自适应帧内 DCT DC/AC 预测：可以通过当前块的左右相邻块预测 DC/AC DCT 系数。* 扩展量化 AC 系数的动态范围，支持高清视频：从 的 [-127:127] 到 [-2047, 2047]。增加了容错功能，以支持丢包情况下的恢复，包括：* 片断重同步 (Slice Resynchronization)：在图像内建立片断 (slice)，以便在出现错误后更快速的进行重新同步。与 MPEG-2 数据包大小不同，MPEG4 数据包大小与用于描述 MB 的比特数量脱离了联系。因此，不管每个 MB 的信息量多少，都可以在位流中按相同间隔进行重新同步。* 数据分割：这种模式允许利用唯一的运动边界标记将视频数据包中的数据分割成运动部分和 DCT 数据部分。这样就可以实现对运动矢量数据更严格的检查。如果出现错误，我们可以更清楚地了解错误之处，从而避免在发现错误情况下抛弃所有运动数据。* 可逆 VLC：VLC 编码表允许后向及前向解码。在遇到错误时，可以在下一个slice进行同步，或者开始编码并且返回到出现错误之处。* 新预测 (NEWPRED)：主要用于在实时应用中实现快速错误恢复，这些应用中的解码器在出现丢包情况下采用逆向通道向解码器请求补充信息。MPEG-4 高级简化类 (ASP) 以简化类为基础，增加了与 MPEG-2 类似的 B 帧及隔行工具（用于Level 4 及以上级别）。另外它还增加了四分之一像素运动补偿及用于全局运动补偿的选项。MPEG-4 高级简化类比简化类的处理性能要求更高，而且复杂性与编码效率都高于 MPEG-2。MPEG-4 最初用于因特网数据流，例如，已经被 Apple 的 QuickTime 播放器采用。MPEG-4 简化类目前在移动数据流中得到广泛应用。MPEG-4 ASP 是已经流行的专有 DivX 编解码器的基石。工具与压缩增益当我们查看 、MPEG1、MPEG2 与 视频编解码技术中引入的功能时，明显可以发现几种基本技巧提供了大部分压缩增益。图 4 说明这些技巧及其相关效果。与 4 个运动矢量以及四分之一像素运动补偿等工具相比，运动补偿（整数像素与半像素）的效果显然更为突出。图 4：基本技巧的效果：1) 无 MC；2) 增加 Skip 模式构成 CR 编码器；3) 仅允许零 MV；4) 允许整数像素 MC；5) 允许半像素 MC；6) 允许 4-MV；7) 允许四分之一像素MC。如欲了解有关详细说明，敬请参见 [7]。7. MPEG4-AVC视频编码技术在过去几年最重要的发展之一是由 ITU 和 ISO/IEC 的联合视频小组 (JVT) 开发了 AVC[8] 标准。在发展过程中，业界为这种新标准取了许多不同的名称。ITU 在 1997 年开始利用重要的新编码工具处理 （长期），结果令人鼓舞，于是 ISO 决定联手 ITU 组建 JVT 并采用一个通用的标准。因此，大家有时会听到有人将这项标准称为 JVT，尽管它并非正式名称。ITU 在 2003 年 5 月批准了新的 标准。ISO 在 2003 年 10 月以 MPEG-4 Part 10、高级视频编码或 AVC 的名称批准了该标准。 在压缩效率方面取得了巨大突破，一般情况下达到 MPEG-2 及 MPEG-4 简化类压缩效率的大约 2 倍。在 JVT 进行的正式测试中 [9]， 在 85 个测试案例中有 78％ 的案例实现 倍以上的编码效率提高，77％ 的案例中达到 2 倍以上，部分案例甚至高达 4 倍。 实现的改进创造了新的市场机遇，如：* 600Kbps 的 VHS 品质视频。可以通过 ADSL 线路实现视频点播。* 高清晰电影无需新的激光头即可适应普通 DVD。 标准化时支持三个类别：基本类、主类及扩展类。后来一项称为高保真范围扩展 (FRExt) 的修订引入了称为高级类的 4 个附加类。在初期主要是基本类和主类引起了大家的兴趣。基本类降低了计算及系统内存需求，而且针对低时延进行了优化。由于 B 帧的内在时延以及 CABAC 的计算复杂性，因此它不包括这两者。基本类非常适合可视电话应用以及其他需要低成本实时编码的应用。主类提供的压缩效率最高，但其要求的处理能力也比基本类高许多，因此使其难以用于低成本实时编码和低时延应用。广播与内容存储应用对主类最感兴趣，它们是为了尽可能以最低的比特率获得最高的视频质量。尽管 采用与旧标准相同的主要编码功能，不过它还具有许多与旧标准不同的新功能，它们一起实现了编码效率的提高。图 5 的编码器框图总结了其主要差别，概述如下：帧内预测与编码： 采用空域帧内预测技术来预测相邻块邻近像素的 Intra-MB 中的像素。它对预测残差信号和预测模式进行编码，而不是编码块中的实际像素。这样可以显著提高帧内编码效率。帧间预测与编码： 中的帧间编码采用了旧标准的主要功能，同时也增加了灵活性及可操作性，包括适用于多种功能的几种块大小选项，如：运动补偿、四分之一像素运动补偿、多参考帧、通用 (generalized) 双向预测和自适应环路去块。可变矢量块大小：允许采用不同块大小执行运动补偿。可以为小至 4(4 的块传输单个运动矢量，因此在双向预测情况下可以为单个 MB 传输多达 32 个运动矢量。另外还支持 16(8、8(16、8(8、8(4 和 4(8 的块大小。降低块大小可以提高运动细节的处理能力，因而提高主观质量感受，包括消除较大的块化失真。四分之一像素运动估计：通过允许半像素和四分之一像素运动矢量分辨率可以改善运动补偿。多参考帧预测：16 个不同的参考帧可以用于帧间编码，从而可以改善视频质量的主观感受并提高编码效率。提供多个参考帧还有助于提高 位流的容错能力。值得注意的是，这种特性会增加编码器与解码器的内存需求，因为必须在内存中保存多个参考帧。自适应环路去块滤波器： 采用一种自适应解块滤波器，它会在预测回路内

以前编的一个霍夫曼编码，你可以参考一下：% b1; %%%输入代码中出现的字符，按ASCII排序% m1; %%%b1中字符在codes中首次出现的位置% n1; %%%codes中字符在b1中出现的位置function coding_callback(Incodes)global decodclc;digits(16);%%设置输出编码的小数点位数Incodes=input('please input the encoding string:\n','s');Incodes=['state tree'];[b1, m1, n1] = unique(Incodes, 'first');Incodes(sort(m1));length(b1);for ii=1:length(b1) a(ii)=length(find(n1(1:end)==ii)); rate(ii)=a(ii)/length(n1); %%%b1中每个字符出现的概率区间 low1(1)=0; %%%b1区间下限 high1(1)=rate(1); %%%b1区间上限 if ii>1 low1(ii)=high1(ii-1); high1(ii)=low1(ii)+rate(ii); endend% high1 %%%每个字符的上限% low1 %%%每个字符的下限% rate %%%每个字符所占有比例%%%%%编码过程%%%%%% judge=n1(1); rang(1)=high1(judge)-low1(judge); low(1)=low1(judge); high(1)=high1(judge);for jj=2:length(Incodes) judge=n1(jj); low(jj)=low(jj-1)+low1(judge).*rang(jj-1); %%%%codes中第jj个字符编码后的下限 high(jj)=low(jj-1)+high1(judge).*rang(jj-1); %%%%codes中第jj个字符编码后的上限 rang(jj)=high(jj)-low(jj); %%%%codes中第jj个字符编码后的区间endr=vpa(rang);x=vpa(low(length(Incodes)));y=vpa(high(length(Incodes)));decod=(x+y)./2set(decod,'string',num2str(decod));save x y r decod low1 high1 b1 Incodes rate