OSA's Digital Library

Journal of the Optical Society of America A

Journal of the Optical Society of America A


  • Editor: Franco Gori
  • Vol. 31, Iss. 4 — Apr. 1, 2014
  • pp: 773–782

Graph theory approach for match reduction in image mosaicing

Armagan Elibol, Nuno Gracias, Rafael Garcia, and Jinwhan Kim  »View Author Affiliations

JOSA A, Vol. 31, Issue 4, pp. 773-782 (2014)

View Full Text Article

Enhanced HTML    Acrobat PDF (1082 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



One of the crucial steps in image mosaicing is global alignment, which requires finding the best image registration parameters by employing nonlinear minimization methods over correspondences between overlapping image pairs for a dataset. Based on graph theory, we propose a simple but efficient method to reduce the number of overlapping image pairs without any noticeable effect on the final mosaic quality. This reduction significantly lowers the computational cost of the image mosaicing process. The proposed method can be applied in a topology estimation process to reduce the number of image matching attempts. The method has been validated through experiments on challenging underwater image sequences obtained during sea trials with different unmanned underwater vehicles.

© 2014 Optical Society of America

OCIS Codes
(150.0150) Machine vision : Machine vision
(110.4153) Imaging systems : Motion estimation and optical flow
(110.4155) Imaging systems : Multiframe image processing

ToC Category:
Imaging Systems

Original Manuscript: August 5, 2013
Revised Manuscript: January 12, 2014
Manuscript Accepted: February 14, 2014
Published: March 19, 2014

Armagan Elibol, Nuno Gracias, Rafael Garcia, and Jinwhan Kim, "Graph theory approach for match reduction in image mosaicing," J. Opt. Soc. Am. A 31, 773-782 (2014)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. A. Fusiello and V. Murino, “Augmented scene modeling and visualization by optical and acoustic sensor integration,” IEEE Trans. Vis. Comput. Graph. 10, 625–636 (2004).
  2. W. S. Pegau, D. Gray, and J. R. V. Zaneveld, “Absorption and attenuation of visible and near-infrared light in water: dependence on temperature and salinity,” Appl. Opt. 36, 6035–6046 (1997). [CrossRef]
  3. H. Loisel and D. Stramski, “Estimation of the inherent optical properties of natural waters from irradiance attenuation coefficient and reflectance in the presence of Raman scattering,” Appl. Opt. 39, 3001–3011 (2000). [CrossRef]
  4. J. Jaffe, K. Moore, J. McLean, and M. Strand, “Underwater optical imaging: status and prospects,” Oceanography 14, 64–75 (2001).
  5. Z. Zhu, E. Riseman, A. Hanson, and H. Schultz, “An efficient method for geo-referenced video mosaicing for environmental monitoring,” Machine Vis. Appl. 16, 203–216 (2005). [CrossRef]
  6. J. Escartin, R. Garcia, O. Delaunoy, J. Ferrer, N. Gracias, A. Elibol, X. Cufi, L. Neumann, D. J. Fornari, S. E. Humpris, and J. Renard, “Globally aligned photomosaic of the Lucky Strike hydrothermal vent field (Mid-Atlantic Ridge, 3718.5’N): release of georeferenced data, mosaic construction, and viewing software,” Geochem. Geophys. Geosyst. 9, Q12009 (2008).
  7. B. Bingham, B. Foley, H. Singh, R. Camilli, K. Delaporta, R. Eustice, A. Mallios, D. Mindell, C. Roman, and D. Sakellariou, “Robotic tools for deep water archaeology: surveying an ancient shipwreck with an autonomous underwater vehicle,” J. Field Robot. 27, 702–717 (2010).
  8. K. Jerosch, A. Lüdtke, M. Schlter, and G. Ioannidis, “Automatic content-based analysis of georeferenced image data: detection of beggiatoa mats in seafloor video mosaics from the Hakon Mosby mud volcano,” Comput. Geosci. 33, 202–218 (2007). [CrossRef]
  9. O. Pizarro, S. B. Williams, M. V. Jakuba, M. Johnson-Roberson, I. Mahon, M. Bryson, D. Steinberg, A. Friedman, D. Dansereau, N. Nourani-Vatani, D. Bongiorno, M. Bewley, A. Bender, N. Ashan, and B. Douillard, “Benthic monitoring with robotic platforms—the experience of Australia,” in IEEE International Underwater Technology Symposium (UT)(2013), pp. 1–10.
  10. A. Gleason, D. Lirman, D. Williams, N. Gracias, B. Gintert, H. Madjidi, R. Reid, G. Boynton, S. Negahdaripour, M. Miller, and P. Kramer, “Documenting hurricane impacts on coral reefs using two-dimensional video-mosaic technology,” Marine Ecol. 28, 254–258 (2007).
  11. O. Delaunoy, N. Gracias, and R. Garcia, “Towards detecting changes in underwater image sequences,” in OCEANS 2008-MTS/IEEE Techno-Ocean, Kobe, Japan (2008), pp. 1–8.
  12. M. Bryson, M. Johnson-Roberson, O. Pizarro, and S. Williams, “Automated registration for multi-year robotic surveys of marine benthic habitats,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan (2013).
  13. R. Prados, R. Garcia, J. Escartin, and L. Neumann, “Challenges of close-range underwater optical mapping,” in MTS/IEEE OCEANS Conference (2011), pp. 1–10.
  14. J. Ferrer, A. Elibol, O. Delaunoy, N. Gracias, and R. Garcia, “Large-area photo-mosaics using global alignment and navigation data,” in MTS/IEEE OCEANS Conference, Vancouver, Canada (2007), pp. 1–9.
  15. N. Gracias, S. Zwaan, A. Bernardino, and J. Santos-Victor, “Mosaic based navigation for autonomous underwater vehicles,” IEEE J. Ocean. Eng. 28, 609–624 (2003).
  16. H. Sawhney, S. Hsu, and R. Kumar, “Robust video mosaicing through topology inference and local to global alignment,” in European Conference on Computer Vision, Freiburg, Germany (1998), Vol. II, pp. 103–119.
  17. D. Gledhill, G. Tian, D. Taylor, and D. Clarke, “Panoramic imaging: a review,” Comput. Graph. 27, 435–445 (2003). [CrossRef]
  18. R. Szeliski, “Image alignment and stitching: a tutorial,” Found. Trends Comput. Graph. Vis. 2, 1–104 (2006).
  19. V. Ila, J. M. Porta, and J. Andrade-Cetto, “Information-based compact pose SLAM,” IEEE Trans. Robot. 26, 78–93 (2010).
  20. A. Cervantes and E. Y. Kang, “Progressive multi-image registration based on feature tracking,” in International Conference on Image Processing, Computer Vision, & Pattern Recognition, Las Vegas (2006), Vol. 2, pp. 633–639.
  21. H. Bulow and A. Birk, “Fast and robust photomapping with an unmanned aerial vehicle UAV,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (2009), pp. 3368–3373.
  22. F. Ferreira, G. Veruggio, M. Caccia, and G. Bruzzone, “Real-time optical SLAM-based mosaicking for unmanned underwater vehicles,” Intel. Serv. Robotics 5, 55–71 (2012).
  23. D. Steedly, C. Pal, and R. Szeliski, “Efficiently registering video into panoramic mosaics,” in Tenth IEEE International Conference on Computer Vision (ICCV) (2005), Vol. 2, pp. 1300–1307.
  24. M. Fadaeieslam, M. Fathy, and M. Soryani, “Key frames selection into panoramic mosaics,” in 7th International Conference on Information, Communications and Signal Processing (ICICS) (2009), pp. 1–5.
  25. Y. Li, C. Wu, S. Yu, and C. Tsuhan, “Motion-focusing key frame extraction and video summarization for lane surveillance system,” in 16th IEEE International Conference on Image Processing (ICIP) (2009), pp. 4329–4332.
  26. O. Mason and M. Verwoerd, “Graph theory and networks in biology,” IET Syst. Biol. 1, 89–119 (2007).
  27. N. Deo, Graph Theory with Applications to Engineering and Computer Science (PHI Learning, 2004).
  28. A. Balaban, Chemical Applications of Graph Theory (Academic, 1976).
  29. F. Roberts, Graph Theory and Its Applications to Problems of Society (SIAM, 1978), Vol. 29.
  30. J. Gross and J. Yellen, Graph Theory and Its Applications (Chapman & Hall/CRC Press, 2005).
  31. S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (Addison-Wesley, 1990).
  32. B. Cherkassky, A. Goldberg, and T. Radzik, “Shortest paths algorithms: theory and experimental evaluation,” Math. Program. 73, 129–174 (1996).
  33. A. Elibol, N. Gracias, R. Garcia, A. Gleason, B. Gintert, D. Lirman, and P. R. Reid, “Efficient autonomous image mosaicing with applications to coral reef monitoring,” in IROS 2011 Workshop on Robotics for Environmental Monitoring, San Francisco, CA (2011).
  34. D. Ribas, N. Palomeras, P. Ridao, M. Carreras, and E. Hernandez, “Ictineu AUV wins the first SAUC-E competition,” in IEEE International Conference on Robotics and Automation, Rome, Italy (2007).
  35. D. Lowe, “Distinctive image features from scale-invariant keypoints,” Int. J. Comput. Vis. 60, 91–110 (2004). [CrossRef]
  36. M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM 24, 381–395 (1981). [CrossRef]
  37. D. Lirman, N. Gracias, B. Gintert, A. Gleason, R. P. Reid, S. Negahdaripour, and P. Kramer, “Development and application of a video-mosaic survey technology to document the status of coral reef communities,” Environ. Monit. Assess. 125, 59–73 (2007). [CrossRef]
  38. N. Gracias and S. Negahdaripour, “Underwater mosaic creation using video sequences from different altitudes,” in MTS/IEEE OCEANS Conference, Washington, DC (2005), pp. 1234–1239.
  39. D. Ribas, N. Palomeras, P. Ridao, M. Carreras, and A. Mallios, “Girona 500 AUV: from survey to intervention,” IEEE/ASME Trans. Mechatron. 17, 46–53 (2012).
  40. B. Triggs, P. McLauchlan, R. Hartley, and A. Fitzgibbon, “Bundle adjustment: a modern synthesis,” in Vision Algorithms: Theory and Practice, B. Triggs, A. Zisserman, and R. Szeliski, eds. (Springer-Verlag, 2000), pp. 298–372.
  41. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. (Cambridge University, 2004).
  42. N. Gracias, J. P. Costeira, and J. S. Victor, “Linear global mosaics for underwater surveying,” in 5th IFAC Symposium on Intelligent Autonomous Vehicles, Lisbon, Portugal (2004), Vol. I.
  43. Z. Wang and A. Bovik, “A universal image quality index,” IEEE Signal Process. Lett. 9, 81–84 (2002). [CrossRef]
  44. A. Goldberg, “Point-to-point shortest path algorithms with preprocessing,” in SOFSEM 2007: Theory and Practice of Computer Science (2007), pp. 88–102.
  45. M. Fredman and R. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM 34, 596–615 (1987). [CrossRef]
  46. J. Nocedal and S. Wright, Numerical Optimization (Springer, 1999).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited