Bonjour,
J'ai des images dont je veux extraire juste le contour. Dans un premier temps, je vais me limiter à des cas "simples". J'ai qu'une seule forme par image. Ce que j'appelle "forme", ce sont des polygones avec de très nombreux côtés (plusieurs milliers de sommets). Ces polygones sont "plein" (pas de forme extrudée). Bien évidemment, comme se sont des images, j'ai pas les coordonnées de ces sommets (sinon, ça serait trop simple ). Je veux justement en sortie un tableau contenant les coordonnées des pixels appartenant au contour.
 
Je commence donc par traiter l'image avec un filtre de Sobel. J'ai trouvé un réglage qui me permet d'avoir grosso modo la plupart des pixels juste du contour de la forme. Les pixels du contour sont en blanc, le reste est en noir. Evidemment, j'ai des "trous" (i.e. des espaces noirs entre 2 pixels appartenant au contour) parce que le filtre de Sobel a un peu endommagé le contour.
 
Ensuite, je cherche un point dans mon image appartenant au contour. Pour ça, je recherche le premier pixel blanc et à partir de là, je regarde les pixels adjacents et trouver ceux qui sont en blanc aussi. Et ainsi de suite...
 
C'est à partir de là que ça se complique   Entre éviter de revenir en arrière sur un pixel du contour déjà traité, arriver à faire des "sauts" par-dessus les "trous" dans le bon sens pour retrouver la suite du contour, je dois avouer que je galère parce que bien évidemment, les formes à traiter sont pas simples du tout avec des "pics", des "creux" ou "replis"...
 
Par hasard, vous auriez un algo ou une idée pour arriver à ce que je veux faire, svp ?
 
Dans google, j'ai cherché sur les termes "image edge tracking algorithm" mais je suis pas sûr que ça soit les bons termes car ce qu'il me sort, c'est juste de l'algo de détection de contour.
 
Merci.

Je viens de trouver une schéma qui résume pas mal ce que je fais déjà :
https://www.researchgate.net/figure [...] _342087877
 
Le problème, c'est que cette méthode permet de récupérer tous les pixels du contour mais pas forcément dans l'ordre qu'un humain aurait agencé les pixels (genre, prendre que les pixels les plus au "bord" du contour, en tournant dans le sens trigo).
 
En effet, mon bord peut être plus ou moins épais.

Bon, je progresse un peu :
- je fais une récupération des voisins plus large (genre, de rang 10)
- j'évalue la qualité du pixel sur le bord avec une fonction qui a calcul un score. S'il y a trop de pixels blancs autour de mon pixel, c'est qu'il n'est pas tant que ça au bord (genre, dans le cas d'un bord épais de plusieurs pixels). Donc, un score, c'est un score petit mais > 0. Par ailleurs, il faut que le pixel évalué appartienne bien au bord.
 
Ca commence à pas mal marcher mais parfois, mon algo repart en arrière. J'ai pas encore trouvé comment l'en empêcher.

Bon, ça avance mais c'est pas encore totalement ça avec ce pb de retour en arrière.
Maintenant, pour chaque voisin du dernier point sur le contour trouvé :
- je calcule le nb de pixels blancs autour du voisin. Plus il est petit, plus je suis prêt d'un bord (et pas au milieux d'un bord épais de plusieurs pixels)
- je calcule l'angle formé entre le point précédent trouvé sur le contour, le dernier point trouvé sur le contour et le voisin. Plus l'angle est grand, mieux c'est (i.e. je vais dans la même direction, ex : 180 -> ligne droite alors que 0, j'ai fait demi-tour).
- je calcule la distance entre le dernier point trouvé sur le contour et le voisin. Plus la distance est faible plus mon voisin est proche de mon dernier point trouvé sur le contour. Ca, c'est pour éviter de faire de trop grand sauts sur le contour
 
Maintenant, j'aimerais trouver une fonction d'évaluation qui prend en paramètre ces 3 données (NbPixelsBlancs, Angle, Distance) et me retourne un score. Si je compare le meilleur voisin trouvé et le voisin courante, le meilleur à conserver est :
- à angle grand proche entre les 2 et NbPixelsBlancs proches, garder celui qui a la distance la plus faible
- à distance proche et NbPixelsBlancs proches, garder celui qui a l'angle le plus grand
- à distance éloignée, garder celui qui a l'angle le plus grand et NbPixelsBlancs faible
- à angle éloigné, garder le plus grand
...
 
Mais c'est pas très clair dans ma tête. En fait, je veux trouver le voisin qui a le meilleur compromis entre grand angle, petite distance et petit NbPixelsBlancs mais pas forcément le min partout.
 
Ex : un voisin qui a un angle < 60° mais un tout petit NbPixelsBlancs et une petite distance sera écarté au profit d'un voisin ayant un grand angle et une distance plus importante et un NbPixelsBlancs plus élevé car le premier me fera très probablement retourner en arrière.

Bon, j'en suis à lire des thèses  
Genre : https://helios2.mi.parisdescartes.f [...] sselle.pdf
 
Mais je vois que ça marche surtout sur des formes simples. Moi, ma forme peut vraiment être "à la con". Je pensais pas m'être attaqué à un pb aussi compliqué. Je suis pas sorti de l'auberge

T'es en train de réinventer la roue là.
 
C'est un problème classique de recherche de contours en traitement d'image.
 
Un exemple avec Lena
 

Si je comprend bien le soucis c'est pas de transformer le polygone en ligne mais ensuite de suivre cette ligne (imparfaite) pour en extraire les coordoonnées des sommets? Après je dis peut-être une bêtise, c'est largement au dessus de mes compétences...

Oui, c'est à peu près ça. J'ai un ensemble de pixels qui constituent le contour d'une forme complexe. Le contour peut avoir une épaisseur d'un ou plusieurs pixels et l'épaisseur de ce contour peut varier suivant les endroits dans l'image. Ce contour peut aussi avoir des trous (du fait du filtre de Sobel).
Moi, je veux récupérer une liste de pixels situés sur ce contour et me permettant de faire le tour complet de ma forme complexe (je pars d'un point situé sur le contour en haut de mon image, je pars sur la gauche et je veux faire le tour de la forme et revenir à mon point de départ).
 
Je ne veux donc pas tous les pixels qui constituent le contour. Idéalement, je veux les pixels situés le plus vers l'extérieur de du contour de la forme. J'ai pas non plus besoin de prendre tous les pixels consécutifs du contour : un sur 2 suffit.

Oui, c'est un pb classique, et j'ai lu plusieurs thèses (je suis même tombé sur celle de mon prof d'informatique que j'avais en école d'ingé qui a bossé sur les contours actifs   ).
Sauf que c'est un pb loin d'être résolu. Les contours actifs, ça va pas : c'est limité à un nb de points et ça n'épouse pas parfaitement la forme. Dans mon cas, vu la complexité, il me faudrait environ 1500 à 2000 points pour les formes les plus "simples". Donc, autant dire que pour les formes complexes, ça tournerait à environ 4000 points pour un contour actif voire plus. Clairement, ce type d'algo n'est pas adapté.
J'ai vu d'autres algos mais ça suppose que le contour soit continu (donc pas de trous) et de 1 pixel d'épaisseur. Là encore, je ne suis pas dans ce cas.
 
Si je fais le parallèle avec ton image de Lena, mon algo doit donner en sortie la liste des pixels qui vont permettre de faire le tour du chapeau, du visage et des épaules de Lena et ignorer tout le reste. Vu ton image, tu vois que ça va pas être de la tarte
 
Actuellement, ma principale difficulté, c'est d'arriver à faire en sorte que mon algo ne choisisse pas comme prochain pixel du contour à retenir un pixel qui va lui faire rebrousser chemin (donc, lui faire faire machine arrière au lieu de continuer à tourner dans le bon sens). Y'a un travail de sélection à faire en local mais aussi à corréler avec une vue plus d'ensemble du contour pour justement arriver à voir si je vais en arrière.
 
En effet, sur mon contour, je peux avoir des partie en forme de U. C'est typiquement dans ce genre de cas que c'est difficile de savoir si le prochain pixel retenu va bien me faire aller de l'avant et pas revenir en arrière  

 
C'est le cas, ce que tu vois sur l'image c'est pas une bitmap, c'est plusieurs contours (chaque contour a une couleur), et chaque contour est une liste ordonnée de points.

Certes mais je vois des contours qui ont plusieurs pixels d'épaisseur. Moi, je ne veux que du contour d'1 pixel d'épaisseur. Par ailleurs, je veux ignorer certains contours pas intéressants et au contraire, relier entre eux certains contours. Dans ton image, on voit plein de petits contours parasites vers le haut : ça, je n'en veux pas. A contrario, je veux que les contours du chapeau soient reliés et pas avoir le gros trou en haut du chapeau.
 
Pour autant que je sache, suite à mes lectures de thèses, ce pb de suivi de contour n'est pas encore résolu pour des formes complexes et encore moins quand il y a plusieurs formes sur une même image.
 
Mais si tu me trouves un algo qui le résout, donnes le moi ou son url, je suis preneur

Ton problème c'est pas uniquement un problème de recherche de contours.
 
C'est beaucoup plus complexe que ça, une recherche de contours seule ne suffit pas sur des formes complexes. Je dirais même que la recherche de contours c'est la partie la plus simple du problème.
 
Un indice : si tu t'y connais en Deep Learning, c'est dans cette direction qu'il faut chercher.
 
 

Je n'y connais rien en traitement des images, mais quitte à itérer, pourquoi ne pas faire un arbre puis supprimer les branches non viables (branches trop courtes, branches trop proches des autres, etc.) ?

EDIT : et si les trous sont trop gros, c'est plus un problème avec le filtre de sobel, non ?

Figure-toi que l'idée de l'arbre m'est venue aussi Le truc qui me gène un peu c'est à partir de quand je m'arrête dans une branche et que je détermine si c'est une branche viable ou pas Par ailleurs, sur le principe, je peux avoir plusieurs branches viables parce que prendre tel pixel ou juste son voisin, ça va pas changer grand chose. Donc, le risque, c'est de me retrouver avec un arbre énorme.
 
Pour le coup des trous, oui, c'est en lien avec Sobel. Mais comme mes images ont des caractéristiques relativement proches (désolé, je ne peux pas rentrer dans les détails de ce que c'est), je suis en mesure de déterminer les paramètres du filtre pour limiter relativement bien la taille max des trous. Je sais donc qu'en prenant les voisins d'un pixel à l'ordre 10, je peux gérer des trous de max 10 pixels, ce qui est déjà du bon gros trou
 
En fait, j'en reviens toujours au même problème : comment déterminer que je suis en train de rebrousser chemin, que je reviens sur mes pas et que je suis en train de prendre des pixels appartenant à une portion du contour que j'ai déjà traitée ? La difficulté vient des formes en U très fins que je peux avoir sur mon contour et ce, n'importe où. Or, un U peut être long de plusieurs dizaines de pixels mais large de 2 pixels Donc calculer une distance entre 2 pixels ne me dira pas forcément si effectivement je rebrousse chemin ou si j'avance.
Pareil en utilisant un angle. Avoir un 180° entre mon point précédent du contour, celui courant et celui que je suis en train d'évaluer ne sera pas forcément une indication que je fais marche-arrière. Je sens bien qu'il faut que je combine plusieurs infos mais j'ai pas encore trouvées lesquelles et comment.  

Le contour, je ne le cherche pas puisque j'en n'ai qu'un sur mon image. Ce que je cherche, c'est à récupérer un ensemble de pixels suffisamment espacés (mais pas trop) pour qu'en les reliant entre eux, j'épouse le mieux possible mon contour de pixels.
 
Le Deep learning ne m'aidera pas. D'une part, je ne pense pas avoir la puissance de calcul suffisante pour me lancer là-dedans (j'ai qu'un PC bureautique). Par ailleurs, faire du DL suppose voir une grosse base de données labellisée pour entraîner le modèle, chose que je n'ai pas. En fait, créer cette base reviendrait à faire manuellement tous les contours des images dont je dispose, donc plus d'intérêt après à avoir l'algo de DL

Je dirai.
Tu vas jusqu'au bout de tes branches, à la fin tu calcules la distance moyenne par rapport aux autres, si des branches sont trop proches, tu supprimes les plus courtes. Bon cela ne répond pas au problème de trous.

Pas sûr de comprendre.
Dans le cas défavorable où je suis en train de faire demi-tour, le calcul de distance ne va rien me montrer, juste une distance assez longue.
Par ailleurs, comment j'arrête le remplissage d'un branche ? (i.e., je continue à lui ajouter des pixels qui sont sur mon contour, donc blanc).

Par contre je n'ai pas compris ton histoire de U, tu les veux ou non ?

Sur mon contour, je peux avoir des portions qui forme des "U" (ou des "V" du reste). Oui, je les veux. Je ne veux pas passer au travers (en gros, faire un direct entre les pixels du bas de chaque branche du U. Je veux suivre la forme proprement.
 
Edit : si je me fichais des U, mon pb serait simplifié : un angle de 180° ou proche et une faible distance entre les pixels = je fais demi-tour.

Je dirai tu arrêtes tes branches lorsqu'elles ajoutent un pixel déjà ajouté ailleurs.
Quand je parle de distance moyenne, je parle de le moyenne des distances qui séparent les pixels point à point de chaque branche. B1P1 <--> B2P1, B1P2 <--> B2P2, etc.

Donc si ton U fais deux pixels de largeur, faut pondérer les distances par l'intensité des pixels je suppose.

EDIT : deux pixels très intenses auront des distances plus proches que deux pixels éloignés de la même manière mais avec une intensité plus faible.

Alors, vérifier qu'un pixel candidat n'est pas déjà dans ma liste de pixels retenus, je le fais déjà. Par ailleurs, pour réduire le nb de pixels, je m'interdis de prendre un pixel séparé d'une distance de 1 avec un pixel précédent. Donc, mas distance min entre 2 pixels de contour OK, c'est une distance de 2 (mais ça peut être plus).

J'ai pas de notion de pixel intense. Ils sont soit noir (fond), soit blanc (255). Sinon, ça serait trop facile : je prend que les plus intenses par ordre décroissant d'intensité et de distance croissante.  
 
Edit : oui, c'est pas simple mon histoire. Problème facile à énoncer mais une purge à résoudre.

La différence d'intensité entre deux pixels tu l'as puisque tu calcules le gradient d'intensité (en niveaux de gris) en chaque pixel lors du filtrage de sobel. D'ailleurs c'est probablement plus sur ces données que tu devrais travailler. Tu prends un pixel puis tu suis le vecteur orthogonal au gradient vers le pixel le plus proche. Quand la norme du vecteur devient trop faible tu arrêtes, et c'est tout je suppose.
Modulo les problèmes de trou.

Mais j'ai du mal à voir ce que te sors ton filtre de sobel, quand je lis sur les internets, normalement c'est bien le gradient d'intensité que tu es censé obtenir.

Oui, mais la lib que j'utilise permets de passer en blanc (255) les pixels restants. C'est un paramètre, du coup, je peux regarder ce que ça donnerait ton idée en gardant les niveaux de gris. A la base, je me disais que ça serait peut-être plus simple d'avoir tous mes pixels en noir ou blanc... Mais peut-être pas.Merci pour l'idée.

Au-delà de garder le niveau de gris, avoir accès aux gradients calculés puisqu'ils te donnent la direction à suivre et l'écart d'intensité.

Dans mon code, le filtre de Sobel, c'est juste une ligne qui me sauvegarde le résultat dans un fichier et la suite de mon algo travaille sur le résultat. Du coup, pas sûr que j'ai accès aux gradients...

Et en données de sortie tu as quoi ? Tu disais que tu avais un paramètre pour sortir les pixels restant en blanc, tu as quoi d'autre comme paramètres ? Qu'est-ce que ça donne si tu ne l'utilises pas ?
 
Sinon, si on reprend ton idée de départ, tu as deux points, tu calcules ton vecteur, puis tu calcules l'angle avec le vecteur formé avec chaque point blanc les plus proches et tu considères que ton suivant est celui avec l'angle le plus faible (ou le plus fort, le tout est de garder le même tout du long). C'est ça que tu fais actuellement ?

J'ai peu de paramètres pour le filtre de Sobel :
- un pour mettre à 255 si un pixel est > 0
- un pour mettre un pixel à 0 s'il est < seuil
- un pour retourner l'image + le seuil (et pas juste l'image). Le seuil est la moyenne des pixels.
 
Pour la suite, oui, c'est ce que je fais. Si j'ai un angle autour de 180° entre mon point précédent retenu sur le contour, le point courant sur le contour et le candidat, c'est que je vais globalement dans la même direction, donc c'est bon. A contrario, si l'angle est tout petit, ça sent potentiellement le pâté (demi-tour), mais c'est pas une obligation.
A noter que comme cet angle calculé n'est pas orienté (ex : 90° -> je sais pas si je tourne à gauche ou à droite), je calcule aussi un angle orienté trigo [0 ; 180] et ] 0 ; -180 [. Je calcul cet angle orienté entre un point situé au même Y que mon point courant et à un X décalé de 2 pixels sur la droite, mon point courant et le point candidat. Mais à la réflexion, je me demande si pour le premier point, je ne devrais pas prendre le centre de mon image...

Pour l'angle, ce qui est important, c'est de garder le plus petit (ou le plus grand) à chaque fois, afin de s'assurer que tu continues vers l'intérieur (ou l'extérieur). Rien ne dit que ton contour n'est pas censé faire demi-tour (exemple du U).
Il faut évidemment calculer cet angle sur ]0; 360], tu dois pouvoir utiliser la fonction atan2 qui te donnera un angle de 2pi entre ]-pi;+pi] en recalculant les coordonnées relatives de ton prochain point recherché par rapport au dernier point trouvé. En effet, la fonction atan2, si je ne me trompe pas, calcules l'angle d'un point par rapport à l'origine, tu ne peux rentrer en arguments que les coordonnées du point. Il faut donc les recalculer comme si l'origine était ton dernier point.

Pour le premier point, pas trop d'idée pour l'instant, je dirai qu'à partir d'un coin tu es certain de prendre le contour par l'extérieur si la forme ne sort pas de l'image.

Bon, j'ai fini par réussir à développer un algo qui marche pas mal du tout. J'ai encore quelques petites améliorations à apporter pour qu'il s'adapte à toutes les situations (ou une grande majorité), mais l'algo de base marche plutôt bien. Y'a une caractéristique commune à mes polygones très complexes que je n'avais pas prise en compte : ils sont générés par un calcul qui dépend d'un angle qui varie de 0 à 360° donc, un cercle.
Du coup, j'ai "entouré" mon polygone à traiter d'un cercle virtuel de même centre que celui de mon image, ce cercle étant en fait un polygone à x sommets. A partir de chaque sommet, j'envoie un "rayon" qui essaye d'aller jusqu'au centre du cercle mais s'arrête au premier pixel blanc trouvé, donc un pixel du contour recherché. Et là, j'arrive bien à détecter tous les creux/pointes de mon polygone complexe (ou, en tout cas, une large majorité, la précision dépendant du nb de points qui composent mon cercle qui entoure, j'ai mis 1000 points).
Parfois, j'ai un petit soucis avec le filtre de sobel qui est un peu trop fort et crée de petits trous dans le contour, du coup, mon rayon va jusqu'au centre. Dans ce cas, pour l'instant, je réduis le seuil du filtre de sobel.
 
Mais bon, j'ai un algo assez simple et qui donne de bons résultats.