Suite

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

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 souhaite prendre en compte pour décider de la position des étiquettes est la "droite" d'un segment particulier d'un contour. Plus il est droit, plus il est probable qu'il soit utilisé 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 numérique quantitative de sa rectitude (disons zéro pour un segment de contour totalement droit, une valeur supérieure à zéro pour un non donc segment droit, et cette valeur augmente au fur et à mesure que la torsion augmente).

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


La réponse dépend du contexte: si vous n'étudiez qu'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 intégrer ce calcul dans une sorte de recherche de bons points d'étiquette. Si c'est le cas, il est très avantageux d'avoir une solution qui soit soit informatiquement rapide, 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ématique à travers une composante connexe entière d'un contour, représentée comme une séquence de points P(0), P(1),… , P(n). Cela serait fait 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 distance(P(f), P(s)) >= 100, puis avancer s aussi longtemps que 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" à prendre en charge une étiquette, vous incrémenterez alors s de 1 (s = s+1) et procéderez à l'augmentation de f à (disons) f' et s à s' jusqu'à ce qu'une fois de plus une polyligne candidate dépasse 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'-1) sont supprimés du candidat précédent et les sommets P(f+1),… , P(f') lui sont ajoutés. Il est hautement souhaitable que la fitness puisse être rapidement mise à jour à partir de la connaissance uniquement des sommets supprimés et ajoutés. (Cette procédure d'analyse serait poursuivie jusqu'à ce que 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 amène à 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. Prendre une analogie avec l'analyse en composantes principales suggère que nous prenions la mesure suivante (où petit est mieux, comme demandé) : utiliser la plus petite des deux valeurs propres de la matrice de covariance des 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 un écart moyen d'un côté à l'autre par rapport à la ligne de base de 100 pixels créée par le début et la fin d'une polyligne, et a donc une interprétation simple.

Comme la matrice de covariance n'est que de 2 par 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, conduisant à 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 les 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 à l'intérieur de 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 un cadre de délimitation 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 la boîte englobante minimale de Wikipedia. Vous pouvez trouver le rectangle de surface minimale entourant votre polyligne, puis utiliser le rapport hauteur/largeur du rectangle, hauteur/longueur. Pour obtenir une mesure plus précise, vous pouvez examiner l'écart de la polyligne par rapport à l'axe central de ce rectangle englobant.


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

Que faire si vous placez un cercle d'un rayon particulier sur votre ligne de contour. Ce cercle croisera 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 incurvée. S'il y a plus de deux points d'intersection, la ligne de contour est beaucoup trop courbée.

Vous pouvez déterminer quelle longueur donnerait le meilleur indicateur de rectitude et mettre en place une routine pour suivre 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 quel que soit 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 chemin entre le début et la fin et la distance la plus courte (ligne droite) du début au point final. 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 bien remarqué, cela équivaudrait à Sinuosity.


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. Par la présenteFil veut direphi, ou alorsTdans la notation de wikipedia ici (http://en.wikipedia.org/wiki/Curvature).

Disons que vous avez une séquence à trois points, p0, p1 et p2. calculer la distancesentre p0 et p1, qui est delta de s (DS), en supposant que les points sont suffisamment proches les uns des autres. Ensuite, vous avez besoin du delta de T (DT), qui est le 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 bectors p0->p1, p1->p2, normaliser chacun pour avoir une longueur d'un, puis prendre la soustraction vectorielle de ces deux puis déterminer la magnitude. C'est-à-direDT. La division donne une courbureK0_1. saisir p1, p2 et p3 pour calculerK1_2etc.

Je me demande cependant si vous obtenez le contour en tant que polyligne, pas en tant que pixels rendus. Vous avez dit 100px donc ça m'inquiète un peu.


Voir la vidéo: Correction du concours 2019 GEOMETRIE ET PERCEPTION Part2 تصحيح مباراة 2019 الجزء الثاني