A Fast Number Theoretic Finite Radon Transform

Abstract

This paper presents a new fast method to map between images and their digital projections based on the Number Theoretic Transform (NTT) and the Finite Radon Transform (FRT). The FRT is a Discrete Radon Transform (DRT) defined on the same finite geometry as the Finite or Discrete Fourier Transform (DFT). Consequently, it may be inverted directly and exactly via the Fast Fourier Transform (FFT) without any interpolation or filtering [F. Matus and J. Flusser (1993)]. As with the FFT, the FRT can be adapted to square images of arbitrary sizes such as dyadic images, prime-adic images and arbitrary-sized images. However, its simplest form is that of prime-sized images [T. Hsung, D. Lun, and W. C. Siu (1996)]. The FRT also preserves the discrete versions of both the Fourier Slice Theorem (FST) and Convolution Property of the Radon Transform (RT). The NTT is also defined on the same geometry as the DFT and preserves the Circular Convolution Property (CCP) of the DFT [J. M. Pollard (1971) and C. Rader (1972)]. This paper shows that the Slice Theorem is also valid within the NTT and that it can be utilized as a new exact, integer-only and fast inversion scheme for the FRT, with the same computational complexity as the FFT. Digital convolutions and exact digital filtering of projections can also be performed using this Number Theoretic FRT (NFRT).