Welcome to Module 8.2.
One of the first things we do when we
first start playing with a program like
Photoshop and similar is learning how to
translate, re-size or crop an image.
The simple image manipulations can be
described in terms of operators called
affine transforms.
The only problem is that affine transforms
are defined for the continuous space,
whereas here we are in discrete space.
So in order to get the sub-pixel values
that affine transforms require, we usually
employ local interpolation schemes.
And one very popular interpolation scheme
is called a bilinear interpolation and we
will study how that works.
Hi, and welcome to module 8.2, Digital
Signal Processing.
We will take about image manipulations,
and in particular we will consider a class
of transformations called affine
transforms and we will see how to
implement affine transformations for the
class of digital images using the
bi-linear interpolation method.
An affine transform is a mapping that
reshapes a coordinate system.
In our case, we're talking about images so
we're interested in a mapping from r two
to r two.
An affine transform is defined in terms of
a two by two matrix and a translation
vector.
And a new coordinate pair is given by the
multiplication of the matrix times the
original coordinate pair minus the
translation vector.
In compact form we will express it like
so.
Let's look at some examples of affine
transform.
A very simple one is translation.
The matrix here is the identity matrix.
And the translation vector specifies the
new origin of the plane.
So if we have this simple image here, and
we apply a translation, we would get the
simple result.
Scaling is an affine transform, where the
matrix is a diagonal matrix and the
diagonal entries are the amount of
stretching or contraction of each axis
independently.
In this example for instance we have a
scaling where clearly a 1 is equal to a 2
and both are less than 1 because the
resulting image is larger.
Rotation is another refined tranform, we
have seen this before, the sturcture of
the matrix is like so.
We have cos sign of the theta on the
diagonal, and sign of the theta and minus
sign of theta on the anti diagonal.
A pure rotation leaves the origin in
place.
And as an example here's a notation by an
angle theta that is clearly larger than pi
over two.
And here for instance you have a rotation
by pi.
Flips can be both horizontal or vertical
and they simply swap the direction of an
axis.
In both cases the matrix is diagonal and,
in the case of a horizontal flip, the
first element of the diagonal would be
minus one and the second one is one.
Vice-versa for a vertical flip, the second
axis gets flipped and so the second
element of the diagonal would be minus
one.
Here in the image we see a horizontal
flip.
Shear is a stretching of the plane in
either the horizontal or vertical
direction.
For this case of Fourier transform, the
matrix is either upper triangular or lower
triangular.
You have ones on the main diagonal.
And according to whether the shear is
horizontal or vertical, you have a
parameter s on the upper corner or on the
lower corner.
Effective shearing is like so, in this
case you have horizontal shearing where
the horizontal axis is stretched.
If we now try to apply affine transform to
a digital image, we run into a fundamental
problem.
Remember, a digital image lives in
discrete space, in other words, pixel
coordinates Are pairs of integers that
live in z2.
The affine transform on the other hand,
maps these original coordinates onto a
point in r2, which means that the new pair
of coordinates can lie anywhere on the
plane, and in particular, it will most
likely lie in between integer pixel
coordinates.
To understand the situation better, if
this is the regualr grid of pixels in Z
two, and this is the result of the affine
transformation we would like that each
point here on this grid be mapped to a
point on this grid here.
But unfortunately the affine transform
would probably map this point here in
between.
So how do we solve this problem?
The first step is to consider the inverse
transform, so instead of going from the
original image to the destination image.
Here, let me draw it again.We start from
the destination image, for which we know
we want points to lie on the grid and we
compute the originating point from the
original image.
So, if this is the original image This is
a transformed image.
We take each point on the grid and we find
the point it would come from with a
inverse transform.
Now, just like before, this point will not
lie on the original grid, but here is the
second step.
This pair of coordinates we found with
inverse transform, we will express as 2
integer coordinte, eta 1 and eta 2, plus 2
correction factors tau 1 and tau 2 where
tau 1 and tau 2 are strictly less than
one, so it is a sub-pixel correction
factor so again if this is a magnifying
view of the original grid are transformed
gives us a point here will define that
this point t1 and t2 is equal to a point
on a grid data 1 data 2 plus a correction
factor of tau 1 here and a correction
factor, tau 2.
So the question now is how to find the
sub-pixel value here in the middle of the
grid.
And the idea is to interpolate from the
four neighboring pixels.
When the interpolation scheme between
neighbouring pixel is the linear
interpolator, this strategy goes under the
name bilinear interpolation.
So, let's see how this works.
We have our reference point, x of eta 1
and eta 2, and we also have the 3
Neighboring points like so remember are
sub pixel value as computed before falls
here in the middle and it is expressed as
a pixel at a horizontal distance of tow
one and a vertical distance of tow two
from the reference coordinate eta one and
eta two.
So, to compute it's value we first
interpolate in the horizontal direction.
And we find two sub-pixel values at
vertical coordinate eta2 and eta2 plus 1,
both at a distance of tau1 from eta1.
And then, once we have these two values,
we compute a vertical interpolation at a
distance of tau2 like so.
And this gives us our desired value.
With the first order interpolater, the
value is simply a linear combination of
the values of the four pixels that we've
solved before weighted by some factors
that take their distance from the
reference point into account.
One thing that can happen is that when we
compute t1 and t2 as the inverse of affine
transform, we get a value that falls
outside of the support of the original
image.
And in that case we will have to replace
this value with a standard value of
choice, which is usually zero.
You can now try and use the bi-linear
interpolation to compute the shearing of a
standard image, and if we do that we
obtain something like this.