#![forbid(unsafe_code)]
use crate::backend::{
Backend, DeviceBuffer, DeviceKind, Elementwise, FbpFilter, Fft, FilteredBackproject,
ForwardProject, RampShape, RankFilter, RayProject, RayRow,
};
use crate::data::{Frames, Layout, Tomo, Volume};
use crate::dtype::{Complex32, Dtype, Element};
use crate::error::{Error, Result};
use crate::geometry::{Beam, Center, Geometry};
use crate::params::FilterName;
use ndarray::{Array3, Axis};
use rayon::prelude::*;
use rustfft::FftPlanner;
#[derive(Clone, Debug, Default)]
pub struct CpuBuffer<T> {
pub data: Vec<T>,
}
impl<T: Element> CpuBuffer<T> {
pub fn zeros(len: usize) -> Self {
Self {
data: vec![T::zero(); len],
}
}
}
impl<T: Element> DeviceBuffer<T> for CpuBuffer<T> {
fn len(&self) -> usize {
self.data.len()
}
fn copy_from_host(&mut self, src: &[T]) -> Result<()> {
if src.len() != self.data.len() {
return Err(Error::ShapeMismatch {
expected: self.data.len().to_string(),
found: src.len().to_string(),
});
}
self.data.copy_from_slice(src);
Ok(())
}
fn copy_to_host(&self, dst: &mut [T]) -> Result<()> {
if dst.len() != self.data.len() {
return Err(Error::ShapeMismatch {
expected: self.data.len().to_string(),
found: dst.len().to_string(),
});
}
dst.copy_from_slice(&self.data);
Ok(())
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct CpuBackend;
impl CpuBackend {
pub fn new() -> Self {
CpuBackend
}
}
impl Backend for CpuBackend {
fn name(&self) -> &'static str {
"cpu"
}
fn device(&self) -> DeviceKind {
DeviceKind::Cpu
}
fn supports(&self, dt: Dtype) -> bool {
dt == Dtype::F32
}
fn fft(&self) -> Option<&dyn Fft> {
Some(self)
}
fn fbp_filter(&self) -> Option<&dyn FbpFilter> {
Some(self)
}
fn backprojector(&self) -> Option<&dyn FilteredBackproject> {
Some(self)
}
fn projector(&self) -> Option<&dyn ForwardProject> {
Some(self)
}
fn ray_projector(&self) -> Option<&dyn RayProject> {
Some(self)
}
fn elementwise(&self) -> Option<&dyn Elementwise> {
Some(self)
}
fn rank_filter(&self) -> Option<&dyn RankFilter> {
Some(self)
}
}
impl Elementwise for CpuBackend {
fn darkflat(&self, data: &mut Tomo<f32>, flat: &Frames<f32>, dark: &Frames<f32>) -> Result<()> {
let (dark2d, denom) = crate::prep::normalize::darkflat_frames(flat, dark)?;
let restore = data.layout == Layout::Sinogram;
if restore {
*data = data.to_layout(Layout::Projection);
}
for mut slab in data.array.axis_iter_mut(Axis(0)) {
slab -= &dark2d;
slab /= &denom;
}
if restore {
*data = data.to_layout(Layout::Sinogram);
}
Ok(())
}
fn minus_log(&self, data: &mut Tomo<f32>) -> Result<()> {
let map = |v: &mut f32| {
let clamped = v.max(1e-6);
let out = -clamped.ln();
*v = if out.is_finite() { out } else { 0.0 };
};
match data.array.as_slice_memory_order_mut() {
Some(s) => s.par_iter_mut().for_each(map),
None => data.array.iter_mut().for_each(map),
}
Ok(())
}
}
impl FbpFilter for CpuBackend {
fn make_filter(&self, name: FilterName, n: usize) -> Result<Vec<f32>> {
crate::backend::make_fbp_filter(name, n, RampShape::Linear)
}
fn apply(&self, sino: &mut Tomo<f32>, filter: &[f32], geom: &Geometry) -> Result<()> {
let pad = filter.len();
if pad == 0 {
return Err(Error::InvalidParam("empty filter".into()));
}
let ncols = sino.n_cols();
if pad < ncols {
return Err(Error::ShapeMismatch {
expected: format!(">= {ncols} (n_cols)"),
found: pad.to_string(),
});
}
let half = ncols as f32 / 2.0;
let two_pi = std::f32::consts::TAU;
let make_w = |delta: f32| -> Vec<Complex32> {
(0..pad)
.map(|k| {
let fk = if k <= pad / 2 {
k as f32
} else {
k as f32 - pad as f32
};
let ang = -two_pi * fk * delta / pad as f32;
Complex32::new(filter[k] * ang.cos(), filter[k] * ang.sin())
})
.collect()
};
let n_rows = sino.n_rows();
let wrows: Vec<Vec<Complex32>> = match &geom.center {
Center::Scalar(c) => vec![make_w(half - c)],
Center::PerRow(_) => (0..n_rows)
.map(|r| make_w(half - geom.center.at(r)))
.collect(),
};
let scalar = wrows.len() == 1;
let layout = sino.layout;
let d1 = sino.array.shape()[1];
let mut planner = FftPlanner::<f32>::new();
let fwd = planner.plan_fft_forward(pad);
let inv = planner.plan_fft_inverse(pad);
let norm = 1.0 / pad as f32;
let mut buf = vec![Complex32::new(0.0, 0.0); pad];
let pad_side = pad / 2 - ncols / 2;
for (flat, mut lane) in sino.array.lanes_mut(Axis(2)).into_iter().enumerate() {
let w = if scalar {
&wrows[0]
} else {
let row = match layout {
Layout::Sinogram => flat / d1,
Layout::Projection => flat % d1,
};
&wrows[row]
};
let first = lane[0];
let last = lane[ncols - 1];
for slot in buf[..pad_side].iter_mut() {
*slot = Complex32::new(first, 0.0);
}
for (i, &v) in lane.iter().enumerate() {
buf[pad_side + i] = Complex32::new(v, 0.0);
}
for slot in buf[pad_side + ncols..].iter_mut() {
*slot = Complex32::new(last, 0.0);
}
fwd.process(&mut buf);
for (c, wk) in buf.iter_mut().zip(w.iter()) {
*c *= *wk;
}
inv.process(&mut buf);
for (i, slot) in lane.iter_mut().enumerate() {
*slot = buf[pad_side + i].re * norm;
}
}
Ok(())
}
}
impl Fft for CpuBackend {
fn for_each_slice(
&self,
out: &mut Array3<f32>,
f: &(dyn Fn(usize, ndarray::ArrayViewMut2<f32>) -> Result<()> + Sync),
) -> Result<()> {
let slabs: Vec<_> = out.axis_iter_mut(Axis(0)).collect();
slabs
.into_par_iter()
.enumerate()
.try_for_each(|(row, slab)| f(row, slab))
}
fn fft_1d(&self, buf: &mut [Complex32], len: usize, batch: usize, inverse: bool) -> Result<()> {
if len == 0 || batch == 0 {
return Ok(());
}
if buf.len() != len * batch {
return Err(Error::ShapeMismatch {
expected: (len * batch).to_string(),
found: buf.len().to_string(),
});
}
let mut planner = FftPlanner::<f32>::new();
let fft = if inverse {
planner.plan_fft_inverse(len)
} else {
planner.plan_fft_forward(len)
};
let scratch_len = fft.get_inplace_scratch_len();
buf.par_chunks_mut(len).for_each_init(
|| vec![Complex32::new(0.0, 0.0); scratch_len],
|scratch, chunk| fft.process_with_scratch(chunk, scratch),
);
if inverse {
let norm = 1.0 / len as f32;
buf.par_iter_mut().for_each(|c| *c *= norm);
}
Ok(())
}
fn fft_2d(
&self,
buf: &mut [Complex32],
rows: usize,
cols: usize,
batch: usize,
inverse: bool,
) -> Result<()> {
if rows == 0 || cols == 0 || batch == 0 {
return Ok(());
}
if buf.len() != rows * cols * batch {
return Err(Error::ShapeMismatch {
expected: (rows * cols * batch).to_string(),
found: buf.len().to_string(),
});
}
let mut planner = FftPlanner::<f32>::new();
let row_fft = if inverse {
planner.plan_fft_inverse(cols)
} else {
planner.plan_fft_forward(cols)
};
let col_fft = if inverse {
planner.plan_fft_inverse(rows)
} else {
planner.plan_fft_forward(rows)
};
let row_scratch = row_fft.get_inplace_scratch_len();
let col_scratch = col_fft.get_inplace_scratch_len();
buf.par_chunks_mut(rows * cols).for_each_init(
|| {
(
vec![Complex32::new(0.0, 0.0); rows],
vec![Complex32::new(0.0, 0.0); row_scratch],
vec![Complex32::new(0.0, 0.0); col_scratch],
)
},
|(col, rscr, cscr), img| {
for row in img.chunks_mut(cols) {
row_fft.process_with_scratch(row, rscr);
}
for c in 0..cols {
for (r, slot) in col.iter_mut().enumerate() {
*slot = img[r * cols + c];
}
col_fft.process_with_scratch(col, cscr);
for (r, &v) in col.iter().enumerate() {
img[r * cols + c] = v;
}
}
},
);
if inverse {
let norm = 1.0 / (rows * cols) as f32;
buf.par_iter_mut().for_each(|c| *c *= norm);
}
Ok(())
}
}
impl FilteredBackproject for CpuBackend {
fn backproject(&self, sino: &Tomo<f32>, geom: &Geometry, out: &mut Volume<f32>) -> Result<()> {
if geom.beam != Beam::Parallel {
return Err(Error::InvalidParam(
"cpu back-projection currently supports parallel beam only".into(),
));
}
let s = sino.as_layout(Layout::Sinogram); let nz = s.n_rows();
let nang = s.n_angles();
let ncols = s.n_cols();
let (oz, ny, nx) = out.dims();
if oz != nz {
return Err(Error::ShapeMismatch {
expected: format!("{nz} sinogram rows"),
found: oz.to_string(),
});
}
let angles = &geom.angles.0;
if angles.len() != nang {
return Err(Error::ShapeMismatch {
expected: format!("{nang} angles"),
found: angles.len().to_string(),
});
}
let trig: Vec<(f32, f32)> = angles
.iter()
.map(|&a| {
let (sn, c) = a.sin_cos();
(c, sn)
})
.collect();
let cx = nx as f32 / 2.0;
let cy = ny as f32 / 2.0;
let sino_slice = s
.array
.as_slice()
.ok_or_else(|| Error::InvalidParam("non-contiguous sinogram".into()))?;
let out_slice = out
.array
.as_slice_mut()
.ok_or_else(|| Error::InvalidParam("non-contiguous volume".into()))?;
out_slice
.par_chunks_mut(ny * nx)
.enumerate()
.for_each(|(row, slab)| {
let center = geom.center.at(row);
let base = row * nang * ncols;
for iy in 0..ny {
let gy = iy as f32 - cy;
for ix in 0..nx {
let gx = ix as f32 - cx;
let mut acc = 0.0f32;
for (ia, &(c, sn)) in trig.iter().enumerate() {
let t = gx * c + gy * sn + center;
let t0 = t.floor();
let i0 = t0 as isize;
if i0 >= 0 && (i0 as usize) + 1 < ncols {
let frac = t - t0;
let off = base + ia * ncols + i0 as usize;
acc += sino_slice[off] * (1.0 - frac) + sino_slice[off + 1] * frac;
}
}
slab[iy * nx + ix] = acc;
}
}
});
Ok(())
}
}
impl ForwardProject for CpuBackend {
fn project(&self, vol: &Volume<f32>, geom: &Geometry, out: &mut Tomo<f32>) -> Result<()> {
if geom.beam != Beam::Parallel {
return Err(Error::InvalidParam(
"cpu forward projection currently supports parallel beam only".into(),
));
}
let (nz, ny, nx) = vol.dims();
let nang = geom.angles.0.len();
let ncols = geom.detector.width;
if nang == 0 || ncols == 0 {
return Err(Error::InvalidParam(
"geometry has no angles or zero detector width".into(),
));
}
let trig: Vec<(f32, f32)> = geom
.angles
.0
.iter()
.map(|&a| {
let (sn, c) = a.sin_cos();
(c, sn)
})
.collect();
let cx = nx as f32 / 2.0;
let cy = ny as f32 / 2.0;
let vol_slice = vol
.array
.as_slice()
.ok_or_else(|| Error::InvalidParam("non-contiguous volume".into()))?;
let mut data = vec![0.0f32; nz * nang * ncols];
data.par_chunks_mut(nang * ncols)
.enumerate()
.for_each(|(row, slab)| {
let center = geom.center.at(row);
let vbase = row * ny * nx;
for iy in 0..ny {
let gy = iy as f32 - cy;
for ix in 0..nx {
let f = vol_slice[vbase + iy * nx + ix];
if f == 0.0 {
continue;
}
let gx = ix as f32 - cx;
for (ia, &(c, sn)) in trig.iter().enumerate() {
let t = gx * c + gy * sn + center;
let t0 = t.floor();
let i0 = t0 as isize;
if i0 >= 0 && (i0 as usize) + 1 < ncols {
let frac = t - t0;
let off = ia * ncols + i0 as usize;
slab[off] += f * (1.0 - frac);
slab[off + 1] += f * frac;
}
}
}
}
});
let array = ndarray::Array3::from_shape_vec((nz, nang, ncols), data)
.map_err(|e| Error::InvalidParam(format!("forward-projection shape: {e}")))?;
*out = Tomo::new(array, Layout::Sinogram);
Ok(())
}
}
impl RayProject for CpuBackend {
fn ray_rows(&self, geom: &Geometry, n: usize) -> Result<Vec<Vec<RayRow>>> {
crate::backend::parallel_ray_rows(geom, n)
}
}
fn medfilt3d_core(input: &Array3<f32>, radius: usize, mu_threshold: f32) -> Array3<f32> {
let (dz, dy, dx) = input.dim();
let r = radius as isize;
let diameter = 2 * radius + 1;
let total = diameter * diameter * diameter;
let midval = total / 2; let (dzi, dyi, dxi) = (dz as isize, dy as isize, dx as isize);
let out: Vec<f32> = (0..dz * dy * dx)
.into_par_iter()
.map(|flat| {
let z = (flat / (dy * dx)) as isize;
let rem = flat % (dy * dx);
let y = (rem / dx) as isize;
let x = (rem % dx) as isize;
let center = input[[z as usize, y as usize, x as usize]];
let mut window = Vec::with_capacity(total);
for di in -r..=r {
let xi = {
let v = x + di;
if v < 0 || v >= dxi {
x
} else {
v
}
};
for dj in -r..=r {
let yj = {
let v = y + dj;
if v < 0 || v >= dyi {
y
} else {
v
}
};
for dk in -r..=r {
let zk = {
let v = z + dk;
if v < 0 || v >= dzi {
z
} else {
v
}
};
window.push(input[[zk as usize, yj as usize, xi as usize]]);
}
}
}
window.sort_by(|a, b| a.total_cmp(b));
let median = window[midval];
if (center - median).abs() >= mu_threshold {
median
} else {
center
}
})
.collect();
Array3::from_shape_vec((dz, dy, dx), out)
.expect("medfilt3d_core: output length matches input dims")
}
impl RankFilter for CpuBackend {
fn median3d(&self, vol: &mut Volume<f32>, size: usize) -> Result<()> {
let radius = (size.max(3) - 1) / 2;
vol.array = medfilt3d_core(&vol.array, radius, 0.0);
Ok(())
}
fn remove_outlier3d(&self, data: &mut Tomo<f32>, diff: f32, size: usize) -> Result<()> {
let radius = (size.max(3) - 1) / 2;
data.array = medfilt3d_core(&data.array, radius, diff);
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geometry::Angles;
use ndarray::Array3;
use std::f32::consts::PI;
#[test]
fn minus_log_matches_definition() {
let arr = Array3::from_shape_fn((1, 1, 3), |(_, _, k)| (k as f32 + 1.0) * 0.25);
let mut t = Tomo::new(arr, Layout::Projection);
CpuBackend.minus_log(&mut t).unwrap();
for (k, v) in t.array.iter().enumerate() {
let expected = -(((k as f32 + 1.0) * 0.25f32).ln());
assert!((v - expected).abs() < 1e-6, "k={k} got {v} want {expected}");
}
}
#[test]
fn darkflat_normalizes_to_unity_on_flat_input() {
let data = Array3::from_elem((2, 2, 2), 100.0f32);
let flat = Array3::from_elem((1, 2, 2), 100.0f32);
let dark = Array3::from_elem((1, 2, 2), 0.0f32);
let mut t = Tomo::new(data, Layout::Projection);
CpuBackend
.darkflat(&mut t, &Frames::new(flat), &Frames::new(dark))
.unwrap();
for v in t.array.iter() {
assert!((v - 1.0).abs() < 1e-6);
}
}
#[test]
fn fft_1d_roundtrips() {
let orig: Vec<Complex32> = (0..8).map(|k| Complex32::new(k as f32, 0.0)).collect();
let mut buf = orig.clone();
CpuBackend.fft_1d(&mut buf, 4, 2, false).unwrap();
CpuBackend.fft_1d(&mut buf, 4, 2, true).unwrap();
for (a, b) in buf.iter().zip(orig.iter()) {
assert!((a.re - b.re).abs() < 1e-4, "re {} vs {}", a.re, b.re);
assert!((a.im - b.im).abs() < 1e-4, "im {} vs {}", a.im, b.im);
}
}
#[test]
fn fft_2d_roundtrips() {
let orig: Vec<Complex32> = (0..12)
.map(|k| Complex32::new(k as f32, -(k as f32)))
.collect();
let mut buf = orig.clone();
CpuBackend.fft_2d(&mut buf, 3, 4, 1, false).unwrap();
CpuBackend.fft_2d(&mut buf, 3, 4, 1, true).unwrap();
for (a, b) in buf.iter().zip(orig.iter()) {
assert!((a.re - b.re).abs() < 1e-4 && (a.im - b.im).abs() < 1e-4);
}
}
#[test]
fn fft_1d_rejects_wrong_buffer_len() {
let mut buf = vec![Complex32::new(0.0, 0.0); 5];
assert!(matches!(
CpuBackend.fft_1d(&mut buf, 4, 2, false),
Err(Error::ShapeMismatch { .. })
));
}
#[test]
fn ramp_filter_is_padded_and_symmetric() {
let f = CpuBackend.make_filter(FilterName::Ramp, 8).unwrap();
assert_eq!(f.len(), 32); assert_eq!(f[0], 0.0); assert!(f[16] > f[8] && f[8] > f[4] && f[4] > f[2] && f[2] > f[1]);
assert!((f[16] - 0.5).abs() < 1e-6);
for k in 1..16 {
assert!((f[k] - f[32 - k]).abs() < 1e-6, "asymmetry at {k}");
}
}
#[test]
fn fbp_none_filter_is_identity() {
let arr = ndarray::Array3::from_shape_fn((1, 1, 16), |(_, _, k)| (k as f32 * 0.4).sin());
let orig = arr.clone();
let mut s = Tomo::new(arr, Layout::Sinogram);
let kernel = CpuBackend.make_filter(FilterName::None, 16).unwrap();
let geom = Geometry::parallel(
crate::geometry::Angles::uniform(1, 0.0, std::f32::consts::PI),
16,
1,
1.0,
);
CpuBackend.apply(&mut s, &kernel, &geom).unwrap();
for (a, b) in s.array.iter().zip(orig.iter()) {
assert!((a - b).abs() < 1e-4, "{a} vs {b}");
}
}
#[test]
fn backproject_single_angle_smears_along_ray() {
let mut sarr = Array3::<f32>::zeros((1, 1, 4)); sarr[[0, 0, 1]] = 1.0;
let s = Tomo::new(sarr, Layout::Sinogram);
let geom = Geometry::parallel(Angles::uniform(1, 0.0, PI), 4, 1, 1.0);
let mut out = Volume::new(Array3::<f32>::zeros((1, 4, 4)));
CpuBackend.backproject(&s, &geom, &mut out).unwrap();
for iy in 0..4 {
assert!((out.array[[0, iy, 1]] - 1.0).abs() < 1e-4, "iy={iy}");
assert!(out.array[[0, iy, 0]].abs() < 1e-6);
assert!(out.array[[0, iy, 2]].abs() < 1e-6);
}
}
#[test]
fn forward_project_center_pixel_hits_center_column() {
let mut varr = Array3::<f32>::zeros((1, 4, 4));
varr[[0, 2, 2]] = 1.0;
let v = Volume::new(varr);
let nang = 4;
let geom = Geometry::parallel(Angles::uniform(nang, 0.0, PI), 4, 1, 1.0);
let mut s = Tomo::new(Array3::<f32>::zeros((1, 4, 4)), Layout::Sinogram);
CpuBackend.project(&v, &geom, &mut s).unwrap();
assert_eq!(s.layout, Layout::Sinogram);
assert_eq!(s.array.dim(), (1, 4, 4));
for ia in 0..4 {
assert!((s.array[[0, ia, 2]] - 1.0).abs() < 1e-4, "ia={ia}");
assert!(s.array[[0, ia, 0]].abs() < 1e-6);
}
}
}