The major challenges in registration between multi-modal images are the non-homogeneous intensity variation and the partial scene changes. Two local frequency representations, namely mean local phase angle (MLPA) and frequency spread phase congruent (FSPC), are used to achieve representations invariant to both non-homogeneous intensity variation and contrast reversal between multi-modal images. In addition, by using FSPC one can effectively emphasize the common structural information. An objective function is constructed to take full advantage of the two representations as well as allocate more confidences to the stable structures. Simplex-simulated annealing algorithm is adjusted to avoid being trapped in local optima. Numerous experiments using real and synthetic images clearly demonstrate that the proposed method can effectively register multi-modal images with significant variation in geometric distortion, non-homogeneous intensity and scene, as well as, improve the registration accuracy and robustness of the conventional methods.