В этой статье я продолжу тему компьютерного зрения.

См. предыдущие статьи: Простой алгоритм распознавания движений и алгоритм поиска смещения объектов на изображении. Напомню, что написать эти статьи меня сподвигло то, что когда я начал работать над магистерской диссертацией на тему «Анализ пространственной структуры динамических изображений», то столкнулся с проблемой, что очень трудно найти какие-то готовые примеры алгоритмов распознавания образов и движущихся объектов. Везде, и в литературе, и в Интернете одна только голая теория. С тех пор прошло довольно много времени, я успел успешно защитить диссертацию и получить красный диплом, а теперь пишу, чтобы поделиться опытом.

Итак, когда я начинал работать над диссертаций мои знания в области компьютерного зрения были нулевые. С чего же я начал? С самых простых экспериментов над изображениями, которые описаны в вышеназванных статьях. Написал пару примитивных алгоритмов, один из которых показал мне в виде пятен, где находятся движущиеся объекты, а второй находил кусок картинки в большей картинке (работал, естественно, медленно).

А что дальше? Дальше затык. Моя задача состояла в том, чтобы беспилотный летательный аппарат ориентировался по кадрам аэрофотосъемки, либо отслеживал движущийся по дороге автомобиль. И как приступить к задаче я не представлял. Что я стал делать? Читать теорию. А теория говорила, что компьютерное зрение разбивается на следующие этапы:

  1. Предобработка изображения (удаление шума, улучшение контрастности, масштабирование и так далее).
  2. Нахождение деталей (линии, границы, точки интереса)
  3. Детектирование, сегментация.
  4. Высокоуровневая обработка.

Ну ок, нарисовал схему программы, которая все это должна делать:

image

Короче, получилось, что я должен создать нечто грандиозное уровня Искусственного Интеллекта. Ну ок, попытаюсь создать. Беру Visual Studio и начинаю в C# ваять классы. Точнее, заготовки классов. Чуть позже понял, на что я замахнулся….

Итак, начинаю отрабатывать первый шаг. Предобработка. Начал с нее, потому что

  1. Это самое простое.
  2. Это первый шаг из списка.

Стал применять к изображению разные фильтры, смотреть, что получается. Попробовал, например, применить фильтр Собеля:

image

Удалить шумы из изображения методом размытия по гауссу:

image

Изучил медианную фильтрацию и выделение контуров:

image

Во всем этом мне очень помогла лекция о компьютерном зрении с лекториума.

Итак, знаний стало гораздо больше, но все равно непонятно, как решить задачу. К тому времени тема и задача магистерской диссертации несколько раз пересматривалась, и в итоге была сформулирована так: «Отслеживание траектории БЛА по кадрам аэрофотосъемки». То есть мне нужно было взять ряд фотографий и построить по ним траекторию.

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

  • Классическое выделение контуров Canny из библиотеки OpenCV
  • Разработанный моим научным руководителем улучшенный алгоритм выделения контуров.
  • Выделение контуров путем бинаризации.
  • Выделение контуров путем сегментации. Сегментация проводилась различными способами, в частности, с использованием текстурных признаков.

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

Ну а дальше научный руководитель подсказал идею: надо использовать особые точки. И даже дал алгоритм, как эти ключевые точки вычислять. Надо сказать, что это был очень нестандартный метод. Это не детектор Харриса, и не BRISK, и не MSER и не AKAZE. Хотя я и их тоже пытался использовать. Но, как оказалось, предложенный научным руководителем детектор работал лучше. И вот принцип его работы. Сначала вычисляем вот по такой формуле контурный препарат:

image

image

Потом находим экстремумы данной функции. Это и есть особые точки. Что характерно, точки могут быть двух типов «Пики» и «ямы». Вот пример этих точек на изображении:

image

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

image

где k – количество особых точек, участвующих в расчете. Для каждого треугольника вычисляется специальный индекс от 0 до 16383. Следующий шаг – распределение треугольников по специальному массиву, в котором номер ячейки соответствует индексу треугольника. Каждая ячейка такого массива представляет собой список из треугольников. Такой массив составляется по двум сравниваемым кадрам. Сопоставления производиться путем сопоставления каждой ячейкой массива с соответствующей ячейкой массива другого кадра. Всего нужно сопоставить 16384 групп, что является вполне выполнимой задачей для компьютера за достаточно короткий промежуток времени.

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

Таким образом, мы нашли смещение по горизонтали и вертикали, угол и изменение масштаба (то есть поднялся БЛА или опустился). Теперь осталось написать программу, которая моделирует отслеживание траектории по серии кадров и рисует эту самую траектории, и можно сказать, что диссертация готова:

image