diff options
Diffstat (limited to 'ml/dlib/dlib/graph_cuts')
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts.h | 959 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h | 636 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/general_flow_graph.h | 172 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/general_potts_problem.h | 99 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/graph_labeler.h | 211 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/graph_labeler_abstract.h | 185 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/min_cut.h | 571 | ||||
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/min_cut_abstract.h | 476 |
8 files changed, 3309 insertions, 0 deletions
diff --git a/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts.h b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts.h new file mode 100644 index 000000000..f035442bf --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts.h @@ -0,0 +1,959 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_Hh_ +#define DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_Hh_ + +#include "find_max_factor_graph_potts_abstract.h" +#include "../matrix.h" +#include "min_cut.h" +#include "general_potts_problem.h" +#include "../algs.h" +#include "../graph_utils.h" +#include "../array2d.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + namespace impl + { + + template < + typename potts_problem, + typename T = void + > + class flows_container + { + /* + This object notionally represents a matrix of flow values. It's + overloaded to represent this matrix efficiently though. In this case + it represents the matrix using a sparse representation. + */ + + typedef typename potts_problem::value_type edge_type; + std::vector<std::vector<edge_type> > flows; + public: + + void setup( + const potts_problem& p + ) + { + flows.resize(p.number_of_nodes()); + for (unsigned long i = 0; i < flows.size(); ++i) + { + flows[i].resize(p.number_of_neighbors(i)); + } + } + + edge_type& operator() ( + const long r, + const long c + ) { return flows[r][c]; } + + const edge_type& operator() ( + const long r, + const long c + ) const { return flows[r][c]; } + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + class flows_container<potts_problem, + typename enable_if_c<potts_problem::max_number_of_neighbors!=0>::type> + { + /* + This object notionally represents a matrix of flow values. It's + overloaded to represent this matrix efficiently though. In this case + it represents the matrix using a dense representation. + + */ + typedef typename potts_problem::value_type edge_type; + const static unsigned long max_number_of_neighbors = potts_problem::max_number_of_neighbors; + matrix<edge_type,0,max_number_of_neighbors> flows; + public: + + void setup( + const potts_problem& p + ) + { + flows.set_size(p.number_of_nodes(), max_number_of_neighbors); + } + + edge_type& operator() ( + const long r, + const long c + ) { return flows(r,c); } + + const edge_type& operator() ( + const long r, + const long c + ) const { return flows(r,c); } + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + class potts_flow_graph + { + public: + typedef typename potts_problem::value_type edge_type; + private: + /*! + This is a utility class used by dlib::min_cut to convert a potts_problem + into the kind of flow graph expected by the min_cut object's main block + of code. + + Within this object, we will use the convention that one past + potts_problem::number_of_nodes() is the source node and two past is + the sink node. + !*/ + + potts_problem& g; + + // flows(i,j) == the flow from node id i to it's jth neighbor + flows_container<potts_problem> flows; + // source_flows(i,0) == flow from source to node i, + // source_flows(i,1) == flow from node i to source + matrix<edge_type,0,2> source_flows; + + // sink_flows(i,0) == flow from sink to node i, + // sink_flows(i,1) == flow from node i to sink + matrix<edge_type,0,2> sink_flows; + + node_label source_label, sink_label; + public: + + potts_flow_graph( + potts_problem& g_ + ) : g(g_) + { + flows.setup(g); + + source_flows.set_size(g.number_of_nodes(), 2); + sink_flows.set_size(g.number_of_nodes(), 2); + source_flows = 0; + sink_flows = 0; + + source_label = FREE_NODE; + sink_label = FREE_NODE; + + // setup flows based on factor potentials + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + const edge_type temp = g.factor_value(i); + if (temp < 0) + source_flows(i,0) = -temp; + else + sink_flows(i,1) = temp; + + for (unsigned long j = 0; j < g.number_of_neighbors(i); ++j) + { + flows(i,j) = g.factor_value_disagreement(i, g.get_neighbor(i,j)); + } + } + } + + class out_edge_iterator + { + friend class potts_flow_graph; + unsigned long idx; // base node idx + unsigned long cnt; // count over the neighbors of idx + public: + + out_edge_iterator( + ):idx(0),cnt(0){} + + out_edge_iterator( + unsigned long idx_, + unsigned long cnt_ + ):idx(idx_),cnt(cnt_) + {} + + bool operator!= ( + const out_edge_iterator& item + ) const { return cnt != item.cnt; } + + out_edge_iterator& operator++( + ) + { + ++cnt; + return *this; + } + }; + + class in_edge_iterator + { + friend class potts_flow_graph; + unsigned long idx; // base node idx + unsigned long cnt; // count over the neighbors of idx + public: + + in_edge_iterator( + ):idx(0),cnt(0) + {} + + + in_edge_iterator( + unsigned long idx_, + unsigned long cnt_ + ):idx(idx_),cnt(cnt_) + {} + + bool operator!= ( + const in_edge_iterator& item + ) const { return cnt != item.cnt; } + + in_edge_iterator& operator++( + ) + { + ++cnt; + return *this; + } + }; + + unsigned long number_of_nodes ( + ) const { return g.number_of_nodes() + 2; } + + out_edge_iterator out_begin( + const unsigned long& it + ) const { return out_edge_iterator(it, 0); } + + in_edge_iterator in_begin( + const unsigned long& it + ) const { return in_edge_iterator(it, 0); } + + out_edge_iterator out_end( + const unsigned long& it + ) const + { + if (it >= g.number_of_nodes()) + return out_edge_iterator(it, g.number_of_nodes()); + else + return out_edge_iterator(it, g.number_of_neighbors(it)+2); + } + + in_edge_iterator in_end( + const unsigned long& it + ) const + { + if (it >= g.number_of_nodes()) + return in_edge_iterator(it, g.number_of_nodes()); + else + return in_edge_iterator(it, g.number_of_neighbors(it)+2); + } + + + template <typename iterator_type> + unsigned long node_id ( + const iterator_type& it + ) const + { + // if this isn't an iterator over the source or sink nodes + if (it.idx < g.number_of_nodes()) + { + const unsigned long num = g.number_of_neighbors(it.idx); + if (it.cnt < num) + return g.get_neighbor(it.idx, it.cnt); + else if (it.cnt == num) + return g.number_of_nodes(); + else + return g.number_of_nodes()+1; + } + else + { + return it.cnt; + } + } + + + edge_type get_flow ( + const unsigned long& it1, + const unsigned long& it2 + ) const + { + if (it1 >= g.number_of_nodes()) + { + // if it1 is the source + if (it1 == g.number_of_nodes()) + { + return source_flows(it2,0); + } + else // if it1 is the sink + { + return sink_flows(it2,0); + } + } + else if (it2 >= g.number_of_nodes()) + { + // if it2 is the source + if (it2 == g.number_of_nodes()) + { + return source_flows(it1,1); + } + else // if it2 is the sink + { + return sink_flows(it1,1); + } + } + else + { + return flows(it1, g.get_neighbor_idx(it1, it2)); + } + + } + + edge_type get_flow ( + const out_edge_iterator& it + ) const + { + if (it.idx < g.number_of_nodes()) + { + const unsigned long num = g.number_of_neighbors(it.idx); + if (it.cnt < num) + return flows(it.idx, it.cnt); + else if (it.cnt == num) + return source_flows(it.idx,1); + else + return sink_flows(it.idx,1); + } + else + { + // if it.idx is the source + if (it.idx == g.number_of_nodes()) + { + return source_flows(it.cnt,0); + } + else // if it.idx is the sink + { + return sink_flows(it.cnt,0); + } + } + } + + edge_type get_flow ( + const in_edge_iterator& it + ) const + { + return get_flow(node_id(it), it.idx); + } + + void adjust_flow ( + const unsigned long& it1, + const unsigned long& it2, + const edge_type& value + ) + { + if (it1 >= g.number_of_nodes()) + { + // if it1 is the source + if (it1 == g.number_of_nodes()) + { + source_flows(it2,0) += value; + source_flows(it2,1) -= value; + } + else // if it1 is the sink + { + sink_flows(it2,0) += value; + sink_flows(it2,1) -= value; + } + } + else if (it2 >= g.number_of_nodes()) + { + // if it2 is the source + if (it2 == g.number_of_nodes()) + { + source_flows(it1,1) += value; + source_flows(it1,0) -= value; + } + else // if it2 is the sink + { + sink_flows(it1,1) += value; + sink_flows(it1,0) -= value; + } + } + else + { + flows(it1, g.get_neighbor_idx(it1, it2)) += value; + flows(it2, g.get_neighbor_idx(it2, it1)) -= value; + } + + } + + void set_label ( + const unsigned long& it, + node_label value + ) + { + if (it < g.number_of_nodes()) + g.set_label(it, value); + else if (it == g.number_of_nodes()) + source_label = value; + else + sink_label = value; + } + + node_label get_label ( + const unsigned long& it + ) const + { + if (it < g.number_of_nodes()) + return g.get_label(it); + if (it == g.number_of_nodes()) + return source_label; + else + return sink_label; + } + + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename label_image_type, + typename image_potts_model + > + class potts_grid_problem + { + label_image_type& label_img; + long nc; + long num_nodes; + unsigned char* labels; + const image_potts_model& model; + + public: + const static unsigned long max_number_of_neighbors = 4; + + potts_grid_problem ( + label_image_type& label_img_, + const image_potts_model& image_potts_model_ + ) : + label_img(label_img_), + model(image_potts_model_) + { + num_nodes = model.nr()*model.nc(); + nc = model.nc(); + labels = &label_img[0][0]; + } + + unsigned long number_of_nodes ( + ) const { return num_nodes; } + + unsigned long number_of_neighbors ( + unsigned long + ) const + { + return 4; + } + + unsigned long get_neighbor_idx ( + long node_id1, + long node_id2 + ) const + { + long diff = node_id2-node_id1; + if (diff > nc) + diff -= (long)number_of_nodes(); + else if (diff < -nc) + diff += (long)number_of_nodes(); + + if (diff == 1) + return 0; + else if (diff == -1) + return 1; + else if (diff == nc) + return 2; + else + return 3; + } + + unsigned long get_neighbor ( + long node_id, + long idx + ) const + { + switch(idx) + { + case 0: + { + long temp = node_id+1; + if (temp < (long)number_of_nodes()) + return temp; + else + return temp - (long)number_of_nodes(); + } + case 1: + { + long temp = node_id-1; + if (node_id >= 1) + return temp; + else + return temp + (long)number_of_nodes(); + } + case 2: + { + long temp = node_id+nc; + if (temp < (long)number_of_nodes()) + return temp; + else + return temp - (long)number_of_nodes(); + } + case 3: + { + long temp = node_id-nc; + if (node_id >= nc) + return temp; + else + return temp + (long)number_of_nodes(); + } + } + return 0; + } + + void set_label ( + const unsigned long& idx, + node_label value + ) + { + *(labels+idx) = value; + } + + node_label get_label ( + const unsigned long& idx + ) const + { + return *(labels+idx); + } + + typedef typename image_potts_model::value_type value_type; + + value_type factor_value (unsigned long idx) const + { + return model.factor_value(idx); + } + + value_type factor_value_disagreement (unsigned long idx1, unsigned long idx2) const + { + return model.factor_value_disagreement(idx1,idx2); + } + + }; + + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename potts_model + > + typename potts_model::value_type potts_model_score ( + const potts_model& prob + ) + { +#ifdef ENABLE_ASSERTS + for (unsigned long i = 0; i < prob.number_of_nodes(); ++i) + { + for (unsigned long jj = 0; jj < prob.number_of_neighbors(i); ++jj) + { + unsigned long j = prob.get_neighbor(i,jj); + DLIB_ASSERT(prob.factor_value_disagreement(i,j) >= 0, + "\t value_type potts_model_score(prob)" + << "\n\t Invalid inputs were given to this function." + << "\n\t i: " << i + << "\n\t j: " << j + << "\n\t prob.factor_value_disagreement(i,j): " << prob.factor_value_disagreement(i,j) + ); + DLIB_ASSERT(prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i), + "\t value_type potts_model_score(prob)" + << "\n\t Invalid inputs were given to this function." + << "\n\t i: " << i + << "\n\t j: " << j + << "\n\t prob.factor_value_disagreement(i,j): " << prob.factor_value_disagreement(i,j) + << "\n\t prob.factor_value_disagreement(j,i): " << prob.factor_value_disagreement(j,i) + ); + } + } +#endif + + typename potts_model::value_type score = 0; + for (unsigned long i = 0; i < prob.number_of_nodes(); ++i) + { + const bool label = (prob.get_label(i)!=0); + if (label) + score += prob.factor_value(i); + } + + for (unsigned long i = 0; i < prob.number_of_nodes(); ++i) + { + for (unsigned long n = 0; n < prob.number_of_neighbors(i); ++n) + { + const unsigned long idx2 = prob.get_neighbor(i,n); + const bool label_i = (prob.get_label(i)!=0); + const bool label_idx2 = (prob.get_label(idx2)!=0); + if (label_i != label_idx2 && i < idx2) + score -= prob.factor_value_disagreement(i, idx2); + } + } + + return score; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + typename graph_type::edge_type potts_model_score ( + const graph_type& g, + const std::vector<node_label>& labels + ) + { + DLIB_ASSERT(graph_contains_length_one_cycle(g) == false, + "\t edge_type potts_model_score(g,labels)" + << "\n\t Invalid inputs were given to this function." + ); + typedef typename graph_type::edge_type edge_type; + typedef typename graph_type::type type; + + // The edges and node's have to use the same type to represent factor weights! + COMPILE_TIME_ASSERT((is_same_type<edge_type, type>::value == true)); + +#ifdef ENABLE_ASSERTS + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + for (unsigned long jj = 0; jj < g.node(i).number_of_neighbors(); ++jj) + { + unsigned long j = g.node(i).neighbor(jj).index(); + DLIB_ASSERT(edge(g,i,j) >= 0, + "\t edge_type potts_model_score(g,labels)" + << "\n\t Invalid inputs were given to this function." + << "\n\t i: " << i + << "\n\t j: " << j + << "\n\t edge(g,i,j): " << edge(g,i,j) + ); + } + } +#endif + + typename graph_type::edge_type score = 0; + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + const bool label = (labels[i]!=0); + if (label) + score += g.node(i).data; + } + + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + for (unsigned long n = 0; n < g.node(i).number_of_neighbors(); ++n) + { + const unsigned long idx2 = g.node(i).neighbor(n).index(); + const bool label_i = (labels[i]!=0); + const bool label_idx2 = (labels[idx2]!=0); + if (label_i != label_idx2 && i < idx2) + score -= g.node(i).edge(n); + } + } + + return score; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + typename potts_grid_problem::value_type potts_model_score ( + const potts_grid_problem& prob, + const array2d<node_label,mem_manager>& labels + ) + { + DLIB_ASSERT(prob.nr() == labels.nr() && prob.nc() == labels.nc(), + "\t value_type potts_model_score(prob,labels)" + << "\n\t Invalid inputs were given to this function." + << "\n\t prob.nr(): " << labels.nr() + << "\n\t prob.nc(): " << labels.nc() + ); + typedef array2d<node_label,mem_manager> image_type; + // This const_cast is ok because the model object won't actually modify labels + dlib::impl::potts_grid_problem<image_type,potts_grid_problem> model(const_cast<image_type&>(labels),prob); + return potts_model_score(model); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_model + > + void find_max_factor_graph_potts ( + potts_model& prob + ) + { +#ifdef ENABLE_ASSERTS + for (unsigned long node_i = 0; node_i < prob.number_of_nodes(); ++node_i) + { + for (unsigned long jj = 0; jj < prob.number_of_neighbors(node_i); ++jj) + { + unsigned long node_j = prob.get_neighbor(node_i,jj); + DLIB_ASSERT(prob.get_neighbor_idx(node_j,node_i) < prob.number_of_neighbors(node_j), + "\t void find_max_factor_graph_potts(prob)" + << "\n\t The supplied potts problem defines an invalid graph." + << "\n\t node_i: " << node_i + << "\n\t node_j: " << node_j + << "\n\t prob.get_neighbor_idx(node_j,node_i): " << prob.get_neighbor_idx(node_j,node_i) + << "\n\t prob.number_of_neighbors(node_j): " << prob.number_of_neighbors(node_j) + ); + + DLIB_ASSERT(prob.get_neighbor_idx(node_i,prob.get_neighbor(node_i,jj)) == jj, + "\t void find_max_factor_graph_potts(prob)" + << "\n\t The get_neighbor_idx() and get_neighbor() functions must be inverses of each other." + << "\n\t node_i: " << node_i + << "\n\t jj: " << jj + << "\n\t prob.get_neighbor(node_i,jj): " << prob.get_neighbor(node_i,jj) + << "\n\t prob.get_neighbor_idx(node_i,prob.get_neighbor(node_i,jj)): " << prob.get_neighbor_idx(node_i,node_j) + ); + + DLIB_ASSERT(prob.get_neighbor(node_j,prob.get_neighbor_idx(node_j,node_i))==node_i, + "\t void find_max_factor_graph_potts(prob)" + << "\n\t The get_neighbor_idx() and get_neighbor() functions must be inverses of each other." + << "\n\t node_i: " << node_i + << "\n\t node_j: " << node_j + << "\n\t prob.get_neighbor_idx(node_j,node_i): " << prob.get_neighbor_idx(node_j,node_i) + << "\n\t prob.get_neighbor(node_j,prob.get_neighbor_idx(node_j,node_i)): " << prob.get_neighbor(node_j,prob.get_neighbor_idx(node_j,node_i)) + ); + + DLIB_ASSERT(prob.factor_value_disagreement(node_i,node_j) >= 0, + "\t void find_max_factor_graph_potts(prob)" + << "\n\t Invalid inputs were given to this function." + << "\n\t node_i: " << node_i + << "\n\t node_j: " << node_j + << "\n\t prob.factor_value_disagreement(node_i,node_j): " << prob.factor_value_disagreement(node_i,node_j) + ); + DLIB_ASSERT(prob.factor_value_disagreement(node_i,node_j) == prob.factor_value_disagreement(node_j,node_i), + "\t void find_max_factor_graph_potts(prob)" + << "\n\t Invalid inputs were given to this function." + << "\n\t node_i: " << node_i + << "\n\t node_j: " << node_j + << "\n\t prob.factor_value_disagreement(node_i,node_j): " << prob.factor_value_disagreement(node_i,node_j) + << "\n\t prob.factor_value_disagreement(node_j,node_i): " << prob.factor_value_disagreement(node_j,node_i) + ); + } + } +#endif + COMPILE_TIME_ASSERT(is_signed_type<typename potts_model::value_type>::value); + min_cut mc; + dlib::impl::potts_flow_graph<potts_model> pfg(prob); + mc(pfg, prob.number_of_nodes(), prob.number_of_nodes()+1); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + void find_max_factor_graph_potts ( + const graph_type& g, + std::vector<node_label>& labels + ) + { + DLIB_ASSERT(graph_contains_length_one_cycle(g) == false, + "\t void find_max_factor_graph_potts(g,labels)" + << "\n\t Invalid inputs were given to this function." + ); + typedef typename graph_type::edge_type edge_type; + typedef typename graph_type::type type; + + // The edges and node's have to use the same type to represent factor weights! + COMPILE_TIME_ASSERT((is_same_type<edge_type, type>::value == true)); + COMPILE_TIME_ASSERT(is_signed_type<edge_type>::value); + +#ifdef ENABLE_ASSERTS + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + for (unsigned long jj = 0; jj < g.node(i).number_of_neighbors(); ++jj) + { + unsigned long j = g.node(i).neighbor(jj).index(); + DLIB_ASSERT(edge(g,i,j) >= 0, + "\t void find_max_factor_graph_potts(g,labels)" + << "\n\t Invalid inputs were given to this function." + << "\n\t i: " << i + << "\n\t j: " << j + << "\n\t edge(g,i,j): " << edge(g,i,j) + ); + } + } +#endif + + dlib::impl::general_potts_problem<graph_type> gg(g, labels); + find_max_factor_graph_potts(gg); + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + void find_max_factor_graph_potts ( + const potts_grid_problem& prob, + array2d<node_label,mem_manager>& labels + ) + { + typedef array2d<node_label,mem_manager> image_type; + labels.set_size(prob.nr(), prob.nc()); + dlib::impl::potts_grid_problem<image_type,potts_grid_problem> model(labels,prob); + find_max_factor_graph_potts(model); + } + +// ---------------------------------------------------------------------------------------- + + namespace impl + { + template < + typename pixel_type1, + typename pixel_type2, + typename model_type + > + struct potts_grid_image_pair_model + { + const pixel_type1* data1; + const pixel_type2* data2; + const model_type& model; + const long nr_; + const long nc_; + template <typename image_type1, typename image_type2> + potts_grid_image_pair_model( + const model_type& model_, + const image_type1& img1, + const image_type2& img2 + ) : + model(model_), + nr_(img1.nr()), + nc_(img1.nc()) + { + data1 = &img1[0][0]; + data2 = &img2[0][0]; + } + + typedef typename model_type::value_type value_type; + + long nr() const { return nr_; } + long nc() const { return nc_; } + + value_type factor_value ( + unsigned long idx + ) const + { + return model.factor_value(*(data1 + idx), *(data2 + idx)); + } + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const + { + return model.factor_value_disagreement(*(data1 + idx1), *(data1 + idx2)); + } + }; + + // ---------------------------------------------------------------------------------------- + + template < + typename image_type, + typename model_type + > + struct potts_grid_image_single_model + { + const typename image_type::type* data1; + const model_type& model; + const long nr_; + const long nc_; + potts_grid_image_single_model( + const model_type& model_, + const image_type& img1 + ) : + model(model_), + nr_(img1.nr()), + nc_(img1.nc()) + { + data1 = &img1[0][0]; + } + + typedef typename model_type::value_type value_type; + + long nr() const { return nr_; } + long nc() const { return nc_; } + + value_type factor_value ( + unsigned long idx + ) const + { + return model.factor_value(*(data1 + idx)); + } + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const + { + return model.factor_value_disagreement(*(data1 + idx1), *(data1 + idx2)); + } + }; + + } + +// ---------------------------------------------------------------------------------------- + + template < + typename pair_image_model, + typename pixel_type1, + typename pixel_type2, + typename mem_manager + > + impl::potts_grid_image_pair_model<pixel_type1, pixel_type2, pair_image_model> make_potts_grid_problem ( + const pair_image_model& model, + const array2d<pixel_type1,mem_manager>& img1, + const array2d<pixel_type2,mem_manager>& img2 + ) + { + DLIB_ASSERT(get_rect(img1) == get_rect(img2), + "\t potts_grid_problem make_potts_grid_problem()" + << "\n\t Invalid inputs were given to this function." + << "\n\t get_rect(img1): " << get_rect(img1) + << "\n\t get_rect(img2): " << get_rect(img2) + ); + typedef impl::potts_grid_image_pair_model<pixel_type1, pixel_type2, pair_image_model> potts_type; + return potts_type(model,img1,img2); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename single_image_model, + typename pixel_type, + typename mem_manager + > + impl::potts_grid_image_single_model<array2d<pixel_type,mem_manager>, single_image_model> make_potts_grid_problem ( + const single_image_model& model, + const array2d<pixel_type,mem_manager>& img + ) + { + typedef impl::potts_grid_image_single_model<array2d<pixel_type,mem_manager>, single_image_model> potts_type; + return potts_type(model,img); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_Hh_ + diff --git a/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h new file mode 100644 index 000000000..69aa59256 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h @@ -0,0 +1,636 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ +#ifdef DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ + +#include "../matrix.h" +#include "min_cut_abstract.h" +#include "../graph_utils.h" +#include "../array2d/array2d_kernel_abstract.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + class potts_problem + { + /*! + WHAT THIS OBJECT REPRESENTS + This object represents a boolean valued factor graph or graphical model + that can be efficiently operated on using graph cuts. In particular, this + object defines the interface a MAP problem on a factor graph must + implement if it is to be solved using the find_max_factor_graph_potts() + routine defined at the bottom of this file. + + Note that there is no dlib::potts_problem object. What you are looking + at here is simply the interface definition for a Potts problem. You must + implement your own version of this object for the problem you wish to + solve and then pass it to the find_max_factor_graph_potts() routine. + + Note also that a factor graph should not have any nodes which are + neighbors with themselves. Additionally, the graph is undirected. This + mean that if A is a neighbor of B then B must be a neighbor of A for + the MAP problem to be valid. + !*/ + + public: + + unsigned long number_of_nodes ( + ) const; + /*! + ensures + - returns the number of nodes in the factor graph. Or in other words, + returns the number of variables in the MAP problem/Potts model. + !*/ + + unsigned long number_of_neighbors ( + unsigned long idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns the number of neighbors of node idx. + !*/ + + // This is an optional variable which specifies a number that is always + // greater than or equal to number_of_neighbors(idx). If you don't know + // the value at compile time then either don't include max_number_of_neighbors + // in your potts_problem object or set it to 0. + const static unsigned long max_number_of_neighbors = 0; + + unsigned long get_neighbor ( + unsigned long idx, + unsigned long n + ) const; + /*! + requires + - idx < number_of_nodes() + - n < number_of_neighbors(idx) + ensures + - returns the node index value of the n-th neighbor of + the node with index value idx. + - The neighbor relationship is reciprocal. That is, if + get_neighbor(A,i)==B then there is a value of j such + that get_neighbor(B,j)==A. + - A node is never its own neighbor. That is, there is + no i such that get_neighbor(idx,i)==idx. + !*/ + + unsigned long get_neighbor_idx ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + ensures + - This function is basically the inverse of get_neighbor(). + - returns a number IDX such that: + - get_neighbor(idx1,IDX) == idx2 + - IDX < number_of_neighbors(idx1) + !*/ + + void set_label ( + const unsigned long& idx, + node_label value + ); + /*! + requires + - idx < number_of_nodes() + ensures + - #get_label(idx) == value + !*/ + + node_label get_label ( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns the current label for the idx-th node. This is a value which is + 0 if the node's label is false and is any other value if it is true. + + Note that this value is not used by factor_value() or factor_value_disagreement(). + It is simply here to provide a mechanism for find_max_factor_graph_potts() + to return its labeled result. Additionally, the reason it returns a + node_label rather than a bool is because doing it this way facilitates + use of a graph cut algorithm for the solution of the MAP problem. For + more of an explanation you should read the paper referenced by the min_cut + object. + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + value_type factor_value ( + unsigned long idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns a value which indicates how "good" it is to assign the idx-th + node the label of true. The larger the value, the more desirable it is + to give it this label. Similarly, a negative value indicates that it is + better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the idx-th node must be labeled + true while negative infinity means it must be labeled false. + !*/ + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + - idx1 != idx2 + - the idx1-th node and idx2-th node are neighbors in the graph. That is, + get_neighbor(idx1,i)==idx2 for some value of i. + ensures + - returns a number >= 0. This is the penalty for giving node idx1 and idx2 + different labels. Larger values indicate a larger penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + class potts_grid_problem + { + /*! + WHAT THIS OBJECT REPRESENTS + This object is a specialization of a potts_problem to the case where + the graph is a regular grid where each node is connected to its four + neighbors. An example of this is an image where each pixel is a node + and is connected to its four immediate neighboring pixels. Therefore, + this object defines the interface this special kind of MAP problem + must implement if it is to be solved by the find_max_factor_graph_potts(potts_grid_problem,array2d) + routine defined at the end of this file. + + + Note that all nodes always have four neighbors, even nodes on the edge + of the graph. This is because these border nodes are connected to + the border nodes on the other side of the graph. That is, the graph + "wraps" around at the borders. + !*/ + + public: + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + long nr( + ) const; + /*! + ensures + - returns the number of rows in the grid + !*/ + + long nc( + ) const; + /*! + ensures + - returns the number of columns in the grid + !*/ + + value_type factor_value ( + unsigned long idx + ) const; + /*! + requires + - idx < nr()*nc() + ensures + - The grid is represented in row-major-order format. Therefore, idx + identifies a node according to its position in the row-major-order + representation of the grid graph. Or in other words, idx corresponds + to the following row and column location in the graph: + - row == idx/nc() + - col == idx%nc() + - returns a value which indicates how "good" it is to assign the idx-th + node the label of true. The larger the value, the more desirable it is + to give it this label. Similarly, a negative value indicates that it is + better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the idx-th node must be labeled + true while negative infinity means it must be labeled false. + !*/ + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < nr()*nc() + - idx2 < nr()*nc() + - idx1 != idx2 + - the idx1-th node and idx2-th node are neighbors in the grid graph. + ensures + - The grid is represented in row-major-order format. Therefore, idx1 and + idx2 identify nodes according to their positions in the row-major-order + representation of the grid graph. For example, idx1 corresponds + to the following row and column location in the graph: + - row == idx1/nc() + - col == idx1%nc() + - returns a number >= 0. This is the penalty for giving node idx1 and idx2 + different labels. Larger values indicate a larger penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + typename potts_problem::value_type potts_model_score ( + const potts_problem& prob + ); + /*! + requires + - potts_problem == an object with an interface compatible with the potts_problem + object defined at the top of this file. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - computes the model score for the given potts_problem. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in prob. Or in other + words, L(i) == (prob.get_label(i) != 0). + - let F == the sum of values of prob.factor_value(i) for only i values + where L(i) == true. + - Let D == the sum of values of prob.factor_value_disagreement(i,j) + for only i and j values which meet the following conditions: + - i and j are neighbors in the graph defined by prob, that is, + it is valid to call prob.factor_value_disagreement(i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + typename graph_type::edge_type potts_model_score ( + const graph_type& g, + const std::vector<node_label>& labels + ); + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_type::edge_type is some signed type such as int or double + - graph_type::type must be the same type as graph_type::edge_type + - graph_contains_length_one_cycle(g) == false + - for all valid i and j: + - edge(g,i,j) >= 0 + ensures + - This function does the same thing as the version of potts_model_score() + defined above, except that this version operates on a dlib::graph + instead of a potts_problem object. + - computes the model score for the given graph and labeling. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in g. Or in other + words, L(i) == (labels[i] != 0). + - let F == the sum of values of g.node(i).data for only i values + where L(i) == true. + - Let D == the sum of values of edge(g,i,j) for only i and j + values which meet the following conditions: + - i and j are neighbors in the graph defined by g, that is, + it is valid to call edge(g,i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + typename potts_grid_problem::value_type potts_model_score ( + const potts_grid_problem& prob, + const array2d<node_label,mem_manager>& labels + ); + /*! + requires + - prob.nr() == labels.nr() + - prob.nc() == labels.nc() + - potts_grid_problem == an object with an interface compatible with the + potts_grid_problem object defined above. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - computes the model score for the given potts_grid_problem. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in prob. Or in other + words, L(i) == (labels[i/labels.nc()][i%labels.nc()] != 0). + - let F == the sum of values of prob.factor_value(i) for only i values + where L(i) == true. + - Let D == the sum of values of prob.factor_value_disagreement(i,j) + for only i and j values which meet the following conditions: + - i and j are neighbors in the graph defined by prob, that is, + it is valid to call prob.factor_value_disagreement(i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + void find_max_factor_graph_potts ( + potts_problem& prob + ); + /*! + requires + - potts_problem == an object with an interface compatible with the potts_problem + object defined at the top of this file. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - This function is a tool for exactly solving the MAP problem in a Potts + model. In particular, this means that this function finds the assignments + to all the labels in prob which maximizes potts_model_score(#prob). + - The optimal labels are stored in #prob. + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + void find_max_factor_graph_potts ( + const graph_type& g, + std::vector<node_label>& labels + ); + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_type::edge_type is some signed type such as int or double + - graph_type::type must be the same type as graph_type::edge_type + - graph_contains_length_one_cycle(g) == false + - for all valid i and j: + - edge(g,i,j) >= 0 + ensures + - This routine simply converts g into a potts_problem and calls the + version of find_max_factor_graph_potts() defined above on it. Therefore, + this routine is just a convenience wrapper that lets you use a dlib::graph + to represent a potts problem. This means that this function maximizes + the value of potts_model_score(g, #labels). + - #labels.size() == g.number_of_nodes() + - for all valid i: + - #labels[i] == the optimal label for g.node(i) + - The correspondence between g and a potts_problem is the following: + - the factor_value() for a node is stored in g.node(i).data. + - the factor_value_disagreement(i,j) is stored in edge(g,i,j). + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + void find_max_factor_graph_potts ( + const potts_grid_problem& prob, + array2d<node_label,mem_manager>& labels + ); + /*! + requires + - potts_grid_problem == an object with an interface compatible with the + potts_grid_problem object defined above. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - This routine solves a version of a potts problem where the graph is a + regular grid where each node is connected to its four immediate neighbors. + In particular, this means that this function finds the assignments + to all the labels in prob which maximizes potts_model_score(prob,#labels). + - The optimal labels are stored in #labels. + - #labels.nr() == prob.nr() + - #labels.nc() == prob.nc() + !*/ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// The following functions and interface definitions are convenience routines for use +// with the potts grid problem version of find_max_factor_graph_potts() defined above. +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + struct single_image_model + { + /*! + WHAT THIS OBJECT REPRESENTS + This object defines a slightly more convenient interface for creating + potts_grid_problems which operate on an image. In this case, the goal + is to assign a binary label to each pixel in an image. In particular, + this object defines the interface used by the make_potts_grid_problem() + routine defined below. + + In the following comments, we will refer to the image supplied to + make_potts_grid_problem() as IMG. + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + template <typename pixel_type> + value_type factor_value ( + const pixel_type& v + ) const; + /*! + requires + - v is a pixel value from IMG. + ensures + - returns a value which indicates how "good" it is to assign the location + in IMG corresponding to v with the label of true. The larger the value, + the more desirable it is to give it this label. Similarly, a negative + value indicates that it is better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the pixel must be labeled + true while negative infinity means it must be labeled false. + !*/ + + template <typename pixel_type> + value_type factor_value_disagreement ( + const pixel_type& v1, + const pixel_type& v2 + ) const; + /*! + requires + - v1 and v2 are pixel values from neighboring pixels in the IMG image. + ensures + - returns a number >= 0. This is the penalty for giving neighboring pixels + with values v1 and v2 different labels. Larger values indicate a larger + penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- + + struct pair_image_model + { + /*! + WHAT THIS OBJECT REPRESENTS + This object defines a slightly more convenient interface for creating + potts_grid_problems which operate on a pair of identically sized images. + In this case, the goal is to assign a label to each pixel in the first + image of the pair. In particular, this object defines the interface + used by the make_potts_grid_problem() routine defined below. + + In the following comments, we will refer to the two images supplied to + make_potts_grid_problem() as IMG1 and IMG2. The goal of the potts + problem will be to assign labels to each pixel in IMG1 (IMG2 is + not labeled, it is simply used as a place to keep auxiliary data). + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + template <typename pixel_type1, typename pixel_type2> + value_type factor_value ( + const pixel_type1& v1, + const pixel_type2& v2 + ) const; + /*! + requires + - v1 and v2 are corresponding pixels from IMG1 and IMG2 respectively. + That is, both pixel values have the same coordinates in the images. + So for example, if v1 is the value of IMG1[4][5] then v2 is the value + of IMG2[4][5]. + ensures + - returns a value which indicates how "good" it is to assign the location + in IMG1 corresponding to v1 with the label of true. The larger the value, + the more desirable it is to give it this label. Similarly, a negative + value indicates that it is better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the pixel must be labeled + true while negative infinity means it must be labeled false. + !*/ + + template <typename pixel_type> + value_type factor_value_disagreement ( + const pixel_type& v1, + const pixel_type& v2 + ) const; + /*! + requires + - v1 and v2 are pixel values from neighboring pixels in the IMG1 image. + ensures + - returns a number >= 0. This is the penalty for giving neighboring pixels + with values v1 and v2 different labels. Larger values indicate a larger + penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename single_image_model, + typename pixel_type, + typename mem_manager + > + potts_grid_problem make_potts_grid_problem ( + const single_image_model& model, + const array2d<pixel_type,mem_manager>& img + ); + /*! + requires + - single_image_model == an object with an interface compatible with the + single_image_model object defined above. + - for all valid i and j: + - model.factor_value_disagreement(i,j) >= 0 + - model.factor_value_disagreement(i,j) == model.factor_value_disagreement(j,i) + ensures + - returns a potts_grid_problem which can be solved using the + find_max_factor_graph_potts(prob,array2d) routine defined above. That is, + given an image to store the labels, the following statement would solve the + potts problem defined by the given model and image: + find_max_factor_graph_potts(make_potts_grid_problem(model,img),labels); + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename pair_image_model, + typename pixel_type1, + typename pixel_type2, + typename mem_manager + > + potts_grid_problem make_potts_grid_problem ( + const pair_image_model& model, + const array2d<pixel_type1,mem_manager>& img1, + const array2d<pixel_type2,mem_manager>& img2 + ); + /*! + requires + - get_rect(img1) == get_rect(img2) + (i.e. img1 and img2 have the same dimensions) + - pair_image_model == an object with an interface compatible with the + pair_image_model object defined above. + - for all valid i and j: + - model.factor_value_disagreement(i,j) >= 0 + - model.factor_value_disagreement(i,j) == model.factor_value_disagreement(j,i) + ensures + - returns a potts_grid_problem which can be solved using the + find_max_factor_graph_potts(prob,array2d) routine defined above. That is, + given an image to store the labels, the following statement would solve the + potts problem defined by the given model and pair of images: + find_max_factor_graph_potts(make_potts_grid_problem(model,img1,img2),labels); + !*/ + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ + + diff --git a/ml/dlib/dlib/graph_cuts/general_flow_graph.h b/ml/dlib/dlib/graph_cuts/general_flow_graph.h new file mode 100644 index 000000000..d0b93e311 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/general_flow_graph.h @@ -0,0 +1,172 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_GENERAL_FLOW_GRaPH_Hh_ +#define DLIB_GENERAL_FLOW_GRaPH_Hh_ + +#include "../graph_utils.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + namespace impl + { + + template < + typename directed_graph_type + > + class general_flow_graph + { + /*! + this is a utility class used by dlib::min_cut to convert a directed_graph + into the kind of flow graph expected by the min_cut object's main block + of code. + !*/ + + directed_graph_type& g; + + typedef typename directed_graph_type::node_type node_type; + typedef typename directed_graph_type::type node_label; + + public: + + general_flow_graph( + directed_graph_type& g_ + ) : g(g_) + { + } + + class out_edge_iterator + { + friend class general_flow_graph; + unsigned long idx; // base node idx + unsigned long cnt; // count over the neighbors of idx + public: + + out_edge_iterator( + ):idx(0),cnt(0) {} + + out_edge_iterator( + unsigned long idx_, + unsigned long cnt_ + ):idx(idx_),cnt(cnt_) + {} + + bool operator!= ( + const out_edge_iterator& item + ) const { return cnt != item.cnt; } + + out_edge_iterator& operator++( + ) + { + ++cnt; + return *this; + } + }; + + class in_edge_iterator + { + + friend class general_flow_graph; + unsigned long idx; // base node idx + unsigned long cnt; // count over the neighbors of idx + public: + + in_edge_iterator( + ):idx(0),cnt(0) {} + + in_edge_iterator( + unsigned long idx_, + unsigned long cnt_ + ):idx(idx_),cnt(cnt_) + {} + + bool operator!= ( + const in_edge_iterator& item + ) const { return cnt != item.cnt; } + + in_edge_iterator& operator++( + ) + { + ++cnt; + return *this; + } + }; + + unsigned long number_of_nodes ( + ) const { return g.number_of_nodes(); } + + out_edge_iterator out_begin( + const unsigned long& it + ) const { return out_edge_iterator(it, 0); } + + in_edge_iterator in_begin( + const unsigned long& it + ) const { return in_edge_iterator(it, 0); } + + out_edge_iterator out_end( + const unsigned long& it + ) const { return out_edge_iterator(it, g.node(it).number_of_children()); } + + in_edge_iterator in_end( + const unsigned long& it + ) const { return in_edge_iterator(it, g.node(it).number_of_parents()); } + + unsigned long node_id ( + const out_edge_iterator& it + ) const { return g.node(it.idx).child(it.cnt).index(); } + unsigned long node_id ( + const in_edge_iterator& it + ) const { return g.node(it.idx).parent(it.cnt).index(); } + + typedef typename directed_graph_type::edge_type edge_type; + + edge_type get_flow (const unsigned long& it1, const unsigned long& it2) const + { + return edge(g, it1, it2); + } + edge_type get_flow (const out_edge_iterator& it) const + { + return g.node(it.idx).child_edge(it.cnt); + } + edge_type get_flow (const in_edge_iterator& it) const + { + return g.node(it.idx).parent_edge(it.cnt); + } + + void adjust_flow ( + const unsigned long& it1, + const unsigned long& it2, + const edge_type& value + ) + { + edge(g, it1, it2) += value; + edge(g, it2, it1) -= value; + } + + void set_label ( + const unsigned long& it, + node_label value + ) + { + g.node(it).data = value; + } + + node_label get_label ( + const unsigned long& it + ) const + { + return g.node(it).data; + } + + }; + + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_GENERAL_FLOW_GRaPH_Hh_ + diff --git a/ml/dlib/dlib/graph_cuts/general_potts_problem.h b/ml/dlib/dlib/graph_cuts/general_potts_problem.h new file mode 100644 index 000000000..ebedbc572 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/general_potts_problem.h @@ -0,0 +1,99 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_GENERAL_POTTS_PRoBLEM_Hh_ +#define DLIB_GENERAL_POTTS_PRoBLEM_Hh_ + +#include "../graph_utils.h" +#include "min_cut.h" +#include <vector> + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + namespace impl + { + template < + typename graph_type + > + class general_potts_problem + { + + const graph_type& g; + std::vector<node_label>& labels; + public: + general_potts_problem ( + const graph_type& g_, + std::vector<node_label>& labels_ + ) : g(g_), labels(labels_) + { + labels.resize(g.number_of_nodes()); + } + + unsigned long number_of_nodes ( + ) const { return g.number_of_nodes(); } + + unsigned long number_of_neighbors ( + unsigned long idx + ) const { return g.node(idx).number_of_neighbors(); } + + unsigned long get_neighbor ( + unsigned long idx, + unsigned long n + ) const { return g.node(idx).neighbor(n).index(); } + + unsigned long get_neighbor_idx ( + unsigned long idx1, + unsigned long idx2 + ) const + { + for (unsigned long i = 0; i < g.node(idx1).number_of_neighbors(); ++i) + { + if (g.node(idx1).neighbor(i).index() == idx2) + return i; + } + + // This should never ever execute + return 0; + } + + void set_label ( + const unsigned long& idx, + node_label value + ) + { + labels[idx] = value; + } + + node_label get_label ( + const unsigned long& idx + ) const { return labels[idx]; } + + typedef typename graph_type::edge_type value_type; + + value_type factor_value ( + unsigned long idx + ) const + { + return g.node(idx).data; + } + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const + { + return edge(g, idx1, idx2); + } + + }; + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_GENERAL_POTTS_PRoBLEM_Hh_ + + diff --git a/ml/dlib/dlib/graph_cuts/graph_labeler.h b/ml/dlib/dlib/graph_cuts/graph_labeler.h new file mode 100644 index 000000000..34c3fcb5e --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/graph_labeler.h @@ -0,0 +1,211 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_GRAPH_LaBELER_Hh_ +#define DLIB_GRAPH_LaBELER_Hh_ + +#include "graph_labeler_abstract.h" +#include "../matrix.h" +#include "../string.h" +#include <vector> +#include "find_max_factor_graph_potts.h" +#include "../svm/sparse_vector.h" +#include "../graph.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + class graph_labeler + { + + public: + + typedef std::vector<bool> label_type; + typedef label_type result_type; + + graph_labeler() + { + } + + graph_labeler( + const vector_type& edge_weights_, + const vector_type& node_weights_ + ) : + edge_weights(edge_weights_), + node_weights(node_weights_) + { + // make sure requires clause is not broken + DLIB_ASSERT(edge_weights.size() == 0 || min(edge_weights) >= 0, + "\t graph_labeler::graph_labeler()" + << "\n\t Invalid inputs were given to this function." + << "\n\t min(edge_weights): " << min(edge_weights) + << "\n\t this: " << this + ); + } + + const vector_type& get_edge_weights ( + ) const { return edge_weights; } + + const vector_type& get_node_weights ( + ) const { return node_weights; } + + template <typename graph_type> + void operator() ( + const graph_type& sample, + std::vector<bool>& labels + ) const + { + // make sure requires clause is not broken +#ifdef ENABLE_ASSERTS + DLIB_ASSERT(graph_contains_length_one_cycle(sample) == false, + "\t void graph_labeler::operator()" + << "\n\t Invalid inputs were given to this function." + << "\n\t get_edge_weights().size(): " << get_edge_weights().size() + << "\n\t get_node_weights().size(): " << get_node_weights().size() + << "\n\t graph_contains_length_one_cycle(sample): " << graph_contains_length_one_cycle(sample) + << "\n\t this: " << this + ); + for (unsigned long i = 0; i < sample.number_of_nodes(); ++i) + { + if (is_matrix<vector_type>::value && + is_matrix<typename graph_type::type>::value) + { + // check that dot() is legal. + DLIB_ASSERT((unsigned long)get_node_weights().size() == (unsigned long)sample.node(i).data.size(), + "\t void graph_labeler::operator()" + << "\n\t The size of the node weight vector must match the one in the node." + << "\n\t get_node_weights().size(): " << get_node_weights().size() + << "\n\t sample.node(i).data.size(): " << sample.node(i).data.size() + << "\n\t i: " << i + << "\n\t this: " << this + ); + } + + for (unsigned long n = 0; n < sample.node(i).number_of_neighbors(); ++n) + { + if (is_matrix<vector_type>::value && + is_matrix<typename graph_type::edge_type>::value) + { + // check that dot() is legal. + DLIB_ASSERT((unsigned long)get_edge_weights().size() == (unsigned long)sample.node(i).edge(n).size(), + "\t void graph_labeler::operator()" + << "\n\t The size of the edge weight vector must match the one in graph's edge." + << "\n\t get_edge_weights().size(): " << get_edge_weights().size() + << "\n\t sample.node(i).edge(n).size(): " << sample.node(i).edge(n).size() + << "\n\t i: " << i + << "\n\t this: " << this + ); + } + + DLIB_ASSERT(sample.node(i).edge(n).size() == 0 || min(sample.node(i).edge(n)) >= 0, + "\t void graph_labeler::operator()" + << "\n\t No edge vectors are allowed to have negative elements." + << "\n\t min(sample.node(i).edge(n)): " << min(sample.node(i).edge(n)) + << "\n\t i: " << i + << "\n\t n: " << n + << "\n\t this: " << this + ); + } + } +#endif + + + graph<double,double>::kernel_1a g; + copy_graph_structure(sample, g); + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + g.node(i).data = dot(node_weights, sample.node(i).data); + + for (unsigned long n = 0; n < g.node(i).number_of_neighbors(); ++n) + { + const unsigned long j = g.node(i).neighbor(n).index(); + // Don't compute an edge weight more than once. + if (i < j) + { + g.node(i).edge(n) = dot(edge_weights, sample.node(i).edge(n)); + } + } + + } + + labels.clear(); + std::vector<node_label> temp; + find_max_factor_graph_potts(g, temp); + for (unsigned long i = 0; i < temp.size(); ++i) + { + if (temp[i] != 0) + labels.push_back(true); + else + labels.push_back(false); + } + } + + template <typename graph_type> + std::vector<bool> operator() ( + const graph_type& sample + ) const + { + std::vector<bool> temp; + (*this)(sample, temp); + return temp; + } + + private: + + vector_type edge_weights; + vector_type node_weights; + }; + + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + void serialize ( + const graph_labeler<vector_type>& item, + std::ostream& out + ) + { + int version = 1; + serialize(version, out); + serialize(item.get_edge_weights(), out); + serialize(item.get_node_weights(), out); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + void deserialize ( + graph_labeler<vector_type>& item, + std::istream& in + ) + { + int version = 0; + deserialize(version, in); + if (version != 1) + { + throw dlib::serialization_error("While deserializing graph_labeler, found unexpected version number of " + + cast_to_string(version) + "."); + } + + vector_type edge_weights, node_weights; + deserialize(edge_weights, in); + deserialize(node_weights, in); + + item = graph_labeler<vector_type>(edge_weights, node_weights); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_GRAPH_LaBELER_Hh_ + + diff --git a/ml/dlib/dlib/graph_cuts/graph_labeler_abstract.h b/ml/dlib/dlib/graph_cuts/graph_labeler_abstract.h new file mode 100644 index 000000000..a0821b696 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/graph_labeler_abstract.h @@ -0,0 +1,185 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_GRAPH_LaBELER_ABSTRACT_Hh_ +#ifdef DLIB_GRAPH_LaBELER_ABSTRACT_Hh_ + +#include "find_max_factor_graph_potts_abstract.h" +#include "../graph/graph_kernel_abstract.h" +#include "../matrix/matrix_abstract.h" +#include <vector> + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + class graph_labeler + { + /*! + REQUIREMENTS ON vector_type + - vector_type is a dlib::matrix capable of representing column + vectors or it is a sparse vector type as defined in dlib/svm/sparse_vector_abstract.h. + + WHAT THIS OBJECT REPRESENTS + This object is a tool for labeling each node in a graph with a value + of true or false, subject to a labeling consistency constraint between + nodes that share an edge. In particular, this object is useful for + representing a graph labeling model learned via some machine learning + method. + + To elaborate, suppose we have a graph we want to label. Moreover, + suppose we can assign a score to each node which represents how much + we want to label the node as true, and we also have scores for each + edge which represent how much we wanted the nodes sharing the edge to + have the same label. If we could do this then we could find the optimal + labeling using the find_max_factor_graph_potts() routine. Therefore, + the graph_labeler is just an object which contains the necessary data + to compute these score functions and then call find_max_factor_graph_potts(). + Additionally, this object uses linear functions to represent these score + functions. + + THREAD SAFETY + It is always safe to use distinct instances of this object in different + threads. However, when a single instance is shared between threads then + the following rules apply: + It is safe to call the const members of this object from multiple + threads. This is because the const members are purely read-only + operations. However, any operation that modifies a graph_labeler is + not threadsafe. + !*/ + + public: + + typedef std::vector<bool> label_type; + typedef label_type result_type; + + graph_labeler( + ); + /*! + ensures + - this object is properly initialized + - #get_node_weights() == an initial value of type vector_type. + - #get_edge_weights() == an initial value of type vector_type. + !*/ + + graph_labeler( + const vector_type& edge_weights, + const vector_type& node_weights + ); + /*! + requires + - min(edge_weights) >= 0 + ensures + - #get_edge_weights() == edge_weights + - #get_node_weights() == node_weights + !*/ + + const vector_type& get_edge_weights ( + ) const; + /*! + ensures + - Recall that the score function for an edge is a linear function of + the vector stored at that edge. This means there is some vector, E, + which we dot product with the vector in the graph to compute the + score. Therefore, this function returns that E vector which defines + the edge score function. + !*/ + + const vector_type& get_node_weights ( + ) const; + /*! + ensures + - Recall that the score function for a node is a linear function of + the vector stored in that node. This means there is some vector, W, + which we dot product with the vector in the graph to compute the score. + Therefore, this function returns that W vector which defines the node + score function. + !*/ + + template <typename graph_type> + void operator() ( + const graph_type& sample, + std::vector<bool>& labels + ) const; + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_type::type and graph_type::edge_type must be either matrix objects + capable of representing column vectors or some kind of sparse vector + type as defined in dlib/svm/sparse_vector_abstract.h. + - graph_contains_length_one_cycle(sample) == false + - for all valid i and j: + - min(edge(sample,i,j)) >= 0 + - it must be legal to call dot(edge(sample,i,j), get_edge_weights()) + - it must be legal to call dot(sample.node(i).data, get_node_weights()) + ensures + - Computes a labeling for each node in the given graph and stores the result + in #labels. + - #labels.size() == sample.number_of_nodes() + - for all valid i: + - #labels[i] == the label of the node sample.node(i). + - The labels are computed by creating a graph, G, with scalar values on each node + and edge. The scalar values are calculated according to the following: + - for all valid i: + - G.node(i).data == dot(get_node_weights(), sample.node(i).data) + - for all valid i and j: + - edge(G,i,j) == dot(get_edge_weights(), edge(sample,i,j)) + Then the labels are computed by calling find_max_factor_graph_potts(G,#labels). + !*/ + + template <typename graph_type> + std::vector<bool> operator() ( + const graph_type& sample + ) const; + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_contains_length_one_cycle(sample) == false + - for all valid i and j: + - min(edge(sample,i,j)) >= 0 + - it must be legal to call dot(edge(sample,i,j), get_edge_weights()) + - it must be legal to call dot(sample.node(i).data, get_node_weights()) + ensures + - Performs (*this)(sample, labels); return labels; + (i.e. This is just another version of the above operator() routine + but instead of returning the labels via the second argument, it + returns them as the normal return value). + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + void serialize ( + const graph_labeler<vector_type>& item, + std::ostream& out + ); + /*! + provides serialization support + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename vector_type + > + void deserialize ( + graph_labeler<vector_type>& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_GRAPH_LaBELER_ABSTRACT_Hh_ + diff --git a/ml/dlib/dlib/graph_cuts/min_cut.h b/ml/dlib/dlib/graph_cuts/min_cut.h new file mode 100644 index 000000000..6bbb57608 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/min_cut.h @@ -0,0 +1,571 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_MIN_CuT_Hh_ +#define DLIB_MIN_CuT_Hh_ + +#include "min_cut_abstract.h" +#include "../matrix.h" +#include "general_flow_graph.h" +#include "../is_kind.h" + +#include <iostream> +#include <fstream> +#include <deque> + + +// ---------------------------------------------------------------------------------------- + + +namespace dlib +{ + + typedef unsigned char node_label; + +// ---------------------------------------------------------------------------------------- + + const node_label SOURCE_CUT = 0; + const node_label SINK_CUT = 254; + const node_label FREE_NODE = 255; + +// ---------------------------------------------------------------------------------------- + + template <typename flow_graph> + typename disable_if<is_directed_graph<flow_graph>,typename flow_graph::edge_type>::type + graph_cut_score ( + const flow_graph& g + ) + { + typedef typename flow_graph::edge_type edge_weight_type; + edge_weight_type score = 0; + typedef typename flow_graph::out_edge_iterator out_edge_iterator; + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + if (g.get_label(i) != SOURCE_CUT) + continue; + + for (out_edge_iterator n = g.out_begin(i); n != g.out_end(i); ++n) + { + if (g.get_label(g.node_id(n)) != SOURCE_CUT) + { + score += g.get_flow(n); + } + } + } + + return score; + } + + template <typename directed_graph> + typename enable_if<is_directed_graph<directed_graph>,typename directed_graph::edge_type>::type + graph_cut_score ( + const directed_graph& g + ) + { + return graph_cut_score(dlib::impl::general_flow_graph<const directed_graph>(g)); + } + +// ---------------------------------------------------------------------------------------- + + class min_cut + { + + public: + + min_cut() + { + } + + min_cut( const min_cut& ) + { + // Intentionally left empty since all the member variables + // don't logically contribute to the state of this object. + // This copy constructor is here to explicitly avoid the overhead + // of copying these transient variables. + } + + template < + typename directed_graph + > + typename enable_if<is_directed_graph<directed_graph> >::type operator() ( + directed_graph& g, + const unsigned long source_node, + const unsigned long sink_node + ) const + { + DLIB_ASSERT(graph_contains_length_one_cycle(g) == false, + "\t void min_cut::operator()" + << "\n\t Invalid arguments were given to this function." + ); + DLIB_ASSERT(graph_has_symmetric_edges(g) == true, + "\t void min_cut::operator()" + << "\n\t Invalid arguments were given to this function." + ); + + dlib::impl::general_flow_graph<directed_graph> temp(g); + (*this)(temp, source_node, sink_node); + } + + template < + typename flow_graph + > + typename disable_if<is_directed_graph<flow_graph> >::type operator() ( + flow_graph& g, + const unsigned long source_node, + const unsigned long sink_node + ) const + { +#ifdef ENABLE_ASSERTS + DLIB_ASSERT(source_node != sink_node && + source_node < g.number_of_nodes() && + sink_node < g.number_of_nodes(), + "\t void min_cut::operator()" + << "\n\t Invalid arguments were given to this function." + << "\n\t g.number_of_nodes(): " << g.number_of_nodes() + << "\n\t source_node: " << source_node + << "\n\t sink_node: " << sink_node + << "\n\t this: " << this + ); + + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + { + typename flow_graph::out_edge_iterator j, end = g.out_end(i); + for (j = g.out_begin(i); j != end; ++j) + { + const unsigned long jj = g.node_id(j); + DLIB_ASSERT(g.get_flow(i,jj) >= 0, + "\t void min_cut::operator()" + << "\n\t Invalid inputs were given to this function." + << "\n\t i: "<< i + << "\n\t jj: "<< jj + << "\n\t g.get_flow(i,jj): "<< g.get_flow(i,jj) + << "\n\t this: "<< this + ); + + } + } +#endif + parent.clear(); + active.clear(); + orphans.clear(); + + typedef typename flow_graph::edge_type edge_type; + COMPILE_TIME_ASSERT(is_signed_type<edge_type>::value); + + typedef typename flow_graph::out_edge_iterator out_edge_iterator; + typedef typename flow_graph::in_edge_iterator in_edge_iterator; + + // initialize labels + for (unsigned long i = 0; i < g.number_of_nodes(); ++i) + g.set_label(i, FREE_NODE); + + g.set_label(source_node, SOURCE_CUT); + g.set_label(sink_node, SINK_CUT); + + // used to indicate "no parent" + const unsigned long no_parent = g.number_of_nodes(); + + parent.assign(g.number_of_nodes(), no_parent); + + time = 1; + dist.assign(g.number_of_nodes(), 0); + ts.assign(g.number_of_nodes(), time); + + active.push_back(source_node); + active.push_back(sink_node); + + + in_edge_iterator in_begin = g.in_begin(active[0]); + out_edge_iterator out_begin = g.out_begin(active[0]); + + unsigned long source_side, sink_side; + while (grow(g,source_side,sink_side, in_begin, out_begin)) + { + ++time; + ts[source_node] = time; + ts[sink_node] = time; + + augment(g, source_node, sink_node, source_side, sink_side); + adopt(g, source_node, sink_node); + } + + } + + + private: + + unsigned long distance_to_origin ( + const unsigned long no_parent, + unsigned long p, + unsigned long + ) const + { + unsigned long start = p; + unsigned long count = 0; + while (p != no_parent) + { + if (ts[p] == time) + { + count += dist[p]; + + unsigned long count_down = count; + // adjust the dist and ts for the nodes on this path. + while (start != p) + { + ts[start] = time; + dist[start] = count_down; + --count_down; + start = parent[start]; + } + + return count; + } + p = parent[p]; + ++count; + } + + return std::numeric_limits<unsigned long>::max(); + } + + template <typename flow_graph> + void adopt ( + flow_graph& g, + const unsigned long source, + const unsigned long sink + ) const + { + typedef typename flow_graph::out_edge_iterator out_edge_iterator; + typedef typename flow_graph::in_edge_iterator in_edge_iterator; + + // used to indicate "no parent" + const unsigned long no_parent = g.number_of_nodes(); + + while (orphans.size() > 0) + { + const unsigned long p = orphans.back(); + orphans.pop_back(); + + const unsigned char label_p = g.get_label(p); + + // Try to find a valid parent for p. + if (label_p == SOURCE_CUT) + { + const in_edge_iterator begin(g.in_begin(p)); + const in_edge_iterator end(g.in_end(p)); + unsigned long best_dist = std::numeric_limits<unsigned long>::max(); + unsigned long best_node = 0; + for(in_edge_iterator q = begin; q != end; ++q) + { + const unsigned long id = g.node_id(q); + + if (g.get_label(id) != label_p || g.get_flow(q) <= 0 ) + continue; + + unsigned long temp = distance_to_origin(no_parent, id,source); + if (temp < best_dist) + { + best_dist = temp; + best_node = id; + } + + } + if (best_dist != std::numeric_limits<unsigned long>::max()) + { + parent[p] = best_node; + dist[p] = dist[best_node] + 1; + ts[p] = time; + } + + // if we didn't find a parent for p + if (parent[p] == no_parent) + { + for(in_edge_iterator q = begin; q != end; ++q) + { + const unsigned long id = g.node_id(q); + + if (g.get_label(id) != SOURCE_CUT) + continue; + + if (g.get_flow(q) > 0) + active.push_back(id); + + if (parent[id] == p) + { + parent[id] = no_parent; + orphans.push_back(id); + } + } + g.set_label(p, FREE_NODE); + } + } + else + { + unsigned long best_node = 0; + unsigned long best_dist = std::numeric_limits<unsigned long>::max(); + const out_edge_iterator begin(g.out_begin(p)); + const out_edge_iterator end(g.out_end(p)); + for(out_edge_iterator q = begin; q != end; ++q) + { + const unsigned long id = g.node_id(q); + if (g.get_label(id) != label_p || g.get_flow(q) <= 0) + continue; + + unsigned long temp = distance_to_origin(no_parent, id,sink); + + if (temp < best_dist) + { + best_dist = temp; + best_node = id; + } + } + + if (best_dist != std::numeric_limits<unsigned long>::max()) + { + parent[p] = best_node; + dist[p] = dist[best_node] + 1; + ts[p] = time; + } + + // if we didn't find a parent for p + if (parent[p] == no_parent) + { + for(out_edge_iterator q = begin; q != end; ++q) + { + const unsigned long id = g.node_id(q); + + if (g.get_label(id) != SINK_CUT) + continue; + + if (g.get_flow(q) > 0) + active.push_back(id); + + if (parent[id] == p) + { + parent[id] = no_parent; + orphans.push_back(id); + } + } + + g.set_label(p, FREE_NODE); + } + } + + + } + + } + + template <typename flow_graph> + void augment ( + flow_graph& g, + const unsigned long& source, + const unsigned long& sink, + const unsigned long& source_side, + const unsigned long& sink_side + ) const + { + typedef typename flow_graph::edge_type edge_type; + + // used to indicate "no parent" + const unsigned long no_parent = g.number_of_nodes(); + + unsigned long s = source_side; + unsigned long t = sink_side; + edge_type min_cap = g.get_flow(s,t); + + // find the bottleneck capacity on the current path. + + // check from source_side back to the source for the min capacity link. + t = s; + while (t != source) + { + s = parent[t]; + const edge_type temp = g.get_flow(s, t); + if (temp < min_cap) + { + min_cap = temp; + } + t = s; + } + + // check from sink_side back to the sink for the min capacity link + s = sink_side; + while (s != sink) + { + t = parent[s]; + const edge_type temp = g.get_flow(s, t); + if (temp < min_cap) + { + min_cap = temp; + } + s = t; + } + + + // now push the max possible amount of flow though the path + s = source_side; + t = sink_side; + g.adjust_flow(t,s, min_cap); + + // trace back towards the source + t = s; + while (t != source) + { + s = parent[t]; + g.adjust_flow(t,s, min_cap); + if (g.get_flow(s,t) <= 0) + { + parent[t] = no_parent; + orphans.push_back(t); + } + + t = s; + } + + // trace back towards the sink + s = sink_side; + while (s != sink) + { + t = parent[s]; + g.adjust_flow(t,s, min_cap); + if (g.get_flow(s,t) <= 0) + { + parent[s] = no_parent; + orphans.push_back(s); + } + s = t; + } + } + + template <typename flow_graph> + bool grow ( + flow_graph& g, + unsigned long& source_side, + unsigned long& sink_side, + typename flow_graph::in_edge_iterator& in_begin, + typename flow_graph::out_edge_iterator& out_begin + ) const + /*! + ensures + - if (an augmenting path was found) then + - returns true + - (#source_side, #sink_side) == the point where the two trees meet. + #source_side is part of the source tree and #sink_side is part of + the sink tree. + - else + - returns false + !*/ + { + typedef typename flow_graph::out_edge_iterator out_edge_iterator; + typedef typename flow_graph::in_edge_iterator in_edge_iterator; + + + while (active.size() != 0) + { + // pick an active node + const unsigned long A = active[0]; + + const unsigned char label_A = g.get_label(A); + + // process its neighbors + if (label_A == SOURCE_CUT) + { + const out_edge_iterator out_end = g.out_end(A); + for(out_edge_iterator& i = out_begin; i != out_end; ++i) + { + if (g.get_flow(i) > 0) + { + const unsigned long id = g.node_id(i); + const unsigned char label_i = g.get_label(id); + if (label_i == FREE_NODE) + { + active.push_back(id); + g.set_label(id,SOURCE_CUT); + parent[id] = A; + ts[id] = ts[A]; + dist[id] = dist[A] + 1; + } + else if (label_A != label_i) + { + source_side = A; + sink_side = id; + return true; + } + else if (is_closer(A, id)) + { + parent[id] = A; + ts[id] = ts[A]; + dist[id] = dist[A] + 1; + } + } + } + } + else if (label_A == SINK_CUT) + { + const in_edge_iterator in_end = g.in_end(A); + for(in_edge_iterator& i = in_begin; i != in_end; ++i) + { + if (g.get_flow(i) > 0) + { + const unsigned long id = g.node_id(i); + const unsigned char label_i = g.get_label(id); + if (label_i == FREE_NODE) + { + active.push_back(id); + g.set_label(id,SINK_CUT); + parent[id] = A; + ts[id] = ts[A]; + dist[id] = dist[A] + 1; + } + else if (label_A != label_i) + { + sink_side = A; + source_side = id; + return true; + } + else if (is_closer(A, id)) + { + parent[id] = A; + ts[id] = ts[A]; + dist[id] = dist[A] + 1; + } + } + } + } + + active.pop_front(); + if (active.size() != 0) + { + in_begin = g.in_begin(active[0]); + out_begin = g.out_begin(active[0]); + } + } + + return false; + } + + inline bool is_closer ( + unsigned long p, + unsigned long q + ) const + { + // return true if p is closer to a terminal than q + return ts[q] <= ts[p] && dist[q] > dist[p]; + } + + mutable std::vector<uint32> dist; + mutable std::vector<uint32> ts; + mutable uint32 time; + mutable std::vector<unsigned long> parent; + + mutable std::deque<unsigned long> active; + mutable std::vector<unsigned long> orphans; + }; + +// ---------------------------------------------------------------------------------------- + +} + +// ---------------------------------------------------------------------------------------- + +#endif // DLIB_MIN_CuT_Hh_ + diff --git a/ml/dlib/dlib/graph_cuts/min_cut_abstract.h b/ml/dlib/dlib/graph_cuts/min_cut_abstract.h new file mode 100644 index 000000000..748aca950 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/min_cut_abstract.h @@ -0,0 +1,476 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_MIN_CuT_ABSTRACT_Hh_ +#ifdef DLIB_MIN_CuT_ABSTRACT_Hh_ + +#include "../graph_utils.h" + +// ---------------------------------------------------------------------------------------- + +namespace dlib +{ + /*!A node_label + The node_label type is the type used to label which part of a graph cut + a node is on. It is used by all the graph cut tools. The three possible + values of a node label are SOURCE_CUT, SINK_CUT, or FREE_NODE. + !*/ + + typedef unsigned char node_label; + const node_label SOURCE_CUT = 0; + const node_label SINK_CUT = 254; + const node_label FREE_NODE = 255; + +// ---------------------------------------------------------------------------------------- + + class flow_graph + { + /*! + WHAT THIS OBJECT REPRESENTS + This object represents a flow capacity graph for use with the + min_cut algorithm defined below. In particular, this object + is a kind of directed graph where the edge weights specify the + flow capacities. + + Note that there is no dlib::flow_graph object. What you are + looking at here is simply the interface definition for a graph + which can be used with the min_cut algorithm. You must implement + your own version of this object for the graph you wish to work with + and then pass it to the min_cut::operator() routine. + + It's also worth pointing out that this graph has symmetric edge + connections. That is, if there is an edge from node A to node B + then there must also be an edge from node B to node A. + !*/ + + public: + + class out_edge_iterator + { + /*! + WHAT THIS OBJECT REPRESENTS + This is a simple forward iterator for iterating over the neighbors + of a node in the graph. It also represents the fact that the neighbors + are on the end of an outgoing edge. That is, the edge represents + the amount of flow which can flow towards the neighbor. + !*/ + + public: + out_edge_iterator( + ); + /*! + ensures + - constructs an iterator in an undefined state. It can't + be used until assigned with a valid iterator. + !*/ + + out_edge_iterator( + const out_edge_iterator& item + ); + /*! + ensures + - #*this is a copy of item + !*/ + + out_edge_iterator& operator=( + const out_edge_iterator& item + ); + /*! + ensures + - #*this is a copy of item + - returns #*this + !*/ + + bool operator!= ( + const out_edge_iterator& item + ) const; + /*! + requires + - *this and item are iterators over the neighbors for the + same node. + ensures + - returns false if *this and item both reference the same + node in the graph and true otherwise. + !*/ + + out_edge_iterator& operator++( + ); + /*! + ensures + - advances *this to the next neighbor node. + - returns a reference to the updated *this + (i.e. this is the ++object form of the increment operator) + !*/ + }; + + class in_edge_iterator + { + /*! + WHAT THIS OBJECT REPRESENTS + This is a simple forward iterator for iterating over the neighbors + of a node in the graph. It also represents the fact that the neighbors + are on the end of an incoming edge. That is, the edge represents + the amount of flow which can flow out of the neighbor node. + !*/ + + public: + + in_edge_iterator( + ); + /*! + ensures + - constructs an iterator in an undefined state. It can't + be used until assigned with a valid iterator. + !*/ + + in_edge_iterator( + const in_edge_iterator& item + ); + /*! + ensures + - #*this is a copy of item + !*/ + + in_edge_iterator& operator=( + const in_edge_iterator& item + ); + /*! + ensures + - #*this is a copy of item + - returns #*this + !*/ + + bool operator!= ( + const in_edge_iterator& item + ) const; + /*! + requires + - *this and item are iterators over the neighbors for the + same node. + ensures + - returns false if *this and item both reference the same + node in the graph and true otherwise. + !*/ + + in_edge_iterator& operator++( + ); + /*! + ensures + - advances *this to the next neighbor node. + - returns a reference to the updated *this + (i.e. this is the ++object form of the increment operator) + !*/ + }; + + + + unsigned long number_of_nodes ( + ) const; + /*! + ensures + - returns the number of nodes in the graph. + !*/ + + out_edge_iterator out_begin( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns an iterator pointing to the first neighboring node of + the idx-th node. If no such node exists then returns out_end(idx). + - The returned iterator also represents the directed edge going from + node idx to the neighbor. + !*/ + + in_edge_iterator in_begin( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns an iterator pointing to the first neighboring node of + the idx-th node. If no such node exists then returns in_end(idx). + - The returned iterator also represents the directed edge going from + the neighbor to node idx. + !*/ + + out_edge_iterator out_end( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns an iterator to one past the last neighboring node of + the idx-th node. + !*/ + + in_edge_iterator in_end( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns an iterator to one past the last neighboring node of + the idx-th node. + !*/ + + + unsigned long node_id ( + const out_edge_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [out_begin(idx), out_end(idx)) + for some valid idx) + ensures + - returns a number IDX such that: + - 0 <= IDX < number_of_nodes() + - IDX == The index which uniquely identifies the node pointed to by the + iterator it. This number can be used with any member function in this + object which expect a node index. (e.g. get_label(IDX) == the label for the + node pointed to by it) + !*/ + + unsigned long node_id ( + const in_edge_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [in_begin(idx), in_end(idx)) + for some valid idx) + ensures + - returns a number IDX such that: + - 0 <= IDX < number_of_nodes() + - IDX == The index which uniquely identifies the node pointed to by the + iterator it. This number can be used with any member function in this + object which expect a node index. (e.g. get_label(IDX) == the label for the + node pointed to by it) + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type edge_type; + + edge_type get_flow ( + const unsigned long& idx1, + const unsigned long& idx2 + ) const; + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + - idx1 and idx2 are neighbors in the graph + ensures + - returns the residual flow capacity from the idx1-th node to the idx2-th node. + - It is valid for this function to return a floating point value of infinity. + This value means this edge has an unlimited capacity. + !*/ + + edge_type get_flow ( + const out_edge_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [out_begin(idx), out_end(idx)) + for some valid idx) + ensures + - let IDX = node_id(it) + - it represents the directed edge from a node, call it H, to the node IDX. Therefore, + this function returns get_flow(H,IDX) + - It is valid for this function to return a floating point value of infinity. + This value means this edge has an unlimited capacity. + !*/ + + edge_type get_flow ( + const in_edge_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [in_begin(idx), in_end(idx)) + for some valid idx) + ensures + - let IDX = node_id(it) + - it represents the directed edge from node IDX to another node, call it H. Therefore, + this function returns get_flow(IDX,H) + - It is valid for this function to return a floating point value of infinity. + This value means this edge has an unlimited capacity. + !*/ + + void adjust_flow ( + const unsigned long& idx1, + const unsigned long& idx2, + const edge_type& value + ); + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + - idx1 and idx2 are neighbors in the graph + ensures + - #get_flow(idx1,idx2) == get_flow(idx1,idx2) + value + - #get_flow(idx2,idx1) == get_flow(idx2,idx1) - value + !*/ + + void set_label ( + const unsigned long& idx, + node_label value + ); + /*! + requires + - idx < number_of_nodes() + ensures + - #get_label(idx) == value + !*/ + + node_label get_label ( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns the label for the idx-th node in the graph. + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename flow_graph + > + typename flow_graph::edge_type graph_cut_score ( + const flow_graph& g + ); + /*! + requires + - flow_graph == an object with an interface compatible with the flow_graph + object defined at the top of this file, or, an implementation of + dlib/directed_graph/directed_graph_kernel_abstract.h. + ensures + - returns the sum of the outgoing flows from nodes with a label of SOURCE_CUT + to nodes with a label != SOURCE_CUT. Note that for a directed_graph object, + the labels are stored in the node's data field. + !*/ + +// ---------------------------------------------------------------------------------------- + + class min_cut + { + /*! + WHAT THIS OBJECT REPRESENTS + This is a function object which can be used to find the min cut + on a graph. + + The implementation is based on the method described in the following + paper: + An Experimental Comparison of Min-Cut/Max-Flow Algorithms for + Energy Minimization in Vision, by Yuri Boykov and Vladimir Kolmogorov, + in PAMI 2004. + + !*/ + + public: + + min_cut( + ); + /*! + ensures + - this object is properly initialized + !*/ + + template < + typename flow_graph + > + void operator() ( + flow_graph& g, + const unsigned long source_node, + const unsigned long sink_node + ) const; + /*! + requires + - flow_graph == an object with an interface compatible with the flow_graph + object defined at the top of this file. + - source_node != sink_node + - source_node < g.number_of_nodes() + - sink_node < g.number_of_nodes() + - for all valid i and j: + - g.get_flow(i,j) >= 0 + (i.e. all the flow capacities/edge weights are non-negative) + - g does not contain any self loops. That is, no nodes are neighbors with + themselves. + ensures + - Finds the minimum cut on the given graph. That is, this function finds + a labeling of nodes in g such that graph_cut_score(g) would be minimized. Note + that the flow values in #g are modified by this algorithm so if you want + to obtain the min cut score you must call min_cut::operator(), then copy + the flow values back into #g, and then call graph_cut_score(#g). But in most + cases you don't care about the value of the min cut score, rather, you + just want the labels in #g. + - #g.get_label(source_node) == SOURCE_CUT + - #g.get_label(sink_node) == SINK_CUT + - for all valid i: + - #g.get_label(i) == SOURCE_CUT, SINK_CUT, or FREE_NODE + - if (#g.get_label(i) == SOURCE_CUT) then + - The minimum cut of g places node i into the source side of the cut. + - if (#g.get_label(i) == SINK_CUT) then + - The minimum cut of g places node i into the sink side of the cut. + - if (#g.get_label(i) == FREE_NODE) then + - Node i can be labeled SOURCE_CUT or SINK_CUT. Both labelings + result in the same cut score. + - When interpreting g as a graph of flow capacities from the source_node + to the sink_node we can say that the min cut problem is equivalent to + the max flow problem. This equivalent problem is to find out how to push + as much "flow" from the source node to the sink node as possible. + Upon termination, #g will contain the final flow residuals in addition to + the graph cut labels. That is, for all valid i and j: + - #g.get_flow(i,j) == the residual flow capacity left after the max + possible amount of flow is passing from the source node to the sink + node. For example, this means that #g.get_flow(i,j) == 0 whenever + node i is in the SOURCE_CUT and j is in the SINK_CUT. + - #g.get_flow(i,j) >= 0 + !*/ + + template < + typename directed_graph + > + void operator() ( + directed_graph& g, + const unsigned long source_node, + const unsigned long sink_node + ) const; + /*! + requires + - directed_graph == an implementation of dlib/directed_graph/directed_graph_kernel_abstract.h + - directed_graph::type == node_label + - directed_graph::edge_type == and integer or double type + - source_node != sink_node + - source_node < g.number_of_nodes() + - sink_node < g.number_of_nodes() + - for all valid i and j: + - edge(g,i,j) >= 0 + (i.e. all the flow capacities/edge weights are positive) + - graph_contains_length_one_cycle(g) == false + - graph_has_symmetric_edges(g) == true + ensures + - This routine simply converts g into a flow graph and calls the version + of operator() defined above. Note that the conversion is done in O(1) + time, it's just an interface adaptor. + - edge weights in g correspond to network flows while the .data field of + each node in g corresponds to the graph node labels. + - upon termination, the flows and labels in g will have been modified + as described in the above operator() routine. + !*/ + }; + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_MIN_CuT_ABSTRACT_Hh_ + + |