MSc in Vision, Visualization and Virtual Environments
School of Computer Studies
Examination Papers/Solutions 1995-1998

1996/7 Exams

1997/8 Exams (original scanned images by Tow-Ann Kew)

AI8 Image Processing, Exam 1997'
Delivered by Dr. Nick Efford

Venue: Sports Hall 1. 2hrs, Attempt three Questions.

Question 1.
(a) Explain how the technique of run length encoding (RLE) gives rise to image compression. [3 marks]
(b) In the 8-bit image below, the grey levels of the dark and bright pixels are 0 and 255, respectively. Calculate the best compression ratio that can be achieved for this image using RLE, assuming that runs can be no bigger than the width of the image. Show all your working.[3]

(c) For certain images, RLE can have unfortunate effect of increasing, rather than reducing, image file sizes. Describe the likely characteristics of such images. [3]
(d) Explain the general principles by which lossy image compression techniques operate. [4]
(e) What are the main advantages and disadvantages of lossy JPEG compression? [4]
(f) A 4-page document is to be scanned, then transmitted from one computer to another using a modem. The scanning process converts each 200mm x 300mm page into an 8-bit greyscale image. The scanner operates at the standard resolution of 95 'dots per inch', giving 30 pixels per cm. The modem transmits data at a rate of 9,600 bits per second. [2]

Question 2.
(a) Give a brief explanation of what is measured by the histogram of a digital greyscale image. [2]
(b) Describe how the histogram of an 8-bit image is calculated. [4]
(c) Is it valid, in general, to say that peaks in the histogram of an image correspond to specific shapes or patterns visible in that image? Explain your reasoning. [3]
(d) An 8-bit image has a minimum grey level of 30 and a maximum grey level of 100. Describe the effects of the following operations on the histogram of this image: (i) Subtraction of 50 from all pixel grey levels. (ii) Exponential mapping of grey level onto the range 0-255 (iii) Histogram Equalisation. [6]
(e) Explain carefully how a grey level mapping that carries out histogram equalisation is derived. [5]

Question 3.
(a) Explain briefly what is meant by the terms 'low pass filtering' and 'high boost filtering', and describe how the appearance of an image changes following these operations. [4]
(b) Give an example of a low pass filter and an example of a high boost filter, each in the form of 3x3 convolution masks. In each case, explain the significance of the mask coefficients you have chosen. [5]
(c) Write down a pair of masks that can convolved with an image to detect grey level gradients in the x and y directions. Suggest a way in which the output from convolution with these masks can be combined to give a directionless measure of gradient magnitudes. [3]
(d) Convolve the two masks derived in (c) with the shaded 3x3 neighbourhood of pixels in the image below, to give gradients Gx and Gy. Then compute gradient magnitude from Gx and Gy using the method given in (c). In each case, show all your working. [5]

(e) How might we use gradient magnitudes to identify the pixels belonging to the boundary of an object in an image? [1]
(f) Explain how the nonlinear technique of rank filtering can be used to compute a quantity similar to gradient magnitude. [2]

Question 4.
(a) Describe the main characteristics of structuring elements (SEs) and explain briefly how they are used to perform morphological processing of binary images. [6]
(b) In the image shown below, the blank pixels have a value of 0 and the shaded pixels have a value of 1. Suppose that this image is subjected to erosion by a 3x3 square SE. The origin of this SE is its central pixels, and all SE pixels have a value of 1. Explain briefly how the erosion is computed and sketch the image produced by this operations. [4]

(c) Suppose that the output of the erosion operations in (b) is then subjected to dilation by the same SE. Explain briefly how the dilation is computed and sketch the image produced by this operations. [4]
(d) What is the term used to describe an erosion followed by a dilation. What would be the effect of a second cycle of erosion and dilation on the image produced in (c)? [2]
(e) A bank is developing a machine that can recognise the handwritten signatures of its customers. Binary images of the signatures are produced by scanning a document and thresholding the scanned image. In these binary images, pen strokes should appear as chains of connected pixels; however, image quality is often so poor that these chains are broken in many places.
Suggest a technique that will join up the broken pen strokes in these binary images, Draw diagrams to illustrate the different stages of the technique. [4]

Question 5.
(a) Give four reasons why images are normally acquired using radiation from the visible region of the electromagnetic spectrum. Give two examples of scenarios in which radiation from other parts of the the spectrum must be used and explain, in each case, why visible radiation is unsuitable. [8]
(b) Describe six structural or functional differences that exist between the human eye and a CCD-based electronic camera. [6]
(c) How many unique colours are available for use in a 24-bit colour image? Explain your reasoning. [2]
(d) It is unlikely that we would ever see a 24-bit image containing every representable colour. Why? [2]
(e) When performing intensity or colour enhancement operations on colour images, the HSI model is preferable to the RGB model. Explain briefly why this is so. [2]

return to top

CS4 Advanced Computing and Multimedia Networks
Delivered by Dr. Mourad Kara

Venue: Roger Stevens LT20. 2hrs, Attempt three Questions.

Question 1.
(a) Most cell networks guarantee the delivery of cells in the order in which they are sent. Discuss the issues that an adaptation layer has to address if the underlying cell network does not guarantee the delivery of cells in the order in which they are sent.[6 marks]
(b) Explain why it is more suitable to use cell networking to support integrated multimedia services than packet switching networks. [4]
(c) Most cell networking technologies which support multimedia services do not re-transmit cell that are lost or corrupted. What would be the consequences if the cell network protocol re-transmit lost and/or corrupted cells? [6]
(d) The ITU-T standard body has initially proposed four ATM Adaptation Layers (AAL1-AAL4). AAL3 and AAL4 support data services (connectionless and connection-oriented). The following revision from the ITU-T combined AAL3 and AAL4 into AAL3/4. The ATM Forum decided to propose an alternative to AAL3/4 called AAL5. Explain the motivation behind the ATM forum proposal to put forward AAL5. [4]

Question 2.
(a) A user is planning to send a 1 Megabyte (MB) file from site A to site B. Sites A and B are linked by a communication channel and are separated by 2000 miles. The parameter a is defined as the ratio of the latency of the channel and the time it takes to pump one packet into the link.

(i) The user selects an X.25 packet network running at 64 Kb/s (kb: kilobits) (ii) The user select a T1 channel running at 1.544 Mb/s (Mb: Megabits)

(iii) The user select a 1.2 Gb/s link. (Gb: Gigabits)

Explain the latency/bandwidth issue in each case. [4, 4, 4]

(b) What are the main implications of the fiber optics technology for communication protocols in high speed networks? [3]
(c) In determining the ATM cell size at the Standard Committees, the telephony industry supported a small cell size (e.g. 16 bytes), while the computing industry preferred a large cell size (e.g. 128 bytes). Explain the motivations behind each industry's choice. Discuss the selected choice for an ATM cell (48 bytes). [5]

Question 3.
(a) Assume a cell network protocol with a fixed cell size of 53 bytes. This protocol guarantees cell retransmission of lost cells. It operates on a SONET (OC3) 155 Mbps link with a round trip time-outs (RTT) of 20 milliseconds. What should be the minimum field size for the cell sequence number in the cell header? What is the percentage of data rate lost due to the cell sequence number field? You should justify your answer. [4 & 3]
(b) In a local area network (LAN) environment, describe the three primary differences between the ATM technology and other shared media technologies such as Ethernet and FDDI.[3, 3, 3]
(c) There are at least two ways of programming an application over an ATM network: (1) with conventional transport and network protocols over ATM (e.g. TCP/IP) using multiprotocol encapsulation over AAL5, and (2) writing your programs at the the AAL level (native ATM programming). Discuss the advantages and disadvantages of each approach. [4]

Question 4.
(a) What is the purpose of traffic shaping in high speed network providing different types of services for multimedia applications. [4]
(b) Describe the following two traffic shaping schemes : (1) the simple leaky bucket (p, B) scheme and (2) the (r,T) smooth traffic scheme. [4, 4]
(c) Discuss the major differences between simple leaky bucket and the smooth traffic schemes. [3]
(d) Assuming an ATM network with several ATM Adaptation Layer (AALs). What is the purpose of the Segmentation and Reassembly (SAR) and the Convergence Sublayer (CS) in an AAL? (You can use as an example TCP/IP over ATM AAL5). [5]

return to top

OOP Object Oriented Programming, Exam 1997'
Delivered by Dr. Willi O. Riha

Venue: Roger Stevens LT15. 2hrs, Attempt all Questions.

Question 1.
Programs often take their input from an input file and optionally send the output to a specified output file instead of to the screen. The file parameters are then conveniently passed on to the command line, For example, the command
java test data -out results
causes the program test to read input from file data and write the output to file results. On the other hand, the command
java test data
will read from file data and write the results to the screen. The command
java test -out results
is incorrect and should be rejected. Program test will therefore have to validate the command line parameters to establish if they are correct and meaningful. In a Java textbook, the author offers the following piece of code for the validation.

if (args.length <1){

System.out.println("USAGE: java test inputFile [-out outputFile]");
System.out.println(" -out outputFile is optional.");
System.exit(1);

}

String inFile = null;
String outFile = null;
boolean toFile = false;

for (int i=0; i< args.length; i++){

if (arg[i].equals("-out")){

if (arg.length>i+1){

outFile = new String(args[i+1]);
i++;
toFile = true;

} else {

System.out.println("No output file specified.");
System.exit(1);

}

} else

inFile = new String(args[i]);

}

Although this code will deal correctly with the first two command lines given above, it does not work in general since the underlying logic is wrong. For example, it does not deal correctly with the third command line above.
Modify, or rewrite the given code so that it deals correctly with all possible command lines. [10 marks]

Question 2.
The class java.lang.System provides a method which is useful for copying (a portion of) an array to another array. IT has the following specification
/* Copies an array from the source array, beginning at the
specified position, to the specified position of the destination array.
This method does not allocate memory for the destination array/ The memory must already be allocated.
param src: the source data
param src_pos: start position in the source data
param dest: the destination
param dest_pos: start position in the destination data
param length: the number of array elements to be copied
exception: ArrayIndexOutOfBoundsException, if copy would cause access of data outside array bounds.
public static native void arraycopy (Object src, int src_position, Object dst, int dst_position, int length);
Given the following declarations
char a[] = new char[20];
char b[] = new char[15];
Person p[] = new Person [10]; // Person is some user defined class
Person q[] = new Person [12];
assuming that the arrays have been suitably initialised, we may use the function as follows
System.arraycopy(p, 2, q, 4, 5); // copies p[2], ... p[6] to q[4], ... q[8]
System.arraycopy(b, 0, a, 18, 2); // copies b[0], b[1] to a[18], a[19]
System.arraycopy(a, 5, b, 10, 7); // throws ArrayIndexOutOfBoundsException

(a) Why is the use of function arraycopy inconsistent with Java's type system, and why is it not possible to write, in Java, the body of a method which deal with the preceding three function calls? [3, 3]
(b) Attempt to give a Java implementation of a function
public static void ArrayCopy (Object src, int src_position, Object dst, int dst_position, int length);
with the the same specification as System.arraycopy, and explain its limitations. [11]
What would you have to do in order to ensure that all possible invocations of Arraycopy can be performed? (A brief explanation is sufficient). [3]
Note: If you do not understand part b), or do not know how to do it, then simply write a function which copy a (portion of a) char array to another char array as specified above. (You will only score 6 marks instead of 14).

Question 3.
Alongside stacks and queues a data structure known as a deque is often used in certain applications. A deque is a dynamic linear structure which supports the following basic operations: checking if a deque is empty, adding, removing and inspecting the first element, adding, removing, inspecting the last element. We might call these operations isEmpty(), addFirst(item), removeFirst(), getFirst(), addLast(item), removeLast(), getLast().
a) From an implementation point view, what is the relationship (if any) between a deque and a queue and the built-in class Vector? (e.g. is the true that every queue is a deque etc.) [3]
b) Given an implementation of a class Queue (as, for example, discussed in the lectures) is it possible or meaningful to derive a class Deque from it? Is it possible to make use of a class Queue in the implementation of a class Deque? (You are not required to write any code, just give a brief explanation). [2]
c) It is possible to implement a class Deque in terms of class Vector. Show how to do this. (Here you are required to produce some Java code. Note that you only need to implement the operations mentioned above (and, obviously, at least one constructor). To keep things simple, no check for homogeneity are to be included). [5]

Question 4.
Suppose that you are required to write a Java program which reads in another Java program and outputs the program text contained in the input file with all comments stripped. Explain how you would go about implementing such a program. You are not required to write any code - this would take too long - but you should attempt to explain the structure and the logic of the program in as much detail as is necessary.
Notes:
You are not allowed to store the entire input file in a char array or a String.
You may assume that the input file contains a syntactically correct Java program, i.e. every multi-line comment is properly delimited by /* and */.

return to top

VIS Distributed Visualization Systems,
Visualization & High Performance Computing, Exam 1997'
Delivered by Dr. Ken Brodlie

Venue: Roger Stevens LT20. 2hrs, Attempt three Questions.

Question 1.
(a) Data values are given at the corners of a unit square as shown in Table 1:

Draw an estimate of the zero level contour line. Explain in detail how you have arrived at this estimate. [10 marks]

(b) The following data relates to the length of rods produced by a manufacturing process. Table 2 shows the probability that any sample rod has a length which is less than a particular value.

o A visualization is required which will give an indication of the probability over the entire range of lengths from 79.0mm to 85.0mm.[2]
o Describe the nearest neighbour and piecewise linear interpolation methods, sketching the estimate of the probability each generates. [2]
o Compare the strengths and weaknesses of the two methods. [2]
o Use the two methods to estimate the probability that a sample rod has length less than 81.8mm [2]
o Describe piecewise cubic interpolation. [2]
o What care is needed in applying piecewise cubic interpolation to this set of data [2]

Question 2.
(a) Consider a 3D dataset of CT data generated by a medical scanner. Describe the basic steps involved in visualizing this data using the ray casting volume rendering technique. Your answer should explain how the compositing of samples along a ray is carried out. [10]
(b) There is freedom in choosing the spacing between the samples taken along a ray. What would the advantage (in saving of computation) be in choosing samples to lie exactly one voxel width apart, each sample being chosen to lie on the face of a voxel? [5]
(c) If you were given a second 3D dataset, this time of SPECT data indicating bloodflow, suggest at least two ways in which a combination of the two datasets might be visualized. [5]

Question 3.
(a) Outline the spot noise technique as applied to the the visualization of 2D velocity data. [7]
(b) Consider a 3D dataset of velocity data defined on a rectilinear grid. Describe the basic steps involved in visualizing this data using a particle advection technique. [7]
(c) Suppose you were also given temperature and pressure values on the same grid. Design a glyph (ie a symbol) which would allow the velocity, temperature and pressure values to be collectively visualized at a point. Discuss the strengths and weaknesses of your design. [6]

Question 4.
(a) What is VRML? Distinguish the capabilities of version 1.0 and 2.0. [2]
Consider the role of VRML in terms of the visualization reference model (due to Haber and McNabb). Use this to explain how VRML can be used in combination with a visualization system such as IRIS Explorer, as a means of publishing visualization. [4]
Discuss how an IRIS Explorer visualization service might be provided via the World Wide Web. [4]
(b) Explain the history tree concept introduced by GRASPARC for maintaining an audit trail of computational experiments which involve an evolutionary (ie time-independent) process. [5]
If the computational experiments involve running a static simulation (ie time invariant) for different values of three parameters, suggest an

AGR Advanced Computer Graphics and Virtual Environments, Exam 1997'
Delivered by Dr. Terrence Fernando

Venue: Auditorium Gallery, Attempt all Questions.

Question 1.
(i) Imagine that you have been given the task of implementing a polygon renderer based on PHIGS. Explain how you would go about designing the renderer. Your answer should discuss the following.

(a) A diagram showing the main stages of the rendering pipeline which support Z-buffering and Gouraud shading. [3]
(b) Brief explanation of the function of each stage of the rendering pipeline. [3]
(c) Will the rendering pipeline be the same for performing Z-buffering and Phong shading? Please give your reasons for your answers. [2]

(ii) Explain how the Z-buffer algorithm and the Gouraud shading algorithm can be combined together to generate 3D images with hidden surface removal. Your answer should explain the main concepts used in both algorithms and their integration. [10]

One of the advantage of the Z-buffer algorithm is that polygons may be presented to it in any order. Does this mean that two renderings of the same scene created by sending polygons in different orders, will have identifical values in their Z-buffer and in their intensity buffer? Explain your answer. [2]

Question 2.
(i) When using Constructive Solid Geometry (CSG), primitives such as blocks and spheres are combined together using Boolean operations. Such CSG models are maintained in a binary tree called a CSG tree. Outline an algorithm for ray tracing such models. Your answer should include the following.

(a) how to compute the nearest intersection. [4]
(b) how to generate shadows, reflections and transparency [6]
(c) a lighting model which can be used to compute the final shading value of a pixel. [2]

(ii) Describe the spatial aliasing artefacts in ray tracing and explain how these artefacts can be reduced using adaptive supersampling techniques. Discuss the limitations of this method. [8]

Question 3.
(i) Virtual Environments are increasely developed for application in area such as Mechanical Engineering, Construction, Medicine etc. Imagine you have been given the task of designing and implementing a highly immersive virtual environment for one of the above applications. What issues would you consider in your design? Your answer should discuss the design issues under the following points:

(a) Direct man-machine interface. [4]
(b) Realism of the virtual world. [3]
(c) Performance issues. [3]

(ii) Open Inventor is an object oriented toolkit for building interactive graphical applications. Explain briefly how Open Inventor support the following facilities:

(a) construction of complex graphical scenes [3]
(b) ability to control level of detail [2]
(c) animation [2]

Compare and contrast the features of Open Inventor with Open GL. [3]

return to top

AI9 Computer Vision, Exam 1997'
Delivered by Prof. David Hogg and Dr. Roger Boyle

Venue: Auditorium Gallery, Attempt all Questions.

Question 1.
(a) For either the Robotic Sheepdog application described by Mr Sumpter or the Deformable Mesh system described by Dr. Bulpitt, describe the system under the heads o image processing o segmentation o shape extraction o shape characterisation o interpretation o understanding From all the information in your answer, it should be clear what the application is doing, and how (in overview form) it does it. [10]

(b) A well known car manufacturer wishes to develop a camera-based system to recognise standard road signs in order to provide auditory safety warning to the driver (e.g. there is a left-hand bend coming up for which you are going too fast). One of the problems will be dealing with the wide range of viewpoints from which road signs may be observed. Produce an outline design for the machine vision component of such a system. You should state precisely which techniques will be used and how they fit together. You are not required to give details of how the individual techniques work. Discuss the reasons for your choice of design and what you think are its weaknesses and strengths. Wherever possible you should use diagrams to illustrate the description. [10] (a) An ellipse at (a,b) with semi-axis r1, r2 is given by the equation

(x-a)^2   (y-b)^2
------- + -------- = 1
  r1^2      r2^2

Explain clearly how you would conduct a Hough Transform to search an M x N image for ellipses with the following three property; o have r1 in the range [10,20] (measured in pixels); o have aspect ratio (r1/r2) in the range [0.5, 0.7]; o are entirely within the image. [6]

+---------------------------+
|                           |
|  x                        |
|  x   xxx            S1    |  xx blobs
|  xxxxxxx                  |   P Pentagon 
|   xxxxxx       S2         |   H Hexagon
|                           |  S1 Semi-circle with intensity about 230
|                 P         |  S2 Semi-circle with intensity about 140
|         S1          H     |  S3 Semi-circle with intensity about 230
|  S3                       |
|             P      S3     |
|    S2            xxxxxxx  |
|               xxxx    xx  |
+---------------------------+

Suppose an image is known to contain a number of semi-circles of known radius R (among other things). Each semi-circle is of uniform intensity, but different semicircles may have different intensity. Explain how you might use a Hogu Transform to locate them (there is no need to repeat details of the conduct of the Transform algorithm). [6] (b)

+------------------------------------------------+
|1                                               |
|   xxxxxxx                                      |
|  xx2    xx                                     |
|   xxxxxxx                               xxxxx  |
|             x3x x4x   xx5               x6  x  |
|              x   x    xxxx              x   x  |
|        xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx   xxx|
|        x7                               x   x9 |
|        x                                x   x  |
|        x        xxxxxxxxxxxxxxxxxxxxx   x   x  |
|        x        x8                  x   x   x  |
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|10                                              |
+------------------------------------------------+

A simple bar-room scene is known to contain only 6 sort of object - bar, floor, glass, mirror, student, wall. The following relationships are also known to hold; Bar is straight edged Floor occurs only once Glass is straight edged Mirror is oval Student is roughly rectangular Wall occurs only once Bar is directly above floor Floor is adjacent to the image border Only Floor is wholly beneath wall Glass is directly above bar Mirror is within wall Student is directly above floor Wall is adjacent to the image border Consider the figure, and use discrete relaxation to label the region 1-10 as unqiuely as possible. [6] Suggest a further restriction or restrictions that would resolve any remaining ambiguity. [2]

Question 3.
(a) A given pair of camera views are related by the following relationships between corresponding points in the two images:

         ( 0  1  0 )( x2 )
(x1 y1 1)( 1  0 -1 )( y2 )  = 0
         ( 0  1  0 )( 1  )

i. By substituting into this matrix equation, derive the equations of the epipolar lines in image 2 corresponding to the points

( x1 )   ( 3 )              ( x2 )   ( 6 )
( y1 ) = ( 1 )       and    ( y2 ) = ( 1 )    from image 1. [3]

ii. From these lines, derive the position of the epipole in image 2. Draw a diagram to illustrate the configuration of epipolar lines in image 2. [4]

iii. The fundamental matrix

    ( 0  0  0 )
F = ( 0  0 -1 )
    ( 0  1  1 )

is unusual in an important respect. What can you say about the associated epipolar lines and the geometrical setup of the pair of views? Justify your answers. [5]

(b) Alignment matching is well suited for matching 2D models against sets of 2D image features. However, it may also be used to match 3D models against sets of 3D points features derived from stereo processing.

i. How many points pairing would be required to completely determine the pose of an object in 3D? Explain your answer. [4]

ii. Suppose 12 three-dimensional point features have been derived from stereo processing. How many distinct candidate poses are generated during the alignment matching algorithm? Show your working. [4] Question 4. (a)

      |
      |a
   e  |  b
 ----- -----
      |
      |c
      |

 

Consider the edge relaxation scheme described in lectures (see Figure); suppose at some stage a=0.2, b=0.1, c=0.5. For what values of q (as defined in your notes) is this vertex of type 0? [2]

              i
            -----
    ##### a ##### d #####
    ##### | ##### | #####
    ##### | ##### | #####
   b------  --e--   -----g
    ##### | ##### | #####
    ##### | ##### | #####
    ##### c ##### f #####
            -----
              k

A problem with edge relaxation schemes is the generation of double edges - that is (see Figure), in addition to e, i and k may also be encouraged. Suggest a way you might amend the relaxation algorithm as describe in notes to compensate for this. [6]

(b) Pictures of starfish are collected from rockpools; the animal vary in size and while they are all 5 pointed, the 'limbs' are capable of independent movement. Provided with an algorithm that segments out the sihouette of a starfish, explain how you would automatically build a point distribution model of the shape. [4]

           xxx
           x  x
            x  x    xxxxxxxxxxX
             x  xxxxx  xxxxxxxX
     xxxxxxxxxx xx   xx
    xxx              x
     xxxxxxxxxxx  x x  x
              x  x   x   x
             x  x     xx  x
             xxx        xxxx            (A star fish)

Assume that a principal components analysis of your model has been conducted, and a low(er) dimensional representation is available. Explain clearly how you would use your model best to fit a shape in a new image. [5]

Suppose you also have information about how the starfish is moving (perhaps from accumulated video data) in the form of direction and speed, while retaining its approximate shape. Describe how you would augment the solution you have described, and mention any particular problems you might foresee. [3]

return to top

DMS Future Directions in Distributed Multimedia Systems, Coursework 1997'
Delivered by Dr. Ken Brodlie

Coursework 1 (30%)

Coursework 2 (30%)

Group Project (40%)

return to top

VWE Virtual Working Environments, Coursework/Exam 1997'
Delivered by Dr. Lydia Lau

Coursework 1 (35%)

Coursework 2 (35%)

Open Book Examination (30%)

return to top

CS4 Advanced Computing and Multimedia Networks, Exam 1998'

Question 1.
(a) A fibre optic link has a wavelength L (units in metres), a bandwidth dL (units in metres), and its index of refraction If (no units).

(i) Assuming the speed of light in vacuum is C (unuts in metres per second), what is the bandwidth capacity of this optical link (units in hertz)? [5]

(ii) Compute the bandwidth capacity for the following values; L=1.30mu, dL=200 nanometers, If=1.45 and C= 3 * 10^8 metres/seconds. [1]

(iii) Current signalling equipment can signal at a maximum rate of 1.2bits per hertz. What is the maximum bit rate of this fibre optic link (unit in bits per seconds)? [2]

(b) In cell networking, discuss the effects of the cell size on serialisation delay using the following criteria:

• mixed traffic delay requirements. [3]
• analog-to-digital conversion delays. [3]
• forwarding delay. [3]

(c) In cell networking, briefly explain the role of the adaptation layers and their protocols. [3]

Question 2.
(a) High speed networks have the capability of transmitting packets at a very high data rate. One of the emerging problems in these networks is the issue of latency versus bandwidth.

(i) Discuss the issue of latency versus bandwidth in high speed wide area networks and its impact on network protocols. Illustrate your answer with suitable examples. [5]

(ii) In a high speed wide area network, assume a link between two host A and B. C is the capacity of the link (in Megabits/sec), b is the average packet size (in bits) transmitted on this link and L is the length of the link (in miles). It takes approximately 5 microseconds for a light pulse to travel one mile on one link on that link. Derive the formula for the critical system parameter a. Recall that the parameter a is the ratio of the latency of the channel to the time it takes to send one packet into the link. [4]

(b) In a high speed wide area network, a large number of users are sharing a high speed fibre link (from host A to host B) and of length L (in miles). The link has a data rate of C Megabits per seconds. We are concerned with the users sending their packets from host A. The speed of light is x microseconds per mile on this link. Assume that the arrival of packets from these users follows a Poisson distribution. A packet has a length which is exponentially distributed with a mean b (in bits). Assume that the queueing model is M/M/1. Derive the formula for the average response time of packet transmission. The formula should be a function of C, b, L, x and R is the system load on host A. [6]

(c) Assume an integrated multimedia services network (i.e. a network supporting different classes of traffic and services). Discuss the advantages and disadvantages of using cell networking as opposed to packet networking to support such services in a high speed network. [5]

Question 3.
(a) Assume a cell network protocol with a fixed cell size of 53 bytes. This protocol guarantees cell retransmission in case of cell loss. This protocol is based on a sliding-window and uses sequence numbers and time-out for retransmission of lost cells. It operates on a high speed link with a bandwidth C (in Megabits per seconds). The round trip time (RTT) of this link is 20 milliseconds. Explain the relationship between the field size of the cell sequence number in the cell header and the bandwidth. What should be the maximum bandwidth C if the field size is 14 bits for the cell sequence number in the cell header? [4, 4]

(b) The Ethernet protocol operates using CSMA/CD. Ethernet operates at 10 Megabits per seconds and has minimum packet size of 64 bytes (maximum cable length 5 km). Consider the problem of scaling up the Ethernet transmission rules to Gigabit speeds. If Ether net was running at 1.2 gigabits per seconds, what would be the minimum packet size? Discuss the Ethernet collision detection and recovery scheme and its suitability for high speed networks. (Assume that the signal propagates at 10.24 microseconds per kilometer (km) on Ethernet cables). [4, 4]

(c) In fibre technology for communications, a typical fibre is made up of two layers. A strand of glass, called the core wrapped with another layer of slightly different glass called the cladding. The core and cladding have different indices of refraction. What is the property of refraction used to send a pulse of light over fibre, and explain how it works. [2, 2]

Question 4.
(a) In a multimedia application programming environment, why is it important to have a degradation path facility? Give an example of what can go wrong if such a facilities is not provided. [6]

(b) What is meant by the degree of commitment in a multimedia communication architecture? Explain how different degrees of commitments agreed between user applications and network providers have an effect on the quality of service provided when the network starts to be congested. [5]

(c) Over the last few years, several network technologies have been emerging for supporting the next generation of integrated services packet networks. Assume a local network environment, discuss the three main differences between ATM technology and other shared media technologies such as Ethernet and FDDI. [3, 3, 3].

return to top

PSS Perceptual Systems, Exam 1998'

Question 1.
A robotic vehicle is exploring the surface of a distant planet. It must navigate through its environment autonomously, using a single electronic camera and onboard image processing to detect and avoid craters, large rocks and other obstacles. Occansionally, it must stop to transmit images of interest back to Earth.

The images acquired by the robot are typically dark and lacking in contrast. The imges also suffer from noise that affects a small proportion of the pixels, forcing them to take extreme values. Pixel grey levels in a 7x7 region from a typical image are given below.

(a) Which problem should the robot's image processing system deal with first? Explain you reasoning. [2]

(b) Discuss how the brightness and contrast of the images might be enhanced. Your discussion should indicate clearly the advantages and disadvantages of your proposed enhancement technique. You should describe how the technique can be implemented efficiently, given that the robot's onboard computer has limited storage and processing power. [5]

(c) How might the noise be removed effectively from the images? Perform calculation on the pixel data given above to demonstrate clearly your proposed technque works, and comment on its potential disadvantages. [4]

(d) Propose a simple method for identifying the boundaries of boulders or similar obstacles. Perform calculations on the pixel data given above that demonstrate your proposed technique is feasible. Show all your working. [6]

(e) Suppose that the technique used in (d) produces a fragmented boundary, containing numerous small gaps. Outline a technique that might be used to fill these gaps, thereby giving a closed boundary. [3]

Question 2.
(a) Pictures of aircraft are collected from aerial shots of airports; the planes vary in size and precise shape, but have obvious similarities (see Figure for example). Provided with an algorithm that segments out the silhouette of a plane, explain how you would automatically build a point. [4]

Suppose you also have information about how a plane is moving (perhaps from accumulated video data of taxi-ing) in the form of direction and speed (while retaining its shape). Describe how you would augment the solution you have given to describe moving aircraft, and mention any particular problems you might foresee. [3]

(b) Basil and Deirdre share a bedroom on the flight path to Heathrow airport; they often lie in bed together with the curtains pulled playing the game of 'blind plane spotting', judging characteristics of the traffic on the basis of what they hear. The know that

• there are 10 different varieties of aircraft that fly over their house
• the noise of a plane may be quantised into: unbearable, really loud, loud, loudish, not so loud, quiet, only just audible
• the complexity of air traffic means that it is impossible to adhere to any formal timetable, but there are perceptible patterns in what passes that change through the day on an hour-by-hour basis.

Given observations of the noise levels of a few consecutive planes, the following questions are posed:

i. From which hour of the day have the observation come?
ii. What were the probable varieties of plane of the recent observations?
iii. What variety of plane is the next observation mostly likely to be?
iv. What is the next observation most likely to be?

Explain fully

• what assumptions would need to be made; [2]
• what information would need to made available; [2]

that would permit them to use a Hidden Markov Model approach to answer these questions. Explain also how the estimates of (i)-(iv) would be made. [1.5 marks each]

Question 3.
(a) A point (24,36,6) in camera-centred coordinates maps on to the point (112,68) in pixel coordinates under perspective projection. If the horizontal and vertical scale factors of the camera are given by sx= 3 and sy=3, what are the coordinates of the principal point? Show your working. [7]

(b) A pair of cameras, C1 and C2, are related by the following relationship between a point (x1, y1) in the image-plane of C1 and the corressponding point (x2, y2) in the image-pane of C2:

         ( 0  1  0 )( x2 )
(x1 y1 1)( 1  0 -1 )( y2 )  = 0
         ( 0  1  0 )( 1  )

Similarly, C2 is related to third camera C3, by the following relationship between a point (x2, y2) in the image-plane of C2 and the corresponding point (x3, y3) in the image-plane of C3:

 

         ( 0  1  0 )( x3 )
(x2 y2 1)( 1  0 -4 )( y3 )  = 0
         ( 1  1 10 )( 1  )

i. Suppose a three-dimensional point P projects to (3, 1) in the image-plane of C1, and to (4, 2) in the image-plane of C3. Derive the equation of the corresponding epipolar lines in the image-plane of C2. Show your workings. [6]

ii. What are the coordinates of the projection of P in the image-plane of C2? Show your working. [7]

Question 4.
The following is a simplified sample of a Latin text, annotated with LOB-style Part-of-Speech tags and English translation:

Caecilius  ambulat  ad  portum  .
NP         VBZ      IN  NN      .
Caecilius  walks    to the port .

Caecilius  circumspectat  portum  .
NP         VBZ            NN      .
Caecilius  looks around  the port . 

argentarius  videt  navem  Syriam  ,  et  ambulat  ad  navem   .
NN           VBZ    NN     JJ      ,  CC  VBZ      IN  NN      .
the banker   sees   a Syrian ship  ,  and walks    to the ship .

Syphax  videt  Caecilius .
NP      VBZ    NP        .
Syphax  sees   Caecilius .

Caecilius  videt  ancillam  pulchram   .
NP         VBZ    NN        JJ         .
Caecilius  sees a beautiful slave-girl .

ancilla         delectat  Caecilium .
NN              VBZ       NP        .
the slave-girl  delights  Caecilius .

Caecilius  emit   anciliam     .
NP         VBZ    NN           .
Caecilius  buys the slave-girl .

[Adapted from Cambridge Latin Course, CUP]

(a) Explain how you would use a hidden Markov Model to build

i. a Part-of-Speech tagger for Latin text;
ii. an English-to-Latin machine translation system.

Your explanation should include:

• an outline of how generic Hidden Markov Model principles apply to these specific language modelling problems; [3]

• the linguistic resources you will need to build these systems; [2]

• likely pitfalls; aspects of the Latin Part-of-Speech tagging and machine translation tasks which are likely to be problematic for a standard Hidden Markov Model. where appropriate, use the above sample text to illustrate your answer. [8]

(b) What is EAGLES? Write down the EAGLES standard grammatical analyses at the top 3 levels (phrase-bracketting, phrase-labelling, dependency structure) for the FIRST and THIRD Latin sentences in the above sample. [7]

return to top

VIS Data Visualization, Exam 1998'

Question 1.
(i)  Isosurfacing and volume rendering are two techniques for the visualization of 3D scalar data. Describe each technique, and discuss their strength and weaknesses. You may assume data is given on on a regular rectangular grid. [12]

(ii) Describe three ways in which the basic volume rendering algorithm can be accelerated. [6]

(iii) Explain how volume rendering effects can be simulated using multiple isosurfaces. [2]

Question 2.
(i) Given 2D flow data on a regular grid, explain the steps involved in tracing the path of a particle through the flow. [6]

(ii) Are steamlines and particle paths identical in 2D flow? Explain your answer. [2]

(iii) A problem with steamline visualization is that the picture can become very cluttered where streamlines are converging. Suggest and algorithm for evenly spaced streamlines. [6]

(iv) A critical point in a flow field is a point where velocity is zero. Explain how critical points in a 2D flow field can be located - you may assume that bilinear interpolation is to be used. Why are critical points important? [6]

Question 3.
(i) The World Wide Web provides an important new environment for data visualisation. Describe three different system architectures for providing visualization services over the Web, identifying any key technologies in each case. Mention any examples you have tried. [9]

(ii) IRIS Explorer uses visual programming. What are the strength and weaknesses of visual programming relative to conventional programming languages? [2]

(iii) Describe what is meant by a problem-solving environment for scientific computing. You may illustrate your answer using GRASPARC project. [6]

(iv) Explain how the use of IRIS Explorer as a framework can alleviate some of the practical difficulties in developing particular GRASPARC applications. [3]

Question 4.
(i) Distinguish multi-dimensional and multivariate data. [2]

(ii) Describe an approach to the visualization of multi-dimensional scalar data that can be used for high dimensional problems. [4]

(iii) Describe two approaches to multivariate visualization, and discuss their strength and weaknesses. [8]

(iv) Suggest ways of visualizing the following information:

(a) UNIX directory tree [3]
(b) e-mail traffic within the School of Computer Studies [3]

return to top

Created in January 25, 1997. Last Revised: Feb  3, 1998