HOME

TheInfoList



Click Here for Items Related To - Size Function
OR:
Size Function on:   [Wikipedia]   [Google]   [Amazon]

Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane x 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 In mathematics, size theory studies the properties of topological spaces endowed with \mathbb^k-valued functions, with respect to the change of these functions. More formally, the subject of size theory is the study of the natural pseudodistance ...
, the size function \ell_:\Delta^+=\\to \mathbb associated with the size pair (M,\varphi:M\to \mathbb) is defined in the following way. For every (x,y)\in \Delta^+, \ell_(x,y) is equal to the number of connected components of the set \ that contain at least one point at which the measuring function (a
continuous function In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...
from a topological space M to \mathbb^k Patrizio Frosini and Claudia Landi, ''Size Theory as a Topological Tool for Computer Vision'', Pattern Recognition And Image Analysis, 9(4):596–603, 1999. Patrizio Frosini and Michele Mulazzani, ''Size homotopy groups for computation of natural size distances'',
Bulletin of the Belgian Mathematical Society ''Simon Stevin'' was a Dutch language academic journal in pure and applied mathematics, or ''Wiskunde'' as the field is known in Dutch. Published in Ghent, edited by Guy Hirsch, it ran for 67 volumes until 1993.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. The concept of size function can be easily extended to the case of a measuring function \varphi:M\to \mathbb^k, where \mathbb^k is endowed with the usual partial order .Silvia Biasotti, Andrea Cerri, Patrizio Frosini, Claudia Landi, ''Multidimensional size functions for shape comparison'', Journal of Mathematical Imaging and Vision 32:161–179, 2008. A survey about size functions (and
size theory In mathematics, size theory studies the properties of topological spaces endowed with \mathbb^k-valued functions, with respect to the change of these functions. More formally, the subject of size theory is the study of the natural pseudodistance ...
) can be found in.Silvia Biasotti, Leila De Floriani, Bianca Falcidieno, Patrizio Frosini, Daniela Giorgi, Claudia Landi, Laura Papaleo, Michela Spagnuolo, ''Describing shapes by geometrical-topological properties of real functions'' ACM Computing Surveys, vol. 40 (2008), n. 4, 12:1–12:87.


History and applications

Size functions were introduced in Patrizio Frosini,
A distance for similarity classes of submanifolds of a Euclidean space
', Bulletin of the Australian Mathematical Society, 42(3):407–416, 1990. for the particular case of M equal to the topological space of all piecewise C^1 closed paths in a C^\infty
closed manifold In mathematics, a closed manifold is a manifold without boundary that is compact. In comparison, an open manifold is a manifold without boundary that has only ''non-compact'' components. Examples The only connected one-dimensional example ...
embedded in a Euclidean space. Here the topology on M is induced by the C^0-norm, while the measuring function \varphi takes each path \gamma\in M to its length. In Patrizio Frosini, ''Measuring shapes by size functions'', Proc. SPIE, Intelligent Robots and Computer Vision X: Algorithms and Techniques, Boston, MA, 1607:122–133, 1991. the case of M equal to the topological space of all ordered k-tuples of points in a submanifold of a Euclidean space is considered. Here the topology on M is induced by the metric d((P_1,\ldots,P_k),(Q_1\ldots,Q_k))=\max_\, P_i-Q_i\, . An extension of the concept of size function to algebraic topology was made in where the concept of
size homotopy group The concept of size homotopy group is analogous in size theory of the classical concept of homotopy group. In order to give its definition, let us assume that a size pair (M,\varphi) is given, where M is a closed manifold of class C^0\ and \var ...
was introduced. Here measuring functions taking values in \mathbb^k are allowed. An extension to
homology theory In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topolog ...
(the
size functor Given a size pair (M,f)\ where M\ is a manifold of dimension n\ and f\ is an arbitrary real continuous function defined on it, the i-th size functor, with i=0,\ldots,n\ , denoted by F_i\ , is the functor in Fun(\mathrm,\mathrm)\ , where \ ...
) was introduced in .Francesca Cagliari, Massimo Ferri and Paola Pozzi, ''Size functions from a categorical viewpoint'', Acta Applicandae Mathematicae, 67(3):225–235, 2001. The concepts of
size homotopy group The concept of size homotopy group is analogous in size theory of the classical concept of homotopy group. In order to give its definition, let us assume that a size pair (M,\varphi) is given, where M is a closed manifold of class C^0\ and \var ...
and
size functor Given a size pair (M,f)\ where M\ is a manifold of dimension n\ and f\ is an arbitrary real continuous function defined on it, the i-th size functor, with i=0,\ldots,n\ , denoted by F_i\ , is the functor in Fun(\mathrm,\mathrm)\ , where \ ...
are strictly related to the concept of persistent homology group Herbert Edelsbrunner, David Letscher and Afra Zomorodian, ''Topological Persistence and Simplification'', Discrete and Computational Geometry, 28(4):511–533, 2002. studied in persistent homology. It is worth to point out that the size function is the rank of the 0-th persistent homology group, while the relation between the persistent homology group and the size homotopy group is analogous to the one existing between
homology group In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topolog ...
s and
homotopy group In mathematics, homotopy groups are used in algebraic topology to classify topological spaces. The first and simplest homotopy group is the fundamental group, denoted \pi_1(X), which records information about loops in a space. Intuitively, homotop ...
s. Size functions have been initially introduced as a mathematical tool for shape comparison in
computer vision Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
and pattern recognition, and have constituted the seed of
size theory In mathematics, size theory studies the properties of topological spaces endowed with \mathbb^k-valued functions, with respect to the change of these functions. More formally, the subject of size theory is the study of the natural pseudodistance ...
.Françoise Dibos, Patrizio Frosini and Denis Pasquignon, ''The use of size functions for comparison of shapes through differential invariants'', Journal of Mathematical Imaging and Vision, 21(2):107–118, 2004.Andrea Cerri, Massimo Ferri, Daniela Giorgi, ''Retrieval of trademark images by means of size functions Graphical Models'' 68:451–471, 2006.Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, Bianca Falcidieno, ''Size functions for comparing 3D models'' Pattern Recognition 41:2855–2873, 2008. 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 \Delta^+.


Main properties

Assume that M is a compact locally connected Hausdorff space. The following statements hold: * every size function \ell_(x,y) is a non-decreasing function in the variable x and a non-increasing function in the variable y. * every size function \ell_(x,y) is locally right-constant in both its variables. * for every x, \ell_(x,y) is finite. * for every x<\min \varphi and every y>x, \ell_(x,y)=0. * for every y\ge\max \varphi and every x, \ell_(x,y) equals the number of connected components of M on which the minimum value of \varphi is smaller than or equal to x. If we also assume that M is a smooth
closed manifold In mathematics, a closed manifold is a manifold without boundary that is compact. In comparison, an open manifold is a manifold without boundary that has only ''non-compact'' components. Examples The only connected one-dimensional example ...
and \varphi is a C^1-function, the following useful property holds: * in order that (x,y) is a discontinuity point for \ell_ it is necessary that either x or y or both are critical values for \varphi.Patrizio Frosini, ''Connections between size functions and critical points'', Mathematical Methods in the Applied Sciences, 19:555–569, 1996. A strong link between the concept of size function and the concept of
natural pseudodistance In size theory, the natural pseudodistance between two size pairs (M,\varphi:M\to \mathbb)\ , (N,\psi:N\to \mathbb)\ is the value \inf_h \, \varphi-\psi\circ h\, _\infty\ , where h\ varies in the set of all homeomorphisms from the manifold M\ to ...
d((M,\varphi),(N,\psi)) between the size pairs (M,\varphi),\ (N,\psi) exists.Pietro Donatini and Patrizio Frosini, ''Lower bounds for natural pseudodistances via size functions'', Archives of Inequalities and Applications, 2(1):1–12, 2004. * if \ell_(\bar x,\bar y)>\ell_(\tilde x,\tilde y) then d((M,\varphi),(N,\psi))\ge \min\. The previous result gives an easy way to get lower bounds for the
natural pseudodistance In size theory, the natural pseudodistance between two size pairs (M,\varphi:M\to \mathbb)\ , (N,\psi:N\to \mathbb)\ is the value \inf_h \, \varphi-\psi\circ h\, _\infty\ , where h\ varies in the set of all homeomorphisms from the manifold M\ to ...
and is one of the main motivation to introduce the concept of size function.


Representation by formal series

An algebraic representation of size functions in terms of collections of points and lines in the real plane with multiplicities, i.e. as particular formal series, was furnished in Claudia Landi and Patrizio Frosini, ''New pseudodistances for the size function space'', Proc. SPIE Vol. 3168, pp. 52–60, Vision Geometry VI, Robert A. Melter, Angela Y. Wu, Longin J. Latecki (eds.), 1997. .Patrizio Frosini and Claudia Landi, ''Size functions and formal series'', Appl. Algebra Engrg. Comm. Comput., 12:327–349, 2001. The points (called ''cornerpoints'') and lines (called ''cornerlines'') of such formal series encode the information about discontinuities of the corresponding size functions, while their multiplicities contain the information about the values taken by the size function. Formally: * ''cornerpoints'' are defined as those points p=(x,y), with x, such that the number ::\mu (p)\min _ \ell _(x+\alpha ,y- \beta)-\ell _ (x+\alpha ,y+\beta )- \ell_ (x-\alpha ,y-\beta )+\ell _ (x-\alpha ,y+\beta ) :is positive. The number \mu (p) is said to be the ''multiplicity'' of p. * ''cornerlines'' and are defined as those lines r:x=k such that :: \mu (r)\min _\ell _(k+\alpha ,y)- \ell _(k-\alpha ,y)>0. : The number \mu (r) is sad to be the '' multiplicity'' of r. * ''Representation Theorem'': For every <, it holds ::\ell _(,)=\sum _\mu\big(p\big)+\sum _\mu\big(r\big). This representation contains the same amount of information about the shape under study as the original size function does, but is much more concise. This algebraic approach to size functions leads to the definition of new similarity measures between shapes, by translating the problem of comparing size functions into the problem of comparing formal series. The most studied among these metrics between size function is the
matching distance In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mode ...
.


References

{{reflist


See also

*
Size theory In mathematics, size theory studies the properties of topological spaces endowed with \mathbb^k-valued functions, with respect to the change of these functions. More formally, the subject of size theory is the study of the natural pseudodistance ...
*
Natural pseudodistance In size theory, the natural pseudodistance between two size pairs (M,\varphi:M\to \mathbb)\ , (N,\psi:N\to \mathbb)\ is the value \inf_h \, \varphi-\psi\circ h\, _\infty\ , where h\ varies in the set of all homeomorphisms from the manifold M\ to ...
*
Size functor Given a size pair (M,f)\ where M\ is a manifold of dimension n\ and f\ is an arbitrary real continuous function defined on it, the i-th size functor, with i=0,\ldots,n\ , denoted by F_i\ , is the functor in Fun(\mathrm,\mathrm)\ , where \ ...
*
Size homotopy group The concept of size homotopy group is analogous in size theory of the classical concept of homotopy group. In order to give its definition, let us assume that a size pair (M,\varphi) is given, where M is a closed manifold of class C^0\ and \var ...
* Size pair *
Matching distance In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mode ...
* Topological data analysis Topology Algebraic topology