Skip to content

Healing fragmented skeletons

Reconstructed skeletons are often broken into several disconnected fragments. Healing means finding the shortest set of new edges that stitches those fragments back into a single rooted tree.

heal_skeleton does the whole job: it finds the minimal-length bridges between connected components and regenerates the parent vector. The two halves are also available on their own — stitch_fragments returns just the bridging edges, so you can inspect or filter them, and reroot_rewire turns any edited edge set back into a rooted forest, whether the edges came from stitch_fragments or from somewhere else entirely.

import navis_fastcore as fastcore

new_parent_ids = fastcore.heal_skeleton(node_ids, parent_ids, coords)

Two options are worth knowing about:

  • max_dist caps how long a single new edge may be. Gaps wider than that are left alone, so the result can still be fragmented — which is usually what you want, as bridging a huge gap is more likely to be wrong than right.
  • use_radius takes node radii into account when measuring distances, which prefers connecting fragments of similar calibre over merely nearby ones. Pass a float rather than True to weight how much influence radius gets. Note that max_dist is then measured in that augmented space too.

API

Heal a fragmented skeleton by reconnecting its fragments.

Rust re-implementation of the core of navis.heal_skeleton: it finds the minimal-length set of bridges between the skeleton's connected components (see :func:stitch_fragments) and regenerates a single rooted tree.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

coords 
     Array of coordinates for each node.

TYPE: (N, 3) array

method 
     Which nodes may form new edges. ``"ALL"`` (default) considers
     every node; ``"LEAFS"`` restricts bridge endpoints to leaf and
     root nodes (faster, occasionally suboptimal attach points).

TYPE: "ALL" | "LEAFS" DEFAULT: 'ALL'

max_dist 
     Maximum length for any single new edge. Gaps larger than this
     are left unhealed (the result may stay fragmented). ``None``
     means no limit.

TYPE: float DEFAULT: None

min_size 
     Fragments with fewer than this many nodes are excluded from
     healing and stay disconnected.

TYPE: int DEFAULT: None

mask 
     If provided, only these nodes may be used as bridge endpoints.
     Combined (AND) with the ``method`` restriction.

TYPE: (N, ) bool array DEFAULT: None

radius 
     Radius for each node. Only required if ``use_radius`` is set.

TYPE: (N, ) array DEFAULT: None

use_radius 
     If truthy, node radii are taken into account when measuring
     distances, which prioritises connecting fragments of similar
     calibre. Pass a float to weight the effect: higher values give
     radius more influence. To keep this robust we use the mean
     radius of the segment a node belongs to, not the node's own.
     Note that ``max_dist`` is then measured in this augmented space
     too.

TYPE: bool | float DEFAULT: False

threads 
     Number of threads to use. If ``None`` uses all available cores.
     If you are healing many skeletons across several *processes*
     (e.g. ``navis.heal_skeleton(nl, parallel=True)``), set this to a
     small number or — better, since it costs nothing per call — call
     :func:`navis_fastcore.set_num_threads` once per worker.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
new_parent_ids

New parent IDs, in the same order as node_ids. If the skeleton could be fully healed this describes a single tree (one root); otherwise it may still contain several roots.

TYPE: (N, ) array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(4)
>>> parent_ids = np.array([-1, 0, -1, 2])   # two fragments
>>> coords = np.array([[0, 0, 0], [1, 0, 0], [10, 0, 0], [11, 0, 0]], dtype=float)
>>> fastcore.heal_skeleton(node_ids, parent_ids, coords)
array([-1,  0,  1,  2])

Find minimal-length edges to reconnect a fragmented skeleton.

This is the low-level primitive behind :func:heal_skeleton: given a skeleton that consists of several disconnected fragments (connected components), it returns the set of new edges that would connect those fragments into a single tree while minimising the total added length. It does not modify the skeleton.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

coords 
     Array of coordinates for each node.

TYPE: (N, 3) array

mask 
     If provided, only nodes where ``mask`` is ``True`` may be used
     as bridge endpoints. A fragment without any unmasked node can
     not be connected.

TYPE: (N, ) bool array DEFAULT: None

max_dist 
     Maximum length for any single new edge. Fragment pairs whose
     closest eligible nodes are farther apart than this are left
     disconnected. ``None`` means no limit.

TYPE: float DEFAULT: None

radius 
     Radius for each node. Only required if ``use_radius`` is set.

TYPE: (N, ) array DEFAULT: None

use_radius 
     If truthy, node radii are taken into account when measuring
     distances, which biases healing towards connecting fragments of
     similar calibre. Pass a float to weight the effect: higher
     values give radius more influence. Note that ``max_dist`` is
     then measured in this augmented space too.

TYPE: bool | float DEFAULT: False

threads 
     Number of threads to use. If ``None`` uses all available cores.
     If you are stitching many skeletons across several *processes*,
     prefer :func:`navis_fastcore.set_num_threads` — it costs nothing
     per call, whereas this builds a thread pool each time.

TYPE: int DEFAULT: None

RETURNS DESCRIPTION
edges

Pairs of node IDs to connect. At most (#fragments - 1) rows.

TYPE: (M, 2) array

distances

Euclidean length of each new edge. If use_radius is set, this includes the radius component.

TYPE: (M, ) float32 array

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(4)
>>> # Two fragments: {0, 1} and {2, 3}
>>> parent_ids = np.array([-1, 0, -1, 2])
>>> coords = np.array([[0, 0, 0], [1, 0, 0], [10, 0, 0], [11, 0, 0]], dtype=float)
>>> edges, dists = fastcore.stitch_fragments(node_ids, parent_ids, coords)
>>> edges
array([[1, 2]])
>>> dists
array([9.], dtype=float32)

Regenerate the parent array after adding a set of undirected edges.

Takes an edited edge set — the skeleton's own child→parent edges plus new_edges — and orients all of it away from a root, which is what turns a bag of edges back into a rooted forest. This is step 2 of :func:heal_skeleton, exposed on its own for callers who choose their own edges rather than taking the minimal bridges from :func:stitch_fragments.

PARAMETER DESCRIPTION
node_ids 
     Array of node IDs.

TYPE: (N, ) array

parent_ids 
     Array of parent IDs for each node. Root nodes' parents
     must be -1.

TYPE: (N, ) array

new_edges 
     Undirected edges to add, as pairs of node IDs. May be empty, in
     which case this is a pure re-orientation.

TYPE: (M, 2) array

root 
     Preferred root. Its component is rooted here; every other
     component is rooted at its lowest-index node. ``None`` auto-picks
     for all of them.

TYPE: node ID DEFAULT: None

RETURNS DESCRIPTION
new_parent_ids

New parent IDs, aligned with node_ids, roots as -1. Always a valid forest: new_edges that would close a cycle are back-edges to the orienting walk and are dropped, and a component the added edges did not reach simply keeps its own root.

TYPE: (N, ) array

Notes

Not the same as navis_fastcore.reroot, which re-roots an unchanged forest by reversing only the edges between each new root and the old one, and leaves components nobody named byte-identical. This one re-orients everything, because after an edge set changes there is no "unchanged" to preserve. Use reroot to move a root; use this when the edges themselves moved.

Examples:

>>> import navis_fastcore as fastcore
>>> import numpy as np
>>> node_ids = np.arange(4)
>>> parent_ids = np.array([-1, 0, -1, 2])       # two fragments
>>> fastcore.reroot_rewire(node_ids, parent_ids, [(1, 2)])
array([-1,  0,  1,  2])

Rooting the joined skeleton at node 3 instead:

>>> fastcore.reroot_rewire(node_ids, parent_ids, [(1, 2)], root=3)
array([ 1,  2,  3, -1])