# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Dtection de contour prcis dans une image propre

## electroremy

Bonsoir,

le titre de mon post peut surprendre :-)

en bref :

- j'ai une image trs propre, c'est  dire un noir et blanc avec une bonne rsolution (ou niveau de gris : noir et blanc avec antialiasing) gnre par un logiciel tel que CAO, traitement de texte, logiciel de dessin
-  partir de cette image, qui contient des formes en noir et blanc (formes qui peuvent tres des textes ou des formes gomtriques) je cherche  dterminer les contours de ces formes
- par contour j'entends une liste de point (x,y) assez prcise, chaque point tant reli par un seguement de droite pour former un contour ferm dans le sens horaire, pousant au mieux la forme dans l'image

Depuis 15 jours je fais des calculs et des recherches... mais je ne trouve pas de solution adapt  mon problme. Dans le domaine du traitement d'image, je ne trouve que des solutions adaptes  des images "sales" (comme des photos par exemple) et qui ne donnent comme rsultat que d'autres images (ce qui est inutile dans mon cas)...

Pourquoi je veux faire cela ? En fait, j'ai cr quelques logiciels de CAO qui sortent des images pour impression (par ex pour ralisation de circuits imprims par mthode photographique)

Je souhaite pourvoir usiner ces formes dessines, et les calculs  faire pour quiper chaque logiciel de la fonction usinage sont extrmement complexes...

Autre aspect des choses : avec une machine, un bug = une casse de matriel !

Hors, la gnration d'image de mes programmes est fiable, et j'ai expriment une solution simple : la possibilit d'usiner une image en niveau de gris, la valeur de gris correspondant  la hauteur Z... mais le soucis c'est que la rsolution est dcevante.... Car l'usinage se fait avec des passes "en balayage" (mthode bourrin) au lieu de chercher  suivre les courbes de niveau dans l'image

Donc je cherche  crer un logiciel qui permet d'usiner proprement une image simple (fortement contraste), la solution tant que les mouvement de l'outil suivent les contours

Merci

A+

----------


## electroremy

J'ai trouv quelque chose d'intressant :

http://potrace.sourceforge.net/

Ce code fonctionne uniquement avec des bitmaps en noir et blanc. Il permet d'obtenir une image vectorielle (donc ce que je cherche)

Cerise sur le gteau : le code existe en API et l'algorithme est expliqu en dtail

Je vais essayer de l'adapter pour mon besoin...

si vous avez d'autres pistes je suis preneur

A+

----------


## ToTo13

Et si tu nous montrais une de ces "images propres"  segmenter !

----------


## electroremy

> Et si tu nous montrais une de ces "images propres"  segmenter !


Effectivement, avec un exemple sous les yeux c'est plus parlant :-)



A+

----------


## ToTo13

Effectivement l'image est parfaite, tu n'as besoin d'aucun pr-traitement.
Donc dans ton cas c'est trs simple :
 - tiquetage des composantes connexes pour isoler les formes.
 - parcours de l'image et pour chaque pixel il faut tester s'il a des voisins noir et blanc. Si c'est le cas, alors il appartient au contour de la forme.

----------


## electroremy

> Effectivement l'image est parfaite, tu n'as besoin d'aucun pr-traitement.
> Donc dans ton cas c'est trs simple :
>  - tiquetage des composantes connexes pour isoler les formes.
>  - parcours de l'image et pour chaque pixel il faut tester s'il a des voisins noir et blanc. Si c'est le cas, alors il appartient au contour de la forme.


Tu pourrais me donner plus de dtail sur l'algorithme que tu me suggre ?

Je voulais tester la mthode de PoTrace aujourd'hui mais j'ai un soucis avec VB.NET qui m'empche de travailler (http://www.developpez.net/forums/d14...l/#post7784219)  ::?: 

Donc du coup j'ai avanc sur un autre logiciel, CiDess... en VB5 :-P (CiDess est le programme qui a servit  crer le circuit imprim montr en exemple). Je suis en train d'essayer de programmer l'usinage directement  partir de CiDess, mais je sais dj que pour les textes je n'ai pas de solution dans l'immdiat (certains circuits imprims comportent des textes, cette fonctionnalit est trs apprcie des utilisateurs)

Concrtement, pour CiDess, je dois passer du dessin  l'usinage :
- en dessin, je dessine des formes noires (morceaux de pistes, pastilles) qui se superposent, cela n'est pas gnant quand on cr une image
- mais en usinage, o il faut dtourer ce qui est noir (donc l'outil va suivre les contours), il va falloir que je fusionne proprement toutes les formes qui se chevauchent pour obtenir une collection de contours ferms propres qui ne se chevauchent pas, car sinon, l'usinage va couper les pistes  chaque connexion et autour de chaque pastille.

(NB : Gros avantage pour moi : dans CiDess je peux grer les perages  part, donc mes formes noires n'ont aucun contour "interne" en blanc.)

Ce calcul de fusion est faisable sans trop de difficults pour les formes telles que morceaux de pistes, pastilles... par contre pour les textes... pour y parvenir je devrait interprter moi-mme les polices TTF, grosse galre.  ::aie::   J'ai dj eu de nombreux problmes  l'poque du dveloppement de CiDess pour simplement avoir une impression conforme  l'cran  cause de problmes de mises  l'chelle et de dformations. (les textes taient soit trop gros, soit trop petits, cela crait des courts-circuits...)

Donc voil pourquoi j'essaye de crer du G-CODE  partir d'une image... avec une dtection de contour propre, car les logiciels d'impression d'image de type "heightmap" sont trop lents et ont une rsolution mdiocre.

D'autre part, ce programme d'usinage propre  partir d'une image permettrait de graver facilement des faces avant, des plaques de boite aux lettres, ect... directement  partir du traitement de texte ou du logiciel de dessin qui a servit  faire les tiquettes... car oui bien sr, des logiciels permettant d'usiner du texte existent, mais il faut refaire tous les fichiers dans ces logiciels... impossible de convertir en trois clic de souris une tiquette faite avec word ou photoshop en fichier XXX pour logiciel d'usinage

A+

----------


## ToTo13

Doucement, une chose  la fois.
Pour l'instant on en est l : 


> -  partir de cette image, qui contient des formes en noir et blanc (formes qui peuvent tres des textes ou des formes gomtriques) je cherche  dterminer les contours de ces formes


 - 1 - Les formes sont noires, il faut tout d'abord les isoler pour savoir combien il y en a et pour ne pas mlanger les contours.
Donc on fait un tiquetage des composantes connexes. Voir dans ce forum ce que c'est si tu ne connais pas ; on a dtaill le principe trs souvent et tu as du code java (basique, presque du C) dans le rubrique Contribuez.

 - 2 - tu parcours l'image et tu testes chaque pixel noir pour savoir s'il appartient  un bord/frontire/contour de forme.
A ce stade, tu sais alors quels sont les points de contour et si tu fais le lien avec l'tape 1, tu connais galement  quelle forme ils appartiennent.

 - 3 - pour chaque ensemble de point de contour, tu les ordonnes dans le sens que tu souhaites (dj trait dans le forum).

----------


## electroremy

OK merci pour ton aide  :8-):  J'ai trouv ton programme "Union-Find" qui a l'air assez intressant

En fait, la 1ire partie de l'algorithme POTRACE fait directement la mme chose que tes tapes 1, 2 et 3 (voir http://potrace.sourceforge.net/potrace.pdf)

La suite de POTRACE fait un lissage (c'est du luxe !)

Pour l'instant je ne fait que de l'algorithme sur des feuilles de papiers, faute de pouvoir manipuler un bitmap monochrome avec VB.NET  ::aie:: 

Je ne dis pas que ce n'est pas intressant, au contraire, mais c'est trs frustrant de ne pas pouvoir gnrer un excutable et de le voir fonctionner.

Je vais donc essayer de lire directement un fichier BMP monochrome (gnr par un programme tiers) en VB dans un tableau d'octets, sans passer par la classe bitmap et marshal de VB.NET. D'ailleurs a vaux mieux - vu que mon programme n'a pas besoin d'afficher l'image, l'utilisation de la classe bitmap est une perte de temps de calcul et aussi une perte de mmoire vive

A+

----------


## ToTo13

::koi:: ... pourquoi lisser un contour aussi net ???

Tu peux gnrer un tableau (reprsentant une image) et travailler dessus.

----------


## electroremy

> Tu peux gnrer un tableau (reprsentant une image) et travailler dessus.


=> OUI ! D'ailleurs c'est pour cela que je souhaite lire directement un fichier bmp en binaire




> pourquoi lisser un contour aussi net ???


=> il faut lisser au minimum au niveau du pixel. Avec la 1ire tape de PoTrace, le contour est "pixelis" en marches d'escalier donc avec des crans correspondant aux pixels (du moins lorsque les trajectoires ne sont pas verticales ou horizontale). Un lger lissage permet d'avoir des points aligns suivant une droite et non un escalier

A noter que PoTrace travaille avec les coordonnes des coins des pixels (en fait dcalage d'un demi pixel sur X et Y) et non en centre pixel. Compte tenu de l'algorithme utilis c'est logique

A+

----------


## electroremy

Bonjour,

c'est cool j'ai bien avanc - le traitement d'image est fait sans DLL ni fonctions graphiques, en travaillant dans un tableau de byte

Voici d'abord quelques explications :



Les carrs sont les pixels de limage. Le centre du pixel en bas  gauche a pour coordonnes (0,0)

Les carrs blancs sont les pixels blancs, les carrs orange sont les pixels noirs de limage

La mthode de dtection de contour est celle de PoTrace. Les points et les flches (vecteurs) en rouge reprsentent un contour. Les coordonnes des points du contour ne correspondent pas aux centres des pixels, mais  leurs coins. Il y a un dcalage dun demi-pixel entre les deux systmes de coordonnes.

Un contour est dfinit par la liste des points dans le bon ordre, dans le sens des flches (sens antihoraire) ; les pixels noirs  lintrieur du contour sont donc toujours  gauche des flches.

Chaque point dun contour est dfinit par ses coordonnes X et Y, et par la direction de la flche qui pointe sur lui (cest--dire la flche qui le relie au point prcdent). Les contours sont ferms, le point prcdent du premier point est le dernier point de la liste.

La direction est stocke sous forme de nombre entier : 0 de gauche  droite ; 1 de bas en haut ; 2 de droite  gauche ; 3 de haut en bas.

Limage est parcourue jusqu trouver un pixel noir. Le contour est alors  suivit  point par point, jusqu ce quil soit ferm. Ensuite, la couleur des pixels  lintrieur du contour est inverse (noir devient blanc et blanc devient noir). Limage est parcourue de nouveaux, jusqu ce quil ny ai plus de pixel noir.

Cette faon de procder fait que les contours situs  lintrieur dautres contours sont dtects de la mme faon. Un calcul ultrieur est ncessaire pour savoir de quelle faon les contours sont imbriqus.

Pour peindre (ou inverser les pixels) de lintrieur dun contour, on fait dabord la liste de tous les vecteurs vers le haut, et la liste de tous les vecteurs vers le bas. Ensuite, on forme des couples de vecteurs qui divisent lintrieur du contour en segments : pour chaque vecteur vers le haut, on cherche sur la mme ligne le vecteur vers le bas  gauche le plus proche. Ensuite, pour chaque couple, on peint le segment de droite situ entre les deux vecteurs. Chaque pixel nest lu et crit quune seule fois, cest une mthode de flood fill trs efficace.

Voici le code complet :



```

```


Voici un test - l'image de dpart en 256 niveaux de gris



L'image convertie en noir et blanc :



Les contours dtects :



Les contours peints :



J'ai russit ici  obtenir des contours, sous forme de polygones avec des cts de 1 pixel de longueur. Il me reste  optimiser ces polygnes, c'est  dire rduire le nombre de ct tout en ayant un rsultat correct et sans marches d'escaliers.

Edition jeudi 1er mai  17h45 : quelques amliorations (effacement de l'image avant traage des contours remplis, suppression de la rcursivit de la dtection de contour inutile et remplacement par une boucle, ...)
A+

----------


## electroremy

Bonjour, la premire version de mon programme est termine  ::D: 

Voici :
- la documentation complte (mode d'emploi, formats de fichiers, algorithmes) : http://www.remylucas.fr/BTP4M_Manuel.pdf 
- lexcutable win 32 : http://www.remylucas.fr/BTP4M_Release.zip (la mise  jour du framework .net sera peut tre ncessaire sur votre PC)
- le code source : http://www.remylucas.fr/BTP4M_CodeSource.zip 

Fonctionnalits :
- lecture et criture d'image bitmap 1bit, 8 bits et 24 bits
- conversion en noir et blanc
- dtection de contours
- algorithme de flood fill efficace
- lissage et optimisation de contours
- sauvegarde au format SVG
- aucune utilisation des fonctions graphiques de VB et de Windows
- aucune utilisation de DLL

A noter que le programme nest pas encore dans sa version finale. Jai des amliorations en vue, et une version en C++ sera faite ce qui permettra de lexcuter sur des machines nutilisant pas Windows.

PS : merci aux pros de ce forum de m'indiquer si une section du forum ou du site serait plus approprie pour mettre en ligne ce programme  :;): 

A+

----------


## ToTo13

Merci de partager ton programme.
Tu peux mettre le code source dans la rubrique Contribuez, il faudra juste expliquer le but et la manire dont tu t'y prends afin que ce soit comprhensible. Pour cela tu pourrais mettre un lien vers cette discussion.

----------


## dorianGrey

> Bonjour, la premire version de mon programme est termine 
> 
> Voici :
> - la documentation complte (mode d'emploi, formats de fichiers, algorithmes) : http://www.remylucas.fr/BTP4M_Manuel.pdf 
> - lexcutable win 32 : http://www.remylucas.fr/BTP4M_Release.zip (la mise  jour du framework .net sera peut tre ncessaire sur votre PC)
> - le code source : http://www.remylucas.fr/BTP4M_CodeSource.zip 
> 
> Fonctionnalits :
> - lecture et criture d'image bitmap 1bit, 8 bits et 24 bits
> ...



S'il vous plat partager un nouveau lien pour tlcharger ce logiciel, lien ne fonctionne pas, Merci!!!
Ma copie de fichier est perdue sur le disque, Mercy

----------


## ToTo13

Et si tu regardais directement sur la page de Rmy Lucas vu que c'est son site ?

----------

