Which metric to use for multi-modal image registration is still a nontrivial research problem. Recently, some methods have used structural representations of images to address this problem. Efficiency and optimization simplicity are the advantages of these algorithms; however, they have some limitations. First, structural representation based registrations often fail when there are intensity variations in the patch (local block) of the image. Second, structural representation based methods are not as accurate as mutual information based methods. In this article, the shortcomings of structural image representation are overcome by devising a new similarity metric called Stochastic Second-Order Entropy Image (SSOEI). We interpolate the neighbourhood intensity information of random pixels in each patch to estimate the histogram of the intensity distribution. Then, entropy of a patch can be computed by this joint histogram. An entropy image is a collection of the entropy value of every image patch. Then, the sum of squared difference from the entropy image can be utilized as the metric of the registration framework. The robustness and accuracy of SSOEI were tested on both synthetic and clinical data, and the results showed the advantages of SSOEI over the state-of-art methods.