Fast multi-mode search algorithm combining genetic algorithm with diamond search in video coding

In order to solve the conflicts between searching precision and searching speed of motion vectors in video coding, a fast MMS (Multi-Mode Search) algorithm based on GA (Genetic Algorithm) and DS (Diamond Search) is proposed in this paper. Its searching modes can be switched adaptively by the criterion of drastic level of the predictive motion vectors derived from the spatio-temporal coherence of the video sequences. In the mild motion mode, DS method is used directly; In the drastic motion mode, a combined GA/DS searching method is adopted. Comparing with nowadays fast sub-optimal searching methods, MMS can solve the performance falling problem in case of large motion vectors, which enhance the capability of video encoders thoroughly. Its performance is near to the results of ideal FS (Full Search) algorithm. Comparing with other searching methods using GA directly for obtaining global optimum, MMS combines DS with GA to achieve rapid convergence speed. Furthermore, by introducing multi-mode processing conception, the efficiency of sub-optimal searching methods is fully carried out. Its searching speed is nearly as fast as DS. And its searching precision is guaranteed simultaneously. This algorithm provides a new framework for solving the conflicts in motion estimation problems in video coding. The experimental results have rectified its effectiveness.