GRASP for seam drawing in mosaicking of aerial photographic maps

Commercial aerial photographic maps are often so large that it is necessary to produce one map from two or more photographs, which are combined two at a time in a process called mosaicking. The objective is to make the final map appear to be the product of a single photograph. Commercial packages exist to do mosaicking, but they are not designed to produce the high quality maps desired by customers of modern cartographic companies. Consequently such companies typically design their own software. Seam-drawing is the most difficult step in the mosaicking process. We model the seam-drawing process by means of several objective functions and present a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the problem. Computational experiments show the merit of the proposed approach.