We propose to develop parallel algorithms and associated data structures for image manipulation in a digital library setting. These operations include image compression needed in data ingesting and transmission, hierarchical image decomposition to support browsing and storage, and efficient content-based search and pattern matching to aid query processing. These operations are critical in ingesting, managing, and manipulating large quantities of data, such as the data sets in the Sierra Nevada Ecosystem Project or the Florida Ecosystem Restoration Initiative Project. Because the amount of data is voluminous, efficient manipulation is crucial in data analysis and usage, and parallelizing operations is the key to achieve efficiency.
Effective strategies in parallelizing computation on images include spatial partitioning and pipelining. Spatial partitioning entails dividing images into chunks and assigning image blocks to separate processors for execution. It is most appropriate when identical, local operations are repeated over a whole image, and communication and data exchange among image blocks are minimal. Pipelining involves dedicating separate processors to perform different stages in a complicated operation to maintain a high throughput for a large data volume.
Instead of studying how to parallelize each individual algorithm, we can study how operations which are common to many image processing algorithms can be efficiently executed on a parallel processor. For example, many image processing algorithms involve filtering an image with a linear or nonlinear filter. Filtering operations are usually accomplished in the frequency domain. Hence, image transformations are an essential building block of many such algorithms. Other image processing algorithms such as mathematical morphology, skeletoning, contouring, and feature extraction are often performed directly in the image domain. These operations involve convolving an image with a suitable mask. Hence, designing parallel filtering operations in both the spatial and frequency domains through spatial partitioning and pipelining should be studied.
We will consider several parallel algorithms for two-dimensional convolution
that have been
developed on various parallel architectures. An example is the
fast algorithm for convolving a 
window of weighting
coefficients with an 
image matrix
on a pyramid computer of 
processors in time 
(excluding time to load the image
matrix) in [9]. For typical values of 
that are
found in practice, the algorithm has an optimal processor-time product
with respect to the usual sequential algorithm.
As efficient filtering operations are the bases of many image processing and signal processing algorithms, a toolkit can be assembled to aid parallelizing many image operations involving filtering. A useful application of the parallel filtering toolkit might be to port khoros to the Meiko CS-2 machine for experimentation. Furthermore, since many image and signal processing problems can be expressed in terms of recurrence equations, it is useful to have efficient parallel algorithms for solving recurrences. The fast parallel algorithms for various types of recurrence equations we developed in [33][32][31] will be useful in this respect.
Another useful class of image operations involves extracting the image features and capturing them in suitable high-level data structures, such as quadtree, boundary code, and run-length code. This process reduces the amount of data to be stored and expedites search and matching operations. We have developed efficient parallel algorithms for transforming between different image representations, such as boundary codes, run length codes, and quadtrees [36][30]. Unlike previous parallel algorithms, ours do not have restrictions on the shape of the images. The algorithms in [36][30] use tree-structures. Effective implementation of other data structures such as stacks, queues, dequeues, priority queues, and dictionary machines on a tree or an X-tree have also been proposed (see, e.g., [8]). These implementations and associated algorithms for manipulating the data structures should be useful in our work.