Clustering pixels in an image by colour over time

daddydean

I have this idea and im wondering if someone might be able to give me a few tips on how I might achieve this..
Basically, I'd like to be able to take an image and then treat each individual pixel as its own organism, so that a pixel of a certain colour value would be attracted to pixels of its own colour like a magnet, so perhaps heavy in the centre.
Each pixel would shift around until it reached its destination - all the pixels in the image would remain within the image, theyd just be rerranged at a final iteration.
But Id like to do it over time to see it actually visualized. Itd be like a ising model or some sort of markovian thing.
I looked around on github for methods to do this, but didnt really come up with anything.
:)

TfGuy44

String http = "http://";
PImage img;

void setup() {
  size(400, 300);
  img = loadImage(http + "i.imgur.com/WKueMZ2.jpg");
  imageMode(CENTER);
  image(img, 200, 150);
}

void draw() {
  loadPixels();
  for ( int t= 0; t < 100000; t++) {
    int a = width+int(random(pixels.length-width));
    int b = a-width;
    if ( pixels[a] < pixels[b] ) {
      color c = pixels[a];
      pixels[a] = pixels[b];
      pixels[b] = c;
    }
  }
  updatePixels();
}

Here's a starting point for you. Notice that what's happening here is that each frame 100000 random pixels are being selected and compared with the pixel above them. The "darker" pixel moves upwards.

TfGuy44

Modify as you like.

String http = "http://";
PImage img;

void setup() {
  size(400, 300);
  img = loadImage(http + "i.imgur.com/WKueMZ2.jpg");
  imageMode(CENTER);
  image(img, 200, 150);
}

void draw() {
  loadPixels();
  for ( int t= 0; t < 100000; t++) {
    int o = random(1)<.5?1:width;
    int a = o+int(random(pixels.length-o));
    int b = a-o;
    if ( brightness(pixels[a]) >= brightness(pixels[b]) ) {
      color c = pixels[a];
      pixels[a] = pixels[b];
      pixels[b] = c;
    }
  }
  updatePixels();
}

daddydean

Superb! Thanks man! Is there a way to do it within the same dimensions of the image though? So there is no negative space?
Also, how would I get them to cluster more towards the centre?

jeremydouglass

I'm not sure what you mean by "negative space" -- those are dark pixels.

For example, try https://processing.org/img/processing3-logo.png

re:

how would I get them to cluster more towards the centre?

Notice that TfGuy44's algorithm was "compare with a pixel above". Before considering what algorithm would get you there, can you first describe abstractly what you mean by "cluster more towards the centre"? What, specifically -- bright colors, primary colors, median or modal colors? Is the center the literal center (divided like a pie color wheel) or is it a ring...? Can you find a reference image that looks like what you imagine the end result looking like? Etc. etc.

daddydean

Whoops I mistook the white for negative space.
I mean the literal centre of the image loaded.
All colours! So if there is a blue that is a different rgb value than another blue within the image, they would get clustered separately.
Im thinking whatever pixel of a colour group is closer to the centre of the image, the rest of the same coloured pixels would work their way towards this pixel.
Each image would end up looking different depending on what colours were in it, so im not sure I can give an example :\

jeremydouglass

So if there is a blue that is a different rgb value than another blue within the image, they would get clustered separately

In order to do this, you first need segmentation based on a color space, assign each pixel a segment, then have them seek each other based on segment id. Otherwise everything is just three values in a multidimensional space -- in many photos, almost every blue is a slightly different blue from every other in a continuity. If they aren't doing anything else, many multidimensional color sorting algorithms will eventually produced different versions of those colorspaces, skewed by whatever the available pixels are.

https://www.google.com/search?tbm=isch&q=colorspace

lmccandless

Not quite what I was going for but should get you along your way. Even this reduced version runs very slowly, so to do this per pixel on large images it would need to be done in a shader.

String http = "http://";
PImage img;
final int w = 400, h = 300;
final int max = (w-1)*(h-1);
int dotSize = 3;
int skip = 3;
float time = 0;

ArrayList<Organism> critters = new ArrayList<Organism>();

class Organism {
  color c;
  PVector loc, finish;
  Organism(color nc, int x, int y) {
    c = nc;
    loc = new PVector(x, y);
  }

  float colorDifference(Organism o) {
    float d = 1+abs(red(c) - red(o.c)) +
      abs(green(c) - green(o.c)) +
      abs(blue(c) - blue(o.c));
    return pow(1.0/d,0.8);
  }

  void planFinish(ArrayList<Organism> others) {
    finish = loc.copy();
    for (Organism o : others) {
      finish.sub ( finish.copy().sub(o.loc).normalize().mult(colorDifference(o)));
    }
  }

  void move() {
    loc.lerp(finish, time);
  }

  void draw() {
    fill(c);
    ellipse(loc.x, loc.y, dotSize, dotSize);
  }
}

void settings() {
  size(w, h);
}

void setup() {
  img = loadImage(http + "image.shutterstock.com/z/stock-photo-red-glossy-shiny-bird-fiery-throated-hummingbird-panterpe-insignis-colorful-bird-sitting-on-660194176.jpg");
  img.resize(w, h);
  img.loadPixels();
  print("loading");
  for (int x = 0; x < w-1; x+=skip) {
    print(".");
    for (int y = 0; y < h-1; y+=skip) {
      critters.add(new Organism(img.pixels[x+y*w], x, y));
    }
  }
  ellipseMode(CENTER);
  noStroke();
  for (Organism critter : critters) {
    critter.planFinish(critters);
  }
}

void draw() {
  time = frameCount/10000.0;
  clear();
  for (Organism critter : critters) {
    critter.move();
    critter.draw();
  }
  //saveFrame("frames/####.png");
}

Edit: Made some fixes that got it working more like how I thought it should, however aesthetically I kind of prefer the first version.

String http = "http://";
PImage img;
final int w = 400, h = 300;
final int max = (w-1)*(h-1);
int dotSize = 3;
int skip = 5;
float time = 0;

ArrayList<Organism> critters = new ArrayList<Organism>();

class Organism {
  color c;
  PVector loc, finish, origin;
  Organism(color nc, int x, int y) {
    c = nc;
    loc = new PVector(x, y);
    origin = loc.copy();
  }

  float colorDifference(Organism o) {
    float d = 1+abs(red(c) - red(o.c)) +
      abs(green(c) - green(o.c)) +
      abs(blue(c) - blue(o.c));
    return pow(1.0/d,0.66);
  }

  void planFinish(ArrayList<Organism> others) {
    finish = loc.copy();
    for (Organism o : others) {
      finish.sub ( finish.copy().sub(o.loc).normalize().mult(colorDifference(o)));
    }
  }

  void move() {
    loc.lerp(finish, time);
  }

  void draw() {
    fill(c,170);
    ellipse(loc.x, loc.y, dotSize, dotSize);
  }
}

void settings() {
  size(w, h);
}

void shuffleCritters(){
  int s = critters.size();
  ArrayList<Organism> tempc = critters;
  critters = new ArrayList<Organism>();
  for (int i = 0; i < s;i++){
    Organism q = tempc.get(floor(random(tempc.size())));
    critters.add(q);
    tempc.remove(q);
  }
}

void setup() {
  println("getting img");
  img = loadImage(http + "image.shutterstock.com/z/stock-photo-red-glossy-shiny-bird-fiery-throated-hummingbird-panterpe-insignis-colorful-bird-sitting-on-660194176.jpg");
  img.resize(w, h);
  img.loadPixels();
  println("initalize points");
  for (int x = 0; x < w-1; x+=skip) {
    for (int y = 0; y < h-1; y+=skip) {
      critters.add(new Organism(img.pixels[x+y*w], x, y));
    }
  }
  ellipseMode(CENTER);
  noStroke();
 println("shuffle points");
  shuffleCritters();
   println("calc finish");
   int i = 0;
  for (Organism critter : critters) {
    critter.planFinish(critters);
    i++;
    if (i%100==0)println((int)(100*((float)i/critters.size())) + "%");
  }
}

void keyPressed(){
  time = 0;
   for (Organism critter : critters) {
    critter.loc = critter.origin.copy();
  }
}

void draw() {
  time += 0.001;
  clear();
  for (Organism critter : critters) {
    critter.move();
    critter.draw();
  }
  //saveFrame("frames/####.png");
}

last one

import java.util.*;
import java.awt.*;

String http = "http://";
PImage img;
final int w = 400, h = 300;
final int max = (w-1)*(h-1);
float dotSize = 1.5;
int skip = 3;
float time = 0;

ArrayList<Organism> critters = new ArrayList<Organism>();

class Organism implements Comparable<Organism>{
  color c;
  PVector loc, finish, origin;
  Organism(color nc, int x, int y) {
    c = nc;
    loc = new PVector(x, y);
    origin = loc.copy();
  }

  float colorDifference(Organism o) {
    float d = 1+abs(red(c) - red(o.c)) +
      abs(green(c) - green(o.c)) +
      abs(blue(c) - blue(o.c));
    return pow(1.0/d,0.8);
  }

  void planFinish(ArrayList<Organism> others) {
    finish = loc.copy();
    for (Organism o : others) {
      finish.sub ( finish.copy().sub(o.loc).normalize().mult(colorDifference(o)));
    }
  }

  void move() {
    loc.lerp(finish, time);
  }

  void draw() {
    fill(c);
    ellipse(loc.x, loc.y, dotSize, dotSize);
  }

    public int compareTo(Organism o) {
    int r = (int)red(c);
    int g = (int)green(c);
    int b = (int)blue(c);
    float[] hsv = new float[3];
    Color.RGBtoHSB(r,g,b,hsv);
    float h1 = hsv[0];

     r = (int)red(o.c);
     g = (int)green(o.c);
     b = (int)blue(o.c);
     hsv = new float[3];
    Color.RGBtoHSB(r,g,b,hsv);
    float h2 = hsv[0];

      if (h2<h1) return 1;
      if (h2>h1) return -1;
      return 0;
    }

}

 void shuffleCritters(){
  int s = critters.size();
  ArrayList<Organism> tempc = critters;
  critters = new ArrayList<Organism>();
  for (int i = 0; i < s;i++){
    Organism q = tempc.get(floor(random(tempc.size())));
    critters.add(q);
    tempc.remove(q);
  }
}

void settings() {
  size(w, h);
}

void setup() {
  img = loadImage(http + "image.shutterstock.com/z/stock-photo-red-glossy-shiny-bird-fiery-throated-hummingbird-panterpe-insignis-colorful-bird-sitting-on-660194176.jpg");
  img.resize(w, h);
  img.loadPixels();
  print("loading");
  for (int x = 0; x < w-1; x+=skip) {
    for (int y = 0; y < h-1; y+=skip) {
      critters.add(new Organism(img.pixels[x+y*w], x, y));
    }
  }
  ellipseMode(CENTER);
  noStroke();
    shuffleCritters();
    Collections.sort(critters);

  int i = 0;
  for (Organism critter : critters) {
    critter.planFinish(critters);
    i++;
    if (i%100==0)println((int)(100*((float)i/critters.size())) + "%");
  }
}

void keyPressed(){
  time = 0;
   for (Organism critter : critters) {
    critter.loc = critter.origin.copy();
  }
}

void draw() {
  time += 0.001;
  clear();
  for (Organism critter : critters) {
    critter.move();
    critter.draw();
  }
 // saveFrame("frames/####.png");
}

daddydean

Woah! This is wild!!! Thanks for putting in the time to trying this out, looks awesome. Ok, is there any way the image can remain where it is though? So no black? Know what I mean? The idea I actually have is to try it out on this: https://github.com/aldnav/musiclookslike
So for the blocks to remain in their grid and just shift around until theyre all matched up with their own colours. .....And then I want to reverse the process! (but thats probably pretty hard to do hahaha)

Chrisir

Why don’t YOU give it a try and show some code for a change...?!

daddydean

I have a lot to learn, but ill give it a try.

jeremydouglass

@daddydean -- if you want pixels to be moving through a grid with no negative space, then you probably want pixel swapping behaviors -- and it is quite likely that your swapping behaviors are part of a cellular automaton for pixels.

The good news is that there is tons of code out there (and on this forum) for cellular automata.

There is some bad news. One is that writing simple rules for pixel swapping (for example, giving each pixel a goal location and having it swap in the direction of that goal) and then applying it to every pixel in a grid will create some pretty crazy artifacts -- stable spaces of pixels in the final arrangement that seem to have nothing to do with your understanding of the original values and the goals.

For just one example, two pixels facing in the same direction may be frozen forever swapping with each other. This can create bands, dead zones, and all kinds of oddities where you expect pixels to self-organize nicely.

Thing get a bit better if you add complications like:

1. randomly sample which pixels get to move each turn
2. let pixels swap at different distances depending on how far they are from their goal, with further pixels swapping farther
3. add random jitter to pixel swapping so that they don't always head straight for the goal

Approaches like these can things can break up log-jams and create more fluid outcomes.

There is more bad news, however. 2D cellular automata are not reversible unless they are broken into blocks and each block is updated with an invertible function...

• https://en.wikipedia.org/wiki/Reversible_cellular_automaton

...so you aren't going to be able to play your 2D cellular automaton backwards algorithmically. Two approaches that might work, however:

1. record every frame (of data or an image), like a movie, then play the frame recordings back in reverse order, or:

2. Pair every single pixel in the outcome with a target pixel in the original image, then have them seek again until they finally reassemble the original image -- it almost certainly won't be the same shuffle, but it will arrive at the origin.

---

Models of a big group of things all shuffling around in a space and heading in their own directions is actually of interest in flocking, traffic analysis, et cetera. Normally the space isn't perfectly dense the way an image is, but see for example "A Cellular Automaton model for pedestrian counterflow with swapping" https://www.sciencedirect.com/science/article/pii/S037843711730122X

daddydean

Hey @jeremydouglass, these are great ideas. Thanks for taking the time. I didnt really think of #1, to record it like a movie then to just play it back in reverse..I think im going to try that out first as it will likely be the easiest way to do it. Im curious about rearranging data in different ways that are more pleasant to look at. I'll do some thinking on this this week and see if I can come up with something good.

daddydean

@jeremydouglass So im curious, with https://en.wikipedia.org/wiki/Block_cellular_automaton
each block could be considered a pixel, so it would be possible to load in an image, yeah?...im not sure if thats whats happening in this video: but I do think this is all in the right direction.

jeremydouglass

Blocks need to be greater than a pixel -- e.g. 2x2 pixels each -- in order for swap operations to happen within blocks, which is what makes them blocks (you can't perform operations across blocks, each one knows only about itself). So if you want to be able to swap pixels that are one apart, you need at least a 3x3 block.

So how does any pixel move across the screen if it can only swap within its block? Each frame, you change the block partitioning. In the wikipedia article you linked, the illustration shows partitioning on even frames (in red dashed lines) and partitioning in odd frames (in blue lines). Swaps are only calculated within blocks.

One warning -- global clustering goals rely on state outside of the block (like, where out there on the canvas is the goal or the centroid of similar pixels). If pixels can only act locally, then simulating things like gas dispersion or gravity are easy, but a clustering effect may be hard. You make checking the global state of the total lattice part of the block update rules, but you need to be careful if you are trying to preserve reversibility. As I mentioned earlier, predictable (non-random) goal seeking through swapping tends to create a lot of really weird artifacts and surprising behaviors unless you salt them with some randomness. However, as soon as you include randomness, your model is no longer reversible -- unless you noise seed to produce a pseudorandom series that is defined for each time frame (so that you can check them forward and backward).