# Central and Periodic Multi-Scale Discrete Radon Transforms
## 3 Central DRT
### Central DRT Algorithm  
Unraveling this access pattern is, in itself, the algorithm that is being looked for, since it will be enough to operate exactly as in conventional DRT but only on the highlighted zones. The algorithm described, however, will add another improvement: the DRT can be formulated with pointwise sums of \(N\)-length vectors lying on different columns, thus paving the road to an efficient implementation on SIMD arithmetic units.  
So, instead of offering a formula for each value \(d\), it is possible to operate on \(N\) consecutive values of two columns on a previous stage to achieve another \(N\)-length vector that comprise the required data at a column on a later stage. The indications of where each \(N\)-length vector of interest starts (for a given stage, size, and slope) is provided next.  
It can be demonstrated that the computation relationship between columns,  
Then, the indexes of stage \(m\) will be expressed as:  
\[S_{0}=\sigma+v<<(m+1)\qquad\text{ and }\qquad S_{1}=S_{0}+1<<m.\]  
To calculate the starting point of the vector on the other axis, \(d\), we have to define:  
\[\Phi=\frac{\left(2^{m+1}-(m<(n-1))\right)\cdot\left(2^{n-m-2}-v\right)}{2^{m+1} -1}\cdot(v<2^{n-m-2}).\]  
With this value, we can calculate: \(\Delta_{d_{even}}=\left\lfloor 2\cdot\sigma\cdot\Phi\right\rfloor\), \(\Delta_{d_{odd}}=\left\lceil\Phi\right\rceil\), and \(\Delta_{d_{S_{1}}}=\sigma\).  
In these formulas, \(\left\lceil\cdot\right\rceil\) and \(\left\lfloor\cdot\right\rfloor\) are, respectively, the rounding operators to the next larger and smaller integer; the \(<<\) symbol refers to the binary shift and \(<\) is the _lower than_ comparison, evaluated to 0 or 1.  
Those values are applied following the schema on Figure 11:  
* \(N\) data in column \(S\), descending from row index \(top-\Delta_{d_{even}}\), are the result of adding \(N\) data in column \(S0\), descending from row index \(top-\Delta_{d_{even}}\), and \(N\) data in column \(S1\), descending from row index \(top-\Delta_{d_{even}}+\Delta_{S_{1}}\).
* \(N\) data in column \(S+1\), descending from row index \(top-\Delta_{d_{even}}-\Delta_{d_{odd}}\), are the result of adding \(N\) data in column \(S0\), descending from row index \(top-\Delta_{d_{even}}-\Delta_{d_{odd}}\), and \(N\) data in column \(S1\), descending from row index \(top-\Delta_{d_{even}}-\Delta_{d_{odd}}+\Delta_{S_{1}}+1\).  
The resulting algorithm can be found in pseudo-code as Algorithm A1. The last **for** loop rectifies the central band, so that the output is a \(N\times N\) square.  
Figure 12 shows the vectors to be added at each stage of the algorithm for a \(16\times 16\) image. From left to right and from bottom to top: initial stage, partial stages, and final stage of the transform. Each stage, labeled as \(f^{m}\), with \(m=0.4\), shows data positions that will be accceded to calculate the next stage. Accesses for even column computations are shown with flat corners, whilst odd columns accesses are shown with rounded corners.  
At each stage of the computation, there will be two memory buffers storing the data at stages \(m\) and \(m+1\). Here, for the sake of depiction, accesses from odd and even columns are shown isolated; otherwise, they would overlap. However, they access the same columns for a pair of \(S\) and \(S+1\) computation, only with different starting row indexes. The result of the computation at a stage is shown again as input for the next step of the transformation.  
Figure 12: N-length vectors lying on different columns to be added at each stage of the algorithm for a \(16\times 16\) image.  
It can be seen in the schema how, in each stage, only the data required by a later stage are computed. During the transformation, positions outside the \(0:3N/2\) zone are sometimes acceded. These accesses are simply ignored because they would add zeros.  
An example of output of central DRT will be shown later, after exposing the periodic DRT algorithm.