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

Computationally Efficient Motion Estimation Algorithm for Video Coding

IP.com Disclosure Number: IPCOM000010111D
Publication Date: 2002-Oct-23
Document File: 3 page(s) / 45K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a motion estimation methodology that reduces search points by changing search window size depending on the motion vectors of macro blocks. Benefits include a reduction in computational requirements and a better prediction of the motion vector.

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 50% of the total text.

Computationally Efficient Motion Estimation Algorithm for Video Coding

Disclosed is a motion estimation methodology that reduces search points by changing search window size depending on the motion vectors of macro blocks. Benefits include a reduction in computational requirements and a better prediction of the motion vector.

Background

Motion estimation is an essential part of video encoders, helping remove temporal redundancies in images. However, most motion estimation algorithms neglect the strong correlations within the motion field. The search windows stay the same size through the image sequences, and the estimation requires heavy computation. To reduce this complexity, several algorithms are used. One of the popular methods is a logarithmic search. Instead of searching all points within the search window, it looks for nine initial points which are apart by a quarter of the search window size. Upon finding a point, it continues the search by reducing the distance between search points by half. It continues until the distance between two search points is one pixel. This method reduces complexity, but neglects the high correlation of motion field. Also, the number of search points increase as the search range increases.

General Description

The disclosed method reduces the number of search points by changing the search window size, depending on the motion vectors of macro blocks. A gradient of neighborhood motion vectors is used to analyze the spatial correlation of the motion field, then motion estimation is started using the variable-size search window centered by the motion vectors of the previous macro block. This method reduces the complexity for motion estimation, but also decreases the entropy of motion vectors for motion vector encoding.

Description of algorithm

When using INTER mode coding in MPEG-2, the motion vector must be coded and transmitted. To reduce the bit requirements for coding, the motion vector components (horizontal and vertical) are coded differentially by using a previous motion vector already transmitted (see Figure 1).

Assuming the motion vectors of the current and previous macro blocks are,

� , ,

the motion vector coding is performed separately on the horizontal and vertical components as follows:

The disclosed method recognizes that motion vector fields have strong correlation among neighborhood macro blocks. The reduction of side information for motion field becomes important, especially in low-bit-rate video compression....