Submission by: Jazzy Doe (jazz@mit.edu)

Homework 1 - convolutions

18.S191, Spring 2021

This notebook contains built-in, live answer checks! In some exercises you will see a coloured box, which runs a test case on your code, and provides feedback based on the result. Simply edit the code, run it, and the check runs again.

For MIT students: there will also be some additional (secret) test cases that will be run as part of the grading process, and we will look at your notebook and write comments.

Feel free to ask questions!

Let's create a package environment:

Exercise 1 - Manipulating vectors (1D images)

A Vector is a 1D array. We can think of that as a 1D image.

Exerise 1.1

👉 Make a random vector random_vect of length 10 using the rand function.

👉 Make a function mean using a for loop, which computes the mean/average of a vector of numbers.

👉 Define m to be the mean of random_vect.

👉 Write a function demean, which takes a vector x and subtracts the mean from each value in x.

Let's check that the mean of the demean(random_vect) is 0:

Due to floating-point round-off error it may not be exactly 0.

Exercise 1.2

👉 Generate a vector of 100 elements. Where:

• the center 20 elements are set to 1, and

• all other elements are 0.

Exercise 1.3

👉 Write a function that turns a Vector of Vectors into a Matrix.

👉 Write a function that turns a Matrix into aVector of Vectors .

Exercise 2 - Manipulating images

In this exercise we will get familiar with matrices (2D arrays) in Julia, by manipulating images. Recall that in Julia images are matrices of RGB color objects.

Let's load a picture of Philip again.

Hi there Philip

Exercise 2.1

👉 Write a function mean_color that accepts an object called image. It should calculate the mean (average) amounts of red, green and blue in the image and return a tuple (r, g, b) of those means.

Exercise 2.2

👉 Look up the documentation on the floor function. Use it to write a function quantize(x::Number) that takes in a value $x$ (which you can assume is between 0 and 1) and "quantizes" it into bins of width 0.1. For example, check that 0.267 gets mapped to 0.2.

Exercise 2.3

👉 Write the second method of the function quantize, i.e. a new version of the function with the same name. This method will accept a color object called color, of the type AbstractRGB.

Here, ::AbstractRGB is a type annotation. This ensures that this version of the function will be chosen when passing in an object whose type is a subtype of the AbstractRGB abstract type. For example, both the RGB and RGBX types satisfy this.

The method you write should return a new RGB object, in which each component ($r$, $g$ and $b$) are quantized.

Exercise 2.4

👉 Write a method quantize(image::AbstractMatrix) that quantizes an image by quantizing each pixel in the image. (You may assume that the matrix is a matrix of color objects.)

Let's apply your method!

Exercise 2.5

👉 Write a function invert that inverts a color, i.e. sends $(r,g,b)$ to $(1-r,1-g,1-b)$.

Let's invert some colors:

Can you invert the picture of Philip?

Exercise 2.6

👉 Write a function noisify(x::Number, s) to add randomness of intensity $s$ to a value $x$, i.e. to add a random value between $-s$ and $+s$ to $x$. If the result falls outside the range $(0,1)$ you should "clamp" it to that range. (Note that Julia has a clamp function, but you should write your own function myclamp(x).)

👉 Write the second method noisify(c::AbstractRGB, s) to add random noise of intensity $s$ to each of the $(r,g,b)$ values in a colour.

👉 Write the third method noisify(image::AbstractMatrix, s) to noisify each pixel of an image.

👉 For which noise intensity does it become unrecognisable?

You may need noise intensities larger than 1. Why?

Exercise 3 - Convolutions

As we have seen in the videos, we can produce cool effects using the mathematical technique of convolutions. We input one image $M$ and get a new image $M^{\prime }$ back.

Conceptually we think of $M$ as a matrix. In practice, in Julia it will be a Matrix of color objects, and we may need to take that into account. Ideally, however, we should write a generic function that will work for any type of data contained in the matrix.

A convolution works on a small window of an image, i.e. a region centered around a given point $(i,j)$. We will suppose that the window is a square region with odd side length $2\ell +1$, running from $-\ell ,\dots ,0,\dots ,\ell$.

The result of the convolution over a given window, centred at the point $(i,j)$ is a single number; this number is the value that we will use for $M_{i,j}^{\prime }$. (Note that neighbouring windows overlap.)

To get started let's restrict ourselves to convolutions in 1D. So a window is just a 1D region from $-\ell$ to $\ell$.

Let's create a vector v of random numbers of length n=100.

Feel free to experiment with different values!

Exercise 3.1

You've seen some colored lines in this notebook to visualize arrays. Can you make another one?

👉 Try plotting our vector v using colored_line(v).

Try changing n and v around. Notice that you can run the cell v = rand(n) again to regenerate new random values.

Exercise 3.2

We need to decide how to handle the boundary conditions, i.e. what happens if we try to access a position in the vector v beyond 1:n. The simplest solution is to assume that $v_i$ is 0 outside the original vector; however, this may lead to strange boundary effects.

A better solution is to use the closest value that is inside the vector. Effectively we are extending the vector and copying the extreme values into the extended positions. (Indeed, this is one way we could implement this; these extra positions are called ghost cells.)

👉 Write a function extend(v, i) that checks whether the position $i$ is inside 1:n. If so, return the $i$th component of v; otherwise, return the nearest end value.

Some test cases:

Extended with 0:

Extended with your extend:

Exercise 3.3

👉 Write a function blur_1D(v, l) that blurs a vector v with a window of length l by averaging the elements within a window from $-\ell$ to $\ell$. This is called a box blur.

Exercise 3.4

👉 Apply the box blur to your vector v. Show the original and the new vector by creating two cells that call colored_line. Make the parameter $\ell$ interactive, and call it l_box instead of just l to avoid a variable naming conflict.

Exercise 3.5

The box blur is a simple example of a convolution, i.e. a linear function of a window around each point, given by

$$v_i^{\prime }=\sum _n{v}_{i-n}{k}_n,$$

where $k$ is a vector called a kernel.

Again, we need to take care about what happens if $v_{i-n}$ falls off the end of the vector.

👉 Write a function convolve_vector(v, k) that performs this convolution. You need to think of the vector $k$ as being centred on the position $i$. So $n$ in the above formula runs between $-\ell$ and $\ell$, where $2\ell +1$ is the length of the vector $k$. You will need to do the necessary manipulation of indices.

Edit the cell above, or create a new cell with your own test cases!

Exercise 3.6

👉 Write a function gaussian_kernel.

The definition of a Gaussian in 1D is

$$G(x)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(\frac{-x^2}{2{\sigma }^2}\right)$$

We need to sample (i.e. evaluate) this at each pixel in a region of size $n^2$, and then normalize so that the sum of the resulting kernel is 1.

For simplicity you can take $\sigma =1$.

Let's test your kernel function!

Exercise 4 - Convolutions of images

Now let's move to 2D images. The convolution is then given by a kernel matrix $K$:

$$M_{i,j}^{\prime }=\sum _{k,l}{M}_{i-k,j-l}{K}_{k,l},$$

where the sum is over the possible values of $k$ and $l$ in the window. Again we think of the window as being centered at $(i,j)$.

A common notation for this operation is $\ast$:

$$M^{\prime }=M\ast K.$$

Exercise 4.1

👉 Write a function extend that takes a matrix M and indices i and j, and returns the closest element of the matrix.

Let's test it!

Extended with 0:

Extended with your extend:

Exercise 4.2

👉 Implement a function convolve_image(M, K).

Let's test it out! 🎃

Edit K_test to create your own test case!

You can create all sorts of effects by choosing the kernel in a smart way. Today, we will implement two special kernels, to produce a Gaussian blur and a Sobel edge detect filter.

Make sure that you have watched the lecture about convolutions!

Exercise 4.3

👉 Apply a Gaussian blur to an image.

Here, the 2D Gaussian kernel will be defined as

$$G(x,y)=\frac{1}{2\pi {\sigma }^2}{e}^{\frac{-(x^2+y^2)}{2{\sigma }^2}}$$

Let's make it interactive. 💫

Exercise 4.4

👉 Create a Sobel edge detection filter.

Here, we will need to create two separate filters that separately detect edges in the horizontal and vertical directions:

$$\begin{array}{rl}{G}_x& =(\left[\begin{array}{c}1\\ 2\\ 1\end{array}\right]\otimes [10-1])\ast A=\left[\begin{array}{ccc}1& 0& -1\\ 2& 0& -2\\ 1& 0& -1\end{array}\right]\ast A\\ G_y& =(\left[\begin{array}{c}1\\ 0\\ -1\end{array}\right]\otimes [121])\ast A=\left[\begin{array}{ccc}1& 2& 1\\ 0& 0& 0\\ -1& -2& -1\end{array}\right]\ast A\end{array}$$

Here $A$ is the array corresponding to your image. We can think of these as derivatives in the $x$ and $y$ directions.

Then we combine them by finding the magnitude of the gradient (in the sense of multivariate calculus) by defining

$$G_{\text{total}}=\sqrt{G_x^2+G_y^2}.$$

For simplicity you can choose one of the "channels" (colours) in the image to apply this to.

Exercise 5 - Lecture transcript

(MIT students only)

Please see the Canvas post for transcript document for week 1 here.

We need each of you to correct about 100 lines (see instructions in the beginning of the document.)

👉 Please mention the name of the video and the line ranges you edited:

Function library

Just some helper functions used in the notebook.

homework 1, version 5