常见的视频编码详解 A VI所采用的压缩算法并无统一的标准。也就是说，同样是以A VI为后缀的视频文件，其采用的压缩算法可能不同，需要相应的解压软件才能识别和回放该A VI文件。除了Microsoft 公司之外，其他公司也推出了自己的压缩算法，只要把该算法的驱动(Codec)加到Windows 系统中，就可以播放用该算法压缩的A VI文件。最新流行的MPEG-4视频也借用A VI的名称，只要机器安装了它的编码解码，也能够实现正常的播放。这些A VI都能够在用Authorware 或PowerPiont开发的作品当中正常放映。各种编码Codec所生成的A VI文件的大小和质量是不同的，对系统和硬件要求也不同。 因此在压缩A VI时，必须根据计算机的软硬件情况，来考虑采用什么Codec算法，否则你的作品中视频放映是难以令人满意的。下面就是对各种常见编码解码Codec的说明。 常见的视频编码 1、Cinepak Codec by Radius 它最初发布的时候是用在386的电脑上看小电影，在高数据压缩率下，有很高的播放速度。利用这种压缩方案可以取得较高的压缩比和较快的回放速度，但是它的压缩时间相对较长。 2、Microsoft Video 1 用于对模拟视频进行压缩，是一种有损压缩方案，最高仅达到256色，它的品质就可想而知，一般还是不要使用它来编码A VI。 3、Microsoft RLE 一种8位的编码方式，只能支持到256色。压缩动画或者是计算机合成的图像等具有大面积色块的素材可以使用它来编码，是一种无损压缩方案。 4、Microsoft H.261和H.263 Video Codec 用于视频会议的Codec，其中H.261适用于ISDN、DDN线路，H.263适用于局域网，不过一般机器上这种Codec是用来播放的，不能用于编码。 5、Intel Indeo Video R3.2 所有的Windows版本都能用Indeo video 3.2播放A VI编码。它压缩率比Cinepak大，但需要回放的计算机要比Cinepak的快。 6、Intel Indeo Video 4和5
实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include
//选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++)
音视频编码技术报告 姓名: 学号： 学院(系):电子与信息工程学院 专业: 电子与通信工程 题目: 基于DCT变换的图像压缩技术的仿真
1.引言 在信息世界迅猛发展的今天, 人们对计算机实时处理图像信息的要求越来越高。如何在保证图像质量的前提下, 同时兼顾实时性和高效性成了一个值得关注的问题。于是, 对图像信息进行一定的压缩处理成为了一个不可或缺的环节。图像压缩是关于用最少的数据量来表示尽可能多的原图像的信息的一个过程。 本文主要研究基于DCT 变换的有损压缩编码技术。离散余弦变换, 简称DCT , 是一种实数域变换, 其变换核为余弦函数, 计算速度快。DCT 除了具有一般的正交变换性质外, 它的变换阵的基向量能很好地描述人类语音信号和图像 信号的相关特征。因此, 在对语音信号、图像信号的变换中,DCT 变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中, 都把DCT 作为其中的一个基本处理模块。而且对于具有一阶马尔柯夫过程的随机信 号,DCT 十分接近于Karhunen -Loeve 变换, 也就是说它是一种最佳近似变换。 2.图像压缩编码的简介 从信息论的角度看，图像是一个信源。描述信源的数据是信息量和信息量冗余之和。数据压缩实际上就是减少这些冗余量。图像编码压缩的方法目前有很多，其分类方法根据出发点不同而有差异。根据解压重建后的图像和原始图像之间是否具有误差（对原图像的保真程度），图像编码压缩分为无误差（亦称无失真、无损、信息保持）编码和有误差（有失真或有损）编码两大类。 无损压缩（冗余度压缩、可逆压缩）：是一种在解码时可以精确地恢复原图像，没有任何损失的编码方法，但是压缩比不大，通常只能获得1~5倍的压缩比。用于要求重建后图像严格地和原始图像保持相同的场合，例如复制、保存十分珍贵的历史、文物图像等。 有损压缩（不可逆压缩）：只能对原始图像进行近似的重建，而不能精确复原，适合大数工用于存储数字化了的模拟数据。压缩比大，但有信息损失，本文采用有损压缩。 DCT图像压缩编码可以概括成图2.1的框图。 图2.1 DCT压缩编码过程简化 3.DCT变换 最小均方误差下得到的最佳正交变化是K-L变换，而离散余弦变换(DCT)是仅次于K-L变换的次最佳变换，目前已获得广泛应用。离散预先变换DCT用于图像压缩操作中的基本思路是，将图像分为8×8的子块或16×16的子块，并对每一个子块进行单独的DCT变换，然后对变换结果进行量化、编码。
数据结构课程设计哈夫曼编码-2
《数据结构与算法》课程设计 目录 一、前言 1．摘要 2．《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1．问题描述 2．基本要求 3．测试要求 4．实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会
前言 1．摘要 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。
收稿日期：2011－03－16；修回日期：2011－05－09。 基金项目：国家自然科学基金资助项目（30970780）；北京市自然科学基金及教委重点科技项目（KZ200910005005）。作者简介：邓智玭（1983－），女，湖南邵阳人，博士研究生，主要研究方向：视频编码；贾克斌（1962－），男，北京人，教授，博士生导师，主要研究方向：多媒体技术；陈锐霖（1971－），男，香港人，教授，博士生导师，主要研究方向：视频技术；伏长虹（1981－），男，香港人，副教授，主要研究方向：视频编码；萧允治（1954－），男，香港人，教授，博士生导师，主要研究方向：视频编码。 文章编号：1001－9081（2011）09－2453－04 doi ：10．3724/SP．J．1087．2011．02453 三维视频编码技术的发展与挑战 邓智玭1，2，贾克斌1，陈锐霖2，伏长虹2，萧允治 2 （1．北京工业大学电子信息与控制工程学院，北京100124；2．香港理工大学电子资讯工程系，香港九龙） (zhipindeng@gmail．com;kebinj@bjut．edu．cn) 摘 要：介绍了三维视频编码的核心技术。首先比较了纯视频格式和深度增强格式三维视频编码技术的发展方 向及面临的挑战，其中重点分析了深度估计技术和视点合成技术的研究思路；然后概括了国际3DV /FTV 标准的制定 现状；最后对三维视频编码技术进行了总结和展望。 关键词：三维视频；多视点视频；立体视频；视频编码；深度图 中图分类号：TN919．81 文献标志码：A New trend and challenges in 3D video coding DENG Zhi-pin 1，2，JIA Ke-bin 1，CHAN Yui-lam 2，FU Chang-hong 2，SIU Wan-chi 2 (1．College of Electronic Information and Control Engineering，Beijing University of Technology，Beijing 100124，China ；2．Department of Electronic and Information Engineering，The Hong Kong Polytechnic University，Kowloon Hongkong，China ) Abstract:The key technologies of 3D video coding were introduced．Firstly，the developing directions and challenges of video-only format and depth-enhancement format 3D videos were elaborated．The depth estimation and view synthesis technologies were analyzed in detail．Subsequently，the process of standardizing the current 3DV /FTV standard of MPEG was summarized．The conclusion and prospect were given at last． Key words:3D video;multiview video;stereoscopic video;video coding;depth map 0引言 近二十年来，视频广播技术发生了重大变革，从20世纪的模拟电视到数字电视、高清数字电视，乃至现在的三维电 视，视频技术随着人们生活水平的提高不断发展进步 ［1－2］ 。当今世界，人们已经不再满足于传统的单目视频带来的视觉感受，具有临场感和交互性的三维立体视频以其独特的景深 效果给用户带来前所未有的奇妙体验［3］ 。随着好莱坞推出《阿凡达》等立体电影，三维视频技术逐渐成为多媒体信息产 业的热门话题［4－6］ 。与传统的单目视频相比，三维视频包含的数据量成倍增加［7］ 。为了避免信道中数据量激增，必须对其进行有效的编码压缩。近年来，全球各大研究机构都投入大量精力对三维视频编码技术进行深入研究。 1三维视频编码技术 根据传输形式不同将三维视频分为两大类：1）纯视频格 式，需要传输所有视角的数据［8］ ；2）深度增强格式，传输有限个单目视频及其深度序列， 在解码端利用视点合成技术生成虚拟视点［9］ 。这两类三维视频由于传输形式不同而采用不同的编码方式。 1．1纯视频格式三维视频 纯视频格式三维视频由多路具有细微视角差异的视频组成，由两台（或多台）相邻摄像机从不同角度同时对同一场景进行拍摄得到，这些视频可以直接在三维立体显示设备上播放。1．1．1 立体视频编码 最直接的双通道立体视频编码方式是采用Simulcast 方 法直接对左右视点数据进行独立压缩，如图1（a ）所示，但是 左右视点间的相关性没有得到利用，编码效率较低［10］ 。早在 十几年前， MPEG-2Multiview Profile 就提出结合左右视点之间的交叉相关性和同一视点内部的时空相关性来提高立体视频编码效率［11－12］ 。近年来，立体补充增强信息（Stereo Supplemental Enhancement Information ，Stereo SEI ）和帧组合补 充增强信息（Frame Packing Arrangement SEI ）被纳入到H.264/AVC 中［13］。根据Stereo SEI ，在编码前将左右视点以左右/上下方式交错排列成一段视频，然后通过场间预测来消除视点间的交叉冗余，在解码端通过反交错将立体视频还原成两段独立视点，如图1（b ）所示。该方式与原有的H．264编 解码器完美兼容， 不需要改变原有硬件结构。2009年7月，国际运动图像专家组（Moving Picture Expert Group ，MPEG ）颁 布了MPEG-4AVC Stereo High Profile ，作为多视点视频编码 （Multiview Video Coding ，MVC ）标准的一个子集［14］。然而，Stereo High Profile 只适用于逐行和隔行扫描的双通道立体视频序列，不支持临场感更强的多视点视频和自由视点视频。1．1．2 多视点视频编码 多视点视频是由多台相邻摄像机从不同角度对同一场景 进行拍摄得到的多路视频序列［15］ 。多视点视频的数据量巨 大，相邻视点间的交叉冗余信息比双通道立体视频大得多，为 了最大限度地提高压缩率， 在编码时采用一种基于分层B 帧（Hierarchical B Pictures ，HBP ）的视点—时间金字塔型预测结构［16－18］ ，如图2所示。该结构被MVC 的官方测试模型JMVC 采纳［19］ 。 2009年1月，国际联合视频小组（Joint Video Team ，JVT ） 第31卷第9期2011年9月 计算机应用 Journal of Computer Applications Vol．31No．9Sep．2011
实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include
#include
if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {
视频编码的基本原理及基本框架 视频图像数据有极强的相关性，也就是说有大量的冗余信息。其中冗余信息可分为空域冗余信息和时域冗余信息。压缩技术就是将数据中的冗余信息去掉（去除数据之间的相关性），压缩技术包含帧内图像数据压缩技术、帧间图像数据压缩技术和熵编码压缩技术。 去时域冗余信息 使用帧间编码技术可去除时域冗余信息，它包括以下三部分： －运动补偿 运动补偿是通过先前的局部图像来预测、补偿当前的局部图像，它是减少帧序列冗余信息的有效方法。 －运动表示 不同区域的图像需要使用不同的运动矢量来描述运动信息。运动矢量通过熵编码进行压缩。－运动估计 运动估计是从视频序列中抽取运动信息的一整套技术。 注：通用的压缩标准都使用基于块的运动估计和运动补偿 去空域冗余信息 主要使用帧内编码技术和熵编码技术： －变换编码 帧内图像和预测差分信号都有很高的空域冗余信息。变换编码将空域信号变换到另一正交矢量空间，使其相关性下降，数据冗余度减小。 －量化编码 经过变换编码后，产生一批变换系数，对这些系数进行量化，使编码器的输出达到一定的位率。这一过程导致精度的降低。
熵编码是无损编码。它对变换、量化后得到的系数和运动信息，进行进一步的压缩。 视频编码的基本框架 H.261 H.261标准是为ISDN设计，主要针对实时编码和解码设计，压缩和解压缩的信号延时不超过150ms，码率px64kbps(p=1~30)。 H.261标准主要采用运动补偿的帧间预测、DCT变换、自适应量化、熵编码等压缩技术。只有I帧和P帧，没有B帧，运动估计精度只精确到像素级。支持两种图像扫描格式：QCIF 和CIF。 H.263 H.263标准是甚低码率的图像编码国际标准，它一方面以H.261为基础，以混合编码为核心，其基本原理框图和H.261十分相似，原始数据和码流组织也相似；另一方面，H.263也吸收了MPEG等其它一些国际标准中有效、合理的部分，如：半像素精度的运动估计、PB帧预测等，使它性能优于H.261。 H.263使用的位率可小于64Kb/s,且传输比特率可不固定（变码率）。H.263支持多种分辨率：SQCIF(128x96)、QCIF、CIF、4CIF、16CIF。 与H.261和H.263相关的国际标准 与H.261有关的国际标准 H.320：窄带可视电话系统和终端设备； H.221：视听电信业务中64~1 920Kb/s信道的帧结构； H.230：视听系统的帧同步控制和指示信号； H.242：使用直到2Mb/s数字信道的视听终端的系统。 与H.263有关的国际标准 H.324：甚低码率多媒体通信终端设备； H.223：甚低码率多媒体通信复合协议； H.245：多媒体通信控制协议； G.723.1.1：传输速率为5.3Kb/s和6.3Kb/s的语音编码器。 JPEG 国际标准化组织于1986年成立了JPEG(Joint Photographic Expert Group)联合图片专家小组，主要致力于制定连续色调、多级灰度、静态图像的数字图像压缩编码标准。常用的基于离散余弦变换(DCT)的编码方法，是JPEG算法的核心内容。
哈夫曼编码的JAVA实现课程设计 目录 摘要 (2) 一、问题综述 (2) 二、求解方法介绍 (3) 三、实验步骤及结果分析 (4) 四、程序设计源代码 (5) 参考文献 (8)
摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。 关键字：哈夫曼编码JA V A语言类方法 一、问题综述 1 哈夫曼编码的算法思想 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树 把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。 1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。 1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。 1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。 1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。 1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。 2 构造哈夫曼树的算法 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。
H.264编码标准的分析和算法优化 一、研究背景： 随着社会的不断进步和多媒体信息技术的发展，人们对信息的需求越来越丰富，方便、快捷、灵活地通过语音、数据、图像与视频等方式进行多媒体通信已成不可或缺的工具。其中视觉信息给人们直观、生动的形象，因此图像与视频的传输更受到广泛的关注。然而，视频数据具有庞大的数据量，以普通的25帧每秒，CIF格式（分辨率为352×288）的视频图像为例，一秒钟的原始视频数据速率高达3.8M字节。不对视频信号进行压缩根本无法实时传输如此庞大的数据量，因此，视频压缩技术成为研究热点。 随着近几年来视频图像传输领域的不断扩展，以往的标准己经难于适应不同信道的传输特征及新兴的应用环境。为此，ISO/IEC&ITU-T共同开发了最新视频编码标准H.264/AVC。相对以前的视频编码标准，H.264集成了许多新的视频压缩技术，具有更高的压缩效率和图像质量。在同等的图像质量条件下，H.264的数据压缩比是应用于当前DVD系统MPEG-2的2~3倍，比MPEG-4高1.5~2倍，并且具有更好的网络友好性。但是H.264高压缩比的代价是编码器计算复杂度大幅度地提高。因此在保持编码效率几乎不变的同时尽可能提高编码速度是H.264/AVC视频编码标准能否得到广泛应用的关键。 在上述研究背景下，本文深入探讨了H.264/AVC标准，分析了编码器主要耗时模块的工作原理，提出三种降低H.264/AVC高计算复杂度的优化算法――快速帧内预测模式选择算法、快速帧间预测模式选择算法以及快速运动估计算法。实验结果表明：本文所提快速算法都可大幅度地降低H.264编码器的计算复杂度，并且保持基本不变的编码效率。 二、新一代视频编码标准H.264简介： 编码标准演进过程：H.261 MPEG-1 MPEG-2 H.263 MPEG-4 从视频编码标准的发展历程来看，视频编码标准都有一个不断追求的目标：在尽可能低的码率（或存储容量）下获得尽可能好的图像质量。MPEG-2、MPEG-4、H.263等标准都取得了巨大的成功，但在应用中也发现一些问题。H.263众多的选项往往令使用者无所适从；MPEG-2压缩效率己显略低；引人注目的MPEG-4的“基于对象的编码”由于尚有技术障碍，目前还难以普遍应用。在此背景下，两大国际标准化组织ITU-T和ISO共同制定了新一代视频编码标准H.264。该编码标准在混合编码的框架下引入新的编码方式，解决了目前编码标 准存在的问题，进一步贴近实际应用，其应用前景是不言而喻的。 三、H.264视频编码标准概述 JVT的工作目标是制定一个新的视频编码标准，以实现视频的高压缩比、高图像质量、良好的网络适应性等目标。JVT的工作已于2003年3月被ITU-T采纳，新的视频编码标准称为H.264标准。该标准也被ISO采纳，称为AVC（Advanced Video Coding）标准，是国际标准ISO14496-10（MPEG-4的第10部分），因此总称为H.264/AVC。 H.264着重于提高压缩效率和传输的可靠性，因而其应用面十分广泛。具体来说，H.264支持三个不同档次的应用： 1、基本档次：H.264简单版本，应用面广，主要用于视频会话，如会议电视、可视电话、远程医疗、远程教学等。 2、主要档次：采用了多项提高图像质量和增加压缩比的技术措施，主要用于消费电子应用，可用于SDTV、HDTV和DVD等。 3、扩展档次：主要用于各种网络的视频流传输，如视频点播等。
0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。
译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c 在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定
各种音视频编解码学习详解 编解码学习笔记（一）：基本概念 媒体业务是网络的主要业务之间。尤其移动互联网业务的兴起，在运营商和应用开发商中，媒体业务份量极重，其中媒体的编解码服务涉及需求分析、应用开发、释放license收费等等。最近因为项目的关系，需要理清媒体的codec，比较搞的是，在豆丁网上看运营商的规范标准，同一运营商同样的业务在不同文档中不同的要求，而且有些要求就我看来应当是历史的延续，也就是现在已经很少采用了。所以豆丁上看不出所以然，从wiki上查。中文的wiki信息量有限，很短，而wiki的英文内容内多，删减版也减肥得太过。我在网上还看到一个山寨的中文wiki，长得很像，红色的，叫―天下维客‖。wiki的中文还是很不错的，但是阅读后建议再阅读英文。 我对媒体codec做了一些整理和总结，资料来源于wiki，小部分来源于网络博客的收集。网友资料我们将给出来源。如果资料已经转手几趟就没办法，雁过留声，我们只能给出某个轨迹。 基本概念 编解码 编解码器（codec）指的是一个能够对一个信号或者一个数据流进行变换的设备或者程序。这里指的变换既包括将信号或者数据流进行编码（通常是为了传输、存储或者加密）或者提取得到一个编码流的操作，也包括为了观察或者处理从这个编码流中恢复适合观察或操作的形式的操作。编解码器经常用在视频会议和流媒体等应用中。 容器 很多多媒体数据流需要同时包含音频数据和视频数据，这时通常会加入一些用于音频和视频数据同步的元数据，例如字幕。这三种数据流可能会被不同的程序，进程或者硬件处理，但是当它们传输或者存储的时候，这三种数据通常是被封装在一起的。通常这种封装是通过视频文件格式来实现的，例如常见的*.mpg, *.avi, *.mov, *.mp4, *.rm, *.ogg or *.tta. 这些格式中有些只能使用某些编解码器，而更多可以以容器的方式使用各种编解码器。 FourCC全称Four-Character Codes，是由4个字符（4 bytes）组成，是一种独立标示视频数据流格式的四字节，在wav、avi档案之中会有一段FourCC来描述这个AVI档案，是利用何种codec来编码的。因此wav、avi大量存在等于―IDP3‖的FourCC。 视频是现在电脑中多媒体系统中的重要一环。为了适应储存视频的需要，人们设定了不同的视频文件格式来把视频和音频放在一个文件中，以方便同时回放。视频档实际上都是一个容器里面包裹着不同的轨道，使用的容器的格式关系到视频档的可扩展性。 参数介绍 采样率 采样率（也称为采样速度或者采样频率）定义了每秒从连续信号中提取并组成离散信号的采样个数，它用赫兹（Hz）来表示。采样频率的倒数叫作采样周期或采样时间，它是采样之间的时间间隔。注意不要将采样率与比特率（bit rate，亦称―位速率‖）相混淆。 采样定理表明采样频率必须大于被采样信号带宽的两倍，另外一种等同的说法是奈奎斯特频率必须大于被采样信号的带宽。如果信号的带宽是100Hz，那么为了避免混叠现象采样频率必须大于200Hz。换句话说就是采样频率必须至少是信号中最大频率分量频率的两倍，否则就不能从信号采样中恢复原始信号。 对于语音采样： ?8,000 Hz - 电话所用采样率, 对于人的说话已经足够 ?11,025 Hz ?22,050 Hz - 无线电广播所用采样率 ?32,000 Hz - miniDV 数码视频camcorder、DAT (LP mode)所用采样率 ?44,100 Hz - 音频CD, 也常用于MPEG-1 音频（VCD, SVCD, MP3）所用采样率
视频编码原理 编码率/比特率直接与文件体积有关。且编码率与编码格式配合是否合适，直接关系到视频文件是否清晰。 在视频编码领域，比特率常翻译为编码率，单位是Kbps，例如800Kbps。 其中，1K=10241M=1024K，b为比特（bit）这个就是电脑文件大小的计量单位，1KB=8Kb，区分大小写，B代表字节(Byte)s为秒（second）p为每（per）以800kbps来编码表示经过编码后的数据每秒钟需要用800K比特来表示。 1MB=8Mb=1024KB=8192Kb Windows系统文件大小经常用B(字节)为单位表示，但网络运营商则用b(比特)，也就是为什么2Mb速度宽带在电脑上显示速度最快只有约256KB的原因，网络运营商宣传网速的时候省略了计量单位。 完整的视频文件是由音频流与视频流2个部分组成的，音频和视频分别使用的是不同的编码率，因此一个视频文件的最终技术大小的编码率是音频编码率+视频编码率。例如一个音频编码率为128Kbps，视频编码率为800Kbps的文件，其总编码率为928Kbps，意思是经过编码后的数据每秒钟需要用928K比特来表示。 了解了编码率的含义以后，根据视频播放时间长度，就不难了解和计算出最终文件的大小。编码率也高，视频播放时间越长，文件体积就越大。不是分辨率越大文件就越大，只是一般情况下，为了保证清晰度，较高的分辨率需要较高的编码率配合，所以使人产生分辨率越大的视频文件体积越大的感觉。 计算输出文件大小公式： （音频编码率（Kbit为单位）/8+视频编码率（Kbit为单位）/8）×影片总长度（秒为单位）=文件大小（MB为单位） 这样以后大家就能精确的控制输出文件大小了。 例：有一个1.5小时（5400秒）的影片，希望转换后文件大小刚好为700M 计算方法如下： 700×8/5400×1024≈1061Kbps 意思是只要音频编码率加上视频编码率之和为1061Kb，则1个半小时的影片转换后文件体积大小刚好为700M。 当然不经过压缩文件的计算公式又不同： 声音为，数据量（位/秒）=(采样频率（Hz）×采样位数（bit）×声道数) 其中，单声道的声道数为1，立体声的声道数为2。 数据量×时间/8＝文件总字节 例如CD即为未经压缩的音频文件，采样44.1k,16位,双声道。 数据量＝44.1×16×2=1411kb/1024=1.38Mb,一般的MP3压缩后为128kbps
实验6：哈夫曼树及哈夫曼编码的算法实现 实验所需 学时数 2学时 实验目的1)掌握哈夫曼树的基本概念及其存储结构； 2)掌握哈夫曼树的建立算法； 3)掌握哈夫曼树的应用（哈夫曼编码和译码）。 实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。 实验所需 器材 计算机及VC++ 6.0软件 内容要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树 2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据： 输入字符串“this*program*is*my*favourite”，完成这28个字符的编码和译码。 实验结果 1、演示程序运行结果。 2、说明调试过程中出现的现象 学生实验评价依据： 优：实验认真、刻苦，有钻研精神，不无故缺席。 良：能认真对待实验，不无故缺席。 中：基本能认真对待实验，不无故缺席。 差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。
#include 视频编码技术实验报告-----算术编码算法的程序实现 学院： 班级： 姓名： 学号： 本实验通过编程实现简单的算术编码解码过程，加深对视频编码中熵编码原理及过程的理解，锻炼理论与实践相联系能力。 二、实验原理 算术编码是另一种常用的变字长编码，它也是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman 一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman 编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman 编码。它和Huffman 编码最大的区别在于它不是使用整数码。Huffman 码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率[0，1] 区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。 三、实验过程 1.给定二进制符号序列：010110101111100110111100100011111111110100101101101101101 2.采用二元二进制算术编码进行编码，输出编码的结果。 3.采用自适应二元算术编码进行编码，输出编码结果。 4. 解码刚才编码的符号序列。 算术编码的C++实现 #include 视频编码算术编码实验报告
相关主题
文本预览