Bookmark and Share

Interpolation

by Gisle Hannemyr

Interpolation is a mathematical technique where a specific alghortim is used to construct new intermediate data points from an existing set of known data points. The result of the interpolation (the new data points) depend on which algorithm is used.

10%   To test how well interpolation works, I tried the following: I cropped a 400 x 400 px portion from an image (Original, below), downsampled it, (using Photoshop's bicubic sharper algorithm) to 127 x 127 px (i.e 10 %, left ). This was then interpolated back to the original size by means of various algorithms (the equivalent of doing a 1000 % enlargement).
Note: Nearest Neighbor is only included for reference (Nearest Neighbor is enlarging without interpolation).
10 %
Original
Original
Nearest Neighbor
Nearest Neighbor (1000 %)
Qimage Pyramid
Qimage Pyramid (1000 %)
Lanczos Interpolation
Lanczos Interpolation (1000 %)
Bicubic
Bicubic (1000 %)
Qimage Vector
Qimage Vector (1000 %)
Bicubic Smoother
Bicubic Smoother (1000 %)
Extensis pxl Smartscale
Extensis pxl Smartscale (1000 %)

As a rule of thumb, I've found that the number of kilobytes (Kb) in a file after lossless compression is a good measure for the amount of detail in a file. So, for what it is worth, here is the file sizes:


Original:301 Kb100 %
Qimage Pyramid:189 Kb63 %
Lanczos Interpolation:185 Kb61 %
Bicubic:183 Kb61 %
Qimage Vector:176 Kb58 %
Bicubic Smoother:172 Kb57 %
Extensis pxl Smartscale:166 Kb55 %

Nearest Neighbor:53 Kb18 %
10 %:35 Kb12 %

I think it is interesting that this table appears to give the same result as visual inspection: Qimage Pyramid has a less prominent pixelized structure (see hair and highlight on upper eyelid) than the other methods. I also think Lanczos looks nice.

The Qimage results have been submitted by Bart van der Wolf. Please note that Qimage is a printing interpolator, designed to do the much larger interpolations required by inkjet printers. Screen crops of print ready results may appear a bit ugly on screen.

Richardson-Lucy

Richardson-Lucy is a well known algorithm for image restoration using a statistical model for image formation based on the Bayes formula. It is not an interpolation method, but a post-processing technique (like sharpening). Applying Richardson-Lucy to interpolated images may create an artifical look for screen images, but usually improves prints.

Below, courtesy of Bart van der Wolf, are examples of the results of applying Richardson-Lucy to the Qimage Pyramid and Vector 1000  images. For easy comparison I've also included the Original, the Nearest Neighbor and the unrestored crops.

Original
Original
Nearest Neighbor
Nearest Neighbor (1000 %)
Qimage Pyramid RL
Qimage Pyramid R-L (1000 %)
Qimage Vector RL
Qimage Vector R-L (1000 %)
Qimage Pyramid RL
Qimage Pyramid (1000 %)
Qimage Vector RL
Qimage Vector (1000 %)

Offer

In the Usenet newsgroup rec.photo.digital, someone with the handle Ryadia (and Douglas MacDonald, D-mac, TechnoAussie, and a number of other aliases) is making extraordinary claims about what interpolation can do to an image.

After I complained about Kodak's Ofoto site stating that a 1600 x 1200 pixel (about 2 Mpx) image would give a “high quality” print up to 30 x 20 inches (i.e. 53 ppi), Ryadia responded:

“What you don't understand here Gisle is precisely how these images are
 printed. The firm are limiting the upload size to save bandwidth. They
 then Interpolate the image to the print size at whatever pixel density
 they need for their printer.

 […]

“Agfa labs, particular the ones using Durst, 'Lambda', continuous tone
 laser printers use a highly refined Interpolation program capable of
 2000% enlargements with only very minimal loss of detail. At 1000%
 and below there is no loss of discernable detail.”

(The full text of the article is in this archive.)

Unless your ability to discern detail is seriously impaired, downsampling (to conserve bandwidth or whatever) and interpolating back up to “restore” the original detail does not work.

Among other things, this process violates the second law of thermodynamics (only half a :-) - which is one of the fundamental laws of nature. The second law of thermodynamics tells us that the decrease of order within a closed system is an irreversable process. If detail is destroyed, there nothing that can restore it.

Standing offer to Ryadia: Download the 10 % crop above, and run it through whatever means you use to make a 1000 % enlargement, and email me the result. I'll put it up here along with the others.
Offer posted Sep. 22, 2004.

Ryadia has elected not to submit a 1000 % enlargement that can be compared to the other examples. He explains why in two separate messages that you'll find below. The first was submitted in May 2005, and the second was submitted in July 2009.

Interpolation Links

Bookmark and Share

9 responses:

avatar

These examples (on Gisle's Blog site) are from low grade (usually free or nearly) software and not representative of what can be achieved in a commercial lab, using high grade, commercial software like Kodak, Durst and Agfa use. The consumer product (pxl Smartscale) sold by Extensis is probably close to what could be described as "entry Level" commercial software.

Certainly at $200 US it could hardly be expected to match a $1500 US commercial application dedicated to the task. This effort to discredit my claims is admirable... I'm flattered that someone with no knowledge of my photographic lab which specializes in enlargement of digital and digitised images using my own process I loosely termed 'Interpolation' for convienence, could have so much time on their hands, they can make all these experiments with no more in mind than to discredit a commercial operator who makes a living from enlarging digital images!

Amazing effort. It is a sad fact of the commercial world that people with the talent to do this, often never have the ability or the funding to do it properly. I can only suggest applying to a University patron for funding to research the process if you are really serious Gisle.

The future of digital photography and camera phones relies on advances in interpolation and image enhancement as does the space exploration conducted by NASA... Who incidently use a commercial interpolation program to enlarge the images from space. Often to 1600% and larger.

avatar

Well, Ryadia, it seems that after reading your comment about too much time on Gisle's hands etc., you have proven yourself vain and unprofessional. Having said all that, I'd like to give you the benefit of the doubt (even though I don't believe for one second that you know anything about digital imaging not to mention my own knowledge) and ask that you email me some pictures interpolated by your miricle software. If what you claim is true, I will have to rethink the meaning of life. My email is petmin@ihug.co.nz. Can't wait to see the proof.

- Mason

avatar

Odd that someone would make a strong claim that interpolation techniques are strongly coupled to market forces. While investment of cash may well spur some amount of research, I would argue that there is a lot of fundamental research happening in the public sector. To give a specific example, the interpolation algorithms available in Helmut Dursch's free Panorama Tools have higher quality (from a signal-preservation point of view from the much more expensive Adobe Photoshop. I would instead stay within the realm of mathematics.

A good, scientific test would be to take a standard image from a standards instutition (ISO, ACM) for testing resolution. I'm specifically thinking those that use a series of converging lines that are resolvable at particular ppi. Alternately, a synthetic test could easily be generated. Downsample that image, then run it through the various interpolation mechanisms. Use a metric like peak signal-to-noise ratio or possibly root mean squared differences to quantify the algorithmic differences. Even a simple test of counting how many adjacent lines are resolvable would be a decent objective metric.

From signal theory, the best possible algorithm for upscaling is using an infinite sinc function. This is extremely expensive from a calculation point of view, since every input pixel has an effect on every output pixel. Other algorithms trade off quality for speed by reducing the scope of interpolation.

I would suggest that the participants in this debate (assuming it is a debate), refrain from self-promotion and instead restrict comments to the realm of mathematics and signal theory, the basis for all image processing algorithms.

avatar
If you can find the time, could you please include the results of bilinear interpolation?
Just curious to see it it with the others.
Thanks,
n.

Sean wrote:

From signal theory, the best possible algorithm for upscaling is using an infinite sinc function. This is extremely expensive from a calculation point of view, since every input pixel has an effect on every output pixel. Other algorithms trade off quality for speed by reducing the scope of interpolation.

Sort of, sort of not.

Using sinc-based interpolation is correct for audio since we mainly preceive it in the form of frequencies. However, much of our perception of images has to do with the time domain (spatial, in other words), not the frequency domain.

I have indeed interpolated images using a sinc kernel before - and it's not too costly by using an FFT. For typical images, it can take just about one minute. The results were rather disturbing: massive ringing around any edges. It's a futily impractical method, unfortunately, even if it is the correct method to prevent frequency alias.

avatar

Interesting that almost three years after Gisle attempted to coerce me into providing him the facilities to duplicate my work, Companies like Genuine Fractals who pioneered digital enlargment at a retail level have changed hands three times, still selling refined versions of the original Genuine Fractals but magically, have escaped being charged with fraud, as Gisle insinuates I committed because I wouldn't give his acces to my algorythm.

I suppose the fact that Epson and HP are selling ever increasing numbers of wide format printer... That department stores like Woolworths and on-line printing filrs like HP's own Snapfish have materialised offering the exact same service Gisle attempted to discredit me for offering... Escapes his attention now that the world in general accepts my algorythms as common place.

I suppose any chance of an appology for the prick is unlikely?

Ryadia.

avatar

Douglas, I think you should try to get a grip on reality.

It has been almost five years (by “attempted to coerce me into providing him the facilities to duplicate my work”, I assume you refer to this offer from September 2004). If your “algorythms” [sic] had any merit, you should have emerged as a successful software entrepreneur by now. The fact that companies like Genuine Fractals are successful, or that digital cameras i 2009 offer a lot more megabytes in 2009 than they did in 2004, has of course nothing to do with your software or your claims in 2004 about having invented interpolation software with magical properties.

I did not call you a fraud back in 2004. I just offered you a fair chance to prove your extraordinary claim – an offer you choose to not follow up on, giving the bogus explanation that if you supplied me with a file to examine, I would be able to steal your secret method.

I certainly do not owe you an “appology” [sic]. And I think the nearly five years that has passed without any software product based upon your work materializing makes this the time to finally call it: Douglas, you are a fraud.

avatar
Interpolation

WILL THIS TYPE OF SOFTWARE HELP INCREASE RESOLUTION, NOISE, THERE FOR A LARGER PRINT CAN BE MADE.

I HAVE NIKON D200, I USE ONLY 100 TO 400 ASA.

WOULD LIKE TO MAKE GREAT 16 X 20 PRINTS.

THANKS====RUSS

avatar

Yes, interpolation software can help you if you want to make large prints. It will of course not create data out of thin air, but it will hide defects, such as pixelation, that otherwise would result from upsampling.

A Nikon D200 is a 10 Mpx camera with 2592 x 3872 pixels. Printing at 16 x 20 inches works out as 162 ppi. For a good 16 x 20 print, you may need 240 ppi, so you should crop to adjust to 4:5 aspect ratio, and them interpolate your file to be 3840 x 4800 pixels. For best results, shoot RAW and work with an uncompressed file format (e.g. PSD or TIFF). Interpolating JPEG files enlarges JPEG artifacts, which is bad.

Take a look on this page for more about the resolution required for high quality prints.

Leave a comment.

Title (optional):

Comment:

Enter the caracters below into the Verify-field to indicate that you are not a spambot.
To avoid having to enter a verify code, register at the site and log in before posting.
CAPTCHA Image new image 2
Verify code:  (Required.)
Your name:   (Required.)
Your email:   (Will not be published.)
782
This page is from: http://dpanswers.com/content/tech_interpolation.php