Massively Parallel Bayesian Object Recognition

10:00 a.m., Friday, August 21, 1992
12th floor conference rm., 719 Broadway

The problem of model-based object recognition is a fundamental one in the field of computer vision, and represents a promising direction for practical applications. In this talk we will describe the design, analysis, implementation and testing of a model-based object recognition system.

In the first part of the talk, we will discuss two parallel algorithms for performing geometric hashing. The first algorithm regards geometric hashing as a connectionist algorithm with information flowing via patterns of communication, and is designed for an SIMD hypercube-based machine. The second algorithm is more general, and treats the parallel architecture as a source of ``intelligent memory;'' the algorithm achieves parallelism through broadcast facilities from the parallel machine's host. A number of enhancements to the geometric hashing method, such as hash table equalization, the use of hash table symmetries, and hash table foldings will also be presented. These enhancements were developed specifically for the parallel algorithms, and lead to substantial performance improvements.

In the second part of the talk, we will examine the performance of geometric hashing methods in the presence of noise. The quantization of the invariants can result in a non-graceful degradation of the performance. We will present precise formulas as well as first-order approximations describing the dependency of the computed invariants on Gaussian positional error, for the similarity and affine transformation cases. Knowledge of this dependency allows the incorporation of an error model in the geometric hashing framework and subsequently leads to improved performance. A counter-intuitive result regarding the solutions of certain linear systems will also be derived as a corollary of this analysis.

In the final part of the talk, we will present an interpretation of geometric hashing that allows the algorithm to be viewed as a Bayesian approach to model-based object recognition. This interpretation, which is a new form of Bayesian-based model matching, leads to well-justified formulas, and gives a precise weighted-voting method for the evidence-gathering phase of geometric hashing. These formulas replace traditional heuristically-derived methods for performing weighted voting, and also provide a precise method for evaluating uncertainty.

A prototype object recognition system using these ideas has been implemented on a CM-2 Connection Machine. The system is scalable and can recognize aircraft and automobile models subjected to 2D rotation, translation, and scale changes in real-world digital imagery. This is the first system of its kind that is scalable, uses large databases, can handle noisy input data, works rapidly on an existing parallel architecture, and exhibits excellent performance with real-world, natural scenes.