OPTIMIZATION OF FAST BLOCK MOTION ESTIMATION ALGORITHMS

There are basically three approaches for carrying out fast block motio n estimation: 1) fast search by a reduction of motion vector candidate s; 2) fast block-matching distortion (BMD) computation; and 3) motion field subsampling, The first approach has been studied more extensivel y since different ways of reducing motion vector candidates may result in significantly different performance; while the second and third ap proaches can in general be integrated into the first one so as to furt her accelerate the estimation process. In this paper, we first formula te the design of good fast estimation algorithms based on motion vecto r candidate reduction into an optimization problem that involves the c hecking point pattern (CPP) design via minimizing the distance from th e true motion vector to the closest checking point (DCCP). Then, we de monstrate through extensive studies on the statistical behavior of rea l-world motion vectors that the DCCP minimization can result in fast s earch algorithms that are very efficient as well as highly robust. To further utilize the spatiotemporal correlation of motion vectors, we d evelop an adaptive search scheme and a hybrid search idea that involve s a fixed CPP and a variable CPP. Simulations are performed to confirm their advantages over conventional fast search algorithms.