Geometric Interpolation of Images

Problem Statement

In many applications, we need to work with a continuous image (i.e., one whose domain is the Euclidean plane R2) or at least an image with arbitrary fine resolution. But in practice, images are discrete, say with domain given by the integer grid Z2. There are many standard ways to transform a continuous image from a discrete image. We are interested in a class of transformations that may be called geometric as each is based on specifying a geometric shape S that is convex and symmetric about the origin. Here is how the geometric transformation works. Let the discrete image be

I: Z2 → [0,1].
Our goal is to define a continuous image
JS: R2 → [0,1].
for any suitable shape S. If |S| is the area of S, then the box function BS: R2 → [0,1] is defined by BS(x,y)= 1/|S| when (x,y) is in S, and BS(x,y)= 0, otherwise. Let J0 be the continuous image J0: R2 → [0,1] where
J0(x,y) = I(x + 0.5], y + 0.5]),
and [x] is the integer part of a real value x. The desired image JS is just the convolution of J0 with the function BS

The well-known bilinear interpolation scheme corresponds to the case where S is the unit square. We implemented the case where S is a circle of unit area. Here is a picture of how JS is computed when (x,y) is at a grid point.

This algorithm is relatively simple and efficient, and may be a useful alternative to bilinear interpolation. Here is the source for our program (called disc) in C/C++. An implementation of bilinear interpolation is also included. The running time of the bilinear program is 3 times faster than our disc program. Here is a short note describing the implementation and experiments.

Our applications need an extension of this algorithm to allow blurring at larger scales. This could be achieved by letting S to be a disc of any size. Unfortunately, such an algorithm would be more complicated to implement. Instead, we propose to "iterate" the algorithm for the case of unit area disc. This seems to have nice properties, as the following images show. Here is the original image,

taken from a larger map. We iterated our algorithm on this image five times. Each time, our algorithm expands an input pixel to an 8 x 8 block for interpolation, then then reduces it back to the original size before output. We also do the same experiment with the bilinear algorithm. The main thing to note at the end is that the diffusion rate is quite small while achieving the main objective of removing jaggies and uneven texture:

Original (x 8) .

First Disc Iterate .

First Bilinear Iterate.

Fifth Disc Iterate.

Fifth Bilinear Iterate.