Tomographic Application-Specific Integrated Circuits for Fast Radon Transformation

Abstract

The application-specific integrated circuit (ASIC) for tomographic processing of point objects is developed. The processing method is based on discrete Radon transform. We constructed modified method of replacing Radon transform with Fourier transform using interpolation on quasi-regular coordinate grids - regular with constant step on lengthwise coordinate and linearly growing step with constant difference on transverse coordinate. The resulting grid is quasi-regular and calculating complexity become significantly smaller. Grounding on concept of separate differences of arbitrary order we overcome the problem of irregularity of coordinate grids. The applied-specific tomographic circuit for processing 2D signals is constructed and three-level automated control technological processes system is developed.

Keywords

• application-specific integrated circuit
• tomographic processing of signals
• discrete Radon transform
• interpolation
• quasi-regular grid

-

In this paper we represent the results of development of application-specific integrated circuit (ASIC) for realisation fan-beam fast Radon transform with interpolation on quasi-regular coordinate grids. Many authors (see, e.g., 1) argue that Radon transform (discrete or fast) successfully replaced by corresponding Fourier transform. Actually Radon transform (RT) is orthogonal transform in polar (cylindrical for 3D transform) coordinate system. (Further we'll consider 2D transforms and polar coordinates without any losses of generality.)

The transformation from Cartesian to polar coordinates is conformal one, but only for infinitesimal areas 2. Figures of arbitrary shape in an infinitesimal area become similar, that is, they remain in shape. At the same time, the figures of finite dimensions are distorted, although the angles between the two curves are preserved (the so-called conservatism of the angles). Consequently, in the case of RT of any kind, including the fan RT, and with the corresponding transition from a discrete rectangular to a discrete polar coordinate grid, there is a distortion of geometric figures with conservatism of the angles. 2

Background overview An obvious regular method of eliminating geometric distortions when sampling the radial transformation of a Radon on a polar raster with irregular grid is the interpolation of data. The papers [ 3 – 5 ] suggest variations of the Lagrange interpolation formula – linear, bilinear, and similar. You can also use the interpolation formulas of Gauss, Stirling, Bessel, Padé approximation methods etc. [ 6,7 ].

In the transition from a rectangular to a polar raster on irregular grid, the difference tables have a fundamentally alternating step, and the interpolation formulas of Gauss, Stirling, Bessel, and others are unacceptable. Let's consider this problem in details.

To simplify the computational complexity of algorithms and to eliminate the problem of uncertainty of finite differences, a modified Lagrange interpolation formula with generalization of the concept of finite differences is introduced, introducing the so-called separated differences [ 8 ]. Using this generalization, the Lagrange interpolation formula is represented in a form similar to Newton's first interpolation formula. We note that Newton's interpolation formula is more convenient for computer calculations [ 9 ]. 3

Integrated circuits for fast Radon transform development The realization of the fan Radon transform with an irregular grid is reduced to the restoring of the function f  x for need number of samples xi , i  1, N , on line segment a  x  b , when its values are known x j , j  1, M , M  N . In this particular problem, the values represent the signals received by the sensors of the computer tomography system. It is desirable to have for f  x quite simple, that is, a less laborious computation formula that could be used to find approximate value of a function with the correct precision at an arbitrary point in the segment. The mathematical problem is formulated as follows. We assign on line segment a  x  b the grid   x0  a  x1  x2 

 xM 1  xM  b . The set of the function f  x values are assigned in the nodes of the grid. They are equal f  x0   f0 , f  x1   f1, , f  xM 1   fM 1, f  xM   fM . (1)

We have to construct the interpolant f  x  . Its values coincide with the values of the function f  x in the nodes of the grid:

f  xj   f j , j  1, 2, M 1, M .

To construct interpolants one needs to find the finite differences n -th order. Given the fact that the finite difference of the first order has the form f  x  f  x  f  x  x , write the general expression for the finite difference n -th order: n f  x    n1 f  x  .

Accordingly, the separated first-order differences will be written as  x0 , x1   f1  f0 ;  x1, x2   f2  f1 ;

x1  x0 x2  x1 separated second-order differences  xi , xi1, xi2  

xi2  xi  xi1, xi2    xi , xi1  , i  1, 2, We obtain separated differences n -th order from separated differences  n 1 -th order (2) etc. using recurrent relation  xi , xi1, xi2 , , xin  

xin  xi  xi1, xi2 , , xin    xi , xi1, , xin1  , n  1, 2, , i  0,1, 2, In a regular coordinate grid, the difference of arbitrary order x1  x0  x2  x1   xi2  xi1   xin  xin1 are constant quantities that are equal to each other. When the differences  x0  x1 ,  x1  x2 , ,  xi2  xi , ,  xin  xi  are independent random variables, the coordinate grid is obviously irregular by definition.

For our particular task, the coordinate grid is 2D one with nodes i , i  , i  1, N . Fig. 1 shows the elemental link of the grid: 1,1  1,2  . i ,i , i  1, 2 :  

2,1  2,2 

If we continue to assign the nodes of the grid along the coordinates , we get a sequence of nodes with coordinates of points i ,  j , i  1, N, j  1, 2 . Based on elementary geometric considerations, one can calculate the values of the intervals between the points i , i1 and  j ,  j1 . Fig. 2 shows a sequence of links. It can be extended as in coordinate , and in coordinate , and the values of the intervals i ,  j  remain unchanged. We call this coordinate

From formulas (3) and Fig. 2 it is seen that the coordinate grid along the lengthwise coordinate  is regular with step  . In transverse coordinate  the angular grid size increases linearly with a constant step  : k    k ; k      k . So, such a grid is fairly called quasi-regular. The illustration of quasi-regular 44 grid is shown on fig. 3.

Let's consider the element of two-dimensional Radon transform 10 (the so-called directed "butterfly" graph). It's shown on fig. 4.

INTERMEDIATE LEVEL Programmable logical controllers, regulation devices, counters etc.

LOW LEVEL Instrumentation, sensors, actuators and devices

REAL-TIME OPERATING SYSTEM

Gk k , k   Gi k , k U k  – estimate of space spectrum section

Given the advanced capabilities of specialized digital computers, it is logical to develop a tomographic detection / measurement device based on a specialized digital signal processor. Consider a functional diagram of a tomographic processor. To substantiate the architecture of the processor, recall that in the most general case, the transformation of Radon S is an integral along the lines  , r   x   x1, x2  2 , x1 cos   x2 sin   r,  0, , r   :

f , r    f r cos   sin , r sin    cos  d , where  2  is a Euclidean space of absolutely smooth functions integrating quadratically on a 2  set.

It is theoretically possible to imagine the Radon transform as a Fourier transform in a polar coordinate system with a smoothing r-filter. The so-called mathematical coprocessors CP1 and CP2 play the role of calculators of smoothing functions of the -filter.

Since the function f r cos   sin , r sin   cos  is neither even nor odd, the Fourier cosine transform and sine transforms must be performed separately. This task must also be solved with the help of the mathematical co-processor CP3. The CP4 mathematical coprocessor is designed to calculate the sum of squares of the cosine ( ucos out ) and sine ( usin out ) components of a signal.

The purpose of the other elements of the tomography processor is clear from Fig. 7. xm ym

FFCT Processor

FFST Processor

RAM1c RAM1s МCP1 (cosine-filter) MCP2 (sine-filter) cos cos VMM MCP3 VMM sin sin RAM2c RAM2s

Inverse FFCT Processor

Inverse FFST Processor

RAM3c MCP4 RAM3s

RAM4 zm

Mathematical coprocessors grounded on application-specific integrated circuits (ASIC) are required for the implementation of the algorithm of Fast Radon fan transform. In the case under consideration, mathematical coprocessors should be powerful and high-speed.

Mathematical coprocessor is a coprocessor for extending a plurality of central processing unit (CPU) commands. It extends the CPU functionality of the floating-point hardware module to processors that do not have a built-in module.

Floating-point unit (FPU) - part of the processor to perform a range of required mathematical operations over numbers. In accordance with the Volder's algorithm,

Representing the vector through its components x, y identifies each of these modes: (vectorisation) and rotation, depending on the angle of rotation of the vector. The basic idea of this algorithm is to split the rotation operation into a sequence of some elementary rotations. The rotation is accomplished by a shift and an arithmetic addition operation. Calculation of sine and cosine can be done using circular CORDIC in rotation mode at any desired angle. The algorithm is as follows.

To implement the Radon discrete transform algorithm, it is necessary to form a linear sample of values x and у: x  xm  xmin  mx, m  0, M 1; y  yn  ymin  ny, n  0, N 1.

In general, M  N .

Let yk  k sin k , 0  k  N 1 . Then the integral is superimposed by sum

M 1 N 1 f   k , k     f m cos m  rn sin n , m sin m  rn cos n 

m0 n0

To implement the basic equations (5-6), the processor uses two controlled arithmeticlogic devices (ADCs), which either add or subtract two 16-bit additions depending on the control signal formed by equation (8), that is, for the controller signal = 0, it executes (A + B) and for control signal = 1 it executes (AB). The addition-subtraction unit receives either x-in or y-in (or (A-B) real or imaginary component) as one input and a displaced version of the second as the second input. The offset value depends on the amount of iteration in the CORDIC loop as the amount of correct input offset to the variable switch ranges from 0 to 15 for the 16-bit precision module.

The operations of converting the current quadrant are performed with the help of the copy of the senior significant bit (SPD) into the cell of the next regular bit. Any angle of rotation from 0 to 2p, located in an arbitrary quadrant, is sufficient to convert within the basic operating range from -p / 2 to p / 2. The initial conversion operation is carried out by copying the normalized MSB of the angle of rotation k in the additional code to the MSB-1 multiplexer. In Fig. 7 A diagram of a coprocessor for vectorization and rotation of angles isin fig. 7. The main definitions are given in table 1. (5) (6) digital amplifier (multiplication device on g coefficient, g>1) =1

XOR device

delay device

If we consider the two-dimensional butterfly of Radon transform on the selected grid, then, taking into account the conservatism of the angles, the computational complexity calc is:  in coordinate  : calc  N log2 N  ;  in coordinate  ; calc  N  M  log2  N  M  , where N and M – numbers of samples  and  .

The computational complexity of orthogonal transformation algorithms based on fast Fourier transform in all cases does not exceed the polynomial.

Taking into account that in the direct calculation (without interpolation) of two-dimensional fast Radon transform, the computational complexity is calc  N 4  , then it's clear that saving computing costs is significant. xinp yinp uk

Counter [0…15] 0 ПП

CDMSB 0 1

G 1 SC 1 2

G

S 0 C Fig. 7. CORDIC mathematical coprocessor.

Shift1

Shift2

MST g U1 L A U2 L A U3 L A

ComD

0 In accordance with the presented scheme and on the basis of the synthesis results of the coprocessing device (Fig. 7), a functional scheme of a specialized tomographic processor was developed. The processor is implemented in hardware using mathematical co-processors of unified architecture for different modes - interpolation, rotation and vectorisation of components of two-dimensional signal [ 13-19 ]. Mathematical coprocessors also calculate the smoothing functions of the r-filter.

Thus, a specialized tomographic system for detecting anomalies (through holes) in pressure pipelines, on the one hand, is a system synthesized on the basis of statistical models of acoustic signals and interference, and on the other hand, it is built according to a modern three-level control and control scheme. Such construction gives additional possibilities for modification, scaling and expansion of system capabilities. 15. Fedushko, S., Ustyianovych, T., Gregus, M. Real-time high-load infrastructure transaction status output prediction using operational intelligence and big data technologies. Electronics (Switzerland), Volume 9, Issue 4, 668. (2020) DOI: 10.3390/electronics9040668 16. Odarchenko R., Abakumova A., Polihenko O., Gnatyuk S. Traffic offload improved method for 4G/5G mobile network operator, Proceedings of 14th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET-2018), pp. 1051-1054, 2018. 17. R. Odarchenko, V. Gnatyuk, S. Gnatyuk, A. Abakumova, Security Key Indicators Assessment for Modern Cellular Networks, Proceedings of the 2018 IEEE First International Conference on System Analysis & Intelligent Computing (SAIC), Kyiv, Ukraine, October 8-12, 2018, pp. 1-7. 18. Z. Hassan, R. Odarchenko, S. Gnatyuk, A. Zaman, M. Shah, Detection of Distributed Denial of Service Attacks Using Snort Rules in Cloud Computing & Remote Control Systems, Proceedings of the 2018 IEEE 5th International Conference on Methods and Systems of Navigation and Motion Control, October 16-18, 2018. Kyiv, Ukraine, pp. 283-288. 19. M. Zaliskyi, R. Odarchenko, S. Gnatyuk, Yu. Petrova. A. Chaplits, Method of traffic monitoring for DDoS attacks detection in e-health systems and networks, CEUR Workshop Proceedings, Vol. 2255, pp. 193-204, 2018.

References

1. Bates R.T.H. Image Restoration and Reconstruction (Oxford Engineering Science Series) / R. H. T. Bates, M. J. McDonnell . - Oxford, Clarendon, 1986 . - 304 pp.

2. Caratheodory C . Conformal Representation / Courier Corporation, 1998 - 115 pp.

3. Dutt A. , Rokhlin V . Fast Fourier transforms for non-equispaced data // Applied and Computational Harmonic Analysis . 1995 . Vol. 2 . P. 85 - 100 .

4. Beylkin G . On Applications of Unequally Spaced Fast Fourier Transforms / Mathematical Geophysics Summer School , Stanford, August 1998 , pp. 1 - 8 .

5. Bressler Y. Three-Dimensional Reconstruction from Projections with Incomplete and Noisy Data by Object Estimation / / Y. Bressler, A. Masovski . - IEEE Trans. on Acoust., Speech , and Signal Proc. , Vol. ASSP- 35 ,No 8, Aug . 1987 . - pp. 1139 - 1152 .

6. George A. Baker . Padé Approximants, 2nd ed. / George A. Baker , Jr., Peter Graves-Morris, Susan S. Baker . - Cambridge University Press, 1996 . - 746 pp.

7. Luke Y.L. The Special Functions and Their Approximations / Academic Press, 1969 . - 348 pp.

8. John F. Lectures on advanced numerical analysis . - Thomas Nelson and Sons Ltd., 36 Park Street London, 1966 . - 179 pp.

9. Samarsky A.A. Introduction to numerical methods . - M.: Nauka , 1982 . - 286 pp.

10. Dudgeon D.E. , Mersereau R.M. Multidimensional Digital Signal Processing. PrenticeHall , Englewood Cliffs, New Jersey, 1983 . - 400 pp.

11. Saaty T. L. The analytic hierarchy process . McGraw Hill , N.-Y., 1980 , 288 pp.

12. Ponomarenko O. V. Computerized system of detecting fistulas in product pipelines . - PhD-of-science thesis Specialty 05 . 13 .05 - computer systems and components. - Kyiv, NAU, 2011 .

13. Mazin Al Hadidi, Jamil S . Al-Azzeh , R. Odarchenko , S. Gnatyuk , A. Abakumova , Adaptive Regulation of Radiated Power Radio Transmitting Devices in Modern Cellular Network Depending on Climatic Conditions, Contemporary Engineering Sciences , Vol. 9 , № 10, рр. 473 - 485 , 2016 .

14. Al-Azzeh J.S. , Al Hadidi M. , Odarchenko R. , Gnatyuk S. , Shevchuk Z. , Hu Z. Analysis of self-similar traffic models in computer networks , International Review on Modelling and Simulations , № 10 ( 5 ), pp. 328 - 336 , 2017 .