Current automated intensity-based registration procedures make use of similarity functions computed with joint histograms, such as the well-known Mutual Information or the recent Correlation Ratio. We notice that the computation of such histograms represents up to 90% of time of the whole process. We propose in this work a method to accelerate the computation of these histograms in the case of affine transformations, with a slight loss of accuracy. An analytical model of the new computation time allows us to find optimal parameters for a chosen precision and to predict the performance of the algorithm. Experimental results show that the speedup is greater than three with the Partial Volume interpolation method or near ten with the Nearest Neighbors distribution, without significant loss of precision in the final result.