This paper presents a unifying approach for calculating a wide range of popular, but seemingly very different, similarity measures. Our domain is the registration of n-dimensional images sampled on a regular grid, and our approach is well suited for gradient-based optimization algorithms. Our approach is based on local intensity histograms and built upon the technique of Locally Orderless Images. Histograms by Locally Orderless Images are well posed and offer explicit control over the 3 inherent and unavoidable scales: the spatial resolution, intensity levels, and spatial extent of local histograms. Through Locally Orderless Images, we offer new insight into the relations between these scales. We demonstrate our unification by developing a Locally Orderless Registration algorithm for two quite different similarity measures, namely, Normalized Mutual Information and Sum of Squared Differences, and we compare these variations both theoretically, and empirically. Finally, using our algorithm, we explain the empirically observed differences between two popular joint density estimation techniques used in registration: Parzen Windows and Generalized Partial Volume.