Chapter 10: Sparse-View Reconstruction and Compressed Sensing

As the previous chapter showed, one road to lower dose is simply to acquire less data: halving the number of projections roughly halves both dose and scan time. But Chapter 4 also showed what happens when there are too few projections: the reconstruction drowns in radial streaks. So how far can we thin the projections without destroying the image? The classical answer comes from sampling theory; the answer that overturned it, in the mid-2000s, is compressed sensing (CS).

The sampling requirement

The classical rule of thumb is that faithfully reconstructing an image of diameter $n$ pixels by FBP requires about

$$N_{\mathrm{views}} \gtrsim \frac{\pi}{2}\, n$$

projections (Crowther's criterion), which follows from Nyquist-style balancing of detector and angular sampling intervals. For $n = 128$ this is about 200 views, and the 180 views used throughout this textbook sit right at that level. Below it, angular aliasing appears as streaks: the star artifacts of Chapter 4 are precisely the signature of angular undersampling.

Classical theory stops here: "the information simply isn't there, so no algorithm can recover it." But that verdict holds only if we assume nothing about the image.

Compressed sensing

Around 2006, Candès–Romberg–Tao and Donoho proved the following: if a signal is sparse in some transform domain (most coefficients zero) and the measurements are incoherent with that representation, then exact recovery is possible from far fewer measurements than Nyquist requires, via $\ell_1$ minimization. This is compressed sensing. JPEG can compress images by an order of magnitude because images are sparse in a transform domain. CS asks: if the signal only carries compressible information anyway, why not measure less to begin with?

In which domain is a CT image sparse? Not in pixel values, but anatomical cross-sections are piecewise smooth, nearly uniform within each organ. Take differences between neighboring pixels (the gradient) and almost everything vanishes except at edges: CT images are sparse in the gradient domain.

Writing the total magnitude of the gradient, the image's total variation,

$$\mathrm{TV}(x) = \sum_{j} \left\| (\nabla x)_j \right\|_2 = \sum_{j} \sqrt{(\Delta_h x)_j^2 + (\Delta_v x)_j^2}$$

(the $\ell_1$ norm of the gradient), sparse-view CT reconstruction becomes the optimization problem

$$\min_x \; \mathrm{TV}(x) \quad \text{s.t.} \quad A x = p, \quad x \ge 0$$

In words: among all images consistent with the measurements, pick the one with the sparsest gradient. Streaks carry lots of gradient (they draw false edges everywhere), so the TV-minimizing solution naturally excludes them.

ASD-POCS

A well-known CT algorithm for this problem is ASD-POCS (adaptive steepest descent and projection onto convex sets) by Sidky and Pan. It adds a regularization step to the iterative loop from Chapter 8:

Chapter 8 claimed that the real strength of iterative reconstruction is its extensibility: the ability to inject prior knowledge. ASD-POCS is the first full-scale example. The implementation here (src/core/recon/tv.ts) is a simplified variant with a fixed TV step size, but the essential behavior is unchanged.

Simulation: FBP vs SART vs SART+TV

We extract $k$ equally spaced views from the full 180 and feed the same data to all three methods; the SART variants run 20 live iterations. Watch SART+TV nearly recover the Shepp-Logan phantom even at $k = 24$ (13% of full sampling), and compare the FBP streaks with SART's residual undersampling artifacts. Raising the TV step $\lambda$ too far flattens the profile into terraces, the classic "staircase" side effect of TV. And if you free-draw a phantom full of fine detail (breaking the sparsity assumption), TV's advantage shrinks accordingly.

Limits, and what comes next

The natural next question, whether we can learn a smarter prior than "piecewise constant" from data, leads directly to the learned methods of Chapter 12. Unrolled networks, which keep the iterative loop but replace hand-crafted steps with trained ones, are direct descendants of ASD-POCS; and the diffusion-model reconstruction methods surveyed in Chapter 13 share exactly the same skeleton: a learned generative prior alternating with data consistency. The compressed sensing seen here, moreover, first flowered in MRI: in the MRI part (Chapter 18) the same TV iteration returns, with the operator swapped for the Fourier transform.

References

• Candès EJ, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Information Theory 52, 489–509 (2006).
• Donoho DL. Compressed sensing. IEEE Trans. Information Theory 52, 1289–1306 (2006).
• Rudin LI, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992) — the original TV paper.
• Sidky EY, Pan X. Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization. Physics in Medicine & Biology 53, 4777–4807 (2008) — ASD-POCS.
• Pan X, Sidky EY, Vannier M. Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? Inverse Problems 25, 123009 (2009).