use coeus_core::{
Backend, CpuAddressableStorage, CpuAddressableStorageMut, Float, FloatElement, Scalar,
};
use coeus_tensor::Tensor;
mod private {
pub trait Sealed {}
}
pub trait BoundaryPolicy: private::Sealed + Copy + Default {
fn neighbours<T: Float + FloatElement>(coordinate: T, extent: usize) -> (usize, usize, T, T);
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Replicate;
impl private::Sealed for Replicate {}
impl BoundaryPolicy for Replicate {
fn neighbours<T: Float + FloatElement>(coordinate: T, extent: usize) -> (usize, usize, T, T) {
let lower_value = Float::floor(coordinate);
let upper_weight = coordinate - lower_value;
let upper_bound = T::from_count(extent - 1);
let lower = clamp_index(lower_value, upper_bound);
let upper = clamp_index(lower_value + T::ONE, upper_bound);
(lower, upper, T::ONE - upper_weight, upper_weight)
}
}
fn clamp_index<T: Float>(value: T, upper: T) -> usize {
let clamped = if value < T::ZERO {
T::ZERO
} else if value > upper {
upper
} else {
value
};
clamped.to_f64() as usize
}
#[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<T: Scalar, B: Backend> {
pub image: Tensor<T, B>,
pub grid: Tensor<T, 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>,
},
}
#[derive(Debug, thiserror::Error)]
pub enum InterpolationFailure<E> {
#[error(transparent)]
Contract(#[from] InterpolationError),
#[error("interpolation backend failure: {0}")]
Backend(E),
}
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<T, const D: usize, B, P>(
image: &Tensor<T, B>,
grid: &Tensor<T, B>,
_policy: P,
) -> Result<Tensor<T, B>, InterpolationFailure<B::Error>>
where
T: Float + FloatElement,
B: Backend + Default,
P: BoundaryPolicy,
Dimension<D>: SupportedDimension,
B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
let contract = validate::<D>(image.shape(), grid.shape())?;
let image = image
.to_contiguous()
.map_err(InterpolationFailure::Backend)?;
let grid = grid
.to_contiguous()
.map_err(InterpolationFailure::Backend)?;
let image_values = image.as_slice();
let grid_values = grid.as_slice();
let output_len = checked_product(&contract.output_shape)?;
let mut output = vec![T::ZERO; 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, T::ZERO, T::ZERO); D];
for (axis, entry) in neighbours.iter_mut().enumerate() {
let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
if !Float::is_finite(coordinate) {
return Err(InterpolationError::NonFiniteCoordinate { axis, point }.into());
}
*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 = T::ZERO;
for corner in 0..corner_count {
let mut indices = [0; D];
let mut weight = T::ONE;
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;
}
}
}
Tensor::from_slice_on(contract.output_shape, &output, &B::default())
.map_err(InterpolationFailure::Backend)
}
pub fn linear_interpolation_backward<T, const D: usize, B, P>(
image: &Tensor<T, B>,
grid: &Tensor<T, B>,
grad_output: &Tensor<T, B>,
_policy: P,
) -> Result<InterpolationGradients<T, B>, InterpolationFailure<B::Error>>
where
T: Float + FloatElement,
B: Backend + Default,
P: BoundaryPolicy,
Dimension<D>: SupportedDimension,
B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
{
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(),
}
.into());
}
let image = image
.to_contiguous()
.map_err(InterpolationFailure::Backend)?;
let grid = grid
.to_contiguous()
.map_err(InterpolationFailure::Backend)?;
let grad_output = grad_output
.to_contiguous()
.map_err(InterpolationFailure::Backend)?;
let image_values = image.as_slice();
let grid_values = grid.as_slice();
let upstream = grad_output.as_slice();
let mut image_gradient = vec![T::ZERO; image_values.len()];
let mut grid_gradient = vec![T::ZERO; 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, T::ZERO, T::ZERO); D];
for (axis, entry) in neighbours.iter_mut().enumerate() {
let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
if !Float::is_finite(coordinate) {
return Err(InterpolationError::NonFiniteCoordinate { axis, point }.into());
}
*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 = [T::ZERO; 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().copied().fold(T::ONE, |acc, w| acc * w);
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 {
T::ONE
} else {
T::ZERO - T::ONE
};
let other_weight = weights
.iter()
.enumerate()
.filter(|(candidate, _)| *candidate != axis)
.map(|(_, weight)| *weight)
.fold(T::ONE, |acc, w| acc * w);
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)
.map_err(InterpolationFailure::Backend)?,
grid: Tensor::from_slice_on(grid_shape, &grid_gradient, &backend)
.map_err(InterpolationFailure::Backend)?,
})
}