CMPUT 604: Programming Assignment# 2 (preliminary version)

Due date: Feb 24, 2006

Max. marks: 100

Background: During wireless transmission it is possible to loose packets. It is therefore important to consider how to best reconstruct a transmitted image if some packets containing information on it are lost. We will study an approach based on image interpolation.

Image interpolation: There are many ways of interpolating images. We will discuss two simple ones --- nearest neighbour and bi-linear interpolations.

Let I(i, j),0iM, 0jN be an image where the values at some locations may be missing. In nearest-neighbour interpolation, the value of a missing pixel I(x, y) is set to the value of the closest non-missing pixel. In bi-linear interpolation, we need to identify 4 of the nearest neighbours of a pixel (x, y), and then estimate the value at (x, y) as an inverse-distance weighted function of the neighboring values. Consider a simple example where the 4 nearest neighbours of (x, y) with pixel values are (x-1, y-1), (x-1, y+2), (x+1, y-1) and (x+1, y+2). In this case the distances from (x, y) to these 4 pixels are respectively d1, d2, d3, and d4. Thus, I(x, y) may be estimated as: d1/(d1+d2+d3+d4)* I(x-1, y-1) + d2/(d1+d2+d3+d4) * I(x-1, y+2) + d3/(d1+d2+d3+d4) * I(x+1, y-1) + d4/(d1+d2+d3+d4) * I(x+1, y+2).

Programming details:

The strategy for transmission and reconstruction is as follows:

1. Create 16 packets representing an image by:

(a) Considering 4 x 4 sub-blocks of the image.

(b) Choosing a unique pixel location from each sub-block to include in a given packet.

2. Simulate packet loss by allowing users to specify a set of lost packets.

3.Using random number generation, determine the set of lost packets given the percentage of packets lost specified by a user of your program.

4. Change the image from RGB color space to YUV color space. The converting formulas are available on MSDN (

Then do 5 in YUV color space.

5. Reconstruct an image after transmission, taking into account the loss of packets, by interpolating missing pixels with:

(a) Nearest neighbour interpolation.

(b) Bi-linear interpolation.

6. Change the image from YUV color space to RGB color space. Then do 7 in RGB color space.

7. Calculate the Mean Square Error (MSE) of the reconstructed image for the methods in 5 (a) and 4 (b), in different lost packets scenarios, and complete the following two tables (the test image is pig_and_tiger.jpg):

Method
Lost packets / Nearest neighbour interpolation / Bi-linear interpolation
0
0-1
0-2
0-3
0-3
0-4
0-5
0-6
0-7
0-8
0-9
0-10
0-11
0-12
0-13
0-14

Table 1: MSE in different lost packets scenarios, with different interpolation methods

Method Packet lost rate / Nearest neighbour interpolation / Bi-linear interpolation
10%
20%
30%
40%
50%
60%
70%
80%
90%

Table 2: MSE in different lost packets scenarios, based on randomly selecting lost packets, with different interpolation methods

Complete Table 1 and Table 2.

8. Outline the algorithm you use to compute the nearest neighbour and the 4 nearest neighbours. What is the complexity of your algorithm?

9. Marks depend on Efficiency, Code Clarity and Documentation/Comments.

10. An example code (ImgInterp.java) is provided. It can do image interpolation but cannot do color space transformation. It does NOT guarantee to be correct. You can use this program as a part of your code. If you decide to do so, you shall read the code and understand it at first. You TA (taowang) will NOT answer any questions about this program. Reading and understanding code is an important skill of CS students.

11. Grads: Email your code, documentation and test result summary to

.