The registration of pre-operative volumetric datasets to intra-operative two-dimensional images provides an improved way of verifying patient position and medical instrument location. In applications from orthopedics to neurosurgery, it has a great value in maintaining up-to-date information about changes due to intervention. We propose a mutual information-based registration algorithm which establishes the proper alignment via a stochastic gradient ascent strategy. Our main contribution lies in estimating probability density measures of image intensities with a sparse histogramming method which could lead to potential speed-up over existing registration procedures and deriving the gradient estimates required by the maximization procedure. Experimental results are presented on fluoroscopy and CT datasets of a real skull, and on a CT-derived dataset of a real skull, a plastic skull and a plastic lumbar spine segment.