Frédéric Chazal

INRIA Saclay, Orsay

Topological data analysis using distance-based functions view abstract Frédéric Chazal
Topological data analysis using distance-based functions
Data often comes in the form of a point cloud sampled from an unknown subset of a metric space. The general goal of geometric inference is then to recover geometric and topological features of this shape from the approximating point cloud data. In recent years, it appeared that the study of distance functions allows to address many of these questions successfully under various sampling conditions of the unknown geometric structures. In this talk we provide a short introduction to these recent results.

Walter Kropatsch

PRIP, Vienna University of Technology

Representing and Manipulating Cyclic Paths in Continuous and Discrete Spaces view abstract Walter Kropatsch
Representing and Manipulating Cyclic Paths in Continuous and Discrete Spaces
A cyclic path in the plane correponds to a simple closed curve that separates the 'inside' from the 'outside' (Jordan's curve theorem). In the case of an image the inside may correspond to an object and the curve to its silhouette. But the curve may also surround a hole (or a set of holes) in the object in which case the curve corresponds to a generator of its homology group. Typically we observe the object by its projection into the image plane (or some well-behaved and bounded part of a surface). This embedding space can be considered continuous or discretely sampled. Accordingly there may be continuous and discrete representations of the curves having more or less strict properties: connectedness (no gaps), smoothness (no corners),... These properties can be propagated to properties of the discrete observations if we suppose sufficiently dense sampling. The most common discrete representations of embedding spaces are the square and triangular grid having two interpretations: it can be seen as a (huge) set of sensor positions or as partitioning the image plane into simply connected patches (square or triangular observation windows) through which the object and its silhouette is observed. Any continuous curve that does not pass through any vertex of the partition intersects two sides of the observation windows (or one side twice) and can be represented by a 'curve relation' between two sides of the window. The corresponding code describes the class of curves intersecting the same sides. The 1D corresponding representation is a chain code (i.e. Freeman) describing the sequence of patches in the order the curve crosses them. The advantage of the square grid is that there is only a small number of relative moves between adjacent windows (typically 4 or 8) but it has the drawback to be sensitive to small relative changes between the curve and the grid (e.g. a moving object). A further disadvantage of the regular square grid is that a small part of the object requiring high resolution needs a huge amount of storage for correct reconstruction although most other parts do not need such high resolution. Multiple and adaptive resolutions overcome this bottleneck of single resolution, this has been explored in the curve pyramid. Its extension to irregular grids have been used to efficiently describe and process huge technical drawings. It could be shown that the flexibility of using patches of different sizes can create hierarchies that preserve certain topological properties of the object, its curve relations and its embedding space. In this hierarchy, homology generators shrink with the reduction of the sampling space while local constraints prevent elimination of connected components and holes until a non-contractible top level is reached which has the same homology structure as the bottom while being reduced to its minimal size (Gonzalez-Diaz). To overcome rotation sensitivity differential chain codes (DCC) have been proposed, e.g. the RULI chain code is equivalent to the curve relations where R stands for right turn, U for U-turn, I continues striaght ahead and L turns left. A variant of this DCC operates on triangular grids: entering a triangle through one side has one corner 'opposite' its entry. It can be passed on the right (R) or on the left (L) or return (U). We explore consequences on such RUL codes on a triangular grid when triangular edges are contracted or removed. These are the only operations used in dual graph contraction to build the topology preserving hierarchy. Since this process also preserves the maximum degree of the dual graph a triangulation remains a triangulation and the RUL chain can be represented at the lower resolution again as a RUL chain. This concept connects these DCC with formal grammars and allows the embedding space to deform while the representation remains the same.

papers indexed by the Odysci Academic Search Engine soon after the conference