Foto personale

Claudia LANDI

Department of Engineering Sciences and Methods

Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia; Masoni, Filippo ( 2017 ) - Algorithmic Construction of Acyclic Partial Matchings for Multidimensional Persistence - DGCI 2017: Discrete Geometry for Computer Imagery - n. volume 10502 - pp. da 375 a 387 ISBN: 978-3-319-66271-8; 978-3-319-66272-5 | 978-3-319-66272-5 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia ( 2017 ) - Reducing complexes in multidimensional persistent homology theory - JOURNAL OF SYMBOLIC COMPUTATION - n. volume 78 - pp. da 61 a 75 ISSN: 0747-7171 [Articolo in rivista (262) - Articolo su rivista]
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.

Di Fabio, Barbara; Landi, Claudia ( 2017 ) - Reeb Graphs of Piecewise Linear Functions - Graph-Based Representations in Pattern Recognition. GbRPR 2017. - n. volume 10310 - pp. da 23 a 35 ISBN: 978-3-319-58960-2; 978-3-319-58961-9 | 978-3-319-58961-9 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Iuricich, Federico; Scaramuccia, Sara; Landi, Claudia; De Floriani, Leila ( 2016 ) - A discrete Morse-based approach to multivariate data analysis - Proceeding SA '16 SIGGRAPH ASIA 2016 Symposium on Visualization - pp. da 1 a 8 ISBN: 9781450345477; 9781450345477 | 9781450345477 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Bauer, Ulrich; Di Fabio, Barbara; Landi, Claudia ( 2016 ) - An Edit Distance for Reeb Graphs - Eurographics Workshop on 3D Object Retrieval - The Eurographics Association ) [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

Cerri, Andrea; Landi, Claudia ( 2016 ) - Hausdorff Stability of Persistence Spaces - FOUNDATIONS OF COMPUTATIONAL MATHEMATICS - n. volume 16 - pp. da 343 a 367 ISSN: 1615-3375 [Articolo in rivista (262) - Articolo su rivista]
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.

Di Fabio, Barbara; Landi, Claudia ( 2016 ) - The Edit Distance for Reeb Graphs of Surfaces - DISCRETE & COMPUTATIONAL GEOMETRY - n. volume 55 - pp. da 423 a 461 ISSN: 0179-5376 [Articolo in rivista (262) - Articolo su rivista]
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.

Cavazza, Niccolò; Ferri, Massimo; Landi, Claudia ( 2015 ) - Estimating multidimensional persistent homology through a finite sampling - INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS - n. volume 25 - pp. da 187 a 205 ISSN: 0218-1959 [Articolo in rivista (262) - Articolo su rivista]
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.

Cagliari, F.; Di Fabio, B.; Landi, C. ( 2015 ) - The natural pseudo-distance as a quotient pseudo-metric, and applications - FORUM MATHEMATICUM - n. volume 27 - pp. da 1729 a 1742 ISSN: 0933-7741 [Articolo in rivista (262) - Articolo su rivista]
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.

Grasselli, Luigi; Landi, Claudia; Barani, Angiolina ( 2014 ) - Algebra lineare e geometria [Altro (298) - Altro]
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.

B. Di Fabio; C. Landi ( 2014 ) - Stable shape comparison of surfaces via Reeb graphs - Discrete Geometry for Computer Imagery - Springer International Cham CHE) - n. volume 8668 - pp. da 202 a 213 ISBN: 9783319099545 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

A. Cerri; B. Di Fabio; M. Ferri; P. Frosini; C. Landi ( 2013 ) - Betti numbers in multidimensional persistent homology are stable functions - MATHEMATICAL METHODS IN THE APPLIED SCIENCES - n. volume 36 - pp. da 1543 a 1557 ISSN: 0170-4214 [Articolo in rivista (262) - Articolo su rivista]
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.

N. Cavazza; M. Ethier; P. Frosini;T. Kaczynski; C. Landi ( 2013 ) - Comparison of Persistent Homologies for Vector Functions: from continuous to discrete and back - COMPUTERS & MATHEMATICS WITH APPLICATIONS - n. volume 66 - pp. da 560 a 573 ISSN: 0898-1221 [Articolo in rivista (262) - Articolo su rivista]
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.

P. Frosini; C. Landi ( 2013 ) - Persistent Betti numbers for a noise tolerant shape-based approach to image retrieval - PATTERN RECOGNITION LETTERS - n. volume 34 - pp. da 863 a 872 ISSN: 0167-8655 [Articolo in rivista (262) - Articolo su rivista]
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.

Andrea Cerri; Claudia Landi ( 2013 ) - The Persistence Space in Multidimensional Persistent Homology - Lecture Notes in Computer Science - Discrete Geometry for Computer Imagery - Springer Berlin Heidelberg Berlin Heidelberg DEU) - n. volume 7749 - pp. da 180 a 191 ISBN: 9783642370663; 9783642370670 | 9783642370670 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

A. Cerri; B. Di Fabio; M. Ferri; P. Frosini; C. Landi ( 2012 ) - Applied and Computational Algebraic Topology Advanced School 2012 (ACAT 2012) [Altro (298) - Altro]
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.

M. Ferri; P. Frosini; C. Landi; A. Cerri; B. Di Fabio ( 2012 ) - Computational Topology in Image Context - Springer Heidelberg DEU) - pp. da 1 a 167 ISBN: 9783642302374 [Curatela (284) - Curatela]
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.

C. Landi ( 2012 ) - Persistence for shape comparison - Applications of Combinatorial Topology to Computer Science - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing Saarbrücken/Wadern DEU) - DAGSTUHL REPORTS - n. volume 2 Issue 3 - pp. da 50 a 66 ISSN: 2192-5283 [Abstract in rivista (266) - Abstract in Rivista]
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.

F. Cagliari; M. Ferri; L. Gualandri; C. Landi ( 2012 ) - Persistence Modules, Shape Description, and Completeness - Proc. CTIC 2012, 4th International Workshop on Computational Topology in Image Contex - LECTURE NOTES IN COMPUTER SCIENCE - n. volume 7309 - pp. da 148 a 156 ISBN: 978-3-642-30237-4 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

B. Di Fabio; C. Landi ( 2012 ) - Persistent Homology and Partial Similarity of Shapes - PATTERN RECOGNITION LETTERS - n. volume 33 - pp. da 1445 a 1450 ISSN: 0167-8655 [Articolo in rivista (262) - Articolo su rivista]
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.

B. Di Fabio; C.Landi ( 2012 ) - Reeb graphs of curves are stable under function perturbations - MATHEMATICAL METHODS IN THE APPLIED SCIENCES - n. volume 35 - pp. da 1456 a 1471 ISSN: 0170-4214 [Articolo in rivista (262) - Articolo su rivista]
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.

B. Di Fabio; C. Landi ( 2012 ) - Stability of Reeb Graphs of Closed Curves - Proc. GETCO, Workshop on Geometric and Topological Methods in Computer Science - ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE - n. volume 283 - pp. da 71 a 76 ISSN: 1571-0661 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

M. Ferri; P. Frosini; C. Landi; A. Cerri; B. Di Fabio; N. Cavazza ( 2012 ) - 4th International Workshop on Computational Topology in Image Context (CTIC 2012) [Altro (298) - Altro]
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.

A. Cerri; P. Frosini; W. G. Kropatsch; C. Landi ( 2011 ) - A Global Method for Reducing Multidimensional Size Graphs - Graph-Based Representations in Pattern Recognition - LECTURE NOTES IN COMPUTER SCIENCE - n. volume 6658 - pp. da 1 a 11 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

B. Di Fabio; C. Landi ( 2011 ) - A Mayer–Vietoris Formula for Persistent Homology with an Application to Shape Recognition in the Presence of Occlusions - FOUNDATIONS OF COMPUTATIONAL MATHEMATICS - n. volume 11 - pp. da 499 a 527 ISSN: 1615-3375 [Articolo in rivista (262) - Articolo su rivista]
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.

F. Cagliari; C. Landi ( 2011 ) - Finiteness of rank invariants of multidimensional persistent homology groups - APPLIED MATHEMATICS LETTERS - n. volume 24 - pp. da 516 a 518 ISSN: 0893-9659 [Articolo in rivista (262) - Articolo su rivista]
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.

P. Frosini; C. Landi ( 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 - APPLIED MATHEMATICS LETTERS - n. volume 24 - pp. da 1654 a 1657 ISSN: 0893-9659 [Articolo in rivista (262) - Articolo su rivista]
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.

P. Frosini; C. Landi ( 2011 ) - Persistent Betti Numbers for a Noise Tolerant Shape-Based Approach to Image Retrieval - Computer Analysis of Images and Patterns: : 14TH INTERNATIONAL CONFERENCE, CAIP 2011, PT I - SPRINGER-VERLAG BERLIN, HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY ) - n. volume 6854 - pp. da 294 a 301 ISBN: 978-3-642-23671-6 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

M. Ferri; P. Frosini; C. Landi ( 2011 ) - Stable Shape Comparison by Persistent Homology - ATTI DEL SEMINARIO MATEMATICO E FISICO DEL'UNIVERSITÀ DI MODENA E REGGIO EMILIA - n. volume 58 - pp. da 143 a 162 ISSN: 1825-1269 [Articolo in rivista (262) - Articolo su rivista]
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.

P. Frosini; C. Landi ( 2011 ) - Uniqueness of models in persistent homology: the case of curves - INVERSE PROBLEMS - n. volume 27 [Articolo in rivista (262) - Articolo su rivista]
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.

P. Bandieri; M.R. Casali; A. Cattabriga; P. Cristofori; P. Frosini;L. Grasselli; C. Landi; M. Mulazzani ( 2010 ) - “Computational and Geometric Topology” - A conference in honour of Massimo Ferri and Carlo Gagliardi on their 60-th birthday. [Altro (298) - Altro]
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)

N. Cavazza; M. Ferri; C. Landi ( 2010 ) - Estimating multidimensional persistent homology through a finite sampling - AMS Acta, Università di Bologna ) [Altro (298) - Working paper]
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.

M. d’Amico; P. Frosini; C. Landi ( 2010 ) - Natural pseudo-distance and optimal matching between reduced size functions - ACTA APPLICANDAE MATHEMATICAE - n. volume 109 - pp. da 527 a 554 ISSN: 1572-9036 [Articolo in rivista (262) - Articolo su rivista]
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.

C. Landi ( 2010 ) - Persistent homology and partial matching of shapes - IMAGEN-A - n. volume 1 - pp. da 13 a 16 ISSN: 1885-4508 [Abstract in rivista (266) - Abstract in Rivista]
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.

B. Di Fabio; C. Landi; F. Medri ( 2009 ) - Recognition of Occluded Shapes Using Size Functions - Image Analysis and Processing – ICIAP 2009 - LECTURE NOTES IN COMPUTER SCIENCE - n. volume 5716 - pp. da 642 a 651 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

P. FROSINI; C. LANDI ( 2009 ) - Reparametrization invariant norms - TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY - n. volume 361 - pp. da 407 a 452 ISSN: 0002-9947 [Articolo in rivista (262) - Articolo su rivista]
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.

BIASOTTI S; DE FLORIANI L; FALCIDIENO B; FROSINI P; GIORGI D; C. LANDI; PAPALEO L; SPAGNOLO M ( 2008 ) - Describing shapes by geometrical- topological properties of real functions - ACM COMPUTING SURVEYS - n. volume 40 - pp. da 1 a 87 ISSN: 0360-0300 [Articolo in rivista (262) - Articolo su rivista]
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.

S. Biasotti; A. Cerri; P. Frosini; D. Giorgi; C. Landi ( 2008 ) - Multidimensional size functions for shape comparison - JOURNAL OF MATHEMATICAL IMAGING AND VISION - n. volume 32 - pp. da 161 a 179 ISSN: 0924-9907 [Articolo in rivista (262) - Articolo su rivista]
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.

A. CERRI; P. FROSINI; C. LANDI ( 2006 ) - A global reduction method for multidimensional size graphs - ELECTRONIC NOTES IN DISCRETE MATHEMATICS - n. volume 26 - pp. da 21 a 28 ISSN: 1571-0653 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

M. Ferri; P. Frosini; C. Landi; B. Di Fabio; A. Cerri ( 2006 ) - Metodi Geometrici nelle Applicazioni e nell'Industria (MeGAI'06) [Altro (298) - Altro]
Abstract

L'obiettivo di MeGAI'06 è far emergere le non poche applicazioni dei metodi geometrici nelle applicazioni e nell'industria

d'Amico M; Frosini P; Landi C ( 2006 ) - Using matching distance in size theory: A survey - INTERNATIONAL JOURNAL OF IMAGING SYSTEMS AND TECHNOLOGY - n. volume 16 - pp. da 154 a 161 ISSN: 0899-9457 [Articolo in rivista (262) - Articolo su rivista]
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.

A. Barani; L. Grasselli; C. Landi ( 2005 ) - Algebra lineare e geometria [Altro (298) - Altro]
Abstract

Quiz ed esercizi commentati e risolti

P. Frosini; C. Landi ( 2003 ) - Intrinsic harmonicity of Morse functions - MATHEMATIKA - n. volume 50 - pp. da 167 a 170 ISSN: 0025-5793 [Articolo in rivista (262) - Articolo su rivista]
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.

C. Landi; P. Frosini ( 2002 ) - Size functions as complete invariants for image recognition - Vision Geometry XI - PROCEEDINGS OF SPIE, THE INTERNATIONAL SOCIETY FOR OPTICAL ENGINEERING - n. volume 4794 - pp. da 101 a 109 ISBN: 9780819445612 ISSN: 0277-786X [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

F. Cagliari; C. Landi; L. Grasselli ( 2001 ) - Presentations of Morse homology for studying shape of manifolds - Dipartimento di Scienze e Metodi dell'Ingegneria, Università di Modena e Reggio Emilia ) [Altro (298) - Working paper]
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.

P. Frosini; C. Landi ( 2001 ) - Size functions and formal series - APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING - n. volume 12 - pp. da 327 a 349 ISSN: 0938-1279 [Articolo in rivista (262) - Articolo su rivista]
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.

C. LANDI ( 2000 ) - Cohomology rings of Artin groups - Roma : Accademia nazionale dei Lincei Zürich : EMS Publishing House ) - ATTI DELLA ACCADEMIA NAZIONALE DEI LINCEI. RENDICONTI LINCEI. MATEMATICA E APPLICAZIONI - n. volume 11 - pp. da 41 a 65 ISSN: 1720-0768 [Articolo in rivista (262) - Articolo su rivista]
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.

C. Landi; P. Frosini ( 1999 ) - Algebraic representation of size functions - Pattern Recognition and Image Understanding, 5th open German-Russian workshop - Infix Sankt Augustin DEU) - pp. da 41 a 46 ISBN: 9783896010162 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

P. DONATINI; P. FROSINI; C. LANDI ( 1999 ) - Deformation energy for size functions - LECTURE NOTES IN COMPUTER SCIENCE - n. volume 1654 - pp. da 44 a 53 ISSN: 0302-9743 [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

P. FROSINI; C. LANDI ( 1999 ) - Size theory as a topological tool for computer vision - Maik Nauka / Interperiodica:Profsoyuznaya 90, Moscow 117864 Russia:011 7 095 3360266, Fax: 011 7 095 3360666 ) - PATTERN RECOGNITION AND IMAGE ANALYSIS - n. volume 9 - pp. da 596 a 603 ISSN: 1054-6618 [Articolo in rivista (262) - Articolo su rivista]
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.

C. Landi; P. Frosini ( 1997 ) - New pseudo-distances for the size function space - Vision Geometry VI - PROCEEDINGS OF SPIE, THE INTERNATIONAL SOCIETY FOR OPTICAL ENGINEERING - n. volume 3168 - pp. da 52 a 60 ISBN: 9780819425904 ISSN: 0277-786X [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.

P. FROSINI; C. LANDI ( 1997 ) - Size functions and morphological transformations - Kluwer Academic Publishers:Journals Department, PO Box 322, 3300 AH Dordrecht Netherlands:011 31 78 6576050, EMAIL: frontoffice@wkap.nl, kluweronline@wkap.nl, INTERNET: http://www.kluwerlaw.com, Fax: 011 31 78 6576254 ) - ACTA APPLICANDAE MATHEMATICAE - n. volume 49 - pp. da 85 a 104 ISSN: 0167-8019 [Articolo in rivista (262) - Articolo su rivista]
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.

C. Landi; P. Frosini ( 1996 ) - Connections between size functions and morphological transformations - Vision Systems: New Image Processing Techniques - PROCEEDINGS OF SPIE, THE INTERNATIONAL SOCIETY FOR OPTICAL ENGINEERING - n. volume 2785 - pp. da 24 a 32 ISBN: 9780819421715 ISSN: 0277-786X [Contributo in Atti di convegno (273) - Relazione in Atti di Convegno]
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.