Ceres简介

Ceres Solver是谷歌的一个开源C++库,用于解决非线性优化问题,包括具有边界约束的非线性最小二乘问题和一般的无约束优化问题。在SLAM项目中Ceres用的非常多,港科大的VINS、谷歌的开源激光雷达SLAM项目Cartographer都有用到Ceres。Ceres的官方文档还是非常详细的,它的docs明确列举了这个库的features,这里就不一一赘述。

简单教程

非线性最小二乘问题

这里我简单搬运一下官方的tutorial。在很多领域,我们都会遇到如下形式的非线性最小二乘问题。
$$\begin{split}\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\end{split} \tag{1}$$
该类问题很常见,如统计学中的拟合曲线、基于图像的三维重建,三维重建的第一步Structure From Motion中的Bundle adjustment实际上就是个非线性最小二乘问题。
公式中的$\rho_i\left(\left\|f_i\left(x_{i_1},...,x_{i_k}\right)\right\|^2\right)$称作ResidualBlock,而$f_i(\cdot)$是关于参数向量$\left[x_{i_1},... , x_{i_k}\right]$的CostFunction 。$\rho_i$是LossFunction,它是一组标量,用于减少outliers对非线性最小二乘解的影响。

一个官方demo

考虑求函数$\frac{1}{2}(10 -x)^2$的最小值。很明显它在$x = 10$处有最小值。
Ceres第一步要求定义代价函数$f(x) = 10 - x$的functor,其代码如下:

struct CostFunctor {
   template <typename T>
   bool operator()(const T* const x, T* residual) const {
     residual[0] = T(10.0) - x[0];
     return true;
   }
};

方法operator()已经模板化了,这使得Ceres可以调用CostFunctor::operator<T>(),当需要残差的值时,T的类型为double,当需要Jacobians时,T的类型为Jet
之后使用代价函数$f(x)$,也就是上面的CostFunctor构建待求解的优化问题。

CostFunction* cost_function = 
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);

再配置求解器,设置如何求解、是否输出求解过程等参数,调用Solve方法即可得到结果。

int main(int argc, char** argv) {
  google::InitGoogleLogging(argv[0]);

  // The variable to solve for with its initial value.
  double initial_x = 0.5;
  double x = initial_x;

  // Build the problem.
  Problem problem;

  // Set up the only cost function (also known as residual). This uses
  // auto-differentiation to obtain the derivative (jacobian).
  CostFunction* cost_function =
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
  problem.AddResidualBlock(cost_function, NULL, &x);

  // Run the solver!
  Solver::Options options;
  options.linear_solver_type = ceres::DENSE_QR;
  options.minimizer_progress_to_stdout = true;
  Solver::Summary summary;
  Solve(options, &problem, &summary);

  std::cout << summary.BriefReport() << "\n";
  std::cout << "x : " << initial_x
            << " -> " << x << "\n";
  return 0;
}

该例的输出为:

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

这里发现官方文档有个问题,示例代码examples/helloworld.cc给出的迭代的初始值为$x=0.5$,而文档给定的初值为$x=5$,提供的结果却是$x=0.5$的,小问题还望大家注意。

PS

在编辑公式的时候发现一些坑,在此记录。我博客的公式是由MathJax在客户端上渲染出来的,然而Markdown会把LaTex的符号\当作转义符,造成公式显示错误。解决方法是公式中所有的\都写成\\,方法来自这篇文章。其实我测试的结果是并不是所有的\都要写两次,如果公式中有\begin\text这种符号前端就无法正确解析,需要将\写两次。对于Tex和Markdown之间的关系,我不甚了解,所以无法给出引起这个问题的结论。不过似乎\begin\text等是Tex独占的语法,Markdown原生并不支持,当然这只是我个人猜想而已,以后再去细究。