# Inverse Multiscale Discrete Radon Transform by Filtered Backprojection
## 1 Introduction
### Multiscale DRT  
Multiscale approach of the discrete Radon transform was proposed at the end of the 90s by three groups of authors almost at the same time [4; 5; 6]. It is characterized by having a linearithmic complexity and does not use interpolation. It uses a divide-and-conquer approach and a definition of discrete line that avoids multiplication by non-integer values, which are substituted by logical \(AND\) interactions at bit level. This gives place to a transform that is performed multidimensionally, a bit at a time, similar to the Fourier transform: which, indeed, can also be interpreted as a divide-and-conquer transform that has linearithmic complexity. In the continuum, the 2D Radon transform allows the description of a 2D signal, \(f(\cdot)\), in terms of the integrals along lines parameterized by an angle and a displacement, \((\theta,\rho)\), instead of single values accessed by their horizontal and vertical pair of cartesian coordinates, \((x,y)\). This is,  
\[\mathfrak{R}f(\theta,\rho)=\iint f(x,y)\ \delta(x\cdot cos\ \theta+y\cdot sin\ \theta-\rho)\ \mathrm{d}x\ \mathrm{d}y, \tag{1}\]  
or, equivalently, using the absolute slope and \(d\)isplacement form, with \(|s|<1\),  
\[\mathfrak{R}_{|\theta|\leq\frac{\pi}{2}}f(s,d)=\int f(u,\ u\cdot s+d)\ \mathrm{d}u, \qquad\qquad\mathfrak{R}_{|\theta|\geq\frac{\pi}{2}}f(s,d)=\int f(u \cdot s+d,\ u)\ \mathrm{d}u. \tag{2}\]  
The calculation of the Radon transform on a computer must deal with the discretization of data. Basically, for regularly spaced discrete data, they will be available only for a finite number of samples normally accessed with integer indexes. And the problem arises when the continuous definition of line integral makes necessary to evaluate the function at positions where there is no sample available and interpolation is required. [PERSON] [4], [PERSON] [5] and [PERSON] [6], almost simultaneously, proposed a divide-and-conquer approach reminiscent to FFT, in the sense that it works solving the problem at smaller scales and then combines those solutions to solve at greater scales, but with no multiplications nor complex _twiddle_ factors involved, relying exclusively on integer arithmetic to achieve its goal. By working at multiple scales, and due to the symmetry of the problem, intermediate computations can be reused preventing any sum to be computed twice and so reducing the computational load from \(\mathrm{O}(N^{3})\) to \(\mathrm{O}(N^{2}\log N)\). To make this possible, the key is to define a loose discrete line that traverses the domain visiting only integer positions, and therefore not exactly in a straight way. Ascensions are defined recursively, making lines composed of two halves, which in turn come each from other two-line segments of half their size and so on until line segments that join only two points are reached, and the problem cannot be further reduced. DRT authors omitted to establish any sort of trigonometric relation between \(x\) and \(y\) variable, instead they decomposed \(u\) and \(s\) variables of Equation (2) into binary indexes and mixed them at binary level, one index of \(u\) and one index of \(s\) at a time, this way avoiding direct multiplication of \(u\) by a slope which would have produced non-integer indexes. This can be achieved thanks to a loose definition of a discrete line, as follows:  
\[l_{s}^{n}(u_{0},\,\ldots,\,u_{n-1})=l_{\lfloor s/2\rfloor}^{n-1}(u_{0},\,\ldots, \,u_{n-2})+u_{n-1}\cdot\left\lfloor\frac{s+1}{2}\right\rfloor=\sum_{i=0}^{n-1}u_ {n-1-i}\cdot\left\lfloor\frac{\left\lfloor\frac{s}{2^{i}}\right\rfloor+1}{2}\right\rfloor \tag{3}\]  
with \(\lambda(u_{0},\,\ldots,\,u_{n-1})=\sum_{i=0}^{n-1}u_{i}\cdot 2^{i}\), i.e., the function that converts from binary multidimensional indexes, to decimal unidimensional index. This function \(l\) indicates how much ascends a line of slope \(s\) in a domain of size \(2^{n}\) by the time it reaches position \(\lambda(\mathbf{u})\). A digital line will be formed be the succession of points \(\{(x,l_{s}^{n}(x))\},\ x\in\{0\,...\,2^{n}-1\}\).