Structure tensor

Structure tensors (or second-moment matrices) are matrix representations of partial derivatives. In the field of image processing and computer vision, they are typically used to represent gradients, edges or similar information. Structure tensors also provide a more powerful description of local patterns when compared with the directional derivative through its coherence measure. They have several other advantages that are detailed in the structure tensor section of this tutorial. This article is written largely from the point of view of image processing applications; however, it should also be useful to those from a more general math background who want to learn more about this representation.

Background

Gradient

Gradient information serves several purposes. It can relatethe structure of objects in an image, identify features of interestfor recognition/classification directly or provide the basis of furtherprocessing for various computer vision tasks. For example, "edges," notedby regions of high gradient magnitude, are central to the task of identifying defects in circuitry. A sample "edge-detected" image created usingthe 'Image Processing Toolbox' for MATLAB is shown where locations marked by white are those points that are indicative of highgradient magnitude, which can also be described as regions of highpixel contrast.

Directional derivative

When representing gradient information derived from an image, there are several options from which to choose. One such choice is the
directional derivative that provides a vector representation. Its magnitude reflects the maximum change in pixel values while the phase is directed along the orientation corresponding to the maximum change. These two components are calculated as per Equations (1) and (2) respectively:

where $I\_x$ denotes the partial derivative of image $I$ along the $x$-axis. An example is shown against a horizontal step-edge image with the directionalderivative overlaid with a red arrow. The direction of the gradient in this case is based purely on the orderingof the pixel values. i.e. it points from black to white. If these colorswere reversed, the gradient magnitude would remain the same; however, thedirection would then be reversed such that it again pointed FROM the blackTO the white region.In applications where the gradient is used to denote contours within the scene,such as object outlines, the polarity is of little use. Nevertheless, thisorientation reveals the "normal" to the contour in question. "Orientation,"in this context, implies PI-periodic behavior, as in the term "horizontalorientation." i.e. orientation ranges between $[0,pi)$. To reflect thisperiodicity, the directional derivative, when applied to the extractionof gradient-based structures, should also have an arrow pointed in theopposite direction.

Although the directional derivative is relatively computationally inexpensive, it does possess a weakness. This is best illustrated with an example.Given an isotropic structure, where there is no preferred direction ofgradient, the directional derivative formula results in a zero magnitude.An example of such an isotropic structure is a black circle on a whitebackground. There is clearly gradient information; however, since thereis no preferred phase, it zeros itself out.

There are several ways to calculate the partial derivatives of the image.For example, simple differencing between neighboring pixels one option, although the gradient will only be representative of a $2x1$ region of interest. The 'Difference of Gaussians' (DoG) is a common technique that convolves a specialized mask to calculate the partial derivative value overa larger region of interest.

The same output is reached if the original input is a uniformly colored region. Again, the directional derivative magnitude is zero as there is no gradient information with which to calculate. What is needed is a representation capable of discerning between thesetwo examples that properly reflects the presence of gradient informationin the first case, but none in the second.

tructure tensors

Overview

A different method of representing gradient information is by using the "structure tensor [cite conference|author=J. Bigun and G. Granlund|title=Optimal Orientation Detection of Linear Symmetry|location=Piscataway|booktitle=First int. Conf. on Computer Vision, ICCV, (London)
publisher=IEEE Computer Society Press, Piscataway, (Tech. Report LiTH-ISY-I-0828, Computer Vision Laboratory, Linkoping University, Sweden 1986. Thesis Report, Linkoping studies in science and technology No. 85, 1986)|pages=433-438|year=1987. ] [cite conference|author=H. Knutsson|title={Representing local structure using tensors|location=Oulu|booktitle=Proceedings 6th Scandinavian Conf.on Image Analysis
publisher=Oulu University|pages=244-251|year=1989] ." It also makes use of the $I\_x$ and $I\_y$ values, however,in a matrix form. The term tensor refers to a representation of an arrayof data. A significant difference between a tensor and a matrix, which is also an array, is that a tensor represents a physical quantity the measurement of which is no more influenced by the coordinates with which one observes it than one can account for it. Tensors can be represented by matrices whereas not all matrices are tensors. The "rank" of a tensor denotes the number of indices needed to describe it. For example, a scalar value $x$ is a single value, hence requires no indices. This means that a scalar is a tensor of rank zero. A vector $vec\; v$, often represented as $v\_i\; =\; \{v\_1,v\_2,..v\_n\}$ uses a single index, $i$.This implies that a vector is a tensor of rank one. A two-dimensional matrix $M\_\{ij\}$ is a tensor of rank two and so and so forth.

2D structure tensor

The structure tensor matrix (also referred to as the "second-moment matrix") is formed as:

: Eigen-decomposition is then applied to the structure tensor matrix $S$ toform the eigenvalues and eigenvectors $(lambda\_1,\; lambda\_2)$ and $(vec\; e\_1,\; vec\; e\_2)$ respectively. These new gradient features allow a more precise description of the local gradient characteristics. For example, $vec\; e\_1$, is a unit vector directed normal to the gradient edge, while the $vec\; e\_2$ vector is tangent. The eigenvalues indicate the underlying certainty of the gradient structure along their associated eigenvector directions. As noted by several researchers, the "coherence" is obtained as a function of the eigen-values. [cite book|author=B. Jahne|title=Spatio-Temporal Image Processing: Theory and Scientific Applications|location=Berlin
publisher=Springer-Verlag|volume=751|year=1993] cite book|author=G. Medioni, M. Lee and C. Tang|title=A Computational Framework for Feature Extractionand Segmentation|publisher=Elsevier Science|month=March|year=2000] [cite journal|author=D. Tschumperle and Deriche|title=Diffusion PDE's on Vector-Valued Images|booktitle=IEEE Signal Processing Magazine|pages=16–25|month=September|year=2002] This value is capable of distinguishing between the isotropic and uniformcases. The coherence is calculated as per the following equation:

: If a different method is used to obtain the partial derivative information, for example using Horn's approach where the average, absolute pixel difference is used, the coherence for the isotropic region is one while the uniform case is zero: opposite of the values obtained above. What is key is that no matter the partial derivative method used, the coherence, a feature of the structure tensor, is able to distinguish between the two cases.

Many corner detection and salient point location algorithms [cite journal
author=W. Forstner|title=A Feature Based Correspondence Algorithm for Image Processing
booktitle=International Archives of Photogrammetry and Remote Sensing|volume=26|pages=150–166|year=1986] [cite conference|author=C. Harris and M. Stephens|title=A Combined Corner and Edge Detector
booktitle=Proc. of the 4th ALVEY Vision Conference|pages=147–151|year=1988] [cite journal|author=K. Rohr|title=On 3D Differential Operators for Detecting Point Landmarks
booktitle=Image and Vision Computing|volume=15|issue=3|pages=219–233|year=1997] [cite conference|author=B. Triggs|title=Detecting Keypoints with Stable Position, Orientation, and Scale under Illumination Changes
booktitle=Proc. European Conference on Computer Vision|volume=4|pages=100–113|year=2004] make use of the eigenvalues that are derived from the structure tensorto quantify the certainty in the measurements [cite conference|author=C. Kenney, M. Zuliani and B. Manjunath, |title=An Axiomatic Approach to Corner Detection|booktitle=Proc. IEEE Computer Vision and Pattern Recognition|pages=191–197|year=2005] There are other advantages to using the structure tensor representation aswell. For example, local shifting of edge locations in minimized when applying a Gaussian smoothing operator element-by-element to the structuretensor.cite conference|author=M. Nicolescu and G. Medioni
title=Motion Segmentation with Accurate Boundaries — A Tensor Voting Approach|booktitle=Proc. IEEE Computer Vision and Pattern Recognition|volume=1|pages=pp.382–389|year=2003] Furthermore, the cancellations ofopposing gradient polarity directions are prevented when structure tensorsare summed. [cite journal|author=T. Brox, J. Weickert, B. Burgeth and P. Mrazek|title=Nonlinear Structure Tensors|booktitle=Universitat des Saarlandes, Tech. Report|issue=113|pages=1–32|year=2004]

For scale-space properties and other theoretical properties of the structure tensor (or second-moment matrix) when using a Gaussian window function for integration, please refer to. [ [http://www.nada.kth.se/~tony/book.html T. Lindeberg: Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, Dordrecht, Netherlands, 1994.] ] [ [http://www.nada.kth.se/cvap/abstracts/cvap117.html J. Garding and T. Lindeberg: "Direct computation of shape cues using scale-adapted spatial derivative operators", International Journal of Computer Vision, vol 17(2), pp. 163--191, 1996.] ] For applications of the structure tensor to motion estimation and to the estimation of affine image deformations, please see the articles on the Lukas-Kanade method and affine shape adaptation. For the application of the structure tensor to non-linear fingerprint enhancement, please see. [ [http://www.nada.kth.se/cvap/abstracts/cvap226.html A. Almansa and T. Lindeberg, ``Enhancement of fingerprint images using shape-adaptated scale-space operators", IEEE Transactions on Image Processing, volume 9, number 12, pp 2027-2042, 2000] ]

3D structure tensors

Overview

This form of gradient representation serves especially well in inferring structure from sparse and noisy data. The structure tensor is also applicable to higher dimensional data. For example, given three-dimensional data, such as that from a spatio-temporal volume $(x,y,time)$ or medical imaging input $(x,y,z)$, the structure tensor is represented as follows:

:

The eigen-decomposition of the tensor of rank two results in $(lambda\_1,\; lambda\_2,\; lambda\_3)$ and $(vec\; e\_1,\; vec\; e\_2,\; vec\; e\_3)$ for the eigenvalues and eigenvectors respectively. The interpretation of these components can be visualized as 3D ellipses where the radii are equal to the eigenvalues in descending order and directed along their corresponding eigenvectors.

3d structure types

The differences between the eigenvalues indicate underlying structure as well. For example, if the value of $(lambda\_1\; -\; lambda\_2)>>0$, this depicts a "surfel" surface element, where $vec\; e\_1$ is the normal to the surface.

3D results

Applied against actual data

Tensor addition

Another desirable property of the structure tensor form is that the tensoraddition equates itself to the adding of the elliptical forms. For example,if the structure tensors for the sphere case and step-edge case are added,the resulting structure tensor is an elongated ellipsed along the directionof the step-edge case.

Applications

Although structure tensors are applicable to many ND domains, it is in the imageprocessing / computer vision domains that is of considerable interest. Usinggradient-based structure tensors, local patterns of contours and surfaces may beinferred through a diffusion process. [cite conference|author=S. Arseneau and J. Cooperstock|title=An Asymmetrical Diffusion Framework for JunctionAnalysis|booktitle=British Machine Vision Conference|volume=2|pages=689–698|month=September|year=2006] Diffusion aids to enforce local structural estimates that serve such applications as defect detection in lumber,occlusion detection in image sequences and aid in biometric identification of fingerprints. [cite conference|author=S. Arseneau, and J. Cooperstock|title=An Improved Representation of Junctions through Asymmetric Tensor Diffusion|booktitle=International Symposium on Visual Computing|month=November|year=2006]

References

ee also

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

Resources

* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12362&objectType=FILE Download MATLAB Source]
* [http://www.cs.cmu.edu/~sarsen/structureTensorTutorial/ Structure Tensor Tutorial (Original)]