Complexity reduction methods for fast motion estimation in HEVC

• Motion estimation is one of the most complex tools in block based video encoders.
• In HEVC, the motion estimation complexity is even higher since there are more block sizes.
• TZSearch algorithm is the fast motion estimation algorithm in HEVC reference software.
• This paper reduces the complexity of TZSearch ME algorithm upto 44.7%.
• The overall RD performance loss is negligible despite decrease in the complexity.

Motion estimation is one of the most demanding and complex tools in block based video encoders. Variable block size motion estimation (ME) and multiple reference frames in H.264/AVC make motion estimation even more complex and time consuming. In HEVC, the complexity is even higher since there are more block sizes. This paper presents an analysis of various tools involved in some fast ME algorithms and proposes some improvements to them in order to achieve a novel fast hybrid algorithm. The proposed algorithm has been tested with HEVC reference software. Simulation results show that the algorithm achieves up to 44.7% decrease in ME complexity when compared to the fast ME algorithm (Test Zone Search or TZSearch) and up to 99% reduction in ME complexity compared to full search algorithm with negligible loss in PSNR and bitrate.