Forma de medir la similitud/diferencia de nubes de puntos 2D

Question

necesito una manera de medir la similitud o diferencia de dos nubes de puntos? El número de puntos en cada punto de la nube puede ser diferente. Las nubes de puntos ya están alineados. Por similitud me refiero a la similitud de las formas.

Ya he probado los siguientes enfoques:

• análisis de componentes principales
• La distancia de Hausdorff
• significa el cuadrado de la distancia de los puntos
• distancia media de los puntos

Todos ellos no funciona.

He incluido ejemplos similares y no similares nubes de puntos.

Answer 1

Sugiero una familia de métricas que pueden ser combinados (por medios ponderados, por ejemplo) para producir un número. Luego de encontrar un buen umbral de este número (es decir, si $\mathrm{mydist}(A,B) \le \epsilon$, las nubes se $A$ $B$ se considera similar) completar el algoritmo.

$$d_i(A,B) = \frac1{|A|+|B|} \left( \sum_{a\in A} \mathrm{dist}_i^i(a,B) + \sum_{b\in B} \mathrm{dist}_i^i(b,A) \right)$$ where $\mathrm{dist}_i$ is the usual distance from a point to a set using the $\|\cdot\|_i$-norm. The exponentiation is optional. The way it is, $d_1$ would be the average Manhattan-distances and $d_2$ sería el promedio de la distancia euclídea al cuadrado.

Otra opción sería $$\tilde d_k (A,B) := \|f_A - f_B\|_k$$ donde $f_C$ es una interpolación de la nube de puntos como una curva (por ejemplo utilizando splines). Este será apropiado si usted realmente no se preocupan acerca de los puntos de sí mismos, sino sobre las curvas que se forman. Tenga en cuenta que este enfoque debe tener cuidado de elegir la "correcta" punto de la secuencia de la curva (el orden en el que los puntos de recorrido). Si la nube tiene algunos inherente de los pedidos (por ejemplo, una medida de la trayectoria), usted puede usarlo. Si la nube puede parecerse a una forma bidimensional (por ejemplo, un cuadrado), este enfoque no funcionará correctamente. En tal caso, es posible que desee encontrar el casco convexo de la nube en primer lugar.
Para lidiar con la "mitad de camino" problema discutido en los comentarios de @Lamento la respuesta, puede exigir $\|\nabla f_C\|_2 \equiv c$, asegurando un constante velocidad de recorrido de la curva. Eligiendo $c$ adecuadamente tal que $f_C : [0,1]\to\mathbb R^2$ entonces permitir que las distancias $\tilde d_k$ a estar bien definidos y $0$ fib de la interpolación de las curvas son geométricamente idénticos.

Answer 2

Aquí es un método que se me ocurre. Desde su punto de nubes en forma curva, crear una función de $[0,1]$ $\Bbb R^2$de nubes de puntos. En esencia, "conectar los puntos". Vamos a llamar a la función de la primera nube de $A$ y la función de la segunda nube de $B$. Así que, básicamente, $A(0)$ sería el primer punto en la nube $A$ $A(1)$ sería el punto final en la nube $A$. $A(0.5)$ sería a mitad de camino a lo largo de la curva.

Para medir la similitud, calcular la siguiente integral.

$$\int_0^1\|A(x)-B(x)\|dx$$

Un valor de $0$ significa que $A=B$, y todo lo mayor que $0$ indica algún tipo de diferencia. Tenga en cuenta que si dos curvas son algo similares, por lo que ellos no va a aumentar este valor, a pesar de que su "similitud" probablemente debería mantenerse la misma. Para hacer esto, usted podría dividir la integral por la suma de las longitudes de las curvas.

Answer 3

Algunas ideas que pueden resultar útiles: Suponiendo que todos hemos listo aplica el proceso iterativo de punto más cercano del algoritmo, como se menciona en los comentarios, me gustaría, en primer lugar ajuste (mínimos cuadrados / programación cuadrática - rápido ajuste en todos los casos) una curva b-spline) en cada conjunto de datos, decir $\mathbf{C}_1(t)$ , $\mathbf{C}_2(t)$, donde $t\in [0,1]$ algunos afín parámetro. Se entiende que cada función es un conjunto de puntos. Lo bueno de estas curvas es que usted puede tomar ventaja de sus propiedades geométricas (pendiente, curvatura, incluso propiedades topológicas etc). Claramente yo esperaría dos conjunto similar de puntos, respectivamente, las curvas, a ser similar en muchos niveles.

Usted puede encontrar el punto de partida de la información sobre b-splines y montaje de aquí: http://en.wikipedia.org/wiki/B-spline#Curve_fitting

Existen varias implementaciones en varios lenguajes de programación para sus necesidades.

Ahora existen muchos interesantes escalar (es decir, la orientación independiente) agradable propiedades que puede utilizar para comparar su resultado. Algunos ejemplos: Similares posiciones espaciales: $$d_1 = \int_0^1 ||\mathbf{C}_1(t) - \mathbf{C}_2(t) || dt$$ Similares posiciones espaciales de la tangente: $$d_2 = \int_0^1 ||\dot{\mathbf{C}}_1(t) - \dot{\mathbf{C}}_2(t) || dt$$ Minimizar el ángulo entre los vectores de tangentes: $$d_3 = \int_0^1 ||\dot{\mathbf{C}}_1(t) \cdot \dot{\mathbf{C}}_2(t) || dt$$ Minimizar la curvatura de las diferencias: $$d_4 = \int_0^1 ||\kappa_1(t) - \kappa_2(t) || dt,$$ $\kappa_i$ la curvatura de cada curva, etc. Minimizar el ángulo entre los vectores de la aceleración: $$d_3 = \int_0^1 ||\ddot{\mathbf{C}}_1(t) \cdot \ddot{\mathbf{C}}_2(t) || dt$$

Supongo que debe existir criterios topológicos (abierto / cerrado /intrusos curvas) que puede utilizar.

Yo no trate de encontrar un escalar que es alguna combinación lineal de estos, en vez de eso me iba a trabajar con un vector de similitud y la aptitud para la función: $$\mathbf{f} = (d_1, \ldots, d_n)$$ y asignar diferentes umbrales numéricos para cada entrada. En un enfoque de la ingeniería de software, dos curvas similares a ser identificados cuando cada entrada de la función de aptitud es más pequeño que algunos de umbral (diferente para cada ranura). La idea de no combinar todo lo anterior en un escalar, viene de multi-objetivo de la optimización.

Importante: me gustaría identificar los umbrales óptimos para cada entrada del ideal teórico de los modelos (construcción de puntos de curvas similares con ruido aleatorio de un poco de orden, y establecer criterios de similitud / umbral).

Espero que ayude.