N-dimensional sorting and color

[Pisicandru]

Hi,

I know this is over 1 year old, but as many others i am interested in this topic. Not necessarily for the sake of actual pixel sorting, but for the more general problem of n-dimensional sorting, and color sorting is a nice visual example of this actually since each color is at least 3-dimensional in RGB. Anyway - looking though posts i am intrigued by the idea of a unique negative number that represent “color”, with -1 white and -16777216 black. How do you do the transformation from RGB to this negative number? I read the processing help for color, but i still don’t understand it. This transformation is also interesting because you actually reduce the dimensions from 3 to 1 - it seems.

Thanks for any insight,
Monica

[jeremydouglass]

@Pisicandru

How do you do the transformation from RGB to this negative number? I read the processing help for color, but i still don’t understand it.

They aren’t actually “negative numbers” in any meaningful sense. All values with alpha greater than 50% have their first bet set – which happens to be the “sign” bit if it was a normal number (which it isn’t).

Try searching the forum for past discussions of

AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB

Maybe this explanation will help?

Println(color) gives strange color number

An important thing to understand is that, from Processing’s perspective, there is no “negative bit” in a color. The bits are AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB. Because the actual storage for a color is an int, if you println() the int, it is interpreted as having a sign bit – but that is just an interpretation of a list of 0s and 1s, and not a helpful one. As long as you don’t try to println(c), there isn’t a hastle – looking at the default print of a color is confusing, because Java’s default …

Or try playing with this sketch:

/**
 * InspectColorBinary
 * 2020-04 Jeremy Douglass - Processing 3.4
 *
 * Use the Processing built-in function binary()
 * to inspect bits in a color. Colors are stored as ints.
 * All values are AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB
 *
 * See:
 * -  https://processing.org/reference/color_datatype.html
 * -  https://processing.org/reference/binary_.html
 */

int c;

void setup() {
  println("AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB\n");

  // RGB
  inspectColor( color(0, 0, 0) );
  inspectColor( color(255, 0, 0) );
  inspectColor( color(0, 255, 0) );
  inspectColor( color(0, 0, 255) );
  inspectColor( color(255, 85, 255) );
  println();
  
  // plus alpha
  inspectColor( color(0, 255, 0, 85) );
  println();
  
  // created with HSB mode
  // -- int still stores AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB
  colorMode(HSB);
  inspectColor( color(0, 255, 255) );
  inspectColor( color(127, 255, 255) );
  inspectColor( color(0, 0, 255) );
  inspectColor( color(0, 0, 255, 10) );
}

void inspectColor (int c) {
  print(binary(c), c, "\n");
}

Output:

AAAAAAAARRRRRRRRGGGGGGGGBBBBBBBB

11111111000000000000000000000000 -16777216 
11111111111111110000000000000000 -65536 
11111111000000001111111100000000 -16711936 
11111111000000000000000011111111 -16776961 
11111111111111110101010111111111 -43521 

01010101000000001111111100000000 1426128640 

11111111111111110000000000000000 -65536 
11111111000000001111111111111011 -16711685 
11111111111111111111111111111111 -1 
00001010111111111111111111111111 184549375 

The binary numbers on the left show you what is going on with the bits, and where the A, R, G, B are stored.

The numbers on the right… don’t really mean anything. They are technically what happens if you combine the color information using this equation:

B + (G * 256) + (R * 65536) + (A * 16777216)

… and then if A>127 multiply everything by -1.

There are a number of other ways we could describe this, using powers of 2
or bit shifting.

But that doesn’t help explain what is actually happening. What is actually happening is you take your A, R, G, B and arrange the bits next to each other in an int, like this:

AAAAAAAA RRRRRRRR GGGGGGGG BBBBBBBB

And those bits are what the int “means” as a color – they act like four different variables, saved in one object. There is no such thing as a negative color, in this model – only different amounts of RGB and alpha. It also doesn’t mean anything to add, multiple, or divide the int as an int – it is really four bands of bits, so if you add one, lots of blue can suddenly become a little green for no reason. Again, it isn’t useful to think of it as “a number” – that isn’t what it represents.

[Pisicandru]

Hi Jeremy,

That really helps, especially the equation you provided which i re-wrote as:
(A256^3)+(R256^2)+(G*256)+B with proviso if A>127 then multiply by -1

This gives me a transformation from 4 dimensions to 1 dimension even if the numbers are meaningless. The idea is that if the transformation is unique (one hopes) then each number will give only 1 unique color expressed as A,R,G,B.

When working in n-dimensions we always try to reduce the dimensions to something we can understand, and hopefully visualize, keeping as much of the information as possible. Mostly we can visualize things up to 3 dimensions in Cartesian coordinates.

Sorting in n-dimensions is problematic at best, because the end result depends on how the sorting is done. Only if we use real numbers in 1-dimension we can have a unique and unambiguous sorting if no number repeats itself. In this situation we know with certainty which number is higher and which is lower. Using color to look at this problem is nice because it lends to obvious visualization, some of which is very surprising.

Again thanks for your quick answer, i really appreciate it,
Monica

[jeremydouglass]

@Pisicandru

When working in n-dimensions

Ah, I think I see what you are doing. Are you trying to map n-dimensional coordinates to unique Processing colors?

Can you give an example or examples of N? Is n usually 4, 5, 6, or is n sometimes 20, 50, 200?

Also, what kind of coordinate range?

An int (the base color representation in Processing) is 16 bits (4 bytes) –

-2,147,483,648 to 2,147,483,647 (4,294,967,295 unique coordinates). For two dimensions each axis can have up 0-65535 range. For four dimensions, 0-256 range (this is RGBA). For eight dimensions you only have two bits per dimension, so 0-2 range on each, and for 16, each dimension is 1 or 0. Other dimension counts don’t fit cleanly into 16 bits.

[jeremydouglass]

Just realized this was all on a year-old post from someone else – splitting.

[Chrisir]

I assume that your goal is N-dimensional sorting and that the color thing is only a metaphor or a bridge to find a solution. Because with colors it works.

Maybe you got weather data with 7 Dimensions you want to sort?

[jeremydouglass]

Ah. If sorting properties of multidimensional data in general is the topic, you might also be interested in this thread…

Generative floor plans with Permutation algorithm

Dear all, I would need your help to implement a permutation algorithm allowing the generation of building plans, that I’ve recently stumbled on while reading Professor Kostas Terzidis’ latest publication: Permutation Design: Buildings, Texts and Contexts (2014). CONTEXT Consider a site (b) that is divided into a grid system (a). Let’s also consider a list of spaces to be placed within the limits of the site ( c ) and an adjacency matrix to determine the placement conditions and neighboring …

[Pisicandru]

Hi,

For now i am thinking in a more abstract way, but certainly there are lots of multidimensional data out there, from multi-spectral satellite data, to more “normal” satellite data with 4, 8 or 16 bands, weather or climate data, geochemical data, pollution, etc. There are also pretty well (and not so well) established ways to decrease the dimensionality of the data. All of them try in the end to keep as much information as previously but in less dimensions, if possible. And lot’s of time we end up sorting that data, and putting it in some categories of sorts, that can be sorted themselves. Think about low, medium and high categories, for example.

So, since i have some time and i am stuck at home like so many others unfortunately, i started to think about what is the “influence” of our sorting decision on our data. One way to think about that, in a more abstract way, is to look at data in 3 or 4 dimensions, and color came to mind since it is readily available (lots of pics on the internet), lends itself to visualization, and lots of people are familiar with it.

So, how many ways can we do it? Well, the obvious choice is by R, or G, or B, or H, or S or V, or luminescence, by some statistics of the values we have (sum, mean, median, whatever), some other type of transformation (for example that blackValue i was asking about), some type of distance, similarity / dissimilarity, some type of “packing” curve like Hilbert curve, principal or independent component, whatever - and the list can do on and on and on. Of course one chooses what to sort from the data depending on the end purpose, but sometime this is not a unique relationship.

And this begs the question, how different is the result when using the same data? Well, until now i used about 10 different ways to sort the colors in an image, and got 10 different results. Now i am ready to try more “esoteric” ways to aggregate data and sort it. And i am getting very interesting results. Most of the work i am doing is in the statistical language R because this is what i know the best (i am a beginner with processing). You guys do amazing work in processing manipulating images, so it was an obvious stop for me to see what i can learn from the examples here, discussion on the forum, code, etc. Besides it is always fun to run code and see the results.

I am now ready to read the post about floor plans and the permutation algorithm , thanks for the suggestion.

Thanks for indulging me, i really appreciate it,

Monica

[jeremydouglass]

If you like R – you might also try Processing.R mode so that you can manipulate your high-dimensional data using familiar matrices and syntax but render it with the Processing API.

processing-r/Processing.R

There are also color modes and libraries for different color spaces, if you are interested in using hue or perceptual color rather than RGB.

[Chrisir]

I wonder about the famous comparator class

If I had a Adress field I would sort by last name, then by first name, then street name, then house number

No need to unify them to a long number like color?

Possible?

[Pisicandru]

Hi,

Jeremy, thanks for the Processing.R, i definitely will look into it. But having time on my hands i will try to learn a little bit of Processing as well, although for a long while i will still be tempted to try it first in R

Chrisir, i am not sure i understand your question. The comparator class is what i would call a “simple” sorting where 1st you sort after x, 2nd after y, … and so on, and for the same values of x in the sorting sequence, y is itself sorted, and so on it trickles down … This to me is interesting only in which dimension i decide to sort 1st, in other words which is my x? If you want to play, try sorting the pixels of an image by R only, and after G or B only - your results will be slightly different …

As i said before i play with colors because the internet is full of photos, everybody understands that color is at least 3d, and very different people with very different skills are interested in this (or not ;-))
So i don’t necessarily want to translate a n-dimensional problem in RGB for example, i am rather using the RGB as an example of a “simple” n-dimensional problem. Besides any n-dimensional numerical dataset (and not categorical) can be reduce to 3 dimensions for example by principal component or independent component analysis, or some other statistical method. And if i so choose, i can map these 3 dimensions to colors to visualize … or whatever. Does that make sense?

Now, can i transform your name and address database into colors? Probably you can come up with some type of algorithm to transform alphanumeric to numeric and numeric on a scale from 0 to 255. In your example you have 4 diff. vars, so you can decide which 3 are your RGB and the 4th could be alpha for example. Map this in a matrix and see what image you get. Sort this image (probably 1st will look like some color noise) and decompose it back to your name and address and see in which order you have now the data. I never did that, but if you have the time to try it, i would be interested to see the results.

Thanks,
Monica

[Pisicandru]

And … Hi again,

I will try to share at least 2 or my "play"results in sorting color …

I decided to sort the pixels using a Hilbert curve which very neatly not only can go through each pixel, but actually decomposes a 2D matrix in 1D. My next trick will be to do a 3D Hilbert curve, but that later.

Anyway in this case i used not only the RGB of the image but the location of the pixels as a kind of coordinates / position of the pixel in the image of form (1,1) or (x, y) meaning row x, column y.

I used the Hilbert curve in 2 ways:
a: traverse all pixels in the image with 1 Hilbert curve
b: sort the pixels in column by column so the Hilbert curve goes only down a column.

And now my results: (all coding done in R) Anybody ready to translate it on Processing?
Original Image (Majuro Atoll, RMI)

Hilbert sorting of all pixels:

Hilbert sorting by column only:

Enjoy,
Monica

[jeremydouglass]

@Pisicandru

And now my results: (all coding done in R) Anybody ready to translate it on Processing?

Great! Maybe start by posting your R code?

If you post your R then we can see what changes are required to run it in R mode – or Java mode.

Another potential output is to unwind your output pixels from the center of the image using a box / diamond / circle path.

[Pisicandru]

Hi Jeremy,

That spiral decomposition was a mind pretzel …

Anyway - i did in the end a pseudo-code in R in the sense that it works only on square matrices for now, and distinguishes between odd or even number of rows / columns. I am not sure if you ever did it and know what should be the expected result …

I decided the code should give me only the coordinates on the cells in a matrix of n x n starting from the top left and going clockwise. After you can add an index as a 3rd column either from 1 to number of rows of the result (a data.frame in R) or reverse if you want to have the 1 cell the middle of the matrix instead of the top left.

My code in R is this (and not the most elegant one either):

spiral.decomp <- function(n){
require(pracma)
# for a square matrix at least 3x3, n is nr.rows=nr.cols
new <- data.frame()
n1 <- ceil(n/2)
if(mod(n, 2)==1){
for (i in 1:(n1-1)){
b1 <- seq(i, (n-i))
a1 <- rep(i, length(b1))
a2 <- seq(i, (n-i))
b2 <- rep((n-i+1), length(a2))
b3<- seq((n-i+1),(i+1))
a3 <- rep((n-i+1), length(b3))
a4 <- seq((n-i+1), (i+1))
b4 <- rep(i, length(a4))
m1 <- data.frame(a=c(a1, a2, a3, a4), b=c(b1, b2, b3, b4))
new <- rbind(new, m1)
} 
i<- n1
a1 <- i
b1 <- i
m1 <- data.frame(a=a1, b=b1)
new <- rbind(new, m1)
} else {
for (i in 1:n1){
b1 <- seq(i, (n-i))
a1 <- rep(i, length(b1))
a2 <- seq(i, (n-i))
b2 <- rep((n-i+1), length(a2))
b3<- seq((n-i+1),(i+1))
a3 <- rep((n-i+1), length(b3))
a4 <- seq((n-i+1), (i+1))
b4 <- rep(i, length(a4))
m1 <- data.frame(a=c(a1, a2, a3, a4), b=c(b1, b2, b3, b4))
new <- rbind(new, m1)
} 
}
return(new)
}

And now results - not what i expected
Doing the spiral on the whole image

And doing the spiral for only 1 column and repeat that pattern on all the other columns

Thanks,
Monica

[jeremydouglass]

Beautiful examples.

@Pisicandru

cells in a matrix of n x n starting from the top left and going clockwise

This mapping / reversal makes sense to me – although I personally find it easier to conceptualize winding out rather than winding in.

Here is an example of an approach using a little turtle called a Winder, wrapped in a Java mode demo sketch.

It is verbose, but it is robust across square and rectangular inputs of any size – it doesn’t need to special case odd or even columns counts.

When you do the spiral, you are using it to read. Another option is to read something in scanlines, or sort it and read it in sorted order, then use the spiral to write. (center examples in image).

/**
 * PixelWinder
 * 2020-04-15 Jeremy Douglass - Processing 3.4 
 *
 * Load an image, then use a Winder to map its
 * pixels onto a new image. A Winder is a small
 * turtle state machine that starts at the center
 * of an image and walks its pixels outward in a
 * counter-clockwise box-spiral.
 *
 * The top row shows reading scanlines and
 * writing in a box-spiral, then reading in a
 * box-spiral and writing scanlines.
 *
 * The second row shows the image sorted by hue,
 * then the same two transformations.
 */
 
PImage img;

void settings() {
  //img = loadImage("https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Lange-MigrantMother02.jpg/185px-Lange-MigrantMother02.jpg");
  //img = loadImage("https://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Processing_3_logo.png/240px-Processing_3_logo.png");
  img = loadImage("https://upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Sunset_-_Majuro.jpg/320px-Sunset_-_Majuro.jpg");
  size(img.width*3, img.height*2);
}
void setup() {
  background(255, 0, 0);
  image(img, 0, 0);
  image(scanToWind(img), img.width, 0);
  image(windToScan(img), img.width*2, 0);
  
  // sort the input image
  PImage sorted = imgSort(img);
  image(sorted, 0, img.height);
  image(scanToWind(sorted), img.width, img.height);
  image(windToScan(sorted), img.width*2, img.height);
  
  saveFrame("PixelWinder--screenshot.png");
}

PImage scanToWind(PImage img) {
  PGraphics out = createGraphics(img.width, img.height);
  Winder st = new Winder(img.width, img.height);
  int pidx = 0;
  img.loadPixels();
  out.beginDraw();
  while (st.bound()) {
    out.set(st.x, st.y, img.pixels[pidx]);
    st.step();
    pidx++;
  }
  out.endDraw();
  return out;
}

PImage windToScan(PImage img) {
  PGraphics out = createGraphics(img.width, img.height);
  Winder st = new Winder(img.width, img.height);
  int pidx = 0;
  img.loadPixels();
  out.beginDraw();
  out.loadPixels();
  while (st.bound()) {
    out.pixels[pidx] = img.get(st.x, st.y);
    st.step();
    pidx++;
  }
  out.updatePixels();
  out.endDraw();
  return out;
}

PImage imgSort(PImage img) {
  // see Daniel Shiffman, CC_047_PixelSorting
  PImage sorted = img.get();
  sorted.loadPixels();
  for (int i = 0; i < sorted.pixels.length; i++) {
    float record = -1;
    int selectedPixel = i;
    for (int j = i; j < sorted.pixels.length; j++) {
      color pix = sorted.pixels[j];
      float b = brightness(pix);
      if (b > record) {
        selectedPixel = j;
        record = b;
      }
    }
    color temp = sorted.pixels[i];
    sorted.pixels[i] = sorted.pixels[selectedPixel];
    sorted.pixels[selectedPixel] = temp;
  }
  sorted.updatePixels();
  return sorted;
}

class Winder {
  int x, y, w, h, dir, dist, wrun, hrun;
  Winder(int w, int h) {
    this.w=w;
    this.h=h;
    dir=0;
    dist=0;
    // find starting center and run lengths
    if (w>h) {
      x = w/2-(w-h)/2-1;
      y = h/2;
      wrun=w-h+1;
      hrun=0;
    } else {
      x = w/2;
      y = h/2+(h-w)/2;
      wrun=0;
      hrun=h-w;
    }
  }
  boolean bound() {
    return (x>=0 && x<w && y>=0 && y<h);
  }
  void step() {
    if (dir==0 || dir==2) {
      if (dist==wrun) {
        dir = (dir+1)%4;
        dist=0;
        hrun+=1;
      }
    }
    if (dir==1 || dir==3) {
      if (dist==hrun) {
        dir = (dir+1)%4;
        dist=0;
        wrun+=1;
      }
    }
    if (dir==0) x+=1;
    if (dir==1) y-=1;
    if (dir==2) x-=1;
    if (dir==3) y+=1;
    dist+=1;
  }
}

[Pisicandru]

Hi Jeremy,

I will need to see if i can understand the code you provided - i know even less java than processing. Anyway - at least even with my partial code i got more or less the results you show in the 3rd column, but for the life of me i cannot understand what you did to get the results in the second column.

If you have time, can you explain that in words? I want to see if i can reproduce that effect in R. Definitely, R is not the right tool to manipulate images, but i definitely learn quite a bit about different kinds of sorting in R playing with all of that. This should give me a push to learn processing since it seems it is more geared towards image manipulation.

Thanks,
Monica

[jeremydouglass]

@jeremydouglass

out.pixels[pidx] = img.get(st.x, st.y);

windToScan (column 3) does what you are doing – wind around the source, and write the pixels one at a time into the destination, like a scanline (0, 1, 2, 3…).

@jeremydouglass

out.set(st.x, st.y, img.pixels[pidx]);

scanToWind (column 2) does the opposite – walk across the source like a scanline (0, 1, 2, 3…), and wind around the destination to write out the pixels.

In both case, the class being used is generating an identical winding mapping sequence, like this:

50,50
51,50
51,49
50,49
49,49

But in one case, you are copying source(50,50) → dest[0] – which in the pixels array is at coordinate (0,0). In the other, you are copying source[0] to dest(50,50).

p.s. this is Processing – by Java mode, I only meant that it is the Java-dialect of Processing, not Processing.R. or processing.py, or p5.js etc.

[Pisicandru]

Hi,

Thanks that helps. But i definitely need to do a spiral decomposition that will take any n x m matrix, and not only a n x n matrix. As you imagine i am still working in R.

Anyway, using a n x n matrix i ended up with this result:

Not too bad, but not quite there, either

Thanks,
Monica

[jeremydouglass]

I find an n x m easier to think about when you first identify the center and then wind out.

For a square, the Winder mapper steps “forward” and advances in this pattern: step 1 pixel, then turn, step 1, then turn, step 2, then turn …

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6…

but for a rectangle, the innermost wind must be a difference between the width and the height (w-h, or h-w). Put another way, if you stretch the square by w+50, then that stretch is incorporated as w-h, like this:

1+50, 1, 2+50, 2, 3+50, 3, 4+50, 4, 5+50, 5, 6+50, 6…

Or if you stretch any square by height+100, then the stretch is incorporated as h-w, like this:

1, 1+100, 2, 2+100, 3, 3+100, 4, 4+100, 5, 5+100, 6, 6+100…

You can see these values defined as wrun and hrun, here:

    if (w>h) {
      x = w/2-(w-h)/2-1;
      y = h/2;
      wrun=w-h+1;
      hrun=0;
    } else {
      x = w/2;
      y = h/2+(h-w)/2;
      wrun=0;
      hrun=h-w;
    }

That is how Winder is able to return a correct rectangular mapping given only the width and height of the image, and no other information.

Also note that the “center” is also no longer the center. it is offset by half the difference in edge length. For example, if the image is 50 pixels higher than wide, the initial center position is 25 pixels higher.

x = w/2;
y = h/2+(h-w)/2;

[Pisicandru]

Hi,

What you say it makes perfect sense - only that i was thinking in those terms … oh well. I saw your answer after i actually fixed my own code to do the spiral. And now works well with any n x m matrix.

here it is the results, FINALY

and here it is my spiral code - evidently in R:

spiral1.decomp <- function(r1, c1){
require(pracma)
# for any matrix, with no. rows r1 > 3, and no.cols c1 >3
new <- data.frame()
if(r1<=c1) n1 <- ceil(r1/2) else n1 <- ceil(c1/2)
if(r1<= c1 & mod(r1, 2)==1 | r1 > c1 & mod(c1,2)==1){
for (i in 1:(n1-1)){
yc1 <- seq(i, (c1-i))
xr1 <- rep(i, length(yc1))
xr2 <- seq(i, (r1-i))
yc2 <- rep((c1-i+1), length(xr2))
yc3<- seq((c1-i+1),(i+1))
xr3 <- rep((r1-i+1), length(yc3))
xr4 <- seq((r1-i+1), (i+1))
yc4 <- rep(i, length(xr4))
m1 <- data.frame(xr=c(xr1, xr2, xr3, xr4), yc=c(yc1, yc2, yc3, yc4))
new <- rbind(new, m1)
} 
i<- n1
if(r1<=c1){
if (c1-n1!=1) yc1 <- seq(i, c1-1) else yc1 <- i
xr1 <- rep(i, length(yc1))
} else {
if(r1-n1!=1) xr1 <- seq(i, r1-1) else xr1 <- i
yc1 <- rep(i, length(xr1))
}
m1 <- data.frame(xr=xr1, yc=yc1)
new <- rbind(new, m1)
} else {
for (i in 1:n1){
yc1 <- seq(i, (c1-i))
xr1 <- rep(i, length(yc1))
xr2 <- seq(i, (r1-i))
yc2 <- rep((c1-i+1), length(xr2))
yc3<- seq((c1-i+1),(i+1))
xr3 <- rep((r1-i+1), length(yc3))
xr4 <- seq((r1-i+1), (i+1))
yc4 <- rep(i, length(xr4))
m1 <- data.frame(xr=c(xr1, xr2, xr3, xr4), yc=c(yc1, yc2, yc3, yc4))
new <- rbind(new, m1)
} 
}
return(new)
}

Not the most elegant code, or fast, but it definitely works, which is what i asked up to now. Thanks for sending me the spiral challenge, i saw code on the internet for it in python and C++ and so on, but none in R, so at least i am happy i was able to do it in the end. I am sure it can be done better in R though.

Thanks,
Monica