A New Rotation Search for Dependent Rate-Distortion Optimization in Video Coding

We present a novel search algorithm which is suitable for optimizing functions with a high-dimensional discrete-valued parameter vector. The algorithm is designed to find a function local optimum with the minimal number of evaluated points without requiring function derivatives. The algorithm is applied to frame-level rate-distortion (R-D) optimization using Lagrangian relaxation to the rate constraints and to block motion estimation in H.264-based video coding. The R-D optimization is further accelerated by finding a good starting point by the golden section search. The results show excellent near-optimal R-D performance while computation is reduced by 99% compared to the quadratic coordinate-wise steepest descent algorithm. In motion estimation, the new algorithm requires 7-13% less checking points than the small diamond search algorithm with only a small penalty in prediction quality.