Share Email Print

Proceedings Paper

Constant-time digital geometry algorithms on the scan model of parallel computation
Author(s): Borivoje Djokic; Ivan Stojmenovic
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Assume that a black/white n X n image is stored one per element of a vector of length n2. We consider determining some characteristics of such images using the scan model of parallel computation. The scan model is introduced by G.E. Blelloch and is a single instruction multiple data (SIMD) vector model of computation. The primitive operation of the model work on vectors (one dimensional arrays) of values, with three types of primitive operations: elementwise arithmetic and logical operations, permutation operation, and scan operation, a type of prefix computation (a scan operation takes a binary associative operator (direct product) and a vector [a1, ..., an] and returns the vector [a1, a1(direct product)a2, ..., a1(direct product)a2(direct product) ... (direct product)an]). We show that many important characteristics of binary images can be determined in constant time on the scan model of parallel computation. These include the convex hull construction, diameter, width, smallest enclosing box, perimeter, area, detecting digital convexity, parallel and point visibility (determining for each pixel of the image the portion that is visible, i.e. not obstructed by any black pixel, in given direction from infinity or from given point, respectively) of an image, smallest, largest and Hausdorff distances between two images, linear separability of two images, and the recognition of digital lines, rectangles and arcs.

Paper Details

Date Published: 9 April 1993
PDF: 9 pages
Proc. SPIE 1832, Vision Geometry, (9 April 1993); doi: 10.1117/12.142166
Show Author Affiliations
Borivoje Djokic, Univ. of Miami (United States)
Ivan Stojmenovic, Univ. of Ottawa (Canada)

Published in SPIE Proceedings Vol. 1832:
Vision Geometry
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top