Coincidencia de perfil en una nube de puntos

Se genera una nube de puntos utilizando una función aleatoria uniforme para (x,y,z). Como se muestra en la siguiente figura, se está investigando un plano de intersección plano ( perfil ) que coincide como el mejor (incluso si no es el exacto) un perfil objetivo, es decir, dado en la esquina inferior izquierda. Entonces la pregunta es:

1- ¿Cómo encontrar una coincidencia de este tipo a target 2D point maptravés de point cloudlas siguientes notas / condiciones?
2- ¿Cuáles son entonces las coordenadas / orientaciones / grado de similitud, etc.?

Nota 1: El perfil de interés podría estar en cualquier lugar con cualquier rotación a lo largo de los ejes y también podría tener una forma diferente, por ejemplo, un triángulo, un rectángulo, un cuadrángulo, etc., dependiendo de su ubicación y orientación. En la siguiente demostración solo se muestra un rectángulo simple.

Nota 2: Un valor de tolerancia podría considerarse como la distancia de los puntos desde el perfil. Para demostrar esto para la siguiente figura suponga una tolerancia de 0.01veces la dimensión más pequeña (~1)de modo tol=0.01. Entonces, si eliminamos el resto y proyectamos todos los puntos restantes en el plano del perfil que se está investigando, podremos verificar su similitud con el perfil objetivo.

Nota 3: Se puede encontrar un tema relacionado en Reconocimiento de patrones de puntos .

Esto siempre requerirá muchos cálculos, especialmente si desea procesar hasta 2000 puntos. Estoy seguro de que ya existen soluciones altamente optimizadas para este tipo de coincidencia de patrones, pero debe descubrir cómo se llama para encontrarlas.

Como estás hablando de una nube de puntos (datos dispersos) en lugar de una imagen, mi método de correlación cruzada realmente no se aplica (y sería aún peor computacionalmente). Algo como RANSAC probablemente encuentre una coincidencia rápidamente, pero no sé mucho al respecto.

Mi intento de una solución:

Suposiciones

• Desea encontrar la mejor coincidencia, no solo una coincidencia suelta o "probablemente correcta"
• La coincidencia tendrá una pequeña cantidad de error debido al ruido en la medición o el cálculo
• Los puntos de origen son coplanarios
• Todos los puntos de origen deben existir en el destino (= cualquier punto no coincidente es una falta de coincidencia para todo el perfil)

Por lo tanto, debería poder tomar muchos atajos descalificando cosas y disminuyendo el tiempo de cálculo. En breve:

1. elige tres puntos de la fuente
2. buscar a través de puntos objetivo, encontrar conjuntos de 3 puntos con la misma forma
3. Cuando se encuentra una coincidencia de 3 puntos, verifique todos los otros puntos en el plano que definen para ver si son una coincidencia cercana
4. Si se encuentra más de una coincidencia de todos los puntos, elija el que tenga la menor suma de error de distancias 3D

Más detallado:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Cualquiera que sea la configuración que tenga el menor error al cuadrado para todos los demás puntos es la mejor coincidencia

Como estamos trabajando con 3 puntos de prueba vecinos más cercanos, los puntos objetivo coincidentes se pueden simplificar comprobando si están dentro de cierto radio. Si busca un radio de 1 desde (0, 0), por ejemplo, podemos descalificar (2, 0) basado en x1 - x2, sin calcular la distancia euclidiana real, para acelerarlo un poco. Esto supone que la resta es más rápida que la multiplicación. También hay búsquedas optimizadas basadas en un radio fijo más arbitrario .

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

El tiempo mínimo de cálculo sería si no se encuentran coincidencias de 2 puntos. $2000 \choose 2$

En realidad, dado que necesitará calcular todo esto de todos modos, ya sea que encuentre coincidencias o no, y dado que solo se preocupa por los vecinos más cercanos para este paso, si tiene la memoria, probablemente sea mejor calcular previamente estos valores utilizando un algoritmo optimizado . Algo así como una triangulación de Delaunay o Pitteway , donde cada punto del objetivo está conectado a sus vecinos más cercanos. Guárdelos en una tabla, luego búsquelos para cada punto cuando intente ajustar el triángulo de origen a uno de los triángulos de destino.

Hay muchos cálculos involucrados, pero debería ser relativamente rápido ya que solo está operando en los datos, lo cual es escaso, en lugar de multiplicar muchos ceros sin sentido, como implicaría la correlación cruzada de datos volumétricos. Esta misma idea funcionaría para el caso 2D si encontrara primero los centros de los puntos y los almacenara como un conjunto de coordenadas.

Agregaría la descripción de @ mirror2image en la solución alternativa al lado de RANSAC, puede considerar el algoritmo ICP (punto iterativo más cercano), ¡ aquí puede encontrar una descripción !

Creo que el próximo desafío al usar este ICP es definir su propia función de costo y la pose inicial del plano objetivo con respecto a los datos del punto de nube 3D. Un enfoque práctico es introducir algo de ruido aleatorio en los datos durante la iteración para evitar la convergencia a los mínimos falsos. Esta es la parte heurística que supongo que necesitas diseñar.

Actualizar:

Los pasos en forma simplificada son:

1. Encuentre el punto más cercano para cada punto de entrada.
2. Calcule la transformación de la entrada al objetivo y luego mueva los puntos de entrada usando la transformación.
3. Calcule la función de similitud (p. Ej., La distancia para cada punto de entrada wrt a su punto objetivo de par correspondiente).
4. Verifique la condición de parada.

Itera el paso 1-4.

¡Hay una biblioteca disponible que puede considerar aquí ! (Todavía no lo he probado), hay una sección en la parte de registro (que incluye otros métodos).