Processing 1.0 - Processing Discourse - need help by sorting a color array

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

Index › Programming Questions & Help › Syntax Questions › need help by sorting a color array

‹ Previous Topic | Next Topic ›

Pages: 1 2

need help by sorting a color array (Read 2744 times)

clankill3r

need help by sorting a color array
Apr 1^st, 2009, 3:23pm

Hi,

I'm using a webcam for color import and I want to sort the colors by brightness and use that to fill the screen.
Only my code shows a strange color effect and I can still se what i'm recording with my webcam. Where does the color effect come from and what did I do wrong?

Code:


import processing.video.*;

//color[][] imageColorRed, imageColorGreen, imageColorBlue, imageColorRGB;
color[] imageColors;

Capture cam;

void setup() {
  size(176, 144);
  cam = new Capture(this, 176, 144);//88, 72 / 176, 144 -default is 320, 240 trust camera_max is 352x288
  frameRate(0.5);
} 

void draw() {
  if (cam.available() == true) {
    cam.read();
    //image(cam, 0, 0, 320, 240);
    //set(0, 0, cam); //faster without any additional resizing, transformations, or tint.
    int count = cam.width * cam.height;
    cam.loadPixels();
    loadPixels();
    for (int i=0; i <= 255; i++){
	for (int j =0; j < count; j++) {
	  if (int(brightness(cam.pixels[j])) == i) {
	    //sorted[num] = colors[j];
	    pixels[j] = cam.pixels[i];
	    //num++;
	  }
	}
    }
    //cam.pixels = sortColors(imageColors);
    println(cam.pixels);
    updatePixels();
  }
} 
/*
color[] sortColors(color[] colors) {
 color[] sorted = new color[colors.length];
 int num = 0;
 for (int i = 0; i < 255; i++){
 for(int j =0; j < colors.length; j++){
 if (int(brightness(colors[j])) == i) {
 sorted[num] = colors[j];
 num++;
 }
 }
 }
 return sorted;
 }
 */

NoahBuddy

Re: need help by sorting a color array
Reply #1 - Apr 1^st, 2009, 4:01pm

I'm not sure you are actually sorting the colors the same way. The commented sorting routine uses num as an index for assignment. Your main code does not.

The commented sort algorithm does work.

Code:


PImage in = new PImage(256,256);
PImage out = new PImage(256,256);

void setup() {
  size(640,480);
  
  for (int i=0; i<in.pixels.length; i++) {
    in.pixels[i] = (int)random(0xffffff) | 0xff000000;;
  }
  
  out.pixels = sortColors(in.pixels);
  
  noLoop();
}

void draw() {
  image(in,0,0);
  image(out,256,0);
}

color[] sortColors(color[] colors) {
  color[] sorted = new color[colors.length];
  int num = 0;
  for (int i = 0; i < 255; i++){
    for(int j =0; j < colors.length; j++){
	if (int(brightness(colors[j])) == i) {
	  sorted[num] = colors[j];
	  num++;
	}
    }
  }
  return sorted;
}

clankill3r

Re: need help by sorting a color array
Reply #2 - Apr 2^nd, 2009, 5:26am

Thx, that helps a bit,

why does this script keeps hanging?
it has to do with
loadPixels();
println(pixels);
updatePixels();

Cause without that it runs fine

Code:


import processing.video.*;
PImage out = new PImage(320, 240);

Capture cam;

void setup() {
  size(640, 480);
  frameRate(0.5);
  cam = new Capture(this, 320, 240);
}


void draw() {
  if (cam.available() == true) {
    cam.read();
    image(cam, 0, 0); //set(0, 0, cam);
    loadPixels();
    println(pixels);
    updatePixels();
    //out.pixels = sortColors(pixels);
    //image(out, 0, 0);
  }
} 

color[] sortColors(color[] colors) {
  color[] sorted = new color[colors.length];
  int num = 0;
  for (int i = 0; i < 255; i++){
    for(int j =0; j < colors.length; j++){
	if (int(brightness(colors[j])) == i) {
	  sorted[num] = colors[j];
	  num++;
	}
    }
  }
  return sorted;
}

NoahBuddy

Re: need help by sorting a color array
Reply #3 - Apr 2^nd, 2009, 8:49am

I believe it is just that the println(pixels) has to print "[index] intvalue" as many times as the number of pixels in your sketch (640*480).

On a side note, I was trying to wrap my head around your sort algorithm and I think it could lead to one of the fastest sorts I have seen.

With a little work, it could probably be used to sort completely (not just by hue or color channel).

If something doesn't make sense, I will do my best to explain.

Edit: This turns out to be a Radix Sort that stops after the first level.

Code:


//Uses more memory to gain speed.

int w = 320, h = 240;

PImage data = new PImage(w,h);
PImage out = new PImage(w,h);


int[][] contents = new int[256][];//256 levels for RGB/hue/brightness/etc

int[] counts = new int[256];//256 levels for RGB/hue/brightness/etc
int[] indexlist = new int[data.pixels.length];

void setup() {
  
  size(640,480);
  
  int tmr = millis();
  
  //This is actually more overhead, as you would have an image as a source, still counted in the timer
  //Pass 0
  for (int i=0; i<data.pixels.length; i++) {
    data.pixels[i] = ((int)random(0xffffff)) | 0xff000000;
  }
  
  
  //this is where it starts assuming that we are receiving data, not generating as shown above
  //Pass 1
  for (int i=0; i<data.pixels.length; i++) {
    indexlist[i] = int(hue(data.pixels[i]));//target
    counts[indexlist[i]]++;//increment the count table
  }
  
  //allocate arrays to hold sorted data
  //possibly faster to pre-allocate [256][data.length] but would require much more RAM
  //[256][65536] == 16 million int's, or a 4096x4096 image
  //Pass 2
  for (int i=0; i<256; i++) {
    contents[i] = new int[counts[i]];
  }
  
  
  //Fills contents from data
  //Pass 3
  for (int i=0; i<data.pixels.length; i++) {
    contents[ indexlist[i] ][ contents[indexlist[i]].length - counts[indexlist[i]] ] = data.pixels[i];
    counts[indexlist[i]]--;//back down the count table
  }
  
  
  //Cycle through the 256 indecies in order and list them out
  //Pass 4
  int idx = 0;//Location to place into output
  
  for (int i=0; i<contents.length; i++) {//outer array size
    
    for (int d=0; d<contents[i].length; d++) {
	out.pixels[idx] = contents[i][d];
	idx++;
    }
    
  }
  
  println("milliseconds: " + (millis() - tmr));
  
  noLoop();
}


void draw() {
  image(data,0,0);
  image(out,w,0);
}

« Last Edit: Apr 3^rd, 2009, 8:13am by N/A »

clankill3r Full Member Offline Posts: 210 Netherlands	Re: need help by sorting a color array Reply #4 - Apr 4^th, 2009, 7:25am hi, looks good but I dont understand all. starting with this, counts[indexlist[i]]++;//increment the count table why is this needed?
	« Last Edit: Apr 4^th, 2009, 9:02am by clankill3r »

NoahBuddy

Re: need help by sorting a color array
Reply #5 - Apr 5^th, 2009, 1:36am

I used counts[] as a kind of stack for each level (0 to 255). A pre-calculation for pass 3 where counts[] is used as an index to fill contents[level][index].

I did that instead of looping through each sub array and finding the matching values from the data.

There may be another way to do it, but 'I believe' it is one of the fastest.

clankill3r Full Member Offline Posts: 210 Netherlands	Re: need help by sorting a color array Reply #6 - Apr 5^th, 2009, 5:16am I tried to get your code to work in a draw to get it working with the webcam. It shows the webcam on the left but on the right I see a black screen drawn instand of the colors sorted by hue. what is going wrong? Code in next post (max 2000 characters is way to less for a forum like this ....)

clankill3r

Re: need help by sorting a color array
Reply #7 - Apr 5^th, 2009, 5:17am

Code:

int w = 320, h = 240;

////PImage data;
PImage out = new PImage(w,h);

import processing.video.*;//+++++
Capture cam;//+++++


int[][] contents = new int[256][];//256 levels for RGB/hue/brightness/etc

int[] counts = new int[256];//256 levels for RGB/hue/brightness/etc
int[] indexlist = new int[76800];//int[] indexlist = new int[data.pixels.length];



void setup() {
  size(640,480);
  ////data = loadImage("test.png");
  ////image(data, 0, 0);
  cam = new Capture(this, 320, 240);//++++++++++
}


void draw() {
  if (cam.available() == true) {
    int tmr = millis();
    cam.read();
    image(cam, 0, 0);
    //set(0, 0, cam);    

    //This is actually more overhead, as you would have an image as a source, still counted in the timer
    //Pass 0
    //this is where it starts assuming that we are receiving data, not generating as shown above
    //Pass 1
    for (int i=0; i<cam.pixels.length; i++) {
	indexlist[i] = int(hue(cam.pixels[i]));//target
	counts[indexlist[i]]++;//increment the count table
    }

    //allocate arrays to hold sorted data
    //possibly faster to pre-allocate [256][data.length] but would require much more RAM
    //[256][65536] == 16 million int's, or a 4096x4096 image
    //Pass 2
    for (int i=0; i<256; i++) {
	contents[i] = new int[counts[i]];
    }

    //Fills contents from data
    //Pass 3
    for (int i=0; i<cam.pixels.length; i++) {
	contents[ indexlist[i] ][ contents[indexlist[i]].length - counts[indexlist[i]] ] = cam.pixels[i];
	counts[indexlist[i]]--;//back down the count table
    }

    //Cycle through the 256 indecies in order and list them out
    //Pass 4
    int idx = 0;//Location to place into output
    for (int i=0; i<contents.length; i++) {//outer array size
	for (int d=0; d<contents[i].length; d++) {
	  out.pixels[idx] = contents[i][d];
	  idx++;
	}

    }

    println("milliseconds: " + (millis() - tmr));

  }

 // image(data,0,0);
   image(out,w,0);
}

NoahBuddy Ex Member	Re: need help by sorting a color array Reply #8 - Apr 5^th, 2009, 10:43pm Ah, to get it to work, I had to surround the meat of the draw function with load -and updatePixels(). cam.loadPixels(); out.loadPixels(); image(cam,0,0); ... //rest of code ... cam.updatePixels(); out.updatePixels(); image(out,w,0);

clankill3r

Re: need help by sorting a color array
Reply #9 - Apr 6^th, 2009, 9:43am

cool, thx it works now

Just some questions,

why a two dimensional aray for this one?
Code:


int[][] contents = new int[256][];//256 levels for RGB/hue/brightness/etc

about:

cam.loadPixels();
out.loadPixels();
image(cam,0,0);
...
//rest of code
...
cam.updatePixels();
out.updatePixels();
image(out,w,0);

why out.loadPixels(); and cam.updatePixels(); it works without so it can be used without right.

Also this one can be used on a image and it works but it doesnt use loadPixels, howcome that it works without using load where the cam version does have to use load?

Code:

int w = 320, h = 240;

PImage data;
PImage out = new PImage(w,h);

int[][] contents = new int[256][];//256 levels for RGB/hue/brightness/etc

int[] counts = new int[256];//256 levels for RGB/hue/brightness/etc
int[] indexlist = new int[76800];//int[] indexlist = new int[data.pixels.length];

void setup() {

  size(640,480);
  data = loadImage("test.png");
  image(data, 0, 0);
  int tmr = millis();

  for (int i=0; i<data.pixels.length; i++) {
    indexlist[i] = int(hue(data.pixels[i]));//target
    counts[indexlist[i]]++;//increment the count table
  }

  for (int i=0; i<256; i++) {
    contents[i] = new int[counts[i]];
  }

  for (int i=0; i<data.pixels.length; i++) {
    contents[ indexlist[i] ][ contents[indexlist[i]].length - counts[indexlist[i]] ] = data.pixels[i];
    counts[indexlist[i]]--;//back down the count table
  }

  int idx = 0;//Location to place into output

  for (int i=0; i<contents.length; i++) {//outer array size
    for (int d=0; d<contents[i].length; d++) {
	out.pixels[idx] = contents[i][d];
	idx++;
    }

  }

  println("milliseconds: " + (millis() - tmr));

  noLoop();
}


void draw() {
  image(data,0,0);
  image(out,w,0);
}

I still don't understand all so maybe I ask more later but I'm prety tired atm so I will look at it again later.

NoahBuddy

Re: need help by sorting a color array
Reply #10 - Apr 6^th, 2009, 1:29pm

Two dimensions:

I knew I would have 256 sub arrays, but the length of each sub array depends on the data of the image.
It was just easier than indexing a single dimension array.

Not needing updatePixels():

I have had mixed results on different machines (possibly different versions of Processing) as to when I need to use load/update so I used both to be safe.
If it works without... cool.

I don't know the 'how' part, but I do know 'why' the example didn't need update: it seems anything done in setup() is ready. Since draw() is called only once after that, no update was needed.

clankill3r

Re: need help by sorting a color array
Reply #11 - Apr 6^th, 2009, 2:50pm

ok I understand that.

for the pass 1, althought you tried to explain it I still not understand what kind of value or how the counts is saved. I tried to println it but then I get a arrayOutOfBoundsExeption: 76800
Why do I get that error?

Code:


    //Pass 1
    for (int i=0; i<cam.pixels.length; i++) {
	indexlist[i] = int(hue(cam.pixels[i]));//target ////saves hue to indexlist[i]
	counts[indexlist[i]]++;//increment the count table
	if ((i % 1000) == 0) {
	  println(counts[indexlist[i]]++);
	}
    }

I also tried
if (i == 76800) {

then it prints nothing, and if I try
if (i == 76799) {

then I get the outOfBounds thing again Undecided

If you don't mind could you give me a noob explenation that goes in detail how it works?

koogy

Re: need help by sorting a color array
Reply #12 - Apr 6^th, 2009, 3:10pm

the array is limited to 76800 integers which is 320x240 (width and height as defined at the top there)

but if your image is bigger than this then it'll try writing beyond the end of the array and will fail

the number of pixels in the image is given by
cam.pixels.length

try printing that out before the loop, see what it is.

NoahBuddy

Re: need help by sorting a color array
Reply #13 - Apr 6^th, 2009, 9:31pm

There is a catch in your println() statement:
Code:


//Pass 1
    for (int i=0; i<cam.pixels.length; i++) {
	indexlist[i] = int(hue(cam.pixels[i]));
	counts[indexlist[i]]++;//increment the count table
	if ((i % 1000) == 0) {
	  println(counts[indexlist[i]]);//<------------Remove the ++
	}
    }

Every 1000 counts, the value would be incremented once more.

As for what counts[indexlist[i]] holds, it is the number of pixels that have a matching hue of indexlist[i].

NoahBuddy

Re: need help by sorting a color array
Reply #14 - Apr 6^th, 2009, 10:14pm

Don't feel bad about not getting it at first, after all, a sorting method that does no > or < comparisons blew my mind at first (that was your code by the way Wink

).

I'll give a shot at explaining.
Let's look at the problem like we are sorting different colored plates. (Hey! I do remember something from school Shocked

).

Pass 1:
Go over each pixel in the image (the pile of dishes).
Look at the hue of each plate (img.pixels[i]).

Put a sticky note next to each plate (at indexlist[i]) that tells which hue pile the plate should go to.

Count the number of sticky notes of the same color. To be efficient, we count them as we place the notes (counts[indexlist[i]]++).

Pass 2:
Make sure we have enough space in each hue pile for all of the plates.
(Allocate arrays)

Pass 3:
Stack the plates on their matching pile, keeping track of how many plates of each hue we have left (counts[indexlist[i]]--).

Pass 4:
Pick up each smaller stack and put them, in order, into the dish rack (out.pixels).

Forgive me if that was a little 'too' basic. It is similar to how a Stack was explained to me during one of my classes.

Edit: Just a side note, since I can't modify my other entry, will put here. I was mistaken before, this is actually a http://en.wikipedia.org/wiki/Counting_sort. Similar to Radix I think.

« Last Edit: Apr 7^th, 2009, 2:48pm by N/A »

Pages: 1 2

‹ Previous Topic | Next Topic ›