Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

System and method for fast variable-size motion estimation

System and method for fast variable-size motion estimation description/claims

This application is a divisional application of application Ser. No. 10/986,649, filed Nov. 12, 2004, incorporated herein by reference in its entirety, and claims the benefit of its earlier filing date under 35 U.S.C. 120(e).

The present invention relates generally to a method and system of variable block-size motion estimation and more particularly, to a method and system of fast variable block-size motion estimation based on merge and split procedures for H.264/MPEG-4 AVC video encoding.

In current video coding standards, Motion Estimation (ME) is a core functional block to remove temporal redundancy in video sequences to achieve high compression. In the emerging H.264/MPEG-4 AVC video coding standard, for Inter coded Macroblocks (MBs), tree-structured block-sizes can be employed in the motion estimation. Each 16*16 MB can be coded in 16*16, 16*8, 8*16, and 8*8 block-modes. If the 8*8 block-mode is chosen, each 8*8 sub-macroblock can be independently partitioned into 8*8, 8*4, 4*8, and 4*4 blocks. So, altogether there can be seven different block-sizes: 16*16, 16*8, 8*16, 8*8, 8*4, 4*8, and 4*4. For these block-sizes, each 16*16 MB contains 1, 2, 2, 4, 8, 8, and 16 blocks respectively.

In the H.264/MPEG-4 AVC reference software, a Fast Full Search (FFS) algorithm is used for the ME. The SADs (Sum of Absolute Differences) of 4*4 blocks are first calculated and the SADs of the other six block-modes are calculated by summing up the SADs of the corresponding 4*4 blocks. Although the SADs in the calculation of the 4*4 block-mode are re-used, for all seven block-sizes, the SAD calculation load will be larger than that using a full-search ME for a 16*16 MB. For example, if a search-window size is 31*31 pixels and the Unrestricted Motion Vector (UMV) mode is enabled, the number of search points using the full-search ME is 31*31=961. Accordingly, the required SAD computation is larger than that for a 16*16 MB with 961 search points, which requires a lot of computations.

Recently some fast variable block-size ME algorithms have been proposed. For example, a fast search algorithm is applied to the seven block-sizes independently, as disclosed by Ma et al. in an article entitled “An Improved Adaptive Rood Pattern Search For Fast Block-matching Motion Estimation in JVT/H.26L”. A merge procedure is also proposed, as disclosed by Tu et al. in “Fast Variable-size Block Motion Estimation Using Merging Procedure With an Adaptive Threshold”, which determines the MVs of larger block-sizes from the MVs of smaller block-sizes, with the threshold for the merge criteria related to the quantization parameter. Kucukgoz et al. in their article entitled “Early-stop and Motion Vector Re-using for MPEG-2 to H.264 Transcoding” apply a bottom-up merge scheme and an early-stop strategy for the variable block-size ME in MPEG-2 to H.264 transcoding. Furthermore, in “Fast Integer Pixel Motion Estimation” disclosed by Li et al., a merge and split process for the ME is proposed. The disclosure, however, fails to describe the detailed process.

Accordingly, one object of the present invention is to provide a MV prediction and MV search strategy for fast variable block-size MEs. Using the strategy, fast variable block-size ME algorithms based on merge and split procedures are proposed and described in details. Experimental results show that using these merge/split schemes, the search-points can be reduced to about 4% of that using the fast full-search ME for a 16*16 MB, with negligible quality degradation.

One embodiment of the present invention is to provide method for predicting motion vectors (MVs) of variable block sizes of a video image frame. The method includes choosing a block size as an initial processed block, wherein the initial processed block has a block size between a smallest block size a largest block size of the variable block sizes, partitioning the initial processed block into a plurality of sub-blocks and obtaining a plurality of prediction MVs from the plurality of sub-blocks. The plurality of prediction MVs are then used in subsequent steps. The initial processed block is merged into larger-size blocks and the plurality of prediction MVs are used in the merging process to predict MVs of the larger-size blocks. Further, the initial processed block is split into smaller-size blocks; and similarly, the plurality of MVs are used in the splitting process to predict MVs of the smaller-size blocks.

According to the present invention, the initial block size is 8*8. In this case, the initial block is divided into four 4*4 sub-blocks and four prediction MVs: MV.sub.A, MV.sub.B, MV.sub.C, and MV.sub.D are calculated. The initial block is merged into 8*16, 16*8, and 16*16, and is split into 8*4, 4*8, and 4*4 blocks.

In the first preferred embodiment, if any two prediction MVs matches with each other, the matched MV is used as a prediction MV of next larger-size block. If none of the prediction MVs matches with each other, the method searches for a new MV for the larger-size block. Similarly, if the MVs of the smaller-size blocks, such as 8*4, and 4*8 blocks, are the same, the MV is used as a prediction block of the 4*4 block. Otherwise, the prediction MVs of the four sub-blocks are average and the averaged MV is used as a search center.

A second embodiment of the present invention is to provide a method for judging motion vector (MV) consistency of a block in a video image frame. The method includes dividing the block into a plurality of sub-blocks, calculating prediction MVs of the plurality of sub-blocks, comparing the prediction MVs of the plurality of sub-blocks, and if horizontal components and vertical components of any adjacent two of the plurality of sub-blocks MVA and MVB match with each other, i.e., |MVA-x−MVB-x|==0 and |MVA-y−MVB-y|=0, then prediction MVa is used as a reference MV for a larger-size block.

In the above embodiment, if the horizontal components and vertical components of any adjacent two of the plurality of sub-blocks MVA and MVB do not match, then the method searches MVs for a larger-size block, in which the criterion for unmatched MV is:

|MVA-x−MVB-x|>=3 or |MVA-y−MVB-y|>=3.

A third embodiment of the present invention is to provide a system module for fast motion estimation of variable block sizes of a video image frame. The system includes a first motion estimation sub-module for processing an initial n×m block to obtain a plurality of prediction MVs and a merging sub-module for merging the n×m block into larger-size blocks and for receiving the plurality of prediction MVs from the first motion estimation sub-module. The merging sub-module uses the plurality of prediction MVs to calculate prediction MVs for the larger-size blocks. The system also includes a splitting sub-module for splitting the n×m block into smaller-size blocks and for receiving the plurality of prediction MVs from the first motion estimation sub-module. The splitting sub-module uses the plurality of prediction MVs to calculate prediction MVs for the smaller-size blocks.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws