A fast and accurate Fourier algorithm for iterative parallel-beam tomography

Alexander H. Delaney, Yoram Bresler

Research output: Contribution to journalArticle

Abstract

We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires script O sign(N2 log N) floating-point operations per iteration to reconstruct an N x N image from P view angles, as compared to script O sign(N2P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary.

Original languageEnglish (US)
Pages (from-to)740-753
Number of pages14
JournalIEEE Transactions on Image Processing
Volume5
Issue number5
DOIs
StatePublished - Dec 1 1996

Fingerprint

Tomography
Floating point
Iteration
Angle
Convolution
Conjugate Gradient Algorithm
Aliasing
Weighted Least Squares
Fast Fourier transform
Series Expansion
Demonstrate
Half line
Fast Fourier transforms
Projection
Statistics
Minimise
Numerical Examples
Scenarios
Sampling
Formulation

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design
  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Computer Vision and Pattern Recognition

Cite this

A fast and accurate Fourier algorithm for iterative parallel-beam tomography. / Delaney, Alexander H.; Bresler, Yoram.

In: IEEE Transactions on Image Processing, Vol. 5, No. 5, 01.12.1996, p. 740-753.

Research output: Contribution to journalArticle

@article{508b53312db4446b8b46844ec7849205,
title = "A fast and accurate Fourier algorithm for iterative parallel-beam tomography",
abstract = "We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires script O sign(N2 log N) floating-point operations per iteration to reconstruct an N x N image from P view angles, as compared to script O sign(N2P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary.",
author = "Delaney, {Alexander H.} and Yoram Bresler",
year = "1996",
month = "12",
day = "1",
doi = "10.1109/83.495957",
language = "English (US)",
volume = "5",
pages = "740--753",
journal = "IEEE Transactions on Image Processing",
issn = "1057-7149",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",

}

TY - JOUR

T1 - A fast and accurate Fourier algorithm for iterative parallel-beam tomography

AU - Delaney, Alexander H.

AU - Bresler, Yoram

PY - 1996/12/1

Y1 - 1996/12/1

N2 - We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires script O sign(N2 log N) floating-point operations per iteration to reconstruct an N x N image from P view angles, as compared to script O sign(N2P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary.

AB - We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires script O sign(N2 log N) floating-point operations per iteration to reconstruct an N x N image from P view angles, as compared to script O sign(N2P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary.

UR - http://www.scopus.com/inward/record.url?scp=0030151068&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030151068&partnerID=8YFLogxK

U2 - 10.1109/83.495957

DO - 10.1109/83.495957

M3 - Article

C2 - 18285163

AN - SCOPUS:0030151068

VL - 5

SP - 740

EP - 753

JO - IEEE Transactions on Image Processing

JF - IEEE Transactions on Image Processing

SN - 1057-7149

IS - 5

ER -