O(N 3 log N) backprojection algorithm for the 3-D radon transform

Samit Basu; Yoram Bresler

doi:10.1109/42.993127

O(N ³ log N) backprojection algorithm for the 3-D radon transform

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

Abstract

We present a novel backprojection algorithm for three-dimensional (3-D) radon transform data that requires O(N ³ log ₂ N) operations for reconstruction of an N × N × N volume from O(N ²) plane-integral projections. Our algorithm uses a hierarchical decomposition of the 3-D radon transform to recursively decompose the backprojection operation. Simulations are presented demonstrating reconstruction quality comparable to the standard filtered backprojection, which requires O(N ⁵) computations under the same circumstances.

Original language	English (US)
Pages (from-to)	76-88
Number of pages	13
Journal	IEEE transactions on medical imaging
Volume	21
Issue number	2
DOIs	https://doi.org/10.1109/42.993127
State	Published - Feb 2002

Keywords

3-D radon transform
Backprojection
Cone beam tomography
Fast algorithm
Hierarchical

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/42.993127

Library availability

Discover UIUC Full Text

Cite this

@article{d1d72765971443a7b48cfab2ba40358b,

title = "O(N 3 log N) backprojection algorithm for the 3-D radon transform",

abstract = "We present a novel backprojection algorithm for three-dimensional (3-D) radon transform data that requires O(N 3 log 2 N) operations for reconstruction of an N × N × N volume from O(N 2) plane-integral projections. Our algorithm uses a hierarchical decomposition of the 3-D radon transform to recursively decompose the backprojection operation. Simulations are presented demonstrating reconstruction quality comparable to the standard filtered backprojection, which requires O(N 5) computations under the same circumstances.",

keywords = "3-D radon transform, Backprojection, Cone beam tomography, Fast algorithm, Hierarchical",

author = "Samit Basu and Yoram Bresler",

note = "Funding Information: Manuscript received February 17, 2000; revised December 14, 2001. This work was supported in part by the National Science Foundation (NSF) under Grant CCR 99-72980 and under Research Infrastructure Grant CDA 96-24396, in part by a Fellowship from the Joint Services Electronics Program, in part by the Mac VanValkenburg Graduate Fellowship, and in part by the National Computational Science Alliance under Grant ASC9900024N using the NCSA SGI/CRAY Origin2000. The Associate Editor responsible for coordinating the review of this paper and recommending its publication was C. Crawford. Asterisk indicates corresponding author.",

year = "2002",

month = feb,

doi = "10.1109/42.993127",

language = "English (US)",

volume = "21",

pages = "76--88",

journal = "IEEE transactions on medical imaging",

issn = "0278-0062",

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

number = "2",

}

TY - JOUR

T1 - O(N 3 log N) backprojection algorithm for the 3-D radon transform

AU - Basu, Samit

AU - Bresler, Yoram

N1 - Funding Information: Manuscript received February 17, 2000; revised December 14, 2001. This work was supported in part by the National Science Foundation (NSF) under Grant CCR 99-72980 and under Research Infrastructure Grant CDA 96-24396, in part by a Fellowship from the Joint Services Electronics Program, in part by the Mac VanValkenburg Graduate Fellowship, and in part by the National Computational Science Alliance under Grant ASC9900024N using the NCSA SGI/CRAY Origin2000. The Associate Editor responsible for coordinating the review of this paper and recommending its publication was C. Crawford. Asterisk indicates corresponding author.

PY - 2002/2

Y1 - 2002/2

N2 - We present a novel backprojection algorithm for three-dimensional (3-D) radon transform data that requires O(N 3 log 2 N) operations for reconstruction of an N × N × N volume from O(N 2) plane-integral projections. Our algorithm uses a hierarchical decomposition of the 3-D radon transform to recursively decompose the backprojection operation. Simulations are presented demonstrating reconstruction quality comparable to the standard filtered backprojection, which requires O(N 5) computations under the same circumstances.

AB - We present a novel backprojection algorithm for three-dimensional (3-D) radon transform data that requires O(N 3 log 2 N) operations for reconstruction of an N × N × N volume from O(N 2) plane-integral projections. Our algorithm uses a hierarchical decomposition of the 3-D radon transform to recursively decompose the backprojection operation. Simulations are presented demonstrating reconstruction quality comparable to the standard filtered backprojection, which requires O(N 5) computations under the same circumstances.

KW - 3-D radon transform

KW - Backprojection

KW - Cone beam tomography

KW - Fast algorithm

KW - Hierarchical

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

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

U2 - 10.1109/42.993127

DO - 10.1109/42.993127

M3 - Article

C2 - 11929107

AN - SCOPUS:0036462552

SN - 0278-0062

VL - 21

SP - 76

EP - 88

JO - IEEE transactions on medical imaging

JF - IEEE transactions on medical imaging

IS - 2

ER -