数据压缩的基本技术

1、数据压缩的基本技术北京邮电大学多媒体通信技术课程2离散无记忆信源的熵与概率分布的关系).,2,1(0)1()(nippxHiii)., 2, 1(1ninpi时nnH22maxlog1logbits/symbol1)(max1niiptosubjectXH条件极值)(.)()(2211nnspsspsspsXniisp11)(离散信源熵iiippXH2log)(bits/symbol3离散无记忆信源的熵与概率分布的关系 一个符号携带的信息量最大，同样信息量需要使用的符号数最少ppX1012n当当21psymbolbitH/1max00.51p1H,:pAX4信源的相关性与序列熵的关系)(.)(

2、)(2211nnspsspsspsXniisp11)()(.)()(2211mmtqttqttqtYmjjtq11)(ijijijrrYXH2log)( )/()()/()()(YXHYHXYHXHYXH给定 X 的条件下 条件熵22( /)loglog / ( )jiijijiijH Y XPrrp s假设离散信源是有记忆的：5信源的相关性与序列熵的关系)(XH)/(XYH)(YH)/()();(XYHYHYXI互信息假设离散信源是无记忆的：)()()(YHXHYXH)/()()(XYHXHYXH)()()/()(YHXHXYHXH)()()(maxYHXHYXH 信源符号之间无相关性时，联

3、合熵最大6通信系统的一般模型csTKTNcsTTNK11 Noiseless channel DecoderSink SourceA, p EncoderE, jSymbol rate 1/TsNAu Symbol rate 1/TcllppssA.11. aajjttE.1.1Nl# of source codes =Ka# of encoder codes = 1/Ts1/TcNmBv # of source codes =Ka率失真函数长度为 N 的码字的失真函数 NrrrrNVUdNd1),(1对于给定信源 A, p：Auup )(是确定的信宿的概率分布为)/()()(uvPupvqA

4、u UN 和 VN 间的互信息为)()/(log)/()()/()();(vquvPuvPupUVHVHVUINNBvAuNNNNN 问题问题： 当DdN 时，);(NNVUI至少要多大？或 至少需要传递多少信息，失真才足够小？率失真函数 );(min1)()/(NNPuvPVUINDRD 率失真函数 R(D) 是对信源信息率进行有损压缩的极限 对应于不同类型的信源、不同类型的编解码器（互 信息）和不同类型的失真度量函数，R(D)不同H(p)Dmax0R(D)D离散信源离散信源PD：所有满足 DdN （所有满足失真条件的编解码器)的条件概率的集合限失真信源编码定理 给定任意 和 ，可以找到正整

5、数N（N 充分大），以使一个长度为N 的（ ）容许码存在，且其信息率 。 换句话说，失真接近于D、而信息率接近于R(D) 的码是存在的。 对于 ， 前述离散无记忆信源可以在容量 的任何离散无记忆信道的输出端还原，而失真为 。00D ()RR D0()CR DDD压缩的途径和极限 无损压缩 解相关 （符号间互信息为零） 等概率 （信源熵） 有损压缩 率失真函数决定限失真压缩的极限 利用视觉特性的限制基本的压缩技术 Down-sampling (sub-sampling) Predictive coding (DPCM) Motion compensated predictive coding T

6、ransform coding Quantization Entropy coding 取样频率的转换下采样2 ：1 下采样？取样频率的转换下采样ffs2fs2424ffs2fsfs = 0.5 fs取样频率的转换下采样Antiaiasing fitr抗混叠滤波器 10)()()(NiinxihnwW(n)(nx)(nw)(my内插（上采样）Introation fitrIntroation fitr内插滤波器b = round(G + H)/2 10)()()(NiimwihmyW(m)？预测编码DPCMX12345 消除空间冗余（亮度、彩色） 1D 线性预测、2D 线性预测)()( 1in

7、xanxNii )( )()(nxnxne Z-1Z-Na1aN)(ne)(nx.预测器QDQ预测器)( nx)(nxPrediction error (residual)最佳预测器最小均方误差（最小均方误差（MMSE）意义下的最佳预测器）意义下的最佳预测器 min)., 2, 1(0)()(0)()()()(11NikiRaiRinxknxainxnxNkkNkk NkkkRaRne1min2)()0()(N阶预测器的设计：阶预测器的设计： 求 ai (I=1,2,N)最佳的准则：最佳的准则：最小均方误差（最小均方误差（minimum mean square error）)., 2, 1(0

8、)(2Nineai Niiinxanxne1)()()(量化误差的传播)()( 1inxanxNii)()(1inxanxNiiZ-1Z-Na1aN)(ne)(nx.预测器QDQ预测器)( nx)(nx)(ne)( nx收、发端的不匹配（Mismatch）DQ预测器)(nx)(nx)(neQDQ预测器)(nx闭环（Close Loop）预测器模仿接收环路序列图像中的冗余 静止物体在前后帧中完全相同 已知运动物体速度可以推算物体在下一帧中的位置 已知摄像机的运动参数(zoom, pan, tilt, rotation)可以推算下一帧的部分内容运动估值 编码：编码：比较 bk 和 bk-1 得到

9、(motion estimation) 解码解码：从 bk-1 和 得到 bkDD 假设 物体是刚体，且只在与摄 像机轴垂直的平面内平移 物体在任何位置上的照明 不变 不考虑 uncovered & covered backgroundDkk-1)()(1Dzbzbkk 运动矢量(Displacement vector)Motion Estimation Block matching Pel recursive Optical flow块匹配方法 在前一帧中找找到相似块到相似块k 帧k-1 帧搜索范围 SR（M+2dm)(N+2dm)MxN 什么是相似 如何搜索 “物体”： 不重叠的块

10、相似准则全搜索：全搜索：总移动次数为（2dm+1)2 (m,n)(m+i,n+j)（M+2dm)(N+2dm) MmNnkkjnimbnmbMNjiMAD111),(),(1),(mean absolute difference： ),(),(),(1),(2111mmMmNnkkdjidjnimbnmbMNjiMSE mean squared error：sum of absolute difference: MmNnkkjnimbnmbjiSAD111),(),(),(经典的搜索方法 全搜索 (2dm+1)2 三步法搜索点数：25搜索步骤 ：3正交搜索法搜索点数：13搜索步骤：6 搜索图形

11、搜索图形搜索算法的基本思想 沿判决函数减小 的方向搜索 判决函数非凸时， 容易搜索到局部极 值点D判决函数optD搜索方法的改进MV预测A组：median3 neighbors B组： C组： , MVk-1+(MVk-1-MVk-2) k-1 帧k 帧k-2 帧搜索方法的改进早期终止如果满足 A组： SAD T1 B组： SAD T2 C组： SAD 2, go to (1) then go to (4)(4) Assign codes1/31/41/51/61/2013/605/127/121.001000111x1x2x3x4x5X1: 00X2: 01X3: 11X4: 100X5:

12、101 给定符号集和概率模型， 找不到其他整数码比霍夫 曼码有更短的平均码长 概率大的符号用短码 概率小的符号用长码霍夫曼码的前缀特性 接收端必须已知码表 短码永远不是长码的开端X2 X5 X5 X2 X2 X3 .如果发生传输误差：0 1 0 0 1 1 0 1 0 1 0 1 1 1 .X2 X1 X3 X2 X2 X2 X3 . Prefix property:0 1 1 0 1 1 0 1 0 1 0 1 1 1 .Variable length codingX1: 00X2: 01X3: 11X4: 100X5: 101Error propogation算术编码的原理符号S1S2S3

13、S4概率（10 进制）0.1250.250.50.125概率（2 进制）p0.0010.010.10.001累积概率 P00.0010.0110.111S3: C=0+1x0.011 =0.011 A=1x0.1=0.1S3: C=0.011+0.1x0.011 =0.1001 A=0.1x0.1=0.01S2: C=0.1001+0.01x0.001 =0.10011 A=0.01x0.01=0.0001新编码点C 原编码点C原区间A x P新区间A 原区间A x pS3S2S1S4S1S2S3S41/83/87/8000.0010.0110.1111.01.0S3S2S1S40.0110.

14、01110.10010.11010.111S3S3S2算术编码的译码输入符号：输入符号： S3 S3 S2 .输出码字：输出码字： 0.10011 .新译码点C (原译码点C P）/ pS1S2S3S41/83/87/8000.0010.0110.1111.01.0S3(0.10011 0.011) / 0.1 = 0.01111S3(0.011110.011) / 0.1 = 0.0011S2算术编码的效率 编码点 C C + A x Pi 编码区间 A A x pi 表示最后编码点（即最后一个区间）所需要的比特数 熵21221222log (.)loglog.lognnTpppppp 1()logNiiiHXpp 二进制算术编码符号S1S2S3S4概率（10 进制）0.1250.250.50.125概率（2 进制） 0.0010.010.10.001累积概率00.0010.0110.111S1S4S2S3010101输入序列：输入序列： S3 S3 S2 . 0 0 10 1.001QeQeMPS： C C A A（1Qe）LPS： C C A（1Qe） A A Qe算术编码实现中的问题