Parallel vision algorithms using sparse array representations

摘要

Sparse arrays are arrays in which the number of non-zero elements is a small fraction of the total number of array elements. Parallel algorithms are presented using sparse representations for arrays. It is shown that adopting such a representation not only reduces the processor/space requirement, but also provides efficient load balancing at no increase in time complexity. New parallel primitives needed to work with such a representation are defined. Sample algorithms from the areas of image processing and computer vision are presented. Alternative schemes for dealing with arrays containing large contiguous blocks of elements with identical array values are considered. The parallel architecture considered is a strict SIMD hypercube, and the applicability of the results presented to other architectures is described.