В конце четвертой недели курса CS50 (Harvard) нам выпало интересное задание: сделать программу, которая принимает исходное изображение и накладывает на него фильтр с выделением краев объектов (filter-more). Этот эффект достигается применением оператора Собеля — вокруг каждого исходного пикселя берется сетка 3х3 (еще 8 пикселей, кроме исходного) и рассчитывается по формуле сначала значения Gx и Gy, а затем вычисляется квадратный корень из суммы квадратов полученных значений. Значения Gx и Gy возводятся в квадрат, чтобы избежать отрицательных чисел.
Что из себя представляет квадрат из чисел Gx и Gy? Это вычисление значений производных по вертикали и по горизонтали, что на практике выглядит как умножение значений цветов RGB каждого пикселя на число в заданных Gx и Gy матрицах. Суть таких вычислений сводится к тому, что мы сравниваем значения по каждую сторону от нулей, если разницы нет — значит цвет не изменяется, если есть переход от меньшего к большему, значит, и есть градиент и чем больше разница, тем сильнее меняется цвет на изображении. Следовательно, в том месте, где есть переход, на новом изображении будет нарисована «граница».
Подобная методика позволяет компьютеру «увидеть», где меняется один цвет на другой, оценить степень резкости перехода оттенков: сначала справа налево, а затем сверху вниз. Близкая по сути методика используется в технологии искусственного интеллекта, когда ИИ нужно обработать картинку и выделить объект или обнаружить его границу. Это крайне интересный подход, и чтобы его реализовать нужно поочередно брать пиксель, мысленно выстраивать вокруг него квадрат и для всего квадрата вычислять новые значения. Чтобы лучше понять суть задачи, с нарисовала схему:
Код программы фильтра (Штукенция)
Я по сути немного обновила код, который я использовала в прошлом задании про фильтры. Сначала вся задача показалась мне сложной, но когда я сообразила, как можно использовать наработки из фильтра Blur, написать код оказалось не так уж трудно. Я на каждом этапе условий ввела дополнительные расчеты Gx и Gy. И в конце двух вложенных циклов добавила вычисление финального значения цвета взятого пикселя для цветов RGB. Это часть программы, отвечающая за работу фильтра:
#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; }
Решение Игроглаза номер 1 (с какой-то странной ошибкой… так и не смог ее отловить. Кто найдет — пишите в комментариях):
// 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; }
Второе решение от Игроглаза, рабочее. Пришлось переписывать все с нуля, но в итоге получилось сильно лучше и понятнее. Специально оставлял нулевые расчеты, чтобы код проще читался… наученный горьким опытом 😀
// 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; }