Pixel sorting - Introduction to glitch art

The beginning

Everything can be sorted in some way. From integers and characters to most ambiguous things. The only necessary thing is a comparable (in some way) key. In this article, I will focus on sorting something that’s not quite ordinary, I’m going to sort pixels. Now, you may ask, why would anybody sort pixels? Well, the answer is quite simple. Sorting pixels can produce magnificent effects called glitch art or databending. You see, when you take an ordinary image and rearrange the pixels in some kind of linear order, you get interesting results. For example, take a look at the transformation below.

The first image is, you’ve guessed it, the original one, and the second one is sorted by green color values.

How the heck can you even sort pixels?

Each pixel is just an object represented by a 32-bit integer that can be split into four 8-bit integers. First 24 bits represent the RGB color values and the last 8 bits contain the alpha value that determines pixel’s transparency. Each of the three core colors is represented by an 8-bit unsigned integer (ranges from 0 to 255). Simple combinatorics tell us that there are about 16 million (2^24) possible color combinations for each pixel separately. Using this values pixels can be sorted by their core colors, red, green, and blue or by their alpha value. Of course, they can also be sorted by multiple keys.

Since we are sorting pixels in a given image, and since image is basically just a matrix, we can sort the matrix horizontally and vertically. Diagonal sorting is also possible, but only on square matrices and it shall not be covered by this article.

The actual sorting

For the actual pixel sorting, I am going to use a sorting algorithm called radix sort. Why radix you may ask? In theory, radix sort is one of the fastest currently known sorting algorithms. It’s worst case asymptotic complexity is O(kn), where n represents number of elements in the array that will be sorted (number of pixels in a line in this case), and k represents the number of bits used to represent the number. I’m not going to go in detail how radix sort works, since that’s not the point of this article. Since I’m saving RGB values as bytes, k will be just 8. That gives us an almost linear sorting algorithm even in the worst case scenario.

The algorithm(s)

All of the code snippets below are written in Java and are a part of open-source project PxlSort. The whole code and project can be freely accessed at my github repository.

Loading the image

For keeping images in memory, I’m going to use a standard Java structure called BufferedImage. It’s perfect for sorting because of the following two methods:

		int getRGB(int x, int y); /* returns the 32-bit integer representation of a pixel at x, y */
		void setRGB(int x, int y, int rgb); /* sets 32-bit RGB value to the pixel at x, y */
Determining core color values is quite simple.
		getRGB(x, y) & 0x00ff0000 >> 16; /* returns the first 8-bit value - red color */
		getRGB(x, y) & 0x0000ff00 >> 8; /* returns the second 8-bit value - green color */
		getRGB(x, y) & 0x000000ff;  /* returns the third 8-bit value - blue color */
Now that the image is in memory we can get onto sorting it’s pixels.

The sorting

First off, we need a method that will run the sorting algorithm across all lines (whether horizontal or vertical).

public void sort(int dir, int by) {
	this.dir = dir;
	this.by = by;

	int lim = (this.dir == 2 ? image.getHeight() : image.getWidth());

	for(int i = 0; i < lim; i++) 
		radix(i);		
}

Now for the actual sorting algorithm.

public void radix(int t) {
	int h = (dir == 2 ? image.getWidth() : image.getHeight());

	for (int s = Byte.SIZE - 1; s > -1; s--) {
		byte tmp[] = new byte[h];
		int indices[] = new int[h];

		int j = 0;	

		for (int i = 0; i < h; i++) {
			byte value;

			if(by == 1)
				value = (byte) (((dir == 1 ? image.getRGB(t, i) : image.getRGB(i, t)) & 0x00ff0000) >> 16 - 128);
			else if(by == 2)
				value = (byte) (((dir == 1 ? image.getRGB(t, i) : image.getRGB(i, t)) & 0x0000ff00) >> 8 - 128);
			else 
				value = (byte) (((dir == 1 ? image.getRGB(t, i) : image.getRGB(i, t)) & 0x000000ff) - 128);

			boolean move = value << s >= 0;

			if (s == 0 ? !move : move) {
				indices[j] = (dir == 1 ? image.getRGB(t, i) : image.getRGB(i, t));
				tmp[j++] = value;
			} else {
				if(dir == 1)
					image.setRGB(t, i-j, image.getRGB(t, i));
				else if(dir == 2)
					image.setRGB(i-j, t, image.getRGB(i, t));
				}
			}
		}

		for (int i = j; i < tmp.length; i++) {
			if(by == 1)
				tmp[j] = (byte) (((dir == 1 ? image.getRGB(t, i-j) : image.getRGB(i-j, t)) & 0x00ff0000) >> 16 - 128);
			else if(by == 2)
				tmp[j] = (byte) (((dir == 1 ? image.getRGB(t, i-j) : image.getRGB(i-j, t)) & 0x0000ff00) >> 8 - 128);
			else 
				tmp[j] = (byte) (((dir == 1 ? image.getRGB(t, i-j) : image.getRGB(i-j, t)) & 0x000000ff) - 128);

			indices[i] = (dir == 1 ? image.getRGB(t, i-j) : image.getRGB(i-j, t));	        
		} 	


		for(int i = 0; i < tmp.length; i++) {
			if(dir == 1) 
				image.setRGB(t, i, indices[i]);
			else if(dir == 2)
				image.setRGB(i, t, indices[i]);
		}
	}
}
    

The code may look a lil’ bit confusing, but it’s just a standard implementation of radix sort applied on pixels using the keys described above.