Algorithme pour quantifier la différence de chemins de segment de ligne

Question

dire que j'ai deux chemins de segment de ligne, par exemple un sous-ensemble des exemples ci-dessous. Comment puis-je quantifier la différence entre eux?

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

Les deux voies peut avoir un nombre différent de segments et la longueur de chaque segment et l'angle entre les deux est variable.

Je pensais qu'il serait bon d'établir un système de coordonnées et de définir les segments en tant que nœuds et les arêtes. La différence pourrait peut-être quantifiée par les opérations nécessaires pour transformer l'un dans l'autre, similaire à la l'algorithme de distance de Levenshtein. Malheureusement, l'espace d'opération est énorme. Des idées? Merci!

Answer 1

Je vais aller un peu plus loin que ce que @awoodland sur pointe. Comment quantifier dépend tout pourquoi vous voulez quantifier la différence

Vous cherchez à trouver un numéro unique (au moins, susceptible d'être unique) comme un code de hachage pour un chemin de segment de ligne? Ou essayez-vous de quantifier les chemins de segments de ligne pour dire, « ce chemin est plus complexe (ou plus, ou a des angles plus aigus) que ce chemin »?

Si vous voulez créer un code de hachage, je suggère de créer deux 32 bits CRCs (ou quelque chose de similaire): l'une pour les longueurs de segment et un pour les angles. Une fois que vous avez calculé ces CRCs, les mettre ensemble dans une valeur 64 bits avec les angles dans les 32 bits de poids fort et les longueurs dans le bas 32 bits. En fonction du nombre de segments, peut-être une seule valeur CRC ferait:. Pour chaque segment, ajouter la longueur et l'angle entre celui-ci et le segment suivant

Notez que le médicament est susceptible de vous donner ci-dessus un numéro unique pour chaque chemin, mais pas garanti.

Si vous voulez quantifier la complexité du chemin de segment de ligne ... Je n'ai pas beaucoup d'idées.

Answer 2

Vous pouvez les dessiner en images de taille fixe, puis utiliser la distance euclidienne pour comparer les images.

Ou vous pouvez mesurer la longueur totale et la somme de la valeur absolue des angles (ainsi que les angles signés peut-être) en tant que mesure. Quelque chose basé sur cela aurait la propriété agréable d'être invariant à l'orientation de la forme (si l'on voulait ça!).

Comment quantifier dépend un peu de pourquoi vous voulez quantifier la différence entre eux.

Answer 3

Vous pouvez consulter cet article:

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

Dans cet article, nous utilisons KAS (une généralisation des paires de segments: vous pouvez avoir plusieurs segments connectés les uns aux autres) pour la détection d'objets. Nous introduisons un descripteur pour ces ensembles de segments que vous pouvez utiliser pour décrire vos paires.

Notre descripteur n'est pas invariant rotation de sorte qu'il pourrait ne pas vous convenir.

Answer 4

Si vous utilisez des opérations:

• coin Ajouter et le segment
• coin Supprimer et le segment
• le segment extensible (avec le poids de la différence)
• pli au coin (avec le poids de la différence)

Vous serait toujours en mesure d'utiliser la distance Levenshtein tout en étant n ^ 2 temps.

coder les segments comme suit [segment, coin] *. Il serait donc:

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

Lorsque la rotation est respectivement à la direction de pointage de segment.

Le calcul d'étirement et de flexion est tout à fait évident. Value[i-1, j-1] + stretch + bend.

Calcul ajouter / supprimer. Ajouter Value[i,j-1] + Cost of adding, supprimer Value[i-1, j] + cost of removal.