1 // Ceres Solver - A fast non-linear least squares minimizer 2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 3 // http://code.google.com/p/ceres-solver/ 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are met: 7 // 8 // * Redistributions of source code must retain the above copyright notice, 9 // this list of conditions and the following disclaimer. 10 // * Redistributions in binary form must reproduce the above copyright notice, 11 // this list of conditions and the following disclaimer in the documentation 12 // and/or other materials provided with the distribution. 13 // * Neither the name of Google Inc. nor the names of its contributors may be 14 // used to endorse or promote products derived from this software without 15 // specific prior written permission. 16 // 17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 // POSSIBILITY OF SUCH DAMAGE. 28 // 29 // Author: sameeragarwal@google.com (Sameer Agarwal) 30 // keir@google.com (Keir Mierle) 31 // 32 // The Problem object is used to build and hold least squares problems. 33 34 #ifndef CERES_PUBLIC_PROBLEM_H_ 35 #define CERES_PUBLIC_PROBLEM_H_ 36 37 #include <cstddef> 38 #include <map> 39 #include <set> 40 #include <vector> 41 42 #include <glog/logging.h> 43 #include "ceres/internal/macros.h" 44 #include "ceres/internal/port.h" 45 #include "ceres/internal/scoped_ptr.h" 46 #include "ceres/types.h" 47 48 namespace ceres { 49 50 class CostFunction; 51 class LossFunction; 52 class LocalParameterization; 53 class Solver; 54 55 namespace internal { 56 class Preprocessor; 57 class ProblemImpl; 58 class ParameterBlock; 59 class ResidualBlock; 60 } // namespace internal 61 62 // A ResidualBlockId is a handle clients can use to delete residual 63 // blocks after creating them. They are opaque for any purposes other 64 // than that. 65 typedef const internal::ResidualBlock* ResidualBlockId; 66 67 // A class to represent non-linear least squares problems. Such 68 // problems have a cost function that is a sum of error terms (known 69 // as "residuals"), where each residual is a function of some subset 70 // of the parameters. The cost function takes the form 71 // 72 // N 1 73 // SUM --- loss( || r_i1, r_i2,..., r_ik ||^2 ), 74 // i=1 2 75 // 76 // where 77 // 78 // r_ij is residual number i, component j; the residual is a 79 // function of some subset of the parameters x1...xk. For 80 // example, in a structure from motion problem a residual 81 // might be the difference between a measured point in an 82 // image and the reprojected position for the matching 83 // camera, point pair. The residual would have two 84 // components, error in x and error in y. 85 // 86 // loss(y) is the loss function; for example, squared error or 87 // Huber L1 loss. If loss(y) = y, then the cost function is 88 // non-robustified least squares. 89 // 90 // This class is specifically designed to address the important subset 91 // of "sparse" least squares problems, where each component of the 92 // residual depends only on a small number number of parameters, even 93 // though the total number of residuals and parameters may be very 94 // large. This property affords tremendous gains in scale, allowing 95 // efficient solving of large problems that are otherwise 96 // inaccessible. 97 // 98 // The canonical example of a sparse least squares problem is 99 // "structure-from-motion" (SFM), where the parameters are points and 100 // cameras, and residuals are reprojection errors. Typically a single 101 // residual will depend only on 9 parameters (3 for the point, 6 for 102 // the camera). 103 // 104 // To create a least squares problem, use the AddResidualBlock() and 105 // AddParameterBlock() methods, documented below. Here is an example least 106 // squares problem containing 3 parameter blocks of sizes 3, 4 and 5 107 // respectively and two residual terms of size 2 and 6: 108 // 109 // double x1[] = { 1.0, 2.0, 3.0 }; 110 // double x2[] = { 1.0, 2.0, 3.0, 5.0 }; 111 // double x3[] = { 1.0, 2.0, 3.0, 6.0, 7.0 }; 112 // 113 // Problem problem; 114 // 115 // problem.AddResidualBlock(new MyUnaryCostFunction(...), x1); 116 // problem.AddResidualBlock(new MyBinaryCostFunction(...), x2, x3); 117 // 118 // Please see cost_function.h for details of the CostFunction object. 119 class Problem { 120 public: 121 struct Options { OptionsOptions122 Options() 123 : cost_function_ownership(TAKE_OWNERSHIP), 124 loss_function_ownership(TAKE_OWNERSHIP), 125 local_parameterization_ownership(TAKE_OWNERSHIP) {} 126 127 // These flags control whether the Problem object owns the cost 128 // functions, loss functions, and parameterizations passed into 129 // the Problem. If set to TAKE_OWNERSHIP, then the problem object 130 // will delete the corresponding cost or loss functions on 131 // destruction. The destructor is careful to delete the pointers 132 // only once, since sharing cost/loss/parameterizations is 133 // allowed. 134 Ownership cost_function_ownership; 135 Ownership loss_function_ownership; 136 Ownership local_parameterization_ownership; 137 }; 138 139 // The default constructor is equivalent to the 140 // invocation Problem(Problem::Options()). 141 Problem(); 142 explicit Problem(const Options& options); 143 144 ~Problem(); 145 146 // Add a residual block to the overall cost function. The cost 147 // function carries with it information about the sizes of the 148 // parameter blocks it expects. The function checks that these match 149 // the sizes of the parameter blocks listed in parameter_blocks. The 150 // program aborts if a mismatch is detected. loss_function can be 151 // NULL, in which case the cost of the term is just the squared norm 152 // of the residuals. 153 // 154 // The user has the option of explicitly adding the parameter blocks 155 // using AddParameterBlock. This causes additional correctness 156 // checking; however, AddResidualBlock implicitly adds the parameter 157 // blocks if they are not present, so calling AddParameterBlock 158 // explicitly is not required. 159 // 160 // The Problem object by default takes ownership of the 161 // cost_function and loss_function pointers. These objects remain 162 // live for the life of the Problem object. If the user wishes to 163 // keep control over the destruction of these objects, then they can 164 // do this by setting the corresponding enums in the Options struct. 165 // 166 // Note: Even though the Problem takes ownership of cost_function 167 // and loss_function, it does not preclude the user from re-using 168 // them in another residual block. The destructor takes care to call 169 // delete on each cost_function or loss_function pointer only once, 170 // regardless of how many residual blocks refer to them. 171 // 172 // Example usage: 173 // 174 // double x1[] = {1.0, 2.0, 3.0}; 175 // double x2[] = {1.0, 2.0, 5.0, 6.0}; 176 // double x3[] = {3.0, 6.0, 2.0, 5.0, 1.0}; 177 // 178 // Problem problem; 179 // 180 // problem.AddResidualBlock(new MyUnaryCostFunction(...), NULL, x1); 181 // problem.AddResidualBlock(new MyBinaryCostFunction(...), NULL, x2, x1); 182 // 183 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 184 LossFunction* loss_function, 185 const vector<double*>& parameter_blocks); 186 187 // Convenience methods for adding residuals with a small number of 188 // parameters. This is the common case. Instead of specifying the 189 // parameter block arguments as a vector, list them as pointers. 190 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 191 LossFunction* loss_function, 192 double* x0); 193 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 194 LossFunction* loss_function, 195 double* x0, double* x1); 196 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 197 LossFunction* loss_function, 198 double* x0, double* x1, double* x2); 199 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 200 LossFunction* loss_function, 201 double* x0, double* x1, double* x2, 202 double* x3); 203 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 204 LossFunction* loss_function, 205 double* x0, double* x1, double* x2, 206 double* x3, double* x4); 207 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 208 LossFunction* loss_function, 209 double* x0, double* x1, double* x2, 210 double* x3, double* x4, double* x5); 211 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 212 LossFunction* loss_function, 213 double* x0, double* x1, double* x2, 214 double* x3, double* x4, double* x5, 215 double* x6); 216 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 217 LossFunction* loss_function, 218 double* x0, double* x1, double* x2, 219 double* x3, double* x4, double* x5, 220 double* x6, double* x7); 221 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 222 LossFunction* loss_function, 223 double* x0, double* x1, double* x2, 224 double* x3, double* x4, double* x5, 225 double* x6, double* x7, double* x8); 226 ResidualBlockId AddResidualBlock(CostFunction* cost_function, 227 LossFunction* loss_function, 228 double* x0, double* x1, double* x2, 229 double* x3, double* x4, double* x5, 230 double* x6, double* x7, double* x8, 231 double* x9); 232 233 // Add a parameter block with appropriate size to the problem. 234 // Repeated calls with the same arguments are ignored. Repeated 235 // calls with the same double pointer but a different size results 236 // in undefined behaviour. 237 void AddParameterBlock(double* values, int size); 238 239 // Add a parameter block with appropriate size and parameterization 240 // to the problem. Repeated calls with the same arguments are 241 // ignored. Repeated calls with the same double pointer but a 242 // different size results in undefined behaviour. 243 void AddParameterBlock(double* values, 244 int size, 245 LocalParameterization* local_parameterization); 246 247 // Hold the indicated parameter block constant during optimization. 248 void SetParameterBlockConstant(double* values); 249 250 // Allow the indicated parameter to vary during optimization. 251 void SetParameterBlockVariable(double* values); 252 253 // Set the local parameterization for one of the parameter blocks. 254 // The local_parameterization is owned by the Problem by default. It 255 // is acceptable to set the same parameterization for multiple 256 // parameters; the destructor is careful to delete local 257 // parameterizations only once. The local parameterization can only 258 // be set once per parameter, and cannot be changed once set. 259 void SetParameterization(double* values, 260 LocalParameterization* local_parameterization); 261 262 // Number of parameter blocks in the problem. Always equals 263 // parameter_blocks().size() and parameter_block_sizes().size(). 264 int NumParameterBlocks() const; 265 266 // The size of the parameter vector obtained by summing over the 267 // sizes of all the parameter blocks. 268 int NumParameters() const; 269 270 // Number of residual blocks in the problem. Always equals 271 // residual_blocks().size(). 272 int NumResidualBlocks() const; 273 274 // The size of the residual vector obtained by summing over the 275 // sizes of all of the residual blocks. 276 int NumResiduals() const; 277 278 private: 279 friend class Solver; 280 internal::scoped_ptr<internal::ProblemImpl> problem_impl_; 281 CERES_DISALLOW_COPY_AND_ASSIGN(Problem); 282 }; 283 284 } // namespace ceres 285 286 #endif // CERES_PUBLIC_PROBLEM_H_ 287