A NEW ROTATION SEARCH FOR DEPENDENT RATE-DISTORTION OPTIMIZATION IN VIDEO CODING

We present a novel search algorithmwhich is suitable for opti-mizing functions with a high-dimensional discrete-valued pa-rameter 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 ap-plied to frame-level rate-distortion (R-D) optimization using Lagrangian relaxation to the rate constraints and to block mo-tion estimation in H.264-based video coding. The R-D op-timization 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 qual-ity. Index Terms — Rate-distortion optimization, Motion es-timation, Optimization method