Complete indexing strategies for sparse sensing techniques

Modeled objects are usually recognized and localized by enumerating interpretations of the sensed data in terms of model features, and then validating each hypothesized interpretation by computing the optimal pose estimate and associated error. The task of enumerating hypothetical interpretations is termed the correspondence problem. Indexing is a general approach for solving the correspondence problem in which coordinates are distilled from the sensed data, and then these indexing coordinates are quantized to index a table entry containing the corresponding interpretations. Indexing tables are central to indexing techniques; if the table is complete, i.e., it contains an entry for every valid combination of indexing coordinates and interpretations, then the indexing strategy is correct. For sparse sensing strategies, where each experiment only provides a few measurements, indexing table completeness is critical. The task of constructing complete indexing tables has previously been an open problem. In this paper, we describe a method for constructing complete indexing tables which involves enumerating cells in an arrangement in configuration space.