A Fast Discrete Approximation Algorithm for the Radon Transform

This paper addresses fast parallel methods for the computation of the Radon (or Hough) transform. The Radon transform of an image is a set of projections of the image taken at different angles. Its computation is important in image processing and computer vision for problems such as pattern recognition and reconstruction of medical images. A unique new method for combining partial results is presented, from which an algorithm is constructed that computes a provably good approximation to the discrete Radon transform. The approximate discrete Radon transform (ADRT) algorithm computes 4, N - 4 projections through an N N image in time O (N²lgN) (the majority of previous algorithms are O (N3, ) ). The method is quite simple and easy to parallelize. A parallel version of the ADRT requires only O (lgN) parallel steps on O (N2) processors, ignoring communication time. An additional property of the algorithm is that it can be applied directly to compute the backprojection step of the inverse RT.