Full Search Based Fast Block Matching Algorithm with Efficient Matching Order in Motion Estimation

Jong-Nam KIM  SeongChul BYUN  ByungHa AHN  

IEICE TRANSACTIONS on Communications   Vol.E86-B   No.3   pp.1191-1195
Publication Date: 2003/03/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Multimedia Systems
motion estimation,  block matching algorithm,  fast full search,  adaptive matching,  

Full Text: PDF(184.8KB)>>
Buy this Article

In this letter we propose a new fast matching algorithm that has no degradation of predicted images such as found in the conventional full search (FS) algorithm, so as to reduce the amount of computation of the FS algorithm for motion estimation in real-time video coding applications. That is, our proposing algorithm reduces only unnecessary computations in the process of motion estimation without decreasing the prediction quality compared to the conventional FS algorithm. The computational reduction comes from rapid elimination of impossible motion vectors. In comparison to the FS algorithm, we obtained faster elimination of inappropriate candidate motion vectors using efficient matching units based on image complexity. Experimentally, we demonstrated that the unnecessary computations were removed by about 30% as compared to the other fast FS algorithms.