Pattern Solving
1. Indexing a Kikuchi Pattern
A Kikuchi pattern can be interpreted as a gnomonic projection of the crystal lattice under the beam spot on the flat registration screen. The angles between the centerlines of bands correspond to interplanar angles of the crystal lattice, and the bandwidths correspond to the reciprocal interplanar spacings. This means that the geometry of a Kikuchi pattern is specific to the structure and the orientation of the crystallite. The bands can therefore
be indexed with the MILLER indices of the associated lattice planes. To do this, the bandwidths are converted into lattice plane spacings using BRAGG's equation. Furthermore, the angles between the band centers are determined and these values are compared with the lattice plane spacings and the angles between the lattice planes of the crystal structure of the material to be examined. To index a Kikuchi pattern, you only need to know the positions and widths of a few bands. So the most important
step in pattern solving is to precisely determine the positions of Kikuchi bands. While a skilled user can easily detect even diffuse bands on a strong background, automatic band localization is a task not so easily accomplished with software. In practice, it has proven successful to localize the bands by applying a Radon transformation to the Kikuchi pattern.
2. Radon versus Hough Transformation
2a. The Radon Transformation
The statement in Johann Karl RADON's publication from 1917 is that for every direct transformation from a manifold in mdimensional space to a manifold in ndimensional space, there also clearly exists an inverse transformation. It was not until recently, with the development of image reconstruction in computer tomography, that the Radon transform found major practical applications. The inverse Radon transform is also particularly advantageous for the
evaluation of Kikuchi patterns as it allows the simple implementation of filter functions.
In the 2dim space R^{2} the Radon transformation [1] is often defined as a continuous function that projects the intensity distribution f(x, y) along a line S in an image f(φ,ρ) into the 2dim Radon space. The transformation process is defined by the line integral
and the backprojection operator
In particular, a straight line S can be parametrized as bx + ay = ab (xintercept yintercept equation) or as
Hence,
ρ is the distance of the straight line from the coordinate origin and φ is the angle between the xaxis and the perpendicular to the origin (i.e. the point at the center). φ is limited to 0° ... 180°. δ denotes the Dirac delta function. Thus, a straight line in a 2dim
image
domain is associated to exactly one point
(φ, ρ) in the 2dim Radon domain.
The digitally recorded Kikuchi pattern, however, consists of a discrete matrix f[x, y] of grayscale image points called pixels. We must therefore consider a discrete Radon transformation, with the integrals replaced by sums. The image domain has the size of the recorded pattern, that are Mx × Ny pixels, or is binned by m × n for the sake of higher speed but at the cost of reduced accuracy. The Radon domain consist of an array of F×R
discrete cells on a Cartesian grid (φ, ρ). The size is adjusted to the angular resolution and the density of the scanned points in the EBSD measurement.
To give an example for an angular resolution of O° one will set
It is advantageous to finally normalize the Radon domain to an empty background pattern to compensate for the intersection lengths of the straight lines and other artifacts.
The concept of Radon transformation has some advantages for band localization [2, 3]. A Kikuchi band can be thought of as a bundle of straight lines slightly rotated and shifted with respect to each other. Thus, applying the Radon transform, the intensity profile of a band is mapped pixel by pixel not to a sharp point, as would be the case with a single straight line, but smeared out in a kind of "butterfly" motif
in the Radon domain. These peaks are much easier to localize than bandlike motifs in the Kikuchi pattern. After the reverse transformation, the width, position and intensity profile of the Kikuchi band under consideration are known. Once at least three bands of a pattern have been determined, indexing can take place. In practice, however, considerably more bands are required to obtain a unique and reliable solution.
The implementation of the inverse Radon transformation offers particular advantage in the construction of the Radon domain from the pattern. Each cell in the Radon domain is firmly correlated with a specific straight line in the pattern, whose intensity values can be interrogated directly, interpolated and rounded if necessary, accumulated and then stored in this cell. A clever approach is so to traverse the domain in Radon space inversely
cell by cell (φ, ρ), instead of traversing the Kikuchi pattern and transforming pixel by pixel into a sinoidal curve in the Radon domain. Since successive points on the straight line
are considered, the intensity profile along the line can be interrogated. For example, sections of the straight line have similar intensity inside a band and a cusp or a peak at the bordering Kikuchi lines. Short sections that indicate lines (partly) outside a band, can be skipped during the transformation by applying a runlength filter. Similarly, artifacts and intensity peaks ("hot spots") can be masked out by
applying local bounds along the intensity profile. Locally
excessive intensity values occur at the zone axes, for example, while diffraction points or dynamic diffraction effects can cause unusually high or low intensity modulations. Applying a nonlinear intensity operator to the domain [3] can further suppress noise and effectively improve contrast. Overall, intensity evaluation along straight lines with the "inverse" construction of the Radon transform results in a clean domain in Radon space.
A nearpattern image can be reconstructed from the Radon transform using the backprojection operator, in a similar way to image reproduction as is common in computer tomography. The inverse transform specifies which straight line in the image space is associated with each cell in the Radon domain, and the stored intensity is equally attributed to all points on that line. The Radon backprojection does not provide the original
image, but produces a smoothed image. In general, statistical noise is reduced. The Kikuchi bands in an originalpattern
are bordered by slightly hyperbolic instead of straight lines.This may cause a further
blur in back projection.
Applying a Radon transformation to the Kikuchi pattern simplifies the inherently difficult task of locating lines and bands, since only isolated peaks in the Radon domain need to be found. The "butterflylike" peaks are best located by a peak search with constraints or by evaluating some coefficients of a 1D FFT of the Radon domain along ρdirection. These peaks are assigned to Kikuchi bands in the pattern according to the inverse Radon
transform
[3].
2b. The Hough Transformation
Fortyfive years after the publication of the Radon transformation, the Hough transformation was proposed by Paul V.C. HOUGH in a patent [4]. The underlying objective was to locate straight lines in a discrete image with binary intensity distribution fb(x, y), which originally represented particle tracks in a bubble chamber. The Hough transform is widely used in image processing to find edges and straight
lines in binary images. It is more convenient to substitute the slope intercept parameterization of y = b  (b/a)× x , as specified in the original patent, with the polar parameterization of the straight line. The transformation from the image to the Hough domain then writes:
The image domain and the Hough domain are 2dimensional spaces with Cartesian coordinates (x, y) and (ρ , φ), respectively. The common interpretation is that each point (x, y) in the image space is transformed to a sinoidal curve
If points (x, y) in the image lie on a straight line, their sinoidals intersect at a common point and their intensity is accumulated to a peak in the Hough domain.
In a binary image, pixels only take a value of either 1 or 0, so the value on each sinoidal is either 1 or 0. The Hough transform is a particularly fast method to locate sparse straight lines with isolated intensity values = 1, because pixels with intensity values = 0 are skipped during the transformation. Only for pixels with fb(x, y) = 1 the sinoidals are calculated and get intensity = 1. Thus, the height of
the Hough peaks is equal to the number of
intersecting sinoidals, i.e. the number of nonzero points on the corresponding line in the image. The discretization, inverse transform, and subsequent detection of bands are the same as described above for the Radon transform.
Originally, the discrete Hough transform was defined only for binary (bitonal, 1pixel) images. In a first step, grayscale images are converted to binary images by an edge filter before the Hough transform is carried out. Since Kikuchi patterns are grayscale and not binary images, a Hough transform is, strictly speaking, not well suited for band detection. Of course, a grayscale Kikuchi pattern can be reduced to a binary pattern, and then Hough
transformed. The result
is a significant loss of information, especially with respect to the band profile used to evaluate a meaningful Pattern Quality (PQ). On the other hand, the speed is increased by about a factor
of 1/3, depending
on the threshold of binarization (0 or 1) of the intensity levels. Another disadvantage of applying a Hough transform to binary Kikuchi patterns is a lower accuracy of orientation data. A better approach to increase speed, at the expense of accuracy, is to work with a higher binning rate, e.g. 60x60 pixels instead of 100x100 or more pixels per pattern.
The discrete Hough transform was therefore "modified" in [5] to account for and evaluate grayscale patterns. Thus the Hough transformation loses the advantage of high speed by skipping pixels with zero intensity. The result is quite similar to that of the direct Radon transformation without the runlength filter as discussed above. The theory and implementations of Radon and Hough transformations are presented in detail in [6, 7]. The Hough
transformation and,
moreover, its modification for grayscales are special cases of the Radon transformation. The essential difference between the Radon transform and the "modified" Hough transform in BKP analysis lies in the method of how the transformed domains are constructed from the image domain and rounding of values is carried out.
In early EBSD analyses, peaks were located in the "Hough" domain by applying a normalized crosscorrelation process with a large "butterflyshaped" filter mask. In the simplest model, a rectangular pot profile was applied to the band intensity [5]. The main drawbacks of this method are the dependence of the band profile on the position of the band in the Kikuchi pattern, the type of pattern, the diffraction geometry, the accelerating
voltage, the
lattice type, and the {h k l} of the band to be detected. To satisfy this, the filter mask must be matched to the current band profile. Incorrectly matched masks will result in inaccurately determined band positions and bandwidths. The wider a band is, the larger the mask would have to be. Large masks increase the computing time extremely. A single mask is generally not sufficient; several masks are required to analyze a pattern. Overall, crosscorrelation with a filter mask tends to be ineffective.

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 ineffective.

2c. Conclusion
The inverse Radon transform ation above is a way of looking at how a data point in Radon space is obtained from the pixels along a particular straight line (φ, ρ) in the image space of the Kikuchi pattern.The line is interrogated according to the intensities of the intersected pixels
for accumulation. In contrast, the Hough transformation considers how each pixel in the image space
of the Kikuchi pattern is mapped to the Hough space into a bundle of sinusoids
representing all straight lines (φ, ρ) that intersect that pixel. They are
all assigned the same pixel intensity. Finally, the sinusoids of all pixels are overlaid
in Hough space and those related to dominant lines intersect in the form of
butterfly shapes.
The advantages of the Radon transformation include its conceptual simplicity and robustness. S is the path used for integration along the projection lines. For curves that are not straight lines, the natural extension is
to project along the given curves, e.g., along hyperbolas, which
are in fact the exact
boundary lines of Kikuchi bands.
The Hough formalism obscures the simplicity of the underlying transformation. The designation of Hough Transform, however, is prevalent in the EBSD literature, perhaps of not being aware of the history.
The
(inverse) Radon transform is ideal not only for parallel data processing on a
GPU (Graphics Processor Unit) to unburden the CPU (Central Processor Unit) for
band indexing and orientation calculations, but also for intelligent software
with neural networks (AI). [2, 3]
The general Radon transformation in R^{n} is an integral transformation that transforms a function f by integration along lines into a function Rf defined on the R^{m}. The Radon transformation has found a wide range of applications in digital image and signal processing [6]. Examples are electron microscopy of macromolecular assemblies such as viruses and protein complexes, barcode scanners, reflection seismology, and solving
hyperbolic partial differential equations. The ODF has been constructed from pole figures by Radon transformation [8], and the algorithm is implemented in the MTEX software package which is available for free [9]. A popular application is the inverse Radon transformation in (axial) medical computer tomography (CT) to recover the twodimensional image from the measured Xray projections [10].
3. 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 are implemented as a linked list.

4. Peak verification by Artificial Neural Networks
(ANN)
Not all peaks in the Radon space that satisfy the constraints correspond to real bands in a diffraction pattern, since the underlying peakshape model for band profile analysis is, in the interest 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 was used to verify the detected
bands [2]. ANN
are superior to "sharp" verification methods based on numerical comparison of the shapes of actual and theoretical peaks, e.g., 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 automatically "learn" complex relationships between data through training.
They can be easily adjusted to many different peak profiles that are already present in one pattern, but in particular may vary significantly in general, especially with a change in material or phase, accelerating voltage, or diffraction setup in general.
A set of threelayer feedforward neural networks with backpropagation (3L FFwBP) was implemented [2]:
• 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, and the number of output neurons, #out, is two: yes/no.)
• The neural networks were trained by backpropagation on the peak intensity distributions in Radon space of 80 real Kikuchi bands.
• The hit rate exceeds 99.2% of correctly detected bands with 9 bands per pattern.
_________
[1] DownloadJ. 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 R. Lohner: On the determination of functions from their integrals along certain manifolds. in [6]: S.R. Deans: The Radon transform and some of its applications, Appendix A, p. 204217. John Wiley & Sons. New York (1983).
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
[2] 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)
[3] J. Sukkau and R.A. Schwarzer: Reconstruction of Kikuchi patterns by intensityenhanced Radon transformation.
Pattern Recognition Letters 33 (2012) 739743
(Download available on request)
[4] Paul V.C. Hough: Method and means for recognizing complex patterns. US Patent 3,069,654 (1962)
[5] Download N. Krieger Lassen: Automated Determination of Crystal Orientations from Electron Backscattering Patterns. PhD Thesis, Technical University of Denmark
at Lyngby, 1994
[6] S.R. Deans: The Radon Transform and Some of its Applications. John Wiley and Sons, New York 1983.
Dover Paperback edition 1993 ISBN 13: 978486462417
[7] Download Peter Toft: The Radon Transform  Theory and Implementation. Ph.D. thesis. Dept Mathematical Modelling, Technical University of Denmark, 1996
[8] K.G. van den Boogaart, R. Hielscher, J. Prestinc and H. Schaeben: Kernelbased methods for inversion of the Radon transform on SO(3) and their applications to texture analysis. J. Computational and Applied Mathematics 199 (2007) 122–140
[9] R. Hielscher and H. Schaeben: A novel pole figure inversion method: Specification of the MTEX algorithm. J. Appl. Cryst. 41 (2008) 1024–1037
[10] K.L. Wininger: Basis of CT  The Radon Transform. Radiologic Technology 84 (2013) 413418
