Algorithm fills blanks in photographs

The advent of digital photography has opened up anew world of image editing possibilities including the ability tofill-in blanks or replace unwanted parts of an image. A new algorithmdevised by James Hayes and Alexei A. Efros of Carnegie MellonUniversity facilitates this process by drawing on a huge database ofmore than a million images from the World Wide Web in order toseamlessly fill in the missing areas of incomplete photographs.

There could be many reasons for an image tofeature an undesirable blank area - a patch of bright light that neededto be cropped out or perhaps a shadow, a person or an object ruined anotherwise perfect shot.

The algorithm tackles this problem bycompleting a given image in a number of different ways leaving the userto select the one which is deemed most suitable. This can be achievedwithout the user having to label the image fragments being used, or forthat matter, offer any direction at all.

"Holes" in images are "patched" as suitableimage fragments are found and re-arranged to complete the image in amanner that is claimed to be semantically valid. That is, the patchedarea is consistent with the rest of the image. Hays and Efros claimthat their algorithm is a means to restore data missing from an imagethat "should have been there". Existing methods of filling such blankareas have largely involved drawing image fragments from other parts ofthe same picture. This algorithm is quite unique in that it draws froman exterior database and also in the means by which it achieves this.

Source: graphics.cs.cmu.eduAdded: 5 September 2007