|
|
latest version v1.9 - last update 10 Apr 2010 |
|
Multiclass normalized cuts. More...
#include <ltiMulticlassNormalizedCuts.h>
Classes | |
| class | parameters |
| the parameters for the class multiclassNormalizedCuts More... | |
Public Member Functions | |
| multiclassNormalizedCuts () | |
| multiclassNormalizedCuts (const parameters &par) | |
| multiclassNormalizedCuts (const multiclassNormalizedCuts &other) | |
| virtual | ~multiclassNormalizedCuts () |
| virtual const char * | getTypeName () const |
| bool | apply (const dmatrix &weights, ivector &xstar) const |
| bool | apply (const int k, const dmatrix &weights, ivector &xstar) const |
| bool | apply (const int k, const dmatrix &weights, const dvector °ree, ivector &xstar) const |
| multiclassNormalizedCuts & | copy (const multiclassNormalizedCuts &other) |
| multiclassNormalizedCuts & | operator= (const multiclassNormalizedCuts &other) |
| virtual functor * | clone () const |
| const parameters & | getParameters () const |
Protected Member Functions | |
| bool | kWayNormalizedCut (const dmatrix &W, const dvector &D, const int k, ivector &Xstar) const |
| void | computeDegree (const dmatrix &W, dvector &D) const |
Multiclass normalized cuts.
This class implements the k-ways normalized cuts algorithm proposed by Stella Yu in:
S. Yu, "Computational Models of Perceptual Organization". Ph.D Thesis, Carnegie Mellon University, May 2003.
The algorithm is general enough to be applied to any graph partitioning problem given the affinity matrix w, which contains the weights between each two nodes. It must be symmetric (and obviously square) and its values must be greater of equal zero.
The weights denote usually similarity measures (and not distances) between two nodes.
The output of the algorithm is an integer vector with labels for each of the n nodes of the graph, corresponding to the indices of the vectors in the affinity matrix.
If you compiled the LTI-Lib with LAPACK support, this vector will work much faster than without. This is because it makes use of an eigensolution functor and the singular value decomposition functor, which are both efficiently computed by the LAPACK.
| lti::multiclassNormalizedCuts::multiclassNormalizedCuts | ( | ) |
default constructor
| lti::multiclassNormalizedCuts::multiclassNormalizedCuts | ( | const parameters & | par | ) |
Construct a functor using the given parameters.
| lti::multiclassNormalizedCuts::multiclassNormalizedCuts | ( | const multiclassNormalizedCuts & | other | ) |
copy constructor
| other | the object to be copied |
| virtual lti::multiclassNormalizedCuts::~multiclassNormalizedCuts | ( | ) | [virtual] |
destructor
| bool lti::multiclassNormalizedCuts::apply | ( | const int | k, | |
| const dmatrix & | weights, | |||
| const dvector & | degree, | |||
| ivector & | xstar | |||
| ) | const |
Compute the k-way partitioning of a graph with affinity matrix "weights".
| k | number of classes to be found, i.e. k subgraphs will be detected. | |
| weights | the affinity matrix containing the weights between each two nodes of the graph. This square matrix must also be symmetric. The elements must be positive or equal zero, and correspond to similarity metrics (not distance metrics). In the original paper is denoted with W | |
| degree | the degree vector, defined as the sum of elements of each row of the weights. | |
| xstar | (X* in the paper) is a vector containing the label of each node. The values will be between 0 and k-1 where k is the value given as argument (the value k in the parameters object will be ignored). |
| bool lti::multiclassNormalizedCuts::apply | ( | const int | k, | |
| const dmatrix & | weights, | |||
| ivector & | xstar | |||
| ) | const |
Compute the k-way partitioning of a graph with affinity matrix "weights".
| k | number of classes to be found, i.e. k subgraphs will be detected. | |
| weights | the affinity matrix containing the weights between each two nodes of the graph. This square matrix must also be symmetric. The elements must be positive or equal zero, and correspond to similarity metrics (not distance metrics). In the original paper is denoted with W | |
| xstar | (X* in the paper) is a vector containing the label of each node. The values will be between 0 and k-1 where k is the value given as argument (the value k in the parameters object will be ignored). |
Compute the k-way partitioning of a graph with affinity matrix "weights".
| weights | the affinity matrix containing the weights between each two nodes of the graph. This square matrix must also be symmetric. The elements weights.at(i,j) denote the similarity between the nodes i and j and must be positive or equal zero. Please note that this are similarity metrics and not distance metrics. In the original paper is denoted with W. | |
| xstar | (X* in the paper) is a vector containing the label of each node. Each values will be between 0 and k-1, where k is the value given in the parameters object. |
| virtual functor* lti::multiclassNormalizedCuts::clone | ( | ) | const [virtual] |
returns a pointer to a clone of this functor.
Implements lti::functor.
| multiclassNormalizedCuts& lti::multiclassNormalizedCuts::copy | ( | const multiclassNormalizedCuts & | other | ) |
copy data of "other" functor.
| other | the functor to be copied |
Reimplemented from lti::functor.
| const parameters& lti::multiclassNormalizedCuts::getParameters | ( | ) | const |
returns used parameters
Reimplemented from lti::functor.
| virtual const char* lti::multiclassNormalizedCuts::getTypeName | ( | ) | const [virtual] |
returns the name of this type ("multiclassNormalizedCuts")
Reimplemented from lti::functor.
| bool lti::multiclassNormalizedCuts::kWayNormalizedCut | ( | const dmatrix & | W, | |
| const dvector & | D, | |||
| const int | k, | |||
| ivector & | Xstar | |||
| ) | const [protected] |
Merge regions using the "k-Way normalized cuts" method of Stella Yu (See S.
Yu "Computational Models of Perceptual Organization" Tech. Report CMU-RI-TR-03-14, Carnegie Mellon University, May 2003.
The main difference with the original paper is that the graph is not formed of single connected pixels, but regions using a simpler faster method to over-partition the image.
The resulting regions mask will contain only k labels.
| W | the weights matrix (or affinity matrix) containing the weight (similarity and NOT distance) between each to nodes of the graph representation. | |
| D | degree vector containing the sum of elements of each row of W | |
| k | number of classes the final partition should have. | |
| Xstar | the resulting vector contains for each corresponding node a label name (from 0 to k-1) for the corresponding label. |
| multiclassNormalizedCuts& lti::multiclassNormalizedCuts::operator= | ( | const multiclassNormalizedCuts & | other | ) |