For almost three decades, I've been interested in photo mosaics since around 1995, when a news report like this one was aired. I remember it differently, but it could just be a simple Mandela effect.
I remember thinking, "Hmm, I know how that was done," and quickly made my own little prototype.
It worked, but it was sloooow.
In the last couple of years, I’ve been on a journey to improve that original idea. And I think I’m getting close to the perfect photo mosaic.
The first mosaics took over an hour to make, testing thousands of images against a single square. Then I made it multithreaded, which significantly reduced the time to tens of minutes, depending on how many images there were to compare.
Now, I stumbled upon K-D Tree. I’m still little miffed (a lot) on how exactly it works but it does. It is a binary tree, but its not. In the past I tried VP-Tree as described in pyimagesearch post on Building an Image Hashing Search Engine with VP-Trees and OpenCV but found it inaccurate for my application.
“A K-D Tree is a binary tree in which each node represents a k-dimensional point. Every non-leaf node in the tree acts as a hyperplane, dividing the space into two partitions. This hyperplane is perpendicular to the chosen axis, which is associated with one of the K dimensions.”
K-D Tree’s most common uses is nearest neighbor search, where they’re used to find the closest point to a given point quickly, like in seconds.
The program first creates a K-D Tree of mean colors of all images that will be used in tiling the mosaic. When mosaic generation is started, it finds the closest 10 results for each tile. Those 10 results are then used as inputs to a “classic” Mean Squared Error (MSE) checker. MSE measures the average squared difference between the pixels of the main image section and the small image tile. MSE is used to fine-tune the match found by the K-D Tree by comparing the actual pixel values of the image tiles. The goal is to minimize the difference between the main image section and the small image tile.
So the rundown is like this, first it took hours, then it took tens of minutes and now it takes tens of seconds. Specifically, it dropped from 2.3h to 11.2 minutes and finally to 10.53 seconds to produce to my eyes even better looking mosaic.
Input images are 14400x14400 px wide with 2819 images to be used in generating the mosaic. Each tile is 100x100px wide totaling in 20.736 tiles to process.
Here is Lenna, but now we will test the mosaic generation at 14400x14400px instead of our prior test with 1024x1024 as it no longer takes hours to complete.
The mosaic on the left is without K-D Tree, the right is with K-D Tree+MSE.
Much more color detail is preserved with K-D Tree search and then structural detail is somewhat restored by refining the search with MSE.
In future testing I will redo the tests from Part #1 where I tested all (to me) known methods of comparing two images. I want to retain even more details in form of shape now that mosaic is more color accurate. The goal would be to use as few tiles and as large tiles as possible but still get a large image.