Piano veloce che si adatta a molti punti

Question

Sto cercando di adattare un piano a un set di ~ 6-10k punti 3D. Sto cercando di farlo il più velocemente possibile, e la precisione non è la preoccupazione più alta (francamente l'aereo può essere spento di + -10 gradi in uno qualsiasi degli assi cardinali).

Il mio approccio attuale è quello di utilizzare al meglio la soluzione migliore, ma è incredibilmente lento (spero di estrarre gli aerei ad una velocità di circa 10-50k volte ogni volta che eseguo l'algoritmo, ea questo ritmo finirebbe in poche settimane, a differenza di ore) poiché funziona su tutte le possibili combinazioni di 6000 punti, quindi ~ 35.000.000.000 di iterazioni e francamente ha una precisione molto superiore a quella di cui ho bisogno.

Qualcuno sa di tecniche di adattamento del velivolo più deboli che potrebbero accelerare considerevolmente il mio algoritmo?

EDIT:

Sono riuscito a ottenere il numero di iterazioni fino a ~ 42k con la creazione di aerei a ogni possibile angolo 3D (passando attraverso a 5 gradi ogni volta) e testare i punti esistenti nei confronti di questi per trovare il miglior aereo, invece di adattarsi ai punti che ho.

Sono sicuro che c'è qualcosa da guadagnare qui anche da dividere e conquistare, anche se mi preoccupo di poter saltare oltre il miglior aereo.

Answer 1

utilizzare l'aereo equazione standard Ax + By + Cz + D = 0, e scrivere l'equazione come una moltiplicazione matrice. P è il vostro sconosciuto 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 

Ora espandere questa a tutti i punti reali, una matrice NX4 G. Il risultato non è più esattamente 0, è l'errore che stai cercando di minimizzare.

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

Quindi, ciò che si vuole è il vettore più vicino al nulla-spazio di G, che si trova dalla SVD. Proviamo:

% 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, ricorda che P può variare in base a uno scalare. Quindi, solo per dimostrare che abbiniamo:

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

ans = 2,0000 3,0038 2,5037 -0,9997

Answer 2

Sembra che griddata potrebbe essere quello che vuoi. Il link ha un esempio in esso.

Se ciò non funziona, è possibile controllare lo gridfit sullo scambio di file MATLAB. È fatto per abbinare un caso più generale di griddata.

Probabilmente non si desidera eseguire il rollover del proprio raccordo di superficie, poiché sono disponibili numerosi strumenti ben documentati.

prendere l'esempio da 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 3

Si può provare il consolidator da Giovanni D'Errico. Raggruppa i punti all'interno di una data tolleranza, ciò consentirà di ridurre la quantità di dati e aumentare la velocità.Puoi anche controllare la funzione di John's gridfit che di solito è più veloce e più flessibile di griddata

Answer 4

In computer vision un modo standard è usare RANSAC o MSAC, nel tuo caso;

1. prendere 3 punti casuali dalla popolazione
2. Calcolare il piano definito da 3 punti
3. Somma gli errori (distanza di aereo) per tutti i punti di quel piano.
4. Conserva i 3 punti che mostrano la più piccola somma di errori (e rientrano in una soglia).
5. Ripetere n iterazioni (? Vedere teoria RANSAC scegliere N, mi permetto di suggerire 50)

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