Pattern Solving
1. Indexing a Kikuchi Pattern
The angles between the center lines of bands correspond to interplanar angles of the crystal lattice, and the band widths correspond to the reciprocal interplanar distances (pattern on the left). The primary step of pattern solving is the precise determination of the position of Kikuchi Bands. So after at least three bands have been located, a best fit of the lattice planes is searched for by checking through the Miller indices which are allowed by the
structure factor
of the crystal lattice under consideration. A simulation of the pattern finally verifies that the grain orientation and the selected crystal structure are the best matches to the pattern. This check can also be visualized by displaying the overlay of the theoretical pattern on the experimental one (pattern on the right).
The conventional extraction of band positions with Hough transform and butterfly mask
The Hough transform [1] was established in 1962 by P.C.V. Hough, in a complex hardware implementation, for the detection of straight lines or contours in bitonal images, that are images with only two intensity values per pixel, either TRUE = 1 or FALSE = 0. Graytone images are usually skeletonized and binarized to bitonal before a Hough transform is applied.

Indeed the Hough transform is a simple forward variant of the more general Radon transform which was published almost half a century earlier [2]. The Hough transform is a fast technique to localize sparse (line) contours in the bitonal image because zero pixels can be skipped from transformation. The motif are single points of intensity level 1 in the pattern whose intensity is transformed in sinusoidal curves in Hough
space. The sinusoidal curves of these nonzero points
are superimposed by accumulating the counts by 1 for each curve cutting a cell. The curves from points on a straight line in the image (pattern) intersect in one point in Hough space and so result in a peak whose intensity equals the number of points on this straight line. A detailed introduction to the theory and implementations of the Radon and Hough transforms can be found in [3, 5].

Since Kikuchi patterns are graytone rather than bitonal images, a Hough transform is, strictly speaking, not well suited for band detection. Sure, a graytone Kikuchi pattern can be reduced to a bitonal pattern, and then Hough transformed. The result is a significant loss of information, in particular concerning the band profile which is a prerequisite to evaluate a meaningful Pattern Quality (PQ). On the other hand, speed is increased by about a factor
of 1/3, depending
on the threshold of bitonalization (0 or 1) the intensity levels. A further disadvantage of applying a Hough transform on bitonal Kikuchi patterns is a reduced accuracy of orientation data. A better approach to increase speed at the cost of accuracy is to work with a higher binning rate, e.g. 60x60 pixels instead of 100x100 or more pixels per pattern.
The Hough transform is closely related to the (forward) Radon transformation (equation 1) for band localization. The concept of the Hough transform in EBSD publications by imagining sinusoidal curves and butterfly masks is at best confusing the newcomer. Only for historical reasons it is discussed here. In practical applications preference should be given to the backward Radon transform by the sheer fact that it is intuitively accessible. A point in Radon
space simply
correlates to a specific straight line in real (pattern) space whose intensities along the line are accumulated.
For band localization a Hough transform has been modified to accommodate for gray tone patterns. The peaks in Hough space  which again correspond to bands in the pattern  are located by applying a normalized crosscorrelation process with a large butterflyshaped filter mask [5]. The main limitations of this approach are due to the dependence of the band profiles and hence the size and shape of a suitable butterflymasks on the position of
the particular band in the
Kikuchi pattern, the type of pattern, the diffraction geometry and accelerating voltage, the type of crystal lattice and the {h k l}. One mask is in general not sufficient, but several masks are required to analyze one pattern. This in particular true in the case of low crystal symmetry where the band widths span over a large range. Determination of band positions and band widths is less accurate when using (inadequate) mask(s.) The wider the bands are, the larger the masks should be. Large masks unduly increase
computation time. In conclusion, crosscorrelation with a filter mask tends to be ineffectual.


Limitations of "butterfly" filter masks

The band profiles and hence the shape of the "butterfly" peaks depend on

• the position of the particular band in the Kikuchi pattern,
• the type of pattern,
• the diffraction geometry,
• the accelerating voltage,
• the crystal lattice and the particular hkl


The conclusion is

• One mask is not sufficient, several masks are required to analyze one pattern.
• Determination of band positions and band widths is less accurate when using (inadequate) mask(s)
• The wider the bands are, the larger the masks should be. Large masks, however, unduly increase computation time

=> Crosscorrelation with a filter mask tends to be ineffectual.

The Radon Transformation
The geometry of a Kikuchi pattern is specific for the structure and the orientation of the crystallite. For indexing, one only needs to know the location and the width of some of the bands in the pattern. Whereas an experienced user may recognize diffuse bands even on a strong background, automated band localization is not an easy task for the software. Because of the small electron wavelength as compared to the lattice spacings, Bragg angles are very
small in electron
diffraction so that the border lines of Kikuchi bands can very well be approximated by straight lines.
Band localization is performed by applying a Radon transform on the Kikuchi patterns and analyzing peak profiles in Radon space. The general Radon transformation [2] is a functional to transform a manifold in an mdimensional space into a manifold in an ndimensional space. With the normal parameterization of a straight line as the functional kernel, a line in a plane is thus transformed into a single
point R(ρ, φ) in 2dimensional Radon space by
f(x,y) stands for the intensity distribution along the line, δ denotes the Dirac function, ρ is the perpendicular distance of the line from the origin, φ is the angle between the x axis and the normal from the origin to the line. Every point (ρ, φ) in the Radon space thus corresponds to the sum of intensity values along a certain
straight line in the image space.
Reconstruction of the pattern by applying the inverse Radon transform
literally means that a peak in Radon space is projected back into image space along its incoming path. By definition,
the intensity I(ρ, φ) of every single cell (ρ_{i}, φ_{i}) in Radon
space is attributed equally to all pixels (x_{l}, y_{l}) on the related straight line ρ_{i} = x·cos φ_{i} + y·sin φ_{i} in the reconstructed Kikuchi pattern.
(N.B.: The Radon transformation and its Inverse are the basis of backtransformation in computer tomography.)
The EBSD image (i.e., the Kikuchi pattern) is made up by a discrete array [x, y] of graytone image points (socalled pixels). So we consider a discrete Radon transform whereby the integrals are replaced by sums, and the Radon domain consists of an array of discrete cells on a Cartesian grid (ρ, φ). A Kikuchi band
can be imagined to be composed of a bundle of straight lines that may be slightly twisted and shifted against each other. By a "forward" Radon transformation,
the intensity profile of a Kikuchi band in the image space is mapped to a "butterflylike" shape in Radon domain with a bright center and dark cusps on the sides in ρ direction, rather than a single point as were the case of a single line.


A "backward" Radon transformation from cells in Radon space to the pattern according to the inverse transformation (equation 2) has some conceptual and numeric advantages. As mentioned above, a cell in Radon space corresponds to a single straight line in the pattern. So the Radon space rather than the image is scanned point by point, and for each point R(ρ, &phii;) the intensities along the corresponding
straight line in the pattern are accumulated. However, the intensity profile can, as contrasted to a "forward" RT, in addition be interrogated along this line. Thus short fragments of the line outside a band can be excluded from transformation by applying a run length threshold, as well as artifacts of hot spots in the pattern can be skipped by defining intensity thresholds. The result is a clearer domain in Radon space.
Noise can further be removed and contrast enhanced effectively in the Radon transformed pattern by applying a square intensity operator.
The task of locating lines or bands in the diffraction pattern is so reduced to the simpler task of searching for isolated peaks in Radon space. The "butterfly peak " is localized by a peak search with constraints or by evaluating some coefficients of a 1D FFT of this Radon domain [6].
A simple model of Radon peak profiles illustrates band detection as a constraint task


The simplified peak profile model leads to a task with three constraints:

The cusps L and R are local minima, and M is a local maximum: h ≥ h_{min} (peak intensity is above the mean level of intensity.) d ≤ d_{max} (skew of the central peak, depends on hkl).

b_{min}
≤ b ≤ b_{max} (range of Bragg angles φ_{hkl}, voltage U, specimentoscreen distance L, binning)

The angular distance between neighboring peaks depends on crystal lattice and range of hkl: Δρ ≤ ρ_{min} and ΔΦ ≤ Φ_{min}

A simple analysis of Radon peak shapes by measuring the height h, breadth b and displacement d of the cusps L, R and central peak M.

The constraints have been implemented previously as a linked list.

Peak verification by Artificial Neural Networks
(ANN)
Not all peaks in the Radon space that meet the constraints correspond to real bands in a diffraction pattern since the underlying peakshape model for band profile analysis is, for the sake of short execution time, as simple as possible and there are artifacts in Radon transforms. To increase the reliability of band extraction, a layered ANN has been applied to verify the detected bands. ANN
are superior to "sharp" verification methods based on the numerical comparison of the shapes of actual and theoretical peaks, for example by checking a threshold value for the mean square deviation or by a crosscorrelation test with a filter mask. The response function of a neuron is "soft" and "fuzzy". It can process a continuous range of intermediate values due to an adjustable sigmoid function. ANN can "learn" automatically complex relationships among data by training.
They can be easily adjusted to many different peak profiles that are found already in one pattern, but in particular may vary significantly when changing the material or phase, the accelerating voltage, or the diffraction setup in general.
A set of threelayer feedforward neural networks with backpropagation (3LFFwBP) has been implemented [6]:

The number of input neurons, #in, (= pixels on a band profile line) is automatically increased with band width.
(The networks range from 10x6x2 to 20x11x2 neurons. The number of neurons in the hidden layer is (#in + #out)/2, the number of output neurons, #out, is two: yes/no.)
2. Image processing of Kikuchi patterns
From the raw backscatter Kikuchi pattern to the Radon transform.
It is common practice to use backscatter Kikuchi patterns with a digitization depth of 256 gray levels. Background is removed. The raw patterns are reduced in resolution, for the sake of speed, to typically 100x100 pixels (consolidation). In the subsequent processing procedure, noise is further reduced and contrast enhanced by applying nonlinear operators in Radon space [7].
Clean.exe is a small demo tool for backscatter Kikuchi patterns. Kikuchi bands in the displayed pattern are accentuated for interactive detection by applying a nonlinear operator to the Radon space. It also demonstrates that backtransformation from Radon space will not produce a faithful reproduction, simply because the intensity in a Radon cell is equally distributed on the corresponding line in pattern space. Gnomonic projection of the pattern
leads
to a widening of the
integrated Radon peaks and hence to some diffusion of the reconstructed bands.
Download Clean (Clean requires Ms dotNet Framework and Ms Visual C++ 2010 Redistributable Package. It is not optimized for high speed.)
A Pattern Quality Map PQ
reveals grain structure

The determination of pattern quality PQ

hkl and uvw orientation, pattern
quality and
grain boundary maps of a rolled Ti specimen.


Measure
height of "butterfly" peaks resp. peak profile.

Measure
slope of Kikuchi band edges.

Sharp
contours correspond to high spatial frequencies in the Kikuchi pattern =>
Fast Fourier Transform (FFT) and frequency analysis.

Special
case: low dislocation density and high spatial resolution: => measure microshifts and slight rotations of bands in successive patterns of a
grain. => automated approach by evaluating correlation function
of successive patterns.

2D
FFT of the whole initial backscatter Kikuchi pattern (Krieger Lassen,
1994):  Measures in all polar directions
with equal weights.  Picks up pixel noise which has almost the same
spatial frequencies as the band contours.  Is
too slow.

1D
FFT along ρ direction
in Radon space  (Schwarzer and Sukkau, 2000) making use of Fourier
slice theorem (Morneburg, 1995): (1D FFT of RT ~ 2D FFT of the original
image) + RT averages off statistical pixel noise. + ρ direction
is perpendicular on each band = slope of band edges. + Extracts
the fine structure of the bands. + 1D FFT is fast, RT has already
been calculated for band tracing.

_________
[1] Paul V.C. Hough: Method and means for recognizing complex patterns. US Patent 3,069,654 (1962)
[2] J. Radon: Über die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten. Ber. Verh. Sächs. Akad. Wiss. Leipzig, Math.Naturw. Klasse 69 (1917) 262267
English translation by P.C. Parks: On the determination of functions from their integral values along certain manifolds. IEEE Trans. Medical Imaging MI5 (1986) 170176
[3] St. Deans: The Radon Transform and Some of its Applications. John Wiley and Sons, New York 1983.
Dover Paperback edition 1993 ISBN 13: 978486462417
[4] Download Peter Toft: "The Radon Transform  Theory and Implementation", Ph.D. thesis. Dept Mathematical Modelling, Technical University of Denmark, 1996
[5] Download N. Krieger Lassen: Automated Determination of Crystal Orientations from Electron Backscattering Patterns. PhD Thesis, Technical University of Denmark at Lyngby, 1994
[6] R.A. Schwarzer and J. Sukkau: Automated evaluation of Kikuchi patterns by means of Radon and Fast Fourier Transformations, and verification by an artificial neural network.
Adv. Eng. Mat. 5 (2003) 601606 (Download available on request)
[7] J. Sukkau and R.A. Schwarzer: Reconstruction of Kikuchi patterns by intensityenhanced Radon transformation.
Pattern Recognition Letters 33 (2012) 739743
(Download available on request) 
