sba一个通用的稀疏光束法平差的软件包解析

如果你来到这个页面来寻找一个通用的Levenberg-Marquardt算法的C/C++实现，请看levmar引言：本页面是关于sba，一个通用的稀疏光束法平差的C/C++软件包。

它基于GNU通用公共许可证GPL分发的。

光束法平差（BA）是作为每个基于特征的多视重建视觉算法的最后一步，用来获得最佳的三维结构和运动（如相机矩阵）参数估计。

提供初始估计，BA同时精化运动和结构参数，通过最小化观测和预测的图像点之间的投影误差。

最小化一般通过Levenberg-Marquardt (LM)算法来辅助完成。

然而，由于许多未知的因素作用于最小投影误差，一个通用的LM算法的实现（如MINPACK的lmder）当应用于BA背景下的定义的最小化问题时，会带来极高的计算代价。

幸运的是，在基本的法方程中不同的三维点和相机参数相互之间影响较小，呈现一种稀疏的块结构（如图）。

Sba利用这种稀疏的特性，使用LM算法的简化的稀疏变量来降低计算的复杂度。

Sba是通用的，因为它保证了用户对于相机和三维结构的描述参数的定义的完全控制。

因此，它事实上可以支持任何多视重建问题的显示和参数化。

比如任意投影相机，部分的或完全标定的相机，由固定的三维点进行外方位元素（即姿态）的估计，精化本征参数，等等。

用户要想在这类问题中使用sba，只需要提供合适的程序对这些问题和参数来计算估计的图像投影和他们的函数行列式（Jacobian）。

用来计算解析的函数行列式可以是手头的代码，或者使用支持符号微分的工具（如maple）生成的代码，或者通过自动微分技术获得的代码。

也可以使用近似的函数行列式，辅之以有限差分的方法。

另外，sba包含了检查用户提供的函数行列式的一致性的程序。

就我们的知识之所及，sba是第一个并且也是当前独一无二的的软件包，因为他能够不受版权限制以源代码形式放置在任何工程中。

作为sba的效率的一个指标，我们在这里说明，sba的单次测试已经涉及54台相机和5207三维点，产生了24609个图像投影。

相应的最小化问题依赖于15999个变量，sba使用非最优的BLAS在Intel P4@1.8 GHz running Linux机器上大约7秒钟内解决。

如果没有BA的稀疏实现，那么这种规模的问题会变得非常棘手。

/lulyon/blog/item/70179866ed90132eaa184c1f.html又一个光束法平差库，由德国斯图加特大学发布。

名字很怪，不知道全称是什么。

引言程序DGAP 实现了光束法平差的摄影测量方法，由Helmut Schmid and Duane Brown 发明。

它基于图像和目标的几何关系的中心投影，使用最小二乘法。

特点Camera-/self-/simultan 标定，连同作者Brown, Ebner and Gruen 建议附加的参数。

两者可选的图像模型：直接线性变换（DLT）和仿射变换。

不同测量位置和/或姿态数据（GPS 支持的空三、直接地理参考）的集成。

精确的计算内外几何参数测试附加参数的意义计算协方差(新！)和相关性新：对分格摄影机图像（frame camera imagery）的扩展的摄影测量模型。

新：线扫描仪（line scanner）图像的直接地理参考。

新：空三（aerial triangulation，AT）的样例，GPS 支持的空三并且直接地理参考。

新：ADS-40 线扫描仪图像的直接地理参考样例。

版权/许可Copyright (C) 2005 Dirk StallmannThis program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of t heLicense, or (at your option) any later version.This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.下载地址：http://www.ifp.uni-stuttgart.de/publications/software/openbundle/index.en.html依赖库genlib2 提供了各种子程序以及模板类。

可以有选择的使用LAPACK 和BLAS。

LAPACK 是一个Fortran77 库，用来解数字线性代数中最常见的问题。

它又依赖于基本的线性代数子程序BLAS。

BLAS 也是一个Fortran77 库，提供优化的向量和矩阵操作。

两个库都是自由软件，并且拥有版权。

LAPACK 和BLAS 可在netlib 上获得: 为了在MS Windows 2000/XP 下编译DGAP，可以使用Cygnus 的GNU-win32 开发工具包“Cygwin” ()，版本1.3.6 或者更高。

LAPACK/BLAS 库在Cygwin 下依然可用。

安装在UNIX 或者Cygwin 下编译1、在同一目录下解压压缩包。

tar xzf genlib2-$RELEASE.tar.gztar xzf dgap-$RELEASE.tar.gz2、编译genlib2 库：cd genlib2-$RELEASEmake3、重命名这个目录为genlib2 或者创建一个符号链接：cd ..ln -s genlib2-$RELEASE genlib24、编译DGAP 程序cd ..ln -s genlib2-$RELEASE genlib2为了安装DGAP 只需要从主目录中复制程序dgap 到/usr/bin or /usr/local/bin.。

Sparse Bundle Adhustment 1.5使用指南Sparse bundle adjustment即稀疏集束调整，现在广泛应用于计算机视觉领域，基本成为最后优化的标准算法，就是在已经得到的初始摄像机参数和三维点数据的基础针对投影误差进行优化，得到使得均方投影误差最小意义下的Motion和Structure。

其算法的核心是利用Levenberg-Marquardt算法，由于视觉中问题的特殊性，造成矩阵稀疏，从而针对此特性进行求解。

这里介绍的是使用比较多的一个工具函数库，由希腊学者Manolis I.A.Lourakis和Antonis A. Argyros开发，网址为：http://www.ics.forth.gr/lourakis/sba。

这里我主要翻译下其中接口函数的使用说明：需要使用的结构体是struct sba_crsm，定义如下：struct sba_crsm{int nr,nc; // 稀疏矩阵的行和列int nnz; //非0元素数量int *val; //非0元素存储空间，大小为nnzint *colidx //非零元素的列下标，大小为nnzint *rowptr; //val中开始一行的位置，大小为:nr+1, rowptr[nr] = nnz}本结构体用于保存稀疏矩阵的元素（根据其定义可以看出，其存储过程其实对于稀疏矩阵按行扫描，得到非零元素出现的行和列，然后用colidx存储列下标，rowptr存储数据中新的一行出现的位置，非零结果存在val中。

）Sparse Bundle Adjustment通过函数sba_motstr_levmar_x()执行，函数原型如下：int sba_motstr_levmar_x(const int n, const int m, const int mcon, char * vmask, double *p, const int cnp, const int pnp, double *x, const int mnp,void(*func)(double *p, struct sba_crsm * idxij, int *wk1, int *wk2, double *hx, void *adata),void(*fjac)(double *p, struct sba_crsm * idxij, int *wk1, int *wk2, double *hx, void *adata),void *adata, int itmax, int verbose, double opts[3], double info[10];函数运行成功终止则返回达到最小需要的迭代次数，否则输入-1。

当前版本中假设观测向量的协方差矩阵为单位矩阵。

函数的核心是通过LU分解求解线性系统，使用LAPACK实现。

下面是用I,O分别表示输入和输出：n: 3D点的数量。

（I）m：摄像机的数量（图像）（I）mcon：从第一个摄像机开始不需要修正参数的摄像机的数量。

当我们将世界坐标系与第一个摄像机的坐标对齐的时候，第一个摄像机矩阵保持为[I 0] （I）vmask：点的可见性标志：mask[(i-1)*m + j -1] = 1 如果点i在图像j中可见，否则为0.需要注意的是点和摄像机的表示从1，2开始而矩阵下标则是从0开始。

Vamsk的大小为n*m（I）；p：作为输入，初始参数向量P0 = （a1,a2,…am, b1,b2,…bn）。

作为输出，估计的最小值，其大小为m*cnp+n*pnp (I/O);cnp: 定义一个摄像机的参数数量。

例如，欧氏摄像机参数化使用6个参数（3个旋转参数+3个平移参数）。

如果使用四元数表述旋转则参数的数量增加到7（4+3）。

完整的透视摄像机使用11个参数表示，如果包括全局的尺度因子则参数为12个（I）pnp：定义一个3D 点需要的参数数量，对于欧氏几何为3，对于投影空间为4 （I）x：观测向量X包括所有图像投影，顺序为（x11,x12,…,x1m,….xnm）.对于不可见的点，对应的xij消失。