One of the most important features of mobile robots is their capability to gather data from areas beyond human reach. This capability has increased the demand for the use of robots undertaking exploration tasks, which has naturally led to the need for efficient methods to process the obtained data. Image mosaicing is a useful tool for obtaining a high-resolution visual representation of a large area that has been explored using optical sensors. In this paper, we present an efficient image mosaicing approach that utilizes submapping methods to obtain a map of a surveyed area with reduced computational effort. The approach uses a modified agglomerative hierarchical clustering method to form submaps according to similarity information obtained through feature descriptor matching, and takes advantage of this submapping to reduce the computation and time costs. Comparative results on real challenging underwater datasets are presented.