Algoritmo de coincidencia de cuerpos rígidos y algoritmo de agrupación con grupos de líneas en 3D

Question

Llevo semanas luchando con este problema y no he podido encontrar un algoritmo adecuado para resolverlo. ¿Podrían darme algunos consejos o sugerencias para resolver esta cuestión? O si conocen a alguien que pueda responder a esta pregunta, por favor envíenlo. Realmente necesito la solución ya que he estado tratando de resolverlo durante mucho tiempo :| ¡Muchas gracias!

Como se puede ver en la imagen de abajo, tengo más de 200 líneas en 3D. Se trata de 3 grupos diferentes de líneas, y la propiedad común de las líneas de cada grupo es que pasan cerca del mismo punto. Sin embargo, en este problema no sabemos qué línea pertenece a cada grupo. Lo que se da son sólo las coordenadas 3D (x,y,z) de los 2 extremos de todas las líneas.

Mi trabajo consiste en encontrar un algoritmo que haga coincidir/ajustar/registrar un triángulo (un cuerpo rígido) a esas líneas de forma que la suma de las distancias entre 3 vértices del triángulo y sus correspondientes líneas sea mínima. En algunos casos, un vértice puede ser el punto más cercano de un grupo, pero los otros vértices serían arrastrados más lejos de sus líneas correspondientes (porque están en un cuerpo rígido), por lo que esta suma no será mínima. Lo que necesito son las mejores posiciones de los 3 vértices (el mejor ajuste del triángulo) para minimizar la suma global.

En conclusión, dados más de 200 conjuntos de (x1,y1,z1,x2,y2,z2) (que son coordenadas de 2 extremos de una recta), necesito encontrar las mejores posiciones de 3 vértices de un triángulo que encajen en esas rectas (dada la distancia relativa entre los 3 vértices).

Sin la condición de cuerpo rígido, he determinado con éxito las posiciones de los 3 puntos independientes utilizando el algoritmo de agrupación de Expectativa-Maximización (EM). Sin embargo, a veces se asignan 2 o 3 puntos a la misma posición. Entonces, me di cuenta de que había olvidado la condición de "cuerpo rígido". Con esta condición añadida, este error no se producirá. En el algoritmo EM, puedo derivar la fórmula de cada paso de reposicionamiento para cada punto. Pero cuando se trata de un cuerpo rígido, no sé cómo calcular la matriz de traslación y rotación para ajustar el triángulo a las líneas.

Gracias por leer este post. Su ayuda será muy apreciada.

Answer 1

Minimizar una suma de distancias es un poco más complicado que minimizar una suma de cuadrados de distancias. A menos que tengas una buena razón teórica para centrarte en la suma de distancias, yo sugeriría minimizar la suma de cuadrados.

En ese caso, un simple enfoque iterativo podría funcionar y converger rápidamente. Puedes optimizar alternativamente las posiciones de los puntos y las asignaciones de las líneas a los puntos. Empiece por asignar aleatoriamente (por ejemplo, uniformemente) cada línea a un punto. A continuación, obtén una primera estimación de la posición de cada punto resolviendo la ecuación lineal que obtienes al diferenciar la suma de los cuadrados de sus distancias a las líneas asignadas. A continuación, reasigna cada línea al punto más cercano a ella, reposiciona, reasigna, ... - esto debería converger bastante rápido; no puede quedarse atascado en un bucle porque cada paso que cambia la configuración disminuye la función objetivo. Si alguna vez te encuentras en una situación degenerada en la que uno de los puntos tiene menos de dos líneas asignadas, simplemente asigna una línea al azar si es necesario, y luego colócalo en algún lugar de la única línea asignada.

El mismo enfoque también debería funcionar si realmente quieres minimizar la suma de las distancias, pero entonces no obtienes una ecuación lineal en el paso de posicionamiento, y tendrás que realizar una optimización no lineal para las posiciones de los puntos.

---

[ Actualización: ]

Tanto Steven como yo olvidamos abordar el problema de optimizar la posición del triángulo, dada una asignación de las líneas a los puntos, teniendo en cuenta la restricción del cuerpo rígido. Así es como yo haría esto; este enfoque puede ser utilizado tanto con Steven o con mi sugerencia para la asignación de las líneas.

Había tomado su uso del término "línea" al pie de la letra, pero veo por la respuesta de Steven que como habla de dos extremos de una línea puede haber querido decir línea segmentos . Eso complicaría las cosas, y dado que los diagramas parecen que podrías salirte con la tuya ampliando los segmentos de línea a líneas, sólo me ocuparé de las líneas.

La distancia de un punto $\vec p$ de una línea a través de $\vec x$ en la dirección del vector unitario $\vec n$ puede expresarse como $(\vec p-\vec x)\times\vec n$ . Se puede escribir la función objetivo como

$$ f(\Omega,\vec a)=\sum_{i,j}\left|(\Omega\vec p_i+\vec a-\vec x_{ij})\times\vec n_{ij}\right|^2\;, $$

donde las variables representan los movimientos del cuerpo rígido, $\Omega$ una matriz de rotación y $\vec a$ un vector de traslación, $\vec p_i$ son los tres vértices en alguna posición de referencia del triángulo, y $\vec x_{ij}$ y $\vec n_{ij}$ describir el $j$ -a la línea asignada al $i$ -enésimo punto.

Primero podemos diferenciar esto con respecto a $\vec a$ para obtener

$$ \sum_{i,j}\left((\Omega\vec p_i+\vec a-\vec x_{ij})\times\vec n_{ij}\right)\times\vec n_{ij}=\vec0\;. $$

Se trata de una ecuación lineal para $\vec a$ que se puede resolver invirtiendo un $3\times3$ matriz que no depende de $\Omega$ , lo que le da $\vec a$ como una función lineal de $\Omega$ . La sustitución de esto en la función objetivo la reduce a

$$ f(\Omega)=\sum_{i,j}\left|(\Omega\vec p_i+\vec a(\Omega)-\vec x_{ij})\times\vec n_{ij}\right|^2\;. $$

Para minimizar esto con respecto a $\Omega$ escribiría $\Omega=\Omega_0\exp(\mathrm iA)$ con $\Omega_0$ el valor actual de $\Omega$ y $A$ antisimétrico, diferenciar con respecto a $A$ y establecer $A=0$ para obtener un gradiente con respecto a $A$ . Entonces se puede satisfacer la restricción antisimétrica del gradiente; esto nos da la dirección de $A$ a lo largo de la cual buscar, que define una familia de rotaciones parametrizadas por un solo ángulo, que puede optimizar mediante la optimización unidimensional estándar.

Se trata de un enfoque iterativo. Para encontrar el óptimo $\Omega$ para una asignación dada de las líneas a los puntos, tendrías que iterar hasta lograr la precisión deseada, pero si estás usando esto junto con mi enfoque de optimizar la asignación de las líneas a los puntos, podría ser más eficiente alternar entre optimizaciones unidimensionales simples y reasignación de las líneas hasta que la asignación ya no cambie, y sólo entonces iterar la búsqueda hasta la convergencia completa.

Answer 2

He aquí una idea:

//For minimization.
//Optimization tip with a danger of not finding the correct answer: 
//choose V a small number (Maybe iterating over some moderate vicinity  
//of a small number outweighs the inaccuracy.) 

 for all "possible assignments" of lines to each group(:=M) k=1:M    
  for each group i=1:3
   find the average of the coordinates specifying a line
    if the "variance_x" Or "variance_y" Or "variance_z" is more than V
     ignore the whole k'th assignment 

    for all "effective possible assignments" of lines to each group(:=N)  j=1:N   
     for group i=1:3  
      project all lines on x-y plane  
       for each line  
        find all collision points   
        x_xy = average(x_collisions)
        y_xy = average(y_collisions)  

      project all lines on x-z plane  
        for each line  
         find all collision points   
         x_xy = average(x_collisions)
         z_xz = average(z_collisions)

      project all lines on y-z plane  
       for each line  
        find all collision points   
         y_yz = average(y_collisions)
         z_yz = average(z_collisions)

    x_i = average(x_xy,x_xz)    
    y_i = average(y_xy,y_yz)  
    z_i = average(z_xz,z_yz)  

    //Calculate the quantity you want to minimize: sum_of_distances    
  P_j = sum_of_distances  

 choose the minimum of P_j

Wikipedia: para el cálculo de la Varianza

Answer 3

Yo adoptaría un enfoque algo diferente al de la solución de joriki: puesto que sabes que las líneas de cada clúster están cerca unas de otras, yo calcularía la matriz de distancias entre segmentos de líneas. Una vez que tengas esa matriz, puedes elegir un umbral para que los segmentos se agrupen de forma natural en tres grupos. Una forma simplista de hacerlo sería elegir un valor (de forma iterativa) para que el inducido (donde los nodos representan segmentos de línea y dos nodos tienen una arista entre ellos sólo cuando la distancia entre los segmentos es menor que el umbral) tiene tres componentes conectados; hay formas fáciles de contar los componentes conectados con DFS. De manera más realista (y más complicada), se podría elegir algún umbral ligeramente más flojo y luego utilizar algoritmos de agrupación social para determinar los tres grupos de líneas. Otra forma (poco relacionada) sería utilizar una técnica de optimización iterativa para asignar las líneas a los grupos, donde la "función de ponderación" que se optimiza es la suma sobre las líneas de la distancia máxima de esa línea a cualquier otra línea en su grupo actual.

Es muy posible que el conocimiento específico del dominio haga que este proceso sea aún más consistente; por ejemplo, si usted sabe que los vértices de su triángulo siempre estarán en la vecindad de los centros de sus líneas, entonces puede "recortar" sus segmentos para el cálculo de la distancia y eliminar cualquier distancia corta falsa-positiva basada en que dos líneas de diferentes clusters tengan puntos finales cerca el uno del otro.

Una vez que tenga las líneas agrupadas adecuadamente, encontrar la posición óptima de su triángulo debería ser un problema relativamente sencillo de optimización numérica: primero, elija una asignación de los vértices de su triángulo a los grupos de líneas (en realidad, querrá repetir el procedimiento para las seis asignaciones posibles y elegir la que produzca el mejor resultado global). Una vez que haya establecido qué clústeres están afiliados a qué vértices, entonces asociado a cualquier colocación de su triángulo puede calcular un función de aptitud : suma las distancias (al cuadrado) entre cada vértice y todas las líneas de su cluster afiliado. Cuanto más pequeño sea este valor, mejor será el ajuste, y esta función de aptitud no debería tener demasiados mínimos locales en los que quedar atrapado, por lo que se pueden utilizar técnicas de optimización estándar (por ejemplo, ideas como descenso de gradiente ) para encontrar el mejor ajuste.

El descenso gradual funciona para la optimización "siempre cuesta abajo": esencialmente, a partir de una colocación y orientación iniciales, calculas la diferencia en la función de aptitud entre todas las diversas "direcciones" en las que te puedes mover, encuentras la dirección con la mayor pendiente negativa y te mueves en esa dirección hasta que alcanzas un mínimo, y luego repites este procedimiento hasta que estás "lo suficientemente cerca". Esto es un poco más complicado, ya que tu espacio de configuración incluye una orientación (por lo que necesitarás un buen medio para optimizar sobre tu "esfera de direcciones"), pero la representación correcta te facilitará mucho las cosas. Un buen punto de partida también hará que estas búsquedas sean mucho más eficientes. Por ejemplo, puede que quieras aproximar las posiciones de los vértices encontrando el centroide de los "puntos de aproximación" de cada grupo, y luego empezar con tu triángulo en ese plano centrado en el punto medio de esos tres puntos centroides.