小程序开发文档/搜索引擎优化是什么意思

我讲一下用一组图片来做3D reconstruction需要的算法吧(SFM), 使用这种方法的软件比较代表性的有 Pix4Dmapper, Autodesk 123D Catch, PhotoModeler, VisualSFM

我用JavaScript撸了个WebSFM, 完全用Javascript实现的3D reconstruction系统，可以在浏览器里跑.

http://websfm.org , 用Chrome,Firefox,IE10+打开即可.

pipeline大致是:

先用SIFT对每张照片提取特征，再对每一对图片做鲁棒的特征匹配，将所有2图匹配合并，找出track，通过tracks估算相机参数场景的稀疏结构, 再用相机参数做dense reconstruction, 输出dense point cloud (with surface nornal)

如果需要,可以用poisson surface reconstruction将dense point cloud转化为polygon

------

SIFT (Scale Invariant Feature Transform)

同样的特征点在不同的scale，方向，光照下都能被检测到，并且理论上会有相同的描述向量. (即invariant)

SIFT有很多变种，但实际上很类似，一般是添加几种可以保持invariant的变换， 比如仿射变换.

一个SIFT特征有四个部分(位置position, 大小scale, 方向direction, 描述向量descriptor).

比较两点可以直接比较其特征向量，不用考虑别的参数.

特征点的position和scale是在DoG Pyramid中找到的extrema.

方向是在特征scale下周边梯度histagram的主导方向.

描述向量是特征scale下以特征方向为准的坐标系下的梯度histagram

-----

ANN Feature Matching (近似最邻近特征匹配)

找出两张图片之间特征向量的Nearest Neighbor，从而找出点与点之间的匹配关系。

这里输出的匹配是嘈杂的，存在错误, 且非常耗时.

先对两组特征(vs1[], vs2[])分别建立kd-tree

特征有128维，传统的kd-tree效果很差，需要对其进行平衡。在构建kd-tree选择hyperplane的时候，取方差最大的维度，在中位数处split.

为了加快速度，并不寻找严格NN, 而是在kd-tree上寻找ANN(Approximate NN).

匹配是否被采纳并不是使用传统的阀值，而是用一个优先序列来找ANN，最后通过第一与第二的距离比来确定是否采纳。同时v1,v2必须同时互为ANN，匹配(v1,v2)才被采纳.

-----

RANSAC:

用RANSAC和八点算法可以将嘈杂的匹配的结果稳定化.

适用情形: dataset存在少量错误，但服从一个constrain，并且constrain可以用dataset的一个很小的子集倒推回去。(在几何中这样的例子很多，比如给你某个平面上1000个点的坐标，但其中有错误数据，其constrain就是这个平面，而平面用3个点就可以确定)

原理: 随机抓一个subset并估算constrain，若subset中有错误数据，该constrain会很不准确，reject大部分数据；相反若subset中恰好都是正确数据，则会得到正确的constrain，accept大部分数据。因此不停的执行这个过程，直到找到正确的constrain，然后判定被其reject的数据为错误数据。(或因尝试次数过多退出)

在这里，dataset就是特征匹配输出的对应关系，而constrain就是核线几何(f-matrix), 用8个对应关系即可用八点算法估算出f-matrix. RANSAC可以筛除不符合核线几何的错误匹配.

------

Eight Point Algorithm (八点算法)

用八个点点对应关系计算核线几何(f-matrix)

两个Projective Camera之间的点点对应关系是需要满足核线几何的，就像三点可以确定一个平面一样，8对匹配可以确定两个相机的核线几何.

核线几何简单的讲就是 x1*F*x2=0, F是fundamental matrix (3x3, rank 2), x1,x2是相对应的两点的homogenous坐标。

将x1,x2代入后可以得到关于(f1,....f9)的一个线性方程，8对就是8个方程，再用SVD即可得最小二乘解.

------

Bundler Camera Registrtion

用tracks来估算相机参数.

bundler是incremental的，并且依赖于sparse bundle adjustment。初始化第一对相机后，便不断的用已知点估算新相机，并triangulate新的点，直到没有candidate为止，中间不断的做SBA来拟合新的参数, 并且每一轮做一次全局SBA。

------

SBA (Sparse Bundle Adjustemt)

SBA就是一个为view geometry优化之后的levenberg-marquardt非线性拟合算法. 在最小化projection error的时候，jacobian和hessian矩阵是稀疏的，而且存在特殊规律。利用了稀疏结构之后，就算有几千个变量需要拟合，速度也非常快。下图为sparse jacobian和sparse hessian.

-------

CMVS/PMVS (Dense Reconstruction)

使用surfel model的dense reconstruction, 比较复杂， 自己看吧

CMVS/PMVS: CMVS