Parallel processing of image contours

Ling Tony Chen; Larry S. Davis; Clyde P. Kruskal

doi:10.1117/12.58056

1 April 1992 Parallel processing of image contours

Ling Tony Chen, Larry S. Davis, Clyde P. Kruskal

Proceedings Volume 1623, The 20th AIPR Workshop: Computer Vision Applications: Meeting the Challenges; (1992) https://doi.org/10.1117/12.58056
Event: The 20th AIPR Workshop, 1991, McLean, VA, United States

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.

Citation Download Citation

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

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Image processing

Image segmentation

Visibility

Algorithm development

Image processing algorithms and systems

Image analysis

Image understanding

Show All Keywords

Keywords/Phrases

Search In:

Publication Years