types.h revision 0ae28bd5885b5daa526898fcf7c323dc2c3e1963
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// 31// Enums and other top level class definitions. 32// 33// Note: internal/types.cc defines stringification routines for some 34// of these enums. Please update those routines if you extend or 35// remove enums from here. 36 37#ifndef CERES_PUBLIC_TYPES_H_ 38#define CERES_PUBLIC_TYPES_H_ 39 40#include "ceres/internal/port.h" 41 42namespace ceres { 43 44// Basic integer types. These typedefs are in the Ceres namespace to avoid 45// conflicts with other packages having similar typedefs. 46typedef short int16; 47typedef int int32; 48 49// Argument type used in interfaces that can optionally take ownership 50// of a passed in argument. If TAKE_OWNERSHIP is passed, the called 51// object takes ownership of the pointer argument, and will call 52// delete on it upon completion. 53enum Ownership { 54 DO_NOT_TAKE_OWNERSHIP, 55 TAKE_OWNERSHIP 56}; 57 58// TODO(keir): Considerably expand the explanations of each solver type. 59enum LinearSolverType { 60 // These solvers are for general rectangular systems formed from the 61 // normal equations A'A x = A'b. They are direct solvers and do not 62 // assume any special problem structure. 63 64 // Solve the normal equations using a dense Cholesky solver; based 65 // on Eigen. 66 DENSE_NORMAL_CHOLESKY, 67 68 // Solve the normal equations using a dense QR solver; based on 69 // Eigen. 70 DENSE_QR, 71 72 // Solve the normal equations using a sparse cholesky solver; requires 73 // SuiteSparse or CXSparse. 74 SPARSE_NORMAL_CHOLESKY, 75 76 // Specialized solvers, specific to problems with a generalized 77 // bi-partitite structure. 78 79 // Solves the reduced linear system using a dense Cholesky solver; 80 // based on Eigen. 81 DENSE_SCHUR, 82 83 // Solves the reduced linear system using a sparse Cholesky solver; 84 // based on CHOLMOD. 85 SPARSE_SCHUR, 86 87 // Solves the reduced linear system using Conjugate Gradients, based 88 // on a new Ceres implementation. Suitable for large scale 89 // problems. 90 ITERATIVE_SCHUR, 91 92 // Conjugate gradients on the normal equations. 93 CGNR 94}; 95 96enum PreconditionerType { 97 // Trivial preconditioner - the identity matrix. 98 IDENTITY, 99 100 // Block diagonal of the Gauss-Newton Hessian. 101 JACOBI, 102 103 // Block diagonal of the Schur complement. This preconditioner may 104 // only be used with the ITERATIVE_SCHUR solver. Requires 105 // SuiteSparse/CHOLMOD. 106 SCHUR_JACOBI, 107 108 // Visibility clustering based preconditioners. 109 // 110 // These preconditioners are well suited for Structure from Motion 111 // problems, particularly problems arising from community photo 112 // collections. These preconditioners use the visibility structure 113 // of the scene to determine the sparsity structure of the 114 // preconditioner. Requires SuiteSparse/CHOLMOD. 115 CLUSTER_JACOBI, 116 CLUSTER_TRIDIAGONAL 117}; 118 119enum SparseLinearAlgebraLibraryType { 120 // High performance sparse Cholesky factorization and approximate 121 // minimum degree ordering. 122 SUITE_SPARSE, 123 124 // A lightweight replacment for SuiteSparse. 125 CX_SPARSE 126}; 127 128enum LinearSolverTerminationType { 129 // Termination criterion was met. For factorization based solvers 130 // the tolerance is assumed to be zero. Any user provided values are 131 // ignored. 132 TOLERANCE, 133 134 // Solver ran for max_num_iterations and terminated before the 135 // termination tolerance could be satified. 136 MAX_ITERATIONS, 137 138 // Solver is stuck and further iterations will not result in any 139 // measurable progress. 140 STAGNATION, 141 142 // Solver failed. Solver was terminated due to numerical errors. The 143 // exact cause of failure depends on the particular solver being 144 // used. 145 FAILURE 146}; 147 148// Logging options 149// The options get progressively noisier. 150enum LoggingType { 151 SILENT, 152 PER_MINIMIZER_ITERATION 153}; 154 155// Ceres supports different strategies for computing the trust region 156// step. 157enum TrustRegionStrategyType { 158 // The default trust region strategy is to use the step computation 159 // used in the Levenberg-Marquardt algorithm. For more details see 160 // levenberg_marquardt_strategy.h 161 LEVENBERG_MARQUARDT, 162 163 // Powell's dogleg algorithm interpolates between the Cauchy point 164 // and the Gauss-Newton step. It is particularly useful if the 165 // LEVENBERG_MARQUARDT algorithm is making a large number of 166 // unsuccessful steps. For more details see dogleg_strategy.h. 167 // 168 // NOTES: 169 // 170 // 1. This strategy has not been experimented with or tested as 171 // extensively as LEVENBERG_MARQUARDT, and therefore it should be 172 // considered EXPERIMENTAL for now. 173 // 174 // 2. For now this strategy should only be used with exact 175 // factorization based linear solvers, i.e., SPARSE_SCHUR, 176 // DENSE_SCHUR, DENSE_QR and SPARSE_NORMAL_CHOLESKY. 177 DOGLEG 178}; 179 180// Ceres supports two different dogleg strategies. 181// The "traditional" dogleg method by Powell and the 182// "subspace" method described in 183// R. H. Byrd, R. B. Schnabel, and G. A. Shultz, 184// "Approximate solution of the trust region problem by minimization 185// over two-dimensional subspaces", Mathematical Programming, 186// 40 (1988), pp. 247--263 187enum DoglegType { 188 // The traditional approach constructs a dogleg path 189 // consisting of two line segments and finds the furthest 190 // point on that path that is still inside the trust region. 191 TRADITIONAL_DOGLEG, 192 193 // The subspace approach finds the exact minimum of the model 194 // constrained to the subspace spanned by the dogleg path. 195 SUBSPACE_DOGLEG 196}; 197 198enum SolverTerminationType { 199 // The minimizer did not run at all; usually due to errors in the user's 200 // Problem or the solver options. 201 DID_NOT_RUN, 202 203 // The solver ran for maximum number of iterations specified by the 204 // user, but none of the convergence criterion specified by the user 205 // were met. 206 NO_CONVERGENCE, 207 208 // Minimizer terminated because 209 // (new_cost - old_cost) < function_tolerance * old_cost; 210 FUNCTION_TOLERANCE, 211 212 // Minimizer terminated because 213 // max_i |gradient_i| < gradient_tolerance * max_i|initial_gradient_i| 214 GRADIENT_TOLERANCE, 215 216 // Minimized terminated because 217 // |step|_2 <= parameter_tolerance * ( |x|_2 + parameter_tolerance) 218 PARAMETER_TOLERANCE, 219 220 // The minimizer terminated because it encountered a numerical error 221 // that it could not recover from. 222 NUMERICAL_FAILURE, 223 224 // Using an IterationCallback object, user code can control the 225 // minimizer. The following enums indicate that the user code was 226 // responsible for termination. 227 228 // User's IterationCallback returned SOLVER_ABORT. 229 USER_ABORT, 230 231 // User's IterationCallback returned SOLVER_TERMINATE_SUCCESSFULLY 232 USER_SUCCESS 233}; 234 235// Enums used by the IterationCallback instances to indicate to the 236// solver whether it should continue solving, the user detected an 237// error or the solution is good enough and the solver should 238// terminate. 239enum CallbackReturnType { 240 // Continue solving to next iteration. 241 SOLVER_CONTINUE, 242 243 // Terminate solver, and do not update the parameter blocks upon 244 // return. Unless the user has set 245 // Solver:Options:::update_state_every_iteration, in which case the 246 // state would have been updated every iteration 247 // anyways. Solver::Summary::termination_type is set to USER_ABORT. 248 SOLVER_ABORT, 249 250 // Terminate solver, update state and 251 // return. Solver::Summary::termination_type is set to USER_SUCCESS. 252 SOLVER_TERMINATE_SUCCESSFULLY 253}; 254 255// The format in which linear least squares problems should be logged 256// when Solver::Options::lsqp_iterations_to_dump is non-empty. 257enum DumpFormatType { 258 // Print the linear least squares problem in a human readable format 259 // to stderr. The Jacobian is printed as a dense matrix. The vectors 260 // D, x and f are printed as dense vectors. This should only be used 261 // for small problems. 262 CONSOLE, 263 264 // Write out the linear least squares problem to the directory 265 // pointed to by Solver::Options::lsqp_dump_directory as a protocol 266 // buffer. linear_least_squares_problems.h/cc contains routines for 267 // loading these problems. For details on the on disk format used, 268 // see matrix.proto. The files are named lm_iteration_???.lsqp. 269 PROTOBUF, 270 271 // Write out the linear least squares problem to the directory 272 // pointed to by Solver::Options::lsqp_dump_directory as text files 273 // which can be read into MATLAB/Octave. The Jacobian is dumped as a 274 // text file containing (i,j,s) triplets, the vectors D, x and f are 275 // dumped as text files containing a list of their values. 276 // 277 // A MATLAB/octave script called lm_iteration_???.m is also output, 278 // which can be used to parse and load the problem into memory. 279 TEXTFILE 280}; 281 282// For SizedCostFunction and AutoDiffCostFunction, DYNAMIC can be specified for 283// the number of residuals. If specified, then the number of residuas for that 284// cost function can vary at runtime. 285enum DimensionType { 286 DYNAMIC = -1 287}; 288 289const char* LinearSolverTypeToString(LinearSolverType type); 290bool StringToLinearSolverType(string value, LinearSolverType* type); 291 292const char* PreconditionerTypeToString(PreconditionerType type); 293bool StringToPreconditionerType(string value, PreconditionerType* type); 294 295const char* SparseLinearAlgebraLibraryTypeToString( 296 SparseLinearAlgebraLibraryType type); 297bool StringToSparseLinearAlgebraLibraryType( 298 string value, 299 SparseLinearAlgebraLibraryType* type); 300 301const char* TrustRegionStrategyTypeToString(TrustRegionStrategyType type); 302bool StringToTrustRegionStrategyType(string value, 303 TrustRegionStrategyType* type); 304 305const char* DoglegTypeToString(DoglegType type); 306bool StringToDoglegType(string value, DoglegType* type); 307 308const char* LinearSolverTerminationTypeToString( 309 LinearSolverTerminationType type); 310 311const char* SolverTerminationTypeToString(SolverTerminationType type); 312 313bool IsSchurType(LinearSolverType type); 314bool IsSparseLinearAlgebraLibraryTypeAvailable( 315 SparseLinearAlgebraLibraryType type); 316 317 318} // namespace ceres 319 320#endif // CERES_PUBLIC_TYPES_H_ 321