Project 2: Filter (Algo)

You can find the handout for this project here. Please skim the handout before your Algo Section!

You may look through the questions below before your section, but we will work through each question together, so make sure to attend section and participate to get full credit!

Convolution

Discrete Convolution

You are given the following 1D kernel and input image. Assume that any pixel outside the bounds of the input image has value 0 (i.e. the image is zero-padded).

What is the output image when the kernel and image are convolved with each other? Present your answer as a vector of size 6, representing the output image.

As a group, discuss what visual effect this kernel might have on a real image.

**Figure 1:** 1D arrays representing the input image, kernel, and output image (unfilled).

Convolution over a 2D Image

Suppose that you are given a 1D image vector , representing a 2D image of height and width . You are also given a 1D kernel vector , with radius . You may ignore edges for now.

Write out pseudocode to slide the kernel over the 2D image. At each kernel position, calculate the index of each pixel in the 1D image vector () that the kernel () overlaps with.

Kernel positioned horizontally over a 2D image. — **Figure 2:** An example of a kernel positioned horizontally over a 2D image.

How would you need to adjust this pseudocode if the kernel were positioned vertically instead?

Continuous Convolution

Convolve the below function and filter. What is the value of at in the output?

TODO — **Figure 3:** Image as a continuous signal with filter function for Q1.2

Visualizing Convolution

Work with your group on a whiteboard to draw the shape of the output function obtained in the previous question (figure 3).

Blurring

Let's try to generalize our solution to the earlier discrete convolution problem.

Consider a 1D kernel of radius that represents a blurring filter. We apply this blur (via convolution) to an input image resulting in a new image .

All of , , and can be considered as 1D arrays storing intensities where gives the intensity of the -th pixel. Remember that the kernel is zero-indexed so gives the left-most value in the kernel array.

We are interested in writing out this convolution as summation over the values of and . For some index within the bounds of the image, please write out the summation equation for in terms of , , , and .

You may ignore edge effects for the purposes of this question (i.e. feel free to "incorrectly" index out-of-bounds).

Begin thinking through this question on your own, and then work with the group to come to an answer. Note that there may be multiple correct answers here!

Scaling

Scaling Up

What is the filter support width when you scale by a factor of , where ?

Scaling Down

What is the filter support width when you scale by a factor of , where ?

Naïve Back-mapping

Recall from lecture that back-mapping refers to finding the correct filter placement given a pixel in the output image.

The naïve back-map function is $ï$ , but the correct back-map function is , where is the scaling factor and is the pixel index in the output image.

Suppose we wanted to scale down a 9-pixel 1D image by a factor of ().

With your group, draw out the 9 pixels of the original image, and show where we would sample the original image using the naïve back-map function. Include an illustration of the filter above each sample point.

Correct Back-map

Draw another picture to show where we would sample the original image using the correct back-map function. Again, please include an illustration of the filter above each sample point.

Discuss the differences between the two methods, and what might happen if we used the naïve back-map function in practice.

Duality of Domains

Visualizing Sinc and Box Duals

Take a look at the box function in figure 5 (left) below. Its dual in the frequency domain is the sinc function, in figure 5 (right). Note that there are no labels on the axes, by design.

**Figure 5:** A box function with its dual, a sinc function.

A sinc function — **Figure 5:** A box function with its dual, a sinc function.

Draw out a sketch of the dual of the box function in figure 6. Your drawing doesn't need to be perfectly accurate; but enough to show that you understand the concept.

**Figure 6:** Another box function, about twice as wide as before.

When you are finished, explain your group's thought process to the TA.