Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::OptimalTransportMap Class Referenceabstract

Computes semi-discrete optimal transport maps. More...

#include <exploragram/optimal_transport/optimal_transport.h>

Inheritance diagram for GEO::OptimalTransportMap:
GEO::OptimalTransportMap2d GEO::OptimalTransportMap3d GEO::OptimalTransportMapOnSurface

Classes

class  Callback
 Base class for the callbacks executed for each intersection between a Laguerre cell and a simplex of the background mesh. More...
 

Public Member Functions

 OptimalTransportMap (index_t dimension, Mesh *mesh, const std::string &delaunay="default", bool BRIO=false)
 OptimalTransportMap constructor. More...
 
virtual ~OptimalTransportMap ()
 OptimalTransportMap destructor.
 
index_t dimension () const
 Gets the dimension. More...
 
Meshmesh ()
 Gets the mesh. More...
 
void set_Newton (bool x)
 Sets whether Newton algorithm should be used. More...
 
void set_points (index_t nb_points, const double *points, index_t stride=0)
 Sets the points that define the target distribution. More...
 
void set_air_particles (index_t nb_air_particles, const double *air_particles, index_t stride, double air_fraction)
 Sets the air particles that define the volume occupied by the free space. More...
 
double air_fraction () const
 Gets the air fraction. More...
 
index_t nb_air_particles () const
 Gets the number of air particles. More...
 
void set_nu (index_t i, double nu)
 Sets the desired mass at one of the Diracs. More...
 
void set_Laguerre_centroids (double *x)
 Specifies a user vector where the centroids of the Laguerre cells will be stored after computing transport. More...
 
void set_epsilon (double eps)
 Sets the maximum error. More...
 
void set_linsolve_epsilon (double eps)
 Sets the tolerance for linear solve. More...
 
void set_linsolve_maxiter (index_t maxiter)
 Sets the maximum number of iterations for linear solve. More...
 
void set_linesearch_maxiter (index_t maxiter)
 Sets the maximum number of line search iterations. More...
 
void set_linesearch_init_iter (index_t init_iter)
 Sets the number of steplength reductions to be done at the first iteration. More...
 
void set_regularization (double eps_reg)
 Sets the weight of the regularization term. More...
 
void set_linear_solver (OTLinearSolver solver)
 Specifies whether a direct solver should be used. More...
 
void optimize (index_t max_iterations)
 Computes the weights that realize the optimal transport map between the source mesh and the target pointset. More...
 
void set_verbose (bool x)
 Enable/disable messages during optimization. More...
 
void optimize_full_Newton (index_t max_iterations, index_t n=0)
 Computes the weights that realize the optimal transport map between the source mesh and the target pointset. More...
 
void optimize_level (index_t b, index_t e, index_t max_iterations)
 Optimizes one level of the multilevel algorithm. More...
 
void optimize_levels (const vector< index_t > &levels, index_t max_iterations)
 Multi-level optimization. More...
 
index_t nb_points () const
 Gets the number of points. More...
 
const double * point_ptr (index_t i) const
 Gets a point. More...
 
double weight (index_t i) const
 Gets weight of a point. More...
 
void set_weight (index_t i, double val)
 Sets a weight of a point. More...
 
double potential (index_t i) const
 Gets the d+1-th coordinate of the embedding for a point. More...
 
RestrictedVoronoiDiagramRVD ()
 Gets the restricted Voronoi diagram. More...
 
void set_save_RVD_iter (bool x, bool show_RVD_seed=false, bool last_iter_only=false)
 Sets whether the restricted Voronoi diagram at each iteration should be saved. More...
 
virtual void get_RVD (Mesh &M)=0
 Computes a mesh with the restricted Voronoi diagram. More...
 
virtual void compute_Laguerre_centroids (double *centroids)=0
 Computes the centroids of the Laguerre cells. More...
 
void update_sparsity_pattern ()
 Updates the sparsity pattern of the Hessian right after a new Laguerre diagram was computed.
 
void new_linear_system (index_t n, double *x)
 Starts a new linear system. More...
 
void add_ij_coefficient (index_t i, index_t j, double a)
 Adds a coefficient to the matrix of the system. More...
 
void add_i_right_hand_side (index_t i, double a)
 Adds a coefficient to the right hand side. More...
 
void solve_linear_system ()
 Solves a linear system. More...
 
void set_initial_weight (index_t i, double w)
 Sets the initial value of the weight associated with one of the points. More...
 
double total_mass () const
 Gets the total mass of the domain. More...
 
void compute_P1_Laplacian (const double *weights, NLMatrix Laplacian, double *measures)
 Computes the P1 Laplacian of the Laguerre cells. More...
 

Static Public Member Functions

static void funcgrad_CB (index_t n, double *x, double &f, double *g)
 Callback for the numerical solver. More...
 
static void newiteration_CB (index_t n, const double *x, double f, const double *g, double gnorm)
 Callback for the numerical solver. More...
 

Protected Member Functions

double nu (index_t p) const
 Gets the mass of the Dirac associated with point p. More...
 
virtual void newiteration ()
 Callback for the numerical solver.
 
void save_RVD (index_t id)
 Saves the RVD at each iteration if specified on command line (just for debugging/ explaining the algorithm). More...
 
void funcgrad (index_t n, double *w, double &f, double *g)
 Computes the objective function and its gradient. More...
 
virtual void call_callback_on_RVD ()=0
 Calls the callback for each intersection between a Laguerre cell and a simplex of the background mesh.
 
void eval_func_grad_Hessian (index_t n, const double *w, double &f, double *g)
 Computes the objective function, its gradient and its Hessian. More...
 
double gradient_threshold (index_t n) const
 Computes the stopping criterion of the solver. More...
 

Protected Attributes

index_t dimension_
 
index_t dimp1_
 dimension_ + 1
 
Meshmesh_
 
Delaunay_var delaunay_
 
RestrictedVoronoiDiagram_var RVD_
 
vector< double > points_dimp1_
 
vector< double > weights_
 
double total_mass_
 
double constant_nu_
 Value of one of the Diracs if cte.
 
vector< double > nu_
 Value of all the Diracs.
 
double epsilon_
 Acceptable relative deviation for the measure of a cell.
 
index_t current_call_iter_
 
Callbackcallback_
 
std::string last_stats_
 
bool pretty_log_
 
index_t level_
 
bool save_RVD_iter_
 
bool save_RVD_last_iter_
 
bool show_RVD_seed_
 
index_t current_iter_
 
bool newton_
 
bool verbose_
 
double epsilon_regularization_
 Add a regularization term to remove translational degree of freedom for the weights.
 
index_t nbZ_
 Number of empty cells in last iteration.
 
double g_norm_
 Norm of the gradient in last iteration.
 
double measure_of_smallest_cell_
 Measure of the smallest Laguerre cell.
 
bool w_did_not_change_
 True if w did not change, thus there is no need to recompute the power diagram.
 
double * Laguerre_centroids_
 If user-specified, then Laguerre centroids are output here.
 
double linsolve_epsilon_
 maximum value of \( \| Ax - b \| / \| b \| \)
 
index_t linsolve_maxiter_
 maximum number of iterations for linear solve
 
index_t linesearch_maxiter_
 maximum number of steplength divisions
 
index_t linesearch_init_iter_
 starting number of steplength divisions
 
OTLinearSolver linear_solver_
 one of OT_PRECG, OT_SUPERLU, OT_CHOLMOD.
 
const double * air_particles_
 if set, pointer to the air particles.
 
index_t nb_air_particles_
 if non-zero, number of air particles.
 
index_t air_particles_stride_
 Number of doubles between two consecutive air particles in air_particles_.
 
double air_fraction_
 The fraction of the total mass occupied by air.
 
bool clip_by_balls_
 Enabled if air fraction is specified without any air particles.
 
bool user_H_g_
 True if class is just used by user to compute Hessian and gradient instead of doing full computation.
 
NLMatrix user_H_
 User-defined Hessian matrix.
 

Static Protected Attributes

static OptimalTransportMapinstance_
 

Detailed Description

Computes semi-discrete optimal transport maps.

Computes an optimal transport map between two distributions. The first distribution is represented by a simplicial mesh. The second distribution is a sum of Diracs. The algorithm is described in the following references:

  • 3D algorithm: http://arxiv.org/abs/1409.1279
  • Earlier 2D version by Quentin M\'erigot: Q. Merigot. A multiscale approach to optimal transport. Computer Graphics Forum 30 (5) 1583–1592, 2011 (Proc SGP 2011).
  • Earlier article on OT and power diagrams: F. Aurenhammer, F. Hoffmann, and B. Aronov. Minkowski-type theorems and least-squares clustering. Algorithmica, 20:61-76, 1998.

Definition at line 91 of file optimal_transport.h.

Constructor & Destructor Documentation

◆ OptimalTransportMap()

GEO::OptimalTransportMap::OptimalTransportMap ( index_t  dimension,
Mesh mesh,
const std::string &  delaunay = "default",
bool  BRIO = false 
)

OptimalTransportMap constructor.

Parameters
[in]meshthe source distribution, represented as a nd mesh.
[in]delaunayfactory name of the Delaunay triangulation.
[in]BRIOtrue if vertices are already ordered using BRIO

Member Function Documentation

◆ add_i_right_hand_side()

void GEO::OptimalTransportMap::add_i_right_hand_side ( index_t  i,
double  a 
)
inline

Adds a coefficient to the right hand side.

Parameters
[in]ithe index of the coefficient
[in]athe value to be added to the coefficient

Definition at line 493 of file optimal_transport.h.

◆ add_ij_coefficient()

void GEO::OptimalTransportMap::add_ij_coefficient ( index_t  i,
index_t  j,
double  a 
)
inline

Adds a coefficient to the matrix of the system.

Parameters
[in]i,jthe indices of the coefficient
[in]athe value to be added to the coefficient

Definition at line 477 of file optimal_transport.h.

◆ air_fraction()

double GEO::OptimalTransportMap::air_fraction ( ) const
inline

Gets the air fraction.

Returns
the air fraction previously specified by set_air_particles()

Definition at line 181 of file optimal_transport.h.

◆ compute_Laguerre_centroids()

virtual void GEO::OptimalTransportMap::compute_Laguerre_centroids ( double *  centroids)
pure virtual

Computes the centroids of the Laguerre cells.

Parameters
[out]centroidsa pointer to the dimension()*nb_points coordinates of the centroids.

Implemented in GEO::OptimalTransportMapOnSurface, GEO::OptimalTransportMap3d, and GEO::OptimalTransportMap2d.

◆ compute_P1_Laplacian()

void GEO::OptimalTransportMap::compute_P1_Laplacian ( const double *  weights,
NLMatrix  Laplacian,
double *  measures 
)

Computes the P1 Laplacian of the Laguerre cells.

Parameters
[in]Omegathe domain, either a surfacic or a volumetric mesh.
[in]weightsthe weights of the Laguerre diagram.
[out]LaplacianP1 Laplacian of the Laguerre diagram or nullptr if not needed.
[out]measuresoptional measures the measures of all Laguerre cells, or nullptr if not needed.

◆ dimension()

index_t GEO::OptimalTransportMap::dimension ( ) const
inline

Gets the dimension.

Returns
2 for 2d, 3 for 3d.

Definition at line 115 of file optimal_transport.h.

◆ eval_func_grad_Hessian()

void GEO::OptimalTransportMap::eval_func_grad_Hessian ( index_t  n,
const double *  w,
double &  f,
double *  g 
)
protected

Computes the objective function, its gradient and its Hessian.

Gradient and Hessian are used to solve a Newton step H p = -g

Parameters
[in]nnumber of variables
[in]wcurrent value of the variables
[out]fcurrent value of the objective function
[out]ggradient of the objective function

◆ funcgrad()

void GEO::OptimalTransportMap::funcgrad ( index_t  n,
double *  w,
double &  f,
double *  g 
)
protected

Computes the objective function and its gradient.

Parameters
[in]nnumber of variables
[in]wcurrent value of the variables
[out]fcurrent value of the objective function
[out]ggradient of the objective function

◆ funcgrad_CB()

static void GEO::OptimalTransportMap::funcgrad_CB ( index_t  n,
double *  x,
double &  f,
double *  g 
)
static

Callback for the numerical solver.

Evaluates the objective function and its gradient.

Parameters
[in]nnumber of variables
[in]xcurrent value of the variables
[out]fcurrent value of the objective function
[out]ggradient of the objective function

◆ get_RVD()

virtual void GEO::OptimalTransportMap::get_RVD ( Mesh M)
pure virtual

Computes a mesh with the restricted Voronoi diagram.

Parameters
[out]Ma reference to the computed restricted Voronoi diagram.

Implemented in GEO::OptimalTransportMapOnSurface, GEO::OptimalTransportMap3d, and GEO::OptimalTransportMap2d.

◆ gradient_threshold()

double GEO::OptimalTransportMap::gradient_threshold ( index_t  n) const
inlineprotected

Computes the stopping criterion of the solver.

The stopping criterion is determined from the user-specified epsilon, number of samples and target measure of a cell (constant_nu_).

Parameters
nnumber of samples
Returns
the gradient threshold
See also
set_epsilon()

Definition at line 602 of file optimal_transport.h.

◆ mesh()

Mesh& GEO::OptimalTransportMap::mesh ( )
inline

Gets the mesh.

Returns
a reference to the mesh

Definition at line 123 of file optimal_transport.h.

◆ nb_air_particles()

index_t GEO::OptimalTransportMap::nb_air_particles ( ) const
inline

Gets the number of air particles.

Returns
the air fraction previously specified by set_air_particles()

Definition at line 189 of file optimal_transport.h.

◆ nb_points()

index_t GEO::OptimalTransportMap::nb_points ( ) const
inline

Gets the number of points.

Returns
The number of points, that was previously defined by set_points()

Definition at line 345 of file optimal_transport.h.

◆ new_linear_system()

void GEO::OptimalTransportMap::new_linear_system ( index_t  n,
double *  x 
)

Starts a new linear system.

Parameters
[in]nthe dimension of the system
[in]xpointer to a contiguous array of n doubles, where the solution will be stored.

◆ newiteration_CB()

static void GEO::OptimalTransportMap::newiteration_CB ( index_t  n,
const double *  x,
double  f,
const double *  g,
double  gnorm 
)
static

Callback for the numerical solver.

Parameters
[in]nnumber of variables
[in]xcurrent value of the variables
[in]fcurrent value of the objective function
[in]ggradient of the objective function
[in]gnormnorm of the gradient of the objective function

◆ nu()

double GEO::OptimalTransportMap::nu ( index_t  p) const
inlineprotected

Gets the mass of the Dirac associated with point p.

Returns
the desired mass at point p.

Definition at line 545 of file optimal_transport.h.

◆ optimize()

void GEO::OptimalTransportMap::optimize ( index_t  max_iterations)

Computes the weights that realize the optimal transport map between the source mesh and the target pointset.

Parameters
[in]max_iterationsmaximum number of solver iterations.

◆ optimize_full_Newton()

void GEO::OptimalTransportMap::optimize_full_Newton ( index_t  max_iterations,
index_t  n = 0 
)

Computes the weights that realize the optimal transport map between the source mesh and the target pointset.

The algorithm is described in http://arxiv.org/abs/1603.05579 Kitawaga, Merigot, Thibert, A Newton Algorithm for semi-discrete OT.

Parameters
[in]max_iterationsmaximum number of solver iterations.
[in]nnumber of weights to optimize, used in hierarchical mode. If zero, optimizes all the weights.

◆ optimize_level()

void GEO::OptimalTransportMap::optimize_level ( index_t  b,
index_t  e,
index_t  max_iterations 
)

Optimizes one level of the multilevel algorithm.

The function supposes that the sequence [0,b) has been previously optimized. It is used to initialize the sequence [b,e). The whole sequence [0,e) is then optimized.

Parameters
[in]bindex fo the first point in the level
[in]eone position past the last index of the level
[in]max_iterationsmaximum number of iterations

◆ optimize_levels()

void GEO::OptimalTransportMap::optimize_levels ( const vector< index_t > &  levels,
index_t  max_iterations 
)

Multi-level optimization.

The points specified by set_points() need to have a hierarchical structure. They can be constructed by compute_hierarchical_sampling().

Parameters
[in]levelssample indices that correspond to level l are in the range levels[l] (included) ... levels[l+1] (excluded)
[in]max_iterationsmaximum number of iterations
See also
compute_hierarchical_sampling()

◆ point_ptr()

const double* GEO::OptimalTransportMap::point_ptr ( index_t  i) const
inline

Gets a point.

Parameters
[in]iindex of the point
Returns
a const pointer to the coordinates of the (dimension()+1)d point i

Definition at line 355 of file optimal_transport.h.

◆ potential()

double GEO::OptimalTransportMap::potential ( index_t  i) const
inline

Gets the d+1-th coordinate of the embedding for a point.

Parameters
[in]iindex of the point
Returns
the d+1-th coordinate that was computed for point i

Definition at line 383 of file optimal_transport.h.

◆ RVD()

RestrictedVoronoiDiagram* GEO::OptimalTransportMap::RVD ( )
inline

Gets the restricted Voronoi diagram.

Returns
a pointer to the restricted Voronoi diagram

Definition at line 415 of file optimal_transport.h.

◆ save_RVD()

void GEO::OptimalTransportMap::save_RVD ( index_t  id)
protected

Saves the RVD at each iteration if specified on command line (just for debugging/ explaining the algorithm).

Parameters
[in]idindex to be used for the file, that will be named RVD_id.meshb

◆ set_air_particles()

void GEO::OptimalTransportMap::set_air_particles ( index_t  nb_air_particles,
const double *  air_particles,
index_t  stride,
double  air_fraction 
)
inline

Sets the air particles that define the volume occupied by the free space.

If air particles are used, then set_air_particles() needs to be called before set_points().

Parameters
[in]nb_air_particlesnumber of air particles.
[in]air_particlesa pointer to the array of doubles with the coordinates of the air particles.
[in]stridenumber of doubles between two consecutive air particles in the array, or 0 if tightly packed.
[in]air_fractionthe fraction of the total mass occupied by air.

Definition at line 164 of file optimal_transport.h.

◆ set_epsilon()

void GEO::OptimalTransportMap::set_epsilon ( double  eps)
inline

Sets the maximum error.

Parameters
epsacceptable relative deviation for the measure of a Voronoi cell.

Definition at line 218 of file optimal_transport.h.

◆ set_initial_weight()

void GEO::OptimalTransportMap::set_initial_weight ( index_t  i,
double  w 
)
inline

Sets the initial value of the weight associated with one of the points.

Parameters
[in]iindex of the point, in 0..nb_points-1, where np_points corresponds to the parameter of set_points.
[in]wthe value of the weight.

Definition at line 513 of file optimal_transport.h.

◆ set_Laguerre_centroids()

void GEO::OptimalTransportMap::set_Laguerre_centroids ( double *  x)
inline

Specifies a user vector where the centroids of the Laguerre cells will be stored after computing transport.

Parameters
[out]xa vector of nb points * dimension() doubles.

Definition at line 209 of file optimal_transport.h.

◆ set_linear_solver()

void GEO::OptimalTransportMap::set_linear_solver ( OTLinearSolver  solver)
inline

Specifies whether a direct solver should be used.

Parameters
[in]solverone of OT_PRECG (default), OT_SUPERLU, OT_CHOLMOD.

The direct solvers (OT_SUPERLU, OT_CHOLMOD) are recommended only for surfacic data, since the sparse factors become not so sparse when volumetric meshes are considered.

Definition at line 281 of file optimal_transport.h.

◆ set_linesearch_init_iter()

void GEO::OptimalTransportMap::set_linesearch_init_iter ( index_t  init_iter)
inline

Sets the number of steplength reductions to be done at the first iteration.

Parameters
[in]init_iterthe number of steplength reductions to be apllied at the first iteration. If left 0, start with Newton step at each iteration, else do tentative steplength prediction.

Definition at line 258 of file optimal_transport.h.

◆ set_linesearch_maxiter()

void GEO::OptimalTransportMap::set_linesearch_maxiter ( index_t  maxiter)
inline

Sets the maximum number of line search iterations.

Parameters
[in]maxiterthe maximum number of step length reduction for line search.

Definition at line 246 of file optimal_transport.h.

◆ set_linsolve_epsilon()

void GEO::OptimalTransportMap::set_linsolve_epsilon ( double  eps)
inline

Sets the tolerance for linear solve.

Parameters
[in]epsthe maximum value of \( \| Ax - b \| / \| b \| \)b

Definition at line 228 of file optimal_transport.h.

◆ set_linsolve_maxiter()

void GEO::OptimalTransportMap::set_linsolve_maxiter ( index_t  maxiter)
inline

Sets the maximum number of iterations for linear solve.

Parameters
[in]maxiterthe maximum number of iterations.

Definition at line 237 of file optimal_transport.h.

◆ set_Newton()

void GEO::OptimalTransportMap::set_Newton ( bool  x)
inline

Sets whether Newton algorithm should be used.

It is (for now) incompatible with multilevel.

Parameters
[in]xif set, Newton algorithm is used instead of BFGS.

Definition at line 133 of file optimal_transport.h.

◆ set_nu()

void GEO::OptimalTransportMap::set_nu ( index_t  i,
double  nu 
)

Sets the desired mass at one of the Diracs.

If unspecified, then default value is total mass divided by number of point. Note that the sum of all specified masses should match the total mass.

Parameters
[in]ithe index of the dirac, in 0 .. nb_points-1
[in]nuthe desired mass at point i

◆ set_points()

void GEO::OptimalTransportMap::set_points ( index_t  nb_points,
const double *  points,
index_t  stride = 0 
)

Sets the points that define the target distribution.

If air particles are used, then set_air_particles() needs to be called before set_points().

Parameters
[in]nb_pointsnumber of points in the target distribution
[in]pointsan array of size nb_points * dimension() with the coordinates of the Diracs centers in the target distribution.
[in]stridenumber of doubles between two consecutive points. If 0 (default), then point coordinates are considered to be packed.

◆ set_regularization()

void GEO::OptimalTransportMap::set_regularization ( double  eps_reg)
inline

Sets the weight of the regularization term.

The regularization term (norm of the weight vector) cancels the translational degree of freedom of the weights.

Parameters
[in]eps_regthe weight of the regularization term. Use 0.0 for no regularization.

Definition at line 269 of file optimal_transport.h.

◆ set_save_RVD_iter()

void GEO::OptimalTransportMap::set_save_RVD_iter ( bool  x,
bool  show_RVD_seed = false,
bool  last_iter_only = false 
)
inline

Sets whether the restricted Voronoi diagram at each iteration should be saved.

If flag is set, then each iteration is saved in file "RVD_nnn.geogram".

Parameters
[in]xtrue if each iteration should be saved, false otherwise.
[in]show_RVD_seedif true, the seed associated with each restricted Voronoi cell is connected to it
[in]last_iter_onlyif true, only the last iteration is saved

Definition at line 431 of file optimal_transport.h.

◆ set_verbose()

void GEO::OptimalTransportMap::set_verbose ( bool  x)
inline

Enable/disable messages during optimization.

Parameters
[in]xtrue if messages should be displayed, false otherwise.

Definition at line 298 of file optimal_transport.h.

◆ set_weight()

void GEO::OptimalTransportMap::set_weight ( index_t  i,
double  val 
)
inline

Sets a weight of a point.

Parameters
[in]iindex of the point
[in]valnew value of the weight

Definition at line 374 of file optimal_transport.h.

◆ solve_linear_system()

void GEO::OptimalTransportMap::solve_linear_system ( )

Solves a linear system.

The solution is stored in the vector that was previously specified to new_linear_system().

◆ total_mass()

double GEO::OptimalTransportMap::total_mass ( ) const
inline

Gets the total mass of the domain.

Returns
the total mass.

Definition at line 521 of file optimal_transport.h.

◆ weight()

double GEO::OptimalTransportMap::weight ( index_t  i) const
inline

Gets weight of a point.

Parameters
[in]iindex of the point
Returns
the weight that was computed for point i

Definition at line 365 of file optimal_transport.h.


The documentation for this class was generated from the following file: