Pixel Sorting

lighthouse

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.

pluto

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.

Before

lighthouse
After

lighthouse sorted1

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;
}

lighthouse sorted vertically 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);
          }
          newRow.addAll(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:

Horizontal

lighthouse sorted3
Vertical

lighthouse sorted4

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);
          }
          newRow.addAll(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:

lighthouse sorted horizontally with variable sort intervals

lighthouse sorted horizontally with variable sort intervals

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.

lighthouse sorted horizontally with variable sort intervals This one was sorted with a maxNumberOfIntervals of 500.

Published 3 Nov 2019

Tech tips, Taylor made for you! :)
Will Taylor on Twitter