Structure tensor

For a function ${\displaystyle I}$ of two variables p = (x, y), the structure tensor is the 2×2 matrix

$${\displaystyle S_{w}(p)={\begin{bmatrix}\int w(r)(I_{x}(p-r))^{2}\,dr&\int w(r)I_{x}(p-r)I_{y}(p-r)\,dr\\[10pt]\int w(r)I_{x}(p-r)I_{y}(p-r)\,dr&\int w(r)(I_{y}(p-r))^{2}\,dr\end{bmatrix}}}$$

where ${\displaystyle I_{x}}$ and ${\displaystyle I_{y}}$ are the partial derivatives of ${\displaystyle I}$ with respect to x and y; the integrals range over the plane ${\displaystyle \mathbb {R} ^{2}}$; and w is some fixed "window function" (such as a Gaussian blur), a distribution on two variables. Note that the matrix ${\displaystyle S_{w}}$ is itself a function of p = (x, y).

The formula above can be written also as ${\textstyle S_{w}(p)=\int w(r)S_{0}(p-r)\,dr}$, where ${\displaystyle S_{0}}$ is the matrix-valued function defined by

$${\displaystyle S_{0}(p)={\begin{bmatrix}(I_{x}(p))^{2}&I_{x}(p)I_{y}(p)\\[10pt]I_{x}(p)I_{y}(p)&(I_{y}(p))^{2}\end{bmatrix}}}$$

If the gradient ${\displaystyle \nabla I=(I_{x},I_{y})^{\text{T}}}$ of ${\displaystyle I}$ is viewed as a 2×1 (single-column) matrix, where ${\displaystyle (\cdot )^{\text{T}}}$ denotes transpose operation, turning a row vector to a column vector, the matrix ${\displaystyle S_{0}}$ can be written as the matrix product ${\displaystyle (\nabla I)(\nabla I)^{\text{T}}}$ or tensor or outer product ${\displaystyle \nabla I\otimes \nabla I}$. Note however that the structure tensor ${\displaystyle S_{w}(p)}$ cannot be factored in this way in general except if ${\displaystyle w}$ is a Dirac delta function.

In image processing and other similar applications, the function ${\displaystyle I}$ is usually given as a discrete array of samples ${\displaystyle I[p]}$, where p is a pair of integer indices. The 2D structure tensor at a given pixel is usually taken to be the discrete sum

$${\displaystyle S_{w}[p]={\begin{bmatrix}\sum _{r}w[r](I_{x}[p-r])^{2}&\sum _{r}w[r]I_{x}[p-r]I_{y}[p-r]\\[10pt]\sum _{r}w[r]I_{x}[p-r]I_{y}[p-r]&\sum _{r}w[r](I_{y}[p-r])^{2}\end{bmatrix}}}$$

Here the summation index r ranges over a finite set of index pairs (the "window", typically ${\displaystyle \{-m\ldots +m\}\times \{-m\ldots +m\}}$ 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 ${\displaystyle I_{x}[p],I_{y}[p]}$ are the partial derivatives sampled at pixel p; which, for instance, may be estimated from by ${\displaystyle I}$ by finite difference formulas.

The formula of the structure tensor can be written also as ${\textstyle S_{w}[p]=\sum _{r}w[r]S_{0}[p-r]}$, where ${\displaystyle S_{0}}$ is the matrix-valued array such that

$${\displaystyle S_{0}[p]={\begin{bmatrix}(I_{x}[p])^{2}&I_{x}[p]I_{y}[p]\\[10pt]I_{x}[p]I_{y}[p]&(I_{y}[p])^{2}\end{bmatrix}}}$$

The importance of the 2D structure tensor ${\displaystyle S_{w}}$ stems from the fact eigenvalues ${\displaystyle \lambda _{1},\lambda _{2}}$ (which can be ordered so that ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq 0}$) and the corresponding eigenvectors ${\displaystyle e_{1},e_{2}}$ summarize the distribution of the gradient ${\displaystyle \nabla I=(I_{x},I_{y})}$ of ${\displaystyle I}$ within the window defined by ${\displaystyle w}$ centered at ${\displaystyle p}$.[1][2][3]

Namely, if ${\displaystyle \lambda _{1}>\lambda _{2}}$, then ${\displaystyle e_{1}}$ (or ${\displaystyle -e_{1}}$) is the direction that is maximally aligned with the gradient within the window.

In particular, if ${\displaystyle \lambda _{1}>0,\lambda _{2}=0}$ then the gradient is always a multiple of ${\displaystyle e_{1}}$ (positive, negative or zero); this is the case if and only if ${\displaystyle I}$ within the window varies along the direction ${\displaystyle e_{1}}$ but is constant along ${\displaystyle e_{2}}$. This condition of eigenvalues is also called linear symmetry condition because then the iso-curves of ${\displaystyle I}$ consist in parallel lines, i.e there exists a one dimensional function ${\displaystyle g}$ which can generate the two dimensional function ${\displaystyle I}$ as ${\displaystyle I(x,y)=g(d^{\text{T}}p)}$ for some constant vector ${\displaystyle d=(d_{x},d_{y})^{T}}$ and the coordinates ${\displaystyle p=(x,y)^{T}}$.

If ${\displaystyle \lambda _{1}=\lambda _{2}}$, 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 ${\displaystyle \lambda _{1}=\lambda _{2}=0}$ happens if and only if the function ${\displaystyle I}$ is constant (${\displaystyle \nabla I=(0,0)}$) within ${\displaystyle W}$.

More generally, the value of ${\displaystyle \lambda _{k}}$, for k=1 or k=2, is the ${\displaystyle w}$-weighted average, in the neighborhood of p, of the square of the directional derivative of ${\displaystyle I}$ along ${\displaystyle e_{k}}$. The relative discrepancy between the two eigenvalues of ${\displaystyle S_{w}}$ 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).[4][5] This attribute can be quantified by the coherence, defined as

$${\displaystyle c_{w}=\left({\frac {\lambda _{1}-\lambda _{2}}{\lambda _{1}+\lambda _{2}}}\right)^{2}}$$

if ${\displaystyle \lambda _{2}>0}$. 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 (${\displaystyle \lambda _{1}=\lambda _{2}=0}$). Some authors define it as 0 in that case.

Note that the average of the gradient ${\displaystyle \nabla I}$ 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.[6] This is a reason for why ${\displaystyle (\nabla I)(\nabla I)^{\text{T}}}$ is used in the averaging of the structure tensor to optimize the direction instead of ${\displaystyle \nabla I}$.

By expanding the effective radius of the window function ${\displaystyle w}$ (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.[5][7] 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.

The interpretation and implementation of the 2D structure tensor becomes particularly accessible using complex numbers.[2] The structure tensor consists in 3 real numbers

$${\displaystyle S_{w}(p)={\begin{bmatrix}\mu _{20}&\mu _{11}\\[10pt]\mu _{11}&\mu _{02}\end{bmatrix}}}$$

where ${\textstyle \mu _{20}=\int (w(r)(I_{x}(p-r))^{2}\,dr}$ , ${\textstyle \mu _{02}=\int (w(r)(I_{y}(p-r))^{2}\,dr}$ and ${\textstyle \mu _{11}=\int w(r)I_{x}(p-r)I_{y}(p-r)\,dr}$ in which integrals can be replaced by summations for discrete representation. Using Parseval's identity it is clear that the three real numbers are the second order moments of the power spectrum of ${\displaystyle I}$. The following second order complex moment of the power spectrum of ${\displaystyle I}$ can then be written as

$${\displaystyle \kappa _{20}=\mu _{20}-\mu _{02}+i2\mu _{11}=\int w(r)(I_{x}(p-r)+iI_{y}(p-r))^{2}\,dr=(\lambda _{1}-\lambda _{2})\exp(i2\phi )}$$

where ${\displaystyle i={\sqrt {-1}}}$ and ${\displaystyle \phi }$ is the direction angle of the most significant eigenvector of the structure tensor ${\displaystyle \phi =\angle {e_{1}}}$ whereas ${\displaystyle \lambda _{1}}$ and ${\displaystyle \lambda _{2}}$ are the most and the least significant eigenvalues. From, this it follows that ${\displaystyle \kappa _{20}}$ contains both a certainty ${\displaystyle |\kappa _{20}|=\lambda _{1}-\lambda _{2}}$ 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 ${\displaystyle I}$, 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 ${\displaystyle I}$, which happens to be always real because ${\displaystyle I}$ is real,

$${\displaystyle \kappa _{11}=\mu _{20}+\mu _{02}=\int w(r)|I_{x}(p-r)+iI_{y}(p-r)|^{2}\,dr=\lambda _{1}+\lambda _{2}}$$

can be obtained, with ${\displaystyle \lambda _{1}}$ and ${\displaystyle \lambda _{2}}$ 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

$${\displaystyle S_{w}(p)=\lambda _{1}e_{1}e_{1}^{\text{T}}+\lambda _{2}e_{2}e_{2}^{\text{T}}=(\lambda _{1}-\lambda _{2})e_{1}e_{1}^{\text{T}}+\lambda _{2}(e_{1}e_{1}^{\text{T}}+e_{2}e_{2}^{\text{T}})=(\lambda _{1}-\lambda _{2})e_{1}e_{1}^{\text{T}}+\lambda _{2}E}$$

where ${\displaystyle E}$ 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, ${\displaystyle (\lambda _{1}-\lambda _{2})e_{1}e_{1}^{\text{T}}}$, 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 ${\displaystyle E}$). To know how much directional information there is in ${\displaystyle I}$ is then the same as checking how large ${\displaystyle \lambda _{1}-\lambda _{2}}$ is compared to ${\displaystyle \lambda _{2}}$.

Evidently, ${\displaystyle \kappa _{20}}$ is the complex equivalent of the first term in the tensor decomposition, whereas

$${\displaystyle {\tfrac {1}{2}}(|\kappa _{20}|-\kappa _{11})=\lambda _{2}}$$

is the equivalent of the second term. Thus the two scalars, comprising three real numbers,

$${\displaystyle {\begin{aligned}\kappa _{20}&=&(\lambda _{1}-\lambda _{2})\exp(i2\phi )&=w*(h*I)^{2}\\\kappa _{11}&=&\lambda _{1}+\lambda _{2}&=w*|h*I|^{2}\\\end{aligned}}}$$

where ${\displaystyle h(x,y)=(x+iy)\exp(-(x^{2}+y^{2})/(2\sigma ^{2}))}$ is the (complex) gradient filter, and ${\displaystyle *}$ is convolution, constitute a complex representation of the 2D Structure Tensor. As discussed here and elsewhere ${\displaystyle w}$ defines the local image which is usually a Gaussian (with a certain variance defining the outer scale), and ${\displaystyle \sigma }$ is the (inner scale) parameter determining the effective frequency range in which the orientation ${\displaystyle 2\phi }$ 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 ${\displaystyle \kappa _{20}}$ and ${\displaystyle \kappa _{11}}$ 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.[8]

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 structure tensor can be defined also for a function ${\displaystyle I}$ of three variables p=(x,y,z) in an entirely analogous way. Namely, in the continuous version we have ${\textstyle S_{w}(p)=\int w(r)S_{0}(p-r)\,dr}$, where

$${\displaystyle S_{0}(p)={\begin{bmatrix}(I_{x}(p))^{2}&I_{x}(p)I_{y}(p)&I_{x}(p)I_{z}(p)\\[10pt]I_{x}(p)I_{y}(p)&(I_{y}(p))^{2}&I_{y}(p)I_{z}(p)\\[10pt]I_{x}(p)I_{z}(p)&I_{y}(p)I_{z}(p)&(I_{z}(p))^{2}\end{bmatrix}}}$$

where ${\displaystyle I_{x},I_{y},I_{z}}$ are the three partial derivatives of ${\displaystyle I}$, and the integral ranges over ${\displaystyle \mathbb {R} ^{3}}$.

In the discrete version,${\textstyle S_{w}[p]=\sum _{r}w[r]S_{0}[p-r]}$, where

$${\displaystyle S_{0}[p]={\begin{bmatrix}(I_{x}[p])^{2}&I_{x}[p]I_{y}[p]&I_{x}[p]I_{z}[p]\\[10pt]I_{x}[p]I_{y}[p]&(I_{y}[p])^{2}&I_{y}[p]I_{z}[p]\\[10pt]I_{x}[p]I_{z}[p]&I_{y}[p]I_{z}[p]&(I_{z}[p])^{2}\end{bmatrix}}}$$

and the sum ranges over a finite set of 3D indices, usually ${\displaystyle \{-m\ldots +m\}\times \{-m\ldots +m\}\times \{-m\ldots +m\}}$ for some m.

As in the two-dimensional case, the eigenvalues ${\displaystyle \lambda _{1},\lambda _{2},\lambda _{3}}$ of ${\displaystyle S_{w}[p]}$, and the corresponding eigenvectors ${\displaystyle {\hat {e}}_{1},{\hat {e}}_{2},{\hat {e}}_{3}}$, summarize the distribution of gradient directions within the neighborhood of p defined by the window ${\displaystyle w}$. This information can be visualized as an ellipsoid whose semi-axes are equal to the eigenvalues and directed along their corresponding eigenvectors.[9][10]

Ellipsoidal representation of the 3D structure tensor.

In particular, if the ellipsoid is stretched along one axis only, like a cigar (that is, if ${\displaystyle \lambda _{1}}$ is much larger than both ${\displaystyle \lambda _{2}}$ and ${\displaystyle \lambda _{3}}$), it means that the gradient in the window is predominantly aligned with the direction ${\displaystyle e_{1}}$, so that the isosurfaces of ${\displaystyle I}$ 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.

The structure tensor ellipsoid of a surface-like neighborhood ("surfel"), where ${\displaystyle \lambda _{1}>\!>\lambda _{2}\approx \lambda _{3}}$.

A 3D window straddling a smooth boundary surface between two uniform regions of a 3D image.

The corresponding structure tensor ellipsoid.

If the ellipsoid is flattened in one direction only, like a pancake (that is, if ${\displaystyle \lambda _{3}}$ is much smaller than both ${\displaystyle \lambda _{1}}$ and ${\displaystyle \lambda _{2}}$), it means that the gradient directions are spread out but perpendicular to ${\displaystyle e_{3}}$; 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.

The structure tensor of a line-like neighborhood ("curvel"), where ${\displaystyle \lambda _{1}\approx \lambda _{2}>\!>\lambda _{3}}$.

A 3D window straddling a line-like feature of a 3D image.

The corresponding structure tensor ellipsoid.

Finally, if the ellipsoid is roughly spherical (that is, if ${\displaystyle \lambda _{1}\approx \lambda _{2}\approx \lambda _{3}}$), it means that the gradient directions in the window are more or less evenly distributed, with no marked preference; so that the function ${\displaystyle I}$ 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 ${\displaystyle I}$ is constant (has zero gradient) within the window.

The structure tensor in an isotropic neighborhood, where ${\displaystyle \lambda _{1}\approx \lambda _{2}\approx \lambda _{3}}$.

A 3D window containing a spherical feature of a 3D image.

The corresponding structure tensor ellipsoid.

The three-dimensional structure tensor has been used to analyze three-dimensional video data (viewed as a function of x, y, and time t).[4] 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 ${\displaystyle v=(v_{x},v_{y})^{\text{T}}}$

$${\displaystyle {\begin{bmatrix}x'\\y'\\t'\end{bmatrix}}=G{\begin{bmatrix}x\\y\\t\end{bmatrix}}={\begin{bmatrix}x-v_{x}\,t\\y-v_{y}\,t\\t\end{bmatrix}},}$$

it is, however, from a computational viewpoint preferable to parameterize the components in the structure tensor/second-moment matrix ${\displaystyle S}$ using the notion of Galilean diagonalization[25]

$${\displaystyle S'=R_{\text{space}}^{-{\text{T}}}\,G^{-{\text{T}}}\,S\,G^{-1}\,R_{\text{space}}^{-1}={\begin{bmatrix}\nu _{1}&\,&\,\\\,&\nu _{2}&\,\\\,&\,&\nu _{3}\end{bmatrix}}}$$

where ${\displaystyle G}$ denotes a Galilean transformation of spacetime and ${\displaystyle R_{\text{space}}}$ 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

$${\displaystyle S''=R_{\text{spacetime}}^{-{\text{T}}}\,S\,R_{\text{spacetime}}^{-1}={\begin{bmatrix}\lambda _{1}&&\\&\lambda _{2}&\\&&\lambda _{3}\end{bmatrix}}.}$$

To obtain true Galilean invariance, however, also the shape of the spatio-temporal window function needs to be adapted,[25][26] corresponding to the transfer of affine shape adaptation[11] from spatial to spatio-temporal image data. In combination with local spatio-temporal histogram descriptors,[27] these concepts together allow for Galilean invariant recognition of spatio-temporal events.[28]