最小二乘法拟合一些基本空间元素的C#实现 —— (一)术语、基本算法与思路

本系列的主要目的是将拟合算法用C#实现,相关的操作用到了Math.NET数值运算库,所以将一些基本概念,算法和对应的C#代码放到前面。

对于线性模型,例如直线和平面,算法大约分三步:

  1. 参数化:将模型用参数化方式表达出来。
  2. 构造Design(非线性中的Jacobian)矩阵:根据参数公式求所有参数的偏导数作为列(Column),将实测值作为行(Row)。将偏差值作为等式右值。
  3. 求解。

对于非线性模型,例如圆柱,Gauss-Newton算法类似:

  1. 参数化:
  2. 求(或猜)初始解。
  3. 找到Jacobian矩阵及右值
  4. 求解
  5. 通过4计算逼近值,重复3和4
  6. 迭代结束

线性模型的解法是基础,详细的分析请看这篇文章,这里只解释代码部分。在Math.Net

对于矩阵\(A=\begin{bmatrix}A_{11} & A_{12}\\A_{21} & A_{22}\end{bmatrix}\)
A.Transpose() 代表A的转置矩阵\(A^T=\begin{bmatrix}A_{11} & A_{21}\\A_{12} & A_{22}\end{bmatrix}\)

这在坐标运算中是非常重要的,因为坐标运算中坐标系都表示为正交矩阵(抱歉,没找到证明),当计算一个点(用二维举例)\(P=\left(x,y\right)\)在新坐标系A中的坐标\(P^{‘}=\left(x^{‘},y^{‘}\right)\)时。\[P^{‘}=PA\]

而已知坐标系A中的坐标点\(P^{‘}\)求原坐标值可用\[P=P^{‘}A^T\]

一些类似的代码为:

A.Inverse()代表A的逆矩阵\(A^{-1}\)

A.Multiply(B)代表矩阵乘法\(A*B\)或者矩阵乘以向量\(A*b\)

对于常用的算法:

线性模型

已知Jacobian矩阵\(J\)及等式右值(偏差值向量)\(y\),另\[Ax=y\]求解向量x

  1. 正规方程(normal equations)
    \[A^TAx=A^Ty\]
    逆矩阵解法
    \[x=\left(A^TA\right)^{-1}A^Ty\]
    实现代码 
    x = A.Transpose().Multiply(A).Inverse().Multiply(A.Transpose().Multiply(y));

    更快和更稳定的方法将是对左侧的矩阵进行乔姆斯基分解(Cholesky decomposition),实现代码

    x = A.Transpose().Multiply(A).Cholesky().Solve(A.Transpose().Multiply(y));

    这两个在一些限定条件下是等价的,而这些限定条件在点数远大于参数的情况下是满足的。

  2. QR分解
    推论见原文,代码更简单: 
    x=A.QR().Solve(y);
  3. 奇异值分解(Singular Value Decomposition, SVD)
    A是方阵的情况下(即点数等于参数)代码为 
    x = A.Svd(true).Solve(y);

    A不是方阵的情况下代码为

// compute the SVD 
Svd svd = A.Svd(true);
// get matrix of left singular vectors with first n columns of U 
Matrix U1 = svd.U().SubMatrix(0, m,0, n); 
// get matrix of singular values 
Matrix S = new DiagonalMatrix(n, n, svd.S().ToArray()); 
// get matrix of right singular vectors 
Matrix V = svd.VT().Transpose(); 
x = V.Multiply(S.Inverse()).Multiply(U1.Transpose().Multiply(y));

非线性模型

这部分对于代码并没有什么区别,只是需要迭代(循环)及判断终止条件。

业余码农选择C#的理由

在网上看了太多又臭又长的类似文章,从方方面面夸或者黑某种语言,我选择C#的理由很简单,所以如果有和我类似情况的,我也推荐你选择C#作为开发语言。

我的情况:

1.公司提供的工作环境和客户的工作站全部是Windows环境。

2.开发程序的规模要求比较小:
比如:不会有大规模的客户端连接,也不需要数据量,负载等等,像我自己目前开发的小程序都是订制型的,客户的数量都是个位数的。

3.对C或C系列语言有些基础,比如(C,C++,JAVA等等)。

C#的优点:

1.免费,因为我写的程序虽然小,但是的确是以公司的名义提供给客户的,当然是收费的,所以选择免费的开发工具是很有必要的。而目前VS Express已经做到了完全免费,除了开发大型软件需要的功能,所有桌面级别的功能全部是免费的。

2.配置简单,千篇一律可能是专业开发人员的槽点,我上大学时也以自己搭建开发环境为兴趣,但是当我只想花一天写一个坐标转换的小程序时,VS Express这种高度集成的开发工具帮助极大,Express不支持绝大部分的插件和订制(专业版可以),但是好处是当你遇到一引起问题,你看到的问题解答中的界面和你永远是一样的,对于初学者这其实是很友好的。

3.语言的自解释,这本来是一种开发者写代码时需要注意的事项,但是我觉得.NET系列语言做得非常好,.NET库是不需要头文件的!刚开始我四处找头文件,后来发现当你引用一个库时,所有的函数及参数列表都是可见,而且所有.NET程序都可以非常简单的反编译,推荐ILSPY,这意味着你不用任何参考就可以直接使用函数,如果愿意还可以看到源码实现。(这叫强制开源吧。。。)

4.部署方便,Win7默认包含.NET 3.5,这意味着你开发的任何一个程序都可以在所有的Win7上运行,不用考虑环境设置,库的引用,而且程序非常小(我之前使用QT开发,最让人郁闷的一点就是任意带GUI的程序都要10M以上)。

缺点:

1.跨平台,很难在其他平台上使用,虽然有MONO,但是不免费。

2.库相对少,并不意味着没有,只不过当你 的需求非常专业,那么C++的历史在那摆着,库肯定多且专业,参考资料也多。
实际上C#的库比较多,但是因为自解释的原因吧,专业人员用起来肯本不需要文档,初学者就会很郁闷了。