### The combinatorics of local constraints in model-based recognition and localization from sparse dataThe combinatorics of local constraints in model-based recognition and localization from sparse data

Access Restriction
Subscribed

 Author Grimson, W. Eric L Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1986 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The problem of recognizing $\textit{what}$ objects are $\textit{where}$ in the workspace of a robot can be cast as one of searching for a consistent matching between sensory data elements and equivalent model elements. In principle, this search space is enormous, and to control the potential combinatorial explosion, constraints between the data and model elements are needed. A set of constraints for sparse sensory data that are applicable to a wide variety of sensors are derived, and their characteristics are examined. Known bounds on the complexity of constraint satisfaction problems are used, together with explicit estimates of the effectiveness of the constraints derived for the case of sparse, noisy, three-dimensional sensory data, to obtain general theoretical bounds on the number of interpretations expected to be consistent with the data. It is shown that these bounds are consistent with empirical results reported previously. The results are used to demonstrate the graceful degradation of the recognition technique with the presence of noise in the data, and to predict the number of data points needed, in general, to uniquely determine the object being sensed. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1986-08-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 33 Issue Number 4 Page Count 29 Starting Page 658 Ending Page 686

#### Open content in new tab

Source: ACM Digital Library