caa a22 4500 469036230 CHVBK 20180323132756.0 cr unu---uuuuu 170328e19920401xx s 000 0 eng 10.1007/BF00126393 doi (NATIONALLICENCE)springer-10.1007/BF00126393 The cost of choosing the wrong model in object recognition by constrained search [Elektronische Daten] [W. Eric, L. Grimson] Many current recognition systems use variations on constrained tree search to locate objects in cluttered environments. If the system is simply finding instances of an object known to be in the scene, then previous formal analysis has shown that the expected amount of search is quadratic in the number of model and data features when all the data is known to come from a single object, but is exponential when spurious data is included. If one can group the data into subsets likely to have come from a single object, then terminating the search once a "good enough” interpretation is found reduces the expected search to cubic. Without successful grouping, terminated search is still exponential. These results apply to finding instances of a known object in the data. What happens when the object is not present? In this article, we turn to the problem of selecting models from a library, and examine the combinatorial cost of determining that an incorrectly chosen candidate object is not present in the data. We show that the expected search is again exponential, implying that naive approaches to library indexing are likely to carry an expensive overhead, since an exponential amount of work is needed to weed out each incorrect model. The analytic results are shown to be in agreement with empirical data for cluttered object recognition. Kluwer Academic Publishers, 1992 Eric W. MIT Artificial Intelligence Laboratory, 545 Technology Square, 02139, Cambridge, MA aut Grimson L. MIT Artificial Intelligence Laboratory, 545 Technology Square, 02139, Cambridge, MA aut International Journal of Computer Vision Kluwer Academic Publishers 7/3(1992-04-01), 195-210 0920-5691 7:3<195 1992 7 11263 https://doi.org/10.1007/BF00126393 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00126393 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Eric W. MIT Artificial Intelligence Laboratory, 545 Technology Square, 02139, Cambridge, MA aut NATIONALLICENCE 700 1- Grimson L. MIT Artificial Intelligence Laboratory, 545 Technology Square, 02139, Cambridge, MA aut NATIONALLICENCE 773 0- International Journal of Computer Vision Kluwer Academic Publishers 7/3(1992-04-01), 195-210 0920-5691 7:3<195 1992 7 11263 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer