视频编解码原理

视频编解码原理视频编解码原理 之一：理论基础第1章 介绍1. 为啥要进行视频压缩呢？未经压缩的数字视频的数据量巨大 存储困难 一张DVD只能存储几秒钟的未压缩数字视频。传输困难 1兆的带宽传输一秒的数字电视视频需要大约4分钟。2.为什么可以压缩去除冗余信息 空间冗余：图像相邻像素之间有较强的相关性 时间冗余：视频序列的相邻图像之间内容相似 编码冗余：不同像素值出现的概率不同 视觉冗余：人的视觉系统对某些细节不敏感 知识冗余：规律性的结构可由先验知识和背景知识得到3.数据压缩分类无损压缩（Lossless） 压缩前解压缩后图像完全一致X=X 压缩比低(2:13:1) 例如：Winzip，JPEG-LS有损压缩（Lossy） 压缩前解压缩后图像不一致XX 压缩比高(10:120:1) 利用人的视觉系统的特性 例如：MPEG-2，H.264/AVC，AVS4.编解码器编码器（Encoder） 压缩信号的设备或程序解码器（Decoder） 解压缩信号的设备或程序编解码器(Codec) 编解码器对5. 压缩系统的组成(1) 编码器中的关键技术(2) 编解码中的关键技术6.编解码器实现编解码器的实现平台： 超大规模集成电路VLSI ASIC， FPGA 数字信号处理器DSP 软件编解码器产品： 机顶盒 数字电视 摄像机 监控器7. 视频编码标准编码标准作用：兼容： 不同厂家生产的编码器压缩的码流能够被不同厂家的解码器解码高效： 标准编解码器可以进行批量生产，节约成本。主流的视频编码标准：MPEG-2 MPEG-4 Simple Profile H.264/AVC AVS VC-1标准化组织：ITU：International Telecommunications Union VECG：Video Coding Experts GroupISO：International Standards Organization MPEG：Motion Picture Experts Group8. 视频传输视频传输：通过传输系统将压缩的视频码流从编码端传输到解码端 传输系统：互联网，地面无线广播，卫星9. 视频传输面临的问题传输系统不可靠 带宽限制 信号衰减 噪声干扰 传输延迟视频传输出现的问题 不能解码出正确的视频 视频播放延迟10. 视频传输差错控制差错控制（Error Control）解决视频传输过程中由于数据丢失或延迟导致的问题 差错控制技术： 信道编码差错控制技术 编码器差错恢复 解码器差错隐藏11.视频传输的QoS参数数据包的端到端的延迟 带宽：比特/秒 数据包的流失率 数据包的延迟时间的波动第2章 数字视频1.图像与视频图像：是人对视觉感知的物质再现。 三维自然场景的对象包括：深度，纹理和亮度信息 二维图像：纹理和亮度信息视频：连续的图像。 视频由多幅图像构成，包含对象的运动信息，又称为运动图像。2. 数字视频数字视频：自然场景空间和时间的数字采样表示。 空间采样 解析度（Resolution） 时间采样 帧率：帧/秒3. 空间采样二维数字视频图像空间采样4. 数字视频系统采集 照相机，摄像机处理 编解码器，传输设备显示 显示器5. 人类视觉系统HVSHVS 眼睛 神经 大脑HVS特点： 对高频信息不敏感 对高对比度更敏感 对亮度信息比色度信息更敏感 对运动的信息更敏感6. 数字视频系统的设计应该考虑HVS的特点：丢弃高频信息，只编码低频信息 提高边缘信息的主观质量 降低色度的解析度 对感兴趣区域（Region of Interesting，ROI）进行特殊处理7. RGB色彩空间三原色：红（R），绿（G），蓝（B）。 任何颜色都可以通过按一定比例混合三原色产生。 RGB色度空间 由RGB三原色组成 广泛用于BMP，TIFF，PPM等 每个色度成分通常用8bit表示0,2558. YUV色彩空间YUV色彩空间： Y：亮度分量 UV：两个色度分量 YUV更好的反映HVS特点9. RGB转化到YUV空间亮度分量Y与三原色有如下关系：经过大量实验后ITU-R给出了，主流的编解码标准的压缩对象都是YUV图像10.YUV图像分量采样YUV图像可以根据HVS的特点，对色度分量下采样，可以降低视频数据量。 根据亮度和色度分量的采样比率，YUV图像通常有以下几种格式：11. 通用 的YUV图像格式根据YUV图像的亮度分辨率定义图像格式12. 帧和场图像一帧图像包括两场顶场，底场13. 逐行与隔行图像逐行图像：一帧图像的两场在同一时间得到，ttop=tbot。 隔行图像：一帧图像的两场在不同时间得到，ttoptbot。14. 视频质量评价有损视频压缩使编解码图像不同，需要一种手段来评价解码图像的质量。 质量评价： 客观质量评价 主观质量评价 基于视觉的视频质量客观评价客观质量评价：通过数学方法测量图像质量评价的方式。 优点： 可量化 测量结果可重复 测量简单缺点： 不完全符合人的主观感知15. 客观评价的方法常用的客观评价方法：16. 主观评价方法主观质量评价：用人的主观感知直接测量的方式。 优点： 符合人的主观感知缺点： 不容易量化 受不确定因素影响，测量结果一般不可重复 测量代价高常用主观评价方法17.基于视觉的视频质量客观评价方法基于视觉的视频质量客观评价：将人的视觉特性用数学方法描述并用于视频质量评价的方式。 结合了主观质量评价和客观质量评价两方面优点。 常用方法：结构相似度（Structural SIMilarity，SSIM）方法。 将HVS的特征用数学模型表达出来。 未来重要的研究方向第3章 信息论基础1. 通信系统的组成信源：产生消息 信道：传输消息 信宿：接收消息2. 基本概念通信中对信息的表达分为三个层次：信号，消息，信息。 信号：是信息的物理层表达，可测量，可描述，可显示。如电信号，光信号。 消息：是信息的载体，以文字，语言，图像等人类可以认知的形式表示。 信息：不确定的内容。3. 信息熵信息的特点信息的测量自信息量条件信息量4. 信息熵5. 条件熵和联合熵6. 熵的性质非负性：信源熵是非负值，即 H(X) =0; 扩展性：信源熵X有M个符号，如果其中一个符号出现的概率趋于零，信源熵就等于剩余M-1个符号的信源熵； 极值性（最大信息熵）：对于具有M个符号的信源，只有在所有符号等概率出现的情况下，信源熵达到最大值，即 可加性： 熵不增：条件熵不大于信息熵H(X|Y) = H(X)； 联合熵不大于各信息熵的和，即H(XY) 0，则C- ，这意味着无干扰信道容量为无穷大； 增加信道带宽B，也可增加信道容量C，但做不到无限制地增加。这是因为，如果S、n0一定，有 维持同样大小的信道容量，可以通过调整信道的B及S/N来达到，即信道容量可以通过系统带宽与信噪比的互换而保持不变。22. 失真失真：信源的消息经过编解码后不能完全复原 在实际的信源和信道编码中，消息的传输并不总是无失真的。 由于存储和传输资源的限制 噪声等因素的干扰23. 率失真理论仙农定义了信息率失真函数R(D) D是消息失真 R是码率率失真定理：在允许一定失真度D的情况下，信源输出的信息率可压缩到R(D)。24. 失真函数失真函数：信源符号X=x1,x2, .xn，经信道传输接收端符号Y=y1,y2.yn，对于每一对(xi,yj)指定一个非负函数d(xi,yj)，称d(xi,yj)为单个符号的失真度或失真函数。对于连续信源连续信道的情况，常用d(x,y)表示。 常用失真函数：平均失真度：视频编解码原理 之二：编解码框架第4章 视频编码基础1. 压缩码流语法：码流中各个元素的位置关系 01001001 图像编码类型(01)，宏块类型(00)，编码系数1001等语义：每个语法元素所表达的意义。 例如：图像编码类型2. 编码层次序列（Sequence） 图像组（Group of Pictures，GOP） 图像（Picture） 条带（Slice） 宏块（Macroblock，MB） 块(Block)3. 码流结构3. PB帧编码4. 序列编码对象（1）IBBP序列序列：一段连续编码的并具有相同参数的视频图像。 序列起始码：专有的一段比特串，标识一个序列的压缩数据的开始 MPEG-2的序列起始码为十六进制数000001(B3)。序列头：记录序列信息 档次（Profile），级别（Level），宽度，高度，是否是逐行序列，帧率等。序列结束码：专有的一段比特串，标识该序列的压缩数据的结束 MPEG-2的序列结束码为十六进制数000001(B7)。5. 图像组编码对象6. 图像编码结构图像： 图像起始码：专有的一段比特串，标识一个图像的压缩数据的开始 MPEG-2的图像起始码为十六进制数000001(00)。图像头：记录图像信息 图像编码类型，图像距离，图像编码结构，图像是否为逐行扫描。7. 图像分块编码8. 条带编码结构条带：多个宏块的组合。 条带起始码：专有的一段比特串，标识一个条带的压缩数据的开始 MPEG-2的条带起始码为十六进制数000001(0AF)。条带头：记录当前图像的相关信息 条带位置，条带量化参数，宏块编码技术标识等。9. 条带编码对象10. 宏块编码结构 宏块：16x16的像素块（对亮度而言）。 宏块内容：宏块编码类型，编码模式，参考帧索引，运动矢量信息，宏块编码系数等。11. 宏块编码对象12. 块编码结构8x8或4x4块的变换量化系数的熵编码数据。 CBP (Coded Block Patten)：用来指示块的变换量化系数是否全为零。 对于YUV(4:2:0)编码，CBP通常6比特长，每个比特对应一个块，当某一块的变换量化系数全为零时，其对应比特位值为0，否则为1。每个块的变换量化系数的最后用一个EOB (End of Block)符号来标识。13. 视频编解码关键技术预测：通过帧内预测和帧间预测降低视频图像的空间冗余和时间冗余。 变换：通过从时域到频域的变换，去除相邻数据之间的相关性，即去除空间冗余。 量化：通过用更粗糙的数据表示精细的数据来降低编码的数据量，或者通过去除人眼不敏感的信息来降低编码数据量。 扫描：将二维变换量化数据重新组织成一维的数据序列。 熵编码：根据待编码数据的概率特性减少编码冗余。14. 预测空间预测：利用图像空间相邻像素的相关性来预测的方法。 帧内预测技术：利用当前编码块周围已经重构出来的像素预测当前块 Intra图像编码（I帧）时间预测：利用时间上相邻图像的相关性来预测的方法。 帧间预测：运动估计（Motion Estimation，ME），运动补偿（Motion Compensation，MC） Inter图像编码：前向预测编码图像（P帧），双向预测编码图像（B帧）15. 帧内预测I帧图像的每个宏块都采用帧内（Intra）预测编码模式。 宏块分成8x8或者4x4块，对每个块采用帧内预测编码，称作Intra8x8或者Intra4x4。 帧内预测有多个预测方向：水平，垂直，左下，右上。 帧内预测还有直流（DC）预测。 色度块预测还有平面预测。16. 帧间预测块基运动估计：为待预测块在参考帧上找到最佳的预测块，并记录预测块在参考帧上的相对位置。 运动矢量（MV）：参考帧上的预测块与当前帧上的的待预测块的相对位置。 MV有两个分量：（x，y）分像素运动估计 最佳的预测块不在整像素位置，而在分像素位置； 1/2，1/4，1/8像素插值得到分像素值。帧间预测流程：运动补偿：给定MV和参考帧，为待解码块从参考帧上获取预测块。 运动矢量编码 MV预测：用当前块的周围可得到邻块的运动矢量来预测当前块的运动矢量 运动矢量差（MV difference，MVD）：实际运动矢量与预测运动矢量的差，即： 运动矢量差采用变长编码。17. 预测残差18. 变换编码变换编码：通过变换将空域信号转换为频域信号来去除空间信号的冗余信息，减少编码数据。 二维离散余弦变换 4x4变换，8x8变换二维离散余弦变换例：变换系数：直流（DC）系数，交流（AC）系数19. 量化 量化原理：将含有大量的数据集合映射到含有少量的数据集合中。 一般情况下量化后高频部分包含大量的零系数 量化对主观质量的影响20. 扫描 扫描：将二维数据转换为一维的数据序列。21. 熵编码 熵编码：根据符号出现的概率，对经常出现的符号分配较短的码字，对不常出现的符号分配较长的码字。 Level-Run编码：用数据中非零值和其前面非零值之间出现零值的个数重新描述量化系数序列为（Level，Run）二元组序列 变长编码 将Level-Run编码后的（level，run）变长编码成最终的比特串。22. 码率控制 受到缓冲区，带宽的限制，编码码率不能无限制的增长，因此需要通过码率控制来将编码码流控制在目标码率范围内。 一般通过调整量化参数的手段控制码率 帧级控制 条带级控制 宏块级控制 码率控制考虑的问题 防止码流有较大的波动，导致缓冲区发生溢出， 同时保持缓冲区尽可能的充满，让图像质量尽可能的好而且稳定 CBR（Constant Bit Rate） 比特率稳定，但图像质量变化大 VBR（Variable Bit Rate） 比特率波动大，但图像质量稳定 码率控制算法 码率分配 码率控制 码率控制属于非标准技术 编码端有，解码端没有第5章 预测1. 预测技术 目的：去除空间冗余和时间冗余。 视频存在大量的空间冗余和时间冗余 空间冗余：用帧内预测编码去除 基于块的帧内预测 时间冗余：用帧间预测编码去除 基于块匹配（Block Matching）的帧间预测 预测后得到去除大部分空间或时间冗余的残差2. 空间冗余 图像空间相邻像素具有很强的相关性。 帧内预测技术去除空间冗余3. 亮度预测模式4. 色度预测模式5. 时间冗余 视频图像在时间上有较强的相关性，即存在时间冗余 去除时间冗余的编码技术 运动估计（Motion Estimation，ME） 为待编码块搜索最相似的预测块 记录运动矢量（Motion Vector，MV) 记录预测残差： 运动补偿（Motion Compensation，MC） 根据运动矢量获取预测块 根据预测残差计算重构块：6. 运动模型（1）平移7. 匹配准则8. 匹配准则简化 简化技术方法 分别计算当前块和预测块的象素值和 根据简化形式，比较当前块和预测块 如果用简化准则对预测块和当前块比较的结果比以前最好的结果差，可以确定预测效果不好，不必对预测块再进行比较。9. 运动估计 去除视频图像的时间冗余 运动估计在搜索范围内为当前块寻找匹配最好的预测块 全搜索方式的运动估计计算复杂度高10. 全搜索复杂度分析 图像大小：MxM 预测块大小：NxN 搜索范围：(-R，R) 每个搜索点象素比较个数：N2 搜索点个数(2R+1)2 在搜索范围内的象素比较个数总和N2(2R+1)2 一帧图像所有块的全搜索象素比较个数总和N2(2R+1)2(M/N)2=(2R+1)2M2 例：M=512，N=4，R=8，帧率：30帧/秒(2R+1)2M2=172X5122= 75759616次/帧= 75759616x30次/秒=2272788480次/秒采用SSD匹配准则：每次象素比较需1个减法，1个乘法，1个加法，则上述全搜索计算每秒需要2272788480x2次加减法和2272788480次乘法操作。11. 快速运动估计 在保持预测精度的同时减少运动估计的搜索次数。 三步搜索（Three Step Search，TSS） 二维Log搜索（2D Logarithmic Search，2DLOG） 正交搜索（Orthogonal Search Algorithm，OSA） 十字搜索（Cross Search Algorithm，CSA） 新三步搜索（New Three Step Search，NTSS） 四步搜索（Four Step Search，FSS） 共轭方向搜索（Conjugate Direction Search，CDS） 梯度下降搜索（Gradient Descent Search，GDS） 层次块搜索（Hierarchical Block Matching Algorithm，HBMA）12. 三步搜索 由粗到精搜索最优点，初始步长为R/2. 第一步：检查起始点和其周围步长为R/2的8个点，将最优点作为第二步的起始点； 第二步：以新的起始点为中心检查其周围步长为R/4的8个点，找到最优点作为第三步的起始点； 第三步：以新的起始点为中心检查其周围步长为R/8的8个点，找到最优点，如果R/8=1则搜索终止，最优点位置的预测块作为最优的预测块，否则重复该过程直到R/n2=1； 三步搜索方法检查点的个数为1+8log2（d+1），当d=8时，检查点个数为9+8+8=2513. 二维Log搜索 每一步采用十字搜索模式 如果每一步的最优点为中心点或者搜索窗的边界点，搜索步长减半，否则搜索步长不变 当搜索步长为1时，中心点周围的8个点都要检查 两个搜索路径一个需要5+3+3+8=19，另外一个需要5+3+2+3+2+8=2314. 正交搜索 起始搜索步长R/2，从起始点开始水平搜索三个点，得到最优点并沿着最优点垂直方向搜索相邻的两个点，得到最优点，以搜索步长为R/4再以同样的方式先水平再垂直搜索，当步长为1时停止搜索 搜索方法检查点的个数为1+4log2(d+1)，当d=8时，检查点个数为3+2+2+2+2+2=13。15. 十字搜索 起始搜索步长R/2，从起始点开始以X形十字搜索，当搜索步长降为1时，如果上一步的最优点为中心点，左上点或右下点，则这一步搜索以+形状十字搜索，然后结束搜索，否则还是以X形十字搜索，然后结束搜索。 十字搜索方法检查点的个数为1+4log22d，当d=8时，检查点个数为5+4+4+4=1716. 新三步搜索 与三步搜索方法不同的是，考虑到运动矢量高的中心分布特点，新三步搜索方法，除了围绕起始点为中心搜索步长为R/2的8个点之外，在起始点周围增加了步长为1的8个搜索点，如果最优点为步长为1的8个搜索点之一，则在最优点邻近的三个点中搜索最优点，然后结束搜索，否则，和三步搜索方法过程一样 其中一个搜索路径需要检查点个数为17+3=20，另一个需要17+8+8=33。17. 块梯度下降搜索 该方法以起始点为中心搜索8个步长为1的相邻点，确定最优点，再以最优点为中心搜索8个步长为1的相邻点，如此循环下去，不限制搜索步骤，但当搜索得到的最优点为中心点或者到搜索窗的边界，搜索终止。18. 层次块搜索 对编码图像和参考图像下采样，分别得到编码图像和参考图像的下采样图像，未经采样处理的编码图像和参考图像属于第0层，一次下采样的编码图像和参考图像属于第1层，对第1层图像再进行下采样得到的编码图像和参考图像属于第2层，依次重复上述过程，得到第n层下采样的编码图像和参考图像。 然后在n层下采样参考图像的搜索范围中找到与下采样编码图像块最佳匹配块的MV，该MV作为n-1层的运动估计搜索范围的中心点，依次重复上述过程，直到n=0为止，此时得到的最佳匹配块就是编码图像的预测块，其对应的MV为最终的最优MV。19. 搜索算法复杂度比较20 . 分像素运动估计与运动补偿 时域运动位置更可能在整象素之间，即分像素上。 利用相邻的整象素可以估计出分象素的值 常用线性或双线性插值得到分象素的值。 分象素运动估计有更高的预测精度，但复杂度也更高， 1/2分象素运动估计，图像存储空间增加4倍，运动矢量需要放大2倍，1/4分象素运动估计，图像存储空间增加16倍，运动矢量需要放大4倍，计算复杂度也成倍增加。21. 分像素插值22. 多参考帧预测 有更多的候选图像，搜索更精确的预测块 需要更多的参考图像存储空间 码流需要标识参考帧索引的语法元素23. 图像分块编码 视频内容的运动非常复杂，图像分块编码可以更好的提高运动预测精度，提高压缩效率。 要在编码块大小和附信息（MV，Mode）编码比特数之间权衡，小的编码块大小会有更好的预测但有更多的附信息比特数。23. 双向预测编码24. B帧有更好的编码效率 B帧有更好的编码效率 新出现的对象参考将来的帧有更好的预测效果 前后两个预测的平均值可以减少预测方差25. 全局运动估计 基于全局仿射运动模型 预测精度不如基于块的运动估计 MV数目少，适合简单运动场景的运动估计视频编解码 之三：变换，量化与熵编码第6章 变换编码1. 变换编码 变换编码的目的 去除空间信号的相关性 将空间信号的能力集中到频域的一小部分低频系数上 能量小的系数可通过量化去除，而不会严重影响重构图像的质量 块变换和全局变换 块变换：离散余弦变换(Discrete Cosine Transform，DCT)，4x4，8x8，16x16 全局变换：小波变换(Wavelet) 变换的能量集中特性 DCT编码2. 变换类型 K-L变换 傅里叶变换 余弦变换 小波变换3. KL变换 最优变换 基函数根据具体图像而确定 没有快速算法 实际中很少使用 复杂度极高 K-L变换非常复杂度很高，不实用 需要计算协方差矩阵U 需要计算特征向量 需要发送 到解码器4. 离散傅立叶变换5. 离散傅立叶变换性质6. 离散余弦变换 比K-L变换，傅里叶变换的复杂度更低 变换性能仅次于K-L变换 有快速算法可以加快变换速度 可以用整数变换进一步降低复杂度7. DCT与DFT的关系8. 离散余弦变换的重要性质9. 快速DCT变换下图是一个动态展示：10. 整数离散余弦变换 离散余弦变换为浮点操作 需要64位精度 浮点计算复杂度高 变换精度高 整数变换：离散余弦变换的整数近似 需要更少的位宽 整数计算复杂度低 好的整数变换的变换精度接近浮点变换 浮点近似方法11. H.264的4x4整数变换12. 小波变换 新的变换方法 避免由于块编码带来的块效应 更适合视频空间可分级编码第7章 量化1. 量化Quantization 用更小的集合表示更大的集合的过程 对信号源的有限近似 有损过程 应用 A/D转换 压缩 量化方法 标量(Scalar)量化 矢量(Vector)量化2. 量化的基本思想 映射一个输入间隔到一个整数 减少信源编码的bit 一般情况重构值与输入值不同3. 量化模型4. 量化的率失真优化 量化器设计问题 量化水平的个数，即Bin的个数 决策边界：Bin的边界 重构水平 量化器设计是对率失真的优化 为了减少码率的大小，需要减少Bin的个数 Bin的个数减少导致重构的误差增大，失真也就随着增大5. 失真测量6. 量化器设计 量化器设计的两个方面 给定量化水平数目M，找到决策边界xi和重构水平使MSE最小 给定失真限制D，找到量化水平数目M，决策边界xi和重构水平yi使MSE=D7.均匀量化（Uniform Quantization）8. 量化与峰值信噪比9.中升量化器（Midrise Quantizer）10.中平量化器（Midtread Quantizer）11.死区量化器（Deadzone Quantizer）12非均匀量化（Non-uniform Quantization） 如果信源不是均匀分布的，采用均匀量化不是最优的 对于非均匀量化，为了减少MSE，当概率密度函数fX(x)高时，使Bin的量化步长减小，当概率密度函数fX(x)低时， 使Bin的量化步长增加。13. 最优的标量量化14. 量化编码 定长编码量化水平 使用等长的码字编码每个量化水平，码字长为： 熵编码量化水平 根据量化水平的概率分布情况，用变长的码字编码每个量化水平 平均码字长 比定长编码量化水平效率高 广泛应用在图像和视频编码中15. 矢量量化 标量量化：对数据一个一个的进行量化，称为标量量化。 矢量量化：将数据分组，每组K个数据构成K维矢量，再以矢量为处理单元进行量化。 矢量量化是标量量化的多维扩展 标量量化是矢量量化的特殊情况 矢量量化工作过程 二维矢量量化 矢量量化优点 只传码字的下标，编码效率高 在相同码率下，比标量量化失真小 在相同失真下，比标量量化码率低 矢量量化缺点：复杂度随着维数的增加呈指数增加第8章 熵编码1. 熵编码 熵（Entropy）：信源的平均信息量，更精确的描述为表示信源所有符号包含信息的平均比特数 信源编码要尽可能的减少信源的冗余，使之接近熵 用更少的比特传递更多的信源信息 熵编码：数据压缩中根据信源消息的概率模型使消息的熵最小化 无损压缩 变长编码2. 熵 信息量：单位：比特 熵：单位：比特/符号3. 定长编码4. 变长编码 变长编码：用不同的比特数表示每一个符号 为频繁发生的符号分配短码字 为很少发生的符号分配长码字 比定长编码有更高的效率 常用的变长编码 Huffman编码 算术编码5. Huffman编码 前缀码：任何码字不是其它码字的前缀 如果011为一个有效码字，则0，1，01，11必不是有效码字 不会引起解码歧义 Huffman： 二叉树 树节点:表示符号或符号组合 分支:两个分支一个表示0，另一个表示1 Huffman的不唯一性 每次分支有两种选择：0，1 相同的概率产生不同的组合 缺点： 数据的概率变化难于实时统计 Huffman树需要编码传输给解码器 只有在p(xi)=1/2ki时是最优编码 最小码字长度为1比特/符号 如果有二值信源，其两个符号的概率相差很大 例如：p(1)=0.0625，p(0)=0.9375则H=0.3373比特/符号，Huffman编码平均码长=1比特/符号 两个符号联合编码有更高效率6. 扩展Huffman编码7. 范式Huffman编码 范式Huffman树的建立规则 节点左支设为0，右支设为1 树的深度从左至右增加 每个符号被放在最先满足的叶子节点 特性 第一个码字是一串0 相同长度的码字的值是连续的 如果所有的码字通过在低位补0的方式，使所有码字的长度相同则有 0000010010001010110011101111 从码字长度n到n+1有如下关系 C(n+1,1)=(C(n,last)+1)1 从码字长度n到n+2有如下关系 C(n+2,1)=(C(n,last)+1)GolombTab_x，用GolombTab_x编码cofN12. 算术编码 信息量=符号编码比特数 Huffman编码为每个符号分配一个码字，这说明Huffman编码的压缩上限是1比特/符号 算术编码若干个符号可编码成1bit 算术编码是把信源表示为实数轴上0,1区间，信源中每个符号都用来缩短这个区间 输出0,1区间的一个实数表示一串编码符号 比Huffman编码更有效 编码思想 编码器用熵编码算法编码一串符号产生一个0,1区间的实数，将实数的一个二进制表示传给解码器 解码器用熵解码算法解码得到一串符号 小数的二进制表示 信源符号概率分布 字符串：X2 X2 X3 X3 X6 X5 X7 Huffman编码，01 01 100 100 00 11 1011，18bit 算术编码更接近熵 有限精度算术编码是次优（Near-optimal）编码，发送整数比特给解码端 算术编码到最后一个字符编码结束才输出码字 编码复杂度也比较高13. 二值算术编码13. 自适应二值算术编码 由于信源0和1出现的概率是在不断变化的，因此0和1的概率区间也应该不断改变 自适应二值算术编码每编码一个0或1都重新统计0和1的概率并重新划分0,1)区间 编解码端的概率统计模型一致，能够得到同样的0,1)区间划分14.CABAC（Context-Based Adaptive Binary Arithmetic Coding） 当前块的语法元素概率分布和其邻块的语法元素概率分布情况相关 当前块C的邻块A和B的语法元素SA与SB可以为编码C块的语法元素SC选择概率模型 二值化 将语法元素值转换成二进制值串 概率模型更新 根据已经编码的比特，重新估计二进制值串的概率并更新概率模型，用新的概率模型编码下一个比特15. Run Length 编码 利用信源字符的重复性来编码的技术 对有很长，很多重复字符的信源编码非常有效 重复字符称为run，重复的字符个数称为run length Run-length编码能够和其它熵编码一起来压缩数据16. 字典编码 字典编码：根据信源符号（消息）的组合特点，建立包含各种符号组合的字典，编码这些符号组合的索引 LZ78=Winzip LZW= GIF 适合一般意义上的数据压缩，去除数据的统计冗余17. LZW 将信源输出的字符串中，每个第一次出现的字符或者字符串用索引来表示，并将字符或字符串对应的索引编码到码流中 解码端根据从码流中解码的字符，在线的建立和编码器完全一样的字典，并恢复出信源输出的字符串 适用于字符串中有大量的子字符串多次重复出现，重复次数越多，压缩效果越好 单个符号被分配为0-255之间的值 初始码表，使其包含值为0-255的256个符号，值大于255的符号为空 编码器将根据编码的符号情况确定字符组合为从 256 到 4095 之间的值 编码时，编码器识别新的字符组合，并将他们增加到码表中 编码器用码表中的符号组合所对应的值编码 解压时LZW解码器能够产生和编码器完全一样的码表 和编码器一样先初始化所有的单字符，将0-255之间的值分配给它们 除了解码第一个字符外，解码其它字符时都要更新码表 通过读码字并根据码表中的值将它们解码为对应的字符或字符组合18. LZ78参考资料： LZW：http:/www.cs.usyd.edu.au/loki/cs2csys/gif-info/lzw.html LZ78：http:/www.cs.usyd.edu.au/loki/cs2csys/gif-info/lz78.html