Rate-based Candidate Elimination for Motion Estimation Algorithms in Video Coding
Keywords:
Video Coding, Integer Motion Estimation, Block-Matching Algorithm, Rate-Constraint, VVCAbstract
This work proposes and evaluates a search space reduction technique for Motion Estimation, which is considered as one of the most important steps in video encoding. Based on previous works' indications that encoder decisions are biased towards candidates with a lower vector cost, the proposed algorithm uses a simple elimination criterion based on the estimated bitrate of candidate motion vectors. In one of the tested configurations of the VVC reference encoder implementation, the technique was able to reduce Motion Estimation search area by more than 80% at the cost of an average 0.74% decrease in coding efficiency with respect to the original search algorithm.
Downloads
References
Amirpour, H., Ghanbari, M., Pinheiro, A., and Pereira, M. (2019). Motion estimation with chessboard pattern prediction strategy. Multimedia Tools and Applications, 78(15):21785–21804.
Bjøntegaard, G. (2001). Calculation of average PSNR differences between RD-curves. Document VCEG-M33, Video Coding Experts Group (VCEG), Austin, Texas, USA.
Bossen, F. (2013). Common HM test conditions and software reference configurations. Document JCTVC-L1100, JCT-VC of ITU-T, Geneva.
Bossen, F., Boyce, J., Li, X., Seregin, V., and Suhring, K. (2019). JVET common test conditions and software reference configurations for SDR video. Document JVETN1010, JVET of ITU-T, Geneva.
Cancellier, L., Seidel, I., and Guntzel, J. L. (2017). Algoritmo de eliminações sucessivas em níveis baseado na soma das diferenças transformadas absolutas. In Anais do XXXVI Concurso de Trabalhos de Iniciação Científica da SBC, Porto Alegre, RS, Brasil. SBC.
Chen, J., Ye, Y., and Kim, S. (2019). Algorithm description for Versatile Video Coding and Test Model 6 (VTM 6). Document JVET-O2002, JVET of ITU-T, Gothenburg.
Cisco (2019). Cisco Visual Networking Index: Forecast and Trends, 2017–2022 White Paper. https://web.archive.org/web/20190820234616/https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/white-paper-c11-741490.html. Accessed: 20 Aug. 2019.
Coban, M. Z. and Mersereau, R. M. (1998). A fast exhaustive search algorithm for rateconstrained motion estimation. IEEE Transactions on Image Processing, 7(5):769–773.
Doan, N., Kim, T. S., Rhee, C. E., and Lee, H.-J. (2017). A hardware-oriented concurrent TZ search algorithm for High-Efficiency Video Coding. EURASIP Journal on Advances in Signal Processing, pages 1–17.
Fan, R., Zhang, Y., and Li, B. (2017). Motion Classification-Based Fast Motion Estimation for High-Efficiency Video Coding. IEEE Transactions on Multimedia, 19(5):893–907.
Goncalves, P., Correa, G., Porto, M., Zatt, B., and Agostini, L. (2017). Multiple earlytermination scheme for TZ search algorithm based on data mining and decision trees. In 2017 IEEE 19th International Workshop on Multimedia Signal Processing (MMSP), pages 1–6.
Goncalves, P., Porto, M., Zatt, B., Agostini, L., and Correa, G. (2018). Octagonal-Axis Raster Pattern for Improved Test Zone Search Motion Estimation. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1763–1767.
Li, W. and Salari, E. (1995). Successive elimination algorithm for motion estimation. IEEE Transactions on Image Processing, 4(1):105–107.
Rosewarne, C., Sharman, K., Sjoberg, R., and Sullivan, G. J. (2019). High Efficiency Video Coding (HEVC) Test Model 16 (HM 16) Encoder Description Update 12. Document JCTVC-AK1002, JCT-VC of ITU-T, Geneva.
Sant’Anna, G. B., Cancellier, L. H., Seidel, I., Grellert, M., and Guntzel, J. L. (2021). Relying on a rate constraint to reduce motion estimation complexity. https://arxiv.org/abs/2102.09656. Preprint.
Shan Zhu and Kai-Kuang Ma (2000). A new diamond search algorithm for fast blockmatching motion estimation. IEEE Transactions on Image Processing, 9(2):287–290.
Siqueira, I., Correa, G., and Grellert, M. (2020). Rate-Distortion and Complexity Comparison of HEVC and VVC Video Encoders. In 2020 IEEE 11th Latin American Symposium on Circuits Systems (LASCAS), pages 1–4.
Sullivan, G. J. and Wiegand, T. (1998). Rate-distortion optimization for video compression. IEEE Signal Processing Magazine, 15(6):74–90.
Trudeau, L., Coulombe, S., and Desrosiers, C. (2018). Cost-Based Search Ordering for Rate-Constrained Motion Estimation Applied to HEVC. IEEE Transactions on Broadcasting, 64(4):922–932.
Watson, A. (2020). Consuming media at home due to the coronavirus worldwide. https://www.statista.com/statistics/1106498/home-media-consumption-coronavirus-worldwide-by-country/. Accessed: 16 Jun. 2020.
Zhang, Y., Zhang, C., and Fan, R. (2018). Fast Motion Estimation in HEVC Inter Coding: An Overview of Recent Advances. In 2018 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pages 49–56.
