Share Email Print

Proceedings Paper

Search algorithm complexity modeling with application to image alignment and matching
Author(s): Stephen DelMarco
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 22 May 2014
PDF: 15 pages
Proc. SPIE 9120, Mobile Multimedia/Image Processing, Security, and Applications 2014, 91200C (22 May 2014); doi: 10.1117/12.2049605
Show Author Affiliations
Stephen DelMarco, BAE Systems (United States)

Published in SPIE Proceedings Vol. 9120:
Mobile Multimedia/Image Processing, Security, and Applications 2014
Sos S. Agaian; Sabah A. Jassim; Eliza Yingzi Du, Editor(s)

© SPIE. Terms of Use
Back to Top