Comparar estructuras tridimensionales

Question

Necesito evaluar si dos conjuntos de puntos 3d son los mismos (ignorando las traducciones y rotaciones) encontrando y comparando un hash geométrico apropiado. Hice algunas investigaciones en papel sobre técnicas de hashing geométrico, y encontré un par de algoritmos, que sin embargo tienden a complicarse por los "requisitos de visión" (por ejemplo, 2d a 3d, oclusiones, sombras, etc.).

Además, me encantaría que, si las dos geometrías son ligeramente diferentes, los valores hash tampoco son muy diferentes.

¿Alguien sabe algún algoritmo que se ajuste a mis necesidades y puede proporcionar algún enlace para estudiarlo más?

Gracias

Answer 1

Esta es la forma en que lo haría:

1. Posición los conjuntos en el centro de la masa
2. Calcular la inertia tensor. Esto le da tres ejes de coordenadas. Gíralas hacia ellos. [*]
3. Escriba la lista de puntos en un orden determinado (por ejemplo, de arriba a abajo, de izquierda a derecha) con la precisión requerida.
4. Aplica cualquier algoritmo que desees para una matriz resultante.

Para comparar dos conjuntos, a menos que necesite almacenar los resultados de hash por adelantado, simplemente aplique su algoritmo de comparación favorito a los conjuntos de puntos del paso 3. Esto podría ser, por ejemplo, calcular una distancia entre dos conjuntos .

No estoy seguro de si puedo recomendarle el algoritmo para el paso 4 ya que parece que sus requisitos son contradictorios. Cualquier cosa llamada hash generalmente tiene la propiedad de que un pequeño cambio en la entrada da como resultado una salida muy diferente. De todos modos, ahora reduje el problema a una matriz de números, por lo que deberías ser capaz de resolver las cosas.

[*] Si dos o tres de sus ejes coinciden, seleccione las coordenadas de alguna otra forma, p. como la distancia más larga. Pero esto es extremadamente raro para los puntos aleatorios.

Answer 2

parece como un problema de optimización numérica para mí. Desea encontrar los parámetros de la transformación que transforma un conjunto de puntos lo más cerca posible del otro. Define algún tipo de residuo o "energía" que se minimiza cuando los puntos son coincidentes, y arréglelo a algún optimizador de mínimos cuadrados o similar. Si logra optimizar la puntuación a cero (o tan cerca como se puede esperar dado el error de punto flotante), los puntos son los mismos.

googlear

least squares rotation translation 

gira hasta un edificio bastante pocos trabajos sobre esta técnica (por ejemplo "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns").

Actualizar el siguiente comentario a continuación: Si se desconoce la correspondencia uno a uno entre los puntos (asumida por el documento anterior), solo necesita asegurarse de que la puntuación minimizada es independiente del orden de puntos. Por ejemplo, si trata los puntos como masas pequeñas (esferas de radio finito para evitar la expansión a cero distancia) y establece minimizar la energía gravitacional total del sistema optimizando los parámetros de rotación de traducción &, eso debería funcionar.

Answer 3

Hay un montón de publicaciones de SIGGRAPH que pueden ser útiles para usted.

p. Ej. "Alineamiento global no rígido de 3-D los análisis" por Brown y Rusinkiewicz:

http://portal.acm.org/citation.cfm?id=1276404

Una búsqueda general que puede empezar:

http://scholar.google.com/scholar?q=siggraph+point+cloud+registration

Answer 4

spin images son un camino a seguir al respecto.

Answer 5

Su primer pensamiento puede estar tratando de encontrar la rotación que mapea un objeto a otro, pero este es un tema muy complejo ... ¡y en realidad no es necesario! No estás preguntando cuál es la mejor forma de unir los dos, solo preguntas si son iguales o no.

Caracterice su modelo por una lista de todas las distancias intermedias. Ordene la lista por esa distancia. Ahora compare la lista para cada objeto. Deben ser idénticos, ya que las distancias intermedias no se ven afectadas por la traslación o la rotación.

tres cuestiones:

1) ¿Qué pasa si el número de puntos es grande, eso es una gran lista de pares (N * (N-1)/2). En este caso, puede optar por quedarse solo con los más largos, o incluso mejor, conservar los 1 o 2 más largos para cada vértice, de modo que cada parte de su modelo tenga alguna contribución.La eliminación de información como esta sin embargo cambia el problema para que sea probabilístico y no determinista.

2) Esto solo usa vértices para definir la forma, no los bordes. Esto puede estar bien (y en la práctica lo será), pero si espera tener figuras con vértices idénticos pero bordes de conexión diferentes. Si es así, primero prueba la similitud de vértices. Si eso pasa, asigne una etiqueta única a cada vértice utilizando esa distancia ordenada. El borde más largo tiene dos vértices. Para cada uno de ESOS vértices, encuentre el vértice con el borde más largo (restante). Rotula el primer vértice 0 y el siguiente vértice 1. Repite para otros vértices en orden, y tendrás etiquetas asignadas que son independientes del desplazamiento y la rotación. Ahora puede comparar las topologías de borde exactamente (compruebe que para cada borde en el objeto 1 entre dos vértices, hay un borde correspondiente entre los mismos dos vértices en el objeto 2) Nota: esto comienza a volverse realmente complejo si tiene múltiples distancias de punto de intersección idénticas y por lo tanto necesita comparaciones de desempate para hacer las asignaciones estables y únicas.

3) Existe la posibilidad de que dos figuras tengan poblaciones idénticas de longitud de borde, pero no son idénticas ... esto es cierto cuando un objeto es la imagen especular del otro. ¡Esto es bastante molesto de detectar! Una forma de hacerlo es usar cuatro puntos no coplanarios (quizás los que están etiquetados como 0 a 3 del paso anterior) y comparar la "destreza" del sistema de coordenadas que definen. Si la destreza no coincide, los objetos son imágenes espejo.

Tenga en cuenta que la lista de distancias le permite rechazar fácilmente objetos no idénticos. También le permite agregar aceptación "difusa" al permitir una cierta cantidad de error en los pedidos. Quizás tomar la diferencia de raíz cuadrada entre las dos listas como una "medida de similitud" funcionaría bien.

Editar: Parece que su problema es una nube de puntos sin bordes. ¡Entonces el molesto problema de la correspondencia de bordes (n. ° 2) ni siquiera se aplica y se puede ignorar! Sin embargo, debes tener cuidado con el problema de la imagen especular n. ° 3.

Answer 6

1. Si desea estimación del rígida transformada entre dos nubes de puntos similares puede utilizar la bien establecida método iterativo punto más cercano . Este método comienza con una estimación aproximada de la transformación y luego se optimiza iterativamente para la transformación , al calcular los vecinos más cercanos y al minimizar una función de costo asociado . Puede ser implementado de manera eficiente (incluso en tiempo real) y hay disponibles implementaciones disponibles para Matlab, C++ ... Este método ha sido varias variantes extendidas y tiene, incluyendo la estimación no rígidos deformaciones, si está interesado en extensiones debe mirar papeles de gráficos por computadora que resuelven el problema de registro de escaneo , donde su problema es un paso crucial. Para un punto de partida vea el Wikipedia page on Iterative Closest Point que tiene varios buenos enlaces externos . Sólo un teaser de un matlab implementation que fue diseñado para que coincida con señalar las nubes: alt text http://www.mathworks.com/matlabcentral/fx_files/12627/1/icp.gif

   Después de la alineación se podía la medida error final a decir cómo es similar a los dos nubes de puntos son, pero esto es en gran medida una adhoc solución, no debería ser mejor.

2. Usando descriptores de forma uno puede huellas dactilares de cómputo de formas que son a menudo invariante bajo traducciones/rotaciones. En la mayoría de los casos están definidos para mallas, y no para nubes de puntos, sin embargo, hay una gran cantidad de descriptores de formas, por lo que dependiendo de su entrada y requisitos puede encontrar algo útil. Para esto, debería consultar el campo shape analysis, y probablemente this 2004 SIGGRAPH course presentation puede dar una idea de lo que hace la gente para calcular los descriptores de forma.

Answer 7

Quizás también deba leer sobre el algoritmo RANSAC. Se usa comúnmente para unir imágenes panorámicas, que parece ser un poco similar a su problema, solo en 2 dimensiones. Simplemente busca en Google RANSAC, panorama y/o costura para obtener un punto de partida.