Source code for healpix_resample.bicubic

"""
bicubic.py

Radial cubic-convolution ("bicubic") HEALPix resampler built on top of
KNeighborsResampler.

Core idea:
- Generalize Keys' cubic convolution kernel (the interpolation kernel behind
  `cv2.INTER_CUBIC` / `PIL.Image.BICUBIC` on regular pixel grids) to
  unstructured samples by evaluating it *radially*: replace the structured
  `(fx, fy)` fractional pixel offset with the existing geodesic distance
  `self.d_m` and length scale `self.sigma_m` already used by every other
  resampler in this package (see `planning/01_bicubic_resampler.md`).
- Reuse the exact same normalize-and-sparsify machinery as
  `BilinearResampler`/`KNeighborsResampler.comp_matrix()` — only the weight
  formula `w` (`_link_weights()`) and the normalisation guards change.

This module is designed for large N and batched values (B,N) on CUDA.
"""
from typing import Optional

from healpix_resample.base import ResampleResults, T_Array
from healpix_resample.knn import KNeighborsResampler, _conservative_resample
import math
import numpy as np
import torch


[docs] class BicubicResampler(KNeighborsResampler): """Radial cubic-convolution HEALPix resampler. Sits between `BilinearResampler` (`Npt=4`, inverse-distance weighted) and `PSFResampler` (iterative CG deconvolution): a fixed, non-iterative local interpolation using more neighbours than bilinear, built purely from `comp_matrix()` — no CG solve involved. Weight function ---------------- Keys' cubic convolution kernel with `a = -0.5` (the common default, matching `PIL`/`cv2`), applied to the radial distance `u = self.d_m / s` in place of a structured pixel offset:: w(u) = (a+2)|u|^3 - (a+3)|u|^2 + 1 for |u| <= 1 = a|u|^3 - 5a|u|^2 + 8a|u| - 4a for 1 < |u| < 2 = 0 for |u| >= 2 Unlike the Gaussian/inverse-distance weights used by `BilinearResampler` and `PSFResampler`, this kernel is *signed* — it goes negative for `1 < |u| < 2`, which is exactly what gives cubic convolution its sharpening property relative to bilinear. Kernel scale ------------ Keys' kernel is defined in units of the *input* grid spacing: its negative lobe `1 < |u| < 2` must fall on the second ring of samples. The scale of each link is therefore `s = max(sigma_m, h)`, where `h` is the spacing of the link's sample (``sample_spacing_m`` below). When the samples are finer than the cells (downsampling) `sigma_m` wins, as before. When they are coarser (upsampling), scaling by the output cell size alone put the nearest samples in the negative lobe: the weights of a cell then cancelled, and the normalisation amplified them up to thousands of times, which gave values far outside the input range. Two further consequences of the signed kernel: - A cell whose links still cancel strongly (`sum|w| > 3 |sum w|`, e.g. on scattered samples) uses only the positive lobe of its links (their absolute values if it has no positive weight), so its value stays a weighted average of its samples. `_norm_col()` / `_norm_row()` keep a last floor on the normalising sums (relative to the *unsigned* accumulated weight), see the inline comments on `_norm_col()`. - `invert()` (inherited from `KNeighborsResampler`, `hval @ self.MT`) can genuinely overshoot/ring outside the local sample-value range — this is expected cubic-convolution behaviour, not a bug. Parameters ---------- Npt : int Number of HEALPix neighbours per source sample used by the KNN. Keys' kernel has support `|u| < 2`, roughly twice the reach of bilinear's `|u| < 1`-ish support, so the natural analogue of the classic 4x4 bicubic stencil on a structured grid is `Npt = 16` (default). All other parameters are forwarded to `KNeighborsResampler`. Parameters ---------- area : array-like or None Per-sample pixel area/weight, shape ``(N,)``. Only used by ``resample(conservative=True)`` -- ignored by the default interpolation path. Defaults to ``1.0`` for every sample. See ``resample()``'s docstring for the conservation guarantee and its one caveat specific to this class's signed kernel. sample_spacing_m : float, array-like or None Spacing of the input samples in metres, a scalar or one value per sample ``(N,)``; sets the kernel scale ``max(sigma_m, h)`` (see "Kernel scale"). ``None`` (default) estimates it as the distance of each sample to its nearest other sample (a ``scipy`` k-d tree on the unit vectors, queried in slices of ``batch_size`` when given). On a regular grid that is the grid spacing; pass it explicitly to skip the estimate on very large inputs. """
[docs] def __init__( self, *args, Npt: int = 16, area: Optional[T_Array] = None, sample_spacing_m=None, **kwargs, ): lon_deg = kwargs["lon_deg"] if "lon_deg" in kwargs else args[0] lat_deg = kwargs["lat_deg"] if "lat_deg" in kwargs else args[1] n = int(lon_deg.numel()) if isinstance(lon_deg, torch.Tensor) else int(np.asarray(lon_deg).size) if sample_spacing_m is None: spacing = _nearest_sample_distance_m( lon_deg, lat_deg, radius=float(kwargs.get("radius", 6371000.0)), batch_size=kwargs.get("batch_size"), ) else: spacing = np.broadcast_to(np.asarray(sample_spacing_m, dtype=np.float64).reshape(-1), (n,)) if not np.all(np.isfinite(spacing) & (spacing >= 0)): raise ValueError("sample_spacing_m must be finite and non-negative") # read by _link_weights() while super().__init__() builds M self._sample_spacing = np.ascontiguousarray(spacing, dtype=np.float64) # Ensure ring_search_max >= ring_search_init(Npt) so the KNN search # loop in healpix_weighted_nearest actually executes. # # healpix_weighted_nearest computes: # r_min = ceil((sqrt(Npt) - 1) / 2) # ring_search_init = max(1, r_min + 1) # # KNeighborsResampler's default ring_search_max=2 is too small for # Npt >= 16 (needs ring_search_init=3). Auto-correct here only when # the caller has not supplied ring_search_max explicitly — copied # from NearestResampler.__init__ (nearest.py:67-84). if "ring_search_max" not in kwargs: r_min = int(math.ceil((math.sqrt(Npt) - 1.0) / 2.0)) ring_search_init_needed = max(1, r_min + 1) # +2 margin so the loop has room to grow and find Npt candidates kwargs["ring_search_max"] = ring_search_init_needed + 2 super().__init__(*args, Npt=Npt, **kwargs) if area is None: area_t = torch.ones(self.N, dtype=self.dtype, device=self.device) else: area_t = area if isinstance(area, torch.Tensor) else torch.as_tensor(area) area_t = area_t.to(self.device, dtype=self.dtype).reshape(-1) if area_t.numel() != self.N: raise ValueError( f"area must have {self.N} elements (one per sample), got {area_t.numel()}" ) if torch.any(area_t < 0): raise ValueError("area must be non-negative") self.area = area_t
def _distance_weights(self, d: torch.Tensor, rows: Optional[torch.Tensor] = None) -> torch.Tensor: # Keys' cubic convolution kernel (a=-0.5) on the radial distance # u = d / s, s = max(sigma_m, spacing of the link's sample) (see # "Kernel scale" in the class docstring), before the cancellation # guard of `_all_link_weights`. a = -0.5 spacing = torch.as_tensor(self._sample_spacing, device=d.device, dtype=d.dtype) scale = torch.clamp(spacing, min=self.sigma_m) scale = scale[:, None] if rows is None else scale[rows] # (N, 1) or (T,) u = (d / scale).abs() u2 = u * u u3 = u2 * u w_inner = (a + 2.0) * u3 - (a + 3.0) * u2 + 1.0 w_outer = a * u3 - 5.0 * a * u2 + 8.0 * a * u - 4.0 * a zero = torch.zeros_like(u) return torch.where(u <= 1.0, w_inner, torch.where(u < 2.0, w_outer, zero)) def _link_weights(self) -> torch.Tensor: return self._all_link_weights()[0] def _tie_weights(self) -> torch.Tensor: return self._all_link_weights()[1] def _all_link_weights(self): # `M`, `MT` and `M_cons` are assembled by `KNeighborsResampler` # (`MT` / `M_cons` on first access) from these weights. return self._limit_cancellation( self._distance_weights(self.d_m), self._distance_weights(self.tie_d, self.tie_rows) ) def _limit_cancellation(self, w: torch.Tensor, w_tie: torch.Tensor): # A cell whose signed weights still cancel strongly (sum|w| larger # than _MAX_CANCELLATION times |sum w|) would be amplified by the # per-cell normalisation. Its links use the positive lobe only # (their absolute values if the cell has no positive weight), so # that cell's value is a weighted average of its samples. The tied # links (`tie_hi`, weights `w_tie`) count like the others. valid = self.hi >= 0 cols = self.hi[valid] wv = w[valid] signed = torch.bincount(cols, weights=wv, minlength=self.K) unsigned = torch.bincount(cols, weights=wv.abs(), minlength=self.K) positive = torch.bincount(cols, weights=wv.clamp(min=0), minlength=self.K) if self.tie_hi.numel(): signed.index_add_(0, self.tie_hi, w_tie.to(signed.dtype)) unsigned.index_add_(0, self.tie_hi, w_tie.abs().to(unsigned.dtype)) positive.index_add_(0, self.tie_hi, w_tie.clamp(min=0).to(positive.dtype)) bad_cell = unsigned > _MAX_CANCELLATION * signed.abs() if not bool(bad_cell.any()): return w, w_tie has_positive_cell = positive > 0 bad = torch.zeros_like(valid) bad[valid] = bad_cell[cols] has_positive = torch.zeros_like(valid) has_positive[valid] = has_positive_cell[cols] fallback = torch.where(has_positive, w.clamp(min=0), w.abs()) w = torch.where(bad, fallback, w) fallback_tie = torch.where(has_positive_cell[self.tie_hi], w_tie.clamp(min=0), w_tie.abs()) w_tie = torch.where(bad_cell[self.tie_hi], fallback_tie, w_tie) return w, w_tie # Unlike the nonnegative Gaussian/IDW weights used by every other # resampler, Keys' kernel is signed, so a per-cell sum norm_col[k] (or a # per-sample sum norm_row[i]) can land close to zero purely from # cancellation between the positive central lobe and the negative outer # lobe (rather than every contributing weight being individually small). # Dividing by such a sum would blow up or flip sign unpredictably. Guard # it with a floor set relative to the *unsigned* accumulated weight # (same area-independent pattern as `norm_col_raw` in # `psf.py:comp_matrix`) -- rather than an absolute epsilon, so the guard # scales correctly across different sigma/threshold configs. This only # clamps the handful of pathologically-cancelled rows/columns; # well-conditioned cells are unaffected (float precision only matters # when the sum is already tiny relative to the unsigned one). Cells this # severe are inherently borderline -- `threshold` (applied upstream # against the unsigned Gaussian weight in `healpix_weighted_nearest`) is # the primary safeguard against weakly-supported cells in the first # place; this is a secondary, purely numerical safety net. def _norm_col(self, cols: torch.Tensor, w: torch.Tensor, tie_cols: Optional[torch.Tensor] = None, tie_w: Optional[torch.Tensor] = None) -> torch.Tensor: norm_col = torch.bincount(cols, weights=w, minlength=self.K) norm_col_raw = torch.bincount(cols, weights=w.abs(), minlength=self.K) if tie_cols is not None and tie_cols.numel(): norm_col.index_add_(0, tie_cols, tie_w.to(norm_col.dtype)) norm_col_raw.index_add_(0, tie_cols, tie_w.abs().to(norm_col_raw.dtype)) return _floor_signed(norm_col.to(self.dtype), norm_col_raw.to(self.dtype)) def _norm_row(self, rows: torch.Tensor, w: torch.Tensor) -> torch.Tensor: norm_row = torch.bincount(rows, weights=w, minlength=self.N).to(self.dtype) norm_row_raw = torch.bincount(rows, weights=w.abs(), minlength=self.N).to(self.dtype) return _floor_signed(norm_row, norm_row_raw) @torch.no_grad() def resample(self, val: T_Array, *, conservative: bool = False, **kwargs) -> ResampleResults[T_Array]: """Estimate the HEALPix field from unstructured samples. Args: val: (N,) or (B, N) values at lon/lat sample points. conservative: see below. Extra ``**kwargs`` are accepted for signature symmetry with other resamplers and forwarded to ``KNeighborsResampler.resample()`` when ``conservative=False`` (no CG solve involved either way); ignored when ``conservative=True``. ``conservative=True`` (issue #44: "conservative bi-linear", applied here to bicubic too) -------------------------------------------------------------------- Same idea as ``BilinearResampler.resample()``: each sample's own (``area``-weighted) value is redistributed across its ``Npt`` nearest cells using ``self.M_cons`` -- Keys' kernel weights, normalized so each sample's own weights sum to 1 instead of being normalized per output cell -- guaranteeing sum_k hval[k] == sum_i (valid i) val[i] * area[i] See ``BilinearResampler.resample()`` for the full NaN-handling discussion (identical here: a NaN sample's value and area are both excluded, and the identity above then holds over exactly the valid samples; an all-NaN row comes back entirely ``nan``). Caveat specific to this class's signed kernel ------------------------------------------------ Unlike ``BilinearResampler``'s non-negative inverse-distance weights, Keys' cubic kernel is signed, so ``self.M_cons``'s per-sample rows only sum to *exactly* 1 for samples whose ``norm_row`` wasn't floored by ``_floor_signed`` in ``_norm_row()`` -- true for the vast majority of well-conditioned samples. For the rare, pathologically-cancelled sample that does hit the floor, that sample's own contribution to the conservation identity above is only approximate (to the extent the floor perturbed its normalization), not bit-exact -- the same accepted trade-off ``_floor_signed`` already makes for ordinary (non-conservative) interpolation. Returns: hval: (B, K) or (K,) """ if not conservative: return super().resample(val, **kwargs) return _conservative_resample(self, val, self.area)
# Largest accepted sum|w| / |sum w| of a cell's Keys weights; see # BicubicResampler._limit_cancellation. Well-conditioned cells on a grid stay # below it: for Keys' kernel, sum|w| / sum w is at most 1.25 per axis (half a # pixel offset), about 1.56 for the 4x4 stencil. _MAX_CANCELLATION = 3.0 def _nearest_sample_distance_m(lon_deg, lat_deg, *, radius: float, batch_size=None) -> np.ndarray: """Distance (m) from each sample to its nearest other sample, ``(N,)``. Chord length between unit vectors (equal to the arc length at these distances) times ``radius``, from a ``scipy`` k-d tree; the query runs in slices of ``batch_size`` samples when given. Duplicated samples get the distance to the nearest *distinct* sample; a single sample gets 0. """ from scipy.spatial import cKDTree lon = np.radians(np.asarray(lon_deg.cpu() if isinstance(lon_deg, torch.Tensor) else lon_deg, dtype=np.float64).reshape(-1)) lat = np.radians(np.asarray(lat_deg.cpu() if isinstance(lat_deg, torch.Tensor) else lat_deg, dtype=np.float64).reshape(-1)) n = lon.size out = np.zeros(n, dtype=np.float64) if n < 2: return out xyz = np.stack([np.cos(lat) * np.cos(lon), np.cos(lat) * np.sin(lon), np.sin(lat)], axis=1) tree = cKDTree(xyz) step = n if batch_size is None else max(1, int(batch_size)) for s in range(0, n, step): q = xyz[s : s + step] # k=2: the first neighbour is the sample itself (or a duplicate) d, _ = tree.query(q, k=2, workers=-1) nearest = d[:, 1] dup = nearest == 0 if dup.any(): # duplicates: look further for the first non-zero distance dd, _ = tree.query(q[dup], k=min(n, 16), workers=-1) dd = np.where(dd > 0, dd, np.inf).min(axis=1) nearest[dup] = np.where(np.isfinite(dd), dd, 0.0) out[s : s + step] = nearest return out * radius def _floor_signed(norm: torch.Tensor, norm_raw: torch.Tensor, rel_floor: float = 1e-3) -> torch.Tensor: """Clamp ``|norm|`` away from zero (preserving sign) relative to ``norm_raw``. ``norm`` is a signed accumulated weight (e.g. ``norm_col``/``norm_row`` from Keys' cubic kernel); ``norm_raw`` is the corresponding *unsigned* accumulated weight (sum of ``|w|``). When ``norm`` is small only because of sign cancellation, dividing by it directly would blow up or flip sign unpredictably; this floors it at ``rel_floor * norm_raw`` (with the sign of ``norm`` itself, defaulting to positive when ``norm`` is exactly 0) without otherwise altering well-conditioned entries. """ floor = rel_floor * norm_raw.clamp(min=1e-12) sign = torch.where(norm >= 0, torch.ones_like(norm), -torch.ones_like(norm)) return torch.where(norm.abs() < floor, sign * floor, norm)