The dog cutting algorithm — From art to encryption. Part I
Understanding the magic behind a simple algorithm and what the images it can produce
Do not be alarmed by the dog cutting part! It is the colloquial name I call a bitmap manipulation algorithm I saw performed on an image of a dog shown in a Youtube video from artist Kensuke Koike. The video was posted on Reddit and I kept thinking that the algorithm behind it was an easy thing to code. I attempted to code the algorithm and after an embarrassingly long time, I had managed to do it using python Pillow. Take a look at the video:
The algorithm is pretty simple:
- Slice the image in P amount of vertical slices
- Separate every other slice to join them in 2 groups and then recreate the image side by side.
- Finally, slice the image again by Q amount of horizontal slices, join the two groups again and you have a modified image.
In the original video, the amount of both vertical and horizontal slices depends on the width and height of the image and the paper shredder. I coded the algorithm and made it so I could change the amount of vertical and horizontal slices. Happy with the result I tried it with an image I had of myself, and well…
It kind of worked but something seems off. There are vertical white lines of different width. Some of you may have figured it out already: the width is not divisible by the number of slices. If you take the width of the image, say it is 200px wide and you divided by 6, the division is not exact and you can’t have 1/3 of a pixel. The width and height have to be divisible by the number of slices you set.
After fixing the slices to a number that had exact division, I played around a little more and after some funny images, I thought I was done. I then got the idea of publishing on Reddit to show my work, but someone had already done it in the comments. Nonetheless, something piqued my interest, another Redditor had experimented a little by applying the algorithm to an image of Lenna. The Redditor had sliced the image multiple times, each time changing the number of vertical and horizontal slices. The results were very interesting!
The images also had an important characteristic, their width and height are the same and it is equal to a power of 2. In addition, interesting results appeared when applying the algorithm to the image where the width and height are equal to a power of 2 and also where the number of vertical and horizontal slices is equal and a power of 2 as well. Therefore:
w (width) = h (height) = 2^n where w and h are the width and height in pixels of an image, but also:
The image was sliced in 2^m slices where m ≤ n and m ≥ 2.
Here is where it gets interesting. Let’s first define what a pass is.
Pass: A pass consists of applying the image slicing algorithm once to an image. The image can be sliced in P vertical and Q horizontal slices. Since we are exploring applying passes to an image where the image has the same width and height and it is equal to a power of 2, let’s make P and Q equal as well. Example: an 8 pass means you are applying the image slicing algorithm to an image where it is sliced in 8 vertical and then 8 horizontal slices.
The Apple Experiments
I took an image of a nice apple I found on Google and began playing around with the algorithm performing different sizes of passes. The results, at least for me, look incredible:
Four groups of “apples” seem to form and if you are keen on the image progression, it seems as if the bottom right corner image begins to show 4 “pixelated” apples. The trick here is that the size of the pass is increasing. First image: size 4 pass, second image: size 8 pass, third image: size 16 pass, last image: size 32 pass. The sequence progression is clear as well: the size of the pass is a 2^n number and on each image, we increase n in 1 with n starting at 2.
The original apple image has a width and height of 2048 pixels (2¹¹), so what happens if we try out a pass with the biggest possible size? We get this image:
We get four clear and distinct apples. These are not copied and pasted and scaled-down. These apples are the same apple. You might be thinking about this phrase and it might not make sense but the individual pixels of the original image have been split into four groups and rearranged by the algorithm into four versions of the original apple but they are all different in an atomic level.
Concatenation of Passes
We’ve now seen how you can perform different size passes on the original apple image to get an increasingly less pixelated image of four apples. But what happens if we concatenate passes? And by concatenation, I mean applying an N size pass to an image and later taking the resulting image and performing a second pass. For example, we can perform an 8 size pass followed by another 8 size pass. Let’s look at this particular concatenation:
Wow! It looks as if the image has imploded, you can clearly see how parts of the stem, leaves, and trunk line up but not quite. We made an 8 size pass followed by another 8 size pass. Still, this is a bit long to write every single time so we can write it down as a simple sequence of numbers, therefore this was an 8,8 sequence. Much simpler right?
Therefore, a sequence is a list of numbers where each step is that number sized pass. Let’s try sequences where the step size is not always the same number, what about 8,8,4? Let’s see how it looks:
Let there be art
Pretty cool! With this new “feature” discovered, let’s get wild. Let’s try different sized sequences with different sized steps. Take a look at 4 different sequences:
Outstanding images! Right? I fail to understand and believe that an image like the top right image is possible. A single apple lies in the center and to each quadrant of the image a small part of the apple is repeated and radiated outwards. The bottom right image is amazing as well. It looks like a pixelated apple as well but each square has its own grid. The entire image has been reduced almost to a small number of colors. And here is where I went wild, testing multiple sequences, of different lengths and step sizes, as well as implementing code so that I could generate random sequences of any size trying to find the perfect images.
Looking at many of these images, I began to wonder, is this art? Some of the images are aesthetically pleasing but this is work generated from an algorithm. There are millions of combinations of the pixels from the original apple that could result in a multitude of images that appeal to us. Is each image produced from a sequence, art? While I cannot answer that question I will leave you with one last image for now. I produced this image from a sequence I never wrote down and that attempting to find it is possibly exceedingly complex. For me, the next image is art. I have spent many hours marveling at the way the colors of the image blend, the way the grid sections of the image weave fine threads of pixels. It is the image at the top of the article and my favorite image.
In the next part, I will write about a new concept because there’s more! We’ve now understood the concept of a pass, a sequence of passes and the images it can produce but this topic leads down into a deeper rabbit hole that I would have never thought of. We will talk about image restoration, encryption, powers higher than 2, image compression, and a complex math problem. I also left out many characteristics of sequences I observed that I will leave here as short questions so that you can think about them:
- There are four apples on simple sequences, can I get sequences that produce more apples?
- What happens if I use different 2^n vertical or horizontal slices in a single pass? Or more explicitly: what happens if I use a number P for the number of vertical slices and a number Q for the horizontal slices for a single pass but where P is not equal to Q but both are equal to some power of 2?
- What happens if I cut an image with multiple vertical steps and then the horizontal steps?
Stay tuned! Thanks for reading. Please follow me on Twitter: @romsearcher