InnovationQ will be updated on Sunday, May 20, from 10am - noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Scalable Zonal Motion Search For Video Encoder

IP.com Disclosure Number: IPCOM000184965D
Original Publication Date: 2009-Jul-06
Included in the Prior Art Database: 2009-Jul-06
Document File: 9 page(s) / 104K

Publishing Venue


Related People

Cheng Chang: INVENTOR [+4]


A zonal motion estimation framework is provided in which a scalable regional search mechanism provides regional motion seeds for motion estimation over a picture. Either full-resolution or down-sampled pictures can be analyzed by first segmenting the picture into a set of regions. Global motion search is performed within each region. The resulting motion vectors are used to guide subsequent motion estimation over the whole picture. Region segmentation is flexible and scalable to make efficient use of available computational resources.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 31% of the total text.


A video encoding system consists of several major components: motion estimation, motion compensation, transform, quantization, and entropy coding.  Motion estimation is often the most computationally expensive of these components.  Capturing fast motion between frames is typically difficult with conventional motion estimation methods.  The invention is a flexible and computationally scalable method of performing motion estimation that is capable of capturing fast motion.

One of the goals of motion estimation is to determine the best match in one or more reference pictures for a given block in the picture to be coded.  The result (i.e., output) of motion estimation is one or more motion vectors that indicate the difference in coordinates between the matches and the block to be coded.  The quality of the match can be indicated by a  quantity, which is denoted as “C” herein, that reflects the difference between the motion compensated block and the block to be coded, the cost of coding that difference, and the cost of coding the motion vectors.  Thus, a goal of motion estimation is to identify a set of motion vectors that minimize C.  The inventive method employs a zonal motion estimation framework in which motion searching on a full resolution picture is restricted to small regions (zones) surrounding motion seeds.

Motion seeds, which are points in the reference picture that are likely to be close to an optimal match, may be generated using a number of conventional approaches.  Conventional methods typically use neighboring motion vectors associated with neighboring macroblocks or motion vectors associated with co-located macroblocks in previously coded pictures as motion seeds for the current block.  These methods produce reasonable results for content with low to medium amounts of motion, but often are ineffective for content having a larger amount of motion.  This is especially true where there is a scene change, where the motion changes direction rapidly, or where the scene contains random motion that is not very predictable from spatially or temporally neighboring macroblocks.  The present invention utilizes scalable zonal motion searching for identifying motion vectors, thereby improving the effectiveness of the motion estimation for scene changes in which motion changes direction rapidly or unpredictably.

With reference to FIGURE 1, the method described herein includes, region segmentation 110, downsampling 120, region motion analysis 130, and zonal search 140.  Region segmentation 110 includes defining one or more regions for a given video frame.  The local motion within each region is used to guide a subsequent zonal search for macroblocks or blocks within that region to generate motion seeds.  A block may be a 16x16 macroblock or an MxN...