Search algorithm complexity modeling with application to image alignment and matching

Stephen DelMarco

doi:10.1117/12.2049605

22 May 2014 Search algorithm complexity modeling with application to image alignment and matching

Stephen DelMarco

Proceedings Volume 9120, Mobile Multimedia/Image Processing, Security, and Applications 2014; 91200C (2014) https://doi.org/10.1117/12.2049605
Event: SPIE Sensing Technology + Applications, 2014, Baltimore, MD, United States

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.

Citation Download Citation

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); https://doi.org/10.1117/12.2049605

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available