# Central and Periodic Multi-Scale Discrete Radon Transforms
## 1 Introduction
### Conventional Discrete Radon Transform  
Discrete Radon transform (DRT), with a multi-scale approach, dates back to the late 1990s [17; 18; 19] and was originally designed to compute all of the integrals (i.e., sums) of pixels located on a discrete line (actually a 1 pixel wide, \(N\) pixels long, stripe with approximately constant slope) that touches at least one point on an image, whose size is \(N\times N\), whilst projecting in a semi-circumference around it. There exists an algorithm that solves this problem with linearithmic complexity (\(O(N^{2}\log(N))\)), for a quadrant covering from 0 to 45 degrees. By joining together four runs of the algorithm on four mirrored versions of the input, a sort of Mobius band is obtained, which comprises of the whole set of line integrals that arise when projecting on 180 degrees around the image: a discrete version of the _sinogram_ in the continuum, devised by [PERSON] [1; 3]. Suppose an image of size \(N\times N\), \(N\) results are obtained by adding together the values in the same rows. Additionally, other \(N\) results are obtained by summing the values lying in the same columns. These two sets of summations correspond with projections at 0 and 90 degrees, respectively. Each summation adds \(N\) values and each set of summations comprises of \(N\) sums, corresponding to different intercepts in the projection axis. Two \(N^{2}\) sums have been computed, in order to obtain \(2N\)_line integrals_. With a little more computational effort, the multi-scale DRT algorithm provides \(N\) sets of line integrals to different angles between 0 and 45 degrees and, for each angle, its whole set of intercepts. Taking into account all the discrete lines that touch an image for a given projection angle is a non-trivial task. In order to not discard any line, even if it touches the image in just a single pixel, more intercepts must be considered for angles close to odd multiples of \(45^{\circ}\) and less for those close to \(0^{\circ}\), \(90^{\circ}\) and so forth. This explains why conventional DRT can have between \(N\) and \(2N-1\) number of intercepts, depending on the angle being calculated. Conventional DRT computes them all, and, as a result, the total output size for an \(N\times N\) input occupies \(3N\times 4N\), where only half of the results sum other than zero. In this work, two alternatives are presented. They generate an output of size \(N\) along the intercept dimension, independent of the angle being considered; that is, the output size for a single quadrant will be the same as the input. This will alleviate the computations and memory footprint of DRT by almost half. Considering the Figure 1, the first three subfigures, from left to right, show the same image but sheared, so that, when summed along rows, they give the conventional DRT for slopes \(0\)\(\frac{1}{2}\) and \(1\) as results. There is a column at the left of each subfigure that is precisely the DRT at each intercept for that slope. It can be appreciated that the number of intercepts to be calculated can be as much as twice the vertical size of the input, in order to accommodate the most extreme intercepts, when slope is maximal. This is what gives rise to the particular shape of the conventional DRT output, as shown to the rightmost in Figure 1.  
The algorithm itself does not shear the images. Instead, it can be thought that a plurality of discrete lines will be traversed, summing the pixels that lie on them. For the 0 to 45 degrees quadrant, the relation between the pixels belonging to the same discrete line is formulated, based on the ascents on the vertical dimension while the horizontal dimension is traversed. A discrete line will visit exactly one pixel on each column, and no  
Figure 1: First three subfigures: from left to right, an image sheared to accommodate, in a row, the discrete lines of conventional DRT for minimal, intermediate, and maximal slope of the 0 to 45 degrees quadrant. Rightmost, a depiction of input and output of conventional DRT for a single quadrant.