Сила оттенков серого: компьютерное зрение с нуля

В обсуждениях компьютерного зрения обычно речь идёт об OpenCV или нейронных сетях глубокого обучения наподобие YOLO. Однако в большинстве случаев для работы с компьютерным зрением требуется понимание базовых алгоритмов, чтобы можно было адаптировать их под свои нужды.

Мне захотелось понять, насколько далеко я смогу зайти, оставив в computer vision только самый минимум: одни лишь 8-битные изображения в градациях серого; никаких сложных структур данных, старый добрый C, немного байтовых массивов и единственный файл заголовка. В конце концов, изображение — это ведь просто прямоугольник из чисел, не так ли?

Этот пост — экскурсия по алгоритмам, лежащим в основе Grayskull — минималистичной библиотеки компьютерного зрения, спроектированной для устройств с ограниченными ресурсами.

Пиксели

Пиксель в градациях серого обычно представлен одним байтом: 0 означает чёрный цвет_, 255 — белый, а промежуточные значения представляют различные оттенки серого.

По сути, изображение в градациях серого — это 2D-массив таких пикселей, задаваемый шириной и высотой, однако на языках с более простой структурой памяти наподобие C он часто представляется в виде 1D-массива размером width * height:

// Изображение размером WxH пикселей, хранящееся как плоский массив байтов struct gs_image { unsigned w, h; uint8_t *data; };  // Вспомогательные функции для считывания/записи значений пикселей с учётом границ uint8_t gs_get(struct gs_image img, unsigned x, unsigned y) {   return (x < img.w && y < img.h) ? img.data[y * img.w + x] : 0; } void gs_set(struct gs_image img, unsigned x, unsigned y, uint8_t value) {   if (x < img.w && y < img.h) img.data[y * img.w + x] = value; }  // Удобный макрос для итеративного обхода всех пикселей #define gs_for(img, x, y)                   for (unsigned y = 0; y < (img).h; y++)      for (unsigned x = 0; x < (img).w; x++)

Этот скромный фундамент уже позволяет нам выполнять определённые трюки, например, инвертировать или отзеркаливать изображения:

// Инвертирование изображения (создание негатива): px[x,y] = 255 - px[x,y] gs_for(img, x, y) gs_set(img, x, y, 255 - gs_get(img, x, y));  // Отзеркаливание изображения: заменяем px[x,y] на px[w-x-1,y] gs_for(img, x, y) { for (unsigned y = 0; y < img.h; y++) {   for (unsigned x = 0; x < img.w/2; x++) { // итеративно обходим только первую половину     uint8_t tmp = gs_get(img, x, y);     gs_set(img, x, y, gs_get(img, img.w - x - 1, y));     gs_set(img, img.w - x - 1, y, tmp);   } }

struct gs_rect { unsigned x, y, w, h; }; // Для интересующих нас областей (region of interest, ROI)  // Обрезаем src изображения в dst на основании roi gs_for(roi, x, y) gs_set(dst, x, y, gs_get(src, roi.x + x, roi.y + y));  // Уменьшаем размер в два раза: усредняем значение пикселя по четырём соседям (2x2) gs_for(dst, x, y) {     unsigned sum = 0;     for (unsigned j = 0; j < 2; j++)       for (unsigned i = 0; i < 2; i++)         sum += gs_get(src, x * 2 + i, y * 2 + j);     gs_set(dst, x, y, sum / 4); }

Можно выполнять наивное изменение размера по ближайшим соседям, результат будет быстрым, но слишком грубым, или же выполнять билинейную интерполяцию, что медленнее и требует операций с плавающей запятой, зато часто выглядит красивее:

// Изменение размера по ближайшим соседям void gs_resize_nn(struct gs_image dst, struct gs_image src) {     gs_for(dst, x, y) {         unsigned sx = x * src.w / dst.w, sy = y * src.h / dst.h;         gs_set(dst, x, y, gs_get(src, sx, sy));     } }  // Билинейное изменение размера GS_API void gs_resize(struct gs_image dst, struct gs_image src) {   gs_for(dst, x, y) {     float sx = ((float)x + 0.5f) * src.w / dst.w, sy = ((float)y + 0.5f) * src.h / dst.h;     sx = GS_MAX(0.0f, GS_MIN(sx, src.w - 1.0f)), sy = GS_MAX(0.0f, GS_MIN(sy, src.h - 1.0f));     unsigned sx_int = (unsigned)sx, sy_int = (unsigned)sy;     unsigned sx1 = GS_MIN(sx_int + 1, src.w - 1), sy1 = GS_MIN(sy_int + 1, src.h - 1);     float dx = sx - sx_int, dy = sy - sy_int;     uint8_t c00 = gs_get(src, sx_int, sy_int), c01 = gs_get(src, sx1, sy_int),             c10 = gs_get(src, sx_int, sy1), c11 = gs_get(src, sx1, sy1);     uint8_t p = (c00 * (1 - dx) * (1 - dy)) + (c01 * dx * (1 - dy)) + (c10 * (1 - dx) * dy) + (c11 * dx * dy);     gs_set(dst, x, y, p);   } }

Так исходное изображение (слева) выглядит после билинейного изменения размера (посередине) и изменения размера по ближайшим соседям (справа).

Обработка изображений

Теперь, когда мы можем манипулировать отдельными пикселями, можно приступать к более серьёзной обработке изображений.

Полезным инструментом здесь будут свёрточные фильтры. Фильтр — это маленький 2D-массив (ядро), применяемый к каждому пикселю изображения. Новое значение пикселя вычисляется как взвешенная сумма соседних пикселей, где веса определяются ядром.

void gs_filter(struct gs_image dst, struct gs_image src, struct gs_image kernel, unsigned norm) {     gs_for(dst, x, y) {         int sum = 0;         gs_for(kernel, i, j) {             sum += gs_get(src, x + i - kernel.w / 2, y + j - kernel.h / 2) * (int8_t)gs_get(kernel, i, j);         }         gs_set(dst, x, y, sum / norm);     } }

Эту методику можно использовать для размытия, повышения резкости, распознавания краёв и многих других эффектов. Вот примеры одних из самых распространённых ядер. Учтите, что они определяются, как 8-битные integer со знаком:

// box blur 3x3, все пиксели имеют одинаковый вес struct gs_image gs_blur_box = {3, 3, (uint8_t *)(int8_t[]){1, 1, 1, 1, 1, 1, 1, 1, 1}}; // гауссово размытие 3x3, центральные пиксели имеют больший вес struct gs_image gs_blur_gaussian = {3, 3, (uint8_t *)(int8_t[]){1, 2, 1, 2, 4, 2, 1, 2, 1}}; // повышение резкости и усиление краёв struct gs_image gs_sharpen = {3, 3, (uint8_t *)(int8_t[]){0, -1, 0, -1, 5, -1, 0, -1, 0}}; // тиснение, изображение становится более "3D" struct gs_image gs_emboss = {3, 3, (uint8_t *)(int8_t[]){-2, -1, 0, -1, 1, 1, 0, 1, 2}};

Аналогично, можно применить фильтры Собеля, которые полезны, если мы хотим распознавать на изображениях края:

struct gs_image gs_sobel_x = {3, 3, (uint8_t *)(int8_t[]){-1, 0, 1, -2, 0, 2, -1, 0, 1}}; struct gs_image gs_sobel_y = {3, 3, (uint8_t *)(int8_t[]){1, 2, 1, 0, 0, 0, -1, -2, -1}};  void gs_sobel(struct gs_image dst, struct gs_image src) {     struct gs_image gx = {src.w, src.h, malloc(src.w * src.h)};     struct gs_image gy = {src.w, src.h, malloc(src.w * src.h)};     gs_filter(gx, src, gs_sobel_x, 1);     gs_filter(gy, src, gs_sobel_y, 1);     gs_for(dst, x, y) {         int mag = sqrt(gs_get(gx, x, y) * gs_get(gx, x, y) + gs_get(gy, x, y) * gs_get(gy, x, y));         gs_set(dst, x, y, GS_MIN(mag, 255));     }     free(gx.data);     free(gy.data); }

Вот примеры таких фильтров; обратите внимание, как некоторые из них устраняют шум или выделяют края:

Первое изображение — это оригинал, далее идут box filter и фильтр гауссова размытия. Затем идёт фильтр повышения резкости, фильтр тиснения и, наконец, фильтр Собеля, выделяющий края.

Пороговые значения

Чтобы «видеть» объекты на изображении, нам нужно разделить его на передний и задний планы, а затем работать с передними сегментами, пытаясь найти интересующие нас объекты.

Гораздо проще это делать, если каждый пиксель полностью чёрный или полностью белый. Такое преобразование из градаций серого в чёрно-белые данные называется thresholding (бинаризацией).

В простейшем случае мы можем считать все пиксели со значениями больше 127 белыми, а ниже — чёрными. Это thresholding с фиксированным уровнем. Разумеется, если изображение тёмное, то такое значение thresholding окажется слишком высоким и многие значимые детали будут утеряны. Как же выбрать пороговое значение точнее?

// Применяем фиксированное пороговое значение и бинаризируем изображение GS_API void gs_threshold(struct gs_image img, uint8_t thresh) {   for (unsigned i = 0; i < img.w * img.h; i++) img.data[i] = (img.data[i] > thresh) ? 255 : 0; }

Одно из решений заключается в вычислении распределения яркости как гистограммы. Мы знаем, что на изображении в градациях серого есть 255 уникальных значений, поэтому можем итеративно обойти все пиксели и посчитать, какие из них имеют то или иное значение. Проанализировав получившуюся гистограмму, мы получим представление, какое значение пикселя лучше всего подойдёт в качестве порогового.

Это можно сделать при помощи способа Оцу. Он автоматически определяет оптимальное пороговое значение, проверяя каждое возможное (от 0 до 255). Для каждого значения он разбивает пиксели изображения на два класса (фон и передний план), а затем вычисляет их межклассовую дисперсию. Пороговым значением, максимизирующим эту дисперсию, будет то, которое создаёт наилучшее разделение между двумя классами. Такой способ довольно неплохо работает для изображений с хорошей контрастностью:

// пытаемся найти наилучшее пороговое значение для разделения "переднего" и "заднего" плана uint8_t gs_otsu_threshold(struct gs_image img) {   unsigned hist[256] = {0}, wb = 0, wf = 0, threshold = 0;   // вычисляем количество пикселей с каждым значением яркости   for (unsigned i = 0; i < img.w * img.h; i++) hist[img.data[i]]++;   float sum = 0, sumB = 0, varMax = -1.0;   for (unsigned i = 0; i < 256; i++) sum += (float)i * hist[i];   // пытаемся найти пороговое значение, максимизирующее межклассовую дисперсию   for (unsigned t = 0; t < 256; t++) {     wb += hist[t];     if (wb == 0) continue;     wf = (img.w * img.h) - wb;     if (wf == 0) break;     sumB += (float)t * hist[t];     float mB = (float)sumB / wb;     float mF = (float)(sum - sumB) / wf;     float varBetween = (float)wb * (float)wf * (mB - mF) * (mB - mF);     if (varBetween > varMax) varMax = varBetween, threshold = t;   }   return threshold; }

Однако в реальной жизни условия освещения часто неравномерны. В таких случаях единое глобальное пороговое значение может не подойти, и ни одно из потенциальных 255 пороговых значений не обеспечит хорошего результата.

Для решения этой проблемы можно использовать адаптивный thresholding. Мы не будем использовать одно пороговое значение для всего изображения, а станем вычислять локальный порог для каждого пикселя на основании средней яркости соседних пикселей. Благодаря этому можно лучше учитывать разные условия освещения в изображении:

gs_for(src, x, y) {   unsigned sum = 0, count = 0;   for (int dy = -radius; dy <= (int)radius; dy++) {     for (int dx = -radius; dx <= (int)radius; dx++) {       int sy = (int)y + dy, sx = (int)x + dx;       if (sy >= 0 && sy < (int)src.h && sx >= 0 && sx < (int)src.w) {         sum += gs_get(src, sx, sy);         count++;       }     }   }   int threshold = sum / count - c;   gs_set(dst, x, y, (gs_get(src, x, y) > threshold) ? 255 : 0); }

Посмотрим, как разные способы вычисления thresholding выглядят на одном и том же изображении:

Первое изображение — оригинал, за ним идут thresholding с фиксированным уровнем (80), способ Оцу и адаптивный thresholding. Обратите внимание, что адаптивный thresholding сохраняет больше деталей и в ярких, и в тёмных областях изображения, а у способа Оцу возникают проблемы с неравномерным освещением.

Морфологические операции

Из-за особенностей работы датчиков изображения в камерах снимки часто содержат шум.

Это означает, что после thresholding в изображении будут встречаться случайные отдельные пиксели, не относящиеся к какому-то объекту, небольшие отверстия в объектах или небольшие разрывы между частями объектов. Всё это сбивает с толку алгоритмы распознавания объектов, однако очистке двоичного изображения могут способствовать морфологические операции.

Две наиболее распространённые операции: это erosion (морфологическое сужение) и dilation (расширение). Сужение убирает пиксели на границах объектов (уменьшая их размеры), а расширение добавляет пиксели к их границам (увеличивая объекты).

Также существует opening (erosion с последующим dilation) и closing (dilation с последующим erosion). Opening полезно для удаления маленьких объектов или шума, а closing — для заполнения небольших отверстий в объектах.

void gs_erode(struct gs_image dst, struct gs_image src, unsigned radius) {   gs_for(dst, x, y) {     uint8_t min_val = 255;     for (int dy = -radius; dy <= (int)radius; dy++) {       for (int dx = -radius; dx <= (int)radius; dx++) {         int sy = (int)y + dy, sx = (int)x + dx;         if (sy >= 0 && sy < (int)src.h && sx >= 0 && sx < (int)src.w) {           uint8_t val = gs_get(src, sx, sy);           if (val < min_val) min_val = val;         }       }     }     gs_set(dst, x, y, min_val);   } } void gs_dilate(struct gs_image dst, struct gs_image src, unsigned radius) {   gs_for(dst, x, y) {     uint8_t max_val = 0;     for (int dy = -radius; dy <= (int)radius; dy++) {       for (int dx = -radius; dx <= (int)radius; dx++) {         int sy = (int)y + dy, sx = (int)x + dx;         if (sy >= 0 && sy < (int)src.h && sx >= 0 && sx < (int)src.w) {           uint8_t val = gs_get(src, sx, sy);           if (val > max_val) max_val = val;         }       }     }     gs_set(dst, x, y, max_val);   } }

Вот пример того, как морфологические операции могут подчистить довольно непонятное изображение с метками ArUco:

Первое изображение — оригинал, за которым следует изображение с thresholding (способ Оцу). Далее идут erosion с последующим dilation. Маркеры чёрные, поэтому это может показаться странным, но так как морфологические операции работают с белыми пикселями, мы, по сути, выполняем closing, но для чёрных пикселей. Также можно предварительно инвертировать изображение, а затем выполнять opening и обратное инвертирование.

В конце все маркеры уменьшаются до их исходных размеров и все их легко можно распознать по форме и размеру.

Пятна и контуры

Получив чистое двоичное изображение, можно приступать к распознаванию объектов на нём. Классический способ решения этой задачи — нахождение соединённых компонентов (пятен, blob).

Blob — группа соединённых белых пикселей (255), образующих объект. Для разметки связанных пикселей проще всего находить blob при помощи алгоритма заливки (flood-fill) или поиска в глубину (depth-first search, DFS):

void gs_flood_fill(struct gs_image img, unsigned x, unsigned y, uint8_t target, uint8_t replacement) {   if (x >= img.w || y >= img.h) return;   if (gs_get(img, x, y) != target || gs_get(img, x, y) == replacement) return;   gs_set(img, x, y, replacement);   gs_flood_fill(img, x + 1, y, target, replacement);   gs_flood_fill(img, x - 1, y, target, replacement);   gs_flood_fill(img, x, y + 1, target, replacement);   gs_flood_fill(img, x, y - 1, target, replacement); }

Разумеется, при обработке большинства реальных изображений это мгновенно увеличит стек до огромных величин. Поэтому предпочтителен итеративный подход с очередью или стеком.

Однако это всё равно не самый оптимальный способ поиска blob. Более эффективный способ — это алгоритм, состоящий из двух проходов, сканирующий изображение дважды: сначала он присваивает предварительные метки и записывает соответствия между ними, а затем выполняет второе сканирование для ресолвинга этих соответствий и присвоения каждому blob окончательной уникальной метки.

Будет здорово, если мы сможем использовать один и тот же тип gs_image для меток, но в большинстве случаев для этого потребуется больше, чем 256 меток (особенно для временных промежуточных меток). Поэтому для хранения меток нужен отдельный массив integer большего размера:

typedef uint16_t gs_label; // наверно, 64 тысяч будет достаточно?  struct gs_blob {   gs_label label; // какую метку имеет blob?   unsigned area; // сколько белых пикселей находится в blob?   struct gs_rect box; // ограничивающий прямоугольник   struct gs_point centroid; // центр "масс" }; unsigned gs_blobs(struct gs_image img, gs_label *labels, struct gs_blob *blobs, unsigned nblobs) { ... }

Прежде чем двигаться дальше, давайте поговорим о связанности. Существует два распространённых типа связанности пикселей: 4-connectivity и 8-connectivity. В 4-connectivity пиксель соединён с четырьмя непосредственными соседями (сверху, снизу, слева, справа). В 8-connectivity пиксель связан со всеми восемью окружающими его пикселями (те же, плюс по диагонали). То есть, в случае 8-connectivity показанный ниже пример будет одним blob, а в случае 4-connectivity — двумя отдельными blob:

...... . .# .###.. ......

В нашей реализации для простоты будет использоваться 4-connectivity. Рассмотрим следующее изображение:

......... .## .###.##.. .#####..# .......##

Начнём сканировать его строка за строкой. Если найден белый пиксель, проверяем соседей слева и справа:

• Если оба чёрные (0), то присваиваем пикселю новую метку, считая, что это будет новый blob.

• Если один из них белый, присваиваем его метку текущему пикселю, так как это продолжение уже имеющегося известного blob.

• Если оба белые, но имеют разные метки, то присваиваем наименьшую из меток текущему пикселю и записываем соответствие между двумя метками в особую структуру данных (как объединение-поиск).

После первого прохода массив меток будет выглядеть так:

......... .111..2.. .111.32.. .11111..4 .......55

Таблица соответствия будет выглядеть так: 1 <-> 3, 3 <-> 2, 4 <-> 5.

Во втором проходе мы разрешаем соответствия и присваиваем каждому пикселю окончательные метки. Массив окончательных меток будет выглядеть так:

......... .111..1.. .111.11.. .11111..4 .......44

На втором проходе также можно вычислять такие свойства blob, как площадь, ограничивающий прямоугольник и центр масс. Площадь самого большого blob составляет 14 пикселей, его ограничивающий прямоугольник имеет координаты от (1,1) до (6,3). Центр масс вычисляется как среднее координат всех пикселей blob, в нашем случае по оси X это будет (3*1+3*2+3*3+4+2*5+2*6)/14, или округлённо 4. По оси Y это будет (4*1+5*2+5*3)/14, или округлённо 2. То есть центр масс находится в координате (4,2), не относящейся к «телу» blob.

Эти геометрические свойства уже дают нам довольно много информации о blob. Например, мы можем фильтровать blob по площади, чтобы удалять небольшие пятна шума. Также можно вычислять соотношение сторон (ширина/высота) ограничивающего прямоугольника, чтобы отфильтровывать очень тонкие или очень широкие blob. Соотношение между реальной площадью и ограничивающим прямоугольником blob позволяет отфильтровывать недостаточно компактные blob. У прямоугольников соотношение близко к 1.0, у кругов — к pi/4 = 0.785, а у линий приближается к нулю.

Другими подсказками будут позиция центра масс, ориентация с использованием моментов или форма контура. Существует достаточно простой способ трассировки контура blob при помощи алгоритма трассировки окрестности Мура. Он начинает с известного пикселя границы и следует по контуру по часовой стрелке, проверяя соседние пиксели, пока не вернётся в начальный:

struct gs_contour { struct gs_rect box; struct gs_point start; unsigned length; }; void gs_trace_contour(struct gs_image img, struct gs_image visited, struct gs_contour *c) {   static const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};   static const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};   c->length = 0;   c->box = (struct gs_rect){c->start.x, c->start.y, 1, 1};   struct gs_point p = c->start;   unsigned dir = 7, seenstart = 0;   for (;;) {     if (!visited.data[p.y * visited.w + p.x]) c->length++;     visited.data[p.y * visited.w + p.x] = 255;     int ndir = (dir + 1) % 8, found = 0;     for (int i = 0; i < 8; i++) {       int d = (ndir + i) % 8, nx = p.x + dx[d], ny = p.y + dy[d];       if (nx >= 0 && nx < (int)img.w && ny >= 0 && ny < (int)img.h &&           img.data[ny * img.w + nx] > 128) {         p = (struct gs_point){nx, ny};         dir = (d + 6) % 8;         found = 1;         break;       }     }     if (!found) break;  // открытый контур     c->box.x = GS_MIN(c->box.x, p.x);     c->box.y = GS_MIN(c->box.y, p.y);     c->box.w = GS_MAX(c->box.w, p.x - c->box.x + 1);     c->box.h = GS_MAX(c->box.h, p.y - c->box.y + 1);     if (p.x == c->start.x && p.y == c->start.y) {       if (seenstart) break;       seenstart = 1;     }   } }

Таким образом можно получать контуры всех blob и анализировать их формы или сравнивать длины контуров (периметр) с площадью blob. Также можно аппроксимировать контуры прямыми отрезками при помощи алгоритма Рамера — Дугласа — Пекера, заменяющего кривую последовательностью отрезков прямых с сохранением общей формы.

Всё это здорово, если мы хотим распознавать простые объекты на статическом изображении. Но что если нам нужно распознавать или отслеживать более сложные объекты, такие как лица, автомобили или пешеходы?

Ключевые точки и дескрипторы

Ключевая точка (keypoint) — это определённый участок изображения, уникальный и надёжно распознаваемый вне зависимости от масштаба, поворота и освещения объекта.

На практике, ключевые точки часто оказываются углами (также называемыми «признаками», feature). Один из самых интуитивно понятных алгоритмов распознавания признаков — это FAST (Features from Accelerated Segment Test). Он исследует окружность из 16 пикселей вокруг пикселя-кандидата (в 4 пикселях от него). Если как минимум 9 смежных пикселей в этой окружности r=4px вокруг пикселя P одновременно ярче или темнее, то пиксель-кандидат считается углом:

.............. ......012..... .....F...3.... ....E.....4... ....D..P..5... ....C.....6... .....B...7.... ......A98..... ..............

Этот алгоритм прост, однако на реальных изображениях находит слишком много признаков. Решить эту проблему можно, записывая «оценку» (score) каждого признака и сохраняя только точки с наибольшей оценкой. Оценку можно вычислить как сумму абсолютных разностей между пикселем-кандидатом и смежными пикселями в окружности или как минимальную разность между центральным пикселем и пикселями на окружности.

  gs_assert(gs_valid(img) && kps && nkps > 0);   static const int dx[16] = {0, 1, 2, 3, 3, 3, 2, 1, 0, -1, -2, -3, -3, -3, -2, -1};   static const int dy[16] = {-3, -3, -2, -1, 0, 1, 2, 3, 3, 3, 2, 1, 0, -1, -2, -3};   unsigned n = 0;   // первый проход: вычисляем карту оценок   for (unsigned y = 3; y < img.h - 3; y++) {     for (unsigned x = 3; x < img.w - 3; x++) {       uint8_t p = img.data[y * img.w + x];       int run = 0, score = 0;       for (int i = 0; i < 16 + 9; i++) {         int idx = (i % 16);         uint8_t v = img.data[(y + dy[idx]) * img.w + (x + dx[idx])];         if (v > p + threshold) {           run = (run > 0) ? run + 1 : 1;         } else if (v < p - threshold) {           run = (run < 0) ? run - 1 : -1;         } else {           run = 0;         }         if (run >= 9 || run <= -9) {           score = 255;           for (int j = 0; j < 16; j++) {             int d = gs_get(img, x + dx[j], y + dy[j]) - p;             if (d < 0) d = -d;             if (d < score) score = d;           }           break;         }       }       scoremap.data[y * img.w + x] = score;     }   }   // второй проход: отбрасывание немаксимальных значений   for (unsigned y = 3; y < img.h - 3; y++) {     for (unsigned x = 3; x < img.w - 3; x++) {       int s = scoremap.data[y * img.w + x], is_max = 1;       if (s == 0) continue;       for (int yy = -1; yy <= 1 && is_max; yy++) {         for (int xx = -1; xx <= 1; xx++) {           if (xx == 0 && yy == 0) continue;           if (scoremap.data[(y + yy) * img.w + (x + xx)] > s) {             is_max = 0;             break;           }         }       }       if (is_max && n < nkps) kps[n++] = (struct gs_keypoint){{x, y}, (unsigned)s, 0, {0}};     }   }   return n; }

Обратите внимание, как на фотографии кота распознаются ключевые точки в углах и таких уникальных признаках, как глаза, нос, усы и так далее. Но как использовать ключевые точки для распознавания объектов?

Здесь на помощь приходит ORB. Он надстраивается поверх того же распознавателя углов FAST, пытается находить резкие изменения яркости, но также добавляет ещё два компонента: ориентацию и дескриптор.

После нахождения углов ORB определяет их ориентацию, вычисляя моменты изображения на небольшом участке вокруг каждой ключевой точки. Благодаря этому у каждой ключевой точки появляется угол, по сути, сообщающий, где у неё «верх».

Дескриптор — это компактное описание локального участка изображения вокруг ключевой точки, инвариантное относительно масштаба и поворота. В ORB используется модифицированная версия дескриптора BRIEF (Binary Robust Independent Elementary Features), позволяющая хитрым образом кодировать участок изображения в виде небольшой битовой строки.

Дескриптор просто сравнивает яркости битов, и если один пиксель светлее другого, то соответствующий бит получает значение 1, а в противном случае 0. Выполнив серию таких сравнений, можно создать двоичную строку, описывающую локальный участок изображения.

Дескриптор имеет длину 256 бит; для каждого из 256 «сэмплов» мы при помощи псевдослучайной таблицы поиска выбираем две точки сэмплирования внутри площади участка и кодируем следующий бит, как 0 или 1 в зависимости от относительных значений пикселей.

Сравнение ключевых точек становится тривиальной задачей, достаточно просто выполнить XOR двух битовых строк и посчитать биты.

Так как ключевые точки не зависят от поворота и условий освещения, можно использовать их для распознавания объектов в различных сценариях.

Последним дополнением этого алгоритма станет многократное изменение размера/масштаба изображения и распознавание ключевых точек в разных масштабах. Благодаря этому можно распознавать объекты, которые ближе или дальше от камеры, повёрнуты на любой угол или частично скрыты.

LBP-каскады

Ключевые точки и дескрипторы отлично подходят для распознавания произвольных объектов, но иногда нам нужен более специализированное решение для определённых типов объектов, например, лиц, транспорта или жестов. Тут нам приходят на помощь каскадные классификаторы, применяемые, например, в методе Виолы — Джонса.

Вместо сложных признаков Хаара, применяемых в алгоритме Виолы — Джонса, можно использовать нечто более простое: локальные бинарные шаблоны (Local Binary Patterns, LBP). LBP — это мощный дескриптор текстур. Он исследует 8 соседей каждого пикселя, и если сосед ярче центрального пикселя, записывает 1, а в противном случае 0. Так мы получаем 8-битное число, описывающее локальную текстуру.

«Каскад» — это последовательность простых классификаторов, или «этапов». На каждом из этапов исследуется окно изображения и применяется несколько признаков LBP для определения того, может ли это окно содержать интересующий объект (например, лицо).

• Если окно не проходит проверку на любом из этапов, оно немедленно отбрасывается. Это очень быстрый процесс.

• Окно классифицируется, как положительное распознавание, только если оно прошло все этапы.

Такая структура позволяет классификатору быстро отбрасывать подавляющую часть площади изображения и сосредоточить вычислительные ресурсы только на областях с высоким потенциалом. Перемещая это окно распознавания по всему изображению (и во множестве разных масштабов), можно находить объекты конкретного заранее обученного класса. В Grayskull есть предварительно обученный детектор лиц анфас, использующий именно эту методику.

Выше показан результат работы LBP-каскадного классификатора, успешно распознавшего лицо сэра Гэри Олдмена во всём разнообразии его ролей. Слева выбрано минимальное количество соседей, равное 4, а справа — 14. Благодаря этому слева распознаётся больше лиц, но и возникает больше ложноположительных срабатываний, а справа выполняется более консервативное распознавание, обнаруживающее только полностью видимые лица анфас.

Заключение

Мы проделали путь от скромного пикселя до сложного распознавания объектов, использовав для всего этого лишь простые структуры C и фундаментальные алгоритмы. Мы попробовали манипулировать пикселями, применять фильтры для обработки изображений, сегментировать объекты при помощи thresholding и подчищать их. Также мы научились находить и анализировать blob, распознавать устойчивые ключевые точки при помощи FAST и ORB, и, наконец, использовали LBP-каскады для распознавания специализированных объектов.

В этом и заключается фундаментальная философия Grayskull: срывание покрова таинственности с компьютерного зрения созданием минимального, свободного от зависимостей и понятного набора инструментов. Она доказывает, что для получения приемлемых результатов не всегда нужны тяжеловесные библиотеки или фреймворки глубокого обучения, особенно в системах с ограниченными ресурсами.

По сути, изображения — это просто прямоугольники из чисел, поэтому благодаря основам знаний алгоритмов можно научить компьютер видеть их. Как всегда, я рекомендую вам изучить репозиторий, экспериментировать с кодом и, может быть, даже попробовать собрать собственный простой проект CV!