diff options
Diffstat (limited to 'docs/source/tutorial.rst')
| -rw-r--r-- | docs/source/tutorial.rst | 179 |
1 files changed, 117 insertions, 62 deletions
diff --git a/docs/source/tutorial.rst b/docs/source/tutorial.rst index 1e5756a..79714f6 100644 --- a/docs/source/tutorial.rst +++ b/docs/source/tutorial.rst @@ -7,10 +7,27 @@ ======== Tutorial ======== -Ceres solves robustified non-linear least squares problems of the form -.. math:: \frac{1}{2}\sum_{i=1} \rho_i\left(\left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2\right). - :label: ceresproblem +Ceres solves robustified non-linear bounds constrained least squares +problems of the form + +.. math:: :label: ceresproblem + + \min_{\mathbf{x}} &\quad \frac{1}{2}\sum_{i} \rho_i\left(\left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2\right) \\ + \text{s.t.} &\quad l_j \le x_j \le u_j + +Problems of this form comes up in a broad range of areas across +science and engineering - from `fitting curves`_ in statistics, to +constructing `3D models from photographs`_ in computer vision. + +.. _fitting curves: http://en.wikipedia.org/wiki/Nonlinear_regression +.. _3D models from photographs: http://en.wikipedia.org/wiki/Bundle_adjustment + +In this chapter we will learn how to solve :eq:`ceresproblem` using +Ceres Solver. Full working code for all the examples described in this +chapter and more can be found in the `examples +<https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/>`_ +directory. The expression :math:`\rho_i\left(\left\|f_i\left(x_{i_1},...,x_{i_k}\right)\right\|^2\right)` @@ -21,24 +38,21 @@ problems small groups of scalars occur together. For example the three components of a translation vector and the four components of the quaternion that define the pose of a camera. We refer to such a group of small scalars as a ``ParameterBlock``. Of course a -``ParameterBlock`` can just be a single parameter. +``ParameterBlock`` can just be a single parameter. :math:`l_j` and +:math:`u_j` are bounds on the parameter block :math:`x_j`. :math:`\rho_i` is a :class:`LossFunction`. A :class:`LossFunction` is a scalar function that is used to reduce the influence of outliers on -the solution of non-linear least squares problems. As a special case, -when :math:`\rho_i(x) = x`, i.e., the identity function, we get the -more familiar `non-linear least squares problem +the solution of non-linear least squares problems. + +As a special case, when :math:`\rho_i(x) = x`, i.e., the identity +function, and :math:`l_j = -\infty` and :math:`u_j = \infty` we get +the more familiar `non-linear least squares problem <http://en.wikipedia.org/wiki/Non-linear_least_squares>`_. -.. math:: \frac{1}{2}\sum_{i=1} \left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2. +.. math:: \frac{1}{2}\sum_{i} \left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2. :label: ceresproblem2 -In this chapter we will learn how to solve :eq:`ceresproblem` using -Ceres Solver. Full working code for all the examples described in this -chapter and more can be found in the `examples -<https://ceres-solver.googlesource.com/ceres-solver/+/master/examples/>`_ -directory. - .. _section-hello-world: Hello World! @@ -68,10 +82,10 @@ function :math:`f(x) = 10 - x`: The important thing to note here is that ``operator()`` is a templated method, which assumes that all its inputs and outputs are of some type -``T``. The reason for using templates here is because Ceres will call -``CostFunctor::operator<T>()``, with ``T=double`` when just the -residual is needed, and with a special type ``T=Jet`` when the -Jacobians are needed. In :ref:`section-derivatives` we discuss the +``T``. The use of templating here allows Ceres to call +``CostFunctor::operator<T>()``, with ``T=double`` when just the value +of the residual is needed, and with a special type ``T=Jet`` when the +Jacobians are needed. In :ref:`section-derivatives` we will discuss the various ways of supplying derivatives to Ceres in more detail. Once we have a way of computing the residual function, it is now time @@ -119,11 +133,12 @@ gives us .. 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 - Ceres Solver Report: Iterations: 2, Initial cost: 1.250000e+01, Final cost: 1.388518e-16, Termination: PARAMETER_TOLERANCE. - x : 5 -> 10 + iter cost cost_change |gradient| |step| tr_ratio tr_radius ls_iter iter_time total_time + 0 4.512500e+01 0.00e+00 9.50e+00 0.00e+00 0.00e+00 1.00e+04 0 5.33e-04 3.46e-03 + 1 4.511598e-07 4.51e+01 9.50e-04 9.50e+00 1.00e+00 3.00e+04 1 5.00e-04 4.05e-03 + 2 5.012552e-16 4.51e-07 3.17e-08 9.50e-04 1.00e+00 9.00e+04 1 1.60e-05 4.09e-03 + Ceres Solver Report: Iterations: 2, Initial cost: 4.512500e+01, Final cost: 5.012552e-16, Termination: CONVERGENCE + x : 0.5 -> 10 Starting from a :math:`x=5`, the solver in two iterations goes to 10 [#f2]_. The careful reader will note that this is a linear problem and @@ -359,21 +374,64 @@ gives us: .. code-block:: bash - Initial x1 = 3, x2 = -1, x3 = 0, x4 = 1 - 0: f: 1.075000e+02 d: 0.00e+00 g: 1.55e+02 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li: 0 it: 0.00e+00 tt: 0.00e+00 - 1: f: 5.036190e+00 d: 1.02e+02 g: 2.00e+01 h: 2.16e+00 rho: 9.53e-01 mu: 3.00e+04 li: 1 it: 0.00e+00 tt: 0.00e+00 - 2: f: 3.148168e-01 d: 4.72e+00 g: 2.50e+00 h: 6.23e-01 rho: 9.37e-01 mu: 9.00e+04 li: 1 it: 0.00e+00 tt: 0.00e+00 - 3: f: 1.967760e-02 d: 2.95e-01 g: 3.13e-01 h: 3.08e-01 rho: 9.37e-01 mu: 2.70e+05 li: 1 it: 0.00e+00 tt: 0.00e+00 - 4: f: 1.229900e-03 d: 1.84e-02 g: 3.91e-02 h: 1.54e-01 rho: 9.37e-01 mu: 8.10e+05 li: 1 it: 0.00e+00 tt: 0.00e+00 - 5: f: 7.687123e-05 d: 1.15e-03 g: 4.89e-03 h: 7.69e-02 rho: 9.37e-01 mu: 2.43e+06 li: 1 it: 0.00e+00 tt: 0.00e+00 - 6: f: 4.804625e-06 d: 7.21e-05 g: 6.11e-04 h: 3.85e-02 rho: 9.37e-01 mu: 7.29e+06 li: 1 it: 0.00e+00 tt: 0.00e+00 - 7: f: 3.003028e-07 d: 4.50e-06 g: 7.64e-05 h: 1.92e-02 rho: 9.37e-01 mu: 2.19e+07 li: 1 it: 0.00e+00 tt: 0.00e+00 - 8: f: 1.877006e-08 d: 2.82e-07 g: 9.54e-06 h: 9.62e-03 rho: 9.37e-01 mu: 6.56e+07 li: 1 it: 0.00e+00 tt: 0.00e+00 - 9: f: 1.173223e-09 d: 1.76e-08 g: 1.19e-06 h: 4.81e-03 rho: 9.37e-01 mu: 1.97e+08 li: 1 it: 0.00e+00 tt: 0.00e+00 - 10: f: 7.333425e-11 d: 1.10e-09 g: 1.49e-07 h: 2.40e-03 rho: 9.37e-01 mu: 5.90e+08 li: 1 it: 0.00e+00 tt: 0.00e+00 - 11: f: 4.584044e-12 d: 6.88e-11 g: 1.86e-08 h: 1.20e-03 rho: 9.37e-01 mu: 1.77e+09 li: 1 it: 0.00e+00 tt: 0.00e+00 - Ceres Solver Report: Iterations: 12, Initial cost: 1.075000e+02, Final cost: 4.584044e-12, Termination: GRADIENT_TOLERANCE. - Final x1 = 0.00116741, x2 = -0.000116741, x3 = 0.000190535, x4 = 0.000190535 + Initial x1 = 3, x2 = -1, x3 = 0, x4 = 1 + iter cost cost_change |gradient| |step| tr_ratio tr_radius ls_iter iter_time total_time + 0 1.075000e+02 0.00e+00 1.55e+02 0.00e+00 0.00e+00 1.00e+04 0 4.95e-04 2.30e-03 + 1 5.036190e+00 1.02e+02 2.00e+01 2.16e+00 9.53e-01 3.00e+04 1 4.39e-05 2.40e-03 + 2 3.148168e-01 4.72e+00 2.50e+00 6.23e-01 9.37e-01 9.00e+04 1 9.06e-06 2.43e-03 + 3 1.967760e-02 2.95e-01 3.13e-01 3.08e-01 9.37e-01 2.70e+05 1 8.11e-06 2.45e-03 + 4 1.229900e-03 1.84e-02 3.91e-02 1.54e-01 9.37e-01 8.10e+05 1 6.91e-06 2.48e-03 + 5 7.687123e-05 1.15e-03 4.89e-03 7.69e-02 9.37e-01 2.43e+06 1 7.87e-06 2.50e-03 + 6 4.804625e-06 7.21e-05 6.11e-04 3.85e-02 9.37e-01 7.29e+06 1 5.96e-06 2.52e-03 + 7 3.003028e-07 4.50e-06 7.64e-05 1.92e-02 9.37e-01 2.19e+07 1 5.96e-06 2.55e-03 + 8 1.877006e-08 2.82e-07 9.54e-06 9.62e-03 9.37e-01 6.56e+07 1 5.96e-06 2.57e-03 + 9 1.173223e-09 1.76e-08 1.19e-06 4.81e-03 9.37e-01 1.97e+08 1 7.87e-06 2.60e-03 + 10 7.333425e-11 1.10e-09 1.49e-07 2.40e-03 9.37e-01 5.90e+08 1 6.20e-06 2.63e-03 + 11 4.584044e-12 6.88e-11 1.86e-08 1.20e-03 9.37e-01 1.77e+09 1 6.91e-06 2.65e-03 + 12 2.865573e-13 4.30e-12 2.33e-09 6.02e-04 9.37e-01 5.31e+09 1 5.96e-06 2.67e-03 + 13 1.791438e-14 2.69e-13 2.91e-10 3.01e-04 9.37e-01 1.59e+10 1 7.15e-06 2.69e-03 + + Ceres Solver v1.10.0 Solve Report + ---------------------------------- + Original Reduced + Parameter blocks 4 4 + Parameters 4 4 + Residual blocks 4 4 + Residual 4 4 + + Minimizer TRUST_REGION + + Dense linear algebra library EIGEN + Trust region strategy LEVENBERG_MARQUARDT + + Given Used + Linear solver DENSE_QR DENSE_QR + Threads 1 1 + Linear solver threads 1 1 + + Cost: + Initial 1.075000e+02 + Final 1.791438e-14 + Change 1.075000e+02 + + Minimizer iterations 14 + Successful steps 14 + Unsuccessful steps 0 + + Time (in seconds): + Preprocessor 0.002 + + Residual evaluation 0.000 + Jacobian evaluation 0.000 + Linear solver 0.000 + Minimizer 0.001 + + Postprocessor 0.000 + Total 0.005 + + Termination: CONVERGENCE (Gradient tolerance reached. Gradient max norm: 3.642190e-11 <= 1.000000e-10) + + Final x1 = 0.000292189, x2 = -2.92189e-05, x3 = 4.79511e-05, x4 = 4.79511e-05 It is easy to see that the optimal solution to this problem is at :math:`x_1=0, x_2=0, x_3=0, x_4=0` with an objective function value of @@ -447,24 +505,24 @@ gives us: .. code-block:: bash - 0: f: 1.211734e+02 d: 0.00e+00 g: 3.61e+02 h: 0.00e+00 rho: 0.00e+00 mu: 1.00e+04 li: 0 it: 0.00e+00 tt: 0.00e+00 - 1: f: 1.211734e+02 d:-2.21e+03 g: 3.61e+02 h: 7.52e-01 rho:-1.87e+01 mu: 5.00e+03 li: 1 it: 0.00e+00 tt: 0.00e+00 - 2: f: 1.211734e+02 d:-2.21e+03 g: 3.61e+02 h: 7.51e-01 rho:-1.86e+01 mu: 1.25e+03 li: 1 it: 0.00e+00 tt: 0.00e+00 - 3: f: 1.211734e+02 d:-2.19e+03 g: 3.61e+02 h: 7.48e-01 rho:-1.85e+01 mu: 1.56e+02 li: 1 it: 0.00e+00 tt: 0.00e+00 - 4: f: 1.211734e+02 d:-2.02e+03 g: 3.61e+02 h: 7.22e-01 rho:-1.70e+01 mu: 9.77e+00 li: 1 it: 0.00e+00 tt: 0.00e+00 - 5: f: 1.211734e+02 d:-7.34e+02 g: 3.61e+02 h: 5.78e-01 rho:-6.32e+00 mu: 3.05e-01 li: 1 it: 0.00e+00 tt: 0.00e+00 - 6: f: 3.306595e+01 d: 8.81e+01 g: 4.10e+02 h: 3.18e-01 rho: 1.37e+00 mu: 9.16e-01 li: 1 it: 0.00e+00 tt: 0.00e+00 - 7: f: 6.426770e+00 d: 2.66e+01 g: 1.81e+02 h: 1.29e-01 rho: 1.10e+00 mu: 2.75e+00 li: 1 it: 0.00e+00 tt: 0.00e+00 - 8: f: 3.344546e+00 d: 3.08e+00 g: 5.51e+01 h: 3.05e-02 rho: 1.03e+00 mu: 8.24e+00 li: 1 it: 0.00e+00 tt: 0.00e+00 - 9: f: 1.987485e+00 d: 1.36e+00 g: 2.33e+01 h: 8.87e-02 rho: 9.94e-01 mu: 2.47e+01 li: 1 it: 0.00e+00 tt: 0.00e+00 - 10: f: 1.211585e+00 d: 7.76e-01 g: 8.22e+00 h: 1.05e-01 rho: 9.89e-01 mu: 7.42e+01 li: 1 it: 0.00e+00 tt: 0.00e+00 - 11: f: 1.063265e+00 d: 1.48e-01 g: 1.44e+00 h: 6.06e-02 rho: 9.97e-01 mu: 2.22e+02 li: 1 it: 0.00e+00 tt: 0.00e+00 - 12: f: 1.056795e+00 d: 6.47e-03 g: 1.18e-01 h: 1.47e-02 rho: 1.00e+00 mu: 6.67e+02 li: 1 it: 0.00e+00 tt: 0.00e+00 - 13: f: 1.056751e+00 d: 4.39e-05 g: 3.79e-03 h: 1.28e-03 rho: 1.00e+00 mu: 2.00e+03 li: 1 it: 0.00e+00 tt: 0.00e+00 - Ceres Solver Report: Iterations: 13, Initial cost: 1.211734e+02, Final cost: 1.056751e+00, Termination: FUNCTION_TOLERANCE. - Initial m: 0 c: 0 - Final m: 0.291861 c: 0.131439 - + iter cost cost_change |gradient| |step| tr_ratio tr_radius ls_iter iter_time total_time + 0 1.211734e+02 0.00e+00 3.61e+02 0.00e+00 0.00e+00 1.00e+04 0 5.34e-04 2.56e-03 + 1 1.211734e+02 -2.21e+03 0.00e+00 7.52e-01 -1.87e+01 5.00e+03 1 4.29e-05 3.25e-03 + 2 1.211734e+02 -2.21e+03 0.00e+00 7.51e-01 -1.86e+01 1.25e+03 1 1.10e-05 3.28e-03 + 3 1.211734e+02 -2.19e+03 0.00e+00 7.48e-01 -1.85e+01 1.56e+02 1 1.41e-05 3.31e-03 + 4 1.211734e+02 -2.02e+03 0.00e+00 7.22e-01 -1.70e+01 9.77e+00 1 1.00e-05 3.34e-03 + 5 1.211734e+02 -7.34e+02 0.00e+00 5.78e-01 -6.32e+00 3.05e-01 1 1.00e-05 3.36e-03 + 6 3.306595e+01 8.81e+01 4.10e+02 3.18e-01 1.37e+00 9.16e-01 1 2.79e-05 3.41e-03 + 7 6.426770e+00 2.66e+01 1.81e+02 1.29e-01 1.10e+00 2.75e+00 1 2.10e-05 3.45e-03 + 8 3.344546e+00 3.08e+00 5.51e+01 3.05e-02 1.03e+00 8.24e+00 1 2.10e-05 3.48e-03 + 9 1.987485e+00 1.36e+00 2.33e+01 8.87e-02 9.94e-01 2.47e+01 1 2.10e-05 3.52e-03 + 10 1.211585e+00 7.76e-01 8.22e+00 1.05e-01 9.89e-01 7.42e+01 1 2.10e-05 3.56e-03 + 11 1.063265e+00 1.48e-01 1.44e+00 6.06e-02 9.97e-01 2.22e+02 1 2.60e-05 3.61e-03 + 12 1.056795e+00 6.47e-03 1.18e-01 1.47e-02 1.00e+00 6.67e+02 1 2.10e-05 3.64e-03 + 13 1.056751e+00 4.39e-05 3.79e-03 1.28e-03 1.00e+00 2.00e+03 1 2.10e-05 3.68e-03 + Ceres Solver Report: Iterations: 13, Initial cost: 1.211734e+02, Final cost: 1.056751e+00, Termination: CONVERGENCE + Initial m: 0 c: 0 + Final m: 0.291861 c: 0.131439 Starting from parameter values :math:`m = 0, c=0` with an initial objective function value of :math:`121.173` Ceres finds a solution @@ -635,10 +693,9 @@ as follows: ceres::Problem problem; for (int i = 0; i < bal_problem.num_observations(); ++i) { ceres::CostFunction* cost_function = - new ceres::AutoDiffCostFunction<SnavelyReprojectionError, 2, 9, 3>( - new SnavelyReprojectionError( - bal_problem.observations()[2 * i + 0], - bal_problem.observations()[2 * i + 1])); + SnavelyReprojectionError::Create( + bal_problem.observations()[2 * i + 0], + bal_problem.observations()[2 * i + 1]); problem.AddResidualBlock(cost_function, NULL /* squared loss */, bal_problem.mutable_camera_for_observation(i), @@ -713,5 +770,3 @@ directory contains a number of other examples: #. `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. - - |