Russ Miller
Dept. of Computer Science, State University of New York at Buffalo
Quentin F. Stout
Computer Science and Engineering, University of Michigan
Abstract: Efficient parallel algorithms are presented for using a pyramid computer (a parallel computer connected in a specific, pyramidal pattern) to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base of n simple processing elements arranged in an n1/2 x n1/2 square, the running times of the algorithms range from Θ(log n) to find the extreme points of a convex figure in a digitized picture, to Θ(n1/6) to find the diameter of a labeled figure, to Θ(n1/4 log n) to find the extreme points of every figure in a digitized picture, to Θ(n1/2) to find the extreme points of every labeled set of processing elements. These results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. They also show the sensitivity of efficient pyramid computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.
Keywords: pyramid computer, convexity, extreme points, digitized pictures, digital geometry, image processing, parallel computing, parallel algorithms, data movement operations, bandwidth limitations, lower bounds
Complete paper. This paper appears in Algorithmica 6 (1991), pp. 658-684.
|
Copyright © 2005-2020 Quentin F. Stout |