"""Bundle segmentation with include / exclude / endpoint ROIs, analytically.
A streamline from a seed is a pair of half-walks launched along +p and -p for each fODF peak
p. The bundle event is
passes every include ROI (either half) AND avoids every exclude ROI (both halves)
AND both ends are valid (grey matter or brain edge) AND >= 1 end in the endpoint ROI.
Include ROIs are handled by inclusion-exclusion over "avoid" sets, P(hit A and B) =
sum_T (-1)^|T| P(avoid union(T)), and avoiding a set is an exclusion ROI. For each avoid
set X and end kind k, one backward solve beta = (I - M Q)^-1 M r gives every state's
probability of completing the requirements (shared by all seeds); one forward solve from
every half's launch, weighted by its partner's completion probability, gives the occupancy.
Occupancy x completion is the bundle density (transition path theory's reactive density).
Each solve is a column; bundles are packed into groups of columns that share every pass
over the transition matrix.
"""
from __future__ import annotations
import logging
import time
from contextlib import contextmanager
from dataclasses import dataclass, field
from itertools import combinations
import numpy as np
from . import kernel as K
from .chain import VALID_ENDS
log = logging.getLogger("mpat")
class Clock:
"""Wall time per stage, summed over calls: ``with clock("forward"): ...``."""
def __init__(self):
self.t = {}
def add(self, key, seconds):
self.t[key] = self.t.get(key, 0.0) + seconds
@contextmanager
def __call__(self, key):
t0 = time.perf_counter()
try:
yield
finally:
self.add(key, time.perf_counter() - t0)
def report(self, title, total=None):
"""One log line per stage, largest first, with its share of ``total`` (default: the sum)."""
total = total or sum(self.t.values()) or 1e-9
log.info("%s (%.0fs):", title, total)
for k, v in sorted(self.t.items(), key=lambda kv: -kv[1]):
log.info(" %-24s %8.1fs %5.1f%%", k, v, 100 * v / total)
STALL_WINDOW, STALL_RATIO = 200, 0.9 # stalled: remaining mass fell < 10% in 200 steps
TAIL_MIN_STEPS = 30 # power steps before the Krylov tail may take over (walkers in transit)
TAIL_SWITCH_AFTER = 500 # ... when power iteration would still need more steps than this
TAIL_MAX_PRODUCTS = 3000 # for the whole Krylov tail, all rounds together
TAIL_ROUNDS = 4 # Krylov rounds on what the previous one left, before power iteration
FLOAT_BLOCKS_PER_COLUMN = 6 # float64 arrays per solution column at the peak
OVERLENGTH_SURVIVAL = 0.5 # states where more walkers than this outlast the soft max length
# ------------------------------------------------------------------ Krylov tail
def _cdot(a, b):
return np.einsum("ij,ij->j", a, b)
def bicgstab(apply, b, tol_abs, rows, max_mv=TAIL_MAX_PRODUCTS, restart=50):
"""BiCGSTAB on every column of b in lockstep (one product per half-step shared by all
columns). Converged columns are frozen; a column whose residual has not halved in
``restart`` iterations restarts. Returns (x, products, residual 1-norm over ``rows``)."""
k = b.shape[1]
x, r, rh = np.zeros_like(b), b.copy(), b.copy()
p, v, t = np.zeros_like(b), np.zeros_like(b), np.empty_like(b)
rho, alpha, omega = np.ones(k), np.ones(k), np.ones(k)
res = np.abs(r[rows]).sum(0)
done = res <= tol_abs
checkpoint = res.copy()
mv = 0
def div(a, d):
ok = (d != 0) & ~done
return np.where(ok, a / np.where(d != 0, d, 1.0), 0.0)
while not done.all() and mv < max_mv:
rho_new = _cdot(rh, r)
beta = div(rho_new, rho) * div(alpha, omega)
p *= beta
p -= v * (beta * omega)
p += r
apply(p, v)
alpha = div(rho_new, _cdot(rh, v))
r -= v * alpha
x += p * alpha
apply(r, t)
mv += 2
omega = div(_cdot(t, r), _cdot(t, t))
x += r * omega
r -= t * omega
rho = np.where(done, rho, rho_new)
res = np.abs(r[rows]).sum(0)
if not np.isfinite(res).all():
break
stuck = (alpha == 0) & (omega == 0) & ~done
if (mv // 2) % restart == 0:
stuck |= ~done & (res > 0.5 * checkpoint)
checkpoint = res.copy()
if stuck.any():
rh[:, stuck], p[:, stuck], v[:, stuck] = r[:, stuck], 0.0, 0.0
rho[stuck] = alpha[stuck] = omega[stuck] = 1.0
done |= res <= tol_abs
return x, mv, res
def _bicgstab_cols(apply, b, tol_abs, rows, cols, ncols, max_mv=TAIL_MAX_PRODUCTS):
"""bicgstab on columns ``cols`` of an operator ``apply`` that works on all ``ncols``
columns (the others zero; the operator acts column by column)."""
def sub(X, out):
full = np.zeros((X.shape[0], ncols))
full[:, cols] = X
res = np.empty_like(full)
apply(full, res)
out[...] = res[:, cols]
return bicgstab(sub, b, tol_abs, rows, max_mv=max_mv)
def _crawling(hist, it, tol, window=10):
"""The remaining mass decays geometrically and power iteration would still need more
than TAIL_SWITCH_AFTER steps to reach ``tol``."""
if it < TAIL_MIN_STEPS or it % window or len(hist) < 2 * window + 1 or hist[-1] <= 0:
return False
q1 = (hist[-1] / hist[-1 - window]) ** (1.0 / window)
q0 = (hist[-1 - window] / hist[-1 - 2 * window]) ** (1.0 / window)
return 0 < q1 < 1 and abs(q1 - q0) < 0.02 and np.log(tol / hist[-1]) / np.log(q1) > TAIL_SWITCH_AFTER
[docs]
def solve_series(mul, x0, mask, tol, max_iter, what, ncomp=1, verbose=False, accel=False, krylov=True,
on_step=None):
"""total = sum_t (M A)^t x0 per column (M = diag(mask)), A x = mul(x, out), by power
iteration until the remaining mass (mass rows, relative to the largest column's start) is
below ``tol``. Stops early when it stalls (mass circulating in states that almost never
get absorbed) and reports where that mass sits as ``info["trapped"]``. ``x0`` is consumed.
``verbose``: log the time per step (matrix product / masking and summing) every 100 steps.
``accel``: False (default), True / "mr" (invariant-preserving Periodic Minimal Residual
extrapolation), or "aitken" (scalar Aitken delta-squared extrapolation).
``on_step``: optional callback ``on_step(it, res, total, term)`` invoked after each iteration
(``term``: that iteration's term of the series, i.e. the current wavefront).
Returns (total, info)."""
t_start = time.perf_counter()
t_mul = t_acc = 0.0
w_mul = w_acc = 0.0 # since the last verbose line
total = x0.copy()
term, nxt = x0, np.empty_like(x0)
mask = np.ascontiguousarray(mask)
rows = slice(None, None, ncomp)
scale = max(np.abs(x0[rows]).sum(0).max(), 1e-300)
use_accel = (accel is not False and accel is not None)
accel_kind = "mr" if accel is True else str(accel)
burn_in, period, omega_max = 25, 8, 25.0
info = dict(iterations=0, residual=0.0, stalled=False, extrapolated_jumps=0)
hist, ref, tried = [], None, (not krylov) or use_accel
for it in range(1, max_iter + 1):
t0 = time.perf_counter()
mul(term, nxt)
t1 = time.perf_counter()
do_extrap = use_accel and (it >= burn_in and (it - burn_in) % period == 0)
if not do_extrap:
res = float(K.mask_accumulate(nxt, mask, total, ncomp).max()) / scale
else:
stats = K._step_stats(term, nxt, mask, ncomp)
u1, w1, uu, uw, ww = stats[:, 0], stats[:, 1], stats[:, 2], stats[:, 3], stats[:, 4]
res = float(w1.max()) / scale
C = x0.shape[1]
omega = np.ones(C)
if res >= tol:
for c in range(C):
if w1[c] / scale < tol:
continue
if accel_kind == "mr":
rr = uu[c] - 2.0 * uw[c] + ww[c]
ur = uw[c] - uu[c]
if rr > 1e-300 and ur < 0.0:
om = 1.0 - ur / rr
if om > 1.05:
omega[c] = min(om, omega_max)
elif accel_kind == "aitken":
if u1[c] > 1e-300 and 0.1 * u1[c] < w1[c] < 0.9999 * u1[c]:
lam = w1[c] / u1[c]
omega[c] = min(1.0 / (1.0 - lam), omega_max)
res = float(K._extrapolate_accumulate(term, nxt, total, omega, ncomp).max()) / scale
if np.any(omega > 1.05):
info["extrapolated_jumps"] += 1
t2 = time.perf_counter()
t_mul += t1 - t0
t_acc += t2 - t1
w_mul += t1 - t0
w_acc += t2 - t1
term, nxt = nxt, term
hist.append(res)
info.update(iterations=it, residual=res)
if on_step is not None:
on_step(it, res, total, term)
if it % 100 == 0:
log.info(" %s step %d: remaining mass %.2e", what, it, res)
if verbose:
log.info(" [timing] %s steps %d-%d: %.1f ms/step (matrix product %.1f, mask+sum %.1f); "
"%d rows x %d columns", what, it - 99, it, 10 * (w_mul + w_acc), 10 * w_mul,
10 * w_acc, x0.shape[0], x0.shape[1])
w_mul = w_acc = 0.0
if res < tol:
break
if not np.isfinite(res) or res > 1e6:
raise RuntimeError(f"{what} solve diverges (remaining mass {res:.1e} after {it} steps)")
stall = False
if it % STALL_WINDOW == 0:
stall = ref is not None and res > STALL_RATIO * ref
ref = res
if not tried and (stall or _crawling(hist, it, tol)):
tried = True
tol_abs = tol * scale
act = np.flatnonzero(np.abs(term[rows]).sum(0) > tol_abs)
tmp = np.empty((term.shape[0], act.size))
msk = np.ascontiguousarray(mask[:, act])
def apply(X, out):
mul(np.ascontiguousarray(X), tmp)
tmp[...] *= msk
np.subtract(X, tmp, out=out)
log.info(" %s: switching to the Krylov tail at step %d (remaining mass %.1e, %s; %d columns)",
what, it, res, "stalled" if stall else "decaying too slowly for power iteration", act.size)
t0_k = time.time()
pending = np.ascontiguousarray(term[:, act])
added = np.ones(act.size, bool)
live = np.ones(act.size, bool)
mv_all, rounds = 0, 0
resid = np.empty_like(pending)
for rounds in range(1, TAIL_ROUNDS + 1):
cols = np.flatnonzero(live)
budget = TAIL_MAX_PRODUCTS - mv_all
if not cols.size or budget < 2:
break
every = cols.size == act.size
b = pending if every else np.ascontiguousarray(pending[:, cols])
r0 = np.abs(b[rows]).sum(0)
y, mv, _ = bicgstab(apply, b, tol_abs, rows, max_mv=budget) if every else \
_bicgstab_cols(apply, b, tol_abs, rows, cols, act.size, max_mv=budget)
mv_all += mv
if every:
apply(y, resid)
np.subtract(b, resid, out=resid)
r = resid
else:
full = np.zeros_like(pending)
full[:, cols] = y
apply(full, resid)
del full
r = b - resid[:, cols]
r1 = np.abs(r[rows]).sum(0)
ok = np.isfinite(r1) & (r1 < 0.5 * r0)
acc = cols[ok]
total[:, act[acc]] += y[:, ok] - np.where(added[acc], 1.0, 0.0) * b[:, ok]
del y
pending[:, acc] = r[:, ok]
added[acc] = False
live[cols[~ok]] = False
live[acc[r1[ok] <= tol_abs]] = False
del r
del tmp, resid
add = ~added
total[:, act[add]] += pending[:, add]
term[:, act] = pending
left = np.abs(term[rows]).sum(0)
res = float(left.max()) / scale
info.update(tail_started_at=it, tail_products=int(mv_all), tail_rounds=rounds, residual=res,
tail_seconds=round(time.time() - t0_k, 1))
log.info(" %s: Krylov tail from step %d, %d products in %d round(s), remaining %.1e (%.0fs)",
what, it, mv_all, rounds, res, time.time() - t0_k)
if res < tol:
break
n_left = int((left[act] > tol_abs).sum())
log.info(" %s: %d of %d columns above tol after the Krylov tail continue with power "
"iteration", what, n_left, act.size)
stall = False
if stall:
info["stalled"] = True
log.warning("%s solve stalled at step %d: remaining mass %.2e circulates in states "
"that (almost) never get absorbed; stopping here", what, it, res)
break
if info["residual"] >= tol: # stalled or max_iter reached
info["trapped"] = np.abs(term[rows]).sum(1).astype(np.float32) / scale
n = max(info["iterations"], 1)
info.update(seconds=round(time.perf_counter() - t_start, 1), ms_per_step=round(1e3 * (t_mul + t_acc) / n, 2))
if verbose:
log.info(" [timing] %s: %d steps in %.1fs, %.1f ms/step (matrix product %.1f, mask+sum %.1f)",
what, n, info["seconds"], 1e3 * (t_mul + t_acc) / n, 1e3 * t_mul / n, 1e3 * t_acc / n)
return total, info
# ------------------------------------------------------------------ soft maximum length
def overlength_states(chain, max_length_mm, zooms):
"""Direction states from which most walkers are still walking after ``max_length_mm``:
the survival probability u_T = Q^T 1 (Q: one step among white-matter states) after
T = max_length / smallest voxel side steps -- every step crosses into a neighbouring voxel,
so a walk of T steps is at least that long. Traps (white matter the turning limit makes
hard to leave, e.g. a ring around a cavity) keep u_T near 1, ordinary states drain
within a tract's length. Bundle ROIs only add ways out, so this holds for every bundle.
Returns (kill: bool per state, survival per state, T)."""
T = int(np.ceil(max_length_mm / float(np.min(np.abs(zooms)))))
nc = chain.ncomp
u = np.zeros((chain.n_states * nc, 1))
u[::nc] = 1.0 # the mass rows (moments: position-averaged)
out = np.empty_like(u)
for _ in range(T):
chain.mul_backward(u, out)
u, out = out, u
surv = u[::nc, 0].copy()
return surv >= OVERLENGTH_SURVIVAL, surv, T
# ------------------------------------------------------------------ launches
[docs]
@dataclass
class Launches:
"""First exits of every half-walk of every seed (independent of the bundle)."""
seeds: np.ndarray # (S, 3) voxel indices
seed_lin: np.ndarray # (S,) padded linear indices
pair_seed: np.ndarray # (P,) seed of each streamline (peak pair)
pair_w: np.ndarray # (P,) weight; sums to 1 per seed
pair_d: np.ndarray # (P, 2) the two signed peak directions (sphere vertices)
hseed: np.ndarray # (2P,) padded linear index of each half's seed (partner = h ^ 1)
lptr: np.ndarray # (2P + 1,) sparse first exits: keys n * nb + b, values (ncomp,)
lkey: np.ndarray
lval: np.ndarray
dead: np.ndarray # (2P,)
@property
def nbytes(self):
return self.lval.nbytes + self.lkey.nbytes + self.lptr.nbytes
[docs]
def prepare_launches(chain, seeds, chunk=4096):
"""One streamline per seed voxel, split over its fODF peak pairs {p, -p}."""
t0 = time.time()
seeds = np.asarray(seeds, np.int64).reshape(-1, 3)
seed_lin = chain.lin(seeds)
anti = chain.geo.antipode()
pair_seed, pair_w, pair_d = [], [], []
for si, v in enumerate(seed_lin):
peaks = chain.seed_peaks(v)
pairs = {}
for p in peaks:
key = (min(p, anti[p]), max(p, anti[p]))
pairs[key] = pairs.get(key, 0.0) + 1.0 / peaks.size
for (p, q), w in pairs.items():
pair_seed.append(si), pair_w.append(w), pair_d.append((p, q))
pair_seed = np.asarray(pair_seed, np.int64)
pair_w = np.asarray(pair_w, np.float64)
pair_d = np.asarray(pair_d, np.int64).reshape(-1, 2)
P, nc, nb = pair_seed.size, chain.ncomp, chain.nb
counts = np.zeros(2 * P, np.int64)
keys, vals = [], []
dead = np.empty(2 * P)
for s0 in range(0, P, chunk):
n = min(P, s0 + chunk) - s0
o = np.empty((2 * n, 26, nb, nc))
d = np.empty(2 * n)
v_chunk = seed_lin[pair_seed[s0:s0 + n]]
if n > 0:
chg = np.flatnonzero(v_chunk[1:] != v_chunk[:-1]) + 1
starts = np.concatenate([[0], chg])
u_vlin = v_chunk[starts]
dptr = 2 * np.concatenate([starts, [n]]).astype(np.int64)
else:
u_vlin = np.zeros(0, np.int64)
dptr = np.zeros(1, np.int64)
chain.launch_halves(u_vlin, dptr, pair_d[s0:s0 + n].reshape(-1), o, d)
hh, nn, bb = np.nonzero(np.any(o != 0, axis=-1))
counts[2 * s0:2 * (s0 + n)] = np.bincount(hh, minlength=2 * n)
keys.append((nn * nb + bb).astype(np.int16))
vals.append(o[hh, nn, bb])
dead[2 * s0:2 * (s0 + n)] = d
L = Launches(seeds, seed_lin, pair_seed, pair_w, pair_d, np.repeat(seed_lin[pair_seed], 2),
np.concatenate([[0], np.cumsum(counts)]).astype(np.int64),
np.concatenate(keys) if keys else np.zeros(0, np.int16),
np.concatenate(vals) if vals else np.zeros((0, nc)), dead)
log.info("launches: %d streamlines (peak pairs) from %d seeds in %.0fs (%.0f MB)", P, len(seeds),
time.time() - t0, L.nbytes / 1e6)
return L
# ------------------------------------------------------------------ bundles
[docs]
@dataclass
class BundleResult:
name: str
seed_vox: np.ndarray # (S, 3)
seed_prob: np.ndarray # (S,) P(the streamline from this seed is in the bundle)
density_t: np.ndarray # (Nt,) expected visits by bundle streamlines, all seeds
endpoints_a: np.ndarray # (Na,) expected bundle endpoints per absorbing voxel
info: dict = field(default_factory=dict)
density_class: np.ndarray = None # (Nt, 26) the visits split by the walker's direction class
fields: object = None # mpat.fields.BundleFields when solved with keep_fields=True
flux26: np.ndarray = None # (Nt, 26) expected steps to each of 26 neighbours (when ncomp == 1)
start_mask: np.ndarray = None # optional start ROI mask on the chain grid
end_mask: np.ndarray = None # optional end ROI mask on the chain grid
@dataclass
class SolveStep:
"""What a :func:`segment_bundles` ``on_step`` callback gets after each series iteration."""
phase: str # "backward" (completion probabilities) or "forward" (occupancy)
it: int # iteration number within the phase
res: float # relative residual
total: np.ndarray # solution so far, (n_states * ncomp, columns)
term: np.ndarray # this iteration's term of the series: the current wavefront
colsign: np.ndarray # inclusion-exclusion sign of each column
n_kinds: int # end kinds of the first bundle (its columns 0 .. n_kinds - 1 avoid nothing)
beta: np.ndarray = None # the backward solution; forward phase only
def _endpoint_kinds(a_valid, a_start, a_end):
"""Disjoint end categories per half and the non-negative bilinear form M >= 0:
P(both ends acceptable) = sum_kl M[k, l] V_k(h1) V_l(h2)."""
if a_start is None and a_end is None:
return [a_valid], np.array([[1.0]]), "both ends valid"
if a_start is None or a_end is None:
E = a_valid & (a_end if a_end is not None else a_start)
R = a_valid & ~E
return [E, R], np.array([[1.0, 1.0], [1.0, 0.0]]), "one end in the endpoint ROI"
S, E = a_valid & a_start, a_valid & a_end
if not (S & E).any():
return [S, E], np.array([[0.0, 1.0], [1.0, 0.0]]), "one end in start, the other in end"
B = S & E
return [S & ~B, E & ~B, B], np.array([
[0.0, 1.0, 1.0],
[1.0, 0.0, 1.0],
[1.0, 1.0, 1.0],
]), "one end in start, the other in end"
class _Plan:
"""A bundle's avoid sets, end kinds and solution columns."""
def __init__(self, chain, spec, valid_classes):
self.name, self.t0 = spec["name"], time.time()
self.start_mask = spec.get("start")
self.end_mask = spec.get("end")
pad = np.zeros(chain.pshape, bool)
def padded(m):
p = pad.copy()
p[1:-1, 1:-1, 1:-1] = m
return p.ravel()
inc = [padded(m) for m in spec.get("include", ())]
exc = padded(spec["exclude"]) if spec.get("exclude") is not None else pad.ravel()
self.subsets = [T for r in range(len(inc) + 1) for T in combinations(range(len(inc)), r)]
self.signs = np.array([(-1.0) ** len(T) for T in self.subsets])
self.nX = len(self.subsets)
self.taboo = np.zeros((pad.size, self.nX), np.bool_)
for x, T in enumerate(self.subsets):
tb = exc.copy()
for i in T:
tb |= inc[i]
self.taboo[:, x] = tb
a_valid = np.isin(chain.a_class, np.asarray(valid_classes))
ends = [padded(spec[k])[chain.a_lin] if spec.get(k) is not None else None for k in ("start", "end")]
kinds, self.M, self.end_rule = _endpoint_kinds(a_valid, *ends)
self.nK = len(kinds)
self.C = self.nX * self.nK
self.xcol = np.repeat(np.arange(self.nX), self.nK)
self.kcol = np.tile(np.arange(self.nK), self.nX)
self.absw = np.stack([kinds[self.kcol[c]] & ~self.taboo[chain.a_lin, self.xcol[c]]
for c in range(self.C)], 1).astype(np.float64)
st = np.repeat(chain.t_lin, chain.nb * chain.ncomp)
self.mask = (~self.taboo[st][:, self.xcol]).astype(np.uint8)
kill = getattr(chain, "kill", None) # states past the soft maximum length: walkers end there
if kill is not None:
self.mask[np.repeat(kill, chain.ncomp)] = 0
def max_columns(chain, launches, max_mem):
"""Solution columns that fit in ``max_mem`` bytes next to the chain and the launches."""
per_col = chain.n_states * chain.ncomp * (8 * FLOAT_BLOCKS_PER_COLUMN + 1)
free = max_mem - chain.nbytes - launches.nbytes - 1e9
return int(max(1, min(256, free // per_col)))
def _trapped(chain, info, what, names, on_trapped):
"""Hand the mass a solve could not finish (per voxel) to ``on_trapped``."""
m = info.pop("trapped", None)
if m is None or on_trapped is None:
return
vol = chain.to_volume(m.reshape(-1, chain.nb).sum(1))
on_trapped(what, names, vol)
def _solve(chain, x0, mask, tol, max_iter, what, verbose=False, accel=False, on_step=None):
mul = chain.mul_forward if what == "forward" else chain.mul_backward
return solve_series(mul, x0, mask, tol, max_iter, what, chain.ncomp, verbose, accel=accel, krylov=False,
on_step=on_step)
def _solve_group(chain, plans, L, tol, max_iter, on_result, on_trapped=None, verbose=False, clock=None,
keep_fields=False, accel=False, arc_length=False, zooms=None, on_step=None):
t0 = time.time()
colsign_all = np.concatenate([p.signs[p.xcol] for p in plans])
n_kinds = plans[0].nK
def step_hook(phase, beta=None):
if on_step is None:
return None
return lambda it, res, total, term: on_step(SolveStep(phase, it, res, total, term, colsign_all,
n_kinds, beta))
gclock = Clock()
nb, Ns, nc = chain.nb, chain.n_states, chain.ncomp
offs = np.cumsum([0] + [p.C for p in plans])
names = [p.name for p in plans]
if len(plans) > 1:
log.info("solving %d bundles together (%d columns): %s", len(plans), offs[-1], ", ".join(names))
with gclock("masks and absorption"):
mask = np.concatenate([p.mask for p in plans], axis=1)
for p in plans:
p.mask = None
r = np.concatenate([chain.absorb_rhs(p.absw) for p in plans], axis=1)
r *= mask
with gclock("backward solve"):
beta, info_b = _solve(chain, r, mask, tol, max_iter, "backward", verbose, accel=accel,
on_step=step_hook("backward"))
with gclock("trapped maps"):
_trapped(chain, info_b, "backward", names, on_trapped)
del r
t_init = time.perf_counter()
P = L.pair_seed.size
pi0 = np.zeros((Ns * nc, int(offs[-1])))
starts = []
for p, o0, o1 in zip(plans, offs[:-1], offs[1:]):
seed_ok = (~p.taboo[L.hseed][:, p.xcol]).astype(np.float64)
vals = np.empty((L.hseed.size, p.C))
K.half_values(L.hseed, L.lptr, L.lkey, L.lval, chain.label, chain.noff, chain.tindex,
chain.aindex, nb, np.ascontiguousarray(beta[:, o0:o1]), p.absw, seed_ok, vals)
V = vals.reshape(P, 2, p.nX, p.nK)
pb = np.einsum("pxk,kl,pxl->px", V[:, 0], p.M, V[:, 1]) @ p.signs # P(pair in bundle)
seed_prob = np.bincount(L.pair_seed, weights=L.pair_w * pb, minlength=len(L.seeds))
coef = np.einsum("phxl,kl->phxk", V[:, ::-1], p.M).reshape(2 * P, p.C)
coef *= np.repeat(L.pair_w, 2)[:, None] * seed_ok
pi0_p = np.zeros((Ns * nc, p.C))
a0 = np.zeros((chain.a_lin.size, p.C))
K.scatter_init(L.hseed, L.lptr, L.lkey, L.lval, coef, chain.label, chain.noff, chain.tindex,
chain.aindex, nb, p.taboo, p.xcol, pi0_p, a0)
pi0[:, o0:o1] = pi0_p
starts.append((a0, seed_prob, pb))
if getattr(chain, "kill", None) is not None:
pi0[np.repeat(chain.kill, nc)] = 0.0
gclock.add("seed weights (forward start)", time.perf_counter() - t_init)
launch = pi0.copy() if keep_fields else None # solve_series consumes pi0
with gclock("forward solve"):
S, info_f = _solve(chain, pi0, mask, tol, max_iter, "forward", verbose, accel=accel,
on_step=step_hook("forward", beta))
with gclock("trapped maps"):
_trapped(chain, info_f, "forward", names, on_trapped)
del pi0, mask
t_dens = time.perf_counter()
out = {}
ti = chain.tindex[L.seed_lin]
pt = ti[L.pair_seed]
on = pt >= 0
chord_w = None
if arc_length:
from .geometry import class_chord_lengths
chord_w = class_chord_lengths(chain.geo, zooms)
for p, o0, o1, (a0, seed_prob, pb) in zip(plans, offs[:-1], offs[1:], starts):
colsign = p.signs[p.xcol]
S_p = np.ascontiguousarray(S[:, o0:o1])
dcls = K.paired_density(S_p, np.ascontiguousarray(beta[:, o0:o1]), colsign, Ns, nc)
dcls = dcls.reshape(chain.t_lin.size, nb)
# step 0 at the seed, half along each direction of the streamline's peak
w0 = 0.5 * (L.pair_w * pb)[on]
for k in (0, 1):
np.add.at(dcls, (pt[on], chain.geo.vbin[L.pair_d[on, k]]), w0)
if chord_w is not None:
dcls = dcls * chord_w[None, :]
density = dcls.sum(1)
endpoints = ((a0 + chain.absorbed_from(S_p)) * p.absw) @ colsign
info = dict(n_seeds=int(len(L.seeds)), n_streamlines=int(P),
expected_bundle_streamlines=float(seed_prob.sum()), endpoint_rule=p.end_rule,
endpoint_mass_check=float(endpoints.sum() / max(2 * seed_prob.sum(), 1e-300)),
n_columns=int(p.C), tolerance=tol, backward=info_b, forward=info_f,
solved_with=[n for n in names if n != p.name],
negative_mass_before_clip=dict(density=float(-density[density < 0].sum()),
seed_prob=float(-seed_prob[seed_prob < 0].sum())),
seconds=round(time.time() - p.t0, 1))
flux26 = None
if nc == 1:
f26 = np.empty((chain.t_lin.size, 26), np.float64)
K.stencil_flux(chain.Q_ptr, chain.Q_slot, chain.Q_w, chain.tmpl_n, chain.tmpl_b, chain.nbr_t,
chain.nb, S_p, np.ascontiguousarray(beta[:, o0:o1]), colsign, f26)
flux26 = np.clip(f26, 0, None).astype(np.float32)
res = BundleResult(p.name, L.seeds, np.clip(seed_prob, 0, None), np.clip(density, 0, None),
np.clip(endpoints, 0, None), info, np.clip(dcls, 0, None).astype(np.float32),
flux26=flux26, start_mask=p.start_mask, end_mask=p.end_mask)
if keep_fields:
from .fields import BundleFields
res.fields = BundleFields(chain, p, S_p, np.ascontiguousarray(beta[:, o0:o1]),
np.ascontiguousarray(launch[:, o0:o1]), a0)
if on_result is not None:
tw = time.perf_counter()
on_result(res)
gclock.add("writing outputs", time.perf_counter() - tw)
t_dens += time.perf_counter() - tw
out[p.name] = res
gclock.add("densities and endpoints", time.perf_counter() - t_dens)
log.info("group done in %.0fs (backward %d steps, forward %d steps)", time.time() - t0,
info_b["iterations"], info_f["iterations"])
log.info(" group time: " + ", ".join(f"{k} {v:.3g}s" for k, v in
sorted(gclock.t.items(), key=lambda kv: -kv[1]) if v >= 0.005))
if clock is not None:
for k, v in gclock.t.items():
clock.add(k, v)
return out
[docs]
def segment_bundles(chain, specs, launches, tol=1e-6, max_mem=8e9, max_iter=5000,
valid_classes=VALID_ENDS, on_result=None, on_trapped=None, verbose=False,
clock=None, keep_fields=False, accel=False, arc_length=False, zooms=None, on_step=None):
"""Segment bundles, sharing solves. ``specs``: dicts with ``name`` and optional
``include`` (list of masks), ``exclude``, ``start``, ``end`` (boolean volumes on the chain
grid). Bundles are packed in order into groups whose columns fit in ``max_mem`` bytes;
each group costs one backward and one forward series.
``on_trapped(direction, names, volume)``: called when a solve stalls or runs out of steps,
with the mass it could not finish per voxel (relative to the largest column's start).
``verbose``: timing inside the solves. ``clock``: a Clock to add the time per stage to
(default: a new one, reported at the end).
``keep_fields``: also keep each bundle's solution columns (occupancy, completion and
launch mass per state) as ``result.fields`` (mpat.fields.BundleFields), for edge flux,
committors and conservation checks. Three more float64 arrays of n_states x columns per
bundle; the plain chain only (not with spatial moments).
``accel``: False (default), True / "mr" (Periodic Minimal Residual), or "aitken".
``arc_length``: weight class visits by physical intra-voxel chord lengths (in mm if ``zooms``
is provided, else in voxels).
``on_step(step)``: called with a :class:`SolveStep` after every backward and forward
iteration (e.g. to stream the solve as it converges).
Returns {name: BundleResult}."""
if keep_fields and chain.ncomp != 1:
raise ValueError("keep_fields needs the plain chain (ncomp == 1), not the moment chain")
if keep_fields:
max_mem = max_mem / 2 # the launch copy during the forward solve
own = clock is None
clock = clock or Clock()
t_all = time.perf_counter()
cap = max_columns(chain, launches, max_mem)
log.info("column groups of up to %d columns (%.1f GB budget)", cap, max_mem / 1e9)
out, group, used = {}, [], 0
it = iter(specs)
while True:
with clock("bundle ROIs"): # specs may warp each bundle's ROIs as it is asked for
spec = next(it, None)
if spec is None:
break
with clock("bundle plans"):
p = _Plan(chain, spec, valid_classes)
if p.C > cap:
log.warning("%s needs %d columns, more than fit in max_mem (%d); solving it alone",
p.name, p.C, cap)
if group and used + p.C > cap:
out.update(_solve_group(chain, group, launches, tol, max_iter, on_result, on_trapped,
verbose, clock, keep_fields, accel=accel, arc_length=arc_length,
zooms=zooms, on_step=on_step))
group, used = [], 0
group.append(p)
used += p.C
if group:
out.update(_solve_group(chain, group, launches, tol, max_iter, on_result, on_trapped,
verbose, clock, keep_fields, accel=accel, arc_length=arc_length,
zooms=zooms, on_step=on_step))
if own:
clock.report("bundle segmentation time", time.perf_counter() - t_all)
return out
def solve_bundle_cascade(chain, spec, launches, tol=1e-6, max_iter=5000, valid_classes=VALID_ENDS,
accel=False):
"""Non-negative Strong-Markov hitting cascade for a bundle with 1 include ROI (or 0 include
ROIs, delegated to segment_bundles). Computes the exact bundle density, seed probabilities
and endpoints with zero signed inclusion-exclusion subtraction (every term >= 0)."""
inc_list = list(spec.get("include", ()))
if len(inc_list) == 0:
return segment_bundles(chain, [spec], launches, tol=tol, max_iter=max_iter,
valid_classes=valid_classes, accel=accel)[spec["name"]]
if len(inc_list) > 1:
raise ValueError("solve_bundle_cascade currently supports 0 or 1 unordered include ROI")
t0 = time.time()
Ns, nb = chain.n_states, chain.nb
pad = np.zeros(chain.pshape, bool)
def padded(m):
p = pad.copy()
p[1:-1, 1:-1, 1:-1] = m
return p.ravel()
inc1 = padded(inc_list[0])
exc = padded(spec["exclude"]) if spec.get("exclude") is not None else pad.ravel()
st_vox = np.repeat(chain.t_lin, nb)
base_ok = ~exc[st_vox]
if getattr(chain, "kill", None) is not None:
base_ok &= ~chain.kill
in_I1 = base_ok & inc1[st_vox]
mask_0 = base_ok.astype(np.uint8)
mask_avoid1 = (base_ok & ~inc1[st_vox]).astype(np.uint8)
a_valid = np.isin(chain.a_class, np.asarray(valid_classes))
ends = [padded(spec[k])[chain.a_lin] if spec.get(k) is not None else None for k in ("start", "end")]
kinds, M_end, end_rule = _endpoint_kinds(a_valid, *ends)
nK = len(kinds)
absw_0 = np.stack([kinds[k] & ~exc[chain.a_lin] for k in range(nK)], 1).astype(np.float64)
absw_avoid1 = np.stack([kinds[k] & ~exc[chain.a_lin] & ~inc1[chain.a_lin] for k in range(nK)], 1).astype(np.float64)
absw_in1 = absw_0 - absw_avoid1
m_post = np.repeat(mask_0[:, None], nK, axis=1)
m_av1 = np.repeat(mask_avoid1[:, None], nK, axis=1)
r_post = chain.absorb_rhs(absw_0) * m_post
beta_post, info_b1 = solve_series(chain.mul_backward, r_post, m_post, tol, max_iter, "b_post", 1, accel=accel)
hit_on_roi = beta_post * in_I1[:, None]
q_into_roi = np.empty_like(beta_post)
chain.mul_backward(np.ascontiguousarray(hit_on_roi), q_into_roi)
r_into_roi = chain.absorb_rhs(absw_in1)
rhs_hit = (q_into_roi + r_into_roi) * m_av1
rhs_avoid = chain.absorb_rhs(absw_avoid1) * m_av1
rhs_both = np.concatenate([rhs_avoid, rhs_hit], axis=1)
m_both = np.concatenate([m_av1, m_av1], axis=1)
sol_both, info_b2 = solve_series(chain.mul_backward, rhs_both, m_both, tol, max_iter, "b_av_hit", 1, accel=accel)
beta_avoid = sol_both[:, :nK]
beta_hit = hit_on_roi + sol_both[:, nK:]
P = launches.pair_seed.size
H = launches.hseed.size
seed_in_exc = exc[launches.hseed]
seed_in_I1 = inc1[launches.hseed] & ~seed_in_exc
seed_outside = ~seed_in_exc & ~inc1[launches.hseed]
beta_all = np.ascontiguousarray(np.concatenate([beta_post, beta_avoid, beta_hit], axis=1))
absw_all = np.concatenate([absw_0, absw_avoid1, absw_in1], axis=1)
seed_ok_all = np.ones((H, 3 * nK))
vals_all = np.empty((H, 3 * nK))
K.half_values(launches.hseed, launches.lptr, launches.lkey, launches.lval,
chain.label, chain.noff, chain.tindex, chain.aindex, nb,
beta_all, absw_all, seed_ok_all, vals_all)
V_post = vals_all[:, :nK]
V_av = vals_all[:, nK:2 * nK]
V_ht = vals_all[:, 2 * nK:]
Vh_hit = np.where(seed_in_I1[:, None], V_post, np.where(seed_outside[:, None], V_ht, 0.0)).reshape(P, 2, nK)
Vh_av = np.where(seed_outside[:, None], V_av, 0.0).reshape(P, 2, nK)
pb = (
np.einsum("pk,kl,pl->p", Vh_hit[:, 0], M_end, Vh_hit[:, 1])
+ np.einsum("pk,kl,pl->p", Vh_hit[:, 0], M_end, Vh_av[:, 1])
+ np.einsum("pk,kl,pl->p", Vh_av[:, 0], M_end, Vh_hit[:, 1])
)
seed_prob = np.bincount(launches.pair_seed, weights=launches.pair_w * pb, minlength=len(launches.seeds))
V_part_any = Vh_hit[:, ::-1] + Vh_av[:, ::-1]
V_part_hit = Vh_hit[:, ::-1]
coef_must_hit = (np.einsum("phl,kl->phk", V_part_any, M_end) * launches.pair_w[:, None, None]).reshape(H, nK)
coef_may_avoid = (np.einsum("phl,kl->phk", V_part_hit, M_end) * launches.pair_w[:, None, None]).reshape(H, nK)
tab_exc = exc[:, None]
tab_av1 = (exc | inc1)[:, None]
xcol_0 = np.zeros(nK, np.int64)
pi_must_hit = np.zeros((Ns, nK))
pi_already_hit = np.zeros((Ns, nK))
pi_may_avoid = np.zeros((Ns, nK))
a0_must_in1 = np.zeros((chain.a_lin.size, nK))
a0_already = np.zeros((chain.a_lin.size, nK))
a0_avoid = np.zeros((chain.a_lin.size, nK))
K.scatter_init(launches.hseed, launches.lptr, launches.lkey, launches.lval,
coef_must_hit * seed_outside[:, None], chain.label, chain.noff, chain.tindex, chain.aindex,
nb, tab_exc, xcol_0, pi_must_hit, a0_must_in1)
K.scatter_init(launches.hseed, launches.lptr, launches.lkey, launches.lval,
coef_must_hit * seed_in_I1[:, None], chain.label, chain.noff, chain.tindex, chain.aindex,
nb, tab_exc, xcol_0, pi_already_hit, a0_already)
K.scatter_init(launches.hseed, launches.lptr, launches.lkey, launches.lval,
coef_may_avoid * seed_outside[:, None], chain.label, chain.noff, chain.tindex, chain.aindex,
nb, tab_av1, xcol_0, pi_may_avoid, a0_avoid)
pi_stage0 = np.concatenate([pi_must_hit * m_av1, pi_may_avoid * m_av1], axis=1)
S_stage0, info_f1 = solve_series(chain.mul_forward, pi_stage0, np.concatenate([m_av1, m_av1], axis=1),
tol, max_iter, "f_stage0", 1, accel=accel)
S_pre = S_stage0[:, :nK]
S_av = S_stage0[:, nK:]
q_from_pre = np.empty_like(S_pre)
chain.mul_forward(np.ascontiguousarray(S_pre), q_from_pre)
flux_I1 = (pi_must_hit + q_from_pre) * in_I1[:, None]
pi_stage1 = (pi_already_hit + flux_I1) * m_post
S_post, info_f2 = solve_series(chain.mul_forward, pi_stage1, m_post, tol, max_iter, "f_stage1", 1, accel=accel)
dcls = (S_pre * beta_hit + S_post * beta_post + S_av * beta_avoid).sum(1).reshape(chain.t_lin.size, nb)
ti = chain.tindex[launches.seed_lin]
pt = ti[launches.pair_seed]
on = pt >= 0
w0 = 0.5 * (launches.pair_w * pb)[on]
for k in (0, 1):
np.add.at(dcls, (pt[on], chain.geo.vbin[launches.pair_d[on, k]]), w0)
density = dcls.sum(1)
endpoints = (
((a0_already + chain.absorbed_from(S_post)) * absw_0)
+ ((a0_must_in1 + chain.absorbed_from(S_pre)) * absw_in1)
+ ((a0_avoid + chain.absorbed_from(S_av)) * absw_avoid1)
).sum(1)
info = dict(
n_seeds=int(len(launches.seeds)), n_streamlines=int(P),
expected_bundle_streamlines=float(seed_prob.sum()), endpoint_rule=end_rule,
endpoint_mass_check=float(endpoints.sum() / max(2 * seed_prob.sum(), 1e-300)),
n_columns=int(3 * nK), tolerance=tol, backward=info_b2, forward=info_f1,
negative_mass_before_clip=dict(density=float(-density[density < 0].sum()),
seed_prob=float(-seed_prob[seed_prob < 0].sum())),
seconds=round(time.time() - t0, 1),
)
return BundleResult(spec["name"], launches.seeds, seed_prob, density, endpoints, info, dcls.astype(np.float32))