Lab 6: Convolution & Mipmapping

Github Classroom assignment

Introduction

Welcome to Lab 6! This lab is designed to help you get started with Project 4: Antialias.

During this lab, you'll learn about digital image processing (particularly convolution) and mipmapping. 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. Learn about kernels and convolution,
2. Begin using convolution to implement more interesting effects, and
3. Implement downsampling to generate mipmaps.

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'll get to explore convolution and mipmapping! 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 allows 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 Generate Mipmap button displays the mipmap chain of your image. Currently, this does nothing because you have not implemented mipmapping yet. (TODO: verify this from student end view)
• The Save Mipmap Levels button saves the mipmap chain to a folder under the mipmaps_generated/student_generations directory. This will help with visualizing and debugging, especially for Project 4: Antialias.
• 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, mipmap.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 mipmap.cpp file is where you will implement the downsampling of the selected image using a separable box filter.
• 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. 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.

Convolution

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 , the one with intensity 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 4.

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 ?

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. 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];
}

3. 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 5: implement this function

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

We have implemented functions (1) getPixelRepeated() and (2) 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 (corrected) 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:

Mipmapping

Now, let's move onto some practices with mipmapping to prepare you for Project 4: Antialias. As we have seen in class, bilinear filtering helps with antialiasing, but a fixed filter window is not always enough. When a texture is viewed at a steep angle or from a distance, a pixel may cover many texels. In this case, we should be averaging over a larger area of the texture to minimize aliasing.

Ideally, we would filter the texture with a filter whose size is proportional to the pixel's footprint on the texture. However, doing so would be prohibitively expensive at render time. Instead, we can precompute a series of downsampled versions of the texture, called mipmaps (short for "multum in parvo," Latin for "many things in a small place"). Each level of the mipmap is downsampled by a factor of in each dimension. Then, at render time, we can choose the appropriate mipmap level(s) to sample from based on a pixel's footprint on the texture.

Downsampling

Generating mipmaps requires the ability to properly downsample an image. Thus, you'll need to implement a function that can take an image and scale it down by a factor, being sure to use a pre-filter to avoid introducing aliases. You will practice doing so with a box filter for this lab, and you should implement it as a separable filter for efficiency. Everything you need to know for this implementation has already been covered in great depth during the Sampling, Reconstruction, & Antialiasing lectures.

Mipmap Generation

Now that you have implemented downsampling, you can generate mipmaps of every level for every texture in your scene!

End

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

Submission

Submit your GitHub link and commit ID to the "Lab 6: Convolution & Mipmapping" assignment on Gradescope, then get checked off by a TA at hours.

Reference the GitHub + Gradescope Guide here.

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.