Translator Disclaimer
1 April 1992 Parallel processing of image contours
Author Affiliations +
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.
© (1992) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Ling Tony Chen, Larry S. Davis, and Clyde P. Kruskal "Parallel processing of image contours", Proc. SPIE 1623, The 20th AIPR Workshop: Computer Vision Applications: Meeting the Challenges, (1 April 1992); https://doi.org/10.1117/12.58056
PROCEEDINGS
12 PAGES


SHARE
Advertisement
Advertisement
RELATED CONTENT

Flexible automatic algorithm for comet assay analysis
Proceedings of SPIE (December 21 2018)
Feature-based image analysis of zebrafish embryonic images
Proceedings of SPIE (October 30 2009)
Tiling Strategies For Image Parallelism
Proceedings of SPIE (March 29 1989)
Automated object detection for astronomical images
Proceedings of SPIE (October 24 2005)
Image analysis of multiple moving wood pieces in real time
Proceedings of SPIE (February 15 2006)

Back to Top