Shear-based fast hierarchical backprojection for parallel-beam tomography

Ashvin K. George; Yoram Bresler

doi:10.1109/TMI.2006.887370

Shear-based fast hierarchical backprojection for parallel-beam tomography

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a family of fast algorithms for 2-D parallel-beam tomographic backprojection. They aggregate the projections in a hierarchical structure involving the shearing and addition of sparsely sampled images. The algorithms achieve a computational cost of O(N² log P), when backprojecting an N × N pixel image from P projections. The algorithms provide a systematic means, guided by a Fourier-domain interpretation, to adjust and optimize the tradeoff between computational cost and accuracy. In an example with N = 512 and P = 1458 the algorithms provide high accuracy, with more than an order of magnitude reduction in operation counts.

Original language	English (US)
Pages (from-to)	317-334
Number of pages	18
Journal	IEEE transactions on medical imaging
Volume	26
Issue number	3
DOIs	https://doi.org/10.1109/TMI.2006.887370
State	Published - Mar 2007

Keywords

Backprojection
Fast algorithm
Image shear
Radon transform
Spline interpolation
Tomography

ASJC Scopus subject areas

Biomedical Engineering
Radiology Nuclear Medicine and imaging
Radiological and Ultrasound Technology
Electrical and Electronic Engineering
Computer Science Applications
Computational Theory and Mathematics

Online availability

10.1109/TMI.2006.887370

Library availability

Discover UIUC Full Text

Cite this

@article{8f0a320872d14be9b4d2e2b72cb7e2fa,

title = "Shear-based fast hierarchical backprojection for parallel-beam tomography",

abstract = "We introduce a family of fast algorithms for 2-D parallel-beam tomographic backprojection. They aggregate the projections in a hierarchical structure involving the shearing and addition of sparsely sampled images. The algorithms achieve a computational cost of O(N2 log P), when backprojecting an N × N pixel image from P projections. The algorithms provide a systematic means, guided by a Fourier-domain interpretation, to adjust and optimize the tradeoff between computational cost and accuracy. In an example with N = 512 and P = 1458 the algorithms provide high accuracy, with more than an order of magnitude reduction in operation counts.",

keywords = "Backprojection, Fast algorithm, Image shear, Radon transform, Spline interpolation, Tomography",

author = "George, {Ashvin K.} and Yoram Bresler",

note = "Funding Information: Manuscript received June 28, 2006; revised October 18, 2006. This work was supported in part by National Science Foundation under Grant CCR 99-72980 and Grant CCR 02-09203. Asterisk indicates corresponding author. *A. K. George is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: akgeorge@uiuc. edu). Y. Bresler is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: ybresler@uiuc.edu). Digital Object Identifier 10.1109/TMI.2006.887370",

year = "2007",

month = mar,

doi = "10.1109/TMI.2006.887370",

language = "English (US)",

volume = "26",

pages = "317--334",

journal = "IEEE Transactions on Medical Imaging",

issn = "0278-0062",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Shear-based fast hierarchical backprojection for parallel-beam tomography

AU - George, Ashvin K.

AU - Bresler, Yoram

N1 - Funding Information: Manuscript received June 28, 2006; revised October 18, 2006. This work was supported in part by National Science Foundation under Grant CCR 99-72980 and Grant CCR 02-09203. Asterisk indicates corresponding author. *A. K. George is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: akgeorge@uiuc. edu). Y. Bresler is with the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: ybresler@uiuc.edu). Digital Object Identifier 10.1109/TMI.2006.887370

PY - 2007/3

Y1 - 2007/3

N2 - We introduce a family of fast algorithms for 2-D parallel-beam tomographic backprojection. They aggregate the projections in a hierarchical structure involving the shearing and addition of sparsely sampled images. The algorithms achieve a computational cost of O(N2 log P), when backprojecting an N × N pixel image from P projections. The algorithms provide a systematic means, guided by a Fourier-domain interpretation, to adjust and optimize the tradeoff between computational cost and accuracy. In an example with N = 512 and P = 1458 the algorithms provide high accuracy, with more than an order of magnitude reduction in operation counts.

AB - We introduce a family of fast algorithms for 2-D parallel-beam tomographic backprojection. They aggregate the projections in a hierarchical structure involving the shearing and addition of sparsely sampled images. The algorithms achieve a computational cost of O(N2 log P), when backprojecting an N × N pixel image from P projections. The algorithms provide a systematic means, guided by a Fourier-domain interpretation, to adjust and optimize the tradeoff between computational cost and accuracy. In an example with N = 512 and P = 1458 the algorithms provide high accuracy, with more than an order of magnitude reduction in operation counts.

KW - Backprojection

KW - Fast algorithm

KW - Image shear

KW - Radon transform

KW - Spline interpolation

KW - Tomography

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

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

U2 - 10.1109/TMI.2006.887370

DO - 10.1109/TMI.2006.887370

M3 - Article

C2 - 17354638

AN - SCOPUS:33847768007

SN - 0278-0062

VL - 26

SP - 317

EP - 334

JO - IEEE Transactions on Medical Imaging

JF - IEEE Transactions on Medical Imaging

IS - 3

ER -

Shear-based fast hierarchical backprojection for parallel-beam tomography

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this