Genetic Algorithms: Evolving Human Faces
Tweetupdated: 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.
What is a genetic algorithm?
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.
How do I do it with faces?
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.
My Algorithm
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:
- Initial population (500) are random grey-scale images (they look like static)
- The best 15 reproduce twice, the worst 15 die
- I did asexual reproduction, depending only on mutation
- Mutation: each pixel had a 1% chance of being mutated to a random value
- The output images are moving averages that have been low-pass-filtered and normalized (in other words, I’ve done a bit of image processing to remove noise from the output)
This is not a sophisticated algorithm. In fact, there are a hundred ways you could improve this algorithm. But I didn’t need to.
Results
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.
The effect is more striking if you see it from a bit further away (stand back a few feet).
Tweet
twitter
April 20th, 2009 at 8:53 am
It would be interesting to see the results of different face detection algorithms side by side – the one used seems to evolve big schnoz’s (especially in profile).
April 20th, 2009 at 9:35 am
If the face detection algorithm is based on an internal template, then this process filters noise until it matches the template.
It would be interesting if your current “population” of face-like images could contain a diversity of faces at the same time.
For kicks, … how about mating the top 10 “probably male” faces with the top 10 “probably female” faces.
April 20th, 2009 at 10:14 am
@justin, keep in mind it found local optima so it might have just found a particular big schnozed region and it couldn’t escape. Also, I think using another face detector (like open-cv) would be interesting. File that under future work.
@david, its not based on templates but learned features. I agree with you, however, that using a machine learned algorithm to simulate faces (going backwards) has some, uh, theoretical problems. But it makes for a cool video.
April 20th, 2009 at 12:05 pm
Thought I’d reply over here since the HN crowd seems a little rowdy today.
I’ve also been working on a genetic algorithm, but for a mechanical design project (car suspensions). Cool to see similar methods used on a completely different application.
If you’re thinking about adding crossover to your model, this paper might be helpful (especially Chapter 3 starting on P 27):
http://dspace.mit.edu/bitstream/handle/1721.1/10207/38277354.pdf?sequence=1
Interesting project though. Thanks for posting it.
April 23rd, 2009 at 9:29 am
Eheh, nice to see “white-noise” images turning into ghostly faces.
November 20th, 2010 at 10:13 pm
It would be cool to do this, but using a virtual pencil, and a series of instructions for what to do with it as the genetic code. just a thought
February 28th, 2011 at 4:23 pm
For an easy next step (might not actually be easy, just seemed like it), how about some color?
would it take any more than using an RGB color value for each pixel instead of a single grayscale value?
December 31st, 2011 at 2:57 am
remote controlled toysFamosos
Descubra com qual celebridade você se parece
Você sempre se achou parecido com alguma celebridade, mas nenhum dos seus amigos ou familiares têm a mesma percepção? Então mostre para eles com quem você se parece com o…
December 31st, 2011 at 11:57 am
alarm systems for apartmentschatten
10 Home Security Systems Benefits To Keep In Mind
Home security systems are the top most requirements for safety purposes. There is a boom in this industry that has allowed home security companies to flourish and it gives many options to the customers to choose from.
January 1st, 2012 at 9:42 pm
yachtcrewκατασκευή ιστοσελίδας
Maritimworld.com is a job portal that provides something different. The reason is quite simple.
Developed and maintained by ‘First Solutions’ a Norwegian Company.
January 1st, 2012 at 9:46 pm
Welcome to Banner Stand Pros . . .
The Superstore for Banner Stands!
You’ve arrived at the best spot on the internet for banner stands. Here you’ll find the largest selection of retractable banner stands (also called roll up or pull up stands), portable models, which are the non-retractable styles, as well as models for trade shows, retail or outdoor use, accessories, replacement parts, shipping cases and more. Our huge selection means you’re sure to find exactly the right display or accessory for your needs, and our large volume means we can offer the best prices in the industry.
banner display standsAustralia Shoes
January 1st, 2012 at 10:27 pm
Please join us in enjoying the luxurious lifestyle that Naples, Florida has to offer—–beautiful tropical weather with warm breezes off the Gulf of Mexico. Fine dining, world class shopping, championship golf and boating are a part of the wonderful lifestyle that Naples has to offer.
Quail WestRYA Course
January 2nd, 2012 at 9:53 pm
bedsresort Fraser Island
Bed and Mattresses for a comfortable night sleep from Absolute Beds London
The best deal bedroom furniture store where you can find bespoke beds and mattresses exclusive beds frames at best and cheap prices in London and UK.
January 2nd, 2012 at 9:58 pm
celebrity newslocation de salle lyon
Is Sonic Youth breaking up? If so, we will need to take a break from gossiping for a few hours to weep and smash furniture.
January 3rd, 2012 at 2:02 am
Air Conditioning Service NYC
Five Borough AC Is The Air Conditioning Experts For Residential And Commercial Units. We Are One Of The Leading HVAC Service Providers In NYC.Our Respond To Your Air Conditioning Repair Needs Will Be Fast And Professional. Our Goal Is To Make Sure Your Air Conditioner Will Preform At It Best. Our Air Conditioner Repair Mechanics Are EPA Certified And Provide Top Customer Service.
air conditioners nycNAIL
January 3rd, 2012 at 8:13 am
Featured Product Freaky Cousin Outdoor Lime
$145.00
The Freaky Cousin bean bag’s vibrant colour and unique shape perfectly compliments any lounge room, childs play area or bedroom. DIMENSIONS 105 x 77 x 55 Recommended beans 220 ltrs Polyester 420 D with PVC Coating Be careful with the shocking color and shape effect of the Freaky Cousin.
outdoor bean bagswedding shower invitation
January 11th, 2012 at 11:16 am
doormats with sayingsst lucia holidays
Serve the Lord MatMates™
This Serve the Lord MatMates™ pattern welcome mat
January 13th, 2012 at 7:44 am
Saving money on ink cartridges is an easy way to lower expenses
We’re a Proud Member of the BBB ASAP Inkjets offers discount inkjet cartridges and laser toner for Epson, Canon, HP, Lexmark, Brother and many other printers at enormous savings.
inkjet print cartridgesMusic for Documentaries
February 1st, 2012 at 9:55 am
Epson M2400 Tonerpower tab files
Compatible Epson M2400 Toner
Our compatible Epson M2400 toner fits the VOSA supplied MOT printers and gives high-quality print for a lot less cost than the Epson originals.
February 1st, 2012 at 10:48 am
holidays to antiguadata cabling engineer
Antigua Weather
As one would expect, Antigua boasts a very generous climate all year round, with only a slight dip in temperature during the winter months.
February 3rd, 2012 at 9:12 am
For many years, we have been dedicated to finding the most talented, up-to-date and qualified dentists to meet your dental needs. Every dentist and office hosted on 18004SMILES.com has met these qualifications.
dentist in san diegoизготовление пластмассовых изделий