Grain tracking#

Overview#

Grain tracking establishes a correspondence between the grains of the same sample reconstructed at two load steps (or times). Each far-field reconstruction is turned into a grain graph (VoronoiMeshBuilder.build_graph), and GraphGrainMatcher matches the two graphs by propagating node features with message passing and then selecting mutual best neighbours under a graph-consistency cost.

Why not just nearest-neighbour matching#

Between two load steps a grain moves and rotates, and the reconstruction renumbers everything, so the only thing carried across is the grain’s description. Matching on that description alone – nearest centroid, or nearest orientation – fails in exactly the cases that matter: a deformed sample has many grains of similar orientation, and the displacement that makes tracking interesting is the same displacement that breaks a proximity match.

What is stable is the neighbourhood. A grain’s set of touching neighbours, and their orientations relative to it, survives deformation far better than its own position does. Grain tracking therefore encodes each grain together with its surroundings into a feature vector, and matches those – which is what the message-passing stage is for.

Method#

Each grain is a graph node carrying \((X, Y, Z, \mathrm{Eul}_0, \mathrm{Eul}_1, \mathrm{Eul}_2)\); edges come from tessellation adjacency (grains that share a face). Node features are refined by \(T\) rounds of message passing over the undirected edge set,

(34)#\[ F^{(k+1)}_v = F^{(k)}_v + \sum_{u \in \mathcal{N}(v)} \Phi\!\left(F^{(k)}_u, F^{(k)}_v, k\right).\]

The default \(\Phi\) writes into a single channel, the packed slice M:

(35)#\[\begin{split}\Phi_{\mathrm{M}}\bigl(F_u, F_v, k\bigr) = \begin{cases} \theta\bigl(g_u, g_v\bigr), & k = 0, \\[4pt] \lVert F^{(k)}_v - F^{(k)}_u \rVert_2, & k \ge 1, \end{cases}\end{split}\]

with \(\theta\) the symmetry-aware disorientation of Eq. 17, in the same angle unit as the input. The first round therefore seeds every node with the sum of the misorientations to its neighbours – a rotation-invariant, translation-invariant local signature – and each later round folds in the spread of the signatures one hop further out. After \(T\) rounds \(F_v\) summarises a \(T\)-hop neighbourhood.

Important

The \(X\), \(Y\) and \(Z\) message channels are written as hard zeros at every \(k\). Positions are not propagated; they survive only as the unchanged initial value of \(F^{(0)}_v\), carried through by the residual term of Eq. 34. So the structural part of the signature is purely orientation-derived, and the raw centroid in micrometres sits in the same vector as an angle in degrees with no scaling between them. Because the candidate pool is generated by Euclidean distance over that unscaled vector, candidate generation is dominated by centroid proximity whenever the sample is larger than a few hundred micrometres. The consistency cost below is what recovers the structural information.

Given the refined features \(F^A\) and \(F^B\), each grain \(i\) in A takes its top-\(k\) candidates in B by squared feature distance (torch.cdist), once, before the loop starts. The match cost is

(36)#\[\begin{split} c(i, j) = \lVert F^A_i - F^B_j \rVert^2 \;-\; \frac{\lambda}{\lvert M_{ij} \rvert} \sum_{\substack{p \in \mathcal{N}(i)\\ q = \pi(p)\, \in\, \mathcal{N}(j)}} \lVert F^A_p - F^B_q \rVert^2,\end{split}\]

where \(\pi\) is the current A→B assignment and \(M_{ij}\) is the set of neighbours of \(i\) whose current match lies in \(\mathcal{N}(j)\). Neighbours that are unassigned, or whose match falls outside \(\mathcal{N}(j)\), are skipped and do not enter the mean. Lower cost wins. Assignment is iterative: each A grain proposes its lowest-cost candidate, each B grain is claimed by its lowest-cost proposer, and \(\pi\) is updated.

Warning

The consistency term carries the opposite sign from the base term, as Eq. 36 shows. The base term rewards a candidate whose feature vector is close; the consistency term rewards one whose already-matched neighbours are far apart in feature space. A candidate with no consistent neighbours at all scores better than one whose consistent neighbours coincide. Averaging rather than summing compounds this: agreeing on ten neighbours is worth no more than agreeing on one.

This is the shipped behaviour, and the results in this repository were produced with it. It is documented here rather than changed, because changing it would silently alter every existing match. Raising \(\lambda\) strengthens this term, so \(\lambda = 0\) – pure feature matching – is the conservative setting. Pass your own neighbor_selection_cost_function to supply a conventional consistency reward.

Note

The loop runs a fixed iterations rounds. The "tolerance" key is accepted and echoed back in the metadata but is never read as a convergence criterion, and the “Converged” message prints only on a degenerate round in which no grain had any candidate to propose. Budget iterations directly; there is no early stop on a settled mapping.

The result is a mutual best-neighbour fixed point, not a global optimum: this is not the Hungarian algorithm and does not minimise the total assignment cost. Two grains can stably hold each other’s better match. FragmentationAnalyzer’s detect_splits is the tool for one-to-many lineage, which this matcher by construction cannot express.

Algorithm#

  1. Build a grain graph for each load step from its FF reconstruction (nodes = grains with position/orientation features, edges = tessellation adjacency).

  2. Run \(T = ` ``message_passing_iter`\) rounds of message passing on each graph to produce refined node features \(F^A\), \(F^B\).

  3. For every A grain, precompute its top-\(k\) B candidates by squared feature distance.

  4. Iterate: score each candidate with the feature + neighbour-consistency cost, let each grain pick its best candidate, resolve conflicts by lowest cost (mutual claiming), and update the A→B map; repeat up to iterations or until it converges.

  5. Emit the matched pairs with their final costs, the full A→B mapping, the node embeddings, and a metadata JSON. The five files are written into output_dir as <output_prefix>matches.csv, <output_prefix>a_to_b.csv, <output_prefix>Fa.pt, <output_prefix>Fb.pt and <output_prefix>meta.json.

Parameters that matter#

  • message_passing_iter (\(T\)): number of hops encoded into each node signature; deeper passing spreads structural context further but costs more.

  • neighbor_selection_param["lambda"] (\(\lambda\)): weight of the neighbour-consistency term. Read the warning above before raising it: the term’s sign is inverted relative to the base term, so \(\lambda = 0\) (pure feature matching) is the conservative setting.

  • neighbor_selection_param["topk"]: candidate pool size per A grain. Fixed once before the loop, so a true match outside the initial top-\(k\) can never be recovered however many iterations run.

  • neighbor_selection_param["iterations"]: iteration budget, and the only thing that stops the loop. ["tolerance"] is accepted and echoed but not read.

  • build_graph(CVT_iter=...): CVT iterations for the tessellation the graph is built on; a consistent bounding box per load step keeps the two graphs comparable.

  • output_prefix (default "out_"): prepended verbatim to all five output file names. Matching a sequence of load steps into one output_dir needs a distinct prefix per step pair, otherwise each pair overwrites the one before it. Writing each pair to its own output_dir works equally well – that is what OrientationTracker does.

See Configuration reference for the surrounding reconstruction options.

References#

  • Neural message passing on graphs: Gilmer et al. (2017), Neural Message Passing for Quantum Chemistry, https://arxiv.org/abs/1704.01212 (the update rule here follows the same message/aggregate/update pattern).

  • The neighbour-consistency term follows the usual graph-matching regularizer pattern, in which a second-order term scores how well an assignment preserves local adjacency. Note the sign caveat above: the shipped default does not realise that pattern as written.

  • The assignment loop is a mutual best-neighbour selection, not a global optimum; contrast Kuhn (1955), The Hungarian method for the assignment problem, https://doi.org/10.1002/nav.3800020109, which REIComparison does use for cluster pairing.

See also#