Computation-constrained dynamic search range control for real-time video encoder

Search range (SR) is a key parameter on the search quality control for motion estimation (ME) of a real-time video encoder. Dynamic search range (DSR) is a commonly employed algorithm to reduce the computational complexity of ME in a video encoder. In this paper, we model an effective predicted motion vector (PMV) deviation metric to predict the relationship between SR and motion vector difference (MVD), according to the prediction differences of both temporal and spatial motions of neighboring blocks. In addition, a computation-constrained DSR (CDSR) control algorithm is proposed to manage the computational complexity while maximizing video coding quality in a real-time computational constrained scenario. The SR is dynamically determined by three factors: motion complexity, user-defined probability and computation budget. Compared to the conventional DSR algorithms, the proposed CDSR is an effective and quantifiable algorithm to allocate more computation budget to the blocks with high PMV deviations (such as motion object boundary), and less computation budget to the well-matched motion predicted blocks, while maintaining a constrained computation requirement. Experimental results show that the proposed CDSR control algorithm is an effective method to manage the computation consumption of the DSR algorithm while keeping similar rate-distortion (RD) performance. It can achieve about 0.1-0.3 dB average PSNR improvement when the computation consumption is restricted to a specific level as compared with its equivalent Fixed SR algorithm and can achieve about 50-90% computation savings when compared to the benchmarks. For ME with high performance Processing Element (PE) engine, the quality degradation caused by the proposed CDSR algorithm can be ignored.