Fast parallel object recognition

The problem of model-based object recognition is one of identifying occurrences of objects known a priori in an image. Not all the existing algorithms lend themselves well to parallel implementations. In this paper, we describe a new formulation of the recognition problem that is amenable to a naturally parallel solution. The method that we describe solves the bounded error recognition problem accurately by incorporating an explicit noise model. The time complexity of the sequential matching algorithm using point features is of the order O(I²NI), where N is the number of model features and I is the number of image features. The corresponding parallel algorithm using O(I²) processors has O(NI) complexity. When line features are used, the sequential complexity is of the order O(I² N) and the parallel algorithm, utilizing O(I) processors has O(NI) complexity. Results are presented for a sequential version running on a Sun as well as a parallel version running on a 1024-processor MasPar MP-1