Algorithm Seamlessly Patches Holes In Images

Beetle B. writes in with research from Carnegie Mellon demonstrating a new way to replace arbitrarily shaped blank areas in an image with portions of images from a huge catalog in a totally seamless manner. From the abstract: "In this paper we present a new image completion algorithm powered by a huge database of photographs gathered from the Web. The algorithm patches up holes in images by finding similar image regions in the database that are not only seamless but also semantically valid. Our chief insight is that while the space of images is effectively infinite, the space of semantically differentiable scenes is actually not that large. For many image completion tasks we are able to find similar scenes which contain image fragments that will convincingly complete the image. Our algorithm is entirely data-driven, requiring no annotations or labelling by the user."

Comments

Finally...

[setirw]

Uncensored Japanese pornography!

Re:Finally...

[pla]

Finally... Uncensored Japanese pornography!

More seriously, I can see this applied to "fixing" pictures of just about anyone you want to see naked.

Fake celeb slips will of course come first, but why stop there? That cute girl at the coffee shop? Snap her with the camera phone, erase all those pesky clothes, and let this algorithm do its thing.

Of course, I could also see this used for more nefarious (even "sick") purposes... Ex-GF cheated and you don't have any nude pics to release to the web? You do now. And if you "repaired" a fully-clothed original of someone underage, would it still count as child porn?

And I don't even want to think about how the furries would use this... Ugh.

Re:Finally...

[voxel]

I'd go more like this:

You take a picture of that cute girl at the coffee shop. Snap her with the camera phone, erase all those pesky clothes, and let the algorithm do its thing.

You wait for the algorithm to finish, it says "Done", you get all excited and click the button to see the result, and.... * DOH *, it put all her clothes back on, albeit a different color and style.

Immediate Application

[ObsessiveMathsFreak]

Broken or flaky video files. Nothing is more irritating than an mpeg, etc error that causes an entire block to go black and smear itself all over the place until the next keyframe. I don't expect realtime correction, but it would be nice if I could patch the file rather than do another six hour encode.

Re:Immediate Application

[CaptainPatent]

Unfortunately, I think this particular algorithm would need a base set of data to begin working. While I'm sure portions of this algorithm could be implemented for such an application, it seems a base set is needed in a single image, therefore a full blank screen from a dropped frame or damaged images showing bad colors would not be successfully mended.
If, on the other hand, you were a movie producer and needed to get rid of the frame change holes after loosing the master print of a film, you perhaps would be able to use such a program to mend those holes in the upper corner.

w00t!

[morgan_greywolf]

It was as if a million fake celebrity pr0n websites cried and were suddenly silenced...

Dead

[Spad]

Slashdotted already.

BBC News coverage of the story is here: http://news.bbc.co.uk/1/hi/technology/6936444.stm

GREYCstoration

[BlackPignouf]

And if you dont have any pictures database, there's always GREYCstoration:
http://www.greyc.ensicaen.fr/~dtschump/greycstorat ion/index.html
It's pretty impressive:
http://www.greyc.ensicaen.fr/~dtschump/greycstorat ion/demonstration.html
and works with the gimp.

What will it do if...

[iknownuttin]

I take a picture of a hole?

DO NOT use it on your Porn-Collection!

[Opportunist]

You never know what that "kinda-like" picture used to patch contains. You might get the opposite of what you want.

Image compression?

[grimJester]

If any hole in the image can be filled with a part of another pic, can't you compress an image by replacing one piece at a time with a reference to a patch? Also, how about replacing with patches of higher resolution than the original? I realize it would all be technically lossy as hell, but the compression artifacts should not be very noticable to the human eye, right? Additionally, how about using this for movie compression? Filling in based on info from previous and next frame.

I may have to actually RTFA this time.

Re:Image compression?

[Anonymous Coward]

If any hole in the image can be filled with a part of another pic, can't you compress an image by replacing one piece at a time with a reference to a patch?

That only works if your patch addressing space takes less space than the bits you're replacing - and of course when you reload the image, you'll still get say a cat instead of an iguana in that window...

Also, how about replacing with patches of higher resolution than the original? I realize it would all be technically lossy as hell, but the compression artifacts should not be very noticable to the human eye, right?

I'm not sure you really understand the concepts here. Replacing a patch with a higher res would be possible (but you'd have to resample the image first, basically) - and would either be incredibly lossy or perfectly unlossy, depending on your viewpoint.

From a compression standpoint there's no reason to consider a high res replace as more lossy as anything else. From a recognition standpoint, whether you're doing it high res or not, this would be a method that throws out image details for others... but that doesn't have anything to do with the resolution. So this is a lossy image manipulation, but not really a compression...

And of course, none of that would cause any compression artifacts, so yeah the human eye wouldn't notice (assuming this software works as claimed)

So to go back over the concepts:

Lossy - a compression or manipulation to an image or other digital file from which you cannot reconstruct the original bits perfectly

Compression Artifact - a noticeable image tearing or other visual defect allowing one to differentiate between a lossy-compressed file and it's original

Additionally, how about using this for movie compression? Filling in based on info from previous and next frame.

That's how movie compression came about. The first moving-file format that was widely available was animated GIF - which quickly got onto the trick of using transparent pixels for non-changing parts of a scene.

MPEG (1) one upped it; one part of the spec specifies which blocks are to be sent in each frame; you can leave out any blocks you don't want... (they also smartly seperated the chrominance and luminance channels, and subsampled the chrominance channel - not only is it a smart compression as the human eye perceives luminosity at greater fidelity than chorminance, but it also ups the chances that you don't have to transmit some blocks)

Fast Forward to MPEG-4 (non-H.263) - same basic block structure, same ability to not draw blocks, and now you can even specify offsets for blocks - you have probably heard this technology referred to as motion compression - basically if something is moving on the screen but remains relatively the same pixel values regardless of motion, the movie file will record the motion without recording every pixel - the difference between a good MP4 compressor and a bad compressor mostly has to do with how well it identifies candidates for motion compression, is my understanding...

pfft

[Shadow Wrought]

CSI Miami and NY have had infinite zoom capability with photos for years, and you excited about this? Bah.

Will it be as smart of MS Word?

[elrous0]

Instead of "You appear to be writing a letter. Should I format it for you?" I guess we'll get "You appear to be viewing Japanese pornography. Should I de-pixelate it for you?"

Re:Will it be as smart of MS Word?

[somersault]

I'm going to have to take out trademark and patent on Clitty, your helpful little hentai fixing friend!

Not "Arbitrary"

[doug141]

Although the summary says the method will fill arbitrary holes, at the link that claim is not made, and in their examples they delete specific picture elements.

New problem-solving paradigm?

[Urban Garlic]

I wonder if this is part of the beginning of a new, computationally-driven problem-solving paradigm. As more and more data is stored, and if search algorithms become more and more clever, the cost of "looking up" (computationally speaking) the answer to a problem might be lower than the cost of "remembering" (using local storage) or "figuring out" (using local CPU power) the answer.

This is already happening informally in the personal sphere, because of things like Google, recently amplified by the iPhone and its inevitable successors in the ubiquitous rapid-access web-tool field. As they say, these days, if you have a web browser, you hardly have to wonder about anything anymore.

Of course, problem solving by search isn't exactly a new paradigm, but it could be a newly-cheap paradigm.

Now we need a patch for dead servers

[objekt]

We need a new way to replace slashdotted servers with portions of articles from a huge catalog in a totally seamless manner.

Is this how the brain fills in the blind spot?

[dpbsmith]

This is very cool, and I wonder how similar it is to what the brain does with respect to blind spots?

For those who don't know: each eye has a surprisingly large blind spot at the place where the optic nerve enters the eye. At reading distance, in the right eye, it's about four or five inches to the right of the spot at which you are gaving, and many textbooks and "fun with optical illusions"-type books will have a diagram... like the one on this web page... and directions for finding it. The blind spot is much larger than the dot on that web page, incidentally. If you explore, you'll find that... at the distance at which the dot disappears... the blind spot is nearly an inch wide and an inch-and-a-half high.

Even allowing for the fact that each eye has the blind spot in a different place so they fill in for each other, once you discover how big the blind spot is... and how relatively close to your position of gaze it is... you'll be astonished that almost nobody notices it until it is pointed out.

The brain does something more or less like filling in the blind spot. I say "more or less like" because it is very hard to answer the question "what do you see in the blind spot." For example, if you hold a computer keyboard at the right distance so that you're looking at the "G" key and the "K" key is in your blind spot, what do you see? Certainly not a black spot, certainly not a white spot, certainly not a "hole" or emptiness. Probably you have an impression of computer keys. Do you see a letter K? Certainly not, yet somehow you don't see a blank key, either.

Incidentally, I used to suffer from migraine headaches, and one of the symptoms for some people is the formation of blind spots which can be even larger than the "normal" blind spot, and can appear in central vision. One one memorable occasion, I was looking at the cover of a hardbound book, and I can tell you that when I looked at the title, my perception was the stamped, printed title disappeared, yet I would have sworn in a court of law that I still saw the cloth texture extending across the blind spot.

Although he does not specifically refer to it as a migraine illusion, I believe Lewis Carroll was known to be a migraineur, and in Chapter V of Through the Looking-Glass, "Wool and Water," Alice notices that "The shop seemed to be full of all manner of curious things -- but the oddest part of it all was that, whenever she looked hard at any shelf, to make out exactly what it had on it, that particular shelf was always quite, empty, though the others round it were crowded as full as they could hold." Any migraineur who experiences central blind spots will recognize this description.

Hays and Efros' system--relatively-simple algorithm operating on a large database of previously-seen images--seems to me to be the sorta-kinda way in which one could imagine the brain working.

I wonder if there's any way to test this?