Skip to main content

tpt_sci_image/
lib.rs

1//! `tpt-sci-image` — 2-D tomographic reconstruction built from scratch.
2//!
3//! This crate implements the core of parallel-beam computed tomography on top
4//! of the in-house `tpt-math` substrate:
5//!
6//! * [`radon_transform`] — the forward Radon transform (a sinogram).
7//! * [`filtered_back_projection`] — the classic ram-lak filtered back
8//!   projection (FBP) inverse.
9//!
10//! The same machinery is extended to volumes in the [`volume`] module:
11//! [`volume::radon_transform_3d`] and [`volume::filtered_back_projection_3d`]
12//! reconstruct a [`volume::Volume`] (a `n_x × n_y × n_z` scalar field) under a
13//! parallel-beam geometry that rotates about the `z` axis.
14//!
15//! Everything is hand-rolled: rotations/interpolation are done by coordinate
16//! remapping with bilinear sampling, and the ramp filter lives in the Fourier
17//! domain via [`tpt_math_signal_fft`]. There are no external image or
18//! tomography dependencies.
19//!
20//! # Examples
21//!
22//! ```
23//! use tpt_sci_image::{linspace, radon_transform};
24//! use tpt_math_linalg::tpt_math_linalg_dense::DMatrix;
25//!
26//! // A 4x4 image with a single bright pixel at the centre.
27//! let image = DMatrix::from_fn(4, 4, |i, j| if i == 1 && j == 1 { 1.0 } else { 0.0 });
28//! let angles = linspace(0.0, std::f64::consts::PI, 8);
29//! let sinogram = radon_transform(&image, &angles).unwrap();
30//!
31//! // The sinogram has one row per angle and one column per detector bin.
32//! assert_eq!(sinogram.nrows(), 8);
33//! assert_eq!(sinogram.ncols(), 4);
34//! ```
35
36use tpt_math_linalg::tpt_math_linalg_dense::DMatrix;
37use tpt_math_signal_fft::{Complex, fft, ifft_normalized};
38
39/// Errors returned by the image reconstruction API.
40pub mod error;
41pub use error::ImageError;
42
43/// 3-D tomographic reconstruction (parallel-beam volume CT).
44pub mod volume;
45pub use volume::{Volume, filtered_back_projection_3d, radon_transform_3d};
46
47/// General cone-beam (divergent source) forward/back-projection geometry and
48/// the Feldkamp-Davis-Kress (FDK) reconstruction, alongside (not replacing)
49/// the parallel-beam `volume` module.
50pub mod cone_beam;
51pub use cone_beam::{ConeBeamGeometry, cone_beam_forward_projection, fdk_reconstruction};
52
53/// Build an inclusive linearly-spaced vector of `n` points from `start` to
54/// `end`.
55///
56/// `linspace(0.0, 1.0, 5)` is `[0.0, 0.25, 0.5, 0.75, 1.0]`. An empty count
57/// yields an empty vector; a count of one yields `[start]`.
58///
59/// # Examples
60///
61/// ```
62/// use tpt_sci_image::linspace;
63/// let v = linspace(0.0, 1.0, 3);
64/// assert_eq!(v, vec![0.0, 0.5, 1.0]);
65/// ```
66pub fn linspace(start: f64, end: f64, n: usize) -> Vec<f64> {
67    if n == 0 {
68        return Vec::new();
69    }
70    if n == 1 {
71        return vec![start];
72    }
73    let step = (end - start) / (n as f64 - 1.0);
74    (0..n).map(|i| start + step * i as f64).collect()
75}
76
77/// The number of detector bins used for an image: the detector must be long
78/// enough to cover the image along its longest axis, so we pick
79/// `max(nrows, ncols)`.
80fn detector_count(image: &DMatrix<f64>) -> usize {
81    image.nrows().max(image.ncols())
82}
83
84/// Bilinear sample of `image` at fractional `(col, row)` coordinates.
85///
86/// `col` is the horizontal (column) coordinate and `row` the vertical (row)
87/// coordinate, both in the image's own pixel grid with the origin at the
88/// top-left pixel. Values outside the image extent are treated as zero (the
89/// object is assumed supported on the image).
90pub(crate) fn sample_bilinear(image: &DMatrix<f64>, col: f64, row: f64) -> f64 {
91    let nrows = image.nrows() as f64;
92    let ncols = image.ncols() as f64;
93    if col < 0.0 || row < 0.0 || col > ncols - 1.0 || row > nrows - 1.0 {
94        return 0.0;
95    }
96    let c0 = col.floor() as usize;
97    let r0 = row.floor() as usize;
98    let c1 = (c0 + 1).min(image.ncols() - 1);
99    let r1 = (r0 + 1).min(image.nrows() - 1);
100    let dc = col - c0 as f64;
101    let dr = row - r0 as f64;
102    let v00 = image[(r0, c0)];
103    let v01 = image[(r0, c1)];
104    let v10 = image[(r1, c0)];
105    let v11 = image[(r1, c1)];
106    v00 * (1.0 - dc) * (1.0 - dr) + v01 * dc * (1.0 - dr) + v10 * (1.0 - dc) * dr + v11 * dc * dr
107}
108
109/// Linear interpolation of a 1-D projection at fractional bin `x`.
110///
111/// Out-of-range positions return zero (no detector data there).
112fn sample_1d(v: &[f64], x: f64) -> f64 {
113    let n = v.len();
114    if n == 0 || x < 0.0 || x > (n - 1) as f64 {
115        return 0.0;
116    }
117    let i0 = x.floor() as usize;
118    let i1 = (i0 + 1).min(n - 1);
119    let d = x - i0 as f64;
120    v[i0] * (1.0 - d) + v[i1] * d
121}
122
123/// Forward Radon transform (parallel beam) of `image` over `angles`.
124///
125/// For each angle `theta` we build a rotated frame of size
126/// `n_bins x n_bins` (with `n_bins = max(nrows, ncols)`) by mapping every
127/// output pixel back through the inverse rotation `R(theta)` into the original
128/// image and bilinearly sampling it. The detector projection for that angle is
129/// then the sum along each row of the rotated frame, so the returned sinogram
130/// has `sinogram.nrows() == angles.len()` and
131/// `sinogram.ncols() == n_bins`.
132///
133/// The rotation uses nearest-pixel-centre coordinates (origin at the centre
134/// pixel) and bilinear interpolation; the same centre convention and rotation
135/// sense are used by [`filtered_back_projection`] so forward and inverse are
136/// consistent.
137///
138/// # Errors
139///
140/// Returns [`ImageError::EmptyImage`] if `image` has zero rows or columns, or
141/// [`ImageError::EmptyAngles`] if `angles` is empty.
142pub fn radon_transform(image: &DMatrix<f64>, angles: &[f64]) -> Result<DMatrix<f64>, ImageError> {
143    if image.nrows() == 0 || image.ncols() == 0 {
144        return Err(ImageError::EmptyImage {
145            nrows: image.nrows(),
146            ncols: image.ncols(),
147        });
148    }
149    if angles.is_empty() {
150        return Err(ImageError::EmptyAngles);
151    }
152    let nb = detector_count(image);
153    let c = (nb - 1) as f64 / 2.0;
154    let cx_img = (image.ncols() - 1) as f64 / 2.0;
155    let cy_img = (image.nrows() - 1) as f64 / 2.0;
156
157    let mut sino = vec![0.0_f64; angles.len() * nb];
158    for (a, &theta) in angles.iter().enumerate() {
159        let cos = theta.cos();
160        let sin = theta.sin();
161        // Fill the rotated frame (nb x nb) by inverse-mapping each output
162        // pixel into the original image.
163        for i in 0..nb {
164            for j in 0..nb {
165                let u = j as f64 - c;
166                let v = i as f64 - c;
167                // Source coordinate in the original image via R(theta).
168                let sx = cos * u - sin * v;
169                let sy = sin * u + cos * v;
170                let src_col = sx + cx_img;
171                let src_row = sy + cy_img;
172                let val = sample_bilinear(image, src_col, src_row);
173                // Accumulate into the row-sum (one detector bin per row).
174                sino[a * nb + i] += val;
175            }
176        }
177    }
178    Ok(DMatrix::from_fn(angles.len(), nb, |a, i| sino[a * nb + i]))
179}
180
181/// Apply the ram-lak ramp filter to a single projection in the Fourier domain.
182///
183/// The forward FFT is taken, each bin `k` is multiplied by `|k|`
184/// (`min(k, n - k)`, which is the folded positive frequency), and the result
185/// is inverse-transformed (normalized) before returning its real part.
186///
187/// Shared by [`filtered_back_projection`], [`volume::filtered_back_projection_3d`]
188/// and [`cone_beam::fdk_reconstruction`] so the ram-lak machinery lives in one
189/// place.
190pub(crate) fn ramp_filter(p: &[f64]) -> Vec<f64> {
191    let n = p.len();
192    if n == 0 {
193        return Vec::new();
194    }
195    let spectrum = fft(p);
196    let filtered: Vec<Complex<f64>> = spectrum
197        .iter()
198        .enumerate()
199        .map(|(k, &z)| {
200            let freq = if k <= n / 2 { k } else { n - k } as f64;
201            z * freq
202        })
203        .collect();
204    let back = ifft_normalized(&filtered);
205    back.iter().map(|z| z.re).collect()
206}
207
208/// Back-project a set of (possibly filtered) 1-D projections into an
209/// `n_bins x n_bins` reconstruction.
210///
211/// Each reconstruction pixel at centre-relative coordinate `(x, y)` is mapped
212/// onto the detector axis for angle `theta` via `t = -sin(theta)*x +
213/// cos(theta)*y`; the projection value at bin `t + c` is added. `projections`
214/// must have one `Vec<f64>` per angle, each of length `n_bins`.
215fn back_project(projections: &[Vec<f64>], angles: &[f64], nb: usize) -> DMatrix<f64> {
216    let c = if nb == 0 { 0.0 } else { (nb - 1) as f64 / 2.0 };
217    let mut rec = vec![0.0_f64; nb * nb];
218    for (a, &theta) in angles.iter().enumerate() {
219        let q = match projections.get(a) {
220            Some(q) => q,
221            None => continue,
222        };
223        let cos = theta.cos();
224        let sin = theta.sin();
225        for i in 0..nb {
226            for j in 0..nb {
227                let x = j as f64 - c;
228                let y = i as f64 - c;
229                let t = -sin * x + cos * y;
230                let bin_f = t + c;
231                rec[i * nb + j] += sample_1d(q, bin_f);
232            }
233        }
234    }
235    DMatrix::from_fn(nb, nb, |i, j| rec[i * nb + j])
236}
237
238/// Filtered back-projection (FBP) reconstruction from a sinogram.
239///
240/// For each angle the projection row is ramp-filtered in the Fourier domain
241/// (ram-lak) and then back-projected. The accumulated image is normalized by
242/// the number of angles, which corresponds to the `1/pi * integral dtheta`
243/// continuous formula with `dtheta ~= pi / n_angles`. An additional linear
244/// scale factor `4 / n_bins` corrects the amplitude of the discrete ramp
245/// filter (which omits the `2*pi/n` frequency spacing and the `1/n` of the
246/// unnormalized FFT) so that a point source reconstructs to its original
247/// amplitude.
248///
249/// The returned reconstruction is always `n_bins x n_bins` with
250/// `n_bins = sinogram.ncols()`.
251///
252/// # Errors
253///
254/// Returns [`ImageError::EmptyAngles`] if `angles` is empty or
255/// [`ImageError::AngleCountMismatch`] if `sinogram.nrows() != angles.len()`.
256pub fn filtered_back_projection(
257    sinogram: &DMatrix<f64>,
258    angles: &[f64],
259) -> Result<DMatrix<f64>, ImageError> {
260    if angles.is_empty() {
261        return Err(ImageError::EmptyAngles);
262    }
263    if sinogram.nrows() != angles.len() {
264        return Err(ImageError::AngleCountMismatch {
265            sino_rows: sinogram.nrows(),
266            n_angles: angles.len(),
267        });
268    }
269    let nb = sinogram.ncols();
270    let mut qs: Vec<Vec<f64>> = Vec::with_capacity(angles.len());
271    for a in 0..angles.len() {
272        let row: Vec<f64> = (0..nb).map(|j| sinogram[(a, j)]).collect();
273        qs.push(ramp_filter(&row));
274    }
275    let rec = back_project(&qs, angles, nb);
276    // Empirical FBP amplitude normalisation. The continuous filtered
277    // back-projection identity is
278    //     f(x) = (1/π) ∫_0^π [Rf(·,θ) * h](x·n(θ)) dθ ,
279    // with ramp kernel h(t) ∝ |ω| in frequency, sampled here as the raw DFT
280    // ramp `|k|` used by `ramp_filter`. Discretely the detector bins are spaced
281    // Δs = 1, the `n_angles` projections cover [0, π) at Δθ = π/n_angles, and the
282    // back-projection simply sums `n_angles` contributions. Matching the
283    // discrete ramp's DC gain to the continuous kernel and absorbing the Δθ and
284    // Δs pixel-area factors yields the constant `4.0 / (nb · n_angles)`
285    // (Kak & Slaney, *Principles of Computerized Tomographic Imaging*, §3.3).
286    let scale = 4.0 / nb as f64 / angles.len() as f64;
287    Ok(rec * scale)
288}
289
290/// Unfiltered (naive) back-projection of a sinogram.
291///
292/// Like [`filtered_back_projection`] but without the ramp filter, used to show
293/// that filtering improves the reconstruction (it removes the characteristic
294/// blur/halo of the naive adjoint).
295///
296/// # Errors
297///
298/// Returns [`ImageError::EmptyAngles`] if `angles` is empty or
299/// [`ImageError::AngleCountMismatch`] if `sinogram.nrows() != angles.len()`.
300pub fn naive_back_projection(
301    sinogram: &DMatrix<f64>,
302    angles: &[f64],
303) -> Result<DMatrix<f64>, ImageError> {
304    if angles.is_empty() {
305        return Err(ImageError::EmptyAngles);
306    }
307    if sinogram.nrows() != angles.len() {
308        return Err(ImageError::AngleCountMismatch {
309            sino_rows: sinogram.nrows(),
310            n_angles: angles.len(),
311        });
312    }
313    let nb = sinogram.ncols();
314    let projections: Vec<Vec<f64>> = (0..angles.len())
315        .map(|a| (0..nb).map(|j| sinogram[(a, j)]).collect())
316        .collect();
317    let rec = back_project(&projections, angles, nb);
318    // Same `4.0 / (nb · n_angles)` normalisation as `filtered_back_projection`
319    // (Kak & Slaney, *Principles of Computerized Tomographic Imaging*, §3.3),
320    // applied to the unfiltered adjoint so the two reconstructions share a scale.
321    let scale = 4.0 / nb as f64 / angles.len() as f64;
322    Ok(rec * scale)
323}
324
325#[cfg(test)]
326mod tests {
327    use super::*;
328    use approx::assert_abs_diff_eq;
329    use tpt_math_linalg::tpt_math_linalg_dense::DMatrix;
330
331    /// Index of the centre pixel of an `n x n` image.
332    fn center(n: usize) -> (usize, usize) {
333        (n / 2, n / 2)
334    }
335
336    fn mean(m: &DMatrix<f64>) -> f64 {
337        let mut s = 0.0;
338        let mut n = 0;
339        for i in 0..m.nrows() {
340            for j in 0..m.ncols() {
341                s += m[(i, j)];
342                n += 1;
343            }
344        }
345        s / n as f64
346    }
347
348    #[test]
349    fn linspace_is_inclusive() {
350        let v = linspace(0.0, 1.0, 5);
351        assert_eq!(v.len(), 5);
352        assert_abs_diff_eq!(v[0], 0.0, epsilon = 1e-12);
353        assert_abs_diff_eq!(v[4], 1.0, epsilon = 1e-12);
354        assert_abs_diff_eq!(v[2], 0.5, epsilon = 1e-12);
355    }
356
357    #[test]
358    fn radon_dimensions_match_angles_and_bins() {
359        let n = 16usize;
360        let image = DMatrix::from_fn(
361            n,
362            n,
363            |i, j| if i == n / 2 && j == n / 2 { 1.0 } else { 0.0 },
364        );
365        let angles = linspace(0.0, std::f64::consts::PI, 32);
366        let sino = radon_transform(&image, &angles).unwrap();
367        assert_eq!(sino.nrows(), 32);
368        assert_eq!(sino.ncols(), n);
369    }
370
371    #[test]
372    fn point_source_peaks_near_centre_column() {
373        let n = 16usize;
374        let image = DMatrix::from_fn(
375            n,
376            n,
377            |i, j| if i == n / 2 && j == n / 2 { 1.0 } else { 0.0 },
378        );
379        let angles = linspace(0.0, std::f64::consts::PI, 32);
380        let sino = radon_transform(&image, &angles).unwrap();
381
382        // Find the column (detector bin) holding the maximum value of the whole
383        // sinogram: for a centred point source it must be the centre bin.
384        let mut max_col = 0;
385        let mut max_val = f64::NEG_INFINITY;
386        for a in 0..sino.nrows() {
387            for j in 0..sino.ncols() {
388                if sino[(a, j)] > max_val {
389                    max_val = sino[(a, j)];
390                    max_col = j;
391                }
392            }
393        }
394        assert!((max_col as isize - n as isize / 2).abs() <= 1);
395    }
396
397    #[test]
398    fn constant_image_conserves_row_sum() {
399        let n = 16usize;
400        let image = DMatrix::from_fn(n, n, |_, _| 1.0);
401        let angles = linspace(0.0, std::f64::consts::PI, 24);
402        let sino = radon_transform(&image, &angles).unwrap();
403        // A constant unit image integrates to at most N samples per detector
404        // bin (a full line through the square). Because the discrete sinogram
405        // samples a rotated `N x N` frame and no bin sits exactly on the
406        // image centre line, the most central line can lose at most a single
407        // boundary sample to the square's edge — so each central bin is within
408        // one of N. Every bin is non-negative and bounded by N.
409        let c = n / 2;
410        for a in 0..sino.nrows() {
411            let max_bin = (0..sino.ncols())
412                .map(|j| sino[(a, j)])
413                .fold(0.0_f64, f64::max);
414            assert!(
415                (max_bin - n as f64).abs() <= 1.0 + 1e-6,
416                "angle {a} max {max_bin}"
417            );
418            assert!(
419                (sino[(a, c)] - n as f64).abs() <= 1.0 + 1e-6,
420                "angle {a} central {}",
421                sino[(a, c)]
422            );
423            for j in 0..sino.ncols() {
424                assert!(
425                    sino[(a, j)] <= n as f64 + 1e-9,
426                    "bin {j} = {}",
427                    sino[(a, j)]
428                );
429                assert!(sino[(a, j)] >= 0.0);
430            }
431        }
432    }
433
434    #[test]
435    fn fbp_point_source_centre_is_positive_and_prominent() {
436        let n = 16usize;
437        let image = DMatrix::from_fn(
438            n,
439            n,
440            |i, j| if i == n / 2 && j == n / 2 { 1.0 } else { 0.0 },
441        );
442        let angles = linspace(0.0, std::f64::consts::PI, 32);
443        let sino = radon_transform(&image, &angles).unwrap();
444        let rec = filtered_back_projection(&sino, &angles).unwrap();
445
446        let c = center(n);
447        assert!(rec[(c.0, c.1)] > 0.0, "centre should be positive");
448        let m = mean(&rec);
449        assert!(
450            rec[(c.0, c.1)] >= m,
451            "centre should be at least the mean (got {} vs mean {})",
452            rec[(c.0, c.1)],
453            m
454        );
455    }
456
457    #[test]
458    fn fbp_recovers_gaussian_and_beats_naive() {
459        let n = 32usize;
460        let sigma = 4.0_f64;
461        let (cx, cy) = (n as f64 / 2.0, n as f64 / 2.0);
462        let original = DMatrix::from_fn(n, n, |i, j| {
463            let dx = i as f64 - cx;
464            let dy = j as f64 - cy;
465            (-(dx * dx + dy * dy) / (2.0 * sigma * sigma)).exp()
466        });
467
468        let angles = linspace(0.0, std::f64::consts::PI, 48);
469        let sino = radon_transform(&original, &angles).unwrap();
470        let rec = filtered_back_projection(&sino, &angles).unwrap();
471        let naive = naive_back_projection(&sino, &angles).unwrap();
472
473        // The centre reconstruction should be positive and reasonably close to
474        // the original centre value (filtered back-projection is not exact, so
475        // we allow a generous band rather than an exact equality).
476        let c = center(n);
477        let centre_val = rec[(c.0, c.1)];
478        assert!(centre_val > 0.0, "centre should be positive");
479        assert!(
480            centre_val > 0.3 * original[(c.0, c.1)] && centre_val < 2.5 * original[(c.0, c.1)],
481            "centre {centre_val} should be reasonably close to {}",
482            original[(c.0, c.1)]
483        );
484
485        // Mean absolute error over the interior (exclude a 4-pixel border that
486        // suffers edge effects in both methods).
487        let lo = 4;
488        let hi = n - 4;
489        let mae = |m: &DMatrix<f64>| -> f64 {
490            let mut s = 0.0;
491            let mut count = 0;
492            for i in lo..hi {
493                for j in lo..hi {
494                    s += (m[(i, j)] - original[(i, j)]).abs();
495                    count += 1;
496                }
497            }
498            s / count as f64
499        };
500        let fbp_err = mae(&rec);
501        let naive_err = mae(&naive);
502        assert!(
503            fbp_err < naive_err,
504            "FBP error {fbp_err} should be below naive error {naive_err}"
505        );
506    }
507
508    #[test]
509    fn radon_rejects_empty_image_and_angles() {
510        let empty = DMatrix::<f64>::zeros(0, 4);
511        let angles = linspace(0.0, std::f64::consts::PI, 8);
512        assert!(matches!(
513            radon_transform(&empty, &angles),
514            Err(ImageError::EmptyImage { .. })
515        ));
516        let image = DMatrix::from_fn(4, 4, |_, _| 1.0);
517        assert!(matches!(
518            radon_transform(&image, &[]),
519            Err(ImageError::EmptyAngles)
520        ));
521    }
522
523    #[test]
524    fn fbp_rejects_angle_count_mismatch() {
525        let n = 8usize;
526        let image = DMatrix::from_fn(n, n, |_, _| 1.0);
527        let angles = linspace(0.0, std::f64::consts::PI, 8);
528        let sino = radon_transform(&image, &angles).unwrap();
529        // A sinogram built from 8 angles cannot be reconstructed with 4 angles.
530        let few = linspace(0.0, std::f64::consts::PI, 4);
531        assert!(matches!(
532            filtered_back_projection(&sino, &few),
533            Err(ImageError::AngleCountMismatch { .. })
534        ));
535        assert!(matches!(
536            naive_back_projection(&sino, &few),
537            Err(ImageError::AngleCountMismatch { .. })
538        ));
539    }
540}