Joe Verbout / Mbed 2 deprecated main

opencv on mbed

Dependencies:   mbed

opencv2/core/optim.hpp@0:ea44dc9ed014, 2016-03-31 (annotated)

Committer:
joeverbout
Date:
Thu Mar 31 21:16:38 2016 +0000
Revision:
0:ea44dc9ed014
OpenCV on mbed attempt

Who changed what in which revision?

UserRevisionLine numberNew contents of line
joeverbout 0:ea44dc9ed014 1 /*M///////////////////////////////////////////////////////////////////////////////////////
joeverbout 0:ea44dc9ed014 2 //
joeverbout 0:ea44dc9ed014 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
joeverbout 0:ea44dc9ed014 4 //
joeverbout 0:ea44dc9ed014 5 // By downloading, copying, installing or using the software you agree to this license.
joeverbout 0:ea44dc9ed014 6 // If you do not agree to this license, do not download, install,
joeverbout 0:ea44dc9ed014 7 // copy or use the software.
joeverbout 0:ea44dc9ed014 8 //
joeverbout 0:ea44dc9ed014 9 //
joeverbout 0:ea44dc9ed014 10 // License Agreement
joeverbout 0:ea44dc9ed014 11 // For Open Source Computer Vision Library
joeverbout 0:ea44dc9ed014 12 //
joeverbout 0:ea44dc9ed014 13 // Copyright (C) 2013, OpenCV Foundation, all rights reserved.
joeverbout 0:ea44dc9ed014 14 // Third party copyrights are property of their respective owners.
joeverbout 0:ea44dc9ed014 15 //
joeverbout 0:ea44dc9ed014 16 // Redistribution and use in source and binary forms, with or without modification,
joeverbout 0:ea44dc9ed014 17 // are permitted provided that the following conditions are met:
joeverbout 0:ea44dc9ed014 18 //
joeverbout 0:ea44dc9ed014 19 // * Redistribution's of source code must retain the above copyright notice,
joeverbout 0:ea44dc9ed014 20 // this list of conditions and the following disclaimer.
joeverbout 0:ea44dc9ed014 21 //
joeverbout 0:ea44dc9ed014 22 // * Redistribution's in binary form must reproduce the above copyright notice,
joeverbout 0:ea44dc9ed014 23 // this list of conditions and the following disclaimer in the documentation
joeverbout 0:ea44dc9ed014 24 // and/or other materials provided with the distribution.
joeverbout 0:ea44dc9ed014 25 //
joeverbout 0:ea44dc9ed014 26 // * The name of the copyright holders may not be used to endorse or promote products
joeverbout 0:ea44dc9ed014 27 // derived from this software without specific prior written permission.
joeverbout 0:ea44dc9ed014 28 //
joeverbout 0:ea44dc9ed014 29 // This software is provided by the copyright holders and contributors "as is" and
joeverbout 0:ea44dc9ed014 30 // any express or implied warranties, including, but not limited to, the implied
joeverbout 0:ea44dc9ed014 31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
joeverbout 0:ea44dc9ed014 32 // In no event shall the OpenCV Foundation or contributors be liable for any direct,
joeverbout 0:ea44dc9ed014 33 // indirect, incidental, special, exemplary, or consequential damages
joeverbout 0:ea44dc9ed014 34 // (including, but not limited to, procurement of substitute goods or services;
joeverbout 0:ea44dc9ed014 35 // loss of use, data, or profits; or business interruption) however caused
joeverbout 0:ea44dc9ed014 36 // and on any theory of liability, whether in contract, strict liability,
joeverbout 0:ea44dc9ed014 37 // or tort (including negligence or otherwise) arising in any way out of
joeverbout 0:ea44dc9ed014 38 // the use of this software, even if advised of the possibility of such damage.
joeverbout 0:ea44dc9ed014 39 //
joeverbout 0:ea44dc9ed014 40 //M*/
joeverbout 0:ea44dc9ed014 41
joeverbout 0:ea44dc9ed014 42 #ifndef __OPENCV_OPTIM_HPP__
joeverbout 0:ea44dc9ed014 43 #define __OPENCV_OPTIM_HPP__
joeverbout 0:ea44dc9ed014 44
joeverbout 0:ea44dc9ed014 45 #include "opencv2/core.hpp"
joeverbout 0:ea44dc9ed014 46
joeverbout 0:ea44dc9ed014 47 namespace cv
joeverbout 0:ea44dc9ed014 48 {
joeverbout 0:ea44dc9ed014 49
joeverbout 0:ea44dc9ed014 50 /** @addtogroup core_optim
joeverbout 0:ea44dc9ed014 51 The algorithms in this section minimize or maximize function value within specified constraints or
joeverbout 0:ea44dc9ed014 52 without any constraints.
joeverbout 0:ea44dc9ed014 53 @{
joeverbout 0:ea44dc9ed014 54 */
joeverbout 0:ea44dc9ed014 55
joeverbout 0:ea44dc9ed014 56 /** @brief Basic interface for all solvers
joeverbout 0:ea44dc9ed014 57 */
joeverbout 0:ea44dc9ed014 58 class CV_EXPORTS MinProblemSolver : public Algorithm
joeverbout 0:ea44dc9ed014 59 {
joeverbout 0:ea44dc9ed014 60 public:
joeverbout 0:ea44dc9ed014 61 /** @brief Represents function being optimized
joeverbout 0:ea44dc9ed014 62 */
joeverbout 0:ea44dc9ed014 63 class CV_EXPORTS Function
joeverbout 0:ea44dc9ed014 64 {
joeverbout 0:ea44dc9ed014 65 public:
joeverbout 0:ea44dc9ed014 66 virtual ~Function() {}
joeverbout 0:ea44dc9ed014 67 virtual int getDims() const = 0;
joeverbout 0:ea44dc9ed014 68 virtual double getGradientEps() const;
joeverbout 0:ea44dc9ed014 69 virtual double calc(const double* x) const = 0;
joeverbout 0:ea44dc9ed014 70 virtual void getGradient(const double* x,double* grad);
joeverbout 0:ea44dc9ed014 71 };
joeverbout 0:ea44dc9ed014 72
joeverbout 0:ea44dc9ed014 73 /** @brief Getter for the optimized function.
joeverbout 0:ea44dc9ed014 74
joeverbout 0:ea44dc9ed014 75 The optimized function is represented by Function interface, which requires derivatives to
joeverbout 0:ea44dc9ed014 76 implement the sole method calc(double*) to evaluate the function.
joeverbout 0:ea44dc9ed014 77
joeverbout 0:ea44dc9ed014 78 @return Smart-pointer to an object that implements Function interface - it represents the
joeverbout 0:ea44dc9ed014 79 function that is being optimized. It can be empty, if no function was given so far.
joeverbout 0:ea44dc9ed014 80 */
joeverbout 0:ea44dc9ed014 81 virtual Ptr<Function> getFunction() const = 0;
joeverbout 0:ea44dc9ed014 82
joeverbout 0:ea44dc9ed014 83 /** @brief Setter for the optimized function.
joeverbout 0:ea44dc9ed014 84
joeverbout 0:ea44dc9ed014 85 *It should be called at least once before the call to* minimize(), as default value is not usable.
joeverbout 0:ea44dc9ed014 86
joeverbout 0:ea44dc9ed014 87 @param f The new function to optimize.
joeverbout 0:ea44dc9ed014 88 */
joeverbout 0:ea44dc9ed014 89 virtual void setFunction(const Ptr<Function>& f) = 0;
joeverbout 0:ea44dc9ed014 90
joeverbout 0:ea44dc9ed014 91 /** @brief Getter for the previously set terminal criteria for this algorithm.
joeverbout 0:ea44dc9ed014 92
joeverbout 0:ea44dc9ed014 93 @return Deep copy of the terminal criteria used at the moment.
joeverbout 0:ea44dc9ed014 94 */
joeverbout 0:ea44dc9ed014 95 virtual TermCriteria getTermCriteria() const = 0;
joeverbout 0:ea44dc9ed014 96
joeverbout 0:ea44dc9ed014 97 /** @brief Set terminal criteria for solver.
joeverbout 0:ea44dc9ed014 98
joeverbout 0:ea44dc9ed014 99 This method *is not necessary* to be called before the first call to minimize(), as the default
joeverbout 0:ea44dc9ed014 100 value is sensible.
joeverbout 0:ea44dc9ed014 101
joeverbout 0:ea44dc9ed014 102 Algorithm stops when the number of function evaluations done exceeds termcrit.maxCount, when
joeverbout 0:ea44dc9ed014 103 the function values at the vertices of simplex are within termcrit.epsilon range or simplex
joeverbout 0:ea44dc9ed014 104 becomes so small that it can enclosed in a box with termcrit.epsilon sides, whatever comes
joeverbout 0:ea44dc9ed014 105 first.
joeverbout 0:ea44dc9ed014 106 @param termcrit Terminal criteria to be used, represented as cv::TermCriteria structure.
joeverbout 0:ea44dc9ed014 107 */
joeverbout 0:ea44dc9ed014 108 virtual void setTermCriteria(const TermCriteria& termcrit) = 0;
joeverbout 0:ea44dc9ed014 109
joeverbout 0:ea44dc9ed014 110 /** @brief actually runs the algorithm and performs the minimization.
joeverbout 0:ea44dc9ed014 111
joeverbout 0:ea44dc9ed014 112 The sole input parameter determines the centroid of the starting simplex (roughly, it tells
joeverbout 0:ea44dc9ed014 113 where to start), all the others (terminal criteria, initial step, function to be minimized) are
joeverbout 0:ea44dc9ed014 114 supposed to be set via the setters before the call to this method or the default values (not
joeverbout 0:ea44dc9ed014 115 always sensible) will be used.
joeverbout 0:ea44dc9ed014 116
joeverbout 0:ea44dc9ed014 117 @param x The initial point, that will become a centroid of an initial simplex. After the algorithm
joeverbout 0:ea44dc9ed014 118 will terminate, it will be setted to the point where the algorithm stops, the point of possible
joeverbout 0:ea44dc9ed014 119 minimum.
joeverbout 0:ea44dc9ed014 120 @return The value of a function at the point found.
joeverbout 0:ea44dc9ed014 121 */
joeverbout 0:ea44dc9ed014 122 virtual double minimize(InputOutputArray x) = 0;
joeverbout 0:ea44dc9ed014 123 };
joeverbout 0:ea44dc9ed014 124
joeverbout 0:ea44dc9ed014 125 /** @brief This class is used to perform the non-linear non-constrained minimization of a function,
joeverbout 0:ea44dc9ed014 126
joeverbout 0:ea44dc9ed014 127 defined on an `n`-dimensional Euclidean space, using the **Nelder-Mead method**, also known as
joeverbout 0:ea44dc9ed014 128 **downhill simplex method**. The basic idea about the method can be obtained from
joeverbout 0:ea44dc9ed014 129 <http://en.wikipedia.org/wiki/Nelder-Mead_method>.
joeverbout 0:ea44dc9ed014 130
joeverbout 0:ea44dc9ed014 131 It should be noted, that this method, although deterministic, is rather a heuristic and therefore
joeverbout 0:ea44dc9ed014 132 may converge to a local minima, not necessary a global one. It is iterative optimization technique,
joeverbout 0:ea44dc9ed014 133 which at each step uses an information about the values of a function evaluated only at `n+1`
joeverbout 0:ea44dc9ed014 134 points, arranged as a *simplex* in `n`-dimensional space (hence the second name of the method). At
joeverbout 0:ea44dc9ed014 135 each step new point is chosen to evaluate function at, obtained value is compared with previous
joeverbout 0:ea44dc9ed014 136 ones and based on this information simplex changes it's shape , slowly moving to the local minimum.
joeverbout 0:ea44dc9ed014 137 Thus this method is using *only* function values to make decision, on contrary to, say, Nonlinear
joeverbout 0:ea44dc9ed014 138 Conjugate Gradient method (which is also implemented in optim).
joeverbout 0:ea44dc9ed014 139
joeverbout 0:ea44dc9ed014 140 Algorithm stops when the number of function evaluations done exceeds termcrit.maxCount, when the
joeverbout 0:ea44dc9ed014 141 function values at the vertices of simplex are within termcrit.epsilon range or simplex becomes so
joeverbout 0:ea44dc9ed014 142 small that it can enclosed in a box with termcrit.epsilon sides, whatever comes first, for some
joeverbout 0:ea44dc9ed014 143 defined by user positive integer termcrit.maxCount and positive non-integer termcrit.epsilon.
joeverbout 0:ea44dc9ed014 144
joeverbout 0:ea44dc9ed014 145 @note DownhillSolver is a derivative of the abstract interface
joeverbout 0:ea44dc9ed014 146 cv::MinProblemSolver, which in turn is derived from the Algorithm interface and is used to
joeverbout 0:ea44dc9ed014 147 encapsulate the functionality, common to all non-linear optimization algorithms in the optim
joeverbout 0:ea44dc9ed014 148 module.
joeverbout 0:ea44dc9ed014 149
joeverbout 0:ea44dc9ed014 150 @note term criteria should meet following condition:
joeverbout 0:ea44dc9ed014 151 @code
joeverbout 0:ea44dc9ed014 152 termcrit.type == (TermCriteria::MAX_ITER + TermCriteria::EPS) && termcrit.epsilon > 0 && termcrit.maxCount > 0
joeverbout 0:ea44dc9ed014 153 @endcode
joeverbout 0:ea44dc9ed014 154 */
joeverbout 0:ea44dc9ed014 155 class CV_EXPORTS DownhillSolver : public MinProblemSolver
joeverbout 0:ea44dc9ed014 156 {
joeverbout 0:ea44dc9ed014 157 public:
joeverbout 0:ea44dc9ed014 158 /** @brief Returns the initial step that will be used in downhill simplex algorithm.
joeverbout 0:ea44dc9ed014 159
joeverbout 0:ea44dc9ed014 160 @param step Initial step that will be used in algorithm. Note, that although corresponding setter
joeverbout 0:ea44dc9ed014 161 accepts column-vectors as well as row-vectors, this method will return a row-vector.
joeverbout 0:ea44dc9ed014 162 @see DownhillSolver::setInitStep
joeverbout 0:ea44dc9ed014 163 */
joeverbout 0:ea44dc9ed014 164 virtual void getInitStep(OutputArray step) const=0;
joeverbout 0:ea44dc9ed014 165
joeverbout 0:ea44dc9ed014 166 /** @brief Sets the initial step that will be used in downhill simplex algorithm.
joeverbout 0:ea44dc9ed014 167
joeverbout 0:ea44dc9ed014 168 Step, together with initial point (givin in DownhillSolver::minimize) are two `n`-dimensional
joeverbout 0:ea44dc9ed014 169 vectors that are used to determine the shape of initial simplex. Roughly said, initial point
joeverbout 0:ea44dc9ed014 170 determines the position of a simplex (it will become simplex's centroid), while step determines the
joeverbout 0:ea44dc9ed014 171 spread (size in each dimension) of a simplex. To be more precise, if \f$s,x_0\in\mathbb{R}^n\f$ are
joeverbout 0:ea44dc9ed014 172 the initial step and initial point respectively, the vertices of a simplex will be:
joeverbout 0:ea44dc9ed014 173 \f$v_0:=x_0-\frac{1}{2} s\f$ and \f$v_i:=x_0+s_i\f$ for \f$i=1,2,\dots,n\f$ where \f$s_i\f$ denotes
joeverbout 0:ea44dc9ed014 174 projections of the initial step of *n*-th coordinate (the result of projection is treated to be
joeverbout 0:ea44dc9ed014 175 vector given by \f$s_i:=e_i\cdot\left<e_i\cdot s\right>\f$, where \f$e_i\f$ form canonical basis)
joeverbout 0:ea44dc9ed014 176
joeverbout 0:ea44dc9ed014 177 @param step Initial step that will be used in algorithm. Roughly said, it determines the spread
joeverbout 0:ea44dc9ed014 178 (size in each dimension) of an initial simplex.
joeverbout 0:ea44dc9ed014 179 */
joeverbout 0:ea44dc9ed014 180 virtual void setInitStep(InputArray step)=0;
joeverbout 0:ea44dc9ed014 181
joeverbout 0:ea44dc9ed014 182 /** @brief This function returns the reference to the ready-to-use DownhillSolver object.
joeverbout 0:ea44dc9ed014 183
joeverbout 0:ea44dc9ed014 184 All the parameters are optional, so this procedure can be called even without parameters at
joeverbout 0:ea44dc9ed014 185 all. In this case, the default values will be used. As default value for terminal criteria are
joeverbout 0:ea44dc9ed014 186 the only sensible ones, MinProblemSolver::setFunction() and DownhillSolver::setInitStep()
joeverbout 0:ea44dc9ed014 187 should be called upon the obtained object, if the respective parameters were not given to
joeverbout 0:ea44dc9ed014 188 create(). Otherwise, the two ways (give parameters to createDownhillSolver() or miss them out
joeverbout 0:ea44dc9ed014 189 and call the MinProblemSolver::setFunction() and DownhillSolver::setInitStep()) are absolutely
joeverbout 0:ea44dc9ed014 190 equivalent (and will drop the same errors in the same way, should invalid input be detected).
joeverbout 0:ea44dc9ed014 191 @param f Pointer to the function that will be minimized, similarly to the one you submit via
joeverbout 0:ea44dc9ed014 192 MinProblemSolver::setFunction.
joeverbout 0:ea44dc9ed014 193 @param initStep Initial step, that will be used to construct the initial simplex, similarly to the one
joeverbout 0:ea44dc9ed014 194 you submit via MinProblemSolver::setInitStep.
joeverbout 0:ea44dc9ed014 195 @param termcrit Terminal criteria to the algorithm, similarly to the one you submit via
joeverbout 0:ea44dc9ed014 196 MinProblemSolver::setTermCriteria.
joeverbout 0:ea44dc9ed014 197 */
joeverbout 0:ea44dc9ed014 198 static Ptr<DownhillSolver> create(const Ptr<MinProblemSolver::Function>& f=Ptr<MinProblemSolver::Function>(),
joeverbout 0:ea44dc9ed014 199 InputArray initStep=Mat_<double>(1,1,0.0),
joeverbout 0:ea44dc9ed014 200 TermCriteria termcrit=TermCriteria(TermCriteria::MAX_ITER+TermCriteria::EPS,5000,0.000001));
joeverbout 0:ea44dc9ed014 201 };
joeverbout 0:ea44dc9ed014 202
joeverbout 0:ea44dc9ed014 203 /** @brief This class is used to perform the non-linear non-constrained minimization of a function
joeverbout 0:ea44dc9ed014 204 with known gradient,
joeverbout 0:ea44dc9ed014 205
joeverbout 0:ea44dc9ed014 206 defined on an *n*-dimensional Euclidean space, using the **Nonlinear Conjugate Gradient method**.
joeverbout 0:ea44dc9ed014 207 The implementation was done based on the beautifully clear explanatory article [An Introduction to
joeverbout 0:ea44dc9ed014 208 the Conjugate Gradient Method Without the Agonizing
joeverbout 0:ea44dc9ed014 209 Pain](http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf) by Jonathan Richard
joeverbout 0:ea44dc9ed014 210 Shewchuk. The method can be seen as an adaptation of a standard Conjugate Gradient method (see, for
joeverbout 0:ea44dc9ed014 211 example <http://en.wikipedia.org/wiki/Conjugate_gradient_method>) for numerically solving the
joeverbout 0:ea44dc9ed014 212 systems of linear equations.
joeverbout 0:ea44dc9ed014 213
joeverbout 0:ea44dc9ed014 214 It should be noted, that this method, although deterministic, is rather a heuristic method and
joeverbout 0:ea44dc9ed014 215 therefore may converge to a local minima, not necessary a global one. What is even more disastrous,
joeverbout 0:ea44dc9ed014 216 most of its behaviour is ruled by gradient, therefore it essentially cannot distinguish between
joeverbout 0:ea44dc9ed014 217 local minima and maxima. Therefore, if it starts sufficiently near to the local maximum, it may
joeverbout 0:ea44dc9ed014 218 converge to it. Another obvious restriction is that it should be possible to compute the gradient of
joeverbout 0:ea44dc9ed014 219 a function at any point, thus it is preferable to have analytic expression for gradient and
joeverbout 0:ea44dc9ed014 220 computational burden should be born by the user.
joeverbout 0:ea44dc9ed014 221
joeverbout 0:ea44dc9ed014 222 The latter responsibility is accompilished via the getGradient method of a
joeverbout 0:ea44dc9ed014 223 MinProblemSolver::Function interface (which represents function being optimized). This method takes
joeverbout 0:ea44dc9ed014 224 point a point in *n*-dimensional space (first argument represents the array of coordinates of that
joeverbout 0:ea44dc9ed014 225 point) and comput its gradient (it should be stored in the second argument as an array).
joeverbout 0:ea44dc9ed014 226
joeverbout 0:ea44dc9ed014 227 @note class ConjGradSolver thus does not add any new methods to the basic MinProblemSolver interface.
joeverbout 0:ea44dc9ed014 228
joeverbout 0:ea44dc9ed014 229 @note term criteria should meet following condition:
joeverbout 0:ea44dc9ed014 230 @code
joeverbout 0:ea44dc9ed014 231 termcrit.type == (TermCriteria::MAX_ITER + TermCriteria::EPS) && termcrit.epsilon > 0 && termcrit.maxCount > 0
joeverbout 0:ea44dc9ed014 232 // or
joeverbout 0:ea44dc9ed014 233 termcrit.type == TermCriteria::MAX_ITER) && termcrit.maxCount > 0
joeverbout 0:ea44dc9ed014 234 @endcode
joeverbout 0:ea44dc9ed014 235 */
joeverbout 0:ea44dc9ed014 236 class CV_EXPORTS ConjGradSolver : public MinProblemSolver
joeverbout 0:ea44dc9ed014 237 {
joeverbout 0:ea44dc9ed014 238 public:
joeverbout 0:ea44dc9ed014 239 /** @brief This function returns the reference to the ready-to-use ConjGradSolver object.
joeverbout 0:ea44dc9ed014 240
joeverbout 0:ea44dc9ed014 241 All the parameters are optional, so this procedure can be called even without parameters at
joeverbout 0:ea44dc9ed014 242 all. In this case, the default values will be used. As default value for terminal criteria are
joeverbout 0:ea44dc9ed014 243 the only sensible ones, MinProblemSolver::setFunction() should be called upon the obtained
joeverbout 0:ea44dc9ed014 244 object, if the function was not given to create(). Otherwise, the two ways (submit it to
joeverbout 0:ea44dc9ed014 245 create() or miss it out and call the MinProblemSolver::setFunction()) are absolutely equivalent
joeverbout 0:ea44dc9ed014 246 (and will drop the same errors in the same way, should invalid input be detected).
joeverbout 0:ea44dc9ed014 247 @param f Pointer to the function that will be minimized, similarly to the one you submit via
joeverbout 0:ea44dc9ed014 248 MinProblemSolver::setFunction.
joeverbout 0:ea44dc9ed014 249 @param termcrit Terminal criteria to the algorithm, similarly to the one you submit via
joeverbout 0:ea44dc9ed014 250 MinProblemSolver::setTermCriteria.
joeverbout 0:ea44dc9ed014 251 */
joeverbout 0:ea44dc9ed014 252 static Ptr<ConjGradSolver> create(const Ptr<MinProblemSolver::Function>& f=Ptr<ConjGradSolver::Function>(),
joeverbout 0:ea44dc9ed014 253 TermCriteria termcrit=TermCriteria(TermCriteria::MAX_ITER+TermCriteria::EPS,5000,0.000001));
joeverbout 0:ea44dc9ed014 254 };
joeverbout 0:ea44dc9ed014 255
joeverbout 0:ea44dc9ed014 256 //! return codes for cv::solveLP() function
joeverbout 0:ea44dc9ed014 257 enum SolveLPResult
joeverbout 0:ea44dc9ed014 258 {
joeverbout 0:ea44dc9ed014 259 SOLVELP_UNBOUNDED = -2, //!< problem is unbounded (target function can achieve arbitrary high values)
joeverbout 0:ea44dc9ed014 260 SOLVELP_UNFEASIBLE = -1, //!< problem is unfeasible (there are no points that satisfy all the constraints imposed)
joeverbout 0:ea44dc9ed014 261 SOLVELP_SINGLE = 0, //!< there is only one maximum for target function
joeverbout 0:ea44dc9ed014 262 SOLVELP_MULTI = 1 //!< there are multiple maxima for target function - the arbitrary one is returned
joeverbout 0:ea44dc9ed014 263 };
joeverbout 0:ea44dc9ed014 264
joeverbout 0:ea44dc9ed014 265 /** @brief Solve given (non-integer) linear programming problem using the Simplex Algorithm (Simplex Method).
joeverbout 0:ea44dc9ed014 266
joeverbout 0:ea44dc9ed014 267 What we mean here by "linear programming problem" (or LP problem, for short) can be formulated as:
joeverbout 0:ea44dc9ed014 268
joeverbout 0:ea44dc9ed014 269 \f[\mbox{Maximize } c\cdot x\\
joeverbout 0:ea44dc9ed014 270 \mbox{Subject to:}\\
joeverbout 0:ea44dc9ed014 271 Ax\leq b\\
joeverbout 0:ea44dc9ed014 272 x\geq 0\f]
joeverbout 0:ea44dc9ed014 273
joeverbout 0:ea44dc9ed014 274 Where \f$c\f$ is fixed `1`-by-`n` row-vector, \f$A\f$ is fixed `m`-by-`n` matrix, \f$b\f$ is fixed `m`-by-`1`
joeverbout 0:ea44dc9ed014 275 column vector and \f$x\f$ is an arbitrary `n`-by-`1` column vector, which satisfies the constraints.
joeverbout 0:ea44dc9ed014 276
joeverbout 0:ea44dc9ed014 277 Simplex algorithm is one of many algorithms that are designed to handle this sort of problems
joeverbout 0:ea44dc9ed014 278 efficiently. Although it is not optimal in theoretical sense (there exist algorithms that can solve
joeverbout 0:ea44dc9ed014 279 any problem written as above in polynomial time, while simplex method degenerates to exponential
joeverbout 0:ea44dc9ed014 280 time for some special cases), it is well-studied, easy to implement and is shown to work well for
joeverbout 0:ea44dc9ed014 281 real-life purposes.
joeverbout 0:ea44dc9ed014 282
joeverbout 0:ea44dc9ed014 283 The particular implementation is taken almost verbatim from **Introduction to Algorithms, third
joeverbout 0:ea44dc9ed014 284 edition** by T. H. Cormen, C. E. Leiserson, R. L. Rivest and Clifford Stein. In particular, the
joeverbout 0:ea44dc9ed014 285 Bland's rule <http://en.wikipedia.org/wiki/Bland%27s_rule> is used to prevent cycling.
joeverbout 0:ea44dc9ed014 286
joeverbout 0:ea44dc9ed014 287 @param Func This row-vector corresponds to \f$c\f$ in the LP problem formulation (see above). It should
joeverbout 0:ea44dc9ed014 288 contain 32- or 64-bit floating point numbers. As a convenience, column-vector may be also submitted,
joeverbout 0:ea44dc9ed014 289 in the latter case it is understood to correspond to \f$c^T\f$.
joeverbout 0:ea44dc9ed014 290 @param Constr `m`-by-`n+1` matrix, whose rightmost column corresponds to \f$b\f$ in formulation above
joeverbout 0:ea44dc9ed014 291 and the remaining to \f$A\f$. It should containt 32- or 64-bit floating point numbers.
joeverbout 0:ea44dc9ed014 292 @param z The solution will be returned here as a column-vector - it corresponds to \f$c\f$ in the
joeverbout 0:ea44dc9ed014 293 formulation above. It will contain 64-bit floating point numbers.
joeverbout 0:ea44dc9ed014 294 @return One of cv::SolveLPResult
joeverbout 0:ea44dc9ed014 295 */
joeverbout 0:ea44dc9ed014 296 CV_EXPORTS_W int solveLP(const Mat& Func, const Mat& Constr, Mat& z);
joeverbout 0:ea44dc9ed014 297
joeverbout 0:ea44dc9ed014 298 //! @}
joeverbout 0:ea44dc9ed014 299
joeverbout 0:ea44dc9ed014 300 }// cv
joeverbout 0:ea44dc9ed014 301
joeverbout 0:ea44dc9ed014 302 #endif
joeverbout 0:ea44dc9ed014 303