english only
Biomedical Imaging Group
IP-LAB: Image Processing Laboratories
BIG > IP-LAB > Sessions > Interpolation and Geometric Transformation II

# Interpolation and geometric transformation

Java Notes

 Operation Syntax Absolute value y = Math.abs(x); Square root y = Math.sqrt(x); Trigonometric functions y = Math.cos(a); y = Math.sin(a); a in radian Arctan [-π..π] a = Math.atan2(dy, dx); a in radian Returns the closest integer of x y = (int)Math.round(x); Returns the smallest integer of x y = (int)Math.ceil(x); Returns the largest integer of x y = (int)Math.floor(x);

1. Interpolation

We propose, here, to compare three standard methods of interpolation, the nearest-neighbor, the bilinear and the cubic spline interpolation. We use these interpolators in a resize algorithm which is provided in the method resize(). This method is call from the plugin Resize which expects the interpolation type and the scale factor (greater than 1.0 to enlarge the image) as parameter.

Test the interpolation methods on the circle.tif and london.tif images.

1.1 Understanding linear interpolation

The method uses B-spline basis functions of degree one. Read and understand the method getInterpolatedPixelLinear() which return the pixel value of an image at the position (x,y).

1.2 Implementation of the nearest-neighbor interpolation

Simplify the code of the above method to return the nearest-neighbor pixel value at the position (x,y). Write the code in the method getInterpolatedPixelNearestNeigbor().

1.3 Implementation of the cubic spline interpolation

1.3.1. B-spline coefficients

To perform the cubic spline interpolation, you have to implement the pre-filter that computes the B-spline coefficients c(k). A fast implementation is obtained by a cascade of recursive filters as schematized below:

 for the cubic B-splinea = sqrt(3) - 2c0 = 6

The method computeCubicSplineCoeffients() computes the coefficients of an image in the separable way and puts the coefficients into an output image. Your assignment is to write the 1D routine doSymmetricalExponentialFilter() that does the recursive filtering.

First, write the recursion for the causal filter incrementing the index from 1 to n-1; second, write the anti-causal recursion decrementing the index from n-2 to 0. The last step is to multiply the result by co.

To simplify the task, we provide the methods that return the appropriate initial values for the mirror boundary conditions:

cp[0] = computeInitialValueCausal(s, a);,

cn[n-1] = computeInitialValueAntiCausal(cp, a);,

1.3.2. Cubic interpolation

Similar to getInterpolatedPixelLinear(), write the method getInterpolatedPixelCubicSpline() that retrieves the pixel value at the position (x,y) using cubic B-spline interpolation:

Only 4*4 points are necessary to evaluate f(x,y), since β3 has a support in [-2, 2].

To compute an output point you need:

• the 4*4 neighborhood of a point (i,j) that is provided by the method getNeighborhood() of ImageAccess.
double arr[][] = new double[4][4];
coef.getNeighborhood(i, j, arr);

arr[0][0] <- coef(i-1,j-1)
arr[1][0] <- coef(i,j-1)
arr[1][1] <- coef(i,j) ...
• the B-spline basis functions that are given by the getCubicSpline() method and computed as follows (with 0 <= t <= 1):
double w[] = getCubicBSpline(t)
The output is w[0] = β3(t+1), w[1] = β3(t), w[2] = β3(t-1), w[3] = β3(t-2);

1.4. Comparison of interpolators

Compare the quality of the result of each interpolation after reducing the london.tif image to [400, 250] pixels and then enlarging it to the original size.

• Nearest-neighbor
• Bilinear
• Cubic B-spline

We provide a plugin that measures the SNR between the reference (london.tif) and a test image. Put the results in the report.doc.

Note: If you don't succeed in implementing the above methods, you can call the corresponding "solution" methods in your code:

e.g. to implement the getInterpolatedPixelCubicSpline(image, x, y) you call:

double v = InterpolationSolution.getInterpolatedPixelCubicSpline(image, x, y);

2. Application: Unwrap a fisheye picture

 We propose to develop a simple algorithm to unwarp a picture taken with a fisheye lens using the following geometric transformation: ρ' = T(ρ) : ρ' = a.ρ2 + b.ρ + c where ρ is the distance of a pixel from the center of the original image and ρ' is the distance from the center of the transformed image. We fix three constraints to identify the three parameters a, b, c: T(0) = 0, the center does not move; T(m/2) = m/2, the source and unwrapped images are square of size [m,m]; T(m/4) = d*m/4. Here, we are only usig d as free parameter to describe the transformation. Give the corresponding analytical values of a, b, c. Code the routine unwrap() which returns an unwrapped image using the cubic-spline interpolation. The plugin RadialUnwrap calls this routine with a variable parameters d in a range [dmin, dmax] with n steps and produce a stack of unwrapped images. Apply this algorithm to obtain a flat horizon line in the clock.tif image. Give the best value d and insert the resulting image in the report.doc

3. Application: What time is it?

 The goal is to automatically determines the time (hour+minute) in the image whattime.tif. We make the following assumptions: the needles are not overlapping, the center of the watch is on the center of the image and the watch is correcty aligned. Code the routine whatTime() which returns the time as a string. The plugin WhatTime calls the routine and display the resulting string over the image. You can transform the image into polar coordinates using a high-quality interpolation method and make a summation of the intensity value along the radius. The 2 minima in this summation correspond to the angular positions of the needles. From these, you can deduce the number of minutes and hours. Fill in the report.

webmaster.big@epfl.ch • 30.11.2006