Generalized structure tensor

Last updated October 21, 2022

In image analysis, the generalized structure tensor (GST) is an extension of the Cartesian structure tensor to curvilinear coordinates.^[1] It is mainly used to detect and to represent the "direction" parameters of curves, just as the Cartesian structure tensor detects and represents the direction in Cartesian coordinates. Curve families generated by pairs of locally orthogonal functions have been the best studied.

GST in 2D and locally orthogonal bases

Let the term image represent a function $f(\xi (x,y),\eta (x,y))$ where $x,y$ are real variables and $\xi ,\eta$ , and $f$ , are real valued functions. GST represents the direction along which the image $f$ can undergo an infinitesimal translation with minimal (total least squares) error, along the "lines" fulfilling the following conditions:

1. The "lines" are ordinary lines in the curvilinear coordinate basis $\xi ,\eta$

\cos(\theta )\xi (x,y)+\sin(\theta )\eta (x,y)={\text{constant}}

which are curves in Cartesian coordinates as depicted by the equation above. The error is measured in the $L^{2}$ sense and the minimality of the error refers thereby to L2 norm.

2. The functions $\xi (x,y),\eta (x,y)$ constitute a harmonic pair, i.e. they fulfill Cauchy–Riemann equations,

{\begin{aligned}&{\frac {\partial \xi }{\partial x}}=-{\frac {\partial \eta }{\partial y}},\\[4pt]&{\frac {\partial \xi }{\partial y}}={\frac {\partial \eta }{\partial x}}.\end{aligned}}

Accordingly, such curvilinear coordinates $\xi ,\eta$ are locally orthogonal.

Then GST consists in

GST=(\lambda _{max}-\lambda _{min})\int w(\xi ,\eta )\left[{\begin{array}{c}{\frac {\partial f}{\partial \xi }}\\{\frac {\partial f}{\partial \eta }}\\\end{array}}\right][{\frac {\partial f}{\partial \xi }},{\frac {\partial f}{\partial \eta }}]d\xi d\eta +\lambda _{min}I

where $0\leq \lambda _{min}\leq \lambda _{max}$ are errors of (infinitesimal) translation in the best direction (designated by the angle $\theta$ ) and the worst direction (designated by $\theta +\pi /2$ ). The function $w(\xi ,\eta )$ is the window function defining the "outer scale" wherein the detection of $\theta$ will be carried out, which can be omitted if it is already included in $f$ or if $f$ is the full image (rather than local). The matrix $I$ is the identity matrix. Using the chain rule, it can be shown that the integration above can be implemented as convolutions in Cartesian coordinates applied to the ordinary structure tensor when $\xi ,\eta$ pair the real and imaginary parts of an analytic function $g(z)$ ,

{\begin{array}{c}\xi (x,y)=\Re g(z)\\\eta (x,y)=\Im g(z)\\\end{array}}

where $z=x+iy$ .^[5] Examples of analytic functions include $g(z)=\log z=\log(x+iy)$ , as well as monomials $g(z)=z^{n}=(x+iy)^{n}$ , $g(z)=z^{n/2}=(x+iy)^{n/2}$ , where $n$ is an arbitrary positive or negative integer. The monomials $g(z)=z^{n}$ are also referred to as harmonic functions in computer vision, and image processing.

Thereby, Cartesian Structure tensor is a special case of GST where $\xi =x$ , and $\eta =y$ , i.e. the harmonic function is simply $g(z)=z=(x+iy)$ . Thus by choosing a harmonic function $g$ , one can detect all curves that are linear combinations of its real and imaginary parts by convolutions on (rectangular) image grids only, even if $\xi ,\eta$ are non-Cartesian. Furthermore, the convolution computations can be done by using complex filters applied to the complex version of the structure tensor. Thus, GST implementations have frequently been done using complex version of the structure tensor, rather than using the (1,1) tensor.

Complex version of GST

As there is a complex version of the ordinary structure tensor, there is also a complex version of the GST

{\begin{array}{c}\kappa _{20}=(\lambda _{1}-\lambda _{2})\exp(i2\theta )&=&w*(h*f)^{2}\\\kappa _{11}=\lambda _{1}+\lambda _{2}&=&|w|*|h*f|^{2}\\\end{array}}

which is identical to its cousin with the difference that $w$ is a complex filter. It should be recalled that, the ordinary structure tensor $w$ is a real filter, usually defined by a sampled and scaled Gaussian to delineate the neighborhood, also known as the outer scale. This simplicity is a reason for why GST implementations have predominantly used the complex version above. For curve families $\xi ,\eta$ defined by analytic functions $g$ , it can be shown that, ^[1] the neighborhood defining function is complex valued,

w=(x\pm iy)^{n}\exp(-(x^{2}+y^{2})/(2\sigma ^{2}))\propto (D_{x}\pm iD_{y})^{n}\exp(-(x^{2}+y^{2})/(2\sigma ^{2}))

,

a so called symmetry derivative of a Gaussian. Thus, the orientation wise variation of the pattern to be looked for is directly incorporated into the neighborhood defining function, and the detection occurs in the space of the (ordinary) structure tensor.

Basic concept for its use in image processing and computer vision

Efficient detection of $\theta$ in images is possible by image processing for a pair $\xi$ , $\eta$ . Complex convolutions (or the corresponding matrix operations) and point-wise non-linear mappings are the basic computational elements of GST implementations. A total least square error estimation of $2\theta$ is then obtained along with the two errors, $\lambda _{max}$ and $\lambda _{min}$ . In analogy with the Cartesian structure tensor, the estimated angle is in double angle representation, i.e. $2\theta$ is delivered by computations, and can be used as a shape feature whereas $\lambda _{max}-\lambda _{min}$ alone or in combination with $\lambda _{max}+\lambda _{min}$ can be used as a quality (confidence, certainty) measure for the angle estimation.

Logarithmic spirals, including circles, can for instance be detected by (complex) convolutions and non-linear mappings.^[1] The spirals can be in gray (valued) images or in a binary image, i.e. locations of edge elements of the concerned patterns, such as contours of circles or spirals, must not be known or marked otherwise.

Generalized structure tensor can be used as an alternative to Hough transform in image processing and computer vision to detect patterns whose local orientations can be modelled, for example junction points. The main differences comprise:

Negative, as well as complex voting are allowed;
With one template multiple patterns belonging to the same family can be detected;
Image binarization is not required.

Physical and mathematical interpretation

The curvilinear coordinates of GST can explain physical processes applied to images. A well known pair of processes consist in rotation, and zooming. These are related to the coordinate transformation $\xi =\log({\sqrt {x^{2}+y^{2}}})$ and $\eta =\tan ^{-1}(x,y)$ .

If an image $f$ consists in iso-curves that can be explained by only $\xi$ i.e. its iso-curves consist in circles $f(\xi ,\eta )=g(\xi )$ , where $g$ is any real valued differentiable function defined on 1D, the image is invariant to rotations (around the origin).

Zooming (comprising unzooming) operation is modeled similarly. If the image has iso-curves that look like a "star" or bicycle spokes, i.e. $f(\xi ,\eta )=g(\eta )$ for some differentiable 1D function $g$ then, the image $f$ is invariant to scaling (w.r.t. the origin).

In combination,

f(\xi ,\eta )=g(\cos(\theta )\log({\sqrt {x^{2}+y^{2}}})+\sin(\theta )\tan ^{-1}(x,y))

is invariant to a certain amount of rotation combined with scaling, where the amount is precised by the parameter $\theta$ .

Analogously, the Cartesian structure tensor is a representation of a translation too. Here the physical process consists in an ordinary translation of a certain amount along $x$ combined with translation along $y$ ,

\cos(\theta )x+\sin(\theta )y={\text{constant}}

where the amount is specified by the parameter $\theta$ . Evidently $\theta$ here represents the direction of the line.

Generally, the estimated $\theta$ represents the direction (in $\xi ,\eta$ coordinates) along which infinitesimal translations leave the image invariant, in practice least variant. With every curvilinear coordinate basis pair, there is thus a pair of infinitesimal translators, a linear combination of which is a Differential operator. The latter are related to Lie algebra.

Miscellaneous

"Image" in the context of the GST can mean both an ordinary image and an image neighborhood thereof (local image), depending on context. For example, a photograph is an image as is any neighborhood of it.

Related Research Articles

In mathematics, a 3-sphere is a higher-dimensional analogue of a sphere. It may be embedded in 4-dimensional Euclidean space as the set of points equidistant from a fixed central point. Analogous to how the boundary of a ball in three dimensions is an ordinary sphere, the boundary of a ball in four dimensions is a 3-sphere. A 3-sphere is an example of a 3-manifold and an n-sphere.

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols $,, or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δ f (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p) .$

In physics and mathematics, the Lorentz group is the group of all Lorentz transformations of Minkowski spacetime, the classical and quantum setting for all (non-gravitational) physical phenomena. The Lorentz group is named for the Dutch physicist Hendrik Lorentz.

In mathematics, the directional derivative of a multivariable differentiable (scalar) function along a given vector v at a given point x intuitively represents the instantaneous rate of change of the function, moving through x with a velocity specified by v.

In the mathematical field of differential topology, the Hopf fibration describes a 3-sphere in terms of circles and an ordinary sphere. Discovered by Heinz Hopf in 1931, it is an influential early example of a fiber bundle. Technically, Hopf found a many-to-one continuous function from the $3$ -sphere onto the $2$ -sphere such that each distinct point of the $2$ -sphere is mapped from a distinct great circle of the $3$ -sphere. Thus the $3$ -sphere is composed of fibers, where each fiber is a circle — one for each point of the $2$ -sphere.

In physics and mathematics, supermanifolds are generalizations of the manifold concept based on ideas coming from supersymmetry. Several definitions are in use, some of which are described below.

In differential geometry, a spray is a vector field H on the tangent bundle TM that encodes a quasilinear second order system of ordinary differential equations on the base manifold M. Usually a spray is required to be homogeneous in the sense that its integral curves t→Φ_H^t(ξ)∈TM obey the rule Φ_H^t(λξ)=Φ_H^λt(ξ) in positive reparameterizations. If this requirement is dropped, H is called a semispray.

In special functions, a topic in mathematics, spin-weighted spherical harmonics are generalizations of the standard spherical harmonics and—like the usual spherical harmonics—are functions on the sphere. Unlike ordinary spherical harmonics, the spin-weighted harmonics are $U(1)$ gauge fields rather than scalar fields: mathematically, they take values in a complex line bundle. The spin-weighted harmonics are organized by degree $l$ , just like ordinary spherical harmonics, but have an additional spin weight $s$ that reflects the additional $U(1)$ symmetry. A special basis of harmonics can be derived from the Laplace spherical harmonics $Y lm$ , and are typically denoted by $s Y lm$ , where $l$ and $m$ are the usual parameters familiar from the standard Laplace spherical harmonics. In this special basis, the spin-weighted spherical harmonics appear as actual functions, because the choice of a polar axis fixes the $U(1)$ gauge ambiguity. The spin-weighted spherical harmonics can be obtained from the standard spherical harmonics by application of spin raising and lowering operators. In particular, the spin-weighted spherical harmonics of spin weight $s = 0$ are simply the standard spherical harmonics:

In a field of mathematics known as differential geometry, the Courant bracket is a generalization of the Lie bracket from an operation on the tangent bundle to an operation on the direct sum of the tangent bundle and the vector bundle of p-forms.

In mathematics, the spectral theory of ordinary differential equations is the part of spectral theory concerned with the determination of the spectrum and eigenfunction expansion associated with a linear ordinary differential equation. In his dissertation Hermann Weyl generalized the classical Sturm–Liouville theory on a finite closed interval to second order differential operators with singularities at the endpoints of the interval, possibly semi-infinite or infinite. Unlike the classical case, the spectrum may no longer consist of just a countable set of eigenvalues, but may also contain a continuous part. In this case the eigenfunction expansion involves an integral over the continuous part with respect to a spectral measure, given by the Titchmarsh–Kodaira formula. The theory was put in its final simplified form for singular differential equations of even degree by Kodaira and others, using von Neumann's spectral theorem. It has had important applications in quantum mechanics, operator theory and harmonic analysis on semisimple Lie groups.

The derivatives of scalars, vectors, and second-order tensors with respect to second-order tensors are of considerable use in continuum mechanics. These derivatives are used in the theories of nonlinear elasticity and plasticity, particularly in the design of algorithms for numerical simulations.

In mathematical physics, the Berezin integral, named after Felix Berezin,, is a way to define integration for functions of Grassmann variables. It is not an integral in the Lebesgue sense; the word "integral" is used because the Berezin integral has properties analogous to the Lebesgue integral and because it extends the path integral in physics, where it is used as a sum over histories for fermions.

In fluid dynamics, a cnoidal wave is a nonlinear and exact periodic wave solution of the Korteweg–de Vries equation. These solutions are in terms of the Jacobi elliptic function cn, which is why they are coined cnoidal waves. They are used to describe surface gravity waves of fairly long wavelength, as compared to the water depth.

In mathematics, log-polar coordinates is a coordinate system in two dimensions, where a point is identified by two numbers, one for the logarithm of the distance to a certain point, and one for an angle. Log-polar coordinates are closely connected to polar coordinates, which are usually used to describe domains in the plane with some sort of rotational symmetry. In areas like harmonic and complex analysis, the log-polar coordinates are more canonical than polar coordinates.

In optics, the Fraunhofer diffraction equation is used to model the diffraction of waves when the diffraction pattern is viewed at a long distance from the diffracting object, and also when it is viewed at the focal plane of an imaging lens.

In probability theory, an interacting particle system (IPS) is a stochastic process $on some configuration space given by a site space, a countable-infinite graph and a local state space, a compact metric space . More precisely IPS are continuous-time Markov jump processes describing the collective behavior of stochastically interacting components. IPS are the continuous-time analogue of stochastic cellular automata.$

Symmetries in quantum mechanics describe features of spacetime and particles which are unchanged under some transformation, in the context of quantum mechanics, relativistic quantum mechanics and quantum field theory, and with applications in the mathematical formulation of the standard model and condensed matter physics. In general, symmetry in physics, invariance, and conservation laws, are fundamentally important constraints for formulating physical theories and models. In practice, they are powerful methods for solving problems and predicting what can happen. While conservation laws do not always give the answer to the problem directly, they form the correct constraints and the first steps to solving a multitude of problems.

In fluid dynamics, a trochoidal wave or Gerstner wave is an exact solution of the Euler equations for periodic surface gravity waves. It describes a progressive wave of permanent form on the surface of an incompressible fluid of infinite depth. The free surface of this wave solution is an inverted (upside-down) trochoid – with sharper crests and flat troughs. This wave solution was discovered by Gerstner in 1802, and rediscovered independently by Rankine in 1863.

In combustion, a Burke–Schumann flame is a type of diffusion flame, established at the mouth of the two concentric ducts, by issuing fuel and oxidizer from the two region respectively. It is named after S.P. Burke and T.E.W. Schumann, who were able to predict the flame height and flame shape using their simple analysis of infinitely fast chemistry in 1928 at the First symposium on combustion.

Moffatt eddies are sequences of eddies that develop in corners bounded by plane walls due to an arbitrary disturbance acting at asymptotically large distances from the corner. Although the source of motion is the arbitrary disturbance at large distances, the eddies develop quite independently and thus solution of these eddies emerges from an eigenvalue problem, a self-similar solution of the second kind.

References

1 2 3 Bigun, J.; Bigun, T.; Nilsson, K. (December 2004). "Recognition by symmetry derivatives and the generalized structure tensor". IEEE Transactions on Pattern Analysis and Machine Intelligence. 26 (12): 1590–1605. doi:10.1109/TPAMI.2004.126. PMID 15573820.
↑ Fronthaler, H.; Kollreider, K.; Bigun, J. (2008). "Local Features for Enhancement and Minutiae Extraction in Fingerprints". IEEE Transactions on Image Processing. 17 (3): 354–363. Bibcode:2008ITIP...17..354F. CiteSeerX 10.1.1.160.6312 . doi:10.1109/TIP.2007.916155. PMID 18270124.
↑ O. Schmitt; H. Birkholz (2010). "Improvement in cytoarchitectonic mapping by combining electrodynamic modeling with local orientation in high-resolution images of the cerebral cortex". Microsc. Res. Tech. 74 (3): 225–243. doi:10.1109/TIP.2007.916155. PMID 18270124.
↑ O. Schmitt; M. Pakura; T. Aach; L. Homke; M. Bohme; S. Bock; S. Preusse (2004). "Analysis of nerve fibers and their distribution in histologic sections of the human brain". Microsc. Res. Tech. 63 (4): 220–243. doi:10.1002/jemt.20033. PMID 14988920.
↑ Bigun, Josef (December 1997). "Pattern Recognition in Images by Symmetries and Coordinate Transformations". Computer Vision and Image Understanding. 68 (3): 290–307. doi:10.1006/cviu.1997.0556.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[bigun04pami3-1] 1 2 3 Bigun, J.; Bigun, T.; Nilsson, K. (December 2004). "Recognition by symmetry derivatives and the generalized structure tensor". IEEE Transactions on Pattern Analysis and Machine Intelligence. 26 (12): 1590–1605. doi:10.1109/TPAMI.2004.126. PMID 15573820.

[fronthaler08tip-2] Fronthaler, H.; Kollreider, K.; Bigun, J. (2008). "Local Features for Enhancement and Minutiae Extraction in Fingerprints". IEEE Transactions on Image Processing. 17 (3): 354–363. Bibcode:2008ITIP...17..354F. CiteSeerX 10.1.1.160.6312 . doi:10.1109/TIP.2007.916155. PMID 18270124.

[Schmitt-3] O. Schmitt; H. Birkholz (2010). "Improvement in cytoarchitectonic mapping by combining electrodynamic modeling with local orientation in high-resolution images of the cerebral cortex". Microsc. Res. Tech. 74 (3): 225–243. doi:10.1109/TIP.2007.916155. PMID 18270124.

[Schmitt2-4] O. Schmitt; M. Pakura; T. Aach; L. Homke; M. Bohme; S. Bock; S. Preusse (2004). "Analysis of nerve fibers and their distribution in histologic sections of the human brain". Microsc. Res. Tech. 63 (4): 220–243. doi:10.1002/jemt.20033. PMID 14988920.

[5] Bigun, Josef (December 1997). "Pattern Recognition in Images by Symmetries and Coordinate Transformations". Computer Vision and Image Understanding. 68 (3): 290–307. doi:10.1006/cviu.1997.0556.

[1]

[2]

[3]

[4]

[5]