List of all members | Classes | Public Types | Public Member Functions
EdgeWeightComputer< GraphT > Class Template Reference

This class computes edge weights for a given point cloud graph. More...

#include <VisionX/libraries/PointCloudGraph/edge_weight_computer.h>

Public Types

enum  NormalizationType { NORMALIZATION_NONE, NORMALIZATION_GLOBAL, NORMALIZATION_LOCAL }
 Different normalization types that could be applied to a term. More...
 
typedef pcl::graph::point_cloud_graph_traits< GraphT >::point_type PointT
 
typedef boost::shared_ptr< EdgeWeightComputer > Ptr
 
enum  SmallWeightPolicy { SMALL_WEIGHT_IGNORE, SMALL_WEIGHT_COERCE_TO_THRESHOLD, SMALL_WEIGHT_REMOVE_EDGE }
 Policy which controls what happens to edges with small weights (i.e. More...
 
typedef boost::function< float(float, float)> TermBalancingFunction
 

Public Member Functions

template<typename TermT >
void addTerm (float influence, float convex_influence_multiplier=1.0, NormalizationType normalization=NORMALIZATION_NONE)
 Add a term to the edge weighting function. More...
 
template<typename TermT >
void addTerm (float influence, NormalizationType normalization)
 Add a term to the edge weighting function. More...
 
void compute (GraphT &graph)
 Compute weights for the edges in a given graph. More...
 
template<typename EdgeWeightMap >
void compute (GraphT &graph, EdgeWeightMap weights)
 Compute weights for the edges in a given graph. More...
 
 EdgeWeightComputer ()
 Construct a weight computer with default settings. More...
 
void setSmallWeightPolicy (SmallWeightPolicy policy)
 Set the policy for edges with small (below threshold) weights. More...
 
void setSmallWeightThreshold (float threshold)
 Set the threshold for edge weights. More...
 
void setTermBalancingFunction (TermBalancingFunction func)
 Set the function used to balance the contributions of the terms. More...
 

Detailed Description

template<typename GraphT>
class pcl::graph::EdgeWeightComputer< GraphT >

This class computes edge weights for a given point cloud graph.

The compute() function interates over graph edges and calculates their weights based on the data contained in their end vertices. The general form of the weighting function used in calculation is fixed, however the user is provided with a means to customize it.

For a pair of vertices $v_i$ and $v_j$ connected by an edge, the weight is computed as a product of $k$ independent terms:

\[ w_{ij} = Term_1\left(v_i,v_j\right) \cdot \dots \cdot Term_k\left(v_i,v_j\right) \]

Each term has the following form:

\[ Term\left(v_i,v_j\right) = \phi\left(\frac{d\left(v_i,v_j\right)} {\bar{d}\left(v_i,v_j\right)}, \sigma\right) \]

$\phi\left(\cdot,\cdot\right)$ is a balancing function. Its first argument is a value calculated from the vertex data, and the second argument controls the influence of the term. An example of a balancing function is Gaussian:

\[ \phi\left(x,\sigma\right) = \exp{\left\{-\frac{x}{\sigma}\right\}} \]

The value that is fed to the balancing function is calculated based on the data in the vertices; it consists of a distance between vertices $d\left(v_i,v_j\right)$ (in numerator) and a normalization term $\bar{d}\left(v_i,v_j\right)$ (in denominator). The former is called "distance" because typically it is indeed a distance function, such as Euclidean distance between 3D points, or angular distance between point normals. The normalization term is needed to account for the cases when the distance has a significant global variation over the graph.

Predefined terms

A few commonly used terms are predefined; they are presented below using the following notation. Given a point cloud graph vertex $v_i$, $p_i$ denotes the 3D coordinates of the associated point, $n_i$ denotes the normal orientation of the associated point, ${rgb}_i$ is a vector consisting of R, G, and B components of the color of the associated point, and $c_i$ denotes the curvature of the associated point.

  • XYZ term (Euclidean distance between points)

    $d_{xyz}(v_i,v_j) = ||p_i-p_j||^2$

  • Normal term (angular distance between normals)

    $d_{normal}(v_i,v_j) = \frac{||n_i-n_j||^2}{2}$

  • Curvature term (product of point curvatures)

    $d_{curvature}(v_i,v_j) = c_i \cdot c_j$

  • RGB term (Euclidean distance in RGB space)

    $d_{xyz}(v_i,v_j) = ||rgb_i-rgb_j||^2$

Normalization

Three types of normalization (defined by the NormalizationType enum) are available:

  • No normalization

    No normalization, the term is left as is.

  • Global normalization

    Normalize term by the average value of the corresponding distance over all edges in the graph.

  • Local normalization

    Normalize term by the average value of the corresponding distance over all edges incident to the end points of the edge.

Small weight policies

After the edge weights were computed, there is an optional step where the weights or the edge set of the graph may be modified to ensure that there are no edges with weights that are "too small". This is useful e.g. if the further processing involves solving linear systems based on adjacency matrix of the graph. Leaving smallish weights might lead to numerical problems in that case.

The threshold is controlled by the setSmallWeightThreshold() function. The policies are defined by the SmallWeightPolicy enum and may be set using setSmallWeightPolicy() function.

Usage

The following code snippet demonstrates a typical usage of the EdgeWeightComputer class:

using namespace pcl::graph;
// Typedef a point cloud graph with internal edge weight map
typedef point_cloud_graph<pcl::PointXYZRGB,
boost::vecS,
boost::undirectedS,
boost::property<boost::edge_weight_t, float>
boost::listS> Graph;
// Create a graph
Graph graph;
// Add vertices and edges
// ...
// Create edge weight computer
EdgeWeightComputer<Graph> computer;
// Add XYZ term with 1.0 influence
computer.addTerm<terms::XYZ> (1.0f);
// Add Normal term with 2.0 influence and a discounting multiplier
// for convex edges
computer.addTerm<terms::Normal> (1.0f, 2.0f);
// Add RGB term with 1.0 influence and local normalization
computer.addTerm<terms::RGB> (1.0f, EdgeWeightComputer<Graph>::NORMALIZATION_LOCAL);
// Compute edge weights;
computer.compute (graph);
Author
Sergey Alexandrov

Definition at line 196 of file edge_weight_computer.h.

Member Typedef Documentation

◆ PointT

typedef pcl::graph::point_cloud_graph_traits<GraphT>::point_type PointT

Definition at line 203 of file edge_weight_computer.h.

◆ Ptr

typedef boost::shared_ptr<EdgeWeightComputer> Ptr

Definition at line 205 of file edge_weight_computer.h.

◆ TermBalancingFunction

typedef boost::function<float (float, float)> TermBalancingFunction

Definition at line 204 of file edge_weight_computer.h.

Member Enumeration Documentation

◆ NormalizationType

enum NormalizationType

Different normalization types that could be applied to a term.

Enumerator
NORMALIZATION_NONE 

No normalization.

NORMALIZATION_GLOBAL 

Global normalization.

NORMALIZATION_LOCAL 

Local normalization.

Definition at line 208 of file edge_weight_computer.h.

◆ SmallWeightPolicy

enum SmallWeightPolicy

Policy which controls what happens to edges with small weights (i.e.

below user-specified threshold).

Enumerator
SMALL_WEIGHT_IGNORE 

Do nothing, leave the weights and edges as is.

SMALL_WEIGHT_COERCE_TO_THRESHOLD 

Coerce the weight to the threshold.

This guarantees that there are no edges in the graph with weight below threshold, and at the same time does not modify the edge set of the graph.

SMALL_WEIGHT_REMOVE_EDGE 

Remove edges with weights below threshold.

This guarantees that there are no edges in the graph with weight below threshold, but may modify the edge set of the graph.

Definition at line 220 of file edge_weight_computer.h.

Constructor & Destructor Documentation

◆ EdgeWeightComputer()

EdgeWeightComputer ( )
inline

Construct a weight computer with default settings.

By default the small weight threshold is set to zero, and the edges with small weights are ignored. The default term balancing function is Gaussian.

Definition at line 239 of file edge_weight_computer.h.

Member Function Documentation

◆ addTerm() [1/2]

void addTerm ( float  influence,
float  convex_influence_multiplier = 1.0,
NormalizationType  normalization = NORMALIZATION_NONE 
)
inline

Add a term to the edge weighting function.

Parameters
[in]influence$\sigma$ that will be passed to the balancing function
[in]convex_influence_multiplieran influence multiplier that will be applied if the edge is convex (default: 1.0, i.e. no diffirence between concave and convex edges).
[in]normalizationnormalization type for the term (default: NORMALIZATION_NONE, i.e. no normalization).

Definition at line 286 of file edge_weight_computer.h.

◆ addTerm() [2/2]

void addTerm ( float  influence,
NormalizationType  normalization 
)
inline

Add a term to the edge weighting function.

This is an overloaded function provided for convenience. See the documentation for addTerm().

Definition at line 299 of file edge_weight_computer.h.

◆ compute() [1/2]

void compute ( GraphT &  graph)
inline

Compute weights for the edges in a given graph.

This function interates over graph edges and calculates their weights based on the data contained in their end vertices. See class documentation for more information.

This version stores computed weights in internal property map.

Parameters
[in]grapha point cloud graph

Definition at line 269 of file edge_weight_computer.h.

◆ compute() [2/2]

void compute ( GraphT &  graph,
EdgeWeightMap  weights 
)

Compute weights for the edges in a given graph.

This function iterates over graph edges and calculates their weights based on the data contained in their end vertices. See class documentation for more information.

This version stores computed weights in external property map.

Parameters
[in]grapha point cloud graph
[in]weightsan external edge weight property map

Definition at line 112 of file edge_weight_computer.hpp.

+ Here is the call graph for this function:

◆ setSmallWeightPolicy()

void setSmallWeightPolicy ( SmallWeightPolicy  policy)
inline

Set the policy for edges with small (below threshold) weights.

Definition at line 308 of file edge_weight_computer.h.

◆ setSmallWeightThreshold()

void setSmallWeightThreshold ( float  threshold)
inline

Set the threshold for edge weights.

Definition at line 315 of file edge_weight_computer.h.

◆ setTermBalancingFunction()

void setTermBalancingFunction ( TermBalancingFunction  func)
inline

Set the function used to balance the contributions of the terms.

Definition at line 322 of file edge_weight_computer.h.

The documentation for this class was generated from the following files:
pcl::graph::EdgeWeightComputer
This class computes edge weights for a given point cloud graph.
Definition: edge_weight_computer.h:196
pcl::graph::EdgeWeightComputer::addTerm
void addTerm(float influence, float convex_influence_multiplier=1.0, NormalizationType normalization=NORMALIZATION_NONE)
Add a term to the edge weighting function.
Definition: edge_weight_computer.h:286
pcl::graph::terms::XYZ
Squared Euclidean distance between points.
Definition: edge_weight_computer_terms.h:57
pcl::graph::terms::RGB
Squared Euclidean distance in RGB space.
Definition: edge_weight_computer_terms.h:124
pcl::graph
Definition: common.h:45
pcl::graph::terms::Normal
Angular distance between normals.
Definition: edge_weight_computer_terms.h:80
armarx::Graph
boost::subgraph< CloudGraph > Graph
Definition: Common.h:54
pcl::graph::point_cloud_graph
Definition: point_cloud_graph.h:302
pcl::graph::EdgeWeightComputer::compute
void compute(GraphT &graph, EdgeWeightMap weights)
Compute weights for the edges in a given graph.
Definition: edge_weight_computer.hpp:112