Fast tomographic reconstruction via rotation-based hierarchical backprojection

Ashvin George, Yoram Bresler

Research output: Contribution to journalArticlepeer-review


We introduce a family of fast algorithms for tomographic backprojection in the parallel-beam geometry. The algorithms reduce the computational cost of backprojecting P projections onto an N × N pixel image from the conventional O(N2P) to O(N2 log P). The new algorithms aggregate the projections in a hierarchical structure, with images in the hierarchy formed by the rotation and addition of other images made up of fewer projections. While these algorithms are related to existing fast algorithms, this work places them within the signal processing framework, providing a systematic means to optimize and adjust the trade-off between computational cost and accuracy. Rotations are performed separably in order that higher-order interpolators may be used with low computational cost. The same ideas are applied to create a tomographic projection algorithm, which computes projections of an N × N pixel image onto P view-angles at a cost of O(N2 log P).

Original languageEnglish (US)
Pages (from-to)574-597
Number of pages24
JournalSIAM Journal on Applied Mathematics
Issue number2
StatePublished - 2007


  • Backprojection
  • Fast algorithms
  • Projection
  • Radon transform
  • Separable rotation
  • Spline interpolation
  • Tomography

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Fast tomographic reconstruction via rotation-based hierarchical backprojection'. Together they form a unique fingerprint.

Cite this