MATH3609 Optimization, Networks and Graphs
Optimization, Networks and Graphs
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH3609 Optimization, Networks and Graphs:
Coursework 1 and Coursework 2
1 General Information about Coursework 1 and
Coursework 2
Please read the following points before attempting the courseworks:
• The deadline for both Coursework 1 and Coursework 2 is 10 am on Thursday, 22nd
April, 2022. You should submit Coursework 1 and Coursework 2 separately through
the MATH3609 Optimization, Networks and Graphs DLE site. Your submission will be
marked anonymously.
• Coursework 1 and Coursework 2 are Group Courseworks. Please work in
a self-assigned group of up to four people. You will need to register your
group on the DLE in the usual way.
Within each coursework, each member of the group will receive the same mark, unless
any member chooses to make use of the Peer Assessment option. You should keep notes
of all your group meetings to use as evidence in case you choose to make use of the Peer
Assessment option. If you wish to make use of the Peer Assessment option, you will need
to make an appointment to see Dr Nathan Broomhead or Dr Julian Stander.
• You should give due consideration to your personal time management to ensure that
your work is submitted in plenty of time prior to the deadline. For further information,
please consult the Student Handbook
• Each member of the group can expect to spend up to around 15 hours on Coursework 1
and up to around 15 hours on Coursework 2. These suggested times do not include the
preparation work that you will need to do.
• Each coursework counts for 15% = 12 × 30% of your final mark on this module. Marks
will be assigned according to the marking grids on pages 26 and 30.
1
• Marked scripts will be returned within 20 working days of the submission date, and,
in particular, you will get full feedback on your work by Friday, 21st May, 2021, unless
extensions are used.
• You are reminded of the University’s Academic Regulations:
Academic offences occur when activity is undertaken which could confer an unfair
advantage to any candidate(s) in assessment. The University recognises the following
(including any attempt to carry out the actions described) as academic offences, regardless
of intent:
a. Plagiarism, which is copying or paraphrasing of other people’s work or ideas into a
submitted assessment without full acknowledgement. More information on plagiarism
is available here:
b. Collusion, which is unauthorised collaboration of students (or others) in producing a
submitted assessment. The offence of collusion occurs if a student copies any part of
another student’s work, or allows their own work to be copied. Collusion also occurs
if other people contribute significantly to work that a student submits as their own.
The complete list of regulations can be found here:
All group members automatically confirm that they have understood the University’s
policy on plagiarism and collusion when they submit each coursework.
We now state the relevant MATH3609 Optimization, Networks and Graphs Assessed Learning
Outcomes (ALOs) for this assignment.
At the end of the module the learner will be expected to be able to:
ALO1 Develop and analyse methods for the solution of optimisation problems;
ALO3 Demonstrate an understanding of the underlying concepts of graph theory;
ALO4 Use computer software for the solution of optimisation problems and report the
results.
You should keep these ALOs in mind when working on these courseworks.
2
2 Image Restoration: Preparation Work
You should study this section carefully. There has also been a lecture on it.
2.1 The Basic Idea
Let us begin by reading in an image and displaying it.
# Set the working directory
# This is where the image R_image_binary.csv is stored
#
# Please note that your working directory will be different
# from ours (only one of which is needed)
#
## setwd("/Users/julianstander/Dropbox/MATH3609_CW_2020_2021")
#
setwd("/Users/nbroomhead/Dropbox/MATH3609_CW_2020_2021")
#
R_logo <- as.matrix(read.table("R_image_binary.csv",
sep = ",")) # The image is thought of as a matrix
#
image(R_logo,
col = c("black", "white"))
0.0 0.2 0.4 0.6 0.8 1.0
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
Please note that this image is a binary image. It comprises two ‘colours’, black and white. In
Coursework 1 and Coursework 2 we work exclusively with binary images for simplicity.
We will discuss the axes labels later.
3
Unfortunately, often images are received in a degraded or noisy form such as
0.0 0.2 0.4 0.6 0.8 1.0
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
This could be because they are observed and then transmitted by a satellite and so are
subject to atmospheric distortions. Similarly, medical images are often distorted in some way;
just think of an ultrasound image of a baby or even an x-ray or magnetic resonance image
when there has been some patient movement.
4
The aim of image restoration is to try to restore the first image
0.0 0.2 0.4 0.6 0.8 1.0
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
from the degraded image
0.0 0.2 0.4 0.6 0.8 1.0
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
5
2.2 Some Mathematical Notation
Images are represented as matrices. Here is a small example to fix ideas:
x <- matrix(c(0, 0, 0,
0, 0, 1,
1, 1, 1,
0, 0, 1),
nrow = 4,
byrow = TRUE)
#
x
## [,1] [,2] [,3]
## [1,] 0 0 0
## [2,] 0 0 1
## [3,] 1 1 1
## [4,] 0 0 1
#
# Dimension
#
dim(x)
## [1] 4 3
nrow(x)
## [1] 4
ncol(x)
## [1] 3
#
# Specific
#
x[1, 2]
## [1] 0
x[3, 1]
## [1] 1
So the image that is stored in the R object x comprises 4 rows and 3 columns. The value
taken by the image in row 1, column 2 is 0 corresponding to black, while the value taken
by the image in row 3, column 1 is 1 corresponding to white. We say that the above image
comprises 4× 3 = 12 pixels. We shall use i to index the pixels: here i = 1, . . . , n = 12, where n
is the total number of pixels. The value taken at pixel i is denoted xi, where xi can take
the values 0 for black or 1 for white: xi ∈ {0,1}. This enables us to write the whole image as
the vector x = (x1, . . . , xn).
6
We label the pixels column by column:
Columns
R
ow
s
i = 1 or ( 1 , 1 )
i = 2 or ( 2 , 1 )
i = 3 or ( 3 , 1 )
i = 4 or ( 4 , 1 )
i = 5 or ( 1 , 2 )
i = 6 or ( 2 , 2 )
i = 7 or ( 3 , 2 )
i = 8 or ( 4 , 2 )
i = 9 or ( 1 , 3 )
i = 10 or ( 2 , 3 )
i = 11 or ( 3 , 3 )
i = 12 or ( 4 , 3 )
1 2 3
1
2
3
4
So that
x
## [,1] [,2] [,3]
## [1,] 0 0 0
## [2,] 0 0 1
## [3,] 1 1 1
## [4,] 0 0 1
is the vector
as.vector(x)
## [1] 0 0 1 0 0 0 1 0 0 1 1 1
or x = (x1, x2, . . . , x12) = (0,0,1,0,0,0,1,0,0,1,1,1).
7
Please note that in
Columns
R
ow
s
i = 1 or ( 1 , 1 )
i = 2 or ( 2 , 1 )
i = 3 or ( 3 , 1 )
i = 4 or ( 4 , 1 )
i = 5 or ( 1 , 2 )
i = 6 or ( 2 , 2 )
i = 7 or ( 3 , 2 )
i = 8 or ( 4 , 2 )
i = 9 or ( 1 , 3 )
i = 10 or ( 2 , 3 )
i = 11 or ( 3 , 3 )
i = 12 or ( 4 , 3 )
1 2 3
1
2
3
4
we also show the row and column numbers in brackets. We will not usually use these, but
they are added here for information. A point to notice is that the column labels increase
from left to right, while the row labels increase from top to bottom which is different from
standard Cartesian co-ordinates.
8
Let’s consider how R draws an image using its image function
x
## [,1] [,2] [,3]
## [1,] 0 0 0
## [2,] 0 0 1
## [3,] 1 1 1
## [4,] 0 0 1
#
image(x,
col = c("black", "white"))
0.0 0.2 0.4 0.6 0.8 1.0
−
0.
2
0.
2
0.
6
1.
0
#
# Or with better labels
#
n_row <- nrow(x) # Number of rows in x
n_row
## [1] 4
#
n_col <- ncol(x) # Number of columns in x
n_col
## [1] 3
#
image(1:n_row, # Label the rows
1:n_col, # Label the columns
x,
col = c("black", "white"),
xlab = "Row number",
9
ylab = "Column number",
axes = FALSE)
#
axis(1, 1:n_row)
axis(2, 1:n_col)
Row number
Co
lu
m
n
nu
m
be
r
1 2 3 4
1
2
3
So R thinks of the horizontal axis as representing row number, and the vertical axis as
representing column number, just like standard Cartesian co-ordinates: (row i, column j) =(horizontal co-ordinate x,vertical co-ordinate y). This means that the first column of the
matrix x is plotted horizontally at the bottom, the middle column of x is plotted horizontally
in the middle, and the final column of x is plotted horizontally at the top.
These plotting details are not important for what will come. However, we give them here for
information.
10
2.3 A Little More Mathematical Notation
We have seen that in practice we observe a degraded version of a ‘true’ image such as:
0.0 0.2 0.4 0.6 0.8 1.0
0.
0
0.
2
0.
4
0.
6
0.
8
1.
0
We refer to this observed or degraded image using the vector y = (y1, . . . , yn), where n is the
number of pixels. Here yi ∈ {0,1}, i = 1, . . . , n.
11
2.4 Some Literature and Other Irrelevant Information
In scientific writing, we should always give credit where credit is due. Many people have
contributed to statistical image restoration. The following are but two references among a
great many:
Besag, J. E. (1986) On the statistical analysis of dirty pictures (with discussion). Journal of
the Royal Statistical Society B, 48, 259–302.
Geman, D. and Geman, S. (1984) Stochastic relaxation, Gibbs distributions and the Bayesian
restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6,
721–41.
Coursework 1 and Coursework 2 are based on the work of
Greig, D. M., Porteous, B. T. and Seheult, A. H. (1989) Maximum a posteriori estimation
for binary images. Journal of the Royal Statistical Society B, 51, 271–279.
Greig, Porteous and Seheult (1989) assume black is coded as 1 and white as 0. In Coursework
1 and Coursework 2, we use take 1 to represent white and 0 to represent black, as this is
more natural and usual.
The work of Greig, Porteous and Seheult (1989) was expanded on in these works:
Jubb, M. D. (1989) Image Reconstruction. PhD thesis. University of Bath.
Stander, J. (1992) Some Topics in Statistical Image Analysis. PhD thesis. University of Bath.
Stander, J. and Silverman, B. W. (1994) Temperature schedules for simulated annealing.
Statistics and Computing, 4, 21–32.
Franconi, L. and Jennison, C. (1997) Comparison of a genetric algorithm and simulated
annealing in an application to statistical image reconstruction. Statistics and Computing, 7,
193–207.
No knowledge of any of this literature is assumed in either Coursework 1 or
Coursework 2.
We end this section by remarking that images are not usually binary. Often each pixel can
take a grey level so that xi ∈ {0,1, . . . ,255} where 0 is black and 255 is white for example,
or a colour, which is more complicated to represent. We work with binary images to keep
life relatively simple, as this may be the first time that you have met image reconstruction
problems.
12
2.5 Statistical Models
Image restoration proceeds by specifying statistical models for possible true images x =(x1, . . . , xn) and for degraded images y = (y1, . . . , yn).
Please note that this is not a statistics module, so not all the details that we present here are
needed for you to be able to do Coursework 1 or Coursework 2. We include these details
to explain how the image restoration problem can be expressed as an optimization
problem. It is with that optimization problem that we shall work.
2.6 A Statistical Model for y given x
We will assume the following statistical model for yi given xi:
Pr(yi = 0 ∣xi = 0) = 1 − p (no error made, no swap)
Pr(yi = 1 ∣xi = 0) = p (error made, swap from 0 to 1)
Pr(yi = 0 ∣xi = 1) = p (error made, swap from 1 to 0)
Pr(yi = 1 ∣xi = 1) = 1 − p (no error made, no swap)
Essentially, we are assuming that the colour at pixel i is swapped from black to white, or
from white to black, with probability p ∈ [0,1]; otherwise, it is not changed. For simplicity,
we assume that p is known.
We assume that the error mechanism at each pixel is independent of the error mechanisms at
every other pixel. This enables us to write down Pr(y ∣x):
Pr(y ∣x) = n∏
i=1 Pr(yi ∣xi).
Let’s recall that the degraded image y is observed, while the ‘true’ image x is unknown and
needs to be estimated. Thought of as a function of the unknown image vector x, Pr(y ∣x)
is the likelihood function that you may have met in MATH2602 Statistical Inference and
Regression or MATH3613 Data Modelling. We shall write L(y ∣x) = Pr(y ∣x).