A showcase of ÉTS researchers’ publications and other contributions

Multi-level rate-constrained successive elimination algorithm tailored to suboptimal motion estimation in HEVC


Downloads per month over past year

Trudeau, Luc, Coulombe, Stéphane and Desrosiers, Christian. 2020. « Multi-level rate-constrained successive elimination algorithm tailored to suboptimal motion estimation in HEVC ». Signal Processing : Image Communication, vol. 81.
Compte des citations dans Scopus : 2.

[thumbnail of Coulombe S 2020 19909.pdf]
Coulombe S 2020 19909.pdf - Accepted Version
Use licence: Creative Commons CC BY-NC-ND.

Download (546kB) | Preview


In the context of motion estimation for video coding, successive elimination algorithms (SEAs) significantly reduce the number of candidates evaluated during motion estimation without altering the resulting optimal motion vector. Nevertheless, SEA is often only used in conjunction with exhaustive search algorithms (e.g., full search). In this paper, we combine the multi-level successive elimination algorithm (ML-SEA) and the rate-constrained successive elimination algorithm (RCSEA) and show that they can be advantageously applied to suboptimal search algorithms. We demonstrate that the savings brought about by the new multi-level RCSEA (ML-RCSEA) outweigh the pre-computational costs of this approach for the Test Zonal (TZ) Search algorithm found in the HM reference encoder. We propose a novel multi-level composition pattern for performing RCSEA on an asymmetric partitioning. We introduce a double-check mechanism for RCSEA, and show that on average, it avoids computing 71% of motion vector (MV) costs. We also apply the proposed ML-RCSEA to bi-predictive refinement search and leverage a cost-based search ordering to remove 56% of error metric computations, on average. When compared to the HM reference encoder, our experiments show that the proposed solution reduces the TZ Search time by approximately 45%, contributing to an average encoding time reduction of about 7%, without increasing the Bjøntegaard delta rate (BD-Rate).

Item Type: Peer reviewed article published in a journal
Coulombe, Stéphane
Desrosiers, Christian
Affiliation: Génie logiciel et des technologies de l'information, Génie logiciel et des technologies de l'information
Date Deposited: 16 Dec 2019 21:46
Last Modified: 26 Nov 2021 05:00

Actions (login required)

View Item View Item