22 May 2014 Search algorithm complexity modeling with application to image alignment and matching
Author Affiliations +
Search algorithm complexity modeling, in the form of penetration rate estimation, provides a useful way to estimate search efficiency in application domains which involve searching over a hypothesis space of reference templates or models, as in model-based object recognition, automatic target recognition, and biometric recognition. The penetration rate quantifies the expected portion of the database that must be searched, and is useful for estimating search algorithm computational requirements. In this paper we perform mathematical modeling to derive general equations for penetration rate estimates that are applicable to a wide range of recognition problems. We extend previous penetration rate analyses to use more general probabilistic modeling assumptions. In particular we provide penetration rate equations within the framework of a model-based image alignment application domain in which a prioritized hierarchical grid search is used to rank subspace bins based on matching probability. We derive general equations, and provide special cases based on simplifying assumptions. We show how previously-derived penetration rate equations are special cases of the general formulation. We apply the analysis to model-based logo image alignment in which a hierarchical grid search is used over a geometric misalignment transform hypothesis space. We present numerical results validating the modeling assumptions and derived formulation.
© (2014) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Stephen DelMarco, Stephen DelMarco, "Search algorithm complexity modeling with application to image alignment and matching", Proc. SPIE 9120, Mobile Multimedia/Image Processing, Security, and Applications 2014, 91200C (22 May 2014); doi: 10.1117/12.2049605; https://doi.org/10.1117/12.2049605


Hierarchical approach to feature indexing
Proceedings of SPIE (March 31 1992)
Depth aspect images for robust object recognition
Proceedings of SPIE (September 29 2003)
Geometric hashing and object recognition
Proceedings of SPIE (September 22 1999)
Performance modeling of vote-based object recognition
Proceedings of SPIE (August 19 2003)

Back to Top