Теоретические основы дополненной реальности: разбор алгоритмов распознавания объектов и маркеров
Ключевые слова: таргет, оверлей, маркер, ArUco, QR-код, гомография, ключевые точки (features points), SURF, BRIF, ORB, алгоритм k-ближайших соседей (k-NN, Brute Force), венгерский алгоритм.
В модуле рассмотрены теоретические вопросы, посвященные разбору алгоритмов компьютерного зрения, которые используются в дополненной реальности.
План модуля:
разбор библиотеки Numpy и работа с массивами;
распознавание маркеров ArUco;
ключевые точки и дескрипторы;
гомография и наложение виртуальных объектов.
Как выглядит общий пайплайн (технологический процесс) для наложения объектов в виртуальной реальности? Обратим внимание на рисунок 1.
Рис.1 Пайплайн (pipeline) для наложения виртуальных объектов
В первую очередь, необходимо составить некоторую базу таргетов, то есть объектов, на которые будут накладываться виртуальные данные. Второй этап - детектирование таргетов в реальном времени, в видеопотоке, и третье - наложение виртуальных объектов. Рассмотрим каждый из этапов по отдельности.
Что может быть таргетом? Во-первых, в качестве таргета могут выступать объекты реального мира. Во-вторых, QR-коды. Они бывают разных типов, один из которых будет рассмотрен в модуле — ArUco маркеры. В-третьих, маркером может быть изображение (Рис. 2).
Рис. 2 Примеры таргетов
Как выделить маркер в видео-потоке?
Начинается все с процесса обнаружения QR-кода, на примере ArUco маркеров. В данном случае процесс обнаружения может быть представлен так, как это сделано на рисунке 3.
Рис. 3 Процесс нахождения маркера в виде ArUco-маркера в видеопотоке
В первую очередь необходимо перевести изображение в grayscale, убрать каналы rgb и свести все к одному каналу. Второй этап — бинаризация: выделяем из изображения контрастные объекты — черно-белые, являющимися маркерами. Третий этап — выделение контуров, четвертый — выделение из контуров тех, которые походят по форме на квадрат. Таким образом найдутся маркеры. Пятый этап — это приведение изображения маркера к некоторой матрице 8 на 8, в случае если используется ArUco маркеры. Последний, шестой, этап заключается в декодировании маркера для того, чтобы понять, какую информацию он в себе несет.
Для тех, кто ни разу не сталкивался с Qr-кодами или ArUco маркерами, на рисунке 4 представлено небольшое объяснение того, как они работают. Рис.4 Принцип работы ArUco маркераЧерный или белый цвет на маркере представляет собой бит, нуль или единицу. Таким образом, в дальнейшем переведя изображение маркера в матрицу, можно его декодировать и получить какую-то информацию. Как обнаружить таргет, если он представлен изображением (Рис. 5)?
Рис.5. Процесс распознавания маркера - изображения
Предположим, что есть некоторое изображение, которое нужно найти в видеопотоке, и есть некоторый алгоритм, который берет это изображение и представляет его в виде матрицы меньшей по размерности, чем исходное изображение. Эта матрица содержит в себе некоторые признаки, которые в дальнейшем будут определяться в видеопотоке. Причем рассматриваемый алгоритм должен обладать определенным свойством. Если исходное изображение кодируется этим алгоритмом, получается некоторая матрица А, а потом берется изображение с видеопотока, которое искажено, но при этом содержит искомый объект, тогда получается матрица B, которая будет равна матрице А. При этом, если берется какое-то третье изображение (отличное от первого), оно снова кодируется тем же самым алгоритмом, не должно быть такого, что матрица A или матрица B окажутся равными матрице С, закодированной данным алгоритмом (рис. 6). Рис.6 Свойство алгоритма для кодирования изображенияКак составляется такая матрица? Самый простой способ, это выделить признаки из изображения вручную. Например, посчитать количество полосок, цветов или замкнутых контуров, площадь фигур, затем представить это в виде некоторого числового вектора, где будут закодированы все эти признаки. В таком подходе есть несколько проблем. Самый очевидный — высокая трудоемкость, каждый объект описывать долго. Второе, несмотря на все старания, нельзя выделить однозначные признаки. Если изображение находится далеко, то соответственно его площадь будет меньше, чем если это же изображение будет расположено ближе к камере. Так какие же подходы могут использоваться для выделения признаков из изображения, чтобы они всегда были однозначны в независимости от искажения изображения на камере? Есть два подхода (Рис. 7).
Рис. 7 Подходы нахождения признаков искомого изображения в видеопотоке
Первое — выделение ключевых точек, второе — кодирование с помощью нейросети. Рассмотрим подробнее, какой из методов будет лучше применим в той или иной ситуации. Если используется выделение ключевых точек, то кодировка может быть однозначно представлена, то есть при кодировании изображения несколько раз, она будет всегда представляться одним и тем же набором цифр. Тоже самое относится и к кодированию с помощью нейросети. Однако, и в том и в другом случае есть ряд ограничений. Рассмотрим ключевые точки в качестве метода кодирования. В этом случае, если на одном устройстве кодируем, а на другом декодируем, то необходимо, чтобы алгоритм был одинаково настроен. Если же используется нейросеть для кодирования изображения, то будет необходима большая обучающая выборка для того, чтобы обучить кодировщик. Второй параметр, по которому сравниваются данные алгоритмы — это нечувствительность к искажениям. И выделение ключевых точек, и кодирование с помощью нейросети не чувствительны к таким искажением, как поворот изображения, аффинные преобразования или перспективные образования, однако, если изображение сильно масштабировать, то алгоритмы выделения ключевых точек будут проигрывать нейросетям. Третий параметр — скорость. Здесь и первый, и второй метод дают достаточную скорость, но для выделения ключевых точек необходимо правильно выбирать алгоритм для задачи. Одним из алгоритмов, который дает наибольшую производительность является алгоритм ORB. И четвертое — возможность вычисления гомографии. Если есть ключевые точки, то их можно выделить, как на таргете, так и на изображении с видеопотока, а затем сопоставить их для того, чтобы в дальнейшем наложить 3d-объект. В случае с нейросетями такое сделать не получится. Сейчас в технологии дополненной реальности в большинстве случаев используют именно алгоритмы на основе ключевых точек. Рассмотрим эти алгоритмы чуть подробнее. Начнем с определения особых или ключевых точек (features points).Ключевые точки (features points) — некоторый участок картинки, который является отличительным для заданного изображения. Если говорить более точно: особая точка m, или точечная особенность (англ. point feature, key point, feature), изображения – это точка изображения, окрестность которой o(m) можно отличить от окрестности любой другой точки изображения o(n) в некоторой другой окрестности особой точки o2(m).
Рисунок 8. Ключевые точки (features points)
Ключевые точки обладают следующими параметрами. Первый параметр — координаты этой точки на изображении, второй — числовое описание (дескрипторы), задающее кодировку окружения точки. Какие существуют алгоритмы для выделения ключевых точек? Это такие алгоритмы, как: SURF, BRIF, ORB и т.д. В модуле будет рассмотрен алгоритм ORB, так как в сравнении со всеми остальными, он дает наилучшую производительность.Следующий этап после выделения ключевых точек на таргете и ключевых точек на снимке, это, как говорилось ранее, их сопоставление (Рис. 9).
Рис.9 Сопоставление признаков
Как можно сопоставить ключевые точки на двух картинках? Первый вариант — алгоритм ближайших соседей. Выбирается некоторая точка, берутся ее дескрипторы (описания ключевой точки), ищутся похожие дескрипторы на снимке и измеряются расстояния между этими дескрипторами. Таким образом, для каждой точки выбираем дескриптор с наименьшим расстоянием до неё (Рис. 10).
Рис.10 Алгоритм k-ближайших соседей (k-NN, Brute Force)
Рис.12 Венгерский алгоритм
Как добавить оверлей — виртуальный объект в видеопоток камеры (рис.13)?
Рис.13 Виртуальный объект, добавленный в видеопоток камеры при распознавании таргета — оверлей
Для этого познакомимся с понятием гомографии изображения (рис.14).
Рис.14 Гомография изображения
Есть оригинальное изображение, но, при наведении камеры с другого угла, изображение будет искажено (так, как на рисунке 14). Такой вид искажения называется перспективным преобразованием. Если взять некоторую точку на одном изображении и попробовать взять эту же точку на втором изображении, то они будут иметь две разные координаты. Соответственно, при наложении некоторого виртуального объекта, нужно посчитать некоторое преобразование h (матрица гомографии). Обычно она представлена матрицей 3 на 3. Какие бывают искажения в нашей реальности? Это искажение типа зеркало, искажение поворот вокруг оси, аффинное и перспективное преобразование, гомография, когда есть несколько искажений сразу. Определить какое искажение касается конкретного изображения сложно (рис.15).
Рис.15 ИскаженияИтак, пришло время разобраться с размещением оверлея в видеопотоке камеры. Есть некоторый таргет, есть кадр из видеопотока, дескрипторы сопоставлены с помощью венгерского алгоритма или k-NN, информация о сопоставлениях хранится в некоторым объекте matches. На рисунке 16, слева внизу, можно увидеть формулу, описывающую преобразования ключевых точек из одного пространства в другое. Рис.16 Поиск матрицы гомографииСоответственно матрица гомографии обычно находится стохастическими методами, то есть просто перебираются параметры матрицы таким образом, чтобы ключевые точки снимка в конечном итоге были равны ключевым точкам таргета. Однако, важно помнить, что для того, чтобы правильно посчитать матрицу гомографии, необходимо знать, как минимум, четыре ключевых точки и соответствие между ними на двух изображениях. Возьмем виртуальный объект — оверлей, который будет добавлен в видео поток и посчитанную матрицу гомографии. Так, на выходе получится кадр с внедренным в него виртуальным объектом (рис.17).
Рис.17 Оверлей в виде изображения рыбы, внедренный в видеопоток камеры
Тоже самое относится и к наложению оверлеев, выполненных в виде трехмерных объектов. Только вместо того, чтобы домножать матрицу H на матрицу оверлея V, будет умножаться матрица Н на матрицу V и на матрицу G, определяющую глубину — матрицу 3D объекта координат 3D точек этого объекта. На данном этапе виртуальный объект внедрен в видеопоток и связан с нашим маркером.
Дополнительные источники информации
2. Технологии и алгоритмы для создания дополненной реальности
3. Дополненная реальность и компьютерное зрение
4. Технологии и алгоритмы дополненной реальности (аналог п.2)
Last updated
