Given an image of 1 w pixels a K-ary segmentation is a clustering that assigns each pixel to one of K-classes, typically under the assumption that neighbouring pixels are more likely to belong to the same class. The most common graphical model approach for image segmentation represents the image as a pairwise Markov random field (Figure 4) where each node corresponds to a pixel. Note that the value of a node is the cluster it belongs to. = {Y} and X = {Xi}, Xi {1... K} is the Formally, the observed image is denoted Y segmentation. The Markov random field has distribution ][ II (x, y) II (xi, xz) 1 P(X,Y) = Z i (i,j)E where is the node potential, the effect that pixel y; has on the label of x; \ is the edge potential, how the label of x; is influenced by the labels of its neighbours. Let (xi, Yi) = exp {- (Yi xi) 202xi V (xi, xj) = exp { (x x ;) } Segmentation: = Consider the image in Figure 5. We want to produce a binary segmentation (K = 2). You are given the following parameters: = 20, = 147, = 1/2, = 150, = 1/2 i.e., pixels from segment 1 are normally distributed with mean and variance ; pixels from segment 2 are normally distributed with mean and variance . The image is located in img.mat (MATLAB format). 1. Produce a binary segmentation using loopy belief propagation. 2. Produce a binary segmentation using Gibbs sampling. Produce plots of your segmentations, which must be included in your writeup. For loopy belief propagation initialize m(xi) = 1 for all i j. Stop running loopy belief propagation once the maximum absolute difference between an old message and a new message is less than 105. For Gibbs sampling, just flip a fair coin to select the initial value of each xi. Remarks: You're free to implement this question in any programming language you like. Remember to compute the messages in log-space, for numerical stability. In Gibbs sampling, the transition corresponds to changing the value of one X, which for K = 2 involves sampling a binomial. In Gibbs sampling, pick a few nodes which are far apart in the graph, and check that each marginal converges. You do not need to implement any automated test for convergence of the Markov chain. Y2 Y X3 X2 Y5 6 X5 Y9 x. Y7 8 Figure 4: An example of a Markov Random Field for image segmentation 5 10 15 40 35 30 ANN 25 20 45 60 50 10 20 30 50 40 50 Figure 5: Image for segmentation question 60 60