Browse Prior Art Database

MULTI-LEVEL GRADIENT MOTION ESTIMATION METHOD

IP.com Disclosure Number: IPCOM000007187D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2002-Mar-04
Document File: 2 page(s) / 105K

Publishing Venue

Motorola

Related People

Ken Jakobsen: AUTHOR

Abstract

In order to use the time correlation in image sequences for compression purposes, motion is esti- mated and compensated. This is done block-wise, as shown in Figure 1. The idea of the motion com- pensation is then to use an estimated motion vector to copy a displaced block to each block.

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

Page 1 of 2

0 M MOLA

Technical Developments Volume 22 June 1994

MULTI-LEVEL GRADIENT MOTION ESTIMATION Ml3HOD

by Ken Jakobsen

  In order to use the time correlation in image sequences for compression purposes, motion is esti- mated and compensated. This is done block-wise, as shown in Figure 1. The idea of the motion com- pensation is then to use an estimated motion vector to copy a displaced block to each block.

  To do this, the motion within that block must be estimated. This can be done by searching for the best block match in the neighborhood of the block. This is very computational demanding. The num- ber of operations to perform is:

O(ky P4S2) = 0(4M,M,S')

where B is the blocck size and the search range is *S pixels and the image is Ml x M2 pixels.

  Since the task is to search for,a minimum ofthe square error, a straight forward suggestion for making this process faster is to use an iterative algorithm, such as a gradient or steepest decent algorithm (Fig- ure 3). The gradient motion estimation algorithm reduces the computational demand of motion esti- mation by an order of magnitude. However, the algo- rithm has a drawback: unlike the full search the computational load ofthe gradient algorithm depends on the source material. This is a problem in real time systems where it is the maximum computational load that is the limiting factor. This algorithm also fails ifthe motion is rapid: the search algorithm then gets stuck in a local minimum far from the opti- mum vector.

  In order to avoid this problem, and even speed up the motion estimation further in some cases, the motion estimation can be done in a multi resolu- tion fashion. Instead of searching the original full resolution image for the best block match, a deci- mated version of the image is searched instead. Dec- imating an image by 2 will decimate the search area and block size as well, and thus give a search area of quarter size and a block size of quarter size. This

will give a total computational saving of 16 times for each time the image is decimated by 2. The motion vector found this way is then the best match...