Posted on June 12, 2011
Mosaics and More Algorithm Love
My mom (whose website I should update) recently celebrated her birthday. My mom is an avid shutterbug, and abuses the digital camera we got for her a handful of Christmases ago to the tune of 10,000 photos a year, give or take. Our basement is piled with boxes of images just begging to be scanned, cataloged, sorted, and all that from back when mom was a film user (you all remember film, right?). I daydream of software that will actually be useful to that endeavor — to say nothing of how fun it would be to digitize the piles of super-8mm movie film that goes along with it — but so far we haven’t made much of a dent.
In the mean time, though, I have a hard drive which contains about 150,000 photos from my mom’s library… basically a full off-site backup in case horror happens to her computer. (ObNote: This is good practice, boys-and-girls, you should all go about giving hard drives away, with complete backups of your stuff in case of a disaster… you’ll thank me when the revolution comes). Anyway, I was looking around for a way to leverage this wealth of digital media for a birthday present and decided to go with a photomosaic.
I’m sure everyone’s seen one of these. Photomosaics are those stubbly looking pictures that are made up of hundreds or thousands of smaller less stubbly little pictures that magically align to form a recognizeable image. A google image search for photomosaic will help clear this up with a few gazillion examples. Good.
Somewhere on my lifelong “to-do” list (which is on a wiki over here) is to write some software, and one of the choices I’ve had was software to build these sorts of images. Naturally, there are some patent issues, but apparently only if you use certain shape-recognizing features, and since I have no idea how to do that (I’d do pixel-by-pixel comparisons, I imagine, much like examples that came before the patent), I shouldn’t have a problem. Fortuitously, though, for my strongly procrastinating self, other people have already done the work for me.
Enter Andrea Mosaic. This is a shareware app that I’ve downloaded a handful of times in the last few years, but haven’t really produced anything of printable quality until now. I have to say I’m hugely impressed. The software offers a ton of choices for layouts, and for a small donation you’ll get a bonus pack which allows you even more varieties. What I’m talking about here is the ability to mix portrait and landscape photos in various ratios and patterns, and even to use hexagons or other tessellating shapes for the internal photos.
The problem with my mom’s photo archive is the mass amount of pictures that look almost identical to each other. I’m referring here to a penchant for snapping a photo and then, for good measure, in case someone blinked or there was a weird reflection, snapping another. That sounds reasonable. My mom, though, has taken this trend to it’s logical yet harrowing conclusion whereby moments are photographed dozens of times causing an increasingly dazed and confused look on the subject’s faces as they clearly, between blinding flashes, are searching for some way out of the kill zone. Mere seconds after the last spots have left their eyes, they realize in horror that they are being asked to recreate some nuance of the moment that the camera may have missed — perhaps grape juice was spilled in a very special way and, kindly, would you please, spill some more on your little sister so that we can capture this moment forever, and possibly post it to the internet.
The upshot of this is that I have a huge collection of folders, organized by date, each containing thousands of photos that look like slow motion film frames of spilled beverages with people in various states of “smiling”. Photomosaic software picks the best photo that matches for a given section of a larger image, and while AndreaMosaic allows you to specify that no single image is used twice, it’s not that adept at recognizing photos that are nearly identical. The result is that sections of the images with similar colors will fill themselves with similar-looking photos. My mom’s forehead was literally covered in nearly-identical pictures of a baby who was slowly spitting up some unidentifiable mass that had the same complexion as, well, my mom’s forehead.
You can imagine the trouble this causes.
Andrea himself seems interesting from his personal website… a bit of a renaissance man, perhaps? He was particularly helpful when I asked for an algorithm change — a nice feature in a free but non-open-source project is the ability to communicate with the programmer. The change was simple: treat folders, rather than photos themselves, as the comparator for identical-ness (!) when filling nearby cells. This avoids the baby-filled forehead issue without having to go through an arduous process of identifying overly-similar photos to eliminate duplicates. Andrea was nice enough to implement that for me and get the software to me in time for me to build a large image, ship it to the printers, and deliver it to my mom in time for her birthday. Many Kudos to Andrea for all the help.
Here’s a very very small version of a nearly-final version of the image. You can see some of the repetition in the forehead (it’s mostly beach scenes at this point), but it’s a bit better in the final. It ended up printing at 36×24 inches and being about a 32MB .jpg file if you’re curious:
And some of the detail, still in a much smaller than the printed resolution; this is a closeup of my dad’s eyeball (ewww):