resampler
resampler: fast differentiable resizing and warping of arbitrary grids.
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, andjax);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
resizedownsampling;efficient backpropagation of gradients for
torchandjax;few dependencies (only
numpyandscipy) and no C extension code, yetfaster 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=Nonewhich by default uses the'power2'transfer function for theuint8image in the second example,scale=1.0, translate=0.0(no domain transformation),- default
precisionand outputdtype.
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
resizeimplements prefiltering,resampledoes 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/> | 1064| --- |:---:|:---:| 1065| Sample positions in 2D<br/>and in 1D at different resolutions |  |  | 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:
Array libraries supported automatically in the resize and resampling operations.
The library is selected automatically based on the type of the
arrayfunction parameter.The class
_Arraylibprovides library-specific implementations of needed basic functions.The
_arr_*()functions dispatch the_Arraylibmethods based on the array type.
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.
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 |
![]() |
![]() |
| 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.
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.
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:
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/.
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.
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.
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.
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, widthand resizing it withlen(shape) == 2produces a new image of scalar values. - An RGB image has
array.shape = height, width, 3and resizing it withlen(shape) == 2produces a new image of RGB values. - A 3D grid of 3x3 Jacobians has
array.shape = Z, Y, X, 3, 3and resizing it withlen(shape) == 3produces 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 firstlen(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
arraymust have at least as many dimensions aslen(shape). - gridtype: Placement of samples on all dimensions of both the source and output domain grids,
specified as either a name in
GRIDTYPESor aGridtypeinstance. It defaults to'dual'ifgridtype,src_gridtype, anddst_gridtypeare all keptNone. - src_gridtype: Placement of the samples in the source domain grid for each dimension.
Parameters
gridtypeandsrc_gridtypecannot both be set. - dst_gridtype: Placement of the samples in the output domain grid for each dimension.
Parameters
gridtypeanddst_gridtypecannot both be set. - boundary: The reconstruction boundary rule for each dimension in
shape, specified as either a name inBOUNDARIESor aBoundaryinstance. 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 tosrc_gamma. - filter: The reconstruction kernel for each dimension in
shape, specified as either a filter name inFILTERSor aFilterinstance. It is used during upsampling (i.e., magnification). - prefilter: The prefilter kernel for each dimension in
shape, specified as either a filter name inFILTERSor aFilterinstance. It is used during downsampling (i.e., minification). IfNone, it inherits the value offilter. 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
arrayand when creating output grid samples. It is specified as either a name inGAMMASor aGammainstance. If botharray.dtypeanddtypeareuint, the default is'power2'. If both are non-uint, the default is'identity'. Otherwise,gammaorsrc_gamma/dst_gammamust be set. Gamma correction assumes that float values are in the range [0.0, 1.0]. - src_gamma: Component transfer function used to "decode"
arraysamples. Parametersgammaandsrc_gammacannot both be set. - dst_gamma: Component transfer function used to "encode" the output samples.
Parameters
gammaanddst_gammacannot 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 onarray.dtypeanddtype. - dtype: Desired data type of the output array. If
None, it is taken to bearray.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
arrayis fromnumpy. 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 shapeshape + array.shape[len(shape):]and data typedtype.
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])
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.
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
arraymust have at least as many dimensions aslen(shape). - object_fit: Like CSS
object-fit. If'contain',arrayis resized uniformly to fit withinshape. If'cover',arrayis resized to fully covershape. - 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 inBOUNDARIESor aBoundaryinstance. The default is'natural', which assignscvalto 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
resizefunction (includingcval).
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]])
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_ndimdimensions define the grid. - grid_ndim: Number of grid dimensions (
coords.shape[-1]in the later calls toresample). - 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"
arraysamples, as inresample. - precision: Inexact precision of the coefficients. If
None, it is determined based on thearraydtype as inresample.
Returns:
An array of floating-point coefficients with the shape of
arrayand the same array library type as the source 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, widthonto a new grayscale image withnew.shape = height2, width2by usingcoords.shape = height2, width2, 2.Resample an RGB image with
array.shape = height, width, 3onto a new RGB image withnew.shape = height2, width2, 3by usingcoords.shape = height2, width2, 2.Sample an RGB image at
num2D points along a line segment by usingcoords.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, 3along a 2D plane by usingcoords.shape = height, width, 3.Map a grayscale image through a color map by using
array.shape = 256, 3andcoords.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 ofcoords. 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 shapecoords.shape[:-1]and each of its grid samples has shapearray.shape[coords.shape[-1]:]. - gridtype: Placement of the samples in the source domain grid for each dimension, specified as
either a name in
GRIDTYPESor aGridtypeinstance. It defaults to'dual'. - boundary: The reconstruction boundary rule for each dimension in
coords.shape[-1], specified as either a name inBOUNDARIESor aBoundaryinstance. The special value'auto'uses'reflect'for upsampling and'clamp'for downsampling. (Currently,resampledoes 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 tosrc_gamma. - filter: The reconstruction kernel for each dimension in
coords.shape[-1], specified as either a filter name inFILTERSor aFilterinstance. - prefilter: The prefilter kernel for each dimension in
coords.shape[:-1], specified as either a filter name inFILTERSor aFilterinstance. It is used during downsampling (i.e., minification). IfNone, it inherits the value offilter. (It is currently unused, becauseresampledoes not yet prefilter.) - gamma: Component transfer functions (e.g., gamma correction) applied when reading samples
from
arrayand when creating output grid samples. It is specified as either a name inGAMMASor aGammainstance. If botharray.dtypeanddtypeareuint, the default is'power2'. If both are non-uint, the default is'identity'. Otherwise,gammaorsrc_gamma/dst_gammamust be set. Gamma correction assumes that float values are in the range [0.0, 1.0]. - src_gamma: Component transfer function used to "decode"
arraysamples. Parametersgammaandsrc_gammacannot both be set. - dst_gamma: Component transfer function used to "encode" the output samples.
Parameters
gammaanddst_gammacannot 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 oncoords. (It is currently unused, as it serves only for prefiltering.) - precision: Inexact precision of intermediate computations. If
None, it is determined based onarray.dtype,coords.dtype, anddtype. - dtype: Desired data type of the output array. If
None, it is taken to bearray.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,
arrayalready holds the reconstruction coefficients returned bycompute_coefficients(its samples decoded bysrc_gammaand transformed by the digital filter offilter), so those two steps are skipped;src_gammastill decodescval. - max_block_size: If nonzero, maximum number of grid points in
coordsbefore 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 shapecoords.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)
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 frommatrix.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 withmatrix.shape[0]dimensions). If the matrix haslen(shape) + 1columns, 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
GRIDTYPESor aGridtypeinstance. It defaults to'dual'ifgridtype,src_gridtype, anddst_gridtypeare all keptNone. - src_gridtype: Placement of samples in the source domain grid for each dimension.
Parameters
gridtypeandsrc_gridtypecannot both be set. - dst_gridtype: Placement of samples in the output domain grid for each dimension.
Parameters
gridtypeanddst_gridtypecannot both be set. - filter: The reconstruction kernel for each dimension in
matrix.shape[0], specified as either a filter name inFILTERSor aFilterinstance. - prefilter: The prefilter kernel for each dimension in
len(shape), specified as either a filter name inFILTERSor aFilterinstance. It is used during downsampling (i.e., minification). IfNone, it inherits the value offilter. - precision: Inexact precision of intermediate computations. If
None, it is determined based onarray.dtypeanddtype. - dtype: Desired data type of the output array. If
None, it is taken to bearray.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
resamplefunction.
Returns:
An array of the same class as the source
array, representing a grid with specifiedshape, where each grid value is resampled fromarray. Thus the shape of the returned array isshape + array.shape[matrix.shape[0]:].
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 tosrc_shape. - scale: Scaling factor applied when mapping the source domain onto the destination domain.
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 toimage.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.


upsampled




