We present a new method for the fast and robust computation of information theoretic similarity measures for alignment of multi-modality medical images. The proposed method defines a non-uniform, adaptive sampling scheme for estimating the entropies of the images, which is less vulnerable to local maxima as compared to uniform and random sampling. The sampling is defined using an octree partition of the template image, and is preferable over other proposed methods of non-uniform sampling since it respects the underlying data distribution. It also extends naturally to a multi-resolution registration approach, which is commonly employed in the alignment of medical images. The effectiveness of the proposed method is demonstrated using both simulated MR images obtained from the BrainWeb database and clinical CT and SPECT images.