9 April 1993 Constant-time digital geometry algorithms on the scan model of parallel computation
Author Affiliations +
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
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.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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); doi: 10.1117/12.142166; https://doi.org/10.1117/12.142166

Back to Top