updated: I’ve been kindly informed that the algorithm described below is not technically a genetic algorithm because there is no crossover (e.g. sexual reproduction). Maybe I’ll do a second version once I figure out a way to make two faces mate.
I work for a company called Pittsburgh Pattern Recognition. We do face detection, tracking, and recognition. This becomes important momentarily.
Not too long ago genetic algorithms were all the rage on the internets (see original here: genetic programming: evolution of mona lisa). I was keenly aware of genetic algorithms since I first learned of them in grad school and have always had the urge to code one up. Given the company I work for, and recent popularity of genetic algorithms, this gave me an idea. Let’s evolve a human face.
A genetic algorithm is an algorithm that tries to find solutions to a problem through a biologically inspired method. Specifically, you create a “population” of solutions, score them to see which are most fit, kill off the weak ones, and have the most successful ones reproduce to form the next generation. You repeat this process until a solution emerges. You can find out more about the details on the wikipedia.
We write face detection and face recognition software. Face recognition is about comparing two faces to see if they come from the same person. Face detection, on the other hand, is the process of locating faces inside images.
Every face detector, somewhere, deep in the heart of the code, has a function that essentially takes a square set of pixels and returns a number representing the likelihood that set of pixels is a face. In other words, every face detector has a built-in fitness function for a genetic algorithm.
So, I set out to write a face-evolving genetic algorithm using a slightly modified version of our face detector as the fitness function.
Turns out it was insanely easy. The very first thing I tried resulted in reasonable faces. I only made minor adjustments to make the output look a bit better. Here’s the details:
This is not a sophisticated algorithm. In fact, there are a hundred ways you could improve this algorithm. But I didn’t need to.
Please note, our detector is a low-resolution detector. It means our detector is capable of finding faces that are quite small. That is an awesome feature for a face-detector but not such a good one for a face evolver. The evolved faces, consequently, must also be at low resolution.
Because detecting smaller faces (a good thing) requires low resolution, the final faces will be low resolution. The effect is more striking if you see it from a bit further away (stand back a few feet).