Geometric Algorithms for Digitized Pictures on a Mesh-Connected Computer

Russ Miller
Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan


Abstract: Although mesh-connected computers are used almost exclusively for low-level local image processing, they are also suitable for higher level image processing tasks. We illustrate this by presenting optimal algorithms for computing several geometric properties of figures. Given a black/white picture, a component is a connected region of black pixels. If the image is stored one pixel per processing element in an n x n mesh-connected computer, we give Θ(n) time algorithms for

Previous mesh-connected computer algorithms for these problems were either nonexistent or had worst-case times of Θ(n2).

Keywords: mesh computer, array processor, computational geometry, convexity, digitized images, digital geometry, minimal paths, nearest neighbors, diameter, farthest points, divide-and-conquer, parallel computing, parallel algorithms, computer science

Complete paper. This paper appears in IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 7 (1985), pp. 216-228.


Related Work

Quentin's Home Copyright © 2005-2018 Quentin F. Stout