Mesure de la rectitude d'un segment de courbe (représenté par une polyligne)

Je travaille sur un algorithme d'étiquetage automatique des contours d'élévation et l'un des facteurs que je veux prendre en compte pour décider de la position des étiquettes est la «droite» d'un segment particulier d'un contour. Plus elle est droite, plus elle est susceptible d'être utilisée pour placer l'étiquette sur ce segment.

Chaque contour est représenté par une polyligne (mais avec des points rapprochés pour ressembler à une courbe à l'œil nu). J'ai alors une longueur fixe (largeur d'une étiquette), disons 100 pixels. Si je choisis au hasard (ou autrement) un segment de contour d'une largeur de 100 pixels, je veux pouvoir obtenir une valeur quantitative numérique de sa rectitude (disons zéro pour un segment de contour totalement droit, une valeur supérieure à zéro pour un non segment si droit, et cette valeur augmentant à mesure que le tortillement augmente).

J'ai cherché des réponses mais je n'ai rien trouvé de vraiment utile. Je serais reconnaissant pour tout pointeur.

La réponse dépend du contexte : si vous étudiez uniquement un petit nombre (limité) de segments, vous pourrez peut-être vous permettre une solution coûteuse en calcul. Cependant, il semble probable que vous souhaitiez incorporer ce calcul dans une sorte de recherche de bons points d'étiquette. Dans l'affirmative, il est très avantageux d'avoir une solution qui soit soit rapide sur le plan des calculs, soit permet une mise à jour rapide d'une solution lorsque le segment de ligne candidat varie légèrement.

Par exemple, supposons que vous ayez l'intention d'effectuer une recherche systématiquesur toute une composante connectée d'un contour, représentée par une séquence de points P (0), P (1), ..., P (n). Cela se ferait en initialisant un pointeur (index dans la séquence) s = 0 ("s" pour "start") et un autre pointeur f (pour "finish") pour être le plus petit index pour lequel la distance (P (f), P (s))> = 100, puis avancer s aussi longtemps que la distance (P (f), P (s + 1))> = 100. Cela produit une polyligne candidate (P (s), P (s + 1) ..., P (f-1), P (f)) pour l'évaluation. Après avoir évalué son "aptitude" à supporter une étiquette, vous incrémenteriez alors s de 1 (s = s + 1) et augmenteriez f à (disons) f 'et s à s' jusqu'à ce qu'une fois de plus une polyligne candidate dépassant le minimum une plage de 100 est produite, représentée par (P (s '), ... P (f), P (f + 1), ..., P (f')). Ce faisant, les sommets P (s) ... P (s ' Il est hautement souhaitable que la forme physique puisse être rapidement mise à jour en ne connaissant que les sommets supprimés et ajoutés. (Cette procédure de numérisation se poursuivrait jusqu'à s = ​​n; comme d'habitude, f doit être autorisé à «boucler» de n à 0 dans le processus.)

Cette considération exclut de nombreuses mesures possibles de la condition physique ( sinuosité , tortuosité , etc.) qui autrement pourraient être attrayantes. Cela nous conduit à privilégier les mesures basées sur L2 , car elles peuvent généralement être mises à jour rapidement lorsque les données sous-jacentes changent légèrement. Une analogie avec l' analyse en composantes principales suggère que nous envisageons la mesure suivante (où petite est meilleure, comme demandé): utiliser la plus petite des deux valeurs propres de la matrice de covariancedes coordonnées du point. Géométriquement, il s'agit d'une mesure de la déviation latérale "typique" des sommets dans la section candidate de la polyligne. (Une interprétation est que sa racine carrée est le plus petit demi-axe de l'ellipse représentant les seconds moments d'inertie des sommets de la polyligne.) Il sera égal à zéro uniquement pour les ensembles de sommets colinéaires; sinon, il dépasse zéro. Il mesure une déviation latérale moyenne par rapport à la ligne de base de 100 pixels créée par le début et la fin d'une polyligne, et a ainsi une interprétation simple.

Parce que la matrice de covariance n'est que de 2 sur 2, les valeurs propres sont rapidement trouvées en résolvant une seule équation quadratique. De plus, la matrice de covariance est une somme des contributions de chacun des sommets d'une polyligne. Ainsi, il est rapidement mis à jour lorsque des points sont supprimés ou ajoutés, ce qui conduit à un algorithme O (n) pour un contour à n points: cela s'adaptera bien aux contours très détaillés envisagés dans l'application.

Voici un exemple du résultat de cet algorithme. Les points noirs sont des sommets d'un contour. La ligne rouge continue est le meilleur segment de polyligne candidat d'une longueur de bout en bout supérieure à 100 dans ce contour. (Le candidat visuellement évident en haut à droite n'est pas assez long.)

Dans la communauté de l'infographie, il est souvent nécessaire de trouver une boîte englobante autour d'un objet. Par conséquent, c'est un problème bien étudié, avec des algorithmes rapides. Par exemple, voir l' article sur les algorithmes de boîte englobante minimale de Wikipedia . Vous pouvez trouver le rectangle de zone minimale entourant votre polyligne, puis utiliser le rapport hauteur / largeur du rectangle. Pour obtenir une mesure plus précise, vous pouvez regarder l'écart de la polyligne par rapport à la ligne médiane de ce rectangle englobant.

Je ne sais pas si cela aide, ou même si cela compte comme réponse, mais alors que j'étais assis ici à réfléchir à la question que je viens de poster, j'ai pensé:

Et si vous placez un cercle d'un rayon particulier sur votre ligne de contour. Ce cercle coupera la ligne de contour à au moins deux endroits. Plus la ligne est droite, plus la distance le long de la ligne de contour entre les deux points d'intersection est courte. Plus la distance le long de la ligne de contour entre les points d'intersection est longue, plus la ligne est courbe. S'il y a plus de deux points d'intersection, la ligne de contour est bien trop courbée.

Vous pouvez déterminer quelle longueur donnerait le meilleur indicateur de rectitude, et mettre en place une routine pour marcher le long de chaque ligne de contour et où elle était suffisamment droite, placez l'étiquette.

Je suis sûr que cela n'aide pas trop, et ce que je dis en anglais est beaucoup plus difficile dans le langage de programmation que vous utilisez, mais cela pourrait être un début?

L'approche la plus simple à laquelle je peux penser est le rapport entre la longueur réelle du trajet entre le début et la fin et la distance la plus courte (ligne droite) du début au point d'arrivée. Les lignes droites auront des ratios proches de un tandis que les lignes très courbes auront un ratio très élevé.

Cela devrait être une solution vraiment facile à mettre en œuvre.

Mise à jour: Comme Mike l'a remarqué correctement, cela équivaudrait à la sinuosité .

En recherchant "courbure" et "polyligne", j'ai obtenu cette information Comment puis-je trouver la courbure d'une polyligne? . Là, il a suggéré d'utiliser revenir à la définition de la courbure - K= DF/Ds. Ici, Fil veut dire phi, ou Tdans la notation de wikipedia ici ( http://en.wikipedia.org/wiki/Curvature ).

Disons que vous avez une séquence de trois points, p0, p1 et p2. calculer la distance sentre p0 et p1, qui est le delta de s ( Ds), en supposant que les points sont assez proches les uns des autres. Ensuite, vous avez besoin d'un delta de T ( DT), qui est un changement de vecteur tangentiel unitaire entre p0 et p1. il peut y avoir un moyen sophistiqué mais la méthode grossière à laquelle je peux penser pour prendre deux becteurs p0-> p1, p1-> p2, normaliser chacun pour avoir une longueur d'un, puis prendre une soustraction vectorielle de ces deux puis déterminer la magnitude. C'est ça DT. La division donne une courbure K0_1. saisir p1, p2 et p3 pour calculer K1_2et ainsi de suite.

Je me demande cependant si vous saisissez le contour comme une polyligne, pas comme des pixels rendus. Vous avez dit 100 pixels pour que je m'inquiète un peu.