38 #ifndef PCL_SEGMENTATION_IMPL_RANDOM_WALKER_HPP 39 #define PCL_SEGMENTATION_IMPL_RANDOM_WALKER_HPP 41 #include <boost/bimap.hpp> 43 #include <Eigen/Sparse> 48 namespace segmentation
64 template <
class Graph,
class EdgeWeightMap,
class VertexColorMap>
70 typedef typename boost::property_traits<VertexColorMap>::value_type
Color;
71 typedef typename boost::property_traits<EdgeWeightMap>::value_type
Weight;
78 typedef typename boost::property_map<Graph, boost::vertex_index_t>::type
VertexIndexMap;
81 typedef Eigen::Matrix<Weight, Eigen::Dynamic, Eigen::Dynamic>
Matrix;
82 typedef Eigen::Matrix<Weight, Eigen::Dynamic, 1>
Vector;
84 RandomWalker (Graph& g, EdgeWeightMap weights, VertexColorMap colors)
105 using namespace boost;
107 for (tie (ei, e_end) = edges (
g_); ei != e_end; ++ei)
118 using namespace boost;
120 typedef Eigen::Triplet<float> T;
121 typedef std::vector<T> Triplets;
126 for (tie (vi, v_end) = vertices (
g_); vi != v_end; ++vi)
140 L_triplets.push_back (T (current_row, current_row,
degree_map_[*vi]));
143 for (tie (ei, e_end) = out_edges (*vi,
g_); ei != e_end; ++ei)
161 B_triplets.push_back (T (current_row, column, w));
169 L_triplets.push_back (T (current_row,
L_vertex_bimap.right.at (tgt), -w));
177 L.resize (num_equations, num_equations);
178 B.resize (num_equations, num_colors);
179 if (L_triplets.size ())
180 L.setFromTriplets(L_triplets.begin(), L_triplets.end());
181 if (B_triplets.size ())
182 B.setFromTriplets(B_triplets.begin(), B_triplets.end());
187 X.resize (
L.rows (),
B.cols ());
190 if (
L.rows () == 0 ||
B.cols () == 0)
193 Eigen::SimplicialCholesky<SparseMatrix, Eigen::Lower> cg;
195 bool succeeded =
true;
196 for (
int i = 0; i <
B.cols (); ++i)
199 X.col (i) = cg.solve (b);
200 if (cg.info () != Eigen::Success)
211 using namespace boost;
213 for (
int i = 0; i <
X.rows (); ++i)
216 X.row (i).maxCoeff (&max_column);
226 using namespace boost;
227 potentials = Matrix::Zero (num_vertices (
g_),
colors_.size ());
229 for (
int i = 0; i <
X.rows (); ++i)
232 for (
size_t i = 0; i <
seeds_.size (); ++i)
239 color_to_column_map.clear ();
240 for (
int i = 0; i < potentials.cols (); ++i)
244 template <
typename T>
static inline size_t 247 if (bimap.right.count (value) != 0)
249 return bimap.right.at (value);
253 size_t s = bimap.size ();
254 bimap.insert (
typename boost::bimap<size_t, T>::value_type (s, value));
282 template <
class Graph>
bool 286 boost::get (boost::edge_weight, graph),
287 boost::get (boost::vertex_color, graph));
290 template <
class Graph,
class EdgeWeightMap,
class VertexColorMap>
bool 292 EdgeWeightMap weights,
293 VertexColorMap colors)
295 using namespace boost;
297 typedef typename graph_traits<Graph>::edge_descriptor
EdgeDescriptor;
300 BOOST_CONCEPT_ASSERT ((VertexListGraphConcept<Graph>));
301 BOOST_CONCEPT_ASSERT ((EdgeListGraphConcept<Graph>));
302 BOOST_CONCEPT_ASSERT ((IncidenceGraphConcept<Graph>));
303 BOOST_CONCEPT_ASSERT ((ReadablePropertyMapConcept<EdgeWeightMap, EdgeDescriptor>));
304 BOOST_CONCEPT_ASSERT ((ReadWritePropertyMapConcept<VertexColorMap, VertexDescriptor>));
312 rw (graph, weights, colors);
313 return rw.segment ();
316 template <
class Graph,
class EdgeWeightMap,
class VertexColorMap>
bool 318 EdgeWeightMap weights,
319 VertexColorMap colors,
320 Eigen::Matrix<
typename boost::property_traits<EdgeWeightMap>::value_type, Eigen::Dynamic, Eigen::Dynamic>& potentials,
321 std::map<
typename boost::property_traits<VertexColorMap>::value_type,
size_t>& colors_to_columns_map)
323 using namespace boost;
325 typedef typename graph_traits<Graph>::edge_descriptor
EdgeDescriptor;
328 BOOST_CONCEPT_ASSERT ((VertexListGraphConcept<Graph>));
329 BOOST_CONCEPT_ASSERT ((EdgeListGraphConcept<Graph>));
330 BOOST_CONCEPT_ASSERT ((IncidenceGraphConcept<Graph>));
331 BOOST_CONCEPT_ASSERT ((ReadablePropertyMapConcept<EdgeWeightMap, EdgeDescriptor>));
332 BOOST_CONCEPT_ASSERT ((ReadWritePropertyMapConcept<VertexColorMap, VertexDescriptor>));
340 rw (graph, weights, colors);
341 bool result = rw.segment ();
342 rw.getPotentials (potentials, colors_to_columns_map);
boost::property_traits< VertexColorMap >::value_type Color
Eigen::Matrix< Weight, Eigen::Dynamic, Eigen::Dynamic > Matrix
Multilabel graph segmentation using random walks.
This file defines compatibility wrappers for low level I/O functions.
boost::iterator_property_map< typename std::vector< Weight >::iterator, VertexIndexMap > VertexDegreeMap
EdgeWeightMap weight_map_
RandomWalker(Graph &g, EdgeWeightMap weights, VertexColorMap colors)
VertexColorMap color_map_
GraphTraits::vertex_iterator VertexIterator
boost::bimap< size_t, Color > B_color_bimap
VertexDegreeMap degree_map_
static size_t insertInBimap(boost::bimap< size_t, T > &bimap, T value)
Eigen::Matrix< Weight, Eigen::Dynamic, 1 > Vector
std::vector< Weight > degree_storage_
GraphTraits::vertex_descriptor VertexDescriptor
bool randomWalker(Graph &graph)
Multilabel graph segmentation using random walks.
GraphTraits::out_edge_iterator OutEdgeIterator
std::set< Color > colors_
boost::graph_traits< Graph > GraphTraits
std::vector< VertexDescriptor > seeds_
boost::property_map< Graph, boost::vertex_index_t >::type VertexIndexMap
void computeVertexDegrees()
GraphTraits::edge_iterator EdgeIterator
VertexIndexMap index_map_
boost::property_traits< EdgeWeightMap >::value_type Weight
GraphTraits::edge_descriptor EdgeDescriptor
Eigen::SparseMatrix< Weight > SparseMatrix
void getPotentials(Matrix &potentials, std::map< Color, size_t > &color_to_column_map)
boost::bimap< size_t, VertexDescriptor > L_vertex_bimap