ML Anthology

The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments

W. Eric L. Grimson
ECCV 1990 pp. 552-556
doi:10.1007/BFB0014905 /eccv/1990/grimson1990eccv-combinatorics/

Abstract

Earlier work on using constrained search to locate objects in cluttered scenes showed that the expected search is quadratic in the number of features, if all the data comes from one object, but is exponential if spurious data is included. Consequently, many methods terminate search once a “good” interpretation is found. Here, we show that correct termination procedures can reduce the exponential search to quartic. This analysis agrees with empirical data for cluttered object recognition. These results imply that one must select subsets of the data likely to have come from one object, before finding a correspondence between data and model features.

PDF ECCV Semantic Scholar

Cite

Text

Grimson. "The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments." European Conference on Computer Vision, 1990. doi:10.1007/BFB0014905

Markdown

[Grimson. "The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments." European Conference on Computer Vision, 1990.](https://mlanthology.org/eccv/1990/grimson1990eccv-combinatorics/) doi:10.1007/BFB0014905

BibTeX

@inproceedings{grimson1990eccv-combinatorics,
  title     = {{The Combinatorics of Heuristic Search Termination for Object Recognition in Cluttered Environments}},
  author    = {Grimson, W. Eric L.},
  booktitle = {European Conference on Computer Vision},
  year      = {1990},
  pages     = {552-556},
  doi       = {10.1007/BFB0014905},
  url       = {https://mlanthology.org/eccv/1990/grimson1990eccv-combinatorics/}
}