Abstract:
A computed tomography apparatus which generates an image of an examined subject using Fourier reconstruction with a gridding algorithm operates so that this algorithm is efficiently implemented by employing a hardware unit in the form of an ASIC, which produces the additional formation of contributions in the Cartesian frequency matrix, derived from the polar support points.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention is directed to a computed tomography apparatus of the type which produces an image of an examination subject by means of Fourier reconstruction. 
     2. Description of the Prior Art 
     In computed tomography, fan projections are measured and the fan projections can be converted into parallel projections by means of a suitable interpolation. 
     For the reconstruction of a sectional image from parallel projections, there are two reconstruction algorithms: convolution back-projection and Fourier reconstruction. 
     In reconstruction using convolution back-projection, the digitally very costly back-projection can be carried out using an RP-ASIC (German acronym for Back-Projection with Application-Specific Integrated Circuits). The RP-ASIC has clear advantages in speed and costs in relation to an implementation of the back-projection in freely programmable processors, due to its architecture, which is specifically adapted to the back-projection algorithm. A gridding algorithm is known (German OS 43 15 279) for Fourier reconstruction that specifies the transition from the polar grid to the Cartesian grid in the frequency space, but is numerically very costly. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is the efficient generation of a computed tomography image with Fourier reconstruction, using a gridding algorithm. 
     The above object is achieved in accordance with the principles of the present invention in a computed tomography apparatus which generates an image of an examined subject using Fourier reconstruction with a gridding algorithm, which operates so that this gridding algorithm is efficiently implemented, by employing a hardware unit in the form of an ASIC (Application-Specific Integrated Circuit) which produces additional formation of contributions in the Cartesian frequency matrix, derived from the polar support points. 
     In the inventive computed tomography apparatus, for the efficient implementation of the gridding algorithm a special hardware unit in the form of a GR-ASIC (Gridding with Application-Specific Integrated Circuits)is used. 
     The address bus, associated with the input data bus, can be omitted, if the addresses belonging to the data are transmitted via the data bus. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows the basic components of a computed tomography apparatus with a fan-shaped beam, for describing the basic idea of the invention. 
     FIG. 2 illustrates the basic steps in a known convolution back-projection technique for generating a computed tomography image. 
     FIG. 3 shows the basic steps for Fourier reconstruction of an image in computed tomography. 
     FIG. 4 illustrates a Cartesian frequency matrix of the type used in the computed tomography apparatus of the invention. 
     FIG. 5 illustrates interfaces to the GR-ASIC in the computed tomography apparatus of the invention. 
     FIG. 6 illustrates a further embodiment of the interfaces for the GR-ASIC in the computed tomography apparatus of the invention. 
     FIG. 7 is a block diagram of GR-ASIC of the computed tomography apparatus of the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 shows an X-ray source 1 and a detector 2 composed of a series of detector elements. The X-ray source 1 and the detector 2 rotate around a system axis 4 in order to scan a subject 3, so that the subject 3 is transilluminated from different directions by the fan-shaped X-ray beam 5 emanating from the X-ray source 1. The data supplied by the detector elements of the detector 2 are supplied to a computer 6, which reconstructs sectional images of the subject 3, which are reproduced on a monitor 7. The subject 3 lies in a measurement field 8, acquired by the X-ray beam 5. 
     FIG. 2 shows the program steps in the known convolution back-projection (which is not the subject matter of the invention). The scaling can be started after all parallel projections have run through the preceding program steps. The term parallel projections means data generated by converting data obtained from the fan-shaped beam projections corresponding to parallel radiation. 
     FIG. 3 shows the program steps in Fourier reconstruction. The 2D IFFT can be started after all parallel projections have run through the previous program steps. 
     Representation of use: 
     The FFTs and multiplications with the convolution Kernel or the phase factor can be adapted to the computing power of the RP-ASIC or GR-ASIC through the use of a corresponding number of freely programmable processors. In order to compare the implementations of the two reconstruction methods with respect to computing speed, it is thus sufficient to compare the processing power of the RP-ASIC and the GR-ASIC. 
     This is accomplished using the following exemplary values for NKan, M and NPix. A parallel data set with NKan=1500 channels per projection should be present. A length of M=4096 results therefrom for the one-dimensional FFTs. The image to be reconstructed should have NPix*NPix=512*512 pixels. 
     The comparison between the RP-ASIC and the GR-ASIC should be carried out on the basis of clock steps. For the RP-ASIC, a processing power of 1 pixel per clock step should be assumed. For the GR-ASIC, a processing power of 32 clock steps (for N=4) per support value in the polar grid is assumed. 
     The number of clock steps for the processing of a projection by the RP-ASIC is NPix*NPix=512*512=262144 clock steps, whereas for the GR-ASIC it is only (M/4+1)*32=1025*32=32800 clock steps. 
     For the case assumed, the GR-ASIC has eight times the processing power of the RP-ASIC. Due to the ability to cascade the RP-ASIC, this can also be expressed differently: for the assumed case, the GR-ASIC has the same processing power as a cascade of eight RP-ASICs. 
     In place of the solution with the GR-ASIC, one could also image the gridding algorithm onto freely programmable processors, however, many signal processors would be necessary for this in order to achieve the processing power of the GR-ASIC, which would have higher costs as a consequence. Given the use of a multiprocessor solution, access problems to the memory having the Cartesian frequency matrix would result, which problems are avoided through the use of a GR-ASIC. 
     Representation of the program steps of the gridding algorithm implemented in the GR-ASIC: 
     Below, the program steps of the gridding algorithm are specified that are to be implemented in the GR-ASIC. 
     In the gridding algorithm, each point of the polar grid contributes to N*N points of the rectangular grid of the Cartesian frequency matrix (FIG. 4). FIG. 4 shows the contribution of a polar support value in the Cartesian frequency matrix, based on N=4. 
     The Cartesian frequency matrix has the dimension FMAT*FMAT (see FIG. 4). A complex matrix element is referred to below as FM k! l!. 
     For each polar support value SP, all the following program steps must be executed. 
     Determination of the coordinates of UP(FXUP,FYUP) from the coordinates of the polar support points SP(FXSP,FYSP): 
     &lt;1.&gt; FXUP is the x coordinate of the lower left Cartesian grid point UP in the interpolation window (1 subtraction with rounding) 
     &lt;2.&gt; FYUP is the y coordinate of the lower left Cartesian grid point UP in the interpolation window (1 subtraction with rounding) Determination of the auxiliary quantities DX and DY: 
     &lt;3.&gt; DX=FXSP-FXUP (1 subtraction) 
     &lt;4.&gt; DY=FYSP-FYUP (1 subtraction) 
     The whole-number control variable l, used subsequently in steps &lt;5.&gt; to &lt;22.&gt;, goes from l=0 to l=N-1. 
     The whole-number control variable j, used subsequently in steps &lt;5.&gt; to &lt;22.&gt;, goes from j=0 to j=N-1. 
     The index region of the interpolation table goes from p=0 to p=LINTP-1. 
     Determination of the access indices px i! and py j! to the interpolation table of length LINTP: 
     &lt;5.&gt; px i! is the value, rounded to the next whole number, of the absolute magnitude of (DX+l)*LINTP*2/N (1 rounding, 1 multiplication and N-1 additions; the value LINTP*2/N represents a constant and needs to be calculated only once) 
     &lt;6.&gt; py j! is the value, rounded to the next whole number, of the absolute magnitude of (DY+j)*LINTP*2/N (1 rounding, 1 multiplication and N-1 additions) 
     Addressing of the values lx i! and ly j! of the interpolation table to the calculated access indices px i! and py j!: 
     &lt;7.&gt; lx i! is the value of the interpolation table at the access index px i! (N accesses to the interpolation table) 
     &lt;8.&gt; ly j! is the value of the interpolation table at the access index py j! (N accesses to the interpolation table) SP --  RE is the real part of the functional value of the polar support point SP. SP --  IM is the imaginary part of the functional value of the polar support point SP. Calculation of the additions ZU --  RE j! l! and ZU --  IM j! l! to the elements of the Cartesian frequency matrix that lie in the interpolation window of the polar support points: 
     &lt;9.&gt; ZUX --  RE i!=SP --  RE*lx i! (N multiplications) 
     &lt;10.&gt; ZUX --  IM i!=SP --  IM*lx i! (N multiplications) 
     &lt;11.&gt; ZU --  RE j! l!=ZUX --  RE i!*ly j! (N*N multiplications) 
     &lt;12.&gt; ZU --  IM j! l!=ZUX --  IM i!*ly j! (N*N multiplications) 
     Calculation of the access indices zl i! and zk j! of the elements of the Cartesian frequency matrix that lie in the interpolation window of the polar support points: 
     &lt;13.&gt; pl i!=FXUP+l (N additions) 
     &lt;14.&gt; pk j!=FYUP+j (N additions) 
     &lt;15.&gt; zl i!=pl i! is imaged modulo onto the region  0,FMAT-1! 
     &lt;16.&gt; zk j!=pk j! is imaged modulo onto the region  0,FMAT-1! 
     Addressing of the values FMZ zk j!! zl i!! of the elements of the Cartesian frequency matrix that lie in the interpolation window of the polar support points: 
     &lt;17.&gt; FMZ --  RE zk j!! zl i!! is the real part value of the memory of the Cartesian frequency matrix FM zk j!! zl i!! (N*N accesses to the Cartesian frequency matrix) 
     &lt;18.&gt; FMZ --  IM zk j!! zl i!! is the imaginary part value of the memory of the Cartesian frequency matrix FM zk j!! zl i!! (N*N accesses to the Cartesian frequency matrix) 
     Formation of the additions to the elements of the Cartesian frequency matrix that lie in the interpolation window of the polar support points: 
     &lt;19.&gt; FMZE --  RE zk j!! zl i!!=FUZ --  RE zk j!! zl i!+ZU --  RE j! l! (N*N additions) 
     &lt;20.&gt; FMZE --  IM zk j!! zl i!!=FMZ --  IM zk j!! zl i!!+ZU --  IM j! l! (N*N additions) 
     Delivery of the calculated values into the memory of the Cartesian frequency matrix: 
     &lt;21.&gt; The real part of the memory cell FM zk j!! zl i!! in the Cartesian frequency matrix is overwritten with the newly calculated value FMZE --  RE zk j!! zl i!!. (N*N accesses to the Cartesian frequency matrix) 
     &lt;22.&gt; The imaginary part of the memory cell FM zk j!! zl i!! in the Cartesian frequency matrix is overwritten with the newly calculated value FUZE --  IU zk j!! zl i!!. (N*N accesses to the Cartesian frequency matrix) 
     Interfaces of the GR-ASIC: 
     For the execution of the gridding algorithm, as input data the functional values of the polar support values SP and the Cartesian coordinates (FX,FY) of the polar support values SP in the frequency region are required. The output data of the gridding algorithm comprise the Cartesian frequency matrix. Both the functional values of the polar support values SP and the data of the Cartesian frequency matrix are complex. For the delivery of the Cartesian coordinates of the polar support values SP to the GR-ASIC, two variants can be used: 
     VK1: coordinate delivery variant 1: 
     The Cartesian coordinates (FX,FY) of the polar support values SP are respectively written in coordinate input buffers of the ASIC after the delivery of the polar support values SP. VK2: coordinate transmission variant 2: 
     All polar support values SP of a projection spectrum are delivered into the GR-ASIC in a block transfer. At the beginning of the block transfer, the subsequently designated setup values are thereby delivered to the GR-ASIC, from which values the GR-ASIC can itself generate the Cartesian coordinates of the polar support values SP delivered in the block transfer: 
     The Cartesian coordinate increments DFX and DFY between the support values delivered in the block transfer and the number of support values in the block transfer. 
     The functional values of the polar support values SP and the Cartesian coordinates (FX,FY) of the polar support values SP, or the associated set-up values, are written into different input buffers of the GR-ASIC via a data bus A (see FIG. 5). An FIFO design is recommended for the input buffer. 
     FIG. 5 shows a representation of the interfaces of the GR-ASIC. The interpolation table and the parameters required for the gridding algorithm are loaded via the data bus A during an initialization phase. The address bus ADR --  A serves for the addressing of the different input buffers and of the interpolation table memory. Via the bidirectional data bus B, the GR-ASIC forms additions to random data with the address RAND of the memory of the Cartesian frequency matrix, by means of read-modify-write accesses. The associated address RAND is generated by the GR-ASIC and applied to the address bus ADR --  B, via which the memory of the Cartesian frequency matrix is addressed. 
     FIG. 6 shows a representation of the interfaces of a further version of the GR-ASIC that does without the address bus ADR --  A. In this case, the addresses belonging to the data must be transmitted via the data bus A. 
     Imaging of the program steps onto the components of the GR-ASIC: 
     In the following, the program steps &lt;1.&gt; to &lt;22.&gt; are referred to: 
     In order to keep the number of accesses to the bus B as low as possible, the real and imaginary parts of the Cartesian frequency matrix are accessed in parallel fashion via the bus B. A total of 2*N*N accesses to the bus B are thus required for the processing of a polar support point SP. These are combined as follows: 
     Program step &lt;17.&gt; and &lt;18.&gt; parallel: N*N accesses, 
     program step &lt;21.&gt; and &lt;22.&gt; parallel: N*N accesses. 
     FIG. 7 shows a representation of the functional blocks of the GR-ASIC, with selected data paths. The computing elements (see FIG. 7) of the GR-ASIC are designed with respect to processing power so that all the program steps are hidden behind the 2*N*N accesses to the bus B. The number of accesses to the bus B thus determines the processing power of the GR-ASIC. If it is assumed that each access to the bus B has the duration of a clock step, the GR-ASIC has a processing power of 2*N*N clock steps for the processing of a polar support value. 
     In the following, a possible division of the program steps &lt;1.&gt; to &lt;22.&gt; into the functional blocks shown in FIG. 7 is represented. A utilization of the capacity of the functional block for the processing of a polar support point SP is thereby indicated in the form of clock steps. 
     Adder AADD 
     +1 subtraction of program step &lt;1.&gt;: 1 clock step 
     +1 subtraction of program step &lt;2.&gt;: 1 clock step 
     +1 subtraction of program step &lt;3.&gt;: 1 clock step 
     +1 subtraction of program step &lt;4.&gt;: 1 clock step 
     +N-1 additions of program step &lt;5.&gt;: N-1 clock steps 
     +N-1 additions of program step &lt;6.&gt;: N-1 clock steps 
     +N additions of program step &lt;13.&gt;: N clock steps 
     +N additions of program step &lt;14.&gt;: N clock steps 
     Total number of clock steps of the adder AADD: 4*N+2 
     Special arithmetic S: 
     +1 rounding of program step &lt;1.&gt;: 1 clock step 
     +1 rounding of program step &lt;2.&gt;: 1 clock step 
     +1 rounding of program step &lt;5.&gt;: 1 clock step 
     +1 rounding of program step &lt;6.&gt;: 1 clock step 
     +1 multiplication of program step &lt;5.&gt;: 1 clock step 
     +1 multiplication of program step &lt;6.&gt;: 1 clock step 
     +N modulo computations of program step &lt;15.&gt;: N clock steps 
     +N modulo computations of program step &lt;16.&gt;: N clock steps 
     Total number of clock steps of special arithmetic S: 2*N+6 
     Access to interpolation table INTTAB: 
     +N accesses from program step &lt;7.&gt;: N clock steps 
     +N accesses from program step &lt;8.&gt;: N clock steps 
     Total number of clock steps during access to the interpolation table INTTAB: 2*N 
     Multiplier MR 
     +N multiplications from program step &lt;9.&gt;: N clock steps 
     +N*N multiplications from program step &lt;11.&gt;: N*N clock steps 
     Total number of clock steps from the multiplier MR: N+N*N 
     Multiplier MI 
     +N multiplications from program step &lt;10.&gt;: N clock steps 
     +N*N multiplications from program step &lt;12.&gt;: N*N clock steps 
     Total number of clock steps from the multiplier MI: N+N*N 
     Adder AR 
     N*N additions from program step &lt;19.&gt;: N*N clock steps 
     Adder AI 
     N*N additions from program step &lt;20.&gt;: N*N clock steps 
     As the utilization of capacities of the individual functional blocks for the processing of a polar support point SP shows, in the case (important in practice) of N&gt;2, the capacity utilization of all functional blocks is smaller than the value 2*N*N, which results by means of the clock steps during access to the bus B. All program steps can thus be hidden behind the access to the Cartesian frequency matrix by means of suitable nesting. 
     The duration of 2*N*N clock steps for the processing of a polar support cell results as the processing power of the GR-ASIC. 
     The control unit SW controls the interfaces of the GR-ASIC, controls the sequence of calculations in the functional blocks, and takes over the generation of addresses. 
     The architecture of the GR-ASIC shown in FIG. 7 is designed so that all calculations of the GR-ASIC can be hidden behind the accesses to the memory SKART. The access bandwidth of the GR-ASIC to the memory SKART of the Cartesian frequency matrix thus determines the processing power of the GR-ASIC. 
     The maximum access bandwidth of the GR-ASIC to the Cartesian frequency matrix in the memory SKART is achieved when the GR-ASIC alone has right of access to the memory SKART. In this way, the time-consuming indivisible read-modify-write accesses and the required arbitration during access to the memory START are avoided, which would arise upon access of several subscribers to the memory SKART. 
     This represents an important advantage of the use of a GR-ASIC according to relation to an implementation of the gridding algorithm with a multiprocessor system, in which several processors would have to share the right of access to the memory having the Cartesian frequency matrix. If several subscribers have access to the memory SKART, the access bandwidth to the memory SKART decreases, due to arbitration expense. 
     The parallel projections NPROJ --  ALL to be processed can be divided into NE units En with n=1 to n=NE by GR-ASICs Gn (claim 1), with associated memory SKART Sn (according to claim 3). The gridding can thus be processed in parallel on the NE units En. As soon as the gridding is concluded on all NE units En, the access by the GR-ASICs Gn to the memory Sn can be removed. 
     Another addition unit ADD --  S, which adds the Cartesian frequency matrices of all NE memories Sn, can then be granted access to the memories Sn. The result of this addition is the Cartesian frequency matrix that arises by taking into account all the parallel projections NPROJ --  ALL to be processed. 
     Although modifications and changes may be suggested by those skilled in the art, it is the intention of the inventors to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of their contribution to the art.