CS50 PSet 4: Filter
A guide to the ‘Filter’ problem in CS50 Week 4 (more difficult version).
Goal: To write a series of functions in C that apply various image filters to bmp inputs.
The grayscale function should take an image and turn it into a black and white version of the same image.
The reflect function should take an image and reflect it horizontally.
The blur function should take an image and turn it into a box-blurred version of the same image.
The edges function should take an image and highlight the edges between objects, according to the Sobel operator.
There are a few files pre written for us in this assignment, but we will be writing all of our functions within the helpers.c file. This file is simply to separate out the functions that will be called in the main filter.c file, which has already been written for us.
The bmp.h file contains several structs that we will be using, in particular RGBTRIPLE. This data type contains values for red, green and blue so will be useful when dealing with RGB values for each pixel in the images. I recommend making sure you understand this struct before reading on.
Every function we go on to define takes three arguments:
- The image height in terms of number of pixels (int)
- The image width, also in terms of number of pixels (int)
- A 2D array of RGBTRIPLEs, with size equivalent to the height times the width of the image being filtered. This gives one RGBTRIPLE for each pixel in the image.
grayscale
This function must take an image and convert it to black and white. This is done by taking an average of the red, green and blue values of each pixel and setting them all equal to the average, as is explained in the problem description.
To do this we simply loop through each pixel in the image using a nested loop. For each pixel, we define variables for the blue, green and red components of that pixel’s RGBTRIPLE. We then calculate an integer average of these three, using round so we get a whole number. Finally set each of the blue, green and red components of the RGBTRIPLE to the average just calculated. When this has been applied to all pixels in the image, a black and white version will be returned.
// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
// Loop through rows
for (int i = 0; i < height; i++)
{
// Loop through columns
for (int j = 0; j < width; j++)
{
// Get RGBTriple values
float blue = image[i][j].rgbtBlue;
float green = image[i][j].rgbtGreen;
float red = image[i][j].rgbtRed; // Calculate average
int average = round((red + blue + green) / 3); // Set all values to average
image[i][j].rgbtBlue = image[i][j].rgbtGreen = image[i] [j].rgbtRed = average;
}
}
return;
}
reflect
This function must flip an image about the vertical axis, which will return a mirror image. To do this each pixel must be moved to the equivalent position at the other side of the image.
The logic used here is similar to the previous function, as again we loop through the height and width to perform an operation on each pixel. The important distinction here is that we only loop to the halfway point of the width, for reasons which may not be immediately obvious. If we simply looped through the entire width and set the value of the current pixel to the equivalent at the other side, by the time we get halfway across the image, half of the pixels would be lost.
To get around this we loop to the halfway point and set a temporary RGBTRIPLE variable for each pixel. The current pixel can now be set to the reflected pixel on the other side of the image, located at image[i][width- (j + 1)]. The reflected pixel can now be set equal to temp, i.e. the original pixel.
When this is repeated for every pixel a reflected image will be returned.
// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
// Loop through rows
for (int i = 0; i < height; i++)
{
// Loop through columns
for (int j = 0; j < width / 2; j++)
{
// Reflect pixels
RGBTRIPLE temp = image[i][j];
image[i][j] = image[i][width - (j + 1)];
image[i][width - (j + 1)] = temp;
}
} return;
}
blur
Things get a bit trickier with this one. The purpose of this function is to return a blurred version of the input image. This is done by setting each pixel’s RGB values to the average of those that surround it. There are effectively 9 kinds of pixel in the image, each of which have different surrounding pixels:
- The four corner pixels (green), which each have three surrounding pixels
- Pixels located on the four edges (orange), away from corners. These have five surrounding pixels.
- Any other pixel, located away from the edges (blue). These each have nine surrounding pixels.
The first way that springs to mind to do this is to loop through each of the pixels and have 9 separate conditional statements to check which kind of pixel it is and therefore how many surrounding pixels there are, and where to find them.
This is of course extremely long winded and violates one of the golden rules of writing good code: don’t repeat yourself. An alternative way is to implement the same method on every pixel as follows:
- Check if each surrounding pixel exists.
- If it does, add each red, green, blue value to the totals. If it doesn’t, ignore it.
- Set the pixel’s red, green and blue values to the average of however many surrounding pixels there are.
The first step with the code for this one is to duplicate the image into a separate array of RGBTRIPLEs. This is required as we require the original surrounding pixels at all times to calculate the averages, which will be removed from the original image once we start blurring.
// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
// Create temp array
RGBTRIPLE temp[height][width];
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
temp[i][j] = image[i][j];
}
}Next loop through each pixel, as we have done previously. For each pixel, a variable must be declared to store the sums of the red, blue and green values of the surrounding pixels as well as a counter of the amount of surrounding pixels.
// Loop through rows
for (int i = 0; i < height; i++)
{
// Loop through columns
for (int j = 0; j < width; j++)
{
// Initialise values
float sum_red;
float sum_blue;
float sum_green;
int counter; sum_red = sum_blue = sum_green = counter = 0;
To check if the surrounding pixels exist, we must loop one pixel up/down and left/right using k and l. If i + k is outside the range of 0 to the height, then that pixel doesn’t exist in the image and can be skipped. The same logic applies for j + l and the width. Otherwise add the red, blue and green values to the sums and increment the counter.
Finally find the average of each and set the original values for that pixel equal to the average, which will achieve the blur effect required.
// For each pixel, loop vertical and horizontal
for (int k = -1; k < 2; k++)
{
for (int l = -1; l < 2; l++)
{
// Check if pixel is outside rows
if (i + k < 0 || i + k >= height)
{
continue;
}
// Check if pixel is outside columns
if (j + l < 0 || j + l >= width)
{
continue;
}
// Otherwise add to sums
sum_red += temp[i + k][j + l].rgbtRed;
sum_blue += temp[i + k][j + l].rgbtBlue;
sum_green += temp[i + k][j + l].rgbtGreen;
counter++;
}
} // Get average and blur image
image[i][j].rgbtRed = round(sum_red / counter);
image[i][j].rgbtGreen = round(sum_green / counter);
image[i][j].rgbtBlue = round(sum_blue / counter);
}
}
return;
}
edges
Last but definitely not least, this function must detect any edges between objects in the image and highlight these. This is done using the Sobel operator, which computes the new value of each pixel by taking a weighted sum of the values for the surrounding pixels. These sums are calculated for both the x and y directions, with the red, blue and green values multiplied by the operators in the following two ‘kernels’:
Essentially what this means is that for every pixel, we can generate a Gx and Gy value for each of the red, green, and blue channels for that pixel. The square root of Gx² + Gy² will then give the final value for the channel in question. I’ll not go into much more detail on the Sobel operator here however I recommend thoroughly reading the guide in the problem description.
The code for this one can be implemented in a similar method to blur, as again we need to work with surrounding pixels. Again we start by making a duplicate array which we will be taking values from while manipulating the original image. We can also initialise the Sobel arrays which will be referenced later.
// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
// Create temp array
RGBTRIPLE temp[height][width];
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
temp[i][j] = image[i][j];
}
} // Initialise Sobel arrays
int Gx[3][3] = {{-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1}};
int Gy[3][3] = {{-1, -2, -1}, {0, 0, 0}, {1, 2, 1}};
Next we loop through each pixel as before, and initialise the Gx and Gy values for each pixel’s red, green and blue channels. The same logic as the blur function can then be used to check for the existence of surrounding pixels. If they exist, add to the Gx and Gy values for each of the red, green and blue channels. This is done by multiplying the surrounding pixels by their respective operators in the Sobel matrix.
// Loop through rows
for (int i = 0; i < height; i++)
{
// Loop through columns
for (int j = 0; j < width; j++)
{
// Initialise ints
float Gx_red;
float Gx_blue;
float Gx_green;
float Gy_red;
float Gy_blue;
float Gy_green; Gx_red = Gx_blue = Gx_green = Gy_red = Gy_blue = Gy_green = 0; // For each pixel, loop vertical and horizontal
for (int k = -1; k < 2; k++)
{
for (int l = -1; l < 2; l++)
{
// Check if pixel is outside rows
if (i + k < 0 || i + k >= height)
{
continue;
}
// Check if pixel is outside columns
if (j + l < 0 || j + l >= width)
{
continue;
}
// Otherwise add to sums
Gx_red += temp[i + k][j + l].rgbtRed * Gx[k + 1][l + 1];
Gx_green += temp[i + k][j + l].rgbtGreen * Gx[k + 1][l + 1];
Gx_blue += temp[i + k][j + l].rgbtBlue * Gx[k + 1][l + 1];
Gy_red += temp[i + k][j + l].rgbtRed * Gy[k + 1][l + 1];
Gy_green += temp[i + k][j + l].rgbtGreen * Gy[k + 1][l + 1];
Gy_blue += temp[i + k][j + l].rgbtBlue * Gy[k + 1][l + 1]; }
}
The square root of the sum of the squares of the red, green and blue Sobel values can now be calculated to give the final values for the pixel being operated on. Make sure to include a check that limits each value to the maximum of 255, before assigning the calculated values to the image pixels.
// Calculate Sobel operator
int red = round(sqrt(Gx_red * Gx_red + Gy_red * Gy_red));
int green = round(sqrt(Gx_green * Gx_green + Gy_green * Gy_green));
int blue = round(sqrt(Gx_blue * Gx_blue + Gy_blue * Gy_blue)); // Cap at 255
if (red > 255)
{
red = 255;
}
if (green > 255)
{
green = 255;
}
if (blue > 255)
{
blue = 255;
} // Assign new values to pixels
image[i][j].rgbtRed = red;
image[i][j].rgbtGreen = green;
image[i][j].rgbtBlue = blue;
}
}
return;
}
So now you know how image filters work! Very satisfying to see such a visual output from our code for this problem.
