Slashdot Mirror
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."
Slashdotted already.
BBC News coverage of the story is here: http://news.bbc.co.uk/1/hi/technology/6936444.stm
Actually, laser printers and supermarket scanners often use holograms of optics rather than actual glass optics (mirrors and lenses). The holograms are usually CGI - making equivalent real glass optics would be fabulously expensive and heavy, or even physically impossible.
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...
Effectively that means that just as you personally can recognize a bunch of pictures as all being "japanese porn" or all being "pictures of boats", or all being "pictures of men in suits", so can the computer.
And that number of different categories that humans take pictures of is not that large, probably less than 200,000 different categorizable subjects.
So with 1 million pictures, you have 5 of any category and can cut/paste pieces in without making it look obviously cut/paste.
excitingthingstodo.blogspot.com
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.
The paper is published on Efros's website; I don't think neural nets were used, but I only glanced at a it a while ago. A program called 'gist' summarizes all of the images in the database and based on similar summaries they narrow down to a couple hundred images. Then they pick one image and look for a cut line slightly surrounding the missing area which minimizes some criterion. You don't see the seam because they fill in more than just what was missing.