Balancing Complexity of Template Matching-based Reference Picture Padding for Video Coding

Reference picture padding is the task of padding the outside of the reference picture for inter prediction. This task is done to accommodate for motion vectors that extend partly outside the picture, thereby increasing compression efficiency. The established approach involves simply duplicating the boundary pixels outward. While this solution boasts low complexity, it often results in suboptimal compression performance in numerous cases. Template matching-based reference picture padding presents itself as a promising method to further increase compression efficiency and reduce artifacts. However, its primary drawback lies in its high computational complexity. One potential solution entails restricting the number of considered candidates per search step to a very small set to maintain a feasibly low increase in decoder runtime. This, however, compromises the compression efficiency. In this study, we propose a novel approach that maintains the efficiency gains, while significantly reducing the increase in decoder runtime. This method primarily focuses the computational complexity on pixels more frequently utilized in inter prediction. Additionaly, we introduce an early stopping criterion that terminates the search if at least one similar candidate is found. Through these modifications we achieve a reduction in decoder runtime increase from 1252% to 159%, while maintaining -0.37% compared to -0.41% Bjontegaard delta rate in a Versatile Video Coding subpicture coding scenario.