Discussion :

[BBouille]

Bonjour les amis,
J'aurais voulu demander à ceux qui utilisent la méthode de squelettisation Zhang-Suen s'ils ne rencontraient pas les mêmes problèmes que moi.
Après avoir testé 36 méthodes de squelettisation je pensais tenir la bonne mais je me suis rendu compte que certains traits disparaissaient.
Si quelqu'un pouvait simplement tester ma petite image jointe et me dire si la branche centrale du W est effacée aussi chez lui?
Si ce n'était pas le cas j'investiguerais plus loin.

[wiwaxia]

Bonjour,

Il m'est arrivé de travailler un sujet apparenté au procédé celui en question.

Tu pourrais, pour mieux cerner le comportement de ton algorithme, effectuer une série d'essais sur des versions agrandies de l'image initiale, pour des valeurs entières et décroissantes du rapport des dimensions, par exemple:

r = L/L_ini = H/H_ini = 8, 6, 4, 3, 2

après t'être assuré que l'algorithme d'agrandissement utilisé conduit toujours à une image binaire, et ne produit par conséquent aucune teinte intermédiaire - et ne comporte aucun calcul d'interpolation sur les couleurs; soit pour l'essentiel:

Pixel[i', j'] = Pixel[i, j] avec i = i' DIV r , j = j' DIV r .

[wiwaxia]

Re-bonjour,

Question: que donne selon ton algorithme le tracé de la ligne médiane lorsque la pointe s'amincit progressivement, et que sa largeur se réduit à 3, 2 ou 1 pixel(s) ?

La frontière apparaissant ci-dessous résulte de la discontinuité de l'orientation du vecteur gradient

associé à la carte des distances séparant chaque point intérieur du bord de la figure:

Il intervient forcément une décision arbitraire lorsque la zone explorée devient trop étroite.

[BBouille]

Oups,
Excuse-moi Wiw, n'ayant pas eu de réponse je n'étais plus venu voir.
Je pense que je me suis mêlé les pinceaux entre les "steps", je vais essayer de remettre tout ça dans l'ordre.
C'est génial ta carte des distances je ne suis jamais arrivé à quelque chose d'aussi "beau".
J'ai pas mal d'autres trucs à résoudre pour le moment mais j'espère pouvoir m'y consacrer et t'apporter une réponse.
Tu parlais d'agrandir l'image mais j'avais tenté de réduire l'image justement pour que la matrice à traiter soit moins grande et donc soit traitée plus rapidement mais là aussi c'est en suspens.

[wiwaxia]

Bonjour,

C'est à la lecture de ton premier message que j'ai en fait découvert le sujet, dont la bizarrerie a attiré mon attention.

L'établissement de la carte des distances m'a paru le procédé le plus naturel susceptible de conduire au tracé du squelette du contour. C'est aussi le plus esthétique, donc le plus motivant pour la recherche d'un algorithme - bien que la démarche soit évidemment très contestable d'un point de vue rationnel.

L'étape suivante, c'est le calcul du laplacien qui doit en principe présenter des extremums négatifs au niveau des crêtes; les résultats obtenus jusque là se sont néanmoins révélés décevants, le tracé n'étant visible que dans la partie centrale où interviennent les plus fortes valeurs des distances. Je suis en fait passé à autre chose, mais il reste cependant une option à envisager: le classement des valeurs d'un ensemble de 9 cases centré sur le pixel considéré.

L'obtention de la carte des distances est conditionnée par la définition d'un "cercle" dans le domaine discret de l'image, dont les points sont caractérisés par des coordonnées entières; on peut même envisager pour le rayon maximal d'un cercle de centre donné des valeurs décimales - ou ce qui revient au même des valeurs entières par exemple 1000 fois plus grandes.

L'obtention d'une image bleue sur ses frontières, blanche dans sa partie centrale et noire à l'extérieur de son contour fait intervenir les fonctions de couleur:

Bleu = Round(255*(r/R_max)^1/4) ; Vert = Round(255*r/R_max) ; Rouge = Round(255*(r/R_max)⁴) .

Voici ce que ce que l'on peut obtenir à partir de silhouettes disponibles sur la Toile:

Le passage à l'angle polaire du vecteur gradient est susceptible de faire apparaître le squelette: il s'agit alors de la frontière séparant deux zones de couleurs complémentaires (ou presque complémentaires):

L'algorithme doit ici être repris, car il utilise la valeur entière initiale du rayon. Je crois que cela vaudrait le coup de poursuivre.

[BBouille]

Wouaw que c'est beau.
J'avais essayé cette méthode que j'ai abandonnée quand il a fallu trouver le squelette de l'image et qu'il y avait des barbules partout.
J'ai essayé une méthode personnelle qui consiste à tracer le centre de toutes les branches d'une image comme si on dessinait au crayon son squelette.
Ça marche par exemple avec des lettres mais une fois que l'image devient plus complexe ou que les branches sont trop "épaisses" ça ne marche plus.
On y arrivera

[wiwaxia]

La relation R = F(x, y) calculée point par point peut être vue comme l'équation de la surface montagneuse d'une île dont les rivages s'ajusteraient au contour de l'objet; les lignes de plus grande pente du relief ainsi défini seraient inclinées de 45°, et ses arêtes correspondraient au squelette recherché.

La quantification des couleurs permet de mieux saisir les variations du rayon par le tracé des courbes de niveau

z = F(x, y) = C^te .

On obtient ainsi à partir de la figure initialement proposée l'image suivante:

On peut alors rechercher sur chaque ensemble de 9 points disposés en carré, centré sur le pixel considéré, ceux pour lesquels la valeur centrale se situe parmi les (N) plus grandes valeurs repérées;
dans le cas où N vaut 3, le squelette apparaît jusqu'aux extrémités des parties les plus étroites:

à des seuils plus élevés (par ex. N = 4) apparaissent des bavures qui invalident la démarche:

Le procédé apparaît généralement décevant, car il ne conduit pas au tracé continu du squelette; si celui-ci est bien restitué dans les parties étroites, c'est loin d'être le cas dans les parties larges et concaves, où la surface localement assimilable à une selle présente des courbures d'orientations opposées:

[BBouille]

Eh oui malheureusement!
Si on pouvait arriver aux performances et à la qualité d'Inkscape
Mais tes résultats sont déjà très beaux et bons.
Peut-être y a-t-il un moyen d'éliminer la plupart des barbules mais de façon sûre et complète c'est autre chose.
Et encore c'est au détriment du temps de calcul.
Au départ on m'avait demandé ça à partir d'une enveloppe postale avec adresse, timbre, annotations, etc, en moins d'une seconde.

[BBouille]

Helloo Wiw,
Je me suis remis à mon affaire de squelettisation suite à un flash nocturne.
Je présenterai la méthode quand j'aurai simplifié au maximum les différentes procédures.
Bien sûr ça ne fonctionne que pour des traits ou des courbes d'une épaisseur donnée, j'avais entamé ça pour reconnaître des caractères, des courbes, des lignes, ... dans une image.
C'est instantané pour une image raisonnable de 640x480 pixels par exemple.
Pour les figures plus complexes telles que celles que tu as présentées, j'avais utilisé à l'époque la carte des distances pour déterminer les points les plus éloignés des bords et ensuite je "squelettisais".
Utilises-tu aussi un balayage de haut en bas puis de bas en haut pour trouver les points les plus éloignés des bords.
Je ne comprends pas trop ta fonction f(x,y) et non plus pour N=3, est-ce un filtre genre Sobel?