Ch1 - Introduction

Overview
History
Image Sources
Applications
Image Interpolation
Image Quantization

Conclusion

Image Interpolation
Image interpolation is used to change the X
and Y dimensions of an image
Different techniques can be used depending on
speed and accuracy trade offs
We will start with methods that increase or
decrease size by a factor of two
We will then discuss image interpolation
techniques that can work for any size change

Image Interpolation
Point sampling used to quickly interpolate an
image down to half the size in x and y
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
Output[y][x] = Input[y*2][x*2];

Pro fast and easy to implement

Image Interpolation
Point sampling example:
10 11 12 13
15 16 17 18

10 12

20 21 22 23

20 22

25 26 27 28

Image Interpolation
Local averaging use average of 2x2
neighborhood to calculate output pixels
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
Output[y][x] = ( Input[y*2][x*2] + Input[y*2+1][x*2]
+ Input[y*2][x*2+1] + Input[y*2+1][x*2+1] ) / 4;

Pro uses all image data

Image Interpolation
Local averaging example:
10

11

12

13

15

16

17

18

13

15

20

21

22

23

23

25

25

26

27

28

Image Interpolation
Local averaging example:

Image Interpolation
Point sampling example:

Image Interpolation
Pixel replication repeat values to double the
size of an image
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
Output[y][x] = Input[y/2][x/2];

Pro very easy to implement

Image Interpolation
Pixel replication example
3

11

11

11

11

11

Image Interpolation
Midpoint interpolation use values half way
between adjacent pixels to fill in output pixels
Pro results in smoother output image
Con uses more additions and divisions
Con must handle last row and column as a
special case (typically using pixel replication)

Image Interpolation
for (int y=0; y<InYdim; y++)
for (int x=0; x<InXdim; x++)
{
int x_out = x*2;
int y_out = y*2;
Output[y_out][x_out] = Input[y][x];
// interpolate right
if (x+1 < InXdim)
Output[y_out][x_out+1] = (Input[y][x]+Input[y][x+1])/2;
else
Output[y_out][x_out+1] = Input[y][x];

Image Interpolation
// interpolate down
if (y+1 < InYdim)
Output[y_out+1][x_out] = (Input[y][x]+Input[y+1][x])/2;
else
Output[y_out+1][x_out] = Input[y][x];
// interpolate diagonal
if ((x+1 < InXdim) && (y+1 < InYdim))
Output[y_out+1][x_out+1] = (Input[y][x]+Input[y+1][x+1])/2;
else
Output[y_out+1][x_out+1] = Input[y][x];
}

Image Interpolation
Midpoint interpolation example
3

11

11

Image Interpolation
Midpoint interpolation example
3

11

11

Image Interpolation
Midpoint interpolation example
3

11

11

Image Interpolation
Midpoint interpolation example
3

11

10

11

Image Interpolation
Midpoint interpolation example
3

11

10

11

11

11

11

Image Interpolation
Midpoint interpolation example:

Image Interpolation
Pixel replication example:

Image Interpolation
Nearest neighbor interpolation a generalized
version of point sampling can be used to
interpolate images up/down to any size
Calculate floating point location of input pixel
Use rounding to get closest integer value
Same as point sampling when OutDim = InDim/2
Same as replication when OutDim = InDim*2
Pro fast and easy to implement
Con data loss or block artifacts

Image Interpolation
float Xscale = (float) (InXdim-1) / (float) (OutXdim-1);
float Yscale = (float) (InYdim-1) / (float) (OutYdim-1);
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
int x_int = (int)(0.5 + x * Xscale);
int y_int = (int)(0.5 + y * Yscale);
if ((x_int < InXdim) && (y_int < InYdim))
Output[y][x] = Input[y_int][x_int];
else
Output[y][x] = 0;
}

Image Interpolation
Bilinear interpolation a generalized version
of midpoint interpolation can be used to
interpolate images up/down to any size
Calculate floating point location of input pixel
Use distance weighted average of adjacent pixels
to obtain output pixel value
Pro more accurate than nearest neighbor
Con slower and more complex to implement

Image Interpolation
// interpolate in x
E = (1-) A + B
F = (1-) C+ D

A
M

// interpolate in y
M = (1-) E + F

1-
C

1-
F

Image Interpolation
// interpolate x and y
M = (1-) (1-) A
+ (1-) B
+ (1-) C
+D

A
M

1-
C

1-
F

Image Interpolation
float Xscale = (float) (InXdim-1) / (float) (OutXdim-1);
float Yscale = (float) (InYdim-1) / (float) (OutYdim-1);
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
// calculate interpolation weights
float x_float = x * Xscale;
float y_float = y * Yscale;
int x_int = (int) x_float;
int y_int = (int) y_float;
float delta_x = x_float x_int
float delta_y = y_float y_int;

Image Interpolation
// interpolate between four input pixels
if ((x_int+1 < InXdim) && (y_int+1 < InYdim))
Output[y][x] = ( Input[y_int][x_int] * (1-delta_x)*(1-delta_y)
+ Input[y_int][x_int+1] * (delta_x)*(1-delta_y)
+ Input[y_int+1][x_int] * (1-delta_x)*(delta_y)
+ Input[y_int+1][x_int+1] * (delta_x)*(delta_y) );
// handle boundary cases
else if ((x_int < InXdim) && (y_int < InYdim))
Output[y][x] = Input[y_int][x_int];
else
Output[y][x] = 0;
}

Image Interpolation
Bilinear interpolation example

Left = 180x300
Top = 300x180

Image Interpolation
Nearest neighbor example

Left = 180x300
Top = 300x180

Image Interpolation
Difference images

Left = 180x300
Top = 300x180

Image Interpolation
We have seen six different methods for image
interpolation, each with their own pros/cons:
Point sampling
Local averaging
Pixel replication
Midpoint interpolation
Nearest neighbor interpolation
Bilinear interpolation

Image Interpolation
Implementation reminders:
looping over all output pixels avoids the potential
for gaps in output image
handle border of images carefully and perform
array bounds checking as needed
consider relative speed/accuracy of integer and
floating point operations
make sure you correctly truncate and round
floating point variables

Image Quantization
The number of intensity values for each pixel
is determined by the quantization level
Typical images are 8-bits/pixel (256 levels) or
24-bits/pixel (256 levels for RGB)
We can lower storage requirements by
reducing the quantization level
This section will discuss several quantization
techniques and their visual effects

Image Quantization
Image quantization can be implemented in a
number of ways:
The easiest method is to multiply input pixels by a
scale factor and round to the nearest integer
To go from 256 levels to 64 levels, we multiply by
scale factor of 64.0/256.0 = 0.25
We can get the same effect by dividing by 4 or by
shifting pixel values right by 2-bits
Clearly information is lost as we quantize

Image Quantization
Lenna quantized to 256 and 64 grey levels

Image Quantization
Lenna quantized to 32 and 16 grey levels

Image Quantization
// calculate scale factor
int InLevels = 256;
int OutLevels = 64;
float Scale = (float) (OutLevels) / (float) (InLevels);
// perform image quantization
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
Output[y][x] = (int)(Input[y][x] * Scale);
}

Image Quantization
// calculate scale factor
int InMin = 0, InMax = 255;
int OutMin = 0, OutMax = 63;
float Scale = (float) (OutMax-OutMin+1) / (float) (InMax-InMin+1);
// perform image quantization
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
Output[y][x] = (int)(0.5 + OutMin + (Input[y][x]-InMin) * Scale);
}

Image Quantization
// calculate scale factor
int InMin = 0, InMax = 255;
int OutMin = 0, OutMax = 63;
float Scale = (float) (OutMax-OutMin) / (float) (InMax-InMin);
// perform image quantization
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
if (Input[y][x] < InMin) Output[y][x] = OutMin;
else if (Input[y][x] > InMax) Output[y][x] = OutMax;
else Output[y][x] = (int)(0.5 + OutMin + (Input[y][x]-InMin) * Scale);
}

Image Quantization
Non-uniform image quantization can be
performed using a lookup table:
Allocate a lookup table based on number of
intensity levels in input image
Initialize the lookup table to have the desired
output pixel values
Loop over input image to assign quantized values
to the output pixels

Image Quantization
// allocate lookup table
int InMin = 0, InMax = 255;
int InRange = InMax-InMin+1;
int *Lookup = new int[InRange];
// initialize lookup table
int Stretch = 8;
for (int level = 0; level < InRange; level++)
Lookup[level] = (int)(0.5 + Stretch * sqrt((double)level) );

Image Quantization
// perform image quantization
for (int y=0; y<OutYdim; y++)
for (int x=0; x<OutXdim; x++)
{
Output[y][x] = Lookup[ Input[y][x]-InMin ];
}
// free memory
delete [] Lookup;

Image Quantization
Lenna quantized using sqrt lookup table

original 256 levels

scale = 8

Image Quantization
Lenna quantized using sqrt lookup table

scale = 2

scale = 1

Image Quantization
The choice of quantization lookup table has a
huge effect on the resulting output image
We can increase/decrease the visibility of
image features in different intensity ranges
We can also maximize the information per bit
in each pixel to assist in image compression

Conclusions
Digital images come from many sources and
can be used for a wide range of applications
Processing digital images is done by
manipulating 2D arrays of pixel values
Image processing operations can be
implemented in different ways to improve
speed and/or accuracy