Discussion :

[jcloupgarou]

Bonjour,

je dispose d'images BMP de motif (un motif par image).



J'utilise OpenCv pour détecter le contour de ce motif. J'obtiens donc la liste des pixels constituant ce contour.
J'aimerais ensuite réduire cette liste de points en ne conservant que les points d'inflexion tels que dessiner en rouge sur l'image jointe.



J'ai essayé l'algo de Douglas-Peucker avec la fonction "ApproxPolyDP" d'OpenCV, aussi réalisé ma propre implémentation de cet algo et tenté des approches itératives (dépendant de la distance et de l'angle)
Aucune de ces tentatives ne m'a permis d'obtenir le résultat escompté...
Avez-vous svp une idée de la manière de s'y prendre pour récupérer les points d'inflexion comme sur l'image jointe ?
Je parcours depuis plusieurs jours des papiers sur l'approximation polygonale sans trouver mon bonheur...
Par avance merci pour votre aide !
Jc

[Nebulix]

Les points rouges ne sont pas des points d'inflexion au sens mathématique.
Comme souvent, la première question est : que cherche-t-on exactement. Cà permet d'avancer vers la solution.
Suggestion : la figure semble constituée de segments et d'arcs de cercle. Cherches-tu les raccordements ? (il y a alors des points en trop)

[jcloupgarou]

Bonjour et merci pour votre intérêt !
Effectivement, le terme n'était pas le bon, je connaissais pas le terme de raccordement (point de raccord en fait)
Je cherche à obtenir les points de raccord entre segments, entre segments et courbes, et entre arcs de cercle lorsque les courbes présentent un angle supérieur à 90°.
Auriez-vous une idée, un nom d'algo ou une piste de dev pour résoudre une telle problématique.
Merci !

[Nebulix]

Ce que j'essaierais, pour commencer.
- Trouver un pixel blanc ayant un voisin noir
- Parmi les huit voisins de ce pixel, il doit y en avoir deux ayant un voisin noir, en sélectionner un
- Parmi les huit voisins de ce pixel, il doit y en avoir deux ayant un voisin noir, sélectionner celui où on n'est pas passé.
- Recommencer jusqu'à revenir au point de départ
On a maintenant la liste des pixels du contour.
Pour chacun de ces pixels :
- Sélectionner celui n positions après
-calculer l'angle du segment défini avec l'horizontale
En traçant cet angle en fonction du pixel, les lignes droites du contour correspondent à des plateaux, les arcs de cercle à des montées ou des descentes. Les bords des plateaux sont des points de raccordement.
On verra plus tard si pour les raccords entre les arcs.
On suppose que les éléments du contour ont une taille minimale. n doit être sensiblement plus petit.
Bon courage

[jcloupgarou]

Un fonction OpenCV (FindContour) retourne la liste des pixels ordonnés constituant le contour.

Ensuite, j'ai déroulé à la main ton algo sur un dessin et cela ne fonctionne pas, même avec n très petit.
Effectivement, l'angle avec l'horizontal va évoluer avant d'avoir atteint le point de raccord,
les plateaux sur le tracé de la fonction d'angles ne correspondent pas exactement aux segments de mon contour
et donc les limites des plateaux ne donneront pas les points de raccord...

[Nebulix]

J'avais oublié que tu avais déjà le contour ...

[jcloupgarou]

Aprés tatonnement, j'ai écrit ce code qui a l'air de pas mal fonctionné.
Il est basé sur un critère de distance des points intermédiaires par rapport aux edges successifs.
C'est en C#...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
List<Point> returnPoints = new List<Point>();
returnPoints.Add(contour[0]);
int iLastPt = 0;
for (int iCurseur = 1; iCurseur < contour.Size; iCurseur++)
{
    Point currentPt = contour[iCurseur];
 
    int iCheck = iCurseur - 1; 
    while ( iCheck > iLastPt)
    {
          Point lastPt = returnPoints[returnPoints.Count - 1];
          Point checkPt = contour[iCheck];
          PointF closest = PointF.Empty;
 
          double dist = FindDistanceToSegment(checkPt, lastPt, currentPt, out closest);
 
          if (Math.Abs(dist) > 3)
          {
                 returnPoints.Add(checkPt);
                 iLastPt = iCheck;
                 continue;
          }
          iCheck--;
    }
}

Ca donne ce résultat pour le motif pris en exemple dans ce post :



Toute autre idée est la bienvenue pour améliorer cet algo !!!
Merci

[Alec6]

Je rebondis sur la question: si on a la liste des points qui forment le contour, est ce que du coup, il est possible d'inventer un algorithm qui soit l'inverse de bresenham ?

[Nebulix]

@jcloupgarou
Si tu peux donner la liste des points du contour, ce sera plus facile.

[anapurna]

salut

si vous avez la liste des points du contour cela va grandement vous faciliter la tache

imagine que vous parcourez la liste
vous comparez n avec n-1 cela vous donne une direction.
Tans que la direction ne change pas vous n'enregistre pas les points intermédiaire.
vous pouvez pour commencer avoir huit directions : 2 verticale ,2 horizontale et 4 diagonale

une fois élagué les point ne servant a rien tu peut affiner avec des combinaison de points genre \_/ il y a de grande chance que cela soit un cercle
donc a toi de peaufiner

Ps : un variante serais de faire la somme des huit pixel autour si la somme ne change pas cela veut dire que la direction ne change pas

[tbc92]

Moyennement d'accord avec le message d'Anapurna.

Si on a un segment qui va de (5,5) à (20,30) , ça va se traduire au niveau pixel par plein de tout petits segments, alternativement verticaux et en diagonale. Mais le besoin, c'est de les synthétiser en un seul segment.

Il faut prendre du recul. Je prends un pixel, je prends 15, voire 20 pixels plus loin. Je calcule le segment qui relie ces 2 points. En arrondissant systématiquement aux entiers les plus proches. Et si la succession de points obtenus coïncide avec les points de notre tableau, alors on peut remplacer les 15 ou 20 points en question par un segment.

Identifier des segments de droite, ça se fait à peu près bien. J'imagine même qu'il existe des librairies qui font ça, parce que c'est un besoin relativement courant.
Par contre, j'ai cru comprendre que l'objectif était de décomposer le contour en une succession de segments, et/ou d'arcs de cercle. Et identifier des arcs de cercle, ça me paraît un peu plus compliqué.

[jcloupgarou]

La réflexion de tbc92 est tout à fait pertinente
Effectivement, le contour est une suite de pixels voisins. Les directions entre chaque pixel suivent soit l'horizontale, soit la verticale, soit une diagonale.
L'algo que j'ai proposé permet de retenir les différents points de raccord (avec plus ou moins de pertinence) à partir d'un critère de distance similaire à celui utilisé dans l'algo de réduction de Douglas-Peucker.
Par contre, ce critère en nombre de pixels n'est pas vraiment adapté pour maitriser l'angle d'ouverture des arcs de cercle.
J'ai mis en pièce jointe un fichier contenant tous les points du contour que j'ai pris en exemple dans ce post.
Merci pour votre aide !

[Alec6]

Tout dépend du niveau de précision que tu recherche pour "vectoriser" le contour. C'est à dire définir les segments et arcs de cercle.

Dans ton exemple tu as un dessin, sans anti-aliasing. Les segments et arcs de cercle sont normalement produit par l'algorithme de Bresenham (qui fait aussi les coniques).

Pour rappel, sur un segment de x1, y1 à x2 ,y2 ont dessine les pixels x,y tel que x1, y1 à x,y minimise l'erreur. C'est à dire avec une pente plus proche de la pente souhaitée.

Pour retrouver un segment dans ton contour peut être que tu peux parcourir des pixels voisins et vérifier qu'à chaque pas on tend vers une pente "idéale".
En faite à chaque pas les bornes qui définissent l'ensemble des pentes possible convergent.

Je t'invite à revoir l'algorithme de bresenham.

Bon courage.

PS: une autre approche avec un changement de repère selon l'algorithme de Hough et peut être intéressant aussi.

[Alex64]

si je comprend bien l'algo. de Bresenham ou de Hough génère une polyligne.
Une fois la poly ligne crée il faut l'interpréter (ex: est-ce un point du début ou fin une droite? un point d'une courbe ?)

A mon avis il faut ,en plus de ses coordonnées, attribuer un paramètre a chaque points de la polyligne (lors du traitement algorithmique).
Comme les données d'une table a digitaliser.

exemple

si c'est un point d'une droite ou le début d'une courbe l'attribut = "C"
X Y attribut
10,22 20,32 C ou C 10.22 20.32

si c'est un pt. d'arc de courbe attribut= "A"
X Y attribut
52,35 30,20 A ou A 52.35 30.20

cas pour la fin d'une courbe

si attribut (n-1) = "A" et attribut (n+1) = "C" alors attribut (n) = "C"

mais est-ce possible ?????

[Guesset]

Bonjour,

Je tenterais ceci :

• En exprimant les points sur forme x(t), y(t) par des polynômes d'ordre donné, je prédis la position suivante à partir des derniers points (nombre plus ou moins important selon l'ordre polynomial choisi).
• Si la prédiction est bonne (dans le demi-point environnant) on n'enregistre pas le point prédit mais on l'intègre dans la prévision suivante.
• Si la prédiction est mauvaise, on enregistre le dernier point OK et on recalcule les coefficients des polynômes à partir des points actuels.

Ce n'est pas idéal mais cela devrait diminuer sensiblement le nombre de points (d'autant plus que l'ordre des polynômes est élevé sans exagérer).

L'ordre 1 reprend une projection de Bresenham et donc tente de réduire la courbe à des segments de droites.

Salutations