"""Connected components and percolation."""
from __future__ import annotations
from dataclasses import dataclass, field
import numpy as np
from scipy import ndimage
from morphogen.analysis.basic import as_array
from morphogen.image import VoxelImage
[docs]
@dataclass
class Components:
"""Connected components of one phase.
``percolating[axis]`` tells whether a component joins the two faces normal to
``axis`` (inside the box, i.e. without using periodicity); ``spanning_fraction`` is
the fraction of the phase volume in components joining at least one pair of faces.
For periodic images, components touching across faces are merged before counting.
"""
n_components: int
sizes: np.ndarray
percolating: dict[str, bool]
spanning_fraction: float
labels: np.ndarray | None = field(default=None, repr=False)
def _structure(connectivity: int) -> np.ndarray:
if connectivity == 6:
return ndimage.generate_binary_structure(3, 1)
if connectivity == 18:
return ndimage.generate_binary_structure(3, 2)
if connectivity == 26:
return ndimage.generate_binary_structure(3, 3)
raise ValueError("connectivity: 6, 18 or 26")
def _merge_periodic(labels: np.ndarray, n: int) -> np.ndarray:
"""Map label -> representative after joining components across opposite faces."""
parent = np.arange(n + 1)
def find(a):
while parent[a] != a:
parent[a] = parent[parent[a]]
a = parent[a]
return a
for axis in range(3):
a = np.take(labels, 0, axis=axis).ravel()
b = np.take(labels, -1, axis=axis).ravel()
mask = (a > 0) & (b > 0)
for u, v in np.unique(np.stack([a[mask], b[mask]], axis=1), axis=0):
ru, rv = find(int(u)), find(int(v))
if ru != rv:
parent[max(ru, rv)] = min(ru, rv)
return np.array([find(i) for i in range(n + 1)])
[docs]
def connected_components(
image, phase: int = 1, *, connectivity: int = 6, periodic=None, return_labels=False
) -> Components:
"""The connected components of a phase of an image (``connectivity``: 6, 18 or 26 neighbours)
and whether they percolate along each axis, through the faces of a periodic image
(``periodic``, by default that of the image); their labels with ``return_labels``."""
data = as_array(image)
if periodic is None:
periodic = image.periodic if isinstance(image, VoxelImage) else False
mask = data == phase
labels, n = ndimage.label(mask, structure=_structure(connectivity))
percolating, spanning = {}, np.zeros(n + 1, dtype=bool)
for axis, name in enumerate("xyz"):
first = np.unique(np.take(labels, 0, axis=axis))
last = np.unique(np.take(labels, -1, axis=axis))
both = np.intersect1d(first[first > 0], last[last > 0])
percolating[name] = bool(len(both))
spanning[both] = True
sizes_raw = np.bincount(labels.ravel(), minlength=n + 1)
phase_volume = int(sizes_raw[1:].sum())
spanning_fraction = float(sizes_raw[spanning].sum() / phase_volume) if phase_volume else 0.0
if periodic and n:
rep = _merge_periodic(labels, n)
roots, inverse = np.unique(rep[1:], return_inverse=True)
sizes = np.bincount(inverse, weights=sizes_raw[1:]).astype(np.int64)
if return_labels:
relabel = np.concatenate([[0], inverse + 1])
labels = relabel[labels]
n = len(roots)
else:
sizes = sizes_raw[1:]
return Components(
n_components=int(n),
sizes=sizes,
percolating=percolating,
spanning_fraction=spanning_fraction,
labels=labels if return_labels else None,
)
def _wrapping(labels: np.ndarray, structure: np.ndarray) -> np.ndarray:
"""Whether a component of ``labels`` (labelled inside the box) wraps around the periodic
box along each axis: a cycle of neighbours through the faces winds around the axis, so
that the component tiles into a cluster unbounded along it."""
shape = labels.shape
edges = [np.empty((0, 5), dtype=np.int64)]
for d in np.argwhere(structure) - 1:
if tuple(d) <= (0, 0, 0): # one offset of each opposite pair, not the centre
continue
for a in np.flatnonzero(d): # voxels whose neighbour x + d is across the face normal to a
index = [np.arange(n) for n in shape]
index[a] = np.array([shape[a] - 1 if d[a] > 0 else 0])
moved = [i + k for i, k in zip(index, d, strict=True)]
u = labels[np.ix_(*index)]
v = labels[np.ix_(*[m % n for m, n in zip(moved, shape, strict=True)])]
shift = np.ix_(*[m // n for m, n in zip(moved, shape, strict=True)])
shift = np.stack(np.broadcast_arrays(*shift), axis=-1)
keep = (u > 0) & (v > 0)
edges.append(np.column_stack([u[keep], v[keep], shift[keep]]))
parent = list(range(int(labels.max()) + 1))
frame = np.zeros((len(parent), 3), dtype=np.int64) # box of a label's copy in its parent's
def find(a):
path = []
while parent[a] != a:
path.append(a)
a = parent[a]
for b in reversed(path[:-1]): # path compression, frames made relative to the root
frame[b] += frame[parent[b]]
parent[b] = a
return a
wraps = np.zeros(3, dtype=bool)
for u, v, *s in np.unique(np.concatenate(edges), axis=0).tolist():
ru, rv = find(u), find(v)
winding = frame[u] + s - frame[v] # copy of v met from u's copy, minus v's own copy
if ru == rv:
wraps |= winding != 0
else:
parent[rv] = ru
frame[rv] = winding
return wraps
[docs]
def wrapping(image, phase: int = 1, *, connectivity: int = 6) -> dict[str, bool]:
"""Whether a component of a phase of an image wraps around the periodic box along each
axis (``connectivity``: 6, 18 or 26 neighbours): a cycle of neighbours through the faces
winds around the axis, so that the tiled component is a cluster unbounded along it, the
percolation of a periodic medium. Joining the two faces normal to the axis inside the
box (the flags ``percolating`` of :func:`connected_components`) neither implies it (a
staircase from face to face closes into no cycle) nor follows from it (a helix through
the faces normal to y wraps along x and y and joins no pair of faces)."""
structure = _structure(connectivity)
labels, _ = ndimage.label(as_array(image) == phase, structure=structure)
return dict(zip("xyz", _wrapping(labels, structure).tolist(), strict=True))