- Source: Size function
Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane
x
<
y
{\displaystyle 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, the size function
ℓ
(
M
,
φ
)
:
Δ
+
=
{
(
x
,
y
)
∈
R
2
:
x
<
y
}
→
N
{\displaystyle \ell _{(M,\varphi )}:\Delta ^{+}=\{(x,y)\in \mathbb {R} ^{2}:x
associated with the size pair
(
M
,
φ
:
M
→
R
)
{\displaystyle (M,\varphi :M\to \mathbb {R} )}
is defined in the following way. For every
(
x
,
y
)
∈
Δ
+
{\displaystyle (x,y)\in \Delta ^{+}}
,
ℓ
(
M
,
φ
)
(
x
,
y
)
{\displaystyle \ell _{(M,\varphi )}(x,y)}
is equal to the number of connected components of the set
{
p
∈
M
:
φ
(
p
)
≤
y
}
{\displaystyle \{p\in M:\varphi (p)\leq y\}}
that contain at least one point at which the measuring function (a continuous function from a topological space
M
{\displaystyle M}
to
R
k
{\displaystyle \mathbb {R} ^{k}}
)
φ
{\displaystyle \varphi }
takes a value smaller than or equal to
x
{\displaystyle x}
.
The concept of size function can be easily extended to the case of a measuring function
φ
:
M
→
R
k
{\displaystyle \varphi :M\to \mathbb {R} ^{k}}
, where
R
k
{\displaystyle \mathbb {R} ^{k}}
is endowed with the usual partial order
.
A survey about size functions (and size theory) can be found in.
History and applications
Size functions were introduced in
for the particular case of
M
{\displaystyle M}
equal to the topological space of all piecewise
C
1
{\displaystyle C^{1}}
closed paths in a
C
∞
{\displaystyle C^{\infty }}
closed manifold embedded in a Euclidean space. Here the topology on
M
{\displaystyle M}
is induced by the
C
0
{\displaystyle C^{0}}
-norm, while the measuring function
φ
{\displaystyle \varphi }
takes each path
γ
∈
M
{\displaystyle \gamma \in M}
to its length.
In
the case of
M
{\displaystyle M}
equal to the topological space of all ordered
k
{\displaystyle k}
-tuples of points in a submanifold of a Euclidean space is considered.
Here the topology on
M
{\displaystyle M}
is induced by the metric
d
(
(
P
1
,
…
,
P
k
)
,
(
Q
1
…
,
Q
k
)
)
=
max
1
≤
i
≤
k
‖
P
i
−
Q
i
‖
{\displaystyle d((P_{1},\ldots ,P_{k}),(Q_{1}\ldots ,Q_{k}))=\max _{1\leq i\leq k}\|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 was introduced. Here measuring functions taking values in
R
k
{\displaystyle \mathbb {R} ^{k}}
are allowed.
An extension to homology theory (the size functor) was introduced in
.
The concepts of size homotopy group and size functor are strictly related to the concept of persistent homology group
studied in persistent homology. It is worth to point out that the size function is the rank of the
0
{\displaystyle 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.
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
Δ
+
{\displaystyle \Delta ^{+}}
.
Main properties
Assume that
M
{\displaystyle M}
is a compact locally connected Hausdorff space. The following statements hold:
every size function
ℓ
(
M
,
φ
)
(
x
,
y
)
{\displaystyle \ell _{(M,\varphi )}(x,y)}
is a non-decreasing function in the variable
x
{\displaystyle x}
and a non-increasing function in the variable
y
{\displaystyle y}
.
every size function
ℓ
(
M
,
φ
)
(
x
,
y
)
{\displaystyle \ell _{(M,\varphi )}(x,y)}
is locally right-constant in both its variables.
for every
x
<
y
{\displaystyle x
,
ℓ
(
M
,
φ
)
(
x
,
y
)
{\displaystyle \ell _{(M,\varphi )}(x,y)}
is finite.
for every
x
<
min
φ
{\displaystyle x<\min \varphi }
and every
y
>
x
{\displaystyle y>x}
,
ℓ
(
M
,
φ
)
(
x
,
y
)
=
0
{\displaystyle \ell _{(M,\varphi )}(x,y)=0}
.
for every
y
≥
max
φ
{\displaystyle y\geq \max \varphi }
and every
x
<
y
{\displaystyle x
,
ℓ
(
M
,
φ
)
(
x
,
y
)
{\displaystyle \ell _{(M,\varphi )}(x,y)}
equals the number of connected components of
M
{\displaystyle M}
on which the minimum value of
φ
{\displaystyle \varphi }
is smaller than or equal to
x
{\displaystyle x}
.
If we also assume that
M
{\displaystyle M}
is a smooth closed manifold and
φ
{\displaystyle \varphi }
is a
C
1
{\displaystyle C^{1}}
-function, the following useful property holds:
in order that
(
x
,
y
)
{\displaystyle (x,y)}
is a discontinuity point for
ℓ
(
M
,
φ
)
{\displaystyle \ell _{(M,\varphi )}}
it is necessary that either
x
{\displaystyle x}
or
y
{\displaystyle y}
or both are critical values for
φ
{\displaystyle \varphi }
.
A strong link between the concept of size function and the concept of natural pseudodistance
d
(
(
M
,
φ
)
,
(
N
,
ψ
)
)
{\displaystyle d((M,\varphi ),(N,\psi ))}
between the size pairs
(
M
,
φ
)
,
(
N
,
ψ
)
{\displaystyle (M,\varphi ),\ (N,\psi )}
exists.
if
ℓ
(
N
,
ψ
)
(
x
¯
,
y
¯
)
>
ℓ
(
M
,
φ
)
(
x
~
,
y
~
)
{\displaystyle \ell _{(N,\psi )}({\bar {x}},{\bar {y}})>\ell _{(M,\varphi )}({\tilde {x}},{\tilde {y}})}
then
d
(
(
M
,
φ
)
,
(
N
,
ψ
)
)
≥
min
{
x
~
−
x
¯
,
y
¯
−
y
~
}
{\displaystyle d((M,\varphi ),(N,\psi ))\geq \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
.
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
)
{\displaystyle p=(x,y)}
, with
x
<
y
{\displaystyle x
, such that the number
μ
(
p
)
=
d
e
f
min
α
>
0
,
β
>
0
ℓ
(
M
,
φ
)
(
x
+
α
,
y
−
β
)
−
ℓ
(
M
,
φ
)
(
x
+
α
,
y
+
β
)
−
ℓ
(
M
,
φ
)
(
x
−
α
,
y
−
β
)
+
ℓ
(
M
,
φ
)
(
x
−
α
,
y
+
β
)
{\displaystyle \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
μ
(
p
)
{\displaystyle \mu (p)}
is said to be the multiplicity of
p
{\displaystyle p}
.
cornerlines and are defined as those lines
r
:
x
=
k
{\displaystyle r:x=k}
such that
μ
(
r
)
=
d
e
f
min
α
>
0
,
k
+
α
<
y
ℓ
(
M
,
φ
)
(
k
+
α
,
y
)
−
ℓ
(
M
,
φ
)
(
k
−
α
,
y
)
>
0.
{\displaystyle \mu (r){\stackrel {\rm {def}}{=}}\min _{\alpha >0,k+\alpha
The number
μ
(
r
)
{\displaystyle \mu (r)}
is sad to be the multiplicity of
r
{\displaystyle r}
.
Representation Theorem: For every
x
¯
<
y
¯
{\displaystyle {\bar {x}}<{\bar {y}}}
, it holds
ℓ
(
M
,
φ
)
(
x
¯
,
y
¯
)
=
∑
p
=
(
x
,
y
)
x
≤
x
¯
,
y
>
y
¯
μ
(
p
)
+
∑
r
:
x
=
k
k
≤
x
¯
μ
(
r
)
{\displaystyle \ell _{({M},\varphi )}({\bar {x}},{\bar {y}})=\sum _{p=(x,y) \atop x\leq {\bar {x}},y>{\bar {y}}}\mu {\big (}p{\big )}+\sum _{r:x=k \atop k\leq {\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.
References
See also
Size theory
Natural pseudodistance
Size functor
Size homotopy group
Size pair
Matching distance
Topological data analysis