DSP seminar, Wed Oct. 19 Time and location: 4:00-5:00 PM 2269 Beckman Institute

Title: Improving The Sampling Efficiency Of Fast Hierarchical Backprojection Algorithms


Speaker: Ashvin George

Graduate Student
ECE Department, UIUC

Abstract:

We introduce a new algorithm for tomographic backprojection of an N x N pixel image 
from P projections. Like existing fast algorithms it has a computational cost 
of O(N^2  logP) compared to the conventional backprojection algorithm whose 
cost is O(N^2 P). It uses the hierarchical decomposition of backprojection 
into the shearing and addition of images made up of small numbers of projections. 
This results in intermediate images that have a spectral support on a 
"bow-tie"/"wedge". The performance of the algorithm depends on  the efficient 
sampling of these intermediate images. The sampling schemes in previous algorithms 
of this nature have not made full use of this distinctive spectral support. 
Attempts were made to design an algorithm modelled on the Directional Filter Bank 
(of Smith and Barnwell) but the restrictions imposed by the tomographic scenario, 
such as a low tolerance for non-ideal filters and the need to incorporate oversampling, 
lead to an expensive algorithm.

In this talk we describe how more efficient sampling can be achieved by modifying 
the original shear-based hierarchical backprojection algorithm. The shearing of 
images is performed in the DFT-domain (via row-by-row fractional shifting by 
multiplication). By maintaining intermediate images in one frequency-variable 
and one space-variable, different frequency channels can be sampled with different 
sampling periods to make full use of the bow-tie-shaped spectral support. This method 
allows for more flexibility in sampling and can be adapted to account for the 
concentration of most of the energy of an image at low spatial frequencies.