Parallel distance transforms on pyramid machines: Theory and implementation

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 arithmet…