use coeus_core::{Backend, CpuAddressableStorage, CpuAddressableStorageMut};
use coeus_tensor::Tensor;
mod private {
pub trait Sealed {}
}
pub trait BoundaryPolicy: private::Sealed + Copy + Default {
fn neighbours(coordinate: f32, extent: usize) -> (usize, usize, f32, f32);
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Replicate;
impl private::Sealed for Replicate {}
impl BoundaryPolicy for Replicate {
fn neighbours(coordinate: f32, extent: usize) -> (usize, usize, f32, f32) {
let lower_value = coordinate.floor();
let upper_weight = coordinate - lower_value;
let upper_bound = (extent - 1) as f32;
let lower = lower_value.clamp(0.0, upper_bound) as usize;
let upper = (lower_value + 1.0).clamp(0.0, upper_bound) as usize;
(lower, upper, 1.0 - upper_weight, upper_weight)
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Dimension<const D: usize>;
pub trait SupportedDimension: private::Sealed {}
impl private::Sealed for Dimension<2> {}
impl private::Sealed for Dimension<3> {}
impl SupportedDimension for Dimension<2> {}
impl SupportedDimension for Dimension<3> {}
pub struct InterpolationGradients<B: Backend> {
pub image: Tensor<f32, B>,
pub grid: Tensor<f32, B>,
}
#[derive(Debug, thiserror::Error, PartialEq, Eq)]
pub enum InterpolationError {
#[error("{dimension}-D interpolation requires image rank {expected}, got {actual}")]
ImageRank {
dimension: usize,
expected: usize,
actual: usize,
},
#[error("{dimension}-D interpolation requires grid rank {expected}, got {actual}")]
GridRank {
dimension: usize,
expected: usize,
actual: usize,
},
#[error("linear interpolation batch mismatch: image {image}, grid {grid}")]
BatchMismatch {
image: usize,
grid: usize,
},
#[error("linear interpolation grid requires {expected} coordinate channels, got {actual}")]
GridChannels {
expected: usize,
actual: usize,
},
#[error("linear interpolation image spatial axis {axis} is empty")]
EmptySpatialAxis {
axis: usize,
},
#[error("linear interpolation coordinate axis {axis} at output point {point} is not finite")]
NonFiniteCoordinate {
axis: usize,
point: usize,
},
#[error("linear interpolation element count overflow")]
SizeOverflow,
#[error("linear interpolation gradient shape mismatch: expected {expected:?}, got {actual:?}")]
GradientShape {
expected: Vec<usize>,
actual: Vec<usize>,
},
}
struct Contract {
batch: usize,
channels: usize,
input_spatial: Vec<usize>,
output_spatial: Vec<usize>,
input_points: usize,
output_points: usize,
output_shape: Vec<usize>,
}
fn checked_product(extents: &[usize]) -> Result<usize, InterpolationError> {
extents
.iter()
.copied()
.try_fold(1usize, usize::checked_mul)
.ok_or(InterpolationError::SizeOverflow)
}
fn validate<const D: usize>(image: &[usize], grid: &[usize]) -> Result<Contract, InterpolationError>
where
Dimension<D>: SupportedDimension,
{
let rank = D + 2;
if image.len() != rank {
return Err(InterpolationError::ImageRank {
dimension: D,
expected: rank,
actual: image.len(),
});
}
if grid.len() != rank {
return Err(InterpolationError::GridRank {
dimension: D,
expected: rank,
actual: grid.len(),
});
}
if image[0] != grid[0] {
return Err(InterpolationError::BatchMismatch {
image: image[0],
grid: grid[0],
});
}
if grid[1] != D {
return Err(InterpolationError::GridChannels {
expected: D,
actual: grid[1],
});
}
for (axis, &extent) in image[2..].iter().enumerate() {
if extent == 0 {
return Err(InterpolationError::EmptySpatialAxis { axis });
}
}
let input_spatial = image[2..].to_vec();
let output_spatial = grid[2..].to_vec();
let input_points = checked_product(&input_spatial)?;
let output_points = checked_product(&output_spatial)?;
let output_shape = [image[0], image[1]]
.into_iter()
.chain(output_spatial.iter().copied())
.collect::<Vec<_>>();
checked_product(&output_shape)?;
Ok(Contract {
batch: image[0],
channels: image[1],
input_spatial,
output_spatial,
input_points,
output_points,
output_shape,
})
}
fn spatial_offset(indices: &[usize], extents: &[usize]) -> usize {
indices
.iter()
.zip(extents)
.fold(0, |offset, (&index, &extent)| offset * extent + index)
}
pub fn linear_interpolation<const D: usize, B, P>(
image: &Tensor<f32, B>,
grid: &Tensor<f32, B>,
_policy: P,
) -> Result<Tensor<f32, B>, InterpolationError>
where
B: Backend + Default,
P: BoundaryPolicy,
Dimension<D>: SupportedDimension,
B::DeviceBuffer<f32>: CpuAddressableStorage<f32> + CpuAddressableStorageMut<f32>,
{
let contract = validate::<D>(image.shape(), grid.shape())?;
let image = image.to_contiguous();
let grid = grid.to_contiguous();
let image_values = image.as_slice();
let grid_values = grid.as_slice();
let output_len = checked_product(&contract.output_shape)?;
let mut output = vec![0.0; output_len];
let corner_count = 1usize << D;
for batch in 0..contract.batch {
for point in 0..contract.output_points {
let mut neighbours = [(0, 0, 0.0, 0.0); D];
for (axis, entry) in neighbours.iter_mut().enumerate() {
let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
if !coordinate.is_finite() {
return Err(InterpolationError::NonFiniteCoordinate { axis, point });
}
*entry = P::neighbours(coordinate, contract.input_spatial[axis]);
}
for channel in 0..contract.channels {
let base = (batch * contract.channels + channel) * contract.input_points;
let mut value = 0.0;
for corner in 0..corner_count {
let mut indices = [0; D];
let mut weight = 1.0;
for (axis, &(lower, upper, lower_weight, upper_weight)) in
neighbours.iter().enumerate()
{
let upper_side = corner & (1 << axis) != 0;
indices[axis] = if upper_side { upper } else { lower };
weight *= if upper_side {
upper_weight
} else {
lower_weight
};
}
value += image_values[base + spatial_offset(&indices, &contract.input_spatial)]
* weight;
}
output[(batch * contract.channels + channel) * contract.output_points + point] =
value;
}
}
}
Ok(Tensor::from_slice_on(
contract.output_shape,
&output,
&B::default(),
))
}
pub fn linear_interpolation_backward<const D: usize, B, P>(
image: &Tensor<f32, B>,
grid: &Tensor<f32, B>,
grad_output: &Tensor<f32, B>,
_policy: P,
) -> Result<InterpolationGradients<B>, InterpolationError>
where
B: Backend + Default,
P: BoundaryPolicy,
Dimension<D>: SupportedDimension,
B::DeviceBuffer<f32>: CpuAddressableStorage<f32> + CpuAddressableStorageMut<f32>,
{
let contract = validate::<D>(image.shape(), grid.shape())?;
if grad_output.shape() != contract.output_shape {
return Err(InterpolationError::GradientShape {
expected: contract.output_shape,
actual: grad_output.shape().to_vec(),
});
}
let image = image.to_contiguous();
let grid = grid.to_contiguous();
let grad_output = grad_output.to_contiguous();
let image_values = image.as_slice();
let grid_values = grid.as_slice();
let upstream = grad_output.as_slice();
let mut image_gradient = vec![0.0; image_values.len()];
let mut grid_gradient = vec![0.0; grid_values.len()];
let corner_count = 1usize << D;
for batch in 0..contract.batch {
for point in 0..contract.output_points {
let mut neighbours = [(0, 0, 0.0, 0.0); D];
for (axis, entry) in neighbours.iter_mut().enumerate() {
let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
if !coordinate.is_finite() {
return Err(InterpolationError::NonFiniteCoordinate { axis, point });
}
*entry = P::neighbours(coordinate, contract.input_spatial[axis]);
}
for channel in 0..contract.channels {
let base = (batch * contract.channels + channel) * contract.input_points;
let output_index =
(batch * contract.channels + channel) * contract.output_points + point;
let grad = upstream[output_index];
for corner in 0..corner_count {
let mut indices = [0; D];
let mut weights = [0.0; D];
for (axis, &(lower, upper, lower_weight, upper_weight)) in
neighbours.iter().enumerate()
{
let upper_side = corner & (1 << axis) != 0;
indices[axis] = if upper_side { upper } else { lower };
weights[axis] = if upper_side {
upper_weight
} else {
lower_weight
};
}
let input_index = base + spatial_offset(&indices, &contract.input_spatial);
let value = image_values[input_index];
let weight = weights.iter().product::<f32>();
image_gradient[input_index] += grad * weight;
for axis in 0..D {
let (lower, upper, _, _) = neighbours[axis];
if lower == upper {
continue;
}
let sign = if corner & (1 << axis) != 0 { 1.0 } else { -1.0 };
let other_weight = weights
.iter()
.enumerate()
.filter(|(candidate, _)| *candidate != axis)
.map(|(_, weight)| *weight)
.product::<f32>();
grid_gradient[(batch * D + axis) * contract.output_points + point] +=
grad * value * sign * other_weight;
}
}
}
}
}
let backend = B::default();
let image_shape = [contract.batch, contract.channels]
.into_iter()
.chain(contract.input_spatial)
.collect::<Vec<_>>();
let grid_shape = [contract.batch, D]
.into_iter()
.chain(contract.output_spatial)
.collect::<Vec<_>>();
Ok(InterpolationGradients {
image: Tensor::from_slice_on(image_shape, &image_gradient, &backend),
grid: Tensor::from_slice_on(grid_shape, &grid_gradient, &backend),
})
}