首页 | 本学科首页   官方微博 | 高级检索  
     


Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays
Authors:Hussein M. Alnuweiri and V. K. Prasanna Kumar
Affiliation:(1) EEB-244, Department of Electrical Engineering Systems, University of Southern California, 90089-2562 Los Angeles, CA, USA
Abstract:
We present processor-time optimal parallel algorithms for several problems onn ×n digitized image arrays, on a mesh-connected array havingp processors and a memory of sizeO(n2) words. The number of processorsp can vary over the range [1,n3/2] while providing optimal speedup for these problems. The class of image problems considered here includes labeling the connected components of an image; computing the convex hull, the diameter, and a smallest enclosing box of each component; and computing all closest neighbors. Such problems arise in medium-level vision and require global operations on image pixels. To achieve optimal performance, several efficient data-movement and reduction techniques are developed for the proposed organization.This research was supported in part by the National Science Foundation under Grant IRI-8710836 and in part by DARPA under Contract F33615-87-C-1436 monitored by the Wright Patterson Airforce Base.
Keywords:Digitized image problems  Parallel algorithms  Processor-time tradeoffs  Mesh arrays
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号