*
programming and human factors
by Jeff Atwood
*
Have you ever noticed how, in movies and television, actors can take a crappy, grainy low-res traffic camera picture of a distant automobile and somehow "enhance" the image until they can read the license plate perfectly?
Yeah.
I don't know what kind of crazy infinite-detail fractal images these scriptwriters think we have. Here in the real world, bitmaps don't scale worth a damn. Take this bitmap, for example:
If we blow that up 300% using the simplest possible algorithm-- a naive nearest neighbor (aka pixel resize) approach-- we get this:
Pixel-tastic! But there's a well known way of interpolating the pixels in the image so it doesn't look quite so bad when upsized-- something called bilinear filtering. Bilinear filtering samples nearby pixels in an effort to guesstimate what the missing pixels would look like in a larger image. Let's enlarge the image 300% using bilinear filtering and see what happens:
A bit blurry, yes, but clearly superior to giant chunky pixels.
There's also something called bicubic filtering which is supposed to be an improvement over bilinear filtering. Video cards have offered bilinear filtering for years, but they don't bother with bicubic filtering to this day. And that's with millions of transistors to burn. If bicubic is only offered by paint programs, you have to wonder, is it really worth it? Here's the same image enlarged 300% using bicubic filtering:
Interesting. It's sharper, but I'm not sure it's all that much better. And there's a bit of an oversharpening or halation effect at some color borders, too.
There's another image sample at Interpolate This with a writeup that implies that bicubic is flat-out superior, but I'm not sure that's the case. Either way you're interpolating*, it's just a question of how sharp you like your simulated pixels to be.
The best solution of all is to move to a vector representation and give up on bitmaps-- and interpolation-- entirely.
* A reader pointed out an interesting algorithm for interpolating low-res images called 2xSAI. Here's a screenshot I generated of a SNES game with 2xSAI interpolation enabled. Compare to the original screenshot.
Posted by Jeff Atwood View blog reactions
« Are All Programming Languages The Same? Despite the incredible slowness and the sparseness of features, this is really really cool »
The example you gave is not very example of the astonishingly high quality effects you get with bicubic and bilinear scaling.
Line drawings, such as the one you use, don't scale well.
However, photographs scale extremely well and the difference between bicubic and bilinear become very apparent.
Wesner Moise on August 20, 2005 05:08 AMThe problem of photographic enhancement is usually not one of "making pixels" (scaling up). A photograph actually has a lot of pixels (a real one, that is); the average size of a silver grain on film is about 1 micron. A typical 35mm negative is 24x36 mm (don't ask). Assuming you scan the film at the full resolution of the grains, you would get 24M x 36M pixels, or 864M pixels. Even if the region of interest doesn't fill the frame, you will generally have plenty of pixels for the subregion (e.g. license plate).
The problem is that the lens system probably wasn't focused exactly on the subregion (license plate), so you have to sharpen the image to enhance it. There are many techniques for sharpening, most of which use a convolution kernel. This is a matrix operation in which a pixel's value is changed by applying postive and negative offsets computed from nearby pixels. For example, the "unsharp mask" operation is a convolution kernel. It is amazing how much contrast and detail can be recovered from an out-of-focus image using this technique. Often you really can read the license plate.
Ole
P.S. In case you're wondering, there are devices which can scan at micron or even submicron resolution, which is two orders of magnitude beyond your typical flatbed scanner. My company Aperio makes instruments called ScanScopes which are used for scanning microscope slides; the resulting images can have a resolution of .25 microns (approx. 100,000 dpi). A typical microscope slide has a tissue area of about 20mm x 15mm, so the resulting digital images are around 100M x 60M pixels. That's a lot of pixels.
Ole Eichhorn on August 20, 2005 10:28 AMSigh. This is what I get for commenting before I've finished my coffee. I used some Ms instead of Ks. A 35mm negative at 1 micron/pixel would have 24K x 36K pixels (which is 864M pixels, as noted). A 20mm x 15mm microscope slide at .25 microns/pixel would have 100K x 60K pixels (which is 6G pixels).
Ole Eichhorn on August 20, 2005 10:35 AMDon't you know that traffic cameras record everything using vector based representation? That's how they do it. And they have in instantaneous shutter speed and Petabytes of storage capacity.
;)
Haacked on August 20, 2005 11:34 AMStuff like 2xSaI will get much better results for drawings like Hello Kitty there.
<a href="http://en.wikipedia.org/wiki/2xSaI">http://en.wikipedia.org/wiki/2xSaI</a>;
Dezro on August 20, 2005 03:13 PMBTW, for EXACTLY the type of image you show here - the low-res, low-color, sharp Hello Kitty - the emulator writers have created a bunch of very good heuristics interpolation algorithms, e.g. 2xSAI:
http://en.wikipedia.org/wiki/2xSaI
Ivan-Assen on August 20, 2005 04:02 PM> photographs scale extremely well
> A photograph actually has a lot of pixels (a real one, that is)
I think both of you are referring to real photography with professional grade pixel counts, eg, many megapixels. I'm thinking of the low-res, grainy security and traffic camera images I frequently see "enhanced" to reveal detail on shows like television's "24".
But I agree that if you have a picture with megapixels of detail to start with, a bit of reasonable upscaling can be done.
> very good heuristics interpolation algorithms, e.g. 2xSAI
That is very cool! More screenshots of it in action:
http://elektron.its.tudelft.nl/~dalikifa/#Screenshots
as well as a detail shot at the top of that page.
Jeff Atwood on August 20, 2005 05:16 PM> However, photographs scale extremely well and the difference between bicubic and bilinear become very apparent.
I'm not so sure about this, particularly for the relatively low-res images I was referring to in the post. Here's an example 640x428 photo image:
http://www.codinghorror.com/blog/images/woz_roth.jpg
I blew this up 300% using both bilinear and bicubic. Then I zoomed in to 100% and browsed the image. I noticed that the sharpening effect of bicubic makes the JPEG artifacts far more prononounced.
That said, bicubic and bilinear are essentially the same. You're basically choosing between a SLIGHTLY sharper image (bicubic) or a SLIGHTLY blurrier one (bilinear). When upsizing an image, I think it's somewhat dangerous to err on the side of sharpening, although I guess this depends how good the source image is. And your decision might be different when you are downsizing the image..
Jeff Atwood on August 20, 2005 11:51 PMI think the people pointing out that bicubic interpolation works best on photos weren't trying to claim that this would enable you to expand 3 pixels into a sharp and legible number plate. I don't think anyone's taking issue with your basic claim that the magic zoom beloved of crime drama writers is impossible.
I think they were just pointing out that bicubic interpolation is often significantly better than bilinear interpolation on photographic images. What you wrote implies that bicubic interpolation is pointless because it offers no benefits over bilinear. That's not actually true - it's not a magic bullet, but it's a definite improvement for certain scenarios.
(But it does interact unfortunately with artifacts on over-compressed JPEGs, as you observe...)
Ian Griffiths on August 31, 2005 06:13 AMHi,
And have you heard of GREYCstoration?
http://www.greyc.ensicaen.fr/~dtschump/greycstoration
It can be used for image resizing, among the others, and it does wonders.
See Image Resizing on http://www.greyc.ensicaen.fr/~dtschump/greycstoration/demonstration.html
eg.:
http://www.greyc.ensicaen.fr/~dtschump/greycstoration/img/res_rabbit.png
the problem with your hello kitty isn't that it's not like a photograph. The problem is that many of the jaggies are double-pixel. If you look at the feet, you can see single-pixel jaggies. These turn into very impressive straight lines using bicubic. The double-pixel features hardly even get blurred by either algorithm, and that is the way you would want it to work.
Anyway, you're second on a google search of "bilinear vs bicubic," so you have much honor and responsibility to fix this.
tho i wonder if maybe one reason you're second is cuz you seem to "debunk" the advantage of bicubic.
alex dub. on August 29, 2006 06:55 AMIf you want to see an example of an "impossible" increase in clarity of a blurry image, check out the sharpened video of the tiles that fell off the space shuttle, leading to the explosion on reentry. The original video that they had was taken from miles away, and showed about what you'd expect: a blurry mess. After some NASA magic, it clearly showed the tiles hitting the wing. If you ask me, I'd say that it's possible because I've seen it (but I don't know how they did it!)
Farkus on March 8, 2007 05:30 PMthats amazing id like to put in to google
hh on May 25, 2007 05:47 AMThank you, very interesint. We use CXImage library in our products - http://www.softorbits.com/batch_picture_resize/ it supports 8 types of image resizing algorithms like lanzcos, bSpline, hermite, bicubic (software and hardrware-based). They have different quality and speed..
Jay Wilson on January 20, 2008 12:37 PM| Content (c) 2008 Jeff Atwood. Logo image used with permission of the author. (c) 1993 Steven C. McConnell. All Rights Reserved. |
Subscribe in a reader
Subscribe via email
