File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Scalable Data-Parallel Implementations of Object Recognition Using Geometric Hashing

TitleScalable Data-Parallel Implementations of Object Recognition Using Geometric Hashing
Authors
Issue Date1994
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdc
Citation
Journal Of Parallel And Distributed Computing, 1994, v. 21 n. 1, p. 96-109 How to Cite?
AbstractObject recognition involves identifying known objects in a given scene. It plays a key role in image understanding. Geometric hashing has been proposed as a technique for model-based object recognition in occluded scenes. However, parallel techniques are needed to realize real time vision systems employing geometric hashing. In this paper, we present scalable parallel algorithms for object recognition using geometric hashing. We define a realistic abstract model of CM-5 in which explicit cost is associated with data routing and synchronization. We develop a load-balancing technique that results in scalable processor-time optimal algorithms for performing a probe on this 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)| 1 3. On a mesh processor array of any size [formula] × [formula] which models MP-1, we show that a probe can be performed on O(|V(S)|/[formula]) time, log2|V(S)| ≤ P ≤ |V(S)|. These results do not assume any distributions of hash bin lengths or scene points. In earlier parallel implementations, the number of processors employed was independent of the size of the scene but depended on the size of the model database (which is usually very large). Our implementations on CM-5 and MP-1 significantly improve upon the number of processors employed and also result in superior time performance. The implementations developed in this paper require a number of processors that are independent of the size of the model database and are scalable with the machine size. Results of concurrent processing of multiple probes are also reported. © 1994 Academic Press. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152197
ISSN
2015 Impact Factor: 1.32
2015 SCImago Journal Rankings: 0.851
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorWang, CLen_US
dc.contributor.authorPrasanna, VKen_US
dc.contributor.authorKim, HJen_US
dc.contributor.authorKhokhar, AAen_US
dc.date.accessioned2012-06-26T06:36:27Z-
dc.date.available2012-06-26T06:36:27Z-
dc.date.issued1994en_US
dc.identifier.citationJournal Of Parallel And Distributed Computing, 1994, v. 21 n. 1, p. 96-109en_US
dc.identifier.issn0743-7315en_US
dc.identifier.urihttp://hdl.handle.net/10722/152197-
dc.description.abstractObject recognition involves identifying known objects in a given scene. It plays a key role in image understanding. Geometric hashing has been proposed as a technique for model-based object recognition in occluded scenes. However, parallel techniques are needed to realize real time vision systems employing geometric hashing. In this paper, we present scalable parallel algorithms for object recognition using geometric hashing. We define a realistic abstract model of CM-5 in which explicit cost is associated with data routing and synchronization. We develop a load-balancing technique that results in scalable processor-time optimal algorithms for performing a probe on this 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)| 1 3. On a mesh processor array of any size [formula] × [formula] which models MP-1, we show that a probe can be performed on O(|V(S)|/[formula]) time, log2|V(S)| ≤ P ≤ |V(S)|. These results do not assume any distributions of hash bin lengths or scene points. In earlier parallel implementations, the number of processors employed was independent of the size of the scene but depended on the size of the model database (which is usually very large). Our implementations on CM-5 and MP-1 significantly improve upon the number of processors employed and also result in superior time performance. The implementations developed in this paper require a number of processors that are independent of the size of the model database and are scalable with the machine size. Results of concurrent processing of multiple probes are also reported. © 1994 Academic Press. All rights reserved.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdcen_US
dc.relation.ispartofJournal of Parallel and Distributed Computingen_US
dc.titleScalable Data-Parallel Implementations of Object Recognition Using Geometric Hashingen_US
dc.typeArticleen_US
dc.identifier.emailWang, CL:clwang@cs.hku.hken_US
dc.identifier.authorityWang, CL=rp00183en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1006/jpdc.1994.1044en_US
dc.identifier.scopuseid_2-s2.0-0011010877en_US
dc.identifier.volume21en_US
dc.identifier.issue1en_US
dc.identifier.spage96en_US
dc.identifier.epage109en_US
dc.identifier.isiWOS:A1994NH27900008-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridWang, CL=7501646188en_US
dc.identifier.scopusauthoridPrasanna, VK=7005057102en_US
dc.identifier.scopusauthoridKim, HJ=36065362900en_US
dc.identifier.scopusauthoridKhokhar, AA=7004753270en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats