快速平面拟合到许多点

Question

我希望将飞机安装到一组约6-10k的3D点上.我希望尽可能快地做到这一点,并且准确性不是最关心的问题(坦白地说,飞机可以在任何主轴上偏离+ -10度).

我目前的方法是使用最好的最佳拟合,但速度非常慢(我希望每次运行算法时以大约10-50k的速度提取平面,并且按照这个速率,它将在几周内完成,如同反对小时)因为它适用于所有可能的6000点组合,所以~35,000,000,000次迭代,坦率地说它具有比我需要的更高的准确度.

有没有人知道任何较弱的平面拟合技术可能会大大提高我的算法速度？

编辑:

通过在每个可能的3D角度(每次踩到5度)创建平面并测试现有点以找到最佳平面,而不是将平面安装到平面,我设法将迭代次数降低到〜42k.我有点.

我确信在这里可以通过分裂和征服获得一些东西,虽然我担心我可以直接跳过最好的飞机.

Answer 1

使用标准平面方程Ax + By + Cz + D = 0,并将方程式写为矩阵乘法. P是你的未知数4x1 [A;B;C;D]

g = [x y z 1];  % represent a point as an augmented row vector
g*P = 0;        % this point is on the plane

现在将其扩展到所有实际点,即Nx4矩阵G.结果不再是0,这是您尝试最小化的错误.

G*P = E;   % E is a Nx1 vector

所以你想要的是距离G的零空间最近的向量,它可以从SVD中找到.我们来测试一下:

% Generate some test data
A = 2;
B = 3;
C = 2.5;
D = -1;

G = 10*rand(100, 2);  % x and y test points
% compute z from plane, add noise (zero-mean!)
G(:,3) = -(A*G(:,1) + B*G(:,2) + D) / C + 0.1*randn(100,1);

G(:,4) = ones(100,1);   % augment your matrix

[u s v] = svd(G, 0);
P = v(:,4);             % Last column is your plane equation

好吧,记住P可以用标量变化.所以只是为了表明我们匹配:

scalar = 2*P./P(1);
P./scalar

ans = 2.0000 3.0038 2.5037 -0.9997

Answer 2

在计算机视觉中,标准方法是在您的情况下使用RANSAC或MSAC;

1. 从人口中取3个随机点
2. 计算由3个点定义的平面
3. 对该平面的所有点的误差(到平面的距离)求和.
4. 保持显示最小误差总和的3个点(并且落在阈值内).
5. 重复N次迭代(参见RANSAC理论选择N,我可以建议50吗？)

http://en.wikipedia.org/wiki/RANSAC