Successive Level Elimination Algorithm based on the Sum of Absolute Transformed Differences

• Luiz Cancellier UFSC
• Ismael Seidel UFSC
• José Luís A. Güntzel UFSC

Abstract

The increasing resolutions combined with storage and processing limitations of mobile devices demand new compression techniques for video coding. Therefore, to achieve higher compression rates without compromising quality, the coding process becomes more and more complex. The most expensive step in video coding is the Motion Estimation, that consists of the search by a candidate block that minimizes a metric. This work proposes a new elimination criterion to Multilevel Successive Elimination Algorithm which is based on the Sum of Absolute Transformed Differences similarity metric. In the worst cases, the criterion eliminates 25% and 69% of evaluated candidates on Fractional and Integer Motion Estimation, respectively.

References

Agaian, S., Sarukhanyan, H., Egiazarian, K., and Astola, J. (2011). Hadamard Transforms. SPIE Press Monograph Vol. PM207. SPIE Press.

Agostini, L. V. (2007). Desenvolvimento de arquiteturas de alto desempenho dedicadas à compressão de vídeo segundo o padrão H.264/AVC. Tese de doutorado, UFRGS.

Bossen, F. (2012). Common test conditions and software reference configurations. Document JCTVC-K1100, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, Shanghai.

Bossen, F., Bross, B., Suhring, K., and Flynn, D. (2012). HEVC complexity and implementation analysis. IEEE Trans. on Circ. Syst. for Video Technology, 22(12):1685–1696.

Gao, X., Duanmu, C., and Zou, C. (2000). A multilevel successive elimination algorithm for block matching motion estimation. IEEE Trans. on Image Process., 9(3):501–504.

Huang, Y.-W., Chen, C.-Y., Tsai, C.-H., Shen, C.-F., and Chen, L.-G. (2006). Survey on block matching motion estimation algorithms and architectures with new results. J. VLSI Signal Process. Syst., 42(3):297–320.

ITU-T (2013). Recommendation ITU-T H.265: High efficiency video coding. Recommendation H.265, International Telecommunication Union, Genebra.

Li, W. and Salari, E. (1995). Successive elimination algorithm for motion estimation. IEEE Trans. on Circ. Syst. for Video Technology, 4(1):105–107.

Liu, J., Chen, X., Fan, Y., and Zeng, X. (2011). A full-mode FME VLSI architecture based on 8x8/4x4 adaptive Hadamard transform for QFHD H.264/AVC encoder. In 2011 IEEE/IFIP 19th International Conference on VLSI and System-on-Chip, pages 434–439.

Richardson, I. E. G. (2003). H. 264 and MPEG-4 video compression: video coding for next-generation multimedia. John Wiley & Sons Inc.

Schechter, E. (1996). Handbook of Analysis and Its Foundations. Elsevier Science.

Seidel, I. (2016). Exploiting SATD Properties to Reduce Energy in Video Coding. Exame de qualificação (doutorado), UFSC, Florianópolis-SC.

Seidel, I., Cancellier, L., Güntzel, J. L., and Agostini, L. (2016). Rate-constrained successive elimination of Hadamard-based SATDs. In IEEE International Conference on Image Process. (ICIP), pages 2395–2399.

Trudeau, L., Coulombe, S., and Desrosiers, C. (2015). An adaptive search ordering for rate-constrained successive elimination algorithms. In IEEE International Conference on Image Process. (ICIP), pages 207–211.

Wiegand, T. and Schwarz, H. (2016). Video coding: Part II of fundamentals of source and video coding. Foundations and Trends in Signal Processing, 10(1–3):1–346.

Zhu, C., Qi, W.-S., and Ser, W. (2005). Predictive fine granularity successive elimination for fast optimal block-matching motion estimation. IEEE Trans. on Image Process., 14(2):213–221.