CMPUT 414/604: Assignment# 2
Due date: Feb.15th , 2005
Weight: 4% of final grade
1 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.
2 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), 0 i < M, 0 < i < N 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-distanceweighted function of the neighbouring 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 1.414, 2.236, 1.414, and 2.236. The inverse of these distances are 0.707, 0.447, 0.707, 0.447. Thus, I(x, y) may be estimated as: 0.306 I(x-1, y-1) + 0.194 I(x-1, y+2) + 0.306 I(x+1, y-1) + 0.194 I(x+1, y+2).
3 Programming details
1. Implement GUI to display images and include necessary interaction by Java.
The strategy for transmission and reconstruction is as follows:
2. Load an image at: http://www.cs.ualberta.ca/~lihang/Campus/c414/assignment/asn2/
(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.
3. Simulate packet loss by allowing users to specify a set of lost packets.
4. GRAD STUDENTS ONLY: Using random number generation, determine the set of lost packets given the percentage of packets lost specified by a user of your program.
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. Calculate and display the Mean Square Error (MSE) of the reconstructed image for the methods in 4 (a) and 4 (b).
7. Outline the algorithm you use to compute the nearest neighbour and the 4 nearest neighbours. What is the complexity of your algorithm?
8. Marks depend on Efficiency, Code Clarity and Documentation/Comments.
4 Submission
l Undergrads: Email your code, documentation and test result summary to .
l Grads: Email your code, documentation and test result summary to .