Size function: Difference between revisions

Revision as of 19:16, 2 July 2017

Revision as of 00:29, 16 July 2017

Line 1:

{{Use dmy dates|date=October 2012}}

'''Size functions''' are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane <math>x<y\ </math> to the natural numbers, counting certain connected components of a [[topological space]]. They are used in [[pattern recognition]] and [[topology]].

==Formal definition==

In [[size theory]], the '''size function''' <math>\ell_{(M,\varphi)}:\Delta^+=\{(x,y)\in \mathbb{R}^2:x<y\}\to \mathbb{N}</math> associated with the [[size pair]] <math>(M,\varphi:M\to \mathbb{R})</math> is defined in the following way. For every <math>(x,y)\in \Delta^+</math>, <math>\ell_{(M,\varphi)}(x,y)</math> is equal to the number of connected components of the set

<math>\{p\in M:\varphi(p)\le y\}</math> that contain at least one point at which the [[measuring function]] (a [[continuous function]] from a [[topological space]] <math>M\ </math> to <math>\mathbb{R}^k\ </math>

<ref name="FroLa99">Patrizio Frosini and Claudia Landi, ''Size Theory as a Topological Tool for Computer Vision'', Pattern Recognition And Image Analysis, 9(4):596–603, 1999.</ref>

<ref name="FroMu99">Patrizio Frosini and Michele Mulazzani, ''Size homotopy groups for computation of natural size distances'', [[Bulletin of the Belgian Mathematical Society]], 6:455–464 1999.</ref>) <math>\varphi</math> takes a value smaller than or equal to <math>x\ </math>

.<ref name="dAFrLa06">Michele d'Amico, Patrizio Frosini and Claudia Landi, ''Using matching distance in Size Theory: a survey'', International Journal of Imaging Systems and Technology, 16(5):154–161, 2006.</ref>

The concept of size function can be easily extended to the case of a measuring function <math>\varphi:M\to \mathbb{R}^k</math>, where <math>\mathbb{R}^k</math> is endowed with the usual partial order

Line 19:

Size functions were introduced in

<ref name="Fro90">Patrizio Frosini, ''[http://journals.cambridge.org/download.php?file=%2FBAZ%2FBAZ42_03%2FS0004972700028574a.pdf&code=eff2726f156a5a8fdb323feb4fadd1e3 A distance for similarity classes of submanifolds of a Euclidean space]'', Bulletin of the Australian Mathematical Society, 42(3):407–416, 1990.</ref>

for the particular case of <math>M\ </math> equal to the topological space of all piecewise <math>C^1\ </math> closed paths in a <math>C^\infty\ </math> [[closed manifold]] embedded in a Euclidean space. Here the topology on <math>M\ </math> is induced by the

<math>C^0\ </math>-norm, while the [[measuring function]] <math>\varphi\ </math> takes each path <math>\gamma\in M</math> to its length.

In

<ref name="Fro91">Patrizio Frosini, ''Measuring shapes by size functions'', Proc. SPIE, Intelligent Robots and Computer Vision X: Algorithms and Techniques, Boston, MA, 1607:122–133, 1991.</ref>

the case of <math>M\ </math> equal to the topological space of all ordered <math>k\ </math>-tuples of points in a submanifold of a Euclidean space is considered.

Here the topology on <math>M\ </math> is induced by the metric <math>d((P_1,\ldots,P_k),(Q_1\ldots,Q_k))=\max_{1\le i\le k}\|P_i-Q_i\|</math>.

An extension of the concept of size function to [[algebraic topology]] was made in

Line 57:

<ref name="CeFeGi06">Andrea Cerri, Massimo Ferri, Daniela Giorgi, ''Retrieval of trademark images by means of size functions Graphical Models'' 68:451–471, 2006.</ref>

.<ref name="BiGiSp08">Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, Bianca Falcidieno, ''Size functions for comparing 3D models'' Pattern Recognition 41:2855–2873, 2008.</ref>

The main point is that size functions are invariant for every transformation preserving the [[measuring function]]. Hence, they can be adapted to many different applications, by simply changing the [[measuring function]] in order to get the wanted invariance. Moreover, size functions show properties of relative resistance to noise, depending on the fact that they distribute the information all over the half-plane <math>\Delta^+\ </math>.

==Main properties==

Assume that <math>M\ </math> is a compact locally connected Hausdorff space. The following statements hold:

¤ every size function <math>\ell_{(M,\varphi)}(x,y)</math> is a [[non-decreasing function]] in the variable <math>x\ </math> and a [[Nonincreasing function|non-increasing function]] in the variable <math>y\ </math>.

¤ every size function <math>\ell_{(M,\varphi)}(x,y)</math> is locally right-constant in both its variables.

¤ for every <math>x<y\ </math>, <math>\ell_{(M,\varphi)}(x,y)</math> is finite.

¤ for every <math>x<\min \varphi</math> and every <math>y>x\ </math>, <math>\ell_{(M,\varphi)}(x,y)=0</math>.

¤ for every <math>y\ge\max \varphi</math> and every <math>x<y\ </math>, <math>\ell_{(M,\varphi)}(x,y)</math> equals the number of connected components of <math>M\ </math> on which the minimum value of <math>\varphi</math> is smaller than or equal to <math>x\ </math>.

If we also assume that <math>M\ </math> is a smooth [[closed manifold]] and <math>\varphi</math> is a <math>C^1\ </math>-function, the following useful property holds:

¤ in order that <math>(x,y)\ </math> is a discontinuity point for <math>\ell_{(M,\varphi)}</math> it is necessary that either <math>x\ </math> or <math>y\ </math> or both are critical values for <math>\varphi</math>

.<ref name="Fro96">Patrizio Frosini, ''Connections between size functions and critical points'', Mathematical Methods In The Applied Sciences, 19:555–569, 1996.</ref>

Line 101:

Formally:

* ''cornerpoints'' are defined as those points <math>p=(x,y)\ </math>, with <math>x<y\ </math>, such that the number

<math>\mu (p){\stackrel{{\rm def}}{=}}\min _{\alpha >0 ,\beta>0} \ell _{({M},\varphi )}(x+\alpha ,y-

\beta)-\ell _{({ M},\varphi )} (x+\alpha ,y+\beta )-

Line 107:

,\varphi )} (x-\alpha ,y+\beta )</math>

is positive.

The number <math>\mu (p)\ </math> is said to be the ''multiplicity'' of <math>p\ </math>.

* ''cornerlines'' and are defined as those lines <math>r:x=k\ </math> such that

<math>\mu (r){\stackrel{\rm def}{=}}\min _{\alpha >0 ,k+\alpha <y}\ell _{({ M},\varphi

)}(k+\alpha ,y)-

\ell _{({ M},\varphi )}(k-\alpha ,y)>0.</math>

The number <math>\mu (r)\ </math> is sad to be the '' multiplicity'' of <math>r\ </math>.

* ''Representation Theorem'': For every <math>{\bar x}<{\bar y}</math>, it holds <math>\ell _{({M},\varphi )}({\bar x},{\bar y})=\sum _{p=(x,y)\atop x\le {\bar x}, y>\bar y }\mu\big(p\big)+\sum _{r:x=k\atop k\le {\bar x} }\mu\big(r\big)</math>