In the last decade information-theoretic similarity measures, especially mutual information and its derivatives, have proven to be accurate measures for rigid and non-rigid, mono- and multi-modal image registration. However, these measures are sometimes not robust enough, especially in cases of poor image quality. This is most likely due to the lack of spatial information included in the measure as usually only intensities are employed to measure similarity between images. Spatial information in the form of intensity gradients or second derivatives may be included in information-theoretic similarity measures. This paper presents a novel method for efficiently combining multiple features into the estimation of mutual information. The proposed measure, under certain assumptions on feature probability distribution, strictly follows information theory in contrast to a number of heuristic methods that were proposed to include spatial information in mutual information. The novel approach solves the problem of efficient estimation of multi-feature mutual information from sparse high-dimensional histograms. The proposed measure was tested on widely used Vanderbilt image database. Results indicate that multi-feature mutual information outperforms the single-feature mutual information measure. The contribution of additional image features to registration is especially significant in cases when standard mutual information measure fails. Moreover, it is expected that non-rigid registration may also benefit from the proposed multi-feature mutual information measure.