Exploiting World Structure to Efficiently Search for Objects
Lambert E. Wixson · 1992
This paper studies the task of using a mobile camera platform to search a region of space for a target object. Our goal is to maximize the efficiency of such searches. The problem is analyzed using a simple mathematical description of the factors that affect search efficiency. This analysis suggests that one way to improve efficiency is to take advantage of the spatial relationships in which the target object commonly participates. Searches that do so, which we call indirect searches, are modeled as two-stage processes that first find an intermediate object that commonly participates in a spatial relationship for the target object, and then look for the target in the restricted region specified by this relationship. A mathematical model of search efficiency is then used to analyze the efficiency of indirect search over a wide range of situations that vary the spatial structure of the domain as well as recognition performance. The model predicts that, for searches that involve rotating a camera about a fixed location, indirect searches improve efficiency by factors of 2 to 8. An implemented robot search system substantiates these predictions. Finally, we highlight some areas in need of further research if these efficiencies are to be achieved.