6

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).

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?

EDIT:

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.

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

したがって、必要なのは、SVD から見つけられる G のヌル空間に最も近いベクトルです。テストしましょう:

% 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

OK、P はスカラーによって変化する可能性があることを思い出してください。したがって、一致することを示すために:

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

ans = 2.0000 3.0038 2.5037 -0.9997

于 2012-06-05T20:11:48.773 に答える
1

それはgriddataあなたが望むものかもしれません。リンクには例があります。

これでうまくいかない場合はgridfit、MATLAB 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

JohnD'Erricoによるコンソリデーターを試すことができます。与えられた許容範囲内でポイントを集約します。これにより、データの量を減らし、速度を上げることができます。また、ジョンのグリッドフィット関数を確認することもできます。これは通常、より高速で柔軟性があります。griddata

于 2012-06-06T13:53:43.277 に答える