Efficient block motion estimation using integral projections

Several efficient techniques have recently been proposed to reduce the computational burden of block matching for motion estimation in video coding. The goal is efficient motion estimation with minimal error in the motion-compensated predicted image. We present a block motion estimation scheme which is based on matching of integral projections of motion blocks with those of the search area in the previous frame. Like many other techniques, ours operates in a sequence of decreasing search radii, but it performs exhaustive search at each level of the hierarchy. The projection method is much less computationally costly than block matching and has prediction accuracy of competitive quality with both full block matching and other efficient techniques. Our algorithm also takes advantage of the similarity of motion vectors in adjacent blocks in typical imagery by subsampling the motion vector field. It has the added advantage of allowing parallel computation of vertical and horizontal displacements.