应用于视频压缩且使用像素匹配欠采样的运动估计方法

摘要

一种应用于视频压缩且使用像素匹配欠采样(sub－sampling)的运动估计方法。运动估计方法包含有：获取第一帧的当前宏块对，以及对第二帧的候选宏块对与当前宏块对执行块匹配操作：根据欠采样格式对当前宏块对以及候选宏块对进行欠采样以获取欠采样结果，以及根据欠采样结果对当前宏块对以及候选宏块对之间进行误差量度。其中上述欠采样格式是由多个重复单元所构成，以及每一个重复单元是由第一格式单元以及第二格式单元所构成。本发明对图场运动估计而言具有均匀的采样分布，故使得匹配结果达到最佳化，也附带增强了视频压缩的图像质量。

说明书

技术领域

本发明与运动估计(motion estimation)有关，尤其是关于在视频压 缩(video compression)中应用像素匹配欠采样(sub-sampling)技术的运 动估计方法。

背景技术

运动估计是一种被广泛使用于视频压缩中的技术，用以降低视频 帧间的时间冗余信息(temporal redundancy)。利用移动向量(motion vector)来取代视频数据中重复出现的类似视频内容，编码视频数据时 所需的存储器需求便可随之降低，也就是说，在视频压缩时采用运动 估计技术可使得在大多数情况下不严重降低视频质量的同时，减少视 频数据的大小。

请参阅图1，图1所示为现有技术的帧运动估计(frame Motion Estimation，frame ME)的示意图。如同先前所述，运动估计的目的即为 用来降低视频帧(例如当前帧120以及参考帧110)之间的时间冗余信息 (temporal redundancy)。参考帧110中包含有参考宏块115，而当前帧 120包含有当前宏块125。如图1所示，当前帧120被划分成多个宏块 (macroblock，MB)，用以与参考帧110中的多个候选宏块(candidate macroblock)进行匹配。如同本领域内技术人员所知，在视频压缩技术 中，宏块的大小可依据使用者对于计算效率以及精准度的需求而折衷 选择；然而，在大多数的算法中，宏块的尺寸是16像素×16像素。

在宏块完成划分之后，利用一个预定的误差量度机制，当前帧120 中的每个宏块即与参考帧110中每个候选宏块做匹配以分别找出与当 前帧120中每个宏块最匹配(matching)的候选宏块。在视频压缩的算法 中，代表两帧中彼此匹配的宏块的距离的移动向量130便被标示出来， 并在压缩算法中取代当前帧120中的当前宏块125。

举例来说，如图1所示，当前帧120中有一个含棒球的当前宏块 125，其可合理地匹配至参考帧110中的一个含棒球的参考宏块115， 另外，图1的移动向量130则代表了与当前宏块125相互匹配的宏块 115由参考帧110移动至当前帧120的位移量。

相较于储存实际的宏块数据，储存位移向量需要较少的存储器， 因此，当运动估计被应用于压缩算法中时，存储器的使用量便可大幅 度地降低。在视频重建(reconstruction)的过程中，在参考帧内由移动向 量所标示出的宏块会用来预测当前帧的信息；而这种视频重建的技术 就是现有技术的移动补偿预测(motion compensated prediction)或移动 补偿(motion compensation)。

在采用移动补偿技术时，参考帧中由移动向量所标示出且对应到 当前帧中的宏块的相匹配的宏块会被复制到重建后的帧当中。请继续 参阅图1，当执行移动补偿时，当前帧中的当前宏块125之前并未被 储存至存储器中，而是根据移动向量130来以参考帧110中的参考宏 块115取代当前帧120中的当前宏块125。

在视频压缩的领域中，采用移动补偿所产生的视频质量可随着用 来计算移动向量的算法而改变，也就是说，一个不精准的移动向量往 往会导致一个不近似的预测结果，并因此造成不佳的视频质量。因此， 误差量度(error measure)即被应用在运动估计的块匹配中，以确定出宏 块彼此间的近似程度，而在进行块匹配时，绝对误差总和(Sum of Absolute Differences，SAD)与均方误差总和(Sum of Squared Error， SSE)是其中广泛使用的误差量度值。

前述的帧运动估计技术通常被使用在循序扫描的视频源 (progressive video source)，其中视频图像的完整帧(full frame)会连续 显示，除此之外，运动估计运算也可使用到交错扫描的视频源中。请 参阅图2，图2所示为现有技术交错帧200的组成的示意图。如图2 所示，在交错扫描的视频中，交错帧200包含有奇图场(odd field)210 以及偶图场(even field)220，其中奇图场210由奇数编号的水平扫描线 构成，而偶图场220由偶数编号的水平扫描线构成。因此，当针对交 错扫描的视频执行运动估计时，相较于比较完整的宏块，当前帧中宏 块内的图场会与参考帧中宏块的图场相比较，而上述针对交错扫描视 频的运动估计也被称作图场运动估计(field Motion Estimation，field ME)。

帧运动估计以及图场运动估计均可应用于交错扫描的视频而产生 不同的运算结果，举例来说，对于内容基本静止的视频序列(即仅具有 程度有限的移动)，此时帧运动估计运算相较于图场运动估计会得到较 佳的匹配结果；然而，对于内容大致上动态的视频序列(即具有较大程 度的移动)，选用图场运动估计会得到较佳的匹配结果。由于图场运动 估计以及交错扫描的视频的相关技术为本领域内技术人员所知，故详 细说明在此省略而不另赘述。

一般而言，在确定彼此匹配的宏块的过程中，可能会针对匹配的 像素(matching pixel)进行采样来降低运算的复杂度，因此，当前宏块 以及候选宏块(即位于参考帧/图场中的宏块)中的某些特定像素会被选 取以计算这些像素的特征值(characterizing value)，而特征值一般而言 会是绝对误差总和(SAD)或均方误差总和(SSE)。在求出不同候选宏块 的特征值之后，会比较这些候选宏块的特征值。

请参阅图3，图3所示为根据大小为32*16(像素)的宏块对(MB pair) 进行采样的示意图，其中，运动估计包含有匹配两个大小为32*16像 素的宏块对，以及采用一个四皇后棋格欠采样格式(four-queen sub-sampling pattern)310。如图3所示，在此范例中，当前宏块对以及 候选宏块对的大小都为16*32像素，而一个四皇后棋格(four-queen)格 式340是由每4*4大小的块中选出四个像素，以重复地构成大小为 16*32像素的四皇后棋格欠采样格式310，而四皇后棋格欠采样格式 310会同时应用在当前宏块对以及参考宏块对，也就是说，仅有被选 取出的像素会使用在误差量度的计算之中。

然而，尽管前述应用在帧运动估计中的四皇后棋格欠采样格式 310看起来似乎是均匀分布的，然而当应用于图场运动估计时，欠采 样格式320、330反而是不均匀的，由于对图场运动估计而言缺乏均匀 的采样分布，故使得匹配结果无法达到最佳化，也附带降低了视频压 缩的图像质量。

发明内容

为了解决运动估计采样分布不均匀的技术问题，本发明提供一种 应用像素匹配欠采样(matching-pixel sub-sampling)的运动估计方法， 来解决前述的问题。欠采样格式可同时应用在循序扫描视频源以及交 错扫描视频源之中，并使得帧运动估计以及图场运动估计都可得到具 有较均匀的采样分布结果。

根据本发明的实施方式，其揭示一种应用在视频压缩且使用像素 匹配欠采样的运动估计方法。此运动估计方法包含有：获取第一帧的 当前宏块对，以及对第二帧的候选宏块对与上述当前宏块对执行块匹 配操作：当前宏块对以及候选宏块对根据欠采样格式进行欠采样以获 取欠采样结果，以及根据欠采样结果对当前宏块对以及候选宏块对之 间进行误差量度。欠采样格式是由多个重复单元所构成，以及每一个 重复单元是由第一格式单元以及第二格式单元所构成。

本发明利用构造欠采样格式，使得视频压缩的欠采样技术更加有 效率以及具有优越的运动估计能力。

附图说明

图1为现有技术的帧运动估计的示意图。

图2为现有技术交错帧的组成的示意图。

图3为使用四皇后棋格格式在运动估计中的帧欠采样格式以及交 错图场采样格式的示意图。

图4为本发明建构欠采样格式的实施方式的示意图。

图5为本发明欠采样格式的实施方式的示意图。

图6为本发明运动估计方法的实施方式的流程图。

具体实施方式

在说明书及权利要求书当中使用了某些词汇来称呼特定的元件。 本领域的技术人员应可理解，硬件制造商可能会用不同的名词来称呼 同一个元件。本说明书及权利要求书并不以名称的差异来作为区分元 件的方式，而是以元件在功能上的差异来作为区分的准则。在通篇说 明书及权利要求书当中所提及的“包含”是开放式的用语，故应解释 成“包含但不限定于”。此外，“耦接”一词在此是包含任何直接及 间接的电气连接手段。因此，若文中描述第一装置耦接于第二装置， 则代表第一装置可直接电气连接于第二装置，或通过其它装置或连接 手段间接地电气连接到第二装置。

如同现有技术的段落中所述，在依据视频的相关移动(relative translational motion)选出所需的信息后，帧运动估计以及图场运动估 计两者都可使用在交错扫描的视频之中，然而，进行交错扫描视频的 视频处理时，判断应该采用帧运动估计或图场运动估计来对视频数据 进行编码在实际运作上具有一定的难度。在这种情况下，在处理流程 中会进行图场运动估计以及帧运动估计两种运动估计方法，而经由绝 对误差总和的计算或均方误差总和的计算等误差量度方法来判定出当 前帧以及参考帧中彼此宏块的不近似度之后，能产生较佳运算结果的 运动估计方法(图场运动估计或帧运动估计)便会被采用。因此，为了 选出较佳的运动估计方法，在执行误差量度运算时会需要一个同时可 使用于帧运动估计以及图场运动估计的欠采样格式，且此欠采样格式 对于帧运动估计以及图场运动估计均可产生一个均匀的欠采样分布结 果，以提升速率-失真性能(rate-distortion performance，R-D performance)。欠采样格式所使用的这些采样点会在帧运动估计以及图 场运动估计中重复使用，以降低其运算复杂度。而本发明所揭露的欠 采样格式不仅可同时提供一个良好的编码结果给帧运动估计以及图场 运动估计，且本发明的欠采样格式可经由一个简单的算法而产生。

本发明的欠采样格式是包含有多个重复单元(repeating unit)，其中 每个重复单元至少具有两个彼此相异的格式单元(pattern unit)，而这两 个格式单元可以是完全不相同的格式，或是由一个格式单元经由反转 (inverted)、镜射(reflected)、向左/向右平移(left/right shift)、向上/向 下平移(up/down shifted)、或旋转来产生另一个格式单元，也就是说， 一个重复单元内的第二个格式单元可由第一个格式单元加以反转、镜 射、左移、右移、上移、下移、旋转或上述方法合并使用而产生。

在本发明的一些实施方式中，一个格式单元的大小为N*N个像 素，而一个重复单元的大小则为N*2N个像素。通过采用由不同格式 单元所构成的一个欠采样格式，应用于交错扫描视频处理的帧运动估 计以及图场运动估计两者都可以得到均匀的采样分布，其细节将在后 续的揭示中详细说明。

请参阅图4，图4所示为本发明建构欠采样格式的实施方式的示 意图。在本实施方式中，欠采样格式是用来对当前宏块对及候选宏块 对进行像素采样，而每个欠采样格式是由多个重复单元所构成。举例 来说，大小为16*32像素的宏块对可经由图3所示的四皇后棋格欠采 样格式310来进行采样，其中四皇后棋格欠采样格式310的重复单元 为大小为4*4像素的格式单元。在本发明的一些实施方式中，利用结 合两个或两个以上的4*4像素的格式单元来构成欠采样格式中的每个 重复单元。如图4所示的范例中，大小为4*4像素的格式单元400被 选定为第一格式单元，用来与格式单元410、420、430中所选出的第 二格式单元进行结合，来构成大小为4*8像素的重复单元。在本实施 方式中，重复单元中的第二格式单元必须相异于第一格式单元，但是 第二格式单元可允许从第一格式单元衍生而出。举例来说，如图所示， 格式单元410经由对第一格式单元400进行逆时钟旋转90度而产生出 的衍生格式；相似地，格式单元420经由第一格式单元400相对于纵 轴的镜射而产生，以及格式单元430是经由第一格式单元400相对于 横轴的镜射而衍生出来的。一旦第二格式单元被选定之后，两个选定 的格式单元(第一格式单元以及第二格式单元)便可构成大小为4*8像 素的重复单元以供欠采样格式来使用。在本实施方式中，一个欠采样 格式经由16个大小为4*8像素的重复单元所构成，而欠采样格式用来 在运动估计运算中，对第一个帧中的当前宏块对以及第二帧中的候选 宏块对进行适当的采样。

请参阅图5，图5所示为本发明欠采样格式的实施方式的示意图。 如图5所示，本实施方式将两个格式单元结合以构成欠采样格式所需 的重复单元。在本实施方式中，第一格式单元510(其大小为4*4像 素)位于欠采样格式500中的左上方角落；而第二格式单元520(其 大小为4*4像素)则位于第一格式单元510的正下方，且第二格式单 元520为第一格式单元510沿横轴(或可沿纵轴)镜射而成的衍生格式。 欠采样格式500是由不断重复第一格式单元510以及第二格式单元 520而成。在本实施方式中，经由使用整个欠采样格式500，可在执行 帧运动估计时由宏块对取得具有均匀分布特性的采样点。除此之外， 在处理图场运动估计时，欠采样格式530可供奇图场使用，而欠采样 格式540则可供偶图场使用，且两个欠采样格式530以及540均可由 宏块对中提取出具有均匀分布特性的采样点，因此，相较于现有技术 的图场运动估计(如图3所示)，本发明欠采样格式(例如欠采样格式530 与540)中彼此间隔的垂直线之间不再出现未被采样的区域了。因此本 发明的欠采样格式500可同时提供图场运动估计以及帧运动估计一个 较均匀的采样分布。

在这里请注意到，在前述的实施方式中尽管使用了四皇后棋格欠 采样格式中的一个格式单元及由上述格式单元变化而成的衍生格式， 然而在本发明其它实施方式中，也可采用一些不同欠采样格式中的格 式单元，举例来说，这些不同欠采样格式可以是全域采样格式(full sampling pattern)、四分之一格式(quarter pattern)、或八皇后棋格格式 (8-queen pattern)。这些用以采样当前宏块对以及候选宏块对的欠采样 格式，其至少包含有两个相异的格式单元。除此之外，在不同的实施 方式中，这些格式单元也可具有不同的变化组合以符合特定压缩需求 或特定采样需求。另外，在本发明其它实施方式中，欠采样格式的重 复单元可将不同的格式单元并排地结合在一起，举例来说，可利用将 第二格式单元置于第一格式单元的右侧来构成大小为8*4像素的重复 单元。

另外，本发明所揭示的欠采样格式设计可同时适用于交错扫描的 视频源和循序扫描的视频源，由于循序扫描视频的块匹配单元为宏块 而非宏块对，故应用于循序扫描视频源的欠采样格式的大小可为 16*16像素。

如前述的揭示，欠采样格式是用来由当前宏块对以及候选宏块对 中选取出某些像素以进行误差量度的计算，而对于参考帧的搜索范围 内的候选宏块对来说，这些候选宏块对的误差量度则被彼此比较，以 根据这些误差量度之中的最小误差量度来确定移动向量，且上述移动 向量标示出相匹配宏块对的位置。所选用的误差量度值可根据本发明 的不同实施方式而变，且所选用的误差量度值可包含有绝对误差总和 (Sum of Absolute Differences，SAD)。

请参阅图6，图6所示为本发明应用于视频压缩的运动估计方法 的实施方式的流程图。请注意到，倘若实质上可达到相同的结果，并 不一定需要遵照图6所示的流程中的步骤顺序来依序进行。本流程包 含有以下步骤：

步骤610：将第一帧划分成多个宏块对，其中包含当前宏块对。

步骤620：在第二帧的候选宏块上进行对上述当前宏块对的块匹配 操作。

步骤630：根据欠采样格式对上述当前宏块对以及上述候选宏块对 进行采样以获取欠采样结果，其中上述欠采样格式是由多个重复单元 所构成，而其中每个重复单元包含有第一格式单元以及第二格式单元。

步骤640：根据上述欠采样结果对上述当前宏块对以及上述候选宏 块对进行误差量度。

在图6所述的运动估计方法的其它实施方式中，也可使用第三格 式单元来构成上述欠采样格式，而上述这些设计变化提供了在不同采 样需求下所需的特定采样分布。

利用提供由不同格式单元所构成的欠采样格式，在交错扫描的视 频中，帧运动估计以及图场运动估计两种运动估计方法都可以得到均 匀的采样分布。在本发明的其它实施方式中，可从第一格式单元经由 旋转、镜射、水平/垂直平移等操作来衍生出第二格式单元，而使用第 一、第二格式单元可轻易地产生出本发明的欠采样格式，而这第一格 式单元可以是一个被广泛使用在像素匹配欠采样技术中的传统格式 (例如四皇后棋格格式)的格式单元。总结来说，本发明提供的视频压 缩的欠采样技术更加有效率以及具有优越的运动估计能力。

本发明虽用较佳实施方式说明如上，然而其并非用来限定本发明 的范围，任何本领域中技术人员，在不脱离本发明的精神和范围内， 做的任何更动与改变，都在本发明的保护范围内，具体以权利要求界 定的范围为准。