resampler

resampler: fast differentiable resizing and warping of arbitrary grids.

CI PyPI Python License

Hugues Hoppe    2026

[Open in Colab]   [Kaggle]   [MyBinder]   [DeepNote]   [GitHub source]   [API docs]   [PyPI package]

The notebook resampler_notebook.ipynb demonstrates the resampler library and contains documentation, usage examples, unit tests, and experiments.

Overview

The resampler library enables fast differentiable resizing and warping of arbitrary grids. It supports:

  • grids of any dimension (e.g., 1D, 2D images, 3D video, 4D batches of videos), containing

  • samples of any shape (e.g., scalars, colors, motion vectors, Jacobian matrices) and

  • any numeric type (e.g., uint8, float64, complex128)

  • within several array libraries (numpy, torch, and jax);

  • either 'dual' ("half-integer") or 'primal' grid-type for each dimension;

  • many boundary rules, specified per dimension, extensible via subclassing;

  • an extensible set of filter kernels, selectable per dimension;

  • optional gamma transfer functions for correct linear-space filtering;

  • prefiltering for accurate antialiasing when resize downsampling;

  • efficient backpropagation of gradients for torch and jax;

  • few dependencies (only numpy and scipy) and no C extension code, yet

  • faster resizing than the C++ implementation in torch.nn.

A key strategy is to leverage existing sparse matrix representations and operations.

Example usage

!pip install -q mediapy numpy resampler

import mediapy as media
import numpy as np
import resampler
array = np.random.default_rng(1).random((4, 6, 3))  # 4x6 RGB image.
upsampled = resampler.resize(array, (128, 192))  # To 128x192 resolution.
media.show_images({'4x6': array, '128x192': upsampled}, height=128)

image = media.read_image('https://github.com/hhoppe/data/raw/main/image.png')
downsampled = resampler.resize(image, (32, 32))
media.show_images({'128x128': image, '32x32': downsampled}, height=128)

import matplotlib.pyplot as plt
array = np.array([3.0, 5.0, 8.0, 7.0])  # 4 source samples in 1D.
new_dual = resampler.resize(array, (32,))  # (default gridtype='dual') 8x resolution.
new_primal = resampler.resize(array, (25,), gridtype='primal')  # 8x resolution.

_, axs = plt.subplots(1, 2, figsize=(7, 1.5))
axs[0].set_title("gridtype='dual'")
axs[0].plot((np.arange(len(array)) + 0.5) / len(array), array, 'o')
axs[0].plot((np.arange(len(new_dual)) + 0.5) / len(new_dual), new_dual, '.')
axs[1].set_title("gridtype='primal'")
axs[1].plot(np.arange(len(array)) / (len(array) - 1), array, 'o')
axs[1].plot(np.arange(len(new_primal)) / (len(new_primal) - 1), new_primal, '.')
plt.show()

batch_size = 4
batch_of_images = media.moving_circle((16, 16), batch_size)
upsampled = resampler.resize(batch_of_images, (batch_size, 64, 64))
media.show_videos({'original': batch_of_images, 'upsampled': upsampled}, fps=1)

original upsampled

Most examples above use the default resize() settings:

  • gridtype='dual' for both source and destination arrays,
  • boundary='auto' which uses 'reflect' for upsampling and 'clamp' for downsampling,
  • filter='lanczos3' (a Lanczos kernel with radius 3),
  • gamma=None which by default uses the 'power2' transfer function for the uint8 image in the second example,
  • scale=1.0, translate=0.0 (no domain transformation),
  • default precision and output dtype.

Advanced usage

Map an image to a wider grid using custom scale and translate vectors, with horizontal 'reflect' and vertical 'natural' boundary rules, providing a constant value for the exterior, using different filters (Lanczos and O-MOMS) in the two dimensions, disabling gamma correction, performing computations in double-precision, and returning an output array in single-precision:

new = resampler.resize(
    image, (128, 512), boundary=('natural', 'reflect'), cval=(0.2, 0.7, 0.3),
    filter=('lanczos3', 'omoms5'), gamma='identity', scale=(0.8, 0.25),
    translate=(0.1, 0.35), precision='float64', dtype='float32')
media.show_images({'image': image, 'new': new})

Warp an image by transforming it using polar coordinates:

shape = image.shape[:2]
yx = ((np.indices(shape).T + 0.5) / shape - 0.5).T  # [-0.5, 0.5]^2
radius, angle = np.linalg.norm(yx, axis=0), np.arctan2(*yx)
angle += (0.8 - radius).clip(0, 1) * 2.0 - 0.6
coords = np.dstack((np.sin(angle) * radius, np.cos(angle) * radius)) + 0.5
resampled = resampler.resample(image, coords, boundary='constant')
media.show_images({'image': image, 'resampled': resampled})

Limitations

  • Filters are assumed to be separable.
  • Although resize implements prefiltering, resample does not yet have it (and therefore may have aliased results if downsampling).
  • Differentiability is only with respect to the grid values, not with respect to the resize shape, scale, translation, or the resampling coordinates.

   1"""resampler: fast differentiable resizing and warping of arbitrary grids.
   2
   3.. include:: ../README.md
   4"""
   5
   6from __future__ import annotations
   7
   8# Note that pdoc uses the module docstring in both __init__.py (for section headings) and
   9# __init__.pyi (for the actual content)!
  10
  11__docformat__ = 'google'
  12__version__ = '1.1.7'
  13__version_info__ = tuple(int(num) for num in __version__.split('.'))
  14
  15import abc
  16import dataclasses
  17import functools
  18import importlib.util
  19import itertools
  20import math
  21import sys
  22import types
  23import typing
  24from collections.abc import Callable, Iterable, Sequence
  25from typing import Any, Generic, Literal, TypeAlias, TypeVar
  26
  27import numpy as np
  28import numpy.typing as npt
  29import scipy.interpolate
  30import scipy.linalg
  31import scipy.ndimage
  32import scipy.sparse
  33import scipy.sparse.linalg
  34
  35
  36def _noop_decorator(*args: Any, **kwargs: Any) -> Any:
  37  """Return function decorated with no-operation; invocable with or without args."""
  38  if len(args) != 1 or not callable(args[0]) or kwargs:
  39    return _noop_decorator  # Decorator is invoked with arguments; ignore them.
  40  func: Callable[..., Any] = args[0]
  41  return func
  42
  43
  44try:
  45  import numba
  46except ModuleNotFoundError:
  47  numba = sys.modules['numba'] = types.ModuleType('numba')
  48  numba.njit = _noop_decorator  # type: ignore[attr-defined]
  49_USING_NUMBA = hasattr(numba, 'jit')
  50
  51if typing.TYPE_CHECKING:
  52  import jax.experimental.sparse
  53  import jax.numpy
  54  import torch
  55
  56  _DType: TypeAlias = np.dtype[Any]
  57  _NDArray: TypeAlias = npt.NDArray[Any]
  58  _DTypeLike: TypeAlias = npt.DTypeLike
  59  _ArrayLike: TypeAlias = npt.ArrayLike
  60  _TorchTensor: TypeAlias = torch.Tensor
  61  _JaxArray: TypeAlias = jax.numpy.ndarray
  62
  63else:
  64  # Typically, create named types for use in the `pdoc` documentation.
  65  # But here, these are superseded by the declarations in __init__.pyi!
  66  _DType: TypeAlias = Any
  67  _NDArray: TypeAlias = Any
  68  _DTypeLike: TypeAlias = Any
  69  _ArrayLike: TypeAlias = Any
  70  _TorchTensor: TypeAlias = Any
  71  _JaxArray: TypeAlias = Any
  72
  73_Array = TypeVar('_Array', _NDArray, _TorchTensor, _JaxArray)
  74_AnyArray = _NDArray | _TorchTensor | _JaxArray
  75
  76
  77def _check_eq(a: Any, b: Any, /) -> None:
  78  """If the two values or arrays are not equal, raise an exception with a useful message."""
  79  are_equal = np.all(a == b) if isinstance(a, np.ndarray) else a == b
  80  if not are_equal:
  81    raise AssertionError(f'{a!r} == {b!r}')
  82
  83
  84def _real_precision(dtype: _DTypeLike, /) -> _DType:
  85  """Return the type of the real part of a complex number."""
  86  return np.array([], dtype).real.dtype
  87
  88
  89def _complex_precision(dtype: _DTypeLike, /) -> _DType:
  90  """Return a complex type to represent a non-complex type."""
  91  return np.result_type(dtype, np.complex64)
  92
  93
  94def _get_precision(
  95    precision: _DTypeLike | None, dtypes: list[_DType], weight_dtypes: list[_DType], /
  96) -> _DType:
  97  """Return dtype based on desired precision or on data and weight types."""
  98  precision2 = np.dtype(
  99      precision if precision is not None else np.result_type(np.float32, *dtypes, *weight_dtypes)
 100  )
 101  if not np.issubdtype(precision2, np.inexact):
 102    raise ValueError(f'Precision {precision2} is not floating or complex.')
 103  check_complex = [precision2, *dtypes]
 104  is_complex = [np.issubdtype(dtype, np.complexfloating) for dtype in check_complex]
 105  if len(set(is_complex)) != 1:
 106    s_types = ','.join(str(dtype) for dtype in check_complex)
 107    raise ValueError(f'Types {s_types} must be all real or all complex.')
 108  return precision2
 109
 110
 111def _sinc(x: _ArrayLike, /) -> _NDArray:
 112  """Return the value `np.sinc(x)` but improved to:
 113  (1) ignore underflow that occurs at 0.0 for np.float32, and
 114  (2) output exact zero for integer input values.
 115
 116  >>> _sinc(np.array([-3, -2, -1, 0], np.float32))
 117  array([0., 0., 0., 1.], dtype=float32)
 118
 119  >>> _sinc(np.array([-3, -2, -1, 0]))
 120  array([0., 0., 0., 1.])
 121
 122  >>> _sinc(0)
 123  1.0
 124  """
 125  x = np.asarray(x)
 126  x_is_scalar = x.ndim == 0
 127  with np.errstate(under='ignore'):
 128    result = np.sinc(np.atleast_1d(x))
 129    result[x == np.floor(x)] = 0.0
 130    result[x == 0] = 1.0
 131    return result.item() if x_is_scalar else result
 132
 133
 134def _is_symmetric(matrix: Any, /, tol: float = 1e-10) -> bool:
 135  """Return True if the sparse matrix is symmetric."""
 136  norm = scipy.sparse.linalg.norm(matrix - matrix.transpose(), np.inf)
 137  return bool(norm <= tol)
 138
 139
 140def _cache_sampled_1d_function(
 141    xmin: float,
 142    xmax: float,
 143    *,
 144    num_samples: int = 3_600,
 145    enable: bool = True,
 146) -> Callable[[Callable[[_ArrayLike], _NDArray]], Callable[[_ArrayLike], _NDArray]]:
 147  """Function decorator to linearly interpolate cached function values."""
 148  # Speed unchanged up to num_samples=12_000, then slow decrease until 100_000.
 149
 150  def wrap_it(func: Callable[[_ArrayLike], _NDArray]) -> Callable[[_ArrayLike], _NDArray]:
 151    if not enable:
 152      return func
 153
 154    dx = (xmax - xmin) / num_samples
 155    x = np.linspace(xmin, xmax + dx, num_samples + 2, dtype=np.float32)
 156    samples_func = func(x)
 157    assert np.all(samples_func[[0, -1, -2]] == 0.0)
 158
 159    @functools.wraps(func)
 160    def interpolate_using_cached_samples(x: _ArrayLike) -> _NDArray:
 161      x = np.asarray(x)
 162      index_float = np.clip((x - xmin) / dx, 0.0, num_samples)
 163      index = index_float.astype(np.int64)
 164      frac = np.subtract(index_float, index, dtype=np.float32)
 165      return (1 - frac) * samples_func[index] + frac * samples_func[index + 1]
 166
 167    return interpolate_using_cached_samples
 168
 169  return wrap_it
 170
 171
 172class _DownsampleIn2dUsingBoxFilter:
 173  """Fast 2D box-filter downsampling using cached numba-jitted functions."""
 174
 175  def __init__(self) -> None:
 176    # Downsampling function for params (dtype, block_height, block_width, ch).
 177    self._jitted_function: dict[tuple[_DType, int, int, int], Callable[[_NDArray], _NDArray]] = {}
 178
 179  def __call__(self, array: _NDArray, shape: tuple[int, ...]) -> _NDArray:
 180    assert _USING_NUMBA
 181    assert array.ndim in (2, 3), array.ndim
 182    _check_eq(len(shape), 2)
 183    dtype = array.dtype
 184    a = array[..., None] if array.ndim == 2 else array
 185    height, width, ch = a.shape
 186    new_height, new_width = shape
 187    if height % new_height != 0 or width % new_width != 0:
 188      raise ValueError(f'Shape {array.shape} not a multiple of {shape}.')
 189    block_height, block_width = height // new_height, width // new_width
 190
 191    def func(array: _NDArray) -> _NDArray:
 192      new_height = array.shape[0] // block_height
 193      new_width = array.shape[1] // block_width
 194      result = np.empty((new_height, new_width, ch), dtype)
 195      factor = dtype.type(1.0 / (block_height * block_width))
 196      for y in numba.prange(new_height):  # pylint: disable=not-an-iterable
 197        totals = np.empty(ch, dtype)  # Private to each thread; no data race across rows.
 198        for x in range(new_width):
 199          # Introducing "y2, x2 = y * block_height, x * block_width" is actually slower.
 200          if ch == 1:  # All the branches involve compile-time constants.
 201            total = dtype.type(0.0)
 202            for yy in range(block_height):
 203              for xx in range(block_width):
 204                total += array[y * block_height + yy, x * block_width + xx, 0]
 205            result[y, x, 0] = total * factor
 206          elif ch == 3:
 207            total0 = total1 = total2 = dtype.type(0.0)
 208            for yy in range(block_height):
 209              for xx in range(block_width):
 210                total0 += array[y * block_height + yy, x * block_width + xx, 0]
 211                total1 += array[y * block_height + yy, x * block_width + xx, 1]
 212                total2 += array[y * block_height + yy, x * block_width + xx, 2]
 213            result[y, x, 0] = total0 * factor
 214            result[y, x, 1] = total1 * factor
 215            result[y, x, 2] = total2 * factor
 216          elif block_height * block_width >= 9:
 217            for c in range(ch):
 218              totals[c] = 0.0
 219            for yy in range(block_height):
 220              for xx in range(block_width):
 221                for c in range(ch):
 222                  totals[c] += array[y * block_height + yy, x * block_width + xx, c]
 223            for c in range(ch):
 224              result[y, x, c] = totals[c] * factor
 225          else:
 226            for c in range(ch):
 227              total = dtype.type(0.0)
 228              for yy in range(block_height):
 229                for xx in range(block_width):
 230                  total += array[y * block_height + yy, x * block_width + xx, c]
 231              result[y, x, c] = total * factor
 232      return result
 233
 234    signature = dtype, block_height, block_width, ch
 235    jitted_function = self._jitted_function.get(signature)
 236    if not jitted_function:
 237      jitted_function = numba.njit(func, parallel=True, fastmath=True, cache=True)
 238      self._jitted_function[signature] = jitted_function
 239
 240    try:
 241      result = jitted_function(a)
 242    except RuntimeError:
 243      message = (
 244          'resampler: This runtime error may be due to a corrupt pycache; '
 245          'try deleting ~/.cache/numba/resampler_*/ and/or ./resampler/__pycache__/ .'
 246      )
 247      print(message, file=sys.stdout, flush=True)
 248      print(message, file=sys.stderr, flush=True)
 249      raise
 250
 251    return result[..., 0] if array.ndim == 2 else result
 252
 253
 254_downsample_in_2d_using_box_filter = _DownsampleIn2dUsingBoxFilter()
 255
 256
 257@numba.njit(nogil=True, fastmath=True, cache=True)  # type: ignore[untyped-decorator]
 258def _numba_serial_csr_dense_mult(
 259    indptr: _NDArray,
 260    indices: _NDArray,
 261    data: _NDArray,
 262    src: _NDArray,
 263    dst: _NDArray,
 264) -> None:
 265  """Faster version of scipy.sparse._sparsetools.csr_matvecs().
 266
 267  The single-threaded numba-jitted code is about 2x faster than the scipy C++.
 268  """
 269  assert indptr.ndim == indices.ndim == data.ndim == 1 and src.ndim == dst.ndim == 2
 270  assert len(indptr) == dst.shape[0] + 1 and src.shape[1] == dst.shape[1]
 271  acc = data[0] * src[0]  # Dummy initialization value, to infer correct shape and dtype.
 272  for i in range(dst.shape[0]):
 273    acc[:] = 0
 274    for jj in range(indptr[i], indptr[i + 1]):
 275      j = indices[jj]
 276      acc += data[jj] * src[j]
 277    dst[i] = acc
 278
 279
 280# I tried using the "minimal" "parallel=" config but this did not result in any jit speedup:
 281#  parallel=dict(comprehension=False, prange=True, numpy=True, reduction=False,
 282#                setitem=False, stencil=False, fusion=False)
 283@numba.njit(parallel=True, fastmath=True, cache=True)  # type: ignore[untyped-decorator]
 284def _numba_parallel_csr_dense_mult(
 285    indptr: _NDArray,
 286    indices: _NDArray,
 287    data: _NDArray,
 288    src: _NDArray,
 289    dst: _NDArray,
 290) -> None:
 291  """Faster version of scipy.sparse._sparsetools.csr_matvecs().
 292
 293  The single-threaded numba-jitted code is about 2x faster than the scipy C++.
 294  The introduction of parallel omp threads provides another 2-4x speedup.
 295  However, "parallel=True" leads to slow jitting (~3 s), so we cache the jitted code on disk.
 296  """
 297  assert indptr.ndim == indices.ndim == data.ndim == 1 and src.ndim == dst.ndim == 2
 298  assert len(indptr) == dst.shape[0] + 1 and src.shape[1] == dst.shape[1]
 299  acc0 = data[0] * src[0]  # Dummy initialization value, to infer correct shape and dtype.
 300  # Default is static scheduling, which is fine.
 301  for i in numba.prange(dst.shape[0]):  # pylint: disable=not-an-iterable
 302    acc = np.zeros_like(acc0)  # Numba automatically hoists the allocation outside the loop.
 303    for jj in range(indptr[i], indptr[i + 1]):
 304      j = indices[jj]
 305      acc += data[jj] * src[j]
 306    dst[i] = acc
 307
 308
 309@dataclasses.dataclass
 310class _Arraylib(abc.ABC, Generic[_Array]):
 311  """Abstract base class for abstraction of array libraries."""
 312
 313  arraylib: str
 314  """Name of array library (e.g., `'numpy'`, `'torch'`, `'jax'`)."""
 315
 316  array: _Array
 317
 318  @staticmethod
 319  @abc.abstractmethod
 320  def recognize(array: Any) -> bool:
 321    """Return True if `array` is recognized by this _Arraylib."""
 322
 323  @abc.abstractmethod
 324  def numpy(self) -> _NDArray:
 325    """Return a `numpy` version of `self.array`."""
 326
 327  @abc.abstractmethod
 328  def dtype(self) -> _DType:
 329    """Return the equivalent of `self.array.dtype` as a `numpy` `dtype`."""
 330
 331  @abc.abstractmethod
 332  def astype(self, dtype: _DTypeLike) -> _Array:
 333    """Return the equivalent of `self.array.astype(dtype, copy=False)` with `numpy` `dtype`."""
 334
 335  def reshape(self, shape: tuple[int, ...]) -> _Array:
 336    """Return the equivalent of `self.array.reshape(shape)`."""
 337    array: Any = self.array
 338    return array.reshape(shape)
 339
 340  def possibly_make_contiguous(self) -> _Array:
 341    """Return a contiguous copy of `self.array` or just `self.array` if already contiguous."""
 342    return self.array
 343
 344  @abc.abstractmethod
 345  def clip(self, low: Any, high: Any, dtype: _DTypeLike | None = None) -> _Array:
 346    """Return the equivalent of `self.array.clip(low, high, dtype=dtype)` with `numpy` `dtype`."""
 347
 348  @abc.abstractmethod
 349  def square(self) -> _Array:
 350    """Return the equivalent of `np.square(self.array)`."""
 351
 352  @abc.abstractmethod
 353  def sqrt(self) -> _Array:
 354    """Return the equivalent of `np.sqrt(self.array)`."""
 355
 356  def getitem(self, indices: Any) -> _Array:
 357    """Return the equivalent of `self.array[indices]` (a "gather" operation)."""
 358    array: Any = self.array
 359    return array[indices]
 360
 361  @abc.abstractmethod
 362  def where(self, if_true: Any, if_false: Any) -> _Array:
 363    """Return the equivalent of `np.where(self.array, if_true, if_false)`."""
 364
 365  @abc.abstractmethod
 366  def transpose(self, axes: Sequence[int]) -> _Array:
 367    """Return the equivalent of `np.transpose(self.array, axes)`."""
 368
 369  @abc.abstractmethod
 370  def best_dims_order_for_resize(self, dst_shape: tuple[int, ...]) -> list[int]:
 371    """Return the best order in which to process dims for resizing `self.array` to `dst_shape`."""
 372
 373  @abc.abstractmethod
 374  def premult_with_sparse(self, sparse: Any, num_threads: int | Literal['auto']) -> _Array:
 375    """Return the multiplication of the `sparse` matrix and `self.array`."""
 376
 377  @staticmethod
 378  @abc.abstractmethod
 379  def concatenate(arrays: Sequence[_Array], axis: int) -> _Array:
 380    """Return the equivalent of `np.concatenate(arrays, axis)`."""
 381
 382  @staticmethod
 383  @abc.abstractmethod
 384  def einsum(subscripts: str, *operands: _Array) -> _Array:
 385    """Return the equivalent of `np.einsum(subscripts, *operands, optimize=True)`."""
 386
 387  @staticmethod
 388  @abc.abstractmethod
 389  def make_sparse_matrix(
 390      data: _NDArray, row_ind: _NDArray, col_ind: _NDArray, shape: tuple[int, int]
 391  ) -> Any:
 392    """Return the equivalent of `scipy.sparse.csr_matrix(data, (row_ind, col_ind), shape=shape)`.
 393    However, the indices must be ordered and unique."""
 394
 395
 396class _NumpyArraylib(_Arraylib[_NDArray]):
 397  """Numpy implementation of the array abstraction."""
 398
 399  def __init__(self, array: _NDArray) -> None:
 400    super().__init__(arraylib='numpy', array=np.asarray(array))
 401
 402  @staticmethod
 403  def recognize(array: Any) -> bool:
 404    return isinstance(array, (np.ndarray, np.number, np.bool_))
 405
 406  def numpy(self) -> _NDArray:
 407    return self.array
 408
 409  def dtype(self) -> _DType:
 410    dtype: _DType = self.array.dtype
 411    return dtype
 412
 413  def astype(self, dtype: _DTypeLike) -> _NDArray:
 414    return self.array.astype(dtype, copy=False)
 415
 416  def clip(self, low: Any, high: Any, dtype: _DTypeLike | None = None) -> _NDArray:
 417    return self.array.clip(low, high, dtype=dtype)
 418
 419  def square(self) -> _NDArray:
 420    return np.square(self.array)
 421
 422  def sqrt(self) -> _NDArray:
 423    return np.sqrt(self.array)
 424
 425  def where(self, if_true: Any, if_false: Any) -> _NDArray:
 426    condition = self.array
 427    return np.where(condition, if_true, if_false)
 428
 429  def transpose(self, axes: Sequence[int]) -> _NDArray:
 430    return np.transpose(self.array, tuple(axes))
 431
 432  def best_dims_order_for_resize(self, dst_shape: tuple[int, ...]) -> list[int]:
 433    # Our heuristics: (1) a dimension with small scaling (especially minification) gets priority,
 434    # and (2) timings show preference to resizing dimensions with larger strides first.
 435    # The optimal ordering might be related to the logic in np.einsum_path().  (Unfortunately,
 436    # np.einsum() does not support the sparse multiplications that we require here.)
 437    src_shape: tuple[int, ...] = self.array.shape[: len(dst_shape)]
 438    strides: Sequence[int] = self.array.strides
 439    largest_stride_dim = max(range(len(src_shape)), key=lambda dim: strides[dim])
 440
 441    def priority(dim: int) -> float:
 442      scaling = dst_shape[dim] / src_shape[dim]
 443      return scaling * ((0.49 if scaling < 1.0 else 0.65) if dim == largest_stride_dim else 1.0)
 444
 445    return sorted(range(len(src_shape)), key=priority)
 446
 447  def premult_with_sparse(
 448      self, sparse: scipy.sparse.csr_matrix, num_threads: int | Literal['auto']
 449  ) -> _NDArray:
 450    assert self.array.ndim == sparse.ndim == 2 and sparse.shape[1] == self.array.shape[0]
 451    if _USING_NUMBA:
 452      # For 'auto', 6 threads are empirically faster than all of numba.config.NUMBA_NUM_THREADS
 453      # (e.g., 24), which is also an upper limit for numba.set_num_threads().
 454      max_threads = numba.config.NUMBA_NUM_THREADS
 455      num_threads2 = min(6, max_threads) if num_threads == 'auto' else num_threads
 456      src = np.ascontiguousarray(self.array)  # Like .ravel() in _mul_multivector().
 457      dtype = np.result_type(sparse.dtype, src.dtype)
 458      dst = np.empty((sparse.shape[0], src.shape[1]), dtype)
 459      num_scalar_multiplies = len(sparse.data) * src.shape[1]
 460      is_small_size = num_scalar_multiplies < 200_000
 461      if is_small_size or num_threads2 == 1:
 462        _numba_serial_csr_dense_mult(sparse.indptr, sparse.indices, sparse.data, src, dst)
 463      else:
 464        numba.set_num_threads(num_threads2)
 465        _numba_parallel_csr_dense_mult(sparse.indptr, sparse.indices, sparse.data, src, dst)
 466      return dst
 467
 468    # Note that scipy.sparse does not use multithreading.  The "@" operation
 469    # calls _spbase.__matmul__() -> _spbase._mul_dispatch() -> _cs_matrix._mul_multivector() ->
 470    # scipy.sparse._sparsetools.csr_matvecs() in
 471    # https://github.com/scipy/scipy/blob/main/scipy/sparse/sparsetools/csr.h
 472    # which iteratively calls the (in theory, LEVEL 1 BLAS) function axpy() in
 473    # https://github.com/scipy/scipy/blob/main/scipy/sparse/sparsetools/dense.h
 474    return sparse @ self.array
 475
 476  @staticmethod
 477  def concatenate(arrays: Sequence[_NDArray], axis: int) -> _NDArray:
 478    return np.concatenate(arrays, axis)
 479
 480  @staticmethod
 481  def einsum(subscripts: str, *operands: _NDArray) -> _NDArray:
 482    return np.einsum(subscripts, *operands, optimize=True)
 483
 484  @staticmethod
 485  def make_sparse_matrix(
 486      data: _NDArray, row_ind: _NDArray, col_ind: _NDArray, shape: tuple[int, int]
 487  ) -> scipy.sparse.csr_matrix:
 488    return scipy.sparse.csr_matrix((data, (row_ind, col_ind)), shape=shape)
 489
 490
 491class _TorchArraylib(_Arraylib[_TorchTensor]):
 492  """Torch implementation of the array abstraction."""
 493
 494  # pylint: disable=missing-function-docstring
 495
 496  def __init__(self, array: _NDArray) -> None:
 497    import torch
 498
 499    self.torch = torch
 500    super().__init__(arraylib='torch', array=self.torch.as_tensor(array))
 501
 502  @staticmethod
 503  def recognize(array: Any) -> bool:
 504    torch = sys.modules.get('torch')  # If torch is not yet imported, `array` is not a tensor.
 505    return torch is not None and isinstance(array, torch.Tensor)
 506
 507  def numpy(self) -> _NDArray:
 508    return self.array.numpy()
 509
 510  def dtype(self) -> _DType:
 511    numpy_type = {
 512        self.torch.float32: np.float32,
 513        self.torch.float64: np.float64,
 514        self.torch.complex64: np.complex64,
 515        self.torch.complex128: np.complex128,
 516        self.torch.uint8: np.uint8,  # (The torch uint16, uint32, uint64 have limited support.)
 517        self.torch.int16: np.int16,
 518        self.torch.int32: np.int32,
 519        self.torch.int64: np.int64,
 520    }.get(self.array.dtype)
 521    if numpy_type is None:
 522      raise ValueError(f'Torch dtype {self.array.dtype} is unsupported.')
 523    return np.dtype(numpy_type)
 524
 525  def astype(self, dtype: _DTypeLike) -> _TorchTensor:
 526    torch_types: dict[Any, Any] = {
 527        np.float32: self.torch.float32,
 528        np.float64: self.torch.float64,
 529        np.complex64: self.torch.complex64,
 530        np.complex128: self.torch.complex128,
 531        np.uint8: self.torch.uint8,
 532        np.int16: self.torch.int16,
 533        np.int32: self.torch.int32,
 534        np.int64: self.torch.int64,
 535    }
 536    return self.array.type(torch_types[np.dtype(dtype).type])
 537
 538  def possibly_make_contiguous(self) -> _TorchTensor:
 539    return self.array.contiguous()
 540
 541  def clip(self, low: Any, high: Any, dtype: _DTypeLike | None = None) -> _TorchTensor:
 542    array = self.array
 543    array = _arr_astype(array, dtype) if dtype is not None else array
 544    return array.clip(low, high)
 545
 546  def square(self) -> _TorchTensor:
 547    return self.array.square()
 548
 549  def sqrt(self) -> _TorchTensor:
 550    return self.array.sqrt()
 551
 552  def getitem(self, indices: Any) -> _TorchTensor:
 553    if not isinstance(indices, tuple):
 554      indices = indices.type(self.torch.int64)
 555    return self.array[indices]  # pylint: disable=unsubscriptable-object
 556
 557  def where(self, if_true: Any, if_false: Any) -> _TorchTensor:
 558    condition = self.array
 559    return if_true.where(condition, if_false)
 560
 561  def transpose(self, axes: Sequence[int]) -> _TorchTensor:
 562    return self.torch.permute(self.array, tuple(axes))
 563
 564  def best_dims_order_for_resize(self, dst_shape: tuple[int, ...]) -> list[int]:
 565    # Similar to `_NumpyArraylib`.  We access `array.stride()` instead of `array.strides`.
 566    src_shape: tuple[int, ...] = self.array.shape[: len(dst_shape)]
 567    strides: Sequence[int] = self.array.stride()
 568    largest_stride_dim = max(range(len(src_shape)), key=lambda dim: strides[dim])
 569
 570    def priority(dim: int) -> float:
 571      scaling = dst_shape[dim] / src_shape[dim]
 572      return scaling * ((0.49 if scaling < 1.0 else 0.65) if dim == largest_stride_dim else 1.0)
 573
 574    return sorted(range(len(src_shape)), key=priority)
 575
 576  def premult_with_sparse(self, sparse: Any, num_threads: int | Literal['auto']) -> _TorchTensor:
 577    del num_threads
 578    if np.issubdtype(_arr_dtype(self.array), np.complexfloating):
 579      sparse = _arr_astype(sparse, _arr_dtype(self.array))
 580    return sparse @ self.array  # Calls torch.sparse.mm().
 581
 582  @staticmethod
 583  def concatenate(arrays: Sequence[_TorchTensor], axis: int) -> _TorchTensor:
 584    import torch
 585
 586    return torch.cat(tuple(arrays), axis)
 587
 588  @staticmethod
 589  def einsum(subscripts: str, *operands: _TorchTensor) -> _TorchTensor:
 590    import torch
 591
 592    operands = tuple(torch.as_tensor(operand) for operand in operands)
 593    if any(np.issubdtype(_arr_dtype(array), np.complexfloating) for array in operands):
 594      operands = tuple(
 595          _arr_astype(array, _complex_precision(_arr_dtype(array))) for array in operands
 596      )
 597    return torch.einsum(subscripts, *operands)
 598
 599  @staticmethod
 600  def make_sparse_matrix(
 601      data: _NDArray, row_ind: _NDArray, col_ind: _NDArray, shape: tuple[int, int]
 602  ) -> _TorchTensor:
 603    import torch
 604
 605    indices = np.vstack((row_ind, col_ind))
 606    # .coalesce() is unnecessary because indices/data are already merged.
 607    with torch.sparse.check_sparse_tensor_invariants(enable=False):
 608      return torch.sparse_coo_tensor(torch.as_tensor(indices), torch.as_tensor(data), shape)
 609
 610
 611class _JaxArraylib(_Arraylib[_JaxArray]):
 612  """Jax implementation of the array abstraction."""
 613
 614  def __init__(self, array: _NDArray) -> None:
 615    import jax.numpy
 616
 617    self.jnp = jax.numpy
 618    super().__init__(arraylib='jax', array=self.jnp.asarray(array))
 619
 620  @staticmethod
 621  def recognize(array: Any) -> bool:
 622    # E.g., jaxlib._jax.ArrayImpl, jax._src.interpreters.ad.JVPTracer.
 623    return type(array).__module__.startswith(('jaxlib.', 'jax.'))
 624
 625  def numpy(self) -> _NDArray:
 626    # Whereas np.asarray(array) may return a non-writable np.ndarray, np.array(array) always
 627    # returns a writable array but the copy may be more costly.
 628    return np.asarray(self.array)
 629
 630  def dtype(self) -> _DType:
 631    return np.dtype(self.array.dtype)
 632
 633  def astype(self, dtype: _DTypeLike) -> _JaxArray:
 634    return self.array.astype(np.dtype(dtype))  # (copy=False is unavailable)
 635
 636  def possibly_make_contiguous(self) -> _JaxArray:
 637    return self.array.copy()
 638
 639  def clip(self, low: Any, high: Any, dtype: _DTypeLike | None = None) -> _JaxArray:
 640    array = self.array
 641    if dtype is not None:
 642      array = array.astype(np.dtype(dtype))  # (copy=False is unavailable)
 643    return self.jnp.clip(array, low, high)
 644
 645  def square(self) -> _JaxArray:
 646    return self.jnp.square(self.array)
 647
 648  def sqrt(self) -> _JaxArray:
 649    return self.jnp.sqrt(self.array)
 650
 651  def where(self, if_true: Any, if_false: Any) -> _JaxArray:
 652    condition = self.array
 653    return typing.cast(Any, self.jnp.where(condition, if_true, if_false))
 654
 655  def transpose(self, axes: Sequence[int]) -> _JaxArray:
 656    return self.jnp.transpose(self.array, tuple(axes))
 657
 658  def best_dims_order_for_resize(self, dst_shape: tuple[int, ...]) -> list[int]:
 659    # Jax/XLA does not have strides.  Arrays are contiguous, almost always in C order; see
 660    # https://github.com/jax-ml/jax/discussions/7544#discussioncomment-1197038.
 661    src_shape: tuple[int, ...] = self.array.shape[: len(dst_shape)]
 662    dims = list(range(len(src_shape)))
 663    if len(dims) > 1 and dst_shape[0] / src_shape[0] > 1.0:
 664      dims[:2] = [1, 0]
 665    return dims
 666
 667  def premult_with_sparse(
 668      self, sparse: jax.experimental.sparse.BCOO, num_threads: int | Literal['auto']
 669  ) -> _JaxArray:
 670    del num_threads
 671    return sparse @ self.array  # Calls jax.experimental.sparse.bcoo_dot_general().
 672
 673  @staticmethod
 674  def concatenate(arrays: Sequence[_JaxArray], axis: int) -> _JaxArray:
 675    import jax.numpy as jnp
 676
 677    return jnp.concatenate(arrays, axis)
 678
 679  @staticmethod
 680  def einsum(subscripts: str, *operands: _JaxArray) -> _JaxArray:
 681    import jax.numpy as jnp
 682
 683    return jnp.einsum(subscripts, *operands, optimize='greedy')
 684
 685  @staticmethod
 686  def make_sparse_matrix(
 687      data: _NDArray, row_ind: _NDArray, col_ind: _NDArray, shape: tuple[int, int]
 688  ) -> Any:
 689    # https://docs.jax.dev/en/latest/jax.experimental.sparse.html
 690    import jax.experimental.sparse
 691    import jax.numpy as jnp
 692
 693    indices = jnp.asarray(np.vstack((row_ind, col_ind)).T)
 694    return jax.experimental.sparse.BCOO(
 695        (jnp.asarray(data), indices), shape=shape, indices_sorted=True, unique_indices=True
 696    )
 697
 698
 699_CANDIDATE_ARRAYLIBS = {
 700    'numpy': _NumpyArraylib,
 701    'torch': _TorchArraylib,
 702    'jax': _JaxArraylib,
 703}
 704
 705
 706def _is_available(arraylib: str) -> bool:
 707  """Return whether the array library (e.g. 'torch') is available as an installed package."""
 708  # Faster than trying to import it.
 709  return importlib.util.find_spec(arraylib) is not None
 710
 711
 712_DICT_ARRAYLIBS: dict[str, Any] = {
 713    arraylib: cls for arraylib, cls in _CANDIDATE_ARRAYLIBS.items() if _is_available(arraylib)
 714}
 715
 716ARRAYLIBS = list(_DICT_ARRAYLIBS)
 717"""Array libraries supported automatically in the resize and resampling operations.
 718
 719- The library is selected automatically based on the type of the `array` function parameter.
 720
 721- The class `_Arraylib` provides library-specific implementations of needed basic functions.
 722
 723- The `_arr_*()` functions dispatch the `_Arraylib` methods based on the array type.
 724"""
 725
 726
 727def _as_arr(array: _AnyArray, /) -> _Arraylib[Any]:
 728  """Return `array` wrapped as an `_Arraylib` for dispatch of functions."""
 729  if isinstance(array, (tuple, list)):
 730    raise ValueError(f'{array} not recognized.  Perhaps convert it using np.asarray().')
 731  for cls in _DICT_ARRAYLIBS.values():
 732    if cls.recognize(array):
 733      return cls(array)
 734  raise ValueError(f'Array type {type(array)} is not recognized by {ARRAYLIBS}.')
 735
 736
 737def _arr_arraylib(array: _AnyArray, /) -> str:
 738  """Return the name of the `Arraylib` representing `array`."""
 739  return _as_arr(array).arraylib
 740
 741
 742def _arr_numpy(array: _AnyArray, /) -> _NDArray:
 743  """Return a `numpy` version of `array`."""
 744  return _as_arr(array).numpy()
 745
 746
 747def _arr_dtype(array: _AnyArray, /) -> _DType:
 748  """Return the equivalent of `array.dtype` as a `numpy` `dtype`."""
 749  return _as_arr(array).dtype()
 750
 751
 752def _arr_shape(array: _AnyArray, /) -> tuple[int, ...]:
 753  """Return `array.shape` as a `tuple` of `int`."""
 754  array2: Any = array
 755  return tuple(array2.shape)
 756
 757
 758def _arr_astype(array: _Array, dtype: _DTypeLike, /) -> _Array:
 759  """Return the equivalent of `array.astype(dtype)` with `numpy` `dtype`."""
 760  return _as_arr(array).astype(dtype)
 761
 762
 763def _arr_reshape(array: _Array, shape: tuple[int, ...], /) -> _Array:
 764  """Return the equivalent of `array.reshape(shape)`."""
 765  return _as_arr(array).reshape(shape)
 766
 767
 768def _arr_possibly_make_contiguous(array: _Array, /) -> _Array:
 769  """Return a contiguous copy of `array` or just `array` if already contiguous."""
 770  return _as_arr(array).possibly_make_contiguous()
 771
 772
 773def _arr_clip(array: _Array, low: Any, high: Any, /, dtype: _DTypeLike | None = None) -> _Array:
 774  """Return the equivalent of `array.clip(low, high, dtype)` with `numpy` `dtype`."""
 775  return _as_arr(array).clip(low, high, dtype)
 776
 777
 778def _arr_square(array: _Array, /) -> _Array:
 779  """Return the equivalent of `np.square(array)`."""
 780  return _as_arr(array).square()
 781
 782
 783def _arr_sqrt(array: _Array, /) -> _Array:
 784  """Return the equivalent of `np.sqrt(array)`."""
 785  return _as_arr(array).sqrt()
 786
 787
 788def _arr_getitem(array: _Array, indices: Any, /) -> _Array:
 789  """Return the equivalent of `array[indices]`."""
 790  return _as_arr(array).getitem(indices)
 791
 792
 793def _arr_where(condition: _Array, if_true: Any, if_false: Any, /) -> _Array:
 794  """Return the equivalent of `np.where(condition, if_true, if_false)`."""
 795  return _as_arr(condition).where(if_true, if_false)
 796
 797
 798def _arr_transpose(array: _Array, axes: Sequence[int], /) -> _Array:
 799  """Return the equivalent of `np.transpose(array, axes)`."""
 800  return _as_arr(array).transpose(axes)
 801
 802
 803def _arr_best_dims_order_for_resize(array: _AnyArray, dst_shape: tuple[int, ...], /) -> list[int]:
 804  """Return the best order in which to process dims for resizing `array` to `dst_shape`."""
 805  return _as_arr(array).best_dims_order_for_resize(dst_shape)
 806
 807
 808def _arr_matmul_sparse_dense(
 809    sparse: Any, dense: _Array, /, *, num_threads: int | Literal['auto'] = 'auto'
 810) -> _Array:
 811  """Return the multiplication of the `sparse` and `dense` matrices."""
 812  assert num_threads == 'auto' or num_threads >= 1
 813  return _as_arr(dense).premult_with_sparse(sparse, num_threads)
 814
 815
 816def _arr_concatenate(arrays: Sequence[_Array], axis: int, /) -> _Array:
 817  """Return the equivalent of `np.concatenate(arrays, axis)`."""
 818  arraylib = _arr_arraylib(arrays[0])
 819  return _DICT_ARRAYLIBS[arraylib].concatenate(arrays, axis)
 820
 821
 822def _arr_einsum(subscripts: str, /, *operands: _Array) -> _Array:
 823  """Return the equivalent of `np.einsum(subscripts, *operands, optimize=True)`."""
 824  arraylib = _arr_arraylib(operands[0])
 825  return _DICT_ARRAYLIBS[arraylib].einsum(subscripts, *operands)
 826
 827
 828def _arr_swapaxes(array: _Array, axis1: int, axis2: int, /) -> _Array:
 829  """Return the equivalent of `np.swapaxes(array, axis1, axis2)`."""
 830  ndim = len(_arr_shape(array))
 831  assert 0 <= axis1 < ndim and 0 <= axis2 < ndim, (axis1, axis2, ndim)
 832  axes = list(range(ndim))
 833  axes[axis1] = axis2
 834  axes[axis2] = axis1
 835  return _arr_transpose(array, axes)
 836
 837
 838def _arr_moveaxis(array: _Array, source: int, destination: int, /) -> _Array:
 839  """Return the equivalent of `np.moveaxis(array, source, destination)`."""
 840  ndim = len(_arr_shape(array))
 841  assert 0 <= source < ndim and 0 <= destination < ndim, (source, destination, ndim)
 842  axes = [n for n in range(ndim) if n != source]
 843  axes.insert(destination, source)
 844  return _arr_transpose(array, axes)
 845
 846
 847def _make_sparse_matrix(
 848    data: _NDArray, row_ind: _NDArray, col_ind: _NDArray, shape: tuple[int, int], arraylib: str, /
 849) -> Any:
 850  """Return the equivalent of `scipy.sparse.csr_matrix(data, (row_ind, col_ind), shape=shape)`.
 851  However, indices must be ordered and unique."""
 852  return _DICT_ARRAYLIBS[arraylib].make_sparse_matrix(data, row_ind, col_ind, shape)
 853
 854
 855def _make_array(array: _ArrayLike, arraylib: str, /) -> Any:
 856  """Return an array from the library `arraylib` initialized with the `numpy` `array`."""
 857  return _DICT_ARRAYLIBS[arraylib](np.asarray(array)).array
 858
 859
 860# Because np.ndarray supports strides, np.moveaxis() and np.transpose() are constant-time.
 861# However, ndarray.reshape() creates a copy whenever the new shape cannot be expressed using
 862# strides, e.g. dim=1 in an RGB image.
 863#
 864# torch.Tensor also supports strides, so torch.movedim() is constant-time and
 865# Tensor.reshape() has the same copy-when-necessary behavior as numpy.
 866#
 867# For jax.Array, both operations lower to XLA ops; under jit the compiler often fuses away
 868# the transpose and turns the reshape into a bitcast, so neither has a fixed cost.
 869
 870
 871def _block_shape_with_min_size(
 872    shape: tuple[int, ...], min_size: int, compact: bool = True
 873) -> tuple[int, ...]:
 874  """Return shape of block (of size at least `min_size`) to subdivide shape."""
 875  if math.prod(shape) < min_size:
 876    raise ValueError(f'Shape {shape} smaller than min_size {min_size}.')
 877  if compact:
 878    root = math.ceil(min_size ** (1 / len(shape)))
 879    block_shape = np.minimum(shape, root)
 880    for dim in range(len(shape)):
 881      if block_shape[dim] == 2 and block_shape.prod() >= min_size * 2:
 882        block_shape[dim] = 1
 883    for dim in range(len(shape) - 1, -1, -1):
 884      if block_shape.prod() < min_size:
 885        block_shape[dim] = shape[dim]
 886  else:
 887    block_shape = np.ones_like(shape)
 888    for dim in range(len(shape) - 1, -1, -1):
 889      if block_shape.prod() < min_size:
 890        block_shape[dim] = min(shape[dim], math.ceil(min_size / block_shape.prod()))
 891  return tuple(int(n) for n in block_shape)
 892
 893
 894def _array_split(array: _Array, axis: int, num_sections: int) -> list[_Array]:
 895  """Split `array` into `num_sections` along `axis`."""
 896  assert 0 <= axis < len(_arr_shape(array))
 897  assert 1 <= num_sections <= _arr_shape(array)[axis]
 898
 899  # Adapted from np.array_split() (which is specific to numpy) in
 900  # https://github.com/numpy/numpy/blob/main/numpy/lib/_shape_base_impl.py.
 901  num_total = _arr_shape(array)[axis]
 902  num_each, num_extra = divmod(num_total, num_sections)
 903  section_sizes = [0] + num_extra * [num_each + 1] + (num_sections - num_extra) * [num_each]
 904  div_points = np.array(section_sizes).cumsum()
 905  tmp: Any = _arr_swapaxes(array, axis, 0)
 906  return [
 907      _arr_swapaxes(tmp[div_points[i] : div_points[i + 1]], axis, 0) for i in range(num_sections)
 908  ]
 909
 910
 911def _split_array_into_blocks(array: Any, block_shape: Sequence[int], start_axis: int = 0) -> Any:
 912  """Split `array` into nested lists of blocks of size at most `block_shape`."""
 913  # See https://stackoverflow.com/a/50305924.  (If the block_shape is known to
 914  # exactly partition the array, see https://stackoverflow.com/a/16858283.)
 915  if len(block_shape) > len(_arr_shape(array)):
 916    raise ValueError(f'Block ndim {len(block_shape)} > array ndim {len(_arr_shape(array))}.')
 917  if start_axis == len(block_shape):
 918    return array
 919
 920  num_sections = math.ceil(_arr_shape(array)[start_axis] / block_shape[start_axis])
 921  split = _array_split(array, start_axis, num_sections)
 922  return [_split_array_into_blocks(split_a, block_shape, start_axis + 1) for split_a in split]
 923
 924
 925def _map_function_over_blocks(blocks: Any, func: Callable[[Any], Any]) -> Any:
 926  """Apply `func` to each block in the nested lists of `blocks`."""
 927  if isinstance(blocks, list):
 928    return [_map_function_over_blocks(block, func) for block in blocks]
 929  return func(blocks)
 930
 931
 932def _merge_array_from_blocks(blocks: Any, axis: int = 0) -> Any:
 933  """Merge an array from the nested lists of array blocks in `blocks`."""
 934  # More general than np.block() because the blocks can have additional dims.
 935  if isinstance(blocks, list):
 936    new_blocks = [_merge_array_from_blocks(block, axis + 1) for block in blocks]
 937    return _arr_concatenate(new_blocks, axis)
 938  return blocks
 939
 940
 941@dataclasses.dataclass(frozen=True)
 942class Gridtype(abc.ABC):
 943  """Abstract base class for grid-types such as `'dual'` and `'primal'`.
 944
 945  In resampling operations, the grid-type may be specified separately as `src_gridtype` for the
 946  source domain and `dst_gridtype` for the destination domain.  Moreover, the grid-type may be
 947  specified per domain dimension.
 948
 949  Examples:
 950    `resize(source, shape, gridtype='primal')`  # Sets both src and dst to be `'primal'` grids.
 951
 952    `resize(source, shape, src_gridtype=['dual', 'primal'],
 953            dst_gridtype='dual')`  # Source is `'dual'` in dim0 and `'primal'` in dim1.
 954  """
 955
 956  name: str
 957  """Gridtype name."""
 958
 959  @abc.abstractmethod
 960  def min_size(self) -> int:
 961    """Return the necessary minimum number of grid samples."""
 962
 963  @abc.abstractmethod
 964  def size_in_samples(self, size: int, /) -> int:
 965    """Return the domain size in units of inter-sample spacing."""
 966
 967  @abc.abstractmethod
 968  def point_from_index(self, index: _NDArray, size: int, /) -> _NDArray:
 969    """Return [0.0, 1.0] coordinates given [0, size - 1] indices."""
 970
 971  @abc.abstractmethod
 972  def index_from_point(self, point: _NDArray, size: int, /) -> _NDArray:
 973    """Return location x given coordinates [0.0, 1.0], where x == 0.0 is the first grid sample
 974    and x == size - 1.0 is the last grid sample."""
 975
 976  @abc.abstractmethod
 977  def reflect(self, index: _NDArray, size: int, /) -> _NDArray:
 978    """Map integer sample indices to interior ones using boundary reflection."""
 979
 980  @abc.abstractmethod
 981  def wrap(self, index: _NDArray, size: int, /) -> _NDArray:
 982    """Map integer sample indices to interior ones using wrapping."""
 983
 984  @abc.abstractmethod
 985  def reflect_clamp(self, index: _NDArray, size: int, /) -> _NDArray:
 986    """Map integer sample indices to interior ones using reflect-clamp."""
 987
 988
 989class DualGridtype(Gridtype):
 990  """Samples are at the center of cells in a uniform partition of the domain.
 991
 992  For a unit-domain dimension with N samples, each sample 0 <= i < N has position (i + 0.5) / N,
 993  e.g., [0.125, 0.375, 0.625, 0.875] for N = 4.
 994  """
 995
 996  def __init__(self) -> None:
 997    super().__init__(name='dual')
 998
 999  def min_size(self) -> int:
1000    return 1
1001
1002  def size_in_samples(self, size: int, /) -> int:
1003    return size
1004
1005  def point_from_index(self, index: _NDArray, size: int, /) -> _NDArray:
1006    return (index + 0.5) / size
1007
1008  def index_from_point(self, point: _NDArray, size: int, /) -> _NDArray:
1009    return point * size - 0.5
1010
1011  def reflect(self, index: _NDArray, size: int, /) -> _NDArray:
1012    index = np.mod(index, size * 2)
1013    return np.where(index < size, index, 2 * size - 1 - index)
1014
1015  def wrap(self, index: _NDArray, size: int, /) -> _NDArray:
1016    return np.mod(index, size)
1017
1018  def reflect_clamp(self, index: _NDArray, size: int, /) -> _NDArray:
1019    return np.minimum(np.where(index < 0, -1 - index, index), size - 1)
1020
1021
1022class PrimalGridtype(Gridtype):
1023  """Samples are at the vertices of cells in a uniform partition of the domain.
1024
1025  For a unit-domain dimension with N samples, each sample 0 <= i < N has position i / (N - 1),
1026  e.g., [0, 1/3, 2/3, 1] for N = 4.
1027  """
1028
1029  def __init__(self) -> None:
1030    super().__init__(name='primal')
1031
1032  def min_size(self) -> int:
1033    return 2
1034
1035  def size_in_samples(self, size: int, /) -> int:
1036    return size - 1
1037
1038  def point_from_index(self, index: _NDArray, size: int, /) -> _NDArray:
1039    return index / (size - 1)
1040
1041  def index_from_point(self, point: _NDArray, size: int, /) -> _NDArray:
1042    return point * (size - 1)
1043
1044  def reflect(self, index: _NDArray, size: int, /) -> _NDArray:
1045    index = np.mod(index, size * 2 - 2)
1046    return np.where(index < size, index, 2 * size - 2 - index)
1047
1048  def wrap(self, index: _NDArray, size: int, /) -> _NDArray:
1049    return np.mod(index, size - 1)
1050
1051  def reflect_clamp(self, index: _NDArray, size: int, /) -> _NDArray:
1052    return np.minimum(np.abs(index), size - 1)
1053
1054
1055_DICT_GRIDTYPES = {
1056    'dual': DualGridtype(),
1057    'primal': PrimalGridtype(),
1058}
1059
1060GRIDTYPES = list(_DICT_GRIDTYPES)
1061r"""Shortcut names for the two predefined grid types (specified per dimension):
1062
1063| `gridtype` | `'dual'`<br/>`DualGridtype()`<br/>(default) | `'primal'`<br/>`PrimalGridtype()`<br/>&nbsp; |
1064| --- |:---:|:---:|
1065| Sample positions in 2D<br/>and in 1D at different resolutions | ![Dual](https://github.com/hhoppe/resampler/raw/main/media/dual_grid_small.png) | ![Primal](https://github.com/hhoppe/resampler/raw/main/media/primal_grid_small.png) |
1066| Nesting of samples across resolutions | The samples positions do *not* nest. | The *even* samples remain at coarser scale. |
1067| Number $N_\ell$ of samples (per-dimension) at resolution level $\ell$ | $N_\ell=2^\ell$ | $N_\ell=2^\ell+1$ |
1068| Position of sample index $i$ within domain $[0, 1]$ | $\frac{i + 0.5}{N}$ ("half-integer" coordinates) | $\frac{i}{N-1}$ |
1069| Image resolutions ($N_\ell\times N_\ell$) for dyadic scales | $1\times1, ~~2\times2, ~~4\times4, ~~8\times8, ~\ldots$ | $2\times2, ~~3\times3, ~~5\times5, ~~9\times9, ~\ldots$ |
1070
1071See the source code for extensibility.
1072"""
1073
1074
1075def _get_gridtype(gridtype: str | Gridtype) -> Gridtype:
1076  """Return a `Gridtype`, which can be specified as a name in `GRIDTYPES`."""
1077  return gridtype if isinstance(gridtype, Gridtype) else _DICT_GRIDTYPES[gridtype]
1078
1079
1080def _get_gridtypes(
1081    gridtype: str | Gridtype | None,
1082    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None,
1083    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None,
1084    src_ndim: int,
1085    dst_ndim: int,
1086) -> tuple[list[Gridtype], list[Gridtype]]:
1087  """Return per-dim source and destination grid types given all parameters."""
1088  if gridtype is None and src_gridtype is None and dst_gridtype is None:
1089    gridtype = 'dual'
1090  if gridtype is not None:
1091    if src_gridtype is not None:
1092      raise ValueError('Cannot have both gridtype and src_gridtype.')
1093    if dst_gridtype is not None:
1094      raise ValueError('Cannot have both gridtype and dst_gridtype.')
1095    src_gridtype = dst_gridtype = gridtype
1096  src_gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(src_gridtype), src_ndim)]
1097  dst_gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(dst_gridtype), dst_ndim)]
1098  return src_gridtype2, dst_gridtype2
1099
1100
1101@dataclasses.dataclass(frozen=True)
1102class RemapCoordinates(abc.ABC):
1103  """Abstract base class for modifying the specified coordinates prior to evaluating the
1104  reconstruction kernels."""
1105
1106  @abc.abstractmethod
1107  def __call__(self, point: _NDArray, /) -> _NDArray:
1108    ...
1109
1110
1111@dataclasses.dataclass(frozen=True)
1112class NoRemapCoordinates(RemapCoordinates):
1113  """The coordinates are not remapped."""
1114
1115  def __call__(self, point: _NDArray, /) -> _NDArray:
1116    return point
1117
1118
1119@dataclasses.dataclass(frozen=True)
1120class MirrorRemapCoordinates(RemapCoordinates):
1121  """The coordinates are reflected across the domain boundaries so that they lie in the unit
1122  interval.  The resulting function is continuous but not smooth across the boundaries."""
1123
1124  def __call__(self, point: _NDArray, /) -> _NDArray:
1125    point = np.mod(point, 2.0)
1126    return np.where(point >= 1.0, 2.0 - point, point)
1127
1128
1129@dataclasses.dataclass(frozen=True)
1130class TileRemapCoordinates(RemapCoordinates):
1131  """The coordinates are mapped to the unit interval using a "modulo 1.0" operation.  The resulting
1132  function is generally discontinuous across the domain boundaries."""
1133
1134  def __call__(self, point: _NDArray, /) -> _NDArray:
1135    return np.mod(point, 1.0)
1136
1137
1138@dataclasses.dataclass(frozen=True)
1139class ExtendSamples(abc.ABC):
1140  """Abstract base class for replacing references to grid samples exterior to the unit domain by
1141  affine combinations of interior sample(s) and possibly the constant value (`cval`)."""
1142
1143  uses_cval: bool = False
1144  """True if some exterior samples are defined in terms of `cval`, i.e., if the computed weight
1145  is non-affine."""
1146
1147  @abc.abstractmethod
1148  def __call__(
1149      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1150  ) -> tuple[_NDArray, _NDArray]:
1151    """Detect references to exterior samples, i.e., entries of `index` that lie outside the
1152    interval [0, size), and update these indices (and possibly their associated weights) to
1153    reference only interior samples.  Return `new_index, new_weight`."""
1154
1155
1156@dataclasses.dataclass(frozen=True)
1157class ReflectExtendSamples(ExtendSamples):
1158  """Find the interior sample by reflecting across domain boundaries."""
1159
1160  def __call__(
1161      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1162  ) -> tuple[_NDArray, _NDArray]:
1163    index = gridtype.reflect(index, size)
1164    return index, weight
1165
1166
1167@dataclasses.dataclass(frozen=True)
1168class WrapExtendSamples(ExtendSamples):
1169  """Wrap the interior samples periodically.  For a `'primal'` grid, the last
1170  sample is ignored as its value is replaced by the first sample."""
1171
1172  def __call__(
1173      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1174  ) -> tuple[_NDArray, _NDArray]:
1175    index = gridtype.wrap(index, size)
1176    return index, weight
1177
1178
1179@dataclasses.dataclass(frozen=True)
1180class ClampExtendSamples(ExtendSamples):
1181  """Use the nearest interior sample."""
1182
1183  def __call__(
1184      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1185  ) -> tuple[_NDArray, _NDArray]:
1186    index = index.clip(0, size - 1)
1187    return index, weight
1188
1189
1190@dataclasses.dataclass(frozen=True)
1191class ReflectClampExtendSamples(ExtendSamples):
1192  """Extend the grid samples from [0, 1] into [-1, 0] using reflection and then define grid
1193  samples outside [-1, 1] as that of the nearest sample."""
1194
1195  def __call__(
1196      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1197  ) -> tuple[_NDArray, _NDArray]:
1198    index = gridtype.reflect_clamp(index, size)
1199    return index, weight
1200
1201
1202@dataclasses.dataclass(frozen=True)
1203class BorderExtendSamples(ExtendSamples):
1204  """Let all exterior samples have the constant value (`cval`)."""
1205
1206  def __init__(self) -> None:
1207    super().__init__(uses_cval=True)
1208
1209  def __call__(
1210      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1211  ) -> tuple[_NDArray, _NDArray]:
1212    low = index < 0
1213    weight[low] = 0.0
1214    index[low] = 0
1215    high = index >= size
1216    weight[high] = 0.0
1217    index[high] = size - 1
1218    return index, weight
1219
1220
1221@dataclasses.dataclass(frozen=True)
1222class ValidExtendSamples(ExtendSamples):
1223  """Assign all domain samples weight 1 and all outside samples weight 0.
1224  Compute a weighted reconstruction and divide by the reconstructed weight.
1225  (A row without exterior samples keeps its weights unchanged.)"""
1226
1227  def __init__(self) -> None:
1228    super().__init__(uses_cval=True)
1229
1230  def __call__(
1231      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1232  ) -> tuple[_NDArray, _NDArray]:
1233    low = index < 0
1234    weight[low] = 0.0
1235    index[low] = 0
1236    high = index >= size
1237    weight[high] = 0.0
1238    index[high] = size - 1
1239    sum_weight = weight.sum(axis=-1)
1240    renormalize = (low | high).any(axis=-1) & (sum_weight != 0.0)
1241    np.divide(weight, sum_weight[..., None], out=weight, where=renormalize[..., None])
1242    return index, weight
1243
1244
1245@dataclasses.dataclass(frozen=True)
1246class LinearExtendSamples(ExtendSamples):
1247  """Linearly extrapolate beyond boundary samples."""
1248
1249  def __call__(
1250      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1251  ) -> tuple[_NDArray, _NDArray]:
1252    if size < 2:
1253      index = gridtype.reflect(index, size)
1254      return index, weight
1255    # For each boundary, define new columns in index and weight arrays to represent the last and
1256    # next-to-last samples.  When we later construct the sparse resize matrix, we will sum the
1257    # duplicate index entries.
1258    low = index < 0
1259    high = index >= size
1260    w = np.empty((*weight.shape[:-1], weight.shape[-1] + 4), weight.dtype)
1261    x = index
1262    w[..., -4] = ((1 - x) * weight).sum(where=low, axis=-1)
1263    w[..., -3] = (x * weight).sum(where=low, axis=-1)
1264    x = (size - 1) - index
1265    w[..., -2] = (x * weight).sum(where=high, axis=-1)
1266    w[..., -1] = ((1 - x) * weight).sum(where=high, axis=-1)
1267    weight[low] = 0.0
1268    index[low] = 0
1269    weight[high] = 0.0
1270    index[high] = size - 1
1271    w[..., :-4] = weight
1272    weight = w
1273    new_index = np.empty(w.shape, index.dtype)
1274    new_index[..., :-4] = index
1275    # Let matrix (including zero values) be banded.
1276    new_index[..., -4:] = np.where(w[..., -4:] != 0.0, [0, 1, size - 2, size - 1], index[..., :1])
1277    index = new_index
1278    return index, weight
1279
1280
1281@dataclasses.dataclass(frozen=True)
1282class QuadraticExtendSamples(ExtendSamples):
1283  """Quadratically extrapolate beyond boundary samples."""
1284
1285  def __call__(
1286      self, index: _NDArray, weight: _NDArray, size: int, gridtype: Gridtype, /
1287  ) -> tuple[_NDArray, _NDArray]:
1288    # [Keys 1981] suggests this as x[-1] = 3*x[0] - 3*x[1] + x[2], calling it "cubic precision",
1289    # but it seems just quadratic.
1290    if size < 3:
1291      index = gridtype.reflect(index, size)
1292      return index, weight
1293    low = index < 0
1294    high = index >= size
1295    w = np.empty((*weight.shape[:-1], weight.shape[-1] + 6), weight.dtype)
1296    x = index
1297    w[..., -6] = (((0.5 * x - 1.5) * x + 1) * weight).sum(where=low, axis=-1)
1298    w[..., -5] = (((-x + 2) * x) * weight).sum(where=low, axis=-1)
1299    w[..., -4] = (((0.5 * x - 0.5) * x) * weight).sum(where=low, axis=-1)
1300    x = (size - 1) - index
1301    w[..., -3] = (((0.5 * x - 0.5) * x) * weight).sum(where=high, axis=-1)
1302    w[..., -2] = (((-x + 2) * x) * weight).sum(where=high, axis=-1)
1303    w[..., -1] = (((0.5 * x - 1.5) * x + 1) * weight).sum(where=high, axis=-1)
1304    weight[low] = 0.0
1305    index[low] = 0
1306    weight[high] = 0.0
1307    index[high] = size - 1
1308    w[..., :-6] = weight
1309    weight = w
1310    new_index = np.empty(w.shape, index.dtype)
1311    new_index[..., :-6] = index
1312    # Let matrix (including zero values) be banded.
1313    new_index[..., -6:] = np.where(
1314        w[..., -6:] != 0.0, [0, 1, 2, size - 3, size - 2, size - 1], index[..., :1]
1315    )
1316    index = new_index
1317    return index, weight
1318
1319
1320@dataclasses.dataclass(frozen=True)
1321class OverrideExteriorValue:
1322  """Base class to set the value outside some domain extent to a constant value (`cval`)."""
1323
1324  boundary_antialiasing: bool = True
1325  """Antialias the pixel values adjacent to the boundary of the extent."""
1326
1327  uses_cval: bool = False
1328  """Modify some weights to introduce references to the `cval` constant value."""
1329
1330  def __call__(self, weight: _NDArray, point: _NDArray, /) -> None:
1331    """For all `point` outside some extent, modify the weight to be zero."""
1332
1333  def override_using_signed_distance(
1334      self, weight: _NDArray, point: _NDArray, signed_distance: _NDArray, /
1335  ) -> None:
1336    """Reduce sample weights for "outside" values based on the signed distance function,
1337    to effectively assign the constant value `cval`."""
1338    all_points_inside_domain = np.all(signed_distance <= 0.0)
1339    if all_points_inside_domain:
1340      return
1341    if self.boundary_antialiasing and min(point.shape, default=0) >= 2:
1342      # For discontinuous coordinate mappings, we may need to somehow ignore
1343      # the large finite differences computed across the map discontinuities.
1344      gradient = np.gradient(point)
1345      gradient_norm = np.linalg.norm(np.atleast_2d(gradient), axis=0)
1346      signed_distance_in_samples = signed_distance / (gradient_norm + 1e-20)
1347      # Opacity is in linear space, which is correct if Gamma is set.
1348      opacity = (0.5 - signed_distance_in_samples).clip(0.0, 1.0)
1349      weight *= opacity[..., None]
1350    else:
1351      is_outside = signed_distance > 0.0
1352      weight[is_outside, :] = 0.0
1353
1354
1355@dataclasses.dataclass(frozen=True)
1356class NoOverrideExteriorValue(OverrideExteriorValue):
1357  """The function value is not overridden."""
1358
1359  def __call__(self, weight: _NDArray, point: _NDArray, /) -> None:
1360    pass
1361
1362
1363@dataclasses.dataclass(frozen=True)
1364class UnitDomainOverrideExteriorValue(OverrideExteriorValue):
1365  """Values outside the unit interval [0, 1] are replaced by the constant `cval`."""
1366
1367  def __init__(self, **kwargs: Any) -> None:
1368    super().__init__(uses_cval=True, **kwargs)
1369
1370  def __call__(self, weight: _NDArray, point: _NDArray, /) -> None:
1371    signed_distance = abs(point - 0.5) - 0.5  # Boundaries at 0.0 and 1.0.
1372    self.override_using_signed_distance(weight, point, signed_distance)
1373
1374
1375@dataclasses.dataclass(frozen=True)
1376class PlusMinusOneOverrideExteriorValue(OverrideExteriorValue):
1377  """Values outside the interval [-1, 1] are replaced by the constant `cval`."""
1378
1379  def __init__(self, **kwargs: Any) -> None:
1380    super().__init__(uses_cval=True, **kwargs)
1381
1382  def __call__(self, weight: _NDArray, point: _NDArray, /) -> None:
1383    signed_distance = abs(point) - 1.0  # Boundaries at -1.0 and 1.0.
1384    self.override_using_signed_distance(weight, point, signed_distance)
1385
1386
1387@dataclasses.dataclass(frozen=True)
1388class Boundary:
1389  """Domain boundary rules.  These define the reconstruction over the source domain near and beyond
1390  the domain boundaries.  The rules may be specified separately for each domain dimension."""
1391
1392  name: str = ''
1393  """Boundary rule name."""
1394
1395  coord_remap: RemapCoordinates = NoRemapCoordinates()
1396  """Modify specified coordinates prior to evaluating the reconstruction kernels."""
1397
1398  extend_samples: ExtendSamples = ReflectExtendSamples()
1399  """Define the value of each grid sample outside the unit domain as an affine combination of
1400  interior sample(s) and possibly the constant value (`cval`)."""
1401
1402  override_value: OverrideExteriorValue = NoOverrideExteriorValue()
1403  """Set the value outside some extent to a constant value (`cval`)."""
1404
1405  @property
1406  def uses_cval(self) -> bool:
1407    """True if weights may be non-affine, involving the constant value (`cval`)."""
1408    return self.extend_samples.uses_cval or self.override_value.uses_cval
1409
1410  def preprocess_coordinates(self, point: _NDArray, /) -> _NDArray:
1411    """Modify coordinates prior to evaluating the filter kernels."""
1412    # Antialiasing across the tile boundaries may be feasible but seems hard.
1413    point = self.coord_remap(point)
1414    return point
1415
1416  def fold(
1417      self, index: _NDArray, weight: _NDArray, point: _NDArray, size: int, gridtype: Gridtype, /
1418  ) -> tuple[_NDArray, _NDArray]:
1419    """Fold the kernel taps that reference exterior samples onto interior samples (and `cval`)."""
1420    index, weight = self.extend_samples(index, weight, size, gridtype)
1421    self.override_reconstruction(weight, point)
1422    return index, weight
1423
1424  def override_reconstruction(self, weight: _NDArray, point: _NDArray, /) -> None:
1425    """For points outside an extent, modify weight to zero to assign `cval`."""
1426    self.override_value(weight, point)
1427
1428
1429_DICT_BOUNDARIES = {
1430    'reflect': Boundary('reflect', extend_samples=ReflectExtendSamples()),
1431    'wrap': Boundary('wrap', extend_samples=WrapExtendSamples()),
1432    'tile': Boundary(
1433        'tile', coord_remap=TileRemapCoordinates(), extend_samples=ReflectExtendSamples()
1434    ),
1435    'clamp': Boundary('clamp', extend_samples=ClampExtendSamples()),
1436    'border': Boundary('border', extend_samples=BorderExtendSamples()),
1437    'natural': Boundary(
1438        'natural',
1439        extend_samples=ValidExtendSamples(),
1440        override_value=UnitDomainOverrideExteriorValue(),
1441    ),
1442    'linear_constant': Boundary(
1443        'linear_constant',
1444        extend_samples=LinearExtendSamples(),
1445        override_value=UnitDomainOverrideExteriorValue(),
1446    ),
1447    'quadratic_constant': Boundary(
1448        'quadratic_constant',
1449        extend_samples=QuadraticExtendSamples(),
1450        override_value=UnitDomainOverrideExteriorValue(),
1451    ),
1452    'reflect_clamp': Boundary('reflect_clamp', extend_samples=ReflectClampExtendSamples()),
1453    'constant': Boundary(
1454        'constant',
1455        extend_samples=ReflectExtendSamples(),
1456        override_value=UnitDomainOverrideExteriorValue(),
1457    ),
1458    'linear': Boundary('linear', extend_samples=LinearExtendSamples()),
1459    'quadratic': Boundary('quadratic', extend_samples=QuadraticExtendSamples()),
1460}
1461
1462BOUNDARIES = list(_DICT_BOUNDARIES)
1463"""Shortcut names for some predefined boundary rules (as defined by `_DICT_BOUNDARIES`):
1464
1465| name                   | a.k.a. / comments |
1466|------------------------|-------------------|
1467| `'reflect'`            | *reflected*, *symm*, *symmetric*, *mirror*, *grid-mirror* |
1468| `'wrap'`               | *periodic*, *repeat*, *grid-wrap* |
1469| `'tile'`               | like `'reflect'` within unit domain, then tile discontinuously |
1470| `'clamp'`              | *clamped*, *nearest*, *edge*, *clamp-to-edge*, repeat last sample |
1471| `'border'`             | *grid-constant*, use `cval` for samples outside unit domain |
1472| `'natural'`            | *renormalize* using only interior samples, use `cval` outside domain |
1473| `'reflect_clamp'`      | *mirror-clamp-to-edge* |
1474| `'constant'`           | like `'reflect'` but replace by `cval` outside unit domain |
1475| `'linear'`             | extrapolate from 2 last samples |
1476| `'quadratic'`          | extrapolate from 3 last samples |
1477| `'linear_constant'`    | like `'linear'` but replace by `cval` outside unit domain |
1478| `'quadratic_constant'` | like `'quadratic'` but replace by `cval` outside unit domain |
1479
1480These boundary rules may be specified per dimension.  See the source code for extensibility
1481using the classes `RemapCoordinates`, `ExtendSamples`, and `OverrideExteriorValue`.
1482
1483**Boundary rules illustrated in 1D:**
1484
1485<center>
1486<img src="https://github.com/hhoppe/resampler/raw/main/media/boundary_rules_in_1D.png" width="100%"/>
1487</center>
1488
1489**Boundary rules illustrated in 2D:**
1490
1491<center>
1492<img src="https://github.com/hhoppe/resampler/raw/main/media/boundary_rules_in_2D.png" width="100%"/>
1493</center>
1494"""
1495
1496_OFTUSED_BOUNDARIES = (
1497    'reflect wrap tile clamp border natural linear_constant quadratic_constant'.split()
1498)
1499"""A useful subset of `BOUNDARIES` for visualization in figures."""
1500
1501
1502def _get_boundary(boundary: str | Boundary, /) -> Boundary:
1503  """Return a `Boundary`, which can be specified as a name in `BOUNDARIES`."""
1504  return boundary if isinstance(boundary, Boundary) else _DICT_BOUNDARIES[boundary]
1505
1506
1507@dataclasses.dataclass(frozen=True)
1508class Filter(abc.ABC):
1509  """Abstract base class for filter kernel functions.
1510
1511  Each kernel is assumed to be a zero-phase filter, i.e., to be symmetric in a support
1512  interval [-radius, radius].  (Some sites instead define kernels over the interval [0, N]
1513  where N = 2 * radius.)
1514
1515  Portions of this code are adapted from the C++ library in
1516  https://github.com/hhoppe/Mesh-processing-library/blob/main/libHh/Filter.cpp
1517
1518  See also https://hhoppe.com/proj/filtering/.
1519  """
1520
1521  name: str
1522  """Filter kernel name."""
1523
1524  radius: float
1525  """Max absolute value of x for which self(x) is nonzero."""
1526
1527  interpolating: bool = True
1528  """True if self(0) == 1.0 and self(i) == 0.0 for all nonzero integers i."""
1529
1530  continuous: bool = True
1531  """True if the kernel function has $C^0$ continuity."""
1532
1533  partition_of_unity: bool = True
1534  """True if the convolution of the kernel with a Dirac comb reproduces the
1535  unity function."""
1536
1537  unit_integral: bool = True
1538  """True if the integral of the kernel function is 1."""
1539
1540  requires_digital_filter: bool = False
1541  """True if the filter needs a pre/post digital filter for interpolation."""
1542
1543  @abc.abstractmethod
1544  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1545    """Return evaluation of filter kernel at locations x."""
1546
1547
1548class ImpulseFilter(Filter):
1549  """See https://en.wikipedia.org/wiki/Dirac_delta_function."""
1550
1551  def __init__(self) -> None:
1552    super().__init__(name='impulse', radius=1e-20, continuous=False, partition_of_unity=False)
1553
1554  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1555    raise AssertionError('The Impulse is infinitely narrow, so cannot be directly evaluated.')
1556
1557
1558class BoxFilter(Filter):
1559  """See https://en.wikipedia.org/wiki/Box_function.
1560
1561  The kernel function has value 1.0 over the half-open interval [-.5, .5).
1562  """
1563
1564  def __init__(self) -> None:
1565    super().__init__(name='box', radius=0.5, continuous=False)
1566
1567  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1568    use_asymmetric = True
1569    if use_asymmetric:
1570      x = np.asarray(x)
1571      return np.where((-0.5 <= x) & (x < 0.5), 1.0, 0.0)
1572    x = np.abs(x)
1573    return np.where(x < 0.5, 1.0, np.where(x == 0.5, 0.5, 0.0))
1574
1575
1576class TrapezoidFilter(Filter):
1577  """Filter for antialiased "area-based" filtering.
1578
1579  Args:
1580    radius: Specifies the support [-radius, radius] of the filter, where 0.5 < radius <= 1.0.
1581      The special case `radius = None` is a placeholder that indicates that the filter will be
1582      replaced by a trapezoid of the appropriate radius (based on scaling) for correct
1583      antialiasing in both minification and magnification.
1584
1585  This filter is similar to the BoxFilter but with linearly sloped sides.  It has value 1.0
1586  in the interval abs(x) <= 1.0 - radius and decreases linearly to value 0.0 in the interval
1587  1.0 - radius <= abs(x) <= radius, always with value 0.5 at x = 0.5.
1588  """
1589
1590  def __init__(self, *, radius: float | None = None) -> None:
1591    if radius is None:
1592      super().__init__(name='trapezoid', radius=0.0)
1593      return
1594    if not 0.5 < radius <= 1.0:
1595      raise ValueError(f'Radius {radius} is outside the range (0.5, 1.0].')
1596    super().__init__(name=f'trapezoid_{radius}', radius=radius)
1597
1598  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1599    x = np.abs(x)
1600    assert 0.5 < self.radius <= 1.0
1601    return ((0.5 + 0.25 / (self.radius - 0.5)) - (0.5 / (self.radius - 0.5)) * x).clip(0.0, 1.0)
1602
1603
1604class TriangleFilter(Filter):
1605  """See https://en.wikipedia.org/wiki/Triangle_function.
1606
1607  Also known as the hat or tent function.  It is used for piecewise-linear
1608  (or bilinear, or trilinear, ...) interpolation.
1609  """
1610
1611  def __init__(self) -> None:
1612    super().__init__(name='triangle', radius=1.0)
1613
1614  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1615    return (1.0 - np.abs(x)).clip(0.0, 1.0)
1616
1617
1618class CubicFilter(Filter):
1619  """Family of cubic filters parameterized by two scalar parameters.
1620
1621  Args:
1622    b: first scalar parameter.
1623    c: second scalar parameter.
1624
1625  See https://en.wikipedia.org/wiki/Mitchell%E2%80%93Netravali_filters and
1626  https://doi.org/10.1145/378456.378514.
1627
1628  [D. P. Mitchell and A. N. Netravali. Reconstruction filters in computer graphics.
1629  Computer Graphics (Proceedings of ACM SIGGRAPH 1988), 22(4):221-228, 1988.]
1630
1631  - The filter has quadratic precision iff b + 2 * c == 1.
1632  - The filter is interpolating iff b == 0.
1633  - (b=1, c=0) is the (non-interpolating) cubic B-spline basis;
1634  - (b=1/3, c=1/3) is the Mitchell filter;
1635  - (b=0, c=0.5) is the Catmull-Rom spline (which has cubic precision);
1636  - (b=0, c=0.75) is the "sharper cubic" used in Photoshop and OpenCV.
1637  """
1638
1639  def __init__(self, *, b: float, c: float, name: str | None = None) -> None:
1640    name = f'cubic_b{b}_c{c}' if name is None else name
1641    interpolating = b == 0
1642    super().__init__(name=name, radius=2.0, interpolating=interpolating)
1643    self.b, self.c = b, c
1644
1645  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1646    x = np.abs(x)
1647    b, c = self.b, self.c
1648    f3, f2, f0 = 2 - 9 / 6 * b - c, -3 + 2 * b + c, 1 - 1 / 3 * b
1649    g3, g2, g1, g0 = -b / 6 - c, b + 5 * c, -2 * b - 8 * c, 8 / 6 * b + 4 * c
1650    # (np.polynomial.polynomial.polyval(x, [f0, 0, f2, f3]) is almost
1651    # twice as slow; see also https://stackoverflow.com/questions/24065904)
1652    v01 = ((f3 * x + f2) * x) * x + f0
1653    v12 = ((g3 * x + g2) * x + g1) * x + g0
1654    return np.where(x < 1.0, v01, np.where(x < 2.0, v12, 0.0))
1655
1656
1657class CatmullRomFilter(CubicFilter):
1658  """Cubic filter with cubic precision.  Also known as Keys filter.
1659
1660  [E. Catmull, R. Rom.  A class of local interpolating splines.  Computer aided geometric
1661  design, 1974]
1662  [Wikipedia](https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull%E2%80%93Rom_spline)
1663
1664  [R. G. Keys.  Cubic convolution interpolation for digital image processing.
1665  IEEE Trans. on Acoustics, Speech, and Signal Processing, 29(6), 1981.]
1666  https://ieeexplore.ieee.org/document/1163711/.
1667  """
1668
1669  def __init__(self) -> None:
1670    super().__init__(b=0, c=0.5, name='cubic')
1671
1672
1673class MitchellFilter(CubicFilter):
1674  """See https://doi.org/10.1145/378456.378514.
1675
1676  [D. P. Mitchell and A. N. Netravali.  Reconstruction filters in computer graphics.  Computer
1677  Graphics (Proceedings of ACM SIGGRAPH 1988), 22(4):221-228, 1988.]
1678  """
1679
1680  def __init__(self) -> None:
1681    super().__init__(b=1 / 3, c=1 / 3, name='mitchell')
1682
1683
1684class SharpCubicFilter(CubicFilter):
1685  """Cubic filter that is sharper than Catmull-Rom filter.
1686
1687  Used by some tools including OpenCV and Photoshop.
1688
1689  See https://en.wikipedia.org/wiki/Mitchell%E2%80%93Netravali_filters and
1690  https://entropymine.com/resamplescope/notes/photoshop/.
1691  """
1692
1693  def __init__(self) -> None:
1694    super().__init__(b=0, c=0.75, name='sharpcubic')
1695
1696
1697class LanczosFilter(Filter):
1698  """High-quality filter: sinc function modulated by a sinc window.
1699
1700  Args:
1701    radius: Specifies the support window [-radius, radius] over which the filter is nonzero.
1702    sampled: If True, use a discretized approximation for improved speed.
1703
1704  See https://en.wikipedia.org/wiki/Lanczos_kernel.
1705  """
1706
1707  def __init__(self, *, radius: int, sampled: bool = True) -> None:
1708    super().__init__(
1709        name=f'lanczos_{radius}', radius=radius, partition_of_unity=False, unit_integral=False
1710    )
1711
1712    @_cache_sampled_1d_function(xmin=-radius, xmax=radius, enable=sampled)
1713    def _eval(x: _ArrayLike) -> _NDArray:
1714      x = np.abs(x)
1715      # Note that window[n] = sinc(2*n/N - 1), with 0 <= n <= N.
1716      # But, x = n - N/2, or equivalently, n = x + N/2, with -N/2 <= x <= N/2.
1717      window = _sinc(x / radius)  # Zero-phase function w_0(x).
1718      return np.where(x < radius, _sinc(x) * window, 0.0)
1719
1720    self._function = _eval
1721
1722  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1723    return self._function(x)
1724
1725
1726class GeneralizedHammingFilter(Filter):
1727  """Sinc function modulated by a Hamming window.
1728
1729  Args:
1730    radius: Specifies the support window [-radius, radius] over which the filter is nonzero.
1731    a0: Scalar parameter, where 0.0 < a0 < 1.0.  The case of a0=0.5 is the Hann filter.
1732
1733  See https://en.wikipedia.org/wiki/Window_function#Hann_and_Hamming_windows,
1734  and hamming() in https://github.com/scipy/scipy/blob/main/scipy/signal/windows/_windows.py.
1735
1736  Note that `'hamming3'` is `(radius=3, a0=25/46)`, which is close to but different from `a0=0.54`.
1737
1738  See also np.hamming() and np.hanning().
1739  """
1740
1741  def __init__(self, *, radius: int, a0: float) -> None:
1742    super().__init__(
1743        name=f'hamming_{radius}_{a0}',
1744        radius=radius,
1745        partition_of_unity=False,  # 1:1.00242  av=1.00188  sd=0.00052909
1746        unit_integral=False,  # 1.00188
1747    )
1748    assert 0.0 < a0 < 1.0
1749    self.a0 = a0
1750
1751  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1752    x = np.abs(x)
1753    # Note that window[n] = a0 - (1 - a0) * cos(2 * pi * n / N), 0 <= n <= N.
1754    # With n = x + N/2, we get the zero-phase function w_0(x):
1755    window = self.a0 + (1.0 - self.a0) * np.cos(np.pi / self.radius * x)
1756    return np.where(x < self.radius, _sinc(x) * window, 0.0)
1757
1758
1759class KaiserFilter(Filter):
1760  """Sinc function modulated by a Kaiser-Bessel window.
1761
1762  See https://en.wikipedia.org/wiki/Kaiser_window, and example use in:
1763  [Karras et al. 2021.  Alias-free generative adversarial networks.
1764  https://arxiv.org/pdf/2106.12423.pdf].
1765
1766  See also np.kaiser().
1767
1768  Args:
1769    radius: Value L/2 in the definition.  It may be fractional for a (digital) resizing filter
1770      (sample spacing s != 1) with an even number of samples (dual grid), e.g., Eq. (6)
1771      in [Karras et al. 2021] --- this affects the precise shape of the window function.
1772    beta: Determines the trade-off between main-lobe width and side-lobe level.
1773    sampled: If True, use a discretized approximation for improved speed.
1774  """
1775
1776  def __init__(self, *, radius: float, beta: float, sampled: bool = True) -> None:
1777    assert beta >= 0.0
1778    super().__init__(
1779        name=f'kaiser_{radius}_{beta}', radius=radius, partition_of_unity=False, unit_integral=False
1780    )
1781
1782    @_cache_sampled_1d_function(xmin=-math.ceil(radius), xmax=math.ceil(radius), enable=sampled)
1783    def _eval(x: _ArrayLike) -> _NDArray:
1784      x = np.abs(x)
1785      window = np.i0(beta * np.sqrt((1.0 - np.square(x / radius)).clip(0.0, 1.0))) / np.i0(beta)
1786      return np.where(x <= radius + 1e-6, _sinc(x) * window, 0.0)
1787
1788    self._function = _eval
1789
1790  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1791    return self._function(x)
1792
1793
1794class BsplineFilter(Filter):
1795  """B-spline of a non-negative degree.
1796
1797  Args:
1798    degree: The polynomial degree of the B-spline segments.
1799      With `degree=0`, it is like `BoxFilter` except with f(0.5) = f(-0.5) = 0.
1800      With `degree=1`, it is identical to `TriangleFilter`.
1801      With `degree >= 2`, it is no longer interpolating.
1802
1803  See [Carl de Boor.  A practical guide to splines.  Springer, 2001.]
1804  https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.BSpline.html
1805  """
1806
1807  def __init__(self, *, degree: int) -> None:
1808    if degree < 0:
1809      raise ValueError(f'Bspline of degree {degree} is invalid.')
1810    radius = (degree + 1) / 2
1811    interpolating = degree <= 1
1812    super().__init__(
1813        name=f'bspline{degree}',
1814        radius=radius,
1815        interpolating=interpolating,
1816        continuous=degree >= 1,
1817    )
1818    t = list(range(degree + 2))
1819    self._bspline = scipy.interpolate.BSpline.basis_element(t)
1820
1821  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1822    x = np.abs(x)
1823    return np.where(x < self.radius, self._bspline(x + self.radius), 0.0)
1824
1825
1826class CardinalBsplineFilter(Filter):
1827  """Interpolating B-spline, achieved with aid of digital pre or post filter.
1828
1829  Args:
1830    degree: The polynomial degree of the B-spline segments.
1831    sampled: If True, use a discretized approximation for improved speed.
1832
1833  See [Hou and Andrews.  Cubic splines for image interpolation and digital filtering, 1978] and
1834  [Unser et al.  Fast B-spline transforms for continuous image representation and interpolation,
1835  1991].
1836  """
1837
1838  def __init__(self, *, degree: int, sampled: bool = True) -> None:
1839    if degree < 0:
1840      raise ValueError(f'Bspline of degree {degree} is invalid.')
1841    self.degree = degree
1842    radius = (degree + 1) / 2
1843    super().__init__(
1844        name=f'cardinal{degree}',
1845        radius=radius,
1846        requires_digital_filter=degree >= 2,
1847        continuous=degree >= 1,
1848    )
1849    t = list(range(degree + 2))
1850    bspline = scipy.interpolate.BSpline.basis_element(t)
1851
1852    @_cache_sampled_1d_function(xmin=-radius, xmax=radius, enable=sampled)
1853    def _eval(x: _ArrayLike) -> _NDArray:
1854      x = np.abs(x)
1855      return np.where(x < radius, bspline(x + radius), 0.0)
1856
1857    self._function = _eval
1858
1859  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1860    return self._function(x)
1861
1862
1863class OmomsFilter(Filter):
1864  """OMOMS interpolating filter, with aid of digital pre or post filter.
1865
1866  Args:
1867    degree: The polynomial degree of the filter segments.
1868
1869  Optimal MOMS (maximal-order-minimal-support) function; see [Blu and Thevenaz, MOMS: Maximal-order
1870  interpolation of minimal support, 2001].
1871  https://infoscience.epfl.ch/record/63074/files/blu0101.pdf
1872  """
1873
1874  def __init__(self, *, degree: int) -> None:
1875    if degree not in (3, 5):
1876      raise ValueError(f'Degree {degree} not supported.')
1877    super().__init__(name=f'omoms{degree}', radius=(degree + 1) / 2, requires_digital_filter=True)
1878    self.degree = degree
1879
1880  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1881    x = np.abs(x)
1882    match self.degree:
1883      case 3:
1884        v01 = ((0.5 * x - 1.0) * x + 3 / 42) * x + 26 / 42
1885        v12 = ((-7 / 42 * x + 1.0) * x - 85 / 42) * x + 58 / 42
1886        return np.where(x < 1.0, v01, np.where(x < 2.0, v12, 0.0))
1887      case 5:
1888        v01 = ((((-1 / 12 * x + 1 / 4) * x - 5 / 99) * x - 9 / 22) * x - 1 / 792) * x + 229 / 440
1889        v12 = (
1890            (((1 / 24 * x - 3 / 8) * x + 505 / 396) * x - 83 / 44) * x + 1351 / 1584
1891        ) * x + 839 / 2640
1892        v23 = (
1893            (((-1 / 120 * x + 1 / 8) * x - 299 / 396) * x + 101 / 44) * x - 27811 / 7920
1894        ) * x + 5707 / 2640
1895        return np.where(x < 1.0, v01, np.where(x < 2.0, v12, np.where(x < 3.0, v23, 0.0)))
1896      case _:
1897        raise ValueError(self.degree)
1898
1899
1900class GaussianFilter(Filter):
1901  r"""See https://en.wikipedia.org/wiki/Gaussian_function.
1902
1903  Args:
1904    standard_deviation: Sets the Gaussian $\sigma$.  The default value is 1.25/3.0, which
1905      creates a kernel that is as-close-as-possible to a partition of unity.
1906  """
1907
1908  DEFAULT_STANDARD_DEVIATION = 1.25 / 3.0
1909  """This value creates a kernel that is as-close-as-possible to a partition of unity; see
1910  mesh_processing/test/GridOp_test.cpp: `0.93503:1.06497     av=1           sd=0.0459424`.
1911  Another possibility is 0.5, as suggested on p. 4 of [Ken Turkowski.  Filters for common
1912  resampling tasks, 1990] for kernels with a support of 3 pixels.
1913  https://cadxfem.org/inf/ResamplingFilters.pdf
1914  """
1915
1916  def __init__(self, *, standard_deviation: float = DEFAULT_STANDARD_DEVIATION) -> None:
1917    super().__init__(
1918        name=f'gaussian_{standard_deviation:.3f}',
1919        radius=np.ceil(8.0 * standard_deviation),  # Sufficiently large.
1920        interpolating=False,
1921        partition_of_unity=False,
1922    )
1923    self.standard_deviation = standard_deviation
1924
1925  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1926    x = np.abs(x)
1927    sdv = self.standard_deviation
1928    v0r = np.exp(np.square(x / sdv) / -2.0) / (np.sqrt(math.tau) * sdv)
1929    return np.where(x < self.radius, v0r, 0.0)
1930
1931
1932class NarrowBoxFilter(Filter):
1933  """Compact footprint, used for visualization of grid sample location.
1934
1935  Args:
1936    radius: Specifies the support [-radius, radius] of the narrow box function.  (The default
1937      value 0.199 is an inexact 0.2 to avoid numerical ambiguities.)
1938  """
1939
1940  def __init__(self, *, radius: float = 0.199) -> None:
1941    super().__init__(
1942        name='narrowbox',
1943        radius=radius,
1944        continuous=False,
1945        unit_integral=False,
1946        partition_of_unity=False,
1947    )
1948
1949  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1950    radius = self.radius
1951    magnitude = 1.0
1952    x = np.asarray(x)
1953    return np.where((-radius <= x) & (x < radius), magnitude, 0.0)
1954
1955
1956_DEFAULT_FILTER = 'lanczos3'
1957
1958_DICT_FILTERS = {
1959    'impulse': ImpulseFilter(),
1960    'box': BoxFilter(),
1961    'trapezoid': TrapezoidFilter(),
1962    'triangle': TriangleFilter(),
1963    'cubic': CatmullRomFilter(),
1964    'sharpcubic': SharpCubicFilter(),
1965    'lanczos3': LanczosFilter(radius=3),
1966    'lanczos5': LanczosFilter(radius=5),
1967    'lanczos10': LanczosFilter(radius=10),
1968    'cardinal3': CardinalBsplineFilter(degree=3),
1969    'cardinal5': CardinalBsplineFilter(degree=5),
1970    'omoms3': OmomsFilter(degree=3),
1971    'omoms5': OmomsFilter(degree=5),
1972    'hamming3': GeneralizedHammingFilter(radius=3, a0=25 / 46),
1973    'kaiser3': KaiserFilter(radius=3.0, beta=7.12),
1974    'gaussian': GaussianFilter(),
1975    'bspline3': BsplineFilter(degree=3),
1976    'mitchell': MitchellFilter(),
1977    'narrowbox': NarrowBoxFilter(),
1978    # Not in FILTERS:
1979    'hamming1': GeneralizedHammingFilter(radius=1, a0=0.54),
1980    'hann3': GeneralizedHammingFilter(radius=3, a0=0.5),
1981    'lanczos4': LanczosFilter(radius=4),
1982}
1983
1984FILTERS = list(itertools.takewhile(lambda x: x != 'hamming1', _DICT_FILTERS))
1985r"""Shortcut names for some predefined filter kernels (specified per dimension).
1986The names expand to:
1987
1988| name           | `Filter`                      | a.k.a. / comments |
1989|----------------|-------------------------------|-------------------|
1990| `'impulse'`    | `ImpulseFilter()`             | *nearest* |
1991| `'box'`        | `BoxFilter()`                 | non-antialiased box, e.g. ImageMagick |
1992| `'trapezoid'`  | `TrapezoidFilter()`           | *area* antialiasing, e.g. `cv.INTER_AREA` |
1993| `'triangle'`   | `TriangleFilter()`            | *linear*  (*bilinear* in 2D), spline `order=1` |
1994| `'cubic'`      | `CatmullRomFilter()`          | *catmullrom*, *keys*, *bicubic* |
1995| `'sharpcubic'` | `SharpCubicFilter()`          | `cv.INTER_CUBIC`, `torch 'bicubic'` |
1996| `'lanczos3'`   | `LanczosFilter`(radius=3)     | support window [-3, 3] |
1997| `'lanczos5'`   | `LanczosFilter`(radius=5)     | [-5, 5] |
1998| `'lanczos10'`  | `LanczosFilter`(radius=10)    | [-10, 10] |
1999| `'cardinal3'`  | `CardinalBsplineFilter`(degree=3) | *spline interpolation*, `order=3`, *GF* |
2000| `'cardinal5'`  | `CardinalBsplineFilter`(degree=5) | *spline interpolation*, `order=5`, *GF* |
2001| `'omoms3'`     | `OmomsFilter`(degree=3)       | non-$C^1$, [-2, 2], *GF* |
2002| `'omoms5'`     | `OmomsFilter`(degree=5)       | non-$C^1$, [-3, 3], *GF* |
2003| `'hamming3'`   | `GeneralizedHammingFilter`(...) | (radius=3, a0=25/46) |
2004| `'kaiser3'`    | `KaiserFilter`(radius=3.0, beta=7.12) | |
2005| `'gaussian'`   | `GaussianFilter()`            | non-interpolating, default $\sigma=1.25/3$ |
2006| `'bspline3'`   | `BsplineFilter`(degree=3)     | non-interpolating |
2007| `'mitchell'`   | `MitchellFilter()`            | *mitchellcubic* |
2008| `'narrowbox'`  | `NarrowBoxFilter()`           | for visualization of sample positions |
2009
2010The comment label *GF* denotes a [generalized filter](https://hhoppe.com/proj/filtering/), formed
2011as the composition of a finitely supported kernel and a discrete inverse convolution.
2012
2013**Some example filter kernels:**
2014
2015<center>
2016<img src="https://github.com/hhoppe/resampler/raw/main/media/filter_summary.png" width="100%"/>
2017</center>
2018
2019<br/>A more extensive set of filters is presented [here](#plots_of_filters) in the
2020[notebook](https://colab.research.google.com/github/hhoppe/resampler/blob/main/resampler_notebook.ipynb),
2021together with visualizations and analyses of the filter properties.
2022See the source code for extensibility.
2023"""
2024
2025
2026def _get_filter(filter: str | Filter, /) -> Filter:
2027  """Return a `Filter`, which can be specified as a name string key in `FILTERS`."""
2028  return filter if isinstance(filter, Filter) else _DICT_FILTERS[filter]
2029
2030
2031def _to_float_01(array: _Array, /, dtype: _DTypeLike) -> _Array:
2032  """Scale uint to the range [0.0, 1.0], and clip float to [0.0, 1.0]."""
2033  array_dtype = _arr_dtype(array)
2034  dtype = np.dtype(dtype)
2035  assert np.issubdtype(dtype, np.floating)
2036  match array_dtype.type:
2037    case np.uint8 | np.uint16 | np.uint32:
2038      if _arr_arraylib(array) == 'numpy':
2039        result: Any = np.multiply(array, 1 / np.iinfo(array_dtype).max, dtype=dtype)
2040        return result
2041      return typing.cast(_Array, _arr_astype(array, dtype) / np.iinfo(array_dtype).max)
2042    case _:
2043      assert np.issubdtype(array_dtype, np.floating)
2044      return _arr_clip(array, 0.0, 1.0, dtype)
2045
2046
2047def _from_float(array: _Array, /, dtype: _DTypeLike) -> _Array:
2048  """Convert a float in range [0.0, 1.0] to uint or float type."""
2049  assert np.issubdtype(_arr_dtype(array), np.floating)
2050  dtype = np.dtype(dtype)
2051  match dtype.type:
2052    case np.uint8 | np.uint16:
2053      scale32 = typing.cast(float, np.float32(np.iinfo(dtype.name).max))
2054      return _arr_astype(typing.cast(_Array, array * scale32 + 0.5), dtype)
2055    case np.uint32:
2056      scale64 = typing.cast(float, np.float64(np.iinfo(dtype.name).max))
2057      return _arr_astype(typing.cast(_Array, array * scale64 + 0.5), dtype)
2058    case _:
2059      assert np.issubdtype(dtype, np.floating)
2060      return _arr_astype(array, dtype)
2061
2062
2063@dataclasses.dataclass(frozen=True)
2064class Gamma(abc.ABC):
2065  """Abstract base class for transfer functions on sample values.
2066
2067  Image/video content is often stored using a color component transfer function.
2068  See https://en.wikipedia.org/wiki/Gamma_correction.
2069
2070  Converts between integer types and [0.0, 1.0] internal value range.
2071  """
2072
2073  name: str
2074  """Name of component transfer function."""
2075
2076  @abc.abstractmethod
2077  def decode(self, array: _Array, /, dtype: _DTypeLike = np.float32) -> _Array:
2078    """Decode source sample values into floating-point, possibly nonlinearly.
2079
2080    Uint source values are mapped to the range [0.0, 1.0].
2081    """
2082
2083  @abc.abstractmethod
2084  def encode(self, array: _Array, /, dtype: _DTypeLike) -> _Array:
2085    """Encode float signal into destination samples, possibly nonlinearly.
2086
2087    Uint destination values are mapped from the range [0.0, 1.0].
2088
2089    Note that `IdentityGamma` does not clip non-integer destination types to the range [0.0, 1.0].
2090    If that is desired, it can be performed as a postprocess using `output.clip(0.0, 1.0)`.
2091    """
2092
2093
2094class IdentityGamma(Gamma):
2095  """Identity component transfer function."""
2096
2097  def __init__(self) -> None:
2098    super().__init__('identity')
2099
2100  def decode(self, array: _Array, /, dtype: _DTypeLike = np.float32) -> _Array:
2101    dtype = np.dtype(dtype)
2102    assert np.issubdtype(dtype, np.inexact)
2103    if np.issubdtype(_arr_dtype(array), np.unsignedinteger):
2104      return _to_float_01(array, dtype)
2105    return _arr_astype(array, dtype)
2106
2107  def encode(self, array: _Array, /, dtype: _DTypeLike) -> _Array:
2108    dtype = np.dtype(dtype)
2109    assert np.issubdtype(dtype, np.number)
2110    if np.issubdtype(dtype, np.unsignedinteger):
2111      return _from_float(_arr_clip(array, 0.0, 1.0), dtype)
2112    if np.issubdtype(dtype, np.integer):
2113      # The conversion to int truncates toward zero, so shift by 0.5 away from zero to round.
2114      shifted = _arr_where(typing.cast(_Array, array < 0.0), array - 0.5, array + 0.5)
2115      return _arr_astype(shifted, dtype)
2116    return _arr_astype(array, dtype)
2117
2118
2119@functools.lru_cache(maxsize=16)
2120def _decode_table(gamma: Gamma, dtype: _DType, num: int, arraylib: str, /) -> Any:
2121  """Return the decoded values of the `num` unsigned-integer sample values, as a lookup table."""
2122  return _make_array(gamma.decode(np.arange(num, dtype=dtype) / (num - 1), dtype), arraylib)
2123
2124
2125def _decode_using_table(gamma: Gamma, array: _Array, dtype: _DType, /) -> _Array | None:
2126  """Decode 8- or 16-bit unsigned samples through a lookup table, or return None for other types."""
2127  num = {np.dtype(np.uint8): 256, np.dtype(np.uint16): 65536}.get(_arr_dtype(array))
2128  if num is None:
2129    return None
2130  return _arr_getitem(_decode_table(gamma, dtype, num, _arr_arraylib(array)), array)
2131
2132
2133class PowerGamma(Gamma):
2134  """Gamma correction using a power function."""
2135
2136  def __init__(self, power: float) -> None:
2137    super().__init__(name=f'power_{power}')
2138    self.power = power
2139
2140  def decode(self, array: _Array, /, dtype: _DTypeLike = np.float32) -> _Array:
2141    dtype = np.dtype(dtype)
2142    assert np.issubdtype(dtype, np.floating)
2143    if self.power != 2 and (decoded := _decode_using_table(self, array, dtype)) is not None:
2144      return decoded
2145
2146    array = _to_float_01(array, dtype)
2147    return _arr_square(array) if self.power == 2 else typing.cast(_Array, array**self.power)
2148
2149  def encode(self, array: _Array, /, dtype: _DTypeLike) -> _Array:
2150    array = _arr_clip(array, 0.0, 1.0)
2151    if self.power == 2:
2152      array = _arr_sqrt(array)
2153    else:
2154      array = typing.cast(_Array, array ** (1.0 / self.power))
2155    return _from_float(array, dtype)
2156
2157
2158class SrgbGamma(Gamma):
2159  """Gamma correction using sRGB; see https://en.wikipedia.org/wiki/SRGB."""
2160
2161  def __init__(self) -> None:
2162    super().__init__(name='srgb')
2163
2164  def decode(self, array: _Array, /, dtype: _DTypeLike = np.float32) -> _Array:
2165    dtype = np.dtype(dtype)
2166    assert np.issubdtype(dtype, np.floating)
2167    if (decoded := _decode_using_table(self, array, dtype)) is not None:
2168      return decoded
2169
2170    x = _to_float_01(array, dtype)
2171    return _arr_where(typing.cast(_Array, x > 0.04045), ((x + 0.055) / 1.055) ** 2.4, x / 12.92)
2172
2173  def encode(self, array: _Array, /, dtype: _DTypeLike) -> _Array:
2174    x = _arr_clip(array, 0.0, 1.0)
2175    # Unfortunately, exponentiation is slow, and np.digitize() is even slower.
2176    x = _arr_where(
2177        typing.cast(_Array, x > 0.0031308), x ** (1.0 / 2.4) * 1.055 - (0.055 - 1e-17), x * 12.92
2178    )
2179    return _from_float(x, dtype)
2180
2181
2182_DICT_GAMMAS = {
2183    'identity': IdentityGamma(),
2184    'power2': PowerGamma(2.0),
2185    'power22': PowerGamma(2.2),
2186    'srgb': SrgbGamma(),
2187}
2188
2189GAMMAS = list(_DICT_GAMMAS)
2190r"""Shortcut names for some predefined gamma-correction schemes:
2191
2192| name | `Gamma` | Decoding function<br/> (linear space from stored value) | Encoding function<br/> (stored value from linear space) |
2193|---|---|:---:|:---:|
2194| `'identity'` | `IdentityGamma()` | $l = e$ | $e = l$ |
2195| `'power2'` | `PowerGamma`(2.0) | $l = e^{2.0}$ | $e = l^{1/2.0}$ |
2196| `'power22'` | `PowerGamma`(2.2) | $l = e^{2.2}$ | $e = l^{1/2.2}$ |
2197| `'srgb'` | `SrgbGamma()` | $l = \left(\left(e + 0.055\right) / 1.055\right)^{2.4}$ | $e = l^{1/2.4} * 1.055 - 0.055$ |
2198
2199See the source code for extensibility.
2200"""
2201
2202
2203def _get_gamma(gamma: str | Gamma, /) -> Gamma:
2204  """Return a `Gamma`, which can be specified as a name in `GAMMAS`."""
2205  return gamma if isinstance(gamma, Gamma) else _DICT_GAMMAS[gamma]
2206
2207
2208def _get_src_dst_gamma(
2209    gamma: str | Gamma | None,
2210    src_gamma: str | Gamma | None,
2211    dst_gamma: str | Gamma | None,
2212    src_dtype: _DType,
2213    dst_dtype: _DType,
2214) -> tuple[Gamma, Gamma]:
2215  if gamma is None and src_gamma is None and dst_gamma is None:
2216    src_uint = np.issubdtype(src_dtype, np.unsignedinteger)
2217    dst_uint = np.issubdtype(dst_dtype, np.unsignedinteger)
2218    if src_uint and dst_uint:
2219      # The default might ideally be 'srgb' but that conversion is costlier.
2220      gamma = 'power2'
2221    elif not src_uint and not dst_uint:
2222      gamma = 'identity'
2223    else:
2224      raise ValueError(f'Gamma must be specified because {src_dtype=} and {dst_dtype=}.')
2225  if gamma is not None:
2226    if src_gamma is not None:
2227      raise ValueError('Cannot specify both gamma and src_gamma.')
2228    if dst_gamma is not None:
2229      raise ValueError('Cannot specify both gamma and dst_gamma.')
2230    src_gamma = dst_gamma = gamma
2231  if src_gamma is None or dst_gamma is None:
2232    raise ValueError('If gamma is not set, both src_gamma and dst_gamma must be set.')
2233  src_gamma = _get_gamma(src_gamma)
2234  dst_gamma = _get_gamma(dst_gamma)
2235  return src_gamma, dst_gamma
2236
2237
2238def _create_resize_matrix(
2239    src_size: int,
2240    dst_size: int,
2241    src_gridtype: Gridtype,
2242    dst_gridtype: Gridtype,
2243    boundary: Boundary,
2244    filter: Filter,
2245    prefilter: Filter | None = None,
2246    scale: float = 1.0,
2247    translate: float = 0.0,
2248    dtype: _DTypeLike = np.float64,
2249    arraylib: str = 'numpy',
2250) -> tuple[Any, _AnyArray | None]:
2251  """Cached version of `_create_resize_matrix_uncached()`; do not modify the returned objects."""
2252  args = (
2253      src_size,
2254      dst_size,
2255      src_gridtype,
2256      dst_gridtype,
2257      boundary,
2258      filter,
2259      prefilter,
2260      scale,
2261      translate,
2262      np.dtype(dtype),
2263      arraylib,
2264  )
2265  try:
2266    hash(args)
2267  except TypeError:  # E.g., a user-defined Boundary or Filter holding an unhashable attribute.
2268    return _create_resize_matrix_uncached(*args)
2269  return _create_resize_matrix_cached(*args)
2270
2271
2272@functools.lru_cache(maxsize=64)
2273def _create_resize_matrix_cached(*args: Any) -> tuple[Any, _AnyArray | None]:
2274  return _create_resize_matrix_uncached(*args)
2275
2276
2277def _create_resize_matrix_uncached(
2278    src_size: int,
2279    dst_size: int,
2280    src_gridtype: Gridtype,
2281    dst_gridtype: Gridtype,
2282    boundary: Boundary,
2283    filter: Filter,
2284    prefilter: Filter | None = None,
2285    scale: float = 1.0,
2286    translate: float = 0.0,
2287    dtype: _DTypeLike = np.float64,
2288    arraylib: str = 'numpy',
2289) -> tuple[Any, _AnyArray | None]:
2290  """Compute affine weights for 1D resampling from `src_size` to `dst_size`.
2291
2292  Compute a sparse matrix in which each row expresses a destination sample value as a combination
2293  of source sample values depending on the boundary rule.  If the combination is non-affine,
2294  the remainder (returned as `cval_weight`) is the contribution of the special constant value
2295  (cval) defined outside the domain.
2296
2297  Args:
2298    src_size: The number of samples within the source 1D domain.
2299    dst_size: The number of samples within the destination 1D domain.
2300    src_gridtype: Placement of the samples in the source domain grid.
2301    dst_gridtype: Placement of the output samples in the destination domain grid.
2302    boundary: The reconstruction boundary rule.
2303    filter: The reconstruction kernel (used for upsampling/magnification).
2304    prefilter: The prefilter kernel (used for downsampling/minification).  If it is `None`,
2305      `filter` is used.
2306    scale: Scaling factor applied when mapping the source domain onto the destination domain.
2307    translate: Offset applied when mapping the scaled source domain onto the destination domain.
2308    dtype: Precision of computed resize matrix entries.
2309    arraylib: Representation of output.  Must be an element of `ARRAYLIBS`.
2310
2311  Returns:
2312    sparse_matrix: Matrix whose rows express output sample values as affine combinations of the
2313      source sample values.
2314    cval_weight: Optional vector expressing the additional contribution of the constant value
2315      (`cval`) to the combination in each row of `sparse_matrix`.  It equals one minus the sum of
2316      the weights in each matrix row.
2317  """
2318  if src_size < src_gridtype.min_size():
2319    raise ValueError(f'Source size {src_size} is too small for resize.')
2320  if dst_size < dst_gridtype.min_size():
2321    raise ValueError(f'Destination size {dst_size} is too small for resize.')
2322  prefilter = filter if prefilter is None else prefilter
2323  dtype = np.dtype(dtype)
2324  assert np.issubdtype(dtype, np.floating)
2325
2326  scaling = dst_gridtype.size_in_samples(dst_size) / src_gridtype.size_in_samples(src_size) * scale
2327  is_minification = scaling < 1.0
2328  filter = prefilter if is_minification else filter
2329  if filter.name == 'trapezoid':
2330    radius = 0.5 + 0.5 * min(scaling, 1.0 / scaling)
2331    filter = TrapezoidFilter(radius=radius)
2332  radius = filter.radius
2333  num_samples = int(np.ceil(radius * 2 / scaling) if is_minification else np.ceil(radius * 2))
2334
2335  dst_index = np.arange(dst_size, dtype=dtype)
2336  # Destination sample locations in unit domain [0, 1].
2337  dst_position = dst_gridtype.point_from_index(dst_index, dst_size)
2338
2339  src_position = (dst_position - translate) / scale
2340  src_position = boundary.preprocess_coordinates(src_position)
2341
2342  # Sample positions mapped back to source unit domain [0, 1].
2343  src_float_index = src_gridtype.index_from_point(src_position, src_size)
2344  src_first_index = (
2345      np.floor(src_float_index + (0.5 if num_samples % 2 == 1 else 0.0)).astype(np.int32)
2346      - (num_samples - 1) // 2
2347  )
2348
2349  sample_index = np.arange(num_samples, dtype=np.int32)
2350  src_index = src_first_index[:, None] + sample_index  # (dst_size, num_samples)
2351
2352  def get_weight_matrix() -> _NDArray:
2353    if filter.name == 'impulse':
2354      return np.ones(src_index.shape, dtype)
2355    if is_minification:
2356      x = (src_float_index[:, None] - src_index.astype(dtype)) * scaling
2357      return filter(x) * scaling
2358    # Either same size or magnification.
2359    x = src_float_index[:, None] - src_index.astype(dtype)
2360    return filter(x)
2361
2362  weight: _NDArray = get_weight_matrix().astype(dtype, copy=False)
2363
2364  if filter.name != 'narrowbox' and (is_minification or not filter.partition_of_unity):
2365    weight = weight / weight.sum(axis=-1)[..., None]
2366
2367  src_index, weight = boundary.fold(src_index, weight, src_position, src_size, src_gridtype)
2368  shape = dst_size, src_size
2369
2370  def prepare_sparse_resize_matrix() -> tuple[_NDArray, _NDArray, _NDArray]:
2371    linearized = (src_index + np.indices(src_index.shape)[0] * src_size).ravel()
2372    values = weight.ravel()
2373    # Remove the zero weights.
2374    nonzero = values != 0.0
2375    linearized, values = linearized[nonzero], values[nonzero]
2376    # Sort and merge the duplicate indices.
2377    unique, unique_inverse = np.unique(linearized, return_inverse=True)
2378    data2 = np.ones(len(linearized), np.float32)
2379    row_ind2 = unique_inverse
2380    col_ind2 = np.arange(len(linearized))
2381    shape2 = len(unique), len(linearized)
2382    csr = scipy.sparse.csr_matrix((data2, (row_ind2, col_ind2)), shape=shape2)
2383    data = csr * values  # Merged values.
2384    row_ind, col_ind = unique // src_size, unique % src_size  # Merged indices.
2385    return data, row_ind, col_ind
2386
2387  data, row_ind, col_ind = prepare_sparse_resize_matrix()
2388  resize_matrix = _make_sparse_matrix(data, row_ind, col_ind, shape, arraylib)
2389
2390  uses_cval = boundary.uses_cval or filter.name == 'narrowbox'
2391  cval_weight = _make_array(1.0 - weight.sum(axis=-1), arraylib) if uses_cval else None
2392
2393  return resize_matrix, cval_weight
2394
2395
2396def _apply_digital_filter_1d(
2397    array: _Array,
2398    gridtype: Gridtype,
2399    boundary: Boundary,
2400    cval: _ArrayLike,
2401    filter: Filter,
2402    /,
2403    *,
2404    axis: int = 0,
2405) -> _Array:
2406  """Apply inverse convolution to the specified dimension of the array.
2407
2408  Find the array coefficients such that convolution with the (continuous) filter (given
2409  gridtype and boundary) interpolates the original array values.
2410  """
2411  assert filter.requires_digital_filter
2412  arraylib = _arr_arraylib(array)
2413
2414  if arraylib == 'torch':
2415    import torch.autograd
2416
2417    class InverseConvolution(torch.autograd.Function):  # type: ignore[misc] # pylint: disable=abstract-method
2418      """Differentiable wrapper for _apply_digital_filter_1d."""
2419
2420      @staticmethod
2421      # pylint: disable-next=arguments-differ
2422      def forward(ctx: Any, *args: _TorchTensor, **kwargs: Any) -> _TorchTensor:
2423        del ctx
2424        assert not kwargs
2425        (x,) = args
2426        a = _apply_digital_filter_1d_numpy(
2427            x.detach().numpy(), gridtype, boundary, cval, filter, axis, False
2428        )
2429        return torch.as_tensor(a)
2430
2431      @staticmethod
2432      def backward(ctx: Any, *grad_outputs: _TorchTensor) -> _TorchTensor:
2433        del ctx
2434        (grad_output,) = grad_outputs
2435        a = _apply_digital_filter_1d_numpy(
2436            grad_output.detach().numpy(), gridtype, boundary, cval, filter, axis, True
2437        )
2438        return torch.as_tensor(a)
2439
2440    return InverseConvolution.apply(array)
2441
2442  if arraylib == 'jax':
2443    import jax
2444    import jax.numpy as jnp
2445    # It seems rather difficult to implement this digital filter (inverse convolution) in Jax.
2446    # https://docs.jax.dev/en/latest/jax.scipy.html sadly omits scipy.signal.filtfilt().
2447    # To include a (non-traceable) numpy function in Jax requires jax.experimental.host_callback
2448    # and/or defining a new jax.core.Primitive (which allows differentiability).  See
2449    # https://github.com/jax-ml/jax/issues/1142#issuecomment-544286585
2450    # https://github.com/jax-ml/jax/blob/main/docs/notebooks/How_JAX_primitives_work.ipynb  :-(
2451    # https://github.com/jax-ml/jax/issues/5934
2452
2453    @jax.custom_gradient  # type: ignore[untyped-decorator]
2454    def jax_inverse_convolution(x: _JaxArray) -> Any:
2455      # This function is not jax-traceable due to the conversion to numpy, so jit and grad fail.
2456      x_py = np.asarray(x)
2457      a = _apply_digital_filter_1d_numpy(x_py, gridtype, boundary, cval, filter, axis, False)
2458      y = jnp.asarray(a)
2459
2460      def grad(grad_output: _JaxArray) -> _JaxArray:
2461        grad_output_py = np.asarray(grad_output)
2462        a = _apply_digital_filter_1d_numpy(
2463            grad_output_py, gridtype, boundary, cval, filter, axis, True
2464        )
2465        return jnp.asarray(a)
2466
2467      return y, grad
2468
2469    return typing.cast(Any, jax_inverse_convolution(array))
2470
2471  assert arraylib == 'numpy'
2472  array_np: Any = array
2473  result: Any = _apply_digital_filter_1d_numpy(
2474      array_np, gridtype, boundary, cval, filter, axis, False
2475  )
2476  return result
2477
2478
2479def _apply_digital_filter_1d_numpy(
2480    array: _NDArray,
2481    gridtype: Gridtype,
2482    boundary: Boundary,
2483    cval: _ArrayLike,
2484    filter: Filter,
2485    axis: int,
2486    compute_backward: bool,
2487    /,
2488) -> _NDArray:
2489  """Version of `_apply_digital_filter_1d` specialized to numpy array."""
2490  assert np.issubdtype(array.dtype, np.inexact)
2491  cval = np.asarray(cval).astype(array.dtype, copy=False)
2492
2493  # Use fast spline_filter1d() if we have a compatible gridtype, boundary, and filter.
2494  # (Its mode='wrap' does not match the 'wrap' boundary on a 'primal' grid.)
2495  mode = {
2496      ('reflect', 'dual'): 'reflect',
2497      ('reflect', 'primal'): 'mirror',
2498      ('wrap', 'dual'): 'grid-wrap',
2499  }.get((boundary.name, gridtype.name))
2500  filter_is_compatible = isinstance(filter, CardinalBsplineFilter)
2501  # For a 'primal' grid, the matrix is not symmetric, so compute_backward requires its transpose.
2502  is_symmetric = gridtype.name == 'dual'
2503  use_spline_filter1d = filter_is_compatible and mode and (is_symmetric or not compute_backward)
2504  if use_spline_filter1d:
2505    assert isinstance(filter, CardinalBsplineFilter)  # Help mypy.
2506    assert filter.degree >= 2
2507    # For a 'dual' grid, compute_backward=True is the same: the matrix is symmetric and cval is
2508    # unused.
2509    return scipy.ndimage.spline_filter1d(
2510        array, axis=axis, order=filter.degree, mode=mode, output=array.dtype
2511    )
2512
2513  array_dim = np.moveaxis(array, axis, 0)
2514  size = array_dim.shape[0]
2515  system = _digital_filter_system(gridtype, boundary, filter, size, array.dtype, compute_backward)
2516
2517  if system.cval_weight is not None:
2518    if array_dim.ndim == 2:  # Handle the case that we have array_flat.
2519      cval = np.tile(cval.reshape(-1), array_dim[0].size // cval.size)
2520    array_dim = array_dim - system.cval_weight.reshape(-1, *(1,) * array_dim[0].ndim) * cval
2521
2522  array_flat = array_dim.reshape(array_dim.shape[0], -1)
2523
2524  if system.banded is not None:
2525    l, u, ab = system.banded
2526    options = dict(check_finite=False, overwrite_ab=False, overwrite_b=False)  # `ab` is shared.
2527    if system.is_symmetric:
2528      array_flat = scipy.linalg.solveh_banded(ab, array_flat, **options)
2529    else:
2530      array_flat = scipy.linalg.solve_banded((l, u), ab, array_flat, **options)
2531  else:
2532    array_flat = system.lu.solve(array_flat)
2533
2534  array_dim = np.asarray(array_flat).reshape(array_dim.shape)
2535  return np.moveaxis(array_dim, 0, axis)
2536
2537
2538@dataclasses.dataclass(frozen=True)
2539class _DigitalFilterSystem:
2540  """The linear system of a digital filter along one grid dimension, shared by all calls with the
2541  same gridtype, boundary, filter, size, dtype, and direction; its arrays must not be modified."""
2542
2543  cval_weight: _NDArray | None
2544  """The weight of `cval` in each row, or None if the boundary does not reference `cval`."""
2545
2546  banded: tuple[int, int, _NDArray] | None
2547  """The lower bandwidth, upper bandwidth, and band storage `ab` of a banded matrix (in the layout
2548  of `scipy.linalg.solve_banded`, or of `scipy.linalg.solveh_banded` if `is_symmetric`), else
2549  None."""
2550
2551  is_symmetric: bool
2552  """Whether the banded matrix is symmetric, so that `solveh_banded` applies."""
2553
2554  lu: Any
2555  """The `scipy.sparse.linalg.SuperLU` factorization of a non-banded matrix (e.g. for 'wrap'), else
2556  None."""
2557
2558
2559def _digital_filter_system(
2560    gridtype: Gridtype,
2561    boundary: Boundary,
2562    filter: Filter,
2563    size: int,
2564    dtype: _DTypeLike,
2565    compute_backward: bool,
2566    /,
2567) -> _DigitalFilterSystem:
2568  """Return the (cached) linear system that `_apply_digital_filter_1d_numpy()` solves."""
2569  args = (gridtype, boundary, filter, size, np.dtype(dtype), compute_backward)
2570  try:
2571    hash(args)
2572  except TypeError:  # E.g., a user-defined Boundary or Filter holding an unhashable attribute.
2573    return _digital_filter_system_uncached(*args)
2574  return _digital_filter_system_cached(*args)
2575
2576
2577@functools.lru_cache(maxsize=64)
2578def _digital_filter_system_cached(*args: Any) -> _DigitalFilterSystem:
2579  return _digital_filter_system_uncached(*args)
2580
2581
2582def _digital_filter_system_uncached(
2583    gridtype: Gridtype,
2584    boundary: Boundary,
2585    filter: Filter,
2586    size: int,
2587    dtype: _DType,
2588    compute_backward: bool,
2589    /,
2590) -> _DigitalFilterSystem:
2591  l = original_l = math.ceil(filter.radius) - 1
2592  x = np.arange(-l, l + 1, dtype=np.empty(0, dtype).real.dtype)
2593  values = filter(x)
2594  src_index = np.arange(size)[:, None] + np.arange(len(values)) - l
2595  weight: _NDArray = np.full((size, len(values)), values)
2596  src_position = np.broadcast_to(0.5, len(values))
2597  src_index, weight = boundary.fold(src_index, weight, src_position, size, gridtype)
2598  if gridtype.name == 'primal' and boundary.name == 'wrap':
2599    # Overwrite redundant last row to preserve unreferenced last sample and thereby make the
2600    # matrix non-singular.
2601    src_index[-1] = [size - 1] + [0] * (src_index.shape[1] - 1)
2602    weight[-1] = [1.0] + [0.0] * (weight.shape[1] - 1)
2603  bandwidth = abs(src_index - np.arange(size)[:, None]).max()
2604  is_banded = bandwidth <= l + 1  # Add one for quadratic boundary and l == 1.
2605  # Currently, matrix is always banded unless boundary.name == 'wrap'.
2606
2607  data = weight.reshape(-1).astype(dtype, copy=False)
2608  row_ind = np.arange(size).repeat(src_index.shape[1])
2609  col_ind = src_index.reshape(-1)
2610  matrix = scipy.sparse.csr_matrix((data, (row_ind, col_ind)), shape=(size, size))
2611  if compute_backward:
2612    matrix = matrix.transpose()
2613
2614  cval_weight = None
2615  if boundary.uses_cval and not compute_backward:
2616    cval_weight = 1.0 - np.asarray(matrix.sum(axis=-1))[:, 0]
2617
2618  if is_banded:
2619    matrix = matrix.todia()
2620    assert np.all(np.diff(matrix.offsets) == 1)  # Consecutive, often [-l, l].
2621    l, u = -matrix.offsets[0], matrix.offsets[-1]
2622    assert l <= original_l + 1 and u <= original_l + 1, (l, u, original_l)
2623    is_symmetric = _is_symmetric(matrix)
2624    ab = matrix.data[l:][::-1] if is_symmetric else matrix.data[::-1]
2625    return _DigitalFilterSystem(cval_weight, (l, u, ab), is_symmetric, None)
2626
2627  lu = scipy.sparse.linalg.splu(matrix.tocsc(), permc_spec='NATURAL')
2628  assert all(s <= size * len(values) for s in (lu.L.nnz, lu.U.nnz))  # Sparse.
2629  return _DigitalFilterSystem(cval_weight, None, False, lu)
2630
2631
2632def resize(
2633    array: _Array,
2634    /,
2635    shape: Iterable[int],
2636    *,
2637    gridtype: str | Gridtype | None = None,
2638    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2639    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2640    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
2641    cval: _ArrayLike = 0.0,
2642    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
2643    prefilter: str | Filter | Iterable[str | Filter] | None = None,
2644    gamma: str | Gamma | None = None,
2645    src_gamma: str | Gamma | None = None,
2646    dst_gamma: str | Gamma | None = None,
2647    scale: float | Iterable[float] = 1.0,
2648    translate: float | Iterable[float] = 0.0,
2649    precision: _DTypeLike | None = None,
2650    dtype: _DTypeLike | None = None,
2651    dim_order: Iterable[int] | None = None,
2652    num_threads: int | Literal['auto'] = 'auto',
2653) -> _Array:
2654  """Resample `array` (a grid of sample values) onto a grid with resolution `shape`.
2655
2656  The source `array` is any object recognized by `ARRAYLIBS`.  It is interpreted as a grid
2657  with `len(shape)` domain coordinate dimensions, where each grid sample value has shape
2658  `array.shape[len(shape):]`.
2659
2660  Some examples:
2661
2662  - A grayscale image has `array.shape = height, width` and resizing it with `len(shape) == 2`
2663    produces a new image of scalar values.
2664  - An RGB image has `array.shape = height, width, 3` and resizing it with `len(shape) == 2`
2665    produces a new image of RGB values.
2666  - A 3D grid of 3x3 Jacobians has `array.shape = Z, Y, X, 3, 3` and resizing it with
2667    `len(shape) == 3` produces a new 3D grid of Jacobians.
2668
2669  This function also allows scaling and translation from the source domain to the output domain
2670  through the parameters `scale` and `translate`.  For more general transforms, see `resample`.
2671
2672  Args:
2673    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
2674      The array must have numeric type.  Its first `len(shape)` dimensions are the domain
2675      coordinate dimensions.  Each grid dimension must be at least 1 for a `'dual'` grid or
2676      at least 2 for a `'primal'` grid.
2677    shape: The number of grid samples in each coordinate dimension of the output array.  The source
2678      `array` must have at least as many dimensions as `len(shape)`.
2679    gridtype: Placement of samples on all dimensions of both the source and output domain grids,
2680      specified as either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`
2681      if `gridtype`, `src_gridtype`, and `dst_gridtype` are all kept `None`.
2682    src_gridtype: Placement of the samples in the source domain grid for each dimension.
2683      Parameters `gridtype` and `src_gridtype` cannot both be set.
2684    dst_gridtype: Placement of the samples in the output domain grid for each dimension.
2685      Parameters `gridtype` and `dst_gridtype` cannot both be set.
2686    boundary: The reconstruction boundary rule for each dimension in `shape`, specified as either
2687      a name in `BOUNDARIES` or a `Boundary` instance.  The special value `'auto'` uses `'reflect'`
2688      for upsampling and `'clamp'` for downsampling.
2689    cval: Constant value used beyond the samples by some boundary rules.  It must be broadcastable
2690      onto `array.shape[len(shape):]`.  It is subject to `src_gamma`.
2691    filter: The reconstruction kernel for each dimension in `shape`, specified as either a filter
2692      name in `FILTERS` or a `Filter` instance.  It is used during upsampling (i.e., magnification).
2693    prefilter: The prefilter kernel for each dimension in `shape`, specified as either a filter
2694      name in `FILTERS` or a `Filter` instance.  It is used during downsampling
2695      (i.e., minification).  If `None`, it inherits the value of `filter`.  The default
2696      `'lanczos3'` is good for natural images.  For vector graphics images, `'trapezoid'` is better
2697      because it avoids ringing artifacts.
2698    gamma: Component transfer functions (e.g., gamma correction) applied when reading samples from
2699      `array` and when creating output grid samples.  It is specified as either a name in `GAMMAS`
2700      or a `Gamma` instance.  If both `array.dtype` and `dtype` are `uint`, the default is
2701      `'power2'`.  If both are non-`uint`, the default is `'identity'`.  Otherwise, `gamma` or
2702      `src_gamma`/`dst_gamma` must be set.  Gamma correction assumes that float values are in the
2703      range [0.0, 1.0].
2704    src_gamma: Component transfer function used to "decode" `array` samples.
2705      Parameters `gamma` and `src_gamma` cannot both be set.
2706    dst_gamma: Component transfer function used to "encode" the output samples.
2707      Parameters `gamma` and `dst_gamma` cannot both be set.
2708    scale: Scaling factor applied to each dimension of the source domain when it is mapped onto
2709      the destination domain.
2710    translate: Offset applied to each dimension of the scaled source domain when it is mapped onto
2711      the destination domain.
2712    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
2713      on `array.dtype` and `dtype`.
2714    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
2715      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
2716      to the uint range.
2717    dim_order: Override the automatically selected order in which the grid dimensions are resized.
2718      Must contain a permutation of `range(len(shape))`.
2719    num_threads: Used to determine multithread parallelism if `array` is from `numpy`.  If set to
2720      `'auto'`, it is selected automatically.  Otherwise, it must be a positive integer.
2721
2722  Returns:
2723    An array of the same class as the source `array`, with shape `shape + array.shape[len(shape):]`
2724      and data type `dtype`.
2725
2726  **Example of image upsampling:**
2727
2728  >>> array = np.random.default_rng(1).random((4, 6, 3))  # 4x6 RGB image.
2729  >>> upsampled = resize(array, (128, 192))  # To 128x192 resolution.
2730
2731  <center>
2732  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_array_upsampled.png"/>
2733  </center>
2734
2735  **Example of image downsampling:**
2736
2737  >>> yx = (np.moveaxis(np.indices((96, 192)), 0, -1) + (0.5, 0.5)) / 96
2738  >>> radius = np.linalg.norm(yx - (0.75, 0.5), axis=-1)
2739  >>> array = np.cos((radius + 0.1) ** 0.5 * 70.0) * 0.5 + 0.5
2740  >>> downsampled = resize(array, (24, 48))
2741
2742  <center>
2743  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_array_downsampled2.png"/>
2744  </center>
2745
2746  **Unit test:**
2747
2748  >>> result = resize(np.array([1.0, 4.0, 5.0]), shape=(4,))
2749  >>> assert np.allclose(result, [0.74240461, 2.88088827, 4.68647155, 5.02641199])
2750  """
2751  arraylib = _arr_arraylib(array)
2752  array_dtype = _arr_dtype(array)
2753  if not np.issubdtype(array_dtype, np.number):
2754    raise ValueError(f'Type {array_dtype} is not numeric.')
2755  shape2 = tuple(shape)
2756  array_ndim = len(_arr_shape(array))
2757  if not 0 < len(shape2) <= array_ndim:
2758    raise ValueError(f'Shape {_arr_shape(array)} cannot be resized to {shape2}.')
2759  src_shape = _arr_shape(array)[: len(shape2)]
2760  src_gridtype2, dst_gridtype2 = _get_gridtypes(
2761      gridtype, src_gridtype, dst_gridtype, len(shape2), len(shape2)
2762  )
2763  boundary2 = np.broadcast_to(np.array(boundary), len(shape2))
2764  cval = np.broadcast_to(cval, _arr_shape(array)[len(shape2) :])
2765  prefilter = filter if prefilter is None else prefilter
2766  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), len(shape2))]
2767  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), len(shape2))]
2768  dtype = array_dtype if dtype is None else np.dtype(dtype)
2769  src_gamma2, dst_gamma2 = _get_src_dst_gamma(gamma, src_gamma, dst_gamma, array_dtype, dtype)
2770  scale2 = np.broadcast_to(np.array(scale), len(shape2))
2771  translate2 = np.broadcast_to(np.array(translate), len(shape2))
2772  del shape, src_gridtype, dst_gridtype, boundary, filter, prefilter
2773  del src_gamma, dst_gamma, scale, translate
2774  precision = _get_precision(precision, [array_dtype, dtype], [])
2775  weight_precision = _real_precision(precision)
2776
2777  is_noop = (
2778      all(src == dst for src, dst in zip(src_shape, shape2, strict=True))
2779      and all(gt1 == gt2 for gt1, gt2 in zip(src_gridtype2, dst_gridtype2, strict=True))
2780      and all(f.interpolating for f in filter2)
2781      and np.all(scale2 == 1.0)
2782      and np.all(translate2 == 0.0)
2783      and src_gamma2 == dst_gamma2
2784      and dtype == array_dtype
2785  )
2786  if is_noop:
2787    return array
2788
2789  if dim_order is None:
2790    dim_order = _arr_best_dims_order_for_resize(array, shape2)
2791  else:
2792    dim_order = tuple(dim_order)
2793    if sorted(dim_order) != list(range(len(shape2))):
2794      raise ValueError(f'{dim_order} is not a permutation of {list(range(len(shape2)))}.')
2795
2796  array = src_gamma2.decode(array, precision)
2797  cval = _arr_numpy(src_gamma2.decode(cval, precision))
2798
2799  can_use_fast_box_downsampling = (
2800      _USING_NUMBA
2801      and arraylib == 'numpy'
2802      and len(shape2) == 2
2803      and array_ndim in (2, 3)
2804      and all(src > dst for src, dst in zip(src_shape, shape2, strict=True))
2805      and all(src % dst == 0 for src, dst in zip(src_shape, shape2, strict=True))
2806      and all(gridtype.name == 'dual' for gridtype in src_gridtype2)
2807      and all(gridtype.name == 'dual' for gridtype in dst_gridtype2)
2808      and all(f.name in ('box', 'trapezoid') for f in prefilter2)
2809      and np.all(scale2 == 1.0)
2810      and np.all(translate2 == 0.0)
2811  )
2812  if can_use_fast_box_downsampling:
2813    # Casting to _NDArray is needed by pyrefly but is redundant for mypy, so cast to Any.
2814    array2 = _downsample_in_2d_using_box_filter(typing.cast(Any, array), shape2)
2815    return typing.cast(_Array, dst_gamma2.encode(array2, dtype))
2816
2817  # Multidimensional resize can be expressed using einsum() with multiple per-dim resize matrices,
2818  # e.g., as in jax.image.resize().  A benefit is to seek the optimal order of multiplications.
2819  # However, efficiency often requires sparse resize matrices, which are unsupported in einsum().
2820  # https://github.com/tensor-compiler/taco: C++ library that computes tensor algebra expressions
2821  # on sparse and dense tensors; however it does not interoperate with torch or jax.
2822
2823  for dim in dim_order:
2824    skip_resize_on_this_dim = (
2825        shape2[dim] == _arr_shape(array)[dim]
2826        and scale2[dim] == 1.0
2827        and translate2[dim] == 0.0
2828        and filter2[dim].interpolating
2829    )
2830    if skip_resize_on_this_dim:
2831      continue
2832
2833    src_in_samples = src_gridtype2[dim].size_in_samples(_arr_shape(array)[dim])
2834    dst_in_samples = dst_gridtype2[dim].size_in_samples(shape2[dim])
2835    is_minification = dst_in_samples / src_in_samples * scale2[dim] < 1.0
2836    boundary_dim = boundary2[dim]
2837    if boundary_dim == 'auto':
2838      boundary_dim = 'clamp' if is_minification else 'reflect'
2839    boundary_dim = _get_boundary(boundary_dim)
2840    resize_matrix, cval_weight = _create_resize_matrix(
2841        _arr_shape(array)[dim],
2842        shape2[dim],
2843        src_gridtype=src_gridtype2[dim],
2844        dst_gridtype=dst_gridtype2[dim],
2845        boundary=boundary_dim,
2846        filter=filter2[dim],
2847        prefilter=prefilter2[dim],
2848        scale=scale2[dim],
2849        translate=translate2[dim],
2850        dtype=weight_precision,
2851        arraylib=arraylib,
2852    )
2853
2854    array_dim: _Array = _arr_moveaxis(array, dim, 0)
2855    array_flat: Any = _arr_reshape(array_dim, (_arr_shape(array_dim)[0], -1))
2856    array_flat = _arr_possibly_make_contiguous(array_flat)
2857    if not is_minification and filter2[dim].requires_digital_filter:
2858      array_flat = _apply_digital_filter_1d(
2859          array_flat, src_gridtype2[dim], boundary_dim, cval, filter2[dim]
2860      )
2861
2862    array_flat = _arr_matmul_sparse_dense(resize_matrix, array_flat, num_threads=num_threads)
2863    if cval_weight is not None:
2864      cval_flat = np.broadcast_to(cval, _arr_shape(array_dim)[1:]).reshape(-1)
2865      cval_weight2: Any = cval_weight
2866      if np.issubdtype(array_dtype, np.complexfloating):
2867        cval_weight2 = _arr_astype(cval_weight2, array_dtype)  # (Only necessary for 'tensorflow'.)
2868      array_flat += cval_weight2[:, None] * cval_flat
2869
2870    if is_minification and prefilter2[dim].requires_digital_filter:
2871      array_flat = _apply_digital_filter_1d(
2872          array_flat, dst_gridtype2[dim], boundary_dim, cval, prefilter2[dim]
2873      )
2874    array_dim = typing.cast(
2875        _Array, _arr_reshape(array_flat, (_arr_shape(array_flat)[0], *_arr_shape(array_dim)[1:]))
2876    )
2877    array = _arr_moveaxis(array_dim, 0, dim)
2878
2879  array = dst_gamma2.encode(array, dtype)
2880  return array
2881
2882
2883_original_resize = resize
2884
2885
2886def resize_in_arraylib(array: _NDArray, /, *args: Any, arraylib: str, **kwargs: Any) -> _NDArray:
2887  """Evaluate the `resize()` operation using the specified array library from `ARRAYLIBS`."""
2888  _check_eq(_arr_arraylib(array), 'numpy')
2889  return _arr_numpy(_original_resize(_make_array(array, arraylib), *args, **kwargs))
2890
2891
2892def resize_in_numpy(array: _NDArray, /, *args: Any, **kwargs: Any) -> _NDArray:
2893  """Evaluate the `resize()` operation using the `numpy` library."""
2894  return resize_in_arraylib(array, *args, arraylib='numpy', **kwargs)
2895
2896
2897def resize_in_torch(array: _NDArray, /, *args: Any, **kwargs: Any) -> _NDArray:
2898  """Evaluate the `resize()` operation using the `torch` library."""
2899  return resize_in_arraylib(array, *args, arraylib='torch', **kwargs)
2900
2901
2902def resize_in_jax(array: _NDArray, /, *args: Any, **kwargs: Any) -> _NDArray:
2903  """Evaluate the `resize()` operation using the `jax` library."""
2904  return resize_in_arraylib(array, *args, arraylib='jax', **kwargs)
2905
2906
2907def _resize_possibly_in_arraylib(
2908    array: _AnyArray, /, *args: Any, arraylib: str, **kwargs: Any
2909) -> _AnyArray:
2910  """If `array` is from numpy, evaluate `resize()` using the array library from `ARRAYLIBS`."""
2911  if _arr_arraylib(array) == 'numpy':
2912    return _arr_numpy(
2913        _original_resize(_make_array(typing.cast(_NDArray, array), arraylib), *args, **kwargs)
2914    )
2915  return _original_resize(typing.cast(Any, array), *args, **kwargs)
2916
2917
2918@functools.cache
2919def _create_jaxjit_resize() -> Callable[..., Any]:
2920  """Lazily invoke `jax.jit` on `resize`."""
2921  import jax
2922
2923  jitted: Any = jax.jit(
2924      _original_resize,
2925      static_argnums=(1,),
2926      static_argnames=list(_original_resize.__kwdefaults__ or []),
2927  )
2928  return jitted
2929
2930
2931def jaxjit_resize(array: _Array, /, *args: Any, **kwargs: Any) -> _Array:
2932  """Compute `resize` but with resize function jitted using Jax."""
2933  return _create_jaxjit_resize()(array, *args, **kwargs)  # pylint: disable=not-callable
2934
2935
2936def uniform_resize(
2937    array: _Array,
2938    /,
2939    shape: Iterable[int],
2940    *,
2941    object_fit: Literal['contain', 'cover'] = 'contain',
2942    gridtype: str | Gridtype | None = None,
2943    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2944    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2945    boundary: str | Boundary | Iterable[str | Boundary] = 'natural',  # Instead of 'auto' default.
2946    scale: float | Iterable[float] = 1.0,
2947    translate: float | Iterable[float] = 0.0,
2948    **kwargs: Any,
2949) -> _Array:
2950  """Resample `array` onto a grid with resolution `shape` but with uniform scaling.
2951
2952  Calls function `resize` with `scale` and `translate` set such that the aspect ratio of `array`
2953  is preserved.  The effect is similar to CSS `object-fit: contain` (or `object-fit: cover` if
2954  `object_fit='cover'`).
2955  The parameter `boundary` (whose default is changed to `'natural'`) determines the values assigned
2956  outside the source domain.
2957
2958  Args:
2959    array: Regular grid of source sample values.
2960    shape: The number of grid samples in each coordinate dimension of the output array.  The source
2961      `array` must have at least as many dimensions as `len(shape)`.
2962    object_fit: Like CSS `object-fit`.  If `'contain'`, `array` is resized uniformly to fit within
2963      `shape`.  If `'cover'`, `array` is resized to fully cover `shape`.
2964    gridtype: Placement of samples on all dimensions of both the source and output domain grids.
2965    src_gridtype: Placement of the samples in the source domain grid for each dimension.
2966    dst_gridtype: Placement of the samples in the output domain grid for each dimension.
2967    boundary: The reconstruction boundary rule for each dimension in `shape`, specified as either
2968      a name in `BOUNDARIES` or a `Boundary` instance.  The default is `'natural'`, which assigns
2969      `cval` to output points that map outside the source unit domain.
2970    scale: Parameter may not be specified.
2971    translate: Parameter may not be specified.
2972    **kwargs: Additional parameters for `resize` function (including `cval`).
2973
2974  Returns:
2975    An array with shape `shape + array.shape[len(shape):]`.
2976
2977  >>> uniform_resize(np.ones((2, 2)), (2, 4), filter='trapezoid')
2978  array([[0., 1., 1., 0.],
2979         [0., 1., 1., 0.]])
2980
2981  >>> uniform_resize(np.ones((4, 8)), (2, 7), filter='trapezoid')
2982  array([[0. , 0.5, 1. , 1. , 1. , 0.5, 0. ],
2983         [0. , 0.5, 1. , 1. , 1. , 0.5, 0. ]])
2984
2985  >>> a = np.arange(6.0).reshape(2, 3)
2986  >>> uniform_resize(a, (2, 2), filter='trapezoid', object_fit='cover')
2987  array([[0.5, 1.5],
2988         [3.5, 4.5]])
2989  """
2990  if scale != 1.0 or translate != 0.0:
2991    raise ValueError('`uniform_resize()` does not accept `scale` or `translate` parameters.')
2992  shape = tuple(shape)
2993  array_ndim = len(_arr_shape(array))
2994  if not 0 < len(shape) <= array_ndim:
2995    raise ValueError(f'Shape {_arr_shape(array)} cannot be resized to {shape}.')
2996  src_gridtype2, dst_gridtype2 = _get_gridtypes(
2997      gridtype, src_gridtype, dst_gridtype, len(shape), len(shape)
2998  )
2999  raw_scales = [
3000      dst_gridtype2[dim].size_in_samples(shape[dim])
3001      / src_gridtype2[dim].size_in_samples(_arr_shape(array)[dim])
3002      for dim in range(len(shape))
3003  ]
3004  scale0 = {'contain': min(raw_scales), 'cover': max(raw_scales)}[object_fit]
3005  scale2 = scale0 / np.array(raw_scales)
3006  translate = (1.0 - scale2) / 2
3007  return resize(
3008      array,
3009      shape,
3010      src_gridtype=src_gridtype2,
3011      dst_gridtype=dst_gridtype2,
3012      boundary=boundary,
3013      scale=scale2,
3014      translate=translate,
3015      **kwargs,
3016  )
3017
3018
3019_MAX_BLOCK_SIZE_RECURSING = -999  # Special value to indicate re-invocation on partitioned blocks.
3020
3021
3022def compute_coefficients(
3023    array: _Array,
3024    /,
3025    grid_ndim: int,
3026    *,
3027    gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual',
3028    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
3029    cval: _ArrayLike = 0.0,
3030    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3031    gamma: str | Gamma | None = None,
3032    src_gamma: str | Gamma | None = None,
3033    precision: _DTypeLike | None = None,
3034) -> _Array:
3035  """Return the reconstruction coefficients of `array`, for repeated calls to `resample`.
3036
3037  Before each evaluation, `resample` decodes the samples of `array` through the source gamma and,
3038  for a kernel that requires it (e.g., `'cardinal3'` or `'omoms5'`), transforms them by a digital
3039  filter.  This function performs just those steps, so that `resample(coefficients, coords,
3040  from_coefficients=True, ...)` can skip them when the same `array` is resampled many times (as
3041  in a warp sequence), given the same `gridtype`, `boundary`, `cval`, `filter`, and gamma settings.
3042
3043  Args:
3044    array: Grid of samples whose first `grid_ndim` dimensions define the grid.
3045    grid_ndim: Number of grid dimensions (`coords.shape[-1]` in the later calls to `resample`).
3046    gridtype: Placement of samples on the grid, as in `resample`.
3047    boundary: Boundary rule for each grid dimension, as in `resample`.
3048    cval: Constant value used beyond the input domain, as in `resample`.
3049    filter: Reconstruction kernel for each grid dimension, as in `resample`.
3050    gamma: Component transfer function applied to both the source and destination samples, as in
3051      `resample`.
3052    src_gamma: Component transfer function used to "decode" `array` samples, as in `resample`.
3053    precision: Inexact precision of the coefficients.  If `None`, it is determined based on
3054      the `array` dtype as in `resample`.
3055
3056  Returns:
3057    An array of floating-point coefficients with the shape of `array` and the same array library
3058    type as the source array.
3059  """
3060  array_ndim = len(_arr_shape(array))
3061  if not 0 < grid_ndim <= array_ndim:
3062    raise ValueError(f'{grid_ndim=} must lie in [1, array.ndim={array_ndim}].')
3063  gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(gridtype), grid_ndim)]
3064  boundary2 = np.broadcast_to(np.array(boundary), grid_ndim).tolist()
3065  boundary2 = [_get_boundary('reflect' if b == 'auto' else b) for b in boundary2]
3066  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), grid_ndim)]
3067  src_dtype = _arr_dtype(array)
3068  src_gamma2, _ = _get_src_dst_gamma(gamma, src_gamma, src_gamma, src_dtype, src_dtype)
3069  precision = _get_precision(precision, [src_dtype], [])
3070  cval = np.broadcast_to(cval, _arr_shape(array)[grid_ndim:])
3071  array = src_gamma2.decode(array, precision)
3072  for dim in range(grid_ndim):
3073    if filter2[dim].requires_digital_filter:
3074      array = _apply_digital_filter_1d(
3075          array, gridtype2[dim], boundary2[dim], cval, filter2[dim], axis=dim
3076      )
3077  return array
3078
3079
3080def resample(
3081    array: _Array,
3082    /,
3083    coords: _ArrayLike,
3084    *,
3085    gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual',
3086    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
3087    cval: _ArrayLike = 0.0,
3088    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3089    prefilter: str | Filter | Iterable[str | Filter] | None = None,
3090    gamma: str | Gamma | None = None,
3091    src_gamma: str | Gamma | None = None,
3092    dst_gamma: str | Gamma | None = None,
3093    jacobian: _ArrayLike | None = None,
3094    precision: _DTypeLike | None = None,
3095    dtype: _DTypeLike | None = None,
3096    from_coefficients: bool = False,
3097    max_block_size: int = 40_000,
3098    debug: bool = False,
3099) -> _Array:
3100  """Interpolate `array` (a grid of samples) at specified unit-domain coordinates `coords`.
3101
3102  The last dimension of `coords` contains unit-domain coordinates at which to interpolate the
3103  domain grid samples in `array`.
3104
3105  The number of coordinates (`coords.shape[-1]`) determines how to interpret `array`: its first
3106  `coords.shape[-1]` dimensions define the grid, and the remaining dimensions describe each grid
3107  sample (e.g., scalar, vector, tensor).
3108
3109  Concretely, the grid has shape `array.shape[:coords.shape[-1]]` and each grid sample has shape
3110  `array.shape[coords.shape[-1]:]`.
3111
3112  Examples include:
3113
3114  - Resample a grayscale image with `array.shape = height, width` onto a new grayscale image with
3115    `new.shape = height2, width2` by using `coords.shape = height2, width2, 2`.
3116
3117  - Resample an RGB image with `array.shape = height, width, 3` onto a new RGB image with
3118    `new.shape = height2, width2, 3` by using `coords.shape = height2, width2, 2`.
3119
3120  - Sample an RGB image at `num` 2D points along a line segment by using `coords.shape = num, 2`.
3121
3122  - Sample an RGB image at a single 2D point by using `coords.shape = (2,)`.
3123
3124  - Sample a 3D grid of 3x3 Jacobians with `array.shape = nz, ny, nx, 3, 3` along a 2D plane by
3125    using `coords.shape = height, width, 3`.
3126
3127  - Map a grayscale image through a color map by using `array.shape = 256, 3` and
3128    `coords.shape = height, width, 1`.
3129
3130  Args:
3131    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
3132      The array must have numeric type.  The coordinate dimensions appear first, and
3133      each grid sample may have an arbitrary shape.  Each grid dimension must be at least 1 for
3134      a `'dual'` grid or at least 2 for a `'primal'` grid.
3135    coords: Grid of points at which to resample `array`.  The point coordinates are in the last
3136      dimension of `coords`.  The domain associated with the source grid is a unit hypercube,
3137      i.e. with a range [0, 1] on each coordinate dimension.  The output grid has shape
3138      `coords.shape[:-1]` and each of its grid samples has shape `array.shape[coords.shape[-1]:]`.
3139    gridtype: Placement of the samples in the source domain grid for each dimension, specified as
3140      either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`.
3141    boundary: The reconstruction boundary rule for each dimension in `coords.shape[-1]`, specified
3142      as either a name in `BOUNDARIES` or a `Boundary` instance.  The special value `'auto'` uses
3143      `'reflect'` for upsampling and `'clamp'` for downsampling.  (Currently, `resample` does
3144      not detect downsampling, so `'auto'` always uses `'reflect'`.)
3145    cval: Constant value used beyond the samples by some boundary rules.  It must be broadcastable
3146      onto the shape `array.shape[coords.shape[-1]:]`.  It is subject to `src_gamma`.
3147    filter: The reconstruction kernel for each dimension in `coords.shape[-1]`, specified as either
3148      a filter name in `FILTERS` or a `Filter` instance.
3149    prefilter: The prefilter kernel for each dimension in `coords.shape[:-1]`, specified as either
3150      a filter name in `FILTERS` or a `Filter` instance.  It is used during downsampling
3151      (i.e., minification).  If `None`, it inherits the value of `filter`.  (It is currently
3152      unused, because `resample` does not yet prefilter.)
3153    gamma: Component transfer functions (e.g., gamma correction) applied when reading samples
3154      from `array` and when creating output grid samples.  It is specified as either a name in
3155      `GAMMAS` or a `Gamma` instance.  If both `array.dtype` and `dtype` are `uint`, the default
3156      is `'power2'`.  If both are non-`uint`, the default is `'identity'`.  Otherwise, `gamma` or
3157      `src_gamma`/`dst_gamma` must be set.  Gamma correction assumes that float values are in the
3158      range [0.0, 1.0].
3159    src_gamma: Component transfer function used to "decode" `array` samples.
3160      Parameters `gamma` and `src_gamma` cannot both be set.
3161    dst_gamma: Component transfer function used to "encode" the output samples.
3162      Parameters `gamma` and `dst_gamma` cannot both be set.
3163    jacobian: Optional array, which must be broadcastable onto the shape
3164      `coords.shape[:-1] + (coords.shape[-1], coords.shape[-1])`, storing for each point in the
3165      output grid the Jacobian matrix of the map from the unit output domain to the unit source
3166      domain.  If omitted, it is estimated by computing finite differences on `coords`.  (It is
3167      currently unused, as it serves only for prefiltering.)
3168    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
3169      on `array.dtype`, `coords.dtype`, and `dtype`.
3170    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
3171      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
3172      to the uint range.
3173    from_coefficients: If True, `array` already holds the reconstruction coefficients returned by
3174      `compute_coefficients` (its samples decoded by `src_gamma` and transformed by the digital
3175      filter of `filter`), so those two steps are skipped; `src_gamma` still decodes `cval`.
3176    max_block_size: If nonzero, maximum number of grid points in `coords` before the resampling
3177      evaluation gets partitioned into smaller blocks for reduced memory usage and better caching.
3178    debug: Show internal information.
3179
3180  Returns:
3181    A new sample grid of shape `coords.shape[:-1]`, represented as an array of shape
3182    `coords.shape[:-1] + array.shape[coords.shape[-1]:]`, of the same array library type as
3183    the source array.
3184
3185  **Example of resample operation:**
3186
3187  <center>
3188  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_warp_coords.png"/>
3189  </center>
3190
3191  For reference, the identity resampling for a scalar-valued grid with the default grid-type
3192  `'dual'` is:
3193
3194  >>> array = np.random.default_rng(1).random((5, 7, 3))
3195  >>> coords = (np.moveaxis(np.indices(array.shape), 0, -1) + 0.5) / array.shape
3196  >>> new_array = resample(array, coords)
3197  >>> assert np.allclose(new_array, array)
3198
3199  It is more efficient to use the function `resize` for the special case where the `coords` are
3200  obtained as simple scaling and translation of a new regular grid over the source domain:
3201
3202  >>> scale, translate, new_shape = (1.1, 1.2), (0.1, -0.2), (6, 8)
3203  >>> coords = (np.moveaxis(np.indices(new_shape), 0, -1) + 0.5) / new_shape
3204  >>> coords = (coords - translate) / scale
3205  >>> resampled = resample(array, coords)
3206  >>> resized = resize(array, new_shape, scale=scale, translate=translate)
3207  >>> assert np.allclose(resampled, resized)
3208  """
3209  arraylib = _arr_arraylib(array)
3210  if len(_arr_shape(array)) == 0:
3211    array = _arr_reshape(array, (1,))
3212  coords = np.atleast_1d(coords)
3213  if not np.issubdtype(_arr_dtype(array), np.number):
3214    raise ValueError(f'Type {_arr_dtype(array)} is not numeric.')
3215  if not np.issubdtype(coords.dtype, np.floating):
3216    raise ValueError(f'Type {coords.dtype} is not floating.')
3217  array_ndim = len(_arr_shape(array))
3218  if coords.ndim == 1 and coords.shape[0] > 1 and array_ndim == 1:
3219    coords = coords[:, None]
3220  grid_ndim = coords.shape[-1]
3221  grid_shape = _arr_shape(array)[:grid_ndim]
3222  sample_shape = _arr_shape(array)[grid_ndim:]
3223  resampled_ndim = coords.ndim - 1
3224  resampled_shape = coords.shape[:-1]
3225  if grid_ndim > array_ndim:
3226    raise ValueError(
3227        f'There are more coordinate dimensions ({grid_ndim}) in {coords=}'
3228        f' than in array.shape={_arr_shape(array)}.'
3229    )
3230  gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(gridtype), grid_ndim)]
3231  boundary2 = np.broadcast_to(np.array(boundary), grid_ndim).tolist()
3232  cval = np.broadcast_to(cval, sample_shape)
3233  prefilter = filter if prefilter is None else prefilter
3234  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), grid_ndim)]
3235  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), grid_ndim)]
3236  dtype = _arr_dtype(array) if dtype is None else np.dtype(dtype)
3237  src_gamma2, dst_gamma2 = _get_src_dst_gamma(gamma, src_gamma, dst_gamma, _arr_dtype(array), dtype)
3238  del gridtype, boundary, filter, prefilter, src_gamma, dst_gamma
3239  if jacobian is not None:
3240    jacobian = np.broadcast_to(jacobian, resampled_shape + (coords.shape[-1],) * 2)
3241  precision = _get_precision(precision, [_arr_dtype(array), dtype], [coords.dtype])
3242  weight_precision = _real_precision(precision)
3243  coords = coords.astype(weight_precision, copy=False)
3244  is_minification = False  # Current limitation; no prefiltering!
3245  assert max_block_size >= 0 or max_block_size == _MAX_BLOCK_SIZE_RECURSING
3246  for dim in range(grid_ndim):
3247    if boundary2[dim] == 'auto':
3248      boundary2[dim] = 'clamp' if is_minification else 'reflect'
3249    boundary2[dim] = _get_boundary(boundary2[dim])
3250
3251  if max_block_size != _MAX_BLOCK_SIZE_RECURSING:
3252    if from_coefficients:
3253      if not np.issubdtype(_arr_dtype(array), np.inexact):
3254        raise ValueError(f'Coefficients must be inexact, unlike {_arr_dtype(array)=}.')
3255    else:
3256      array = src_gamma2.decode(array, precision)
3257      for dim in range(grid_ndim):
3258        assert not is_minification
3259        if filter2[dim].requires_digital_filter:
3260          array = _apply_digital_filter_1d(
3261              array, gridtype2[dim], boundary2[dim], cval, filter2[dim], axis=dim
3262          )
3263    cval = _arr_numpy(src_gamma2.decode(cval, precision))
3264
3265  if math.prod(resampled_shape) > max_block_size > 0:
3266    block_shape = _block_shape_with_min_size(resampled_shape, max_block_size)
3267    if debug:
3268      print(f'(resample: splitting coords into blocks {block_shape}).')
3269    coord_blocks = _split_array_into_blocks(coords, block_shape)
3270
3271    def process_block(coord_block: _NDArray) -> _Array:
3272      return resample(
3273          typing.cast(Any, array),
3274          coord_block,
3275          gridtype=gridtype2,
3276          boundary=boundary2,
3277          cval=cval,
3278          filter=filter2,
3279          prefilter=prefilter2,
3280          src_gamma='identity',
3281          dst_gamma=dst_gamma2,
3282          jacobian=None,  # (It would have to be split into blocks, but it is currently unused.)
3283          precision=precision,
3284          dtype=dtype,
3285          max_block_size=_MAX_BLOCK_SIZE_RECURSING,
3286      )
3287
3288    result_blocks = _map_function_over_blocks(coord_blocks, process_block)
3289    array = _merge_array_from_blocks(result_blocks)
3290    return array
3291
3292  # A concrete example of upsampling:
3293  #   array = np.ones((5, 7, 3))  # source RGB image has height=5 width=7
3294  #   coords = np.random.default_rng(1).random((8, 9, 2))  # output RGB image has height=8 width=9
3295  #   resample(array, coords, filter=('cubic', 'lanczos3'))
3296  #   grid_shape = 5, 7  grid_ndim = 2
3297  #   resampled_shape = 8, 9  resampled_ndim = 2
3298  #   sample_shape = (3,)
3299  #   src_float_index.shape = 8, 9
3300  #   src_first_index.shape = 8, 9
3301  #   sample_index.shape = (4,) for dim == 0, then (6,) for dim == 1
3302  #   weight = [shape(8, 9, 4), shape(8, 9, 6)]
3303  #   src_index = [shape(8, 9, 4), shape(8, 9, 6)]
3304
3305  # Both:[shape(8, 9, 4), shape(8, 9, 6)]
3306  weight: list[_NDArray] = [np.array([]) for _ in range(grid_ndim)]
3307  src_index: list[_NDArray] = [np.array([]) for _ in range(grid_ndim)]
3308  uses_cval = False
3309
3310  for dim in range(grid_ndim):
3311    src_size = grid_shape[dim]  # scalar
3312    coords_dim = coords[..., dim]  # (8, 9)
3313    radius = filter2[dim].radius  # scalar
3314    num_samples = int(np.ceil(radius * 2))  # scalar
3315
3316    boundary_dim = boundary2[dim]
3317    coords_dim = boundary_dim.preprocess_coordinates(coords_dim)
3318
3319    # Sample positions mapped back to source unit domain [0, 1].
3320    src_float_index = gridtype2[dim].index_from_point(coords_dim, src_size)  # (8, 9)
3321    src_first_index = (
3322        np.floor(src_float_index + (0.5 if num_samples % 2 == 1 else 0.0)).astype(np.int32)
3323        - (num_samples - 1) // 2
3324    )  # (8, 9)
3325
3326    sample_index = np.arange(num_samples, dtype=np.int32)  # (4,) then (6,)
3327    src_index[dim] = src_first_index[..., None] + sample_index  # (8, 9, 4) then (8, 9, 6)
3328    if filter2[dim].name == 'trapezoid':
3329      # (It might require changing the filter radius at every sample.)
3330      raise ValueError('resample() cannot use adaptive `trapezoid` filter.')
3331    if filter2[dim].name == 'impulse':
3332      weight[dim] = np.ones_like(src_index[dim], weight_precision)
3333    else:
3334      x = src_float_index[..., None] - src_index[dim].astype(weight_precision)
3335      weight[dim] = filter2[dim](x).astype(weight_precision, copy=False)
3336      if filter2[dim].name != 'narrowbox' and (
3337          is_minification or not filter2[dim].partition_of_unity
3338      ):
3339        weight[dim] = weight[dim] / weight[dim].sum(axis=-1)[..., None]
3340
3341    src_index[dim], weight[dim] = boundary_dim.fold(
3342        src_index[dim], weight[dim], coords_dim, src_size, gridtype2[dim]
3343    )
3344    if boundary_dim.uses_cval or filter2[dim].name == 'narrowbox':
3345      uses_cval = True
3346
3347  # Gather the samples.
3348
3349  # Recall that src_index = [shape(8, 9, 4), shape(8, 9, 6)].
3350  src_index_expanded = []
3351  for dim in range(grid_ndim):
3352    src_index_dim = np.moveaxis(
3353        src_index[dim].reshape(src_index[dim].shape + (1,) * (grid_ndim - 1)),
3354        resampled_ndim,
3355        resampled_ndim + dim,
3356    )
3357    src_index_expanded.append(src_index_dim)
3358  indices = tuple(src_index_expanded)  # (shape(8, 9, 4, 1), shape(8, 9, 1, 6))
3359  samples = _arr_getitem(array, indices)  # (8, 9, 4, 6, 3)
3360
3361  # Indirectly derive samples.ndim (which is unavailable during Tensorflow grad computation).
3362  samples_ndim = resampled_ndim + grid_ndim + len(sample_shape)
3363
3364  # Compute an Einstein summation over the samples and each of the per-dimension weights.
3365
3366  def label(dims: Iterable[int]) -> str:
3367    return ''.join(chr(ord('a') + i) for i in dims)
3368
3369  operands: list[Any] = [samples]  # (8, 9, 4, 6, 3)
3370  assert samples_ndim < 26  # Letters 'a' through 'z'.
3371  labels = [label(range(samples_ndim))]  # ['abcde']
3372  for dim in range(grid_ndim):
3373    operands.append(weight[dim])  # (8, 9, 4), then (8, 9, 6)
3374    labels.append(label(list(range(resampled_ndim)) + [resampled_ndim + dim]))  # 'abc' then 'abd'
3375  output_label = label(
3376      list(range(resampled_ndim)) + list(range(resampled_ndim + grid_ndim, samples_ndim))
3377  )  # 'abe'
3378  subscripts = ','.join(labels) + '->' + output_label  # 'abcde,abc,abd->abe'
3379  array = _arr_einsum(subscripts, *operands)  # (8, 9, 3)
3380
3381  # Gathering `samples` is the memory bottleneck.  It would be ideal if the gather() and einsum()
3382  # computations could be fused.  In Jax, https://github.com/jax-ml/jax/issues/3206 suggests
3383  # that this may become possible.  In any case, for large outputs it helps to partition the
3384  # evaluation over output tiles (using max_block_size).
3385
3386  if uses_cval:
3387    cval_weight = 1.0 - np.multiply.reduce(
3388        [weight[dim].sum(axis=-1) for dim in range(grid_ndim)]
3389    )  # (8, 9)
3390    cval_weight_reshaped = cval_weight.reshape(cval_weight.shape + (1,) * len(sample_shape))
3391    array += _make_array((cval_weight_reshaped * cval).astype(precision, copy=False), arraylib)
3392
3393  array = dst_gamma2.encode(array, dtype)
3394  return array
3395
3396
3397def resample_affine(
3398    array: _Array,
3399    /,
3400    shape: Iterable[int],
3401    matrix: _ArrayLike,
3402    *,
3403    gridtype: str | Gridtype | None = None,
3404    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
3405    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
3406    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3407    prefilter: str | Filter | Iterable[str | Filter] | None = None,
3408    precision: _DTypeLike | None = None,
3409    dtype: _DTypeLike | None = None,
3410    **kwargs: Any,
3411) -> _Array:
3412  """Resample a source array using an affinely transformed grid of given shape.
3413
3414  The `matrix` transformation can be linear,
3415    `source_point = matrix @ destination_point`,
3416  or it can be affine where the last matrix column is an offset vector,
3417    `source_point = matrix @ (destination_point, 1.0)`.
3418
3419  Args:
3420    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
3421      The array must have numeric type.  The number of grid dimensions is determined from
3422      `matrix.shape[0]`; the remaining dimensions are for each sample value and are all
3423      linearly interpolated.
3424    shape: Dimensions of the desired destination grid.  The number of destination grid dimensions
3425      may be different from that of the source grid.
3426    matrix: 2D array for a linear or affine transform from unit-domain destination points
3427      (in a space with `len(shape)` dimensions) into unit-domain source points (in a space with
3428      `matrix.shape[0]` dimensions).  If the matrix has `len(shape) + 1` columns, the last column
3429      is the affine offset (i.e., translation).
3430    gridtype: Placement of samples on all dimensions of both the source and output domain grids,
3431      specified as either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`
3432      if `gridtype`, `src_gridtype`, and `dst_gridtype` are all kept `None`.
3433    src_gridtype: Placement of samples in the source domain grid for each dimension.
3434      Parameters `gridtype` and `src_gridtype` cannot both be set.
3435    dst_gridtype: Placement of samples in the output domain grid for each dimension.
3436      Parameters `gridtype` and `dst_gridtype` cannot both be set.
3437    filter: The reconstruction kernel for each dimension in `matrix.shape[0]`, specified as either
3438      a filter name in `FILTERS` or a `Filter` instance.
3439    prefilter: The prefilter kernel for each dimension in `len(shape)`, specified as either
3440      a filter name in `FILTERS` or a `Filter` instance.  It is used during downsampling
3441      (i.e., minification).  If `None`, it inherits the value of `filter`.
3442    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
3443      on `array.dtype` and `dtype`.
3444    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
3445      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
3446      to the uint range.
3447    **kwargs: Additional parameters for `resample` function.
3448
3449  Returns:
3450    An array of the same class as the source `array`, representing a grid with specified `shape`,
3451    where each grid value is resampled from `array`.  Thus the shape of the returned array is
3452    `shape + array.shape[matrix.shape[0]:]`.
3453  """
3454  shape = tuple(shape)
3455  matrix = np.asarray(matrix)
3456  dst_ndim = len(shape)
3457  if matrix.ndim != 2:
3458    raise ValueError(f'Array {matrix} is not a 2D matrix.')
3459  src_ndim = matrix.shape[0]
3460  # grid_shape = array.shape[:src_ndim]
3461  is_affine = matrix.shape[1] == dst_ndim + 1
3462  if src_ndim > len(_arr_shape(array)):
3463    raise ValueError(
3464        f'Matrix {matrix} has more rows ({matrix.shape[0]}) than ndim in'
3465        f' array.shape={_arr_shape(array)}.'
3466    )
3467  if matrix.shape[1] != dst_ndim and not is_affine:
3468    raise ValueError(
3469        f'Matrix has {matrix.shape=}, but we expect either {dst_ndim} or {dst_ndim + 1} columns.'
3470    )
3471  src_gridtype2, dst_gridtype2 = _get_gridtypes(
3472      gridtype, src_gridtype, dst_gridtype, src_ndim, dst_ndim
3473  )
3474  prefilter = filter if prefilter is None else prefilter
3475  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), src_ndim)]
3476  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), src_ndim)]
3477  del src_gridtype, dst_gridtype, filter, prefilter
3478  dtype = _arr_dtype(array) if dtype is None else np.dtype(dtype)
3479  precision = _get_precision(precision, [_arr_dtype(array), dtype], [])
3480  weight_precision = _real_precision(precision)
3481
3482  dst_position_list = []  # per dimension
3483  for dim in range(dst_ndim):
3484    dst_size = shape[dim]
3485    dst_index = np.arange(dst_size, dtype=weight_precision)
3486    dst_position_list.append(dst_gridtype2[dim].point_from_index(dst_index, dst_size))
3487  dst_position = np.meshgrid(*dst_position_list, indexing='ij')
3488
3489  linear_matrix = matrix[:, :-1] if is_affine else matrix
3490  src_position = np.tensordot(linear_matrix, dst_position, 1)
3491  coords = np.moveaxis(src_position, 0, -1)
3492  if is_affine:
3493    coords += matrix[:, -1]
3494
3495  # TODO: Based on grid_shape, shape, linear_matrix, and prefilter, determine a
3496  # convolution prefilter and apply it to bandlimit 'array', using boundary for padding.
3497
3498  return resample(
3499      array,
3500      coords,
3501      gridtype=src_gridtype2,
3502      filter=filter2,
3503      prefilter=prefilter2,
3504      precision=precision,
3505      dtype=dtype,
3506      **kwargs,
3507  )
3508
3509
3510def _resize_using_resample(
3511    array: _Array,
3512    /,
3513    shape: Iterable[int],
3514    *,
3515    scale: _ArrayLike = 1.0,
3516    translate: _ArrayLike = 0.0,
3517    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3518    fallback: bool = False,
3519    **kwargs: Any,
3520) -> _Array:
3521  """Use the more general `resample` operation for `resize`, as a debug tool."""
3522  shape = tuple(shape)
3523  scale = np.broadcast_to(scale, len(shape))
3524  translate = np.broadcast_to(translate, len(shape))
3525  # TODO: let resample() do prefiltering for proper downsampling.
3526  src_shape = _arr_shape(array)[: len(shape)]
3527  has_minification = np.any(np.array(shape) < src_shape) or np.any(scale < 1.0)
3528  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), len(shape))]
3529  has_auto_trapezoid = any(f.name == 'trapezoid' for f in filter2)
3530  if fallback and (has_minification or has_auto_trapezoid):
3531    return _original_resize(array, shape, scale=scale, translate=translate, filter=filter, **kwargs)
3532  offset = -translate / scale
3533  matrix = np.concatenate([np.diag(1.0 / scale), offset[:, None]], axis=1)
3534  return resample_affine(array, shape, matrix, filter=filter, **kwargs)
3535
3536
3537def rotation_about_center_in_2d(
3538    src_shape: _ArrayLike,
3539    /,
3540    angle: float,
3541    *,
3542    new_shape: _ArrayLike | None = None,
3543    scale: float = 1.0,
3544) -> _NDArray:
3545  """Return the 3x3 matrix mapping the destination unit domain into the source unit domain.
3546
3547  The returned matrix accounts for the possibly non-square domain shapes.
3548
3549  Args:
3550    src_shape: Resolution `(ny, nx)` of the source domain grid.
3551    angle: Angle in radians (positive from x to y axis) applied when mapping the source domain
3552      onto the destination domain.
3553    new_shape: Resolution `(ny, nx)` of the destination domain grid; it defaults to `src_shape`.
3554    scale: Scaling factor applied when mapping the source domain onto the destination domain.
3555  """
3556
3557  def translation_matrix(vector: _NDArray) -> _NDArray:
3558    matrix = np.eye(len(vector) + 1)
3559    matrix[:-1, -1] = vector
3560    return matrix
3561
3562  def scaling_matrix(scale: _NDArray) -> _NDArray:
3563    return np.diag(tuple(scale) + (1.0,))
3564
3565  def rotation_matrix_2d(angle: float) -> _NDArray:
3566    cos, sin = np.cos(angle), np.sin(angle)
3567    return np.array([[cos, sin, 0], [-sin, cos, 0], [0, 0, 1]])
3568
3569  src_shape = np.asarray(src_shape)
3570  new_shape = src_shape if new_shape is None else np.asarray(new_shape)
3571  _check_eq(src_shape.shape, (2,))
3572  _check_eq(new_shape.shape, (2,))
3573  half = np.array([0.5, 0.5])
3574  matrix = (
3575      translation_matrix(half)
3576      @ scaling_matrix(min(src_shape) / src_shape)
3577      @ rotation_matrix_2d(angle)
3578      @ scaling_matrix(scale * new_shape / min(new_shape))
3579      @ translation_matrix(-half)
3580  )
3581  assert np.allclose(matrix[-1], [0.0, 0.0, 1.0])
3582  return matrix
3583
3584
3585def rotate_image_about_center(
3586    image: _Array,
3587    /,
3588    angle: float,
3589    *,
3590    new_shape: _ArrayLike | None = None,
3591    scale: float = 1.0,
3592    num_rotations: int = 1,
3593    **kwargs: Any,
3594) -> _Array:
3595  """Return a copy of `image` rotated about its center.
3596
3597  Args:
3598    image: Source grid samples; the first two dimensions are spatial (ny, nx).
3599    angle: Angle in radians (positive from x to y axis) applied when mapping the source domain
3600      onto the destination domain.
3601    new_shape: Resolution `(ny, nx)` of the output grid; it defaults to `image.shape[:2]`.
3602    scale: Scaling factor applied when mapping the source domain onto the destination domain.
3603    num_rotations: Number of rotations (each by `angle`).  Successive resamplings are useful in
3604      analyzing the filtering quality.
3605    **kwargs: Additional parameters for `resample_affine`.
3606  """
3607  new_shape = _arr_shape(image)[:2] if new_shape is None else np.asarray(new_shape)
3608  for _ in range(num_rotations):
3609    src_shape = _arr_shape(image)[:2]  # It becomes new_shape after the first rotation.
3610    matrix = rotation_about_center_in_2d(src_shape, angle, new_shape=new_shape, scale=scale)
3611    image = resample_affine(image, new_shape, matrix[:-1], **kwargs)
3612  return image
3613
3614
3615def _pil_image_resize(
3616    array: _ArrayLike,
3617    /,
3618    shape: Iterable[int],
3619    *,
3620    filter: str,
3621    boundary: str = 'natural',
3622    cval: float = 0.0,
3623) -> _NDArray:
3624  """Invoke `PIL.Image.resize` using the same parameters as `resize`."""
3625  import PIL.Image
3626
3627  if boundary != 'natural':
3628    raise ValueError(f"{boundary=} must equal 'natural'.")
3629  del cval
3630  array = np.asarray(array)
3631  assert 1 <= array.ndim <= 3
3632  assert np.issubdtype(array.dtype, np.floating)
3633  shape = tuple(shape)
3634  _check_eq(len(shape), 2 if array.ndim >= 2 else 1)
3635  if array.ndim == 1:
3636    return _pil_image_resize(array[None], (1, *shape), filter=filter)[0]
3637  if not hasattr(PIL.Image, 'Resampling'):  # Pillow<9.0
3638    PIL.Image.Resampling = PIL.Image  # type: ignore
3639  filters = {
3640      'impulse': PIL.Image.Resampling.NEAREST,
3641      'box': PIL.Image.Resampling.BOX,
3642      'triangle': PIL.Image.Resampling.BILINEAR,
3643      'hamming1': PIL.Image.Resampling.HAMMING,
3644      'cubic': PIL.Image.Resampling.BICUBIC,
3645      'lanczos3': PIL.Image.Resampling.LANCZOS,
3646  }
3647  if filter not in filters:
3648    raise ValueError(f'{filter=} not in {filters=}.')
3649  pil_resample = filters[filter]
3650  ny, nx = shape
3651  if array.ndim == 2:
3652    return np.array(PIL.Image.fromarray(array).resize((nx, ny), resample=pil_resample), array.dtype)
3653  stack = []
3654  for channel in np.moveaxis(array, -1, 0):
3655    pil_image = PIL.Image.fromarray(channel).resize((nx, ny), resample=pil_resample)
3656    stack.append(np.array(pil_image, array.dtype))
3657  return np.dstack(stack)
3658
3659
3660def _cv_resize(
3661    array: _ArrayLike,
3662    /,
3663    shape: Iterable[int],
3664    *,
3665    filter: str,
3666    boundary: str = 'clamp',
3667    cval: float = 0.0,
3668) -> _NDArray:
3669  """Invoke `cv.resize` using the same parameters as `resize`."""
3670  import cv2 as cv
3671
3672  if boundary != 'clamp':
3673    raise ValueError(f"{boundary=} must equal 'clamp'.")
3674  del cval
3675  array = np.asarray(array)
3676  assert 1 <= array.ndim <= 3
3677  shape = tuple(shape)
3678  _check_eq(len(shape), 2 if array.ndim >= 2 else 1)
3679  if array.ndim == 1:
3680    return _cv_resize(array[None], (1, *shape), filter=filter)[0]
3681  filters = {
3682      'impulse': cv.INTER_NEAREST,  # Or consider cv.INTER_NEAREST_EXACT.
3683      'triangle': cv.INTER_LINEAR_EXACT,  # Or just cv.INTER_LINEAR.
3684      'trapezoid': cv.INTER_AREA,
3685      'sharpcubic': cv.INTER_CUBIC,
3686      'lanczos4': cv.INTER_LANCZOS4,
3687  }
3688  if filter not in filters:
3689    raise ValueError(f'{filter=} not in {filters=}.')
3690  interpolation = filters[filter]
3691  result = cv.resize(array, shape[::-1], interpolation=interpolation)
3692  if array.ndim == 3 and result.ndim == 2:
3693    assert array.shape[2] == 1
3694    return result[..., None]  # Add back the last dimension dropped by cv.resize().
3695  return result
3696
3697
3698def _scipy_ndimage_resize(
3699    array: _ArrayLike,
3700    /,
3701    shape: Iterable[int],
3702    *,
3703    filter: str,
3704    boundary: str = 'reflect',
3705    cval: float = 0.0,
3706    scale: float | Iterable[float] = 1.0,
3707    translate: float | Iterable[float] = 0.0,
3708) -> _NDArray:
3709  """Invoke `scipy.ndimage.map_coordinates` using the same parameters as `resize`."""
3710  array = np.asarray(array)
3711  shape = tuple(shape)
3712  assert 1 <= len(shape) <= array.ndim
3713  filters = {'box': 0, 'triangle': 1} | {f'cardinal{i}': i for i in range(2, 6)}
3714  if filter not in filters:
3715    raise ValueError(f'{filter=} not in {filters=}.')
3716  order = filters[filter]
3717  boundaries = {'reflect': 'reflect', 'wrap': 'grid-wrap', 'clamp': 'nearest', 'border': 'constant'}
3718  if boundary not in boundaries:
3719    raise ValueError(f'{boundary=} not in {boundaries=}.')
3720  mode = boundaries[boundary]
3721  shape_all = shape + array.shape[len(shape) :]
3722  coords = np.moveaxis(np.indices(shape_all, array.dtype), 0, -1)
3723  coords[..., : len(shape)] = (
3724      (coords[..., : len(shape)] + 0.5) / shape - np.asarray(translate)
3725  ) / np.asarray(scale) * np.array(array.shape)[: len(shape)] - 0.5
3726  coords = np.moveaxis(coords, -1, 0)
3727  return scipy.ndimage.map_coordinates(array, coords, order=order, mode=mode, cval=cval)
3728
3729
3730def _skimage_transform_resize(
3731    array: _ArrayLike,
3732    /,
3733    shape: Iterable[int],
3734    *,
3735    filter: str,
3736    boundary: str = 'reflect',
3737    cval: float = 0.0,
3738) -> _NDArray:
3739  """Invoke `skimage.transform.resize` using the same parameters as `resize`."""
3740  import skimage.transform
3741
3742  array = np.asarray(array)
3743  shape = tuple(shape)
3744  assert 1 <= len(shape) <= array.ndim
3745  filters = {'box': 0, 'triangle': 1} | {f'cardinal{i}': i for i in range(2, 6)}
3746  if filter not in filters:
3747    raise ValueError(f'{filter=} not in {filters=}.')
3748  order = filters[filter]
3749  boundaries = {'reflect': 'symmetric', 'wrap': 'wrap', 'clamp': 'edge', 'border': 'constant'}
3750  if boundary not in boundaries:
3751    raise ValueError(f'{boundary=} not in {boundaries=}.')
3752  mode = boundaries[boundary]
3753  shape_all = shape + array.shape[len(shape) :]
3754  # Default anti_aliasing=None automatically enables (poor) Gaussian prefilter if downsampling.
3755  # clip=False is the default behavior in `resampler` if the output type is non-integer.
3756  return skimage.transform.resize(
3757      array, shape_all, order=order, mode=mode, cval=cval, clip=False
3758  )  # type: ignore[no-untyped-call]
3759
3760
3761_TORCH_INTERPOLATE_MODE_FROM_FILTER = {
3762    'impulse': 'nearest-exact',  # ('nearest' matches buggy OpenCV's INTER_NEAREST)
3763    'trapezoid': 'area',
3764    'triangle': 'bilinear',
3765    'sharpcubic': 'bicubic',
3766}
3767
3768
3769def _torch_nn_resize(
3770    array: _ArrayLike,
3771    /,
3772    shape: Iterable[int],
3773    *,
3774    filter: str,
3775    boundary: str = 'clamp',
3776    cval: float = 0.0,
3777    antialias: bool = False,
3778) -> _TorchTensor:
3779  """Invoke `torch.nn.functional.interpolate` using the same parameters as `resize`."""
3780  import torch
3781
3782  if filter not in _TORCH_INTERPOLATE_MODE_FROM_FILTER:
3783    raise ValueError(f'{filter=} not in {_TORCH_INTERPOLATE_MODE_FROM_FILTER=}.')
3784  if boundary != 'clamp':
3785    raise ValueError(f"{boundary=} must equal 'clamp'.")
3786  del cval
3787  a = torch.as_tensor(array)
3788  del array
3789  assert 1 <= a.ndim <= 3
3790  shape = tuple(shape)
3791  _check_eq(len(shape), 2 if a.ndim >= 2 else 1)
3792  mode = _TORCH_INTERPOLATE_MODE_FROM_FILTER[filter]
3793
3794  def local_resize(a: _TorchTensor) -> _TorchTensor:
3795    # For upsampling, BILINEAR antialias is same PSNR and slower,
3796    #  and BICUBIC antialias is worse PSNR and faster.
3797    # For downsampling, antialias improves PSNR for both BILINEAR and BICUBIC.
3798    # Default align_corners=None corresponds to False which is what we desire.
3799    return torch.nn.functional.interpolate(a, shape, mode=mode, antialias=antialias)
3800
3801  match a.ndim:
3802    case 1:
3803      shape = (1, *shape)
3804      return local_resize(a[None, None, None])[0, 0, 0]
3805    case 2:
3806      return local_resize(a[None, None])[0, 0]
3807    case _:
3808      return local_resize(a.moveaxis(2, 0)[None])[0].moveaxis(0, 2)
3809
3810
3811def _jax_image_resize(
3812    array: _ArrayLike,
3813    /,
3814    shape: Iterable[int],
3815    *,
3816    filter: str,
3817    boundary: str = 'natural',
3818    cval: float = 0.0,
3819    scale: float | Iterable[float] = 1.0,
3820    translate: float | Iterable[float] = 0.0,
3821) -> _JaxArray:
3822  """Invoke `jax.image.scale_and_translate` using the same parameters as `resize`."""
3823  import jax.image
3824  import jax.numpy as jnp
3825
3826  filters = 'triangle cubic lanczos3 lanczos5'.split()
3827  if filter not in filters:
3828    raise ValueError(f'{filter=} not in {filters=}.')
3829  if boundary != 'natural':
3830    raise ValueError(f"{boundary=} must equal 'natural'.")
3831  # When `scale` or `translate` are applied, any region outside the unit domain is assigned value 0.
3832  # To be consistent, the parameter `cval` must be zero.
3833  if scale != 1.0 and cval != 0.0:
3834    raise ValueError(f'Non-unity {scale=} requires that {cval=} be zero.')
3835  if translate != 0.0 and cval != 0.0:
3836    raise ValueError(f'Nonzero {translate=} requires that {cval=} be zero.')
3837  array2 = jnp.asarray(array)
3838  del array
3839  shape = tuple(shape)
3840  assert len(shape) <= array2.ndim
3841  completed_shape = shape + (1,) * (array2.ndim - len(shape))
3842  spatial_dims = list(range(len(shape)))
3843  scale2 = np.broadcast_to(np.array(scale), len(shape))
3844  scale2 = scale2 / np.array(array2.shape[: len(shape)]) * np.array(shape)
3845  translate2 = np.broadcast_to(np.array(translate), len(shape))
3846  translate2 = translate2 * np.array(shape)
3847  return jax.image.scale_and_translate(
3848      array2, completed_shape, spatial_dims, scale2, translate2, filter
3849  )
3850
3851
3852_CANDIDATE_RESIZERS: dict[str, Callable[..., _AnyArray]] = {
3853    'resampler.resize': resize,
3854    'PIL.Image.resize': _pil_image_resize,
3855    'cv.resize': _cv_resize,
3856    'scipy.ndimage.map_coordinates': _scipy_ndimage_resize,
3857    'skimage.transform.resize': _skimage_transform_resize,
3858    'torch.nn.functional.interpolate': _torch_nn_resize,
3859    'jax.image.scale_and_translate': _jax_image_resize,
3860}
3861
3862
3863def _resizer_is_available(library_function: str) -> bool:
3864  """Return whether the resizer is available as an installed package."""
3865  top_name = library_function.split('.', 1)[0]
3866  module = {'cv': 'cv2'}.get(top_name, top_name)
3867  return importlib.util.find_spec(module) is not None
3868
3869
3870_RESIZERS = {
3871    library_function: resizer
3872    for library_function, resizer in _CANDIDATE_RESIZERS.items()
3873    if _resizer_is_available(library_function)
3874}
3875
3876
3877def _find_closest_filter(filter: str, resizer: Callable[..., Any]) -> str:
3878  """Return the filter supported by `resizer` (i.e., `*_resize`) that is closest to `filter`."""
3879  match filter:
3880    case 'box_like':
3881      return {
3882          _cv_resize: 'trapezoid',
3883          _skimage_transform_resize: 'box',
3884          _torch_nn_resize: 'trapezoid',
3885      }.get(resizer, 'box')
3886    case 'cubic_like':
3887      return {
3888          _cv_resize: 'sharpcubic',
3889          _scipy_ndimage_resize: 'cardinal3',
3890          _skimage_transform_resize: 'cardinal3',
3891          _torch_nn_resize: 'sharpcubic',
3892      }.get(resizer, 'cubic')
3893    case 'high_quality':
3894      return {
3895          _pil_image_resize: 'lanczos3',
3896          _cv_resize: 'lanczos4',
3897          _scipy_ndimage_resize: 'cardinal5',
3898          _skimage_transform_resize: 'cardinal5',
3899          _torch_nn_resize: 'sharpcubic',
3900      }.get(resizer, 'lanczos5')
3901    case _:
3902      return filter
3903
3904
3905# For Emacs:
3906# Local Variables:
3907# fill-column: 100
3908# End:
ARRAYLIBS: list[str] = ['numpy']

Array libraries supported automatically in the resize and resampling operations.

  • The library is selected automatically based on the type of the array function parameter.

  • The class _Arraylib provides library-specific implementations of needed basic functions.

  • The _arr_*() functions dispatch the _Arraylib methods based on the array type.

@dataclasses.dataclass(frozen=True)
class Gridtype(abc.ABC):
942@dataclasses.dataclass(frozen=True)
943class Gridtype(abc.ABC):
944  """Abstract base class for grid-types such as `'dual'` and `'primal'`.
945
946  In resampling operations, the grid-type may be specified separately as `src_gridtype` for the
947  source domain and `dst_gridtype` for the destination domain.  Moreover, the grid-type may be
948  specified per domain dimension.
949
950  Examples:
951    `resize(source, shape, gridtype='primal')`  # Sets both src and dst to be `'primal'` grids.
952
953    `resize(source, shape, src_gridtype=['dual', 'primal'],
954            dst_gridtype='dual')`  # Source is `'dual'` in dim0 and `'primal'` in dim1.
955  """
956
957  name: str
958  """Gridtype name."""
959
960  @abc.abstractmethod
961  def min_size(self) -> int:
962    """Return the necessary minimum number of grid samples."""
963
964  @abc.abstractmethod
965  def size_in_samples(self, size: int, /) -> int:
966    """Return the domain size in units of inter-sample spacing."""
967
968  @abc.abstractmethod
969  def point_from_index(self, index: _NDArray, size: int, /) -> _NDArray:
970    """Return [0.0, 1.0] coordinates given [0, size - 1] indices."""
971
972  @abc.abstractmethod
973  def index_from_point(self, point: _NDArray, size: int, /) -> _NDArray:
974    """Return location x given coordinates [0.0, 1.0], where x == 0.0 is the first grid sample
975    and x == size - 1.0 is the last grid sample."""
976
977  @abc.abstractmethod
978  def reflect(self, index: _NDArray, size: int, /) -> _NDArray:
979    """Map integer sample indices to interior ones using boundary reflection."""
980
981  @abc.abstractmethod
982  def wrap(self, index: _NDArray, size: int, /) -> _NDArray:
983    """Map integer sample indices to interior ones using wrapping."""
984
985  @abc.abstractmethod
986  def reflect_clamp(self, index: _NDArray, size: int, /) -> _NDArray:
987    """Map integer sample indices to interior ones using reflect-clamp."""

Abstract base class for grid-types such as 'dual' and 'primal'.

In resampling operations, the grid-type may be specified separately as src_gridtype for the source domain and dst_gridtype for the destination domain. Moreover, the grid-type may be specified per domain dimension.

Examples:

resize(source, shape, gridtype='primal') # Sets both src and dst to be 'primal' grids.

resize(source, shape, src_gridtype=['dual', 'primal'], dst_gridtype='dual') # Source is 'dual' in dim0 and 'primal' in dim1.

GRIDTYPES: list[str] = ['dual', 'primal']

Shortcut names for the two predefined grid types (specified per dimension):

gridtype 'dual'
DualGridtype()
(default)
'primal'
PrimalGridtype()
 
Sample positions in 2D
and in 1D at different resolutions
Dual Primal
Nesting of samples across resolutions The samples positions do not nest. The even samples remain at coarser scale.
Number $N_\ell$ of samples (per-dimension) at resolution level $\ell$ $N_\ell=2^\ell$ $N_\ell=2^\ell+1$
Position of sample index $i$ within domain $[0, 1]$ $\frac{i + 0.5}{N}$ ("half-integer" coordinates) $\frac{i}{N-1}$
Image resolutions ($N_\ell\times N_\ell$) for dyadic scales $1\times1, ~~2\times2, ~~4\times4, ~~8\times8, ~\ldots$ $2\times2, ~~3\times3, ~~5\times5, ~~9\times9, ~\ldots$

See the source code for extensibility.

@dataclasses.dataclass(frozen=True)
class Boundary:
1388@dataclasses.dataclass(frozen=True)
1389class Boundary:
1390  """Domain boundary rules.  These define the reconstruction over the source domain near and beyond
1391  the domain boundaries.  The rules may be specified separately for each domain dimension."""
1392
1393  name: str = ''
1394  """Boundary rule name."""
1395
1396  coord_remap: RemapCoordinates = NoRemapCoordinates()
1397  """Modify specified coordinates prior to evaluating the reconstruction kernels."""
1398
1399  extend_samples: ExtendSamples = ReflectExtendSamples()
1400  """Define the value of each grid sample outside the unit domain as an affine combination of
1401  interior sample(s) and possibly the constant value (`cval`)."""
1402
1403  override_value: OverrideExteriorValue = NoOverrideExteriorValue()
1404  """Set the value outside some extent to a constant value (`cval`)."""
1405
1406  @property
1407  def uses_cval(self) -> bool:
1408    """True if weights may be non-affine, involving the constant value (`cval`)."""
1409    return self.extend_samples.uses_cval or self.override_value.uses_cval
1410
1411  def preprocess_coordinates(self, point: _NDArray, /) -> _NDArray:
1412    """Modify coordinates prior to evaluating the filter kernels."""
1413    # Antialiasing across the tile boundaries may be feasible but seems hard.
1414    point = self.coord_remap(point)
1415    return point
1416
1417  def fold(
1418      self, index: _NDArray, weight: _NDArray, point: _NDArray, size: int, gridtype: Gridtype, /
1419  ) -> tuple[_NDArray, _NDArray]:
1420    """Fold the kernel taps that reference exterior samples onto interior samples (and `cval`)."""
1421    index, weight = self.extend_samples(index, weight, size, gridtype)
1422    self.override_reconstruction(weight, point)
1423    return index, weight
1424
1425  def override_reconstruction(self, weight: _NDArray, point: _NDArray, /) -> None:
1426    """For points outside an extent, modify weight to zero to assign `cval`."""
1427    self.override_value(weight, point)

Domain boundary rules. These define the reconstruction over the source domain near and beyond the domain boundaries. The rules may be specified separately for each domain dimension.

BOUNDARIES: list[str] = ['reflect', 'wrap', 'tile', 'clamp', 'border', 'natural', 'linear_constant', 'quadratic_constant', 'reflect_clamp', 'constant', 'linear', 'quadratic']

Shortcut names for some predefined boundary rules (as defined by _DICT_BOUNDARIES):

name a.k.a. / comments
'reflect' reflected, symm, symmetric, mirror, grid-mirror
'wrap' periodic, repeat, grid-wrap
'tile' like 'reflect' within unit domain, then tile discontinuously
'clamp' clamped, nearest, edge, clamp-to-edge, repeat last sample
'border' grid-constant, use cval for samples outside unit domain
'natural' renormalize using only interior samples, use cval outside domain
'reflect_clamp' mirror-clamp-to-edge
'constant' like 'reflect' but replace by cval outside unit domain
'linear' extrapolate from 2 last samples
'quadratic' extrapolate from 3 last samples
'linear_constant' like 'linear' but replace by cval outside unit domain
'quadratic_constant' like 'quadratic' but replace by cval outside unit domain

These boundary rules may be specified per dimension. See the source code for extensibility using the classes RemapCoordinates, ExtendSamples, and OverrideExteriorValue.

Boundary rules illustrated in 1D:

Boundary rules illustrated in 2D:

@dataclasses.dataclass(frozen=True)
class Filter(abc.ABC):
1508@dataclasses.dataclass(frozen=True)
1509class Filter(abc.ABC):
1510  """Abstract base class for filter kernel functions.
1511
1512  Each kernel is assumed to be a zero-phase filter, i.e., to be symmetric in a support
1513  interval [-radius, radius].  (Some sites instead define kernels over the interval [0, N]
1514  where N = 2 * radius.)
1515
1516  Portions of this code are adapted from the C++ library in
1517  https://github.com/hhoppe/Mesh-processing-library/blob/main/libHh/Filter.cpp
1518
1519  See also https://hhoppe.com/proj/filtering/.
1520  """
1521
1522  name: str
1523  """Filter kernel name."""
1524
1525  radius: float
1526  """Max absolute value of x for which self(x) is nonzero."""
1527
1528  interpolating: bool = True
1529  """True if self(0) == 1.0 and self(i) == 0.0 for all nonzero integers i."""
1530
1531  continuous: bool = True
1532  """True if the kernel function has $C^0$ continuity."""
1533
1534  partition_of_unity: bool = True
1535  """True if the convolution of the kernel with a Dirac comb reproduces the
1536  unity function."""
1537
1538  unit_integral: bool = True
1539  """True if the integral of the kernel function is 1."""
1540
1541  requires_digital_filter: bool = False
1542  """True if the filter needs a pre/post digital filter for interpolation."""
1543
1544  @abc.abstractmethod
1545  def __call__(self, x: _ArrayLike, /) -> _NDArray:
1546    """Return evaluation of filter kernel at locations x."""

Abstract base class for filter kernel functions.

Each kernel is assumed to be a zero-phase filter, i.e., to be symmetric in a support interval [-radius, radius]. (Some sites instead define kernels over the interval [0, N] where N = 2 * radius.)

Portions of this code are adapted from the C++ library in https://github.com/hhoppe/Mesh-processing-library/blob/main/libHh/Filter.cpp

See also https://hhoppe.com/proj/filtering/.

FILTERS: list[str] = ['impulse', 'box', 'trapezoid', 'triangle', 'cubic', 'sharpcubic', 'lanczos3', 'lanczos5', 'lanczos10', 'cardinal3', 'cardinal5', 'omoms3', 'omoms5', 'hamming3', 'kaiser3', 'gaussian', 'bspline3', 'mitchell', 'narrowbox']

Shortcut names for some predefined filter kernels (specified per dimension). The names expand to:

name Filter a.k.a. / comments
'impulse' ImpulseFilter() nearest
'box' BoxFilter() non-antialiased box, e.g. ImageMagick
'trapezoid' TrapezoidFilter() area antialiasing, e.g. cv.INTER_AREA
'triangle' TriangleFilter() linear (bilinear in 2D), spline order=1
'cubic' CatmullRomFilter() catmullrom, keys, bicubic
'sharpcubic' SharpCubicFilter() cv.INTER_CUBIC, torch 'bicubic'
'lanczos3' LanczosFilter(radius=3) support window [-3, 3]
'lanczos5' LanczosFilter(radius=5) [-5, 5]
'lanczos10' LanczosFilter(radius=10) [-10, 10]
'cardinal3' CardinalBsplineFilter(degree=3) spline interpolation, order=3, GF
'cardinal5' CardinalBsplineFilter(degree=5) spline interpolation, order=5, GF
'omoms3' OmomsFilter(degree=3) non-$C^1$, [-2, 2], GF
'omoms5' OmomsFilter(degree=5) non-$C^1$, [-3, 3], GF
'hamming3' GeneralizedHammingFilter(...) (radius=3, a0=25/46)
'kaiser3' KaiserFilter(radius=3.0, beta=7.12)
'gaussian' GaussianFilter() non-interpolating, default $\sigma=1.25/3$
'bspline3' BsplineFilter(degree=3) non-interpolating
'mitchell' MitchellFilter() mitchellcubic
'narrowbox' NarrowBoxFilter() for visualization of sample positions

The comment label GF denotes a generalized filter, formed as the composition of a finitely supported kernel and a discrete inverse convolution.

Some example filter kernels:


A more extensive set of filters is presented here in the notebook, together with visualizations and analyses of the filter properties. See the source code for extensibility.

@dataclasses.dataclass(frozen=True)
class Gamma(abc.ABC):
2064@dataclasses.dataclass(frozen=True)
2065class Gamma(abc.ABC):
2066  """Abstract base class for transfer functions on sample values.
2067
2068  Image/video content is often stored using a color component transfer function.
2069  See https://en.wikipedia.org/wiki/Gamma_correction.
2070
2071  Converts between integer types and [0.0, 1.0] internal value range.
2072  """
2073
2074  name: str
2075  """Name of component transfer function."""
2076
2077  @abc.abstractmethod
2078  def decode(self, array: _Array, /, dtype: _DTypeLike = np.float32) -> _Array:
2079    """Decode source sample values into floating-point, possibly nonlinearly.
2080
2081    Uint source values are mapped to the range [0.0, 1.0].
2082    """
2083
2084  @abc.abstractmethod
2085  def encode(self, array: _Array, /, dtype: _DTypeLike) -> _Array:
2086    """Encode float signal into destination samples, possibly nonlinearly.
2087
2088    Uint destination values are mapped from the range [0.0, 1.0].
2089
2090    Note that `IdentityGamma` does not clip non-integer destination types to the range [0.0, 1.0].
2091    If that is desired, it can be performed as a postprocess using `output.clip(0.0, 1.0)`.
2092    """

Abstract base class for transfer functions on sample values.

Image/video content is often stored using a color component transfer function. See https://en.wikipedia.org/wiki/Gamma_correction.

Converts between integer types and [0.0, 1.0] internal value range.

GAMMAS: list[str] = ['identity', 'power2', 'power22', 'srgb']

Shortcut names for some predefined gamma-correction schemes:

name Gamma Decoding function
(linear space from stored value)
Encoding function
(stored value from linear space)
'identity' IdentityGamma() $l = e$ $e = l$
'power2' PowerGamma(2.0) $l = e^{2.0}$ $e = l^{1/2.0}$
'power22' PowerGamma(2.2) $l = e^{2.2}$ $e = l^{1/2.2}$
'srgb' SrgbGamma() $l = \left(\left(e + 0.055\right) / 1.055\right)^{2.4}$ $e = l^{1/2.4} * 1.055 - 0.055$

See the source code for extensibility.

def resize( array: Array, /, shape: Iterable[int], *, gridtype: str | Gridtype | None = None, src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, boundary: str | Boundary | Iterable[str | Boundary] = 'auto', cval: ArrayLike = 0.0, filter: str | Filter | Iterable[str | Filter] = 'lanczos3', prefilter: str | Filter | Iterable[str | Filter] | None = None, gamma: str | Gamma | None = None, src_gamma: str | Gamma | None = None, dst_gamma: str | Gamma | None = None, scale: float | Iterable[float] = 1.0, translate: float | Iterable[float] = 0.0, precision: DTypeLike | None = None, dtype: DTypeLike | None = None, dim_order: Iterable[int] | None = None, num_threads: int | Literal['auto'] = 'auto') -> Array:
2633def resize(
2634    array: _Array,
2635    /,
2636    shape: Iterable[int],
2637    *,
2638    gridtype: str | Gridtype | None = None,
2639    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2640    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2641    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
2642    cval: _ArrayLike = 0.0,
2643    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
2644    prefilter: str | Filter | Iterable[str | Filter] | None = None,
2645    gamma: str | Gamma | None = None,
2646    src_gamma: str | Gamma | None = None,
2647    dst_gamma: str | Gamma | None = None,
2648    scale: float | Iterable[float] = 1.0,
2649    translate: float | Iterable[float] = 0.0,
2650    precision: _DTypeLike | None = None,
2651    dtype: _DTypeLike | None = None,
2652    dim_order: Iterable[int] | None = None,
2653    num_threads: int | Literal['auto'] = 'auto',
2654) -> _Array:
2655  """Resample `array` (a grid of sample values) onto a grid with resolution `shape`.
2656
2657  The source `array` is any object recognized by `ARRAYLIBS`.  It is interpreted as a grid
2658  with `len(shape)` domain coordinate dimensions, where each grid sample value has shape
2659  `array.shape[len(shape):]`.
2660
2661  Some examples:
2662
2663  - A grayscale image has `array.shape = height, width` and resizing it with `len(shape) == 2`
2664    produces a new image of scalar values.
2665  - An RGB image has `array.shape = height, width, 3` and resizing it with `len(shape) == 2`
2666    produces a new image of RGB values.
2667  - A 3D grid of 3x3 Jacobians has `array.shape = Z, Y, X, 3, 3` and resizing it with
2668    `len(shape) == 3` produces a new 3D grid of Jacobians.
2669
2670  This function also allows scaling and translation from the source domain to the output domain
2671  through the parameters `scale` and `translate`.  For more general transforms, see `resample`.
2672
2673  Args:
2674    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
2675      The array must have numeric type.  Its first `len(shape)` dimensions are the domain
2676      coordinate dimensions.  Each grid dimension must be at least 1 for a `'dual'` grid or
2677      at least 2 for a `'primal'` grid.
2678    shape: The number of grid samples in each coordinate dimension of the output array.  The source
2679      `array` must have at least as many dimensions as `len(shape)`.
2680    gridtype: Placement of samples on all dimensions of both the source and output domain grids,
2681      specified as either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`
2682      if `gridtype`, `src_gridtype`, and `dst_gridtype` are all kept `None`.
2683    src_gridtype: Placement of the samples in the source domain grid for each dimension.
2684      Parameters `gridtype` and `src_gridtype` cannot both be set.
2685    dst_gridtype: Placement of the samples in the output domain grid for each dimension.
2686      Parameters `gridtype` and `dst_gridtype` cannot both be set.
2687    boundary: The reconstruction boundary rule for each dimension in `shape`, specified as either
2688      a name in `BOUNDARIES` or a `Boundary` instance.  The special value `'auto'` uses `'reflect'`
2689      for upsampling and `'clamp'` for downsampling.
2690    cval: Constant value used beyond the samples by some boundary rules.  It must be broadcastable
2691      onto `array.shape[len(shape):]`.  It is subject to `src_gamma`.
2692    filter: The reconstruction kernel for each dimension in `shape`, specified as either a filter
2693      name in `FILTERS` or a `Filter` instance.  It is used during upsampling (i.e., magnification).
2694    prefilter: The prefilter kernel for each dimension in `shape`, specified as either a filter
2695      name in `FILTERS` or a `Filter` instance.  It is used during downsampling
2696      (i.e., minification).  If `None`, it inherits the value of `filter`.  The default
2697      `'lanczos3'` is good for natural images.  For vector graphics images, `'trapezoid'` is better
2698      because it avoids ringing artifacts.
2699    gamma: Component transfer functions (e.g., gamma correction) applied when reading samples from
2700      `array` and when creating output grid samples.  It is specified as either a name in `GAMMAS`
2701      or a `Gamma` instance.  If both `array.dtype` and `dtype` are `uint`, the default is
2702      `'power2'`.  If both are non-`uint`, the default is `'identity'`.  Otherwise, `gamma` or
2703      `src_gamma`/`dst_gamma` must be set.  Gamma correction assumes that float values are in the
2704      range [0.0, 1.0].
2705    src_gamma: Component transfer function used to "decode" `array` samples.
2706      Parameters `gamma` and `src_gamma` cannot both be set.
2707    dst_gamma: Component transfer function used to "encode" the output samples.
2708      Parameters `gamma` and `dst_gamma` cannot both be set.
2709    scale: Scaling factor applied to each dimension of the source domain when it is mapped onto
2710      the destination domain.
2711    translate: Offset applied to each dimension of the scaled source domain when it is mapped onto
2712      the destination domain.
2713    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
2714      on `array.dtype` and `dtype`.
2715    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
2716      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
2717      to the uint range.
2718    dim_order: Override the automatically selected order in which the grid dimensions are resized.
2719      Must contain a permutation of `range(len(shape))`.
2720    num_threads: Used to determine multithread parallelism if `array` is from `numpy`.  If set to
2721      `'auto'`, it is selected automatically.  Otherwise, it must be a positive integer.
2722
2723  Returns:
2724    An array of the same class as the source `array`, with shape `shape + array.shape[len(shape):]`
2725      and data type `dtype`.
2726
2727  **Example of image upsampling:**
2728
2729  >>> array = np.random.default_rng(1).random((4, 6, 3))  # 4x6 RGB image.
2730  >>> upsampled = resize(array, (128, 192))  # To 128x192 resolution.
2731
2732  <center>
2733  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_array_upsampled.png"/>
2734  </center>
2735
2736  **Example of image downsampling:**
2737
2738  >>> yx = (np.moveaxis(np.indices((96, 192)), 0, -1) + (0.5, 0.5)) / 96
2739  >>> radius = np.linalg.norm(yx - (0.75, 0.5), axis=-1)
2740  >>> array = np.cos((radius + 0.1) ** 0.5 * 70.0) * 0.5 + 0.5
2741  >>> downsampled = resize(array, (24, 48))
2742
2743  <center>
2744  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_array_downsampled2.png"/>
2745  </center>
2746
2747  **Unit test:**
2748
2749  >>> result = resize(np.array([1.0, 4.0, 5.0]), shape=(4,))
2750  >>> assert np.allclose(result, [0.74240461, 2.88088827, 4.68647155, 5.02641199])
2751  """
2752  arraylib = _arr_arraylib(array)
2753  array_dtype = _arr_dtype(array)
2754  if not np.issubdtype(array_dtype, np.number):
2755    raise ValueError(f'Type {array_dtype} is not numeric.')
2756  shape2 = tuple(shape)
2757  array_ndim = len(_arr_shape(array))
2758  if not 0 < len(shape2) <= array_ndim:
2759    raise ValueError(f'Shape {_arr_shape(array)} cannot be resized to {shape2}.')
2760  src_shape = _arr_shape(array)[: len(shape2)]
2761  src_gridtype2, dst_gridtype2 = _get_gridtypes(
2762      gridtype, src_gridtype, dst_gridtype, len(shape2), len(shape2)
2763  )
2764  boundary2 = np.broadcast_to(np.array(boundary), len(shape2))
2765  cval = np.broadcast_to(cval, _arr_shape(array)[len(shape2) :])
2766  prefilter = filter if prefilter is None else prefilter
2767  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), len(shape2))]
2768  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), len(shape2))]
2769  dtype = array_dtype if dtype is None else np.dtype(dtype)
2770  src_gamma2, dst_gamma2 = _get_src_dst_gamma(gamma, src_gamma, dst_gamma, array_dtype, dtype)
2771  scale2 = np.broadcast_to(np.array(scale), len(shape2))
2772  translate2 = np.broadcast_to(np.array(translate), len(shape2))
2773  del shape, src_gridtype, dst_gridtype, boundary, filter, prefilter
2774  del src_gamma, dst_gamma, scale, translate
2775  precision = _get_precision(precision, [array_dtype, dtype], [])
2776  weight_precision = _real_precision(precision)
2777
2778  is_noop = (
2779      all(src == dst for src, dst in zip(src_shape, shape2, strict=True))
2780      and all(gt1 == gt2 for gt1, gt2 in zip(src_gridtype2, dst_gridtype2, strict=True))
2781      and all(f.interpolating for f in filter2)
2782      and np.all(scale2 == 1.0)
2783      and np.all(translate2 == 0.0)
2784      and src_gamma2 == dst_gamma2
2785      and dtype == array_dtype
2786  )
2787  if is_noop:
2788    return array
2789
2790  if dim_order is None:
2791    dim_order = _arr_best_dims_order_for_resize(array, shape2)
2792  else:
2793    dim_order = tuple(dim_order)
2794    if sorted(dim_order) != list(range(len(shape2))):
2795      raise ValueError(f'{dim_order} is not a permutation of {list(range(len(shape2)))}.')
2796
2797  array = src_gamma2.decode(array, precision)
2798  cval = _arr_numpy(src_gamma2.decode(cval, precision))
2799
2800  can_use_fast_box_downsampling = (
2801      _USING_NUMBA
2802      and arraylib == 'numpy'
2803      and len(shape2) == 2
2804      and array_ndim in (2, 3)
2805      and all(src > dst for src, dst in zip(src_shape, shape2, strict=True))
2806      and all(src % dst == 0 for src, dst in zip(src_shape, shape2, strict=True))
2807      and all(gridtype.name == 'dual' for gridtype in src_gridtype2)
2808      and all(gridtype.name == 'dual' for gridtype in dst_gridtype2)
2809      and all(f.name in ('box', 'trapezoid') for f in prefilter2)
2810      and np.all(scale2 == 1.0)
2811      and np.all(translate2 == 0.0)
2812  )
2813  if can_use_fast_box_downsampling:
2814    # Casting to _NDArray is needed by pyrefly but is redundant for mypy, so cast to Any.
2815    array2 = _downsample_in_2d_using_box_filter(typing.cast(Any, array), shape2)
2816    return typing.cast(_Array, dst_gamma2.encode(array2, dtype))
2817
2818  # Multidimensional resize can be expressed using einsum() with multiple per-dim resize matrices,
2819  # e.g., as in jax.image.resize().  A benefit is to seek the optimal order of multiplications.
2820  # However, efficiency often requires sparse resize matrices, which are unsupported in einsum().
2821  # https://github.com/tensor-compiler/taco: C++ library that computes tensor algebra expressions
2822  # on sparse and dense tensors; however it does not interoperate with torch or jax.
2823
2824  for dim in dim_order:
2825    skip_resize_on_this_dim = (
2826        shape2[dim] == _arr_shape(array)[dim]
2827        and scale2[dim] == 1.0
2828        and translate2[dim] == 0.0
2829        and filter2[dim].interpolating
2830    )
2831    if skip_resize_on_this_dim:
2832      continue
2833
2834    src_in_samples = src_gridtype2[dim].size_in_samples(_arr_shape(array)[dim])
2835    dst_in_samples = dst_gridtype2[dim].size_in_samples(shape2[dim])
2836    is_minification = dst_in_samples / src_in_samples * scale2[dim] < 1.0
2837    boundary_dim = boundary2[dim]
2838    if boundary_dim == 'auto':
2839      boundary_dim = 'clamp' if is_minification else 'reflect'
2840    boundary_dim = _get_boundary(boundary_dim)
2841    resize_matrix, cval_weight = _create_resize_matrix(
2842        _arr_shape(array)[dim],
2843        shape2[dim],
2844        src_gridtype=src_gridtype2[dim],
2845        dst_gridtype=dst_gridtype2[dim],
2846        boundary=boundary_dim,
2847        filter=filter2[dim],
2848        prefilter=prefilter2[dim],
2849        scale=scale2[dim],
2850        translate=translate2[dim],
2851        dtype=weight_precision,
2852        arraylib=arraylib,
2853    )
2854
2855    array_dim: _Array = _arr_moveaxis(array, dim, 0)
2856    array_flat: Any = _arr_reshape(array_dim, (_arr_shape(array_dim)[0], -1))
2857    array_flat = _arr_possibly_make_contiguous(array_flat)
2858    if not is_minification and filter2[dim].requires_digital_filter:
2859      array_flat = _apply_digital_filter_1d(
2860          array_flat, src_gridtype2[dim], boundary_dim, cval, filter2[dim]
2861      )
2862
2863    array_flat = _arr_matmul_sparse_dense(resize_matrix, array_flat, num_threads=num_threads)
2864    if cval_weight is not None:
2865      cval_flat = np.broadcast_to(cval, _arr_shape(array_dim)[1:]).reshape(-1)
2866      cval_weight2: Any = cval_weight
2867      if np.issubdtype(array_dtype, np.complexfloating):
2868        cval_weight2 = _arr_astype(cval_weight2, array_dtype)  # (Only necessary for 'tensorflow'.)
2869      array_flat += cval_weight2[:, None] * cval_flat
2870
2871    if is_minification and prefilter2[dim].requires_digital_filter:
2872      array_flat = _apply_digital_filter_1d(
2873          array_flat, dst_gridtype2[dim], boundary_dim, cval, prefilter2[dim]
2874      )
2875    array_dim = typing.cast(
2876        _Array, _arr_reshape(array_flat, (_arr_shape(array_flat)[0], *_arr_shape(array_dim)[1:]))
2877    )
2878    array = _arr_moveaxis(array_dim, 0, dim)
2879
2880  array = dst_gamma2.encode(array, dtype)
2881  return array

Resample array (a grid of sample values) onto a grid with resolution shape.

The source array is any object recognized by ARRAYLIBS. It is interpreted as a grid with len(shape) domain coordinate dimensions, where each grid sample value has shape array.shape[len(shape):].

Some examples:

  • A grayscale image has array.shape = height, width and resizing it with len(shape) == 2 produces a new image of scalar values.
  • An RGB image has array.shape = height, width, 3 and resizing it with len(shape) == 2 produces a new image of RGB values.
  • A 3D grid of 3x3 Jacobians has array.shape = Z, Y, X, 3, 3 and resizing it with len(shape) == 3 produces a new 3D grid of Jacobians.

This function also allows scaling and translation from the source domain to the output domain through the parameters scale and translate. For more general transforms, see resample.

Arguments:
  • array: Regular grid of source sample values, as an array object recognized by ARRAYLIBS. The array must have numeric type. Its first len(shape) dimensions are the domain coordinate dimensions. Each grid dimension must be at least 1 for a 'dual' grid or at least 2 for a 'primal' grid.
  • shape: The number of grid samples in each coordinate dimension of the output array. The source array must have at least as many dimensions as len(shape).
  • gridtype: Placement of samples on all dimensions of both the source and output domain grids, specified as either a name in GRIDTYPES or a Gridtype instance. It defaults to 'dual' if gridtype, src_gridtype, and dst_gridtype are all kept None.
  • src_gridtype: Placement of the samples in the source domain grid for each dimension. Parameters gridtype and src_gridtype cannot both be set.
  • dst_gridtype: Placement of the samples in the output domain grid for each dimension. Parameters gridtype and dst_gridtype cannot both be set.
  • boundary: The reconstruction boundary rule for each dimension in shape, specified as either a name in BOUNDARIES or a Boundary instance. The special value 'auto' uses 'reflect' for upsampling and 'clamp' for downsampling.
  • cval: Constant value used beyond the samples by some boundary rules. It must be broadcastable onto array.shape[len(shape):]. It is subject to src_gamma.
  • filter: The reconstruction kernel for each dimension in shape, specified as either a filter name in FILTERS or a Filter instance. It is used during upsampling (i.e., magnification).
  • prefilter: The prefilter kernel for each dimension in shape, specified as either a filter name in FILTERS or a Filter instance. It is used during downsampling (i.e., minification). If None, it inherits the value of filter. The default 'lanczos3' is good for natural images. For vector graphics images, 'trapezoid' is better because it avoids ringing artifacts.
  • gamma: Component transfer functions (e.g., gamma correction) applied when reading samples from array and when creating output grid samples. It is specified as either a name in GAMMAS or a Gamma instance. If both array.dtype and dtype are uint, the default is 'power2'. If both are non-uint, the default is 'identity'. Otherwise, gamma or src_gamma/dst_gamma must be set. Gamma correction assumes that float values are in the range [0.0, 1.0].
  • src_gamma: Component transfer function used to "decode" array samples. Parameters gamma and src_gamma cannot both be set.
  • dst_gamma: Component transfer function used to "encode" the output samples. Parameters gamma and dst_gamma cannot both be set.
  • scale: Scaling factor applied to each dimension of the source domain when it is mapped onto the destination domain.
  • translate: Offset applied to each dimension of the scaled source domain when it is mapped onto the destination domain.
  • precision: Inexact precision of intermediate computations. If None, it is determined based on array.dtype and dtype.
  • dtype: Desired data type of the output array. If None, it is taken to be array.dtype. If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range to the uint range.
  • dim_order: Override the automatically selected order in which the grid dimensions are resized. Must contain a permutation of range(len(shape)).
  • num_threads: Used to determine multithread parallelism if array is from numpy. If set to 'auto', it is selected automatically. Otherwise, it must be a positive integer.
Returns:

An array of the same class as the source array, with shape shape + array.shape[len(shape):] and data type dtype.

Example of image upsampling:

>>> array = np.random.default_rng(1).random((4, 6, 3))  # 4x6 RGB image.
>>> upsampled = resize(array, (128, 192))  # To 128x192 resolution.

Example of image downsampling:

>>> yx = (np.moveaxis(np.indices((96, 192)), 0, -1) + (0.5, 0.5)) / 96
>>> radius = np.linalg.norm(yx - (0.75, 0.5), axis=-1)
>>> array = np.cos((radius + 0.1) ** 0.5 * 70.0) * 0.5 + 0.5
>>> downsampled = resize(array, (24, 48))

Unit test:

>>> result = resize(np.array([1.0, 4.0, 5.0]), shape=(4,))
>>> assert np.allclose(result, [0.74240461, 2.88088827, 4.68647155, 5.02641199])
def jaxjit_resize(array: Array, /, *args: Any, **kwargs: Any) -> Array:
2932def jaxjit_resize(array: _Array, /, *args: Any, **kwargs: Any) -> _Array:
2933  """Compute `resize` but with resize function jitted using Jax."""
2934  return _create_jaxjit_resize()(array, *args, **kwargs)  # pylint: disable=not-callable

Compute resize but with resize function jitted using Jax.

def uniform_resize( array: Array, /, shape: Iterable[int], *, object_fit: Literal['contain', 'cover'] = 'contain', gridtype: str | Gridtype | None = None, src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, boundary: str | Boundary | Iterable[str | Boundary] = 'natural', scale: float | Iterable[float] = 1.0, translate: float | Iterable[float] = 0.0, **kwargs: Any) -> Array:
2937def uniform_resize(
2938    array: _Array,
2939    /,
2940    shape: Iterable[int],
2941    *,
2942    object_fit: Literal['contain', 'cover'] = 'contain',
2943    gridtype: str | Gridtype | None = None,
2944    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2945    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
2946    boundary: str | Boundary | Iterable[str | Boundary] = 'natural',  # Instead of 'auto' default.
2947    scale: float | Iterable[float] = 1.0,
2948    translate: float | Iterable[float] = 0.0,
2949    **kwargs: Any,
2950) -> _Array:
2951  """Resample `array` onto a grid with resolution `shape` but with uniform scaling.
2952
2953  Calls function `resize` with `scale` and `translate` set such that the aspect ratio of `array`
2954  is preserved.  The effect is similar to CSS `object-fit: contain` (or `object-fit: cover` if
2955  `object_fit='cover'`).
2956  The parameter `boundary` (whose default is changed to `'natural'`) determines the values assigned
2957  outside the source domain.
2958
2959  Args:
2960    array: Regular grid of source sample values.
2961    shape: The number of grid samples in each coordinate dimension of the output array.  The source
2962      `array` must have at least as many dimensions as `len(shape)`.
2963    object_fit: Like CSS `object-fit`.  If `'contain'`, `array` is resized uniformly to fit within
2964      `shape`.  If `'cover'`, `array` is resized to fully cover `shape`.
2965    gridtype: Placement of samples on all dimensions of both the source and output domain grids.
2966    src_gridtype: Placement of the samples in the source domain grid for each dimension.
2967    dst_gridtype: Placement of the samples in the output domain grid for each dimension.
2968    boundary: The reconstruction boundary rule for each dimension in `shape`, specified as either
2969      a name in `BOUNDARIES` or a `Boundary` instance.  The default is `'natural'`, which assigns
2970      `cval` to output points that map outside the source unit domain.
2971    scale: Parameter may not be specified.
2972    translate: Parameter may not be specified.
2973    **kwargs: Additional parameters for `resize` function (including `cval`).
2974
2975  Returns:
2976    An array with shape `shape + array.shape[len(shape):]`.
2977
2978  >>> uniform_resize(np.ones((2, 2)), (2, 4), filter='trapezoid')
2979  array([[0., 1., 1., 0.],
2980         [0., 1., 1., 0.]])
2981
2982  >>> uniform_resize(np.ones((4, 8)), (2, 7), filter='trapezoid')
2983  array([[0. , 0.5, 1. , 1. , 1. , 0.5, 0. ],
2984         [0. , 0.5, 1. , 1. , 1. , 0.5, 0. ]])
2985
2986  >>> a = np.arange(6.0).reshape(2, 3)
2987  >>> uniform_resize(a, (2, 2), filter='trapezoid', object_fit='cover')
2988  array([[0.5, 1.5],
2989         [3.5, 4.5]])
2990  """
2991  if scale != 1.0 or translate != 0.0:
2992    raise ValueError('`uniform_resize()` does not accept `scale` or `translate` parameters.')
2993  shape = tuple(shape)
2994  array_ndim = len(_arr_shape(array))
2995  if not 0 < len(shape) <= array_ndim:
2996    raise ValueError(f'Shape {_arr_shape(array)} cannot be resized to {shape}.')
2997  src_gridtype2, dst_gridtype2 = _get_gridtypes(
2998      gridtype, src_gridtype, dst_gridtype, len(shape), len(shape)
2999  )
3000  raw_scales = [
3001      dst_gridtype2[dim].size_in_samples(shape[dim])
3002      / src_gridtype2[dim].size_in_samples(_arr_shape(array)[dim])
3003      for dim in range(len(shape))
3004  ]
3005  scale0 = {'contain': min(raw_scales), 'cover': max(raw_scales)}[object_fit]
3006  scale2 = scale0 / np.array(raw_scales)
3007  translate = (1.0 - scale2) / 2
3008  return resize(
3009      array,
3010      shape,
3011      src_gridtype=src_gridtype2,
3012      dst_gridtype=dst_gridtype2,
3013      boundary=boundary,
3014      scale=scale2,
3015      translate=translate,
3016      **kwargs,
3017  )

Resample array onto a grid with resolution shape but with uniform scaling.

Calls function resize with scale and translate set such that the aspect ratio of array is preserved. The effect is similar to CSS object-fit: contain (or object-fit: cover if object_fit='cover'). The parameter boundary (whose default is changed to 'natural') determines the values assigned outside the source domain.

Arguments:
  • array: Regular grid of source sample values.
  • shape: The number of grid samples in each coordinate dimension of the output array. The source array must have at least as many dimensions as len(shape).
  • object_fit: Like CSS object-fit. If 'contain', array is resized uniformly to fit within shape. If 'cover', array is resized to fully cover shape.
  • gridtype: Placement of samples on all dimensions of both the source and output domain grids.
  • src_gridtype: Placement of the samples in the source domain grid for each dimension.
  • dst_gridtype: Placement of the samples in the output domain grid for each dimension.
  • boundary: The reconstruction boundary rule for each dimension in shape, specified as either a name in BOUNDARIES or a Boundary instance. The default is 'natural', which assigns cval to output points that map outside the source unit domain.
  • scale: Parameter may not be specified.
  • translate: Parameter may not be specified.
  • **kwargs: Additional parameters for resize function (including cval).
Returns:

An array with shape shape + array.shape[len(shape):].

>>> uniform_resize(np.ones((2, 2)), (2, 4), filter='trapezoid')
array([[0., 1., 1., 0.],
       [0., 1., 1., 0.]])
>>> uniform_resize(np.ones((4, 8)), (2, 7), filter='trapezoid')
array([[0. , 0.5, 1. , 1. , 1. , 0.5, 0. ],
       [0. , 0.5, 1. , 1. , 1. , 0.5, 0. ]])
>>> a = np.arange(6.0).reshape(2, 3)
>>> uniform_resize(a, (2, 2), filter='trapezoid', object_fit='cover')
array([[0.5, 1.5],
       [3.5, 4.5]])
def compute_coefficients( array: Array, /, grid_ndim: int, *, gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual', boundary: str | Boundary | Iterable[str | Boundary] = 'auto', cval: ArrayLike = 0.0, filter: str | Filter | Iterable[str | Filter] = 'lanczos3', gamma: str | Gamma | None = None, src_gamma: str | Gamma | None = None, precision: DTypeLike | None = None) -> Array:
3023def compute_coefficients(
3024    array: _Array,
3025    /,
3026    grid_ndim: int,
3027    *,
3028    gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual',
3029    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
3030    cval: _ArrayLike = 0.0,
3031    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3032    gamma: str | Gamma | None = None,
3033    src_gamma: str | Gamma | None = None,
3034    precision: _DTypeLike | None = None,
3035) -> _Array:
3036  """Return the reconstruction coefficients of `array`, for repeated calls to `resample`.
3037
3038  Before each evaluation, `resample` decodes the samples of `array` through the source gamma and,
3039  for a kernel that requires it (e.g., `'cardinal3'` or `'omoms5'`), transforms them by a digital
3040  filter.  This function performs just those steps, so that `resample(coefficients, coords,
3041  from_coefficients=True, ...)` can skip them when the same `array` is resampled many times (as
3042  in a warp sequence), given the same `gridtype`, `boundary`, `cval`, `filter`, and gamma settings.
3043
3044  Args:
3045    array: Grid of samples whose first `grid_ndim` dimensions define the grid.
3046    grid_ndim: Number of grid dimensions (`coords.shape[-1]` in the later calls to `resample`).
3047    gridtype: Placement of samples on the grid, as in `resample`.
3048    boundary: Boundary rule for each grid dimension, as in `resample`.
3049    cval: Constant value used beyond the input domain, as in `resample`.
3050    filter: Reconstruction kernel for each grid dimension, as in `resample`.
3051    gamma: Component transfer function applied to both the source and destination samples, as in
3052      `resample`.
3053    src_gamma: Component transfer function used to "decode" `array` samples, as in `resample`.
3054    precision: Inexact precision of the coefficients.  If `None`, it is determined based on
3055      the `array` dtype as in `resample`.
3056
3057  Returns:
3058    An array of floating-point coefficients with the shape of `array` and the same array library
3059    type as the source array.
3060  """
3061  array_ndim = len(_arr_shape(array))
3062  if not 0 < grid_ndim <= array_ndim:
3063    raise ValueError(f'{grid_ndim=} must lie in [1, array.ndim={array_ndim}].')
3064  gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(gridtype), grid_ndim)]
3065  boundary2 = np.broadcast_to(np.array(boundary), grid_ndim).tolist()
3066  boundary2 = [_get_boundary('reflect' if b == 'auto' else b) for b in boundary2]
3067  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), grid_ndim)]
3068  src_dtype = _arr_dtype(array)
3069  src_gamma2, _ = _get_src_dst_gamma(gamma, src_gamma, src_gamma, src_dtype, src_dtype)
3070  precision = _get_precision(precision, [src_dtype], [])
3071  cval = np.broadcast_to(cval, _arr_shape(array)[grid_ndim:])
3072  array = src_gamma2.decode(array, precision)
3073  for dim in range(grid_ndim):
3074    if filter2[dim].requires_digital_filter:
3075      array = _apply_digital_filter_1d(
3076          array, gridtype2[dim], boundary2[dim], cval, filter2[dim], axis=dim
3077      )
3078  return array

Return the reconstruction coefficients of array, for repeated calls to resample.

Before each evaluation, resample decodes the samples of array through the source gamma and, for a kernel that requires it (e.g., 'cardinal3' or 'omoms5'), transforms them by a digital filter. This function performs just those steps, so that resample(coefficients, coords, from_coefficients=True, ...) can skip them when the same array is resampled many times (as in a warp sequence), given the same gridtype, boundary, cval, filter, and gamma settings.

Arguments:
  • array: Grid of samples whose first grid_ndim dimensions define the grid.
  • grid_ndim: Number of grid dimensions (coords.shape[-1] in the later calls to resample).
  • gridtype: Placement of samples on the grid, as in resample.
  • boundary: Boundary rule for each grid dimension, as in resample.
  • cval: Constant value used beyond the input domain, as in resample.
  • filter: Reconstruction kernel for each grid dimension, as in resample.
  • gamma: Component transfer function applied to both the source and destination samples, as in resample.
  • src_gamma: Component transfer function used to "decode" array samples, as in resample.
  • precision: Inexact precision of the coefficients. If None, it is determined based on the array dtype as in resample.
Returns:

An array of floating-point coefficients with the shape of array and the same array library type as the source array.

def resample( array: Array, /, coords: ArrayLike, *, gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual', boundary: str | Boundary | Iterable[str | Boundary] = 'auto', cval: ArrayLike = 0.0, filter: str | Filter | Iterable[str | Filter] = 'lanczos3', prefilter: str | Filter | Iterable[str | Filter] | None = None, gamma: str | Gamma | None = None, src_gamma: str | Gamma | None = None, dst_gamma: str | Gamma | None = None, jacobian: ArrayLike | None = None, precision: DTypeLike | None = None, dtype: DTypeLike | None = None, from_coefficients: bool = False, max_block_size: int = 40000, debug: bool = False) -> Array:
3081def resample(
3082    array: _Array,
3083    /,
3084    coords: _ArrayLike,
3085    *,
3086    gridtype: str | Gridtype | Iterable[str | Gridtype] = 'dual',
3087    boundary: str | Boundary | Iterable[str | Boundary] = 'auto',
3088    cval: _ArrayLike = 0.0,
3089    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3090    prefilter: str | Filter | Iterable[str | Filter] | None = None,
3091    gamma: str | Gamma | None = None,
3092    src_gamma: str | Gamma | None = None,
3093    dst_gamma: str | Gamma | None = None,
3094    jacobian: _ArrayLike | None = None,
3095    precision: _DTypeLike | None = None,
3096    dtype: _DTypeLike | None = None,
3097    from_coefficients: bool = False,
3098    max_block_size: int = 40_000,
3099    debug: bool = False,
3100) -> _Array:
3101  """Interpolate `array` (a grid of samples) at specified unit-domain coordinates `coords`.
3102
3103  The last dimension of `coords` contains unit-domain coordinates at which to interpolate the
3104  domain grid samples in `array`.
3105
3106  The number of coordinates (`coords.shape[-1]`) determines how to interpret `array`: its first
3107  `coords.shape[-1]` dimensions define the grid, and the remaining dimensions describe each grid
3108  sample (e.g., scalar, vector, tensor).
3109
3110  Concretely, the grid has shape `array.shape[:coords.shape[-1]]` and each grid sample has shape
3111  `array.shape[coords.shape[-1]:]`.
3112
3113  Examples include:
3114
3115  - Resample a grayscale image with `array.shape = height, width` onto a new grayscale image with
3116    `new.shape = height2, width2` by using `coords.shape = height2, width2, 2`.
3117
3118  - Resample an RGB image with `array.shape = height, width, 3` onto a new RGB image with
3119    `new.shape = height2, width2, 3` by using `coords.shape = height2, width2, 2`.
3120
3121  - Sample an RGB image at `num` 2D points along a line segment by using `coords.shape = num, 2`.
3122
3123  - Sample an RGB image at a single 2D point by using `coords.shape = (2,)`.
3124
3125  - Sample a 3D grid of 3x3 Jacobians with `array.shape = nz, ny, nx, 3, 3` along a 2D plane by
3126    using `coords.shape = height, width, 3`.
3127
3128  - Map a grayscale image through a color map by using `array.shape = 256, 3` and
3129    `coords.shape = height, width, 1`.
3130
3131  Args:
3132    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
3133      The array must have numeric type.  The coordinate dimensions appear first, and
3134      each grid sample may have an arbitrary shape.  Each grid dimension must be at least 1 for
3135      a `'dual'` grid or at least 2 for a `'primal'` grid.
3136    coords: Grid of points at which to resample `array`.  The point coordinates are in the last
3137      dimension of `coords`.  The domain associated with the source grid is a unit hypercube,
3138      i.e. with a range [0, 1] on each coordinate dimension.  The output grid has shape
3139      `coords.shape[:-1]` and each of its grid samples has shape `array.shape[coords.shape[-1]:]`.
3140    gridtype: Placement of the samples in the source domain grid for each dimension, specified as
3141      either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`.
3142    boundary: The reconstruction boundary rule for each dimension in `coords.shape[-1]`, specified
3143      as either a name in `BOUNDARIES` or a `Boundary` instance.  The special value `'auto'` uses
3144      `'reflect'` for upsampling and `'clamp'` for downsampling.  (Currently, `resample` does
3145      not detect downsampling, so `'auto'` always uses `'reflect'`.)
3146    cval: Constant value used beyond the samples by some boundary rules.  It must be broadcastable
3147      onto the shape `array.shape[coords.shape[-1]:]`.  It is subject to `src_gamma`.
3148    filter: The reconstruction kernel for each dimension in `coords.shape[-1]`, specified as either
3149      a filter name in `FILTERS` or a `Filter` instance.
3150    prefilter: The prefilter kernel for each dimension in `coords.shape[:-1]`, specified as either
3151      a filter name in `FILTERS` or a `Filter` instance.  It is used during downsampling
3152      (i.e., minification).  If `None`, it inherits the value of `filter`.  (It is currently
3153      unused, because `resample` does not yet prefilter.)
3154    gamma: Component transfer functions (e.g., gamma correction) applied when reading samples
3155      from `array` and when creating output grid samples.  It is specified as either a name in
3156      `GAMMAS` or a `Gamma` instance.  If both `array.dtype` and `dtype` are `uint`, the default
3157      is `'power2'`.  If both are non-`uint`, the default is `'identity'`.  Otherwise, `gamma` or
3158      `src_gamma`/`dst_gamma` must be set.  Gamma correction assumes that float values are in the
3159      range [0.0, 1.0].
3160    src_gamma: Component transfer function used to "decode" `array` samples.
3161      Parameters `gamma` and `src_gamma` cannot both be set.
3162    dst_gamma: Component transfer function used to "encode" the output samples.
3163      Parameters `gamma` and `dst_gamma` cannot both be set.
3164    jacobian: Optional array, which must be broadcastable onto the shape
3165      `coords.shape[:-1] + (coords.shape[-1], coords.shape[-1])`, storing for each point in the
3166      output grid the Jacobian matrix of the map from the unit output domain to the unit source
3167      domain.  If omitted, it is estimated by computing finite differences on `coords`.  (It is
3168      currently unused, as it serves only for prefiltering.)
3169    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
3170      on `array.dtype`, `coords.dtype`, and `dtype`.
3171    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
3172      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
3173      to the uint range.
3174    from_coefficients: If True, `array` already holds the reconstruction coefficients returned by
3175      `compute_coefficients` (its samples decoded by `src_gamma` and transformed by the digital
3176      filter of `filter`), so those two steps are skipped; `src_gamma` still decodes `cval`.
3177    max_block_size: If nonzero, maximum number of grid points in `coords` before the resampling
3178      evaluation gets partitioned into smaller blocks for reduced memory usage and better caching.
3179    debug: Show internal information.
3180
3181  Returns:
3182    A new sample grid of shape `coords.shape[:-1]`, represented as an array of shape
3183    `coords.shape[:-1] + array.shape[coords.shape[-1]:]`, of the same array library type as
3184    the source array.
3185
3186  **Example of resample operation:**
3187
3188  <center>
3189  <img src="https://github.com/hhoppe/resampler/raw/main/media/example_warp_coords.png"/>
3190  </center>
3191
3192  For reference, the identity resampling for a scalar-valued grid with the default grid-type
3193  `'dual'` is:
3194
3195  >>> array = np.random.default_rng(1).random((5, 7, 3))
3196  >>> coords = (np.moveaxis(np.indices(array.shape), 0, -1) + 0.5) / array.shape
3197  >>> new_array = resample(array, coords)
3198  >>> assert np.allclose(new_array, array)
3199
3200  It is more efficient to use the function `resize` for the special case where the `coords` are
3201  obtained as simple scaling and translation of a new regular grid over the source domain:
3202
3203  >>> scale, translate, new_shape = (1.1, 1.2), (0.1, -0.2), (6, 8)
3204  >>> coords = (np.moveaxis(np.indices(new_shape), 0, -1) + 0.5) / new_shape
3205  >>> coords = (coords - translate) / scale
3206  >>> resampled = resample(array, coords)
3207  >>> resized = resize(array, new_shape, scale=scale, translate=translate)
3208  >>> assert np.allclose(resampled, resized)
3209  """
3210  arraylib = _arr_arraylib(array)
3211  if len(_arr_shape(array)) == 0:
3212    array = _arr_reshape(array, (1,))
3213  coords = np.atleast_1d(coords)
3214  if not np.issubdtype(_arr_dtype(array), np.number):
3215    raise ValueError(f'Type {_arr_dtype(array)} is not numeric.')
3216  if not np.issubdtype(coords.dtype, np.floating):
3217    raise ValueError(f'Type {coords.dtype} is not floating.')
3218  array_ndim = len(_arr_shape(array))
3219  if coords.ndim == 1 and coords.shape[0] > 1 and array_ndim == 1:
3220    coords = coords[:, None]
3221  grid_ndim = coords.shape[-1]
3222  grid_shape = _arr_shape(array)[:grid_ndim]
3223  sample_shape = _arr_shape(array)[grid_ndim:]
3224  resampled_ndim = coords.ndim - 1
3225  resampled_shape = coords.shape[:-1]
3226  if grid_ndim > array_ndim:
3227    raise ValueError(
3228        f'There are more coordinate dimensions ({grid_ndim}) in {coords=}'
3229        f' than in array.shape={_arr_shape(array)}.'
3230    )
3231  gridtype2 = [_get_gridtype(g) for g in np.broadcast_to(np.array(gridtype), grid_ndim)]
3232  boundary2 = np.broadcast_to(np.array(boundary), grid_ndim).tolist()
3233  cval = np.broadcast_to(cval, sample_shape)
3234  prefilter = filter if prefilter is None else prefilter
3235  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), grid_ndim)]
3236  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), grid_ndim)]
3237  dtype = _arr_dtype(array) if dtype is None else np.dtype(dtype)
3238  src_gamma2, dst_gamma2 = _get_src_dst_gamma(gamma, src_gamma, dst_gamma, _arr_dtype(array), dtype)
3239  del gridtype, boundary, filter, prefilter, src_gamma, dst_gamma
3240  if jacobian is not None:
3241    jacobian = np.broadcast_to(jacobian, resampled_shape + (coords.shape[-1],) * 2)
3242  precision = _get_precision(precision, [_arr_dtype(array), dtype], [coords.dtype])
3243  weight_precision = _real_precision(precision)
3244  coords = coords.astype(weight_precision, copy=False)
3245  is_minification = False  # Current limitation; no prefiltering!
3246  assert max_block_size >= 0 or max_block_size == _MAX_BLOCK_SIZE_RECURSING
3247  for dim in range(grid_ndim):
3248    if boundary2[dim] == 'auto':
3249      boundary2[dim] = 'clamp' if is_minification else 'reflect'
3250    boundary2[dim] = _get_boundary(boundary2[dim])
3251
3252  if max_block_size != _MAX_BLOCK_SIZE_RECURSING:
3253    if from_coefficients:
3254      if not np.issubdtype(_arr_dtype(array), np.inexact):
3255        raise ValueError(f'Coefficients must be inexact, unlike {_arr_dtype(array)=}.')
3256    else:
3257      array = src_gamma2.decode(array, precision)
3258      for dim in range(grid_ndim):
3259        assert not is_minification
3260        if filter2[dim].requires_digital_filter:
3261          array = _apply_digital_filter_1d(
3262              array, gridtype2[dim], boundary2[dim], cval, filter2[dim], axis=dim
3263          )
3264    cval = _arr_numpy(src_gamma2.decode(cval, precision))
3265
3266  if math.prod(resampled_shape) > max_block_size > 0:
3267    block_shape = _block_shape_with_min_size(resampled_shape, max_block_size)
3268    if debug:
3269      print(f'(resample: splitting coords into blocks {block_shape}).')
3270    coord_blocks = _split_array_into_blocks(coords, block_shape)
3271
3272    def process_block(coord_block: _NDArray) -> _Array:
3273      return resample(
3274          typing.cast(Any, array),
3275          coord_block,
3276          gridtype=gridtype2,
3277          boundary=boundary2,
3278          cval=cval,
3279          filter=filter2,
3280          prefilter=prefilter2,
3281          src_gamma='identity',
3282          dst_gamma=dst_gamma2,
3283          jacobian=None,  # (It would have to be split into blocks, but it is currently unused.)
3284          precision=precision,
3285          dtype=dtype,
3286          max_block_size=_MAX_BLOCK_SIZE_RECURSING,
3287      )
3288
3289    result_blocks = _map_function_over_blocks(coord_blocks, process_block)
3290    array = _merge_array_from_blocks(result_blocks)
3291    return array
3292
3293  # A concrete example of upsampling:
3294  #   array = np.ones((5, 7, 3))  # source RGB image has height=5 width=7
3295  #   coords = np.random.default_rng(1).random((8, 9, 2))  # output RGB image has height=8 width=9
3296  #   resample(array, coords, filter=('cubic', 'lanczos3'))
3297  #   grid_shape = 5, 7  grid_ndim = 2
3298  #   resampled_shape = 8, 9  resampled_ndim = 2
3299  #   sample_shape = (3,)
3300  #   src_float_index.shape = 8, 9
3301  #   src_first_index.shape = 8, 9
3302  #   sample_index.shape = (4,) for dim == 0, then (6,) for dim == 1
3303  #   weight = [shape(8, 9, 4), shape(8, 9, 6)]
3304  #   src_index = [shape(8, 9, 4), shape(8, 9, 6)]
3305
3306  # Both:[shape(8, 9, 4), shape(8, 9, 6)]
3307  weight: list[_NDArray] = [np.array([]) for _ in range(grid_ndim)]
3308  src_index: list[_NDArray] = [np.array([]) for _ in range(grid_ndim)]
3309  uses_cval = False
3310
3311  for dim in range(grid_ndim):
3312    src_size = grid_shape[dim]  # scalar
3313    coords_dim = coords[..., dim]  # (8, 9)
3314    radius = filter2[dim].radius  # scalar
3315    num_samples = int(np.ceil(radius * 2))  # scalar
3316
3317    boundary_dim = boundary2[dim]
3318    coords_dim = boundary_dim.preprocess_coordinates(coords_dim)
3319
3320    # Sample positions mapped back to source unit domain [0, 1].
3321    src_float_index = gridtype2[dim].index_from_point(coords_dim, src_size)  # (8, 9)
3322    src_first_index = (
3323        np.floor(src_float_index + (0.5 if num_samples % 2 == 1 else 0.0)).astype(np.int32)
3324        - (num_samples - 1) // 2
3325    )  # (8, 9)
3326
3327    sample_index = np.arange(num_samples, dtype=np.int32)  # (4,) then (6,)
3328    src_index[dim] = src_first_index[..., None] + sample_index  # (8, 9, 4) then (8, 9, 6)
3329    if filter2[dim].name == 'trapezoid':
3330      # (It might require changing the filter radius at every sample.)
3331      raise ValueError('resample() cannot use adaptive `trapezoid` filter.')
3332    if filter2[dim].name == 'impulse':
3333      weight[dim] = np.ones_like(src_index[dim], weight_precision)
3334    else:
3335      x = src_float_index[..., None] - src_index[dim].astype(weight_precision)
3336      weight[dim] = filter2[dim](x).astype(weight_precision, copy=False)
3337      if filter2[dim].name != 'narrowbox' and (
3338          is_minification or not filter2[dim].partition_of_unity
3339      ):
3340        weight[dim] = weight[dim] / weight[dim].sum(axis=-1)[..., None]
3341
3342    src_index[dim], weight[dim] = boundary_dim.fold(
3343        src_index[dim], weight[dim], coords_dim, src_size, gridtype2[dim]
3344    )
3345    if boundary_dim.uses_cval or filter2[dim].name == 'narrowbox':
3346      uses_cval = True
3347
3348  # Gather the samples.
3349
3350  # Recall that src_index = [shape(8, 9, 4), shape(8, 9, 6)].
3351  src_index_expanded = []
3352  for dim in range(grid_ndim):
3353    src_index_dim = np.moveaxis(
3354        src_index[dim].reshape(src_index[dim].shape + (1,) * (grid_ndim - 1)),
3355        resampled_ndim,
3356        resampled_ndim + dim,
3357    )
3358    src_index_expanded.append(src_index_dim)
3359  indices = tuple(src_index_expanded)  # (shape(8, 9, 4, 1), shape(8, 9, 1, 6))
3360  samples = _arr_getitem(array, indices)  # (8, 9, 4, 6, 3)
3361
3362  # Indirectly derive samples.ndim (which is unavailable during Tensorflow grad computation).
3363  samples_ndim = resampled_ndim + grid_ndim + len(sample_shape)
3364
3365  # Compute an Einstein summation over the samples and each of the per-dimension weights.
3366
3367  def label(dims: Iterable[int]) -> str:
3368    return ''.join(chr(ord('a') + i) for i in dims)
3369
3370  operands: list[Any] = [samples]  # (8, 9, 4, 6, 3)
3371  assert samples_ndim < 26  # Letters 'a' through 'z'.
3372  labels = [label(range(samples_ndim))]  # ['abcde']
3373  for dim in range(grid_ndim):
3374    operands.append(weight[dim])  # (8, 9, 4), then (8, 9, 6)
3375    labels.append(label(list(range(resampled_ndim)) + [resampled_ndim + dim]))  # 'abc' then 'abd'
3376  output_label = label(
3377      list(range(resampled_ndim)) + list(range(resampled_ndim + grid_ndim, samples_ndim))
3378  )  # 'abe'
3379  subscripts = ','.join(labels) + '->' + output_label  # 'abcde,abc,abd->abe'
3380  array = _arr_einsum(subscripts, *operands)  # (8, 9, 3)
3381
3382  # Gathering `samples` is the memory bottleneck.  It would be ideal if the gather() and einsum()
3383  # computations could be fused.  In Jax, https://github.com/jax-ml/jax/issues/3206 suggests
3384  # that this may become possible.  In any case, for large outputs it helps to partition the
3385  # evaluation over output tiles (using max_block_size).
3386
3387  if uses_cval:
3388    cval_weight = 1.0 - np.multiply.reduce(
3389        [weight[dim].sum(axis=-1) for dim in range(grid_ndim)]
3390    )  # (8, 9)
3391    cval_weight_reshaped = cval_weight.reshape(cval_weight.shape + (1,) * len(sample_shape))
3392    array += _make_array((cval_weight_reshaped * cval).astype(precision, copy=False), arraylib)
3393
3394  array = dst_gamma2.encode(array, dtype)
3395  return array

Interpolate array (a grid of samples) at specified unit-domain coordinates coords.

The last dimension of coords contains unit-domain coordinates at which to interpolate the domain grid samples in array.

The number of coordinates (coords.shape[-1]) determines how to interpret array: its first coords.shape[-1] dimensions define the grid, and the remaining dimensions describe each grid sample (e.g., scalar, vector, tensor).

Concretely, the grid has shape array.shape[:coords.shape[-1]] and each grid sample has shape array.shape[coords.shape[-1]:].

Examples include:

  • Resample a grayscale image with array.shape = height, width onto a new grayscale image with new.shape = height2, width2 by using coords.shape = height2, width2, 2.

  • Resample an RGB image with array.shape = height, width, 3 onto a new RGB image with new.shape = height2, width2, 3 by using coords.shape = height2, width2, 2.

  • Sample an RGB image at num 2D points along a line segment by using coords.shape = num, 2.

  • Sample an RGB image at a single 2D point by using coords.shape = (2,).

  • Sample a 3D grid of 3x3 Jacobians with array.shape = nz, ny, nx, 3, 3 along a 2D plane by using coords.shape = height, width, 3.

  • Map a grayscale image through a color map by using array.shape = 256, 3 and coords.shape = height, width, 1.

Arguments:
  • array: Regular grid of source sample values, as an array object recognized by ARRAYLIBS. The array must have numeric type. The coordinate dimensions appear first, and each grid sample may have an arbitrary shape. Each grid dimension must be at least 1 for a 'dual' grid or at least 2 for a 'primal' grid.
  • coords: Grid of points at which to resample array. The point coordinates are in the last dimension of coords. The domain associated with the source grid is a unit hypercube, i.e. with a range [0, 1] on each coordinate dimension. The output grid has shape coords.shape[:-1] and each of its grid samples has shape array.shape[coords.shape[-1]:].
  • gridtype: Placement of the samples in the source domain grid for each dimension, specified as either a name in GRIDTYPES or a Gridtype instance. It defaults to 'dual'.
  • boundary: The reconstruction boundary rule for each dimension in coords.shape[-1], specified as either a name in BOUNDARIES or a Boundary instance. The special value 'auto' uses 'reflect' for upsampling and 'clamp' for downsampling. (Currently, resample does not detect downsampling, so 'auto' always uses 'reflect'.)
  • cval: Constant value used beyond the samples by some boundary rules. It must be broadcastable onto the shape array.shape[coords.shape[-1]:]. It is subject to src_gamma.
  • filter: The reconstruction kernel for each dimension in coords.shape[-1], specified as either a filter name in FILTERS or a Filter instance.
  • prefilter: The prefilter kernel for each dimension in coords.shape[:-1], specified as either a filter name in FILTERS or a Filter instance. It is used during downsampling (i.e., minification). If None, it inherits the value of filter. (It is currently unused, because resample does not yet prefilter.)
  • gamma: Component transfer functions (e.g., gamma correction) applied when reading samples from array and when creating output grid samples. It is specified as either a name in GAMMAS or a Gamma instance. If both array.dtype and dtype are uint, the default is 'power2'. If both are non-uint, the default is 'identity'. Otherwise, gamma or src_gamma/dst_gamma must be set. Gamma correction assumes that float values are in the range [0.0, 1.0].
  • src_gamma: Component transfer function used to "decode" array samples. Parameters gamma and src_gamma cannot both be set.
  • dst_gamma: Component transfer function used to "encode" the output samples. Parameters gamma and dst_gamma cannot both be set.
  • jacobian: Optional array, which must be broadcastable onto the shape coords.shape[:-1] + (coords.shape[-1], coords.shape[-1]), storing for each point in the output grid the Jacobian matrix of the map from the unit output domain to the unit source domain. If omitted, it is estimated by computing finite differences on coords. (It is currently unused, as it serves only for prefiltering.)
  • precision: Inexact precision of intermediate computations. If None, it is determined based on array.dtype, coords.dtype, and dtype.
  • dtype: Desired data type of the output array. If None, it is taken to be array.dtype. If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range to the uint range.
  • from_coefficients: If True, array already holds the reconstruction coefficients returned by compute_coefficients (its samples decoded by src_gamma and transformed by the digital filter of filter), so those two steps are skipped; src_gamma still decodes cval.
  • max_block_size: If nonzero, maximum number of grid points in coords before the resampling evaluation gets partitioned into smaller blocks for reduced memory usage and better caching.
  • debug: Show internal information.
Returns:

A new sample grid of shape coords.shape[:-1], represented as an array of shape coords.shape[:-1] + array.shape[coords.shape[-1]:], of the same array library type as the source array.

Example of resample operation:

For reference, the identity resampling for a scalar-valued grid with the default grid-type 'dual' is:

>>> array = np.random.default_rng(1).random((5, 7, 3))
>>> coords = (np.moveaxis(np.indices(array.shape), 0, -1) + 0.5) / array.shape
>>> new_array = resample(array, coords)
>>> assert np.allclose(new_array, array)

It is more efficient to use the function resize for the special case where the coords are obtained as simple scaling and translation of a new regular grid over the source domain:

>>> scale, translate, new_shape = (1.1, 1.2), (0.1, -0.2), (6, 8)
>>> coords = (np.moveaxis(np.indices(new_shape), 0, -1) + 0.5) / new_shape
>>> coords = (coords - translate) / scale
>>> resampled = resample(array, coords)
>>> resized = resize(array, new_shape, scale=scale, translate=translate)
>>> assert np.allclose(resampled, resized)
def resample_affine( array: Array, /, shape: Iterable[int], matrix: ArrayLike, *, gridtype: str | Gridtype | None = None, src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None, filter: str | Filter | Iterable[str | Filter] = 'lanczos3', prefilter: str | Filter | Iterable[str | Filter] | None = None, precision: DTypeLike | None = None, dtype: DTypeLike | None = None, **kwargs: Any) -> Array:
3398def resample_affine(
3399    array: _Array,
3400    /,
3401    shape: Iterable[int],
3402    matrix: _ArrayLike,
3403    *,
3404    gridtype: str | Gridtype | None = None,
3405    src_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
3406    dst_gridtype: str | Gridtype | Iterable[str | Gridtype] | None = None,
3407    filter: str | Filter | Iterable[str | Filter] = _DEFAULT_FILTER,
3408    prefilter: str | Filter | Iterable[str | Filter] | None = None,
3409    precision: _DTypeLike | None = None,
3410    dtype: _DTypeLike | None = None,
3411    **kwargs: Any,
3412) -> _Array:
3413  """Resample a source array using an affinely transformed grid of given shape.
3414
3415  The `matrix` transformation can be linear,
3416    `source_point = matrix @ destination_point`,
3417  or it can be affine where the last matrix column is an offset vector,
3418    `source_point = matrix @ (destination_point, 1.0)`.
3419
3420  Args:
3421    array: Regular grid of source sample values, as an array object recognized by `ARRAYLIBS`.
3422      The array must have numeric type.  The number of grid dimensions is determined from
3423      `matrix.shape[0]`; the remaining dimensions are for each sample value and are all
3424      linearly interpolated.
3425    shape: Dimensions of the desired destination grid.  The number of destination grid dimensions
3426      may be different from that of the source grid.
3427    matrix: 2D array for a linear or affine transform from unit-domain destination points
3428      (in a space with `len(shape)` dimensions) into unit-domain source points (in a space with
3429      `matrix.shape[0]` dimensions).  If the matrix has `len(shape) + 1` columns, the last column
3430      is the affine offset (i.e., translation).
3431    gridtype: Placement of samples on all dimensions of both the source and output domain grids,
3432      specified as either a name in `GRIDTYPES` or a `Gridtype` instance.  It defaults to `'dual'`
3433      if `gridtype`, `src_gridtype`, and `dst_gridtype` are all kept `None`.
3434    src_gridtype: Placement of samples in the source domain grid for each dimension.
3435      Parameters `gridtype` and `src_gridtype` cannot both be set.
3436    dst_gridtype: Placement of samples in the output domain grid for each dimension.
3437      Parameters `gridtype` and `dst_gridtype` cannot both be set.
3438    filter: The reconstruction kernel for each dimension in `matrix.shape[0]`, specified as either
3439      a filter name in `FILTERS` or a `Filter` instance.
3440    prefilter: The prefilter kernel for each dimension in `len(shape)`, specified as either
3441      a filter name in `FILTERS` or a `Filter` instance.  It is used during downsampling
3442      (i.e., minification).  If `None`, it inherits the value of `filter`.
3443    precision: Inexact precision of intermediate computations.  If `None`, it is determined based
3444      on `array.dtype` and `dtype`.
3445    dtype: Desired data type of the output array.  If `None`, it is taken to be `array.dtype`.
3446      If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range
3447      to the uint range.
3448    **kwargs: Additional parameters for `resample` function.
3449
3450  Returns:
3451    An array of the same class as the source `array`, representing a grid with specified `shape`,
3452    where each grid value is resampled from `array`.  Thus the shape of the returned array is
3453    `shape + array.shape[matrix.shape[0]:]`.
3454  """
3455  shape = tuple(shape)
3456  matrix = np.asarray(matrix)
3457  dst_ndim = len(shape)
3458  if matrix.ndim != 2:
3459    raise ValueError(f'Array {matrix} is not a 2D matrix.')
3460  src_ndim = matrix.shape[0]
3461  # grid_shape = array.shape[:src_ndim]
3462  is_affine = matrix.shape[1] == dst_ndim + 1
3463  if src_ndim > len(_arr_shape(array)):
3464    raise ValueError(
3465        f'Matrix {matrix} has more rows ({matrix.shape[0]}) than ndim in'
3466        f' array.shape={_arr_shape(array)}.'
3467    )
3468  if matrix.shape[1] != dst_ndim and not is_affine:
3469    raise ValueError(
3470        f'Matrix has {matrix.shape=}, but we expect either {dst_ndim} or {dst_ndim + 1} columns.'
3471    )
3472  src_gridtype2, dst_gridtype2 = _get_gridtypes(
3473      gridtype, src_gridtype, dst_gridtype, src_ndim, dst_ndim
3474  )
3475  prefilter = filter if prefilter is None else prefilter
3476  filter2 = [_get_filter(f) for f in np.broadcast_to(np.array(filter), src_ndim)]
3477  prefilter2 = [_get_filter(f) for f in np.broadcast_to(np.array(prefilter), src_ndim)]
3478  del src_gridtype, dst_gridtype, filter, prefilter
3479  dtype = _arr_dtype(array) if dtype is None else np.dtype(dtype)
3480  precision = _get_precision(precision, [_arr_dtype(array), dtype], [])
3481  weight_precision = _real_precision(precision)
3482
3483  dst_position_list = []  # per dimension
3484  for dim in range(dst_ndim):
3485    dst_size = shape[dim]
3486    dst_index = np.arange(dst_size, dtype=weight_precision)
3487    dst_position_list.append(dst_gridtype2[dim].point_from_index(dst_index, dst_size))
3488  dst_position = np.meshgrid(*dst_position_list, indexing='ij')
3489
3490  linear_matrix = matrix[:, :-1] if is_affine else matrix
3491  src_position = np.tensordot(linear_matrix, dst_position, 1)
3492  coords = np.moveaxis(src_position, 0, -1)
3493  if is_affine:
3494    coords += matrix[:, -1]
3495
3496  # TODO: Based on grid_shape, shape, linear_matrix, and prefilter, determine a
3497  # convolution prefilter and apply it to bandlimit 'array', using boundary for padding.
3498
3499  return resample(
3500      array,
3501      coords,
3502      gridtype=src_gridtype2,
3503      filter=filter2,
3504      prefilter=prefilter2,
3505      precision=precision,
3506      dtype=dtype,
3507      **kwargs,
3508  )

Resample a source array using an affinely transformed grid of given shape.

The matrix transformation can be linear, source_point = matrix @ destination_point, or it can be affine where the last matrix column is an offset vector, source_point = matrix @ (destination_point, 1.0).

Arguments:
  • array: Regular grid of source sample values, as an array object recognized by ARRAYLIBS. The array must have numeric type. The number of grid dimensions is determined from matrix.shape[0]; the remaining dimensions are for each sample value and are all linearly interpolated.
  • shape: Dimensions of the desired destination grid. The number of destination grid dimensions may be different from that of the source grid.
  • matrix: 2D array for a linear or affine transform from unit-domain destination points (in a space with len(shape) dimensions) into unit-domain source points (in a space with matrix.shape[0] dimensions). If the matrix has len(shape) + 1 columns, the last column is the affine offset (i.e., translation).
  • gridtype: Placement of samples on all dimensions of both the source and output domain grids, specified as either a name in GRIDTYPES or a Gridtype instance. It defaults to 'dual' if gridtype, src_gridtype, and dst_gridtype are all kept None.
  • src_gridtype: Placement of samples in the source domain grid for each dimension. Parameters gridtype and src_gridtype cannot both be set.
  • dst_gridtype: Placement of samples in the output domain grid for each dimension. Parameters gridtype and dst_gridtype cannot both be set.
  • filter: The reconstruction kernel for each dimension in matrix.shape[0], specified as either a filter name in FILTERS or a Filter instance.
  • prefilter: The prefilter kernel for each dimension in len(shape), specified as either a filter name in FILTERS or a Filter instance. It is used during downsampling (i.e., minification). If None, it inherits the value of filter.
  • precision: Inexact precision of intermediate computations. If None, it is determined based on array.dtype and dtype.
  • dtype: Desired data type of the output array. If None, it is taken to be array.dtype. If it is a uint type, the intermediate float values are rescaled from the [0.0, 1.0] range to the uint range.
  • **kwargs: Additional parameters for resample function.
Returns:

An array of the same class as the source array, representing a grid with specified shape, where each grid value is resampled from array. Thus the shape of the returned array is shape + array.shape[matrix.shape[0]:].

def rotation_about_center_in_2d( src_shape: ArrayLike, /, angle: float, *, new_shape: ArrayLike | None = None, scale: float = 1.0) -> np.ndarray:
3538def rotation_about_center_in_2d(
3539    src_shape: _ArrayLike,
3540    /,
3541    angle: float,
3542    *,
3543    new_shape: _ArrayLike | None = None,
3544    scale: float = 1.0,
3545) -> _NDArray:
3546  """Return the 3x3 matrix mapping the destination unit domain into the source unit domain.
3547
3548  The returned matrix accounts for the possibly non-square domain shapes.
3549
3550  Args:
3551    src_shape: Resolution `(ny, nx)` of the source domain grid.
3552    angle: Angle in radians (positive from x to y axis) applied when mapping the source domain
3553      onto the destination domain.
3554    new_shape: Resolution `(ny, nx)` of the destination domain grid; it defaults to `src_shape`.
3555    scale: Scaling factor applied when mapping the source domain onto the destination domain.
3556  """
3557
3558  def translation_matrix(vector: _NDArray) -> _NDArray:
3559    matrix = np.eye(len(vector) + 1)
3560    matrix[:-1, -1] = vector
3561    return matrix
3562
3563  def scaling_matrix(scale: _NDArray) -> _NDArray:
3564    return np.diag(tuple(scale) + (1.0,))
3565
3566  def rotation_matrix_2d(angle: float) -> _NDArray:
3567    cos, sin = np.cos(angle), np.sin(angle)
3568    return np.array([[cos, sin, 0], [-sin, cos, 0], [0, 0, 1]])
3569
3570  src_shape = np.asarray(src_shape)
3571  new_shape = src_shape if new_shape is None else np.asarray(new_shape)
3572  _check_eq(src_shape.shape, (2,))
3573  _check_eq(new_shape.shape, (2,))
3574  half = np.array([0.5, 0.5])
3575  matrix = (
3576      translation_matrix(half)
3577      @ scaling_matrix(min(src_shape) / src_shape)
3578      @ rotation_matrix_2d(angle)
3579      @ scaling_matrix(scale * new_shape / min(new_shape))
3580      @ translation_matrix(-half)
3581  )
3582  assert np.allclose(matrix[-1], [0.0, 0.0, 1.0])
3583  return matrix

Return the 3x3 matrix mapping the destination unit domain into the source unit domain.

The returned matrix accounts for the possibly non-square domain shapes.

Arguments:
  • src_shape: Resolution (ny, nx) of the source domain grid.
  • angle: Angle in radians (positive from x to y axis) applied when mapping the source domain onto the destination domain.
  • new_shape: Resolution (ny, nx) of the destination domain grid; it defaults to src_shape.
  • scale: Scaling factor applied when mapping the source domain onto the destination domain.
def rotate_image_about_center( image: Array, /, angle: float, *, new_shape: ArrayLike | None = None, scale: float = 1.0, num_rotations: int = 1, **kwargs: Any) -> Array:
3586def rotate_image_about_center(
3587    image: _Array,
3588    /,
3589    angle: float,
3590    *,
3591    new_shape: _ArrayLike | None = None,
3592    scale: float = 1.0,
3593    num_rotations: int = 1,
3594    **kwargs: Any,
3595) -> _Array:
3596  """Return a copy of `image` rotated about its center.
3597
3598  Args:
3599    image: Source grid samples; the first two dimensions are spatial (ny, nx).
3600    angle: Angle in radians (positive from x to y axis) applied when mapping the source domain
3601      onto the destination domain.
3602    new_shape: Resolution `(ny, nx)` of the output grid; it defaults to `image.shape[:2]`.
3603    scale: Scaling factor applied when mapping the source domain onto the destination domain.
3604    num_rotations: Number of rotations (each by `angle`).  Successive resamplings are useful in
3605      analyzing the filtering quality.
3606    **kwargs: Additional parameters for `resample_affine`.
3607  """
3608  new_shape = _arr_shape(image)[:2] if new_shape is None else np.asarray(new_shape)
3609  for _ in range(num_rotations):
3610    src_shape = _arr_shape(image)[:2]  # It becomes new_shape after the first rotation.
3611    matrix = rotation_about_center_in_2d(src_shape, angle, new_shape=new_shape, scale=scale)
3612    image = resample_affine(image, new_shape, matrix[:-1], **kwargs)
3613  return image

Return a copy of image rotated about its center.

Arguments:
  • image: Source grid samples; the first two dimensions are spatial (ny, nx).
  • angle: Angle in radians (positive from x to y axis) applied when mapping the source domain onto the destination domain.
  • new_shape: Resolution (ny, nx) of the output grid; it defaults to image.shape[:2].
  • scale: Scaling factor applied when mapping the source domain onto the destination domain.
  • num_rotations: Number of rotations (each by angle). Successive resamplings are useful in analyzing the filtering quality.
  • **kwargs: Additional parameters for resample_affine.