We present efficient parallel
algorithms 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 Theta(log n) to find the extreme points of a
convex figure in a digitized picture, to Theta(n1/6) to
find the diameter of a labeled figure,
to Theta(n1/4 log n) to find the extreme points of every
figure in a digitized picture,
to Theta (n1/2) to find
the extreme points of every labeled set of processing elements.
Our results show that the pyramid computer can be used to obtain
efficient solutions to nontrivial problems in image analysis.
We 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, digitized pictures,
digital geometry, image processing, parallel computing, parallel algorithms,
data movement operations, bandwidth limitations, lower bounds, computer
science
Much of the content of this paper has been incorporated into the book
Parallel Algorithms for Regular Architectures: Meshes and Pyramids,
by R. Miller and Q.F. Stout.
More information
about the book is available.
Russ Miller (miller@cse.buffalo.edu)