Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

include/opencv2/core/optim.hpp@0:0e0631af0305, 2021-01-29 (annotated)

Committer:
RyoheiHagimoto
Date:
Fri Jan 29 04:53:38 2021 +0000
Revision:
0:0e0631af0305
copied from https://github.com/d-kato/opencv-lib.

Who changed what in which revision?

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