|
Claudia LANDI
Professore Ordinario Dipartimento di Scienze e Metodi dell'Ingegneria
|
Home |
Curriculum(pdf) |
Didattica |
Pubblicazioni
2023
- Decomposing filtered chain complexes: Geometry behind barcoding algorithms
[Articolo su rivista]
Chachólski, Wojciech; Giunti, Barbara; Jin, Alvin; Landi, Claudia
abstract
2023
- Morse inequalities for the Koszul complex of multi-persistence
[Articolo su rivista]
Guidolin, Andrea; Landi, Claudia
abstract
In this paper, we define the homological Morse numbers of a filtered cell complex in terms of the relative homology of nested filtration pieces and derive inequalities relating
these numbers to the Betti tables of the multi-parameter persistence modules of the considered filtration. Using the Mayer-Vietoris spectral sequence we first obtain strong and weak Morse inequalities involving the above quantities, and then
we improve the weak inequalities achieving a sharp lower bound for phonological Morse numbers. Furthermore, we prove a sharp upper bound for homological Morse numbers, expressed again in terms of the Betti tables.
2022
- Morse-Based Fibering of the Persistence Rank Invariant
[Capitolo/Saggio]
Bapat, A.; Brooks, R.; Hacker, C.; Landi, C.; Mahler, B. I.
abstract
2022
- Relative-perfectness of discrete gradient vector fields and multi-parameter persistent homology
[Articolo su rivista]
Landi, Claudia; Scaramuccia, Sara
abstract
The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires
the detection and interpretation of the possible interdependence among data components. To this end, in this paper, we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical
cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in 2-parameter persistence, our second contribution consists of two inequalities bounding Betti tables
of persistence modules from above and below, via the number of critical cells. Our last result shows that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension 2.
2021
- Invariants for tame parametrised chain complexes
[Articolo su rivista]
Chachólski, Wojciech; Giunti, Barbara; Landi, Claudia
abstract
We set the foundations for a new approach to Topological Data Analysis (TDA) based on homotopical methods at the chain complex level. We present the category of tame parametrised chain complexes as a comprehensive environment that includes several cases that usually TDA handles separately, such as persistence modules, zigzag modules, and commutative ladders. We extract new invariants in this category using a model structure and various minimal cofibrant approximations. Such approximations and their invariants retain some of the topological, and not just homological, aspects of the objects they approximate.
2020
- Computing multiparameter persistent homology through a discrete Morse-based approach
[Articolo su rivista]
Scaramuccia, Sara; Iuricich, Federico; De Floriani, Leila; Landi, Claudia
abstract
Persistent homology allows for tracking topological features, like loops, holes and their higher-dimensional analogues, along a single-parameter family of nested shapes. Computing descriptors for complex data characterized by multiple parameters is becoming a major challenging task in several applications, including physics, chemistry, medicine, and geography. Multiparameter persistent homology generalizes persistent homology to allow for the exploration and analysis of shapes endowed with multiple filtering functions. Still, computational constraints prevent multiparameter persistent homology to be a feasible tool for analyzing large size data sets. We consider discrete Morse theory as a strategy to reduce the computation of multiparameter persistent homology by working on a reduced dataset. We propose a new preprocessing algorithm, well suited for parallel and distributed implementations, and we provide the first evaluation of the impact of multiparameter persistent homology on computations.
2020
- Critical sets of PL and discrete Morse theory: a correspondence
[Articolo su rivista]
Fugacci, Ulderico; Landi, Claudia; Varli, Hanife
abstract
Piecewise-linear (PL) Morse theory and discrete Morse theory are used in shape analysis tasks to investigate the topological features of discretized spaces. In spite of their common origin in smooth Morse theory, various notions of critical points have been given in the literature for the discrete setting, making a clear understanding of the relationships occurring between them not obvious. This paper aims at providing equivalence results about critical points of the two discretized Morse theories. First of all, we prove the equivalence of the existing notions of PL critical points. Next, under an optimality condition called relative perfectness, we show a dimension agnostic correspondence between the set of PL critical points and that of discrete critical simplices ofthe combinatorial approach. Finally, we show how a relatively perfect discrete gradient vector field can be algorithmically built up to dimension 3. This way, we guarantee a formal and operative connection between critical sets in the PL and discrete theories.
2020
- The Reeb Graph Edit Distance Is Universal
[Relazione in Atti di Convegno]
Bauer, ULRICH ALEXANDER; Landi, Claudia; Mémoli, Facundo
abstract
We consider the setting of Reeb graphs of piecewise linear functions and study distances between
them that are stable, meaning that functions which are similar in the supremum norm ought to have
similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and
universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a
specific construction, we show that the interleaving distance and the functional distortion distance
on Reeb graphs are not universal.
2020
- The Reeb Graph Edit Distance is Universal
[Articolo su rivista]
Bauer, Ulrich; Landi, Claudia; Mémoli, Facundo
abstract
We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show
that the interleaving distance and the functional distortion distance on Reeb graphs are not universal.
2019
- A kernel for multi-parameter persistent homology
[Articolo su rivista]
Corbet, René; Fugacci, Ulderico; Kerber, Michael; Landi, Claudia; Wang, Bei
abstract
Topological data analysis and its main method, persistent homology, provide a toolkit for computing topological information of high-dimensional and noisy data sets. Kernels for one-parameter persistent homology have been established to connect persistent homology with machine learning techniques with applicability on shape analysis, recognition, and classification. We contribute a kernel construction for multi-parameter persistence by integrating a one-parameter kernel weighted along straight lines. We prove that our kernel is stable and efficiently computable, which establishes a theoretical connection between topological data analysis and machine learning for multivariate data analysis.
2019
- Acyclic Partial Matchings for Multidimensional Persistence: Algorithm and Combinatorial Interpretation
[Articolo su rivista]
Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo
abstract
Given a simplicial complex and a vector-valued function on its vertices, we present an algorithmic construction of an acyclic partial matching on the cells of the complex compatible with the given function. This implies the construction can be used to build a reduced filtered complex with the same multidimensional persistent homology as of the original one filtered by
the sublevel sets of the function. The correctness of the algorithm is proved, and its complexity is analyzed. A combinatorial interpretation of our algorithm based on the concept of a multidimensional discrete Morse function is introduced for the first time in this paper. Numerical experiments show a substantial rate of reduction in the number of cells achieved by the algorithm.
2019
- The persistent homotopy type distance
[Articolo su rivista]
Frosini, Patrizio; Landi, Claudia; Mémoli, Facundo
abstract
We introduce the persistent homotopy type distance d_HT to compare two real-valued functions dened on possibly different homotopy equivalent topological spaces. The underlying idea in the denition of d_HT is to measure the minimal shift that is necessary to apply to one of the two functions in order that the sublevel sets of the two functions become homotopy equivalent. This distance is interesting in connection with persistent
homology. Indeed, our main result states that d_HT still provides an upper bound for the bottleneck distance between the persistence diagrams of the intervening functions. Moreover, because homotopy equivalences are weaker than homeomorphisms, this implies a lifting of the standard stability results provided by the L^\infty distance and the natural pseudo-distance d_NP. From a different standpoint, we prove that d_HT extends the L^\infty distance and d_NP in two ways. First, we show that, appropriately restricting the category of objects to which d_HT applies, it can be made to coincide with the other two distances. Finally, we show that d_HT has an interpretation in terms of interleavings that naturally places it in the family of distances used in persistence theory.
2018
- The Rank Invariant Stability via Interleavings
[Capitolo/Saggio]
Landi, Claudia
abstract
A lower bound for the interleaving distance on persistence modules
is given in terms of matching distance of rank invariants. This offers
an alternative proof of the stability of rank invariants. As a further
contribution, also the internal stability of the rank invariant is proved in
terms of interleavings.
2017
- Algorithmic Construction of Acyclic Partial Matchings for Multidimensional Persistence
[Relazione in Atti di Convegno]
Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo
abstract
Given a simplicial complex and a vector-valued function on its vertices, we present an algorithmic construction of an acyclic partial matching on the cells of the complex. This construction is used to build a reduced filtered complex with the same multidimensional persistent homology as of the original one filtered by the sublevel sets of the function. A number of numerical experiments show a substantial rate of reduction in the number of cells achieved by the algorithm.
2017
- Reducing complexes in multidimensional persistent homology theory
[Articolo su rivista]
Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia
abstract
Forman's discrete Morse theory appeared to be useful for providing filtration-preserving reductions of complexes in the study of persistent homology. So far, the algorithms computing discrete Morse matchings have only been used for one-dimensional filtrations. This paper is perhaps the first attempt in the direction of extending such algorithms to multidimensional filtrations. An initial framework related to Morse matchings for the multidimensional setting is proposed, and a matching algorithm given by King, Knudson, and Mramor is extended in this direction. The correctness of the algorithm is proved, and its complexity analyzed. The algorithm is used for establishing a reduction of a simplicial complex to a smaller but not necessarily optimal cellular complex. First experiments with filtrations of triangular meshes are presented.
2017
- Reeb Graphs of Piecewise Linear Functions
[Relazione in Atti di Convegno]
Di Fabio, Barbara; Landi, Claudia
abstract
The Reeb graph is a popular tool in the field of computational
topology for shape analysis. The Reeb graph is usually thought of
as a transform from shapes, viewed as spaces endowed with functions, to
graphs. It finds its roots in the classical Morse theory, where the Reeb
graph transform is granted to produce a graph, but it finds its applications
mostly in Computer Graphics. Therefore it is usually applied on
objects that are not smooth but polyhedral. While the definition of the
Reeb graph perfectly makes sense also in the polyhedral case, it is not
straightforward to see that the output of the transform in this case is a
graph. This paper is devoted to provide a formal guarantee of this fact.
2016
- A discrete Morse-based approach to multivariate data analysis
[Relazione in Atti di Convegno]
Iuricich, Federico; Scaramuccia, Sara; Landi, Claudia; De Floriani, Leila
abstract
Multivariate data are becoming more and more popular in several
applications, including physics, chemistry, medicine, geography,
etc. A multivariate dataset is represented by a cell complex and a
vector-valued function defined on the complex vertices. The major
challenge arising when dealing with multivariate data is to obtain
concise and effective visualizations. The usability of common visual
elements (e.g., color, shape, size) deteriorates when the number
of variables increases. Here, we consider Discrete Morse Theory
(DMT) [Forman 1998] for computing a discrete gradient field on a
multivariate dataset. We propose a new algorithm, well suited for
parallel and distribute implementations. We discuss the importance
of obtaining the discrete gradient as a compact representation of the
original complex to be involved in the computation of multidimensional
persistent homology. Moreover, the discrete gradient field
that we obtain is at the basis of a visualization tool for capturing the
mutual relationships among the different functions of the dataset.
2016
- An Edit Distance for Reeb Graphs
[Relazione in Atti di Convegno]
Bauer, Ulrich; DI FABIO, Barbara; Landi, Claudia
abstract
We consider the problem of assessing the similarity of 3D shapes using Reeb graphs from the standpoint of robustness under perturbations. For this purpose, 3D objects are viewed as spaces endowed with real-valued functions, while the similarity between the resulting Reeb graphs is addressed through a graph edit distance. The cases of smooth functions on manifolds and piecewise linear functions on polyhedra stand out as the most interesting ones. The main contribution of this paper is the introduction of a general edit distance suitable for comparing Reeb graphs in these settings. This edit distance promises to be useful for applications in 3D object retrieval because of its stability properties in the presence of noise.
2016
- Hausdorff Stability of Persistence Spaces
[Articolo su rivista]
Cerri, Andrea; Landi, Claudia
abstract
Multidimensional persistence modules do not admit a concise representation
analogous to that provided by persistence diagrams for real-valued functions.
However, there is no obstruction for multidimensional persistent Betti numbers to
admit one. Therefore, it is reasonable to look for a generalization of persistence
diagrams concerning those properties that are related only to persistent Betti numbers.
In this paper, the persistence space of a vector-valued continuous function is
introduced to generalize the concept of persistence diagram in this sense. The main
result is its stability under function perturbations: Any change in vector-valued functions
implies a not greater change in the Hausdorff distance between their persistence
spaces.
2016
- The Edit Distance for Reeb Graphs of Surfaces
[Articolo su rivista]
DI FABIO, Barbara; Landi, Claudia
abstract
Reeb graphs are structural descriptors that capture shape properties of a
topological space from the perspective of a chosen function. In this work, we define a
combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary
to transform one graph into another by edit operations. The main contributions
of this paper are the stability property and the optimality of this edit distance. More precisely,
the stability result states that changes in the Reeb graphs, measured by the edit
distance, are as small as changes in the functions, measured by the maximum norm.
The optimality result states that the edit distance discriminates Reeb graphs better than
any other distance for Reeb graphs of surfaces satisfying the stability property.
2015
- Estimating multidimensional persistent homology through a finite sampling
[Articolo su rivista]
Cavazza, Niccolò; Ferri, Massimo; Landi, Claudia
abstract
An exact computation of the persistent Betti numbers of a submanifold X of a Euclidean space is possible only in a theoretical setting. In practical situations, only a finite sample of X is available. We show that, under suitable density conditions, it is possible to estimate the multidimensional persistent Betti numbers of X from the ones of a union of balls centered on the sample points; this even yields the exact value in restricted areas of the domain.
Using these inequalities we improve a previous lower bound for the natural pseudodistance to assess dissimilarity between the shapes of two objects from a sampling of them.
Similar inequalities are proved for the multidimensional persistent Betti numbers of the ball union and the one of a combinatorial description of it.
2015
- The natural pseudo-distance as a quotient pseudo-metric, and applications
[Articolo su rivista]
Cagliari, F.; Di Fabio, B.; Landi, Claudia
abstract
The natural pseudo-distance is a similarity measure conceived for the purpose of comparing shapes. In this paper we revisit this pseudo-distance from the point of view of quotients. In particular, we show that the natural pseudo-distance coincides with the quotient pseudo-metric on the space of continuous functions on a compact manifold, endowed with the uniform convergence metric, modulo self-homeomorphisms of the manifold. As applications of this result, the natural pseudo-distance is shown to be actually a metric on a number of function subspaces such as the space of topological embeddings, of isometries, and of simple Morse functions on surfaces.
2014
- Algebra lineare e geometria
[Altro]
Grasselli, Luigi; Landi, Claudia; Barani, Angiolina
abstract
Il presente testo propone prove di verifica formativa relative agli argomenti tradizionalmente trattati nei corsi universitari di Algebra Lineare e Geometria degli Spazi Euclidei. Per ogni argomento, vengono proposti e risolti due tipi di prove:
Si parte con una successione di quiz a risposta multipla, aventi lo scopo di fornire allo studente uno strumento di autovalutazione del grado di conoscenza degli aspetti più teorici della materia;
Una volta verificato, attraverso i quiz, il raggiungimento di una soddisfacente padronanza dei concetti teorici di base, lo studente può misurare la sua capacità di applicare tali strumenti in contesti concreti, affrontando la seconda tipologia di prove consistenti in esercizi numerici di tipo tradizionale.
La presente edizione risulta integrata, rispetto a quella precedente, da quiz ed esercizi riguardanti la teoria delle coniche e delle quadriche sviluppata nel contesto dell’ampliamento proiettivo degli spazi euclidei.
2014
- Special section on computational topology in image context
[Curatela]
Ferri, M.; Frosini, P.; Landi, C.
abstract
2014
- Stable shape comparison of surfaces via Reeb graphs
[Relazione in Atti di Convegno]
B., Di Fabio; Landi, Claudia
abstract
Reeb graphs are combinatorial signatures that capture shape properties from the perspective of a chosen function. One of the most important questions is whether Reeb graphs are robust against function perturbations that may occur because of noise and approximation errors in the data acquisition process. In this work we tackle the problem of stability by providing an editing distance between Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. Our main result is that the editing distance between two Reeb graphs is upper bounded by the extent of the difference of the associated functions, measured by the maximum norm. This yields the stability property under function perturbations.
2013
- Betti numbers in multidimensional persistent homology are stable functions
[Articolo su rivista]
A., Cerri; B., Di Fabio; M., Ferri; P., Frosini; Landi, Claudia
abstract
Multidimensional persistence mostly studies topological features of shapes by analyzing the lower level sets of vectorvalued functions, called filtering functions. As is well known, in the case of scalar-valued filtering functions, persistent homology groups can be studied through their persistent Betti numbers, that is, the dimensions of the images of the homomorphisms induced by the inclusions of lower level sets into each other. Whenever such inclusions exist for lower level sets of vector-valued filtering functions, we can consider the multidimensional analog of persistent Betti numbers. Varying the lower level sets,we obtain that persistent Betti numbers can be seen as functions taking pairs of vectors to the set of non-negative integers. In this paper,we prove stability of multidimensional persistent Betti numbers. More precisely, we prove that small changes of the vector-valued filtering functions imply only small changes of persistent Betti numbers functions. This result can be obtained by assuming the filtering functions to be just continuous.Multidimensional stability
opens the way to a stable shape comparison methodology based on multidimensional persistence. In order to obtain our
stability theorem, some other new results are proved for continuous filtering functions. They concern the finiteness of persistent Betti numbers for vector-valued filtering functions and the representation via persistence diagrams of persistent
Betti numbers, as well as their stability, in the case of scalar-valued filtering functions. Finally, from the stability of multidimensional persistent Betti numbers, we obtain a lower bound for the natural pseudo-distance.
2013
- Comparison of Persistent Homologies for Vector Functions: from continuous to discrete and back
[Articolo su rivista]
N., Cavazza; M., Ethier; P., Frosini; T., Kaczynski; Landi, Claudia
abstract
The theory of multidimensional persistent homology was initially developed in the discrete setting, and involved the study of simplicial complexes filtered through an ordering of the simplices. Later, stability properties of multidimensional persistence have been proved to hold when topological
spaces are filtered by continuous functions, i.e. for continuous data. This paper aims to provide a bridge between the continuous setting, where stability properties hold, and the discrete setting, where actual computations are carried out. More precisely, a stability preserving method is developed to compare rank invariants of vector functions obtained from discrete data. These advances confirm that multidimensional persistent homology is an appropriate tool for shape comparison in computer vision and computer graphics applications. The results are supported by numerical tests.
2013
- Erratum: Persistent Betti numbers for a noise tolerant shape-based approach to image retrieval (Pattern Recognition Letters (2013) 34 (1320-1321))
[Articolo su rivista]
Frosini, P.; Landi, C.
abstract
2013
- Persistent Betti numbers for a noise tolerant shape-based approach to image retrieval
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
In content-based image retrieval a major problem is the presence of noisy shapes. Noise
can present itself not only in the form of continuous deformations, but also as topological
changes. It is well known that persistent Betti numbers are a shape descriptor that admits
dissimilarity distances stable under continuous shape deformations. In this paper we focus
on the problem of dealing with noise that alters the topology of the studied objects. We
present a general method to turn persistent Betti numbers into stable descriptors also in
the presence of topological changes. Retrieval tests on the Kimia-99 database show the
effectiveness of the method.
2013
- The Persistence Space in Multidimensional Persistent Homology
[Relazione in Atti di Convegno]
Andrea, Cerri; Landi, Claudia
abstract
Multidimensional persistent modules do not admit a concise representation analogous to that provided by persistence diagrams for real-valued functions. However, there is no obstruction for multidimensional persistent Betti numbers to admit one. Therefore, it is reasonable to look for a generalization of persistence diagrams concerning those properties that are related only to persistent Betti numbers. In this paper, the persistence space of a vector-valued continuous function is introduced to generalize the concept of persistence diagram in this sense. Furthermore, it is presented a method to visualize topological features of a shape via persistence spaces. Finally, it is shown that this method is resistant to perturbations of the input data.
2012
- Applied and Computational Algebraic Topology Advanced School 2012 (ACAT 2012)
[Altro]
A., Cerri; B., Di Fabio; M., Ferri; P., Frosini; Landi, Claudia
abstract
The Bologna ACAT Advanced School focuses on the area of Computational Topology applied to Computer Image and Vision. It is mainly aimed at PhD students and young researchers in Mathematics, Applied Mathematics, and Computer Science interested in Computational Topology and Computer Vision and the interaction between these areas.In the Bologna ACAT Advanced School, experts in the fields of - Computational Homology - Persistent Topology - Discrete Morse Theory - Computer Vision will give introductory talks on the respective topics in which they are specialists.The Bologna ACAT Advanced School will be followed by the 4th International Workshop on Computational Topology in Image Context (CTIC2012), held in Bertinoro (Italy), May 28-30, 2012.
2012
- Computational Topology in Image Context
[Curatela]
M., Ferri; P., Frosini; Landi, Claudia; A., Cerri; B., Di Fabio
abstract
Organizing the 4th International Workshop on Computational Topology in ImageContext (CTIC 2012) has been an interesting experience indeed, going farbeyond Mathematics and Computer Science. This collection documents the presentations accepted at CTIC 2012. Theresearch made by the authors of these papers has been the core of the workshop,and we thank all the contributors for their commitment and dedication. Theireort has allowed us to continue the tradition of CTIC in providing a forum forscientic exchange in Topology and Computation in Image Context at a highquality level.
2012
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface
[Breve Introduzione]
Ferri, M.; Frosini, P.; Landi, C.; Cerri, A.; Di Fabio, B.
abstract
2012
- Persistence for shape comparison
[Abstract in Rivista]
Landi, Claudia
abstract
Persistence is a theory for Topological Data Analysis based on analyzing the scale at whichtopological features of a topological space appear and disappear along a filtration of thespace itself. As such, it is particularly suited for handling qualitative rather than quantitativeinformation about the studied space. Moreover, persistence deals with noise consistently, inthat noisy data do not need to be smoothed out in advance. Last but not least, it is modular,meaning that different filtrations give insights from different perspectives on the space understudy.For all these reasons persistence turns out to be a well-suited tool for shape comparison,i.e. the task of assessing similarity between digital shapes.In particular, persistence provides a shape descriptor, the persistence diagram, and adistance between these diagrams, the bottleneck distance. Thus the similarity between twoshapes, represented by spaces endowed by functions, is measured by the bottleneck distancebetween the corresponding persistence diagrams.Persistence diagrams are very concise descriptors, consisting of finitely many points ofthe plane. Moreover, the bottleneck distance between persistence diagrams is stable in thesense that small changes in the filtration imply small changes in the bottleneck distance.Finally, the bottleneck distance between persistence diagrams bounds from below the naturalpseudo-distance between the original shapes.
2012
- Persistence Modules, Shape Description, and Completeness
[Relazione in Atti di Convegno]
F., Cagliari; M., Ferri; L., Gualandri; Landi, Claudia
abstract
Persistence modules are algebraic constructs that can be used to describe the shape of an object starting from a geometric representation of it. As shape descriptors, persistence modules are not complete, that is they may not distinguish non-equivalent shapes. In this paper we show that one reason for this is that homomorphisms between persistence modules forget the geometric nature of the problem. Therefore we introduce geometric homomorphisms between persistence modules, and show that in some cases they perform better. A combinatorialstructure, the H0-tree, is shown to be an invariant for geometric isomorphism classes in the case of persistence modules obtained through the 0th persistent homology functor.
2012
- Persistent Homology and Partial Similarity of Shapes
[Articolo su rivista]
B., Di Fabio; Landi, Claudia
abstract
Persistent homology provides shapes descriptors called persistence diagrams. We use persistence diagrams to address the problem of shape comparison based on partial similarity. We show that two shapes having a common sub-part in general present a common persistence sub-diagram. Hence, the partial Hausdorff distance between persistence diagrams measures partial similarity between shapes. The approach is supported by experiments on 2D and 3D data sets.
2012
- Reeb graphs of curves are stable under function perturbations
[Articolo su rivista]
B., Di Fabio; Landi, Claudia
abstract
Reeb graphs provide a method to combinatorially describe the shape of amanifold endowed with a Morse function. One question deserving attention is whetherReeb graphs are robust against function perturbations. Focusing on 1-dimensional manifolds,we define an editing distance between Reeb graphs of curves, in terms of the costnecessary to transform one graph into another through editing moves. Our main result isthat changes in Morse functions induce smaller changes in the editing distance betweenReeb graphs of curves, implying stability of Reeb graphs under function perturbations. Wealso prove that our editing distance is equal to the natural pseudo-distance, and, moreover,that it is lower bounded by the bottleneck distance of persistent homology.
2012
- Stability of Reeb Graphs of Closed Curves
[Articolo su rivista]
B., Di Fabio; Landi, Claudia
abstract
Reeb graphs are very popular shape descriptors in computational frameworks as they capture both geometrical properties of the shape, and its topological features. Some different methodologies have been proposed in the literature to estimate the similarity of shapes through the comparison of the associated Reeb graphs. In this context, one of the most important open questions is whether Reeb graphs are robust against function perturbations. In fact, it is clear that any data acquisition is subject to perturbations, noise and approximation errors and, if Reeb graphs were not stable, then distinct computational investigations of the same object could produce completely different results. In this paper we present an initial contribution to establishing stability properties for Reeb graphs. More precisely, focusing our attention on 1-dimensional manifolds, we define an editing distance between Reeb graphs, in terms of the cost necessary to transform one graph into another. Our main result is that changes in Morse functions imply smaller changes in the editing distance between Reeb graphs.
2012
- 4th International Workshop on Computational Topology in Image Context (CTIC 2012)
[Altro]
M., Ferri; P., Frosini; Landi, Claudia; A., Cerri; B., Di Fabio; N., Cavazza
abstract
CTIC 2012 is a workshop devoted to computational methods using topology for the analysis and comparison of images. The involved research fields comprise computational topology and geometry, discrete topology and geometry, geometrical modeling, algebraic topology for image applications, and any other field involving a geometric-topological approach to image processing.
2011
- A Global Method for Reducing Multidimensional Size Graphs
[Relazione in Atti di Convegno]
A., Cerri; P., Frosini; W. G., Kropatsch; Landi, Claudia
abstract
This paper introduces the concept of discrete multidimensionalsize function, a mathematical tool studying the so-called sizegraphs. These graphs constitutes an ingredient of Size Theory, a geometrical/topological approach to shape analysis and comparison. A globalmethod for reducing size graphs is presented, together with a theoremstating that size graphs reduced in such a way preserve all the informationin terms of multidimensional size functions. This approach can leadto simplify the effective computation of discrete multidimensional sizefunctions, as shown by examples.
2011
- A Mayer–Vietoris Formula for Persistent Homology with an Application to Shape Recognition in the Presence of Occlusions
[Articolo su rivista]
B., Di Fabio; Landi, Claudia
abstract
In algebraic topology it is well known that, using the Mayer–Vietoris sequence, the homology of a space X can be studied by splitting X into subspaces A and B and computing the homology of A, B, and A∩B. A natural question is: To what extent does persistent homology benefit from a similar property? In this paper we show that persistent homology has a Mayer–Vietoris sequence that is generally not exact but only of order 2. However, we obtain a Mayer–Vietoris formula involving the ranks of the persistent homology groups of X, A, B, and A∩B plus three extra terms. This implies that persistent homological features of A and B can be found either as persistent homological features of X or of A∩B. As an application of this result, we show that persistence diagrams are able to recognize an occluded shape by showing a common subset of points.
2011
- Finiteness of rank invariants of multidimensional persistent homology groups
[Articolo su rivista]
F., Cagliari; Landi, Claudia
abstract
Rank invariants of multidimensional persistent homology groups are a parameterized version of Betti numbers of a space multi-filtered by a continuous vector-valued function. In this note we give a sufficient condition for their finiteness. This condition is sharp for spaces embeddable in R^n.
2011
- No embedding of the automorphisms of a topological space into a compact metric space endows them with a composition that passes to the limit
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
The Hausdorff distance, the Gromov–Hausdorff, the Fréchet and the natural pseudo-distance are instances of dissimilarity measures widely used in shape comparison. We show that they share the property of being defined as inf F(ρ) where F is a suitable functional and ρ varies in a set of correspondences containing the set of homeomorphisms. Our main result states that the set of homeomorphisms cannot be enlarged to a metric space K, in such a way that the composition in K (extending the composition of homeomorphisms) passes to the limit and, at the same time, K is compact.
2011
- Persistent Betti Numbers for a Noise Tolerant Shape-Based Approach to Image Retrieval
[Relazione in Atti di Convegno]
P., Frosini; Landi, Claudia
abstract
In content-based image retrieval a major problem is the presence of noisy shapes. It is well known that persistent Betti numbers area shape descriptor that admits a dissimilarity distance, the matchingdistance, stable under continuous shape deformations. In this paper wefocus on the problem of dealing with noise that changes the topologyof the studied objects. We present a general method to turn persistentBetti numbers into stable descriptors also in the presence of topologicalchanges. Retrieval tests on the Kimia-99 database show the effectivenessof the method.
2011
- Stable Shape Comparison by Persistent Homology
[Articolo su rivista]
M., Ferri; P., Frosini; Landi, Claudia
abstract
When shapes of objects are modeled as topologicalspaces endowed with functions, the shape comparison problem canbe dealt with using persistent homology to provide shape descriptors,and the matching distance to measure dissimilarities. Motivatedby the problem of dealing with incomplete or imprecise acquisitionof data in computer vision and computer graphics, recentpapers have studied stability properties of persistent Betti numbers with respect to perturbations both in the topological space and in the function. This paper reports on progress in this area of research.
2011
- Uniqueness of models in persistent homology: the case of curves
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
We consider generic curves in R^2, i.e. generic C^1 functions f : S^1 → R^2. We analyze these curves through the persistent homology groups of a filtration induced on S^1 by f . In particular, we consider the question whether these persistent homology groups uniquely characterize f , at least up to reparameterizationsof S^1. We give a partially positive answer to this question.More precisely, we prove that f = g ◦ h, where h : S^1 → S^1 is a C^1-diffeomorphism, if and only if the persistent homology groups of s ◦ f and s ◦g coincide, for every s belonging to the group S generated by reflections in the coordinate axes. Moreover, for a smaller set of generic functions, we show that f and g are close to each other in themax-norm (up to re-parameterizations)if and only if, for every s in S, the persistent Betti number functions of s ◦ f and s ◦ g are close to each other, with respect to a suitable distance.
2010
- “Computational and Geometric Topology” - A conference in honour of Massimo Ferri and Carlo Gagliardi on their 60-th birthday.
[Altro]
Bandieri, Paola; Casali, Maria Rita; A., Cattabriga; Cristofori, Paola; P., Frosini; Grasselli, Luigi; Landi, Claudia; M., Mulazzani
abstract
La conferenza ha inteso mettere in contatto ricercatori provenienti sia dall'ambito matematico che da quello ingegneristico, accomunati dall'interesse per tecniche topologiche di carattere geometrico e computazionale. Questi strumenti di ricerca sono essenziali in vari settori scientifici e per molteplici classi di applicazioni. In topologia geometrica risultano di particolare importanza le ricerche in teoria dei nodi, connesse allo studio di strutture biologiche (p.e. il confronto di dati genetici) e in fisica (con particolare riferimento alla teoria delle stringhe). La topologia computazionale si è invece rivelata indispensabile per la descrizione di forme al calcolatore e per la loro comparazione, con conseguenti ricadute nelle applicazioni che richiedono manipolazione grafica, confronto di modelli e reperimento di informazioni visuali. Tutto ciò ha ovvie importanti ricadute nel trattamento di dati in Internet. Tutti questi ambiti applicativi richiedono lo sviluppo di nuovi approcci teorici e competenze fortemente e intrinsecamente interdisciplinari, che l'iniziativa ha favorito.Il convegno si è articolato in sei conferenze su invito, tenute da alcuni tra i massimi esperti internazionali, della durata di 50 minuti ciascuna e da numerose comunicazioni di 30 minuti. Ha vauto lo scopo di divulgare nuovi risultati in Topologia Geometrica e Computazionale, ed ha coinvolto sia docenti che giovani ricercatori, nonché studenti di dottorato di ricerca in Matematica e/o in Ingegneria.Conferenzieri principali:Herbert Edelsbrunner (Duke University, Durham, NC, USA) Tomasz Kaczynski (Université de Sherbrooke, Canada)Sóstenes Lins (Departamento de Matemática, UFPE, Brasile)Sergei Matveev (Chelyabinsk State University, Russia) José María Montesinos (Universidad Complutense, Madrid, Spagna)Marian Mrozek (Jagiellonian University, Kraków, Polonia)
2010
- Estimating multidimensional persistent homology through a finite sampling
[Working paper]
N., Cavazza; M., Ferri; Landi, Claudia
abstract
An exact computation of the persistent Betti numbers of a submanifold X of a Euclidean space is possible only in a theoretical setting. In practical situations, only a finite sample of X is available. We show that, under suitable density conditions, it is possible to estimate the multidimensional persistent Betti numbers of X from the ones of a union of balls centered on the sample points;this even yields the exact value in restricted areas of the domain.Similar inequalities are proved for the multidimensional persistent Betti numbers of the ball union and the one of a combinatorial description of it.
2010
- Natural pseudo-distance and optimal matching between reduced size functions
[Articolo su rivista]
M., D’Amico; P., Frosini; Landi, Claudia
abstract
This paper studies the properties of a new lower bound for the natural pseudo-distance. The natural pseudo-distance is a dissimilarity measure between shapes, where a shape is viewed as a topological space endowed with a real-valued continuous function. Measuring dissimilarity amounts to minimizing the change in the functions due to the application of homeomorphisms between topological spaces, with respect to the L ∞-norm. In order to obtain the lower bound, a suitable metric between size functions, called matching distance, is introduced. It compares size functions by solving an optimal matching problem between countable point sets. The matching distance is shown to be resistant to perturbations, implying that it is always smaller than the natural pseudo-distance. We also prove that the lower bound so obtained is sharp and cannot be improved by any other distance between size functions.
2010
- Persistent homology and partial matching of shapes
[Abstract in Rivista]
Landi, Claudia
abstract
The ability to perform not only global matching but also partial matching is investigated in computer vision and computer graphics in order to evaluate the performance ofshape descriptors. In my talk I will consider the persistent homology shape descriptor, and Iwill illustrate some results about persistence diagrams of occluded shapes and partial shapes.The main tool is a Mayer-Vietoris formula for persistent homology. Theoretical results indicate that persistence diagrams are able to detect a partial matching between shapes byshowing a common subset of points both in the one-dimensional and the multi-dimensionalsetting. Experiments will be presented which outline the potential of the proposed approachin recognition tasks in the presence of partial information.
2009
- Recognition of Occluded Shapes Using Size Functions
[Relazione in Atti di Convegno]
B., Di Fabio; Landi, Claudia; F., Medri
abstract
The robustness against occlusions and the ability to performnot only global matching, but also partial matching are investigated incomputer vision in order to evaluate the performance of shape descriptors.In this paper we consider the size function shape descriptor, andwe illustrate some results about size functions of occluded shapes. Theoreticalresults indicate that size functions are able to detect a partialmatching between shapes by showing a common subset of cornerpoints.Experiments are presented which outline the potential of the proposedapproach in recognition tasks in the presence of occlusions.
2009
- Reparametrization invariant norms
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
This paper explores the concept of reparametrization invariantnorm (RPI-norm) for C^1-functions that vanish at −∞ and whose derivativehas compact support, such as C^1_c -functions. An RPI-norm is any norm invariantunder composition with orientation-preserving diffeomorphisms. TheL_∞-norm and the total variation norm are well-known instances of RPI-norms.We prove the existence of an infinite family of RPI-norms, called standard RPI-norms,for which we exhibit both an integral and a discrete characterization.Our main result states that for every piecewise monotone function ϕ in C^1_c (R)the standard RPI-norms of ϕ allow us to compute the value of any other RPI-normof ϕ. This is proved using the standard RPI-norms to reconstruct thefunction ϕ up to reparametrization, sign and an arbitrarily small error withrespect to the total variation norm.
2008
- Describing shapes by geometrical- topological properties of real functions
[Articolo su rivista]
Biasotti, S; DE FLORIANI, L; Falcidieno, B; Frosini, P; Giorgi, D; Landi, Claudia; Papaleo, L; Spagnolo, M.
abstract
In the last decade, an increasing number of methods that are rooted in Morse theory andmake use of properties of real-valued functions for describing shapes have been proposed in theliterature. The methods proposed range from approaches which use the configuration of contoursfor encoding topographic surfaces to more recent work on size theory and persistent homology.All these have been developed over the years with a specific target domain and it is not trivial tosystematize this work and understand the links, similarities and differences among the differentmethods. Moreover, different terms have been used to denote the same mathematical constructs,which often overwhelms the understanding of the underlying common framework.The aim of this survey is to provide a clear vision of what has been developed so far, focusingon methods that make use of theoretical frameworks that are developed for classes of realfunctions rather than for a single function, even if they are applied in a restricted manner. Theterm geometrical-topological used in the title is meant to underline that both levels of informationcontent are relevant for the applications of shape descriptions: geometrical, or metrical, propertiesand attributes are crucial for characterizing specific instances of features, while topologicalproperties are necessary to abstract and classify shapes according to invariant aspects of their geometry.The approaches surveyed will be discussed in detail, with respect to theory, computationand application. Several properties of the shape descriptors will be analyzed and compared. Webelieve this is a crucial step to exploit fully the potential of such approaches in many applications,as well as to identify important areas of future research.
2008
- Multidimensional size functions for shape comparison
[Articolo su rivista]
S., Biasotti; A., Cerri; P., Frosini; D., Giorgi; Landi, Claudia
abstract
Size Theory has proven to be a useful framework for shape analysis in the context of pattern recognition. Its main tool is a shape descriptor called size function.Size Theory has been mostly developed in the $1$-dimensional setting, meaning that shapes are studied with respect to functions, defined on the studied objects, with values in $\R$. The potentialities of the $k$-dimensional setting, that is using functions with values in $\R^k$, were not explored until now for lack of an efficient computational approach. In this paper we provide the theoretical results leading to a concise and complete shape descriptor also in the multidimensional case. This is possible because we prove that in Size Theory thecomparison of multidimensional size functions can be reduced tothe $1$-dimensional case by a suitable change of variables.Indeed, a foliation in half-planes can be given, suchthat the restriction of a multidimensional size function to eachof these half-planes turns out to be a classical size function intwo scalar variables. This leads to the definition of a newdistance between multidimensional size functions, and to the proofof their stability with respect to that distance. Experiments are carried out to show the feasibility of the method.
2006
- A global reduction method for multidimensional size graphs
[Articolo su rivista]
A., Cerri; P., Frosini; Landi, Claudia
abstract
This paper introduces the concept of discrete multidimensional size function, a mathematical tool that studies particular graphs called size graphs. A global method for reducing size graphs and a theorem, stating that discrete multidimensional size functions are invariant with respect to this reduction method, are shown. This result allows us to easly and fast compute discrete multidimensional size functions for applications.
2006
- Metodi Geometrici nelle Applicazioni e nell'Industria (MeGAI'06)
[Altro]
M., Ferri; P., Frosini; Landi, Claudia; B., Di Fabio; A., Cerri
abstract
L'obiettivo di MeGAI'06 è far emergere le non poche applicazioni dei metodi geometrici nelle applicazioni e nell'industria
2006
- Using matching distance in size theory: A survey
[Articolo su rivista]
D'Amico, M; Frosini, P; Landi, Claudia
abstract
In this survey we illustrate how the matching distance between reduced size functions can be applied for shape comparison. We assume that each shape can be thought of as a compact connected manifold with a real continuous function defined on it, that is a pair : (M,phi : M --> R), called size pair. In some sense, the function phi focuses on the properties and the invariance of the problem at hand. In this context, matching two size pairs (M, phi) and (N, psi) means looking for a homeomorphism between M and N that minimizes the difference of values taken by phi and psi on the two manifolds. Measuring the dissimilarity between two shapes amounts to the difficult task of computing the value delta = inf(f) max(P is an element of M)\phi(P) - psi(f(P))\, where f varies among all the homeomorphisms from M to N. From another point of view, shapes can be described by reduced size functions associated with size pairs. The matching distance between reduced size functions allows for a robust to perturbations comparison of shapes. The link between reduced size functions and the dissimilarity measure delta is established by a theorem, stating that the matching distance provides an easily computable lower bound for delta. Throughout this paper we illustrate this approach to shape comparison by means of examples and experiments. (C) 2007 Wiley Periodicals, Inc.
2005
- Algebra lineare e geometria
[Altro]
A., Barani; Grasselli, Luigi; Landi, Claudia
abstract
Quiz ed esercizi commentati e risolti
2003
- Intrinsic harmonicity of Morse functions
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
Consider a real valued Morse function f on a C-2 closed connected n-dimensional manifold M. It is proved that a suitable Riemannian metric exists on M, such that f is harmonic outside the set of critical points off of index 0 and n. The proof is based on a result of Calabi [1], providing a criterion for a closed one-form on a closed connected manifold to be harmonic with respect to some Riemannian metric.
2002
- Size functions as complete invariants for image recognition
[Relazione in Atti di Convegno]
Landi, Claudia; P., Frosini
abstract
The problem of completeness for invariant size functions isstudied. Families of size functions are introduced, which allowrecognition of some classes of plane curves up to transformations of increasing generality.
2001
- Presentations of Morse homology for studying shape of manifolds
[Working paper]
F., Cagliari; Landi, Claudia; Grasselli, Luigi
abstract
A new paradigm for describing the shape of manifolds is presented,with a particular regard to applications in pattern recognition.Given a Morse function f defined on a closed smooth manifoldM, the shape of the pair (M,f) is represented by the evolutionof the homology groups of the lower level sets of M with respect to f. The main tool is classical Morse theory. Analgorithm for treating the case of orientable surfaces is given.
2001
- Size functions and formal series
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
In this paper we consider a mathematical tool for shape description called size function. We prove that every size function can be represented as a set of points and lines in the real plane, with multiplicities. This allows for an algebraic approach to size functions and the construction of new pseudo-distances between size functions for comparing shapes.
2000
- Anelli di coomologia dei gruppi di Artin
[Articolo su rivista]
Landi, C.
abstract
2000
- Cohomology rings of Artin groups
[Articolo su rivista]
Landi, Claudia
abstract
In this paper integer cohomology rings of Artin groups associated with exceptional groupsare determined. Computations have been carried out by using an effective method for calculation of cupproduct in cellular cohomology which we introduce here. Actually, our method works in general for anyfinite regular complex with identifications, the regular complex being geometrically realized by a compactorientable manifold, possibly with boundary.
1999
- Algebraic representation of size functions
[Relazione in Atti di Convegno]
Landi, Claudia; P., Frosini
abstract
In this paper we show that size functions, a class of shape descriptors, can be represented as countable collections of points and lines of the real plane with multiplicities, i.e. as particular formal series. This algebraic approach allows to reduce the information storage necessary to work with size functions. Some further applications are discussed. Namely, the possibility ofdefining new pseudo-distances between size functions and the possibility of emphasizing the part of information considered more important from the shape recognition viewpoint in order to make recognition more efficient.
1999
- Deformation energy for size functions
[Relazione in Atti di Convegno]
P., Donatini; P., Frosini; Landi, Claudia
abstract
Size functions are functions from the real plane to thenatural numbers useful for describing shapes of objects. Theyallow to translate the problem of comparing shapes to the problemof comparing functions, that is a much simpler task. In order toperform the comparison between size functions we present a methodto measure the energy necessary to deform size functions into eachother. Minimizing such an energy allows for a measure of thesimilarity between shapes. Some experimental results concerningthe comparison of free hand-drawn sketches are shown.
1999
- Size theory as a topological tool for computer vision
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
In this paper we give an outline of Size Theory and its mainresults. The usefulness of such a theory in comparing shapes is high-lighted by showing some examples. The robustness of Size Theory withrespect to noise and occlusions is pointed out. In addition, an algebraicapproach to the theory is presented.
1997
- New pseudo-distances for the size function space
[Relazione in Atti di Convegno]
Landi, Claudia; P., Frosini
abstract
A method to construct new pseudo-distances for the size function space based on the formal series representation of size functions is introduced. These new pseudo-distances allow to measure quantitatively the differences in shapes by comparing size functions. Some experiments on digital images are shown.
1997
- Size functions and morphological transformations
[Articolo su rivista]
P., Frosini; Landi, Claudia
abstract
In this paper changes of size functions under morphological transformations are studied. Some inequalities concerning size functions of a subset of the Euclidean plane, its dilation by an open disk and its skeleton are proved. Such inequalities prove the stability of size functions with respect to these morphological transformations and give a new approach for computation in Size Theory.
1996
- Connections between size functions and morphological transformations
[Relazione in Atti di Convegno]
Landi, Claudia; P., Frosini
abstract
Inequalities involving size functions of a subset of the Euclidean plane, its dilation and its skeleton are given, which lead to new techniques of computation of size functions. Some experiments on digital images are shown.