diff options
Diffstat (limited to 'ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h')
| -rw-r--r-- | ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h | 636 |
1 files changed, 636 insertions, 0 deletions
diff --git a/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h new file mode 100644 index 000000000..69aa59256 --- /dev/null +++ b/ml/dlib/dlib/graph_cuts/find_max_factor_graph_potts_abstract.h @@ -0,0 +1,636 @@ +// Copyright (C) 2012 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ +#ifdef DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ + +#include "../matrix.h" +#include "min_cut_abstract.h" +#include "../graph_utils.h" +#include "../array2d/array2d_kernel_abstract.h" + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + class potts_problem + { + /*! + WHAT THIS OBJECT REPRESENTS + This object represents a boolean valued factor graph or graphical model + that can be efficiently operated on using graph cuts. In particular, this + object defines the interface a MAP problem on a factor graph must + implement if it is to be solved using the find_max_factor_graph_potts() + routine defined at the bottom of this file. + + Note that there is no dlib::potts_problem object. What you are looking + at here is simply the interface definition for a Potts problem. You must + implement your own version of this object for the problem you wish to + solve and then pass it to the find_max_factor_graph_potts() routine. + + Note also that a factor graph should not have any nodes which are + neighbors with themselves. Additionally, the graph is undirected. This + mean that if A is a neighbor of B then B must be a neighbor of A for + the MAP problem to be valid. + !*/ + + public: + + unsigned long number_of_nodes ( + ) const; + /*! + ensures + - returns the number of nodes in the factor graph. Or in other words, + returns the number of variables in the MAP problem/Potts model. + !*/ + + unsigned long number_of_neighbors ( + unsigned long idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns the number of neighbors of node idx. + !*/ + + // This is an optional variable which specifies a number that is always + // greater than or equal to number_of_neighbors(idx). If you don't know + // the value at compile time then either don't include max_number_of_neighbors + // in your potts_problem object or set it to 0. + const static unsigned long max_number_of_neighbors = 0; + + unsigned long get_neighbor ( + unsigned long idx, + unsigned long n + ) const; + /*! + requires + - idx < number_of_nodes() + - n < number_of_neighbors(idx) + ensures + - returns the node index value of the n-th neighbor of + the node with index value idx. + - The neighbor relationship is reciprocal. That is, if + get_neighbor(A,i)==B then there is a value of j such + that get_neighbor(B,j)==A. + - A node is never its own neighbor. That is, there is + no i such that get_neighbor(idx,i)==idx. + !*/ + + unsigned long get_neighbor_idx ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + ensures + - This function is basically the inverse of get_neighbor(). + - returns a number IDX such that: + - get_neighbor(idx1,IDX) == idx2 + - IDX < number_of_neighbors(idx1) + !*/ + + void set_label ( + const unsigned long& idx, + node_label value + ); + /*! + requires + - idx < number_of_nodes() + ensures + - #get_label(idx) == value + !*/ + + node_label get_label ( + const unsigned long& idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns the current label for the idx-th node. This is a value which is + 0 if the node's label is false and is any other value if it is true. + + Note that this value is not used by factor_value() or factor_value_disagreement(). + It is simply here to provide a mechanism for find_max_factor_graph_potts() + to return its labeled result. Additionally, the reason it returns a + node_label rather than a bool is because doing it this way facilitates + use of a graph cut algorithm for the solution of the MAP problem. For + more of an explanation you should read the paper referenced by the min_cut + object. + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + value_type factor_value ( + unsigned long idx + ) const; + /*! + requires + - idx < number_of_nodes() + ensures + - returns a value which indicates how "good" it is to assign the idx-th + node the label of true. The larger the value, the more desirable it is + to give it this label. Similarly, a negative value indicates that it is + better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the idx-th node must be labeled + true while negative infinity means it must be labeled false. + !*/ + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < number_of_nodes() + - idx2 < number_of_nodes() + - idx1 != idx2 + - the idx1-th node and idx2-th node are neighbors in the graph. That is, + get_neighbor(idx1,i)==idx2 for some value of i. + ensures + - returns a number >= 0. This is the penalty for giving node idx1 and idx2 + different labels. Larger values indicate a larger penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + class potts_grid_problem + { + /*! + WHAT THIS OBJECT REPRESENTS + This object is a specialization of a potts_problem to the case where + the graph is a regular grid where each node is connected to its four + neighbors. An example of this is an image where each pixel is a node + and is connected to its four immediate neighboring pixels. Therefore, + this object defines the interface this special kind of MAP problem + must implement if it is to be solved by the find_max_factor_graph_potts(potts_grid_problem,array2d) + routine defined at the end of this file. + + + Note that all nodes always have four neighbors, even nodes on the edge + of the graph. This is because these border nodes are connected to + the border nodes on the other side of the graph. That is, the graph + "wraps" around at the borders. + !*/ + + public: + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + long nr( + ) const; + /*! + ensures + - returns the number of rows in the grid + !*/ + + long nc( + ) const; + /*! + ensures + - returns the number of columns in the grid + !*/ + + value_type factor_value ( + unsigned long idx + ) const; + /*! + requires + - idx < nr()*nc() + ensures + - The grid is represented in row-major-order format. Therefore, idx + identifies a node according to its position in the row-major-order + representation of the grid graph. Or in other words, idx corresponds + to the following row and column location in the graph: + - row == idx/nc() + - col == idx%nc() + - returns a value which indicates how "good" it is to assign the idx-th + node the label of true. The larger the value, the more desirable it is + to give it this label. Similarly, a negative value indicates that it is + better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the idx-th node must be labeled + true while negative infinity means it must be labeled false. + !*/ + + value_type factor_value_disagreement ( + unsigned long idx1, + unsigned long idx2 + ) const; + /*! + requires + - idx1 < nr()*nc() + - idx2 < nr()*nc() + - idx1 != idx2 + - the idx1-th node and idx2-th node are neighbors in the grid graph. + ensures + - The grid is represented in row-major-order format. Therefore, idx1 and + idx2 identify nodes according to their positions in the row-major-order + representation of the grid graph. For example, idx1 corresponds + to the following row and column location in the graph: + - row == idx1/nc() + - col == idx1%nc() + - returns a number >= 0. This is the penalty for giving node idx1 and idx2 + different labels. Larger values indicate a larger penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + typename potts_problem::value_type potts_model_score ( + const potts_problem& prob + ); + /*! + requires + - potts_problem == an object with an interface compatible with the potts_problem + object defined at the top of this file. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - computes the model score for the given potts_problem. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in prob. Or in other + words, L(i) == (prob.get_label(i) != 0). + - let F == the sum of values of prob.factor_value(i) for only i values + where L(i) == true. + - Let D == the sum of values of prob.factor_value_disagreement(i,j) + for only i and j values which meet the following conditions: + - i and j are neighbors in the graph defined by prob, that is, + it is valid to call prob.factor_value_disagreement(i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + typename graph_type::edge_type potts_model_score ( + const graph_type& g, + const std::vector<node_label>& labels + ); + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_type::edge_type is some signed type such as int or double + - graph_type::type must be the same type as graph_type::edge_type + - graph_contains_length_one_cycle(g) == false + - for all valid i and j: + - edge(g,i,j) >= 0 + ensures + - This function does the same thing as the version of potts_model_score() + defined above, except that this version operates on a dlib::graph + instead of a potts_problem object. + - computes the model score for the given graph and labeling. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in g. Or in other + words, L(i) == (labels[i] != 0). + - let F == the sum of values of g.node(i).data for only i values + where L(i) == true. + - Let D == the sum of values of edge(g,i,j) for only i and j + values which meet the following conditions: + - i and j are neighbors in the graph defined by g, that is, + it is valid to call edge(g,i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + typename potts_grid_problem::value_type potts_model_score ( + const potts_grid_problem& prob, + const array2d<node_label,mem_manager>& labels + ); + /*! + requires + - prob.nr() == labels.nr() + - prob.nc() == labels.nc() + - potts_grid_problem == an object with an interface compatible with the + potts_grid_problem object defined above. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - computes the model score for the given potts_grid_problem. We define this + precisely below: + - let L(i) == the boolean label of the i-th variable in prob. Or in other + words, L(i) == (labels[i/labels.nc()][i%labels.nc()] != 0). + - let F == the sum of values of prob.factor_value(i) for only i values + where L(i) == true. + - Let D == the sum of values of prob.factor_value_disagreement(i,j) + for only i and j values which meet the following conditions: + - i and j are neighbors in the graph defined by prob, that is, + it is valid to call prob.factor_value_disagreement(i,j). + - L(i) != L(j) + - i < j + (i.e. We want to make sure to only count the edge between i and j once) + + - Then this function returns F - D + !*/ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename potts_problem + > + void find_max_factor_graph_potts ( + potts_problem& prob + ); + /*! + requires + - potts_problem == an object with an interface compatible with the potts_problem + object defined at the top of this file. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - This function is a tool for exactly solving the MAP problem in a Potts + model. In particular, this means that this function finds the assignments + to all the labels in prob which maximizes potts_model_score(#prob). + - The optimal labels are stored in #prob. + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename graph_type + > + void find_max_factor_graph_potts ( + const graph_type& g, + std::vector<node_label>& labels + ); + /*! + requires + - graph_type is an implementation of dlib/graph/graph_kernel_abstract.h + - graph_type::edge_type is some signed type such as int or double + - graph_type::type must be the same type as graph_type::edge_type + - graph_contains_length_one_cycle(g) == false + - for all valid i and j: + - edge(g,i,j) >= 0 + ensures + - This routine simply converts g into a potts_problem and calls the + version of find_max_factor_graph_potts() defined above on it. Therefore, + this routine is just a convenience wrapper that lets you use a dlib::graph + to represent a potts problem. This means that this function maximizes + the value of potts_model_score(g, #labels). + - #labels.size() == g.number_of_nodes() + - for all valid i: + - #labels[i] == the optimal label for g.node(i) + - The correspondence between g and a potts_problem is the following: + - the factor_value() for a node is stored in g.node(i).data. + - the factor_value_disagreement(i,j) is stored in edge(g,i,j). + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename potts_grid_problem, + typename mem_manager + > + void find_max_factor_graph_potts ( + const potts_grid_problem& prob, + array2d<node_label,mem_manager>& labels + ); + /*! + requires + - potts_grid_problem == an object with an interface compatible with the + potts_grid_problem object defined above. + - for all valid i and j: + - prob.factor_value_disagreement(i,j) >= 0 + - prob.factor_value_disagreement(i,j) == prob.factor_value_disagreement(j,i) + ensures + - This routine solves a version of a potts problem where the graph is a + regular grid where each node is connected to its four immediate neighbors. + In particular, this means that this function finds the assignments + to all the labels in prob which maximizes potts_model_score(prob,#labels). + - The optimal labels are stored in #labels. + - #labels.nr() == prob.nr() + - #labels.nc() == prob.nc() + !*/ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- +// The following functions and interface definitions are convenience routines for use +// with the potts grid problem version of find_max_factor_graph_potts() defined above. +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + struct single_image_model + { + /*! + WHAT THIS OBJECT REPRESENTS + This object defines a slightly more convenient interface for creating + potts_grid_problems which operate on an image. In this case, the goal + is to assign a binary label to each pixel in an image. In particular, + this object defines the interface used by the make_potts_grid_problem() + routine defined below. + + In the following comments, we will refer to the image supplied to + make_potts_grid_problem() as IMG. + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + template <typename pixel_type> + value_type factor_value ( + const pixel_type& v + ) const; + /*! + requires + - v is a pixel value from IMG. + ensures + - returns a value which indicates how "good" it is to assign the location + in IMG corresponding to v with the label of true. The larger the value, + the more desirable it is to give it this label. Similarly, a negative + value indicates that it is better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the pixel must be labeled + true while negative infinity means it must be labeled false. + !*/ + + template <typename pixel_type> + value_type factor_value_disagreement ( + const pixel_type& v1, + const pixel_type& v2 + ) const; + /*! + requires + - v1 and v2 are pixel values from neighboring pixels in the IMG image. + ensures + - returns a number >= 0. This is the penalty for giving neighboring pixels + with values v1 and v2 different labels. Larger values indicate a larger + penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- + + struct pair_image_model + { + /*! + WHAT THIS OBJECT REPRESENTS + This object defines a slightly more convenient interface for creating + potts_grid_problems which operate on a pair of identically sized images. + In this case, the goal is to assign a label to each pixel in the first + image of the pair. In particular, this object defines the interface + used by the make_potts_grid_problem() routine defined below. + + In the following comments, we will refer to the two images supplied to + make_potts_grid_problem() as IMG1 and IMG2. The goal of the potts + problem will be to assign labels to each pixel in IMG1 (IMG2 is + not labeled, it is simply used as a place to keep auxiliary data). + !*/ + + // This typedef should be for a type like int or double. It + // must also be capable of representing signed values. + typedef an_integer_or_real_type value_type; + + template <typename pixel_type1, typename pixel_type2> + value_type factor_value ( + const pixel_type1& v1, + const pixel_type2& v2 + ) const; + /*! + requires + - v1 and v2 are corresponding pixels from IMG1 and IMG2 respectively. + That is, both pixel values have the same coordinates in the images. + So for example, if v1 is the value of IMG1[4][5] then v2 is the value + of IMG2[4][5]. + ensures + - returns a value which indicates how "good" it is to assign the location + in IMG1 corresponding to v1 with the label of true. The larger the value, + the more desirable it is to give it this label. Similarly, a negative + value indicates that it is better to give the node a label of false. + - It is valid for the returned value to be positive or negative infinity. + A value of positive infinity indicates that the pixel must be labeled + true while negative infinity means it must be labeled false. + !*/ + + template <typename pixel_type> + value_type factor_value_disagreement ( + const pixel_type& v1, + const pixel_type& v2 + ) const; + /*! + requires + - v1 and v2 are pixel values from neighboring pixels in the IMG1 image. + ensures + - returns a number >= 0. This is the penalty for giving neighboring pixels + with values v1 and v2 different labels. Larger values indicate a larger + penalty. + - this function is symmetric. That is, it is true that: + factor_value_disagreement(i,j) == factor_value_disagreement(j,i) + - It is valid for the returned value to be positive infinity. Returning + infinity indicates that the idx1-th and idx2-th nodes must share the same + label. + !*/ + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename single_image_model, + typename pixel_type, + typename mem_manager + > + potts_grid_problem make_potts_grid_problem ( + const single_image_model& model, + const array2d<pixel_type,mem_manager>& img + ); + /*! + requires + - single_image_model == an object with an interface compatible with the + single_image_model object defined above. + - for all valid i and j: + - model.factor_value_disagreement(i,j) >= 0 + - model.factor_value_disagreement(i,j) == model.factor_value_disagreement(j,i) + ensures + - returns a potts_grid_problem which can be solved using the + find_max_factor_graph_potts(prob,array2d) routine defined above. That is, + given an image to store the labels, the following statement would solve the + potts problem defined by the given model and image: + find_max_factor_graph_potts(make_potts_grid_problem(model,img),labels); + !*/ + +// ---------------------------------------------------------------------------------------- + + template < + typename pair_image_model, + typename pixel_type1, + typename pixel_type2, + typename mem_manager + > + potts_grid_problem make_potts_grid_problem ( + const pair_image_model& model, + const array2d<pixel_type1,mem_manager>& img1, + const array2d<pixel_type2,mem_manager>& img2 + ); + /*! + requires + - get_rect(img1) == get_rect(img2) + (i.e. img1 and img2 have the same dimensions) + - pair_image_model == an object with an interface compatible with the + pair_image_model object defined above. + - for all valid i and j: + - model.factor_value_disagreement(i,j) >= 0 + - model.factor_value_disagreement(i,j) == model.factor_value_disagreement(j,i) + ensures + - returns a potts_grid_problem which can be solved using the + find_max_factor_graph_potts(prob,array2d) routine defined above. That is, + given an image to store the labels, the following statement would solve the + potts problem defined by the given model and pair of images: + find_max_factor_graph_potts(make_potts_grid_problem(model,img1,img2),labels); + !*/ + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_FIND_MAX_FACTOR_GRAPH_PoTTS_ABSTRACT_Hh_ + + |