Size function

Size function

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

Contents

Formal definition

In size theory, the size function \ell_{(M,\varphi)}:\Delta^+=\{(x,y)\in \mathbb{R}^2:x<y\}\to \mathbb{N} associated with the size pair (M,\varphi:M\to \mathbb{R}) is defined in the following way. For every (x,y)\in \Delta^+, \ell_{(M,\varphi)}(x,y) is equal to the number of connected components of the set \{p\in M:\varphi(p)\le y\} that contain at least one point at which the measuring function (a continuous function from a topological space M\ to \mathbb{R}^k\ .[1] [2]) φ takes a value smaller than or equal to x\ [3]. The concept of size function can be easily extended to the case of a measuring function \varphi:M\to \mathbb{R}^k, where \mathbb{R}^k is endowed with the usual partial order [4]. A survey about size functions (and size theory) can be found in [5].

An example of size function. (A) A size pair (M,\varphi:M\to\mathbb{R}), where M is the blue curve and \varphi:M\to \mathbb{R} is the height function. (B) The set \{p\in M:\varphi(p)\le b\} is depicted in green. (C) The set of points at which the measuring function φ takes a value smaller than or equal to a is depicted in red. (D) Two connected component of the set \{p\in M:\varphi(p)\le b\} contain at least one point at which the measuring function φ takes a value smaller than or equal to a. (E) The value of the size function \ell_{(M,\varphi)} in the point (a,b) is equal to 2.

History and applications

Size functions were introduced in [6] for the particular case of M\ equal to the topological space of all piecewise C^1\ closed paths in a C^\infty\ closed manifold 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 [7] 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_{1\le i\le k}\|P_i-Q_i\|.

An extension of the concept of size function to algebraic topology was made in [2], where the concept of size homotopy group was introduced. Here measuring functions taking values in \mathbb{R}^k are allowed. An extension to homology theory (the size functor) was introduced in [8]. The concepts of size homotopy group and size functor are strictly related to the concept of persistent homology group [9], 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 groups and homotopy groups.

Size functions have been initially introduced as a mathematical tool for shape comparison in computer vision and pattern recognition, and have constituted the seed of size theory [10], [11], [12], [13], [14], [3], [15], [16] 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_{(M,\varphi)}(x,y) is a non-decreasing function in the variable x\ and a non-increasing function in the variable y\ .

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

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

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

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


If we also assume that M\ is a smooth closed manifold and φ is a C^1\ -function, the following useful property holds:

¤ in order that (x,y)\ is a discontinuity point for \ell_{(M,\varphi)} it is necessary that either x\ or y\ or both are critical values for φ. [17]


A strong link between the concept of size function and the concept of natural pseudodistance d((M,φ),(N,ψ)) between the size pairs (M,\varphi),\  (N,\psi) exists [1], [18]:

¤ if \ell_{(N,\psi)}(\bar x,\bar y)>\ell_{(M,\varphi)}(\tilde x,\tilde y) then d((M,\varphi),(N,\psi))\ge \min\{\tilde x-\bar x,\bar y-\tilde y\}.

The previous result gives an easy way to get lower bounds for the natural pseudodistance 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 [19], [1], [20]. 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<y\ , such that the number

\mu (p){\stackrel{{\rm def}}{=}}\min _{\alpha >0 ,\beta>0} \ell _{({M},\varphi  )}(x+\alpha ,y-
\beta)-\ell _{({ M},\varphi )} (x+\alpha ,y+\beta )-
\ell_{({ M},\varphi )} (x-\alpha ,y-\beta )+\ell _{({ M} 
,\varphi   )} (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){\stackrel{\rm def}{=}}\min  _{\alpha >0 ,k+\alpha <y}\ell _{({ M},\varphi 
)}(k+\alpha ,y)-
\ell _{({ M},\varphi )}(k-\alpha ,y)>0. The number \mu (r)\ is sad to be the multiplicity of r\ .

  • Representation Theorem: For every {\bar x}<{\bar y}, it holds \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)

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[3].


References

  1. ^ a b c Patrizio Frosini, Claudia Landi, Size theory as a topological tool for computer vision, Pattern Recognition And Image Analysis, 9(4):596-603, 1999.
  2. ^ a b Patrizio Frosini, Michele Mulazzani, Size homotopy groups for computation of natural size distances, Bulletin of the Belgian Mathematical Society - Simon Stevin, 6:455-464 1999.
  3. ^ a b c Michele d'Amico, Patrizio Frosini, Claudia Landi, Using matching distance in Size Theory: a survey, International Journal of Imaging Systems and Technology, 16(5):154–161, 2006.
  4. ^ Silvia Biasotti, Andrea Cerri, Patrizio Frosini, Claudia Landi, Multidimensional size functions for shape comparison, Journal of Mathematical Imaging and Vision 32:161-179, 2008.
  5. ^ 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.
  6. ^ Patrizio Frosini, A distance for similarity classes of submanifolds of a Euclidean space, Bulletin of the Australian Mathematical Society, 42(3):407-416, 1990.
  7. ^ Patrizio Frosini, Measuring shapes by size functions, Proc. of SPIE, Intelligent Robots and Computer Vision X: Algorithms and Techniques, Boston, MA, 1607:122-133, 1991.
  8. ^ Francesca Cagliari, Massimo Ferri and Paola Pozzi, Size functions from a categorical viewpoint, Acta Applicandae Mathematicae, 67(3):225-235, 2001.
  9. ^ Herbert Edelsbrunner, David Letscher and Afra Zomorodian, Topological Persistence and Simplification, Discrete and Computational Geometry, 28(4):511-533, 2002.
  10. ^ Alessandro Verri, Claudio Uras, Patrizio Frosini and Massimo Ferri, On the use of size functions for shape analysis, Biological Cybernetics, 70:99-107, 1993.
  11. ^ Patrizio Frosini and Claudia Landi, Size functions and morphological transformations, Acta Applicandae Mathematicae, 49(1):85-104, 1997.
  12. ^ Alessandro Verri and Claudio Uras, Metric-topological approach to shape representation and recognition, Image Vision Comput., 14:189-207, 1996.
  13. ^ Alessandro Verri and Claudio Uras, Computing size functions from edge maps, Internat. J. Comput. Vision, 23(2):169-183, 1997.
  14. ^ 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.
  15. ^ Andrea Cerri, Massimo Ferri, Daniela Giorgi: Retrieval of trademark images by means of size functions Graphical Models 68:451-471, 2006.
  16. ^ Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, Bianca Falcidieno: Size functions for comparing 3D models. Pattern Recognition 41:2855-2873, 2008.
  17. ^ Patrizio Frosini, Connections between size functions and critical points, Mathematical Methods In The Applied Sciences, 19:555-569, 1996.
  18. ^ Pietro Donatini and Patrizio Frosini, Lower bounds for natural pseudodistances via size functions, Archives of Inequalities and Applications, 2(1):1-12, 2004.
  19. ^ Claudia Landi and Patrizio Frosini, New pseudodistances for the size function space, Proc. SPIE Vol. 3168, p. 52-60, Vision Geometry VI, Robert A. Melter, Angela Y. Wu, Longin J. Latecki (eds.), 1997.
  20. ^ Patrizio Frosini and Claudia Landi, Size functions and formal series, Appl. Algebra Engrg. Comm. Comput., 12:327-349, 2001.

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Size functor — Given a size pair (M,f) where M is a manifold of dimensionn and f is an arbitrary real continuous function definedon it, the i th size functor Francesca Cagliari, Massimo Ferri, Paola Pozzi, Size functions from a categorical viewpoint , Acta… …   Wikipedia

  • Size pair — In size theory, a size pair is a pair (M,varphi), where M is a compact topological space and varphi:M o mathbb{R}^k is a continuous function Patrizio Frosini, Claudia Landi, Size theory as a topological tool for computer vision , Pattern… …   Wikipedia

  • Size homotopy group — The concept of size homotopy group is the anologous 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… …   Wikipedia

  • Size changing — is the hypothetical process of reducing or enlarging the size, mass, and volume of an object in space, usually proportionally. It is a hypothetical process and is not to be confused with known processes where objects appear to change size through …   Wikipedia

  • Size-exclusion chromatography — Equipment for running size exclusion chromatography. The buffer is pumped through the column (right) by a computer controlled device Acronym SEC Classification Chromatography Analytes …   Wikipedia

  • Function-Point-Verfahren — Das Function Point Verfahren (auch Analyse oder Methode, kurz FPA) dient zur Bewertung des fachlich funktionalen Umfangs eines Informationstechnischen Systems, im Folgenden als Anwendung bezeichnet. Das Ergebnis einer Function Point Bewertung… …   Deutsch Wikipedia

  • Function point — A function point is a unit of measurement to express the amount of business functionality an information system provides to a user. Function points are the units of measure used by the IFPUG Functional Size Measurement Method. The IFPUG FSM… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • Function key — A function key is a key on a computer or terminal keyboard which can be programmed so as to cause an operating system command interpreter or application program to perform certain actions. On some keyboards/computers, function keys may have… …   Wikipedia

  • Function pointer — A function pointer is a type of pointer in C, C++, D, and other C like programming languages, and Fortran 2003.[1] When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function. In… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”