Implémentation de l’algorithme de diffusion Floyd-Steinberg

L’algorithme de diffusion Floyd-Steinberg, inventé en 1976, permet de tramer une image de manière intelligente. On peut lire son fonctionnement en détails sur Wikipédia.
L’image qui suit nous permet de comparer un détail d’image transformée en image 1bit (noir ou blanc) avec cet algorithme (gauche) et sans (droite).

Le programme qui suit est une implémentation de cet algorithme pour Processing. Il n’est pas forcément rapide mais il fonctionne bien, en niveaux de gris. Lorsque la variable colorsNumber est 2, il n’y a que deux couleurs qui seront employées : le blanc et le noir.


En entrant l’image en couleurs ci-dessus (« montagne.png »), on obtient l’image en noir et blanc qui suit et qui sera enregistrée sous le nom « floyd_steinberg.png ».

float palette[];
float mu1 = 7.0/16, mu2 = 3.0/16, mu3=5.0/16, mu4=1.0/16;


void setup() {
  size(600, 480);
  background(255);
  int colorsNumber = 2; // ici on décide le nombre de couleurs de la palette
  palette=getPalette(0,255,colorsNumber);  
}

void draw() {
  // l'image à charger s'appelle "montagne.jpg" et doit 
  // se trouver dans le dossier "data"
  PGraphics g= floydSteinberg(loadImage("montagne.jpg")); 
  image(g,0,0);
  g.save("floyd_steinberg.png");
  noLoop();
}

PGraphics floydSteinberg(PImage img) { 
  PGraphics g = createGraphics(img.width, img.height);
  g.beginDraw();
  g.background(0);
  float[][] pixelz;
  pixelz = new float[img.width][img.height];
  for (int y=0; y<img.height; y++) {
    for (int x=0; x<img.width; x++) {
      pixelz[x][y]= brightness(img.get(x, y));
    }
  }
  for (int y=0; y<img.height; y++) {
    for (int x=0; x<img.width; x++) {
      float ancien=pixelz[x][y];  
      float[] nouveau = couleur_la_plus_proche(ancien);

      pixelz[x][y] = nouveau[0];
      float error= nouveau[1];
      boolean xMax=(x==img.width-1);
      boolean xMin=(x==0);
      boolean yMax=(y==img.height-1);
      if (!xMax) pixelz[x+1][y] += mu1* error;
      if (!xMin && !yMax) pixelz[x-1][y+1] += mu2* error;
      if (!yMax)pixelz[x][y+1] += mu3* error;
      if (!xMax && !yMax)pixelz[x+1][y+1] += mu4* error;
    }
  }
  for (int y=0; y<img.height; y++) {
    for (int x=0; x<img.width; x++) {
      float b=pixelz[x][y];
      g.stroke(b);
      g.point(x, y);
    }
  }
  g.endDraw();
  return g;
}

float[] couleur_la_plus_proche(float b) {
  float[] paire = {0, 0};
  float min=256; 
  for (int i=0; i<palette.length; i++) {
    float c=palette[i];
    float dis = abs(b-c);
    if (dis<min) {
      min=dis;
      paire[0]=c;
    }
  } 
  paire[1]=b-paire[0];
  return paire;
}

float[] getPalette(float depart, float fin, int n){
  if(n<2)n=2;
  float[] toreturn = new float[0];
  float diff = (fin-depart)/(n-1);
  for(int a=0;a<n;a++){
    toreturn = (float[]) append (toreturn, a*diff);
  } 
  return toreturn;
}

La valeur de chaque pixel (ligne par ligne depuis le haut jusqu’en bas et de gauche à droite à l’intérieur de chaque ligne) est lue et comparé à sa valeur indexée la plus proche. Si la valeur du pixel est 120 et que la valeur la plus proche dans ma palette est 128, la marge (dite « erreur ») sera de -8. Nous allons alors ajouter :
7/16e de -8 à la valeur du pixel (x+1, y)
3/16e de -8 au pixel (x-1, y+1)
5/16e de -8 à (x,y+1)
1/16e de -8 à (x+1,y+1)

Leave a Reply