IMAGE Team - The Pantheon project

Tutorial: Image Rescaling

Identification

Resources

Introduction

Rescaling or resampling is the technique used to create a new version of an image with a different size. Increasing the size of the image is called upsampling, and reducing the size of an image is called downsampling.

It turns out that these operations are not lossless. For example, if you downsample an image and then upsample the resulted image, you will get a sightly different image than the original. This is a non trivial process that involves a trade-off between efficiency, smoothness, sharpness and speed. That's why there exist different algorithms.

Pandore supports several different algorithms to perform resampling. Each of them have their own advantages and drawbacks in terms of lossless, blur, and speed.

We present here a list of examples that use the Pandore operators to realize the resampling. We distinguish the case of image downsampling and image upsampling because the algorithms can have different performance in each case.

I. Upsampling

I.1. Upsampling of Color or Grayscale Image

Image upsampling is illustrated with the small image below which is magnified by 400% (x4).

Nearest Neighbor Resampling Bilinear Resampling
prescale 4 4 0 jellybeans.pan result.pan
Temps: 0.036s
plinearrescale 4 4 0 jellybeans.pan result.pan
Temps: 0.086s
Hermite Resampling Bell Resampling
phermiterescale 4 4 0 jellybeans.pan result.pan
Temps: 0.099s
pbellrescale 4 4 0 jellybeans.pan result.pan
Temps: 0.077s
Mitchell Resampling Bicubic Resampling
pmitchellrescale 4 4 0 jellybeans.pan result.pan
Temps: 0.189s
pbicubicrescale 4 4 0 jellybeans.pan result.pan
time: 0.106s
Lanczos Resampling
planczosrescale 4 4 0 jellybeans.pan result.pan
Temps: 1.49s

I.2. Upsampling of Binary Image

Image upsampling is illustrated with the small image below which is magnified by 400% (x 4).

Nearest Neighbor Resamplingn Bilinear Resampling
prescale 4 4 0 binarysmall.pan result.pan
Temps: 0.004s
plinearrescale 4 4 0 binarysmall.pan result.pan
Temps: 0.019s
Hermite Resampling Bell Resampling
phermiterescale 4 4 0 binarysmall.pan result.pan
Temps: 0.012s
pbellrescale 4 4 0 binarysmall.pan result.pan
Temps: 0.012s
Mitchell Resampling Bicubic Resampling
pmitchellrescale 4 4 0 binarysmall.pan result.pan
Temps: 0.043s
pbicubicrescale 4 4 0 binarysmall.pan result.pan
time: 0.022s
Lanczos Resampling
planczosrescale 4 4 0 binarysmall.pan result.pan
Temps: 0.302s

II. Downsampling

II.1. Downsampling of Color or Grayscale Image

Image downsampling is illustrated with the image below which is reduced by 400% (x 0.4).

Nearest Neighbor Resampling Bilinear Resampling
prescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.008s
plinearrescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.044s
Hermite Resampling Bell Resampling
phermiterescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.073s
pbellrescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.166s
Mitchell Resampling Bicubic Resampling
pmitchellrescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.477s
pbicubicrescale 0.4 0.4 0 whiteboard.pan result.pan
Temps: 0.049s
Lanczos Resampling
planczosrescale 0.4 0.4 0 whiteboard.pan result.pan
Temps:6.616s

II.2. Downsampling of Binary Image

The various algorithms are applied to the binary image below which is reduced by 400% (x0.4).

Nearest Neighbor Resampling Bilinear Resampling
prescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.006s
plinearrescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.006s
Hermite Resampling Bell Resampling
phermiterescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.009s
pbellrescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.015s
Mitchell Resampling Bicubic Resampling
pmitchellrescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.037s
pbicubicrescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.006s
Lanczos Resampling
planczosrescale 0.4 0.4 0 binary.pan result.pan
Temps: 0.423s

III. Resampling Algorithms

When an image is scaled up to a larger size, there is a question of what will be the color of the new pixels in between the original pixels. When an image is scaled down to a lower size, the inverse question is what will be the color of the remaining pixels. There exists several answers to these questions.

To simplify the presentation, consider the case of an 1D image f(x) that we want to magnify by a factor of 2 to create the new image g(x). Mathematically, this is formulated as:

	g(x) = f(x/2)

Consider a concrete example for f(x) with the sample values [2, 3, 5, 4, 3, 2, 4]. This provides the image here-after (where the image is represented by its profile, the gray levels are visualized in height):

We want to double the size of the image f(x) to create the image g(x) 

Therefore, we have to determine what will be the value of the new pixels.

There are two obvious answers:

One may wonder which of the previous method is "best". The answer is "it depends". In case of intensity image, the second solution is the best one because the first produces blocky effects whilst the second produces a smoother image. However, in case of region maps, the first solution is the only possible solution since the first one add new labels.

III.1. Resampling by convolution

Before considering the 2D, we examine a less intuitive but more general way to implement these methods: convolution. The convolution defines a general principle for the interpolation. The interpolation kernel k(i) defines the list of neighbors to be considered and the weight assigned to them for calculating the value of the central pixel. Mathematically, this corresponds to the operation:

By choosing the suitable filter, we can define different types of reconstruction. For example, the nearest neighbor interpolation with left priority to double the size is implemented by the convolution kernel [1, 1, 0]. Linear interpolation can be implemented by the kernel [0.5 1 0.5]. For other distances, we just use other kernels. For example, the nearest neighbor kernel for size tripling is [0, 1, 1, 1, 0] and the linear interpolation kernel is [1/3, 2/3, 1, 2/3, 1 / 3].

To illustrate the principle of interpolation with a convolution kernel, consider the case of the bilinear kernel for size doubling. The first is to double the size of f(x). Then the new pixels is set to 0 to produce the image f'(x). From there, convolution is applied to produce g(x). Thus, the value at the coordinate 6 is: 1*34+0*2/3+0*1/3+0*2/3+0*1/3.

The value at the coordinate 7 is: 39 = 1/3*50 + 2/3*34.

This implementation by convolution has several advantages:

III.2. A variety of kernels

Within the convolution framework, it is easy to vary the types of kernel and thus the type of interpolation. As we saw earlier, the simplest kernel is the nearest neighbor kernel, which corresponds to a box. It produces images with blocky effect.

Linear interpolation use a convolution kernel k(x) which has the shape of a triangle. The output image thus has a smoother surface because the discretization is less strong.

But the transition betwen two pixels can be smoother if curve is used instead of straight line.

In general, B-splines are used to model the transition between two original pixels. The B-spline curves are described by a series of polynomials with a given degree. The higher the degree, the higher the variations in the curve.

A B-spline of degree 1 is formed by a series of straight lines, and therefore corresponds to a bilinear kernel. A B-spline of degree 2 is composed of a series of parabolic curves and B-spline of degree 3 is composed of cubic curves.

III.3. Extension to other dimensions

The previous description done for 1D can easily be extended to 2D and 3D. The only difference is that convolution is performed along the x, y and z axis. For example the following formulae is used for 2D interpolation:

The different kernels developed in Pandore for 2D and 3D images are described in the following sections.

III.4. Nearest Neighbor Resampling (also called Box Resampling)

The color of a pixel in the result image is the color of the nearest pixel of the original image. If we enlarge an image by 2, one pixel will be enlarged to 2x2 area with the same color. If we shrink an image by 2, only 1 pixel over 2x2 pixels is retained in the output image. The interpolation kernel k(x) is simply:

   k(x) = | 1 ; if |x| < 0.5
          | 0 ; otherwise 

This operator produces blocky effects on result in case of upsampling and removes thin edges in case of downsampling. However, it is the fastest algorithm and it is the only one that does not insert new colors in the result.

III.5. Bilinear Resampling (B-spline order 1)

Bilinear sampling considers the closest 2x2 neighborhood of known pixel values surrounding the unknown pixel. It can be implemented by the triangle kernel k(x):

   k(x) = | 1-|x| ; |x| < 1
          | 0 ; sinon

III.6. Bell Resampling (B-spline order 2)

Bell resampling uses a convolution kernel to interpolate the pixels of the input image in order to calculate the pixel values of the output image. The Bell convolution kernel k(x) is defined as:

          | 0.75-|x|2 ; if |x| < 0.5
   k(x) = | 0.5 * (|x|-1.5)2 ; if 0.5 < |x| <1.5
          | 0 ; otherwise 

III.7. Hermite Resampling (B-spline order 3)

Hermite resampling uses a convolution kernel to interpolate the pixels of the input image in order to calculate the pixel values of the output image. Hermite is a particular case of the bicubic algorithm, where a=0. The Hermite convolution kernel k(x) is defined as:

   k(x) = | 2|x|3 - 3|x|2 + 1 ; if |x| ≤ 1
          | 0 ; otherwise

III.8. Bicubic Resampling (B-Spline order 3)

For bicubic resampling, the convolution kernel is composed of piecewise cubic polynomials. The output pixel value is a weighted sum of pixels in the nearest 4-by-4 neighborhood. The kernel is k(x):

          | (a+2)|x|3 - (a+3)|x|2+1 ; if x ≤ 1
   k(x) = | a|x|3 - 5a|x|2 +8a|x| - 4a ; if 1 < x < 2
          | 0 ; otherwise

where a=-0.5 in the present implementation. Note that if a=0, the algorithm is equivalent to the Hermite algorithm.

It is probably the most used of the resampling algorithm in image manipulation software programs.

III.9. Mitchell Resampling (B-Spline order 3)

Mitchell resampling uses a convolution kernel to interpolate the pixels of the input image in order to calculate the pixel values of the output image. It is also a bicubic filter.

The Mitchell convolution kernel k(x) is defined as:

          | 1/6. [ ((12-9B-6C)|x|3 + ((-18+12B+6C)|x|2 + (6-2B)) ]; if |x| < 1
   k(x) = | 1/6. [ ((-B-6C)|x|3 + (6B+30C)|x|2 + (-12B-48C)|x|2 + (8B+24C) ]; if 1 ≤ |x| < 2
          | 0 ; otherwise 

where B=1/3, and C=1/3.

III.10. Lanczos Resampling

Lanczos resampling uses a convolution kernel to interpolate the pixels of the input image in order to calculate the pixel values of the output image. The Lanczos convolution kernel k(x) is defined as:

   k(x) = | sinc(x).sinc(x/a) ; if |x| < a
          | 0 otherwise 

where a=3 in the present implementation.

This algorithm provides the best results, however it is extremely time-consuming.


The Pantheon project
Image Team GREYC Laboratory
UMR CNRS 6072 - ENSICAEN - University of Caen, France
This page was last modified on 08 September 2017