Posts Tagged ‘interpolation’

More on interpolation in bitmaps

Hi folks,

Today we are going to provide some more details on interpolation algorithms, not because we intend to annoy you with mathematics but just as an attempt to offer simple explanations to terms you might have encountered and puzzled you in imaging and photo processing documentations.
Or at least to give you a clue on the complexity that lays behind even very basic PaperScan bitmap handling features you are frequently and easily using, such as resizing an image/changing its dpi, rotating it at any angle you want or using the magnifier tool.

As shortly explained in a previous article, interpolation is a mathematically-based “guess” for determining new, unknown values to be placed in between known values (as opposed to extrapolation, when new values are guessed for outside the range of the known values).
Quick example: we know the air temperatures at 6:00 AM and at 10:00 AM and need to figure out a best guess for the temperature at 8:30 AM (interpolation) or at 11:45 AM (extrapolation).
In bitmaps, interpolation is required for example when scaling an image (more obvious when enlarging it) or when rotating an image with an angle, because bitmaps are a given, fixed grid of pixels and therefore resolution-dependent.
Being an approximation process, there will always be some loss of quality when interpolation is performed, the results depending on the interpolation algorithm used.

As mentioned before, among the many existing methods there are 3 commonly used algorithms for bitmap image interpolation: nearest-neighbor, bilinear and bicubic.

1) Nearest neighbor algorithm is the simplest of them all.
An image is worth a thousand words, so take a look here : the original image (left) is 4×4 pixels, the 100% upscaled grid (middle) is 8×8 pixels, showing the to-be-created (with color value to be determined), “empty” pixels as black, for ease of understanding.
Now start from upper-left corner going to the right and assign to each “empty” (black) pixel the same color as its nearest known neighbor and, after finishing a row, go to the next one under it until completing all of them.
The resulting grid is shown on the right and you have just performed (mentally) a nearest-neighbor interpolation!
It is simple, blazing fast but only makes each original pixel bigger so how about seeing its shortcomings? Here you go: http://photoenlargement.imagener.com/images/nn.jpg

2) Bilinear algorithm is “smarter”:
Instead of simply replicating the nearest pixel, it takes into account the closest 2×2 neighborhood of known pixels that surrounds the “empty” (to-be-created) pixel.
It then determines the new (interpolated) value by calculating the average of these 4 known pixels, weighted according to their relative distance to the to-be-created pixel.
Resulting images are much smoother compared to those obtained by nearest-neighbor method.

3) Bicubic algorithm is more complex than bilinear and, because it offers very good quality of output in a short enough processing time, it became a standard for image editing software, as well as for printer drivers.
Bicubic method takes into account 16 (4×4) known pixels located closest to the “empty” one, whose color value is to be determined.
That value will still be a weighted average and the closer a known pixel is, the more weight he will get in the calculation.
This is the most accurate interpolation method of the 3 presented here providing a smooth and sharp output which explains its wide adoption.
If you kept all 3 sample images (links provided above) in separate browser tabs, you can easily compare and see the differences between algorithms.
Note that any algorithm’s efficiency is limited so, when pushed beyond a certain margin, it will start producing lesser and lesser quality output.

As a conclusion to this article, each time you zoom, resize, rotate, crop a zone of a bitmap to another resolution or print, remember the result is “artificial” and, despite the ease of use, it is obtained by non-trivial methods.
Interpolation is a nice thing (and it has a cool name, too), but best idea for your valued images/photos would be to adjust initial resolution settings so you will need it as rarely as possible.

See you next week!

Bogdan

Big Browser on May 17

Samsung Faces Same Problem As Apple : Too Much Cash Read article The Windows Kernel Is Slower Than Other Operating Systems. Here Is Why. Read article Is the Linux desktop becoming extinct? Read article The top 6 worst passwords from the Star Trek universe Read article Microsoft: Office won’t go subscription-only any time soon Read article

Casual Friday on May 17

You talking to me?

You talking to me ?"

Bitmaps : some explanations

Hi folks,

As shown in a previous article, all raster (bitmap) files hold information on each and every pixel in the grid that makes an image.
Today we are going to describe some consequences of this storage principle and, hopefully, we will shed some light on some related, “esoteric” terms.

First, all bitmap images are rectangular, as there has to be a grid (vector images, being defined by mathematical equations not by pixels, aren’t “restricted” to rectangular shape)

Secondly, bitmaps are resolution-dependant.
That means the bitmap stores information on a given (fixed) number of pixels only.
If you want to rescale the image to a lower resolution, some pixels from the original grid will have to be discarded while rescaling to higher resolution means new pixels (not existing in the original grid) need to be created.
Down-scaling a bitmap (for example when creating a thumbnail) produces far less damages to the quality of the image as opposed to up-scaling it.
So let’s take a closer look at the up-scaling case: zooming-in a bitmap image (in order to get a better view on details or to enlarge the image) won’t reveal new information at all, because such information simply isn’t there, the bitmap contains information only for the given number of pixels and that’s it.
And beyond a certain threshold, each discretely visible pixel composing the original image will became a bigger and bigger rectangle, altering the image more and more.
To reduce (eliminating is impossible) this upscaling problem, new pixels are created based on original pixels color information and this process of estimating new intermediary values from known existing values is called “interpolation“.
There are several interpolation algorithms, 3 of which are most commonly used: “nearest-neighbour“, bilinear and bicubic interpolations.
Nearest-neighbour is is the most simple but less effective interpolation method, producing jagged edges (looking like stairs) on increased-sized image while bicubic is much more complex and generates smoother straight-lines and curves.
But in the end of the day, no matter their complexity, all algorithms are creating the new pixels by some more or less reasonable aproximation or “educated guess“, so to speak.

Resolution-dependency of bitmaps imposes for another important aspect to be discussed: screen and printer rendering.
This subject contains many confusing terms, some of them commonly misused, so we will dedicate our next blog article entirely to that matter, in an attempt to untangle frequent confusions.

A fourth thing about bitmaps is about converting a bitmap format to another one and is actually good news.
As they are all based on the same encoding principle (storing information on all pixels in the image) conversion between different bitmaps file formats is rather easy.
Most popular bitmap formats are non-proprietary (have open specifications) like PNG, TIFF, JPEG or GIF.
BMP format was invented by Microsoft but being a relatively simple, well documented and free of patents format, it became quite a common raster image format.

See you next week, folks!

Bogdan

Big Browser on April 26

Apple and Volkswagen team up on iBeetle, but it's no iCar Read article No-ads messaging app, WhatsApp, has more users than Twitter Read article Samsung Demos a Tablet Controlled by Your Brain Read article Better Testers Read article Remember when AMD could compete with Intel in both speed and price? Read article

Casual Friday on April 26

How To Scare Your Neighbors