I did something similar to this once and used a similarity algorithm for fitness. The result was really neat, the output image looked very similar to the input image when you were zoomed out but when you zoomed in it was unrecognizable. It was a really interesting result!
Your comment kinda reminded me of "Rasterbator", a software I used 15 years ago to decorate a wall at my uni dorm. It took an image and a size, and gave you back a pdf with a4 pages to print. The pages were just dots up close, but when arranged in the grid with the other papers and looked at from afar it would be the original image.
