A spatially adaptive generalization of motioncompensated prediction that models correspondence as occurring within band-limited ranges of spatial frequencies is presented. An efficient estimation algorithm—frequency adaptive block half-pixel interpolative prediction—is proposed for block translational compensation for video compression. This algorithm decreases the meansquared error (MSE) of temporal prediction for typical video sequences, capturing interframe correlations more accurately than a nonadaptive approach. The algorithm is implemented efficiently with the same hardware and software developed for traditional blockmatching algorithms. Unlike generalized deformational motion models, which require an order of magnitude more computation for similar coding gains, the storage and computational requirements of the new algorithm are modest. Experiments demonstrate that wavelet coding of spatial interframes may be improved by 1 dB [peak signalto- noise ratio (PSNR)] at medium bit rates. For H.263 coding with constant quantization, a 5% reduction in bit rate is achieved even at extremely low rates, with significant additional gains at higher rates. A detailed analysis of H.263 coding of the Foreman sequence demonstrates that 30% bit rate reduction is possible for high-quality coding of frames that frequently violate a traditional block translational motion model.