The topic of aerial image registration attracts considerable interest within the imaging research community due to its significance for several applications, including change detection, sensor fusion, and topographic mapping. Our interest is focused on finding the optimal transformation between two aerial images that depict the same visual scene in the presence of pronounced spatial, temporal, and sensor variations. We first introduce a stochastic edge estimation process suitable for geometric shape-based registration, which we also compare to intensity-based registration. Furthermore, we propose an objective function that weights the distances of the edge estimates by the feature points’ energy, which we denote by sum of normalized squared differences and compare to standard objective functions, such as mutual information and the sum of absolute centered differences. In the optimization stage, we employ a genetic algorithm scheme in a multiscale image representation scheme to enhance the registration accuracy and reduce the computational load. Our experimental tests, measuring registration accuracy, rate of convergence, and statistical properties of registration errors, suggest that the proposed edge-based representation and objective function in conjunction with genetic algorithm optimization are capable of addressing several forms of imaging variations and producing encouraging registration results.