US 2011/0255604 A1Published application

Method of block matching-based motion estimation in video coding

AssigneeChang Gung University

InventorsJiann-Der Lee, Hao-Hang Hsu

Life of this patent

Estimating the term…

Loading patent…

Abstract

Motion estimation is efficient to reduce redundant information among successive frames in video compression applications. The blocks in the current frame can be replaced with the neighboring blocks in the spatial directions in the previous frame with small errors. Many types of motion estimation methods such as Block Matching Algorithm are widely used to take a balance between a good image quality and the computation complexity. A Block Matching Algorithm named as New Cellular Search (NCS) Algorithm utilizes two particular search patterns: HCSP and VCSP, in the horizontal and vertical directions to search the best motion vector. Three performance measurements including peak signal to noise ration (PSNR), Average Search Point (ASP), and Mean Square Error (MSE) are used to compare this new search algorithm with some major motion estimations like FS, TSS, CS, and NCDS. The NCS is very efficient in computation reduction while keeping the almost same picture quality.

Claims3

Dependent claims

A method of block-matching-based motion estimation in video coding by finding an optimal motion vector for the matching block using a data processing device, comprising the following steps, in which:

step 1, an origin in a search area is first set to a central search point in a Horizontal Cellular Search Pattern (HCSP) and coordinates are set to (0, 0);
next, error values between six candidate points and the central point around a block and HCSP are calculated;
if a minimum error value occurs at the central point, jump to step 3, and if it occurs at the rest of six candidate points outside, then go on to execute step 2;
step 2, if the minimum error value occurs horizontally, a position of the minimum error value as Mean Absolute Distance (MAD) searched at step 1 is set to a new central point in HCSP;
on the contrary, if the minimum error value occurs vertically, it is set to a new central point in Vertical Cellular Search Pattern (VCSP) and re-calculation is made for a new error value as MAD;
if the minimum error value as MAD lies in the central point of HCSP or VCSP, directly execute step 3, if not repeat step 2;
and
step 3, MAD values at points 3 and 6 are compared;
if the MAD value at point 3 is lower, a point 8 between points 1 and 3 is added as a candidate point and MAD values at points 1 and 8 are calculated and two lower MAD values are found, and if the MAD value at point 6 is lower, a point 9 between points 1 and 6 is added as a candidate point and MAD values at points 1 and 9 are calculated and two minimum MAD values are found;
finding the coordinates of minimum error value as MAD at this step finds an exact optimal motion vector for the matching block.

7 more elements

Dependencies are inferred from the claim text.