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

Shu Xiao, Yoram Bresler, David C. Munson

Research output: Chapter in Book/Report/Conference proceedingConference 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(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.

Original languageEnglish (US)
Title of host publication2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings
PublisherIEEE Computer Society
Pages824-827
Number of pages4
ISBN (Electronic)078037584X
DOIs
StatePublished - Jan 1 2002
EventIEEE International Symposium on Biomedical Imaging, ISBI 2002 - Washington, United States
Duration: Jul 7 2002Jul 10 2002

Publication series

NameProceedings - International Symposium on Biomedical Imaging
Volume2002-January
ISSN (Print)1945-7928
ISSN (Electronic)1945-8452

Other

OtherIEEE International Symposium on Biomedical Imaging, ISBI 2002
CountryUnited States
CityWashington
Period7/7/027/10/02

Fingerprint

Fans
Cones
Computational complexity
Degradation

ASJC Scopus subject areas

  • Biomedical Engineering
  • Radiology Nuclear Medicine and imaging

Cite this

Xiao, S., Bresler, Y., & Munson, D. C. (2002). O(N2 log N) native fan-beam tomographic reconstruction. In 2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings (pp. 824-827). [1029386] (Proceedings - International Symposium on Biomedical Imaging; Vol. 2002-January). IEEE Computer Society. https://doi.org/10.1109/ISBI.2002.1029386

O(N2 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 proceedingConference contribution

Xiao, S, Bresler, Y & Munson, DC 2002, O(N2 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
Xiao S, Bresler Y, Munson DC. O(N2 log N) native fan-beam tomographic reconstruction. In 2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings. IEEE Computer Society. 2002. p. 824-827. 1029386. (Proceedings - International Symposium on Biomedical Imaging). https://doi.org/10.1109/ISBI.2002.1029386
Xiao, Shu ; Bresler, Yoram ; Munson, David C. / O(N2 log N) native fan-beam tomographic reconstruction. 2002 IEEE International Symposium on Biomedical Imaging, ISBI 2002 - Proceedings. IEEE Computer Society, 2002. pp. 824-827 (Proceedings - International Symposium on Biomedical Imaging).
@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.}",
year = "2002",
month = "1",
day = "1",
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/1/1

Y1 - 2002/1/1

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

ER -