During a boring weekend, I proposed the following programming challenge to myself: build Mona Lisa from Pablo Picasso's paintings.
And just so you know, I wasn't high. :)
Here goes a thumbnail of the resulting image. Believe it or not, the original image's resolution is 13960x20800 with over a hundred megabytes (113.7M to be more precise):
This is the highlighted section in more details:
This image was generated using a corpus of 3,588 images of Pablo Picasso's paintings and drawings.
The script took about 5 minutes to complete in my laptop equipped with a quad-core (8 threads, 8M cache) Intel i7-920@2GHz processor and 8GB of RAM:
$ time lein run -w 40 -s <picasso-img-dir> -t ./tmp/ \ -o ./tmp/output.jpg ./img/mona-lisa-original.jpg real 4m31.411s user 21m47.763s sys 0m18.977s
As you can see, the code was optimized for parallel execution. If you know how to make the code even more efficient, please let me know.
Note: You can use a smaller corpus, but the output image quality will vary (for better or worse) depending on how diverse the input palette generated from the corpus is.
How Does It Work?
The first step is to crop and scale down each image to be used to recreate the desired picture. After that, we calculate the average color of each of those images and store them in a k-d tree.
Then, for each pixel in the desired picture, we perform a nearest neighbor search in the k-d tree in order to find the image with the closest average color. The distance measure used is the squared distance, which provides a good balance between performance and correctness. (There are other distance functions that model the human eye perception more accurately, but they are much more complex and expensive to compute).
lein run to list all options available.
If this project is useful for you, buy me a beer!
Copyright © 2014 Daniel Martins
Distributed under the 2-Clause BSD License. See LICENCE for further details.