Ceres Solver: 高效的非线性优化库(一)

Ceres Solver: 高效的非线性优化库(一)

注:本文基于Ceres官方文档,大部分由英文翻译而来。可作为非官方参考文档。


简介

Ceres,原意是谷神星,是发现不久的一颗轨道在木星和火星之间“矮行星”(冥王星降级之后,同为矮行星)。Google开源了Ceres Solver库,是一个解很多非线性最优化问题的高效、方便的工具。


安装

引用地址:http://ceres-solver.org/installation.html

目前开源方未提供可安装文件。需要源码下载编译。
下载方式,首先安装Git。Git,主流版本管理工具,使用方法见官方文档。
git clone https://ceres-solver.googlesource.com/ceres-solver
依赖项:

  • Eigen,好用的数学库,无源码,全部是头文件。
  • CMake,工程生产工具,跨平台。
  • Glog,log库,选装。TBB,选装。
  • Gflags,SuiteSparse, CXSparse,BLAS,LAPACK主要是用来解大型稀疏矩阵的,必须要装。

Linux系统下可以很方便的用命令行安装各种库。
sudo apt-get install cmake libatalas-base-dev libeigen3-dev libsuitesparse-dev
安装Ceres-Solver,根据CMake的方式,进入Ceres目录,

mkdir build & cmake ..
make -j4
sudo make install

可以愉快的使用Ceres啦!先看Example,有示例嘛,学起来更快!
直接运行一下如下结果,
bin/simple_bundle_adjuster ../ceres-solver-1.14.0/data/problem-16-22106-pre.txt
似乎成功了?输出很多内容,好像看不懂。没关系,能运行成功,说明Ceres安装成功,可以愉快的使用。
注:这里解释的是更多在linux下面安装。Widows下基本大同小异,需要花点时间的是SuiteSparse几个三方库的安装和配置,不过也并不复杂。


实战

找到并使用Ceres-Solver

推荐使用CMake工具找到并使用Ceres,类似OpenCV。

什么是非线性最小二乘问题

Ceres-Solver可解形如下列公式的问题
\[ \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} \]
有点复杂,具体什么含义呢?
比如,平面(空间)很多带噪声的点,我们要拟合一条直线(平面)或曲线。比如,三维视觉的全局最优问题。
Ceres Solver: 高效的非线性优化库(一)
注意:直线拟合一般也可用线性回归解决。
公式中的目标函数集合称之为残差项,目标是是这个值最小;\(f_i\)函数被称为代价函数,由参数\(x_i\)组成。\(l_i, u_j\)则是函数的取值范围。
下面用了一个具体的示例说明。
求如下目标函数的最小值。
\[ \frac{1}{2}(10 -x)^2. \]
通过求二阶导数我们很容易知道x=10时,最小值取0.但这里我们尝试用Ceres来解决。

  • 第一步,代价函数\(f(x) = 10 - x\).
struct CostFunctor {
   template <typename T>
   bool operator()(const T* const x, T* residual) const {
     residual[0] = T(10.0) - x[0];
     return true;
   }};

代码中符号()是一个模板方法,输入是同一类型。

  • 第二步,构建非线性最小二乘问题。
int main(int argc, char** argv)
 {
  // The variable to solve for with its initial value.
  double initial_x = 5.0;
  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;
}

AutoDiffCostFunctionCostFunctor作为输入,并提供了一个自动求微分的接口。
计算example/helloworld.cc会得到相应输出结果。

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

实际上此示例是个线性问题,却能很好的解释非线性优化的思想。
接下来的文章会处理一些更加复杂的问题,敬请期待。

上一篇:ceres 点云平面拟合 实例


下一篇:如何在Mac下通过NDK来编译Ceres Android库