Share Email Print

Proceedings Paper

Parallel processing of image contours
Author(s): Ling Tony Chen; Larry S. Davis; Clyde P. Kruskal
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

This paper describes a parallel algorithm for ranking the pixels on a curve in O(log N) time using an EREW PRAM model. The algorithms accomplish this with N processors for a (root)N X (root)N image. After applying such an algorithm to an image, we are able to move the pixels from a curve into processors having consecutive addresses. This is important on hypercube connected machines like the Connection Machine because we can subsequently apply many algorithms to the curve using powerful segmented scan operations (i.e., parallel prefix operations). We shall illustrate this by first showing how we can find piecewise linear approximations of curves using Ramer's algorithm. This process has the effect of converting closed curves into simple polygons. As another example, we shall describe a more complicated parallel algorithm for computing the visibility graph of a simple planar polygon. The algorithm accomplishes this in O(k log N) time using O(N2/log N) processors for an N vertex polygon, where k is the link-diameter of the polygon in consideration. Both of these algorithms require only scan operations (as well as local neighbor communication) as the means of inter-processor communication. Thus, the algorithms can not only be implemented on an EREW PRAM, but also on a hypercube connected parallel machine, which is a more practical machine model. All these algorithms were implemented on the Connection Machine, and various performance tests were conducted.

Paper Details

Date Published: 1 April 1992
PDF: 12 pages
Proc. SPIE 1623, The 20th AIPR Workshop: Computer Vision Applications: Meeting the Challenges, (1 April 1992); doi: 10.1117/12.58056
Show Author Affiliations
Ling Tony Chen, Univ. of Maryland (United States)
Larry S. Davis, Univ. of Maryland (United States)
Clyde P. Kruskal, Univ. of Maryland (United States)

Published in SPIE Proceedings Vol. 1623:
The 20th AIPR Workshop: Computer Vision Applications: Meeting the Challenges

© SPIE. Terms of Use
Back to Top