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

but also have speed close to that of TSS.