快速平面拟合到许多点 [英] Fast plane fitting to many points
问题描述
我正在寻找使飞机适应一组〜6-10k 3D点的方法.我希望尽快执行此操作，并且精度不是最重要的问题(坦率地说，该平面可以在任何基本轴上偏离+ -10度).
I'm looking to fit a plane to a set of ~ 6-10k 3D points. I'm looking to do this as fast as possible, and accuracy is not the highest concern (frankly the plane can be off by +-10 degrees in any of the cardinal axes).
我目前的方法是使用最佳拟合，但速度非常慢(我希望每次运行算法时以大约10-50k倍的速度提取平面，并且以此速度可以完成周，而不是小时)，因为它可以处理6000点的所有可能组合，因此〜35,000,000,000次迭代，并且坦率地说，它的精度比我需要的要高得多.
My current approach is to use best of best fit, but it's incredibly slow (I'm hoping to extract planes at a rate of about 10-50k times each time I run the algorithm, and at this rate it would finish in weeks, as opposed to hours) as it works on all possible combinations of 6000 points, so ~35,000,000,000 iterations, and frankly it has a much higher accuracy than I need.
有人知道任何较弱的平面拟合技术可能会大大加快我的算法的速度吗?
Does anybody know of any weaker plane-fitting techniques that might speed my algorithm up considerably?
我已经设法通过在每个可能的3D角度创建平面(每次以5度步进)并针对这些点测试现有点以找到最佳平面(而不是拟合)来将迭代次数降低至〜42k飞机到我的要点.
I've managed to get the number of iterations down to ~42k by creating planes at each possible 3D angle (stepping through at 5 degrees each time) and testing the existing points against these to find the best plane, instead of fitting planes to the points I have.
我敢肯定，通过分而治之，这里也会有所收获，尽管我担心我会直接越过最好的飞机.
I'm sure there's something to be gained here by divide and conquering too, although I worry I could jump straight past the best plane.
推荐答案
使用标准平面方程Ax + By + Cz + D = 0，并将该方程写为矩阵乘法. P是您未知的4x1 [A;B;C;D]
Use the standard plane equation Ax + By + Cz + D = 0, and write the equation as a matrix multiplication. P is your unknown 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，这是您要尽量减少的错误.
Now expand this to all your actual points, an Nx4 matrix G. The result is no longer exactly 0, it's the error you're trying to minimize.
G*P = E; % E is a Nx1 vector
因此，您想要的是最接近G的零空间的向量，可以从SVD找到该向量.让我们测试一下:
So what you want is the closest vector to the null-space of G, which can be found from the SVD. Let's test:
% 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可以随标量变化.因此，为了证明我们匹配:
OK, remember that P can vary by a scalar. So just to show that we match:
scalar = 2*P./P(1);
P./scalar
ans = 2.0000 3.0038 2.5037 -0.9997
ans = 2.0000 3.0038 2.5037 -0.9997
这篇关于快速平面拟合到许多点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
