Lab 3: Convolution

Github Classroom assignment

Introduction

Welcome to lab 3! This lab is designed to help you get started with Project 2: Filter.

During this lab, you'll learn about digital image processing, particularly convolution. The lectures covering this topic can be quite dense, but you can rest assured that the programming you'll be doing is nowhere near as complicated.

Objectives

1. Implement basic, per-pixel processing effects,
2. Learn about kernels and convolution, and
3. Begin using convolution to implement more interesting effects.

Conceptual Background

Broadly, digital image processing is the processing of images through algorithms in order to modify, enhance, or extract useful information from them. These cover a wide range of applications, including noise removal, feature extraction, image compression, and image enhancement.

In this lab, we will be doing some simple image manipulation. We'll also get to explore convolution!. Before we get into that, though, here is some optional information which might help contextualize what was taught in lecture:

Getting Started

GUI Elements

If you haven't done so, accept the Github Classroom assignment, clone the generated repository, and run the application in Qt Creator. A window that looks like this should appear:

These buttons are fairly self-explanatory, but we'll go through them anyway:

• The Choose Image button allow you to select any image file from your computer to upload to the canvas. We have provided you with some images in the resources directory.
• The Apply Filter button applies the currently-selected filter to the image. Currently, this does nothing because you have neither implemented, nor selected, any filters.
• The Revert to Original Image button reverts the image to its original state.

Interested in how GUI elements like these are set up? Feel free to take a look at mainwindow.h and mainwindow.cpp in our stencil code!

Command Line Arguments

We will use command line arguments to specify the type of the filter we wish to apply to the image. The available filter types are enumerated below.

Reminder: how to set command line arguments

Stencil Code

Take a look through the provided stencil code. In this lab, you will be working with the following files: canvas2d.h, canvas2d.cpp, the files in the filters directory, and settings.h (read-only).

The Canvas2D class is responsible for storing and manipulating the 2D canvas that will be displayed by the application window. This class has a applyFilter() method which is called whenever the Apply Filter button is clicked.

The filters directory contains several filterXYZ.cpp files, each of which implements a filterXYZ() function. These will be called by applyFilter() to do specific things, such as shifting the image or inverting its colors. The helper functions in filterutils are used to assist in some of these operations.

Notice that the filterXYZ() functions are actually methods of the Canvas2D class; it's perfectly valid, though less common, to implement functions declared in a .h file in one or more differently-named .cpp files.

The settings global object contains information about the specific filter type to be applied to the image. You've already seen a similar object used to specify brush settings in Project 1: Brush.

Let's set up the applyFilter() function so that it applies the appropriate filter when the Apply Filter button is clicked.

Grayscale Filter

The first filter we will implement is the grayscale filter.

This is a "per-pixel" filter—in other words, the final value of each pixel depends only on its original value, and is unaffected by neighboring pixels.

Your filter should produce the following output:

Invert Filter

It only takes a little more effort to implement a filter which inverts an image's colors, producing a 'negative' effect. This method works by inverting each color channel of every pixel, which can be done by subtracting its value from the maximum value (255).

Your filter should produce the following output:

Convolution

Thus far, we've only seen filters that deal with each pixel independently. We will now introduce the concept of convolution, which allows us to apply operations to a pixel while taking into account its neighbors.

Understanding the Process

Generally speaking, convolution is an operation which takes two input signals, and produces an output signal. In digital image processing, we use discrete 2D convolution. This takes in an image and kernel*, and produces an output image.

* A kernel is simply a 2D matrix of values, not unlike an image. And, since convolution is commutative, the distinction between "image" and "kernel" is merely an arbitrary one.

Let's look at an example below.

Worked Example

For simplicity, let us represent our image(s) with only one color channel. In general, convolution is performed per-channel anyway, so this isn't too much of a stretch.

Next, we can proceed to iterate over every pixel in the output image to determine their values. For this example, we will look only at pixel (1, 1), the one with intensity 201 in the original image.

As described earlier, a region around the pixel is multiplied element-wise with the kernel, then summed:

This sum is then stored as the pixel intensity in the output image:

This process of element-wise multiplication and summation must be repeated for every pixel in the output image. As you can probably guess, this makes convolution computationally expensive, due to the large number of multiplications, especially with larger kernels.

Implementing Convolution

Finally, let's get to actually implementing the convolve2D() function in filterutils.cpp!

We will follow the steps outlined above, with the caveat that instead of actually flipping our kernel, we'll cleverly index into it "backwards", in a way that effectively flips it. This will be done as part of task 8.

Preparatory Tasks

First, let's prepare the output image.

Later, in order to perform our element-wise multiplication, we'll need to iterate through the kernel. So, let's also determine the kernel's dimensions.

Beginning The Loop

Now, it's time to implement our element-wise multiplication and sum. This is a pretty big task, so don't be afraid to ask a TA or your peers for help!

Out-Of-Bounds Pixels

As promised earlier, we'll now discuss how to account for the case where the kernel extends beyond the boundary of the image, where pixel data is not defined. How can we obtain pixel "data" for, say, a pixel at (-1, -1)?

There are several ways to deal with this, and in filterutils.cpp, we have provided you some functions for this purpose:

1. getPixelRepeated()

// Repeats the pixel on the edge of the image such that A,B,C,D looks like ...A,A,A,B,C,D,D,D...
RGBA getPixelRepeated(std::vector<RGBA> &data, int width, int height, int x, int y) {
    int newX = (x < 0) ? 0 : std::min(x, width  - 1);
    int newY = (y < 0) ? 0 : std::min(y, height - 1);
    return data[width * newY + newX];
}

2. getPixelReflected()

// Flips the edge of the image such that A,B,C,D looks like ...C,B,A,B,C,D,C,B...
RGBA getPixelReflected(std::vector<RGBA> &data, int width, int height, int x, int y) {
    // Task 9: implement this function

    return RGBA{0, 0, 0, 255};
}

3. getPixelWrapped()

// Wraps the image such that A,B,C,D looks like ...C,D,A,B,C,D,A,B...
RGBA getPixelWrapped(std::vector<RGBA> &data, int width, int height, int x, int y) {
    int newX = (x < 0) ? x + width  : x % width;
    int newY = (y < 0) ? y + height : y % height;
    return data[width * newY + newX];
}

We have implemented functions (1) getPixelRepeated() and (3) getPixelWrapped() for you, and you are welcome to use either one of them in convolve2D().

Using Your Accumulated Values

Having accumulated your red, green, and blue values, you now need to update result with the new RGBA value.

Wrapping Up

Your result vector should now contain the output image's RGBA values. To display this image, we must overwrite the image data currently stored in data:

Good work! You're done with the hardest part of this lab, and, in following sections, we'll use the convolve2D function you just implemented to perform some basic filtering. We will do so by defining different kernels for each filter, then convolving our input image with those kernels.

Identity Filter

An identity filter convolves the input image with an identity kernel, returning the original image.

Your filter should produce the following output:

Shift Filter

A shift filter shifts the image by some number of pixels.

Your filter should produce the following output:

End

Congrats on finishing the Convolution lab! Now, it's time to submit your code and get checked off by a TA. Be prepared to show the TA your working grayscale, invert, identity, shiftLeft, and shiftRight filters.

Submission

Submit your Github repo for this lab to the "Lab 3: Convolution" assignment on Gradescope, then get checked off by a TA during lab hours.

Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS 1230 document by filling out our anonymous feedback form.