1# Rotation-invariant Pattern Detection
2For pattern detection, the orientation of the pattern is usually not known a priory. The process should not be decelerated more than necessary while the pattern detection algorithm looks for all possible rotated copies of the template. Therefore, rotation invariance is a critical requirement.
3Moment invariants can achieve rotation invariance without the need for point to point correlations, which are difficult to generate in smooth fields. For an introduction, we recommend
4
5*Flusser, J., Suk, T., & Zitová, B. (2016). 2D and 3D Image Analysis by Moments. John Wiley & Sons*.
6
7
8We have implemented the prototypes of two vtk filters that together are able to perform pattern detection. The algorithm, which we used, is described in
9
10*Bujack, R., & Hagen, H. (2017). Moment Invariants for Multi-Dimensional Data. In Modeling, Analysis, and Visualization of Anisotropy (pp. 43-64). Springer, Cham*.
11
12The first filter computes the moments and the second one performs the normalization based on the given pattern and computes the similarity. They are able to handle two- and three-dimensional scalar, vector, and matrix fields in the format of a vtkImageData. The architecture with inputs and outputs and their types can be found in the following figure.
13
14![The architectiure of the moments module.][workflow with types]
15
16[workflow with types]: chartTypes.jpg "The architectiure of the moments module."
17
18The architecture illustrated with example images is shown the following figure.
19
20![The architectiure of the moments module.][workflow with images]
21
22[workflow with images]: chartOverview.jpg "The architectiure of the moments module with example images."
23
24<!--
25# Theory
26Moments are the projections of a function with respect to a function space basis. We can think of them as the coordinates that represent the pattern.
27They can then be used to construct moment invariants - values that do not change under certain transformations.
28We will follow the normalization approach for the construction of moment invariants. That means a standard position is defined by demanding certain moments to assume fixed values and all functions are transformed to match it.
29Then the remaining moments form a complete and independent set of moment invariants.
30
31In *Dirilten, H., & Newman, T. G. (1977). Pattern matching under affine transformations. IEEE Transactions on Computers, 26(3), 314-317*, Dirilten and Newman suggest the use of moment tensors for the construction of moment invariants through tensor contraction for scalar functions.
32Langbein et al. have generalized the definition of the moment tensor to tensor valued functions in *Langbein, M., & Hagen, H. (2009). A generalization of moment invariants on 2D vector fields to tensor fields of arbitrary order and dimension. Advances in Visual Computing, 1151-1160*.
33
34**Definition:** For a tensor field $T:\R^d\to\R^{d^n \times d^m}$ with compact support, the **moment tensor** $\leftidx{^o}M$ of order $o\in\N$ takes the shape
35\begin{equation} \begin{aligned}\label{mom_tensor2}
36\leftidx{^o}M=\int_{\R^d} x^{\otimes o} \otimes T(x)\d^d x,
37\end{aligned}\end{equation}
38where $x^{\otimes o}$ denotes the $o$-th tensor power of the vector $x$.
39-->
40
41# Extensions
42The **MomentInvariants** module contains actually a bunch of extra algorithms and helper classes.
43
44The class **vtkMomentsHelper** provides functions for the moments computation that will be needed by vtkComputeMoments and vtkMomentInvariants.
45
46The class **vtkMomentsTensor** provides the functionality to treat tensors of arbitrary dimension and rank. It supports addition, outer product, and contractions.
47
48The algorithm **vtkSimilarityBalls** is a filter that takes the similarity field as produced by vtkMomentInvariants and a grid of type vtkImageData. It computes the local maxima in space plus scale and produces the output localMaxSimilarity that contains the similarity value together with the corresponding radius at the maxima. All other points are zero.
49For further visualization, it also produces two output fields that encode the radius through drawing a solid ball or a hollow sphere around those places.
50The second input, i.e. the grid, steers the resolution of the balls. It is helpful if its extent is a multiple of the first input's. Then, the circles are centered nicely.
51The spheres/circles are good for 2D visualizations, because they can be laid over a visualization of the field.
52The balls are good for 3D volume rendering or steering of the seeding of visualization elements.
53The 2D visualzation is described in
54
55*Bujack, R., Hotz, I., Scheuermann, G., & Hitzer, E. (2015). Moment invariants for 2D flow fields via normalization in detail. IEEE transactions on visualization and computer graphics, 21(8), 916-929*
56
57and the 3D counterpart in
58
59*Bujack, R., Kasten, J., Hotz, I., Scheuermann, G., & Hitzer, E. (2015, April). Moment invariants for 3D flow fields via normalization. In Visualization Symposium (PacificVis), 2015 IEEE Pacific (pp. 9-16). IEEE*.
60
61A schematic overview of the use of vtkSimilarityBalls with example images is given in the following Figure.
62
63![The extended architectiure of the moments module.][workflow of vtkSimilarityBalls]
64
65[workflow of vtkSimilarityBalls]: chartBalls.jpg "The extended architectiure of the moments module: vtkSimilarityBalls."
66
67The algorithm **vtkReconstructFromMoments** is a filter that takes the momentData as produced by vtkComputeMoments or vtkMomentInvariants and a grid.
68It reconstructs the function from the moments, just like from the coefficients of a Taylor series.
69For the reconstruction, we need to orthonormalize the moments first. Then, we multiply the coefficients with their corresponding basis function and add them up.
70There are in principal three applications.
71First, if we put in the moments of the pattern and the grid of the pattern, we see which parts of the template the algorithm can actually grasp with the given order during the pattern detection. Tte following Figure shows images created using moments up to second order.
72
73![The extended architectiure of the moments module.][workflow to reconstruct the pattern]
74
75[workflow to reconstruct the pattern]: chartReconstructPattern.jpg "The extended architectiure of the moments module: reconstruction of the pattern."
76
77Second, if we put in the normalized moments of the pattern and the grid of the pattern, we can see how the standard position looks like. There might be several standard positions due to the ambiguity of the eigenvectors that differ by rotations of 180 degree and possibly a reflection. The algorithm will use the first one. In the previous Figure, the reflection along the x-axis would also be a standard position.
78
79Third, if we put in the moments of the field and the original field data, we can see how well the subset of points, on which the moments were computed, actually represents the field. The following Figure depicts an example using a 16 x 16 coarse grid and moments up to second order.
80
81![The extended architectiure of the moments module.][workflow to reconstruct the field]
82
83[workflow to reconstruct the field]: chartReconstructField.jpg "The extended architectiure of the moments module: reconstruction of the field."
84