# Patent

## Title
Three-dimensional forward and back projection methods

## Abstract

Methods provided for forward and back-projection, which are referred to as separable footprint (SF) projectors: exemplified by the SF-TR and SF-TT projectors. These methods approximate the voxel footprint functions as 2D separable functions. Because of the separability of these footprint functions, calculating their integrals over a detector cell is greatly simplified and can be implemented efficiently. In some embodiments, the SF-TR projector uses trapezoid functions in the transaxial direction and rectangular functions in the axial direction. In some embodiments, the SF-TT projector uses trapezoid functions in both the axial and transaxial directions. Simulations and experiments showed that both SF projector methods are more accurate than conventional distance-driven (DD) projectors. Moreover, the SF-TT projector is more accurate than the SF-TR projector for rays associated with large cone angles. In some embodiments, the SF-TR projector has similar computation speed with the DD projector and the SF-TT projector is about two times slower.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of U.S. Provisional Application No. 61/378,041, filed on Aug. 30, 2010. The entire disclosure of the above application is incorporated herein by reference.


GOVERNMENT INTEREST
This invention was made with government support under CA059827 awarded by the National Institutes of Health. The Government has certain rights in the invention.


FIELD
The present disclosure relates to X-ray computed tomography (CT) and, more particularly, relates to three-dimensional (3D) forward and backward projection methods. The invention also is applicable to other tomographic imaging modalities, such as position emission tomography (PET), and tomosynthesis imaging, and to image-guided therapy applications.
BACKGROUND AND SUMMARY
This section provides background information related to the present disclosure that is not necessarily prior art. This section also provides a general summary of the disclosure, and is not a comprehensive disclosure of its full scope or all of its features.
According to the principles of the present teachings, methods are provided for forward and back-projection, which are referred to as separable footprint (SF) projectors: the SF-TR and SF-TT projectors being exemplary embodiments. These methods approximate the voxel footprint functions as 2D separable functions. Because of the separability of these footprint functions, calculating their integrals over a detector cell is greatly simplified and can be implemented efficiently. In some embodiments, the SF-TR projector uses trapezoid functions in the transaxial direction and rectangular functions in the axial direction. In some embodiments, the SF-TT projector uses trapezoid functions in both the axial and transaxial directions. Simulations and experiments showed that both SF projector methods are more accurate than conventional distance-driven (DD) projectors. Moreover, the SF-TT projector is more accurate than the SF-TR projector for rays associated with large cone angles. In some embodiments, the SF-TR projector has similar computation speed with the DD projector and the SF-TT projector is about two times slower.
Further areas of applicability will become apparent from the description provided herein. The description and specific examples in this summary are intended for purposes of illustration only and are not intended to limit the scope of the present disclosure.



DRAWINGS
The drawings described herein are for illustrative purposes only of selected embodiments and not all possible implementations, and are not intended to limit the scope of the present disclosure.
FIG. 1 illustrates an exemplary axial cone-beam flat-detector geometry according to the principles of the present teachings—the method also is applicable to systems with curved detectors;
FIGS. 2A-2C are a series of illustrations of exact footprint functions and their associated profiles for 1 mm3 voxels centered at the origin (left series—(i) series)), (100, 150, 15) mm (center series—(ii) series), and (93, 93, 93) mm (right series-(iii) series));
FIGS. 3A-3B are a series of illustrations showing the maximum error comparison between the forward DD, SF-TR, and SF-TT projectors for a voxel centered at the origin (FIG. 3A) and a voxel centered at (100, 150, −100) right (FIG. 3B);
FIGS. 4A-4B are a series of illustrations of Shepp-Logan digital phantoms in Hounsfield units, wherein the left series illustrates an axial view, the center series illustrates a coronal view, and the right series illustrates a sagittal view;
FIGS. 5A-5B are a series of axial views of FOV images reconstructed by the interactive method (PWLS-CG) using the SF and DD methods, respectively, wherein FIG. 5A uses a SF-TR projector and FIG. 5B uses a DD projector; and
FIGS. 6A-6D are a series of axial views of ROI images reconstructed by the interactive method (PWLS-CG) using the SF-TR and DD methods, respectively (FIGS. 6A, 6B), and the associate error (FIGS. 6C, 6D), wherein FIGS. 6A, 6C use a SF-TR projector and FIGS. 6B, 6D use a DD projector.



Corresponding reference numerals indicate corresponding parts throughout the several views of the drawings.
DETAILED DESCRIPTION
Example embodiments will now be described more fully with reference to the accompanying drawings. Example embodiments are provided so that this disclosure will be thorough, and will fully convey the scope to those who are skilled in the art. Numerous specific details are set forth such as examples of specific components, devices, and methods, to provide a thorough understanding of embodiments of the present disclosure. It will be apparent to those skilled in the art that specific details need not be employed, that example embodiments may be embodied in many different forms and that neither should be construed to limit the scope of the disclosure. In some example embodiments, well-known processes, well-known device structures, and well-known technologies are not described in detail.
The terminology used herein is for the purpose of describing particular example embodiments only and is not intended to be limiting. As used herein, the singular forms “a”, “an” and “the” may be intended to include the plural forms as well, unless the context clearly indicates otherwise. The terms “comprises,” “comprising,” “including,” and “having,” are inclusive and therefore specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. The method steps, processes, and operations described herein are not to be construed as necessarily requiring their performance in the particular order discussed or illustrated, unless specifically identified as an order of performance. It is also to be understood that additional or alternative steps may be employed.
Spatially relative terms, such as “inner,” “outer,” “beneath”, “below”, “lower”, “above”, “upper” and the like, may be used herein for ease of description to describe one element or feature's relationship to another element(s) or feature(s) as illustrated in the figures. Spatially relative terms may be intended to encompass different orientations of the device in use or operation in addition to the orientation depicted in the figures. For example, if the device in the figures is turned over, elements described as “below” or “beneath” other elements or features would then be oriented “above” the other elements or features. Thus, the example term “below” can encompass both an orientation of above and below. The device may be otherwise oriented (rotated 90 degrees or at other orientations) and the spatially relative descriptors used herein interpreted accordingly.
I INTRODUCTION
Iterative statistical methods for 3D tomographic image reconstruction offer numerous advantages such as the potential for improved image quality and reduced dose, as compared to the conventional methods such as filtered back-projection (FBP). They are based on models for measurement statistics and physics, and can easily incorporate prior information, the system geometry and the detector response.
The main disadvantage of statistical reconstruction methods is the longer computation time of iterative algorithms that are usually required to minimize certain cost functions. For most iterative reconstruction methods, each iteration requires one forward projection and one back-projection, where the forward projection is roughly a discretized evaluation of the Radon transform, and the back-projector is the adjoint of the forward projector. These operations are the primary computational bottleneck in iterative reconstruction methods, particularly in 3D image reconstruction. Forward projector methods are also useful for making digitally rendered radiographs (DRR).
Traditional forward and back-projectors compute the intersection lengths between each tomographic ray and each image basis function. Many methods for accelerating this process have been proposed. Due to the finite size of detector cells, averaging the intersection lengths over each detector cell is considered to be a more precise modeling. Mathematically, it is akin to computing the convolution of the footprint of each basis function and some detector blur, such as a 2D rectangular function.
Any projector method must account for the geometry of the imaging system. Cone-beam geometries are needed for axial and helical cone-beam X-ray computed tomography (CT). In 3D parallel-beam geometry projection space, there are four independent indices (μ, ν, φ, θ). The ray direction is specified by (φ, θ) where φ and θ denote the azimuthal and polar angle of the ray respectively and (μ, ν) denote the local coordinates on a 2D area detector. In contrast, axial cone-beam projection space is characterized by three independent indices (s, t, β) and two distance parameters (Ds0, D0d), where β denotes the angle of the source point counter-clockwise from the y axis, (s, t) denote the detector coordinates, Ds0 denotes the source to rotation center distance and D0d denotes the isocenter to detector distance. (See FIG. 1). The axial cone-beam geometry is a special case of helical cone-beam geometry with zero helical pitch.
The divergence of tomographic rays in the cone-beam geometry causes depth-dependent magnification of image basis functions, i.e., voxels close to the X-ray source cast larger shadows on the detector than voxels close to the detector. This complication does not appear in the parallel-beam geometry (e.g., in certain PET systems). Therefore, many existing projection and back-projection methods designed for 3D parallel-beam geometry are not directly suitable for cone-beam geometry.
A variety of projection methods for 3D cone-beam geometries have been proposed. All methods provide some compromise between computational complexity and accuracy. Among these, spherically symmetric basis functions (blobs) have many advantages over simple cubic voxels or other basis functions for the image representation, e.g., their appearance is independent of the viewing angle. However, evaluating integrals of their footprint functions is computationally intensive. Ziegler et al. (a) stored these integrals in a lookup-table. If optimized blobs are used and high accuracy is desired, the computation of forward and back-projection is still expensive due to loading a large table and the fact that blobs intersect many more tomographic rays than voxels.
Rectification techniques were introduced to accelerate the computation of cone-beam forward and backward projections. Riddell et al. resampled the original data to planes that are aligned with two of the reconstructed volume main axes, so that the original cone-beam geometry can be replaced by a simpler geometry that involves only a succession of plane magnifications. In iterative methods, resampled measurements can simplify forward and back-projection each iteration. However, resampling involves interpolation that may slightly decrease spatial resolution. Another drawback of this method is that the usual assumption of statistical independence of the original projection data samples no longer holds after rectification, since interpolation introduces statistical correlations.
The distance-driven (DD) projector is a current state-of-the-art method. It maps the horizontal and vertical boundaries of the image voxels and detector cells onto a common plane such as xz or yz plane, approximating their shapes by rectangles. (This step is akin to rectification). It calculates the lengths of overlap along the x (or y) direction and along the z direction, and then multiplies them to get the area of overlap. The DD projector has the largest errors for azimuthal angles of the X-ray source that are around odd multiples of π/4, because the transaxial footprint is approximately triangular rather than rectangular at those angles.
This disclosure describes new approaches for 3D forward and back-projection that we call the separable footprint (SF) projectors, exemplified by the SF-TR and SF-TT projectors. They approximate the voxel footprint functions as 2D separable functions. This approximation is reasonable for typical axial or helical cone-beam CT geometries and for typical PET geometries. The separability of these footprint functions greatly simplifies the calculation of their integrals over a detector cell and allows efficient implementation of the SF projectors. The SF-TR projector uses trapezoid functions in the transaxial direction and rectangular functions in the axial direction, whereas the SF-TT projector uses trapezoid functions in both directions. It is accurate to use rectangle approximation in the axial direction for cone-beam geometries with small cone angles (<2°) such as the multi-slice detector geometries, and to use trapezoid approximation for CT systems with larger cone angles (>10°) such as flat-panel detector geometries. Other functions besides rectangles and trapezoids may also be suitable.
Our studies showed that both SF projector methods are more accurate than the distance-driven (DD) projector. In particular, the SF methods reduce the errors around odd multiples of π/4 seen with DD. The SF-TT projector is more accurate than the SF-TR projector for voxels associated with large cone angles. The SF-TR projector has similar computation speed with the DD projector and the SF-TT projector is about 2 times slower.
To balance computation and accuracy, one may combine the SF-TR and SF-TT projector, that is, to use the SF-TR projector for voxels associated with small cone angles such as voxels near the plane of the X-ray source where the rectangle approximation is adequate, and use the SF-TT projector for voxels associated with larger cone angles. Other combinations of approximations may also be suitable, where the combination may depend on any of the voxel location or the detector cell location or combinations thereof.
The organization of this disclosure is as follows. Section II reviews the cone-beam geometry and projection, describes the cone-beam 3D system model. and presents the analytical formula of cone-beam projections of voxel basis functions. Section III introduces the SF projectors and contrasts the SF projectors with DD projector. Section IV gives simulation results, including accuracy and speed comparison between the SF-TR, SF-TT and DD projector as standalone modules and within iterative reconstruction. Finally, conclusions are presented in Section V.
II CONE-BEAM PROJECTION
II.1 Cone-Beam Geometry
For simplicity of presentation, we focus on the flat-detector axial cone-beam geometry (see FIG. 1). The methods generalize easily to arc detectors and helical geometries among others.
The X-ray source lies on points on a circle of radius Ds0 centered at the rotation center on the z=0 plane. The source position {right arrow over (p)}0 can be parameterized as follows:




  
    
      
        
          
            
              p
              →
            
            0
          
          =
          
            (
            
              
                
                  
                    
                      
                        
                          
                            -
                            
                              D
                              
                                
                                  
                                
                                ⁢
                                
                                  s
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  0
                                
                              
                            
                          
                          ⁢
                          sin
                          ⁢
                          
                            
                          
                          ⁢
                          β
                        
                      
                    
                    
                      
                        
                          
                            D
                            
                              
                                
                              
                              ⁢
                              
                                s
                                ⁢
                                
                                  
                                
                                ⁢
                                0
                              
                            
                          
                          ⁢
                          cos
                          ⁢
                          
                            
                          
                          ⁢
                          β
                        
                      
                    
                  
                
              
              
                
                  0
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        1
        )
      
    
  




where Ds0 is the source to rotation center distance and β denotes the angle of the source point counter-clockwise from the y axis. For simplicity, we present the case of an ideal point source of X-rays. To partially account for non-ideal X-ray sources, one can modify the footprint function in (20) and (26) below.

Let (s, t) denote the local coordinates on the 2D detector plane, where the s-axis is perpendicular to the z-axis, and the t-axis is parallel to the z-axis. A point on the 2D detector can be expressed as




  
    
      
        
          
            
              p
              →
            
            1
          
          =
          
            (
            
              
                
                  
                    
                      s
                      ⁢
                      
                        
                      
                      ⁢
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      β
                    
                    +
                    
                      
                        D
                        
                          0
                          ⁢
                          
                            
                          
                          ⁢
                          d
                        
                      
                      ⁢
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      β
                    
                  
                
              
              
                
                  
                    
                      s
                      ⁢
                      
                        
                      
                      ⁢
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      β
                    
                    -
                    
                      
                        D
                        
                          0
                          ⁢
                          
                            
                          
                          ⁢
                          d
                        
                      
                      ⁢
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      β
                    
                  
                
              
              
                
                  t
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where D0d=Dsd−Ds0 is the isocenter to detector distance. The direction vector of a ray from {right arrow over (p)}0 to {right arrow over (p)}1 can then be expressed as





  
    
      
        
          
            e
            →
          
          =
          
            
              
                
                  
                    p
                    →
                  
                  1
                
                -
                
                  
                    p
                    →
                  
                  0
                
              
              
                
                
                  
                    
                      p
                      →
                    
                    1
                  
                  -
                  
                    
                      p
                      →
                    
                    0
                  
                
                
              
            
            =
            
              (
              
                
                  
                    
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      φ
                      ⁢
                      
                        
                      
                      ⁢
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      θ
                    
                  
                
                
                  
                    
                      
                        -
                        cos
                      
                      ⁢
                      
                        
                      
                      ⁢
                      φ
                      ⁢
                      
                        
                      
                      ⁢
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      θ
                    
                  
                
                
                  
                    
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      θ
                    
                  
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        3
        )
      
    
  
  
    
      where
    
    
      
        
      
    
  
  
    
      
        γ
        =
        
          
            γ
            ⁡
            
              (
              s
              )
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            arctan
            ⁡
            
              (
              
                s
                
                  D
                  sd
                
              
              )
            
          
        
      
    
    
      
        (
        4
        )
      
    
  
  
    
      
        φ
        =
        
          
            φ
            ⁡
            
              (
              
                s
                ,
                β
              
              )
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            
              γ
              ⁡
              
                (
                s
                )
              
            
            +
            β
          
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        
          θ
          =
          
            
              θ
              ⁡
              
                (
                
                  s
                  ,
                  t
                
                )
              
            
            ⁢
            
              =
              △
            
            ⁢
            
              -
              
                arctan
                (
                
                  t
                  
                    
                      
                        s
                        2
                      
                      +
                      
                        D
                        sd
                        2
                      
                    
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        6
        )
      
    
  




and φ and θ denote the azimuthal and polar angle of the ray from {right arrow over (p)}0 to {right arrow over (p)}1 respectively.

The cone-beam projections of a 3D object ƒ({right arrow over (x)}) where {right arrow over (x)}=(x, y, z), are given by

p(s,t;β)=∫L(s,t,β)ƒ({right arrow over (x)})dl,  (7)

where the integral is along the line segment:





  
    
      
        
          
            L
            ⁡
            
              (
              
                s
                ,
                t
                ,
                β
              
              )
            
          
          =
          
            {
            
              
                
                  
                    p
                    →
                  
                  0
                
                +
                
                  l
                  ⁢
                  
                    e
                    →
                  
                  ⁢
                  
                    ∷
                  
                  ⁢
                  
                    
                  
                  ⁢
                  l
                
              
              ∈
              
                [
                
                  0
                  ,
                  
                    L
                    p
                  
                
                ]
              
            
            }
          
        
        ⁢
        
          

        
        ⁢
        
          
            L
            p
          
          ⁢
          
            =
            △
          
          ⁢
          
            
              
                
                  D
                  sd
                  2
                
                +
                
                  s
                  2
                
                +
                
                  t
                  2
                
              
            
            .
          
        
      
    
    
      
        (
        8
        )
      
    
  




For a point {right arrow over (x)}=(x, y, z) between the source and detector, the projected s coordinate of it is




  
    
      
        
          
            τ
            ⁡
            
              (
              
                
                  β
                  ;
                  x
                
                ,
                y
              
              )
            
          
          =
          
            
              D
              sd
            
            ⁢
            
              
                
                  τ
                  p
                
                ⁡
                
                  (
                  
                    
                      β
                      ;
                      x
                    
                    ,
                    y
                  
                  )
                
              
              
                
                  d
                  s
                
                ⁡
                
                  (
                  
                    
                      β
                      ;
                      x
                    
                    ,
                    y
                  
                  )
                
              
            
          
        
        ,
      
    
    
      
        (
        9
        )
      
    
  
  
    
      where
    
    
      
        
      
    
  
  
    
      
        
          
            
              τ
              p
            
            ⁡
            
              (
              
                
                  β
                  ;
                  x
                
                ,
                y
              
              )
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            
              x
              ⁢
              
                
              
              ⁢
              cos
              ⁢
              
                
              
              ⁢
              β
            
            +
            
              y
              ⁢
              
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              β
            
          
        
        ,
      
    
    
      
        (
        10
        )
      
    
  
  
    
      
        
          
            
              d
              s
            
            ⁡
            
              (
              
                
                  β
                  ;
                  x
                
                ,
                y
              
              )
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            
              D
              
                s
                ⁢
                
                  
                
                ⁢
                0
              
            
            -
            
              
                τ
                ⊥
              
              ⁡
              
                (
                
                  
                    β
                    ;
                    x
                  
                  ,
                  y
                
                )
              
            
          
        
        ,
      
    
    
      
        
      
    
  
  
    
      
        
          
            τ
            ⊥
          
          ⁡
          
            (
            
              
                β
                ;
                x
              
              ,
              y
            
            )
          
        
        ⁢
        
          =
          △
        
        ⁢
        
          
            
              -
              x
            
            ⁢
            
              
            
            ⁢
            sin
            ⁢
            
              
            
            ⁢
            β
          
          +
          
            y
            ⁢
            
              
            
            ⁢
            cos
            ⁢
            
              
            
            ⁢
            
              β
              .
            
          
        
      
    
    
      
        
      
    
  




The projected t coordinate is





  
    
      
        
          t
          ⁡
          
            (
            
              
                β
                ;
                x
              
              ,
              y
              ,
              z
            
            )
          
        
        =
        
          z
          ⁢
          
            
              
                D
                sd
              
              
                
                  d
                  s
                
                ⁡
                
                  (
                  
                    
                      β
                      ;
                      x
                    
                    ,
                    y
                  
                  )
                
              
            
            .
          
        
      
    
    
      
        (
        11
        )
      
    
  




The azimuthal and polar angles of the ray connecting the source and {right arrow over (x)} are





  
    
      
        
          φ
          ⁡
          
            (
            
              
                β
                ;
                x
              
              ,
              y
            
            )
          
        
        =
        
          β
          +
          
            arctan
            ⁡
            
              (
              
                
                  
                    τ
                    p
                  
                  ⁡
                  
                    (
                    
                      
                        β
                        ;
                        x
                      
                      ,
                      y
                    
                    )
                  
                
                
                  
                    d
                    s
                  
                  ⁡
                  
                    (
                    
                      
                        β
                        ;
                        x
                      
                      ,
                      y
                    
                    )
                  
                
              
              )
            
          
        
      
    
    
      
        (
        12
        )
      
    
  
  
    
      
        
          θ
          ⁡
          
            (
            
              
                β
                ;
                x
              
              ,
              y
              ,
              z
            
            )
          
        
        =
        
          -
          
            
              arctan
              (
              
                z
                
                  
                    
                      τ
                      p
                      2
                    
                    +
                    
                      d
                      s
                      2
                    
                  
                
              
              )
            
            .
          
        
      
    
    
      
        (
        13
        )
      
    
  




II.2 Cone-Beam 3D System Model

In the practice of iterative image reconstruction, rather than operating on a continuous object ƒ({right arrow over (x)}), we forward project a discretized object represented by a common basis function β0({right arrow over (x)}) superimposed on a N1×N2×N3 Cartesian grid as follows:




  
    
      
        
          
            f
            ⁡
            
              (
              
                x
                →
              
              )
            
          
          =
          
            
              ∑
              
                n
                →
              
            
            ⁢
            
              
                f
                ⁡
                
                  [
                  
                    n
                    →
                  
                  ]
                
              
              ⁢
              
                
                  β
                  0
                
                ⁡
                
                  (
                  
                    
                      (
                      
                        
                          x
                          →
                        
                        -
                        
                          
                            c
                            →
                          
                          ⁡
                          
                            [
                            
                              n
                              →
                            
                            ]
                          
                        
                      
                      )
                    
                    ⁢
                    ∅
                    ⁢
                    
                      Δ
                      →
                    
                  
                  )
                
              
            
          
        
        ,
      
    
    
      
        (
        14
        )
      
    
  




where the sum is over the N1×N2×N3 lattice that is estimated and {right arrow over (c)}[{right arrow over (n)}]=(c1[{right arrow over (n)}], c2[{right arrow over (n)}], c3[{right arrow over (n)}]) denotes the center of the {right arrow over (n)}th basis function and [{right arrow over (n)}]=(n1, n2, n3)εZ3. The grid spacing is {right arrow over (Δ)}=(Δ1, Δ2, Δ3), and Ø denotes element-wise division. We consider the case Δ1=±Δ2 hereafter, but we allow Δ1≠Δ3, because voxels are often not cubic.

Most projection/back-projection methods use a linear model that ignores the “exponential edge gradient effect” caused by the nonlinearity of Beer's law. We adopt the same type of approximation here. Assume that the detector blur h(s, t) is shift invariant, independent of β and acts only along the s and t coordinates. Then the ideal noiseless projections satisfy

 yβ[sk,tl]=∫∫h(sk−s,tl−t)p(s,t;β)dsdt,  (15)

where p(s, t; β) is the 3D projection of ƒ({right arrow over (x)}) given by (7), and (sk, tl) denotes the center of detector cell specified by indices (k, l). The methods we present are applicable to arbitrary samples (sk, tl), but for simplicity of presentation and implementation we focus on the case of uniformly spaced samples:

sk(k−ws)ΔS,k=0, . . . ,Ns−1,

tl=(l−wt)ΔT,l=0, . . . ,Nt−1

ws=(Ns−1)/2+cs 

wt=(Nt−1)/2+ct,  (16)

where ΔS and ΔT denote the sample spacing in s and t respectively. The user-selectable parameters cs and ct denote offsets for the detector, e.g., cs=1⁄4 corresponds to a quarter detector offset.

Substituting the basis expansion model (14) for the object into (15) and using (7) leads to the linear model




  
    
      
        
          
            
              
                y
                _
              
              β
            
            ⁡
            
              [
              
                
                  s
                  k
                
                ,
                
                  t
                  l
                
              
              ]
            
          
          =
          
            
              ∑
              
                n
                →
              
            
            ⁢
            
              
                
                  a
                  β
                
                ⁡
                
                  [
                  
                    
                      s
                      k
                    
                    ,
                    
                      
                        t
                        l
                      
                      ;
                      
                        n
                        →
                      
                    
                  
                  ]
                
              
              ⁢
              
                f
                ⁡
                
                  [
                  
                    n
                    →
                  
                  ]
                
              
            
          
        
        ,
      
    
    
      
        (
        17
        )
      
    
  




where the elements of system matrix A are samples of the following cone-beam projection of a single basis function centered at {right arrow over (c)}[{right arrow over (n)}]:

αβ[sk,tl;{right arrow over (n)}]=F(sk,tl;β;{right arrow over (n)}),  (18)

where the “blurred footprint” function is





  
    
      
        
          
            F
            ⁡
            
              (
              
                
                  s
                  k
                
                ,
                
                  
                    t
                    l
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
              
              )
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            ∫
            
              ∫
              
                
                  h
                  ⁡
                  
                    (
                    
                      
                        
                          s
                          k
                        
                        -
                        s
                      
                      ,
                      
                        
                          t
                          l
                        
                        -
                        t
                      
                    
                    )
                  
                
                ⁢
                
                  q
                  ⁡
                  
                    (
                    
                      s
                      ,
                      
                        t
                        ;
                        β
                        ;
                        
                          n
                          →
                        
                      
                    
                    )
                  
                
                ⁢
                
                  d
                  s
                
                ⁢
                
                  d
                  t
                
              
            
          
        
        ,
      
    
    
      
        (
        19
        )
      
    
  




and q(s, t; β; {right arrow over (n)}) denotes the cone-beam footprint of basis function β0(({right arrow over (x)}−{right arrow over (c)}[{right arrow over (n)}])Π{right arrow over (Δ)}), i.e.,

q(s,t;β;{right arrow over (n)})=∫L(s,t,β)β0(({right arrow over (x)}−{right arrow over (c)}[{right arrow over (n)}])Π{right arrow over (Δ)})dl.  (20)

Computing the footprint of the voxel is also known as “splatting”.

The goal of forward projectors is to compute (17) rapidly but accurately. Although the system matrix A is sparse, it is impractical to precompute and store even the nonzero system matrix values for the problem sizes of interest in cone-beam CT, so practical methods (including our proposed approach) essentially compute those values on the fly.
We focus on a simple separable model for the detector blur




  
    
      
        
          
            h
            ⁡
            
              (
              
                s
                ,
                t
              
              )
            
          
          =
          
            
              1
              
                
                  r
                  s
                
                ⁢
                
                  r
                  t
                
              
            
            ⁢
            
              rect
              ⁡
              
                (
                
                  s
                  
                    r
                    s
                  
                
                )
              
            
            ⁢
            
              rect
              ⁡
              
                (
                
                  t
                  
                    r
                    t
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        21
        )
      
    
  




where rs and rt denote the width along s and t respectively. This model accounts for the finite size of the detector elements. Note that rs and rt can differ from the sample spacing sk−sk-1 and tl−tl-1 to account for detector gaps.

II.3 Footprints of Voxel Basis Functions

We focus on cubic voxel basis functions hereafter, but one could derive analytical formulas for footprints of other basis functions. The cubic voxel basis function is given by,




  
    
      
        
          
            
              
                
                  β
                  0
                
                ⁡
                
                  (
                  
                    x
                    →
                  
                  )
                
              
              =
              
                
                  rect
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  rect
                  ⁡
                  
                    (
                    y
                    )
                  
                
                ⁢
                
                  rect
                  ⁡
                  
                    (
                    z
                    )
                  
                
              
            
          
        
        
          
            
              
                =
                
                  
                                        
                      {
                      
                        
                          
                          x
                          
                        
                        ≤
                        
                          1
                          /
                          2
                        
                      
                      }
                    
                  
                  ⁢
                  
                                        
                      {
                      
                        
                          
                          y
                          
                        
                        ≤
                        
                          1
                          /
                          2
                        
                      
                      }
                    
                  
                  ⁢
                  
                                        
                      {
                      
                        
                          
                          z
                          
                        
                        ≤
                        
                          1
                          /
                          2
                        
                      
                      }
                    
                  
                
              
              ,
            
          
        
      
    
    
      
        (
        22
        )
      
    
  




where 1{·} denotes the indicator function.

Substituting (22) into (20), the analytical formula for the cone-beam projection footprint of the {right arrow over (n)}th basis function is:




  
    
      
        
          
            
              
                q
                ⁡
                
                  (
                  
                    s
                    ,
                    
                      t
                      ;
                      β
                      ;
                      
                        n
                        →
                      
                    
                  
                  )
                
              
              =
              
              ⁢
              
                
                  ∫
                  0
                  
                    L
                    p
                  
                
                ⁢
                
                  
                    
                      β
                      0
                    
                    ⁡
                    
                      (
                      
                        
                          (
                          
                            
                              
                                p
                                →
                              
                              0
                            
                            +
                            
                              l
                              ⁢
                              
                                e
                                →
                              
                            
                            -
                            
                              
                                c
                                →
                              
                              ⁡
                              
                                [
                                
                                  n
                                  →
                                
                                ]
                              
                            
                          
                          )
                        
                        ⁢
                        ∅
                        ⁢
                        
                          Δ
                          →
                        
                      
                      )
                    
                  
                  ⁢
                  
                    d
                    l
                  
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  ∫
                  0
                  
                    L
                    p
                  
                
                ⁢
                
                  
                                        
                      {
                      
                        
                          
                          
                            
                              d
                              1
                            
                            +
                            
                              l
                              ⁢
                              
                                
                              
                              ⁢
                              
                                e
                                1
                              
                            
                          
                          
                        
                        ≤
                        
                          
                            Δ
                            1
                          
                          /
                          2
                        
                      
                      }
                    
                  
                  ⁢
                  
                  ⁢
                  
                                        
                      {
                      
                        
                          
                          
                            
                              d
                              2
                            
                            +
                            
                              l
                              ⁢
                              
                                
                              
                              ⁢
                              
                                e
                                2
                              
                            
                          
                          
                        
                        ≤
                        
                          
                            Δ
                            2
                          
                          /
                          2
                        
                      
                      }
                    
                  
                
              
            
          
        
        
          
            
              
              ⁢
              
                
                                    
                    {
                    
                      
                        
                        
                          
                            d
                            3
                          
                          +
                          
                            le
                            3
                          
                        
                        
                      
                      ≤
                      
                        
                          Δ
                          3
                        
                        /
                        2
                      
                    
                    }
                  
                
                ⁢
                
                  d
                  l
                
              
            
          
        
        
          
            
              
                =
                
                ⁢
                
                  
                    a
                    1
                  
                  ·
                  
                    a
                    2
                  
                  ·
                  
                    a
                    3
                  
                  ·
                  
                    
                      [
                      
                        
                          l
                          max
                        
                        -
                        
                          l
                          min
                        
                      
                      ]
                    
                    +
                  
                
              
              ,
            
          
        
      
    
    
      
        (
        23
        )
      
    
  




where {right arrow over (e)}=(e1, e2, e3) was defined in (3),





  
    
      [
      x
      ]
    
    +
  
  ⁢
  
    =
    △
  
  ⁢
  
    max
    ⁡
    
      (
      
        x
        ,
        0
      
      )
    
  




and





  
    
      
        
          
            
              d
              →
            
            ⁢
            
              =
              △
            
            ⁢
            
              
                
                  
                    p
                    →
                  
                  0
                
                -
                
                  
                    c
                    →
                  
                  ⁡
                  
                    [
                    
                      n
                      →
                    
                    ]
                  
                
              
              =
              
                (
                
                  
                    d
                    1
                  
                  ,
                  
                    d
                    2
                  
                  ,
                  
                    d
                    3
                  
                
                )
              
            
          
          ,
          
            

          
          ⁢
          
            
              a
              1
            
            =
            
              {
              
                
                  
                    
                      
                                                
                          {
                          
                            
                              
                              
                                d
                                1
                              
                              
                            
                            ≤
                            
                              
                                Δ
                                1
                              
                              /
                              2
                            
                          
                          }
                        
                      
                      ,
                    
                  
                  
                    
                      
                        sin
                        ⁢
                        
                          
                        
                        ⁢
                        φ
                      
                      =
                      0
                    
                  
                
                
                  
                    
                      1
                      ,
                    
                  
                  
                    
                      
                        
                          sin
                          ⁢
                          
                            
                          
                          ⁢
                          φ
                        
                        ≠
                        0
                      
                      ,
                    
                  
                
              
               
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            a
            2
          
          =
          
            {
            
              
                
                  
                    
                                            
                        {
                        
                          
                            
                            
                              d
                              2
                            
                            
                          
                          ≤
                          
                            
                              Δ
                              2
                            
                            /
                            2
                          
                        
                        }
                      
                    
                    ,
                  
                
                
                  
                    
                      cos
                      ⁢
                      
                        
                      
                      ⁢
                      φ
                    
                    =
                    0
                  
                
              
              
                
                  
                    1
                    ,
                  
                
                
                  
                    
                      
                        cos
                        ⁢
                        
                          
                        
                        ⁢
                        φ
                      
                      ≠
                      0
                    
                    ,
                  
                
              
            
             
          
        
        ⁢
        
          

        
        ⁢
        
          
            a
            3
          
          =
          
            {
            
              
                
                  
                    
                                            
                        {
                        
                          
                            
                            
                              d
                              3
                            
                            
                          
                          ≤
                          
                            
                              Δ
                              3
                            
                            /
                            2
                          
                        
                        }
                      
                    
                    ,
                  
                
                
                  
                    
                      sin
                      ⁢
                      
                        
                      
                      ⁢
                      φ
                    
                    =
                    0
                  
                
              
              
                
                  
                    1
                    ,
                  
                
                
                  
                    
                      
                        sin
                        ⁢
                        
                          
                        
                        ⁢
                        φ
                      
                      ≠
                      0
                    
                    ,
                  
                
              
            
             
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              l
              max
            
            =
            
              min
              ⁢
              
                {
                
                  
                    L
                    p
                  
                  ,
                  
                    l
                    +
                    1
                  
                  ,
                  
                    l
                    +
                    2
                  
                  ,
                  
                    l
                    +
                    3
                  
                
                }
              
            
          
          ,
          
            

          
          ⁢
          
            
              l
              min
            
            =
            
              max
              ⁢
              
                {
                
                  0
                  ,
                  
                    l
                    -
                    1
                  
                  ,
                  
                    l
                    -
                    2
                  
                  ,
                  
                    l
                    -
                    3
                  
                
                }
              
            
          
          ,
          
            

          
          ⁢
          
            
              l
              +
              i
            
            =
            
              {
              
                
                  
                    
                      
                        max
                        ⁢
                        
                          {
                          
                            
                              
                                
                                  
                                    
                                      Δ
                                      →
                                    
                                    i
                                  
                                  /
                                  2
                                
                                -
                                
                                  d
                                  i
                                
                              
                              
                                e
                                i
                              
                            
                            ,
                            
                              
                                
                                  
                                    -
                                    
                                      
                                        Δ
                                        →
                                      
                                      i
                                    
                                  
                                  /
                                  2
                                
                                -
                                
                                  d
                                  i
                                
                              
                              
                                e
                                i
                              
                            
                          
                          }
                        
                      
                      ,
                    
                  
                  
                    
                      
                        e
                        i
                      
                      ≠
                      0
                    
                  
                
                
                  
                    
                      ∞
                      ,
                    
                  
                  
                    
                      
                        
                          e
                          i
                        
                        =
                        0
                      
                      ,
                    
                  
                
              
               
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            l
            -
            i
          
          =
          
            {
            
              
                
                  
                    
                      min
                      ⁢
                      
                        {
                        
                          
                            
                              
                                
                                  
                                    Δ
                                    →
                                  
                                  i
                                
                                /
                                2
                              
                              -
                              
                                d
                                i
                              
                            
                            
                              e
                              i
                            
                          
                          ,
                          
                            
                              
                                
                                  -
                                  
                                    
                                      Δ
                                      →
                                    
                                    i
                                  
                                
                                /
                                2
                              
                              -
                              
                                d
                                i
                              
                            
                            
                              e
                              i
                            
                          
                        
                        }
                      
                    
                    ,
                  
                
                
                  
                    
                      e
                      i
                    
                    ≠
                    0
                  
                
              
              
                
                  
                    
                      -
                      ∞
                    
                    ,
                  
                
                
                  
                    
                      e
                      i
                    
                    =
                    0.
                  
                
              
            
             
          
        
      
    
    
      
        (
        24
        )
      
    
  




For typical cone-beam geometries, polar angles θ of rays are much smaller than 90°, so there is no need to consider the case of cos θ=0. Combining (18), (19) and (23) yields the “ideal” projector for cubic voxels in cone-beam CT.

III SEPARABLE FOOTPRINT (SF) PROJECTOR
It would be expensive to exactly compute the true footprint (23) and the “blurred footprint” (19) for the voxel basis function on the fly, so appropriate approximations of the “blurred footprint” (19) are needed to simplify the double integral calculation.
To explore alternatives, we simulated a flat-detector cone-beam geometry with Ds0=541 mm and Dsd=949 mm. We computed cone-beam projections of voxels analytically using (23) at sample locations (nΔS, mΔT) where ΔS=ΔT=0.001 mm and n, mεZ. The left column of FIG. 2 shows the exact footprint function and its profiles for a voxel with Δ1=Δ2=Δ3=1 mm centered at the origin when β=30°. The center column of FIG. 2 shows those of a voxel centered at (100, 150, 15) mm when β=0°. The azimuthal and polar angle of the ray connecting the source and this voxel center are 14.3° and 2.1° respectively. The cone angle of a typical 64-slice cone-beam CT geometry is about 2°. The right column of FIG. 2 shows those of a voxel centered at (93, 93, 93) mm when β=0°. The azimuthal and polar angle of the ray connecting the source and this voxel center are 11.7° and 11.5° respectively. The cone angle of a typical cone-beam CT geometry with 40×40 cm2 flat-panel detector is about 12°. The first two true footprints look like 2D separable functions. The third footprint is approximately separable except for small areas at the upper left and lower right corner.
Inspired by shapes of the true footprints (see FIG. 2), we approximate them as follows,




  
    
      
        
          
            
              q
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
            ≈
            
              
                q
                ap
              
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
          
          ⁢
          
            =
            △
          
          ⁢
          
            
              l
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
            ⁢
            
              
                q
                sf
              
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        25
        )
      
    
  




where qsf(s, t; β; {right arrow over (n)}) denotes a 2D separable function with unit maximum amplitude,





  
    
      
        
          
            
              q
              sf
            
            ⁡
            
              (
              
                s
                ,
                
                  t
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
              
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              
                q
                1
              
              ⁡
              
                (
                
                  s
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
            ⁢
            
              
                q
                2
              
              ⁡
              
                (
                
                  t
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        26
        )
      
    
  




where q1(s; β; {right arrow over (n)}) and q2(t; β; {right arrow over (n)}) denote the approximating functions in s and t respectively. In (25), l(s, t; β; {right arrow over (n)}) denotes the “amplitude” of qsf(s, t; β; {right arrow over (n)}).

For small basis functions and narrow blurs h(s, t), the angles of rays within each detector cell that intersect each basis function are very similar, so l(s, t; β; {right arrow over (n)}) is much smoother than h(s, t) and q(s, t; β; {right arrow over (n)}). Substituting (25) into (19) leads to




  
    
      
        
          
            
              F
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
            ≈
            
              
                F
                sf
              
              ⁡
              
                (
                
                  s
                  ,
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              
                h
                ⁡
                
                  (
                  
                    s
                    ,
                    t
                  
                  )
                
              
              **
              
                [
                
                  
                    l
                    ⁡
                    
                      (
                      
                        s
                        ,
                        
                          t
                          ;
                          β
                          ;
                          
                            n
                            →
                          
                        
                      
                      )
                    
                  
                  ⁢
                  
                    
                      q
                      sf
                    
                    ⁡
                    
                      (
                      
                        s
                        ,
                        
                          t
                          ;
                          β
                          ;
                          
                            n
                            →
                          
                        
                      
                      )
                    
                  
                
                ]
              
            
            ≈
            
              
                l
                ⁡
                
                  (
                  
                    s
                    ,
                    
                      t
                      ;
                      β
                      ;
                      
                        n
                        →
                      
                    
                  
                  )
                
              
              ⁡
              
                [
                
                  
                    h
                    ⁡
                    
                      (
                      
                        s
                        ,
                        t
                      
                      )
                    
                  
                  **
                  
                    
                      q
                      sf
                    
                    ⁡
                    
                      (
                      
                        s
                        ,
                        
                          t
                          ;
                          β
                          ;
                          
                            n
                            →
                          
                        
                      
                      )
                    
                  
                
                ]
              
            
          
        
        ,
      
    
    
      
        (
        27
        )
      
    
  




where the inequality uses the fact that l(s, t; β; {right arrow over (n)}) is approximately a constant over each detector cell. The value l(sk, tl; β; {right arrow over (n)}) denotes this constant for detector cell (sk, tl), and * denotes 2D convolution.

If the detector blur is also modeled as separable, i.e.,

h(s,t)=h1(s)h2(t),  (28)

then the blurred footprint functions (27) have the following separable approximation:





  
    
      
        
          
            
              F
              sf
            
            ⁡
            
              (
              
                
                  s
                  k
                
                ,
                
                  
                    t
                    l
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
              
              )
            
          
          =
          
            
              l
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ,
                  
                    
                      t
                      l
                    
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                
                )
              
            
            ⁢
            
              
                F
                1
              
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
            ⁢
            
              
                F
                2
              
              ⁡
              
                (
                
                  
                    t
                    l
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
          
        
        ,
        
          

        
        ⁢
        where
      
    
    
      
        (
        29
        )
      
    
  
  
    
      
        
          
            
              F
              1
            
            ⁡
            
              (
              
                
                  s
                  k
                
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            ∫
            
              
                
                  h
                  1
                
                ⁡
                
                  (
                  
                    
                      s
                      k
                    
                    -
                    s
                  
                  )
                
              
              ⁢
              
                
                  q
                  1
                
                ⁡
                
                  (
                  
                    s
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                  )
                
              
              ⁢
              
                d
                s
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              F
              2
            
            ⁡
            
              (
              
                
                  t
                  l
                
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            ∫
            
              
                
                  h
                  2
                
                ⁡
                
                  (
                  
                    
                      t
                      l
                    
                    -
                    t
                  
                  )
                
              
              ⁢
              
                
                  q
                  2
                
                ⁡
                
                  (
                  
                    t
                    ;
                    β
                    ;
                    
                      n
                      →
                    
                  
                  )
                
              
              ⁢
              
                
                  d
                  t
                
                .
              
            
          
        
      
    
    
      
        (
        30
        )
      
    
  




III.1 Amplitude Approximation Methods

One natural choice for the amplitude function l(·) is the following voxel-dependent factor that we call the A3 method:




  
    
      
        
          
            l
            ⁡
            
              (
              
                
                  s
                  k
                
                ,
                
                  
                    t
                    l
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
              
              )
            
          
          =
          
            
              
                l
                3
              
              ⁡
              
                (
                
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
            ⁢
            
              =
              Δ
            
            ⁢
            
              
                l
                
                  φ
                  0
                
              
              ·
              
                l
                
                  θ
                  0
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        where
      
    
    
      
        (
        31
        )
      
    
  
  
    
      
        
          l
          
            φ
            0
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            Δ
            1
          
          
            max
            ⁢
            
              {
              
                
                  
                  
                    cos
                    ⁡
                    
                      (
                      
                        φ
                        0
                      
                      )
                    
                  
                  
                
                ,
                
                  
                  
                    sin
                    ⁡
                    
                      (
                      
                        φ
                        0
                      
                      )
                    
                  
                  
                
              
              }
            
          
        
      
    
    
      
        (
        32
        )
      
    
  
  
    
      
        
          
            l
            
              θ
              0
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            1
            
              
              
                cos
                ⁡
                
                  (
                  
                    θ
                    0
                  
                  )
                
              
              
            
          
        
        ,
      
    
    
      
        (
        33
        )
      
    
  




where φ0=φ0(β, {right arrow over (n)}) and θ0=θ0(β, {right arrow over (n)}) denote the azimuthal and polar angles of the ray connecting the source and center of the {right arrow over (n)}th voxel. They can be computed by (12) and (13). Since this voxel-dependent amplitude depends on angles (θ0, φ0) and β, the approximated footprint qap(s, t; β; {right arrow over (n)}) is separable with respect to s and t too. However, the dependence on voxel centers {right arrow over (c)}[{right arrow over (n)}] requires expensive computation. One must compute N1×N2×N3×Nβ different lθ0 values and N1×N2×Nβ different lφ0 values, where Nβ denotes the number of projection views. In addition, computing lθ0 and lφ0 for each voxel at each projection view involves either trigonometric operations (cos, sin and tan−1) or square and square root operations to directly evaluate cos and sin.

To accelerate computation of the SF projector, we propose a voxel-ray-dependent amplitude named the A2 method:




  
    
      
        
          
            l
            2
          
          ⁡
          
            (
            
              
                s
                k
              
              ,
              
                
                  t
                  l
                
                ;
                β
                ;
                
                  n
                  →
                
              
            
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            l
            
              φ
              0
            
          
          ·
          
            l
            
              θ
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ,
                  
                    t
                    l
                  
                
                )
              
            
          
        
      
    
    
      
        (
        34
        )
      
    
  
  
    
      
        
          
            l
            
              θ
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ,
                  
                    t
                    l
                  
                
                )
              
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            1
            
              
              
                cos
                ⁡
                
                  (
                  
                    θ
                    ⁡
                    
                      (
                      
                        
                          s
                          k
                        
                        ,
                        
                          t
                          l
                        
                      
                      )
                    
                  
                  )
                
              
              
            
          
        
        ,
      
    
    
      
        (
        35
        )
      
    
  




where θ(sk, tl) given in (6) is the polar angle of the ray connecting the source and detector center (sk, tl). There are many fewer tomographic rays (Ns×Nt) than voxels in a 3D image (N1×N2×Nβ) and θ(sk, tl) does not depend on β for flat detector geometries (see (6)), so using (34) saves substantial computation versus (31).

We also investigated a ray-dependent amplitude named the A1 method:




  
    
      
        
          
            l
            1
          
          ⁡
          
            (
            
              
                s
                k
              
              ,
              
                
                  t
                  l
                
                ;
                β
              
            
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            l
            
              φ
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ;
                  β
                
                )
              
            
          
          ·
          
            l
            
              θ
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ,
                  
                    t
                    l
                  
                
                )
              
            
          
        
      
    
    
      
        (
        36
        )
      
    
  
  
    
      
        
          
            l
            
              φ
              ⁡
              
                (
                
                  
                    s
                    k
                  
                  ;
                  β
                
                )
              
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              Δ
              1
            
            
              max
              ⁢
              
                {
                
                  
                    
                    
                      cos
                      ⁡
                      
                        (
                        
                          φ
                          ⁡
                          
                            (
                            
                              
                                s
                                k
                              
                              ;
                              β
                            
                            )
                          
                        
                        )
                      
                    
                    
                  
                  ,
                  
                    
                    
                      sin
                      ⁡
                      
                        (
                        
                          φ
                          ⁡
                          
                            (
                            
                              
                                s
                                k
                              
                              ;
                              β
                            
                            )
                          
                        
                        )
                      
                    
                    
                  
                
                }
              
            
          
        
        ,
      
    
    
      
        (
        37
        )
      
    
  




where φ(sk; β) given in (5) is the azimuthal angle of the ray connecting the source and detector cell center (sk, tl). For each β, there are Ns different lφ(sk; β) for the A1 method and N1×N2 different lφ0 for the A2 method.

These amplitude methods are similar to Joseph's method where the triangular footprint function is scaled by 1/max(|cos φ|, |sin φ|) for 2D fan-beam geometry. All three methods have similar accuracies, but the A3 method is much slower than the other two (see Section IV.1). Thus we do not recommend using the A3 amplitude in the SF projector method. Hereafter, we refer to (29) with either (34) or (36) as “the SF method”.
III.2 SF Projector with Trapezoid/Rectangle Function (SF-TR)
Inspired by the shapes of the true footprints associated with small cone angles (see the first two columns of FIG. 2), we approximate them as 2D separable functions with trapezoid functions in the transaxial direction and rectangular functions in the axial direction. This approximation is reasonable for typical multi-slice cone-beam geometries, where the azimuthal angles φ of rays cover the entire 360° range since the X-ray source rotates around the z axis, whereas the polar angles θ of rays are small (less than 2°) since the cone angle is small.
The approximating function in the s direction is




  
    
      
        
          
            q
            1
          
          ⁡
          
            (
            
              s
              ;
              β
              ;
              
                n
                →
              
            
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            trap
            ⁡
            
              (
              
                
                  s
                  ;
                  
                    τ
                    0
                  
                
                ,
                
                  τ
                  1
                
                ,
                
                  τ
                  2
                
                ,
                
                  τ
                  3
                
              
              )
            
          
          ⁢
          
            

          
          ⁢
          
            
          
          =
          
            {
            
              
                
                  
                    
                      
                        s
                        -
                        
                          τ
                          0
                        
                      
                      
                        
                          τ
                          1
                        
                        -
                        
                          τ
                          0
                        
                      
                    
                    ,
                  
                
                
                  
                    
                      τ
                      0
                    
                    <
                    s
                    <
                    
                      τ
                      1
                    
                  
                
              
              
                
                  
                    1
                    ,
                  
                
                
                  
                    
                      τ
                      1
                    
                    ≤
                    s
                    ≤
                    
                      τ
                      2
                    
                  
                
              
              
                
                  
                    
                      
                        
                          τ
                          3
                        
                        -
                        s
                      
                      
                        
                          τ
                          3
                        
                        -
                        
                          τ
                          2
                        
                      
                    
                    ,
                  
                
                
                  
                    
                      τ
                      2
                    
                    <
                    s
                    <
                    
                      τ
                      3
                    
                  
                
              
              
                
                  
                    0
                    ,
                  
                
                
                  
                    otherwise
                    ,
                  
                
              
            
          
        
      
    
    
      
        (
        38
        )
      
    
  




where τ0, τ1, τ2 and τ3 denote vertices of the trapezoid function that we choose to match the exact locations of those of the true footprint function in the s direction. They are the projected s coordinates of four corner points located at (c1[{right arrow over (n)}]±Δ1/2, c2[{right arrow over (n)}]±Δ2/2) for all z.

The approximating function in the t direction is




  
    
      
        
          
            
              q
              2
            
            ⁡
            
              (
              
                t
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            rect
            ⁡
            
              (
              
                
                  t
                  -
                  
                    t
                    0
                  
                
                
                  w
                  
                    t
                    ⁢
                    
                      
                    
                    ⁢
                    0
                  
                
              
              )
            
          
        
        ,
        
          

        
        ⁢
        where
      
    
    
      
        (
        39
        )
      
    
  
  
    
      
        
          
            t
            0
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              
                t
                +
              
              +
              
                t
                -
              
            
            2
          
        
        ,
        
          

        
        ⁢
        
          
            w
            
              t
              ⁢
              
                
              
              ⁢
              0
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            
              t
              +
            
            -
            
              t
              -
            
          
        
        ,
      
    
    
      
        (
        40
        )
      
    
  




where t+ and t− denote the boundaries of the rectangular function which we choose to be the projected t coordinates of the two endpoints of the axial midline of the voxel. Those endpoints are located at {right arrow over (c)}[{right arrow over (n)}]±(0, 0, Δ3/2). Given β and a point {right arrow over (x)}=(x, y, z), the projected s and t coordinate of this point can be computed by (9) and (11). Since the boundaries of the separable function are determined by the projections of boundaries of the voxel basis function under the cone-beam geometry, the depth-dependent magnification is accurately modeled.

The blurred footprint functions (30) of this SF-TR projector are




  
    
      
        
          
            
              F
              1
            
            ⁡
            
              (
              
                
                  s
                  k
                
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          =
          
            
              1
              
                r
                s
              
            
            ⁢
            
              γ
              ⁡
              
                (
                
                  
                    
                      s
                      k
                    
                    -
                    
                      
                        r
                        s
                      
                      2
                    
                  
                  ,
                  
                    
                      s
                      k
                    
                    +
                    
                      
                        r
                        s
                      
                      2
                    
                  
                
                )
              
            
          
        
        ,
        
          

        
        ⁢
        and
      
    
    
      
        (
        41
        )
      
    
  
  
    
      
        
          
            
              
                F
                2
              
              ⁡
              
                (
                
                  
                    t
                    l
                  
                  ;
                  β
                  ;
                  
                    n
                    →
                  
                
                )
              
            
            =
            
              
                
                  1
                  
                    r
                    t
                  
                
                ⁡
                
                  [
                  
                    
                      min
                      ⁡
                      
                        (
                        
                          
                            
                              t
                              l
                            
                            +
                            
                              
                                r
                                t
                              
                              2
                            
                          
                          ,
                          
                            t
                            +
                          
                        
                        )
                      
                    
                    -
                    
                      max
                      ⁡
                      
                        (
                        
                          
                            
                              t
                              l
                            
                            -
                            
                              
                                r
                                t
                              
                              2
                            
                          
                          ,
                          
                            t
                            -
                          
                        
                        )
                      
                    
                  
                  ]
                
              
              +
            
          
          ,
          
            

          
          ⁢
          where
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                
                  γ
                  ⁡
                  
                    (
                    
                      
                        s
                        1
                      
                      ,
                      
                        s
                        2
                      
                    
                    )
                  
                
                ⁢
                
                  =
                  Δ
                
                ⁢
                
                ⁢
                
                  
                    ∫
                    
                      s
                      1
                    
                    
                      s
                      2
                    
                  
                  ⁢
                  
                    
                      traps
                      ⁡
                      
                        (
                        
                          
                            s
                            ;
                            
                              τ
                              0
                            
                          
                          ,
                          
                            τ
                            1
                          
                          ,
                          
                            τ
                            2
                          
                          ,
                          
                            τ
                            3
                          
                        
                        )
                      
                    
                    ⁢
                    
                      d
                      s
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    
                      γ
                      1
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      (
                      
                        
                          max
                          ⁡
                          
                            (
                            
                              
                                s
                                1
                              
                              ,
                              
                                τ
                                0
                              
                            
                            )
                          
                        
                        ,
                        
                          min
                          ⁡
                          
                            (
                            
                              
                                s
                                2
                              
                              ,
                              
                                τ
                                1
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      γ
                      2
                    
                    ⁡
                    
                      (
                      
                        
                          max
                          ⁡
                          
                            (
                            
                              
                                s
                                1
                              
                              ,
                              
                                τ
                                1
                              
                            
                            )
                          
                        
                        ,
                        
                          min
                          ⁡
                          
                            (
                            
                              
                                s
                                2
                              
                              ,
                              
                                τ
                                2
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      γ
                      3
                    
                    ⁡
                    
                      (
                      
                        
                          max
                          ⁡
                          
                            (
                            
                              
                                s
                                1
                              
                              ,
                              
                                τ
                                2
                              
                            
                            )
                          
                        
                        ,
                        
                          min
                          ⁡
                          
                            (
                            
                              
                                s
                                2
                              
                              ,
                              
                                τ
                                3
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                  ,
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                γ
                1
              
              (
              
                
                  b
                  1
                
                ,
                
                  b
                  2
                
              
              ⁢
              
                
              
              )
            
            ⁢
            
              =
              Δ
            
            ⁢
            
              
                
                  1
                  
                    2
                    ⁢
                    
                      (
                      
                        
                          τ
                          1
                        
                        -
                        
                          τ
                          0
                        
                      
                      )
                    
                  
                
                ⁡
                
                  [
                  
                    
                      
                        (
                        
                          
                            b
                            2
                          
                          -
                          
                            τ
                            0
                          
                        
                        )
                      
                      2
                    
                    -
                    
                      
                        (
                        
                          
                            b
                            1
                          
                          -
                          
                            τ
                            0
                          
                        
                        )
                      
                      2
                    
                  
                  ]
                
              
              ⁢
              
                1
                
                  {
                  
                    
                      b
                      2
                    
                    >
                    
                      b
                      1
                    
                  
                  }
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              
                γ
                2
              
              ⁡
              
                (
                
                  
                    b
                    1
                  
                  ,
                  
                    b
                    2
                  
                
                )
              
            
            ⁢
            
              =
              Δ
            
            ⁢
            
              
                (
                
                  
                    b
                    2
                  
                  -
                  
                    b
                    1
                  
                
                )
              
              ⁢
              
                1
                
                  {
                  
                    
                      b
                      2
                    
                    >
                    
                      b
                      1
                    
                  
                  }
                
              
            
          
          ,
        
      
    
    
      
        (
        42
        )
      
    
  
  
    
      
        
          
            γ
            3
          
          ⁡
          
            (
            
              
                b
                1
              
              ,
              
                b
                2
              
            
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            
              1
              
                2
                ⁢
                
                  (
                  
                    
                      τ
                      3
                    
                    -
                    
                      τ
                      2
                    
                  
                  )
                
              
            
            ⁡
            
              [
              
                
                  
                    (
                    
                      
                        b
                        1
                      
                      -
                      
                        τ
                        3
                      
                    
                    )
                  
                  2
                
                -
                
                  
                    (
                    
                      
                        b
                        2
                      
                      -
                      
                        τ
                        3
                      
                    
                    )
                  
                  2
                
              
              ]
            
          
          ⁢
          
            
              1
              
                {
                
                  
                    b
                    2
                  
                  >
                  
                    b
                    1
                  
                
                }
              
            
            .
          
        
      
    
    
      
        (
        43
        )
      
    
  




III.3 SF Projector with Trapezoid/Trapezoid Function (SF-TT)

Inspired by the shape of true footprint of a voxel associated with large cone angles (see the last column of FIG. 2), we approximate it as a 2D separable function with trapezoid functions in both the transaxial and axial direction. This trapezoid approximation in axial direction is reasonable for cone-beam geometries with large cone angles (>10°) such as flat-panel detector geometries.
Along s, the SF-TT projector uses the same trapezoid approximation as the SF-TR projector. The trapezoid footprint and the blurred footprint are given in (38) and (41).
The approximated footprint function in t is




  
    
      
        
          
            
              q
              2
            
            ⁡
            
              (
              
                t
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          ⁢
          
            =
            Δ
          
          ⁢
          
            trap
            ⁡
            
              (
              
                
                  t
                  ;
                  
                    ξ
                    0
                  
                
                ,
                
                  ξ
                  1
                
                ,
                
                  ξ
                  2
                
                ,
                
                  ξ
                  3
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        44
        )
      
    
  




where ξ0, ξ1, ξ2 and ξ3 denote vertices of the trapezoid function. ξ0 and ξ1 are the smallest and largest one of the projected t coordinates of the lower four corners of the {right arrow over (n)}th voxel located at (c1[{right arrow over (n)}]±Δ1/2, c2[{right arrow over (n)}]±Δ2/2, c3[{right arrow over (n)}]−Δ3/2), and ξ2 and ξ3 are the smallest and largest one of the projected t coordinates of the upper four corners located at (c1[{right arrow over (n)}]±Δ1/2, c2[{right arrow over (n)}]±Δ2/2, c3[{right arrow over (n)}]+Δ3/2). The blurred footprint function in t is





  
    
      
        
          
            
              F
              2
            
            ⁡
            
              (
              
                
                  t
                  l
                
                ;
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          =
          
            
              1
              
                r
                t
              
            
            ⁢
            
              γ
              ⁡
              
                (
                
                  
                    
                      t
                      l
                    
                    -
                    
                      
                        r
                        t
                      
                      2
                    
                  
                  ,
                  
                    
                      t
                      l
                    
                    +
                    
                      
                        r
                        t
                      
                      2
                    
                  
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        45
        )
      
    
  




where γ is given in (43).

By choosing the vertices of the approximating footprints to match the projections of the voxel boundaries, the approximation adapts to the relative positions of the source, voxels and detector, as true footprints do. Take a voxel centered at the origin as an example. Its axial footprint is approximately a rectangular function (see the left figure in the third row of FIG. 2), instead of a trapezoid function. For this voxel trap(t; ξ0, ξ1, ξ2, ξ3) is almost a rectangle because ξ0≈ξ1 and ξ2≈ξ3 because ξ0, ξ1, ξ2, and ξ3 are the projected t coordinates of four axial boundaries of this voxel.
III.4 Implementation of SF Projector
We use the system matrix model (18) with the separable footprint approach (29) for both forward and back projection, which ensures that the SF forward and back projector are exact adjoint operators of each other.







TABLE 1





Pseudo-code for the SF-TR forward projector with the A1


amplitude method (SF-TR-A1) and the A2 method (SF-TR-A2).
















•
Initialize projection view array to zero, i.e., yβ[sk, tl] = 0 for k = 0, . . . , Ns − 1 and



l = 0, . . . , Nt − 1


•
For each row n1 = 0, 1, . . . , N1 − 1 of f[{right arrow over (n)}]:









1. For each column n2 = 0, 1, . . . , N2 − 1:










(a)
Compute trapezoid vertices τ0, τ1, τ2, τ3 in (38) using (9).



(b)
Determine indices (sk values) of detector cells that intersect [τ0, τ3], i.e.









{k : [sk − rs/2, sk + rs/2] ∩ [τ0, τ3] ≠ ∅}.










(c)
Compute transaxial footprint F1 (sk ; β; {right arrow over (n)}) using (41) and (43) for all these









sk values and store them.










(d)
Compute lφ0 using (32) (SF-TR-A2 only)



(e)
For each slice n3 = 0, 1, . . . , N3 − 1:










 i.
Determine indices (tl values) of detector cells that intersect [t−, t+],









i.e., {l : [tl − rt/2, tl + rt/2] ∩ [t−, t+] ≠ ∅}.










ii.
For each tl value:










A.
Compute F2(tl; β; {right arrow over (n)}) using (42).



B.
For each sk value:










-
Compute projection p(sk, tl; β; {right arrow over (n)}) where









p = f[{right arrow over (n)}] F1 (sk; β; {right arrow over (n)}) F2(tl; β; {right arrow over (n)}) for SF-TR-A1 ,



p = f[{right arrow over (n)}]lφ0 F1 (sk; β; {right arrow over (n)}) F2(tl; β; {right arrow over (n)}) for SF-TR-A2.










-
Update projection view yβ[sk, tl] + = p.








•
Scale all the projection view by l1 (sk, tl; β) using (36) for SF-TR-A1 or by lθ(sk,tl)



using (35) for SF-TR-A2 .









Table 1 summaries the SF-TR projector with the A1 amplitude method (SF-TR-A1) and with the A2 method (SF-TR-A2) for a given projection view angle β. Implementing the SF-TT projector with these two amplitude methods is similar. Implementation of the back-projector is similar, except for scaling the projections at the beginning instead of the end. The key to efficient implementation of this method is to make the inner loop over z (or equivalently over tl), because the values of F1(sk; β; {right arrow over (n)}) are independent of z and tl so they are precomputed prior to that loop. Because (11) is linear in z, the first value of t± for a given (x, y) position can be computed prior to the inner loop over z, and subsequent values can be computed by simple incremental updates. Thus only simple arithmetic operations and conditionals are needed for evaluating F2(tl; β; {right arrow over (n)}) in that inner loop; all trigonometric computations occur outside that loop. Note that this separable footprint approach does not appear to be particularly advantageous for 2D fan-beam forward and backprojection because computing the transaxial footprint F1(sk; β; {right arrow over (n)}) requires trigonometric operations. The compute efficiency here comes from the simple rectangular footprint approximation in the axial direction. More computation is needed for the SF-TT method because it uses trapezoids in the axial direction instead rectangles.
The implementation of amplitude l(sk, tl; β; {right arrow over (n)}) in (29) for the A1 and A2 methods are different. For the A1 method, for each β the amplitude l1(sk, tl; β) is implemented by scaling projections outside the loop over voxels since it depends on detector cells only. For the A2 method, we implemented the two terms (lφ0 and lθ(sk, tl) of l2(sk, t1; β; {right arrow over (n)}) separately. We scaled the projections by lθ(sk, tl) outside of the loop over voxels and computed lφ0 outside the inner loop over z since it does not depend on z.
The SF methods require O(N4) operations for forward/back projection of a N3 volume to/from N3 samples of the cone-beam projections. There exist O(N3 log N) methods for back-projection. However, those algorithms may not capture the distance-dependent effect of detector blur incorporated in the model (18). In 2D one can use the Fourier Slice Theorem to develop O(N2 log N) methods, but it is unclear how to generalize those to 3D axial and helical CT efficiently.
III.5 SF Compared with DD
The DD method essentially approximates the voxel footprints using rectangles in both directions on a common plane such as xz or yz plane. It also uses the separable and shift-invariant detector blur (21) on the detector plane. However, the approximated separable detector blurs on the common plane based on the mapped boundaries of original detector blurs are no longer shift invariant. This appears to prevent using the inner loop over sk that aids efficiency of the SF methods.
IV RESULTS
To evaluate our proposed SF-TR and ST-TT projectors, we compared them with the DD projector, a current start-of-the-art method. We compared their accuracy and speed as single modules and within iterative reconstruction methods.
IV.1 Forward and Back-Projector as Single Modules
We simulated an axial cone-beam flat-detector X-ray CT system with a detector size of Ns×Nt=512×512 cells spaced by ΔS=ΔT=1 mm with Nβ=984 angles over 360°. The source to detector distance Dsd is 949 mm, and the source to rotation center distance Ds0 is 541 mm. We included a rectangular detector response (21) with rs=ΔS and rt=ΔT.
We implemented the SF-TR and SF-TT projector in an ANSI C routine. The DD projector was provided by De Man et al., also implemented as ANSI C too. All used single precision. For both the SF methods and the DD method we used POSIX threads to parallelize the operations. For the forward projector each thread works on different projection views, whereas for the back projector each thread works on different image rows (n2).
IV.1.1 Maximum Errors of Forward Projectors
We define the maximum error as




  
    
      
        
          
            e
            ⁡
            
              (
              
                β
                ;
                
                  n
                  →
                
              
              )
            
          
          =
          
            
              max
              
                s
                ,
                
                  t
                  ∈
                  R
                
              
            
            ⁢
            
              
              
                
                  F
                  ⁡
                  
                    (
                    
                      s
                      ,
                      
                        t
                        ;
                        β
                        ;
                        
                          n
                          →
                        
                      
                    
                    )
                  
                
                -
                
                  
                    F
                    ap
                  
                  ⁡
                  
                    (
                    
                      s
                      ,
                      
                        t
                        ;
                        β
                        ;
                        
                          n
                          →
                        
                      
                    
                    )
                  
                
              
              
            
          
        
        ,
      
    
    
      
        (
        46
        )
      
    
  




where Fap is any of the approximate blurred footprints by the SF-TR, SF-TT and DD methods. We generated the true blurred footprint F(s, t; β; {right arrow over (n)}) in (19) by linearly averaging 1000×1000 analytical line integrals of rays sampled over each detector cell. We computed the line integral of each ray by the exact method described in (23).

We compared the maximum errors of these forward projectors for a voxel with Δ1=Δ2=Δ3=1 mm centered at the origin. Since the voxel is centered at the origins of all axes, we choose Nβ=180 angles over only 90° rotation. FIG. 3 shows the errors on a logarithmic scale. We compared the proposed three amplitude methods by combining them with the SF-TR projector. The errors of the A1 method are slightly larger than those of the A2 and A3 method; the biggest difference, at β=45°, is only 3.4×10−4. The error curves of the A2 and A3 methods overlap with each other. For the SF-TT projector, we plotted only the A1 and A2 methods because the combination of the SF-TT projector and A3 method is computationally much slower but only slightly improves accuracy. For the same amplitude method, the error curves of the SF-TR and SF-TT method overlap. The reason is that the rectangular and trapezoid approximation are very similar for a voxel centered at the origin of z axis. All the SF methods have smaller errors than the DD method, i.e., the maximum error of the DD projector is about 652 times larger than the proposed SF methods with the A1 amplitude, and 2.6×103 times larger than the SF methods with the A2 amplitude when β=45°.







TABLE 2







Speed comparison of DD, SF-TR and


SF-TT forward and back projectors.















SF-TR-
SF-TR-
SF-TR-
SF-TT-
SF-TT-


Projectors
DD
A1
A2
A3
A1
A2





Forward
46
35
35
59
91
91


time








Backward
49
44
45
63
92
93


time





The units are seconds.






FIG. 3 also compares the maximum errors of these forward projectors for a voxel centered at (100, 150, −100) mm. We choose Nβ=720 angles over 360° rotation. The error curves of the SF-TR projector with three amplitude methods overlap and the curves of the SF-TT projector with the A1 and A2 amplitude methods overlap with each other, demonstrating again that these three amplitude methods have similar accuracies. For voxels associated with large cone angles, the SF-TT projector is more accurate than the SF-TR projector. The maximum errors of the DD and SF-TR projector are about 13 and 3 times of that of the SF-TT projector respectively.
IV.1.2 Speed of Forward and Back-Projectors
We compared computation times of the DD, SF-TR and SF-TT forward and backward projectors using an image with a size of N1=512, N2=512, N3=128 and a spacing of Δ1=Δ2=Δ3=0.5 mm in the x, y, z direction respectively. We evaluated the elapsed time using the average of 5 projector runs on a 8-core Sun Fire X2270 server with 2.66 GHz Xeon X5500 processors. Because of the “hyperthreading” of these Nehalem cores, we used 16 POSIX threads. (We found that using 16 threads reduced computation time by only about 10% compared to using 8 threads.)
Table 2 summarizes the computation times. For the SF-TR projector, the A1 and A2 amplitude methods have similar speed, but the A3 method is about 50% slower. The computation times of the SF-TR and DD projector are about the same, whereas the SF-TT projector is about 2 times slower. Although execution times depend on code implementation, we expect SF-TR and DD to have fairly similar compute times because the inner loop over z involves similar simple arithmetic operations for both methods.
IV.2 Forward and Back-projectors within Iterative ROI Reconstruction
We compared the DD and SF projectors (SF-TR and SF-TT) with the A1 and A2 amplitude methods within iterative image reconstructions. The results of A1 and A2 methods were visually the same. For simplicity, we present the results of SF projectors with the A1 method.
IV.2.1 SF-TR vs. DD
In many cases, the region of interest (ROI) needed for diagnosis is much smaller than the scanner field of view (FOV). ROI reconstruction can save computation time and memory. Ziegler et al. (b) proposed the following approach for iterative reconstruction of a ROI.

    
    
        1. Iterative reconstruction of the whole FOV, yielding an initial estimate {circumflex over (x)}FOV of {circumflex over (x)}FOV which is the vector of basis coefficients of the object ƒ({right arrow over (x)}), i.e., ƒ[{right arrow over (n)}] in (14).
        2. Define {circumflex over (x)}FOVm={circumflex over (x)}FOV·m where m=(m1, . . . , mp) with 0≦mj≦1 (j=1, . . . , p) is a mask vector setting the estimated object, inside the ROI to zero and providing a smooth transition from the ROI to the remaining voxels.
        3. Compute pout=A{circumflex over (x)}FOVm which is the forward projection of the masked object {circumflex over (x)}FOVm.
        4. Compute the projection of ROI, proi=y−pout where y is the measured data.
        5. Iterative reconstruction of the ROI only from proi. Due to the transition zone, the region of this reconstruction needs to be extended slightly from the predetermined ROI.
    
    


This method requires accurate forward and back projectors. Errors in step 2, where re-projection of the masked image is computed, can greatly affect the results of subsequent iterative ROI reconstruction. Moreover, for general iterative image reconstruction, even small approximation errors might accumulate after many iterations. We evaluated the accuracy of our proposed SF-TR projector and the DD projector in this iterative ROI reconstruction method.
We simulated the geometry of a GE LightSpeed X-ray CT system with an arc detector of 888 detector channels for 64 slices (Ns=888, Nt=64) by Nβ=984 views over 360°. The size of each detector cell was ΔS×ΔT=1.0239×1.0964 mm2. The source to detector distance was Dsd=949.075 mm, and the source to rotation center distance was Ds0=541 mm. We included a quarter detector offset in the s direction to reduce aliasing.
We used a modified 3D Shepp-Logan digital phantom that has ellipsoids centered at the z=0 plane to evaluate the projectors. The brain-size field of view (FOV) was 250×250×40 mm3, sampled into 256×256×64 voxels with a coarse resolution of 0.9766×0.9766×0.6250 mm3.
We simulated noiseless cone-beam projection measurements from the Shepp-Logan phantom by linearly averaging 8×8 analytical rays sampled across each detector cell. Noiseless data is used because we want to focus on projector accuracy. We scaled the line integrals by a chosen factor to set their maximum value to about 5.
We chose a ROI centered at the rotation center that covered about 48.8×48.8×12.5 mm3 (50×50×20 voxels with the coarse resolution). The transition zone surrounds the ROI, and covers about 13.7×13.7×5 mm3 (14×14×8 voxels with the coarse resolution). To construct masked images {circumflex over (x)}FOVm, we removed the ROI and smoothly weighted the voxels corresponding to the transition zone by a 3D separable Gaussian function. FIG. 4 shows different views of xFOV with the transition zone superimposed on it in the first row.
We implemented iterative image reconstruction of the entire FOV with these two projector/backprojector methods. We ran 300 iterations of the conjugate gradient algorithm, initialized with reconstruction by the FDK method, for the following penalized weighted least-squares cost function with an edge-preserving penalty function (PWLS-CG):




  
    
      
        
          Φ
          ⁡
          
            (
            
              x
              FOV
            
            )
          
        
        =
        
          
            
              ∑
              i
            
            ⁢
            
              
                w
                i
              
              ⁢
              
                1
                2
              
              ⁢
              
                
                  (
                  
                    
                      y
                      i
                    
                    -
                    
                      
                        [
                        
                          Ax
                          FOV
                        
                        ]
                      
                      i
                    
                  
                  )
                
                2
              
            
          
          +
          
            β
            ⁢
            
              
            
            ⁢
            
              R
              ⁡
              
                (
                
                  x
                  FOV
                
                )
              
            
          
        
      
    
    
      
        (
        47
        )
      
    
  
  
    
      
        
          
            R
            ⁡
            
              (
              
                x
                FOV
              
              )
            
          
          =
          
            
              ∑
              k
            
            ⁢
            
              ψ
              ⁡
              
                (
                
                  
                    [
                    
                      Cx
                      FOV
                    
                    ]
                  
                  k
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        48
        )
      
    
  




where y, is the negative log of the measured cone-beam projection, wi values are statistical weighting factors, A is the system matrix, C is a differencing matrix and ψ(t) is the potential function. We used the hyperbola:





  
    
      
        
          ψ
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            
              δ
              2
            
            3
          
          ⁢
          
            
              (
              
                
                  
                    1
                    +
                    
                      3
                      ⁢
                      
                        
                          (
                          
                            t
                            δ
                          
                          )
                        
                        2
                      
                    
                  
                
                -
                1
              
              )
            
            .
          
        
      
    
    
      
        (
        49
        )
      
    
  




For this simulation, we used wi=exp(−yi), β=4 and δ=5 Hounsfield units (HU).

FIG. 5 shows axial views of the reconstructed images {circumflex over (x)}FOVSF-TR and {circumflex over (x)}FOVDD by the iterative method (PWLS-CG) using the SF-TR and DD method respectively. We computed the maximum error, maxj|{circumflex over (x)}j−xj|, and root-mean-square (RMS) error,




  
    
      
        1
        N
      
      ⁢
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          (
          
            
              
                x
                ^
              
              j
            
            -
            
              x
              j
            
          
          )
        
      
    
  
  .




The maximum and RMS errors of {circumflex over (x)}FOVSF-TR and {circumflex over (x)}FOVDD are close because the errors are dominated by the axial cone-beam artifacts due to the poor sampling (not truncation) at the off-axis slices, but the DD method causes artifacts that are obvious around the top and bottom areas. This figure illustrates that the SF method improves image quality for full FOV reconstruction with large basis functions (coarse resolution).

We applied the PWLS-CG iterative method mentioned above with β=1 and δ=1 HU to reconstruct estimated ROI images {circumflex over (x)}FOVSF-TR and {circumflex over (x)}ROIDD of 256×256×64 voxels with a fine resolution of 0.2441×0.2441×0.3125 mm3. The domains of {circumflex over (x)}ROISF-TR and {circumflex over (x)}ROIDD covered the ROI and transition zone (see FIG. 4). For this image geometry, we also generated a Shepp-Logan reference image xROI from the same ellipsoid parameters used to generate xFOV. FIG. 4 shows different views of xROI in the second row. The fine sampling of xROI is 1⁄4 and 1⁄2 of the coarse sampling of xFOV in the transaxial and axial direction respectively, and has a size of 200×200×40.
FIG. 6 shows the axial view of reconstructed images {circumflex over (x)}ROISF-TR and {circumflex over (x)}ROIDD by the iterative method (PWLS-CG) using the SF-TR and DD projector. The maximum errors are 20 HU and 105 HU for the SF and DD method respectively and the RMS errors are 1.6 HU and 2.8 HU. The SF-TR projector provides lower artifact levels than the DD projector. The rectangle approximation in the transaxial direction of the DD method resulted in larger errors in the reprojection step and caused more errors when resolution changed from coarse to fine. The rectangle approximation basically blurs corners of image voxels, and the level of blur varies for different image voxel sizes.
We also reconstructed full FOV images (not shown) at a fine resolution, i.e., 1024×1024×128 voxels with a spacing of 0.2441×0.2442×0.3125 mm3. There were no apparent artifacts in both reconstructed images using the SF-TR and DD method and the maximum and RMS errors were similar. It seems that the aliasing artifacts in the reconstruction by the DD method were removed by fine sampling. For smaller transaxial voxel sizes, the difference between the rectangular (DD method) and trapezoid (SF-TR) approximation becomes less visible.
IV.2.2 SF-TR Vs. SF-TT
We compared the SF-TR and SF-TT projectors by reconstructing an image under an axial cone-beam CT system with largest cone angle of 15° or so using these two methods. We expected to see differences in some off-axis slices of the reconstructed images because the trapezoid approximation of the SF-TT method is more realistic than the rectangle approximation of the SF-TR method especially for voxels far away from the origin. Nevertheless, we did not see obvious visual difference, and the maximum and RMS errors were similar. It appears that the axial cone-beam artifacts due to poor sampling (not truncation) at the off-axis slices dominate other effects in the reconstructed images, such as the errors caused by rectangle approximation. Further research will evaluate these two projectors within iterative reconstruction methods under other CT geometries where the off-axis sampling is better, such as helical scans, yet where the cone angle is large enough to differentiate the SF-TR and SF-TT method.
V CONCLUSION
We presented two new 3D forward and back projector for X-ray CT: SF-TR and SF-TT. Simulation results have shown that the SF-TR projector is more accurate with similar computation speed than the DD projector, and the SF-TT projector is more accurate but computationally slower than the SF-TR projector. The DD projector is particularly favorable relative to other previously published projectors in terms of the balance between speed and accuracy. The SF-TR method uses trapezoid functions in the transaxial direction and rectangular functions in the axial direction, while the SF-TT method uses trapezoid functions in both directions. The rectangular approximation in the axial direction is adequate for CT systems with small cone angles, such as the multi-slice geometries. The trapezoid approximation is more realistic for geometries with large cone angles, such as the flat-panel detector geometries. To balance accuracy and computation, we recommend to combine the SF-TR and SF-TT method, which is to use the SF-TR projector for voxels corresponding to small cone angles and to use the SF-TT projector for voxels corresponding to larger cone angles.
The model and simulations here considered an ideal point source. For a finite sized X-ray source there would be more blur and it is possible that the differences between the SF and DD methods would be smaller.
Approximating the footprint functions as 2D separable functions is the key innovation of this approach. Since the separability greatly simplifies the calculation of integrals of the footprint functions, using more accurate functions in the transaxial and axial direction is possible without complicating significantly the calculations.
The computational efficiency of the SF methods rely on the assumption that the vertical (t) axis of the detector plane is parallel to the rotation axis. If the detector plane is slightly rotated then slight interpolation would be needed to resample onto coordinates that are parallel to the rotation axis.
Although we focused on voxel basis functions in this disclosure, the idea of 2D separable footprint approximation could also be applied to other basis functions with separability in the axial and transaxial directions, with appropriate choices of functions.
The foregoing description of the embodiments has been provided for purposes of illustration and description. It is not intended to be exhaustive or to limit the disclosure. Individual elements or features of a particular embodiment are generally not limited to that particular embodiment, but, where applicable, are interchangeable and can be used in a selected embodiment, even if not specifically shown or described. The same may also be varied in many ways. Such variations are not to be regarded as a departure from the disclosure, and all such modifications are intended to be included within the scope of the disclosure.

## Claims

1. A processor-implemented method for forward and back projection for image construction, the method comprising:
computing projected coordinates of a plurality of 3D voxels on a detector surface;
approximating 2D footprints of said plurality of voxels as separable functions, said separable functions being a computational product of a 1D axial footprint function and a 1D transaxial footprint function;
approximating 2D detector blur as a computational product of a 1D axial blur function and a 1D transaxial blur function; and
determining the contribution of said plurality of voxels to detector cells or vice versa using computational sums and products of said 1D axial footprint function, said 1D transaxial footprint function, said 1D axial blur function, and said 1D transaxial blur function in accordance with said projected coordinates.

2. The method according to claim 1,
wherein said 1D transaxial footprint function comprises trapezoidal functions and said 1D axial footprint function comprises rectangular functions.

3. The method according to claim 1
wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises trapezoidal functions.

4. The method according to claim 1
wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises a combination of trapezoidal functions and rectangular functions.

5. The method according to claim 1, further comprising:
determining vertices of said 1D axial footprint function and said 1D transaxial footprint function using said projected coordinates of said plurality of 3D voxels.

6. The method according to claim 1 wherein parameters of the step of computing projected coordinates of said plurality of voxels comprises connecting a source and computing said projected coordinates in response to said boundaries of said plurality of voxels and said detector surface.

7. The method according to claim 1 wherein parameters of the step of determining the contribution of said plurality of voxels to detector cells or vice versa comprises:
computing 2D blurred footprints of said plurality of 3D voxels as computational products of 1D axial blurred footprints and 1D transaxial blurred footprints, said 1D axial blurred footprints being 1D convolutions of said 1D axial footprint functions and said 1D axial blur functions, said 1D transaxial blurred footprints being 1D convolutions of said 1D transaxial footprint functions and said 1D transaxial blur functions.

8. The method according to claim 1 wherein said determining the contribution of said plurality of voxels to said detector cells or vice versa comprises at least one of a forward projection and a back projection operation followed or preceded by detector-cell-dependent amplitude scaling factors.

9. The method according to claim 1 wherein the determining the contribution of said plurality of voxels to said detector cells or vice versa comprises at least one of a forward projection and a back projection operation followed or preceded by voxel-dependent scaling factors.

10. The method according to claim 1 wherein the determining the contribution of said plurality of voxels to said detector cells or vice versa comprises at least one of a forward projection and a back projection operation followed or preceded by a combination of detector-cell-dependent and voxel-dependent scaling factors.

11. A projector or back-projector system having a non-transitory computer readable medium encoded with an executable program for image reconstruction, said projector or back-projector system comprising:
a computational system using computational operations occurring separately in axial and transaxial directions that exploit the separability of approximation of a footprint function, said computational operations comprising:
computing projected coordinates of a plurality of 3D voxels on a detector surface;
approximating 2D footprints of said plurality of voxels as separable functions, said separable functions being a computational product of a 1D axial footprint function and a 1D transaxial footprint function;
approximating 2D detector blur as a computational product of a 1D axial blur function and a 1D transaxial blur function; and
determining the contribution of said plurality of voxels to detector cells or vice versa using computational sums and products of said 1D axial footprint function, said 1D transaxial footprint function, said 1D axial blur function, and said 1D transaxial blur function in accordance with said projected coordinates.

12. The system according to claim 11 wherein said computational operations occur separately and in parallel in axial and transaxial directions.

13. The system according to claim 11 wherein said 1D transaxial footprint function comprises trapezoidal functions and said 1D axial footprint function comprises rectangular functions.

14. The system according to claim 11 wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises trapezoidal functions.

15. The system according to claim 11 wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises rectangular functions.

16. The system according to claim 11 wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises a combination of trapezoidal functions and rectangular functions.

17. The method according to claim 1 wherein said 1D transaxial footprint function and said 1D axial footprint function each comprises rectangular functions.

18. The method according to claim 1 wherein said 1D axial blur function and said 1D transaxial blur function each comprises rectangular functions.