EUCLIDEAN DISTANCE TRANSFORM OF 3D iMAG,ES ON L.A.R.'P.B.S. MODEL

Abstract

Euclidean Distance Transform (EDT) of 2-D and 3-D images is one of the useful tools in various image processing algorithms. It is one of the basic operations in image processing and computer vision fields and essentially used in expanding, shrinking, thinning, segmentation, clustering and computing of images, object reconstruction, etc. It converts a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. Many sequential and parallel algorithms have been developed for Euclidean Distance Transform computation of 2-D and 3-D images on various, computational platforms. The objective of this dissertation work is to develop a time-optimal and scalable algorithm for EDT computation of 3-D images. In this dissertation work, an efficient and scalable parallel algorithm has been designed and implemented for computing EDT of 3-D images, on Linear Array with Reconfigurable Pipelined Bus System (LARPBS) multiprocessor model, which is a recently proposed architecture based on optical buses. This work is the extension of the algorithm for 2-D EDT computation on LARPBS architecture which is given by Chen, Pan and Xu. The algorithm computes the EDT of a 3-D image represented by N x N x N binary matrix in O( N2 log N /(a(n) * b(n))) time using N2 * a(N) * b(N) processors where a(N) and b(N) are the parameters and their values can be selected between 1 and N. By selecting different values for a(N) and b(N), time complexity and number of processors required can be altered which makes the algorithm more flexible and scalable. This algorithm has been implemented and tested on the multiprocessor cluster available at the Institute Computer Center. The performance has been analyzed and compared with other EDT algorithms given on various parallel computing platforms.