Mutual information is an attractive registration criterion because it provides a meaningful comparison of images that represent different physical properties. In this paper, we review the shortcomings of three published methods for its computation. We identify the grid effect and the overlap problem as the most severe artifacts that these methods face, and propose a solution based on irregular sampling to solve for the grid effect. By implementing irregular sampling as stochastic sampling, we see that our solution covers the two problems at once, as the overlap problem ceases to be an issue, too.