Search algorithm cost modeling offers search efficiency measures

Recognition applications often involve a search over a reference object model library. The search goal is to find a suitable match between the query and reference data to identify the query object. This straightforward library search paradigm works well in model-based object recognition applications such as computer vision, industrial robot vision, and automatic target recognition^1–3 because the set of objects to match are known a priori. A large reference library size often precludes exhaustive searching, thus necessitating efficient search algorithms to perform matching within a practical time period. Penetration rate modeling estimates the number of library searches required to find a match. Accurate penetration rate modeling is useful because it provides measures of the search algorithm efficiency.

Most prior approaches to penetration rate modeling used simple, overview statistical modeling. We derive a general, flexible statistical modeling framework⁴ to estimate penetration cost. It is applicable to a wide range of matching problems, including model-based object recognition, automatic target recognition, biometric matching, and image matching and alignment. We extend current approaches^5–7 to use more general probabilistic modeling assumptions, which provides more accurate modeling over a wider class of problems. We develop models for a tree-based hierarchy of classification objects under a two-step matching process. A classifier first chooses a bin (a reference database partition) in which a likely match exists. A matcher then searches over the chosen bin to find a match.

We proceed by modeling penetration cost as a random variable, and develop expressions for the joint probability of a set of probabilistic events under different modeling assumptions. These events are the bin selection, the true match existing in the selected bin, the mathematical matcher finding the match in the selected bin, and the penetration cost value. We develop models under both prioritized and non-prioritized classifier bin ranking. With the mathematical modeling machinery developed, we interpret and formulate an image alignment problem as a recognition problem and apply the penetration rate models to estimate search cost.

To verify the mathematical modeling, we generate numerical performance results for a logo image alignment and matching application. We define an alignment problem in which test exemplar logos from 12 logo classes are aligned to reference exemplar logos from the corresponding class. That is, exemplars from each class are naturally geometrically misaligned with respect to the corresponding class reference template. The alignment problem consists of determining the proper geometric transform that brings the exemplar into alignment with the reference. The search process determines the geometric transformation hypothesis that brings the test image into alignment with the reference image. We use the penetration cost model equations to estimate the number of searches required to find the alignment transform hypothesis.

For each alignment problem, we compare the estimated penetration cost value to the actual value obtained by performing the search and counting the number of search iterations performed. We use real-world logos and search over a two-parameter geometric transformation hypothesis space (see Figure 1) consisting of scale and rotation. Translation offsets are automatically estimated by the mathematical matcher. The matcher conducts the search using a two-level hierarchical grid search approach⁸ over the match score surface (see Figure 2). The match score surface is a function that gives the alignment match score, calculated by the mathematical matcher, as a function of the geometrical misalignment hypothesis parameters, in this case, scale and rotation. Match scores over a coarse grid are generated first. A higher-resolution search is then performed by the same process over neighboring areas of the nine highest coarse grid match scores. We use data from class 1, representing less than 40% of the available data, as training data to tune the model parameters.

Figure 1. Hierarchical grid partitioning of transform hypothesis space. The search space over rotation and scale is coarsely sampled. Coarse grid points (red circles) producing high match scores are more finely partitioned (blue circles) for subsequent search.

Figure 2. Typical match score surface (large match values signify high match likelihood).

The mean penetration cost results across image class are displayed in Figure 3. Results in Figure 3 show that the penetration estimation tracks the actual penetration cost value across the image class. Estimated and actual penetration cost data, aggregated across all classes, produces an estimated cost of approximately 16.0 versus an actual mean counted cost of 16.6. The results indicate that the penetration cost model accurately reflects actual penetration costs, thus validating the modeling assumptions and statistical formulation.

Figure 3. Mean penetration cost across class. The estimated penetration cost from the model is compared to the actual penetration cost for each image class.

We developed penetration rate models, and generated numerical results validating and justifying our modeling assumptions and formulation. Our modeling approach used sets of specific assumptions on bin search strategy, binning accuracy, distribution of true match within the hypothesis space, and other probabilistic assumptions. The modeling here is a general framework from which related approaches may be developed by modifying modeling assumptions. Alternative assumptions, either more stringent or more flexible, may be used to produce other penetration rate models for use in other problem domains.

Going forward, we plan to use alternative assumptions for penetration rate modeling. For example, bin search stopping rules (in which search over a bin is terminated when a desired criterion is met) may be used to trade off between search time and accuracy. Suspension of stopping rules incurs larger search times, but potentially gains more accurate matching performance.