In block matching type motion compensation schemes, the image is divided into blocks of the same size. For each block a search is conducted in the previous frame to locate the best correspondence. For the scheme to succeed an implicit assumption has to be made that the motion within each block is uniform, an assumption which may not necessarily be correct, and as a result the quality of the prediction suffers. In the paper, a new motion compensation scheme based on block matching is presented, where the size for each block is variable. The proposed algorithm adaptively divides the image into blocks of variable size to meet the assumption on uniform motion for all blocks. The scheme has been successfully applied to simple interframe video coding. It is shown that the proposed algorithm can be extended to form the basis of a complete and efficient codec with low complexity. The possibility of the combination of the scheme with novel hybrid coding techniques to form sophisticated systems with low bit-rate performance, that compare favourably with other existing schemes, is also demonstrated.