#[cfg(feature = "rayon")]
use rayon::prelude::*;
use tpt_math_linalg::tpt_math_linalg_dense::DMatrix;
use crate::error::ImageError;
use crate::ramp_filter;
#[derive(Debug, Clone)]
pub struct Volume {
pub nx: usize,
pub ny: usize,
pub nz: usize,
pub data: Vec<f64>,
}
impl Volume {
#[must_use]
pub fn new(nx: usize, ny: usize, nz: usize) -> Self {
Self {
nx,
ny,
nz,
data: vec![0.0; nx * ny * nz],
}
}
#[must_use]
pub fn from_fn(
nx: usize,
ny: usize,
nz: usize,
f: impl Fn(usize, usize, usize) -> f64,
) -> Self {
let mut data = vec![0.0; nx * ny * nz];
for iz in 0..nz {
for iy in 0..ny {
for ix in 0..nx {
data[ix + iy * nx + iz * nx * ny] = f(ix, iy, iz);
}
}
}
Self { nx, ny, nz, data }
}
#[must_use]
pub fn index(&self, ix: usize, iy: usize, iz: usize) -> usize {
ix + iy * self.nx + iz * self.nx * self.ny
}
#[must_use]
pub fn len(&self) -> usize {
self.nx * self.ny * self.nz
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
fn sample_slice(vol: &Volume, z: usize, col: f64, row: f64) -> f64 {
let nrows = vol.ny as f64;
let ncols = vol.nx as f64;
if col < 0.0 || row < 0.0 || col > ncols - 1.0 || row > nrows - 1.0 {
return 0.0;
}
let c0 = col.floor() as usize;
let r0 = row.floor() as usize;
let c1 = (c0 + 1).min(vol.nx - 1);
let r1 = (r0 + 1).min(vol.ny - 1);
let dc = col - c0 as f64;
let dr = row - r0 as f64;
let base = vol.index(0, 0, z);
let v00 = vol.data[base + c0 + r0 * vol.nx];
let v01 = vol.data[base + c1 + r0 * vol.nx];
let v10 = vol.data[base + c0 + r1 * vol.nx];
let v11 = vol.data[base + c1 + r1 * vol.nx];
v00 * (1.0 - dc) * (1.0 - dr) + v01 * dc * (1.0 - dr) + v10 * (1.0 - dc) * dr + v11 * dc * dr
}
fn sample_1d(v: &[f64], x: f64) -> f64 {
let n = v.len();
if n == 0 || x < 0.0 || x > (n - 1) as f64 {
return 0.0;
}
let i0 = x.floor() as usize;
let i1 = (i0 + 1).min(n - 1);
let d = x - i0 as f64;
v[i0] * (1.0 - d) + v[i1] * d
}
pub(crate) fn sample_trilinear(vol: &Volume, x: f64, y: f64, z: f64) -> f64 {
let nx = vol.nx as f64;
let ny = vol.ny as f64;
let nz = vol.nz as f64;
if x < 0.0 || y < 0.0 || z < 0.0 || x > nx - 1.0 || y > ny - 1.0 || z > nz - 1.0 {
return 0.0;
}
let x0 = x.floor() as usize;
let y0 = y.floor() as usize;
let z0 = z.floor() as usize;
let x1 = (x0 + 1).min(vol.nx - 1);
let y1 = (y0 + 1).min(vol.ny - 1);
let z1 = (z0 + 1).min(vol.nz - 1);
let dx = x - x0 as f64;
let dy = y - y0 as f64;
let dz = z - z0 as f64;
let at = |ix: usize, iy: usize, iz: usize| -> f64 { vol.data[vol.index(ix, iy, iz)] };
let c00 = at(x0, y0, z0) * (1.0 - dx) + at(x1, y0, z0) * dx;
let c10 = at(x0, y1, z0) * (1.0 - dx) + at(x1, y1, z0) * dx;
let c01 = at(x0, y0, z1) * (1.0 - dx) + at(x1, y0, z1) * dx;
let c11 = at(x0, y1, z1) * (1.0 - dx) + at(x1, y1, z1) * dx;
let c0 = c00 * (1.0 - dy) + c10 * dy;
let c1 = c01 * (1.0 - dy) + c11 * dy;
c0 * (1.0 - dz) + c1 * dz
}
pub fn radon_transform_3d(
volume: &Volume,
angles: &[f64],
) -> Result<Vec<DMatrix<f64>>, ImageError> {
if volume.is_empty() {
return Err(ImageError::EmptyImage {
nrows: volume.ny,
ncols: volume.nx,
});
}
if angles.is_empty() {
return Err(ImageError::EmptyAngles);
}
let nb = volume.nx.max(volume.ny);
let c = (nb - 1) as f64 / 2.0;
let cx = (volume.nx - 1) as f64 / 2.0;
let cy = (volume.ny - 1) as f64 / 2.0;
let mut out = Vec::with_capacity(angles.len());
for &theta in angles {
let cos = theta.cos();
let sin = theta.sin();
let mut proj = vec![0.0_f64; volume.nz * nb];
for z in 0..volume.nz {
for i in 0..nb {
let u = i as f64 - c;
for j in 0..nb {
let v = j as f64 - c;
let sx = cos * u - sin * v;
let sy = sin * u + cos * v;
proj[z * nb + i] += sample_slice(volume, z, sx + cx, sy + cy);
}
}
}
out.push(DMatrix::from_fn(volume.nz, nb, |z, i| proj[z * nb + i]));
}
Ok(out)
}
pub fn filtered_back_projection_3d(
sinograms: &[DMatrix<f64>],
angles: &[f64],
nx: usize,
ny: usize,
nz: usize,
) -> Result<Volume, ImageError> {
if angles.is_empty() {
return Err(ImageError::EmptyAngles);
}
if nx == 0 || ny == 0 || nz == 0 {
return Err(ImageError::EmptyImage {
nrows: ny,
ncols: nx,
});
}
if sinograms.len() != angles.len() {
return Err(ImageError::AngleCountMismatch {
sino_rows: sinograms.len(),
n_angles: angles.len(),
});
}
let nb = nx.max(ny);
for s in sinograms {
if s.ncols() != nb {
return Err(ImageError::DimensionMismatch {
expected: nb,
got: s.ncols(),
});
}
if s.nrows() != nz {
return Err(ImageError::DimensionMismatch {
expected: nz,
got: s.nrows(),
});
}
}
let c = (nb - 1) as f64 / 2.0;
let cx = (nx - 1) as f64 / 2.0;
let cy = (ny - 1) as f64 / 2.0;
let mut filtered: Vec<Vec<Vec<f64>>> = Vec::with_capacity(sinograms.len());
for s in sinograms {
let mut rows = Vec::with_capacity(s.nrows());
for z in 0..s.nrows() {
let row: Vec<f64> = (0..s.ncols()).map(|j| s[(z, j)]).collect();
rows.push(ramp_filter(&row));
}
filtered.push(rows);
}
let mut rec = vec![0.0_f64; nx * ny * nz];
let trig: Vec<(f64, f64)> = angles.iter().map(|&theta| theta.sin_cos()).collect();
let slice_len = nx * ny;
let fill_slice = |iz: usize, out: &mut [f64]| {
for (a, &(sin, cos)) in trig.iter().enumerate() {
for iy in 0..ny {
let y = iy as f64 - cy;
for ix in 0..nx {
let x = ix as f64 - cx;
let t = -sin * x + cos * y;
out[ix + iy * nx] += sample_1d(&filtered[a][iz], t + c);
}
}
}
};
#[cfg(feature = "rayon")]
rec.par_chunks_mut(slice_len)
.enumerate()
.for_each(|(iz, out)| fill_slice(iz, out));
#[cfg(not(feature = "rayon"))]
rec.chunks_mut(slice_len)
.enumerate()
.for_each(|(iz, out)| fill_slice(iz, out));
let scale = 4.0 / nb as f64 / angles.len() as f64;
for v in &mut rec {
*v *= scale;
}
Ok(Volume {
nx,
ny,
nz,
data: rec,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn radon_3d_dimensions() {
let v = Volume::from_fn(16, 16, 8, |ix, iy, iz| {
if ix == 8 && iy == 8 && iz == 4 {
1.0
} else {
0.0
}
});
let angles = crate::linspace(0.0, std::f64::consts::PI, 16);
let sino = radon_transform_3d(&v, &angles).unwrap();
assert_eq!(sino.len(), 16);
for s in &sino {
assert_eq!(s.nrows(), 8);
assert_eq!(s.ncols(), 16);
}
}
#[test]
fn fbp_3d_recovers_point_source() {
let n = 16usize;
let v = Volume::from_fn(n, n, n, |ix, iy, iz| {
if ix == n / 2 && iy == n / 2 && iz == n / 2 {
1.0
} else {
0.0
}
});
let angles = crate::linspace(0.0, std::f64::consts::PI, 32);
let sino = radon_transform_3d(&v, &angles).unwrap();
let rec = filtered_back_projection_3d(&sino, &angles, n, n, n).unwrap();
let c = rec.data[rec.index(n / 2, n / 2, n / 2)];
assert!(c > 0.0, "centre should be positive");
let mean = rec.data.iter().sum::<f64>() / rec.data.len() as f64;
assert!(
c >= mean,
"centre should be at least the mean (c={c}, mean={mean})"
);
}
#[test]
fn fbp_3d_beats_naive_3d() {
let n = 24usize;
let sigma = 3.0_f64;
let (cx, cy, cz) = (n as f64 / 2.0, n as f64 / 2.0, n as f64 / 2.0);
let orig = Volume::from_fn(n, n, n, |ix, iy, iz| {
let dx = ix as f64 - cx;
let dy = iy as f64 - cy;
let dz = iz as f64 - cz;
(-(dx * dx + dy * dy + dz * dz) / (2.0 * sigma * sigma)).exp()
});
let angles = crate::linspace(0.0, std::f64::consts::PI, 40);
let sino = radon_transform_3d(&orig, &angles).unwrap();
let rec = filtered_back_projection_3d(&sino, &angles, n, n, n).unwrap();
let naive = naive_back_projection_3d(&sino, &angles, n, n, n);
let mut fbp_err = 0.0;
let mut naive_err = 0.0;
let mut count = 0;
let b = 3;
for iz in b..n - b {
for iy in b..n - b {
for ix in b..n - b {
let k = orig.index(ix, iy, iz);
fbp_err += (rec.data[k] - orig.data[k]).abs();
naive_err += (naive.data[k] - orig.data[k]).abs();
count += 1;
}
}
}
fbp_err /= count as f64;
naive_err /= count as f64;
assert!(
fbp_err < naive_err,
"FBP error {fbp_err} should be below naive error {naive_err}"
);
}
#[test]
fn radon_3d_rejects_empty() {
let empty = Volume::new(0, 4, 4);
let angles = crate::linspace(0.0, std::f64::consts::PI, 8);
assert!(matches!(
radon_transform_3d(&empty, &angles),
Err(ImageError::EmptyImage { .. })
));
let v = Volume::from_fn(4, 4, 4, |_, _, _| 1.0);
assert!(matches!(
radon_transform_3d(&v, &[]),
Err(ImageError::EmptyAngles)
));
}
fn naive_back_projection_3d(
sinograms: &[DMatrix<f64>],
angles: &[f64],
nx: usize,
ny: usize,
nz: usize,
) -> Volume {
let nb = nx.max(ny);
let c = (nb - 1) as f64 / 2.0;
let cx = (nx - 1) as f64 / 2.0;
let cy = (ny - 1) as f64 / 2.0;
let mut rec = vec![0.0_f64; nx * ny * nz];
for (a, &theta) in angles.iter().enumerate() {
let cos = theta.cos();
let sin = theta.sin();
for iz in 0..nz {
let row: Vec<f64> = (0..sinograms[a].ncols())
.map(|j| sinograms[a][(iz, j)])
.collect();
for iy in 0..ny {
let y = iy as f64 - cy;
for ix in 0..nx {
let x = ix as f64 - cx;
let t = -sin * x + cos * y;
let bin = t + c;
let val = sample_1d(&row, bin);
rec[ix + iy * nx + iz * nx * ny] += val;
}
}
}
}
let scale = 4.0 / nb as f64 / angles.len() as f64;
for v in &mut rec {
*v *= scale;
}
Volume {
nx,
ny,
nz,
data: rec,
}
}
}