Automatic image registration is an attractive and unresolved problem in the machine vision literature. This paper presents two novel structural constraints, namely proximity and closeness constraints, that improve both the accuracy and robustness of an existing motion consistency based algorithm (GICP) for automatic image registration. It also defines the conditions when such constraints are fired at specific points of the registration of two overlapping range images. The proximity constraint says that neighbouring points should be neighbouring before and after a rigid motion. The closeness constraint implements a local closest point search from the second image to the first image. While the GICP algorithm uses an exhaustive search for the closest points, in this paper, we employ the optimised k-d tree data structure to accelerate the closest point search. A large number of experiments based on real range images demonstrate that the combination of rigid motion constraints with these novel proximity and closeness constraints leads to a more accurate and robust evaluation of possible correspondences leading, in turn, to more accurate, robust and efficient automatic image registration results.