Subsampling

Enumerations
enum	: std::size_t { Gudhi::subsampling::random_starting_point = std::size_t(-1) }

Functions
template<typename Distance, typename Point_range, typename PointOutputIterator, typename DistanceOutputIterator = Null_output_iterator>
void	Gudhi::subsampling::choose_n_farthest_points (Distance dist, Point_range const &input_pts, std::size_t final_size, std::size_t starting_point, PointOutputIterator output_it, DistanceOutputIterator dist_it={})
	Subsample by an iterative, greedy strategy.
template<typename Distance, typename Point_range, typename PointOutputIterator, typename DistanceOutputIterator = Null_output_iterator>
void	Gudhi::subsampling::choose_n_farthest_points_metric (Distance dist_, Point_range const &input_pts, std::size_t final_size, std::size_t starting_point, PointOutputIterator output_it, DistanceOutputIterator dist_it={})
	Subsample by an iterative, greedy strategy.
template<typename Point_container, typename OutputIterator>
void	Gudhi::subsampling::pick_n_random_points (Point_container const &points, std::size_t final_size, OutputIterator output_it)
	Subsample a point set by picking random vertices.
template<typename Kernel, typename Point_range, typename OutputIterator>
void	Gudhi::subsampling::sparsify_point_set (const Kernel &k, Point_range const &input_pts, typename Kernel::FT min_squared_dist, OutputIterator output_it)
	Outputs a subset of the input points so that the squared distance between any two points is greater than min_squared_dist.

Detailed Description

Author

Clément Jamin, Siargey Kachanovich, Marc Glisse

Introduction

This Gudhi component offers methods to subsample a set of points.

Example: sparsify_point_set

This example outputs a subset of the input points so that the squared distance between any two points is greater than or equal to 0.4.

#include <gudhi/sparsify_point_set.h>
 
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
 
#include <iostream>
#include <vector>
#include <iterator>
 
int main(void) {
  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
  typedef typename K::Point_d Point_d;
 
  CGAL::Random rd;
 
  std::vector<Point_d> points;
  for (int i = 0; i < 500; ++i)
    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
  K k;
  std::vector<Point_d> results;
  Gudhi::subsampling::sparsify_point_set(k, points, 0.4, std::back_inserter(results));
  std::clog << "Before sparsification: " << points.size() << " points.\n";
  std::clog << "After  sparsification: " << results.size() << " points.\n";
 
  return 0;
}

Example: choose_n_farthest_points

This example outputs a subset of 100 points obtained by González algorithm, starting with a random point, and greedily adding the point farthest from those already picked.

#include <gudhi/choose_n_farthest_points.h>
 
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
 
#include <iostream>
#include <vector>
#include <iterator>
 
int main(void) {
  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
  typedef typename K::Point_d Point_d;
 
  CGAL::Random rd;
 
  std::vector<Point_d> points;
  for (int i = 0; i < 500; ++i)
    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
  K k;
  std::vector<Point_d> results;
  Gudhi::subsampling::choose_n_farthest_points(k.squared_distance_d_object(), points, 100,
                                               Gudhi::subsampling::random_starting_point,
                                               std::back_inserter(results));
  std::clog << "Before sparsification: " << points.size() << " points.\n";
  std::clog << "After  sparsification: " << results.size() << " points.\n";
 
  return 0;
}

There is an alternative version choose_n_farthest_points_metric() with the same syntax, which can be faster in many cases.

Example: pick_n_random_points

This example outputs a subset of 100 points picked randomly.

#include <gudhi/pick_n_random_points.h>
 
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
 
#include <iostream>
#include <vector>
#include <iterator>
 
int main(void) {
  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
  typedef typename K::Point_d Point_d;
 
  CGAL::Random rd;
 
  std::vector<Point_d> points;
  for (int i = 0; i < 500; ++i)
    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
  K k;
  std::vector<Point_d> results;
  Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(results));
  std::clog << "Before sparsification: " << points.size() << " points.\n";
  std::clog << "After  sparsification: " << results.size() << " points.\n";
 
  return 0;
}

Enumeration Type Documentation

anonymous enum

anonymous enum : std::size_t

Enumerator
random_starting_point	Argument for choose_n_farthest_points to indicate that the starting point should be picked randomly.

Function Documentation

choose_n_farthest_points()

template<typename Distance, typename Point_range, typename PointOutputIterator, typename DistanceOutputIterator = Null_output_iterator>

void Gudhi::subsampling::choose_n_farthest_points	(	Distance	dist,
		Point_range const &	input_pts,
		std::size_t	final_size,
		std::size_t	starting_point,
		PointOutputIterator	output_it,
		DistanceOutputIterator	dist_it = {} )

Subsample by an iterative, greedy strategy.

The algorithm starts with the landmark starting point or, if starting point==random_starting_point, with a landmark chosen randomly from the point set. At each iteration, it finds the point farthest from the set of current landmarks, outputs this distance, and promotes the point to landmark. It stops after finding final_size landmarks.

Template Parameters

Distance	must provide an operator() that takes 2 points (value type of the range) and returns their distance (or some more general proximity measure) as a double.
Point_range	Random access range of points.
PointOutputIterator	Output iterator whose value type is the point type.
DistanceOutputIterator	Output iterator for distances.

Parameters

[in]	dist	Distance function.
[in]	input_pts	The input points.
[in]	final_size	The size of the subsample to compute (reduced to the number of input points if final_size is larger).
[in]	starting_point	The seed in the farthest point algorithm.
[out]	output_it	The output iterator where landmarks are written.
[out]	dist_it	The optional output iterator where the distance from a landmark to the previous landmarks is written.

Warning

Older versions of this function took a CGAL kernel as argument. Users need to replace k with k.squared_distance_d_object() in the first argument of every call to choose_n_farthest_points.

Examples

example_choose_n_farthest_points.cpp, example_custom_distance.cpp, example_strong_witness_complex_off.cpp, example_witness_complex_off.cpp, example_witness_complex_sphere.cpp, strong_witness_persistence.cpp, and weak_witness_persistence.cpp.

choose_n_farthest_points_metric()

template<typename Distance, typename Point_range, typename PointOutputIterator, typename DistanceOutputIterator = Null_output_iterator>

void Gudhi::subsampling::choose_n_farthest_points_metric	(	Distance	dist_,
		Point_range const &	input_pts,
		std::size_t	final_size,
		std::size_t	starting_point,
		PointOutputIterator	output_it,
		DistanceOutputIterator	dist_it = {} )

Subsample by an iterative, greedy strategy.

This computes the same thing as choose_n_farthest_points(), but relies on the triangle inequality to reduce the amount of computation when the doubling dimension and spread are small. In the worst case, this can be much slower than choose_n_farthest_points() though. See [chubet_et_al:LIPIcs.SoCG.2023.64] and its associated video for details about this algorithm.

Template Parameters

Distance	must provide an operator() that takes 2 points (value type of the range) and returns their distance as a double. It must be a true metric (not squared Euclidean), the algorithm relies on the triangle inequality.
Point_range	Random access range of points.
PointOutputIterator	Output iterator whose value type is the point type.
DistanceOutputIterator	Output iterator for distances.

Parameters

[in]	dist_	Distance function.
[in]	input_pts	The input points.
[in]	final_size	The size of the subsample to compute (reduced to the number of input points if final_size is larger).
[in]	starting_point	The seed in the farthest point algorithm.
[out]	output_it	The output iterator where landmarks are written.
[out]	dist_it	The optional output iterator where the distance from a landmark to the previous landmarks is written.

pick_n_random_points()

template<typename Point_container, typename OutputIterator>

void Gudhi::subsampling::pick_n_random_points	(	Point_container const &	points,
		std::size_t	final_size,
		OutputIterator	output_it )

Subsample a point set by picking random vertices.

It chooses final_size distinct points from a random access range points and outputs them to the output iterator output_it. Point_container::iterator should be ValueSwappable and RandomAccessIterator.

Examples

example_pick_n_random_points.cpp.

sparsify_point_set()

template<typename Kernel, typename Point_range, typename OutputIterator>

void Gudhi::subsampling::sparsify_point_set	(	const Kernel &	k,
		Point_range const &	input_pts,
		typename Kernel::FT	min_squared_dist,
		OutputIterator	output_it )

Outputs a subset of the input points so that the squared distance between any two points is greater than min_squared_dist.

Template Parameters

Kernel	must be a model of the SearchTraits concept, such as the CGAL::Epick_d class, which can be static if you know the ambiant dimension at compile-time, or dynamic if you don't.
Point_range	Range whose value type is Kernel::Point_d. It must provide random-access via operator[] and the points should be stored contiguously in memory.
OutputIterator	Output iterator whose value type is Kernel::Point_d.

Parameters

[in]	k	A kernel object.
[in]	input_pts	Const reference to the input points.
[in]	min_squared_dist	Minimum squared distance separating the output points.
[out]	output_it	The output iterator.

Examples

example_sparsify_point_set.cpp, and example_with_perturb.cpp.