Saturday, June 15th, 2013
Imagine is an image processing framework that I began writing in 2009. The framework makes it easy to load, manipulate, and analyze images and perform lots of common tasks. I've used imagine in several of my projects involving graphics, games, computer vision, and artificial intelligence. There are a lot of components in the framework that we could cover in this post, but I'd like to focus on one particular area: image resampling.
Definition: Image resampling is the process of resizing an image by sampling it at discrete intervals. This process typically produces a higher quality result than basic scaling
because it uses more sophisticated processing and may perform sub-pixel interpolation to improve visual quality.
Imagine offers a number of different options for resampling, each with their own benefits and trade-offs. Before we step through each of the resampling kernels in
greater detail, let's take a quick look at their results. Resampling always involves one of two operations: magnification (making images bigger), or minification (making them smaller).
Most kernels are better at one of these than the other.
Our original image is 256x192 pixels. Each kernel is run on this image to magnify it up to 1024x768. We then take the center region of each image for presentation and comparison. Click on an image to see the full size result.
Original (256x192)
Nearest (1024x768)
Average (1024x768)
Bilinear (1024x768)
Bicubic (1024x768)
Catmull-Rom (1024x768)
Mitchell-Netravali (1024x768)
Lanczos-1 (1024x768)
Lanczos-3 (1024x768)
Lanczos-5 (1024x768)
Gaussian (1024x768)
Cubic B-Spline (1024x768)For minification we run each kernel to reduce the original image down to 64x48 pixels. We then render it with a 4x zoom for presentation and comparison here.
Original (256x192)
Nearest (64x48)
Average (64x48)
Bilinear (64x48)
Bicubic (64x48)
Catmull-Rom (64x48)
Mitchell-Netravali (64x48)
Lanczos-1 (64x48)
Lanczos-3 (64x48)
Lanczos-5 (64x48)
Gaussian (64x48)
Cubic B-Spline (64x48)For the remainder of this post we'll walk through the supported sampler kernels in detail. Also, don't forget to check out the accompanying source code.
Nearest Kernel
NearestKernel simply selects the requested pixel closed to the specified coordinates from
the source image and places it within the output buffer.
More formally, our 1D kernel is defined as:
{ image( floor( x ) ) for x - floor(x) < 0.5
f(x): {
{ image( floor( x ) + 1 ) otherwise
Pros:
o: Speed -- this is one of the fastest kernels in the library
o: Preservation of noise distribution
Cons:
o: Results in obvious blocking artifacts due to strong discontinuities created when
resizing or rotating the image
o: No sub-pixel estimation
Bilinear Kernel
BilinearKernel performs three weighted average computations in order to interpolate four
pixels from the source image and produce the output pixel value.
The 2D kernel is defined as:
x1 = floor( x ) f11 = image( x1, y1 )
x2 = x1 + 1 f12 = image( x1, y2 )
y1 = floor( y ) f21 = image( x2, y1 )
y2 = y1 + 1 f22 = image( x2, y2 )
fy1 = f11 + [ ( f21 - f11 ) / ( x2 - x1 ) ] * ( x - x1 )
fy2 = f12 + [ ( f22 - f12 ) / ( x2 - x1 ) ] * ( x - x1 )
f( x, y ) = fy1 + [ ( fy2 - fy1 ) / ( y2 - y1 ) ] * ( y - y1 )
Pros:
o: Noticable improvement over NearestKernel
o: Reasonable quality when resizing to 4x or 1/4th the resolution. For this reason,
it is implemented in most modern GPUs and used for real-time bilinear texture
sampling.
Cons:
o: Poor preservation of image detail (may blur the image)
o: Strong aliasing artifacts when resizing or rotating an image
Average (Coverage) Kernel
CoverageKernel attempts to balance the benefits of the bilinear kernel with that of the
nearest kernel, while also providing a quality improvement over both.
The kernel attempts to calculate, for each destination pixel, the set of source pixels
that should contribute to it. For each of these source pixels, a weight is determined
based on the percentage of the destination pixel that is covered by the source pixel.
For minification operations, this kernel effectively performs a distance based weighted
average over the set of contributing source pixels. For magnification, the kernel performs
a nearest sampling if the destination pixel is fully covered by a single source pixel,
and (bi)linear interpolation otherwise.
This kernel is designed for image resizing operations and generally performs better than
the bilinear kernel for minimization.
Note that when filtering 2D images with this kernel the processing should occur in two
passes whenever possible as it will generate a higher quality result than a single combined
pass.
Pros:
o: Much faster than the more expensive cubic kernels, with speed roughly equivalent to
that of the bilinear kernel.
o: The kernel will copy source data to a destination image if no resizing is requested.
o: For minification, the kernel typically reduces jagged edges better than nearest
and bilinear kernels, and may not discard as much (high frequency) information.
o: For magnification, the kernel decides whether to directly sample a source pixel
(if the kernel deems its coverage to be 100%), or to interpolate
Cons:
o: During minification, the kernel may overly blur the image.
Bicubic (Generic)
BicubicKernel samples the surrounding sixteen pixels in an image and computes a
weighted average using a 2D cubic function. The shape of the cubic curve has a
dramatic effect on the quality of the kernel.
The kernel is sampled with the following:
{ 6x^3 - 12x^2 + 6 for 0 <= abs( x ) < 1
f(x) = { -6x^3 + 30x^2 -48x + 24 for 1 <= abs( x ) < 2
{ 0 otherwise
Pros:
o: Better reconstruction than bilinear for greater scale changes
Cons:
o: Significantly slower than the linear kernels
o: Produces halo and ringing artifacts
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.
Catmull-Rom Bicubic Kernel
Similar to BicubicKernel, this kernel interpolates 16 source pixels to produce
the output pixel. The cubic function used for this kernel is similar to the following:
{ 9x^3 - 15x^2 + 6 for 0 <= abs( x ) < 1
f(x) = { -3x^3 + 15x^2 -24x + 12 for 1 <= abs( x ) < 2
{ 0 otherwise
Pros:
o: Better reconstruction than bilinear for greater scale changes
o: Sharper results than generic bicubic and bicubic b-spline
o: Fewer halo artifacts than generic bicubic
Cons:
o: B-spline may produce smoother results for certain images
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.
Mitchell-Netravali Bicubic Kernel
Similar to BicubicKernel, this kernel interpolates 16 source pixels to produce
the output pixel. The cubic function used for this kernel is similar to the following:
{ 7x^3 - 12x^2 + 5.33 for 0 <= abs( x ) < 1
f(x) = { -2.33x^3 + 12x^2 -20x + 10.66 for 1 <= abs( x ) < 2
{ 0 otherwise
Pros:
o: Softer results than Catmull-Rom
o: Crisper results than cubic b-spline
Cons:
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.
Cubic B-Spline Bicubic Kernel
Similar to BicubicKernel, this kernel interpolates 16 source pixels to produce
the output pixel. The cubic function used for this kernel is similar to the following:
{ 3x^3 - 6x^2 + 4 for 0 <= abs( x ) < 1
f(x) = { -x^3 + 6x^2 -12x + 8 for 1 <= abs( x ) < 2
{ 0 otherwise
Pros:
o: Quality improvement over linear
Cons:
o: Often results in a significant amount of blurring
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.
Cubic Spline Bicubic Kernel
Similar to BicubicKernel, this kernel interpolates 16 source pixels to produce
the output pixel. The cubic function used for this kernel is similar to the following:
{ 1.5x^3 - 2.5x^2 + 1 for 0 <= abs( x ) < 1
f(x) = { -0.5^3 + 2.5x^2 - 4x + 2 for 1 <= abs( x ) < 2
{ 0 otherwise
Pros:
o: Usually a safe bet for resizing operations
Cons:
o: Non-separable filter (although this may be overridden by applying
two 1D kernels in succession, but the results may deviate from the
intended quality of this kernel.
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.
Lanczos Kernel
This kernel interpolates (2n)^2 source pixels to produce the output kernel, where
n is the sampling radius. The sampling function used for this kernel is similar to
the following:
{ 1 for x = 0
sinc(x) {
{ sin( pi * x ) / ( pi * x ) otherwise
{ sinc(x) * sinc( x / n ) for abs( x ) <= n
f(x) = {
{ 0 otherwise
Pros:
o: Usually a safe bet for resizing operations
Cons:
o: Non-separable filter (although this may be overridden by applying
two 1D kernels in succession, but the results may deviate from the
intended quality of this kernel.
o: Selection of this kernel requires careful testing and comparison
with each particular operator and image.