Motion estimation is essential for many interframe video coding techniques
block matching algorithms
such as FSA and TSS
have been widely used for motion estimation. The easiest implementation is the FSA
which evaluates all the blocks in the search window and has the highest computational cost. Therefore
many fast search algorithm including TSS
have been proposed to reduce the computational complexity
but most of them are based on the assumption that there should be only one optimal solution in the search window
however
in normal cases
there always exist multitudinous local optima
so they will miss the global optima
but get a suboptimal solution. In this paper
we propose a genetic search algorithm for motion estimation(GSAME) which applies genetic operation to motion estimation. We also introduce a scheme called competition evolution
which can bring the better solutions into the next evolution
and can accelerate the iteration process converging. In this method
the motion vector of block is defined as chromosome
after crossover
mutation and competition evolution
the global optimal solutions will be got. Last we compare the GASME to TSS
FSA
and the result shows that the method not only solve the problem of being trapped to local optima