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
