# Central and Periodic Multi-Scale Discrete Radon Transforms
## 1 Introduction  
### Radon Transform, Use, and Algorithms for Its Computation  
The Radon transform, as originally envisioned [1], describes a bi-dimensional function, in terms of the set of line integrals through its domain. A set of line integrals that is complete, in the sense of covering all possible angles and interceptions. This mathematical tool has had an enormous impact in radiology, as it made tomography of the human body viable [2, 3]. This is because, as a pair of transforms, it manages not only to describe the integrals from the values in the measurement domain, but also to recover the values, based on their line integrals. Those are the forward and backward Radon transforms, respectively. In tomography, the most relevant part is the inverse path: the backward transform that reconstructs the values (the absorption rate of the different tissues within the human body) from the line integrals (the measured energy of beams attenuated after they traversed the body). In order to cope with Radon transform in a computer, several methods have been proposed. The inverse transform is a hard problem, not only because of its ill-posed nature,but even the forward one can be tricky, as its computational complexity, with a brute force approach, is \(O(N^{3})\), because an integral must be calculated for each slope and for each intercept; additionally, each integral involves the many elements present in the path of that line. Fortunately there are better algorithms than brute force, and they bring the complexity down to \(O(N^{2}\log(N))\). Although the calculation of the forward transform can be uninspiring for tomography (that is the task of the computer tomography scanner), it can still be of interest, nowadays, in other fields. It can be used to aid in robot auto-positioning [4], as a biometric identifier [5], to speed up differential equations solvers [6], or to straighten pictures taken with mobile phones [7], to name but a few examples. There are as many possible uses as there are methods to calculate the Radon transform. Some methods arose because of and for tomography; that is, with an emphasis on the inverse path. Among them are the algebraic reconstruction techniques [8], which are very tightly coupled to the design of the scanner. Another family of algorithms, probably the most widespread, arises from the Fourier projection-slice theorem [9; 10]. This theorem allows Radon transforms to be expressed in terms of Fourier transforms; in doing so, the backward Radon transform is not only feasible, but inherits the computational complexity of the latter, becoming fast to compute. Moreover, after years of refinement, Fourier-based methods are virtually free of artifacts. There are also methods designed specifically for the analysis of lines in images, i.e., with the emphasis on the forward transform. These are methods whose inputs will be intensities on a Cartesian grid. Although Fourier-based methods are still applicable, and despite their reduced complexity (of \(O(N^{2}\log(N))\)), they are not the most optimal. There are methods, such as the Hough transform [11; 12], with voting bins, which may be more efficient. Another family of methods relies on Dirac lattices and lines of rational slope [13; 14] which can be also of interest, for example, for reconstructions with just a few projections [15]. Finally, we will consider a family of methods, which we will call multi-scale, that compute the forward transform with a divide-and-conquer approach, and so they exhibit the same complexity as those based on Fourier, \(O(N^{2}\log(N))\), but without requiring interpolation or the use of floating point numbers. When they were initially proposed, they were not considered invertible, but it was later shown that such methods, although operating on integer mathematics, had a fast and exact inverse [16]. Our work is motivated by trying to squeeze the maximum computational efficiency out of the multi-scale DRT transform, in pursuit of its application, at video acquisition rates, in computer vision problems.