Browse Prior Art Database

Method for a general line reduction algorithm for motion estimation

IP.com Disclosure Number: IPCOM000103408D
Publication Date: 2005-Mar-17
Document File: 5 page(s) / 48K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for a general line reduction algorithm for motion estimation. With the proposed method, the performance can be improved a lot.

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

Method for a general line reduction algorithm for motion estimation

Disclosed is a method for a general line reduction algorithm for motion estimation. With the proposed method, the performance can be improved a lot.

Background

              A conventional full search (FS) algorithm can determine the globally optimal block-matching point for motion estimation. However, the algorithm must traverse all checking points, which results in an extensive computation load. To improve performance, several search algorithms have been developed, including the following:

•             Three-step search (TSS)

•             Four-step search (4SS)

•             Diamond search (DS)

•             Motion vector field adaptive search technique (MVFAST)

      These algorithms use different patterns and a corresponding search strategy to determine the locally optimal matching point. However, further performance improvements are required, especially for embedded system.

      Every macroblock (MB) has some correlation with surrounding MBs. This correlation can be used to reduce temporal redundancy. For example, MVFAST uses a prediction motion vector (MV) to position the startup search point if large motion exists. The prediction MV indicates the direction of the best matching point. As a result, it can position the relative minimum point and help to find the global minimum point.

General description

      The disclosed method includes a line reduction algorithm (LRA) to improve motion estimation performance. The key elements of the disclosed method include:

•             Reduce the number of calculations by reducing the number of calculating lines using the correlation of INTER MBs and line sum of absolute difference (SAD)

•             Search from the best matching point to the worst matching point using search patterns

•             Start the calculation from the line of maximum SAD to the one of minimum SAD within a searching point

•             Use subsampling based on the line SAD correlation to reduce the number of line calculations

      The performance improvement from the disclosed method is at least 21.4% for an Akiyo-type sequence with an MVFAST algorithm and up to 67.1% for Foreman-based data with a DS algorithm.

      The LRA is a general method that can be used for all video CODECs and most ME algorithms to improve block matching performance.

Advantages                                                                                                                                                                                                        

              The disclosed method provides advantages, including:

•             Improved functionality due to providing a general LRA for use with most block-matching algorithms

•             Improved...