VVC Search Space Analysis Including an Open, Optimized Implementation

Abstract

Versatile Video Coding (VVC) is a new video coding standard finalized in July 2020. During the standard development much attention was paid to keeping the decoding complexity increase as small as possible, with more permissive approach being taken with regard to the encoding. The VVC reference software VTM in random access configuration requires around double the time to decode and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8\times $ </tex-math></inline-formula> the time to encode a video, compared to High Efficiency Video Coding (HEVC) reference software HM. With this runtime increase, an objective bitrate reduction of around 40% is achieved. In this paper we analyze the encoding complexity increase of VVC over HEVC. We abstract the implementation-based aspects, including low-level software optimizations and introduce an empirical measure to quantify the extent of encoder search space given a specific search algorithm. Based on the measure, we compare the search space of HM and VTM, but also of the open and optimized VVC encoder implementation VVenC, showing the potential for search space reduction and its impact on compression performance. Overall, it can be seen that while VVC’s search space is quite large in VTM, it can be efficiently limited either by including early termination strategies or by disabling VVC coding tools.