Structure tensor

In mathematics, the structure tensor, also referred to as the second-moment matrix, is a matrix derived from the gradient of a function. It summarizes the predominant directions of the gradient in a specified neighborhood of a point, and the degree to which those directions are coherent. The structure tensor is often used in image processing and computer vision.
The 2D structure tensor.
Continuous version.
For a function formula_1 of two variables , the structure tensor is the 2×2 matrix
where formula_3 and formula_4 are the partial derivatives of formula_1 with respect to "x" and "y"; the integrals range over the plane formula_6; and "w" is some fixed "window function", a distribution on two variables. Note that the matrix formula_7 is itself a function of .
The formula above can be written also as formula_8, where formula_9 is the matrix-valued function defined by
If the gradient formula_11 of formula_1 is viewed as a 2×1 (single-column) matrix, where formula_13 denotes transpose operation, turning a row vector to a column vector, the matrix formula_9 can be written as the matrix product formula_15, also known as an outer product, or tensor product. Note however that the structure tensor formula_16 cannot be factored in this way in general except if formula_17 is a Dirac delta function.
Discrete version.
In image processing and other similar applications, the function formula_1 is usually given as a discrete array of samples formula_19, where "p" is a pair of integer indices. The 2D structure tensor at a given pixel is usually taken to be the discrete sum
Here the summation index "r" ranges over a finite set of index pairs (the "window", typically formula_21 for some "m"), and "w"["r"] is a fixed "window weight" that depends on "r", such that the sum of all weights is 1. The values formula_22 are the partial derivatives sampled at pixel "p"; which, for instance, may be estimated from by formula_1 by finite difference formulas.
The formula of the structure tensor can be written also as formula_24, where formula_9 is the matrix-valued array such that
Interpretation.
The importance of the 2D structure tensor formula_7 stems from the fact eigenvalues formula_28 (which can be ordered so that formula_29) and the corresponding eigenvectors formula_30 summarize the distribution of the gradient formula_31 of formula_1 within the window defined by formula_17 centered at formula_34.
Namely, if formula_35, then formula_36 (or formula_37) is the direction that is maximally aligned with the gradient within the window.
In particular, if formula_38 then the gradient is always a multiple of formula_36 (positive, negative or zero); this is the case if and only if formula_1 within the window varies along the direction formula_36 but is constant along formula_42. This condition of eigenvalues is also called linear symmetry condition because then the iso-curves of formula_1 consist in parallel lines, i.e there exists a one dimensional function formula_44 which can generate the two dimensional function formula_1 as formula_46 for some constant vector formula_47 and the coordinates formula_48.
If formula_49, on the other hand, the gradient in the window has no predominant direction; which happens, for instance, when the image has rotational symmetry within that window. This condition of eigenvalues is also called balanced body, or directional equilibrium condition because it holds when all gradient directions in the window are equally frequent/probable.
Furthermore, the condition formula_50 happens if and only if the function formula_1 is constant (formula_52) within formula_53.
More generally, the value of formula_54, for "k"=1 or "k"=2, is the formula_17-weighted average, in the neighborhood of "p", of the square of the directional derivative of formula_1 along formula_57. The relative discrepancy between the two eigenvalues of formula_7 is an indicator of the degree of anisotropy of the gradient in the window, namely how strongly is it biased towards a particular direction (and its opposite). This attribute can be quantified by the coherence, defined as
if formula_60. This quantity is 1 when the gradient is totally aligned, and 0 when it has no preferred direction. The formula is undefined, even in the limit, when the image is constant in the window (formula_61). Some authors define it as 0 in that case.
Note that the average of the gradient formula_62 inside the window is not a good indicator of anisotropy. Aligned but oppositely oriented gradient vectors would cancel out in this average, whereas in the structure tensor they are properly added together. This is a reason for why formula_15 is used in the averaging of the structure tensor to optimize the direction instead of formula_62.
By expanding the effective radius of the window function formula_17 (that is, increasing its variance), one can make the structure tensor more robust in the face of noise, at the cost of diminished spatial resolution. The formal basis for this property is described in more detail below, where it is shown that a multi-scale formulation of the structure tensor, referred to as the multi-scale structure tensor, constitutes a "true multi-scale representation of directional data under variations of the spatial extent of the window function".
Complex version.
The interpretation and implementation of the 2D structure tensor becomes particularly accessible using complex numbers. The structure tensor consists in 3 real numbers
where formula_67 , formula_68 and formula_69 in which integrals can be replaced by summations for discrete representation. Using Parseval relationship it is clear that the three real numbers are the second order moments of the power spectrum of formula_1. The following second order complex moment of the power spectrum of formula_1 can then be written as
where formula_73 and formula_74 is the direction angle of the most significant eigenvector of the structure tensor formula_75 whereas formula_76 and formula_77 are the most and the least significant eigenvalues. From, this it follows that formula_78 contains both a certainty formula_79 and the optimal direction in double angle representation since it is a complex number consisting of two real numbers. It follows also that if the gradient is represented as a complex number, and is remapped by squaring (i.e. the argument angles of the complex gradient is doubled), then averaging acts as an optimizer in the mapped domain, since it directly delivers both the optimal direction (in double angle representation) and the associated certainty. The complex number represents thus how much linear structure (linear symmetry) there is in image formula_1, and the complex number is obtained directly by averaging the gradient in its (complex) double angle representation without computing the eigenvalues and the eigenvectors explicitly.
Likewise the following second order complex moment of the power spectrum of formula_1, which happens to be always real because formula_1 is real,
can be obtained, with formula_76 and formula_77 being the eigenvalues as before. Notice that this time the magnitude of the complex gradient is squared (which is always real).
However, decomposing the structure tensor in its eigenvectors yields its tensor components as
where formula_87 is the identity matrix in 2D because the two eigenvectors are always orthogonal (and sum to unity). The first term in the last expression of the decomposition, formula_88, represents the linear symmetry component of the structure tensor containing all directional information (as a rank-1 matrix), whereas the second term represents the balanced body component of the tensor, which lacks any directional information (containing an identity matrix formula_87). To know how much directional information there is in formula_1 is then the same as checking how large formula_91is compared to formula_77.
Evidently, formula_93 is the complex equivalent of the first term in the tensor decomposition, whereas formula_94is the equivalent of the second term. Thus the two scalars, comprising three real numbers,
where formula_96 is the (complex) gradient filter, and formula_97 is convolution, constitute a complex representation of the 2D Structure Tensor. As discussed here and elsewhere formula_17 defines the local image which is usually a Gaussian (with a certain variance defining the outer scale), and formula_99 is the (inner scale) parameter determining the effective frequency range in which the orientation formula_100 is to be estimated.
The elegance of the complex representation stems from that the two components of the structure tensor can be obtained as averages and independently. In turn, this means that formula_93 and formula_102 can be used in a scale space representation to describe the evidence for presence of unique orientation and the evidence for the alternative hypothesis, the presence of multiple balanced orientations, without computing the eigenvectors and eigenvalues. A functional, such as squaring the complex numbers have to this date not been shown to exist for structure tensors with dimensions higher than two. In Bigun 91, it has been put forward with due argument that this is because complex numbers are commutative algebras whereas quaternions, the possible candidate to construct such a functional by, constitute a non-commutative algebra.
The complex representation of the structure tensor is frequently used in fingerprint analysis to obtain direction maps containing certainties which in turn are used to enhance them, to find the locations of the global (cores and deltas) and local (minutia) singularities, as well as automatically evaluate the quality of the fingerprints.
The 3D structure tensor.
Definition.
The structure tensor can be defined also for a function formula_1 of three variables "p"=("x","y","z") in an entirely analogous way. Namely, in the continuous version we have formula_104, where
where formula_106 are the three partial derivatives of formula_1, and the integral ranges over formula_108.
In the discrete version,formula_24, where 
and the sum ranges over a finite set of 3D indices, usually formula_111 for some "m".
Interpretation.
As in the three-dimensional case, the eigenvalues formula_112 of formula_113, and the corresponding eigenvectors formula_114, summarize the distribution of gradient directions within the neighborhood of "p" defined by the window formula_17. This information can be visualized as an ellipsoid whose semi-axes are equal to the eigenvalues and directed along their corresponding eigenvectors.
In particular, if the ellipsoid is stretched along one axis only, like a cigar (that is, if formula_76 is much larger than both formula_77 and formula_118), it means that the gradient in the window is predominantly aligned with the direction formula_36, so that the isosurfaces of formula_1 tend to be flat and perpendicular to that vector. This situation occurs, for instance, when "p" lies on a thin plate-like feature, or on the smooth boundary between two regions with contrasting values.
If the ellipsoid is flattened in one direction only, like a pancake (that is, if formula_118 is much smaller than both formula_76 and formula_77), it means that the gradient directions are spread out but perpendicular to formula_124; so that the isosurfaces tend to be like tubes parallel to that vector. This situation occurs, for instance, when "p" lies on a thin line-like feature, or on a sharp corner of the boundary between two regions with contrasting values.
Finally, if the ellipsoid is roughly spherical (that is, if formula_125), it means that the gradient directions in the window are more or less evenly distributed, with no marked preference; so that the function formula_1 is mostly isotropic in that neighborhood. This happens, for instance, when the function has spherical symmetry in the neighborhood of "p". In particular, if the ellipsoid degenerates to a point (that is, if the three eigenvalues are zero), it means that formula_1 is constant (has zero gradient) within the window.
The multi-scale structure tensor.
The structure tensor is an important tool in scale space analysis. The multi-scale structure tensor (or multi-scale second moment matrix) of a function formula_1 is in contrast to other one-parameter scale-space features an image descriptor that is defined over "two" scale parameters.
One scale parameter, referred to as "local scale" formula_129, is needed for determining the amount of pre-smoothing when computing the image gradient formula_130. Another scale parameter, referred to as "integration scale" formula_131, is needed for specifying the spatial extent of the window function formula_132 that determines the weights for the region in space over which the components of the outer product of the gradient by itself formula_15 are accumulated.
More precisely, suppose that formula_1 is a real-valued signal defined over formula_135. For any local scale formula_136, let a multi-scale representation formula_137 of this signal be given by formula_138 where formula_139 represents a pre-smoothing kernel. Furthermore, let formula_130 denote the gradient of the scale space representation.
Then, the "multi-scale structure tensor/second-moment matrix" is defined by
Conceptually, one may ask if it would be sufficient to use any self-similar families of smoothing functions formula_139 and formula_132. If one naively would apply, for example, a box filter, however, then non-desirable artifacts could easily occur. If one wants the multi-scale structure tensor to be well-behaved over both increasing local scales formula_129 and increasing integration scales formula_131, then it can be shown that both the smoothing function and the window function "have to" be Gaussian. The conditions that specify this uniqueness are similar to the scale-space axioms that are used for deriving the uniqueness of the Gaussian kernel for a regular Gaussian scale space of image intensities.
There are different ways of handling the two-parameter scale variations in this family of image descriptors. If we keep the local scale parameter formula_129 fixed and apply increasingly broadened versions of the window function by increasing the integration scale parameter formula_131 only, then we obtain a "true formal scale space representation of the directional data computed at the given local scale" formula_129. If we couple the local scale and integration scale by a "relative integration scale" formula_149, such that formula_150 then for any fixed value of formula_151, we obtain a reduced self-similar one-parameter variation, which is frequently used to simplify computational algorithms, for example in corner detection, interest point detection, texture analysis and image matching.
By varying the relative integration scale formula_149 in such a self-similar scale variation, we obtain another alternative way of parameterizing the multi-scale nature of directional data obtained by increasing the integration scale.
A conceptually similar construction can be performed for discrete signals, with the convolution integral replaced by a convolution sum and with the continuous Gaussian kernel formula_153 replaced by the discrete Gaussian kernel formula_154:
When quantizing the scale parameters formula_129 and formula_131 in an actual implementation, a finite geometric progression formula_158 is usually used, with "i" ranging from 0 to some maximum scale index "m". Thus, the discrete scale levels will bear certain similarities to image pyramid, although spatial subsampling may not necessarily be used in order to preserve more accurate data for subsequent processing stages.
Applications.
The eigenvalues of the structure tensor play a significant role in many image processing algorithms, for problems like corner detection, interest point detection, and feature tracking. The structure tensor also plays a central role in the Lucas-Kanade optical flow algorithm, and in its extensions to estimate affine shape adaptation; where the magnitude of formula_77 is an indicator of the reliability of the computed result. The tensor has been used for scale space analysis, estimation of local surface orientation from monocular or binocular cues, non-linear fingerprint enhancement, diffusion-based image processing, and several other image processing problems. The structure tensor can be also applied in geology to filter seismic data.
Processing spatio-temporal video data with the structure tensor.
The three-dimensional structure tensor has been used to analyze three-dimensional video data (viewed as a function of "x", "y", and time "t").
If one in this context aims at image descriptors that are "invariant" under Galilean transformations, to make it possible to compare image measurements that have been obtained under variations of a priori unknown image velocities formula_160
it is, however, from a computational viewpoint preferable to parameterize the components in the structure tensor/second-moment matrix formula_162 using the notion of "Galilean diagonalization"
where formula_164 denotes a Galilean transformation of spacetime and formula_165 a two-dimensional rotation over the spatial domain,
compared to the abovementioned use of eigenvalues of a 3-D structure tensor, which corresponds to an eigenvalue decomposition and a (non-physical) three-dimensional rotation of spacetime
To obtain true Galilean invariance, however, also the shape of the spatio-temporal window function needs to be adapted, corresponding to the transfer of affine shape adaptation from spatial to spatio-temporal image data.
In combination with local spatio-temporal histogram descriptors,
these concepts together allow for Galilean invariant recognition of spatio-temporal events.