We report two techniques for variable size block matching (VSBM) motion compensation. Firstly an algorithm is described which, based on a quad-tree structure, results in the optimal selection of variable-sized square blocks. It is applied in a VSBM scheme in which the total mean squared error (MSE) is minimised. This provides the best-achievable performance for a quad-tree based VSBM technique. Although it is computationally demanding and hence impractical for real-time codecs, it does provide a yardstick by which the performance of other VSBM techniques can be measured. Secondly, a new VSBM algorithm which adopts a `bottom-up' approach is described. The technique starts by computing sets of `candidate' motion vectors for fixed-size small blocks. Blocks are then effectively merged in a quad-tree manner if they have similar motion vectors. The result is a computationally-efficient VSBM technique which attempts to estimate the `true' motion within the image.

Both methods have been tested on a number or real image sequences. In all cases the new `bottom-up' technique was only marginally worse than the optimal VSBM method but significantly better than the fixed-size block matching and other known VSBM implementations.