Project 2: Filter (Algo Answers)
You can find the handout for this project here. Please read the handout before working on this algo assignment!
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.
The value of the output image at index
Applying this formula for each index results in the image above.
Convolve the below function and filter. What is the value of
Draw the shape of the output function obtained in the previous question (figure 2).
Imagine the filter, flipped (such that
While doing this, we can identify 4 important points we need to accurately graph the output function:
- The first point where the boxes start to overlap (
- The first point where the boxes fully overlap (
- The point where the boxes stop fully overlapping (
- The point where the boxes stop overlapping at all. (
As the maximum overlapping area of both inputs is
Let's try to generalize our solution to the earlier discrete convolution problem.
Consider a 1D kernel
, , 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
You may ignore edge effects for the purposes of this question (i.e. feel free to "incorrectly" index out-of-bounds).
Both answers below are equivalent:
Remember that we must define a summation over the element-wise multiplication of function
We must also ensure that
With these two constraints in hand, we are ready to define a summation either from
What is the filter support width when you scale by a factor of
For this explanation, please assume a 1D image.
A triangle filter of width
There are cases where, for an output pixel, we sample only "one" pixel in the original image:
- An output pixel at the edge of the image samples only the input pixel at the exact same position, and its neighbor pixel (but with weight 0, since it's at the tip of the triangle);
- In fact, any output pixel which has the exact same position as an input pixel will sample only that input pixel, plus its neighbors (again, with weight 0).
- This makes sense, since we already know what color that pixel should be: the same color as the input pixel at the same position.
What is the filter support width when you scale by a factor of
The reason we use a filter while scaling is to avoid aliasing. Ideally, we'd like to use an ideal low-pass filter: this would be a box in the frequency domain, and a sinc in the spatial domain. Of course, we cannot use a sinc, so we approximate this sinc with a triangle (for scaling, in CS 1230).
This approximation is what gives rise to the answer
Extra: but why is it
It's not necessary for you to understand the math behind this derivation, but given that we have an input image with some max frequency
This corresponds to a filter which looks like a box function with width
We approximate this sinc with a triangle with width
Recall that back-mapping refers to finding the correct filter placement given a pixel in the output image.
The naïve back-map function is
Suppose we wanted to scale down a 9-pixel 1D image by a factor of
Draw a picture to show where we would sample the original image using the naïve back-map function. Please include an illustration of the filter above each sample point.
Since we are scaling the image by a factor of
If you got both this question and the next question correct, you got an extra point on the algo assignment!
Draw another picture to show where we would sample the original image using the naïve back-map function. Again, please include an illustration of the filter above each sample point.
Again, the support width of our filter should be 6 because we are scaling the image by a factor of
If you got both this question and the previous question correct, you got an extra point on the algo assignment!
Duality of Domains
Visualizing Sinc and Box Duals
Take a look at the box function in figure 4 (left) below. Its dual in the frequency domain is the sinc function, in figure 4 (right). Note that there are no labels on the axes, by design.
Please sketch the dual of the box function in figure 5. Your drawing doesn't need to be perfectly accurate; we just need to see that you get the idea.
A wider box function in the frequency domain means that there are more signals with higher frequency. To reflect this fact in the spatial domain, the sinc function needs to have higher frequency, or, oscillate more. Visually, the sinc function becomes narrower.
What do we usually use to approximate the sinc function, and why do we have to make this approximation when translating these theoretical concepts into code?
A Gaussian function. Though, in cases where the approximation doesn't have to be as good, a triangle function can be used instead.
Both the Gaussian and triangle filters are cheaper to use.
Sinc functions are infinite in extent, and it's simply not feasible to perform discrete convolution with an infinitely large, nor would it be performant to approximate it with a "very large" one.
Gaussians are technically also infinite in extent, but fall to almost-zero fairly quickly. Thus, Gaussians can be used as a cheaper approximations to the sinc filter. Compared to the triangle, it also has a nice property: a Gaussian's dual in the frequency domain is another Gaussian, which means it better approximates a good low-pass filter.
Sampling in the Frequency Domain
If we're sampling a continuous function at a frequency of
Any frequency less than, but not equal to
In order to capture all frequencies in a signal, we must sample at a rate that is strictly higher than 2 times the highest frequency. Thus, if are sampling
Now, examine the following frequency plot of a 1D, continuous signal. If you were going to sample this signal at a rate of 8 samples per unit, to avoid aliasing, you would use what we know about the Nyquist limit to pre-filter it. Sketch the new frequency plot after someone has performed this pre-filtering step optimally.
To avoid aliasing, we need to prefilter the signal by running a low-pass (blur) filter to eliminate high frequencies. In the frequency domain, if we want to eliminte frequencies higher than
In our case, since we are sampling the signal at 8 samples per unit, we can only represent functions with frequency lower than 4. Thus, the box function centered around 0 should have width
Submit your answers to these questions to the "Project 2: Filter (Algo)" assignment on Gradescope.