Scalable data parallel implementations of object recognition on connection machine CM-5

Abstract

Object recognition involves identifying known objects in a given scene. It plays a key role in image understanding, a Grand Challenge problem. Geometric hashing has been recently proposed as a technique for model based object recognition in occluded scenes. In this paper, we present scalable data parallel algorithms for geometric hashing on Connection Machine CM-5. Given a scene consisting of S feature points, the parallel algorithm for one probe of the recognition-phase takes O(S/P log S) time on a fat tree based architecture. We perform implementations of the proposed algorithms on CM-5, after a careful study of its computation and communication characteristics. Earlier parallel implementations of the geometric hashing algorithm have been carried out on the Connection Machine CM-2 using O(Mn3) processors, where M is the number of models in the database and n is the number of features in each model. In these implementations, the number of processors is independent of the size of the scene but depends on the size of model database which is usually very large. The algorithms presented in this paper significantly improve on the number of processors employed while at the same time achieve much superior time performance. Earlier implementations claim 700 to 1300 msec for one probe of the recognition phase, assuming 200 feature points in the scene on an 8 K processor CM-2. Our implementations run on a P processor Connection Machine CM-5, such that 1≤P≤S. Our results show that a probe of the recognition phase for a scene consisting of 1024 feature points takes less than 10 msec on a 256 processor CM-5. The implementations developed in this paper require number of processors independent of the size of the model database and are also scalable with the machine size.