MBS 94-11
Recognition Polynomials Reduce the Complexity of Matching in Object Recognition
Marc K. Albert, Donald D. Hoffman, Manish Singh

---

This paper introduces a polynomial pruning method (PPM) to deal with one aspect of the problem of object recognition, viz., the matching of model features with image features in order to identify objects in cluttered environments. Previous work has shown that, if there are spurious image features or if the indexing process provides candidate models that are not, in fact, present in the scene, then the expected amount of search is exponential in the problem parameters. We present a computationally simple method, using recognition polynomials, that reduces this search to a low degree polynomial - in many cases of degree four and, in the worst case, of degree eight.