University of Ulster, Magee College. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1996. Lecturer: J.G. Campbell. Date: 04/09/96 OLD EXAMINATION QUESTIONS + TESTS. ---------------------------------- These are all the past examination papers and class tests that I possess -- honest!. Consequently, I think that it would be a waste of time trying to find any more; better to spend the time studying! Examination Autumn 1995 ----------------------- Questions only. All questions carry equal marks. Answer any FOUR questions. 1. Digital Image Fundamentals and Image Sensing. [Answer (a), (b), and EITHER (c) OR (d)] (a) Explain in detail, employing diagrammatic illustrations where appropriate, the process of the creation of a two-dimensional 'digital image' from a three-dimensional scene? [10 marks] (b) Equation 1-1 describes the sensing of a two-dimensional (planar) scene: f(x,y) = b(x,y) + h(x,y).r(x,y).i(x,y) + n(x,y) (1-1) where f(x,y) is the value recorded for the pixel corresponding to position (x,y) in the plane, r(x,y) is the reflectivity at (x,y), i(x,y) is the illumination incident on the plane at (x,y), h(x,y) is the gain of the sensor system for pixel (x,y), b(x,y) is the bias of the sensor system for pixel (x,y), n(x,y) is the additive noise at pixel (x,y). Discuss equation 1-1, paying attention to how the user of the image is likely to interpret the image data, and how the various unwanted elements (data) and their interactions may be eliminated. [9 marks] (c) a visible colour image may be represented by three 'bands'; nevertheless, in a digital image processing system, it is possible to envisage images of very many more than three bands. Discuss. [6 marks] OR (d) Discuss image representation in computer memory. [6 marks] 2. Image Enhancement. (a) In the context of image enhancement describe the principles underlying: point operations, and neighbourhood operations. Your answer should should include representative examples of each, together with illustrations of their operation, and descriptions of applications for which one type is more suitable than the other. [10 marks] (b) Equation 2-1 defines a statistics based contrast stretching transformation, z' = (z-m) . s'/s + m' 2-1 where z', and z are, respectively, the output and input values, s', s are the output and input standard deviations, m', m are the output and means. Discuss this transformation, both in the context of general image enhancement, and of part (a); e.g. compare it to other transformations, and to other methods used to obtain the transformation parameters, discuss in what circumstances might it be used, give illustrative examples, etc. [9 marks] (c) Apply equation 2-1 to the image shown in Figure 2-1, using the values m' = 128, s' = 40. Comment on the significance of the values m' = 128, and s' = 40. [6 marks] 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 Figure 2-1 5 x 5 image 3. Convolution, Edge Detection, and related. [Answer parts (a), EITHER (b) OR (c), and (d)] (a) Explain the importance of 'convolution', in EITHER digital signal processing (one-dimension), OR digital image processing (two-dimensions). [9 marks] (b) Explain, using appropriate examples, application of the Prewitt operators shown in Figure 3-1; in addition, explain the significance of each operator, and how their results are normally combined. [9 marks] hr = -1 0 +1 hc = -1 -1 -1 -1 0 +1 0 0 0 -1 0 +1 +1 +1 +1 (a) vertical edges. (b) horizontal edges. Figure 3-1 Prewitt Operators OR (c) Write a computer program (or computer programs) to apply the Prewitt operators shown in Figure 3-1; explain how their results are normally combined. Use any language of your choice, or pseudo- code. [9 marks] (d) Figure 3-2 shows a character representation of an image of a cross; 'M' represents pixel value 1, while blank represents 0. Describe the results that would be obtained using Prewitt edge enhancement. Identify and discuss examples of common problems associated with edge enhancement, and suggest pre-, and / or post- processing that may eliminate them. [7 marks] 0123456789012345678901234567890123456789012345678901 ---------------------------------------------------- 0| | 1| | 2| M M | 3| | 4| MMMMM | 5| MMMMM | 6| M MMMMM | 7| MMMMM | 8| MMMMM | 9| MMMMM | 0| MMMMM | 1| MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM MMMMMMMMMM | 2| MMMMMMM MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM | 3| MMMMMMMMMMMMM MMMMMMMMMMMMMM MMMMMMMMMMMMMMM | 4| MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM | 5| MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM | 6| MMMMM | 7| MMMMM | 8| MMMMM | 9| MMMMM | 0| MMMMM | 1| MMMMM M | 2| | 3| | 4| | 5| | +----------------------------------------------------+ +0123456789012345678901234567890123456789012345678901 Figure 3-2 4. Discrete Fourier Transform. [Refer to formulae in the Appendix, as neccessary.] [Answer EITHER (a) OR (b) and (c), (d) and (e)] (a) Give an interpretation of the discrete Fourier transform (DFT), and explain its significance in EITHER digital signal processing (one-dimension), OR digital image processing (two-dimensions). [10 marks] OR (b) Write a computer program to implement, with appropriate comments, the one-dimensional DFT; Use any language of your choice, or appropriate pseudo-code. [10 marks] (c) Figures 4-1 (a), (b) and 4-2 (a), (b), respectively, show representations of a cosine sequence, and an impulse sequence. Figures 4-3 and 4-4 show corresponding DFT sequences; which of these form DFT 'pairs'? Your answer MUST contain detailed justification, and refer to the DFT formulae. [8 marks] 1 * x[n] | * * | | +---1---*---3---4---5---*---7----------------------> n | | | * * -1 | * (b) ---------------------------------------- n 0 1 2 3 4 5 6 7 ---------------------------------------- x[n] 1 0.707 0 -.707 -1 -.707 0 0.707 ---------------------------------------- (a) Figure 4-1 1 * x[n] | | | +---*---*---*---*---*---*---*-----> n 0 1 2 3 4 5 6 7 (a) -------------------------------------- n 0 1 2 3 4 5 6 7 -------------------------------------- x[n] 1 0 0 0 0 0 0 0 -------------------------------------- (b) Figure 4-2 --------------------------------------------- u 0 1 2 3 4 5 6 7 --------------------------------------------- X[u] .125 .125 .125 .125 .125 .125 .125 .125 --------------------------------------------- Figure 4-3 --------------------------------------------- u 0 1 2 3 4 5 6 7 --------------------------------------------- X[u] 0 0.5 0 0 0 0 0 0.5 --------------------------------------------- Figure 4-4 (d) Hence, or otherwise, deduce, with brief justification, the DFT of the sequence given by Figure 4-5. [2 marks] 2 * | | 1 | x[n] | * * | | +---1---*---3---4---5---*---7----------------------> n | | | * * -1 | * ---------------------------------------- n 0 1 2 3 4 5 6 7 ---------------------------------------- x[n] 2 0.707 0 -.707 -1 -.707 0 0.707 ---------------------------------------- Figure 4-5 (e) Hence, or otherwise, deduce, with brief justification, the DFT of the convolution of sequence in Figure 4-1, with that in 4-2. Comment on the significance of this result. [5 marks] 5. Data Compression (a) Discuss entropy as a measure of information. [8 marks] (b) Verify, for the image shown in Figure 5-1 (probability table in Figure 5-2), that the average entropy per symbol is 2.55.[4 marks] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 Figure 5-1 Image 10 x 10 ---------------------------------------------------- z 0 1 2 3 4 5 6 7 ---------------------------------------------------- p(z) 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 ----------------------------------------------------- Figure 5-2 Probabilities for Figure 5-1 (c) Figure 5-3 shows Huffman code lengths for the same data; calculate the average length per symbol for your Huffman code, and explain any difference between this and the average entropy. [4 marks] ---------------------------------------------------- z 0 1 2 3 4 5 6 7 ---------------------------------------------------- p(z) 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.04 ----------------------------------------------------- L(z) 3 3 1 5 4 4 4 5 ----------------------------------------------------- Figure 5-3 Probabilities and Huffman Code Lengths (d) Explain the two chief reasons why the Lempel-Ziv compression scheme can normally outperform Huffman compression and is nowadays, therefore, the algorithm of choice for general applications (disc- file and data communications). Illustrate the principle or operation of the Lempel-Ziv algorithm on the binary sequence below; assume that 0, 1 are already stored in the codebook. [9 marks] Input data stream: 1011010100010... Assume that the symbols 0 and 1 are already in the codebook. [Essentially, in L-Z, encoding is performed by parsing the source data stream into substrings that are the shortest substrings which have not already been encountered.] 6. Neural Networks and Pattern Recognition. (a) Give a brief description of the structure, principles, and operation of a multilayer perceptron neural network (i.e. the common feedforward neural network). [10 marks] (b) Plot a feature space diagram of the two-dimensional feature data shown in Table 6-1. [Hint: as a check, note the class means supplied, and note that the data are distributed symmetrically]. [2 marks] Table 6-1 class x1 x2 ---------------------- 0 0.00 0.00 0 2.00 0.00 0 0.00 2.00 0 0.00 1.00 0 1.00 0.00 0 1.00 1.00 0 1.00 2.00 0 2.00 1.00 0 1.99 1.99 1 2.00 2.00 1 2.00 3.00 1 3.00 1.00 1 3.00 2.00 1 3.00 3.00 1 3.00 4.00 1 4.00 2.00 1 4.00 3.00 Class means Class 1: 0.998889 0.998889 Class 2: 3.000000 2.500000 (c) Prove, or otherwise verify, that the neuron shown in Figure 6-1 will form a linear classification boundary which cuts the x2 axis at -w0/w2 and the x1 axis at -w0/w1. [5 marks] x1 | +1 \ | \w1 |w0 \ | \ v +--+--+ output x2 w2 | | y ------------+ +----------> | | +--+--+ Figure 6-1 (d) Hence, or otherwise, verify that the weights below provide an appropriate classifying neuron for the data given in Table 6-1; pay particular attention to the points (1.99, 1.99) and (2.0, 2.0). w0 = -29.28 w1 = 9.76 w2 = 4.91 [4 marks] Answer either (e) OR (f) (e) Give a brief discussion on the ability of neural networks to generalise. [4 marks] (f) Give a brief description of neural network training via backpropogation. [4 marks] 7. The 10 x 10 image Figure 1-1, is a small part of an infra-red satellite image of water (top left) and land (bottom left). [Note, you may have worked with similar data before; in this examination, to ease calculation, the original SPOT satellite data have been divided by 10]. (a) Segment the image using: (i) a thresholding based on the histogram, i.e. first obtain h(z), for z = 0, 1 .. 14; [6 marks] (ii) k-means clustering (k=2); use any shortcut you wish -- e.g. choose initial values for your means, e.g. ma = 1, mb = 10. [6 marks] (iii) Look at your histogram for part (a) again, and comment on the assumption of two classes (k=2). [2 marks] (b) Figures 1-2, and 1-3 show further colours / bands. Assuming your segmentation from (a) is correct, what, approximately, are the three-dimensional mean vectors for water, mw, and land ml, respectively; comment on the discriminating power, for water versus land, of the three colours. [4 marks] 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 1 1 1 1 2 6 10 1 1 1 4 4 7 12 13 1 4 8 7 7 11 13 11 5 11 8 7 10 13 14 12 10 10 9 11 13 14 14 13 Figure 7-1 Infra-red Image. 1 2 3 3 2 2 2 2 2 3 2 2 2 3 2 1 3 2 3 3 3 2 3 4 3 3 4 4 3 3 5 7 4 6 5 3 3 5 7 7 7 5 3 4 6 7 7 7 6 3 4 6 7 9 9 9 4 3 5 7 8 10 10 10 Figure 7-2 Red Image 3 3 3 4 3 4 3 3 3 3 3 3 3 3 3 2 3 3 4 5 3 3 3 3 4 4 4 4 3 2 5 6 6 4 3 3 3 3 5 6 5 3 3 4 4 5 6 6 3 2 3 4 6 6 6 6 3 2 3 6 6 6 7 6 Figure 7-3 Green Image (c) Discuss the application of k-means clustering (or segmentation in general) to data compression. [7 marks] Appendix A: Formulae and Algorithms for Image Processing -------------------------------------------------------- Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = sum x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = sum x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = sum sum f[r-k,c-l].h[k,l] k=0 l=0 or, zero centred: r+w c+v g[r,c] = sum sum f[k,l].h[r-k,c-l] k=r-w l=c-v Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N)sum x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = sum X[u] exp(+j.2PI.u.n/N) n=0 Linear Contrast Stretch. ----------------------- z' = T(z) = (zG-z0).(z-a)/(b-a) + z0 where z = input value z'= output value z0..zG = desired output range a..b = input range. Histogram / Probability Distribution Transformation. ---------------------------------------------------- Notation: Input grey levels z, Output grey levels w, Transformation (lut) w = T(z), Input probability distribution p(z), cdf P(z) Desired (output) distribution q(w), cdf Q(w) Np = number of pixels in image. Algorithm: (1) Estimate frequency of grey levels (histogram), ph(z). (2) From ph(z) compute p(z) = ph(z)/Np. (3) Form cdfs P(z), and Q(w), from p() and q(), respectively, z' eg. P(z') = sum p(z) z=z0 (4) for each z in the input do: choose w such that Q(w) is closest to P(z), set T(z) = w; (5) Apply T(z) to input image f1[r,c]: f2[r,c] = T(f1[r,c]) Entropy. -------- Average entropy, Hav = - sum { p(zi).log2[p(zi)] } Logarithm to base B in terms of log10. ------------------------------------- logB(x) = log10(x)/log10(B). log10(2) = 0.3010 ie. log2(x) = log10(x)/0.3010 = 3.322 . log10(x) Huffman coding procedure. ------------------------- 1. List the symbols, along with their probability. 2. Pick the two least probable nodes. 3. Make a new node out of these two - adding the probabilities. 4. Repeat steps 2, 3, until only one node remains - the root. 5. Bit allocation. Starting at the root, allocate 1 to one branch (left, say), and 0 to the other; until all branches have been allocated. 6. Read out the codes. Starting at the root, travel to the leaf that represents each level, reading off the bits that make up the code for that level. Sigmoid activation function. ---------------------------- sigmoid(x) = 1/(1+exp(-x)) Procedure k-Means Clustering: Inputs: nc = number of classes, xij data to be clustered; i=1..d; j=1..N d = dimensionality of data vectors N = total number of pixels. Outputs: labj, j=1..N, labels of pixels xj labj = {1..nc} 1. Partition the pixels arbitrarily into nc classes (labels), eg. divide the image into nc regions, label all the pixels in the first region '1', second region, label '2', etc. 2. Compute the mean vectors of each class: m[i][c], i=1..d, c=1..nc 3. Procedure: k-Means Classifier: 3.0 Change = False 3.1 for j = 1..N do 3.2 reset Distmin = Bignumber, class = 0 3.3 Find nearest mean: 3.3.1 for c = 1..nc do 3.3.2 Compute Dist = Distance (xj to mean mc) 3.3.3 if Dist < Distmin then Distmin = Dist class = c 3.3.4 end. 3.4 labj = class; if 'changed' set Change = True. 3.5 end. 4. if Change = True goto 2 (*loop again*) 5. end. (* we are finished*) Function Distance(x,m) (*this calculates squared Euclidean distance*) Dist = 0 for i = 1 .. d do Dist = Dist + (xi -mi)**2 (*Euclidean distance*) return Dist end of examination paper. University of Ulster, Magee College. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1995. Lecturer: J.G. Campbell. Date: / /95 ASSIGNMENT 1 ------------ Submission Date: Fri. 10th November 1995. 2.15pm - class. Marks: 50% of coursework. Title: Programming Image Processing Operations in DataLab. All answers must be typed and presented neatly bound or stapled - with a proper title page. I will reserve a proportion of the marks for presentation. I will especially reward comments that include insight and criticism. I reserve the right to change the marking scheme. Background. ----------- In DataLab, I have inserted slots for 'user' functions, i.e. so that users can fill in their own functions. I have provided templates, so that most of the hassle of programming DataLab is sidestepped. (a) Here are the entries in the DataLab function table: "user1", 201, 2, 1, 1, 0, "user2", 202, 2, 1, 1, 0, (b) here are the calls to the functions: case 201: ret=user1(&im[dd[0]],&im[ss[0]],&im[ss[1]],args); break; case 202: closegraph(); ret=user2(&im[dd[0]],&im[ss[0]],&im[ss[1]],args); CMbegin(&w,&werr,&pp); break; (c) the module 'user' (user.c, user.h) is available in U:\jc\dl\s You will notice that 'user1' merely adds two images to produce a third (the 'argument') is ignored. 'user2' (selection 1) does convolution using eqn 3.8-7; this convolution das been encapsulated in function 'conv1'; selection 2 is meant to do convolution using the alternative form - eqn 3.8-6. It does NOT use the 'centred' convolution scheme given in chapter 4 - in other words, the convolution mask has indices [0..rowmax-1], [0..cmax-1], instead of [-rowmax/2..+rowmax/2] ... (d) I have also created a 'dl' batch file 'ipuser.dl' that creates images, reads in images and exercises functions user1, and user2. (e) I have created a DOS batch file 'dlmake.bat' that makes a full set of DataLab directories on the C:\scratch directory - this will allow you to develop your own software. (f) Make sure to load 'project-file' 'dl.prj', and ensure that it has directories set appropriately. Note: in 'user.c' you will find the answers to last years equivalent assignment, i.e. median filtering, and various forms of convolution. I have decided to leave them there -- they may be of assistance. References: 1. Course Notes Chapters 3, 4, 9. 2. DataLab Users' Manual. 3. DataLab Programmers' Manual. 4. You may need to consult a text-book regarding 'template- matching'. Tasks: ------ 1. (a) Implement a function 'oorf' -- analogous to 'conv2' -- that performs out-of-range filtering as described in Chapter 4.14.4. (b) Test it with appropriate data (read from file). (c) Compare a 3 x 3 smoothing filter to a 3 x 3 'oorf' filter. Required: 1.1 Software for 'oorf' - commented as neccessary. 1.2 Data printouts for each of tests of 'oorf' and comparison with 3 x 3 smoothing - input images f[], - output images g[]. These data should be commented as neccessary. Note: DataLab function 'tps', prints 'images' on the screen, 'tpf' '' '' in a file, 'tpp' '' '' on a printer. 2. (a) Implement a function 'msstr' that performs the statistical contrast enhancement given by equation 4.7-1, chapter 4.7. The desired mean (m') and standard deviation (s') should be input, by the user, as arguments. (b) Carry out tests to verify its performance. Required: 2.1 Software for 'msstr' - commented as neccessary. 2.2 Data printouts for each of your tests. These data should be commented as neccessary. 3. (a) Implement the function 'rfdft' given in Chapter 3.6. Note I have not tested this, so ther may be minor errors. void rfdft( float x[], /*- real input -*/ float xro[], float xio[],/*- real and imag. outputs -*/ int N) /*- length -*/ { float pi = 3.1415926,tpi; int n, u; tpi=2.0*pi; for(u=0;u Hav. [4 marks] 3. Answer 3.A OR 3.B, OR 3.C. (ONE out of three) A. Very briefly, write short notes to explain TWO major deficiencies of a data compression scheme such as Huffman codes, and explain how dictionary or sliding-window based methods (e.g. some variants of the Lempel-Ziv compression scheme) can remedy these deficiencies. B. Discuss the principle of employing Fourier (or similar) transforms in signal or image data compression. [6 marks] C. Discuss vector quantisation. [Hint: segmentation]. [6 marks] Appendix. Definitions, Formulae, and Algorithms. Entropy. -------- Average entropy, Hav = - sum { p(zi).log2[p(zi)] } Logarithm to base B in terms of log10. ------------------------------------- logB(x) = log10(x)/log10(B). log10(2) = 0.3010 ie. log2(x) = log10(x)/0.3010 = 3.322 . log10(x) Huffman coding procedure. ------------------------- 1. List the symbols, along with their probability. 2. Pick the two least probable nodes. 3. Make a new node out of these two - adding the probabilities. 4. Repeat steps 2, 3, until only one node remains - the root. 5. Bit allocation. Starting at the root, allocate 1 to one branch (left, say), and 0 to the other; until all branches have been allocated. 6. Read out the codes. Starting at the root, travel to the leaf that represents each level, reading off the bits that make up the code for that level. end. University of Ulster, Magee College. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1995. Lecturer: J.G. Campbell. Date: / /95 Supplemental Class Test: 33.3% of C/W Marks. 11/12/1995 11.00am-12.05pm. There are 49 potential marks in this test, 100% coursework credit will correspond to about 42. 1. Compare and contrast the image enhancement techniques: linear contrast stretching, histogram equalisation. In your answer, be careful to mention the type of image, and applications, to which these techniques are particularly suitable. In addition, explain why these are called POINT enhancement methods. [10 marks] (b) An 8 x 8 3-bit (8-level) image is shown in Figure 1. Compute (preferably using the algorithm given in the Appendix) the grey level transformation, T(z), required for histogram equalisation. Apply T(z) to obtain the enhanced output image. Comment on all your results. [12 marks] 0 1 2 3 5 4 4 3 6 1 2 3 5 4 4 3 6 1 2 3 3 4 4 5 6 3 2 3 5 4 4 3 2 4 2 3 3 4 4 5 2 5 2 3 3 4 4 5 2 5 2 3 3 4 4 5 7 5 2 3 3 5 4 4 Figure 1 --------- (c) What is the probability density function for the image; N.B. you really don't need this for part (b). [2 marks] 2. Discrete Convolution. The following equations define two-dimensional discrete convolution: N-1 M-1 (2-1) g[r,c] = sum sum f[r-k,c-l].h[k,l] k=0 l=0 r c (2-2) g[r,c] = sum sum f[k,l].h[r-k,c-l] k=r-N+1 l=c-M+1 In each case, h[.,.] is an N x M two-dimensional image, row: [0..N-1], column: [0..M-1]. For part (b), assume that f[.,.] and g[.,.] are NR x NC. (a) Pick one of them (*), explain the components, and explain, physically / practically, what it is doing. You should specifically explain which part of the equation is often called the impulse response, any why. [12 marks] (*) If you prefer, use the following ONE-dimensional equivalents, and answer the same question - the marks are the same. M-1 (2-3) y[n] = sum x[n-m].h[m] m=0 m=n (2-4) y[n] = sum x[m].h[n-m] m=n-M+1 In each case, h[.] is an M sample discrete sequence. For part (b), assume that y[.] and x[.] are N samples long.. (b) Referring to one of the equations above, write a computer program, to implement either one- or two-dimensional convolution. [Use any language you wish, or pseudo-code if you prefer; do NOT concern yourself with edge effects]. [6 marks] (c) Convolve f[.,.] with h[.,.] and comment on the result. [7 marks] h[.,.] = 0 1 2 1 1 2 1 2 3 f[.,.] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Appendix A: Formulae and Algorithms for Image Processing -------------------------------------------------------- Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = # # f[k,l].h[r-k,c-l] k=0 l=0 Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N) # x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = # X[u] exp(+j.2PI.u.n/N) n=0 Linear Contrast Stretch. ----------------------- z' = T(z) = (zG-z0).(z-a)/(b-a) + z0 where z = input value z'= output value z0..zG = desired output range a..b = input range. Histogram / Probability Distribution Transformation. ---------------------------------------------------- Notation: Input grey levels z, Output grey levels w, Transformation (lut) w = T(z), Input probability distribution p(z), cdf P(z) Desired (output) distribution q(w), cdf Q(w) Np = number of pixels in image. Algorithm: (1) Estimate frequency of grey levels (histogram), ph(z). (2) From ph(z) compute p(z) = ph(z)/Np. (3) Form cdfs P(z), and Q(w), from p() and q(), respectively, z' eg. P(z') = # p(z) z=z0 (4) for each z in the input do: choose w such that Q(w) is closest to P(z), set T(z) = w; (5) Apply T(z) to input image f1[r,c]: f2[r,c] = T(f1[r,c]) end. University of Ulster, Magee College. Notes for PgDip / MSc KBS 19/12/95. Lecturer: J.G. Campbell. Date: / /95 Some Questions on Neural Networks from previous Architecture & OS and Image Processing Exams. The A&OS course is BSc1, so these questions are a little easier than PgDip/MSc might expect. For a KBS course it could be argued that the applications _could_ be biased away from AND gates etc., however, implementation of such functions by NN are very important in the discussion of the contribution of NN to AI, and to 'real' brain modelling. And, of course the XOR is important since it exposed a problem with one layer networks, i.e. a single layer could implement only a *single* linear boundary, whilst XOR requires two boundaries, which in turn require one neuron for each boundary, and then the results of these need to be combined -- another layer. Before backpropogation, there was no way to train other than a single layer. Now, we can train arbitrarily sized networks (theoretically, at least), and hence, *any* (well almost!) function can be approximated by an appropriately configured and trained neural network. The Image Processing course is BSc4, so the general parts of the questions might match what would be expected of PgDip / MSc; as for applications, those for the KBS module might be expected to be biased towards general decision making -- rather than, for example, pattern recognition or image processing. On the other hand, as treated in these courses, neural networks are *always* covered with a focus on their abilities to approximate functions -- mostly decision functions (with discrete binary outputs). To my mind, quantitative decision-making is decision- making, I don't care whether my input data are extracted from a balance sheet, questionnaire, or from measurements of marks on a page!. As well as working through questions such as those following, I's *strongly* urge you to look carefully at what was handed out at the lecture -- I'm fairly sure I meant that to be as 'complete' as possible. A&OS Questions. 8. (a) In an artificial neural network, describe the activities carried out by a single (neuron) processing unit, and explain what components of the network represent its 'memory'. [8 marks] (b) Explain how the neuron shown in Figure 8-1 computes the AND function (F = A AND B). [5 marks] A +1 \ | \0.35 | \ |-0.5 \ | +--+--+ B 0.35 | | ------------+ +------------> F | | +--+--+ (c) Explain how a single neuron may be used to recognise patterns, eg. the letter 'C' shown in Figure 8-2. [5 marks] Pixel number: 1 2 3 +----+----+----+ |****|****|****| |****|****|****| +----+----+----+ 4 |****|5 |6 | |****| | | +----+----+----+ |****|****|****| |****|****|****| +----+----+----+ 7 8 9 x1=1, x2=1, x3=1, x4=1, x5=0, x6=0, x7=1, x8=1, x9=1. 'T' would give: 1,1,1, 0,1,0, 0,1,0 'O': 1,1,1, 1,0,1, 1,1,1 etc... Figure 8-1 A Letter C ---------------------- 9. (a) Outline the structure of an artificial neural network, describe the activities carried out by a single (neuron) processing unit. [8 marks] (b) Explain the process of 'training' a neural network differs from programming a computer or designing logic circuitry; explain how 'training' affects the network, ie. what components of the network represent its 'memory'. [4 marks] (c) Explain how the network shown in Figure 9-1 computes the 'exclusive-OR' function. [ 1 XOR 1 = 0, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1] [4 marks] (d) Referring to Figure 9-2, derive the values of W22, and W12, required to make the network compute the 'AND' function, for binary inputs. [ x AND y = 1, if x = 1, y = 1, = 0, otherwise ]. [4 marks] ------------------------------------------------------------------- BSc4 Image Processing Questions. 7. Neural Networks and Pattern Recognition. (a) What is meant by the statement, "neural networks are trained, not programmed", and explain one major advantage, and one major disadvantage of this fact. [10 marks] (b) What is the significance of the XOR function in the history and theory of neural networks. [6 marks] (c) Figure 7-1 below shows four two-pixel images and their associated classes (class 0 or class 1); '*' denotes bright, value 1, blank denotes dark, value 0; describe a neural network that will distinguish class 1 objects from class 0. [9 marks] x1 x2 +-----+-----+ |*****|*****| class 1 |*****|*****| +-----+-----+ x1 x2 +-----+-----+ |*****| | class 0 |*****| | +-----+-----+ x1 x2 +-----+-----+ | |*****| class 0 | |*****| +-----+-----+ x1 x2 +-----+-----+ | | | class 0 | | | +-----+-----+ Figure 7-1 ---------- 2. [20 marks] (a) Draw a scatter plot for the data set given in Figure 2-1; use graph-paper if you wish. [3 marks] (b) Explain how you would 'train' a nearest mean classifier on data set given in Figure 2-1, and do it. [4 marks] (c) How, normally, would you test such a classifier -- explain any pitfalls. [4 marks] (d) Apply the nearest neighbour classifier to the points 0,2 2,1.5 4,4 [3 marks] (e) Describe the application of a one layer neural network to the classification task (again training data = Figure 2-1) . [Hint: w00 = -1, w01 = -1, w02 = 4] [6 marks] label x0 x1 1 : 0.00 1.00 1 : 1.00 0.00 1 : 1.00 1.00 1 : 1.00 2.00 1 : 2.00 1.00 2 : 3.00 2.00 2 : 2.00 3.00 2 : 3.00 3.00 2 : 4.00 3.00 2 : 3.00 4.00 7. Artificial neural networks. (a) Describe the activities carried out by a single (neuron) processing unit; explain what components of the network represent its 'memory', and explain what is meant by the statement 'neural networks are trained, not programmed'. [10 marks] (b) Explain how the neuron shown in Figure 8-1 computes the AND function (F = A AND B); show how an alternative choice of weights can implement an 'OR' neuron. [4 marks] A +1 \ | \0.35 | \ |-0.5 \ | +--+--+ B 0.35 | | ------------+ +------------> F | | +--+--+ (c) Explain how you would apply a neural network to pattern recognition. Identify a major weakness of single layer neural network and explain how a multilayer network can overcome this weakness. [6 marks] end. 1994 stuff follows. Class Test No. 1 20 % of C/W Marks. 12/12/1994 10.10am 11.15am ----------------------------------- 1. [20 marks] The following 10 x 10 image Figure 1-1, is a small part of an infra-red satellite image of water (top left) and land (bottom left). [Note, you will have worked with such data before, but, to ease calculation, the data have been divided by 10]. (i) Segment the image using: (a) thresholding based on histogram, i.e. first obtain h(z), for z = 0, 1 .. 14; [6 marks] (b) k-means clustering (k=2); use any shortcut you wish -- e.g. choose initial values for your means, e.g. ma = 1, mb = 10. [6 marks] (c) Figures 1-2, and 1-3 show further colours / bands; (c-1) assuming your segmentation from (b) is correct, what, roughly, are the three-dimensional mean vectors for water, mw, and land ml, respectively. [3 marks]. (c-2) Comment on the discriminating power, for water versus land, of the three colours. [2 marks] (d) Look at your histogram again, and comment on the assumption of two classes (k=2). [3 marks] 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 2 1 1 1 1 1 2 6 10 1 1 1 4 4 7 12 13 1 4 8 7 7 11 13 11 5 11 8 7 10 13 14 12 10 10 9 11 13 14 14 13 Figure 1-1 Infra-red Image. 1 2 3 3 2 2 2 2 2 3 2 2 2 3 2 1 3 2 3 3 3 2 3 4 3 3 4 4 3 3 5 7 4 6 5 3 3 5 7 7 7 5 3 4 6 7 7 7 6 3 4 6 7 9 9 9 4 3 5 7 8 10 10 10 Figure 1-2 Red 3 3 3 4 3 4 3 3 3 3 3 3 3 3 3 2 3 3 4 5 3 3 3 3 4 4 4 4 3 2 5 6 6 4 3 3 3 3 5 6 5 3 3 4 4 5 6 6 3 2 3 4 6 6 6 6 3 2 3 6 6 6 7 6 Figure 1-3 Green. 2. [20 marks] (a) Draw a scatter plot for the data set given in Figure 2-1; use graph-paper if you wish. [3 marks] (b) Explain how you would 'train' a nearest mean classifier on data set given in Figure 2-1, and do it. [4 marks] (c) How, normally, would you test such a classifier -- explain any pitfalls. [4 marks] (d) Apply the nearest neighbour classifier to the points 0,2 2,1.5 4,4 [3 marks] (e) Describe the application of a one layer neural network to the classification task (again training data = Figure 2-1) . [Hint: w00 = -1, w01 = -1, w02 = 4] [6 marks] label x0 x1 1 : 0.00 1.00 1 : 1.00 0.00 1 : 1.00 1.00 1 : 1.00 2.00 1 : 2.00 1.00 2 : 3.00 2.00 2 : 2.00 3.00 2 : 3.00 3.00 2 : 4.00 3.00 2 : 3.00 4.00 end. University of Ulster, Magee College. Faculty of Informatics. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1994. Lecturer: J.G. Campbell. Date: / /94 Class Test No. 2 20 % of C/W Marks. 19/12/1994 10.00am-11.00am ----------------------------------- 1. Image data compression. (i) Explain the terms: ENTROPY or INFORMATION, REDUNDANCY or INDEPENDENCE, in the context of image data compression. [8 marks] (b) (i) Compute the probability density function of the 10 x 10 image given in Figure 6-1 below. Hence, derive the average entropy per symbol / pixel. Derive a Huffman code for this image and compute the average length of the Huffman codewords (averaged over the image) [If you wish, refer to the Huffman algorithm given in the Appendix]. Assuming that the image is originally coded with 3 bit pixels, and, neglecting the space occupied by the code table, derive the compression performance of the Huffman code. Hence compare this compression performance with that of the theoretically optimum source code. Note: log2(0.25) = -2.0, log2(0.2) = -2.32, log2(0.15) = -2.74 (b) (ii) Derive a Huffman code, or some other compression scheme of your choice, for the image given in Figure 6-2 below, and, hence, derive the savings compared to 'plain' 8-bit coding. [Hint: if using Huffman, carefully compare this image with the one in Figure 6-1]. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 Figure 6-1 ---------- 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Figure 6-2 ---------- [12 marks] (ii) (b) Derive a Huffman code, or some other compression scheme of your choice, for the image given in Figure 6-2 below, and, hence, derive the savings compared to 'plain' 8-bit coding. [Hint: if using Huffman, carefully compare this image with the one in Figure 6-1]. 4 marks 2. (a) Explain how a Discrete Fourier Transform may be used to do frequency analysis of a sampled waveform. [6 marks] (b) Consider a CD signal sequence; each channel is sampled at fs=44.1 KHz. Take a one second sequence, ie. 44,100 samples. Show how you would provide a frequency analysis of this sequence and provide output corresponding to 10 bands: B1: 0-2000 Hz, B2: 2- 4Khz, 4-6Khz, ..., B10: 18-20KHz. [7 marks] (c) You take the DFT of a 8 sample sequence, and get the following: u 0 1 2 3 4 5 6 7 Xc[u] 1 0 0 0 0 0 0 0 Xs[u] 0 0 0 0 0 0 0 0 Answer with explanation: what does the sequence x[n], n=0..7 look like? [3 marks] (d) You take the DFT of a 8 sample sequence, and get the following: u 0 1 2 3 4 5 6 7 Xc[u] 0 1 0 0 0 0 0 1 Xs[u] 0 0 0 0 0 0 0 0 Answer with explanation: what does the sequence x[n], n=0..7 look like? [4 marks] end. University of Ulster, Magee College. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1994. Lecturer: J.G. Campbell. Date: 12/11/94 Examination Autumn Term 1994 ---------------------------- Answer any FOUR questions. All questions carry equal marks. 1. Machine Inspection Applications of Image Processing. You are developing a system for automatic inspection for denim fabric manufacture. Under the following headings, describe the major issues that will occupy you - giving where possible definite problems, solutions, and other suggestions. (a) image acquisition, (b) preprocessing, e.g. calibration, noise reduction, (c) data volumes and data rates, (d) algorithms for fault detection, (e) economic rationale for such a system. [25 marks] 2. Linear Shift-invariant Filters, and Non-linear Filters. (a) Compare and contrast linear shift-invariant filters, with non-linear filters; [Suggestion: you could indicate what is the essential matter that distinguishes linear from non-linear, what implications this has on implementation, and give specific examples of instances and applications of each] [12 marks] (b) The image given in Figure 2-1 is corrupted with 'salt' (the 99s) and 'pepper' (the 01s and 02s) noise. Discuss at least TWO possible filtering methods to reduce this noise, pointing out their strengths and weaknesses specific to this application. [We do NOT require you to filter the whole image, just pick key areas / pixels to exemplify your answer]. [8 marks] 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 01 21 21 21 21 21 21 21 21 02 21 21 21 21 21 21 21 21 21 21 99 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 99 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 42 42 42 02 42 42 99 42 21 21 21 21 21 21 21 21 42 42 42 42 42 42 42 42 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 99 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 Figure 2-1 2(c) What is the general principle behind the use of summation / averaging in noise reduction? [5 marks] 3. Edge Enhancement and Detection. (a) Explain the use of gradient operators (filters) in image sharpening and edge enhancement; explain further steps that must be performed to fully DETECT edges; be careful to explain the role of gradient. [12 marks] (b) Use a Sobel gradient filter to enhance the edges in the image in Figure 3-1. Comment on your result. [8 marks] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 3-1 (c) Describe one practical application of edge detection. [5 marks]. 4. Discrete Convolution. The following equations define two-dimensional discrete convolution: N-1 M-1 (4-1) g[r,c] = sum sum f[r-k,c-l].h[k,l] k=0 l=0 r c (4-2) g[r,c] = sum sum f[k,l].h[r-k,c-l] k=r-N+1 l=c-M+1 In each case, h[.,.] is an N x M two-dimensional image, row: [0..N-1], column: [0..M-1]. For part (b), assume that f[.,.] and g[.,.] are NR x NC. (a) Pick one of them (*), explain the components, and explain, physically / practically, what it is doing. You should specifically explain which part of the equation is often called the impulse response, any why. [12 marks] (*) If you prefer, use the following ONE-dimensional equivalents, and answer the same question - the marks are the same. M-1 (4-3) y[n] = sum x[n-m].h[m] m=0 m=n (4-4) y[n] = sum x[m].h[n-m] m=n-M+1 In each case, h[.] is an M sample discrete sequence. For part (b), assume that y[.] and x[.] are N samples long. (b) Referring to one of the equations above, write a computer program, to implement either one- or two-dimensional convolution. [Use any language you wish, or pseudo-code if you prefer; do NOT concern yourself with edge effects]. [6 marks] 4(c) Convolve f[.,.] with h[.,.] and comment on the result. [7 marks] h[.,.] = 0 1 2 1 1 2 1 2 3 f[.,.] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5. Discrete Fourier Transform. (a) Explain how the Discrete Fourier Transform can be used to do spectrum analysis. [8 marks] (b) Compute the frequency spectrum of a digital signal containing an 'impulse' x[n] = {1,0,0,0,0.....}; [7 marks] (c) How can a version of the Discrete Fourier Transform be used to perform 'fast' convolutions or correlations; give numerical examples of the performance improvements that can be obtained. [8 marks] 6. Pattern Classification. Figure 6-1 summarises a general pattern classification system. +-----------------+ +---------------+ | | | | Observ- | Feature |Feature | Classifier |Deci --------->| Extraction |-------->| |---> -ation x | |Vector y | |sion Vector | | | | w +-----------------+ +---------------+ Figure 6-1 Pattern Classification System ---------------------------------------- (a) Explain the components of Figure 6-1. [10 marks] (b) Explain the roles of EITHER distance, OR, discriminants, in pattern classification algorithms. [5 marks] (c) Table 6-1 below shows two-dimensional feature data for a two- class problem. (i) Explain the use of a nearest mean classifier, and one other relatively different classification method, to solve the problem. (ii) Verify that either of the dimensions, alone, is inadequate to separate the data. [10 marks] [Hint: a scatter diagram, and / or a histogram will help you a lot]. Class x1 x2 ---------------- 1 0.4 1.0 1 1.0 0.4 1 1.0 1.0 1 1.0 1.6 1 1.6 1.0 2 1.4 2.0 2 2.0 1.4 2 2.0 2.0 2 2.0 2.6 2 2.6 2.0 Table 6-1 Two-class, Two-dimensional feature data. -------------------------------------------------- 7. Neural Networks and Pattern Recognition. (a) What is meant by the statement, "neural networks are trained, not programmed", and explain one major advantage, and one major disadvantage of this fact. [10 marks] (b) What is the significance of the XOR function in the history and theory of neural networks. [6 marks] (c) Figure 7-1 below shows four two-pixel images and their associated classes (class 0 or class 1); '*' denotes bright, value 1, blank denotes dark, value 0; describe a neural network that will distinguish class 1 objects from class 0. [9 marks] x1 x2 +-----+-----+ |*****|*****| class 1 |*****|*****| +-----+-----+ x1 x2 +-----+-----+ |*****| | class 0 |*****| | +-----+-----+ x1 x2 +-----+-----+ | |*****| class 0 | |*****| +-----+-----+ x1 x2 +-----+-----+ | | | class 0 | | | +-----+-----+ Figure 7-1 ---------- 8. Data Compression. (a) Distinguish between LOSSY and LOSSLESS data compression; give instances of each, and give examples of applications that CAN, and CANNOT tolerate lossy compression. [6 marks] (b) Describe a numerical measure of information (see Appendix); in your answer, as well as giving a precise definition of the measure, you should give intuitive explanation of how it can be applied to any sort of 'information', not just numerical data. [8 marks] (c) A two-bit image has relative frequency of occurrence (probabilities) of grey levels as follows: grey-level(i) 0 1 2 3 frequency (pi) 0.5 0.25 0.125 0.125 (i) show that the average entropy per pixel is 1.75. [3 marks] (ii) Suggest a coding scheme that will allow the image to be compressed from two bits per pixel to an average of 1.75 bits per pixel. [We do NOT require detailed working of any algorithm or formula]. [2 marks] (iii) Prove, either mathematically, or intuitively, that your scheme in (ii) will actually achieve 1.75 bits per symbol.[3 marks] (iv) Identify ONE difficulty with single symbol entropy based methods, and suggest one way the difficulty can be reduced. [3 marks] Appendix A: Formulae and Algorithms for Image Processing -------------------------------------------------------- Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = sum sum f[k,l].h[r-k,c-l] k=0 l=0 Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N)sum x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = sum X[u] exp(+j.2PI.u.n/N) n=0 Linear Contrast Stretch. ----------------------- z' = T(z) = (zG-z0).(z-a)/(b-a) + z0 where z = input value z'= output value z0..zG = desired output range a..b = input range. Histogram / Probability Distribution Transformation. ---------------------------------------------------- Notation: Input grey levels z, Output grey levels w, Transformation (lut) w = T(z), Input probability distribution p(z), cdf P(z) Desired (output) distribution q(w), cdf Q(w) Np = number of pixels in image. Algorithm: (1) Estimate frequency of grey levels (histogram), ph(z). (2) From ph(z) compute p(z) = ph(z)/Np. (3) Form cdfs P(z), and Q(w), from p() and q(), respectively, z' eg. P(z') = sum p(z) z=z0 (4) for each z in the input do: choose w such that Q(w) is closest to P(z), set T(z) = w; (5) Apply T(z) to input image f1[r,c]: f2[r,c] = T(f1[r,c]) Entropy. -------- Average entropy, Hav = - sum { p(zi).log2[p(zi)] } Logarithm to base B in terms of log10. ------------------------------------- logB(x) = log10(x)/log10(B). log10(2) = 0.3010 ie. log2(x) = log10(x)/0.3010 = 3.322 . log10(x) Huffman coding procedure. ------------------------- 1. List the symbols, along with their probability. 2. Pick the two least probable nodes. 3. Make a new node out of these two - adding the probabilities. 4. Repeat steps 2, 3, until only one node remains - the root. 5. Bit allocation. Starting at the root, allocate 1 to one branch (left, say), and 0 to the other; until all branches have been allocated. 6. Read out the codes. Starting at the root, travel to the leaf that represents each level, reading off the bits that make up the code for that level. Sigmoid activation function. ---------------------------- sigmoid(x) = 1/(1+exp(-x)) Procedure k-Means Clustering: Inputs: nc = number of classes, xij data to be clustered; i=1..d; j=1..N d = dimensionality of data vectors N = total number of pixels. Outputs: labj, j=1..N, labels of pixels xj labj = {1..nc} 1. Partition the pixels arbitrarily into nc classes (labels), eg. divide the image into nc regions, label all the pixels in the first region '1', second region, label '2', etc. 2. Compute the mean vectors of each class: m[i][c], i=1..d, c=1..nc 3. Procedure: k-Means Classifier: 3.0 Change = False 3.1 for j = 1..N do 3.2 reset Distmin = Bignumber, class = 0 3.3 Find nearest mean: 3.3.1 for c = 1..nc do 3.3.2 Compute Dist = Distance (xj to mean mc) 3.3.3 if Dist < Distmin then Distmin = Dist class = c 3.3.4 end. 3.4 labj = class; if 'changed' set Change = True. 3.5 end. 4. if Change = True goto 2 (*loop again*) 5. end. (* we are finished*) Function Distance(x,m) (*this calculates squared Euclidean distance - because there is no need to take square root, since we are not interested in actual values, just in finding the minimum*) Dist = 0 for i = 1 .. d do Dist = Dist + (xi -mi)**2 (*Euclidean distance*) return Dist end. end of examination paper. University of Ulster, Magee College. BSc. Applied Computing (1220), Year 4. Course: Image Processing (AC460). Autumn Term 1994. Lecturer: J.G. Campbell. Date: / /94 Revision Questions and Old Exam Papers. --------------------------------------- Supplemental EXAMINATION May 1994. ---------------------------------- QUESTIONS only Answer any FIVE questions; all questions carry equal marks. Exams. office, please remove this page; please note Appendices to be included. 1. (a) Explain in detail the steps in the progression from a 3- dimensional scene to a two-dimensional digital image. [10 marks] (b) Explain, using appropriate examples, why it is neccessary, in an image processing application, to carefully tradeoff spatial resolution versus data volume. [4 marks] (c) An industrial inspection system is monitoring lace manufacture; one requirement is to detect very small stich flaws in the lace. The structure of the lace is such that thread width is 0.1 mm and thread separation is 0.5 mm; (i) Supporting your work with appropriate illustrations, derive a suitable sampling resolution (in millimeters). (ii) Discuss data-rates and data volumes for this problem. [6 marks] 2. Image Processing Applications. Explain how digital image processing may be applied to ONE of the following: (a) Medical PACS (Picture Archiving and Communication Systems). (b) Document image processing. [Suggestion. Full marks would be obtained for an answer containing: - an appropriate system block diagram that identifies the major components of the system, - a description of each component (function / processing performed), - an indication of the state-of-the-art, - a description of the major problem / risk areas, - a description of a potential solution to one or more of the problem areas.] 3. Discrete Fourier Transform and Frequency Analysis. (a) Explain how a Discrete Fourier Transform may be used to do frequency analysis of a sampled waveform. [8 marks] (b) Consider a CD signal sequence; each channel is sampled at fs=44.1 KHz. Take a one second sequence, show how you would provide a frequency analysis of this sequence and provide output corresponding to 10 bands: 0-2KHz, 2-3Khz, 4-5Khz, etc. [4 marks] (c) Show that the 8-point DFT of a sequence containing a constant value x[n] = {1,1,1,1,1,1,1,1} is Xr = {1,0,0,0,0,0,0,0} Xi = {0,0,0,0,0,0,0,0} and explain the meaning of this result. [8 marks] 4. Image Enhancement. (a) Explain image enhancement, paying particular attention to what is meant by (i) NOISE, (ii) POINT / pixel operations, (iii) SPATIAL operations. [10 marks] (b) Use Figure 4-1 to compare and contrast image enhancement using (i) a median filter, (ii) an averaging filter (in each case use 3 x 3 filters). [10 marks] 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 9 1 1 5 5 5 5 5 5 5 0 1 5 5 5 5 5 5 5 1 1 5 5 4 5 4 5 5 0 1 1 9 5 9 5 1 1 1 1 1 1 5 5 5 9 1 1 1 1 1 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 Figure 4-1 5. Data Compression. (a) Explain, using appropriate examples, how ENTROPY can be used as a numerical measure of information. [8 marks] (b) Explain, using an example, how REDUNDANCY reduces the entropy of a source. [4 marks] (c) The distribution of values in an image is: z 0 1 2 3 p(z) 0.5 0.25 0.125 0.125 (i) What is he average entropy per symbol ? [Note: log2(1/2) = -1, log2(1/4) = -2, log2(1/8) = -3] (ii) Show that the following choice of codewords is optimal, and demonstrate that the code is uniquely decodable. z 0 1 2 3 p(z) 0.5 0.25 0.125 0.125 code 0 10 110 111 [8 marks] 6. Image Pattern Recognition. [Answer either 6A or 6B.] 6A. (a) Using appropriate pictorial or numerical illustrations, explain the roles of FEATURE VECTOR and FEATURE EXTRACTION in pattern recognition. [10 marks] (b) Define one or two invariant features that will distinguish the shapes given below (you don't need to give a detailed implementation of the feature extraction technique); plot each shape on a feature space diagram. [6 marks] (c) Describe and illustrate an appropriate classification technique. [4 marks] ********** ***** * ********** ***** ** ********** ***** *** ********** ***** **** ********** ***** ***** ********** ***** ****** ********** ***** ******* ********** ***** ******** OR 6B. Outline the functional requirements an industrial inspection system that must identify, and monitor for shape conformance, flat objects passing along a conveyer belt. The system will use a television camera as input; it must alert an operator in the case of non-conformance. The system must be capable of being adapted to virtually any (flat) shape - but only one at a time. Assume that there is no problem of occlusion (overlapping) on the conveyer belt. [20 marks] 7. Neural Networks and Pattern Recognition. (a) Describe the operation of a two-input, single layer neural network, and discuss the difficulty of implementing an XOR function using such a network. [10 marks] (b) Figure 8 below shows four two-pixel images and their associated classes (class 0 or class 1); '*' denotes bright, value 1, blank denotes dark, value 0; describe a neural network that will distinguish class 1 objects from class 0. [10 marks] x1 x2 +-----+-----+ |*****|*****| class 1 |*****|*****| +-----+-----+ x1 x2 +-----+-----+ |*****| | class 0 |*****| | +-----+-----+ x1 x2 +-----+-----+ | |*****| class 0 | |*****| +-----+-----+ x1 x2 +-----+-----+ | | | class 0 | | | +-----+-----+ Figure 8 -------- Appendix A: Formulae and Algorithms for Image Processing -------------------------------------------------------- Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = # # f[k,l].h[r-k,c-l] k=0 l=0 Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N) # x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = # X[u] exp(+j.2PI.u.n/N) n=0 Linear Contrast Stretch. ----------------------- z' = T(z) = (zG-z0).(z-a)/(b-a) + z0 where z = input value z'= output value z0..zG = desired output range a..b = input range. Histogram / Probability Distribution Transformation. ---------------------------------------------------- Notation: Input grey levels z, Output grey levels w, Transformation (lut) w = T(z), Input probability distribution p(z), cdf P(z) Desired (output) distribution q(w), cdf Q(w) Np = number of pixels in image. Algorithm: (1) Estimate frequency of grey levels (histogram), ph(z). (2) From ph(z) compute p(z) = ph(z)/Np. (3) Form cdfs P(z), and Q(w), from p() and q(), respectively, z' eg. P(z') = # p(z) z=z0 (4) for each z in the input do: choose w such that Q(w) is closest to P(z), set T(z) = w; (5) Apply T(z) to input image f1[r,c]: f2[r,c] = T(f1[r,c]) Entropy. -------- Average entropy, Hav = - # p(zi).log2[p(zi)] Logarithm to base B in terms of log10. ------------------------------------- logB(x) = log10(x)/log10(B). log10(2) = 0.3010 ie. log2(x) = log10(x)/0.3010 = 3.322 . log10(x) Huffman coding procedure. ------------------------- 1. List the symbols, along with their probability. 2. Pick the two least probable nodes. 3. Make a new node out of these two - adding the probabilities. 4. Repeat steps 2, 3, until only one node remains - the root. 5. Bit allocation. Starting at the root, allocate 1 to one branch (left, say), and 0 to the other; until all branches have been allocated. 6. Read out the codes. Starting at the root, travel to the leaf that represents each level, reading off the bits that make up the code for that level. Sigmoid activation function. ---------------------------- sigmoid(x) = 1/(1+exp(-x)) Procedure k-Means Clustering: Inputs: nc = number of classes, xij data to be clustered; i=1..d; j=1..N d = dimensionality of data vectors N = total number of pixels. Outputs: labj, j=1..N, labels of pixels xj labj = {1..nc} 1. Partition the pixels arbitrarily into nc classes (labels), eg. divide the image into nc regions, label all the pixels in the first region '1', second region, label '2', etc. 2. Compute the mean vectors of each class: m[i][c], i=1..d, c=1..nc 3. Procedure: k-Means Classifier: 3.0 Change = False 3.1 for j = 1..N do 3.2 reset Distmin = Bignumber, class = 0 3.3 Find nearest mean: 3.3.1 for c = 1..nc do 3.3.2 Compute Dist = Distance (xj to mean mc) 3.3.3 if Dist < Distmin then Distmin = Dist class = c 3.3.4 end. 3.4 labj = class; if 'changed' set Change = True. 3.5 end. 4. if Change = True goto 2 (*loop again*) 5. end. (* we are finished*) Function Distance(x,m) (*this calculates squared Euclidean distance - because there is no need to take square root, since we are not interested in actual values, just in finding the minimum*) Dist = 0 for i = 1 .. d do Dist = Dist + (xi -mi)**2 (*Euclidean distance*) return Dist end. end of examination paper. EXAMINATION January 1994. ------------------------- QUESTIONS only. Note: the Appendix is intentional. Answer any FIVE questions. 1. Digital Image Fundamentals and Image Sensing. (a) Explain in detail what is a meant by 'digital image'? [10 marks] (b) Explain the components of the image sensing model given in Figure 1-1. Hence, or otherwise, using appropriate numerical or graphical illustrations, explain how a colour light-sensor works. [10 marks] | | illumination, i(\) | V +---------+---------+ | | | Reflectance, r(\) | | | +---------+---------+ | | lightness, g(\) = i(\).r(\) | V +---------+---------+ | | | Filter, t(\) | | | +---------+---------+ | | modified lightness, | g'(\) = t(\).(g(\) V +---------+---------+ | | | Detector, d(\) | | | +---------+---------+ | | voltage, v = ! d(\).g'(\). d\ V 2. Image Processing Applications. Explain how digital image processing may be applied to ONE of the following: (a) Medical X-ray storage, retrieval, communication and analysis. (b) Automatic face recognition. (c) Industrial inspection. (d) Document image processing. (e) Land use monitoring using satellite remotely sensed imagery. (f) Geographical Information Systems. [20 marks] [Suggestion. Full marks would be obtained for an answer containing: - an appropriate system block diagram that identifies the major components of an example system, - a description of each component (function / processing performed), - an indication of the state-of-the-art, - a description of the major problem / risk areas, - a description of a potential solution to one or more of the problem areas, - brief discussion of commercial implications.] 3. Convolution and the Discrete Fourier Transform. (a) Using appropriate numerical or pictorial illustrations, explain convolution, in the context of EITHER (i) digital (1-dimensional) signal processing, or (ii) continuous signal processing, or (iii) digital image processing. [6 marks] (b) Explain the relationship between the equations, and the significance of this relationship: (3-1) y[n] = x[n](*)h[n] and (3-2) Y[u] = N . X[u].H[u] where (*) denotes convolution, and uppercase symbols denote Discrete Fourier Transforms. [4 marks] (c) Show that the DFT of the 'impulse' sequence h[n] = {1,0,0,0,0,0,0,0} is H[u] = {1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8} and, hence, verify the equivalence of the equations (3-1) and (3- 2), for the case of h[n] = {1,0,0,0,0,0,0,0} for ANY x[]. Practically, what does this last result mean? [10 marks] 4. Image Enhancement. (a) Explain the image enhancement techniques: linear contrast stretching, histogram equalisation. In your answer, be careful to mention the type of image, and applications, to which these techniques are particularly suitable. [8 marks] (b) The 8 x 8 3-bit (8-level) image, shown in Figure 4-1 has the histogram given in Figure 4-2. Compute (if you wish, using the algorithm given in the Appendix) the grey level transformation, T(z), required for histogram equalisation. Apply T(z) to obtain the enhanced output image. Comment on all your results. 0 1 2 3 3 4 4 5 6 1 2 3 3 4 4 5 6 1 2 3 3 4 4 5 6 3 2 3 3 4 4 5 2 4 2 3 3 4 4 5 2 5 2 3 3 4 4 5 2 5 2 3 3 4 4 5 7 5 2 3 3 4 4 5 Figure 4-1 ---------- z 0 1 2 3 4 5 6 7 ----------------------------------------- h(z) 1 3 11 17 17 11 3 1 ------------------------------------------ Figure 4-2 ---------- 5. Pattern Recognition and Image Segmentation. (a) Explain the term CLASSIFICATION, making sure to distinguish between SUPERVISED classification and UNSUPERVISED. Explain the role of DISTANCE in classification. [8 marks] (b) Use k-means clustering to segment, into two classes / regions, the 10 x 10 image given in Figure 5-1 [If you wish, refer to the algorithm given in the Appendix]. The image in Figure 5-1 is monochrome, explain what changes you would make to the algorithm, for a multi-colour image. Suggest an improved / alternative segmentation scheme that may, in general, give improved results. [12 marks] 0 1 2 0 2 1 2 0 1 2 1 2 0 2 1 2 0 1 2 0 2 0 2 1 2 8 1 2 0 1 0 1 2 7 8 9 9 8 7 0 1 2 8 8 9 9 8 7 7 1 2 0 1 9 9 8 7 7 8 2 2 0 1 7 8 0 0 7 8 2 0 1 2 0 2 1 2 0 1 2 1 2 0 2 1 6 0 1 2 0 2 0 2 1 2 0 1 2 0 1 Figure 5-1 ---------- 6. Image data compression. (a) Explain the terms: ENTROPY or INFORMATION, REDUNDANCY or INDEPENDENCE, in the context of image data compression. [8 marks] (b) (i) Compute the probability density function of the 10 x 10 image given in Figure 6-1 below. Hence, derive the average entropy per symbol / pixel. Derive a Huffman code for this image and compute the average length of the Huffman codewords (averaged over the image) [If you wish, refer to the Huffman algorithm given in the Appendix]. Assuming that the image is originally coded with 3 bit pixels, and, neglecting the space occupied by the code table, derive the compression performance of the Huffman code. Hence compare this compression performance with that of the theoretically optimum source code. Note: log2(0.25) = -2.0, log2(0.2) = -2.32, log2(0.15) = -2.74 (b) (ii) Derive a Huffman code, or some other compression scheme of your choice, for the image given in Figure 6-2 below, and, hence, derive the savings compared to 'plain' 8-bit coding. [Hint: if using Huffman, carefully compare this image with the one in Figure 6-1]. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 Figure 6-1 ---------- 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Figure 6-2 ---------- [12 marks] 7. Artificial neural networks. (a) Describe the activities carried out by a single (neuron) processing unit; explain what components of the network represent its 'memory', and explain what is meant by the statement 'neural networks are trained, not programmed'. [10 marks] (b) Explain how the neuron shown in Figure 8-1 computes the AND function (F = A AND B); show how an alternative choice of weights can implement an 'OR' neuron. [4 marks] A +1 \ | \0.35 | \ |-0.5 \ | +--+--+ B 0.35 | | ------------+ +------------> F | | +--+--+ (c) Explain how you would apply a neural network to pattern recognition. Identify a major weakness of single layer neural network and explain how a multilayer network can overcome this weakness. [6 marks] Appendix. Formulae and Algorithms for Image Processing ------------------------------------------------------ Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = # # f[k,l].h[r-k,c-l] k=0 l=0 Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N) # x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = # X[u] exp(+j.2PI.u.n/N) n=0 Complex Exponentials: exp(-jB) = cos(B) - j sin(B) ; j = sqrt(-1) cos(0) = 1, cos(PI/4) = sqrt(2)/2 = 0.707, cos(PI/2) = 0 sin(0) = 0, sin(PI/4) = 0.707 sin(PI/2) = 1 PI/4 radians = 45 degrees, PI/2 = 90 degrees. Linear Contrast Stretch. ----------------------- z' = T(z) = (zG-z0).(z-a)/(b-a) + z0 where z = input value z'= output value z0..zG = desired output range a..b = input range. Histogram / Probability Distribution Transformation. ---------------------------------------------------- Notation: Input grey levels z, Output grey levels w, Transformation (lut) w = T(z), Input probability distribution p(z), cdf P(z) Desired (output) distribution q(w), cdf Q(w) Np = number of pixels in image. Algorithm: (1) Estimate frequency of grey levels (histogram), ph(z). (2) From ph(z) compute p(z) = ph(z)/Np. (3) Form cdfs P(z), and Q(w), from p() and q(), respectively, z' eg. P(z') = # p(z) z=z0 (4) for each z in the input do: choose w such that Q(w) is closest to P(z), set T(z) = w; (5) Apply T(z) to input image f1[r,c]: f2[r,c] = T(f1[r,c]) Entropy. -------- Average entropy, Hav = - # p(zi).log2[p(zi)] Logarithm to base B in terms of log10. ------------------------------------- logB(x) = log10(x)/log10(B). log10(2) = 0.3010 ie. log2(x) = log10(x)/0.3010 = 3.322 . log10(x) Huffman coding procedure. ------------------------- 1. List the symbols, along with their probability. 2. Pick the two least probable nodes. 3. Make a new node out of these two - adding the probabilities. 4. Repeat steps 2, 3, until only one node remains - the root. 5. Bit allocation. Starting at the root, allocate 1 to one branch (left, say), and 0 to the other; until all branches have been allocated. 6. Read out the codes. Starting at the root, travel to the leaf that represents each level, reading off the bits that make up the code for that level. Sigmoid activation function. ---------------------------- sigmoid(x) = 1/(1+exp(-x)) end. RESIT EXAMINATION 1993 - identical to Summer 1992 exam. ---------------------- [Note: Appendix A contains formulae that may assist you in your answering some of the questions] 1. An industrial inspection system uses a 256 x 256 element CCD camera. The images produced by the system show three deficiencies: - unevenness of illumination, - uneven bias and gain in the CCD detector elements, - random noise in the detectors (assume zero mean noise). (a) Explain the following formulae and their relevance to the problem: (i) g(x,y) = r(x,y).i(x,y) , [g()=light entering camera]. (ii) f(x,y,t) = a0(x,y)+a1(x,y).g(x,y)+n(x,y,t), [f(x,y,t) = output from detector, at time t, corresponding to point (x,y)] [8 marks] (b) Explain how you would reduce the effects of noise, and calibrate the bias, gain, and uneven illumination. [12 marks] 2. (a) Compare and contrast, 'averaging filters', and 'median filters', as used in image processing. [12 marks] (b) Apply a 3x3 median filter to the image given in Figure 2-1. Comment on your result, and explain, using appropriate example pixels, how an averaging filter of similar size would perform on the same image. [8 marks] 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 9 1 1 5 5 5 5 5 5 5 0 1 5 5 5 5 5 5 5 1 1 5 5 4 5 4 5 5 0 1 1 9 5 9 5 1 1 1 1 1 1 5 5 5 9 1 1 1 1 1 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2-1 ---------- 3. (a) Explain the use of gradient operators (filters) in image sharpening and edge enhancement; explain further steps that must be performed to fully DETECT edges. [12 marks] (b) Use a Sobel gradient filter to enhance the edges in the image in Figure 3-1. [8 marks] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 3-1 ---------- 4. (a) Explain 'convolution', in EITHER digital signal processing (one-dimension), OR digital image processing (two-dimensions). [10 marks] (b) How can a version of the Discrete Fourier Transform be used to perform 'fast' convolutions; give numerical examples of the performance improvements that can be obtained. [10 marks] [N.B. You may answer only one question 5.] EITHER 5. Outline the functional requirements an industrial inspection system that must identify, and monitor for shape conformance, flat objects passing along a conveyer belt. The system will use a television camera as input; it must alert an operator in the case of non-conformance. The system must be capable of being adapted to virtually any (flat) shape - but only one at a time. Assume that there is no problem of occlusion (overlapping) on the conveyer belt. [20 marks] OR 5. Outline a system would automate the process of land-use mapping using multispectral (ie. multicolour) satellite images. Explain how would you evaluate the accuracy of such a system, and explain major pitfalls in such a system. [20 marks] Appendix A: Formula for Image Processing ---------------------------------------- Sobel Gradient Operators: hv = -1 0 +1 hh = -1 -2 -1 -2 0 +2 0 0 0 -1 0 +1 +1 +2 +1 Discrete Convolution: --------------------- +inf y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=-inf For finite sequences: N-1 y[n] = x[n] (*) h[n] = # x[n-m].h[m] m=0 For images: N-1 M-1 g[r,c] = # # f[k,l].h[r-k,c-l] k=0 l=0 Integral Fourier transform: --------------------------- +inf X(w) = (1/2.PI) ! x(t).exp(-jwt) dw -inf Inverse transform: ----------------- +inf x(t) = (1/2.PI) ! X(w)exp(+jwt) dw -inf Discrete Fourier Transform: --------------------------- N-1 X[u] = (1/N) # x[n] exp(-j.2PI.u.n/N) n=0 Inverse DFT: ------------ N-1 x[n] = # X[u] exp(+j.2PI.u.n/N) n=0 end. REVISION QUESTIONS ------------------ You will see that these questions match closely the sorts of questions I set on exams. Also they match closely the questions / exercise interspersed through the notes and end of chapters; also assignment questions. Therefore, I would expect that a clear pattern would emerge - not of exactly what will appear on the exam. but the 'sort' of question that will appear. Practice on questions like this and you will gain a lot. Remember, THE MOST EFFICIENT STUDY METHOD IS not just reading your notes / text, BUT READING THEM WITH THE AIM OF FINDING AN ANSWER TO SOME QUESTION. 1. Usually, an exam. question is composed of two parts: - a theory part - mostly recall; may be either mathematical, or 'descriptive', [usually about 40% of marks] - an application part - show an understanding of the theory (eg. formula, algorithm) by applying in a numerical example [usually about 60% marks]. 2. Often there will be some marks (eg. 15-20%) allocated for 'insight' ie. showing an especially clear understanding of the material. 3. Most of the 'application' questions are of the same form as the Examples and Exercises contained in the notes. Assignments are another good source of such guidelines. PART I Chapters 1 and 2. Digital Image Fundamentals, Sensors, and Calibration. 1. (a) Explain in detail the steps (and data flow) in the progression from a 3-dimensional scene to a two-dimensional digital image. (b) Explain, using appropriate examples, the neccessity to carefully tradeoff spatial resolution versus data volume. (c) An industrial inspection system is monitoring lace manufacture; the fabric is lace, and you want to detect very small stich flaws in it. The structure of the lace is such that thread separation is 0.5 mm. (i) Supporting your work with appropriate illustrations, derive a suitable sampling resolution (in millimeters). (ii) Discuss data-rates and data volumes for this problem. 2. (a) Explain in detail the steps (and data flow) in the progression from a 3-dimensional scene to a two-dimensional digital image. (b) Explain, using appropriate examples, the neccessity to carefully tradeoff spatial resolution versus data volume. (c) A satellite earth observation system is required to be able to monitor landuse in fields of two hectares and above. (i) Supporting your work with appropriate illustrations, derive a suitable spatial ground sampling resolution (in meters). [1 Hectare = 100m x 100m]. (ii) Discuss data-rates and data volumes for this problem. 3. (a) Explain the components of the (monochrome) image sensing model given in the figure below. [8 marks] (b) Essentially, a CCD camera is comprised of many such sensors. Explain how the problem of 'calibration' arises. [4 marks] (c) Distinguish between 'absolute' and 'relative' calibration. [3 marks]. (d) Briefly, explain how you would calibrate / measure detector 'bias' [Hint: d0], and how you would use this result in practice to compensate for uneven bias. [5 marks] | | illumination, i | V +---------+---------+ | | | Reflectance, r | | | +---------+---------+ | | lightness, g = i . r | V +---------+---------+ | | | Filter, t | | | +---------+---------+ | | modified lightness, | g' = t . g V +---------+---------+ | | | Detector, d | | +---------+---------+ | | voltage, v = d0 + d1 . g' V Figure 3-1 ---------- 4. (a) Explain the components of the (monochrome) image sensing model given in Figure 3-1. [8 marks] (b) Essentially, a CCD camera is comprised of many such sensors. Explain how the problem of 'calibration' arises. [4 marks] (c) Distinguish between 'absolute' and 'relative' calibration. [3 marks]. (d) Briefly, explain how you would calibrate / measure detector 'gain' [Hint: d1], and how you would use this result in practice to compensate for uneven gain. [5 marks] 5. Q3. with (d) focussing on noise reduction. 6. Q3. with (d) focussing on uneven illumination. 7. (a) Explain the components of the (monochrome) image sensing model given in Figure 3-1. [8 marks] (b) Extend the equations to include wavelength sensitivity. [NB. the detector will now have an integration]. [6 marks] (c) Hence, use appropriate diagrams and/or equations to explain the operation of a 'colour' sensing (ie. one which senses 'red', 'green' and 'blue'.). [6 marks]. Chapter 3 - Transforms etc. 1. (a) Using appropriate numerical or pictorial illustrations, explain convolution, in the context of EITHER (i) digital (1-dimensional) signal processing, or (ii) continuous signal processing, or (iii) digital image processing. Explain how a Discrete Fourier transform (DFT) may be used to perform convolutions. (b) Compute the DFT of the 'impulse' sequence h[n] = {1,0,0,0,0,0,0,0} Hence or otherwise show, in both the frequency and 'time' domains, that the output of convolution of any sequence with an impulse is the same as the input. 2. (a) Explain how a Discrete Fourier Transform may be used to do frequency analysis of a sampled waveform. [Ans. DFT, amplitude (or power) spectrum, mention highest freq = fs/2, mention who to work out freqs. corresp. to each amplitude spectrum component, perhaps mention how to get frequency 'bands']. (b) Consider a CD signal sequence; each channel is sampled at fs=44.1 KHz. Take a one second sequence, ie. 44,100 samples. Show how you would provide a frequency analysis of this sequence and provide output corresponding to 10 bands: 0-1999 Hz, 2-3Khz, 4- 5Khz, etc. 3. Give an intuitive explanation of the Discrete Fourier transform. (b) Compute the DFT of an 8 sample sequence containing a single cycle of sine-wave, ie. x[n] starts at x[0] = 0, slowly increasing to x[2] = 1, then decreasing to x[4] = 0, and x[6] = -1 ... (c) What is the amplitude spectrum? (d) What is the phase spectrum. 4. (a) ... (b) What is the DFT of a sequence containing a single cycle of cosine-wave. (c) What is the amplitude spectrum? (d) What is the phase spectrum. 5. (a) ... (b) What is the DFT of a sequence containing a constant value x[n] = {1,1,1,1,1,..1}. (c) What is the amplitude spectrum (d) What is the phase spectrum. 6. (a) ... (b) The following is the 'prototype' of a 'C' function that computes the DFT - using the FFT algorithm; void four1(float data[],int N,int isign) The arguments are: data[]: is an array containing the input data; because we must accomodate complex data, the FFT expects both real and imaginary parts; these are interleaved (and, in addition, the arrays are '1' offset, ie. start at index 1): xre0 -> data[1], xim0 -> data[2], ... ie. xre0, xim0, xre1, xim1, ..., xreN-1, ximN-1; Likewise, the output (transformed) data are interleaved: Xre0, Xim0, Xre1, Xim1, ..., XreN-1, XimN-1; or using our earlier notation: Xc0, Xs0, Xc1, Xs1, ..., XcN-1, XsN-1; N: is the length of the array - which must be a power of 2 (2, 4, 8, 16, 32, 1024, ... etc.) isign: defines whether the transform is Inverse (+1) or Forward (-1); all this does is set the sign in the exp( ) to select the appropriate equation: A typical calling program: /* get data from image store */ d=0; /*dimension 0 - assume there is only one */ r=0; /*row 0 - assume there is only one row */ for(j=1,c=cl;c<=ch;c++,j+=2){ IMget(&val,d,r,c,ims); data[j]=val; data[j+1]=0.0; /*zero complex part*/ } /* now do fft */ four1(data,len,-1);/* we use -1 for forward*/ /* now extract re and cmplx parts*/ for(j=1,c=cl;c<=ch;c++,j+=2){ re=data[j]; /* Real and Imaginary are interleaved*/ im=data[j+1]; [&&&] } Frequencies associated with output data. Positive frequencies: data[1] = Xc[0], cosine(0) - DC term data[2] = Xs[0], sine(1) term; always 0 for real input. data[3] = Xc[1], cosine(1) term; freq 1 => 1.df data[4] = Xs[1], sine(1) term data[5] = Xc[2], cosine(2) term freq 2 => 2.df data[6] = Xs[2], sine(2) term ... data[N+1] = Xc[N/2], cos(N/2) term => (N/2).df data[N+2] = Xs[N/2], sin(N/2) term Negative Frequencies. data[N+3] = Xc[N/2 +1], cos(-[N/2+1]) term data[N+4] = Xs[N/2 +1], sin(-[N/2+1]) term ... data[2N] = Xc[N-1] cos(-1) term data[2N+1]= Xs[N-1] sin(-1) term. Insert code at [&&&] to perform the frequency analysis mentioned in question 2(b). Ie. if we have data from a CD, and an FFT of length 32768; write the few lines of program that compute the average amplitude in 10 bands of frequencies between 0 and 20000 Hz. What is the highest frequency available? (c) If, in the program above, the sampling frequency is 10,000 Hz, work out 'df' and, hence, write the few lines of program that compute the amplitude of frequencies (get as close as possible): 0 Hz, 50 Hz, 100 Hz, 3000 Hz, 5000 Hz, 6000 Hz (be careful!). 7. (a) Show that the convolution of a rectangular sequence, {1,1,1,1,0,0,0,0} with itself is a triangular sequence, [shaped like a triangle]. (b) Compute the DFT of the rectangular sequence, and hence its amplitude spectrum. (c) Combine the results of (a) and (b) to compute the DFT of a 'triangle' (your answer may be intuitive, rather than fully numerical). 8. (a) Explain how the DFT can be called a 'transformation? [Ans: DFT(x[]) == A.x where x is the vector corresponding to x[], and A is a square matrix containing terms: exp(-j.2.PI.u.n/N) u = column index, n = row index ] (b) Verify that the DFT and IDFT are indeed inverses of each other. [Hint: find a few elements of C = A.B where A and B are the matrices corresponding to the DFT and IDFT, respectively, and check that C is, indeed, the identity matrix ie. it has 1s along the diagonal, zero elsewhere. 9. (a) Explain the role of the DFT in cross correlation. [The cross-correlation of two sequences is given defined as: +inf c[k] = x[n] (c) y[n] = # x[m].y[m+k] m=-inf ] (b) Explain applications of cross correlation in image processing. 10. (a) Explain how the DFT may be used for deconvolution. (b) An amateur photographer chances upon a bank robbery. As the robbers' van speeds past him he takes a photograph of the side of the van. When printed the photograph turns out to be blurred - the photographer forgot to 'pan' with the moving van; thus the photograph has been 'convolved' with a smoothing function. The sign on the van cannot be read. Assuming the the smoothing was along the horizontal (ie. along the rows) suggest a digital image processing method for restoring the image. (The image is scanned at 100 pixels per inch, the smoothing appears to be about 1/10 inch wide, ie. 10 pixels). Suggest a restoration technique. (c) If we didn't already knw it, suggest a way in which we might estimate the blurring function. [Hint: if the van was black, and there was a shiny bright spot somewhere in the field of view of the photograph,... impulse response ...]. 10. (a) Explain how the DFT may be used to perform filtering. (b) Explain how to use a 2-d DFT to perform smoothing with a 4 x 4 averaging window ie. 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 (c) Make a qualitative comparison of the frequency response in (b) with that of a 8 x 8 averaging window, ie. 1/32.... 11. (a) Explain how the DFT may be used to perform filtering. [as 10 with a 1-dimensional slant] (b) Explain how to use a DFT to perform smoothing with a 4 wide averaging window ie. [1/4 1/4 1/4 1/4] (c) Make a qualitative comparison of the frequency response in (b) with that of a 8 wide averaging window, ie. [1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8] (d) Make a qualitative comparison of the frequency response in (b) with that of a 2 wide averaging window, ie. [1/2 1/2] (e) Make a qualitative comparison of the frequency response in (b) with that of a 1 wide averaging window, ie. [1] 12. (a) Explain the correspondence between convolution and an FIR (finite impulse response) filter. (b) Explain how a four sample moving average may be implemented as a FIR filter. (c) How may (b) be implemented recursively. 13. (a) Contrast recursive filters with FIR filters; why are recursive filters called Infinite Impulse Response (IIR) filters?; what are the advantages of IIR filters? (b) Explain, using appropriate pictorial or numerical illustrations, a practical example of each of FIR and IIR. Part IV: Chapter 4 Image Enhancement. ------------------------------------ 1. (a) Explain two contrast enhancement techniques. In your answer, be careful to mention the type of image, and applications, to which these techniques are particularly suitable. (b) The histogram of an 8 x 16 3-bit (8-level) image is shown in Figure 1-1 Compute the grey level transformation, T(z), required for histogram equalisation. Apply T(z) to obtain the enhanced output image. COMMENT ON ALL OF YOUR RESULTS. [j.c. comment - this is looking for the extra sparkle that gets the last 3 or 4 marks] z 0 1 2 3 4 5 6 7 ----------------------------------------- p(z) 1 7 21 35 35 21 7 1 Figure 1-1 ---------- [More likely, you would be given an image and so would have to work out the histogram] 2. (a) Explain and contrast 'point' and 'spatial' operations for image enhancement. In your answer, be careful to mention, for each type, one form of image / noise to which it is appropriate. (b) Explain, using appropriate numerical or pictorial examples, the linear contrast transformation given in Equation 2-1. (2-1) z'= (zG-z0).(z-a)/(b-a) + z0 [Ans: = (zG-z0).z/(b-a) + (z0.b-zG.a)/(b-a) scale shift etc.] (c) Explain how eqn. (2-1) may be used to contrast stretch OR contrast compress. 3. (a) Explain how eqn. (3-1) may be used to transform the grey level distribution of an image from having mean m, standard deviation s, to a distribution having mean m', standard deviation s'. Give a qualitative explanation of an application of such a transformation. (3-1) z' = (z-m) . s'/s + m' [ANS: ^ ^ ^ | | | shift scale shift to mean = m' to mean = 0 etc.] (b) Input image: 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 8 8 8 8 8 10 10 10 10 10 What is mean, m? What is standard deviation, s? Transform to mean, m'= 128, std. dev s' = 80. Will it fit into [0,255]? If not, 'clip' to 0 below 0 and to 255 above 255. 4. (a) Explain how certain types of noise may be reduced by averaging multiple images. (b) Local or 'point' enhancement operations have the disadvantage that they operate uniformly over an image, however, the image may not be uniform. Discuss, and explain methods of overcoming this problem. 5. (a) Using appropriate numerical and / or pictorial illustrations, compare and contrast the algorithms for spatial smoothing and edge enhancement. [You should employ appropriate equations and masks given in the appendix] (b) Explain applications of each. 6. (a) Using appropriate numerical and / or pictorial illustrations, compare and contrast the algorithms for spatial smoothing and median filter. [You should employ appropriate equations and masks given in the appendix] (b) Explain applications of each. 7. (a) Using appropriate numerical and / or pictorial illustrations, compare and contrast the algorithms for spatial smoothing and median filter. [You should employ appropriate equations and masks given in the appendix] (b) Explain why any convolution operation is called LINEAR, yet median filtering is called NON-LINEAR. (c) Explain any other non-linear filter (other than median). 8. (a) Explain Sobel edge enhancement. (b) Explain how the results of edge enhancement may be used to complete edge DETECTION. 9. (a) Explain the roles of 'gradient' and 'differentiation' in edge enhancement [Use one- or two-dimensional examples to illustrate your answer]. (b) Apply Sobel edge enhancement to the image given in Figure 9-1 Draw a picture of the result. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 9-1 ---------- 10. (a) Explain the connection between the Prewitt operators and differentiation. (b) Given an input image f[rl..rh][cl..ch], an output image g[rl..rh][cl..ch], write a computer program fragment to apply the Prewitt vertical operator. 11. (a) Explain the connection between the Sobell operators and differentiation. (b) Given an input image f[rl..rh][cl..ch], an output image g[rl..rh][cl..ch], write a computer program fragment to apply the Sobel vertical operator. 12. (a) Explain the connection between cross-correlation and convolution. (b) Given an input image f[rl..rh][cl..ch], a convolution mask h[0..w-1][0..v-1] and an output image g[rl..rh][cl..ch], write a computer program fragment to apply two dimensional convolution. (c) [Assignment question only: give at least TWO sets of sample inputs and outputs]. 13. A 7 x 7 image is shown in Figure 13-1. (a) Show that the Sobel gradient operator, applied to Figure 13-1 will yield Figure 13-2, |G(r,c|; the image boundary pixels are not shown in Figure 13-2 - because you cannot apply the Sobel operator at these points. (b) If you choose a threshold of 100, what are the candidate edge points? (c) It is neccessary to perform edge thinning on the result of (b), ie. to wide strips of edges. Suppose we decide that any point among the candidate edge points is a true edge point if it is a local maximum of |G| in either horizontal, or vertical directions. On this basis, determine edge points. 60 60 62 65 68 70 70 60 60 62 65 68 70 70 70 70 72 75 78 80 80 100 100 102 105 108 110 110 130 130 132 135 138 140 140 140 140 142 145 148 150 150 140 140 142 145 148 150 150 Figure 13-1 ----------- 40.8 44.7 46.6 44 7 40.8 160.2 161.2 161.8 161.2 160.2 240.1 240.8 241.2 240.8 240.1 160.2 161.2 161.8 161.2 160.2 40.8 44.7 46.6 44 7 40.8 Figure 13-2 ----------- Part V: Chapter 6. Image data compression. ------------------------------------------ 1. (a) Define a quantitative measure of information; make sure to give intuitive explanations. (b) Explain, using appropriate numerical examples, why data compression is needed. 2. (a) Explain the role of entropy in data compression. (b) Explain the role of redundancy in data compression. (c) "A sequence is one-dimensional, an image two-dimensional, a 'movie' three-dimensional; as the dimensionality increases, so does the scope for exploiting redundancy for data compression". Discuss. 3. (a) In the context of data compression, explain the components of Figure 3-1. SOURCE----->ENCODER---->CHANNEL---->DECODER--->RECEIVER ^ | | NOISE Figure 3-1 Information Transmission Model ------------------------------------------- (b) Explain how channel capacity is limited. 4. (a) Explain, giving examples of each, LOSSLESS and LOSSY data compression. (b) Explain applications for which each is (i) definitely appropriate, (ii) definitely inappropriate. (c) Explain a 'fidelity criterion' for lossy data compression. 5. (a) Explain the terms, ENTROPY, REDUNDANCY, in the context of image data compression [j.c. comment NB IN THE CONTEXT OF ... examples needed!]. (b) Compute the probability density function of the 10 x 16 image given in Figure 5-1 below. Hence, derive the average entropy per symbol / pixel. Derive a Huffman code for this image and compute the average length of the Huffman codewords (averaged over the image). Assuming that the image is originally coded with 2 bit pixels, and, neglecting the space occupied by the code table, derive the compression performance of the Huffman code. Hence compare this compression performance with that of the theoretically optimum source code. 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 3 3 1 1 1 1 0 0 0 0 0 0 1 1 1 1 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 2 0 0 0 1 1 1 1 0 0 0 2 0 0 Figure 5-1 ---------- (c) Hence, derive a compression code for the image in Figure 5-2. 9 9 9 9 9 0 9 9 0 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 1 1 1 5 5 1 1 1 1 9 9 9 9 9 9 1 1 1 1 5 5 1 1 1 1 9 9 9 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 9 9 9 9 9 9 9 9 0 9 9 9 1 1 1 1 9 9 9 0 9 9 Figure 5-2 ---------- 6. (a) Explain run-length encoding. (b) Apply run-length encoding to Figure 6-1. Assuming 'runs' can be encoded as 4 bits [1..16], and grey level as two bits compute the coding efficiency (see Appendix). 0 0 0 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 3 3 1 1 1 1 0 0 0 0 0 0 1 1 1 1 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 2 0 0 0 1 1 1 1 0 0 0 2 0 0 Figure 5-1 ---------- (c) Obviously, run length encoding will not provide any compresssion for 'busy' images (ie. where the pixel values are rapidly varying, and there is very little correlation between adjacent pixels). Considering the model of a checker-board (alternate black (0), white (1), squares, and a 16 x 16 image, and starting with (1) a pure white image, next, (2) an image with 4 squares (white,black black, white) and so on, At what stage does run-length encoding start to INCREASE rather than compress the data? 7. (a) Explain the principle undelying variable length source coding; give an appropriate example. (b) Explain how variable length codes need to be uniquely decodable; give an appropriate example. 8 (a) Compute the histogram of the 10 x 10 image given below; (b) hence, compute the probability density; (c) hence, derive the average entropy per symbol / pixel; (d) derive a Huffman code for this image; (e) compute the average length of the Huffman code (averaged over all pixels in the image); (f) compare (e) with the theoretical optimum; (g) assuming the image is originally coded with 3 bit pixels, how many bits will the full image occupy? (h) neglecting the space occupied by the code table, how many bits will the Huffman code image occupy? (i) what saving will the Huffman code give? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 2 2 1 2 2 1 1 2 1 2 2 2 1 3 3 1 1 3 3 3 0 0 4 0 0 4 4 0 4 4 4 4 5 4 5 4 4 5 5 5 5 4 4 6 6 7 6 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (j) Use the the previous results to derive a Huffman code for the image below. 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 24 250 250 24 250 250 24 24 250 24 250 250 250 24 121 121 24 24 121 121 121 119 119 93 119 119 93 93 119 93 93 93 93 150 93 150 93 93 150 150 150 150 93 93 61 61 200 61 150 150 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 (k) Compare the coding efficiencies of the original image (assume 8 bits) and coded image. (l) Apply quantisation coding to the image above; compare the coding efficiency of the quantisation coding with that of (1) the raw image, and (2) the Huffman code in (k). 9. (a) The distribution of values in an image are: z 0 1 2 3 p(z) 0.5 0.25 0.125 0.125 (i) Compute average entropy per symbol. (ii) Derive a Huffman variable length code for this set of values. (iii) Compare the average length of the Huffman code with that of (1) the average entropy per symbol, and (2) the average codeword length in the raw image. Comment. (b) Repeat (a) for the following symbols and probabilities; comment on your result. z 1 2 3 4 p(z) 0.5 0.25 0.125 0.125 (c) Repeat (a) for the following symbols and probabilities; comment on your result. z 1 120 122 250 p(z) 0.5 0.25 0.125 0.125 (d) Repeat (a) for the following symbols and probabilities; comment on your result. z