Abstract

We present a scheme for macropipelining an L-stage image-analysis algorithm into a message-passing Ns-processor multicomputer system in which Ns > L. The resulting architectures achieve high speeds in processing multiple images. Most image-processing applications consist of a sequence of tasks, e.g., preprocessing, detection, segmentation, feature extraction, and classification. This sequence lends itself to an assignment of the tasks to a series-connected set of processors, or pipelining of the tasks. We refer to this form of pipelining as macropipelining. To minimize the effects of throughput-limiting tasks, or bottlenecks, in this pipeline, we introduce a performance model that accounts for both the computation aspects and the communication aspects of parallel processing. With the help of this model, we assign the appropriate number of processors to each task so as to balance the workloads. We then generate a problem graph describing the relationships among the tasks. We use an estimator of the frame-time of the image-processing system as an objective function for choosing a mapping of the problem processing graph into a system graph. This estimator takes account of computation times and communication intensities the tasks in the problem graph, and it accounts for link contentions. To find an efficient mapping, we use a among heuristic optimization in which possible bottlenecks are given high priority in the mapping procedure. We tested our macropipelining scheme on a target-recognition algorithm in a simulated hypercube computer system. The results support our belief that this scheme yields effective architectures for high-speed processing of long sequences of images.

© 1989 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Focal-plane processing architectures for real-time hyperspectral image processing

Sek M. Chai, Antonio Gentile, Wilfredo E. Lugo-Beauchamp, Javier Fonseca, José L. Cruz-Rivera, and D. Scott Wills
Appl. Opt. 39(5) 835-849 (2000)

Three-dimensional image analysis and display by space-scale matching of cross sections

V. R. Algazi, B. W. Reutter, W. L. G. van Warmerdam, and C. C. Liu
J. Opt. Soc. Am. A 6(6) 890-899 (1989)

Image algebra representation of parallel optical binary arithmetic

Kung-Shiuh Huang, B. Keith Jenkins, and Alexander A. Sawchuk
Appl. Opt. 28(6) 1263-1278 (1989)

References

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Figures (12)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Tables (6)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Equations (23)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Metrics

You do not have subscription access to this journal. Article level metrics are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription