Questions Regarding Increasing Speed of Processing Sketch

kieransta..

Questions Regarding Increasing Speed of Processing Sketch

in Contributed Library Questions • 1 year ago

Hey, I'm trying to create a live pixel sorting algorithm using the Kinect and a mashed up version of the Sorting Algorithm's seen here...

http://www.onformative.com/lab/the-form-of-sorting-algorithms/

The idea is to have the kinect facing people moving etc, and for the sketch to display the pixels being sorted live on screen.

At the moment the idea of it is working alright, however i've executed it pretty poorly and it's running very slowly. Ideally I'd like it to run at a reasonable framerate, however I've set the framerate to 60 and it's definitely not running anywhere near that. I'm guessing it's probably something to do with the efficiency of it, or something to do with arrays looping infinitely, but I'm not too too sure.

Thanks in advancement for any help/ ideas of things to look at to help me with this.

/* OpenProcessing Tweak of *@*http://www.openprocessing.org/sketch/27745*@* */
/* !do not delete the line above, required for linking your tweak if you re-upload */
import processing.video.*;
import processing.opengl.*;
import org.openkinect.*;
import org.openkinect.processing.*;
// Kinect Library object
Kinect kinect;
float deg = 20; // Start at 15 degrees
int[] colors;
float mainY = 0;
int mainStep = 0;
int CURRENTSORTING = 0;
String sortingName = "quickSort";
PImage colorImage;
void setup() {
//size (640, 480);
//width = 640;
//height = 480;
size(1280, 720);
//background(190, 90, 90);
frameRate(60);
kinect = new Kinect(this);
kinect.start();
kinect.enableRGB(true);
//kinect.enableIR(false);
//kinect.enableDepth(false);
kinect.processDepthImage(false);
kinect.tilt(deg);
colors = new int[width];
}
void draw() {
colorImage = kinect.getVideoImage();
image(colorImage,0,0);
scale(2.5);
colorImage.updatePixels();
//tint(255, 126);
//width = 640;
//height = 480;
smooth();
doSort();
//colorImage.updatePixels();
//image(colorImage,0,0);
// sortedImage = colorImage.get();
//sortedImage.loadPixels();
//image(colorImage,0,0);
}
void doSort() {
//colorImage = kinect.getVideoImage();
//image(colorImage,0,0);
//colorImage.loadPixels();
mainY = 0;
mainStep = 0;
//background(0);
// fill colors array
int imageY = (int)random(colorImage.height);
for(int i=0;i<width;i++) {
colors[i] = colorImage.get(i, imageY);
}
//background(255);
smooth();
switch(CURRENTSORTING) {
case 0:
quickSort(colors,0,colors.length-1);
break;
case 1:
bubbleSort(colors);
break;
case 2:
selectionSort(colors);
break;
case 3:
insertionSort(colors);
break;
case 4:
shellsort(colors);
break;
case 5:
heapSort(colors);
break;
}
}
/*
* draw the values of given array as colors
*/
void drawArray(int[] array) {
for(int i=0;i<array.length;i++) {
stroke(array[i]);
line(i, mainY, i, mainY+1);
}
mainY++;
}
// ------ quicksort --------- //
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right)/2];
int counting = 0;
while (i <= j) {
if(mainStep++ % 8 == 0) drawArray(arr);
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
}
if (index < right) {
quickSort(arr, index, right);
}
}
// ------ selection sort --------- //
public void selectionSort(int[] arr) {
int i, j, minIndex, tmp;
int n = arr.length;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
if(mainStep++%2==0) drawArray(arr);
}
}
}
// ------ insertion sort --------- //
void insertionSort(int[] arr) {
int i, j, newValue;
int counts = 0;
for (i = 1; i < arr.length; i++) {
newValue = arr[i];
j = i;
while (j > 0 && arr[j - 1] > newValue) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = newValue;
if(mainStep++%2==0) drawArray(arr);
}
}
// ------ bubble sort --------- //
public void bubbleSort(int[] a)
{
int out, in;
int nElems = a.length;
int counts = 0;
for(out=nElems-1; out>1; out--) {
for(in=0; in<out; in++) {
if( a[in] > a[in+1] ) {
swap(a, in, in+1);
}
}
if(counts++%2 == 0) drawArray(a);
}
}
private void swap(int[] a, int one, int two)
{
int temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// ------ shell sort --------- //
void shellsort(int[] a)
{
int i, j, k, h, t;
int n = n=a.length;
int[] cols = {
1391376, 463792, 198768, 86961, 33936,
13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1
};
int steps = 0;
for (k=0; k<16; k++)
{
h=cols[k];
steps++;
for (i=h; i<n; i++)
{
j=i;
t=a[j];
steps++;
while (j>=h && a[j-h]>t)
{
a[j]=a[j-h];
j=j-h;
steps++;
}
a[j]=t;
if(steps % 12 == 0) drawArray(a);
}
}
}
// heapsort
void sift (int[] a, int l, int r) {
int i, j;
int x;
i = l;
x = a[l];
j = 2*i+1;
if ((j<r) && (a[j+1]<a[j])) j++;
while ((j<=r) && (a[j] < x)) {
a[i] = a[j];
i = j;
j = j*2+1;
if ((j<r) && (a[j+1]<a[j])) j++;
}
a[i] = x;
}
// ------ heap sort --------- //
void heapSort (int[] a) {
int l,r,n,tmp;
n = a.length;
for (l=(n-2)/2; l>=0; l--)
sift(a,l,n-1);
for (r=n-1; r>0; r--) {
tmp = a[0];
a[0] = a[r];
a[r] = tmp;
sift(a, 0, r-1);
if(mainStep++%2==0)drawArray(a);
}
}
void mousePressed() {
save(sortingName + "_" + (System.currentTimeMillis()/1000) + ".tif");
print("SAVED");
}
void keyPressed() {
if (key == CODED){
if (keyCode == UP){
deg++;
}
else if (keyCode == DOWN){
deg--;
}
deg = constrain(deg,0,30);
kinect.tilt(deg);
}
if(key == '0') {
CURRENTSORTING = 0;
sortingName = "quickSort";
print("Quick_Sort");
print(" ");
}
if(key == '1') {
CURRENTSORTING = 1;
sortingName = "bubbleSort";
print("Bubble_Sort");
print(" ");
}
if(key == '2') {
CURRENTSORTING = 2;
sortingName = "selectionSort";
print("Selection_Sort");
print(" ");
}
if(key == '3') {
CURRENTSORTING = 3;
sortingName = "insertionSort";
print("Insertion_Sort");
print(" ");
}
if(key == '4') {
CURRENTSORTING = 4;
sortingName = "shellSort";
print("Shell_Sort");
print(" ");
}
if(key == '5') {
CURRENTSORTING = 5;
sortingName = "heapSort";
print("Heap_Sort");
print(" ");
}
doSort();
}
void stop() {
kinect.quit();
super.stop();
}

Cheers

Replies(9)

not_55

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

Have you tried some basic 'profiling', turning off scaling/smoothing or particular sorts etc to find out where the bottlenecks are?

A very quick look, (sorry if this isn't too accurate!)

76 int imageY = (int)random(colorImage.height);

Isn't colorImage always the same size? If so maybe you could optimise this line?

Switch statement from line 84 onwards

Am I imagining things or are you passing the colors array to the various functions unnecessarily as it's declared globally?

kieransta..

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

Thanks for getting back in touch not_55

I've tried turning off the scaling + smoothing but it's running just as slow.

It's fine, thanks for looking over it..

I've got quite a bit of knowledge about Processing but I'm no master at it so sorry if some of my questions are solved very simply...

—In what way could I optimise line 76?

—The code in general is an amalgamation of me working things out and using code written by onformative, however from my understanding yes, I think the colors array is being passed unnecessarily to the various functions. Do you have any advice on how to sort this out?

Cheers

not_55

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

Re the colors array - just remove it from the function calls if it's declared globally so:

quickSort(colors,0,colors.length-1); becomes quickSort(0,colors.length-1); and you redefine the function/method so it knows not to expect an array ... void quickSort(int left, int right).

Furthermore, the left right parameters are redundant as left is zero and right is the array size which you can get within the function rather than passing these values every time.

Re line 76 - well to my old-school head dereferencing values is always slower so store 'colorImage.height' in a simple variable/constant as it never changes. I can think of other things but to be honest with processor speed these days they're probably irrelevant.

These two changes will probably make next-to-no difference - you need to find where the slow down is occuring and attack there first!

Take this with a pinch of salt - I'm new to processing too although I have lots of other coding experience...

Good luck!

kieransta..

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

I've been working on it solidly over the past few days trying to nail what exactly is slowing the code down. I've cut it down so that it runs with only one sorting algorithm at the moment and discovered that from line 84 where the 'switch' statement begins there is a massive slow down in speed. I've taken out the 'switch' at the moment and replaces it with an 'if' statement and it's running a lot faster at the moment compared to what it was, but it is still only running at 4fps rather than the 0.87fps i was experiencing beforehand.

Thanks for all your help, I'll keep going with it and I'll hopefully be able to crack whats slowing it down so much and try to get it running around the 30fps if possible.

If anyone else has any more tips or ideas how to speed it up just get back at me on this.

Cheers!

PhiLho

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

To be honest, the suggestions of avoiding dereferencing (a.x) or remove parameters from a function call were good in C code when we had a 1 MHz CPU... Now, I doubt it will gain anything measurable.

Likewise, replacing a switch with several ifs would surprise me if if gains any speed. Switch is supposed to be faster, actually.
Now, if you removed all the code of the switch, indeed it can gain speed: sorting is a costly and slow operation, that's probably where your lost FPS are...

not_55

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

"To be honest, the suggestions of avoiding dereferencing (a.x) or remove parameters from a function call were good in C code when we had a 1 MHz CPU... Now, I doubt it will gain anything measurable."

I did say it was probably irrelevant :D

Maybe it's just trying to deal with too much data, try reducing the size() or re-scaling somehow.

PhiLho

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

" I did say it was probably irrelevant"
Yes, my remark was only a confirmation...

I come from the 1 MHz CPU era, and I had similar suspicions when I started Java, so I understand them.

kieransta..

Re: Questions Regarding Increasing Speed of Processing Sketch

1 year ago

I don't even know if this is possible/ me being completely stupid, but do you reckon it is possible to scale down the initial video feed in void setup

i.e. set it as something like:

void setup(){

size(640, 280);

scale(-10);

and then further along in the code rescale the outputted sorted image feed as something like:

scale(10);

or is that me just being completely ridiculous haha?

not_55

Re: Questions Regarding Increasing Speed of Processing Sketch

11 months ago

I'm afraid I'm not familiar with using video input to Processing.. I think a search of the forums/wiki/web will be your best bet.

In essence I'd guess you need to either limit the 'bandwidth' of the input by hardware settings or somehow 'ignore' parts of it so you have less data to deal with..sorry I can't help more.

Top Reply