分类 Cpp tutorial 下的文章

Ceres solver简介


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


C++多线程编程——C++11 thread初探


引言

由于项目需要,尝试在代码中引入多线程操作。看了一些博客介绍多线程,但普遍为入门级别的教程;尝试在项目中使用,性能又不忍直视,遂决定在博客中记录C++多线程的学习过程。
std::thread是C++11引入的新特性,在此之前只能使用Windows api或Linux的Pthread编写多线程程序,增加了代码跨平台移植的难度。C++11后,我们可以在编程语言层面使用多线程。本系列文章主要探讨C++标准库的多线程。

简单例程

std::thread类声明在头文件<thread>中。下面给出一个最基本的使用例程

// thread example
#include <iostream>       // std::cout
#include <thread>         // std::thread
 
void foo() 
{
  // do stuff...
}

void bar(int x)
{
  // do stuff...
}

int main() 
{
  std::thread first (foo);     // spawn new thread that calls foo()
  std::thread second (bar,0);  // spawn new thread that calls bar(0)

  std::cout << "main, foo and bar now execute concurrently...\n";

  // synchronize threads:
  first.join();                // pauses until first finishes
  second.join();               // pauses until second finishes

  std::cout << "foo and bar completed.\n";

  return 0;
}

该例输出为:

main, foo and bar now execute concurrently...
foo and bar completed.

该段代码首先声明了两个线程并在构造期间传入相应的函数和参数,之后线程就调用相应函数,该函数的参数即由线程构造函数中的参数给出。在线程执行完之前,主线程main等待子线程的执行完成(join)。

小结

本文仅仅示例了std::thread最简单的用法,它只是后续内容的一个引子。希望自己多学习多思考多记录多交流,做出一些微小的贡献。


从中序与后序遍历序列构造二叉树


问题
  根据一棵树的中序遍历与后序遍历构造二叉树。可以假设数中没有重复元素。
  例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

  返回以下的二叉树

分析
  首先明确两点:
  1. 后序遍历输出的数组,最后一个元素为树根。
  2. 中序遍历输出的数组,树根左边的元素构成左子树,树根右边的元素构成右子树。
  基于这两点,可以先从后序遍历中找到整个树的树根,再在中序遍历的结果中找到该树根,树根左边的元素即为左子树,右边的元素即为右子树。至此,该问题形成一个递归问题--左子树和右子树在后序遍历中也分别对应一个数组集合,对左子树和右子树分别递归即可还原原来的二叉树。

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*   int val;
*   TreeNode *left;
*   TreeNode *right;
*   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if(inorder.size()!=postorder.size())
      return NULL;
    if(inorder.size()==0 || postorder.size()==0)
      return NULL;

    int length=inorder.size();
    TreeNode* root=new TreeNode(postorder[length-1]);
    int root_inorder_index=-1;
    vector inorder_l,inorder_r,postorder_l,postorder_r;
    for(int i=0;i<length;i++)
      if(inorder[i]==postorder[length-1]){
        root_inorder_index=i;
        break;
      }

    for(int i=0;i<root_inorder_index;i++){
      inorder_l.push_back(inorder[i]);
      postorder_l.push_back(postorder[i]);
    }

    for(int i=root_inorder_index+1;i<inorder.size();i++){ 
      inorder_r.push_back(inorder[i]); 
      postorder_r.push_back(postorder[i-1]); 
    } 

    root->left=buildTree(inorder_l,postorder_l);
    root->right=buildTree(inorder_r,postorder_r);
    return root;
  }
};