1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
/* This file is part of the Gudhi Library. The Gudhi library
* (Geometric Understanding in Higher Dimensions) is a generic C++
* library for computational topology.
*
* Author(s): Mathieu Carriere
*
* Copyright (C) 2017 Inria
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef DOC_COVER_COMPLEX_INTRO_COVER_COMPLEX_H_
#define DOC_COVER_COMPLEX_INTRO_COVER_COMPLEX_H_
namespace Gudhi {
namespace cover_complex {
/** \defgroup cover_complex Cover complex
*
* \author Mathieu Carrière
*
* @{
*
* Visualizations of the simplicial complexes can be done with either
* neato (from <a target="_blank" href="http://www.graphviz.org/">graphviz</a>),
* <a target="_blank" href="http://www.geomview.org/">geomview</a>,
* <a target="_blank" href="https://github.com/MLWave/kepler-mapper">KeplerMapper</a>.
* Input point clouds are assumed to be
* <a target="_blank" href="http://www.geomview.org/docs/html/OFF.html">OFF files</a>.
*
* \section covers Covers
*
* Nerves and Graph Induced Complexes require a cover C of the input point cloud P,
* that is a set of subsets of P whose union is P itself.
* Very often, this cover is obtained from the preimage of a family of intervals covering
* the image of some scalar-valued function f defined on P. This family is parameterized
* by its resolution, which can be either the number or the length of the intervals,
* and its gain, which is the overlap percentage between consecutive intervals (ordered by their first values).
*
* \section nerves Nerves
*
* \subsection nervedefinition Nerve definition
*
* Assume you are given a cover C of your point cloud P. Then, the Nerve of this cover
* is the simplicial complex that has one k-simplex per k-fold intersection of cover elements.
* See also <a target="_blank" href="https://en.wikipedia.org/wiki/Nerve_of_a_covering"> Wikipedia </a>.
*
* \image html "nerve.png" "Nerve of a double torus"
*
* \subsection nerveexample Example
*
* This example builds the Nerve of a point cloud sampled on a 3D human shape (human.off).
* The cover C comes from the preimages of intervals (10 intervals with gain 0.3)
* covering the height function (coordinate 2),
* which are then refined into their connected components using the triangulation of the .OFF file.
*
* \include Nerve_GIC/Nerve.cpp
*
* When launching:
*
* \code $> ./Nerve ../../data/points/human.off 2 10 0.3 -v
* \endcode
*
* the program output is:
*
* \include Nerve_GIC/Nerve.txt
*
* The program also writes a file ../../data/points/human_sc.txt. The first three lines in this file are the location
* of the input point cloud and the function used to compute the cover.
* The fourth line contains the number of vertices nv and edges ne of the Nerve.
* The next nv lines represent the vertices. Each line contains the vertex ID,
* the number of data points it contains, and their average color function value.
* Finally, the next ne lines represent the edges, characterized by the ID of their vertices.
*
* Using KeplerMapper, one can obtain the following visualization:
*
* \image html "nervevisu.jpg" "Visualization with KeplerMapper"
*
* \section gic Graph Induced Complexes (GIC)
*
* \subsection gicdefinition GIC definition
*
* Again, assume you are given a cover C of your point cloud P. Moreover, assume
* you are also given a graph G built on top of P. Then, for any clique in G
* whose nodes all belong to different elements of C, the GIC includes a corresponding
* simplex, whose dimension is the number of nodes in the clique minus one.
* See \cite Dey13 for more details.
*
* \image html "GIC.jpg" "GIC of a point cloud."
*
* \subsection gicexamplevor Example with cover from Voronoï
*
* This example builds the GIC of a point cloud sampled on a 3D human shape (human.off).
* We randomly subsampled 100 points in the point cloud, which act as seeds of
* a geodesic Voronoï diagram. Each cell of the diagram is then an element of C.
* The graph G (used to compute both the geodesics for Voronoï and the GIC)
* comes from the triangulation of the human shape. Note that the resulting simplicial complex is in dimension 3
* in this example.
*
* \include Nerve_GIC/VoronoiGIC.cpp
*
* When launching:
*
* \code $> ./VoronoiGIC ../../data/points/human.off 700 -v
* \endcode
*
* the program outputs SC.off. Using e.g.
*
* \code $> geomview ../../data/points/human_sc.off
* \endcode
*
* one can obtain the following visualization:
*
* \image html "gicvoronoivisu.jpg" "Visualization with Geomview"
*
* \subsection functionalGICdefinition Functional GIC
*
* If one restricts to the cliques in G whose nodes all belong to preimages of consecutive
* intervals (assuming the cover of the height function is minimal, i.e. no more than
* two intervals can intersect at a time), the GIC is of dimension one, i.e. a graph.
* We call this graph the functional GIC. See \cite Carriere16 for more details.
*
* \subsection functionalGICexample Example
*
* Functional GIC comes with automatic selection of the Rips threshold,
* the resolution and the gain of the function cover. See \cite Carriere17c for more details. In this example,
* we compute the functional GIC of a Klein bottle embedded in R^5,
* where the graph G comes from a Rips complex with automatic threshold,
* and the cover C comes from the preimages of intervals covering the first coordinate,
* with automatic resolution and gain. Note that automatic threshold, resolution and gain
* can be computed as well for the Nerve.
*
* \include Nerve_GIC/CoordGIC.cpp
*
* When launching:
*
* \code $> ./CoordGIC ../../data/points/KleinBottle5D.off 0 -v
* \endcode
*
* the program outputs SC.dot. Using e.g.
*
* \code $> neato SC.dot -Tpdf -o SC.pdf
* \endcode
*
* one can obtain the following visualization:
*
* \image html "coordGICvisu2.jpg" "Visualization with Neato"
*
* where nodes are colored by the filter function values and, for each node, the first number is its ID
* and the second is the number of data points that its contain.
*
* We also provide an example on a set of 72 pictures taken around the same object (lucky_cat.off).
* The function is now the first eigenfunction given by PCA, whose values
* are written in a file (lucky_cat_PCA1). Threshold, resolution and gain are automatically selected as before.
*
* \include Nerve_GIC/FuncGIC.cpp
*
* When launching:
*
* \code $> ./FuncGIC ../../data/points/COIL_database/lucky_cat.off ../../data/points/COIL_database/lucky_cat_PCA1 -v
* \endcode
*
* the program outputs again SC.dot which gives the following visualization after using neato:
*
* \image html "funcGICvisu.jpg" "Visualization with neato"
*
*/
/** @} */ // end defgroup cover_complex
} // namespace cover_complex
} // namespace Gudhi
#endif // DOC_COVER_COMPLEX_INTRO_COVER_COMPLEX_H_
|
