[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

The problem of finding the optimal correspondence between two sets of geometric entities or features is known to be NP-hard in the worst case. This problem appears in many real scenarios such as fingerprint comparisons, image matching and global localization of mobile robots. The inherent complexity of the problem can be avoided by suboptimal solutions, but these could fail with high noise or corrupted data. The correspondence problem has an interesting equivalent formulation in finding a maximum clique in an association graph. We have developed a novel algorithm to solve the correspondence problem between two sets of features based on an efficient solution to the Maximum Clique Problem using bit parallelism. It outperforms an equivalent non bit parallel algorithm in a number of experiments with simulated and real data from two different correspondence problems. This article validates for the first time, to the best of our knowledge, that bit parallel optimization techniques can greatly reduce computational cost, thus making feasible the use of an exact solution in real correspondence search problems despite their inherent NP computational complexity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Dominguez S, Campoy P, Baeza C (2000) On automated trademark search techniques. In: Pattern recognition and applications. IOS Press, Amsterdam, pp 126–133

    Google Scholar 

  2. Hogg DW, Blanton M, Lang D, Mierle K, Roweis S (2008) Automated astrometry. In: Argyle RW, Bunclark PS, Lewis JR (eds) Astronimical data analysis software and systems XVII. ASP conference series, vol 394, pp 27–34

  3. Ballard DH, Brown M (1982) Computer vision. Prentice-Hall, New York

    Google Scholar 

  4. Betke M, Gurvits L (1997) Mobile robot localization using landmarks. IEEE Trans Robot Autom 13(2):251–263

    Article  Google Scholar 

  5. Neira J, Tardós JD, Castellanos JA (2003) Linear time vehicle relocation in SLAM. In: IEEE int conf robotics and automation, Taipei, Taiwan, May 2003

  6. Paz LM, Piníes P, Neira J, Tardós JD (2005) Global localization in SLAM in bilinear time. In: IEE/RSJ int conf on intelligent robots and systems, Edmonton, Canada, 2–6 August 2005

  7. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York

    MATH  Google Scholar 

  8. Bunke H, Kandel A (2000) Mean and maximum common subgraph of two graphs. Pattern Recogn Lett 21(2):163–168

    Article  Google Scholar 

  9. Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) Handbook of combinatorial optimization, supplement vol A. Kluwer Academic, Dordrecht, pp 1–74

    Google Scholar 

  10. Tomita E, Kameda T (2006) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J Glob Optim 37:95–111

    Article  MathSciNet  Google Scholar 

  11. San Segundo P, Galán R, Rodríguez-Losada D (2006) Efficient search using bitboard models. In: Proceedings XVIII int joint conf on tools with AI (ICTAI’06), pp 132–138

  12. San Segundo P, Rodriguez-Losada D, Galán R, Matía F, Jiménez A (2007) Exploiting CPU bit parallel operations to improve efficiency in search. In: Proceedings XIX int joint conf on tools with AI (ICTAI’07), Greece, pp 53–59

  13. San Segundo P, Galán R (2005) Bitboards, a new approach. In: Proceedings artificial intelligence and applications, AIA-2005, IASTED, Austria, pp 394–399

  14. Heinz EA (1997) How DarkThought plays chess. ICCA J 20(3):166–176

    Google Scholar 

  15. Ambler AP, Barrow HG, Brown CM, Burstall RM, Popplesotne RJ (1973) A versatile computer-controlled assembly system. In: Proc III int joint conf on art intelligence, pp 298–307

  16. Warren HS Jr (2002) Hacker’s delight. Addison-Wesley, Reading

    Google Scholar 

  17. Pardalos PM, Xue J (1994) The maximum clique problem. J Glob Optim 4:301–328

    Article  MATH  MathSciNet  Google Scholar 

  18. Pardalos PM, Rodgers GP (1992) A branch and bound algorithm for the maximum clique problem. Comput Oper Res 19(5):363–375

    Article  MATH  Google Scholar 

  19. Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375–382

    Article  MATH  Google Scholar 

  20. Rodriguez-Losada D, Matia F, Galan R (2006) Building geometric feature based maps for indoor service robots. Robot Auton Syst 54(7):546–558

    Article  Google Scholar 

  21. Rosten E, Drummond T (2005) Fusing points and lines for high performance tracking. In: IEEE international conference on computer vision, vol 2, Oct 2005, pp 1508–1511

  22. Rosten E, Drummond T (2006) Machine learning for high-speed corner detection. In: European conference on computer vision

  23. Thrun S (2002) Robotic mapping: a survey. In: Lakemeyer G, Nebel B (eds) Exploring artificial intelligence in the new millennium. Morgan Kaufmann, San Mateo

    Google Scholar 

  24. Rodriguez-Losada D, Matia F, Jimenez A, Galan R (2006) Local map fusion for real-time indoor simultaneous localization and mapping. J Field Robot 23(5):291–309

    Article  MATH  Google Scholar 

  25. Rodriguez-Losada D, Matia F, Pedraza L, Jimenez A, Galan R (2007) Consistency of SLAM-EKF algorithms for indoor environments. J Intell Robot Syst 50(4):375–397

    Article  MATH  Google Scholar 

  26. Neira J, Tardos JD (2001) Data association in stochastic mapping using the joint compatibility test. IEEE Trans Robot Autom 176:890–897

    Article  Google Scholar 

  27. Bailey T (2002) Mobile robot localisation and mapping in extensive outdoor environments. PhD thesis, Australian Centre for Field Robotics, University of Sydney

Download references

Author information

Authors and Affiliations

  1. Intelligent Control Group, Universidad Politécnica de Madrid, UPM, C/ Jose Gutiérrez Abascal, 2, 28006, Madrid, Spain

    Pablo San Segundo, Diego Rodríguez-Losada, Fernando Matía & Ramón Galán

Authors
  1. Pablo San Segundo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diego Rodríguez-Losada
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fernando Matía
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ramón Galán
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo San Segundo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

San Segundo, P., Rodríguez-Losada, D., Matía, F. et al. Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver. Appl Intell 32, 311–329 (2010). https://doi.org/10.1007/s10489-008-0147-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-008-0147-6

Keywords

Search

Navigation