On a Parallel Implementation of Geometric Hashing on the Connection Machine

Productinformatie

Excerpt from On a Parallel Implementation of Geometric Hashing on the Connection Machine: Technical Report 554
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 64K-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 O(log M + log S log M) in 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, 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 provide information about detection and false alarm rates for varying amounts of noise in the input.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works."