第五章序列图像编码及运动估计

1、第五章第五章 序列图像编码及运动估计序列图像编码及运动估计中国矿业大学中国矿业大学信电学院信电学院l 5.1 概述概述l 5.2 视频信号的数字化视频信号的数字化l 5.3 二维运动估计二维运动估计l 5.4 采用时间预测和变换编码的视采用时间预测和变换编码的视 频编码频编码 5.1 概述概述 概念：概念：活动图像信号，也称为数字序列图像或连活动图像信号，也称为数字序列图像或连续帧图像，指续帧图像，指由多幅尺寸相同的静止图像组成的图由多幅尺寸相同的静止图像组成的图像序列像序列。例如数字化后的电视或视频信号。例如数字化后的电视或视频信号。 其中的每幅静止图像称为一个帧。其中的每幅静止图像称为一个

2、帧。 活动图像活动图像与静止图像相比，可以认为多了一个与静止图像相比，可以认为多了一个时间轴，成为三维信号，因此时间轴，成为三维信号，因此活动图像活动图像也被称为也被称为三三维图像。维图像。活动图像都是一帧一帧地传输，看作一个沿时间轴活动图像都是一帧一帧地传输，看作一个沿时间轴分布的图像序列，统称为序列图像。分布的图像序列，统称为序列图像。这里主要讨论序列图像中的视频图像的压缩编码这里主要讨论序列图像中的视频图像的压缩编码视频图像压缩编码分类：视频图像压缩编码分类： 帧内编码帧内编码：也称为空间压缩。利用每幅：也称为空间压缩。利用每幅( (单帧单帧) )图像内部的相关性进行帧内压缩编码。当压缩

3、一图像内部的相关性进行帧内压缩编码。当压缩一帧图像时，仅考虑本帧的数据而不考虑相邻帧之帧图像时，仅考虑本帧的数据而不考虑相邻帧之间的冗余信息。帧内一般采用有损压缩算法。间的冗余信息。帧内一般采用有损压缩算法。压压缩后的视频数据仍可以以帧为单位进行编辑。帧缩后的视频数据仍可以以帧为单位进行编辑。帧内压缩一般达不到很高的压缩。内压缩一般达不到很高的压缩。 帧间编码帧间编码：也称为时间压缩。利用时间轴上相：也称为时间压缩。利用时间轴上相邻帧之间的相关性邻帧之间的相关性( (前后两帧信息变化很小前后两帧信息变化很小) )进行进行帧间压缩编码。帧间压缩一般是无损的。帧间压缩编码。帧间压缩一般是无损的。

4、混合编码混合编码：为不同的编码方法组合在一起相结：为不同的编码方法组合在一起相结合的编码方法。如变换编码和帧间预测编码。合的编码方法。如变换编码和帧间预测编码。视频图像编码要求：视频图像编码要求： 实时性实时性：图像传输系统必须能实时地对活动电视：图像传输系统必须能实时地对活动电视 图像进行编码传输。图像进行编码传输。 高效性高效性：必须能使数字视频信号以一定目标码率：必须能使数字视频信号以一定目标码率 传输。如视频信号传输。如视频信号8bit/像素，数码率高像素，数码率高 达达216Mbit/s。视频图像编码目的：视频图像编码目的：在保证一定重建质量前提下，以尽量少数据量来在保证一定重建质量

5、前提下，以尽量少数据量来表征视频信息，以减少视频序列的码率，便于能表征视频信息，以减少视频序列的码率，便于能够在给定的通信信道上实时传输视频信号。够在给定的通信信道上实时传输视频信号。5.2 视频信号的数字化视频信号的数字化 5.2.1 电视制式电视制式 帧：一段视频中的每一幅图像称为一帧。帧：一段视频中的每一幅图像称为一帧。 根据视觉暂留原理，要使人的视觉产生连续的动根据视觉暂留原理，要使人的视觉产生连续的动态感觉，每秒钟图像的播放帧数要在态感觉，每秒钟图像的播放帧数要在24243030（帧频）（帧频） 帧频：每秒播放的帧数。帧频：每秒播放的帧数。电视制式：即电视的播放标准（扫描分辨率、帧电

6、视制式：即电视的播放标准（扫描分辨率、帧频、色彩空间的转换关系不同）。频、色彩空间的转换关系不同）。 目前国际上有三种不同的电视制式目前国际上有三种不同的电视制式: NTSC; PAL; SECAMu NTSC(national television system committee),u 是国家电视制式委员会的缩写。是国家电视制式委员会的缩写。u 美国研制的一种与黑白电视兼容的彩色电视制式。美国研制的一种与黑白电视兼容的彩色电视制式。l帧频：每秒播放帧频：每秒播放30帧画面帧画面l扫描行数（扫描分辨率）：每帧有扫描行数（扫描分辨率）：每帧有526行像素行像素l美国、加拿大、日本、韩国、菲律宾

7、、台湾等美国、加拿大、日本、韩国、菲律宾、台湾等 NTSC制式优点：制式优点：在信号传输无失真情况下，具有比较高彩色图在信号传输无失真情况下，具有比较高彩色图像质量；兼容性好；重现的彩色图像无明显的像质量；兼容性好；重现的彩色图像无明显的“爬行爬行”和亮度闪烁现象；较易于实现信号处和亮度闪烁现象；较易于实现信号处理；色度信号的形成和分离都比较简单。理；色度信号的形成和分离都比较简单。u PAL(Phase Alternation Line), 是相位逐行交替的缩写。西德在是相位逐行交替的缩写。西德在1962年研制的一年研制的一种与黑白电视兼容的彩色电视制式。种与黑白电视兼容的彩色电视制式。l帧

8、频：每秒播放帧频：每秒播放25帧画面帧画面l扫描行数（扫描分辨率）：每帧有扫描行数（扫描分辨率）：每帧有625行像素行像素l西欧国家、新加坡、澳大利亚、中国大陆以及香西欧国家、新加坡、澳大利亚、中国大陆以及香港等港等 PAL制式基本原理：制式基本原理：采用逐行倒相正交平衡调幅的色度信号，解采用逐行倒相正交平衡调幅的色度信号，解调时先经过逐行梳状滤波器将色度信号分离调时先经过逐行梳状滤波器将色度信号分离后再同步检波；最后利用视觉平均作用补偿后再同步检波；最后利用视觉平均作用补偿小幅度串色所引起的彩色偏差。小幅度串色所引起的彩色偏差。 PAL制式优点：制式优点：对相位失真不敏感，多径接收对对相位失

9、真不敏感，多径接收对PAL信号影信号影响小。响小。u SECAM (Sequential Couleur Avec Memoire) u 是顺序与存储彩色电视系统的缩写。是顺序与存储彩色电视系统的缩写。 法国研制的一种与黑白电视兼容的彩色电视制式；法国研制的一种与黑白电视兼容的彩色电视制式；l 帧频：每秒播放帧频：每秒播放2525帧画面帧画面l 扫描行数（扫描分辨率）：每帧有扫描行数（扫描分辨率）：每帧有625625行像素行像素l 法国、俄罗斯等东欧国家和中东一带法国、俄罗斯等东欧国家和中东一带 SECAM制式优点：制式优点：传输失真对色度信号影响小，大面积彩色图像几乎传输失真对色度信号影响小

10、，大面积彩色图像几乎不受微分增益和微分相位失真的影响，受传输通道不受微分增益和微分相位失真的影响，受传输通道频率特性和多径接收的影响也不大。频率特性和多径接收的影响也不大。SECAMSECAM是一种顺序同时制。是采用错开传输时是一种顺序同时制。是采用错开传输时间的方法（时分原则）来避免串色以及造成的间的方法（时分原则）来避免串色以及造成的彩色失真。彩色失真。SECAM编码解码方式与编码解码方式与PAL制式完全不同。制式完全不同。 不同电视制式的技术指标不同电视制式的技术指标TV制式制式NTSCPALSECAM帧频帧频/Hz302525行行/帧帧525625625亮度带宽亮度带宽/MHz4.26

11、.06.0彩 色 幅 载 波彩 色 幅 载 波/MHz3.584.434.25色度带宽色度带宽/MHz1.3(I)，0.6(Q)1.3(U)，1.3(V)1.0(U)，1.0(V)声音载波声音载波/MHz4.56.56.55.2.2 视频信号的数字化视频信号的数字化l（1）复合数字化：复合数字化：先用高速模先用高速模/数转换器对彩色全数转换器对彩色全电视信号进行数字化，然后在数字域中进行分离亮电视信号进行数字化，然后在数字域中进行分离亮度和色度，以获得所希望的度和色度，以获得所希望的YUV（PAL，SECAM制）分量或制）分量或YIQ（NTSC制）分量，最后转换成制）分量，最后转换成RGB分量

12、数据。此种方法称为分量数据。此种方法称为复合数字化复合数字化。l（2）分量数字化：分量数字化：从复合彩色电视图像中分离出从复合彩色电视图像中分离出彩色分量的亮度和色度，得到彩色分量的亮度和色度，得到YUV或或YIQ分量，然分量，然后用后用3个模个模/数转换器对数转换器对3个分量分别进行数字化，个分量分别进行数字化，最后再转换成最后再转换成RGB空间，此种方法称为空间，此种方法称为分量数字分量数字化化。 分量数字化是视频信号数字化的主流。分量数字化是视频信号数字化的主流。1视频信号数字化方法分类视频信号数字化方法分类 2视频信号采样结构的选择视频信号采样结构的选择 概念概念：采样结构是指采样点在

13、空间与时间上的相对位置。采样结构是指采样点在空间与时间上的相对位置。 采样结构分类采样结构分类： 正交结构：在图像平面上沿着水平方向采样点等正交结构：在图像平面上沿着水平方向采样点等间隔排列，沿垂直方向采样点上下对齐排列。间隔排列，沿垂直方向采样点上下对齐排列。 行交叉结构：每行内采样点数为整数加半个。行交叉结构：每行内采样点数为整数加半个。（a） 正交结构正交结构（b） 行交叉结构行交叉结构3数字视频的采样格式数字视频的采样格式 在复合电视信号中，亮度信号的带宽是色度信在复合电视信号中，亮度信号的带宽是色度信号带宽的两倍号带宽的两倍因此其因此其数字化时可采用对信号的数字化时可采用对信号的色差

14、分量的采样率低于对亮度分量的采样率色差分量的采样率低于对亮度分量的采样率。用。用Y:U:V来表示来表示YUV三分量的采样比例，则数字视三分量的采样比例，则数字视频的采样格式有如下频的采样格式有如下4种：种： （1）Y:U:V=4:4:4 l指在每条扫描线上在水平和垂直方向上每指在每条扫描线上在水平和垂直方向上每4个连个连续的取样点取续的取样点取4个亮度个亮度Y样本、样本、4个红色差个红色差Cr样本样本和和4个蓝色差个蓝色差Cb样本，相当于每个像素包含样本，相当于每个像素包含3个个样本。即对每个采样点，亮度样本。即对每个采样点，亮度Y、色差、色差U和和V各取各取一个样本，也就是每个像素用一个样本

15、，也就是每个像素用3个样本表示。个样本表示。 采样格式采样格式4:4:4采样格式采样格式4:2:2采样格式采样格式表示亮度表示亮度Y采样点采样点表示色度表示色度UV采样点采样点 （2）Y:U:V=4:2:2 l这种方式指在每条扫描线上，在每这种方式指在每条扫描线上，在每4个连续的采样个连续的采样点上，取点上，取4个亮度个亮度Y的样本值，而色差的样本值，而色差U、V分别取分别取其第一点和第三点的样本值，共其第一点和第三点的样本值，共8个样本，平均每个样本，平均每个像素用个像素用2个样本表示。这种方式能给信号的转换个样本表示。这种方式能给信号的转换留有一定余量，效果更好一些。留有一定余量，效果更好

16、一些。l这是通常所用的方式，每这是通常所用的方式，每4个连续的采样点取个连续的采样点取4个个亮度亮度Y样本、样本、2个红色差个红色差Cr样本和样本和2个蓝色差个蓝色差Cb样样本，结果相当于平均每个像素用本，结果相当于平均每个像素用2个样本表示。个样本表示。l 色度信号在水平方向上采样点数为亮度信号的一色度信号在水平方向上采样点数为亮度信号的一半，而在垂直方向上的采样点数相同。半，而在垂直方向上的采样点数相同。 （3）Y:U:V=4:1:1l这种方式是在每这种方式是在每4个连续的采样点上，取个连续的采样点上，取4个亮个亮度度Y的样本值，而色差的样本值，而色差U、V分别取其第一点的分别取其第一点的

17、样本值，共样本值，共6个样本，每个像素用个样本，每个像素用1.5个样本表个样本表示。示。 l 色差信号在色差信号在在水平方向上采样点数为亮度信号的在水平方向上采样点数为亮度信号的1/41/4，而在垂直方向上的采样点数相同。，而在垂直方向上的采样点数相同。采样格式采样格式4:1:1采样格式采样格式表示亮度表示亮度Y采样点采样点表示色度表示色度UV采样点采样点（4）Y:U:V=4:2:04:2:0子采样格式是指分别在水平和垂直方向子采样格式是指分别在水平和垂直方向上每上每2个连续的采样点上取个连续的采样点上取2个亮度个亮度Y样本、样本、1个红色差个红色差Cr样本和样本和1个蓝色差个蓝色差Cb样本，

18、平均每样本，平均每个像素用个像素用1.5个样本表示。个样本表示。 色差信号分别在水平方向和垂直方向上采样点色差信号分别在水平方向和垂直方向上采样点数为亮度信号的数为亮度信号的1/21/2。采样格式采样格式4:2:0采样格式采样格式4:2:0采样格式采样格式表示亮度表示亮度Y采样点采样点表示色度表示色度UV采样点采样点MPEG1、H.261支持支持MPEG2支持支持扫描方式小结扫描方式小结l电视图像既是空间的函数，也是时间的函数，电视图像既是空间的函数，也是时间的函数，而且又是隔行扫描式，所以其采样方式比扫描而且又是隔行扫描式，所以其采样方式比扫描仪扫描图像的方式要复杂得多。分量采样时采仪扫描图

19、像的方式要复杂得多。分量采样时采到的是隔行样本点，要把隔行样本组合成逐行到的是隔行样本点，要把隔行样本组合成逐行样本，然后进行样本点的量化，样本，然后进行样本点的量化，YUV到到RGB色彩空间的转换等，最后才能得到数字视频数色彩空间的转换等，最后才能得到数字视频数据。据。 4数字视频标准数字视频标准 为了在为了在PAL、NTSC和和SECAM电视制式之间电视制式之间确定共同的数字化参数，国际无线电咨询委员会确定共同的数字化参数，国际无线电咨询委员会（CCIR）制订了）制订了广播级质量的数字电视编码标准广播级质量的数字电视编码标准，称为称为CCIR 601标准标准。该标准规定了彩色电视图像。该标

20、准规定了彩色电视图像转换成数字图像时使用的采样频率，彩色空间之转换成数字图像时使用的采样频率，彩色空间之间的转换关系等。间的转换关系等。（1）采样频率）采样频率 ITU-RBT.601标准为三种电视制式规定了共同的标准为三种电视制式规定了共同的电视图像采样频率。其基本的计算方法是：电视图像采样频率。其基本的计算方法是：对对PAL制、制、SECAM制，采样频率制，采样频率fs为：为： fs=62525N=15625N=13.5 MHz，N=864 其中：其中：N为每一扫描行上的采样数目。在为每一扫描行上的采样数目。在PAL制、制、SECAM制中，制中，625是指行数，是指行数，25表示每秒帧数。

21、表示每秒帧数。 （2）有效显示分辨率）有效显示分辨率 对对PAL制和制和SECAM制的亮度信号，每一条扫描制的亮度信号，每一条扫描行采样行采样864个样本；对个样本；对NTSC制的亮度信号，每一条制的亮度信号，每一条扫描行采样扫描行采样858个样本。个样本。为了使这些制式的采样点兼为了使这些制式的采样点兼容，规定每一扫描行的有效样本数均为容，规定每一扫描行的有效样本数均为720720个。个。（3）数据量）数据量 CCIR 601规定，每个样本点都按规定，每个样本点都按8位数字位数字化，即有化，即有256个等级。但实际上亮度信号占个等级。但实际上亮度信号占220级、色度信号占级、色度信号占225

22、级，其他位作同步、编码级，其他位作同步、编码等控制用。如果按等控制用。如果按fs的采样率和的采样率和4:2:2的格式采的格式采样，则数字视频的数据量为：样，则数字视频的数据量为： 13.5(MHz)8(bit)+26.75(MHz)8(bit)=27MB/s （4）CIF、QCIF和和SQCIF 为了兼容为了兼容625行的电视图像和行的电视图像和525行的电视图像，行的电视图像，CCITT定义了定义了公用公用中分辨率格式中分辨率格式CIF（Common Intermediate Format），），1/4公用中分辨率格式公用中分辨率格式（Quarter-CIF，QCIF）和和（Sub-Quar

23、ter Common Intermediate Format，SQCIF）格式格式。CIF格式具有如下特性：格式具有如下特性：l 电视图像的空间分辨率为电视图像的空间分辨率为352288。l 使用非隔行扫描（使用非隔行扫描（Non-Interlaced Scan）。）。 使用使用NTSC帧速率，电视图像的最大帧速率为帧速率，电视图像的最大帧速率为30 000/100129.97幅幅/秒。秒。CIF QCIFSQCIF行数行数/帧帧像素像素/行行行数行数/帧帧像素像素/行行行数行数/帧帧像素像素/行行亮度（亮度（Y）288360(352)144180(176)96128色度（色度（Cb）1441

24、80(176)7290(88)4864色度（色度（Cr）144180(176)7290(88)4864 下表是下表是CIF、QCIF和和SQCIF图像格式参数。图像格式参数。5.3 视频信号编码方法视频信号编码方法 一、一、视频信号视频信号编码的依据：编码的依据：1 1、视频信号编码的出发点：、视频信号编码的出发点： 对于活动图像，相邻帧的时间间隔很短对于活动图像，相邻帧的时间间隔很短(1/25(1/25 1/30s),1/30s),在景物运动不很剧烈场合，相邻帧在景物运动不很剧烈场合，相邻帧间相关性很强。间相关性很强。编码时充分利用活动图像的相邻编码时充分利用活动图像的相邻帧帧( (在时间轴

25、方向在时间轴方向) )的相关性进行预测。的相关性进行预测。2 2、视频信号视频信号编码的依据：编码的依据： 依据依据1 1：从信源角度看，自然景物大多都处于相从信源角度看，自然景物大多都处于相对不变或缓变状态，为帧间相关性存在前提条件。对不变或缓变状态，为帧间相关性存在前提条件。5.3.1 视频信号编码基础视频信号编码基础帧间预测典型情况：可视电话图像帧间预测典型情况：可视电话图像 可视电话图像内容通常为一个细节不十分复杂可视电话图像内容通常为一个细节不十分复杂背景前，有一个活动量不大的单个人物的头背景前，有一个活动量不大的单个人物的头- -肩像。肩像。假定人位置在假定人位置在第第k帧与第帧与

26、第k-1帧相比有一定帧相比有一定x方向位移方向位移,可可将画面分为将画面分为3个各具特点区个各具特点区域：域：背景区、运动物体区、暴露区背景区、运动物体区、暴露区背景区背景区：指摄像机不动而摄取人物后面的背景。：指摄像机不动而摄取人物后面的背景。 一般背景区是静止的，若外界条件不变，则一般背景区是静止的，若外界条件不变，则这两帧背景区绝大部分数据相同，意味着两帧背这两帧背景区绝大部分数据相同，意味着两帧背景区之间帧间相关性很强。景区之间帧间相关性很强。运动物体区运动物体区：若将物体运动近似看作简单平移，则：若将物体运动近似看作简单平移，则第第k帧与第帧与第k-1-1帧的运动区的数据也基本相同。

27、帧的运动区的数据也基本相同。简单平移看作只有简单平移看作只有x方向位移量方向位移量Dx，则可采用某种位，则可采用某种位移估值方法对位移量进行移估值方法对位移量进行“运动补偿运动补偿”。暴露区暴露区：指在运动后所暴露出的原来曾被物体遮盖：指在运动后所暴露出的原来曾被物体遮盖住区域。住区域。 若有存储器将这暴露区的数据暂时存储，则再次若有存储器将这暴露区的数据暂时存储，则再次经遮盖后再暴露出来的数据与原先存储数据相同，经遮盖后再暴露出来的数据与原先存储数据相同，这为一帧间相关性。这为一帧间相关性。注意：注意：如果将整个画面从一类景物切换为另一类景如果将整个画面从一类景物切换为另一类景物时，则谈不上

28、帧间相关性利用。因为整个画面内物时，则谈不上帧间相关性利用。因为整个画面内容数据全部改变了。容数据全部改变了。 这三类区域的帧间相关性是帧间压缩编码的重这三类区域的帧间相关性是帧间压缩编码的重要依据。要依据。 依据依据2 2：利用人眼视觉特性，在活动图像编码中利用人眼视觉特性，在活动图像编码中针对图像内容在清晰度和活动性针对图像内容在清晰度和活动性( (帧频帧频) )适当调整码适当调整码率，可使重建图像在视觉上保持一致主观效果。率，可使重建图像在视觉上保持一致主观效果。 保证对于传输序列图像的静止部分的较高空间分保证对于传输序列图像的静止部分的较高空间分辨率。同时，可降低时间轴分辨率，通过抽帧

29、或跳帧辨率。同时，可降低时间轴分辨率，通过抽帧或跳帧减少传输帧数，在接收端依靠帧存储器把未传输帧补减少传输帧数，在接收端依靠帧存储器把未传输帧补充。充。 可降低序列图像中的运动物体部分的分辨率。物可降低序列图像中的运动物体部分的分辨率。物体的运动速度愈高，可用更低清晰度进行传输。体的运动速度愈高，可用更低清晰度进行传输。二、视频信号编码的关键问题：二、视频信号编码的关键问题：n 对于序列图像中大量存在的静止或缓变区域，对于序列图像中大量存在的静止或缓变区域，？n 对于静止区域如何压缩编码？对于静止区域如何压缩编码？n 对于运动区域如何压缩编码？对于运动区域如何压缩编码？设第设第k帧图像位于位置

30、帧图像位于位置z=(x, y)的像素采样值为的像素采样值为Ik(z)。其预测值其预测值 为第为第k-1帧图像帧图像(前一帧图像前一帧图像)的相对应的相对应同一位置处像素复原值同一位置处像素复原值Ik-1(z)。则有：。则有：)(zIk(z)I(z)I(z)I(z)I(z)FD(z)I(z)Ikkkkk1k1k 定义一定义一阈值阈值TH，则有：，则有： 若若|FDk(z)| TH ，认为，认为Ik(z)位于图像相对静止部分位于图像相对静止部分 (背景区背景区) 若若|FDk(z)| TH ，认为，认为Ik(z)位于图像运动区域。位于图像运动区域。帧间差帧间差v 帧（场）重复工作形式：帧（场）重复

31、工作形式：l 通常用在可视电话等传输码率很低应用场合。通常用在可视电话等传输码率很低应用场合。l 在序列图像传输中进行抽帧，使少传一些帧。在序列图像传输中进行抽帧，使少传一些帧。l 在接收端可以采用对前帧重复读出方式补满。在接收端可以采用对前帧重复读出方式补满。v 运动估计与补偿预测方法：运动估计与补偿预测方法：l相邻画面高度相似，其中差别变化是由于物体相邻画面高度相似，其中差别变化是由于物体运动或摄象机运动所引起的。运动或摄象机运动所引起的。l 画面中物体或像素的运动是可以估计的。画面中物体或像素的运动是可以估计的。l 因此，可以因此，可以从前面的画面预测当前画面，编码从前面的画面预测当前画

32、面，编码器只对预测误差进行编码器只对预测误差进行编码。l 不能进行预测的画面或区域使用不能进行预测的画面或区域使用JPEG进行编进行编码（利用画面内部相关性）。码（利用画面内部相关性）。l相邻帧间的主要变化是由于构成景物的各物相邻帧间的主要变化是由于构成景物的各物体的运动引起的。体的运动引起的。5.3.2 运动估计与补偿的基本概念运动估计与补偿的基本概念 定义定义：将活动图像分为若干个块，检测出当前帧中：将活动图像分为若干个块，检测出当前帧中每个块在前一帧每个块在前一帧(参考帧参考帧)图像中的对应位置，从而可图像中的对应位置，从而可以估计出这个块的位移，用运动矢量表示。这个过程以估计出这个块的

33、位移，用运动矢量表示。这个过程叫做运动估计。叫做运动估计。 运动估计通常以宏块为单位进行，计算被压缩图像运动估计通常以宏块为单位进行，计算被压缩图像与参考图像在对应位置处的宏块间的位置偏移。与参考图像在对应位置处的宏块间的位置偏移。 该位置偏移是以运动矢量描述，代表水平和垂直两该位置偏移是以运动矢量描述，代表水平和垂直两个方向的位移。个方向的位移。1. 运动估计运动估计场景中物体运动反场景中物体运动反映在画面中，表现映在画面中，表现为当前画面部分内为当前画面部分内容是前一画面部分容是前一画面部分内容的位移运动。内容的位移运动。 2. 运动补偿运动补偿 定义定义：就是根据求出的运动矢量，找到当：

34、就是根据求出的运动矢量，找到当前帧的像素（或像素块）是从前一帧的哪个前帧的像素（或像素块）是从前一帧的哪个位置移动过来的，从而得到当前帧像素（或位置移动过来的，从而得到当前帧像素（或像素块）的预测值。像素块）的预测值。 由于用当前帧在前一帧图像中对应部分来对当前由于用当前帧在前一帧图像中对应部分来对当前帧进行预测，而相邻两帧中对应的运动部分图像信帧进行预测，而相邻两帧中对应的运动部分图像信息会有所不同，所以一般会产生补偿残差。息会有所不同，所以一般会产生补偿残差。 运动估计及补偿的基本原理运动估计及补偿的基本原理：利用帧间运动估计：利用帧间运动估计得到待编码图像块的一个（或多个）参考块，然后得

35、到待编码图像块的一个（或多个）参考块，然后用这个参考块进行运动补偿，将补偿后用这个参考块进行运动补偿，将补偿后残差进行残差进行DCT变换和可变长编码。变换和可变长编码。3. 运动补偿帧间预测编码运动补偿帧间预测编码定义：定义：对于运动的物体，如果能估计出物体在相邻对于运动的物体，如果能估计出物体在相邻帧内的相对位移，那么用上一帧中物体的对应区域帧内的相对位移，那么用上一帧中物体的对应区域对当前帧物体进行预测，编码传输预测误差部分，对当前帧物体进行预测，编码传输预测误差部分，就可压缩这部分区域的码率。这种考虑了运动物体就可压缩这部分区域的码率。这种考虑了运动物体对应区域的位移或运动的预测方式称为

36、运动补偿帧对应区域的位移或运动的预测方式称为运动补偿帧间预测编码。间预测编码。帧间运动估计与补偿预测的基本过程帧间运动估计与补偿预测的基本过程运动补偿帧间预测编码原理框图：运动补偿帧间预测编码原理框图：压缩图像块压缩图像块输入图像块输入图像块e en nf fn n f fn n运动补偿预测帧间误差图像运动补偿预测帧间误差图像运动补偿预测图像运动补偿预测图像nnnffe 其中：其中：fn 为输入图像块；为输入图像块； fn 为运动补偿预测图像为运动补偿预测图像运动补偿帧间预测编码技术的组成：运动补偿帧间预测编码技术的组成： 物体的划分物体的划分：划分静止区域和运动区域。这里：划分静止区域和运动

37、区域。这里假设运动物体仅作平移。假设运动物体仅作平移。 运动估计运动估计：对每一个运动物体进行位移估计。：对每一个运动物体进行位移估计。 运动补偿运动补偿：由位移估值建立同一运动物体在不：由位移估值建立同一运动物体在不同帧空间位置对应关系，建立预测关系。同帧空间位置对应关系，建立预测关系。 补偿后的预测信息编码补偿后的预测信息编码：对运动物体的补偿后：对运动物体的补偿后的位移帧差信号的位移帧差信号DFD，以及运动矢量等进行编码，以及运动矢量等进行编码传输。传输。5.3.3 基于块的基于块的运动估计运动估计块匹配算法块匹配算法块匹配算法通过对图像序列中相邻两帧图像间的子块匹配算法通过对图像序列中

38、相邻两帧图像间的子块匹配来进行运动估计。块匹配来进行运动估计。前提条件前提条件：在块匹配算法中，图像被分割为子块，在块匹配算法中，图像被分割为子块，把子块分成静止和运动两类，运动子块中的所有像把子块分成静止和运动两类，运动子块中的所有像素的运动矢量被认为相同，都只作相等的平移。素的运动矢量被认为相同，都只作相等的平移。基本思想基本思想：对于帧对于帧k(k(当前帧当前帧) )中像素中像素(n1,n2)(n1,n2)的位移的位移，通过考虑一个中心定位在，通过考虑一个中心定位在(n1,n2)(n1,n2)的块，搜索帧来的块，搜索帧来找出同样大小的最佳匹配块的位置来确定。找出同样大小的最佳匹配块的位置

39、来确定。1. 基本思想基本思想 初始搜索点的选择。初始搜索点的选择。 直接选择参考帧对应块直接选择参考帧对应块中心位置；中心位置； 选择预测的起点。选择预测的起点。 匹配准则。匹配准则。一般方法有均方误差函数和平均绝对一般方法有均方误差函数和平均绝对误差函数等准则。误差函数等准则。 搜索方法。搜索方法。有全搜索、三步搜索、交叉搜索、分有全搜索、三步搜索、交叉搜索、分层运动估计算法等。层运动估计算法等。 块的大小选择。块的大小选择。块的大小应满足下列要求：每一块的大小应满足下列要求：每一个块几乎都只具有单一运动或者没有运动。块不能个块几乎都只具有单一运动或者没有运动。块不能过小，以保证可以搜索到

40、正确的块。过小，以保证可以搜索到正确的块。目前块大小用目前块大小用较多为较多为16，有时也取，有时也取4 4，8 8。 2. 提高搜索效率的主要技术提高搜索效率的主要技术常用的匹配准则常用的匹配准则l 给定两个图像块给定两个图像块B Bi i和和B Bi-1i-1，均方误差均方误差绝对误差绝对误差 21n0 x1n0y1ii22ms)yy,xx(f)y,x(fn1e 1n0 x1n0y1ii2av)yy,xx(f)y,x(fn1e 求这两个误差函数对应最小值时求这两个误差函数对应最小值时(x, y)为最佳运为最佳运动估计动估计 全搜索算法（全搜索算法（FSFS）基本思想：基本思想：要估计一个像

41、素的位移要估计一个像素的位移( (运动运动) )时，在当时，在当前帧中取以该像素为中心的一个子块，然后在前一前帧中取以该像素为中心的一个子块，然后在前一帧图像中所有可能位置寻找一个与之最匹配帧图像中所有可能位置寻找一个与之最匹配( (相关最相关最大大) )的子块，则匹配子块中心与当前帧中子块中心的的子块，则匹配子块中心与当前帧中子块中心的位移即为估计的位移位移即为估计的位移( (运动运动) )矢量。矢量。匹配准则：匹配准则：最小平均绝对误差函数（最小平均绝对误差函数（MAD)设将当前帧中划分为设将当前帧中划分为N N像素子块，像素子块，A为为待处理的子待处理的子块。块。水平和垂直方向最大位移均

42、为水平和垂直方向最大位移均为dm 。3. 典型的块匹配算法典型的块匹配算法块匹配算法就是在其前一帧以块匹配算法就是在其前一帧以A为中心的搜索区为中心的搜索区SR:(N+2dm) (N+2dm) 内寻找一内寻找一个与个与A相关性最大的同样大小相关性最大的同样大小的子块的子块B，B与与A的坐标偏移量的坐标偏移量即为估计的子块即为估计的子块A的运动矢量的运动矢量设设B与与A的坐标偏移量为的坐标偏移量为(i，j)， 则：则：平均绝对平均绝对误差误差MAD 10,12| ),(),(|1NnmkkijjnimInmIN 第第k帧灰度值帧灰度值则在某一个位置偏移则在某一个位置偏移(i，j)下有最小误差下有

43、最小误差min ij，选定，选定一阈值一阈值T，则有：，则有： 当当min ij T，说明在一定误差范围内达到匹配，说明在一定误差范围内达到匹配，运动矢量为运动矢量为dx=i，dy=j当当min ij T，说明不能匹配。应该对该子块直接帧，说明不能匹配。应该对该子块直接帧内编码。内编码。在全搜索条件下，块匹配算法达到全局最优，但缺在全搜索条件下，块匹配算法达到全局最优，但缺点为运算量大，总共要计算点为运算量大，总共要计算(1+2dm) (1+2dm) 次匹次匹配运算，且搜索算法时间占到整个编码时间的配运算，且搜索算法时间占到整个编码时间的50%80%。 二维对数算法（二维对数算法（TDL） 开

44、创了快速算法的先例。开创了快速算法的先例。基本思想：基本思想：从原点开始，以从原点开始，以“十十”字形分布的五个点字形分布的五个点构成每次搜索的点群，通过快速搜索跟踪最匹配点。构成每次搜索的点群，通过快速搜索跟踪最匹配点。算法步骤：算法步骤： 从原点开始，选取一定的步长，在以从原点开始，选取一定的步长，在以“十十”字字形分布的五个点处进行块匹配计算并比较形分布的五个点处进行块匹配计算并比较 若最匹配点在边缘四个点处，则以该点作为中若最匹配点在边缘四个点处，则以该点作为中心点，保持步长不变，重新搜索心点，保持步长不变，重新搜索“十十”字形分布字形分布的五个点的五个点l 若最匹配点位于中心点，则保

45、持中心点位置不变，若最匹配点位于中心点，则保持中心点位置不变，将步长减半，构成将步长减半，构成“十十”字形点群，在五个点处字形点群，在五个点处计算计算l 若步长为若步长为1，在中心及周围，在中心及周围8个点处找出最匹配点，个点处找出最匹配点，该点所在位置即对应最佳运动矢量，算法结束；该点所在位置即对应最佳运动矢量，算法结束；否则，重复第否则，重复第2步步算法搜索过程图示：算法搜索过程图示：11111222223333344444-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7-7-6-5-4-3-2-1012345674444算法搜索过程图示：算法搜索过程图示：起初步长

46、起初步长=2 三步搜索法（三步搜索法（TSS）基本思想：基本思想：搜索范围为搜索范围为 7 7。即在上一帧以当前子块。即在上一帧以当前子块为原点，将当前子块在其上下左右距离为为原点，将当前子块在其上下左右距离为7 7范围内按范围内按一定规则移动，每移动到一个位置，取出同样大小一定规则移动，每移动到一个位置，取出同样大小的子块与当前子块进行匹配计算。的子块与当前子块进行匹配计算。匹配准则：匹配准则：最小均方误差函数最小均方误差函数(MSE)或最小平均绝或最小平均绝 对误差函数（对误差函数（MAD)具体方法具体方法： 第一步：第一步：在搜索范围内，以当前子块为中心，以在搜索范围内，以当前子块为中心

47、，以4为步幅。选择标记为为步幅。选择标记为“1” 的的9个点分别为中心位置个点分别为中心位置的子块与当前子块进行匹配，求出最佳匹配的子块的子块与当前子块进行匹配，求出最佳匹配的子块中心位置，然后把中心位置移到该点。如果在某点中心位置，然后把中心位置移到该点。如果在某点找到最小的找到最小的MSE或或MAD，则表示在该点一定范围内，则表示在该点一定范围内达到最佳匹配。达到最佳匹配。 第二步：第二步：以第一步求出最佳子块为中心，以以第一步求出最佳子块为中心，以2为为步幅。选择步幅。选择9个标记为个标记为“2”点分别为中心位置的子块点分别为中心位置的子块与当前子块进行匹配，求出最佳匹配的子块中心位与当

48、前子块进行匹配，求出最佳匹配的子块中心位置，然后把中心位置移到该点。置，然后把中心位置移到该点。 第三步：第三步：以第二步求出最佳子块为中心，以以第二步求出最佳子块为中心，以1为步幅。选择为步幅。选择9个标记为个标记为“3”点分别为中心位置点分别为中心位置的子块与当前子块进行匹配，求出最佳匹配的的子块与当前子块进行匹配，求出最佳匹配的子块中心位置。则它与当前子块中心位置偏移子块中心位置。则它与当前子块中心位置偏移量为估计的位移量。量为估计的位移量。结论：在结论：在dm=7dm=7时，三步法仅需要时，三步法仅需要3 3 9-7=259-7=25次匹配，次匹配，比全搜索算法匹配次数少很多。比全搜索

49、算法匹配次数少很多。三步搜索算法三步搜索算法111111111222222222333333333搜索搜索9+8+825次次-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7-7-6-5-4-3-2-101234567 交叉法（交叉法（CSACSA）是在是在TDLTDL、TSSTSS基础上为进一步减少计算量发展起来的基础上为进一步减少计算量发展起来的基本思想：基本思想：从原点开始，以从原点开始，以“”字形分布的五个点字形分布的五个点构成搜索点群，以构成搜索点群，以TDLTDL的搜索方式搜索最匹配点，的搜索方式搜索最匹配点，仅在最后一步采用仅在最后一步采用“十十”字形点群字

50、形点群算法描述：算法描述： 从原点开始，选取最大搜索长度的一半作为步从原点开始，选取最大搜索长度的一半作为步长，在以长，在以“”字形分布的五个点处进行块匹字形分布的五个点处进行块匹配计算并比较配计算并比较l 以上一步的最匹配点为中心，步长减半，继续进以上一步的最匹配点为中心，步长减半，继续进行行“”字形五点搜索，若步长大于字形五点搜索，若步长大于1，重复本步；，重复本步；若步长为若步长为1，则进行第三步，则进行第三步l 若上一步最匹配点处于中心点、左下角或右上角，若上一步最匹配点处于中心点、左下角或右上角，做做“十十”字形搜索；若上一步最匹配点处于左上字形搜索；若上一步最匹配点处于左上角或右下

51、角，则做角或右下角，则做“”字形搜索。搜索到的最字形搜索。搜索到的最匹配点为最佳运动矢量，算法结束匹配点为最佳运动矢量，算法结束交叉法搜索过程图示：交叉法搜索过程图示：111112222233333搜索搜索5+4+413次次-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7-7-6-5-4-3-2-101234567 四步搜索法（四步搜索法（FSSFSS）l基本思路基本思路l现实中序列图像的运动矢量大多都是中心分布的，现实中序列图像的运动矢量大多都是中心分布的，从而在从而在55大小的搜索窗口上构造了有大小的搜索窗口上构造了有9个检测个检测点的搜索模板点的搜索模板l步骤步骤

52、l 以搜索区域原点为中心选定以搜索区域原点为中心选定55的搜索窗，然后的搜索窗，然后在在9个检测点处进行匹配计算个检测点处进行匹配计算l若最匹配点位于中心点，跳到第若最匹配点位于中心点，跳到第3步，即缩小搜步，即缩小搜索窗口为索窗口为33最匹配点不在中心点，跳到第最匹配点不在中心点，跳到第2步步l 窗口保持窗口保持55，搜索模式改变，搜索模式改变l上一步最匹配点位于窗口上一步最匹配点位于窗口4个角上，个角上，则另外再搜索则另外再搜索5个检测点个检测点l上一步最匹配点位于窗口的上一步最匹配点位于窗口的4边中边中心点处，则需再搜索心点处，则需再搜索3个检测点个检测点l若这一次的最匹配点在窗口中心，

53、若这一次的最匹配点在窗口中心，则跳到第则跳到第3步，否则，重复本步步，否则，重复本步l 将窗口缩小到将窗口缩小到33，计算出最匹配，计算出最匹配点的位置即对应最佳运动矢量点的位置即对应最佳运动矢量四步搜索法过程图示四步搜索法过程图示1111111112222333333444444444-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7-7-6-5-4-3-2-101234567最匹配点分最匹配点分别为：别为：(0,-2) (2,-4) (2,-4) (3,-4),搜索共搜索共分分4步。步。 菱形搜索法（菱形搜索法（DSDS）本算法经过多次改进，已成为目前快速匹配算法本算

54、法经过多次改进，已成为目前快速匹配算法中性能最优异的算法之一；中性能最优异的算法之一；1999年年10月，月，DS算算法被法被MPEG-4国际标准采用并收入验证模型。国际标准采用并收入验证模型。基本思想：基本思想： 使用两种搜索模板，使用两种搜索模板，9个检测点的大模板个检测点的大模板LDSP和和5个检测点的个检测点的SDSP 搜索时，先用大模板计算，当最匹配块出现搜索时，先用大模板计算，当最匹配块出现在中心点处时，换大模板为小模板，再进行匹配在中心点处时，换大模板为小模板，再进行匹配计算，计算，5个点中的最匹配点即为最优点个点中的最匹配点即为最优点。大模板大模板LDSP小模板小模板SDSP算

55、法步骤：算法步骤： 用用LDSP在搜索区域中心及周围在搜索区域中心及周围8个点处进个点处进行匹配计算，若最匹配点位于中心，则进行行匹配计算，若最匹配点位于中心，则进行Step3；否则，到；否则，到Step2 以上一次找到的最匹配点为中心点，用新以上一次找到的最匹配点为中心点，用新的的LDSP来计算，若最匹配点位于中心点，来计算，若最匹配点位于中心点，则进行则进行Step3；否则，重复本步；否则，重复本步 以上一次找到的最匹配点为中心点，将以上一次找到的最匹配点为中心点，将LDSP换为换为SDSP，在，在5个点处计算，找到最个点处计算，找到最匹配点，该点所在位置即为最佳运动矢量。匹配点，该点所在

56、位置即为最佳运动矢量。菱形搜索算法过程图示菱形搜索算法过程图示1111111112222223333344444-7-6-5-4-3-2-101234567-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7最匹配点分最匹配点分别为：别为：(2,0) (2,-2) (2,-2) (2,-3),使用使用次次LDSP和和次次SDSP,搜索搜索共分共分5步。步。菱形搜索算法分析菱形搜索算法分析l选用了大小两种形状的搜索模板，先用选用了大小两种形状的搜索模板，先用LDSP搜索，步长大，搜索范围广，进行搜索，步长大，搜索范围广，进行粗定位，避免搜索窗口太小时，陷入局部粗定位，避免搜索

57、窗口太小时，陷入局部最优；粗定位后，再用最优；粗定位后，再用SDSP准确定位，准确定位，保证匹配精度保证匹配精度l从前图中可看出，搜索时各步之间相关性从前图中可看出，搜索时各步之间相关性强，模板移动只需要在几个新的检测点处强，模板移动只需要在几个新的检测点处进行匹配计算，提高了搜索速度进行匹配计算，提高了搜索速度复习：复习：l 视频信号编码技术视频信号编码技术 运动补偿帧间预测编码技术运动补偿帧间预测编码技术 物体的划分物体的划分：划分静止区域和运动区域。这：划分静止区域和运动区域。这里假设运动物体仅作平移。里假设运动物体仅作平移。 运动估计运动估计：对每一个运动物体进行位移估计。：对每一个运

58、动物体进行位移估计。 运动补偿运动补偿：由位移估值建立同一运动物体在不：由位移估值建立同一运动物体在不同帧空间位置对应关系，建立预测关系。同帧空间位置对应关系，建立预测关系。 补偿后的预测信息编码补偿后的预测信息编码：对运动物体的补偿后：对运动物体的补偿后的位移帧差信号，以及运动矢量等进行编码传的位移帧差信号，以及运动矢量等进行编码传输。输。抽帧或跳帧抽帧或跳帧复习：复习：l如何实现运动矢量估计？如何实现运动矢量估计？块匹配算法块匹配算法 初始搜索点的选择。初始搜索点的选择。 直接选择参考帧对应块直接选择参考帧对应块中心位置；中心位置； 选择预测的起点。选择预测的起点。 匹配准则。匹配准则。一

59、般方法有均方误差函数和平均绝对一般方法有均方误差函数和平均绝对误差函数等准则。误差函数等准则。 搜索方法。搜索方法。有全搜索、三步搜索、交叉搜索等。有全搜索、三步搜索、交叉搜索等。 块的大小选择。块的大小选择。块的大小应满足下列要求：每一块的大小应满足下列要求：每一个块几乎都只具有单一运动或者没有运动。块不个块几乎都只具有单一运动或者没有运动。块不能过小，以保证可以搜索到正确的块。能过小，以保证可以搜索到正确的块。目前块大目前块大小用较多为小用较多为16，有时也取，有时也取4 4，8 8。 复习：复习：l块匹配方法块匹配方法 全搜索算法全搜索算法 二维对数搜索算法二维对数搜索算法 三步搜索算法

60、三步搜索算法 交叉法交叉法 四步搜索算法四步搜索算法 菱形（钻石形）搜索菱形（钻石形）搜索算法算法以以“十十”字形分布的字形分布的五个点构成每次搜索的五个点构成每次搜索的点群，若步长为点群，若步长为1，周围，周围8邻域匹配。邻域匹配。搜索范围为搜索范围为 7“4-2-1”以以“”字形的五个点构成字形的五个点构成搜索点群，若步长为搜索点群，若步长为1，上，上一步最匹配点处于中心点、一步最匹配点处于中心点、左下角或右上角，左下角或右上角， “十十”字形搜索；若处于左上角字形搜索；若处于左上角或右下角，则或右下角，则 “”字形字形搜索。搜索。“55”的搜索窗口，若的搜索窗口，若步长为步长为1，则，则