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, 0 insertions, 3309 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 deleted file mode 100644 index f035442bf..000000000 --- a/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts.h +++ /dev/null @@ -1,959 +0,0 @@ -// 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 deleted file mode 100644 index 69aa59256..000000000 --- a/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h +++ /dev/null @@ -1,636 +0,0 @@ -// 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 deleted file mode 100644 index d0b93e311..000000000 --- a/ml/dlib/dlib/graph_cuts/general_flow_graph.h +++ /dev/null @@ -1,172 +0,0 @@ -// 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 deleted file mode 100644 index ebedbc572..000000000 --- a/ml/dlib/dlib/graph_cuts/general_potts_problem.h +++ /dev/null @@ -1,99 +0,0 @@ -// 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 deleted file mode 100644 index 34c3fcb5e..000000000 --- a/ml/dlib/dlib/graph_cuts/graph_labeler.h +++ /dev/null @@ -1,211 +0,0 @@ -// 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 deleted file mode 100644 index a0821b696..000000000 --- a/ml/dlib/dlib/graph_cuts/graph_labeler_abstract.h +++ /dev/null @@ -1,185 +0,0 @@ -// 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 deleted file mode 100644 index 6bbb57608..000000000 --- a/ml/dlib/dlib/graph_cuts/min_cut.h +++ /dev/null @@ -1,571 +0,0 @@ -// 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 deleted file mode 100644 index 748aca950..000000000 --- a/ml/dlib/dlib/graph_cuts/min_cut_abstract.h +++ /dev/null @@ -1,476 +0,0 @@ -// 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_ - - |