6533b859fe1ef96bd12b7560

RESEARCH PRODUCT

Parallel distance transforms on pyramid machines: Theory and implementation

subject

description

Abstract A distance transform of a binary image is an array each of whose elements gives the distance from the corresponding pixel to the closest ‘1’ in the binary image. Distance transforms have uses in image matching and shape analysis, among other applications. We present a parallel algorithm for weighted distance transforms that runs particularly efficiently on hierarchical cellular-logic machines, a subclass of the architectures known as pyramid machines. The algorithm computes the 3–4 distance transform; however it can be readily adapted to the city-block (‘Manhattan’) and chessboard distance measures. The algorithm runs in O(M) time, for an M × M image. Since it avoids using arithmetic except to maintain a counter, it is well-suited to the bit-serial processor architectures common in massively-parallel image processing. The algorithm updates the wave of distance values by repeatedly checking if any of each pixel's neighbors have particular markings. The pattern-matching instructions of the University of Washington HCLM-1 prototype pyramid machine are particularly appropriate for this checking. A memory-efficient variant of the algorithm is also presented; here the upper levels of the pyramid are employed to restrict the ranges of values that finer-level cells can take on. The result is that only four bit-pyramids are necessary to represent arbitrarily large distance maps with the 3–4 distance, and only two bits are necessary for the chessboard distance.