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

Author

Prasanna, Viktor K. ; Wang, Cho-Li

Author_Institution

Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA

fYear

1994

fDate

23-25 May 1994

Firstpage

817

Lastpage

824

Abstract

Presents scalable parallel algorithms for object recognition using geometric hashing. We define an abstract model of the CM-5 computer. 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 a CM-5 with P processor nodes 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 a number of processors which is independent of the size of the model database and which is scalable with the machine size

Keywords

computational complexity; computational geometry; computer vision; feature extraction; file organisation; image recognition; parallel algorithms; parallel machines; resource allocation; Connection Machine CM-5; abstract computer model; feature points; geometric hashing; hash bin length; load balancing technique; machine size; model database; model probe; object recognition; processor nodes; processor-time optimal algorithms; scalable data-parallel algorithms; scene points; voting; Layout; Machine vision; Object recognition; Parallel algorithms; Performance analysis; Predictive models; Probes; Solid modeling; Spatial databases; Voting;

fLanguage

English

Publisher

ieee

Conference_Titel

Scalable High-Performance Computing Conference, 1994., Proceedings of the

Conference_Location

Knoxville, TN

Print_ISBN

0-8186-5680-8

Type

conf

DOI

10.1109/SHPCC.1994.296725

Filename

296725