Documentation updates. 1. Further tightening of the Covariance documentation. 2. Documented minimizer progress output. 3. Lint cleanup from William Rucklidge. 4. Updated version history. Change-Id: I8bc28484675d4edf89a7c050b6379dbac6c39e91
diff --git a/docs/source/solving.rst b/docs/source/solving.rst index 9b26166..e26f87b 100644 --- a/docs/source/solving.rst +++ b/docs/source/solving.rst
@@ -1126,6 +1126,52 @@ :member:`Solver::Options::logging_type` is not ``SILENT``, the logging output is sent to ``STDOUT``. + For ``TRUST_REGION_MINIMIZER`` the progress display looks like + + .. code-block:: bash + + 0: f: 1.250000e+01 d: 0.00e+00 g: 5.00e+00 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li: 0 it: 6.91e-06 tt: 1.91e-03 + 1: f: 1.249750e-07 d: 1.25e+01 g: 5.00e-04 h: 5.00e+00 rho: 1.00e+00 mu: 3.00e+04 li: 1 it: 2.81e-05 tt: 1.99e-03 + 2: f: 1.388518e-16 d: 1.25e-07 g: 1.67e-08 h: 5.00e-04 rho: 1.00e+00 mu: 9.00e+04 li: 1 it: 1.00e-05 tt: 2.01e-03 + + Here + + #. ``f`` is the value of the objective function. + #. ``d`` is the change in the value of the objective function if + the step computed in this iteration is accepted. + #. ``g`` is the max norm of the gradient. + #. ``h`` is the change in the parameter vector. + #. ``rho`` is the ratio of the actual change in the objective + function value to the change in the the value of the trust + region model. + #. ``mu`` is the size of the trust region radius. + #. ``li`` is the number of linear solver iterations used to compute + the trust region step. For direct/factorization based solvers it + is always 1, for iterative solvers like ``ITERATIVE_SCHUR`` it + is the number of iterations of the Conjugate Gradients + algorithm. + #. ``it`` is the time take by the current iteration. + #. ``tt`` is the the total time taken by the minimizer. + + For ``LINE_SEARCH_MINIMIZER`` the progress display looks like + + .. code-block:: bash + + 0: f: 2.317806e+05 d: 0.00e+00 g: 3.19e-01 h: 0.00e+00 s: 0.00e+00 e: 0 it: 2.98e-02 tt: 8.50e-02 + 1: f: 2.312019e+05 d: 5.79e+02 g: 3.18e-01 h: 2.41e+01 s: 1.00e+00 e: 1 it: 4.54e-02 tt: 1.31e-01 + 2: f: 2.300462e+05 d: 1.16e+03 g: 3.17e-01 h: 4.90e+01 s: 2.54e-03 e: 1 it: 4.96e-02 tt: 1.81e-01 + + Here + + #. ``f`` is the value of the objective function. + #. ``d`` is the change in the value of the objective function if + the step computed in this iteration is accepted. + #. ``g`` is the max norm of the gradient. + #. ``h`` is the change in the parameter vector. + #. ``s`` is the optimal step length computed by the line search. + #. ``it`` is the time take by the current iteration. + #. ``tt`` is the the total time taken by the minimizer. + .. member:: vector<int> Solver::Options::lsqp_iterations_to_dump Default: ``empty``
diff --git a/docs/source/tutorial.rst b/docs/source/tutorial.rst index da63e9e..1e5756a 100644 --- a/docs/source/tutorial.rst +++ b/docs/source/tutorial.rst
@@ -710,4 +710,8 @@ <http://www.itl.nist.gov/div898/strd/nls/nls_main.shtm>`_ non-linear regression problems. +#. `libmv_bundle_adjuster.cc + <https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/libmv_bundle_adjuster.cc>`_ + is the bundle adjustment algorithm used by `Blender <www.blender.org>`_/libmv. +
diff --git a/docs/source/version_history.rst b/docs/source/version_history.rst index 11e1e46..b76e43c 100644 --- a/docs/source/version_history.rst +++ b/docs/source/version_history.rst
@@ -4,8 +4,8 @@ Version History =============== -HEAD -==== +HEAD (52c3d9a) +============== New Features ------------ @@ -17,11 +17,14 @@ and runtime statistics for inner iterations are not reported in ``Solver::Summary`` and ``Solver::Summary::FullReport``. #. Add BlockRandomAccessCRSMatrix. - +#. Bundle adjustment example from libmv/Blender (Sergey Sharybin) Bug Fixes --------- +#. Add documentation for minimizer progress output. +#. Lint and other cleanups (William Rucklidge) +#. Collections port fix for MSC 2008 (Sergey Sharybin) #. Various corrections and cleanups in the documentation. #. Change the path where CeresConfig.cmake is installed (Pablo Speciale) #. Minor erros in documentation (Pablo Speciale)
diff --git a/examples/libmv_bundle_adjuster.cc b/examples/libmv_bundle_adjuster.cc index 4ae934c..60b1382 100644 --- a/examples/libmv_bundle_adjuster.cc +++ b/examples/libmv_bundle_adjuster.cc
@@ -254,10 +254,10 @@ // Reader of binary file which makes sure possibly needed endian // conversion happens when loading values like floats and integers. // -// File's endian type is reading from a first character of file, -// which could either be V for big endian or v for little endian. -// This means you need to design file format assuming first character -// denotes file endianes in this way. +// File's endian type is reading from a first character of file, which +// could either be V for big endian or v for little endian. This +// means you need to design file format assuming first character +// denotes file endianness in this way. class EndianAwareFileReader { public: EndianAwareFileReader(void) : file_descriptor_(-1) { @@ -541,7 +541,7 @@ const double observed_y; }; -// Print a message to the log which camera intrinsics are gonna to be optimixed. +// Print a message to the log which camera intrinsics are gonna to be optimized. void BundleIntrinsicsLogMessage(const int bundle_intrinsics) { if (bundle_intrinsics == BUNDLE_NO_INTRINSICS) { LOG(INFO) << "Bundling only camera positions.";
diff --git a/include/ceres/covariance.h b/include/ceres/covariance.h index 26f94f7..f65d9eb 100644 --- a/include/ceres/covariance.h +++ b/include/ceres/covariance.h
@@ -113,7 +113,7 @@ // blocks. The computation assumes that the CostFunctions compute // residuals such that their covariance is identity. // -// Since the computation of the covariance matrix involves computing +// Since the computation of the covariance matrix requires computing // the inverse of a potentially large matrix, this can involve a // rather large amount of time and memory. However, it is usually the // case that the user is only interested in a small part of the @@ -222,16 +222,18 @@ bool use_dense_linear_algebra; // If the Jacobian matrix is near singular, then inverting J'J - // will result in unreliable results, e.g, + // will result in unreliable results, e.g, if // // J = [1.0 1.0 ] // [1.0 1.0000001 ] // - // Which is essentially a rank deficient matrix + // which is essentially a rank deficient matrix, we have // // inv(J'J) = [ 2.0471e+14 -2.0471e+14] // [-2.0471e+14 2.0471e+14] // + // This is not a useful result. + // // The reciprocal condition number of a matrix is a measure of // ill-conditioning or how close the matrix is to being // singular/rank deficient. It is defined as the ratio of the @@ -242,51 +244,31 @@ // interpet the results of such an inversion. // // Matrices with condition number lower than - // min_reciprocal_condition_number are considered rank deficient. + // min_reciprocal_condition_number are considered rank deficient + // and by default Covariance::Compute will return false if it + // encounters such a matrix. // - // Depending on the value of use_dense_linear_algebra this may - // have further consequences on the covariance estimation process. + // use_dense_linear_algebra = true + // ------------------------------- // - // 1. use_dense_linear_algebra = false + // When using dense linear algebra, the user has more control in + // dealing with singular and near singular covariance matrices. // - // If the reciprocal_condition_number of J'J is less than - // min_reciprocal_condition_number, Covariance::Compute() will - // fail and return false. + // As mentioned above, when the covariance matrix is near + // singular, instead of computing the inverse of J'J, the + // Moore-Penrose pseudoinverse of J'J should be computed. // - // 2. use_dense_linear_algebra = true + // If J'J has the eigen decomposition (lambda_i, e_i), where + // lambda_i is the i^th eigenvalue and e_i is the corresponding + // eigenvector, then the inverse of J'J is // - // When dense covariance estimation is being used, then rank - // deficiency/singularity of the Jacobian can be handled in a - // more sophisticated manner. + // inverse[J'J] = sum_i e_i e_i' / lambda_i // - // If null_space_rank = -1, then instead of computing the - // inverse of J'J, the Moore-Penrose Pseudoinverse is computed. If - // (lambda_i, e_i) are eigenvalue and eigenvector pairs of J'J. + // and computing the pseudo inverse involves dropping terms from + // this sum that correspond to small eigenvalues. // - // pseudoinverse[J'J] = sum_i e_i e_i' / lambda_i - // - // if lambda_i / lambda_max >= min_reciprocal_condition_number. - // - // If null_space_rank is non-negative, then the smallest - // null_space_rank eigenvalue/eigenvectors are dropped - // irrespective of the magnitude of lambda_i. If the ratio of - // the smallest non-zero eigenvalue to the largest eigenvalue - // in the truncated matrix is still below - // min_reciprocal_condition_number, then the - // Covariance::Compute() will fail and return false. - double min_reciprocal_condition_number; - - // When use_dense_linear_algebra is true, null_space_rank - // determines how many of the smallest eigenvectors of J'J are - // dropped when computing the pseudoinverse. - // - // If null_space_rank = -1, then instead of computing the inverse - // of J'J, the Moore-Penrose Pseudoinverse is computed. If - // (lambda_i, e_i) are eigenvalue and eigenvector pairs of J'J. - // - // pseudoinverse[J'J] = sum_i e_i e_i' / lambda_i - // - // if lambda_i / lambda_max >= min_reciprocal_condition_number. + // How terms are dropped is controlled by + // min_reciprocal_condition_number and null_space_rank. // // If null_space_rank is non-negative, then the smallest // null_space_rank eigenvalue/eigenvectors are dropped @@ -295,6 +277,22 @@ // truncated matrix is still below // min_reciprocal_condition_number, then the Covariance::Compute() // will fail and return false. + // + // Setting null_space_rank = -1 drops all terms for which + // + // lambda_i / lambda_max < min_reciprocal_condition_number. + // + double min_reciprocal_condition_number; + + // Truncate the smallest "null_space_rank" eigenvectors when + // computing the pseudo inverse of J'J. + // + // If null_space_rank = -1, then all eigenvectors with eigenvalues s.t. + // + // lambda_i / lambda_max < min_reciprocal_condition_number. + // + // are dropped. See the documentation for + // min_reciprocal_condition_number for more details. int null_space_rank; // Even though the residual blocks in the problem may contain loss