In image registration, we determine the most accurate match between two images, which may have been taken at the same or different times by different or identical sensors. In the past, correlation and mutual information have been used as similarity measures for determining the best match for remote sensing images. Mutual information or relative entropy is a concept from information theory that measures the statistical dependence between two random variables, or equivalently it measures the amount of information that one variable contains about another. This concept has been successfully applied to automatically register remote sensing images based on the assumption that the mutual information of the image intensity pairs is maximized when the images are geometrically aligned. The transformation which maximizes a given similarity measure has been previously determined using exhaustive search, but this has been found to be inefficient and computationally expensive. In this paper we utilize a new simple, yet powerful technique based on stochastic gradient, for the maximization of both similarity measures with remote-sensing images, and we compare its performance to that of the exhaustive search. We initially consider images, which are misaligned by a rotation and/or translation only, and we compare the accuracy and efficiency of a registration scheme based on optimization for this data. In addition, the effect of wavelet pre-processing on the efficiency of a multi- resolution registration scheme is determined, using Daubechies wavelets. Finally we evaluate this optimization scheme for the registration of satellite images obtained at different times, and from different sensors. It is noted that once a correct optimization result is obtained at one of the coarser levels in the multi-resolution scheme, then the registration process is much faster in achieving subpixel accuracy, and is more robust when compared to a single level optimization. Mutual information was generally found to optimize in about one third the time required by correlation.