Algoritmo Para cuantificar la diferencia de trayectorias segmento de línea

Question

decir que tengo dos caminos de segmentos de línea, como un subconjunto de los ejemplos siguientes. ¿Cómo puedo cuantificar la diferencia entre ellos?

1. | __
2. \ _
3. _ _
4. / \
5. \ /
6. |
7. _

Los dos caminos puede tener un número diferente de segmentos, y la longitud de cada segmento y el ángulo entre ellos es variable.

Yo estaba pensando que sería bueno para establecer un sistema de coordenadas y definir los segmentos como nodos y los bordes. La diferencia podría quizás ser cuantificada por las operaciones necesarias para transformar una en la otra, similar a la algoritmo de distancia Levenshtein . Por desgracia, el espacio de operación es enorme. ¿Algunas ideas? Gracias!

Answer 1

Voy a ir un poco más allá de lo @awoodland a cabo en punta:. ¿Cómo se cuantifica que depende completamente sobre por qué desea cuantificar la diferencia

¿Está buscando para llegar a un único (al menos, probable que sea única) como un número de código hash de un camino segmento de línea? ¿O está tratando de cuantificar caminos segmento de línea que dicen, "este camino es más complejo (o más, o tiene ángulos más agudos) que ese camino"?

Si desea crear un código hash, sugeriría la creación de dos CRC de 32 bits (o algo similar): uno para las longitudes de segmento y uno de los ángulos. Una vez que haya computada esos CRC, ponerlos juntos en un valor de 64 bits con los ángulos en los altos 32 bits y las longitudes en el bajo 32 bits. Dependiendo del número de segmentos, tal vez un solo valor CRC haría:. Para cada segmento, añadir la longitud y el ángulo entre éste y el siguiente segmento

Tenga en cuenta que lo anterior es probable que le de un número único para cada ruta, pero no garantizada a.

Si desea cuantificar la complejidad del trazado segmento de línea ... no tengo muchas ideas.

Answer 2

Se podría dibujar en imágenes de tamaño fijo y luego usar la distancia euclídea para comparar las imágenes.

O se podría medir la longitud total y la suma del valor absoluto de los ángulos (así como los ángulos firmados quizás) como una medida. Algo sobre la base de que esto tendría la buena propiedad de ser invariante a la orientación de la forma (si quería que!).

¿Cómo se cuantifica que depende un poco de ¿Por qué que desea cuantificar la diferencia entre ellos.

Answer 3

Puede buscar en este documento:

http://www.vision.ee.ethz.ch /~calvin/Publications/ferrari07pami.pdf

En este trabajo que estamos utilizando Kas (una generalización de segmentos de pares: se puede tener múltiples segmentos conectados entre otros) para la detección de objetos. Se introduce un descriptor para estos conjuntos de segmentos que se pueden utilizar para describir sus pares.

Nuestra descriptor no es invariante rotación por lo que no se pudo adaptarse.

Answer 4

Si utiliza operaciones:

• Agregar esquina y el segmento
• Quitar esquina y el segmento
• segmento Stretch (con el peso de la diferencia)
• esquina doblada (con el peso de la diferencia)

Usted todavía sería capaz de usar la distancia Levenshtein sin dejar de ser n ^ 2 tiempo.

codificar los segmentos de la siguiente manera [segmento, esquina] *. Por lo que sería:

[length, rotation] [length, rotation]...

donde la rotación es respectiva a la dirección segmento señalador.

Cálculo de estiramiento y flexión es bastante obvio. Value[i-1, j-1] + stretch + bend.

añadir Cálculo / Quitar. Añadir Value[i,j-1] + Cost of adding, Value[i-1, j] + cost of removal quitar.