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. The structure tensor is often used in image processing and computer vision..

The 2D structure tensor

Continuous version

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

$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 $I_{x}$ and $I_{y}$ are the partial derivatives of $I$ with respect to x and y; the integrals range over the plane $\mathbb {R} ^{2}$; and w is some fixed "window function", a distribution on two variables. Note that the matrix S_w is itself a function of p=(x,y).

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

$S(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 gradient $\nabla I=(I_{x},I_{y})$ of $I$ is viewed as a 1×2 (single-row) matrix, the matrix $S$ can be written as the matrix product $(\nabla I)'(\nabla I)$, where $(\nabla I)'$ denotes the 2×1 (single-column) transpose of the gradient. (Note however that the structure tensor $S_{w}(p)$ cannot be factored in this way.)

Discrete version

In image processing and other similar applications, the function $I$ is usually given as a discrete array of samples $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

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

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

$S[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}}$

Interpretation

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

Namely, if $\lambda _{1}>\lambda _{2}$, then $e_{1}$ (or $-e_{1}$) is the direction that is maximally aligned with the gradient within the window. In particular, if $\lambda _{1}>0,\lambda _{2}=0$ then the gradient is always a multiple of $e_{1}$ (positive, negative or zero); this is the case if and only if $I$ within the window varies along the direction $e_{1}$ but is constant along $e_{2}$.

If $\lambda _{1}=\lambda _{2}$, on the other hand, the gradient in $W$ has no predominant direction; which happens, for instance, when the image has rotational symmetry within that window. In particular, $\lambda _{1}=\lambda _{2}=0$ if and only if the function $I$ is constant ($\nabla I=(0,0)$) within $W$.

More generally, the value of $\lambda _{k}$, for k=1 or k=2, is the weighted average of the square of the directional derivative of $I$ along $e_{k}$ within $W$. The relative discrepancy between the two eigenvalues of $S_{w}$ is an indicator of the degree of anisotropy of the gradient in the window, namely how strongly is its biased towards a particular direction (and its opposite). This attribute can be quantified by the coherence, defined as

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

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

Note that the average of the gradient $\nabla I$ inside the window is not a good indicator of anisotropy. Aligned but oppositely oriented gradients would cancel out in this average, whereas in the structure tensor they are properly added together.

By increasing the window size and spreading out the weights, one can make the structure tensor more robust in the face of noise, at the cost of diminished spatial resolution., which reflects the abovementioned scale-space property of directional data as obtained from the multi-scale structure tensor .

The 3D structure tensor

Definition

The structure tensor can be defined also for a function $I$ of three variables p=(x,y,z) in an entirely analogous way. Namely, in the continuous version we have $S_{w}(p)=\int w(r)S(p-r)\,dr$, where

$S(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 $I_{x},I_{y},I_{z}$ are the three partial derivatives of $I$, and the integral ranges over $\mathbb {R} ^{3}$. In the discrete version,$S_{w}[p]=\sum _{r}w[r]S[p-r]$, where

$S[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 three-dimensional window $W$, usually $\{-m..+m\}\times \{-m..+m\}\times \{-m..+m\}$ for some m.

Interpretation

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

Ellipsoidal representation of the 3D structure tensor.

In particular, if the ellipsoid is stretched along one axis only, like a cigar (that is, if $\lambda _{1}$ is much larger than both $\lambda _{2}$ and $\lambda _{3}$), it means that the gradient in the window is predominantly aligned with the direction $e_{1}$, so that the isosurfaces of $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 $\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 $\lambda _{3}$ is much smaller than both $\lambda _{1}$ and $\lambda _{2}$), it means that the gradient directions are spread out but perendicular to $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 plate-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 $\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 $\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 $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 $I$ is constant (has zero gradient) within the window.

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

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

The corresponding structure tensor ellipsoid.

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 $\lambda _{2}$ is an indicator of the reliability of the computed result. The tensor has also 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.

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). 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 $v=(v_{x},v_{y})^{T}$

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

it is, however, from a computational viewpoint more preferable to parameterize the components in the structure tensor/second-moment matrix $S$ using the notion of Galilean diagonalization

$S'=R_{space}^{-T}\,G^{-T}\,S\,G^{-1}\,R_{space}^{-1}$

where $G$ denotes a Galilean transformation of space-time and $R_{space}$ a two-dimensional rotation over the spatial domain, compared to the abovementioned use of eigenvalues that correspond to an eigenvalue decomposition and a (non-physical) three-dimensional rotation of space-time

$S''=R_{space-time}^{-T}\,S\,R_{space-time}^{-1}$.

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.

See also

• Tensor
• Directional derivative
• Gaussian
• Corner detection
• Edge detection
• Lucas-Kanade method
• Affine shape adaptation

Resources

• Download MATLAB Source
• Structure Tensor Tutorial (Original)