-- If(){design}else{art} » 2017 » mars

Archives mars, 2017

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

Article publié le : mardi 28 mars 2017. Rédigé par : Jean-no

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)

Ordonner les éléments d’un tableau au hasard

Article publié le : mardi 14 mars 2017. Rédigé par : Jean-no

Il est souvent intéressant de déterminer aléatoirement l’ordre des éléments d’un tableau.
La fonction qui suit permet très simplement d’obtenir ce résultat : on lui soumet un tableau, elle parcourt ses éléments un à un puis ajoute ces derniers à un nouveau tableau, à une position au hasard. Le type de tableau doit être indiqué, il faut donc remplacer le mot type par String, int, float, etc., selon le besoin :

type[] shuffle(type[] origine){
  type[] resultat = new type[0];
  for(type s:origine){
     int pos = floor(random(resultat.length+1));
     resultat = (type[]) splice(resultat, s, pos);
  }
  return resultat;
} 

Dans l’exemple qui suit, le type de tableau choisi est String[] (chaîne de caractère).
Nous créons un tableau contenant les valeurs « 1 », « 2 », « 3 », « 4 », « 5 », puis, à dix reprises, nous mélangeons ce tableau.

void setup(){
  size(1024,768);
  String[] s = {"A", "B", "C", "D", "E"};
  for(int a=0;a<10;a++){
    s = shuffle(s); println(s); 
  }
}
  
String[] shuffle(String[] origine){
  String[] resultat = new String[0];
  for(String s:origine){
     int pos = floor(random(resultat.length+1));
     resultat = (String[]) splice(resultat, s, pos);
  }
  return resultat;
}

Le résulstat sera (par exemple) :

D B E C A
A E B C D
B D E C A
A D C E B
B D C E A
A C D E B
D C E B A
A E C B D
E D C B A
D A C B E