Research Repository

A low complexity and computationally scalable fast motion estimation algorithm for HEVC

Pakdaman, Farhad and Hashemi, Mahmoud Reza and Ghanbari, Mohammad (2020) 'A low complexity and computationally scalable fast motion estimation algorithm for HEVC.' Multimedia Tools and Applications, 79 (17-18). pp. 11639-11666. ISSN 1380-7501

Full text not available from this repository. (Request a copy)


Motion Estimation (ME) is one of the most computationally demanding parts of video encoders. The Test Zone (TZ) search is a popular fast ME algorithm, which is recommended for High-Efficiency Video Coding (HEVC). While the TZ search achieves an excellent coding efficiency, it is not a favorable choice for hardware implementations due to 1) a relatively high computational complexity, 2) inducing data dependency among the neighboring blocks, which complicates hardware implementations and parallel processing in software implementations, and 3) lack of computational adjustability, which is required for video encoding in power-constrained devices. This paper diagnoses the cause of these issues to be in the multiple starting search points of the TZ search algorithm. Accordingly, a method is proposed to find a single reliable starting point that replaces the first step of the TZ search algorithm. To do so, both current and reference frames are analyzed using a complex wavelet transform, and similar salient points are identified among the two frames. Then a light-weight process is used to match these points to find a single reliable starting point. The reliability of this point leads to reduced zonal refinement range with negligible cost in compression efficiency. Since adjusting the refinement range can be used as an effective way for adjusting the complexity, this results in a computationally scalable ME algorithm, named FMECWT. In contrast to the existing methods, FMECWT does not rely on neighboring blocks, which eliminates the inherent data dependency of TZ search. Experimental results show that FMECWT achieves ~35% to ~85% ME time reduction compared to TZ search, with only 0.1% to 1.7% increase in BD-Rate.

Item Type: Article
Uncontrolled Keywords: Motion estimation; Video compression; Power-constrained video coding; High efficiency video coding (HEVC); Search range reduction
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 04 Dec 2020 09:33
Last Modified: 06 Jan 2022 14:09

Actions (login required)

View Item View Item