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);