Quicksort

Hello!

I’ve just started with ofx recently and I’ve been trying to port some of sketches from processing over to open frameworks to practice and learn.

In this particular project, I’m trying to send the pixels of an image into a quicksort algorithm. It seems pretty straight forward, and I got it working (kind of) but I can only sort one channel at a time, which has generated some interesting results, but not ultimately my goal. As I understand it, this is because of the way ofx stores pixels in the array of unsigned chars as rgbrgbrgb etc.

What I’m trying to do is create a variable representing all the channels of one pixel, so I can move it and all of it’s channels together in unison. I would think that I would need to store all of the r,g,b vals in a small array and replace the relevant datatypes in the quicksort algorithm to match this. I tried throwing this line into quicksort instead of the loc but it crashed out of the array.

int colors = (pixels[loc]<<16 | pixels[loc+1] <<8 | pixels[loc+2]);

Does anyone have any advice on a good way to group my pixels with all their channels together?

As an aside, I also understand there is already a quicksort function (qsort) built in to c++, is there any reason to use that over the one I have below (which seems to work fine)?

Here’s what I’m working with:

(click 2 or 3 times to increase the inc variable and start the sorting process.)

my .h file

  
  
#pragma once  
  
#include "ofMain.h"  
  
class testApp : public ofBaseApp{  
	public:  
		void setup();  
		void update();  
		void draw();  
          
		void keyPressed(int key);  
		void keyReleased(int key);  
		void mouseMoved(int x, int y);  
		void mouseDragged(int x, int y, int button);  
		void mousePressed(int x, int y, int button);  
		void mouseReleased(int x, int y, int button);  
		void windowResized(int w, int h);  
		void dragEvent(ofDragInfo dragInfo);  
		void gotMessage(ofMessage msg);  
          
        int h, w, inc;  
        ofImage img;  
        unsigned char * pixels;          
      
        void quicksort(unsigned char x[], int left, int right);        
};  
  

my .cpp file

  
  
#include "testApp.h"  
  
//--------------------------------------------------------------  
void testApp::setup(){  
    img.loadImage("image.jpg");  
    ofSetFrameRate(60);  
    ofSetWindowShape(img.width, img.height);  
      
    inc = 1;  
      
    w = img.width;  
    h = img.height;  
      
}  
  
//--------------------------------------------------------------  
void testApp::update(){  
      
  
}  
  
//--------------------------------------------------------------  
void testApp::draw(){  
    img.draw(0,0);  
    pixels = img.getPixels();  
    for(int y = 0; y<h-1; y++){  //loop through pixels  
        for(int x = 0; x<w-1; x++){  
      
            int loc = (x+y*w)*3;  //pixel location  
  
            //int colors = (pixels[loc]<<16 | pixels[loc+1] <<8 | pixels[loc+2]);  
                                  
            int red = pixels[loc];  
            int green = pixels[loc+1];  
            int blue = pixels[loc+2];  
              
//if greater than red, sort those pixels  
            if(red>30){  
            quicksort(pixels, loc, loc+inc);  
            }  
       }  
    }  
  
    img.update();  
  
    //show frameRate  
    ofDrawBitmapString(ofToString(ofGetFrameRate())+"fps", 10, 15);  
    //show inc  
    ofDrawBitmapString("inc="+ofToString(inc), 10, 30);  
}  
  
  
//--------------------------------------------------------------  
  
//the pivot partition for quicksort  
int partition(unsigned char a [], int l, int r) {    
    int i = l;  
    int j = r;  
    int temp;  
    int pivot = a[(i+j)/2];  
    while (i<=j) {  
        while (a[i] < pivot) {  
            i++;  
        }  
        while (a[j] > pivot) {  
            j--;  
        }  
        if (i <= j) {  
            temp = a[i];  
            a[i] = a[j];  
            a[j] = temp;  
            i++;  
            j--;  
        }  
    }  
    return i;  
}  
//--------------------------------------------------------------  
  
void testApp::quicksort(unsigned char x [], int left, int right) {   
    int index = partition(x, left, right);  
  
    if (left < index - 1) { //changing the 1 vals here to a 2 or 3 helps when the program immediately crashes  
        quicksort(x, left, index-1);  
    }  
    if (index > right) {  
        quicksort(x, index, right);  
    }  
}  
  
//--------------------------------------------------------------  
void testApp::keyPressed(int key){  
  
}  
  
//--------------------------------------------------------------  
void testApp::keyReleased(int key){  
  
}  
  
//--------------------------------------------------------------  
void testApp::mouseMoved(int x, int y){  
  
}  
  
//--------------------------------------------------------------  
void testApp::mouseDragged(int x, int y, int button){  
  
}  
  
//--------------------------------------------------------------  
void testApp::mousePressed(int x, int y, int button){  
    inc+=1; //click to increase inc  
}  
  
//--------------------------------------------------------------  
void testApp::mouseReleased(int x, int y, int button){  
  
}  
  
//--------------------------------------------------------------  
void testApp::windowResized(int w, int h){  
  
}  
  
//--------------------------------------------------------------  
void testApp::gotMessage(ofMessage msg){  
  
}  
  
//--------------------------------------------------------------  
void testApp::dragEvent(ofDragInfo dragInfo){   
  
}  
  

Many thanks!!

What I’m trying to do is create a variable representing all the channels of one pixel, so I can move it and all of it’s channels together in unison

You’re in luck, ofColor is exactly that. Because it has a getHue() method, you can easily sort by hue or compare RGB as well if you want. There is a sort method in the std library http://www.cplusplus.com/reference/algorithm/sort/?kw=sort that you can use in a weird way:

float pixelHues[SIZE_OF_IMG];

  
std::sort(pixelHues, pixelHues + (SIZE_OF_IMG * sizeof(float)), std::greater<float>());  

You’re going to need to copy the ofColors from an ofPixels instance, run a sort, then place the array back in the ofPixels instance. This might be sped up by just using the bitwise channel grabbing that you’re doing, test it out and see what happens :slight_smile:

Thank you Joshua! I will see if I can figure it out with the information you’ve provided.

Also, I’ve been reading your programming interactivity book, on and off for a couple weeks now and found it very helpful. So thanks for that too :slight_smile:

OK, I think I was able to make some progress, but I have a few more questions. I am essentially doing what you’ve done in the Analyzing bitmaps chapter, kind of replicating what you have going on in page 313.

So my pixelHues array should be equal to the image size (width*height), so that there is one value for every pixel in the source image. In your example, you use the value 2048 (256*8) instead, which is standing in for all possible hues in an 8 bit image. I want a list of all the hues in my image, but not necessarily all the possible hues.

I’m a little confused about when I should be using getPixelsRef vs. getPixels. If I am understanding correctly, getpixels pulls the unsigned char pointers to the pixels, whereas getPixelsRef pulls the reference for each pixel. This seems to make sense, but when should one be used over the other? Is this data not interchangeable?

Is it possible to allocate the size of the array in the header file more dynamically? I realize I could just multiply the width*height and put that value in there, but is there a more reusable way to do this? it would be nice if I could just use float pixelHues[imgSize]; rather than writing an exact value in there every time I want to use an image of a different size. I feel like there is a simple solution to this, and while not necessarily a big problem, it would be nice to see how this is done.

Why is the color.getHue() value multiplied by 8? Is this to fill up the array to 2048? Is this necessary in this instance? I was under the impression that the getHue function would return a value between 0-255, aren’t those the ones I’m trying to get a hold of?

  
  
    for(int i  = 0; i<imgSize; i++){   
        pixelHues[i] = 0;  
    }  
  
        ofPixels pixelsRef = img.getPixelsRef();   
        unsigned char* pixels = img.getPixels();  
  
    #ifndef USE_OFCOLOR  
    for(int y = 0; y<h; y++){  
        for(int x = 0; x<w; x++){  
            ofColor color = img.getColor(x,y);  
            //ofColor color = pix.getColor(x,y);   
            hue = int(color.getHue()*8.0);  
            pixelHues[hue]+=1;              
        }  
    }  
    #endif  
  

Then in my draw loop I want to have something like

  
  
for(int i = 0; i<imgSize; i++){  
quicksort(pixelHues, i, i+1);  
}  
  

Which will perform the sort on the array, and I’ve been successful at making this happen. Actually I got it to sort the lines in the example sketch. But I’m stymied at how I can plug the resorted pixelHues back into the ofPixels instance. This seems like it is my biggest problem here.

The goal is to have the sort happen one frame at a time, so that you can see it in real time. Here is one of my preliminary tests to give you an idea of what’s going on. https://vimeo.com/69284015. This one is sorting pixels from loc to loc+3.

I was wondering if another way to do it would be to group parts of the pixel array into smaller arrays of 3 values(or 4 if alpha) containing the rgb values for instance pixelGroup[2] = {loc, loc+1, loc+2}, and then sort those? Sorry if that is not making much sense.

Lastly, I was reading that ofPixels uses pixels on the CPU whereas ofTexture is using pixels on the GPU. Would it not be much faster to store my pixels in an ofTexture, since even with a 500px x 500px image we’re dealing with 250,000 values?

Anyway, thank you for bearing with my inane questions! Very much appreciated :slight_smile:

I like the look of that video. Ok, so I can’t get to all of your questions right here, but I’ll do what I can:

pixels are on the CPU and this is a good thing because we can sort them, we can’t (I mean, without some heavy-firepower) sort them on the GPU.

Allocating an array dynamically looks like this:

  
unsigned char *blah;  
// later  
blah = new unsigned char[2048]; // or whatever  
// when you're all done with it  
delete[] blah;  

I kinda can’t remember what I was doing and I don’t have the book in front me, sorry :slight_smile:

Putting hues back into the ofPixels would look like this (sorry for the pseudo-code, I’m on my phone):

  
for( pixels ) {  
    ofColor c( hue[i], 255, 255 );  
    pixels.setColor( x, y, c );  
}  

Hope that helps a little.

Thank you again for the help Joshua!

It’s moved me along a little, but I’ve hit another stumbling block. I was able to take the hues from the ofPixels and place them into an array of unsigned chars (phues). From there I can set their colors back into a new ofImage.

I can print out the list of hues with the commented cout line down there. I painted the first few pixels in my image red, green, and blue, to be absolutely sure that the correct hue values are being read (they are).

But when I try and plug the hue array into my sorting algorithm, nothing happens. The program runs unchanged. I’m truly stumped as to why this is. I have all the values in the array, shouldn’t I be able to sort them? The quicksort algorithm I was using before had no trouble sorting unsigned chars. I’m using the same one as posted above. What am I missing here? Would it help me if something was written into quicksort to check if sorted or not? Doesn’t seem like it’s doing anything.

  
  
  
    int imgSize = w*h;  
    unsigned char phues[imgSize];  
    int huePos = 0;  
  
void testApp::draw(){  
    img.draw(0,0);  
    newImg.draw(w,0);  
  
    ofColor color;  
  
    ofPixels pix = img.getPixelsRef();   
      
    for(int y = 0; y<h; y++){  
        for(int x = 0; x<w; x++){  
              
            color = img.getColor(x,y);  // grab colors from ofpixels instance  
            int loc = (x+y*w);  
          
            //hsb  
            hue = color.getHue();  
            sat = color.getSaturation();  
            bri = color.getBrightness();  
                  
            phues[int(huePos)] = color.getHue() ; // store hues in phues array  
  
            quicksort(phues, huePos, huePos+1); //I thought this would sort the phues but nothing happens                      
              
            ofColor c = ofColor::fromHsb(phues[int(huePos)],sat,bri);  //convert to HSB and save to c  
            pix.setColor(x,y,c);  //place back into pix  
      
            //cout << (int)phues[huePos] << ' ';  
       }  
    }  
      
     
    newImg.setFromPixels(pix);  //place pix into newImg  
    img.update();  
    newImg.update();  
}  
  
  

As an aside, I also tried to use the std::sort function that you provided above, but it won’t sort unsigned chars. I changed the unsigned chars to ints, but it came up with a runtime error that looked like it was going out of the array. The closest I got was:

  
  
std::sort(hueInt, hueInt+(imgSize*sizeof(int)), std::greater<int>());  
  

Thank you again for the help :slight_smile:

Hi Again,

Now that some time has passed and I’m feeling a little more competent with oF I thought I would return to this program that I never got working correctly.

Per Joshua’s suggestion I made a float array, stored the hues from the ofPixels in it, ran it through the sort, returned them to a new img, and it does something…but definitely not what’s intended. It seems to leave only the red channel, and instead of doing a per-pixel sort it just drags everything across the window evenly to the left.

To my eyes everything looks right, but maybe someone can take a look and see if I am making a mistake somewhere?

It’s also extremely slow, like runs down to about 3fps almost instantly. Aside from doing some bitwise grabbing of the color channels, is there anything I can do to boost performance? I know I’m operating on a relatively large array, but it should still be faster than 3fps, especially with an image thats only 500x500px.

in.h I have

  
  
#pragma once  
  
#include "ofMain.h"  
  
class testApp : public ofBaseApp{  
	public:  
		void setup();  
		void update();  
		void draw();  
          
		void keyPressed(int key);  
		void keyReleased(int key);  
		void mouseMoved(int x, int y);  
		void mouseDragged(int x, int y, int button);  
		void mousePressed(int x, int y, int button);  
		void mouseReleased(int x, int y, int button);  
		void windowResized(int w, int h);  
		void dragEvent(ofDragInfo dragInfo);  
		void gotMessage(ofMessage msg);  
          
        int h, w;  
        ofImage img, newImg;  
        ofPixels pix;  
        unsigned char * pixels;  
          
        float * hues;          
        float hue;  
        float bri;  
        float sat;  
          
        void quicksort(float x[], int left, int right);     
};  
  

testApp.cpp

  
  
void testApp::setup(){  
    img.loadImage("image.jpg");  
  
    ofSetWindowShape(img.width, img.height);  
      
    w = img.width;  
    h = img.height;  
  
    imgSize = w*h;  
      
    newImg.allocate(w, h, OF_IMAGE_COLOR);  
    pix.allocate(w, h, 3);  
  
    hues = new float [w*h];  
}  
  
//--------------------------------------------------------------  
void testApp::update(){  
      
    ofColor color;  
    pix = img.getPixelsRef();   
      
    for(int y = 0; y<h-1; y++){  
        for(int x = 0; x<w-1; x++){  
      
            color = pix.getColor(x,y);  
            int loc = x+y*w;  
  
            hues[loc] = color.getHue();  
        
            float sat = color.getSaturation();  
            float bri = color.getBrightness();  
              
            quicksort(hues, loc, loc+1);  
              
            ofColor c = ofColor::fromHsb(hues[loc],sat,bri);   
            pix.setColor(x,y,c);  
        }  
    }  
    newImg.setFromPixels(pix);  
    newImg.update();  
}  
  
  
  
//--------------------------------------------------------------  
void testApp::draw(){  
    newImg.draw(0,0);  
}  
  
unsigned char partition(float a[], int l, int r) {    
    int i = l;  
    int j = r;  
    int temp;  
    int pivot = a[(i+j)/2];  
    while (i<=j) {  
          
        while (a[i] < pivot) {  
            i+=1;  
              
        }  
        while (a[j] > pivot) {  
            j-=1;  
        }  
        if (i <= j) {  
            temp = a[i];  
            a[i] = a[j];  
            a[j] = temp;  
            i+=1;  
            j-=1;  
        }  
    }  
     
    return i;  
}  
  
void testApp::quicksort(float x [], int left, int right) {   
    int index = partition(x, left, right);  
    if (left < index - 1) {  
        quicksort(x, left, index-1);  
          
    }  
    if (index > right) {  
        quicksort(x, index, right);  
          
    }  
}  
  

With just a quick look, I think what you are doing wrong is that you are sorting “hues” while you are inserting into the array. You need to insert all hue values into the array, sort the array and then get them back into the image, but you need to figure out how to keep the sat and the brightness values.

Also the getHue() method is slow and when using getBrightness() and getSaturation(), you are basically calling the getHsb() method of ofColor three times. You should use this:

  
  
float h,s,b;  
color.getHsb(h,s,b);  
  

And here is how you could use std::sort to sort ofColor directly, but it’s def really slow!

  
  
bool sortByHSB(const ofColor &c1,const ofColor &c2) {  
	return c1.r < c2.r;  
}  
  
//--------------------------------------------------------------  
void testApp::update(){  
	  
	pix = img.getPixelsRef();  
	colors.clear();  
	  
	for(int y = 0; y<h-1; y++){  
        for(int x = 0; x<w-1; x++){  
			colors.push_back(pix.getColor(x,y));  
        }  
    }  
	  
	std::sort(colors.begin(), colors.end(), sortByHSB);  
	  
	for(int y = 0; y<h-1; y++){  
        for(int x = 0; x<w-1; x++){  
			int index = x+y*w;  
			pix.setColor(x, y,colors[index]);  
        }  
    }  
  
    newImg.setFromPixels(pix);  
    newImg.update();  
  
}  
  

colors is vector

I will try to come up with a faster method for sorting, when I have more free time.

Cheerz,
Kamen

1 Like