An efficient dynamic multiple-candidate motion vector approach for GPU-based hierarchical motion estimation
Dung T. Vu, Yang Yang, Laxmi Narayan Bhuyan · 2012
Hierarchical or pyramid search is a widely used approach in motion estimation, a most expensive function in video encoding, for its low computational complexity and high efficiency. In this approach, multiple down-sampled resolutions from video frames are created. An initial motion estimation is quickly made at a lowest resolution. The final motion estimation result is achieved by propagating the initial estimation towards the original resolution. GPU or General purpose GPU embedded hundreds of number of SIMD-based cores is best suitable for motion estimation, especially with full-search-based approaches as the process can be efficiently parallelized. However, a common fundamental drawback of the hierarchical search is the erroneous estimation from the reduced resolutions may cause the final motion estimation inaccurate. Multiple-candidate motion vector approaches are proposed, however, they lack a mechanism to select the best multiple-candidate schemes considering diverse video encoding characteristics. In this paper we analyse and verify the computational complexity of the hierarchical search using NVIDIA's GPU with realistic workloads. Based on this analysis, we propose an efficient dynamic multiple-candidate motion vector approach to dynamically select best multiple-candidate motion vector schemes at runtime. This approach can achieve highest possible speedups and satisfy a desire motion estimation efficiency. Experiments on realistic workloads show the dynamic scheme selection outperforms the fixed scheme selection based on profiling.