Algoritmo per quantificare la differenza della linea Percorsi Segmento

Question

Di 'Ho due percorsi segmento di linea, come ad esempio un sottoinsieme degli esempi che seguono. Come posso quantificare la differenza tra loro?

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

I due percorsi può avere un numero diverso di segmenti, e la lunghezza di ciascun segmento e l'angolo tra loro è variabile.

ho pensato che sarebbe bene stabilire un sistema di coordinate e definire i segmenti come nodi e spigoli. La differenza potrebbe forse essere quantificati mediante le operazioni necessarie per trasformare l'uno nell'altro, simile alla Levenshtein distanza algoritmo. Purtroppo lo spazio operazione è enorme. Qualche idea? Grazie!

Answer 1

andrò un po 'più di quello che @awoodland fuori punte:. Come si quantificare dipende tutto sul motivo per cui si vuole quantificare la differenza

Stai cercando di venire con un unico (almeno, rischia di essere unico) numero come un codice hash per un percorso segmento di linea? Oppure stai cercando di quantificare i percorsi segmento di linea per dire, "questo percorso è più complesso (o più a lungo, o ha angoli più acuti) rispetto a quella strada"?

Se si desidera creare un codice hash, vorrei suggerire la creazione di due CRC a 32 bit (o qualcosa di simile): uno per le lunghezze di segmento e uno per gli angoli. Una volta Computerizzata tali CRC, metterli insieme in un valore a 64 bit con gli angoli in alto 32 bit e le lunghezze della bassa 32 bit. A seconda del numero di segmenti, forse un singolo valore CRC avrebbe fatto:. Per ogni segmento, aggiungere la lunghezza e quindi l'angolo tra esso e il segmento successivo

Si noti che quanto sopra è probabile per darvi un numero unico per ogni percorso, ma non sono garantite a.

Se si vuole quantificare la complessità del percorso segmento di linea ... Non ho un sacco di idee.

Answer 2

Si potrebbe attirarli in immagini di dimensioni fisse e quindi utilizzare distanza euclidea per confrontare le immagini.

In alternativa è possibile misurare la lunghezza totale e sommare il valore assoluto degli angoli (così come gli angoli firmati forse) come misura. Qualcosa sulla base di questo avrebbe la bella proprietà di essere invariante per l'orientamento della forma (se si voleva che!).

Come quantificare in qualche modo dipende da perché si vuole quantificare la differenza tra loro.

Answer 3

Si può guardare a questo documento:

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

In questo lavoro usando KAS (una generalizzazione di segmenti coppie: si possono avere più segmenti collegati gli uni agli altri) per il rilevamento di oggetti. Introduciamo un descrittore per queste serie di segmenti che si possono usare per descrivere le coppie.

Il nostro descrittore non è invariante la rotazione in modo che non si potrebbe soddisfare.

Answer 4

Se si utilizza operazioni:

• Add angolo e segmento
• angolo Rimuovere e segmento
• segmento Stretch (con il peso della differenza)
• Bend angolo (con il peso della differenza)

Si sarebbe ancora in grado di utilizzare Levenshtein distanza pur essendo n ^ 2 tempo.

Codifica i segmenti come segue [segmento, angolo] *. Quindi sarebbe:

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

Dove rotazione è relativa alla direzione di puntamento segmento.

Calcolo allungamento e flessione è abbastanza evidente. Value[i-1, j-1] + stretch + bend.

Calcolo Aggiungi / Rimuovi. Aggiungere Value[i,j-1] + Cost of adding, rimuovere Value[i-1, j] + cost of removal.