School of Computer Science The University of Adelaide Advanced Algorithms Assignment 1 Semester 1 2017 Due 11:59pm Tuesday 28 Mar 1 Dirty pictures A digital image consists of a set of pixels fxigN i=1 arranged in a 2D matrix. The image is called binary if each pixel xi can take on only two possible values, xi = 0 (for black) or xi = 1 (for white). The following are examples of binary images. (a) Original. (b) Noisy. Figure 1: Original and corrupted/noisy binary images. Download the images from the following URL and read/display them in Matlab. Verify that they are indeed 2D matrices with values 0 and 1 only. https://myuni.adelaide.edu.au/courses/23889/files/931664/download Due to various reasons (noisy communication channels, compression artefacts, etc.), digital images often become corrupted. In binary images, the pixel values are \flipped" from 0 to 1 and vice versa. Figure 1 shows a binary image and its corrupted version. Semester 1 2017 Page 1 by Tat-Jun Chin1.1 Cleaning dirty pictures An image denoising technique attempts to recover the original image from the corrupted image. Let x = fxigN i=1 be the (unknown) original image and y = fyigN i=1 be the observed corrupted image. By modelling a digital image as a Markov Random Field (MRF) and the corruption as a probabilistic measurement process, an estimate for x given y can be obtained as the maximiser of the log-posterior 1 function L(x j y) = NX i =1 λixi + 1 2 X hi;ji2N β [xixj + (1 − xi)(1 − xj)] ; (1) where N is the set of all neighbouring pixels, i.e., if hi; ji 2 N , then xi and xj are adjacent pixels in the image. We use 8-connectedness in this assignment, where each pixel has 8 neighbours, except for the boundary pixels (in the image below with N = 25 pixels, x7, x8, x9, x12, x14, x17, x18 and x19 are adjacent to x13). x1 x6 x11 x16 x21 x2 x7 x12 x17 x22 x3 x8 x13 x18 x23 x4 x9 x14 x19 x24 x5 x10 x15 x20 x25 The constants λi; i = 1; : : : ; N and β reflect our belief of the \strength" of the corruption. The constant λi is the log-likelihood ratio of the i-th pixel: λi = (ln ln f f f f1 1 0 0j j j j1 0 1 0 if if y yi i = 1 = 0 ; (2) where f1j1 is the probability of observing value 1 if the original value is 1, and f0j1 is the probability of observing value 0 if the original value is 1 (similarly for f1j0 and f0j0). The constant β is the likelihood of two pixels having equal values in the image. Except for tiny images, checking all possible 2N choices for x 2 f0; 1gN to find the maximiser to (1) is infeasible. An ingenious polynomial-time solution is by s-t mincut; first, construct a directed graph G = (V; E) from y as follows: 1Details of MRF are not essential for this assignment. If you are interested in the theory, see [Greig et al., Exact Maximum A Posteriori Estimation for Binary Images, Journal of the Royal Statistical Society, Series B, Vol. 51, No. 2 (1989), 271{279]. Semester 1 2017 Page 2 by Tat-Jun Chin• The vertex set V consists of the observed pixels fyigN i=1 and two additional vertices fyN+1; yN+2g, where yN+1 is the source and yN+2 is the sink. • The edge set E is defined as follows: { For i = 1; : : : ; N, - If λi > 0, there is a directed edge from yN+1 to yi with capacity cN+1;i = λi; - If λi ≤ 0, there is a directed edge from yi to yN+2 with capacity ci;N+2 = −λi. { For each pair of adjacent pixels hi; ji 2 N , there is an undirected edge between yi and yj with capacity β (recall that an undirected edge is implemented as two directed edges of opposite directions with weights ci;j = β and cj;i = β). The following illustrates the graph G constructed in the above manner. sink source For any candidate x of the original image, we can define a partition of the vertices V = fy1; : : : ; yN+2g into two sets, indexed by S := fN + 1g [ fi j xi = 1g and T := fi j xi = 0g [ fN + 2g. The partition (S; T) is an s-t cut of G, since it separates the source and the sink. The capacity of the s-t cut (S; T) corresponding to an x is exactly C(x) = X p2S X q2T c p;q; (3) i.e., the sum of the capacities of the directed edges from S to T that are cut by the partition. Crucially, C(x) can be written as C(x) = NX i =1 xi max(0; −λi) + NX i =1 (1 − xi) max(0; λi) + 1 2 NX i =1 NX j =1 β(xi − xj)2; (4) which equals to −L(x j y) except for a term that does not depend on x. Hence, maximising L(x j y) is equivalent to minimising C(x), i.e., finding the s-t mincut in G! Semester 1 2017 Page 3 by Tat-Jun Chin2 Deliverables Write a Matlab function mrfdenoise.m that takes as input • a matrix that represents a noisy binary image; • the probabilities f1j1 and f0j0; and • the likelihood β (a positive number). The task of mrfdenoise.m is to estimate the denoised binary image based on s-t mincut. Your function must be able to be run as follows (in the following, f1j1 = 0:95, f0j0 = 0:95, and β = 0:9): >> img1 = imread('monalisa_noisy.pbm'); % Read image. >> figure; imshow(img1); % Display the noisy image. >> [img2,I,J,W] = mrfdenoise(img1,0.95,0.95,0.9); % Perform MRF denoising. >> figure; imshow(img2); % Display the cleaned image. As an example, with the above input settings, the noisy image in Figure 1 is denoised to become Figure 2(a). The difference between the noisy and cleaned image is Figure 2(b). (a) Cleaned image. (b) Difference image. Figure 2: Cleaned and difference image. Apart from outputting the denoised image, the function must output the edge set E for the graph G constructed based on the input image; E is represented using vectors I, J and W, each of length jEj, where jEj is the number of edges. For any k where 1 ≤ k ≤ jEj, there is a directed edge from vertex I(k) to vertex J(k) with weight W(k). Semester 1 2017 Page 4 by Tat-Jun Chin2.1 Expected run time For the images given, your program should be able to terminate well within 1 minute. 2.2 Web submission Only the file mrfdenoise.m needs to be submitted. You must submit via the Web Submission System. This means you must create the assignment under your own SVN repository to store the submission file. The SVN path for this submission is 2017/s1/aa/Assignment1 The link to the Web Submission System used for this assignment is https://cs.adelaide.edu.au/services/websubmission/ 2.3 Due date and late submission policy This assignment is due by 11:59pm Tuesday 28 Mar. If your submission is late the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted. 2.4 Grading We will manually run your code on different tests. If it passes all tests you will get 10% of the overall course mark. There will be no marks awarded on the basis of coding style, \amount" of code/comments written, or assertions of \understanding". For self testing prior to submission, the expected target output shown in Figure 2(a) has been given to you for comparisons. 2.5 Using other source code and libraries You may not use other source code for this assignment. All submitted code must be your own work written from scratch. Only by writing the solution yourself will you fully understand the concept. You will also not require external libraries to complete this assignment|all required functions should be available in the university's Matlab versions. ∼∼∼ The End ∼∼∼ Semester 1 2017 Page 5 by Tat-Jun Chin