# The variant graph approach to improved parent grain reconstruction

Ralf Hielscher  Tuomo Nyyssönen  Frank Niessen  Azdiar A. Gazder  Chemnitz
University of Technology, Department of Mathematics, 09107 Chemnitz, Germany
Swerim AB, 164 40 Kista, Sweden  Technical University of Denmark, Department
of Mechanical Engineering, 2800 Kgs. Lyngby, Denmark  Electron Microscopy
Centre, University of Wollongong, New South Wales 2500, Australia

###### Abstract

The variant graph is a new, hybrid algorithm that combines the strengths of
established global grain graph and local neighbor level voting approaches,
while alleviating their shortcomings, to reconstruct parent grains from
orientation maps of partially or fully phase-transformed microstructures. The
variant graph algorithm is versatile and is capable of reconstructing
transformation microstructures from any parent-child combination by clustering
together child grains based on a common parent orientation variant. The main
advantage of the variant graph over the grain graph is its inherent ability to
more accurately detect prior austenite grain boundaries.

A critical examination of Markovian clustering and neighbor level voting as
methods to reconstruct prior austenite orientations is first conducted.
Following this, the performance of the variant graph algorithm is showcased by
reconstructing the prior austenite grains and boundaries from an example low-
carbon lath martensite steel microstructure. Programmatic extensions to the
variant graph algorithm for specific morphological conditions and the merging
of variants with small mutual disorientation angles are also proposed. The
accuracy of the reconstruction and the computational performance of the
variant graph algorithm is either on-par or outperforms alternate methods for
parent grain reconstruction.

The variant graph algorithm is implemented as a new addition to the
functionalities for phase transformation analysis in MTEX 5.8 and is freely
available for download by the community.

###### keywords:

electron backscattering diffraction (EBSD) , phase transformation ,
orientation relationship (OR) , martensite , parent phase reconstruction

##  1 Introduction

Many alloys undergo partial or complete phase transformation from a metastable
parent to a stable child phase when exposed to thermo-mechanical stimuli.
Alloy design begins with optimizing the high temperature thermo-mechanical
processing regime of the parent microstructure. Here the morphology and
crystallographic texture of the parent phase after high temperature processing
affects the final microstructure, phase fractions and mechanical properties of
the alloy upon transformation during cooling. Alternatively, phase
transformation is also an effective means to improve the mechanical properties
of alloys by refining the final grain size and crystallographic texture of the
final child phase(s) [1, 2]. In the specific case of partial phase
transformation, where some of the parent phase is retained, multi-phase
parent-child microstructures with optimal strength-ductility combinations are
designed [3]. Since microstructure analyses are usually undertaken at room
temperature, it is generally only possible to characterize the transformed
child phase(s), or a combination of remnant parent and child phase(s). Thus,
various methods to reconstruct the high temperature parent phase
microstructure from experimental phase and orientation maps have been
developed [4, 5, 6, 7].

A particular difficulty in reconstructing parent grains are alloys in which
both parent and child phases exhibit a high degree of crystallographic
symmetry. Perhaps the most challenging example in this category is low-carbon
lath martensite formed from high-temperature austenite during quenching.
Typically, and depending on the operative orientation relationship (OR), up to
$24$ individual child orientation variants are generated from a single parent
austenite orientation [8]. A second difficulty to reconstruction is the high
boundary fraction of $\Sigma$3 annealing twins in the parent austenite
microstructure. Twinned grains share a mutual (111) plane across the twin
boundary, and consequently, the six martensitic variants formed on this
particular habit plane (in both twins) are crystallographically close to
equivalent [5]. A single prior austenite orientation may, and often does, have
as many as three twins, all sharing variants across twin boundaries. The third
major difficulty is that martensite variants with low misorientations form
side-by-side as thin laths; bundles of which make up the well-known block
structure in martensite [9]. The low misorientation angle between the laths
within a block makes it difficult to obtain crystallographic information from
the microstructure at the level of individual martensite variant orientations.
Thus, despite a good amount of work towards improving reconstruction
algorithms in recent years, the accurate reconstruction of annealing twin
boundaries in low-carbon steels at the level of individual variants remains a
huge challenge to this day.

Generally speaking, there are two classes of algorithms for parent grain
reconstruction that operate on a grain level, namely, grain graph [10, 8, 11]
and local neighbor voting types, of which the nucleation-growth approach [4,
6, 12] is the most prominent example. Grain graph algorithms consider a graph
in which all child grains in a microstructure are represented as nodes. The
boundaries between a grain and its neighbors are represented as edges that
connect the nodes. By assigning probabilities of belonging to a common parent
grain to these edges, clusters of child grains that are likely to belong to
the same parent grain are identified and reconstructed. The approach is
computationally efficient and considers all grains within the microstructure.
A drawback of this method is that it utilizes scalar probabilities to describe
the likelihood of having a common parent orientation. These probabilities are
extended to higher order neighboring grains without checking whether or not
they apply to the same parent orientation variant; thereby leading to the
erroneous clustering of child grains in some localized areas [8, 11]. As a
consequence, varying degrees of additional processing steps are often required
following the application of the grain graph approach.

As stated previously, the nucleation-growth approach is the most prominent
example of local neighbor level voting algorithms. It identifies nuclei, i.e.
local groups of child grains that have a common parent orientation variant,
and allows these nuclei to grow into the surrounding parent phase. The
determination of the common (and by extension, correct) parent orientation
variant is facilitated by a voting mechanism of the participating child
grains. The main advantage of this algorithm is that it is relatively robust.
A drawback is that some microstructures may not contain enough nuclei to cover
all parent orientations. Furthermore, the growth part of the algorithm may
lead to the reversion of parent orientation variants that may not be the best
fit. In recent work in Ref. [13], the growth stage of nuclei is replaced by
sectioning the map in square grids and applying a voting algorithm to the
grains in each square grid separately to determine parent orientations.

In this study, we introduce a new, hybrid variant graph algorithm to parent
grain reconstruction. The algorithm combines the advantages of the established
grain graph and nucleation-growth approaches while alleviating their
shortcomings. The variant graph enhances and improves on the grain graph
algorithm by enabling transitivity conditions to be satisfied, i.e. the
product of two edge probabilities agreeing with the probability that the two
outer grains belong to the same parent grain. To achieve this, we do not
associate each child grain with only one node in the graph but rather, each
child grain is associated with one node for each of the potential parent
orientation variants. Consequently, the number of nodes associated with a
child grain are the number of parent orientation variants allowed by an
orientation relationship.

Iterating via the variant graph approach automatically generates the most
likely parent orientation for each grain such that no clustering is required.
The use of sparse matrices for the probability graphs and a streamlined
implementation of matrix multiplication results in an efficient and robust
reconstruction algorithm suitable for large orientation microscopy data sets.
The new approach to parent grain reconstruction is implemented in MTEX 5.8 as
as a programmatic addition to the previously established phase transformation
analysis framework [7] and is freely available to the community.

##  2 The example data set: Low-carbon lath martensite steel

The new, hybrid algorithm is introduced by applying it to a low-carbon lath
martensite steel microstructure. The electron backscattering diffraction map
consists of 4 million data points at approximately 0.5 $\mu m$ spacing. All
processing prior to the application of reconstruction algorithms was
undertaken in MTEX 5.8 [14] and entailed: (i) the removal of single-pixel
orientation measurements, leaving $83\%$ indexed points, (ii) the defining of
a grain map with an angular threshold of $3^{\circ}$, and (iii) the
determination of a refined orientation relationship between austenite and
martensite using the method described in Ref. [15].

The map shown in Fig. 1(a) comprises band contrast overlaid with individual
pixels colored by their inverse pole figure (IPF) orientation. The prior
austenite grain boundaries determined by reconstruction in Section 5.5 are
overlaid on the map as black boundaries to highlight the wide distribution of
parent austenite grain sizes. Fig. 1(b) highlights a small region of the map
containing a single, heavily twinned prior austenite grain. The grain
morphology is representative of the hierarchical structure typical of lath
martensite [9]. The (001) pole figure in Fig. 1(c) shows the martensite
orientations of this grain, illustrated by the same IPF colors.

In subsequent sections, this prior austenite grain is also used as a
representative example to review and showcase the performance of the presented
reconstruction algorithms. For example, as shown in Section 3.3, there are
multiple instances where the martensite variant orientations of twinned
austenite grains almost completely overlap.

Figure 1: (a, b) Band contrast maps overlaid with (a) the initial martensite
inverse pole figure colors. The reconstructed parent austenite grain
boundaries (sans $\Sigma$3 boundaries) are shown in black. (b) A single,
heavily twinned parent austenite grain extracted from the map (marked by a
white rectangle in (a)). (c) A (001) pole figure showing the martensite
orientations in (b).

##  3 Established methods of parent grain reconstruction

In this section we review the two most well established grain level parent
grain reconstruction methods. Both methods take advantage of an initial
segmentation of the EBSD data into grains $G_{n}$, $n=1,\ldots,N$, cf. [16].
Each grain is associated with a parent or a child phase and a mean grain
orientation $\mathbf{\boldsymbol{g}}_{n}$.

Assuming a parent-to-child orientation relationship
$\mathbf{\boldsymbol{g}}_{\mathrm{p\to c}}$, all potential parent orientation
variants of a child orientation $\mathbf{\boldsymbol{g}}_{n}$ are given by

$\mathbf{\boldsymbol{g}}_{n}^{j}=\mathbf{\boldsymbol{g}}_{n}S_{j}^{c}\mathbf{\boldsymbol{g}}_{\mathrm{p\to
c}},$ (3.1)

where $S_{j}^{c}$, $j=1,\ldots,|\mathcal{S}^{c}|$ enumerates all child
symmetries. In the case of a degenerated orientation relationship, for
example, the Nishiyama Wassermann OR [17], some of the parent orientation
variants may be symmetrically equivalent. To keep the notation simple in such
situations, we assume that the index $j$ runs over a maximum set of child
symmetries $S_{j}^{c}$ such that none of the parent orientation variants
$\mathbf{\boldsymbol{g}}_{n}^{j}$ are symmetrically equivalent.

The goal of parent grain reconstruction is to compute the true parent
orientation of each child grain $G_{n}$ from all possible parent orientations
$\mathbf{\boldsymbol{g}}_{n}^{j}$. The true parent microstructure of a
transformed microstructure is revealed by targeted surface etching techniques
[10]. Alternatively, the true parent microstructure of recrystallized
austenite reconstructed from individual child grains is generally identified
by

  * i)

Several clusters of neighboring child grains voting for the same parent
orientation.

  * ii)

The morphology of a high-temperature parent phase microstructure, typically
comprising equiaxed grains.

  * iii)

An annealing twin structure exhibiting a boundary morphology typical of
coherent $\Sigma 3$ related twin boundaries [18].

###  3.1 Grain graph based parent grain reconstruction

The method describing the successful identification of clusters of similar
parent orientation variants was first introduced by Gomes and Kestens cf. [11]
and relies on the so-called grain graph. The grain graph is a mathematical
description of the adjacency relationships of the grains $G_{n}$. Each grain
$G_{n}$ corresponds to exactly one node in the graph. Two nodes are connected
by an edge if the corresponding grains share a common grain boundary. During
the reconstruction algorithm, the edges are labeled with weights $P_{m,n}$
describing the probability that two grains $G_{m}$ and $G_{n}$ originate from
a common parent grain.

An example of a grain graph is displayed in Figure 2(a). The nodes labeled
$G_{1},\ldots,G_{9}$ represent the grains. Adjacent grains are connected by
solid lines that are referred to as edges. In order to simplify the example
schematic, we assume an OR with only three possible parent variants, i.e.,
every child grain $G_{n}$ corresponds to only three potential parent
orientations $\mathbf{\boldsymbol{g}}_{n}^{j}$, $j=1,2,3$. The three possible
parent variants of each child grain are visualized by differently colored
sectors.

$\displaystyle G_{3}$$\displaystyle G_{7}$$\displaystyle G_{5}$$\displaystyle
G_{8}$$\displaystyle G_{6}$0.50.90.80.8$\displaystyle G_{4}$$\displaystyle
G_{2}$$\displaystyle G_{1}$$\displaystyle G_{9}$0.50.80.80.60.6 (a) Initial
grain graph

$\displaystyle G_{3}$$\displaystyle G_{7}$$\displaystyle G_{5}$$\displaystyle
G_{8}$$\displaystyle G_{6}$$\displaystyle G_{4}$$\displaystyle
G_{2}$$\displaystyle G_{1}$$\displaystyle G_{9}$ (b) Grain graph after the
first expansion step

Figure 2: Schematic example of a grain graph. The circular nodes represent
child grains $G_{1},\ldots,G_{9}$. Each child orientation is associated with
three potential parent variants, each of which are in turn illustrated by
differently colored sectors. The square node $G_{6}$ represents a retained
parent grain with a “cyan” orientation. In the initial grain graph (a), grains
with a common grain boundary are connected by an edge. The darkness or
brightness of an edge corresponds to the probability associated with the
misorientation angle between best fitting parent variants. For example, grains
$G_{4}$ and $G_{8}$ are connected by a dark high probability edge since they
share a very similar yellow parent orientation. In contrast, grains $G_{8}$
and $G_{5}$ are connected by a bright low probability edge since the green
parent orientations are slightly different for both child grains. Following
the first expansion steps of the Markovian clustering algorithm, all second
neighbors are then connected by edges. The brightness (and probability) of
each of the new edges is computed as the product of the brightness of the
individual segments.

Grain $G_{6}$ is a retained parent grain and, hence, is represented by a
square filled with one color. From the colors, the guess is that:

  * i)

Grains $G_{1}$, $G_{2}$, $G_{4}$, $G_{7}$ and $G_{8}$ originate from a common
yellow parent grain.

  * ii)

Grains $G_{2}$, $G_{5}$ and $G_{8}$ originate from a common green parent
grain.

  * iii)

Grains $G_{3},G_{5},G_{6}$ and $G_{9}$ originate from a common cyan parent
grain.

Obviously, the three guesses cannot simultaneously be true. The challenging
task for any parent grain reconstruction algorithm is to identify the
physically most likely solution.

In the case of grain graph based parent grain reconstruction, random walks are
simulated through the graph to identify strongly connected clusters. More
precisely, the algorithm consists of the following steps:

  1. i)

Constructing the grain graph as described above.

  2. ii)

Assigning a weight $w_{m,n}$ to each edge which describes the probability that
the two adjacent grains $G_{n}$, $G_{m}$ originate from a common parent grain.

  3. iii)

Clustering the graph into strongly connected components, for example, via the
Markovian clustering algorithm [19].

  4. iv)

Determining the best fitting parent orientation for each cluster.

The processes of grain graph construction and clustering are detailed further
as an understanding of these two items is crucial to the introduction of the
new, hybrid variant graph approach in Section 4.

#### Constructing the grain graph

The most critical part in constructing the grain graph is the computation of
edge weights. Edges are either of _parent - child_ or _child - child_ types.
For a _parent - child_ grain pair $G_{m}$ \- $G_{n}$, where
$\mathbf{\boldsymbol{g}}_{m}$ is the parent orientation of $G_{m}$ and
$\mathbf{\boldsymbol{g}}_{n}^{j}$ are the potential parent orientations of the
child grain $G_{n}$ (see Equ. (3.1)), the misorientation angle $\omega_{m,n}$
between the parent orientation $\mathbf{\boldsymbol{g}}_{m}$ and the best
fitting parent variant $\mathbf{\boldsymbol{g}}_{n}^{j}$ is given by

$\omega_{m,n}=\min_{j=1,\ldots,|\mathcal{S}^{c}|}\omega_{p}(\mathbf{\boldsymbol{g}}_{m},\mathbf{\boldsymbol{g}}_{m,j}).$

where $\omega_{p}(\mathbf{\boldsymbol{g}}_{1},\mathbf{\boldsymbol{g}}_{2})$
denotes the angular distance in orientation space modulo parent symmetry.

For two neighboring child grains $G_{m}$, $G_{n}$, the misorientation angle
$\omega_{m,n}$ between the best fitting combination of parent variants is

$\omega_{m,n}=\min_{i,j=1,\ldots,|\mathcal{S}^{c}|}\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j}).$

In order to translate the misfits $\omega_{m,n}$ into probabilities

$P_{m,n}=\Phi(\omega_{m,n})$

a function $\Phi$ is used that is close to $1$ for very small misfits and
decays to zero as the misfit exceeds a certain threshold $\delta$. A common
choice for such a function is the Gauss error function $\mathrm{erf}(x)$
scaled by constants $\sigma$ and $\delta$ as

$\Psi(\omega)=1-\tfrac{1}{2}\left(1+\mathrm{erf}(2\tfrac{\omega-\delta}{\sigma})\right).$
(3.2)

The scaling is chosen such that $\Psi(\delta-\sigma)=0.75$, $\Psi(\delta)=0.5$
and $\Psi(\delta+\sigma)=0.25$. The grain graph is efficiently stored as a
sparse $N\times N$ adjacency matrix $P$, where $N$ is the number of grains,
containing at row $m$ and column $n$ the entry $P_{m,n}$ if the grains $G_{m}$
and $G_{n}$ are connected by an edge with non-zero probability. All remaining
matrix entries are zero.

In Fig. 2(a), the edge weights are the numbers attached to each of the edges.
Furthermore, the darkness of the edges is chosen proportional to the edge
weights. In the more complicated follow up graphs, the numbers are omitted.

It should be noted that because of $\omega_{m,n}=\omega_{n,m}$, the matrix $P$
is symmetric and the initial grain graph is not directed. This property is
lost during the subsequent clustering step.

#### Clustering of the grain graph

While different clustering algorithms may be applied to group grains with a
common parent orientation, the following discussion is limited to the commonly
used Markovian clustering algorithm [19]. The latter algorithm simulates
random walks within a grain graph via the following steps:

  1. i)

Expansion: $P:=P\cdot P$

  2. ii)

Inflation: $P_{m,n}:=P_{m,n}^{\alpha}$

  3. iii)

Normalization: $P_{m,n}:=P_{m,n}/\sum_{o}P_{m,o}$

  4. iv)

Pruning of elements: $P_{m,n}:=0$ if $P_{m,n}<\delta$

The key assumption of the expansion step 1 is as follows: If the probability
to walk from node $m$ to node $o$ is $P_{m,o}$ and the probability to walk
from node $o$ to node $n$ is $P_{o,n}$, then the probability to walk from $m$
via $o$ to $n$ is $P_{m,o}\cdot P_{o,n}$. Accordingly, summing over all
possible intermediate nodes $o$, we obtain the total probability to walk from
$m$ to $n$

$\tilde{P}_{m,n}=\sum_{o=1}P_{m,o}P_{o,n}.$ (3.3)

This is exactly the $(m,n)$-th entry of the product matrix $P\cdot P$ in step
1. As the values $\tilde{P}_{m,n}$ may exceed $1$, they are interpreted as
probabilities only after the normalization step 3. The purpose of the
inflation step 2 just before the normalization step is to emphasise higher
probability edges over lower probability edges. More precisely, the ratio
between two entries in the matrix $P$ becomes more pronounced when higher
inflation parameter $\alpha$ values are used. The pruning in the last step 4
attempts to keep the matrix $P$ as sparse as possible.

The grain graph Fig. 2(a) after a single run of the steps 1-4 is depicted in
Fig. 2(b). It is observed that by connecting all second order neighbours, the
grain graph becomes much more connected. While new edges arise within the
yellow, green or cyan clusters, they also unfortunately arise between grains
that do not share a common parent orientation. Most notably, the grains
$G_{4}$ and $G_{5}$ get connected with a high probability edge even though
they cannot possibly originate from a common parent grain. This occurs because
$G_{4}$ is connected to $G_{5}$ by two routes through $G_{2}$ and $G_{8}$,
respectively. Although both routes contain low probability edges, they sum up
to a high probability edge between $G_{4}$ and $G_{5}$. As a consequence, all
nodes in our example appear as a single cluster. A complex situation as
described above is one of the core reasons behind why the Markovian clustering
algorithm sometimes generates very large clusters of child grains that do not
necessarily agree on a common parent orientation.

By iterating this process, i.e., by considering $P^{2}$, $P^{4}$, $P^{8}$, up
to second, fourth, eight order neighbors are included into the probability
matrix. As a consequence, the matrix $P$ includes more and more non-zero
elements and, hence, becomes less sparse. The combination of the inflation and
normalization steps ensures that during the iteration process for each node,
higher probability edges become stronger while lower probability edges decay
to zero. This keeps the matrix sparse and eventually ensures that the matrix
separates into disconnected components by converging to an idempotent matrix
with all entries being either $0$ or $1$.

#### Computing parent orientations

After the grain graph converges to an idempotent binary matrix, parent grains
are constructed by merging all pairs of child grains $G_{m}$, $G_{n}$ with
$P_{m,n}=1$. The parent orientation $\mathbf{\boldsymbol{g}}^{p}$ of a grain
merged from child grains $G_{m_{1}},G_{m_{2}},\ldots,G_{m_{X}}$ is usually
computed by minimizing the mean misorientation angle to the best fitting
potential parent orientations $\mathbf{\boldsymbol{g}}_{m_{k}}^{j}$ of the
child grains. This is written as the optimization problem

$\min_{\mathbf{\boldsymbol{g}}^{p}}\sum_{k=1}^{X}\min_{j}\omega_{p}(\mathbf{\boldsymbol{g}}^{p},\mathbf{\boldsymbol{g}}^{j}_{m_{k}}).$

Unfortunately, the grain graph does not contain the information about the best
fitting parent orientations $\mathbf{\boldsymbol{g}}_{m_{k}}^{j}$. This makes
the optimization problem computationally expensive to solve. Usually, this
step is the most time consuming in the grain graph approach to parent grain
reconstruction.

###  3.2 Local neighbor level voting based parent grain reconstruction

In local neighbor level voting based reconstruction algorithms, votes for each
potential parent orientation are collected from the neighboring grains of each
child grain. In the schematic example in Fig. 2(a), grain $G_{2}$ collects a
yellow vote from $G_{1}$ and a green vote from $G_{3}$ while $G_{3}$ collects
a yellow vote from $G_{2}$ and two cyan votes from $G_{4}$ and $G_{5}$.

In order to formalize the voting, the misorientation angles between potential
parent orientation variants of the child grains are considered. If a grain
pair comprising a neighboring child grain $G_{m}$ and a parent grain $G_{n}$
is considered, the misorientation angles $\omega_{m,n}^{i}$ between the
potential parent orientations $\mathbf{\boldsymbol{g}}_{m}^{i}$ of $G_{m}$ and
the parent orientation $\mathbf{\boldsymbol{g}}_{n}$ of $G_{n}$ is denoted by

$\omega_{m,n}^{i}=\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n})$

Similar to the grain graph approach, we use a function $\Psi$ to transform the
misorientation angles $\omega_{m,n}^{i}$ into values

$P_{m,n}^{i}=\Psi(\omega_{m,n}^{i})$ (3.4)

that approach zero if the misorientation angle exceeds a certain threshold or
are close to one for small misorientation angles. The value $P_{m,n}^{i}$ is
interpreted as the voting weight for the parent orientation
$\mathbf{\boldsymbol{g}}_{m}^{i}$ of the child grain $G_{m}$. In this sense,
the neighboring parent grain $G_{n}$ generates a voting weight $P_{m,n}^{i}$
for each potential parent orientation $\mathbf{\boldsymbol{g}}_{m}^{i}$ of the
child grain $G_{m}$. Depending on the threshold of the function $\Psi$, most
of these weights will be zero.

In the case of a pair $G_{m}$, $G_{n}$ of neighboring child grains, we have
$|\mathcal{S}^{c}|\times|\mathcal{S}^{c}|$ misorientation angles

$\omega_{m,n}^{i,j}=\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j})$

between all possible combinations of potential parent orientations
$\mathbf{\boldsymbol{g}}_{m}^{i}$ of $G_{m}$ and potential parent orientations
$\mathbf{\boldsymbol{g}}_{n}^{j}$ of $G_{n}$. Again, the function $\Psi$ is
used to transform the misorientation angles into voting weights. More
specifically, for a potential parent orientation
$\mathbf{\boldsymbol{g}}_{m}^{i}$ of grain $G_{m}$, the grain $G_{n}$
generates a vote with the weight

$P_{m,n}^{i}=\max_{j}\Psi(\omega_{m,n}^{i,j}).$

Depending on the threshold angle of the function $\Psi$ and the orientation
relationship between the two child orientations $\mathbf{\boldsymbol{g}}_{m}$
and $\mathbf{\boldsymbol{g}}_{n}$, most of the voting weights will be zero.

By summing the voting weights $P_{m,n}^{i}$ separately for each potential
parent orientation $\mathbf{\boldsymbol{g}}_{m}^{i}$ of $G_{m}$ over all
neighboring grains $G_{n}$, we obtain the final voting weights

$P_{m}^{i}=\sum\limits_{n}P_{m,n}^{i}.$ (3.5)

If it is momentarily assumed that the function $\Psi$ is simply a cutoff
function, i.e., $\Psi(\omega)=0$ if $\omega$ is above a certain threshold and
$\Psi(\omega)=1$ otherwise, then $P_{m}^{i}$ simply counts the number of
neighboring grains that have a potential parent orientation close to
$\mathbf{\boldsymbol{g}}_{m}^{i}$. In order to make the voting weights
comparable across different child grains, the voting weights are often
normalized by

$\bar{P}_{m}^{i}=\frac{P_{m}^{i}}{\sum\limits_{i}P_{m}^{i}}$

such that the sum of all votes for any child grain $G_{m}$ satisfies
$\sum\limits_{i}\bar{P}_{m}^{i}=1$.

In its simplest form, a voting algorithm requires the selection of the parent
orientation $\mathbf{\boldsymbol{g}}_{m}^{i}$ with the highest voting weight
$\bar{P}_{m}^{i}$ for each child grain $G_{m}$. More involved schemes may
assign parent orientations to only those child grains when the highest voting
weight exceeds a certain threshold, or when the difference between the highest
and second highest voting weight is sufficiently large. After parent
orientation assignment, the process is iterated with equal or relaxed
criteria. In fully transformed microstructures, the iteration process is often
started by considering only child - child grain pairs, which is termed as the
nucleation step, followed by several growth steps where only parent - child
grain pairs are considered.

###  3.3 Advantages and drawbacks of established parent grain reconstruction
methods

The global grain graph and the local neighbor level voting approaches to
parent grain reconstruction described in the above two sub-sections have
complementary advantages and limitations. While the grain graph algorithm
considers only the best fitting combination of parent orientations for each
pair of neighboring grains, the voting based algorithm considers all possible
parent orientations for a child grain and accordingly, all possible fits to
the neighboring grains. Furthermore, while the grain graph approach also
considers higher-order neighbors, i.e. grains that are further away, the
voting based approach only considers first-order neighbors and hence makes its
choice based on local and immediate neighbor information.

The aim of the new and hybrid variant graph approach is to combine the
advantages of the two approaches while overcoming their shortcomings. In this
regard, Section 3.1 refers to one of the central assumptions of the
conventional Markovian clustering algorithm which is as follows.

Consider that $P_{m,o}$ is the probability that the two child grains $G_{m}$
and $G_{o}$ belong to the same parent grain and $P_{n,o}$ is the probability
that the child grains $G_{n}$ and $G_{o}$ belong to the same parent grain. In
this case, the product $P_{m,o}\cdot P_{o,n}$ is the probability that the
grains $G_{m}$ and $G_{n}$ belong to the same parent grain. Generally
speaking, this assumption is not true. It may happen that $G_{m}$ and $G_{o}$
agree on a common parent orientation which may be completely different to the
parent orientation that $G_{n}$ and $G_{o}$ agree on. In such a situation, the
true probability $P_{m,n}$ is much lower than $P_{m,o}\cdot P_{o,n}$. The
consequence of this condition not being satisfied is frequently observed when
the conventional Markovian clustering algorithm detects potential parent
grains where no reasonable grain orientation is assigned [7].

Figure 3: (a, b, c) Band contrast maps overlaid with (a) the initial
martensite inverse pole figure colors for a single, heavily twinned parent
austenite grain. The parent austenite grain map reconstructed using the grain
graph algorithm after clustering with (b) $\alpha$ = 1.2 and (c) $\alpha$ =
1.6. (d, e, f) (001) pole figures showing (d) martensite orientations and (e,
f) grain graph based parent austenite orientations with calculated martensite
orientations overlaid on to measured martensite orientations for (e) $\alpha$
= 1.2 and (f) $\alpha$ = 1.6.

This issue is highlighted by showing the result of applying Markovian
clustering to segment the grain graph generated from the example data set in
Fig. 3. The edge weights for the grain graph were determined by Equ. (3.2)
using the parameters $\delta$ = 5°and $\sigma$ = 1.5°. The graph was then
clustered in two separate calculations, first with the inflation parameter
$\alpha$ = 1.2 and then with $\alpha$ = 1.6. After convergence, the parent
orientations were computed in a separate step as outlined in Section 3.1.
Grains that were successfully reconstructed to a parent orientation are shown
using inverse pole figure colors while the grains for which no parent
orientation was found are shown in white. The clusters formed by the algorithm
are marked by thick black boundaries.

Fig. 3(b) clearly shows the effect of using a very low value for the inflation
parameter. Under-clustering results in several clusters that extend beyond the
boundaries of the parent austenite grain and the determined orientations are
insufficient to account for the observed martensite orientations. The latter
is also as shown by the pole figure below in (Fig. 3(e)). Conversely, using a
larger inflation parameter results in over-clustering of the parent austenite
structure (Fig. 3(c)). As opposed to Fig. 3(b), over-clustering enables the
calculation of a larger number of parent orientations with more than 97% of
child grains undergoing reconstruction. The latter also account for the
observed martensite orientations in Fig. 3(e). However, the biggest
disadvantage to over-clustering is the increase in the number of optimization
problems that need to be resolved in the second reconstruction step. In turn,
this issue increases the amount of computational resources needed for
reconstruction. A second consideration is that extreme over-clustering results
in clusters comprising one or two grains; resulting in poorly defined parent
orientations.

Figure 4: (a) Band contrast map overlaid with the parent austenite grain map
reconstructed using the voting algorithm. (b) (001) pole figure showing
martensite orientations, the reconstructed austenite orientations and the
theoretical martensite orientations calculated from these.

On the other hand, local neighbor level voting based reconstruction applies
variant level information between neighboring grain pairs; thus ensuring a
locally viable solution for each reconstructed parent austenite grain.
However, this locally viable solution is reached after applying either: (i) a
nominal orientation relationship referenced from the literature, or (ii) an
average orientation relationship determined for the entire data set. Previous
work has shown that there is considerable local variation in the orientation
relationship between austenite and martensite [20, 21] such that applying a
representative average orientation relationship could result in the local
misindexing of parent austenite variants.

Fig. 4 shows the result of reconstruction using the voting algorithm. For each
child grain a parent orientation was determined based on the votes of
neighboring child grains, as outlined in Section 3.2. The voting based
reconstruction returned a high fraction of local twinned orientations (pink
boundaries), seen as inclusions within larger grains. In addition, although
several parent austenite orientations are indexed as they produce locally
viable solutions, they do not correspond well with the observed martensite
orientations. This aspect is clearly seen in the pole figure in Fig. 4(b).

In summary, while the grain graph algorithm is able to efficiently cluster the
data into segments, it is prone to under and over -clustering as it lacks
information at the individual parent variants level. Meanwhile, applying
variant level information locally in voting based algorithms results in
frequent misindexing; especially when nominal or averaged orientation
relationship are used. As detailed next in Section 4, the new, hybrid variant
graph approach eliminated the shortcomings identified in these two algorithms
by combining variant level information with larger-scale clustering.

##  4 Variant graph based parent grain reconstruction

###  4.1 The variant graph

The variant graph is a generalization of the grain graph. In the grain graph
each child grain is represented by a single node $G_{m}$. Alternatively, the
variant graph contains as many nodes $\mathbf{\boldsymbol{g}}_{m}^{i}$ as the
number of potential parent orientation variants allowed by an orientation
relationship for each child grain $G_{m}$. In both methods, the parent grains
appear as single nodes $\mathbf{\boldsymbol{g}}_{m}$.

Two nodes in the variant graph are connected by an edge if two conditions are
met: (i) they correspond to adjacent grains, and (ii) their misorientation
angle is below a certain threshold. The weighting of these edges is computed
from the misorientation angle between the node orientations using the function
$\Psi$, c.f. Equ. (3.2). More precisely, for two adjacent child nodes
$\mathbf{\boldsymbol{g}}_{m}^{i}$, $\mathbf{\boldsymbol{g}}_{n}^{j}$, the edge
weight is

$P_{m,n}^{i,j}=\Psi(\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j}))$

and for a pair $\mathbf{\boldsymbol{g}}_{m}^{i}$,
$\mathbf{\boldsymbol{g}}_{n}$ of adjacent child - parent nodes, the edge
weight is

$P_{m,n}^{i}=\Psi(\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n})).$

The variant graph for the example in Fig. 2(a) is shown in Fig. 5(a). Since
this simplified example only considers three parent variants, every child
grain appears as three nodes $\mathbf{\boldsymbol{g}}_{n}^{1}$,
$\mathbf{\boldsymbol{g}}_{n}^{2}$ and $\mathbf{\boldsymbol{g}}_{n}^{3}$.
Meanwhile, the number of edges has only increased by one. The additional edge
stems from the two edges
$\mathbf{\boldsymbol{g}}_{5}^{1}-\mathbf{\boldsymbol{g}}_{9}^{2}$ and
$\mathbf{\boldsymbol{g}}_{9}^{3}-\mathbf{\boldsymbol{g}}_{5}^{3}$ connecting
the grains $G_{5}$ and $G_{9}$. Using the variant graph approach, the clusters
of green, yellow and cyan parent orientations are far more separated compared
to the grain graph.

$\mathbf{\boldsymbol{g}}_{3}^{1}$$\mathbf{\boldsymbol{g}}_{7}^{1}$$\mathbf{\boldsymbol{g}}_{5}^{1}$$\mathbf{\boldsymbol{g}}_{8}^{1}$$\mathbf{\boldsymbol{g}}_{4}^{1}$$\mathbf{\boldsymbol{g}}_{2}^{1}$$\mathbf{\boldsymbol{g}}_{1}^{1}$$\mathbf{\boldsymbol{g}}_{9}^{1}$variant
1$\mathbf{\boldsymbol{g}}_{3}^{2}$$\mathbf{\boldsymbol{g}}_{7}^{2}$$\mathbf{\boldsymbol{g}}_{5}^{2}$$\mathbf{\boldsymbol{g}}_{8}^{2}$$\mathbf{\boldsymbol{g}}_{4}^{2}$$\mathbf{\boldsymbol{g}}_{2}^{2}$$\mathbf{\boldsymbol{g}}_{1}^{2}$$\mathbf{\boldsymbol{g}}_{9}^{2}$variant
2$\mathbf{\boldsymbol{g}}_{3}^{3}$$\mathbf{\boldsymbol{g}}_{7}^{3}$$\mathbf{\boldsymbol{g}}_{5}^{3}$$\mathbf{\boldsymbol{g}}_{8}^{3}$$\mathbf{\boldsymbol{g}}_{4}^{3}$$\mathbf{\boldsymbol{g}}_{2}^{3}$$\mathbf{\boldsymbol{g}}_{1}^{3}$$\mathbf{\boldsymbol{g}}_{9}^{3}$variant
3$\mathbf{\boldsymbol{g}}_{6}$ (a) Initial variant graph

$\mathbf{\boldsymbol{g}}_{3}^{1}$$\mathbf{\boldsymbol{g}}_{7}^{1}$$\mathbf{\boldsymbol{g}}_{5}^{1}$$\mathbf{\boldsymbol{g}}_{8}^{1}$$\mathbf{\boldsymbol{g}}_{4}^{1}$$\mathbf{\boldsymbol{g}}_{2}^{1}$$\mathbf{\boldsymbol{g}}_{1}^{1}$$\mathbf{\boldsymbol{g}}_{9}^{1}$$\mathbf{\boldsymbol{g}}_{3}^{2}$$\mathbf{\boldsymbol{g}}_{7}^{2}$$\mathbf{\boldsymbol{g}}_{5}^{2}$$\mathbf{\boldsymbol{g}}_{8}^{2}$$\mathbf{\boldsymbol{g}}_{4}^{2}$$\mathbf{\boldsymbol{g}}_{2}^{2}$$\mathbf{\boldsymbol{g}}_{1}^{2}$$\mathbf{\boldsymbol{g}}_{9}^{2}$$\mathbf{\boldsymbol{g}}_{3}^{3}$$\mathbf{\boldsymbol{g}}_{7}^{3}$$\mathbf{\boldsymbol{g}}_{5}^{3}$$\mathbf{\boldsymbol{g}}_{8}^{3}$$\mathbf{\boldsymbol{g}}_{4}^{3}$$\mathbf{\boldsymbol{g}}_{2}^{3}$$\mathbf{\boldsymbol{g}}_{1}^{3}$$\mathbf{\boldsymbol{g}}_{9}^{3}$$\mathbf{\boldsymbol{g}}_{6}$
(b) Variant graph after the first expansion step

Figure 5: The variant graph corresponding to the grain graph in Fig. 2(a).
Each child grain $G_{n}$ is represented by three nodes
$\mathbf{\boldsymbol{g}}_{n}^{1}$, $\mathbf{\boldsymbol{g}}_{n}^{2}$ and
$\mathbf{\boldsymbol{g}}_{n}^{3}$ which refer to the three potential parent
orientations. An exception is the square parent grain $G_{6}$ which appears as
a single parent orientation $\mathbf{\boldsymbol{g}}_{6}$. In Fig. 5(a) the
nodes are connected by an edge if the child grains are adjacent and the
misorientation angle between the potential parent orientations is below a
certain threshold. Edges are not restricted within the same variant number as
the edge between the orientations $\mathbf{\boldsymbol{g}}_{5}^{3}$ and
$\mathbf{\boldsymbol{g}}_{9}^{2}$ illustrates. Fig. 5(b) displays the variant
graph after the first expansion step.

Here the crucial distinction in the theories behind the grain and variant
graph approaches is emphasized:

Grain graph:

In the grain graph approach, two adjacent grains $G_{m}$ and $G_{n}$ are
connected by an edge with a weight $P_{m,n}$ if there is a pair of parent
orientations $\mathbf{\boldsymbol{g}}_{m}^{i}$,
$\mathbf{\boldsymbol{g}}_{n}^{j}$ among all possible parent orientations of
grain $G_{m}$ and all possible parent orientations of grain $G_{n}$ such that
the misorientation angle
$\omega_{m,n}^{i,j}=\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j})$
is below a certain threshold. However, the critical information on the
specific best fitting pair $i,j$ is not stored.

Variant graph:

In the variant graph approach, all possible parent orientations
$\mathbf{\boldsymbol{g}}_{m}^{i}$ for each child grain $G_{m}$ are stored. Two
possible parent orientations $\mathbf{\boldsymbol{g}}_{m}^{i}$ and
$\mathbf{\boldsymbol{g}}_{n}^{j}$ are connected by an edge with a weight
$P_{m,n}^{i,j}$ if the corresponding grains $G_{m}$ and $G_{n}$ are adjacent
and the misorientation angle
$\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j})$
is below a certain threshold.

In a sense, the variant graph is a generalization of the grain graph such that
the latter may be directly derived from the former by collapsing the many
variant nodes $\mathbf{\boldsymbol{g}}_{m}^{i}$ into single nodes $G_{m}$ and
by replacing the edge probabilities $P_{m,n}^{i,j}$ between the variant nodes
with their maximum

$P_{m,n}=\max_{i,j}P_{m,n}^{i,j}$

over all possible variant pairs which in turn, gives the edge probabilities of
the grain graph.

At first glance, the variant graph may appear to be much larger than the grain
graph, and hence, may be construed as numerically unwieldy to work with.
However, the number of stored edges in the variant graph are of similar
magnitude as that for the grain graph approach. More specifically, if the
misorientation angle threshold is chosen such that for any pair of neighboring
grains $G_{m}$, $G_{n}$ only the best fitting pair
$\mathbf{\boldsymbol{g}}_{m}^{i}$, $\mathbf{\boldsymbol{g}}_{n}^{j}$ of parent
orientations is connected by an edge in the variant graph, then the number of
edges in the variant graph is equal to the number of edges in the grain graph.
Since the amount of memory required to store a graph by a sparse adjacency
matrix only depends on the number of edges, it is safely concluded that the
variant graph is computationally manageable.

One of the main advantages of the variant graph is that information about
second and third best fits is utilized as well. The inclusion of higher order
fits significantly improves the quality of the reconstructed parent grains.
However, this comes at a price, with higher memory usage requirements that
scale linearly with the number of considered fits.

Similar to the grain graph, the variant graph is symmetric at the beginning as
$P_{m,n}^{i,j}=P_{n,m}^{j,i}$ but this property is lost during the clustering
process.

###  4.2 Generalization of the Markovian clustering algorithm

The idea behind the Markovian clustering algorithm is to compute the
probabilities of random walks throughout the grain graph. Therefore, two steps
are crucial: (i) the expansion step 1, and (ii) the normalization step 3.
These two steps are applied to the variant graph in a straightforward manner.

In the expansion step 1 of the grain graph, a probability $\tilde{P}_{m,n}$
that two grains $G_{m}$, $G_{n}$ belong to a common parent grain is computed
by summing the product of such probabilities $P_{m,o}P_{o,n}$ with respect to
all middle grains $G_{o}$. Alternatively, in the variant graph, only those
products of probabilities $P_{m,o}^{i,k}P_{o,n}^{k,i}$ that agree with the
parent orientation $\mathbf{\boldsymbol{g}}_{o}^{k}$ of the middle grain are
summed up. Since all middle grains and all parent variants need consideration,
the sum enlarges to

$\tilde{P}_{m,n}^{i,j}=\sum_{o}\sum_{k}P_{m,o}^{i,k}P_{o,n}^{k,j}.$ (4.1)

It should be noted that although two summations indices in Equ. (4.1) are
included, the expansion step is simply the matrix product $\tilde{P}=P\cdot
P$.

In order to turn the expanded matrix $P^{2}$ again into a probability matrix,
the normalization step 3 of the conventional Markovian clustering algorithm is
required. For the variant graph this is

$\tilde{P}_{m,n}^{i,j}=P_{m,n}^{i,j}/\sum_{i}\bar{P}_{m}^{i}\text{ with
}\bar{P}_{m}^{i}=\sum_{n}\sum_{j}P_{m,n}^{i,j}.$

The normalization ensures that for any grain $G_{m}$, the total sum of
probabilities for its potential parent orientations and all neighbouring
potential parent orientations is one, i.e.,

$\sum_{n}\sum_{i,j}\tilde{P}_{m,n}^{i,j}=1.$

The purpose of the remaining two steps of the Markovian clustering algorithm,
(iii) the inflation step 2, and (iv) the pruning step 4, is the keep the grain
graph sparse and enforce its convergence to an idempotent matrix. Both steps
are generalized to the variant graph as

$P_{m,n}^{i,j}\leftarrow\left(P_{m,n}^{i,j}\right)^{\alpha}$

and

$P_{m,n}^{i,j}\leftarrow 0\text{ if }P_{m,n}^{i,j}<\delta.$

###  4.3 Computing parent orientations

Unlike the grain graph approach, no optimization problems need to be resolved
in order to determine parent orientations. In fact, once the generalized
Markovian clustering algorithm has converged, the edge probabilities
$P_{m_{0},n}^{i,j}$ for a certain child grain $G_{m_{0}}$ are all zero except
for a single entry $P_{m_{0},n^{*}}^{i^{*},j^{*}}=1$. This single edge
indicates that the grains $G_{m_{0}}$ and $G_{n^{*}}$ belong to a common
parent grain with the parent orientation of $G_{m_{0}}$ being
$\mathbf{\boldsymbol{g}}_{m_{0}}^{i^{*}}$ and the parent orientation of
$G_{n^{*}}$ being $\mathbf{\boldsymbol{g}}_{n^{*}}^{j^{*}}$.

In fact, even the requirement of full convergence for the generalized
Markovian clustering may be relaxed. In this case, for all possible parent
orientations $\mathbf{\boldsymbol{g}}_{m}^{i}$ of a fixed child grain $G_{m}$,
the most robust solution is to compute the sum of the edge probabilities to
all other grains, i.e.,

$\bar{P}_{m}^{i}=\sum_{n}\sum_{j}P_{m,n}^{i,j}$

and select the parent orientation $\mathbf{\boldsymbol{g}}_{m}^{i}$
corresponding to the largest value of $\bar{P}_{m}^{i}$. When normalized to
one by setting

$P_{m}^{i}=\bar{P}_{m}^{i}/\sum_{i}\bar{P}_{m}^{i}$ (4.2)

the values are interpreted as probabilities voting for the parent orientation
$\mathbf{\boldsymbol{g}}_{m}^{i}$ of the child grain $G_{m}$. In this respect,
the variant graph directly resembles the voting based parent grain
reconstruction approach from Section 3.2.

This final step of parent orientation determination is much faster than the
corresponding step in the grain graph approach.

###  4.4 Variant graph clustering of the example data set

Fig. 6 shows the results of parent grain reconstruction using the variant
graph algorithm, along with the reconstructed orientations and calculated
martensite variants on (001) pole figures. The edge weights for the variant
graph were determined in a similar manner as the grain graph using Equ. (3.2)
and the parameters $\delta$ = 5°and $\sigma$ = 1.5°. The variant graph was
then run through the Markovian clustering algorithm using an inflation
parameter $\alpha$ = 1.05. The graph was used to reconstruct parent austenite
orientations after 3 and 10 iterations.

Using the variant graph algorithm, all the grains in the original map have
been successfully assigned a parent austenite orientation. In addition, there
is no spilling over of clusters to neighboring parent grains as seen when
using the grain graph in Fig. 3(b). Since the variant graph stores the
orientations as well as the probability value for each edge, there is no
chance of such spillover. Inspection of the pole figure indicates that the
variants calculated from the reconstructed parent orientations account for
each martensite orientation in the original grain map after only 3 iterations.
Fig. 6(c) shows the result of parent grain reconstruction after 7 more
iterations, i.e., for a total of 10 iterations. At this point, all child
grains are assigned parent austenite orientations and all martensite
orientations are accounted for. There is, however, a slight difference in the
regions assigned to the various parent orientations.

Figure 6: (a, b, c) Band contrast maps overlaid with (a) the initial
martensite grain map for a single, heavily twinned parent austenite grain and
parent austenite grain map reconstructed with the variant graph algorithm
after (b) 3 and (c) 10 iterations, along with (d, e, f) the (001) pole figures
showing (d) martensite orientations and parent austenite orientations after
(e) 3 and (f) 10 iterations with calculated martensite orientations overlaid
on measured martensite orientations. Figure 7: (a, b, c) Edges and nodes in a
variant graph for a selected martensite grain and (d, e, f) the parent
orientations from the variant graph algorithm after (a, d) 0, (b, e) 3 and (c,
f) 10 iterations. The edges in the top image comprise the IPF colors after the
parent orientation of each edge. The area marked with a dashed line in (a) is
looked at more closely in Fig. 9.

The progress of the variant graph algorithm for a selected grain in the
martensite grain map is shown in Fig. 7. The upper figure shows a selected
grain in the upper left-hand region of the prior austenite grain shown in 6,
as well as the neighboring grains for which variant pairs are found that meet
the threshold requirement for the creation of connecting edges. The edges are
IPF color coded corresponding to the parent austenite orientation of each
edge. The lower figure shows the IPF colored prior austenite orientations
assigned to each grain after accumulating votes according to Section 4.3.

Initially, as shown in Fig. 7(a), the selected grain is only connected to its
immediate neighbors by edges formed by pairs of variants. Initially, 22 nodes
are connected by a total of 162 edges, implying that multiple variant
combinations were found to satisfy the threshold criterion for each pair of
nodes. In lath martensite, it is typical that in each grain, the threshold
requirement is met by two variants with low misorientation that make up its
block structure (V1-V4, V2-V5 and V3-V6 pairing according to Ref. [9]). In
addition, the variant combinations corresponding to an annealing twin for the
best fitting candidate orientation typically meet the threshold requirement,
as well as its closest variant pairs. This indicates that as many as sixteen
edges corresponding to different variant combinations may be potentially found
that connect each pair of nodes in the graph.

After 3 iterations, new edges are created to account for second- and third-
degree neighbors. The number of edges decreased relative to the number of
nodes, as the weaker connections are pruned by the inflation step of the
algorithm. Observation of the IPF coloring of the edges indicates that two
colors appear to dominate and correspond to twinned prior austenite
orientations. After 10 iterations, tenth-order neighbors would nominally be
considered for the selected grain. However, this is not possible due to the
fact that the edges must be connected by variants that produce a mutually
acceptable parent orientation. At this point, it means that all possible edges
for the selected grain are found and additional iterations only result in a
gradual pruning of weaker edges. Thus, it is clear that the clusters of
orientations cannot grow too large even if the inflation parameter is set to
1. The IPF coloring of the edges after 10 iterations indicates that the
selected grain would give a good match with either of the twinned prior
austenite grains in the immediate vicinity.

As opposed to the grain graph, the variant graph is able to find and preserve
the information on every potential prior austenite solution for each original
grain in the graph. A simple accumulation of votes as outlined in Section 3.2
is then enough to produce a prior austenite orientation map that is, based on
visual observation, morphologically sound when it comes to non-twinned
boundaries, as well as being able to reliably satisfy each individual
martensite grain with a suitable parent orientation. As shown by the prior
austenite orientation map in Fig. 7(c), some ambiguously indexed, small prior
austenite grains remain in local regions when twinned prior austenite grains
that are in close proximity share martensite variant orientations in the
graph.

Fig. 8 shows the convergence behavior of the number of non-zero edges at
different inflation parameters. As mentioned previously, for an inflation
parameter of 1, the convergence of the Markovian graph is not enforced. For
this value, the number of edges quickly increases to its maximum up to 11
iterations following which it then slowly decays towards a constant value.
This value is much larger than the number of child grains, meaning that the
convergence is not towards a single parent variant per child grain but rather,
towards a steady state in the computation.

Slightly increasing the inflation parameter to 1.02 or 1.05 leads to
convergence to a low number of non-zero edges. This means the algorithm
eventually decides on one possible parent orientation per martensite grain.
Increasing the inflation parameter even further to 1.1 and then up to 1.4
leads to extremely rapid convergence for a low maximum value of non-zero
edges. Also, the maximum number of non-zero edges is reached after fewer
iterations with higher inflation parameter values. This scenario corresponds
to a locally restricted search for the best possible parent orientation.

Figure 8: The convergence behavior of the amount of non-zero edges in the
variant graph as a function of inflation parameter.

The range of optimal inflation parameter values, denoting a good trade-off
between computational efficiency and an accurate reconstruction that considers
many neighboring grains and alternative solutions, is between 1.05 and 1.1. No
significant changes in the reconstructed parent microstructure are visible for
continued iterations after the maximum number of non-zero edges is reached.
Further iterations mostly led to deletion of already unfavorable edges and
therefore, did not affect the final result. Stopping the computation when the
maximum number of edges are reached is therefore recommended to avoid
unnecessary additional iterations and to keep the information on alternative
solutions for the best fitting parent orientation.

##  5 Discussion

In this section, a couple of technical details are discussed following which
extensions to the variant graph approach are presented. The computational
performance of the new, hybrid method is also reported.

###  5.1 Pure random walks

As noted in Section 4.2, the parent orientations are computed even if the
Markovian clustering algorithm has not converged. In the specific case that
the inflation parameter $\alpha$ is set to $1$, the sum $P_{m}^{i}$ of the
edge weights $P_{m,n}^{i,j}$ derived in Equ. (4.2) are interpreted as a
generalization of the voting weights defined in Equ. (3.5). The major
difference is that in conventional local neighbor level voting based parent
grain reconstruction, the weight include only first order neighbors while in
the variant graph approach, neighbours up to $2^{n}$ order, where $n$ is the
number of iterations, are considered. This explains why the variant graph
approach gives better results even for very small $n$. In the corner case of
$n=0$, it simply resembles the conventional neighbor level voting based
algorithm.

The advantage of running the variant graph algorithm with an inflation
parameter $\alpha=1$ and small $n$ is that the resulting voting weight
$P_{m}^{i}$ is used efficiently to identify child grains when multiple parent
orientations are assigned with similar probability. The drawback of setting
$\alpha=1$ is that the number of non-zero edges in variant graph increases
with the number of iterations. This makes the algorithm unfeasible for large
grain maps and many iterations.

###  5.2 Diagonal entries

The diagonal entries $P_{m,m}^{i,i}$ of the variant graph matrix correspond to
self loops of each node of the variant graph. In the grain graph, the weights
of these self loops is initialized by $1$, thus making it equally probable to
start a random walk at each node. In the case of the variant graph, the
weights are initialized to $P_{m,m}^{i,i}=1/|\mathcal{S}^{c}|$, which makes it
equally probable to start a random walk with every possible parent orientation
variant.

The variant graph also contains so-called pseudo diagonal entries
$P_{m,m}^{i,j}$, which correspond to edges connecting different parent
variants of the same child grain. Those edges are interpreted as follows:
Assuming a certain probability $P_{m}^{i}$ for parent orientation variant
$\mathbf{\boldsymbol{g}}_{m}^{i}$ and a second, very similarly oriented parent
orientation variant $\mathbf{\boldsymbol{g}}_{m}^{j}$, then a certain
probability for $\mathbf{\boldsymbol{g}}_{m}^{j}$, namely, $P_{m}^{i}\cdot
P_{m,m}^{i,j}$ also exists.

Pairs of similarly orientated parent variants appear frequently for
experimentally derived and refined irrational orientation relationships that
are close to but do not coincide with an ideal rational orientation
relationship.

Although these pseudo diagonal entries possess a physical interpretation,
their inclusion in the variant graph is not preferred.

###  5.3 Specific morphological conditions

Up to this point, the initial probability $P_{m,n}^{i,j}$ that two child
grains belong to a common parent grain is based solely on the misorientation
angle
$\omega_{p}(\mathbf{\boldsymbol{g}}_{m}^{i},\mathbf{\boldsymbol{g}}_{n}^{j})$
between the potential parent orientations. On the other hand, morphological
information may also contribute to this probability.

As an example, consider the boundary curvature $\kappa$ and denote by
$\kappa_{m,n}$ the average over the all boundary segments separating the
grains $G_{m}$ and $G_{n}$. Following this, the misorientation based weights
$P_{m,n}^{i,j}$ are updated according to the curvature by

$\hat{P}_{m,n}^{i,j}=(1+\beta\kappa_{m,n})P_{m,n}$ (5.1)

where $\beta$ is a modelling parameter that controls the influence of the
curvature to the final weight. The effect of this modification is that only
straight boundaries, and not curved boundaries, are more likely to be chosen
by the algorithm as parent boundaries. This is especially helpful if the
algorithm is presented with an ambiguous situation of finding the correct twin
boundary. It is emphasized that any other morphological criterion can also be
implemented, as the framework for parent grain reconstruction is a
programmatic and fully customizable implementation [7].

###  5.4 Merging variants with small mutual disorientation angles

An effective means of reducing memory requirements and computation time is
merging closely related variants, i.e., variants that have a small
misorientation to each other. For the example data set of austenite to
$\alpha^{\prime}$ martensite transformation, the number of variants are
reduced from 24 to 12, which reduces the number of edges by a factor four.
This four-fold reduction in number of edges roughly reduces the computation
time and memory requirements by a factor of four as well. While it may seem
that valuable information about the microstructure is discarded by this step,
it is worth noting that child variants with low misorientation to each other
are usually paired as neighboring laths and are often not detected during
grain reconstruction by the angular threshold criterion in the first place.
Inspection of the morphology of the grain map in Fig. 6 reveals many
irregularly shaped grains, which significantly deviate from a lath-like
morphology. It suggests that rather than individual laths, the grains
represent blocks comprising multiple variants with a low mutual disorientation
angle instead. This observation is made even for a relatively low angular
threshold value of 3°. If it is assumed that variant level precision is lost
when the initial grain map is constructed, it follows that the incorporation
of full variant level precision into the edges of a variant graph for
clustering is simply not necessary. While this assertion definitely bears out
in the present and prominently difficult case of $\alpha^{\prime}$ martensite
microstructures in steel, it should be re-examined on other data sets with
different parent-child symmetry combinations.

Fig. 9 shows the effect of merging closely related parent variants on the
number of edges and the final reconstruction result for the example data set.
Using a threshold value $\delta=8.5^{\circ}$ to determine candidate parent
variants, a total of 8 edges are established between grains A and B (Fig.
9(a)). Fig. 9(b) shows the variant indices and the misorientation angle
between the parent variants for each individual edge. Closer inspection
reveals that the edges represent closely related parent variants forming two
clusters of twin-related parent orientations (see (111) pole figure in Fig.
9(c)). In Fig. 9(d) and (e), merging closely related parent variants reduces
the number of edges between grains A and B from eight to two. In the present
case, the lowest misorientation angle between the edges formed by closely
related variants represents the strength of the combined edge.

Figure 9: (a) A small section of the example data set (see Fig. 7(a)), showing
IPF colored edges according to the mean parent orientation corresponding to
the edge. (b) The IPF colored edges between neighboring child grains A and B
labelled with the parent variant numbers for the two grains, separated by the
angular deviation of the candidate parent variants. (c) (111) pole figure
showing the candidate parent variant orientations. The shared (111) plane is
highlighted with a red circle. (d) The edges between grain A and its
neighboring grain after merging of closely related variants. (e) The number of
edges between grains A and B have been reduced from eight to two by the
merging process. (f) The final reconstruction result after 10 iterations of
clustering following the merging of closely related variants, showing
excellent agreement with the parent grain reconstruction from 24 variants in
Fig. 6(c).

When closely related variants are merged according to this procedure, the
resulting reconstruction returns a pair of closely related parent orientations
for each child grain. The determination of the final parent orientation
therefore requires an additional step to restore variant level precision. The
voting algorithm outlined in Section 3.2 is efficient in choosing the locally
best fitting parent variant out of the two options determined by the
clustering algorithm. Fig. 9(f) shows the result of applying this procedure on
the variant graph reconstruction result of the example data set. The threshold
value for edge detection is $\delta$ = 5°, and the above merging procedure of
closely related parent variants is applied. The inflation parameter is
$\alpha$ = 1.05 and clustering is allowed to proceed for 10 iterations. The
variant level detail is restored by applying the neighbor level voting
algorithm from Section 3.2 to choose the locally best fitting variant from the
two closely related variants. Fig. 9(f) shows good agreement with the
reconstruction using all 24 variants in Fig. 5(a)(c).

###  5.5 Performance of the variant graph algorithm

Figure 10: Comparison of the memory usage vs. time for parent grain
reconstruction of the 4 million pixel data set from Fig. 11 using the variant
graph algorithm with 24 and 12 variants as discussed in Section 5.4. Figure
11: Reconstructed prior austenite grains with IPF coloring overlaid on the
$\alpha^{\prime}$ martensite band contrast map. $\Sigma$3 boundaries are
highlighted in white.

Comparing the performance of the grain graph method with the performance of
the variant graph method is not straightforward. While the number of edges is
significantly smaller in the grain graph, the calculation of parent
orientations in the grain graph method requires a separate step and the
additional post processing steps are generally non-optional. If the
orientation clusters are of only interest, the grain graph algorithm is a
quick and robust way of obtaining them. However, as shown in Fig. 6, these
clusters rarely correspond to prior austenite grains. With the variant graph
approach, the parent orientations are automatically obtained from the graph
and only minor post processing is necessary. Running the variant graph
algorithm with a large threshold value (as in the current example) yields a
good result. However, when working with large data sets, hundreds of millions
of edges are created which in turn, translates to high memory usage. In this
case, a significant reduction in memory usage is obtained when the extension
from Section 5.4 is applied which merges variants with mutually close
disorientation.

Fig. 10 shows the memory usage versus time for reconstructing the full example
data set, a map of 4 million pixels (see Fig. 11). The plot compares the
performance of the variant graph approach using all 24 variants versus 12
variants as per the adaptation from Section 5.4. As expected, the memory usage
is significantly reduced when only 12 variants are used. The 24 variant
implementation peaked at 62.2 Gb whereas the 12 variant implementation only
required 27.5 Gb at its peak. The 12 variant implementation took 416 s on an
Intel(R) Core(TM) i9-10920x processor and was thus 16 % faster than the 24
variant implementation.

The amount of memory required is directly proportional to the number of non-
zero edges in the graph. The performance metrics presented in Fig. 10 are just
an indicator of the code performance, with all reconstruction parameters kept
constant for the different runs. In reality, parameters require tuning for
optimal performance with each algorithm. While the code requires a fair amount
of memory, its computational performance and efficiency makes it an ideal
candidate for virtual memory use when physical memory is insufficient. As a
last resort, large data sets could be sectioned and reconstructed in smaller
subsets to avoid out-of-memory errors.

Fig. 11 shows the reconstruction of the full example data set, consisting of 4
million data points. The reconstruction was undertaken using the variant graph
approach with the extension presented in Section 5.4 and an inflation
parameter $\alpha$ of 1.05. The reconstructed prior austenite grains are shown
in IPF coloring superimposed onto the $\alpha^{\prime}$ martensite band
contrast map with twin boundaries highlighted in white. No post processing was
applied.

##  6 Conclusions

This study introduces the new variant graph algorithm for improved parent
grain reconstructions from orientation maps of partially or fully phase
transformed microstructures. Using the well-known and challenging example of
low-carbon lath martensite steel, the algorithm’s inherent accuracy in
reconstructing parent austenite grains and boundaries is showcased and its
computational performance is assessed for a 4 million point data set.

The variant graph is capable of reconstructing transformation microstructures
from any parent-child combination. It is a hybrid algorithm that combines the
generalization of the global grain graph with the strengths of the local
neighbor level voting based approach. The key advantage of the variant graph
is its ability to store all possible parent orientations for each child grain
such that following parent grain reconstruction, no additional post processing
steps are necessary.

The unique advantages offered by programmatic extensions to the variant graph
algorithm include: (i) the ability to account for specific morphological
conditions other than the misorientation angle, like boundary curvature, when
reconstruction algorithms are faced with ambiguous microstructures, and (ii)
the merging of variants with small mutual disorientation angles as an
effective means of reducing memory requirements and computation time for
parent grain reconstruction.

The variant graph algorithm is implemented as an addition to the phase
transformation analysis module in MTEX 5.8 and is freely available for
download by the community.

##  7 Acknowledgements

This work is partially financed by the Strategic Innovation Program for
Metallic Materials, Vinnova, the Swedish Energy Agency, and Formas as well as
the European Union’s Research Fund for Coal and Steel research program under
grant agreement number RFCS-2018-847296. Frank Niessen acknowledges the Danish
Council for Independent Research (Grants DFF-8027-00009B and DFF-9041-00145B)
for financial support.

## References

  * Niessen et al. [2021a] F. Niessen, A.A. Gazder, D.R.G. Mitchell, and E.V. Pereloma.  In-situ observation of nucleation, growth and interaction of deformation-induced $\alpha^{\prime\prime}$ martensite in metastable Ti–10V–2Fe–3Al.  _Materials Science and Engineering A_ , 802(140237), 2021a.  ISSN 09215093.  doi: 10.1016/j.msea.2020.140237.
  * Kundu and Bhadeshia [2007] S. Kundu and H.K.D.H. Bhadeshia.  Crystallographic texture and intervening transformations.  _Scripta Materialia_ , 57(9):869–872, 2007.  ISSN 13596462.  doi: 10.1016/j.scriptamat.2007.06.056.
  * Edmonds et al. [2006] D.V. Edmonds, K. He, F.C. Rizzo, B.C. De Cooman, D.K. Matlock, and J.G. Speer.  Quenching and partitioning martensite-A novel steel heat treatment.  _Materials Science and Engineering A_ , 438-440:25–34, 2006\.  ISSN 0921-5093.  doi: 10.1016/j.msea.2006.02.133.
  * Cayron et al. [2006] C. Cayron, B. Artaud, and L. Briottet.  Reconstruction of parent grains from EBSD data.  _Materials Characterization_ , 57(4-5):386–401, 2006.  ISSN 10445803.  doi: 10.1016/j.matchar.2006.03.008.
  * Miyamoto et al. [2010] G Miyamoto, N Iwata, N Takayama, and T Furuhara.  Mapping the parent austenite orientation reconstructed from the orientation of martensite by EBSD and its application to ausformed martensite.  _Acta Materialia_ , 58(19):6393–6403, 2010.  ISSN 13596454.  doi: 10.1016/j.actamat.2010.08.001.  URL http://dx.doi.org/10.1016/j.actamat.2010.08.001.
  * Germain et al. [2012] L. Germain, N. Gey, R. Mercier, P. Blaineau, and M. Humbert.  An advanced approach to reconstructing parent orientation maps in the case of approximate orientation relations: Application to steels.  _Acta Materialia_ , 60(11):4551–4562, 2012.  ISSN 1359-6454.  doi: https://doi.org/10.1016/j.actamat.2012.04.034.  URL https://www.sciencedirect.com/science/article/pii/S135964541200290X.
  * Niessen et al. [2021b] F. Niessen, T. Nyyssönen, A.A. Gazder, and R. Hielscher.  Parent grain reconstruction from partially or fully transformed microstructures in mtex.  _Accepted for publication in Journal of Applied Crystallography_ , 2021b.  doi: https://arxiv.org/abs/2104.14603v1.
  * Nyyssönen et al. [2016] T. Nyyssönen, M. Isakov, P. Peura, and V.T. Kuokkala.  Iterative Determination of the Orientation Relationship Between Austenite and Martensite from a Large Amount of Grain Pair Misorientations.  _Metallurgical and Materials Transactions A: Physical Metallurgy and Materials Science_ , 47(6):2587–2590, 2016.  ISSN 10735623.  doi: 10.1007/s11661-016-3462-2.
  * Morito et al. [2003] S. Morito, H. Tanaka, R. Konishi, T. Furuhara, and T. Maki.  The morphology and crystallography of lath martensite in Fe-C alloys.  _Acta Materialia_ , 51:1789–1799, 2003.  ISSN 13596454.  doi: 10.1016/j.actamat.2006.07.009.
  * Brust et al. [2021] A. Brust, E. Payton, T. Hobbs, V. Sinha, V. Yardley, and S. Niezgoda.  Probabilistic Reconstruction of Austenite Microstructure from Electron Backscatter Diffraction Observations of Martensite.  _Microscopy and Microanalysis_ , pages 1–21, 2021.  ISSN 1431-9276.  doi: 10.1017/s1431927621012484.
  * Gomes de Araujo et al. [2021] E. Gomes de Araujo, H. Pirgazi, M. Sanjari, M. Mohammadi, and L.A.I. Kestens.  Automated reconstruction of parent austenite phase based on the optimum orientation relationship.  _Journal of Applied Crystallography_ , 54, 2021.  doi: 10.1107/S1600576721001394.
  * Bernier et al. [2014] N. Bernier, L. Bracke, L. Malet, and S. Godet.  An alternative to the crystallographic reconstruction of austenite in steels.  _Materials Characterization_ , 89, 2014.  ISSN 1044-5803.  doi: https://doi.org/10.1016/j.matchar.2013.12.014.
  * Huang et al. [2020] C.-Y. Huang, H.-C. Ni, and H.-W. Yen.  New protocol for orientation reconstruction from martensite to austenite in steels.  _Materialia_ , 9, 2020.  ISSN 2589-1529.  doi: https://doi.org/10.1016/j.mtla.2019.100554.
  * Bachmann et al. [2010] F. Bachmann, R. Hielscher, and H. Schaeben.  Texture analysis with MTEX - free and open source software toolbox.  _Diffusion and Defect Data Pt.B: Solid State Phenomena_ , 160:63–68, 2010.
  * Nyyssönen et al. [2016] T. Nyyssönen, M. Isakov, P. Peura, and V.T. Kuokkala.  Iterative determination of the orientation relationship between austenite and martensite from a large amount of grain pair misorientations.  _Metallurgical and Materials Transactions A_ , 47:2587–2590, 2016.
  * Bachmann et al. [2011] F. Bachmann, R. Hielscher, and H. Schaeben.  Grain detection from 2d and 3d EBSD data–specification of the MTEX algorithm.  _Ultramicroscopy_ , 111:1720–1733, 2011.
  * Nishiyama [1934] Z. Nishiyama.  X-Ray investigation of the mechanism of the transformation from face-centred cubic lattice to body-centred cubic.  Technical report, 1934.
  * Mahajan et al. [1997] S. Mahajan, C.S. Pande, M.A. Imam, and B.B. Rath.  Formation of annealing twins in f.c.c. crystals.  _Acta Materialia_ , 45:2633–2638, 1997.  doi: https://doi.org/10.1016/S1359-6454(96)00336-9.
  * van Dongen [2000] S. van Dongen.  _Graph Clustering by Flow Simulation_.  PhD thesis, University of Utrecht, 2000.
  * Cayron [2014] C. Cayron.  Ebsd imaging of orientation relationships and variant groupings in different martensitic alloys and widmanstätten iron meteorites.  _Materials Characterization_ , 94:93–110, 2014.  doi: https://doi.org/10.1016/j.matchar.2014.05.015.
  * Sandvik and Wayman [1983] B.P.J. Sandvik and C.M. Wayman.  Characteristics of Lath Martensite: Part I. Crystallographic and Substructural Features.  _Metallurgical Transactions A_ , 14(4):809–822, 1983.  doi: 10.1007/BF02644284.