Point Cloud Library (PCL)  1.12.0
random_walker.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2012-, Open Perception, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  */
37 
38 #pragma once
39 
40 #include <boost/graph/adjacency_list.hpp>
41 #include <boost/graph/graph_concepts.hpp>
42 #include <boost/concept/assert.hpp>
43 
44 #include <Eigen/Core> // for Matrix
45 
46 namespace pcl
47 {
48 
49  namespace segmentation
50  {
51 
52  /** \brief Multilabel graph segmentation using random walks.
53  *
54  * This is an implementation of the algorithm described in "Random Walks
55  * for Image Segmentation" by Leo Grady.
56  *
57  * Given a weighted undirected graph and a small number of user-defined
58  * labels this algorithm analytically determines the probability that a
59  * random walker starting at each unlabeled vertex will first reach one
60  * of the prelabeled vertices. The unlabeled vertices are then assigned
61  * to the label for which the greatest probability is calculated.
62  *
63  * The input is a BGL graph, a property map that associates a weight to
64  * each edge of the graph, and a property map that contains initial
65  * vertex colors (the term "color" is used interchangeably with "label").
66  *
67  * \note The colors of unlabeled vertices should be set to 0, the colors
68  * of labeled vetices could be any positive numbers.
69  *
70  * \note This is the responsibility of the user to make sure that every
71  * connected component of the graph has at least one colored vertex. If
72  * the user failed to do so, then the behavior of the algorithm is
73  * undefined, i.e. it may or may not succeed, and also may or may not
74  * report failure.
75  *
76  * The output of the algorithm (i.e. label assignment) is written back
77  * to the color map.
78  *
79  * \param[in] graph an undirected graph with internal edge weight and
80  * vertex color property maps
81  *
82  * Several overloads of randomWalker() function are provided for
83  * convenience.
84  *
85  * \sa randomWalker(Graph&, EdgeWeightMap, VertexColorMap)
86  * \sa randomWalker(Graph&, EdgeWeightMap, VertexColorMap, Eigen::Matrix <typename boost::property_traits<EdgeWeightMap>::value_type, Eigen::Dynamic, Eigen::Dynamic>&, std::map<typename boost::property_traits <VertexColorMap>::value_type, std::size_t>&)
87  *
88  * \author Sergey Alexandrov
89  * \ingroup segmentation
90  */
91 
92  template <class Graph> bool
93  randomWalker (Graph& graph);
94 
95  /** \brief Multilabel graph segmentation using random walks.
96  *
97  * This is an overloaded function provided for convenience. See the
98  * documentation for randomWalker().
99  *
100  * \param[in] graph an undirected graph
101  * \param[in] weights an external edge weight property map
102  * \param[in,out] colors an external vertex color property map
103  *
104  * \author Sergey Alexandrov
105  * \ingroup segmentation
106  */
107  template <class Graph, class EdgeWeightMap, class VertexColorMap> bool
108  randomWalker (Graph& graph,
109  EdgeWeightMap weights,
110  VertexColorMap colors);
111 
112  /** \brief Multilabel graph segmentation using random walks.
113  *
114  * This is an overloaded function provided for convenience. See the
115  * documentation for randomWalker().
116  *
117  * \param[in] graph an undirected graph
118  * \param[in] weights an external edge weight property map
119  * \param[in,out] colors an external vertex color property map
120  * \param[out] potentials a matrix with calculated probabilities,
121  * where rows correspond to vertices, and columns
122  * correspond to colors
123  * \param[out] colors_to_columns_map a mapping between colors and
124  * columns in \a potentials matrix
125  *
126  * \author Sergey Alexandrov
127  * \ingroup segmentation
128  */
129  template <class Graph, class EdgeWeightMap, class VertexColorMap> bool
130  randomWalker (Graph& graph,
131  EdgeWeightMap weights,
132  VertexColorMap colors,
133  Eigen::Matrix<typename boost::property_traits<EdgeWeightMap>::value_type, Eigen::Dynamic, Eigen::Dynamic>& potentials,
134  std::map<typename boost::property_traits<VertexColorMap>::value_type, std::size_t>& colors_to_columns_map);
135 
136  }
137 
138 }
139 
140 #include <pcl/segmentation/impl/random_walker.hpp>
bool randomWalker(Graph &graph)
Multilabel graph segmentation using random walks.