An approach to increase the performance of motion estimation algorithms implemented in hardware

ABSTRACT

Internally to a video coder, the motion estimation module is the computational block which most demands processing power. One of the components that increase significantly the motion estimation computational cost is the block matching mechanism that consists in searching for similar macroblocks in comparation among the current macroblock and others reference image macroblocks. This article presents a new approach of SAD (Sum of Absolute Differences) calculation, which increases the performance of the macroblock comparison. As result of this new approach we can observe the high performance to calculate the image motion vectors, allowing real time encoding of high definition videos, which is hard to get with nowadays approaches. The cost of this performance increasing is a small loss of video quality, lower than a quarter of one dB (PSNR).Internamente a um codificador de vídeo, o módulo de estimativa de movimento é o bloco computacional que mais demanda processamento. Um dos componentes que aumenta significativamente o custo computacional deste módulo é o mecanismo de comparação de afinidade de blocos de pixels (block matching) que consiste no método de busca por macroblocos semelhantes tomando-se o macrobloco atual e outros da imagem de referência. Este artigo apresenta uma nova abordagem de c´lculo de SAD (Sum of Absolute Differences), que aumenta consideravelmente o desempenho da comparação de macroblocos. A conseqüência dessa abordagem é a grande rapidez para calcular os vetores de movimento de um determinado vídeo, permitindo a codificação em tempo real de vídeos de alta resolução, o que é uma dificuldade presente em abordagens convencionais. O custo desse aumento de desempenho é uma pequena perda de qualidade do vídeo, na ordem de alguns décimos de dB (PSNR).

REFERENCES

• 1: MPEG-2: ISO/IEC JTC1/SC29/WG11 e ITU-T, "ISO/IEC 13818-5: Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Software Simulation". ISO/IEC and ITU-T, 1997.
• 2: Jack, K. Video Demystified. Eagle Rock, VA: LLH Technology Publishing. 3a ed, 2001, 759p.
• 3: Richardson I. E. G. Richardson, H.264 and MPEG-4 Video Compression, UK: Wiley & Sons, 2003.
• 4: Gao, W. et al, "AVS - The Chinese Next-Generation Video Coding Standard," NAB 2004, Las Vegas, Abril, 2004.
• 5: Bruno, G. VEBIT: um novo algoritmo para codificação de vídeo com escalabilidade. 2003. 95p. Dissertação (Mestrado em Ciência da Computação) - Instituto de Informática, UFRGS, Porto Alegre.
• 6: Nielsen, O.; Eriksen, N. A Broadcaster's Guide to MPEG - the MPEG Technology in Perspective. RE Technology AS. 1996. 108p.
• 7: Nousias, I. "Optimized Hardware/Software MPEG Video Player". Institute for System Level Integration - The Alba Campus. 2002. Livingston - Escócia, Inglaterra.
• 8: FRÖHLICH, Humberto et al. Análise da implementação de um decodificador de vídeo em FPGA. In: XI SIMPÓSIO BRASILEIRO DE SISTEMAS MULTIMÍDIA E WEB (WEBMEDIA 2005), Poços de Caldas, MG. v. 1, p. 145--160.
• 9: HUSEMANN, Ronaldo; SOUZA JR, Adão Antonio de; TOME, Takashi; ROESLER, Valter. Análise da implementação de algoritmos de codificação e decodificação de vídeo MPEG-2 HD escalável em hardware. In: XXXIII SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE (SEMISH 2006), 2006, Campo Grande, MS.
• 10: ISO/IEC TR 14496 - Part 7, 'Optimized Reference Software for Coding of Audio-visual Objects', first edition, 2002.
• 11: ITU-T H.262 ou ISO/IEC 13818-2. "Coding of Moving Pictures and Associated Audio". November 1993.
• 12: T. Koga et al. Motion-compensated interframe coding for video conferencing. In: proceedings Nat. Telecom. Conf., dez 81.
• 13: R. Li, B. Zeng, and M. L. Liou, "A new three-step search algorithm for block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438--442, Aug. 1994.
• 14: L. M. Po and W. C. Ma, "A novel four-step search algorithm for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313--317, June 1996.
• 15: Kuo-Liang Chung, Lung-Chun Chang: A new predictive search area approach for fast block motion estimation. IEEE Transactions on Image Processing. V. 12 N. 6, pp 648--652. 2003.
• 16: Shan Zhu and Kai-Kuang Ma. A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation. IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 2, FEBRUARY 2000.
• 17: Sung-Eun Kim; Jong-Ki Han; Jae-Gon Kim. Efficient motion estimation algorithm for MPEG-4 to H.264 transcoder. ICIP 2005. IEEE International Conference on Image Processing. Sept. 2005. V3, page(s): III-656--659.
• 18: J. Xu, Z. Chen, and Y. He "Efficient Fast ME Predictions and Early-termination Strategy Based on H.264 Statistical Characters," In proc., Int. Conf., Inform., Communication and Signal Processing vol.1, pp.218--222, Dec. 2003.
• 19: Y.-Q. Zhang and S. Zafar, "Motion-compensated wavelet transform coding for color video compression," IEEE Trans. Circuits Syst. Video Technol., vol. 2, pp. 285--296, Sept. 1992.
• 20: S. Kim, S. Rhee, J. G. Jeon, and K. T. Park, "Interframe coding using two-stage variable block-size multiresolution motion estimation and wavelet decomposition," IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 399--409, Aug. 1998.
• 21: K. M. Nam, J.-S. Kim, R.-H. Park, and Y. S. Shim, "A fast hierarchical motion vector estimation algorithm using mean pyramid," IEEE Trans. Circuits Syst. Video Technol., vol. 5, pp. 344--351, Aug. 1999.
• 22: Xudong S. et. al. "New Fast Binary Pyramid Motion Estimation for MPEG2 and HDTV Encoding", In IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, n. 7, October 2000, p. 1015--1028.
• 23: Zan, J. Ahmad, M. O. Swamy. Pyramidal motion estimation techniques exploiting intra-level motion correlation. In: IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. V 50, N. 2; pp 83--93. Feb 2003.
• 24: Lee S. et. al. "New Motion Estimation Algorithm Using Adaptively Quantized Low Bit-Resolution Image and Its VLSI Architecture for MPEG2 Video Encoding", In IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, n. 6, October 1998, p. 734--744
• 25: X. Q. Gao, C. J. Duanmu, and C. R. Zou, "A multilevel successive elimination algorithm for block matching motion estimation," IEEE Trans. Image Processing, vol. 9, pp. 501--504, Mar. 2000.
• 26: M. Brünig and W. Niehsen, "Fast full-search block matching," IEEE Trans. Circuits Syst. Video Technol., vol. 11, pp. 241--247, Feb. 2001.
• 27: Yu-Wen Huang et. al. "Global elimination algorithm and architecture design for fast block matching motion estimation". In: IEEE Transactions on Circuits and Systems for Video Technology, V. 14, N. 6, June 2004. pp 898--907.
• 28: Tourapis A. M., Au 0. C. and Liou M. L. "Predictive Motion Vector Field Adaptive Search Technique (PMVFAST) - Enhancing Block Based Motion Estimation," in Proc. of Visual Communications and Image Processing, pp.883--892, Jan. 2001.
• 29: Sung-Eun Kim , Jong-Ki Han, Efficient Motion Estimation Using a Modified Early Termination Algorithm in H.264, IEICE - Transactions on Information and Systems, v.E88-D n.7, p.1707-1715, July 2005 [doi>10.1093/ietisy/e88-d.7.1707]
• 30: Liu, B.; Zaccarin, A. "New fast algorithms for the estimation of block motion vectors". In: IEEE Transactions on Circuits and Systems for Video Technology, V. 3, N. 2, April 1993, pp 148--157
• 31: Zhong-Li He et al. "Low-power VLSI design for motion estimation using adaptive pixel truncation". In: IEEE Transactions on Circuits and Systems for Video Technology, V. 10, N. 5, Aug. 2000, pp 669--6

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
PMVFast, estimativa de movimento