An efficient parallel algorithm for computing the Gaussian convolution of multi-dimensional image data

In this paper, we propose a parallel convolution algorithm for estimating t he partial derivatives of 2D and 3D images on distributed-memory MIMD archi tectures. Exploiting the separable characteristics of the Gaussian filter, the proposed algorithm consists of multiple phases such that each phase cor responds to a separated filter. Furthermore, it exploits both the task and data parallelism, and reduces communication through data redistribution. We have implemented the proposed algorithm on the Intel Paragon and obtained a substantial speedup using more than 100 processors. The performance of th e algorithm is also evaluated analytically. The analytical results confirmi ng with the experimental results indicate that the proposed algorithm scale s very well with the problem size and number of processors. We have also ap plied our algorithm to the design and implementation of an efficient parall el scheme for the 3D surface tracking process. Although our focus is on 3D image data, the algorithm is also applicable to 2D image data, and can be u seful for a myriad of important applications including medical imaging, mag netic resonance imaging, ultrasonic imagery, scientific visualization, and image sequence analysis.