# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Meilleur algorithme d'rosion/dilatation

## Gwindor

Salut,

Je suis en train de dvelopper des algorithmes de morpho.

J'essaie de les rendre les plus rapides possible.

Voici ce que j'ai fait pour l'rosion binaire avec un disque de rayon 1:


```

```

Vaut-il mieux effectuer le "Si" ? Ca dpend forcment du nombre de pixel gal  1 dans l'image.

Connaissez-vous la complexit d'une comparaison par rapport  3 additions, ou 3 ET logique ? (Personnellement je dveloppe en Java).

----------


## Flo.

Salut,

Il manque le "SINON" dans le pseudo-code pour l'affectation de result(x, y) si image(x,y) est diffrent de 1.

Je pense que des modifications importantes ne peuvent venir que de la faon dont tu l'crits. Cet algorithme est tellement trivial que seul le codeur fera la diffrence. 

Vaut-il mieux un IF/ELSE permanent qu'une srie de ET logiques ? Je ne crois pas que la diffrence sera vraiment importante.

(En c / c++) En revanche, si tu ne travailles que sur une seule boucle, tu vites l'imbrication d'une boucle dans une autre. Si tu peux passer directement par des pointeurs, tu gagnes aussi un peu de temps (quoique les compilos sont plus performants que nous). Puis ensuite en xmmx par exemple pour travailler 16 pixels par 16 pixels ... l c'est flagrant et incomparable.

Ce n'est que mon avis.

Flo.

----------


## Gwindor

> Il manque le "SINON" dans le pseudo-code pour l'affectation de result(x, y) si image(x,y) est diffrent de 1.


A priori je ne pense pas qu'il y est besoin de sinon, si l'image rsultat est remplie au pralable avec des 0.

Et je pense que le SI est en trop en fait. D'aprs ce qu'on m'a dit, faire une comparaison est bien plus couteux que 3 (ou peu plus, mais jusqu' combien?) oprations logiques.

J'ai donc modifi l'algorithme:


```

```




> Je pense que des modifications importantes ne peuvent venir que de la faon dont tu l'crits. Cet algorithme est tellement trivial que seul le codeur fera la diffrence.


 ::lol::  Bah oui justement c'est des conseils de codeur que je veux. Programmer l'rosion je sais faire y a pas de souci, mais je voudrai trouver des solutions pour l'amliorer.


A propos du C/C++, c'est sr qu'il y aurait des moyens d'acclerer, mais malheureusement, je dois travailler en Java puisque l'application est une applet.


Tu parlais d'une seule boucle pour parcourir l'image. J'y avais dj un peu rflchi.
A ton avis, il vaut mieux avoir une image sous forme d'un tableau de points ou d'une matrice?


Sinon j'ai vu des algorithmes qui utilisent le RLE (Run Length Encoding):
http://www.eurasip.org/content/Eusip...aper/pi_12.pdf
http://etrij.etri.re.kr/Cyber/servle...-1134112698124





> Ce n'est que mon avis.


Mais ton avis m'intresse, sois en sr !
Merci

----------


## Flo.

Salut,




> A priori je ne pense pas qu'il y est besoin de sinon, si l'image rsultat est remplie au pralable avec des 0.


Dans ce cas, cette tape doit apparatre dans le pseudo-code. A mon humble avis, il vaut mieux privilgier le SINON : cela vite le nettoyage de l'image qui constitue un parcours d'image en plus. De plus l'utilisateur d'une rosion n'a pas  se poser la question de devoir nettoyer ou pas son image avant de faire une rosion. Bon t'as rsolu le truc puisque tu as enlev le SI (c'est galement ce que je fais).




> A ton avis, il vaut mieux avoir une image sous forme d'un tableau de points ou d'une matrice?


Quand tu dfinis un tableau de tableaux (ce que tu appelles une matrice), a reste un tableau  une dimension en mmoire. C'est exactement la mme chose (en tous cas en c / c++, en Java je ne sais pas). Dans tous les cas, c'est toujours la solution d'un tableau mono-dimension qui est retenue.




> Tu parlais d'une seule boucle pour parcourir l'image. J'y avais dj un peu rflchi.


C'est plus qu'une obligation : si tu peux viter d'imbriquer des boucles, fais-le.




> Sinon j'ai vu des algorithmes qui utilisent le RLE (Run Length Encoding):


Je ne pense pas que cela soit ncessaire pour de simples oprations  ::?:  .

Propose directement ton code ... a sera plus simple.

Flo.

----------


## Gwindor

Voila un algo qui doit fonctionner  peu prs (Je ne suis pas pass au dveloppement java encore). On passe en paramtre l'image source "img", et l'image rsultat "res". se est l'lment structurant (une matrice de booleens) height et width sont les demi-tailles de l'lment se.

Le problme est que quand on utilise des lments structurants assez grand (j'avais fait le test en C++), le temps d'excution devient insuportable. 

D'o mes interrogations sur l'amlioration d'un tel algorithme.
Quand on effectue une grosse rosion avec le logiciel Aphelion par exemple, on n'attend pas aussi longtemps.



```

```

----------


## Flo.

> Le problme est que quand on utilise des lments structurants assez grand (j'avais fait le test en C++), le temps d'excution devient insuportable.


Cela ce rsoud en utilisant la proprit de sparabilit de certains filtres de convolution. Cependant, cela ne s'applique pas  une rosion en connexit 4 ( moins que je me trompe). Ton rosion doit tre en connexit 8.

L'ide consiste  faire 2 passages de l'image pour acclerer l'opration. Un premier passage pour faire une rosion horizontale. Un second passage sur le rsultat du premier passage pour faire une rosion verticale. Il te faut donc une image temporaire. On parcourt (2 * w * h * s) pixels au lieu de (w * h * s * s) pixels (w = width, h = height et s = taille du noyau).

A noter que ton temps d'excution varie selon la taille du masque. Dans ce cas moi je prfre opter pour une autre solution qui consiste  calculer une carte des distances de ton image (distance morphologique). Puis de seuiller cette carte. Avec cette opration, tu fais une rosion multiple en temps constant (indpendant de la taille du masque). Il faut en tout 2 passages (voire 3 si on chipote).

Par contre, ils ont pas autre chose que le getPixel et le setPixel en Java. J'y connais strictement rien en Java mais les fonctions correspondantes en c++ sont toujours trs lentes. D'un autre ct, comme ya pas de pointeurs en Java (je crois) .... 

Flo.

----------


## Gwindor

Oui effectivement, je devrai sparer l'rosion en 2.

Mais je vais peut-tre retenir la deuxime solution, puisque je vais avoir besoin d'un lment structurant rond je pense.

Mais comment calcules tu la carte des distances. Moi je pensais qu'il fallait faire des rosions successives pour l'obtenir.

Pour getPixel et setPixel, je ne sais mme pas si ces fonction existent, je fonctionne toujours  moiti en pseudo-code, en attendant que mon collgue me livre son code.

Je n'ai jamais entendu parler de pointeurs en Java mais je ne suis pas un spcialiste non plus.

----------


## Flo.

Ce site en parle 

http://www.tsi.enst.fr/tsi/enseignem...n_RdF/mti.html

Flo.

----------


## pseudocode

> Mais comment calcules tu la carte des distances. Moi je pensais qu'il fallait faire des rosions successives pour l'obtenir.


http://www.citr.auckland.ac.nz/~rkle...s/08slides.pdf




> Pour getPixel et setPixel, je ne sais mme pas si ces fonction existent, je fonctionne toujours  moiti en pseudo-code, en attendant que mon collgue me livre son code.


int BufferedImage.getRGB(int x, int y);
void BufferedImage.setRGB(int x, int y, int rgb);




> Je n'ai jamais entendu parler de pointeurs en Java mais je ne suis pas un spcialiste non plus.


Non, il n'y en a pas. (enfin si, il y en a en interne, mais ils ne sont pas accessibles au developpeur).

----------


## Matthieu Brucher

Perso, si l'lement structurant es quelconque, je stockerai dans un tableau les distances entre les diffrents lments et je parcourerais ce tableau dans une boucle for pour obtenir le rsultat.

----------


## Flo.

Salut,

Je pense qu'il doit tre possible de faire une rosion multiple (avec la carte des distances) et un lment structurant quelconque. Il faut juste changer l'lment structurant qui permet de calculer la carte des distances.

Je m'avance un peu en disant cela car je ne l'ai jamais test (avec un lment structurant quelconque) mais a ne me parat pas illogique.

Flo.

----------


## Matthieu Brucher

On a fait a il y a longtemps au labo, a marche sans problme. Plus l'lment est grand, meilleure est la prcision, faut pas oublier !

----------


## Gwindor

Bon bah j'ai de la lecture pour ce lundi matin pluvieux.

Merci de vos rponses.

----------


## Gwindor

Effectivement a  l'air d'une super solution la carte des distances seuille.
Je vais crire l'algo en pseudo-code pour moi et ceux que a interesserait.

Mais je vois quand mme un problme : la carte des distances est calcule en 4 ou 8 connexits. Et quand on la seuille, on se retrouve avec une forme rode par un carr.

Je ne crois pas me tromper mais je ne suis pas sr.

Donc si on veut garder l'lment "disque", il faut calculer la carte des distances autrement.
L'lment "disque" n'existe vraiment qu'avec un noyau de taille suprieure ou gale  5x5. Sinon, en 3x3, il quivaut  un carr 3x3  4 connexits.

----------


## Flo.

Salut,

Je crois que j'ai dit une btise dans mon post prcdent  ::oops::  ; je me suis emport et j'ai rpondu trop vite.

Comme le dit Miles, plus l'lment structurant est grand, plus la carte des distances obtenues sera prcise. Dans le lien que je donne, une rubrique est consacre  la comparaison entre distances de Chanfrein et distances relles :

http://www.tsi.enst.fr/tsi/enseignem...RdF/zones.html

La prcision de l'rosion issue d'une carte des distances est donne par celle de la carte des distances  partir de laquelle elle est ralise. 

L'lment structurant d'une telle opration correspondant n'existe pas je crois. 

Effectivement quand on enchane une srie d'rosions, on cumule une erreur qui vient de l'imperfection de l'lment structurant. Trop petit, cet lment est trop approximatif (un disque de 5x5 n'est pas tout  fait un disque). Trop grand, cet lment est trop gros (un disque de 20x20 commence  ressembler  un disque mais l'rosion est trop importante). 

Il faut bien voir ce qu'est une carte des distances. Il s'agit d'assigner  chaque pixel "fond", la distance qui le spare du pixel "objet" le plus prs (et donc de l'objet le plus prs). 

Eroder une image en seuillant la carte des distances consiste  dire que tous les pixels "objet" qui sont "trop prs" du "fond" deviennent "fond".

Flo.

PS : si je ne m'abuse pas encore une fois et si tu travaillais avec une carte des distances avec une prcision en valeurs dcimales (des sqrt(2) au lieu 
des 14 par exemple), tu verrais que ton rosion serait diffrente de celle effectue basiquement par un masque 3x3.

----------


## Gwindor

Voici l'algo utilisant la carte des distances calcules avec un carr 3x3 4 connexits que je viens de coder:



```

```

----------


## Flo.

En guise d'illustration :

Voici la comparaison de 2 rosions multiples (300 rosions) utilisant le mme code (une fonction utilisant de template en C++), l'une en prcision 16 bits (unsigned short en c) l'autre en flottants 32 bits (double en c).

Au lieu d'utiliser le couple (10; 14) pour l'opration 16 bits, j'utilise le couple (10; 10 * sqrt(2)) pour l'opration 32 bits.



- en noir : le fond 
- en gris : partie rode commune aux 2 mthodes
- en rouge : partie non rode commune aux 2 mthodes
- en jaune : partie erode pour l'une des mthodes et non rode pour l'autre.

Flo.

----------


## ToTo13

Pour les algorithmes les plus rapides, voir dans la discussion "Important" au sujet des librairies de traitement d'images

----------


## mitmal

Euh, pourquoi mes messages ont disparus ???

Peux tu me donner le lien pour voir la discussion "Important" au sujet des librairies de traitement d'images   ::oops:: 

Merci

----------


## ToTo13

Parce qu'ils n'avaient rien  faire l...

Et la discussion est celle juste au dessus de la premire du forum.

----------

