Source code for phenotypic.measure._measure_neighbor_dist

"""Measure spatial relationships between neighboring colonies in grid cells."""

from __future__ import annotations

from typing import ClassVar, TYPE_CHECKING, cast

if TYPE_CHECKING:
    from phenotypic import Image
    from phenotypic._core._grid_image import GridImage

import numpy as np
import pandas as pd
from scipy import ndimage as ndi
from scipy.spatial import cKDTree

from phenotypic.abc_ import MeasureFeatures
from phenotypic.schema import OBJECT
from phenotypic.schema import NEIGHBOR_DIST, GRID, BBOX


def _boundary_coords(
        objmap: np.ndarray, label: int, sl: tuple[slice, slice]
) -> np.ndarray:
    """Full-image (row, col) coordinates of ``label``'s 4-connected boundary.

    A pixel is boundary when at least one 4-neighbour is outside the object;
    hole edges count. The minimum distance between two disjoint masks is always
    attained on these pixels (spec §3.6 C1). Pixels on the crop edge are
    boundary because ``binary_erosion`` treats outside-the-crop as background,
    which is correct for the tight ``find_objects`` slice.
    """
    mask = objmap[sl] == label
    edge = mask & ~ndi.binary_erosion(mask)
    coords = np.argwhere(edge)
    coords[:, 0] += sl[0].start
    coords[:, 1] += sl[1].start
    return coords


def _nearest_objects(
        objmap: np.ndarray, eligible: np.ndarray
) -> tuple[np.ndarray, np.ndarray]:
    """Exact nearest other object for every eligible label.

    Branch and bound: candidates are visited in ascending (bounding-box lower
    bound, label) order, and the search stops at the first candidate whose
    lower bound strictly exceeds the best exact distance found. The box gap
    never exceeds the mask distance (C2), so no nearer object is skipped, and
    equal-distance candidates are still visited for the smaller-label
    tie-break (C3).

    Args:
        objmap: 2-D integer label map.
        eligible: 1-D labels to search among; only these are targets or
            candidates.

    Returns:
        ``(nearest_label, nearest_distance)`` float arrays aligned to
        ``eligible``; ``NaN`` where no other eligible object exists.

    Raises:
        ValueError: If an eligible label has no pixels in ``objmap``.
    """
    eligible = np.asarray(eligible, dtype=np.int64)
    n = eligible.size
    nearest_label = np.full(n, np.nan)
    nearest_dist = np.full(n, np.nan)
    if n < 2:
        return nearest_label, nearest_dist

    slices = ndi.find_objects(objmap)
    boundaries: list[np.ndarray] = []
    bboxes = np.empty((n, 4), dtype=np.int64)  # inclusive min_r, max_r, min_c, max_c
    for i, label in enumerate(eligible):
        sl = slices[label - 1] if 0 < label <= len(slices) else None
        if sl is None:
            raise ValueError(f"eligible label {label} has no pixels in objmap")
        coords = _boundary_coords(objmap, int(label), sl)
        boundaries.append(coords)
        bboxes[i] = (coords[:, 0].min(), coords[:, 0].max(),
                     coords[:, 1].min(), coords[:, 1].max())

    trees: dict[int, cKDTree] = {}
    for i in range(n):
        gap_r = np.maximum(0, np.maximum(bboxes[:, 0] - bboxes[i, 1],
                                         bboxes[i, 0] - bboxes[:, 1]))
        gap_c = np.maximum(0, np.maximum(bboxes[:, 2] - bboxes[i, 3],
                                         bboxes[i, 2] - bboxes[:, 3]))
        # sqrt of an exact integer sum, the same rounding path cKDTree uses, so
        # a lower bound equal to a true distance compares equal rather than
        # 1 ulp high (np.hypot is not guaranteed correctly rounded on every libm),
        # and tied candidates are never skipped.
        lower = np.sqrt((gap_r * gap_r + gap_c * gap_c).astype(np.float64))
        lower[i] = np.inf
        best, best_j = np.inf, -1
        for j in np.lexsort((eligible, lower)):
            if j == i or lower[j] > best:
                break
            # Distance is symmetric: query the shorter boundary against the
            # longer one's tree, so a large object (plate rim, spreading
            # colony) is indexed once rather than queried per candidate.
            small, big = (i, j) if len(boundaries[i]) <= len(boundaries[j]) else (j, i)
            if big not in trees:
                trees[big] = cKDTree(boundaries[big])
            d = float(np.min(trees[big].query(boundaries[small], k=1)[0]))
            if d < best or (d == best and eligible[j] < eligible[best_j]):
                best, best_j = d, int(j)
        nearest_label[i] = eligible[best_j]
        nearest_dist[i] = best
    return nearest_label, nearest_dist


def _nearest_relation(self_rc: np.ndarray, nearest_rc: np.ndarray) -> np.ndarray:
    """Grid relation code per spec §3.4 from (row, col) cell positions."""
    dr = np.abs(nearest_rc[:, 0] - self_rc[:, 0])
    dc = np.abs(nearest_rc[:, 1] - self_rc[:, 1])
    step = dr + dc
    return np.select(
            [step == 0, step == 1, (dr == 1) & (dc == 1)],
            [0.0, 1.0, 2.0],
            default=3.0,
    )


[docs] class MeasureNeighborDist(MeasureFeatures): """Measure distances to grid neighbours and to the nearest object. For each detected colony, report (a) the nearest object in the left, right, above, and below grid cells with the minimum Euclidean distance between their pixel masks, and (b) the single closest other object anywhere on the plate, with its distance and its grid relation (same cell, adjacent, diagonal, or further). Directional distances use a per-section distance transform over a local window; the nearest-object search is an exact branch and bound over mask boundaries. Works on a ``GridImage`` (objects without a grid cell are excluded from the nearest search) and on a plain ``Image``, where only the nearest label and distance are populated. Returns: pd.DataFrame: Object-level neighbor measurements with columns: - Label: unique object identifier. - LeftNeighborObjLabel, LeftDistance. - RightNeighborObjLabel, RightDistance. - AboveNeighborObjLabel, AboveDistance. - UnderNeighborObjLabel, UnderDistance. - NearestObjLabel, NearestDistance, NearestRelation. - ``NaN`` where no neighbor exists (out of plate, empty neighbor cell, shielded by a cellmate, no grid, or fewer than two eligible objects). Best For: - Quantifying colony spacing and crowding to assess nutrient competition risk on arrayed plates, especially for round or irregular colony shapes where bounding-box geometry overstates proximity. - Screening for satellite colonies, fragments, and contaminants: a small ``NearestDistance`` with a same-cell ``NearestRelation``. - Flagging closely spaced colonies that may cross-contaminate. - Enabling neighbor-aware paired statistical comparisons for competition or cooperation studies. Consider Also: - :class:`MeasureGridLinRegStats` for regression-based positional quality metrics. - :class:`MeasureGridSpread` for within-well colony dispersion rather than between-well distances. - :class:`MeasureBounds` for raw bounding boxes and centroids without neighbor lookups. See Also: :doc:`/tutorials/notebooks/07_measuring_and_exporting` for a walkthrough of grid-level measurements. """ _measurement_infoclass: ClassVar[type] = NEIGHBOR_DIST # (d_row, d_col, label_col, dist_col) _DIRECTIONS: ClassVar[tuple] = ( (0, -1, NEIGHBOR_DIST.LEFT_NEIGHBOR_OBJ_LABEL, NEIGHBOR_DIST.LEFT_DISTANCE), (0, +1, NEIGHBOR_DIST.RIGHT_NEIGHBOR_OBJ_LABEL, NEIGHBOR_DIST.RIGHT_DISTANCE), (-1, 0, NEIGHBOR_DIST.ABOVE_NEIGHBOR_OBJ_LABEL, NEIGHBOR_DIST.ABOVE_DISTANCE), (+1, 0, NEIGHBOR_DIST.UNDER_NEIGHBOR_OBJ_LABEL, NEIGHBOR_DIST.UNDER_DISTANCE), ) def _operate(self, image: Image) -> pd.DataFrame: # Densify once; subsequent windowing is pure numpy slicing on this view. objmap = image.objmap[:] directional = [col for _, _, lab, dist in self._DIRECTIONS for col in (lab, dist)] if hasattr(image, "grid"): info = image.grid.info(include_metadata=False) results = self._measure_grid_directions( cast("GridImage", image), info, objmap ) grid_rc = info[[GRID.ROW_NUM, GRID.COL_NUM]].to_numpy(dtype=float) eligible_rows = np.flatnonzero(~np.isnan(grid_rc).any(axis=1)) elif image.num_objects == 0: # image.objects raises on an empty map; the spec'd result is no rows. info = pd.DataFrame({OBJECT.LABEL: np.empty(0, dtype=np.int64)}) results = {col: np.empty(0) for col in directional} grid_rc = None eligible_rows = np.empty(0, dtype=np.int64) else: info = image.objects.info(include_metadata=False) results = {col: np.full(len(info), np.nan) for col in directional} grid_rc = None eligible_rows = np.arange(len(info)) labels = info[OBJECT.LABEL].to_numpy().astype(np.int64) n_objs = labels.size nearest_label = np.full(n_objs, np.nan) nearest_dist = np.full(n_objs, np.nan) relation = np.full(n_objs, np.nan) e_label, e_dist = _nearest_objects(objmap, labels[eligible_rows]) nearest_label[eligible_rows] = e_label nearest_dist[eligible_rows] = e_dist if grid_rc is not None: label_to_row = {int(lab): i for i, lab in enumerate(labels)} found = ~np.isnan(e_label) rows_self = eligible_rows[found] rows_near = np.array( [label_to_row[int(lab)] for lab in e_label[found]], dtype=np.int64, ) relation[rows_self] = _nearest_relation( grid_rc[rows_self], grid_rc[rows_near] ) results[NEIGHBOR_DIST.NEAREST_OBJ_LABEL] = nearest_label results[NEIGHBOR_DIST.NEAREST_DISTANCE] = nearest_dist results[NEIGHBOR_DIST.NEAREST_RELATION] = relation df = pd.DataFrame(results) df.insert(0, OBJECT.LABEL, info[OBJECT.LABEL].to_numpy()) return df def _measure_grid_directions( self, image: GridImage, grid_info: pd.DataFrame, objmap_full: np.ndarray, ) -> dict: """The eight directional columns, keyed in enum order.""" nrows, ncols = image.grid.nrows, image.grid.ncols # Each public edge getter re-fits the grid, so fetch both once and # memoize every occupied cell's window up front. section_bbox = self._section_bboxes( grid_info, image.grid.get_row_edges(), image.grid.get_col_edges(), height=image.shape[0], width=image.shape[1], ) labels = grid_info[OBJECT.LABEL].to_numpy() n_objs = len(labels) label_to_row = {int(label): i for i, label in enumerate(labels)} results: dict = { NEIGHBOR_DIST.LEFT_NEIGHBOR_OBJ_LABEL : np.full(n_objs, np.nan), NEIGHBOR_DIST.LEFT_DISTANCE : np.full(n_objs, np.nan), NEIGHBOR_DIST.RIGHT_NEIGHBOR_OBJ_LABEL: np.full(n_objs, np.nan), NEIGHBOR_DIST.RIGHT_DISTANCE : np.full(n_objs, np.nan), NEIGHBOR_DIST.ABOVE_NEIGHBOR_OBJ_LABEL: np.full(n_objs, np.nan), NEIGHBOR_DIST.ABOVE_DISTANCE : np.full(n_objs, np.nan), NEIGHBOR_DIST.UNDER_NEIGHBOR_OBJ_LABEL: np.full(n_objs, np.nan), NEIGHBOR_DIST.UNDER_DISTANCE : np.full(n_objs, np.nan), } # Build (row, col) -> section_df once so neighbour lookups are O(1) # instead of an O(n_objects) DataFrame scan per direction per target. section_groups: dict[tuple[int, int], pd.DataFrame] = {} for (g_row, g_col), sec_df in grid_info.groupby( [GRID.ROW_NUM, GRID.COL_NUM], observed=True ): if pd.isna(g_row) or pd.isna(g_col): continue section_groups[(int(g_row), int(g_col))] = sec_df for (target_row, target_col), section_df in section_groups.items(): target_labels = section_df[OBJECT.LABEL].to_numpy().astype(np.int64) if target_labels.size == 0: continue target_bbox = section_bbox[(target_row, target_col)] valid_neighbors = self._collect_neighbors( section_groups, section_bbox, target_row, target_col, nrows, ncols, ) if not valid_neighbors: continue # Include target bbox so any target-object pixels that spilled past # the section's grid edges are still seeded into target_mask (the # object-fitting bounds may extend beyond the naive grid edges). all_bboxes = [target_bbox] + [n[2] for n in valid_neighbors] win = self._window_bbox(all_bboxes) objmap_win = objmap_full[win[0]:win[1] + 1, win[2]:win[3] + 1] target_mask = np.isin(objmap_win, target_labels) if not target_mask.any(): continue # Distance from each window pixel to the nearest target-section # object pixel, with index back-pointers so we can attribute every # pixel to a specific target object. dt, indices = ndi.distance_transform_edt( ~target_mask, return_indices=True ) nearest_target_label = objmap_win[indices[0], indices[1]] for (_n_row, _n_col, n_bbox, n_labels, label_col, dist_col) in valid_neighbors: lo_rr = n_bbox[0] - win[0] hi_rr = n_bbox[1] - win[0] + 1 lo_cc = n_bbox[2] - win[2] hi_cc = n_bbox[3] - win[2] + 1 objmap_n = objmap_win[lo_rr:hi_rr, lo_cc:hi_cc] neighbor_pixel_mask = np.isin(objmap_n, n_labels) if not neighbor_pixel_mask.any(): continue dt_n = dt[lo_rr:hi_rr, lo_cc:hi_cc] nearest_n = nearest_target_label[lo_rr:hi_rr, lo_cc:hi_cc] for target_label in target_labels: cand = neighbor_pixel_mask & (nearest_n == target_label) if not cand.any(): continue cand_dt = dt_n[cand] cand_obj = objmap_n[cand] argmin = int(np.argmin(cand_dt)) row_idx = label_to_row[int(target_label)] results[label_col][row_idx] = int(cand_obj[argmin]) results[dist_col][row_idx] = float(cand_dt[argmin]) return results @staticmethod def _section_bboxes( grid_info: pd.DataFrame, row_edges: np.ndarray, col_edges: np.ndarray, *, height: int, width: int, ) -> dict[tuple[int, int], tuple[int, int, int, int]]: """Window (min_rr, max_rr, min_cc, max_cc) for every occupied grid cell. The cell's grid rectangle, widened to cover every object assigned to it (colonies may spill past a grid line), then clipped to the image. Built from public grid members only, once per measurement. """ bboxes: dict[tuple[int, int], tuple[int, int, int, int]] = {} for key, sec in grid_info.groupby( [GRID.ROW_NUM, GRID.COL_NUM], observed=True ): g_row, g_col = cast("tuple[float, float]", key) if pd.isna(g_row) or pd.isna(g_col): continue r, c = int(g_row), int(g_col) min_rr = max(min(row_edges[r], sec[BBOX.MIN_RR].min()), 0) max_rr = min(max(row_edges[r + 1], sec[BBOX.MAX_RR].max()), height - 1) min_cc = max(min(col_edges[c], sec[BBOX.MIN_CC].min()), 0) max_cc = min(max(col_edges[c + 1], sec[BBOX.MAX_CC].max()), width - 1) bboxes[(r, c)] = (int(min_rr), int(max_rr), int(min_cc), int(max_cc)) return bboxes @staticmethod def _window_bbox( bboxes: list[tuple[int, int, int, int]] ) -> tuple[int, int, int, int]: """Union of (min_rr, max_rr, min_cc, max_cc) bboxes.""" arr = np.asarray(bboxes, dtype=np.int64) return ( int(arr[:, 0].min()), int(arr[:, 1].max()), int(arr[:, 2].min()), int(arr[:, 3].max()), ) def _collect_neighbors( self, section_groups: dict[tuple[int, int], pd.DataFrame], section_bbox: dict[tuple[int, int], tuple[int, int, int, int]], target_row: int, target_col: int, nrows: int, ncols: int, ) -> list[tuple[int, int, tuple[int, int, int, int], np.ndarray, str, str]]: """Enumerate valid (in-bounds, non-empty) neighbor sections.""" valid: list[tuple[ int, int, tuple[int, int, int, int], np.ndarray, str, str ]] = [] for d_row, d_col, label_col, dist_col in self._DIRECTIONS: n_row, n_col = target_row + d_row, target_col + d_col if not (0 <= n_row < nrows and 0 <= n_col < ncols): continue n_section_df = section_groups.get((n_row, n_col)) if n_section_df is None or n_section_df.empty: continue n_labels = n_section_df[OBJECT.LABEL].to_numpy().astype(np.int64) valid.append((n_row, n_col, section_bbox[(n_row, n_col)], n_labels, label_col, dist_col)) return valid
MeasureNeighborDist.__doc__ = NEIGHBOR_DIST.append_rst_to_doc(MeasureNeighborDist)