Over the past few years, underwater vehicles have greatly improved as a tool for undersea exploration and navigation. In particular, autonomous navigation, localization, and mapping through optical imaging have become topics of interest for researchers in both underwater robotics and marine science. Underwater imagery can be used to construct image composites (photomosaics) used in many different application areas such as underwater surveying and navigation. For surveying operations with a low-cost robot limited to a down-looking camera and a sonar altimeter, it is common practice to ensure that there is enough overlap between time-consecutive images as this is the only data source of navigation. When the robot revisits a previously surveyed area, it is essential to detect and match the non-time-consecutive images to close a loop and, thus, improve trajectory estimation. While creating the mosaic, most of the existing algorithms try to match all image pairs to detect the non-time-consecutive overlapping images when there is no additional navigation information. We present a framework to obtain a two-dimensional mosaic with minimum image matching attempts and simultaneously get the best possible trajectory estimation by exploring the contribution of the image pairs matching to the whole system. Different strategies for choosing match candidates have been tested, and the results are given in different challenging underwater image sequences. (C) 2010 Wiley Periodicals, Inc.