Scalable data parallel object recognition using geometric hashing on CM-5

Abstract

In this paper, we present scalable parallel algorithms for object recognition using geometric hashing. We define an abstract model of CM-5. We develop a load-balancing technique that results in scalable processor-time optimal algorithms for performing a probe on the CM-5 model. Given a model of CM-5 with P PNs and a set S of feature points in a scene, a probe of the recognition phase can be performed in O(|V(S)|/P) time, where V(S) is the set of votes cast by feature points in S. This algorithm is scalable in the range 1≤P≤√|V(S)|/log|V(S)|. These results do not assume any distributions of hash bin lengths or scene points. The implementations developed in this paper require number of processors independent of the size of the model database and are scalable with the machine size.