Instant makeup: Perfect your holiday snaps

You pay a small fortune to reach your dream location, whip out your new digital camera, set up what you think is a composition worthy of Ansel Adams, and click. When you get home, you think to yourself, you'll have it blown up and framed. The perfect holiday snap. Until you get back to the hotel, and spot that baseball-capped stranger right there, in front of the Taj Mahal. A Kodak moment, ruined.

But help may be at hand, courtesy of American computer graphics researchers who have discovered the ultimate fast and easy solution to the dodgy holiday pic. Scene Completion, as they've named their software, replaces the ugly patches in your photos. Take the example shown here. All you need do is trace the area of the photo you wish to replace – such as that rooftop in the foreground. The software identifies what kind of scene it's working with, calculates the height the camera is at, works out the exact angles of the planes of sky and sea, and searches through a library of millions of images, looking for something it can superimpose over the rooftop. Magazine and newspaper picture editors often try to fill in such gaps on a smaller scale, spending hours duplicating sections from elsewhere in the same image. But this is not always successful.

"You have to be an experienced Adobe Photoshop artist to do this. And there are some things you could, realistically, never achieve," says Alexei Efros, an assistant professor of computer science and robotics at Carnegie Mellon University in Pittsburgh, where the software has been developed. "If you're removing a small detail, then fine, but in the example you see here, you're dropping in a huge area with boats and sea. You could never do that in Photoshop. A human could, in theory, go over a million images and try and find a match. But it would require perhaps a month to go over each image carefully to see if it would be useful. Scene Completion does it in five minutes."

In tests, people failed to spot the deception in a remarkable 70 per cent of the images the software had worked on. The system was developed by Efros and James Hays, a graduate student at Carnegie Mellon. One of the most difficult challenges was teaching the software to identify what it is looking at. "You need to know what to fill in and have some semantic understanding of the scene," Efros says. In essence, you don't want the computer to put a skier on to a white sandy dune because it thinks it's looking at snow.

The software draws on a huge database of images that Efros and Hays borrowed from the photo-sharing website Flickr.com. "We take the 'Google' approach," says Efros. "We have a huge collection of images – about two million – and then we search for images that look similar to the one that we need to complete. We take the missing content from the image and put it into the hole." As more of the world's tourist attractions and areas of outstanding natural beauty crop up in online libraries, the number of scenes that can be matched exactly will grow.

So, when can you get your hands on the software? Well, you may have to wait a while yet. "There are issues with copyright that must be solved for this to be commercially viable," says Efros. "The software borrows pieces of other people's images, but the authors of those images might not be happy about it."

The other stumbling block is in the processing power required. "The operation needs large amounts of processing power. It needs many machines to search the images."

For these reasons, you won't see it on Amazon just yet. "For now, I think we've made more of a scientific contribution than a practical one," says Efros. "We don't plan to put it out in the public domain yet, but we are pursuing research in that direction." If it does become commercially viable, this will be software that every snapper – amateur and professional – will want.

A second system, Photo Clip Art, also designed by postgraduates at Carnegie Mellon with help from Microsoft researchers, is of more interest to architects – or anyone else who's trying to create a fake landscape. It uses thousands of "clip art" images from a website called LabelMe and makes it easy to add people and other features into existing photos. One of the students involved, Jean-François Lalonde, says: "We were looking at how to create images. Currently you have to start with image-editing software such as Photoshop. You look for another image with the right kind of person or other object in it, you trace their outline, form a cut-out of them and paste them over the landscape. It can take a very long time. We were trying to find a way of making that easy enough for anyone to do."

Photo Clip Art analyses the photograph you start with and works out where the light sources are coming from, and how strong the light is. With this information it goes through its database of images and finds the best matching objects. You then drag these on to your photo.

"Let's say you submitted a picture of a street in sunlight. It will try to find all the objects in the database that were also taken in sunlight so that when you put them in the new image they look right," says Lalonde. "In Photoshop you could create all the images that we create, but it will take you anything up to a day, depending on your level of expertise, Whereas the images we create take five to 10 minutes." Photo Clip Art should be ready for public use by the end of the year – and it will be free.

"For now, the system will be mostly for architects and story-boarding for film directors," says Lalonde. "What we are trying to do in the future will be general picture creation. Maybe you have a set of pictures of yourself and you have a picture of another location that you have never been to so you want to put yourself in that picture." It could herald a whole new type of holiday snap, the distance you have to travel only being the journey to your desk.

Photo Clip Art: http://graphics.cs.cmu.edu/projects/photoclipart/;
Scene Completion: http://graphics.cs.cmu.edu/projects/scene-completion/