快速平面拟合多点

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

Answer 3

看起来

griddata

可能就是你想要的。该链接中有一个示例。

如果这不起作用，也许可以查看 MATLAB File Exchange 上的

gridfit

。它是为了匹配比

griddata

更一般的情况。

您可能不想滚动自己的表面配件，因为有几种记录良好的工具。

以

griddata

为例：

x = % some values 
y = % some values
z = % function values to fit to

ti = % this range should probably be greater than or equal to your x,y test values
[xq,yq] = meshgrid(ti,ti);
zq = griddata(x,y,z,xq,yq,'linear'); % NOTE: linear will fit to a plane!
Plot the gridded data along with the scattered data.

mesh(xq,yq,zq), hold
plot3(x,y,z,'o'), hold off

Answer 4

您可以尝试 John D'Errico 的consolidator。它将给定容差内的点聚合起来，这将减少数据量并提高速度。您还可以检查 John 的 gridfit 函数，它通常比

griddata

更快、更灵活

Answer 5

如果没有异常值，只是每个点的位置有一点误差，那么您可以选择任意 3 个间隔较远的点来定义平面。我就是这样做的：

1. 找到每个轴方向 +/- 极值处的 6 个点。这是对所有点的简单搜索。

2. 确定 3 对点中哪一对点在其轴方向上的间距最大。这些定义了平面上的一条线。

3. 找到距离这条线最远的第三个点。您不必进行全面的 3D 线点距离计算，只需投影从每个点到线的每个点距离即可。投影到垂直于长轴的平面上。