Detectando el eje de rotación desde una nube de puntos

Question

Estoy tratando de detectar automáticamente el eje de rotación en una nube de puntos 3d.

En otras palabras, si tomé una pequeña nube de puntos 3d, elegí un único eje de rotación y realicé varias copias de los puntos en diferentes ángulos de rotación, y luego obtuve una nube de puntos más grande.

La entrada a mi algoritmo es la nube de puntos más grande, y la salida deseada es el eje único de simetría. Y eventualmente voy a calcular las correspondencias entre puntos que son rotaciones entre sí.

El tamaño de la nube de puntos más grande es del orden de 100K puntos, y se desconoce el número de copias de rotación realizadas.

Los ángulos de rotación en mi caso tienen deltas constantes, pero no necesariamente abarcan 360 grados. Por ejemplo, podría tener 0, 20, 40, 60. O podría tener 0, 90, 180, 270. Pero no tendré 0, 13, 78, 212 (o si lo hago, no me importa para detectarlo).

Esto parece un problema de visión artificial, pero tengo problemas para encontrar la forma de encontrar el eje con precisión. La entrada generalmente estará muy limpia, cerca de la precisión de flotación.

No tengo la nube de puntos más pequeña original que se rotó/copió para hacer la nube de puntos más grande. Sé que los datos son sintéticos con muy poco ruido (en general, es el resultado de otro programa).

No podemos calcular fácilmente el número posible de puntos en la nube más pequeña, porque justo a lo largo del eje los puntos no están duplicados, desafortunadamente. Si supiéramos qué puntos están a lo largo del eje, podríamos encontrar posibles factores, pero ya habríamos resuelto el problema.

-

Gracias a todos por sus sugerencias. Parece que mi último algoritmo intentará crear grupos de puntos coincidentes utilizando una métrica k-nn. Cada camarilla dará un eje. Entonces puedo usar RANSAC para ajustar un eje a los resultados de todas las camarillas.

Answer 1

Bueno, el siguiente enfoque puede ser útil, pero depende de la especificidad de sus datos. Se basa en las suposiciones de que la brecha entre las posiciones vecinas es lo suficientemente grande (20 grados probablemente sea bueno) y la pequeña nube de puntos se aproxima a una superficie (la última podría superarse). Sugiero usar la función de coincidencia local (la técnica popular en la visión por computadora).

En primer lugar, para cada punto de la nube grande debe calcular las descripciones locales (como SIFT o SURF para las imágenes). La más popular de las nubes de puntos es imagen Vuelta:

Johnson, A., & Hebert, M. (1999). Uso de imágenes de giro para el reconocimiento eficiente de objetos en escenas abarrotadas de 3 d. Transacciones IEEE sobre análisis de patrones e inteligencia artificial, 21 (5), 433-449. Citeseer. Obtenido de http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&type=pdf.

La modificación avanzada se utiliza aquí:

Endres, F., Plagemann, C., Stachniss, C., & Burgard, W. (2009). Descubrimiento no supervisado de clases de objetos a partir de datos de rango utilizando la asignación de Dirichlet latente. En Robótica: Ciencia y Sistemas. Seattle, EE. UU.

Si es computacionalmente difícil, pregúnteme cómo reducir la dimensionalidad sin perder mucho en poder discriminativo, lo he hecho una vez.

Luego debe hacer coincidir los descriptores, es decir, para encontrar los vecinos más cercanos para cada uno de ellos en su espacio de alta dimensión. Si la nube pequeña se ha girado 3 veces, debería haber 3 buenos vecinos más cercanos. Sin embargo, debido a las autointersecciones en la nube, las coincidencias probablemente contengan ruido. Aún debe encontrar el eje que se ajuste bien a una gran cantidad de coincidencias (aunque no a todas). Aquí puede usar un accesorio robusto como RANSAC (debe hacer algunos cálculos matemáticos para definir la probabilidad de una posición del eje para las coincidencias encontradas). Tenga en cuenta que difiere de los métodos que sugirieron los otros. Debería caber solo una línea en lugar de la familia de planos, según los descriptores, no los puntos originales (RANSAC probablemente no se ajuste a un avión con 4-5 puntos correctos y 100K valores atípicos).

También tenga en cuenta:

Si usted tiene la pequeña exploración que no se aproxima a una superficie, se debe llegar a un descriptor de rotación invariante diferente, no girar imágenes.

Para calcular normales y realizar la recuperación, puede consultar esta biblioteca: http://graphics.cs.msu.ru/en/science/research/3dpoint/lidark (próximamente se lanzará una versión principal).

Answer 2

1) Si encuentra el centroide C de la nube de puntos más grande, ISTM el eje de rotación original tendría que pasar por ese punto.

No importa: no vi el requisito de que las rotaciones no abarquen un círculo completo. Para su ejemplo de 20,40,60, el centroide no estaría en el eje de rotación.

¿Quizás la siguiente referencia podría ayudar?

"Reconstrucción de superficies de revolución con muestreo parcial" http://portal.acm.org/citation.cfm?id=980064

Answer 3

algunos puntos :)

1. Si tenemos 1 punto inicial nunca se hace girar a continuación, hay un número infinito de ejes.
2. Si tenemos 1 punto inicial girado 1 veces, entonces también hay un número infinito de ejes.
3. Si tenemos 1 punto inicial y lo rotamos 2 veces, podemos encontrar el eje porque 3 puntos determinan un plano de forma única. Perpendicular al cual, a través del punto equidistante de cada uno de los 3 puntos (1 inicial + 2 girados) es el eje.
4. Tenga en cuenta que girar 360 no tiene sentido.

---

1. elegir cualquiera punto (P) de la nube.
2. Trace el locus (L) del punto P (como P está girando sobre algunos ejes, L debe ser un círculo)
3. Perpendicular al plano del círculo (L) que pasa por su centro es el eje de rotación de la nube.

Lo que quiero decir es que el eje de rotación de un cuerpo rígido es el mismo que el eje de rotación de una sola partícula del cuerpo. No necesitamos preocuparnos por todos los otros puntos.

Answer 4

Elija cualquier punto y encuentre otros dos puntos que sean equidistantes de él. Esto debería tomar O (n^2) en el peor de los casos, pero la heurística puede reducirlo en gran medida. Estos tres puntos determinan de manera única un círculo. Si hay un cuarto punto a la misma distancia del primero o del tercer punto, eso aumenta su confianza en el círculo.

El centro del círculo es un punto en el eje, y el vector normal del círculo es el vector direccional del eje.

Dado el eje, puede determinar el ángulo entre las rotaciones y verificar su conjetura con algunos otros puntos. Si está mal, elige otro punto y comienza de nuevo.

Editar: Por cierto, obviamente esto no es determinista, pero si los datos de su punto son tan limpios como dice y utiliza una buena heurística, debería ser bastante preciso.

Answer 5

Eche un vistazo a las técnicas utilizadas en visión estéreo para calcular la homografía entre dos imágenes: su problema con conjuntos de nubes de puntos parece análogo a los puntos coincidentes en múltiples imágenes del mismo objeto/escena. Parece que podría aplicar un algoritmo RANSAC para calcular una transformación entre sus conjuntos de nubes de puntos.

Answer 6

Una idea loca ...

Si el mismo punto se gira alrededor del mismo eje varias veces, todos los puntos se encuentran en el mismo plano. Dependiendo de su conjunto de datos, podría ser posible detectar este plano usando el método de ransac.

El eje de rotación será perpendicular a este plano, y debería ser relativamente fácil determinar la ubicación del eje una vez que se ha determinado su orientación.

Answer 7

Lo siguiente asume que hay 3 o más copias. Considere el casco convexo de la gran nube de puntos. Encuentra dos de sus caras que son paralelas. El eje de rotación será perpendicular a estos. Si encuentra más de un par, simplemente pruebe cada orientación.

Obviamente, esto no funciona si los puntos más extremos según el eje están justo en el eje, sin embargo, en el caso general, esto es muy raro.

Answer 8

Hay 2 cosas que usted debe considerar:

1. El lapso angular de la nube de puntos.
2. El ángulo de rotación.

Ahora, si (rotation> span) la solución es más simple, porque tiene que buscar un subpatrón y, en función de su aparición, intente hacer coincidir un patrón más grande.

en el caso (rotación < span), tendrá que mirar más de cerca los efectos de borde, porque dentro de la región (después de la primera rotación, antes de la última rotación) todavía tendrá una nube de puntos simétrica, con un ángulo de simetría = ángulo de span; como en el caso anterior.

En caso de que no sepa en qué categoría se cae, es seguro asumir en el segundo.

Como se mencionó anteriormente, RANSAC es el mejor método de emparejamiento de patrones, porque lleva menos tiempo y da resultados decentes. El único problema que le queda es el ángulo de estimación del alcance de la mini nube de puntos durante la inicialización. esta estimación es difícil de hacer.Entonces, si tienes suficiente potencia/tiempo de cálculo, te sugiero que iteres con pasos de 1 grado. comenzando desde un modesto grado de 5 grados para decir 45 grados. A medida que los resultados comienzan a converger, aumente la precisión angular.

Answer 9

Desde la nube de puntos original es pequeña, la solución más simple podría ser RANSAC:

1. elegir tres puntos al azar
2. Compute el eje de rotación para estos puntos (línea perpendicular al círculo y pasa a través de el centro)
3. ¿Los otros puntos están de acuerdo?
4. Si no, iterar hasta eje correcto encontró

La probabilidad de que una estimación correcta es 1/((n-1) (n-2)), donde n es el número de puntos en la nube originales . Dado que cada prueba se puede realizar muy rápidamente, este podría ser un enfoque útil.