O(N2 log N) native fan-beam tomographic reconstruction

Shu Xiao; Yoram Bresler; David C. Munson

doi:10.1109/ISBI.2002.1029386

O(N² log N) native fan-beam tomographic reconstruction

Shu Xiao, Yoram Bresler, David C. Munson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a new fast backprojection algorithm for CT fan-beam reconstruction. The new algorithm operates directly on fan-beam data without prior rebinning to parallel-beam projections. The algorithm reduces the computational complexity from O(N³) for the traditional fan-beam algorithm to O(N² log N). Simulations demonstrate speedups of greater than 50-fold for a 512 × 512 image, with no perceivable degradation in accuracy. The algorithm also applies to multi-slice helical 3D reconstruction, and extends to 3D cone-beam reconstruction.

Original language	English (US)
Title of host publication	2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings
Publisher	IEEE Computer Society
Pages	824-827
Number of pages	4
ISBN (Electronic)	078037584X
DOIs	https://doi.org/10.1109/ISBI.2002.1029386
State	Published - 2002
Event	IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Washington, United States Duration: Jul 7 2002 → Jul 10 2002

Publication series

Name	Proceedings - International Symposium on Biomedical Imaging
Volume	2002-January
ISSN (Print)	1945-7928
ISSN (Electronic)	1945-8452

Other

Other	IEEE International Symposium on Biomedical Imaging, ISBI 2002
Country/Territory	United States
City	Washington
Period	7/7/02 → 7/10/02

ASJC Scopus subject areas

Biomedical Engineering
Radiology Nuclear Medicine and imaging

Online availability

10.1109/ISBI.2002.1029386

Library availability

Discover UIUC Full Text

Cite this

O(N² log N) native fan-beam tomographic reconstruction. / Xiao, Shu; Bresler, Yoram; Munson, David C.
2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings. IEEE Computer Society, 2002. p. 824-827 1029386 (Proceedings - International Symposium on Biomedical Imaging; Vol. 2002-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Xiao, S, Bresler, Y & Munson, DC 2002, O(N² log N) native fan-beam tomographic reconstruction. in 2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings., 1029386, Proceedings - International Symposium on Biomedical Imaging, vol. 2002-January, IEEE Computer Society, pp. 824-827, IEEE International Symposium on Biomedical Imaging, ISBI 2002, Washington, United States, 7/7/02. https://doi.org/10.1109/ISBI.2002.1029386

@inproceedings{64c4a71b92134cc0bcdd525bad3c2e5c,

title = "O(N2 log N) native fan-beam tomographic reconstruction",

abstract = "We present a new fast backprojection algorithm for CT fan-beam reconstruction. The new algorithm operates directly on fan-beam data without prior rebinning to parallel-beam projections. The algorithm reduces the computational complexity from O(N3) for the traditional fan-beam algorithm to O(N2 log N). Simulations demonstrate speedups of greater than 50-fold for a 512 × 512 image, with no perceivable degradation in accuracy. The algorithm also applies to multi-slice helical 3D reconstruction, and extends to 3D cone-beam reconstruction.",

author = "Shu Xiao and Yoram Bresler and Munson, {David C.}",

note = "Publisher Copyright: {\textcopyright} 2002 IEEE. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.; IEEE International Symposium on Biomedical Imaging, ISBI 2002 ; Conference date: 07-07-2002 Through 10-07-2002",

year = "2002",

doi = "10.1109/ISBI.2002.1029386",

language = "English (US)",

series = "Proceedings - International Symposium on Biomedical Imaging",

publisher = "IEEE Computer Society",

pages = "824--827",

booktitle = "2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings",

}

TY - GEN

T1 - O(N2 log N) native fan-beam tomographic reconstruction

AU - Xiao, Shu

AU - Bresler, Yoram

AU - Munson, David C.

PY - 2002

Y1 - 2002

N2 - We present a new fast backprojection algorithm for CT fan-beam reconstruction. The new algorithm operates directly on fan-beam data without prior rebinning to parallel-beam projections. The algorithm reduces the computational complexity from O(N3) for the traditional fan-beam algorithm to O(N2 log N). Simulations demonstrate speedups of greater than 50-fold for a 512 × 512 image, with no perceivable degradation in accuracy. The algorithm also applies to multi-slice helical 3D reconstruction, and extends to 3D cone-beam reconstruction.

AB - We present a new fast backprojection algorithm for CT fan-beam reconstruction. The new algorithm operates directly on fan-beam data without prior rebinning to parallel-beam projections. The algorithm reduces the computational complexity from O(N3) for the traditional fan-beam algorithm to O(N2 log N). Simulations demonstrate speedups of greater than 50-fold for a 512 × 512 image, with no perceivable degradation in accuracy. The algorithm also applies to multi-slice helical 3D reconstruction, and extends to 3D cone-beam reconstruction.

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

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

U2 - 10.1109/ISBI.2002.1029386

DO - 10.1109/ISBI.2002.1029386

M3 - Conference contribution

AN - SCOPUS:0344044972

T3 - Proceedings - International Symposium on Biomedical Imaging

SP - 824

EP - 827

BT - 2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings

PB - IEEE Computer Society

T2 - IEEE International Symposium on Biomedical Imaging, ISBI 2002

Y2 - 7 July 2002 through 10 July 2002

ER -