On a Parallel Implementation of Geometric Hashing on the Connection Machine
Abstract
We report on a scalable parallel implementation of geometric hashing on a Connection Machine. The algorithm that is employed has been described in [9]. Using the resulting implementation, it is possible to recognize models consisting of patterns of points embedded in scenes, independent of translation, rotation, and scale changes, when there are thousands of models containing approximately 16 points each, with scenes consisting of hundreds of points, where most of the scene points are spurious noise points, and where embedded model points in the scene may be obscured or misplaced. With 1024 models and a scene of 200 points, the implementation yields an execution time of 70 milliseconds per probe on a 641(-processor CM-2 parallel computer. Most of the execution time is taken in performing histograms of (model, basis-set) records. The algorithm is scalable, yielding an expected execution time that is Omicron (log2 M +logS logM) on a Mn3-processor hypercube-connected SIMD machine such as the Connection Machine. M is the number of models, n is the number of points per model, and S is the number of scene points. We also describe and report on a series of experiments for both the similarity and rigid transformation cases; these experiments provideinformation about detection and false alarm rates for varying amounts of noise in the input.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1991
- Accession Number
- AD1020187
Entities
People
- Isidore Rigoutsos
- Robert Hummel
Organizations
- New York University