6

我正在寻找将飞机安装到一组 ~ 6-10k 3D 点上。我希望尽可能快地做到这一点，而准确性并不是最关心的问题（坦率地说，飞机在任何基本轴上都可以偏离 +-10 度）。

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

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

编辑：

我设法通过在每个可能的 3D 角度创建平面（每次以 5 度步进）并针对这些点测试现有点以找到最佳平面，而不是将平面拟合到我有积分。

我敢肯定，通过分而治之也可以在这里获得一些东西，尽管我担心我会直接跳过最好的飞机。

4

4 回答 4

15

使用标准平面方程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

答案 = 2.0000 3.0038 2.5037 -0.9997

于 2012-06-05T20:11:48.773 回答
5

在计算机视觉中，一种标准方法是使用 RANSAC 或 MSAC，在您的情况下；

  1. 从总体中随机抽取 3 个点
  2. 计算由 3 个点定义的平面
  3. 将所有点到该平面的误差（到平面的距离）相加。
  4. 保留显示最小误差总和的 3 个点（并且在阈值内）。
  5. 重复 N 次迭代（参见 RANSAC 理论选择 N，我可以建议 50 次吗？）

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

于 2013-06-21T23:15:07.453 回答
1

看起来griddata可能是你想要的。该链接中有一个示例。

如果这不起作用，请查看gridfitMATLAB File Exchange。它是为了匹配比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
于 2012-06-05T15:30:16.260 回答
0

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

于 2012-06-06T13:53:43.277 回答