Ajuste rápido del avión a muchos puntos

Question

Estoy buscando encajar un avión en un conjunto de ~ 6-10k puntos 3D. Estoy tratando de hacer esto lo más rápido posible, y la precisión no es la mayor preocupación (francamente el avión puede estar fuera de +10 grados en cualquiera de los ejes cardinales).

Mi enfoque actual es usar lo mejor de lo mejor, pero es increíblemente lento (espero extraer planos a una velocidad de aproximadamente 10-50k veces cada vez que ejecuto el algoritmo, y a este ritmo terminaría en semanas, en lugar de horas) ya que funciona en todas las combinaciones posibles de 6000 puntos, por lo que ~ 35,000,000,000 iteraciones, y francamente tiene una precisión mucho más alta que la que necesito.

¿Alguien sabe de alguna técnica de ajuste plano más débil que pueda acelerar mi algoritmo considerablemente?

EDIT:

he logrado obtener el número de iteraciones hasta ~ 42k mediante la creación de planos en cada ángulo posible en 3D (paso a paso a través a 5 grados cada vez) y prueba de los puntos existentes en contra de estos para encontrar el mejor avión, en lugar de adaptar los aviones a los puntos que tengo.

Estoy seguro de que hay algo que ganar aquí dividiendo y conquistando también, aunque me preocupa poder pasar directamente al mejor plano.

Answer 1

usar la ecuación plano estándar Ax + By + Cz + D = 0, y escribir la ecuación como una multiplicación de matriz. P es su desconocida 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 

Ahora ampliar esto a todos sus puntos actuales, una matriz NX4 G. El resultado ya no es exactamente 0, es el error que intenta minimizar.

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

Así que lo que quiere es el vector más cercano a la nula en el espacio de G, que se puede encontrar a partir de la SVD. Probemos:

% 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 

Bien, recuerde que P puede variar en escalar. Así que para demostrar que coinciden con:

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

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

Answer 2

Parece que griddata podría ser lo que quieras. El enlace tiene un ejemplo.

Si esto no funciona, tal vez consulte gridfit en MATLAB File Exchange. Está hecho para coincidir con un caso más general que griddata.

Probablemente no desee enrollar su propio accesorio de superficie, ya que existen varias herramientas bien documentadas.

tomar el ejemplo de 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

Usted puede probar el consolidator por John D'Errico. Agrupa los puntos dentro de una tolerancia dada, esto permitirá reducir la cantidad de datos y aumentar la velocidad.También puede verificar la función de John gridfit que es generalmente más rápido y más flexible que griddata

Answer 4

En la visión artificial, una forma estándar es usar RANSAC o MSAC, en su caso;

1. tomar 3 puntos al azar de la población
2. Calcular el plano definido por los 3 puntos
3. Sum los errores (distancia al plano) para todos los puntos a ese plano.
4. Mantenga los 3 puntos que muestran la suma más pequeña de errores (y caen dentro de un umbral).
5. Repetir N iteraciones (? Ver la teoría RANSAC para elegir N, puedo sugerir 50)

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