FPGA implementation of a novel, fast motion estimation algorithm for real-time video compression

ABSTRACT

A novel block matching algorithm for motion estimation in a video frame sequence, well suited for a high performance FPGA implementation is presented in this paper. The algorithm is up to 40% faster when compared to one of the fastest existing algorithms, viz., one-at-a-time step search algorithm without compromising either in the image quality or in the compression effected. The speed advantage is preserved even in the event of a sudden scene change in a video sequence. The proposed algorithm is also capable of dynamically detecting the direction of motion of image blocks. The FPGA implementation of the algorithm is capable of processing color pictures of sizes up to 1024x768 pixels at the real time video rate of 25 frames/second and conforms to MPEG-2 standards.

REFERENCES

• 1: S.C. Cheng and H.M. Hang, "A comparison of block matching algorithms mapped to systolic array implementation", IEEE Trans. on circuits and systems for video technology, Vol. 7, No. 5, 1997, pp. 741-757.
• 2: M.J. Chen, L.G. Chen, T.D Chieuh, One-dimensional full search motion estimation algorithm for video coding, IEEE Trans. on circuits and systems for video technology, Vol. 4, No. 5, Oct. 1994, pp. 504-509.
• 3: H.M. Jong, L.G. Chen and T.D. Chiueh, Parallel architectures for three step hierarchical search block matching algorithm, IEEE Trans. on circuits and systems for video technology, Vol. 4, No. 4, 1994, pp. 407-417.
• 4: R. Srinivasan, K.R. Rao, Predictive coding based on efficient motion estimation, IEEE Trans. on communications, Vol. COM-33, No. 8, Aug. 1985, pp. 888- 895.
• 5: A Pruning Based Fast Rate Control Algorithm for MPEG Coding, Proceedings of the 3rd International Conference on Computational Intelligence and Multimedia Applications, p.403, September 23-26, 1999
• 6: Rajesh T.N. Rajaram, Optimization of fast search block matching motion estimation algorithms and their VLSI implementation, Thesis work for the degree of Master of Science (by research), Department of Electrical Engineering, Indian Institute of Technology, Madras, June 1999.
• 7: S. Ramachandran, S. Srinivasan and R. Chen, EPLD-based Architecture of Real Time 2D-Discrete Cosine Transform and Quantization for Image Compression, IEEE International symposium on circuits and systems, Orlando, Florida, pp. iii375-378, May-June 1999.
• 8: S. Ramachandran and S. Srinivasan, Design and Implementation of an EPLD-based Variable Length Coder for Real Time Image Compression Applications, The IEEE International symposium on circuits and systems (ISCAS), eneva, Switzerland, pp. I607-610, May 28-31, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Design

Keywords:
block matching algorithm, discrete cosine transform, macroblock, motion estimation, quantization and variable length code, sum of absolute pixel intensity difference