A comparison of block-matching search algorithms in motion estimation
Saket Jamkar, Swapnil Belhe, Sankalp Dravid, Mukul Sutaone · 2002
This paper deals with a comparison of the search algorithms used for Motion Estimation in Video Compression. A comparison is made between four block search algorithms: Full Search, Three Step Search, Two Dimensional Logarithmic Search and Binary Search. The computational complexity of the search algorithms as represented by CPU time and the algorithm quality as represented by the Pixel Difference Classification and Average Minimum Absolute Distance are given.A comparison of the performance of search algorithms with block sizes of 8 × 8 and 16 × 16 is also given with sample images to show the perceptual difference. All the algorithms were tested on test video-streams called news.qcif and container.qcif and the algorithms were implemented on TurboC and executed on a Pentium 3 machine.