At the end of the fourth week of the CS50 (Harvard) course, we had an interesting task: to make a program that takes the original image and imposes a filter on it with selection of the edges of objects (filter-more). This effect is achieved by applying the Sobel operator – a 3×3 grid is taken around each source pixel (another 8 pixels, in addition to the source one) and calculated by the formula, first the Gx and Gy values, and then the square root is calculated from the sum of the squares of the obtained values. The Gx and Gy values are squared to avoid negative numbers.
What is the square of the numbers Gx and Gy? This is the calculation of the vertical and horizontal derivative values, which in practice looks like multiplying the RGB color values of each pixel by a number in the given Gx and Gy matrices. The essence of such calculations is that we compare the values on each side of zero, if there is no difference, then the color does not change, if there is a transition from smaller to larger, then there is a gradient and the larger the difference, the more the color changes in the image . Therefore, in the place where there is a transition, a “border” will be drawn on the new image.
This technique allows the computer to “see” where one color changes to another, to assess the degree of sharpness of the transition of shades: first from right to left, and then from top to bottom. An essentially similar technique is used in artificial intelligence technology when AI needs to process a picture and select an object or detect its border. This is an extremely interesting approach, and in order to implement it, you need to take a pixel in turn, mentally build a square around it, and calculate new values for the entire square. To better understand the essence of the problem, I drew a diagram:
Filter – program code (Stukensia)
I basically updated the code that I used in the previous task about filters a little. At first, the whole task seemed daunting to me, but when I figured out how to use the best practices from the Blur filter, writing the code turned out to be not so difficult. I introduced additional calculations for Gx and Gy at each stage of the conditions. And at the end of the two nested loops, I added the calculation of the final color value of the taken pixel for RGB colors. This is the part of the program responsible for the filter operation:
#include "helpers.h"
#include <math.h>
// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
RGBTRIPLE copy[height][width]; // New array for copy of image color values
for (int i = 0; i <= (height - 1); i++)
{
for (int j = 0; j <= (width - 1); j++)
{
copy[i][j] = image[i][j]; // make copy of initail array of colors
}
}
for (int k = 0; k <= (height - 1); k++)
{
for (int m = 0; m <= (width - 1); m++)
{
float amount = 1.0; // to divide at 1.0 and not just 1 to get float
// Initial sum of RGB for central pixel Gx
int sum_Blue_Gx = 0;
int sum_Green_Gx = 0;
int sum_Red_Gx = 0;
// Initial sum of RGB for central pixel Gy
int sum_Blue_Gy = 0;
int sum_Green_Gy = 0;
int sum_Red_Gy = 0;
// Check if the point has suitable neighbors and calculate sum RGB
if (0 <= (m - 1) && 0 <= (k - 1))
{
// Calculate Gx
sum_Blue_Gx += copy[k - 1][m - 1].rgbtBlue * (- 1);
sum_Green_Gx += copy[k - 1][m - 1].rgbtGreen * (- 1);
sum_Red_Gx += copy[k - 1][m - 1].rgbtRed * (- 1);
// Calculate Gy
sum_Blue_Gy += copy[k - 1][m - 1].rgbtBlue * (- 1);
sum_Green_Gy += copy[k - 1][m - 1].rgbtGreen * (- 1);
sum_Red_Gy += copy[k - 1][m - 1].rgbtRed * (- 1);
amount += 1;
}
if (0 <= (m - 1))
{
sum_Blue_Gx += copy[k][m - 1].rgbtBlue * (-2);
sum_Green_Gx += copy[k][m - 1].rgbtGreen * (-2);
sum_Red_Gx += copy[k][m - 1].rgbtRed * (-2);
sum_Blue_Gy += copy[k][m - 1].rgbtBlue * (0);
sum_Green_Gy += copy[k][m - 1].rgbtGreen * (0);
sum_Red_Gy += copy[k][m - 1].rgbtRed * (0);
amount += 1;
}
if (0 <= (m - 1) && (k + 1) <= (height - 1))
{
sum_Blue_Gx += copy[k + 1][m - 1].rgbtBlue * (-1);
sum_Green_Gx += copy[k + 1][m - 1].rgbtGreen * (-1);
sum_Red_Gx += copy[k + 1][m - 1].rgbtRed * (-1);
sum_Blue_Gy += copy[k + 1][m - 1].rgbtBlue * (1);
sum_Green_Gy += copy[k + 1][m - 1].rgbtGreen * (1);
sum_Red_Gy += copy[k + 1][m - 1].rgbtRed * (1);
amount += 1;
}
if (0 <= (k - 1))
{
sum_Blue_Gx += copy[k - 1][m].rgbtBlue * (0);
sum_Green_Gx += copy[k - 1][m].rgbtGreen * (0);
sum_Red_Gx += copy[k - 1][m].rgbtRed * (0);
sum_Blue_Gy += copy[k - 1][m].rgbtBlue * (-2);
sum_Green_Gy += copy[k - 1][m].rgbtGreen * (-2);
sum_Red_Gy += copy[k - 1][m].rgbtRed * (-2);
amount += 1;
}
if ((k + 1) <= (height - 1))
{
sum_Blue_Gx += copy[k + 1][m].rgbtBlue * (0);
sum_Green_Gx += copy[k + 1][m].rgbtGreen * (0);
sum_Red_Gx += copy[k + 1][m].rgbtRed * (0);
sum_Blue_Gy += copy[k + 1][m].rgbtBlue * (2);
sum_Green_Gy += copy[k + 1][m].rgbtGreen * (2);
sum_Red_Gy += copy[k + 1][m].rgbtRed * (2);
amount += 1;
}
if ((m + 1) <= (width - 1) && 0 <= (k - 1))
{
sum_Blue_Gx += copy[k - 1][m + 1].rgbtBlue * (1);
sum_Green_Gx += copy[k - 1][m + 1].rgbtGreen * (1);
sum_Red_Gx += copy[k - 1][m + 1].rgbtRed * (1);
sum_Blue_Gy += copy[k - 1][m + 1].rgbtBlue * (-1);
sum_Green_Gy += copy[k - 1][m + 1].rgbtGreen * (-1);
sum_Red_Gy += copy[k - 1][m + 1].rgbtRed * (-1);
amount += 1;
}
if ((m + 1) <= (width - 1))
{
sum_Blue_Gx += copy[k][m + 1].rgbtBlue * (2);
sum_Green_Gx += copy[k][m + 1].rgbtGreen * (2);
sum_Red_Gx += copy[k][m + 1].rgbtRed * (2);
sum_Blue_Gy += copy[k][m + 1].rgbtBlue * (0);
sum_Green_Gy += copy[k][m + 1].rgbtGreen * (0);
sum_Red_Gy += copy[k][m + 1].rgbtRed * (0);
amount += 1;
}
if ((m + 1) <= (width - 1) && (k + 1) <= (height - 1))
{
sum_Blue_Gx += copy[k + 1][m + 1].rgbtBlue * (1);
sum_Green_Gx += copy[k + 1][m + 1].rgbtGreen * (1);
sum_Red_Gx += copy[k + 1][m + 1].rgbtRed * (1);
sum_Blue_Gy += copy[k + 1][m + 1].rgbtBlue * (1);
sum_Green_Gy += copy[k + 1][m + 1].rgbtGreen * (1);
sum_Red_Gy += copy[k + 1][m + 1].rgbtRed * (1);
amount += 1;
}
// Calculate the Sobel filter with Gx and Gy
// Blue final color
double Sobel_Blue = sqrt(sum_Blue_Gx * sum_Blue_Gx + sum_Blue_Gy * sum_Blue_Gy);
int Sob_Blue = (roundf(Sobel_Blue));
if (Sob_Blue > 255)
{
Sob_Blue = 255;
}
// Green final color
double Sobel_Green = sqrt(sum_Green_Gx * sum_Green_Gx + sum_Green_Gy * sum_Green_Gy);
int Sob_Green = (roundf(Sobel_Green));
if (Sob_Green > 255)
{
Sob_Green = 255;
}
// Red final color
double Sobel_Red = sqrt(sum_Red_Gx * sum_Red_Gx + sum_Red_Gy * sum_Red_Gy);
int Sob_Red = (roundf(Sobel_Red));
if (Sob_Red > 255)
{
Sob_Red = 255;
}
// reassign new RGB values
image[k][m].rgbtBlue = Sob_Blue;
image[k][m].rgbtGreen = Sob_Green;
image[k][m].rgbtRed = Sob_Red;
}
}
return;
}
Igroglaz’s solution number 1 (with some strange error … I could not catch it. Whoever finds it – write in the comments):
// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
// create buffer array
RGBTRIPLE buffer[height][width];
int xr = 0, xg = 0, xb = 0, yr = 0, yg = 0, yb = 0; // Sobel Operators: Gx and Gy
// hack.. -1 cause width/height starts from 1; while we count from 0
height -= 1;
width -= 1;
for (int h = 0; h <= height; h++)
{
for (int w = 0; w <= width; w++)
{
// upper left corner
if (h == 0 && w == 0)
{
xr = image[h][w + 1].rgbtRed * 2 + image[h + 1][w + 1].rgbtRed;
xg = image[h][w + 1].rgbtGreen * 2 + image[h + 1][w + 1].rgbtGreen;
xb = image[h][w + 1].rgbtBlue * 2 + image[h + 1][w + 1].rgbtBlue;
yr = image[h + 1][w].rgbtRed * 2 + image[h + 1][w + 1].rgbtRed;
yg = image[h + 1][w].rgbtGreen * 2 + image[h + 1][w + 1].rgbtGreen;
yb = image[h + 1][w].rgbtBlue * 2 + image[h + 1][w + 1].rgbtBlue;
}
// upper right corner
else if (h == 0 && w == width)
{
xr = image[h][w - 1].rgbtRed * -2 + -image[h + 1][w - 1].rgbtRed;
xg = image[h][w - 1].rgbtGreen * -2 + -image[h + 1][w - 1].rgbtGreen;
xb = image[h][w - 1].rgbtBlue * -2 + -image[h + 1][w - 1].rgbtBlue;
yr = image[h + 1][w - 1].rgbtRed + image[h + 1][w].rgbtRed * 2;
yg = image[h + 1][w - 1].rgbtGreen + image[h + 1][w].rgbtGreen * 2;
yb = image[h + 1][w - 1].rgbtBlue + image[h + 1][w].rgbtBlue * 2;
}
// bottom left corner
else if (h == height && w == 0)
{
xr = image[h - 1][w + 1].rgbtRed + image[h][w + 1].rgbtRed * 2;
xg = image[h - 1][w + 1].rgbtGreen + image[h][w + 1].rgbtGreen * 2;
xb = image[h - 1][w + 1].rgbtBlue + image[h][w + 1].rgbtBlue * 2;
yr = image[h - 1][w].rgbtRed * -2 + -image[h - 1][w + 1].rgbtRed;
yg = image[h - 1][w].rgbtGreen * -2 + -image[h - 1][w + 1].rgbtGreen;
yb = image[h - 1][w].rgbtBlue * -2 + -image[h - 1][w + 1].rgbtBlue;
}
// bottom right corner
else if (h == height && w == width)
{
xr = image[h][w - 1].rgbtRed * -2 + -image[h - 1][w - 1].rgbtRed;
xg = image[h][w - 1].rgbtGreen * -2 + -image[h - 1][w - 1].rgbtGreen;
xb = image[h][w - 1].rgbtBlue * -2 + -image[h - 1][w - 1].rgbtBlue;
yr = -image[h - 1][w - 1].rgbtRed + image[h - 1][w].rgbtRed * -2;
yg = -image[h - 1][w - 1].rgbtGreen + image[h - 1][w].rgbtGreen * -2;
yb = -image[h - 1][w - 1].rgbtBlue + image[h - 1][w].rgbtBlue * -2;
}
// upper border
else if (h == 0)
{
xr = image[h][w - 1].rgbtRed * -2 + -image[h + 1][w - 1].rgbtRed + image[h + 1][w + 1].rgbtRed +
image[h][w + 1].rgbtRed * 2;
xg = image[h][w - 1].rgbtGreen * -2 + -image[h + 1][w - 1].rgbtGreen + image[h + 1][w + 1].rgbtGreen +
image[h][w + 1].rgbtGreen * 2;
xb = image[h][w - 1].rgbtBlue * -2 + -image[h + 1][w - 1].rgbtBlue + image[h + 1][w + 1].rgbtBlue +
image[h][w + 1].rgbtBlue * 2;
yr = image[h + 1][w - 1].rgbtRed + image[h + 1][w].rgbtRed * 2 + image[h + 1][w + 1].rgbtRed;
yg = image[h + 1][w - 1].rgbtGreen + image[h + 1][w].rgbtGreen * 2 + image[h + 1][w + 1].rgbtGreen;
yb = image[h + 1][w - 1].rgbtBlue + image[h + 1][w].rgbtBlue * 2 + image[h + 1][w + 1].rgbtBlue;
}
// left side
else if (w == 0)
{
xr = image[h - 1][w + 1].rgbtRed + image[h][w + 1].rgbtRed * 2 + image[h + 1][w + 1].rgbtRed;
yg = image[h - 1][w + 1].rgbtGreen + image[h][w + 1].rgbtGreen * 2 + image[h + 1][w + 1].rgbtGreen;
xb = image[h - 1][w + 1].rgbtBlue + image[h][w + 1].rgbtBlue * 2 + image[h + 1][w + 1].rgbtBlue;
yr = image[h - 1][w].rgbtRed * -2 + -image[h - 1][w + 1].rgbtRed + image[h + 1][w + 1].rgbtRed +
image[h + 1][w].rgbtRed * 2;
yg = image[h - 1][w].rgbtGreen * -2 + -image[h - 1][w + 1].rgbtGreen + image[h + 1][w + 1].rgbtGreen +
image[h + 1][w].rgbtGreen * 2;
yb = image[h - 1][w].rgbtBlue * -2 + -image[h - 1][w + 1].rgbtBlue + image[h + 1][w + 1].rgbtBlue +
image[h + 1][w].rgbtBlue * 2;
}
//right side
else if (w == width)
{
xr = -image[h - 1][w - 1].rgbtRed + image[h][w - 1].rgbtRed * -2 + -image[h + 1][w - 1].rgbtRed;
xg = -image[h - 1][w - 1].rgbtGreen + image[h][w - 1].rgbtGreen * -2 + -image[h + 1][w - 1].rgbtGreen;
xb = -image[h - 1][w - 1].rgbtBlue + image[h][w - 1].rgbtBlue * -2 + -image[h + 1][w - 1].rgbtBlue;
yr = image[h - 1][w].rgbtRed * -2 + -image[h - 1][w - 1].rgbtRed + image[h + 1][w - 1].rgbtRed +
image[h + 1][w].rgbtRed * 2;
yg = image[h - 1][w].rgbtGreen * -2 + -image[h - 1][w - 1].rgbtGreen + image[h + 1][w - 1].rgbtGreen +
image[h + 1][w].rgbtGreen * 2;
yb = image[h - 1][w].rgbtBlue * -2 + -image[h - 1][w - 1].rgbtBlue + image[h + 1][w - 1].rgbtBlue +
image[h + 1][w].rgbtBlue * 2;
}
// bottom border
else if (h == height)
{
xr = image[h][w - 1].rgbtRed * -2 + -image[h - 1][w - 1].rgbtRed + image[h - 1][w + 1].rgbtRed +
image[h][w + 1].rgbtRed * 2;
xg = image[h][w - 1].rgbtGreen * -2 + -image[h - 1][w - 1].rgbtGreen + image[h - 1][w + 1].rgbtGreen +
image[h][w + 1].rgbtGreen * 2;
xb = image[h][w - 1].rgbtBlue * -2 + -image[h - 1][w - 1].rgbtBlue + image[h - 1][w + 1].rgbtBlue +
image[h][w + 1].rgbtBlue * 2;
yr = -image[h - 1][w - 1].rgbtRed + image[h - 1][w].rgbtRed * -2 + -image[h - 1][w + 1].rgbtRed;
yg = -image[h - 1][w - 1].rgbtGreen + image[h - 1][w].rgbtGreen * -2 + -image[h - 1][w + 1].rgbtGreen;
yb = -image[h - 1][w - 1].rgbtBlue + image[h - 1][w].rgbtBlue * -2 + -image[h - 1][w + 1].rgbtBlue;
}
// general case
else
{
xr = image[h - 1][w + 1].rgbtRed + image[h][w + 1].rgbtRed * 2 + image[h + 1][w + 1].rgbtRed +
-image[h + 1][w - 1].rgbtRed + image[h][w - 1].rgbtRed * -2 + -image[h - 1][w - 1].rgbtRed;
xg = image[h - 1][w + 1].rgbtGreen + image[h][w + 1].rgbtGreen * 2 + image[h + 1][w + 1].rgbtGreen +
-image[h + 1][w - 1].rgbtGreen + image[h][w - 1].rgbtGreen * -2 + -image[h - 1][w - 1].rgbtGreen;
xb = image[h - 1][w + 1].rgbtBlue + image[h][w + 1].rgbtBlue * 2 + image[h + 1][w + 1].rgbtBlue +
-image[h + 1][w - 1].rgbtBlue + image[h][w - 1].rgbtBlue * -2 + -image[h - 1][w - 1].rgbtBlue;
yr = image[h - 1][w].rgbtRed * -2 + -image[h - 1][w + 1].rgbtRed + image[h + 1][w + 1].rgbtRed +
image[h + 1][w].rgbtRed * 2 + image[h + 1][w - 1].rgbtRed + -image[h - 1][w - 1].rgbtRed;
yg = image[h - 1][w].rgbtGreen * -2 + -image[h - 1][w + 1].rgbtGreen + image[h + 1][w + 1].rgbtGreen +
image[h + 1][w].rgbtGreen * 2 + image[h + 1][w - 1].rgbtGreen + -image[h - 1][w - 1].rgbtGreen;
yb = image[h - 1][w].rgbtBlue * -2 + -image[h - 1][w + 1].rgbtBlue + image[h + 1][w + 1].rgbtBlue +
image[h + 1][w].rgbtBlue * 2 + image[h + 1][w - 1].rgbtBlue + -image[h - 1][w - 1].rgbtBlue;
}
int sr = 0;
sr = round(sqrt((xr * xr) + (yr * yr))); // ! as rgbt is BYTE (255) - we can't put there Sobel number
if (sr > 255)
{
sr = 255;
}
buffer[h][w].rgbtRed = sr;
int sg = 0;
sg = round(sqrt((xg * xg) + (yg * yg)));
if (sg > 255)
{
sg = 255;
}
buffer[h][w].rgbtGreen = sg;
int sb = 0;
sb = round(sqrt((xb * xb) + (yb * yb)));
if (sb > 255)
{
sb = 255;
}
buffer[h][w].rgbtBlue = sb;
}
}
// put pixels from buffer array back to the picture
for (int h = 0; h <= height; h++)
{
for (int w = 0; w <= width; w++)
{
image[h][w].rgbtRed = buffer[h][w].rgbtRed;
image[h][w].rgbtGreen = buffer[h][w].rgbtGreen;
image[h][w].rgbtBlue = buffer[h][w].rgbtBlue;
}
}
return;
}
The second solution from Igroglaz, working. I had to rewrite everything from scratch, but in the end it turned out much better and clearer. I deliberately left zero calculations to make the code easier to read … learned from bitter experience 😀
// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
// create buffer array
RGBTRIPLE buffer[height][width];
// hack.. -1 cause width/height starts from 1; while we count from 0
height -= 1;
width -= 1;
for (int h = 0; h <= height; h++)
{
for (int w = 0; w <= width; w++)
{
// Sobel Operators: Gx and Gy. Must be initialized there to wipe old values.
int xr = 0, xg = 0, xb = 0, yr = 0, yg = 0, yb = 0;
if (h - 1 >= 0 && w - 1 >= 0)
{
xr += image[h - 1][w - 1].rgbtRed * - 1;
xg += image[h - 1][w - 1].rgbtGreen * - 1;
xb += image[h - 1][w - 1].rgbtBlue * - 1;
yr += image[h - 1][w - 1].rgbtRed * - 1;
yg += image[h - 1][w - 1].rgbtGreen * - 1;
yb += image[h - 1][w - 1].rgbtBlue * - 1;
}
if (h - 1 >= 0)
{
xr += image[h - 1][w].rgbtRed * 0;
xg += image[h - 1][w].rgbtGreen * 0;
xb += image[h - 1][w].rgbtBlue * 0;
yr += image[h - 1][w].rgbtRed * -2;
yg += image[h - 1][w].rgbtGreen * -2;
yb += image[h - 1][w].rgbtBlue * -2;
}
if (h - 1 >= 0 && w + 1 <= width)
{
xr += image[h - 1][w + 1].rgbtRed * 1;
xg += image[h - 1][w + 1].rgbtGreen * 1;
xb += image[h - 1][w + 1].rgbtBlue * 1;
yr += image[h - 1][w + 1].rgbtRed * -1;
yg += image[h - 1][w + 1].rgbtGreen * -1;
yb += image[h - 1][w + 1].rgbtBlue * -1;
}
if (w - 1 >= 0)
{
xr += image[h][w - 1].rgbtRed * -2;
xg += image[h][w - 1].rgbtGreen * -2;
xb += image[h][w - 1].rgbtBlue * -2;
yr += image[h][w - 1].rgbtRed * 0;
yg += image[h][w - 1].rgbtGreen * 0;
yb += image[h][w - 1].rgbtBlue * 0;
}
//
// <--- there should be center, but we pass it as it's 0 in both cases
//
if (w + 1 <= width)
{
xr += image[h][w + 1].rgbtRed * 2;
xg += image[h][w + 1].rgbtGreen * 2;
xb += image[h][w + 1].rgbtBlue * 2;
yr += image[h][w + 1].rgbtRed * 0;
yg += image[h][w + 1].rgbtGreen * 0;
yb += image[h][w + 1].rgbtBlue * 0;
}
if (h + 1 <= height && w - 1 >= 0)
{
xr += image[h + 1][w - 1].rgbtRed * -1;
xg += image[h + 1][w - 1].rgbtGreen * -1;
xb += image[h + 1][w - 1].rgbtBlue * -1;
yr += image[h + 1][w - 1].rgbtRed * 1;
yg += image[h + 1][w - 1].rgbtGreen * 1;
yb += image[h + 1][w - 1].rgbtBlue * 1;
}
if (h + 1 <= height)
{
xr += image[h + 1][w].rgbtRed * 0;
xg += image[h + 1][w].rgbtGreen * 0;
xb += image[h + 1][w].rgbtBlue * 0;
yr += image[h + 1][w].rgbtRed * 2;
yg += image[h + 1][w].rgbtGreen * 2;
yb += image[h + 1][w].rgbtBlue * 2;
}
if (h + 1 <= height && w + 1 <= width)
{
xr += image[h + 1][w + 1].rgbtRed * 1;
xg += image[h + 1][w + 1].rgbtGreen * 1;
xb += image[h + 1][w + 1].rgbtBlue * 1;
yr += image[h + 1][w + 1].rgbtRed * 1;
yg += image[h + 1][w + 1].rgbtGreen * 1;
yb += image[h + 1][w + 1].rgbtBlue * 1;
}
int sr = 0;
sr = round(sqrt((xr * xr) + (yr * yr))); // ! as rgbt is BYTE (255) - we can't put there Sobel number
if (sr > 255)
{
sr = 255;
}
buffer[h][w].rgbtRed = sr;
int sg = 0;
sg = round(sqrt((xg * xg) + (yg * yg)));
if (sg > 255)
{
sg = 255;
}
buffer[h][w].rgbtGreen = sg;
int sb = 0;
sb = round(sqrt((xb * xb) + (yb * yb)));
if (sb > 255)
{
sb = 255;
}
buffer[h][w].rgbtBlue = sb;
}
}
// put pixels from buffer array back to the picture
for (int h = 0; h <= height; h++)
{
for (int w = 0; w <= width; w++)
{
image[h][w].rgbtRed = buffer[h][w].rgbtRed;
image[h][w].rgbtGreen = buffer[h][w].rgbtGreen;
image[h][w].rgbtBlue = buffer[h][w].rgbtBlue;
}
}
return;
}