22 May 2014 Search algorithm complexity modeling with application to image alignment and matching
Author Affiliations +
Abstract
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
PROCEEDINGS
15 PAGES


SHARE
RELATED CONTENT

Hierarchical approach to feature indexing
Proceedings of SPIE (April 01 1992)
Matching shape descriptions of objects
Proceedings of SPIE (October 05 2001)
Cascade fuzzy ART a new extensible database for model...
Proceedings of SPIE (February 27 1996)
Adoption, impact, and vision of model-based design
Proceedings of SPIE (May 22 2006)

Back to Top