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}