From metric homotopies to nD
persistence
Massimo Ferri
Mathematics Department
Univ. of Bologna
http://www.dm.unibo.it/~ferri/e.htm
[email protected]
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
2/57
The University of Bologna
• Oldest in Europe?
(Competitor: La Sorbonne)
• Active at the end of the
11th century as a Law
school
• 1158: formal recognition by
Emperor Frederick I
Barbarossa
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
3/57
The University of Bologna
Some “visiting professors”:
• Dante Alighieri
• Thomas Becket
• Erasmus of Rotterdam
Thomas Becket
Ljubljana, 12/4/2012
A good student:
• Nicolaus Copernicus
M. Ferri – From metric homotopies to nD persistence
4/57
The University of Bologna
Mathematics in Bologna:
• Luca Pacioli (14th c.): arithmetic and geometry
• Rafael Bombelli (16th c.): invention of complex #’s
• Scipione Dal Ferro, Gerolamo Cardano, Ludovico
Ferrari (16th c.): 3rd and 4th degree formulas
• Bonaventura Cavalieri, Pietro Mengoli (17th c.):
early integral calculus
• Maria Gaetana Agnesi (18th c.): analytical geometry
• Luigi Cremona, Eugenio Beltrami, Beniamino Segre
(19th-20th c.): algebraic geometry
• Cesare Arzela`, Leonida Tonelli (20th c.): analysis
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
5/57
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
6/57
Metric homotopies
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
7/57
Metric homotopies
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
8/57
Metric homotopies
Two minimal paths…
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
9/57
Metric homotopies
…showing the lack of associativity
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
10/57
Metric homotopies
• No way of obtaining a group
• Just a fake one…
A minimal
path on a
cube
… which may be fairly complicated.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
11/57
Metric homotopies
My student Patrizio Frosini decided for a totally
different approach:
Size Functions
Frosini, P., Measuring shapes by size functions, Proc. of SPIE, Intelligent Robots
and Computer Vision X: Algorithms and Techniques, Boston, MA 1607 (1991).
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
12/57
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
13/57
Size Functions and Natural Pseudodistance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
14/57
Size Functions and Natural Pseudodistance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
15/57
Size Functions and Natural Pseudodistance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
16/57
Size Functions and Natural Pseudodistance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
17/57
Size Functions and Natural Pseudodistance
Approximation
translates into
“blind strips”.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
18/57
Size Functions and Natural Pseudodistance
All information carried by a size function can be
condensed in the formal series of its cornerpoints
The matching distance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
19/57
Size Functions and Natural Pseudodistance
The matching distance between formal series of
cornerpoints is stable under perturbation of the
measuring function!
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
20/57
Size Functions and Natural Pseudodistance
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
21/57
Size Functions and Natural Pseudodistance
It turns out that:
i.e. the matching distance between size functions
yields a lower bound (and an optimal one!) to the
natural pseudodistance.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
22/57
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
23/57
Applications
• Classification problems:
 Bologna
•
•
•
•
Leukocytes
Monograms
Sketches
Melanocytic lesions
 Genova
•
•
•
•
Ljubljana, 12/4/2012
Tree leaves
Numerals
Alphabet of the deaf
Cars
M. Ferri – From metric homotopies to nD persistence
24/57
Applications
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
25/57
Applications
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
26/57
Applications
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
27/57
Applications
Similitudes
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
28/57
Applications
Affine transformations
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
29/57
Applications
Homographies
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
30/57
Applications
naevus
melanoma
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
31/57
Applications
An image and one
of its splittings.
The curve of the image
(meas. fct.: luminance).
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
32/57
Applications
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
33/57
Applications
• Image retrieval
 Sea fauna
 Silhouettes
 Trade marks
• “Keypics”
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
34/57
Applications
Query
1
2
3
CSS
our system
CSS
our system
The challenge of a public database.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
35/57
Applications
Query
1
2
3
CSS
our system
CSS
our system
The challenge of a public database.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
36/57
Applications
Trade marks: two queries and the first eight
retrieved images
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
37/57
Applications
• We suggest that images on the Internet
should be equipped with simplified sketches
representing the essentials of the images
themselves: keypics.
• Keypics should be provided by the image
owner or manager.
• This graphical indexing might be extended to
whole Web pages.
• Encoding of keypics should be standard (e.g.
in SVG).
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
38/57
Applications
A Data Manager might wish to index the image of a
saxophone by its geometrical outline, but also (or only)
with a musical note.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
39/57
Applications
Some different
keypic drawing
conceptions.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
40/57
Applications
A retrieval experiment
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
41/57
Applications
A retrieval experiment
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
42/57
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
43/57
nD persistence
• k-dimensional measuring functions
• Higher degree homology
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
44/57
nD persistence
k-dimensional measuring functions
Frosini, P., Mulazzani, M., Size homotopy groups for computation of natural size distances,
Bull. of the Belgian Math. Soc. - Simon Stevin, 6 (1999), 455-464.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
45/57
nD persistence
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
46/57
nD persistence
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
47/57
nD persistence
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
48/57
nD persistence
Higher homology modules (persistent homology /
size functor)
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
49/57
nD persistence
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
50/57
nD persistence
Persistent homology for k-dimensional measuring
functions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
51/57
nD persistence
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
52/57
nD persistence
The reduction theorem from k-dimensional to 1dimensional measuring functions - through
maxima along admissible pairs - works
unaltered also for higher homology modules!
Cagliari, F., Di Fabio, B., Ferri, M., One-dimensional reduction of multidimensional
persistent homology, Proc. Amer. Math. Soc. 138 (2010), 3003-3017.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
53/57
From metric homotopies to nD persistence
•
•
•
•
•
•
The University of Bologna
Metric homotopies
Size Functions and Natural Pseudodistance
Applications
nD persistence
Work in progress and conclusions
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
54/57
Work in progress and conclusions
Present research:
•
•
•
•
•
Search for optimal admissible pairs
Better bounds for the natural pseudodistance
Algorithms
Applications to colour images and 3D meshes
New applications to melanoma diagnosis
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
55/57
Work in progress and conclusions
The theory of Size Functions is developing along
two directions: k-dimensionality and higher
homology modules.
Together with “concrete” applications in Pattern
Recognition, we would like to find contact points
with other theoretical domains.
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
56/57
THANK YOU FOR YOUR
ATTENTION !
Ljubljana, 12/4/2012
M. Ferri – From metric homotopies to nD persistence
57/57