Discussion :

[lcfseth]

Bonjour,
Dans le cadre d'un projet d'application d'edition photo ( Je ne peut pas trop m'etendre sur le concept ), je dois implementer un mecanisme similaire à la "magic wand" de photoshop.
En gros, quand l'utilisateur clique sur un pixel, tous les points adjascents et de couleur similaire ( j'utilise pour cela une valeur de tolerance et la distance euclidienne de l'espace RGB ) doivent etre selectionnés.

Je precise que je travaille en C#, version .net 3.5 avec GDI+ (Pas de WPF ni DirectX).
L'algorithm en lui meme n'est pas un pobleme. Le sujet est largement couvert sur le net.
Mon probleme reside dans le fait qu'a peu pres tous les algos que j'ai pu trouver, retournaient un ensemble de points ( A part le Snake mais apparement, il est tres difficile de faire un algo generic pour tous type d'image). Or je dois ( disons plutot que je prefere ) avoir un graphicsPath ou au minimum un PolyLine :
A la fois pour des raisons de stockage ( Un carré 200*200 peut etre representé par 400 points voir meme 4 points apres simplification, au lieu des 40000 pixels qu'il contient ).
Mais aussi car les utlisateur de PhotoShop ont l'habitude de voir le contour de selection et que je préfére garder ca.


En gros j'aimerais avoir une polyline representant le contour en noir.

L'algo que j'ai choisis pour le moment est le FloodFill par ScanLines :http://fr.wikipedia.org/wiki/Flood_fill.
Au depart, cette algorithm sert principalement à colorier à la maniere de l'outil
"Remplissage" de Paint. je l'ai quelque peu modifié selon mes besoins.

J'ai bien étudié l'algo, et j'ai réussis à representer la region en lignes adjascentes plutot qu'en pixels.
J'ai pris l'image presente sur la page en anglais de wikipedia qui montre bien l'idée.

Comme on peut le voir, l'algorithm parcour des lignes, de proche en proche jusqu'a remplir tout l'espace. Les coordonnées des extrimités de ses lignes peuvent être facilement extraite lors de la colorisation, mais comme on peut le voir dans l'animation, elle ne sont pas ordonnées.

Je ne sais si cela peut aider, je penche dessue depuis 3 jours, je ne trouve pas de facon propre de le faire.

Une autre solution, serait de créer une region ( GDI+) à partir de ses lignes puis d'extraire le contour à partir de cette region.
Pour rappel : Les regions sont representées en interne comme un ensemble de rectangles adjascents.

En utilisant cette information, je pense pouvoir trouver le contour externe de la region. Ce n'est bien sur pas suffisant puisque la region peut contenir des trous.

Bref, si quelqu'un pouvait m'aider à trouver une solution. Merci.

Ps: J'aurais une autre question, L'implementation que j'utilise utilise un stack pour stocker les pixels à visiter. D'aprés la page wikipedia, l'utilisation d'une queue à la place, dans le cas des Flood Fill 4 convexes, supprimerait l'effet "je laisse des trous puis je rebouche ("leave gaps and then return to fill them later")". J'ai essayé avec le scanline et le resultat fut un temps de traitement sensiblement superieur. Je serais simplement curieux de connaitre l'explication theorique de ce comportement ? Cela laisserais supposer que d'autre structures pourrait peut etre optimisé l'algorithm?

[pseudocode]

Or je dois ( disons plutot que je prefere ) avoir un graphicsPath ou au minimum un PolyLine

Si la surface finale contient des trous, on va avoir du mal a faire la segmentation avec un seul polygone.

A la fois pour des raisons de stockage ( Un carré 200*200 peut etre representé par 400 points voir meme 4 points apres simplification, au lieu des 40000 pixels qu'il contient ).

Bof, un tableau de 40000 booléens c'est pas si cher payé. Et c'est pratique pour la multi-selection.

Mais aussi car les utlisateur de PhotoShop ont l'habitude de voir le contour de selection et que je préfére garder ca.

Rien n'empêche de "dessiner" le contour mais de conserver le tableau de booléens en interne.

[lcfseth]

Si la surface finale contient des trous, on va avoir du mal a faire la segmentation avec un seul polygone.

Ce n'est pas le but recherché. C'est pour ca que je parlais de GraphicsPath.
L'important est d'avoir le contour.

Bof, un tableau de 40000 booléens c'est pas si cher payé. Et c'est pratique pour la multi-selection.

Pas faux, j'utilise des regions pour la multi-selection, y'a tous les operateurs ( union, soustraction, XOr ...)

Rien n'empêche de "dessiner" le contour mais de conserver le tableau de booléens en interne..

J'ai deja programmé tous les autres outils de selection, avec des graphicspath comme contour et une region comme interieur. Je prefere, eviter si possible, avoir à tout reprendre

[pseudocode]

J'ai deja programmé tous les autres outils de selection, avec des graphicspath comme contour et une region comme interieur. Je prefere, eviter si possible, avoir à tout reprendre

Ca va être bien compliqué à gérer.

Rien que pour une seule sélection d'une zone en forme de "grillage", ca va faire beaucoup de path/région. Si on ajoute la multi-sélection, il va falloir calculer les intersections path/région à chaque ajout.

Si en plus tu veux ajouter des fonctions avancées (genre feather) ca va vite devenir impossible.

[lcfseth]

Les intersections/unions sont gerer par un simple appel de fonction de la classe region du GDI+. L'algorithm utilisé est trés rapide donc, aucun probléme de ce point de vue. De plus, le traitement que je souhaite faire est trés simple et permet la superposition de selection ( Je vais juste appliquer un filtre de couleur avec un indice de transparence à 100 ) .

Simple curiosité qu'est ce que le feather?

Sinon, toujours aucune idée pour mon probléme de contour?

[pseudocode]

Les intersections/unions sont gerer par un simple appel de fonction de la classe region du GDI+. L'algorithm utilisé est trés rapide donc, aucun probléme de ce point de vue. De plus, le traitement que je souhaite faire est trés simple et permet la superposition de selection ( Je vais juste appliquer un filtre de couleur avec un indice de transparence à 100 ) .

Je ne parlais pas de "superposer" les sélections, mais plutôt de faire une seule sélection "en plusieurs clics". Enfin bon.

Simple curiosité qu'est ce que le feather?

C'est un effet progressif de transparence (channel alpha) quand on arrive au bord de la sélection.

Sinon, toujours aucune idée pour mon probléme de contour?

Si tu as le tableau de boolean qui représente les pixels sélectionnes, tu peux identifier les pixels qui forment la "frontière" et construire le contour avec un algo de "Contour Tracing" (par ex, Moore Neighbor). Pour gérer les trous dans ta forme, il faut recommencer une construction de contour pour chaque pixel "frontière" qui n'a pas été traité.

[lcfseth]

Merci, je vais de suite tester cet algo.

Voici le lien d'un excellent site exliquant les differents algorithmes de recherche de contour.
http://www.imageprocessingplace.com/...eim/moore.html