Ceres 翻譯為谷神星，是太陽系中的一顆矮行星，于1801年被意大利神父 Piazzi 首次觀測到，但隨后 Piazzi 因為生病，跟丟了它的運行軌跡，
幾個月后，德國數學家 Gauss，利用最小二乘法，僅僅依靠 Piazzi 之前觀測到的12個資料，便成功的預測了谷神星的運行軌跡，
兩百多年后，為了解決一些復雜的最優化問題 (如：帶邊界約束的非線性最小二乘、一般的無約束最優化等)，谷歌開發了一個 C++ 庫 Ceres Solver
之所以取名 Ceres Solver，是為了紀念 Gauss 利用最小二乘法，成功的預測了谷神星軌跡，這個在最優化、統計學、天文學歷史上，都具有重要意義的事件
1 Ceres 簡介
1.1 特點
1) 模型介面簡潔
- 求導簡單；魯棒的損失函式；區域引數化
2) 求解方法多
- 信賴域法：Lenberg-Marquardt, Powell’s Dogleg, Subspace dogleg
- 線搜索法：Non-linear Conjugate Gradients, BFGS, LBFGS
3) 求解質量高
- 在 NIST 資料集下，按照 Mondragon 和 Borchers 的測驗標準，Ceres 的準確度最高
1.2 應用
在谷歌內部，Ceres 已經被應用于多個產品中，如：谷歌街景中汽車、飛行器的位姿估計；PhotoTours 中 3D 模型的建立；SLAM 演算法 Cartographer 等
此外，一些公司和研究所也在使用 Ceres，像是 Southwest Research Institute 的機器人視覺系統標定，OpenMVG 的光束平差 (BA) 問題，Willow Garage 的 SLAM 問題等
1.3 非線性最小二乘
帶邊界約束的非線性最小二乘形式，如下：
$\quad \begin{split} \min_x &\quad \frac{1}{2}\sum_{i} \rho_i\left(\left\|f_i\left(x_{i_1}, x_{i_2}, ... ,x_{i_k}\right)\right\|^2\right) \\\text{s.t.} &\quad l_j \le x_j \le u_j \end{split}$
其中，1) s.t. = "subject to"，限定了 $x_j$ 的取值范圍
2) $ \rho_i\left(\left\|f_i\left(x_{i_1},x_{i_2},...,x_{i_k}\right)\right\|^2\right) $ 為殘差塊
3) $f_i(\cdot)$ 為代價函式，取決于引數塊 $\left[x_{i_1},x_{i_2},... , x_{i_k}\right]$
4) $\rho_i$ 為損失函式，是一個標量函式，主要用來消除例外點對求解程序的影響
如果令損失函式 $\rho_i = x$ 為恒等函式，且放寬邊界約束條件為 $[-\infty, \infty]$
則非線性最小二乘問題，可簡化為如下形式：
$\quad \begin{split}\frac{1}{2}\sum_{i} \left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2 \end{split}$
上面的最小二乘形式，在科學和工程領域有著廣泛的應用，例如，統計學中的曲線擬合，計算機視覺的三維重建等
2 編譯配置
Win10 64-bit ；VS 2019 社區版，下載地址 ；CMake 解壓版，下載地址
2.1 源檔案
- Ceres Solver 源檔案，下載地址，從 2.0 開始，需要支持 C++14 的編譯器
- eigen 源檔案，必須，>=3.3，下載地址
- glog 源檔案，推薦，>=0.3.1，下載地址，及其依賴庫 gflags，下載地址
2.2 配置生成
1) 將源檔案 ceres、eigen、glog 和 gflags 解壓，運行 cmake-gui.exe，配置生成 eigen (先點 "Configure"，再點 "Generate" 即可)
2) 編譯 gflags，先點 "Configure"，再點 "Generate"，然后點 "Open Project"，在 VS 中打開工程，最后在 debug 和 release 模式下分別編譯
3) 編譯 glog，操作同 3)，其中 cmake 配置不再贅述，如：CMAKE_CONFGURATION_TYPES 只保留 Debug 和 Release，gflags_DIR 指向含 gflags-config.cmake 的目錄等
4) 編譯 ceres，操作同 3)，注意配置 eigen、glog 和 gflags 的 _DIR 目錄，并勾上 BUILD_SHARED_LIBS 以便生成 dll 庫
2.3 VS 配置
將生成的 .lib 和 .dll 檔案放在特定目錄下，并新建 include 檔案夾，匯總對應的 .h 檔案
1）環境變數
計算機 -> 屬性 -> 高級系統設定 -> 環境變數，編輯系統變數里的 path 變數
D:\3rdparty\gflags\bin\Debug D:\3rdparty\glog\bin\Debug D:\3rdparty\ceres\bin\Debug
2) 頭檔案和庫檔案
在 VS 中配置 ceres, eigen, glog 和 gflags 的 頭檔案目錄，以及 庫檔案目錄
注：在編譯時，若出現頭檔案缺失，則在源檔案中找到對應的 .h，拷貝到 include 目錄中即可
3) 依賴庫
添加對應的 .lib 依賴庫，如下：
ceres-debug.lib gflags_debug.lib glogd.lib
4) 錯誤處理
運行程式，如出現如下錯誤，則在 "專案屬性 - 前處理器定義" 中，定義 _USE_MATH_DEFINES 宏可解決
3 代碼實體
給定一個目標函式 $\begin{split} \frac{1}{2}(10 -x)^2 \end{split}$，求其取最小值時，對應的 $x$ 為多少
3.1 求解步驟
1) 構建代價函式
Ceres 中利用仿函式，通過多載 operator() 運算子，來實作代價函式的定義，本例中的代價函式為 $f(x) = 10 -x $
// A templated cost functor that implements the residual r = x - 10
struct CostFunctor {
template <typename T> bool operator()(const T* const x, T* residual) const {
residual[0] = x[0] - 10.0;
return true;
}
};
2) 構建殘差塊
// Build the problem
Problem problem;
// Set up the cost function (also known as residual)
CostFunction* cost_function = new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
problem.AddResidualBlock(cost_function, NULL, &x);
3) 配置求解器
// The options structure, which controls how the solver operates
Solver::Options options;
options.linear_solver_type = ceres::DENSE_QR;
options.minimizer_progress_to_stdout = true;
4) 求解
// Run the solver
Solver::Summary summary;
Solve(options, &problem, &summary);
3.2 完整代碼
#include "ceres/ceres.h"
using ceres::AutoDiffCostFunction;
using ceres::CostFunction;
using ceres::Problem;
using ceres::Solver;
using ceres::Solve;
// A templated cost functor that implements the residual r = x - 10.
struct CostFunctor {
template <typename T> bool operator()(const T* const x, T* residual) const {
residual[0] = 10.0 - x[0];
return true;
}
};
int main()
{
// The variable to solve for with its initial value
double x = 0.5;
const double initial_x = x;
// Build the problem.
Problem problem;
// Set up the cost function (also known as residual)
CostFunction* cost_function = new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
problem.AddResidualBlock(cost_function, NULL, &x);
// The options structure, which controls how the solver operates
Solver::Options options;
options.linear_solver_type = ceres::DENSE_QR;
options.minimizer_progress_to_stdout = true;
// Run solver
Solver::Summary summary;
Solve(options, &problem, &summary);
std::cout << summary.BriefReport() << "\n";
std::cout << "x : " << initial_x << " -> " << x << "\n";
}
運行結果如下：
參考資料
Ceres Solver 在 Windows 下的安裝
Mondragon 和 Borchers 標準對比測驗
原文鏈接： http://www.cnblogs.com/xinxue/
專注于機器視覺、OpenCV、C++ 編程
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/424930.html
標籤：其他