Implementation of geometric hashing on the Connection Machine

The authors report on a scalable implementation of geometric hashing on the Connection Machine. Using this implementation, it is possible to recognize models consisting of patterns of points embedded in scenes, independent of translation, rotation, and scale changes. With 1024 models and a scene of 200 points, the implementation yields an execution time of 70 milliseconds for recognition of the one embedded model given a two-point basis set (consisting of a pair of points in the model) on a 64 K-processor CM-2 parallel computer. The algorithm is scalable, yielding an expected execution time that is 𝒪(log² M+log S log M) on a Mn³ -processor hypercube-connected SIMD machine such as the Connection Machine; M is the number of models, n is the number of points per model, S is the number of scene points, and it is assumed that execution proceeds until the first model is discovered