# Pixel Sorting

Like many dangerous things one comes across on the internet, I stumbled upon pixel sorting on a late evening Reddit session. A post from the pixel sorting subreddit bubbled up to the top of my news feed and grabbed hold of my attention. The site was full of corrupt images, real pictures taken with a camera that looked like they were recovered from a fatally corrupted hard drive. Take a look at a few of them below.

I was hooked. It didn’t take long for the programmer in me to cry out “I bet I could do this!“. Surely it couldn’t be that hard, right? I cracked open my IDE and got to work. Here’s how I got it done.

## Breaking Down the Problem

Basic pixel sorting is pretty straightforward. To perform the most basic pixel sort, we need to:

1. Break down an image into a matrix of pixels
2. Sort each row or column of the matrix by the color value of the pixels

It’s that simple! Once we get this down, we can make things a bit fancier to achieve what we see in the images at the top of the post.

## Sorting Some Pixels

Let’s write some code! The Java method below takes in a `PixelBuffer` object, which is a wrapper around a 2 dimensional list of pixels. The function then iterates through and sorts each row of the pixel buffer and returns the sorted buffer!

``````public PixelBuffer sortImageHorizontally(PixelBuffer pixelBuffer){

// Iterate through each row in the buffer
for(int y = 0; y < pixelBuffer.getHeight(); y++){
List<Integer> row = pixelBuffer.getRow(y);  // Get the row
row.sort(Comparator.naturalOrder());        // Sort the row
pixelBuffer.setRow(y, row);       // Persist the sorted row
}

return pixelBuffer;
}``````

So, we’re finally ready to do some pixel sorting! Let’s try it out on this picture of a lighthouse.

Pretty neat, huh? We can see that each row has been sorted by the pixel’s color from darkest to lightest. With this alone, we can get some pretty impressive results. We can modify our code easily from here to sort the image vertically by columns as well.

``````public PixelBuffer sortImageVertically(PixelBuffer pixelMatrix, boolean reverseOrder){

// Iterate & sort the columns instead of the rows
for(int x = 0; x < pixelMatrix.getWidth(); x++){
List<Integer> column = pixelMatrix.getColumn(x);
column.sort(Comparator.naturalOrder());
// Reverse the column to prevent it from being upside-down
Collections.reverse(column);
pixelMatrix.setColumn(x, column);
}

return pixelMatrix;
}`````` Sorting images vertically can produce some astounding pictures too!

What we have so far looks impressive, but can’t we take it a little further? After all, this doesn’t quite look like the pictures at the top of this page…

## Introducing Sort Intervals!

Let’s make things more interesting. What if instead of sorting an entire row at one time, we instead sorted parts of a row at a time? This could give us a more interesting picture!

``````public PixelBuffer sortImageHorizontally(
PixelBuffer pixelBuffer,
int numberOfIntervals,
boolean reverseOrder
) {
// Determine the width of each interval
int intervalWidth = pixelBuffer.getWidth() / numberOfIntervals;

// Iterate through the rows
for(int y = 0; y < pixelBuffer.getHeight(); y++){
List<Integer> row = pixelBuffer.getRow(y);
List<Integer> newRow = new ArrayList<>();

// Iterate through the intervals
for(int i = 0; i < pixelBuffer.getWidth(); i = i + intervalWidth){
// Ensure that we don't sort pixels that are not in the image
int stoppingPoint = Math.min(i + intervalWidth, pixelBuffer.getWidth());

// Get the sub interval from the row
List<Integer> sortingInterval = row.subList(i, stoppingPoint);

// Perform the sort
sortingInterval.sort(Comparator.naturalOrder());

// Reverse the order if needed
if(reverseOrder){
Collections.reverse(sortingInterval);
}
}

pixelBuffer.setRow(y, newRow);
}

return pixelBuffer;
}``````

Adding this extra `for` loop to our algorithm raises the time complexity by a considerable amount, but the results speak for themselves:

## Pushing It Further: Variable Width Sort Intervals

Let’s see how far we can take this! What if we could make the picture more interesting by adding in some more variance to it? The pictures above are a little too predictable, aren’t they? Why not give each row a different number of sorting intervals? While we’re at it, let’s give the intervals a random width instead of the constant width they already have!

``````public PixelBuffer sortImageHorizontally(
PixelBuffer pixelBuffer,
boolean randomIntervals,
int maxNumberOfIntervals,
int numberOfIntervals,
boolean reverseOrder
){
for(int y = 0; y < pixelBuffer.getHeight(); y++){
List<Integer> row = pixelBuffer.getRow(y);
List<Integer> newRow = new ArrayList<>();

// Determine the width of each interval. This can be static or
// dynamic
int intervalWidth;
if(randomIntervals){
int dynamicNumberOfIntervals = (int) (Math.random() * maxNumberOfIntervals + 1);
intervalWidth = pixelBuffer.getWidth() / dynamicNumberOfIntervals;
} else {
intervalWidth = pixelBuffer.getWidth() / numberOfIntervals;
}

// Iterate through the intervals
for(int i = 0; i < pixelBuffer.getWidth(); i = i + intervalWidth){
// Ensure that we don't sort pixels that are not in the image
int stoppingPoint = Math.min(i + intervalWidth, pixelBuffer.getWidth());

// Get the sub interval from the row
List<Integer> sortingInterval = row.subList(i, stoppingPoint);

// Perform the sort
sortingInterval.sort(Comparator.naturalOrder());

// Reverse the order if needed
if(reverseOrder){
Collections.reverse(sortingInterval);
}
}

pixelBuffer.setRow(y, newRow);
}

return pixelBuffer;
}``````

Whew!! Our code is getting to be pretty long, isn’t it? Despite the length, the results from this algorithm are absolutely stunning. Check it out:

The greater the value of the `maxNumberOfIntervals` input variable is, the smaller the individual intervals are, and thus the more like the sorted image will look more like the original image. This one was sorted with a `maxNumberOfIntervals` of 500.

Published 3 Nov 2019

Tech tips, Taylor made for you! :)