1use coeus_core::{
4 Backend, CpuAddressableStorage, CpuAddressableStorageMut, Float, FloatElement, Scalar,
5};
6use coeus_tensor::Tensor;
7
8mod private {
9 pub trait Sealed {}
10}
11
12pub trait BoundaryPolicy: private::Sealed + Copy + Default {
14 fn neighbours<T: Float + FloatElement>(coordinate: T, extent: usize) -> (usize, usize, T, T);
16}
17
18#[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
35fn 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
57pub struct Dimension<const D: usize>;
58
59pub 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
67pub struct InterpolationGradients<T: Scalar, B: Backend> {
69 pub image: Tensor<T, B>,
71 pub grid: Tensor<T, B>,
73}
74
75#[derive(Debug, thiserror::Error, PartialEq, Eq)]
77pub enum InterpolationError {
78 #[error("{dimension}-D interpolation requires image rank {expected}, got {actual}")]
80 ImageRank {
81 dimension: usize,
83 expected: usize,
85 actual: usize,
87 },
88 #[error("{dimension}-D interpolation requires grid rank {expected}, got {actual}")]
90 GridRank {
91 dimension: usize,
93 expected: usize,
95 actual: usize,
97 },
98 #[error("linear interpolation batch mismatch: image {image}, grid {grid}")]
100 BatchMismatch {
101 image: usize,
103 grid: usize,
105 },
106 #[error("linear interpolation grid requires {expected} coordinate channels, got {actual}")]
108 GridChannels {
109 expected: usize,
111 actual: usize,
113 },
114 #[error("linear interpolation image spatial axis {axis} is empty")]
116 EmptySpatialAxis {
117 axis: usize,
119 },
120 #[error("linear interpolation coordinate axis {axis} at output point {point} is not finite")]
122 NonFiniteCoordinate {
123 axis: usize,
125 point: usize,
127 },
128 #[error("linear interpolation element count overflow")]
130 SizeOverflow,
131 #[error("linear interpolation gradient shape mismatch: expected {expected:?}, got {actual:?}")]
133 GradientShape {
134 expected: Vec<usize>,
136 actual: Vec<usize>,
138 },
139}
140
141#[derive(Debug, thiserror::Error)]
143pub enum InterpolationFailure<E> {
144 #[error(transparent)]
146 Contract(#[from] InterpolationError),
147 #[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
233pub 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
310pub 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}