Generalized structure tensor: Difference between revisions

Revision as of 14:30, 20 July 2018

Latest revision as of 05:24, 29 May 2024

(18 intermediate revisions by 11 users not shown)

Line 1:

{{FeatureDetectionCompVisNavbox}}

In [[image analysis]], the '''generalized structure tensor (GST)''' is an extension of the Cartesian [[structure tensor]] to [[curvilinear coordinates]].<ref name="bigun04pami3">{{cite newsjournal |author1last1=Bigun |first1=J. |last2=Bigun |author2first2=T. Bigun|last3=Nilsson |author3first3=K. Nilsson|title=Recognition by symmetry derivatives and the generalized structure tensor |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=December 2004 |volume=26 |issue=12 |pages=1590–1605 |doi=10.1109/TPAMI.2004.126|pmid=15573820 |s2cid=602221 |url=http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-237 }}</ref> 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.

title = Recognition by symmetry derivatives and the generalized structure tensor|

journal = IEEE trans. Pattern Analysis and Machine Intelligence|

pages = 1590–1605|

volume = 26|

year = 2004}}</ref> 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.

It is a widely known method in applications of image and video processing including computer vision, such as biometric identification by fingerprints,<ref name=fronthaler08tip>{{cite news|journal

|doi=10.1109/TIP.2007.916155

title=Local features for enhancement and minutiae extraction in fingerprints|author1=H. Fronthaler |author2=K. Kollreider |author3=J. Bigun |

|pmid=18270124

journal=Image Processing, IEEE Transactions on|

|title=Local Features for Enhancement and Minutiae Extraction in Fingerprints

volume=17|

|journal=Image Processing, IEEE Transactions on| Image Processing

number=3|

|volume=17|

pages=354–363|

|issue=3

issn=1057-7149|

|pages=354–363|

|year=2008|

publisher=IEEE}}</ref> and studies of human tissue sections.<ref name=Schmitt>{{cite news|author1=O. Schmitt |author2=H. Birkholz |

|last1=Fronthaler

|first1=H.

|last2=Kollreider

|first2=K.

|last3=Bigun

|first3=J.

|bibcode=2008ITIP...17..354F

|url=http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-1358

|citeseerx=10.1.1.160.6312

|s2cid=7119251

publisher=IEEE}}</ref> and studies of human tissue sections.<ref name=Schmitt>{{cite newsjournal|author1=O. Schmitt |author2=H. Birkholz |

title=Improvement in cytoarchitectonic mapping by combining electrodynamic modeling with local orientation in high-resolution images of the cerebral cortex|

journal=Microsc. Res. Tech.|

volume= 74|issue=3 |

year=2010|

pages= 225–243|

doi=10.1109/TIP.2007.916155

}}</ref>

|pmid=18270124 |s2cid=7119251 |url=http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-1358

<ref name=Schmitt2>{{cite news|author1=O. Schmitt |author2=M. Pakura |author3=T. Aach |author4=L. Homke |author5=M. Bohme |author6=S. Bock |author7=S. Preusse |

}}</ref><ref name=Schmitt2>{{cite journal |author1=O. Schmitt |author2=M. Pakura |author3=T. Aach |author4=L. Homke |author5=M. Bohme |author6=S. Bock |author7=S. Preusse |title=Analysis of nerve fibers and their distribution in histologic sections of the human brain |journal=Microsc. Res. Tech. |volume=63 |issue=4 |year=2004 |pages=220–243 |doi=10.1002/jemt.20033 |pmid=14988920 |s2cid=28746142}}</ref>

journal=Microsc. Res. Tech.|

volume= 63|

year=2004|

pages= 220–243}}</ref>

==GST in 2D and locally orthogonal bases==

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

Let the term image represent a function

<math>f(\xi(x,y),\eta(x,y))</math>

where <math>x,y </math> are real variables and

<math>\xi,\eta </math>, and <math>f</math>, are real valued functions.

GST represents the direction along which the image <math>f</math> 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 <math>\xi,\eta</math>

: <math> \cos(\theta) \xi(x,y)+\sin(\theta) \eta(x,y)= \text{constant} </math>

which are curves in Cartesian coordinates as depicted by the equation above. The error is measured in the <math>L^2</math> sense and the minimality of the error refers thereby to [[L2 norm]].

2. The functions <math>\xi(x,y), \eta(x,y)</math> constitute a harmonic pair, i.e. they fulfill [[Cauchy–Riemann equations]],

Line 54 ⟶ 52:

Accordingly, such curvilinear coordinates <math>\xi,\eta</math> are locally orthogonal.

Then GST consists in

: <math> GST=(\lambda_{max}-\lambda_{min})

\int w(\xi,\eta)\left[

\begin{array}{c}

\frac{\partial f}{\partial \xi} \\

Line 62 ⟶ 61:

\end{array}

\right]

[\frac{\partial f}{\partial \xi}, \frac{\partial f}{\partial \eta}] d\xi d\eta +\lambda_{min} I </math>

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

where <math> 0\le \lambda_{min}\le \lambda_{max}</math> are errors of (infinitesimal) translation in the best direction (designated by the angle <math> \theta </math>) and the worst direction (designated by <math> \theta+\pi/2</math>). The function <math> \omega </math> is the window function defining the "outer scale" wherein the detection of <math>\theta</math> will be carried out, which can be omitted if it is already included in <math>f</math> or if <math>f</math> is the full image (rather than local). The matrix <math> I </math> 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 <math>\xi,\eta</math> pair the real and imaginary parts of an analytic function <math>g(z)</math>,

:<math>

\begin{array}{c}

Line 71:

\end{array}

</math>

where <math>z=x+iy</math> <ref>{{cite journal |last1=Bigün |first1=Josef |title=Pattern Recognition in Images by Symmetries and Coordinate Transformations |journal=Computer Vision and Image Understanding |date=December 1997 |volume=68 |issue=3 |pages=290–307 |doi=https://doi.org/10.1006/cviu.1997.0556}}</ref>.

Examples of analytic functions include <math> g(z)=\log z=\log(x+iy)</math>, as well as monomials <math> g(z)=z^n=(x+iy)^n</math>, <math> g(z)=z^{n/2}=(x+iy)^{n/2}</math>, where <math> n</math> is an arbitrary positive or negative integer. The monomials <math> g(z)=z^n</math> are also referred to as [[Harmonic functions]] in Computer Vision, and Image Processing.

where <math>z=x+iy</math> .<ref>{{cite journal |last1=BigünBigun |first1=Josef |title=Pattern Recognition in Images by Symmetries and Coordinate Transformations |journal=Computer Vision and Image Understanding |date=December 1997 |volume=68 |issue=3 |pages=290–307 |doi=https://doi.org/10.1006/cviu.1997.0556}}</ref> Examples of analytic functions include <math>g(z)=\log z=\log(x+iy)</math>, as well as monomials <math>g(z)=z^n=(x+iy)^n</math>, <math>g(z)=z^{n/2}=(x+iy)^{n/2}</math>, where <math>n</math> is an arbitrary positive or negative integer. The monomials <math>g(z)=z^n</math> are also referred to as [[harmonic functions]] in computer vision, and image processing.

Thereby, Cartesian [[Structure tensor]] is a special case of GST where <math> \xi=x</math>, and <math> \eta=y</math>, i.e. the harmonic function is simply <math> g(z)= z=(x+iy)</math>. Thus by choosing a harmonic function <math>g</math>, one can detect all curves that are linear combinations of its real and imaginary parts by convolutions on (rectangular) image grids only, even if <math>\xi,\eta</math> 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.

Thereby, Cartesian [[Structure tensor]] is a special case of GST where <math> \xi=x</math>, and <math> \eta=y</math>, i.e. the harmonic function is simply <math> g(z)= z=(x+iy)</math>. Thus by choosing a harmonic function <math>g</math>, one can detect all curves that are linear combinations of its real and imaginary parts by convolutions on (rectangular) image grids only, even if <math>\xi,\eta</math> 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[structure tensor]], there is also a complex version of the GST

:<math>

\begin{array}{c}

\kappa_{20} =(\lambda_1-\lambda_2)\exp(i2\theta)&=&w*(h*If)^2\\

\kappa_{11} =\lambda_1+\lambda_2&=&|w|*|h*If|^2\\

\end{array}

</math>

which is identical to its cousin with the difference that <math>w</math> is a complex filter. It should be recalled that, the ordinary [[structure tensor]] <math>w</math> 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 <math>\xi,\eta</math> defined by analytic functions <math>g</math>, it can be shown that, <ref name="bigun04pami3" /> the neighborhood defining function is complex valued,

:<math>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))

</math>,

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 <math>\theta</math> in images is possible by image processing for a pair <math>\xi</math>, <math>\eta</math>. 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 <math>2\theta</math> is then obtained along with the two errors, <math>\lambda_{max}</math> and <math>\lambda_{min}</math>. In analogy with the Cartesian [[Structurestructure tensor]], the estimated angle is in double angle representation, i.e. <math>2\theta</math> is delivered by computations, and can be used as a shape feature whereas <math>\lambda_{max}-\lambda_{min}</math> alone or in combination with <math>\lambda_{max}+\lambda_{min}</math> can be used as a quality (confidence, certainty) measure for the angle estimation.

<math>\lambda_{max}+\lambda_{min}</math> 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.<ref name=bigun04pami3 /> The spirals can be in [[Grayscale|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 mathemicalmathematical 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 <math>\xi=\log(\sqrt{x^2+y^2})</math> and <math>\eta=\tan^{-1}(x,y)</math>.

If an image <math>f</math> consists in iso-curves that can be explained by only $<math>\xi$ </math> i.e. its iso-curves consist in circles <math>f(\xi,\eta)=g(\xi)</math>, where <math>g </math> 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. <math>f(\xi,\eta)=g(\eta)</math> for some differentabledifferentiable 1D function <math>g</math> then, the image <math>f</math> is invariant to scaling (w.r.t. the origin).

In combination,

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

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

Analogously, the Cartesian [[structure tensor]] is a representation of a [[Translation (geometry)|translation]] too. Here the physical process consists in an ordinary translation of a certain amount along <math>x</math> combined with translation along <math>y</math>,

: <math> \cos(\theta) x+\sin(\theta) y= \text{constant} </math>

where the amount is specified by the parameter <math>\theta</math>. Evidently <math>\theta</math> here represents the direction of the line.

Generally, the estimated <math>\theta</math> represents the direction (in <math>\xi,\eta</math> coordinates) along which infinitisemalinfinitesimal 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]].

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==

Line 144 ⟶ 147:

{{reflist}}

== Resources ==

[[Category:Tensors]]