Créer une liste de coordonnées à partir de formes

[Sephi-Chan]

Coucou,

En ce moment, je cherche ce qui existe en terme d'algorithmes et outils pour produire une liste de coordonnées à partir d'images.
L'idée est de créer une image map HTML pour un fichier d'entrée de cette forme :



Ce traitement inclut plusieurs sous-tâches :

• Détecter chaque forme ;
  
• Produire une liste de coordonnées pour chacune de ces formes ;
  
• Simplifier ces liste de points en lignes droites ;
  

Si vous avez des pistes, des outils que vous connaissez pour l'une ou l'autre de ces tâches, ou bien des idées plus intelligentes, lâchez-vous !

Si je développe ça (avec votre aide j'espère), ce sera diffusé en open source (avec mes autres outils du genre).

[niahoo]

Mais heuu comment produis-tu les images sources ?

[Sephi-Chan]

C'est un graphiste qui les produit, avec ses outils. Ses tracés peuvent inclure des arrondis. Mon but est de map ses tracés assez fidèlement et de manière automatisée. S'il change un peu un tracé, je veux pouvoir régénérer la map simplement.

[Xenos]

Je tenterai cela avec Inkscape qui permet de vectoriser un fichier raster (type PNG).
Tu pourrais donc tirer un SVG à partir de l'image PNG (avec, par exemple, uniquement les formes blanches) et convertir ce SVG en une map HTML.

Pour plus d'automatisation, il faut voir avec Imagemagick pour vectoriser le PNG en SVG.

Les deux softs sont open source.

Note que suivant le cas, le SVG peut être suffisant plutôt qu'une HTML map: svg accepte les ancres <a/>, donc il suffit d'englober les objets SVG dans un tag <a/> pour créer un lien classique.

[Sephi-Chan]

J'ai réalisé une solution en SVG mais ça ne me convient pas pour plusieurs raisons : manque de texture, verrouillage dans le monde SVG (notamment à cause de React, qui gère encore mal les tags use ou image). Dommage car c'était royal pour la gestion des événements.

Du coup je laisse SVG de côté et je pars sur du bitmap et du DOM : simple et efficace, mais assez laborieux sans de bons outils : il faut donc les créer.

J'ai pensé à la vectorisation puis à la conversion en image map, mais je n'ai rien trouvé de fonctionnel et/ou concluant pour passer de paths SVG à une image map.


J'utilise effectivement ImageMagick dans les outils d'extraction de données que j'avais fait pour Seelies. Je pense que je devrais arriver sans trop de soucis à collecter les points du contour de chaque forme. Mais il restera ensuite à simplifier ce nuage de points pour ne pas avoir un tag area avec des milliers de points, c'est la plus grosse difficulté pour un non-matheux comme moi.

[@lucard]

J'aurais dit la même chose que Xenos,
en convertissant (ou en demandant à ton Graphiste de le faire directement) l'image en SVG (Vectoriel) l'action sur les formes pourra se faire institut.
Les events onmouseover sont aussi acceptés.


Edit : Bon bah, tant pis.

[niahoo]

Pas con d'utiliser Inkscape surtout qu'il a probablement une API.


Ensuite il est possible de coupler d3js à React ...

[Xenos]

Mais l'image map, ce n'est pas du tag HTML classique? Les tags SVG <circle/>, <rect/> et <polygon/> ont donc directement un pendant <area/>...

SVG possède le système de Pattern pour les textures.

De ce que j'ai vu, Inkscape n'a pas d'API directe pour la conversion PNG→SVG, il faudra creuser un peu plus la ligne de commandes.

Pour le lissage, j'avais eu ce genre d'opération à faire sur un stage de 2e année.
Comme algo, j'ai itéré sur les sommets. Pour chaque sommet (P0), je teste si les deux suivants (P1, P2) sont alignés (à peu près) avec P0. Si oui, je supprime le sommet inutile (P1), sinon, je passe au sommet suivant (P1), et je recommence.

Code :

Une valeur de seuil → S
Point initial du path → P0
Tant qu'on n'a pas fait le tour du path {
    Point suivant P0 → P1
    Point suivant P1 → P2
    Si [P0P1]^[P0P2] < S
        Alors Supprimer P1
        Sinon Garder P0; P1 → P0
}

Une solution bien plus propre mathématiquement reviendrait à utiliser la méthode des moindres carrés (pour nous, la variante régression linéaire).

On part d'un point P0, on considère les 2 points qui le suivent (P1,P2), et on cherche la droite qui passe "au plus près" de ces points {P0,P1,P2}. On peut forcer la droite à passer par P0 et P2 (les extrémités) pour éviter les effets colatéraux. Cette droite est définie par la régression (pour {P0,P1,P2}, il n'existera qu'une et une seule droite de régression, parfaitement calculable). Une fois la droite trouvée, on calcule son coefficient de corrélation, et tant qu'il est inférieur à un seuil donné, on ajoute le point suivant (P3) à la liste des points lissés, et on recommence. Dès que ce coefficient est trop grand, on vire le dernier point ajouté, et on ne garde que les extrémités de la dernière droite.
Si le coefficient de régression est trop grand dès le début (pour {P0,P1,P2}), alors {P0,P1,P2} ne sont pas alignés, et on ne vire aucun point; on passe directement à P1 et on recommence le calcul.

Pour éviter le cas particulier de fin ({P0,P1,P2} non alignés), on peut dire:

Code :

Coeff de regression max → R
Point initial → P0
Tant qu'on n'a pas fait le tour {
    Liste de points vide → X[]
    P0 → X[]
    Faire {
        Trouver la droite de régression de X[] → D
        Calculer le coefficient de régression pour {D, X[]} → r
    } Tant que r < R
    Supprimer les points de X[], sauf le premier (P0) et le dernier (P1)
    Dernier point de X[] (P1) → P0
}

Après, la condition sur le coeff de régression peut être modifiée (coeff moyen plutôt qu'une somme? variance maximale, pour ne pas supprimer les points aberrants?).

---

En prêt à l'emploi, Simplify semble adapté.

[Sephi-Chan]

Pas mal Simplify, d'autant qu'il a un portage en Ruby. Ça m'arrange puisque je collecte toutes les informations statiques sur la carte côté serveur.
En plus je suis stupide de ne pas y avoir pensé alors que je l'avais utilisé dans le cadre de l'API de cartographie Leaflet…

Merci Xenos ! C'est toujours intéressant de te lire.


Du coup, je n'ai plus qu'à écrire mon algorithme de détection de contour des formes.

Je pense que je vais partir sur un parcours du document pixel par pixel (de haut en bas et de gauche à droite) et — à la rencontre d'un pixel coloré — commencer à le suivre. Il faut que je réfléchisse à la manière dont je vais suivre le bord d'une forme dans laquelle je "rentre", en évitant de continuer dedans.

[Xenos]

Si l'algo de simplification est puissant et si l'image est bicolore, tu peux simplement considérer les sommets des pixels au lieu des pixels eux-mêmes.
Si l'image fait 10x10 pixels, on crée la grille de 11x11 sommets correspondants, qu'on lie par des segments. Pour chaque segment de cette grille, on détermine si c'est une frontière ou non (en testant la couleur des deux pixels qui constitue ce segment Si ce n'est pas une frontière, on supprime ce segment de la grille. On a directement la forme des tâches blanches, car elles sont toutes disjointes. Y'a plus qu'à chercher un sommet de la grille qui a encore au moins un segment, on suit ce segment jusqu'au sommet suivant, on recommence et on a la forme (en escaliers).