Skip to main content

coeus_ops/
interpolation.rs

1//! Dimension-generic coordinate-grid interpolation operations.
2
3use coeus_core::{
4    Backend, CpuAddressableStorage, CpuAddressableStorageMut, Float, FloatElement, Scalar,
5};
6use coeus_tensor::Tensor;
7
8mod private {
9    pub trait Sealed {}
10}
11
12/// Static boundary behavior for linear interpolation.
13pub trait BoundaryPolicy: private::Sealed + Copy + Default {
14    /// Returns lower/upper indices and their interpolation weights.
15    fn neighbours<T: Float + FloatElement>(coordinate: T, extent: usize) -> (usize, usize, T, T);
16}
17
18/// Replicate the nearest border value outside the image extent.
19#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
20pub struct Replicate;
21
22impl private::Sealed for Replicate {}
23
24impl BoundaryPolicy for Replicate {
25    fn neighbours<T: Float + FloatElement>(coordinate: T, extent: usize) -> (usize, usize, T, T) {
26        let lower_value = Float::floor(coordinate);
27        let upper_weight = coordinate - lower_value;
28        let upper_bound = T::from_count(extent - 1);
29        let lower = clamp_index(lower_value, upper_bound);
30        let upper = clamp_index(lower_value + T::ONE, upper_bound);
31        (lower, upper, T::ONE - upper_weight, upper_weight)
32    }
33}
34
35/// Clamp an integer-valued coordinate into `[0, upper]` and return it as an
36/// index.
37///
38/// `Float` exposes no float-to-integer conversion, so the clamped value
39/// widens through `NumericElement::to_f64`. The widening is exact — `f64`
40/// holds every value of the narrower formats — and a valid input is an
41/// integer in `[0, upper]`, so the final cast neither saturates nor
42/// truncates. Callers reject non-finite coordinates before reaching here; a
43/// NaN compares false against both bounds and saturates to `0`.
44fn clamp_index<T: Float>(value: T, upper: T) -> usize {
45    let clamped = if value < T::ZERO {
46        T::ZERO
47    } else if value > upper {
48        upper
49    } else {
50        value
51    };
52    clamped.to_f64() as usize
53}
54
55/// Const-dimension marker restricting interpolation monomorphizations.
56#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
57pub struct Dimension<const D: usize>;
58
59/// Compile-time evidence that an interpolation dimension is implemented.
60pub trait SupportedDimension: private::Sealed {}
61
62impl private::Sealed for Dimension<2> {}
63impl private::Sealed for Dimension<3> {}
64impl SupportedDimension for Dimension<2> {}
65impl SupportedDimension for Dimension<3> {}
66
67/// Gradients produced by dimension-generic linear interpolation reverse mode.
68pub struct InterpolationGradients<T: Scalar, B: Backend> {
69    /// Gradient with respect to image values.
70    pub image: Tensor<T, B>,
71    /// Gradient with respect to sampling coordinates.
72    pub grid: Tensor<T, B>,
73}
74
75/// Contract failures for [`linear_interpolation`].
76#[derive(Debug, thiserror::Error, PartialEq, Eq)]
77pub enum InterpolationError {
78    /// The image rank differs from `[batch, channel, spatial...]`.
79    #[error("{dimension}-D interpolation requires image rank {expected}, got {actual}")]
80    ImageRank {
81        /// Spatial dimension.
82        dimension: usize,
83        /// Required rank.
84        expected: usize,
85        /// Supplied rank.
86        actual: usize,
87    },
88    /// The grid rank differs from `[batch, coordinate, spatial...]`.
89    #[error("{dimension}-D interpolation requires grid rank {expected}, got {actual}")]
90    GridRank {
91        /// Spatial dimension.
92        dimension: usize,
93        /// Required rank.
94        expected: usize,
95        /// Supplied rank.
96        actual: usize,
97    },
98    /// The grid batch does not match the image batch.
99    #[error("linear interpolation batch mismatch: image {image}, grid {grid}")]
100    BatchMismatch {
101        /// Image batch extent.
102        image: usize,
103        /// Grid batch extent.
104        grid: usize,
105    },
106    /// The grid coordinate-channel count differs from the spatial dimension.
107    #[error("linear interpolation grid requires {expected} coordinate channels, got {actual}")]
108    GridChannels {
109        /// Spatial dimension.
110        expected: usize,
111        /// Supplied channel count.
112        actual: usize,
113    },
114    /// An input spatial axis is empty.
115    #[error("linear interpolation image spatial axis {axis} is empty")]
116    EmptySpatialAxis {
117        /// Zero-based spatial axis.
118        axis: usize,
119    },
120    /// A sampling coordinate is NaN or infinite.
121    #[error("linear interpolation coordinate axis {axis} at output point {point} is not finite")]
122    NonFiniteCoordinate {
123        /// Coordinate axis.
124        axis: usize,
125        /// Flattened output point.
126        point: usize,
127    },
128    /// A shape product overflowed `usize`.
129    #[error("linear interpolation element count overflow")]
130    SizeOverflow,
131    /// The upstream gradient shape does not match the interpolation output.
132    #[error("linear interpolation gradient shape mismatch: expected {expected:?}, got {actual:?}")]
133    GradientShape {
134        /// Shape implied by the image and sampling grid.
135        expected: Vec<usize>,
136        /// Supplied upstream-gradient shape.
137        actual: Vec<usize>,
138    },
139}
140
141/// Interpolation contract or storage failure.
142#[derive(Debug, thiserror::Error)]
143pub enum InterpolationFailure<E> {
144    /// The interpolation contract was violated.
145    #[error(transparent)]
146    Contract(#[from] InterpolationError),
147    /// The selected backend rejected a storage operation.
148    #[error("interpolation backend failure: {0}")]
149    Backend(E),
150}
151
152struct Contract {
153    batch: usize,
154    channels: usize,
155    input_spatial: Vec<usize>,
156    output_spatial: Vec<usize>,
157    input_points: usize,
158    output_points: usize,
159    output_shape: Vec<usize>,
160}
161
162fn checked_product(extents: &[usize]) -> Result<usize, InterpolationError> {
163    extents
164        .iter()
165        .copied()
166        .try_fold(1usize, usize::checked_mul)
167        .ok_or(InterpolationError::SizeOverflow)
168}
169
170fn validate<const D: usize>(image: &[usize], grid: &[usize]) -> Result<Contract, InterpolationError>
171where
172    Dimension<D>: SupportedDimension,
173{
174    let rank = D + 2;
175    if image.len() != rank {
176        return Err(InterpolationError::ImageRank {
177            dimension: D,
178            expected: rank,
179            actual: image.len(),
180        });
181    }
182    if grid.len() != rank {
183        return Err(InterpolationError::GridRank {
184            dimension: D,
185            expected: rank,
186            actual: grid.len(),
187        });
188    }
189    if image[0] != grid[0] {
190        return Err(InterpolationError::BatchMismatch {
191            image: image[0],
192            grid: grid[0],
193        });
194    }
195    if grid[1] != D {
196        return Err(InterpolationError::GridChannels {
197            expected: D,
198            actual: grid[1],
199        });
200    }
201    for (axis, &extent) in image[2..].iter().enumerate() {
202        if extent == 0 {
203            return Err(InterpolationError::EmptySpatialAxis { axis });
204        }
205    }
206    let input_spatial = image[2..].to_vec();
207    let output_spatial = grid[2..].to_vec();
208    let input_points = checked_product(&input_spatial)?;
209    let output_points = checked_product(&output_spatial)?;
210    let output_shape = [image[0], image[1]]
211        .into_iter()
212        .chain(output_spatial.iter().copied())
213        .collect::<Vec<_>>();
214    checked_product(&output_shape)?;
215    Ok(Contract {
216        batch: image[0],
217        channels: image[1],
218        input_spatial,
219        output_spatial,
220        input_points,
221        output_points,
222        output_shape,
223    })
224}
225
226fn spatial_offset(indices: &[usize], extents: &[usize]) -> usize {
227    indices
228        .iter()
229        .zip(extents)
230        .fold(0, |offset, (&index, &extent)| offset * extent + index)
231}
232
233/// Sample a 2-D or 3-D image at a voxel-coordinate grid.
234///
235/// `image` has shape `[batch, channel, spatial...]`; `grid` has shape
236/// `[batch, D, output_spatial...]`. Coordinate channels follow image spatial
237/// axis order. `D` is restricted to 2 or 3, while `P` selects boundary
238/// behavior at compile time with zero runtime storage.
239///
240/// # Errors
241///
242/// Returns [`InterpolationError`] when ranks, batches, coordinate channels,
243/// spatial extents, finite-coordinate requirement, or shape products violate
244/// the contract.
245pub fn linear_interpolation<T, const D: usize, B, P>(
246    image: &Tensor<T, B>,
247    grid: &Tensor<T, B>,
248    _policy: P,
249) -> Result<Tensor<T, B>, InterpolationFailure<B::Error>>
250where
251    T: Float + FloatElement,
252    B: Backend + Default,
253    P: BoundaryPolicy,
254    Dimension<D>: SupportedDimension,
255    B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
256{
257    let contract = validate::<D>(image.shape(), grid.shape())?;
258    let image = image
259        .to_contiguous()
260        .map_err(InterpolationFailure::Backend)?;
261    let grid = grid
262        .to_contiguous()
263        .map_err(InterpolationFailure::Backend)?;
264    let image_values = image.as_slice();
265    let grid_values = grid.as_slice();
266    let output_len = checked_product(&contract.output_shape)?;
267    let mut output = vec![T::ZERO; output_len];
268    let corner_count = 1usize << D;
269
270    for batch in 0..contract.batch {
271        for point in 0..contract.output_points {
272            let mut neighbours = [(0, 0, T::ZERO, T::ZERO); D];
273            for (axis, entry) in neighbours.iter_mut().enumerate() {
274                let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
275                if !Float::is_finite(coordinate) {
276                    return Err(InterpolationError::NonFiniteCoordinate { axis, point }.into());
277                }
278                *entry = P::neighbours(coordinate, contract.input_spatial[axis]);
279            }
280            for channel in 0..contract.channels {
281                let base = (batch * contract.channels + channel) * contract.input_points;
282                let mut value = T::ZERO;
283                for corner in 0..corner_count {
284                    let mut indices = [0; D];
285                    let mut weight = T::ONE;
286                    for (axis, &(lower, upper, lower_weight, upper_weight)) in
287                        neighbours.iter().enumerate()
288                    {
289                        let upper_side = corner & (1 << axis) != 0;
290                        indices[axis] = if upper_side { upper } else { lower };
291                        weight *= if upper_side {
292                            upper_weight
293                        } else {
294                            lower_weight
295                        };
296                    }
297                    value += image_values[base + spatial_offset(&indices, &contract.input_spatial)]
298                        * weight;
299                }
300                output[(batch * contract.channels + channel) * contract.output_points + point] =
301                    value;
302            }
303        }
304    }
305
306    Tensor::from_slice_on(contract.output_shape, &output, &B::default())
307        .map_err(InterpolationFailure::Backend)
308}
309
310/// Backpropagate through [`linear_interpolation`].
311///
312/// Returns gradients for `(image, grid)`. The image derivative scatters to
313/// `2^D` neighbours. Each coordinate derivative differentiates the same
314/// multilinear polynomial; replicated axes have zero derivative when both
315/// neighbours resolve to one border element.
316///
317/// # Errors
318///
319/// Returns [`InterpolationError`] under the forward contract failures or when
320/// `grad_output` does not have the implied output shape. Non-finite sampling
321/// coordinates are rejected before derivative arithmetic.
322pub fn linear_interpolation_backward<T, const D: usize, B, P>(
323    image: &Tensor<T, B>,
324    grid: &Tensor<T, B>,
325    grad_output: &Tensor<T, B>,
326    _policy: P,
327) -> Result<InterpolationGradients<T, B>, InterpolationFailure<B::Error>>
328where
329    T: Float + FloatElement,
330    B: Backend + Default,
331    P: BoundaryPolicy,
332    Dimension<D>: SupportedDimension,
333    B::DeviceBuffer<T>: CpuAddressableStorage<T> + CpuAddressableStorageMut<T>,
334{
335    let contract = validate::<D>(image.shape(), grid.shape())?;
336    if grad_output.shape() != contract.output_shape {
337        return Err(InterpolationError::GradientShape {
338            expected: contract.output_shape,
339            actual: grad_output.shape().to_vec(),
340        }
341        .into());
342    }
343    let image = image
344        .to_contiguous()
345        .map_err(InterpolationFailure::Backend)?;
346    let grid = grid
347        .to_contiguous()
348        .map_err(InterpolationFailure::Backend)?;
349    let grad_output = grad_output
350        .to_contiguous()
351        .map_err(InterpolationFailure::Backend)?;
352    let image_values = image.as_slice();
353    let grid_values = grid.as_slice();
354    let upstream = grad_output.as_slice();
355    let mut image_gradient = vec![T::ZERO; image_values.len()];
356    let mut grid_gradient = vec![T::ZERO; grid_values.len()];
357    let corner_count = 1usize << D;
358
359    for batch in 0..contract.batch {
360        for point in 0..contract.output_points {
361            let mut neighbours = [(0, 0, T::ZERO, T::ZERO); D];
362            for (axis, entry) in neighbours.iter_mut().enumerate() {
363                let coordinate = grid_values[(batch * D + axis) * contract.output_points + point];
364                if !Float::is_finite(coordinate) {
365                    return Err(InterpolationError::NonFiniteCoordinate { axis, point }.into());
366                }
367                *entry = P::neighbours(coordinate, contract.input_spatial[axis]);
368            }
369            for channel in 0..contract.channels {
370                let base = (batch * contract.channels + channel) * contract.input_points;
371                let output_index =
372                    (batch * contract.channels + channel) * contract.output_points + point;
373                let grad = upstream[output_index];
374                for corner in 0..corner_count {
375                    let mut indices = [0; D];
376                    let mut weights = [T::ZERO; D];
377                    for (axis, &(lower, upper, lower_weight, upper_weight)) in
378                        neighbours.iter().enumerate()
379                    {
380                        let upper_side = corner & (1 << axis) != 0;
381                        indices[axis] = if upper_side { upper } else { lower };
382                        weights[axis] = if upper_side {
383                            upper_weight
384                        } else {
385                            lower_weight
386                        };
387                    }
388                    let input_index = base + spatial_offset(&indices, &contract.input_spatial);
389                    let value = image_values[input_index];
390                    let weight = weights.iter().copied().fold(T::ONE, |acc, w| acc * w);
391                    image_gradient[input_index] += grad * weight;
392                    for axis in 0..D {
393                        let (lower, upper, _, _) = neighbours[axis];
394                        if lower == upper {
395                            continue;
396                        }
397                        let sign = if corner & (1 << axis) != 0 {
398                            T::ONE
399                        } else {
400                            T::ZERO - T::ONE
401                        };
402                        let other_weight = weights
403                            .iter()
404                            .enumerate()
405                            .filter(|(candidate, _)| *candidate != axis)
406                            .map(|(_, weight)| *weight)
407                            .fold(T::ONE, |acc, w| acc * w);
408                        grid_gradient[(batch * D + axis) * contract.output_points + point] +=
409                            grad * value * sign * other_weight;
410                    }
411                }
412            }
413        }
414    }
415
416    let backend = B::default();
417    let image_shape = [contract.batch, contract.channels]
418        .into_iter()
419        .chain(contract.input_spatial)
420        .collect::<Vec<_>>();
421    let grid_shape = [contract.batch, D]
422        .into_iter()
423        .chain(contract.output_spatial)
424        .collect::<Vec<_>>();
425    Ok(InterpolationGradients {
426        image: Tensor::from_slice_on(image_shape, &image_gradient, &backend)
427            .map_err(InterpolationFailure::Backend)?,
428        grid: Tensor::from_slice_on(grid_shape, &grid_gradient, &backend)
429            .map_err(InterpolationFailure::Backend)?,
430    })
431}