Orientación robusta de una nube de puntos

Question

Tengo nubes de puntos en 2D que son simétricas de 4 maneras (invariantes por rotación de 90°). Los puntos suelen estar dispuestos en los nodos de una cuadrícula cuadrada, densamente poblados, pero algunos casos pueden ser más complicados. Conozco el patrón de puntos de antemano.

Necesito encontrar los ejes de simetría, que están orientados de manera arbitraria. Inicialmente pensé en los momentos de inercia, pero en el caso de nubes simétricas, la elipse de inercia es un círculo y no se puede obtener información de orientación.

Además, el método debe ser robusto porque puede faltar, desplazarse o ser excesivo algunos puntos (digamos <2%). Puede haber entre 500 y 2500 puntos en total.

¿Alguna sugerencia sobre cómo se puede hacer esto de manera eficiente? Sospecho que algunos otros momentos pueden hacerlo.

Caso típico:

Answer 1

Una nube de puntos que es 4-simétrica tendrá 4 ejes de simetría de reflexión, donde cada eje está desplazado del siguiente por 45 grados. Para encontrar todos los ejes, por lo tanto, basta con encontrar uno.

El siguiente algoritmo casero funciona bastante bien para encontrar ese eje. Las pruebas de ensayo de nubes con un promedio de 500 puntos dan las siguientes estadísticas con respecto a la desviación $D$ entre el ángulo del eje encontrado por el algoritmo y el verdadero ángulo del eje:

Nube perfecta:

$D \lt 1^\circ$: $100$%

Nube con 2% de puntos faltantes:

$D \lt 1^\circ$: $55$%

$D \lt 2^\circ$: $90$%

$D \lt 3^\circ$: $99$%

Discutiré áreas problemáticas al final de la publicación, pero primero el algoritmo.

Resumen del algoritmo

Para una nube 4-simétrica, al menos un eje de simetría debe existir dentro de cualquier sector de $45^\circ$, visto desde el centroide de la nube. En el extremo, habrá un eje al comienzo del sector y otro eje al final del sector. Un eje de simetría se caracteriza, en este caso, por el hecho de que todos los puntos dentro de un sector de $45^\circ$ a la "izquierda" del eje están reflejados por los puntos dentro de un sector de $45^\circ$ a la "derecha" del eje. Una forma muy simple (no robusta) de verificar si un eje en un ángulo dado es un eje de simetría, es ver si el número de puntos en el sector de $45^\circ$ a la izquierda del eje es igual al número de puntos en el sector de $45^\circ$ a la derecha del eje. Una mejor manera (que este algoritmo utiliza) es verificar si la suma de las distancias desde el centroide a los puntos en el sector de $45^\circ$ a la izquierda del eje, es igual a la suma de las distancias a los puntos en el sector de $45^\circ$ a la derecha del eje.

Por lo tanto, la idea básica del algoritmo es tener un eje que se mueva desde $91^\circ$ hasta $44^\circ$ en pasos de $1^\circ$, calculando la suma de las distancias a los puntos en el sector izquierdo y la suma de las distancias a los puntos en el sector derecho en cada paso, y comparando estas sumas. El ángulo del eje donde las sumas son "más iguales" es entonces el ángulo de simetría del algoritmo.

La razón para usar $91^\circ$ y $44^\circ$ en lugar de $90^\circ$ y $45^\circ$ es evitar problemas de redondeo. Además, uso sectores de $47^\circ$ (lo que significa que el sector izquierdo y derecho se superponen) en lugar de sectores de $45^\circ$ para evitar problemas con puntos que están en o cerca de la línea divisoria entre el sector izquierdo y el sector derecho.

Lo anterior obviamente no es un método robusto en general, pero para una nube donde se asume una simetría de 4 vías, funciona.

Algoritmo con detalles

Suponiendo que todos los puntos están en una matriz con coordenadas cartesianas:

1. Encuentra el centroide $(X_c, Y_c)$ de la nube.

2. Encuentra las coordenadas polares de cada punto, usando $(X_c, Y_c)$ como origen, y guarda los puntos que tienen un ángulo entre $91 + 46 = 137$ grados y $44 - 46 = -2$ grados en una nueva matriz $NewA$.

3. Ordena $NewA$ según el ángulo, de mayor a menor.

4. Recorre los ángulos $A$ desde $91^\circ$ hasta $44^\circ$ en pasos de $1^\circ$. En cada ángulo, calcula la suma de distancias para los puntos en el sector izquierdo (es decir, puntos con $ A - 1 \lt$ ángulo $\lt A + 46$) y compara con la suma de distancias para los puntos en el sector derecho (es decir, puntos con $ A + 1 \lt$ ángulo $\lt A - 46$).

5. El ángulo $A$ en el que esta comparación está más cerca de uno, es el ángulo del eje de simetría del algoritmo.

Áreas para mejorar

1. El algoritmo es sensible a "errores" en las coordenadas del centroide. Cuando faltan puntos o están desplazados, el centroide no está en la ubicación ideal (correcta).

2. El algoritmo también es algo sensible a los errores del 2% si ocurren principalmente en el primer y segundo cuadrante (de donde proviene la entrada de este algoritmo).

No estoy seguro de qué hacer con estos puntos.

Answer 2

Esta no es una respuesta, sino un comentario extendido que podría conducir a una solución viable.

Hice algunos experimentos, generando histogramas de $$\chi_{ij} = -\chi_{ji} = \frac{x_j - x_i}{\lvert x_j - x_i \rvert + \lvert y_j - y_i \rvert}$$ y $$\gamma_{ij} = -\gamma_{ji} = \frac{x_j - x_i}{\lvert x_j - x_i \rvert + \lvert y_j - y_i \rvert}$$ con cada muestra ponderada por $$\omega_{ij} = \omega_{ji} = \frac{1}{(x_j - x_i)^2 + (y_j - y_i)^2}$$ a partir de nubes de puntos rotadas y traducidas con simetría de espejo de cuatro vías, con hasta un 10% adicional de puntos (no simétricos) o faltantes.

Nota que para $$\theta_{ij} = \arctan\left(\frac{x_j - x_i}{y_j - y_i}\right)$$tenemos $$\theta_{ij} = \begin{cases} \arctan\left(\frac{1}{\chi_{ij}} - 1\right), & 0 \le \theta \lt \frac{\pi}{2} \\ \arctan\left(1 - \frac{1}{\chi_{ij}}\right), & -\frac{\pi}{2} \lt \theta \le 0 \end{cases}$$ y $$\theta_{ij} = \begin{cases} \arctan\left(\frac{\gamma_{ij}}{1 - \gamma_{ij}}\right), & 0 \lt \theta \le \frac{\pi}{2} \\ \arctan\left(\frac{\gamma_{ij}}{1 + \gamma_{ij}}\right), & -\frac{\pi}{2} \le \theta \lt 0 \end{cases}$$

Para $N$ puntos, hay $N(N-1)/2$ pares $i , j$ únicos, y lo anterior es computacionalmente barato de calcular y también es relativamente fácil de vectorizar; aritmética de precisión simple o de enteros de punto fijo es suficiente para los propósitos del histograma. Donde $\arctan$ o $\operatorname{atan2}$ podrían considerarse demasiado lentos, lo anterior debería ser suficientemente rápido.

La razón por la que creo que esto podría conducir a una solución viable, es que el histograma muestra picos extremadamente claros a lo largo de los ejes de simetría/espejo para nubes de puntos aleatorias. (Debido a las diferencias de signo, es necesario observar ambas para determinar los ejes de simetría reales.)

Para algunas redes regulares, vi más picos (como uno esperaría), incluidos picos duales en ciertos casos, por lo que definitivamente se necesita un trabajo matemático adicional (ya sea una investigación numérica exhaustiva de diferentes nubes de puntos, o un análisis sobre cómo la simetría de espejo de cuatro vías causa los picos vistos en el histograma angular, si están ponderados adecuadamente por la distancia) antes de considerarlo una solución.