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原生并不支持,当然这只是我个人猜想而已,以后再去细究。
0 条评论