Title: Fast Block Motion Estimation Using
Gray‐Code Kernels
Abstract:
Motion estimation plays an important role in modern video coders. In such
coders, motion is estimated using a block matching algorithm that estimates
the amount of motion on a block‐by‐block basis. A full search technique for
finding the best matching blocks delivers good accuracy but is usually not
practical because of its high computational complexity. In this talk, a
novel fast block‐based motion estimation algorithm is presented. This
algorithm uses an efficient projection framework which bounds the distance
between a template block and candidate blocks. Fast projection is performed
with a family of highly efficient filter kernels – the Gray‐Code Kernels –
using only 2 operations per pixel for each filter kernel. The projection
framework is combined with a rejection scheme which allows rapid rejection
of candidate blocks that are distant from the template block. The tradeoff
between computational complexity and quality of results could be easily
controlled in the proposed algorithm, thus it enables adaptivity to image
content to further improve the results. Experiments show that the proposed
adaptive algorithm significantly outperforms popular fast motion estimation
algorithms, such as three‐step search and diamond search.