Constant-time digital geometry algorithms on the scan model of parallel computation

Borivoje Djokic; Ivan Stojmenovic

doi:10.1117/12.142166

9 April 1993 Constant-time digital geometry algorithms on the scan model of parallel computation

Borivoje Djokic, Ivan Stojmenovic

Proceedings Volume 1832, Vision Geometry; (1993) https://doi.org/10.1117/12.142166
Event: Applications in Optical Science and Engineering, 1992, Boston, MA, United States

Abstract

Assume that a black/white n X n image is stored one per element of a vector of length n². 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 [a₁, ..., a_n] and returns the vector [a₁, a₁(direct product)a₂, ..., a₁(direct product)a₂(direct product) ... (direct product)a_n]). 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.

Citation Download Citation

Borivoje Djokic and Ivan Stojmenovic "Constant-time digital geometry algorithms on the scan model of parallel computation", Proc. SPIE 1832, Vision Geometry, (9 April 1993); https://doi.org/10.1117/12.142166

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