Quadtree-structured variable-size block-matching motion estimation with minimal error

This paper reports two efficient quadtree-based algorithms for variable-siz e block matching (VSBM) motion estimation, The schemes allow the dimensions of blocks to adapt to local activity within the image, and the total numbe r of blocks in any frame can be varied while still accurately representing true motion, This permits adaptive hit allocation between the representatio n of displacement and residual data, and also the variation of the overall bit-rate on a frame-by-frame basis, The first algorithm computes the optima l selection of variable-sized blocks to provide the hest-achievable predict ion error under the fixed number of blocks for a quadtree-based VSBM techni que. The algorithm employs an efficient dynamic programming technique utili zing the special structure of a quadtree, Although this algorithm is comput ationally intensive, it does provide a yardstick by which the performance o f other more practical VSBM techniques can be measured. The second algorith m adopts a heuristic vr ay to select variable-sized square blocks. It relie s more on local motion information than on global error optimization. Exper iments suggest that the effective use of local information contributes to m inimizing the overall error. The result is a more computationally efficient VSBM technique than the optimal algorithm, but with a comparable predictio n error.