1、第第04讲讲 预测编码及变换编码预测编码及变换编码多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院预测编码预测编码原理：原理：利用前面的一个或多个信号对下一个利用前面的一个或多个信号对下一个信号进行预测，然后对实际值和预测值的差信号进行预测，然后对实际值和预测值的差（预测误差）进行编码。（预测误差）进行编码。)|()|()|()(121211xxxxHxxxHxxHxHnnnnnnnnn第第n个符号个符号xn的熵满足：的熵满足： 参与预测的符号越多，预测就越准确，该参与预测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低
2、。信源的不确定性就越小，数码率就可以降低。多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院样本值样本值预测值预测值误差值误差值量化、编码、传输量化、编码、传输模型模型编码思路：编码思路：多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院y(n)差分脉冲编码调制差分脉冲编码调制a1D1D2DNa2aNQe(n)DQ预测器预测器+x(n)x(n)多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院由原理图可知：由原理图可知：1、收发两端必
3、须具有相同的预测条件。、收发两端必须具有相同的预测条件。2、预测系数为固定的情况称、预测系数为固定的情况称线性预测线性预测，根据，根据均匀误差最小准则获得的线性预测称均匀误差最小准则获得的线性预测称最佳线最佳线性预测性预测，此时压缩比最大。，此时压缩比最大。3、存在误码扩散现象。、存在误码扩散现象。多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院Qe(n)预测器预测器+x(n)x(n)可以证明可以证明：在相同的均方量化误差下，：在相同的均方量化误差下，e(n)比比x(n)要求较少的量化级数，即传送要求较少的量化级数，即传送e(n)的数据率
4、的数据率比比x(n)低。低。实际实现中实际实现中： 将量化器置于将量化器置于预测环路之内，通预测环路之内，通过反馈回路，可以过反馈回路，可以减少量化误差的积减少量化误差的积累。累。多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院序列图像中运动矢量的估值序列图像中运动矢量的估值运动矢量估值的必要性：运动矢量估值的必要性： 序列图像的相关性很大，通过运动矢量序列图像的相关性很大，通过运动矢量的估计可以极大地降低图像的数据传送率。的估计可以极大地降低图像的数据传送率。如何提取序列图像中的物体运动信息如何提取序列图像中的物体运动信息？ 块匹配方法
5、和递归方法块匹配方法和递归方法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院dmdmdmdmNM位移矢量位移矢量前一帧中的前一帧中的最佳匹配子块最佳匹配子块前一帧中的前一帧中的搜索区域搜索区域当前帧中当前帧中的子块的子块块匹配方法块匹配方法搜索范围搜索范围SR：SR=(M+2dm)(N+2dm)两个重要问题：两个重要问题：1. 匹配准则匹配准则2. 搜索方法搜索方法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院块匹配准则块匹配准则用以衡量用以衡量2子块的相似程度子块的相似程度常见
6、常见4种准则：种准则：1. 归一化二维互相关函数归一化二维互相关函数NCCF2/111212/1112111),(),(),(),(),(MmNnkMmNnkMmNnkkjnimbnmbjnimbnmbjiNCCF2. 均方差值均方差值MSEMmNnkkjnimbnmbMNjiMSE1121),(),(1),(3. 绝对均值绝对均值MADMmNnkkjnimbnmbMNjiMAD111| ),(),(|1),(多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院4. 匹配像素个数匹配像素个数NTAD) | ),(),(| ,(),(1110M
7、mNnkkjnimbnmbTfjiNTAD其中其中aTaTaTf00010),(搜索方法：搜索方法：1. 全搜索全搜索2. 二维对数法二维对数法3. 三步法三步法4. 共轭方向法共轭方向法5. 正交搜索法正交搜索法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院i-6 i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 i+4 i+5 i+6j+6j+5 j+4 j+3j+2 j+1 jj-1j-2 j-3j-4j-5 j-6 二维对数法二维对数法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学
8、与工程学院信息科学与工程学院i-6 i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 i+4 i+5 i+6j+6j+5 j+4 j+3j+2 j+1 jj-1j-2 j-3j-4j-5 j-6三步法三步法 多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院i-6 i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 i+4 i+5 i+6j+6j+5 j+4 j+3j+2 j+1 jj-1j-2 j-3j-4j-5 j-6 共轭方向法共轭方向法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换
9、编码信息科学与工程学院信息科学与工程学院i-6 i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 i+4 i+5 i+6j+6j+5 j+4 j+3j+2 j+1 jj-1j-2 j-3j-4j-5 j-6 正交法正交法多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院搜索方法搜索方法所需的搜索点数所需的搜索点数所需的搜索步骤所需的搜索步骤(a)(a)(b)(b)(a)(a)(b)(b)二维对数法二维对数法181821215 57 7三步法三步法252525253 33 3共轭正交法共轭正交法121215159 91212
10、正交搜索法正交搜索法131313136 66 6不同方法的搜索量不同方法的搜索量(dm=6,全搜索点数为全搜索点数为169(132)值得一提的是：值得一提的是：如果有条件并行计算，减少搜索步骤比减少搜索点如果有条件并行计算，减少搜索步骤比减少搜索点数更重要数更重要多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院像素递归法像素递归法思路：首先将图像中的运动部分和静止部分区分开来思路：首先将图像中的运动部分和静止部分区分开来 再在每个像素点上通过迭代计算位移矢量。再在每个像素点上通过迭代计算位移矢量。iiiUDD1分割分割取位移矢量取位移矢量
11、形成预测值形成预测值计算预测误差计算预测误差小于阈值小于阈值可预测可预测对误差进行量对误差进行量化、编码、传输化、编码、传输大于阈值大于阈值多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院像素递归法像素递归法难点：难点：1. 首先要区分运动和静止部分首先要区分运动和静止部分2. 对每一个像素都要计算，计算量大对每一个像素都要计算，计算量大3. 计算复杂计算复杂4. 计算的收敛性问题计算的收敛性问题 迭代准则：迭代准则： 使使DFD(前一帧图像与当前帧图像差值前一帧图像与当前帧图像差值)的平方最的平方最小小212)()(),(ikkiDzb
12、zbDzDFD多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院快速算法的改进：快速算法的改进： 避免局部最小点和缩短搜索时间避免局部最小点和缩短搜索时间策略策略： 1. 运动矢量估计运动矢量估计 2. 提前中止搜索：中止阈值提前中止搜索：中止阈值 3. 紧凑的搜索图形紧凑的搜索图形 多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院具有运动补偿的帧间预测具有运动补偿的帧间预测前向预测：前向预测： 只传送当前帧与前只传送当前帧与前1帧图像对应像素点的差值帧图像对应像素点的差值步骤步骤：
13、1.区分静止背景和运动物体，通过运动估值得到运动矢量区分静止背景和运动物体，通过运动估值得到运动矢量 2. 利用运动矢量得到运动补偿后的预测值利用运动矢量得到运动补偿后的预测值 3. 对预测误差进行编码、传送，并传送运动矢量及分割等信息对预测误差进行编码、传送，并传送运动矢量及分割等信息 量化量化预测预测+预测误差预测误差分割分割运动估值运动估值分割的地址分割的地址运动矢量运动矢量输入输入多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院后向预测与双向预测后向预测与双向预测后向预测：后向预测： 从后续的图像帧预测前面的图像帧从后续的图像帧预
14、测前面的图像帧双向预测：双向预测： 由前、后两帧来预测中间的图像帧由前、后两帧来预测中间的图像帧k+1帧帧k帧帧k1帧帧多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院 具有运动补偿的帧内内插具有运动补偿的帧内内插方法：方法：)()()(BbtAbtCbii 1. 重复显示重复显示2. 线性内插线性内插传送帧传送帧丢弃帧丢弃帧传送帧传送帧t1CBA采用亚取样，在发送端每隔一段时间丢掉采用亚取样，在发送端每隔一段时间丢掉n帧图像，帧图像，在接收端根据帧间相关性恢复丢弃帧。在接收端根据帧间相关性恢复丢弃帧。适用于低速系统，如可视电话、电视会议
15、等适用于低速系统，如可视电话、电视会议等多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院区别对待区别对待4种区域：种区域：1. 静止背景静止背景2. 运动物体运动物体3. 被覆盖的背景被覆盖的背景4. 新暴露的背景新暴露的背景)1 ()()1 ()(1DazabaDzbazbkki这是处理方式为：这是处理方式为：)()()( 1 0 新暴露部分被覆盖部分静止或运动部分 ita其中：其中：多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院变换编码变换编码 将空域（时域）的图像信号变换到另
16、一个正交将空域（时域）的图像信号变换到另一个正交矢量空间，并对产生的变换系数进行编码处理。矢量空间，并对产生的变换系数进行编码处理。 经过正交变换后为什么能够压缩数据量？经过正交变换后为什么能够压缩数据量？ 设有两个相邻的数据样本设有两个相邻的数据样本x x1 1,x,x2 2，每样本用每样本用3bit3bit编码，则编码，则各有各有8 8个幅度等级，两个样本的联合事件有个幅度等级，两个样本的联合事件有8 88=648=64种可能性。种可能性。 对于慢变信号，相邻两样本同时出现相近幅度等级的可能对于慢变信号，相邻两样本同时出现相近幅度等级的可能性较大。性较大。 进行正交变换后，相关圈正好处在进
17、行正交变换后，相关圈正好处在y y1 1上下，且相关圈越扁上下，且相关圈越扁长，在长，在y y1 1上的投影越大，而在上的投影越大，而在y y2 2上的投影越小，这意味着上的投影越小，这意味着y y1 1和和y y2 2趋于统计独立。趋于统计独立。多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院变换编码工作原理变换编码工作原理变换变换量化量化编码器编码器解码器解码器逆变换逆变换信信道道输入输入发送端发送端接收端接收端输出输出GGUUAA多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院
18、正交变换编码正交变换编码关键关键：寻找最佳正交变换，使得在恢复：寻找最佳正交变换，使得在恢复X时所时所 产生的均方误差最小产生的均方误差最小如正交变换：如正交变换：TXY 线性正交变换线性正交变换卡南洛伊夫变换卡南洛伊夫变换(KL) ： 均方误差准则下的最佳变换矩阵均方误差准则下的最佳变换矩阵为为 以信号的协方差矩阵以信号的协方差矩阵X X的本征向量的本征向量i i ( (i i=1,2,=1,2,N N) )组成的变换矩阵组成的变换矩阵多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院准最佳正交变换：准最佳正交变换： 离散傅里叶变换（离散
19、傅里叶变换（DFT）、哈尔变换）、哈尔变换(HRT)、 WalshHadamard变换变换(WHT)、斜变换、斜变换(SLT)、 离散余弦变换离散余弦变换(DCT)、离散正弦变换、离散正弦变换(DST)等。等。从变换后的能量集中程度的优劣来看，各种正交变换从变换后的能量集中程度的优劣来看，各种正交变换的由优至劣的顺序为：的由优至劣的顺序为： KLTDCTSLTDFTWHTHRT若从运算量的大小，它们由小到大的顺序依次为若从运算量的大小，它们由小到大的顺序依次为 HRTWHTSLTDCTDFTKLT 多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与
20、工程学院离散余弦变换离散余弦变换一维一维DCT正变换和反变换为：正变换和反变换为：102/1102/1) 1, 2 , 1 , 0(2) 12(cos)()()2()() 1, 2 , 1 , 0(2) 12(cos)()()2()(NnNkNnNnknSnCNksNnNnkksnCNnS 121)( nCn0n0其中，其中，s(k)为信号样值，为信号样值，S(n)为变换系数为变换系数多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院)1()1 ()0(2)1)(12(cos2)1(3cos2)1(cos2)12(cos23cos2cos2
21、121212)1()1 ()0(NsssNNNNNNNNNNNNNSSS 一维一维DCT变换的矩阵形式变换的矩阵形式PsS 一维一维DCT变换矢量形式变换矢量形式记为矢量记为矢量PSPsT一维一维IDCT变换矢量形式变换矢量形式多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院二维二维DCT正变换和反变换为：正变换和反变换为：) 1, 2 , 1 , 0; 1, 2 , 1 , 0(2) 12(cos2) 12(cos),()()(2),() 1, 2 , 1 , 0; 1, 2 , 1 , 0(2) 12(cos2) 12(cos),()
22、()(2),(10101010NkNjNvkNujvuSvCuCNkjsNvNuNvkNujkjsvCuCNvuSNuNvNjNk 121)(uCu0u0其中：其中：121)(vCv0v0多媒体通信技术：预测编码及变换编码多媒体通信技术：预测编码及变换编码信息科学与工程学院信息科学与工程学院89101 114 125 126 115 1059697115 131 147 149 135 123 113114 134 159 178 175 164 149 137121 143 177 196 201 189 165 150119 141 175 201 207 186 162 144107 130 165 189 192 171 144 12597119 149 171 172 145 1179688107 136 156 155 1299775直流直流DC基函数基函数水平方向频率增加水平方向频率增加垂直方向频率增加垂直方向频率增加DCT变换变换
