О дополненной реальности(Augumented reality, AR) написано много статей. На хабре есть целый раздел посвящённый этому направлению. Если коротко, то существуют два принципиальных подхода для создания дополненной реальности: с использованием заранее приготовленного маркера(ещё), который нужно распечатывать и без такого. Оба подхода используя алгоритмы “компьютерного зрения” распознают объекты в кадре и дополняют их.
Данная статья посвящена алгоритмам распознавания при создании дополнительной реальности с заранее приготовленным маркером.

Что может быть маркером?

В теории маркером может быть любая фигура(объект). Но на практике мы ограничены разрешением веб-камеры(телефона), особенностями цветопередачи, освещения и вычислительной мощностью оборудования (все ведь происходит в реальном времени, а потому должно делаться быстро), а потому выбирается обычно черно-белый маркер простой формы. Как правило это прямоугольник или квадрат со вписанным во внутрь идентификатором-образом.
В статье [1] описаны основные типы маркеров, которые могут выглядеть так:

ArToolKit(ATK) marker system.

Institut Graphische Datenverarbeitung (IGD) marker system.

Siemens Corporate Research (SCR) marker system.

Hoffman marker system (HOM) used by SCR and Framatome ANP.


В этой же статье[1] приводится сравнение производительности разных реализаций маркеров и распознавания.

Обобщенный алгоритм распознавания маркера

Вкратце, алгоритм распознавания маркера выглядит так(взято здесь):

a) Приводим в градации серого.
b) Бинаризация изображения(порог).
c) Определление замкнутых областей.
d) Выделяем контуры.
e) Выделяем углы маркера.
f) Преобразуем координаты.

Рассмотрим более подробно что происходит на каждом шаге с иллюстрациями.

Перевод цветного изображения в градации серого

Приведем три алгоритма перевода цветного изображения в градации серого.
1. Светлота(Lightness)
GS = (max(R,G,B) + min(R,G,B))/2
2. Светимость(Luminosity)
GS = 0.21 × R + 0.72 × G + 0.07 × B
3. Среднее(Average)
GS = (R + G + B) / 3
Вот пример, как выглядят эти три способа. Как правило используют “Светимость”.
Исходное изображение:

Светлота:

Светимость:

Среднее:


Бинаризация изображения. Порог

Прозрачно, что для перевода изображения в двухцветное состояние используется определенный порог. Вопрос в том, как и к чему этот порог применять. Самый простой способ — задать порог. Например если у нас 256 цветов, то можем задать порог 128. Если немного усложнить — то можем выбрать порог пользуясь гистограммой цвета. Вообще все методы превращения изображения в ч\б вид можно разделить на шесть больших групп которые перечислены и классифицированы в статье [2].
1) Методы основанные на “форме“ гистограммы.
2) Методы на основе кластеризации.
3) Методы на основе изучения энтропии.
4) Методы основанные на поиске сходства между серым и ч/б изображением.
5) Методы использующие корреляционные зависимости и особенности статистического распределения между пикселами в областях изображения.
6) Методы основанные на локальной адаптации порога для каждого пиксела изо��ражения.

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

Жестко заданный порог:

Адаптивный:

Метод Оцу:


Определение замкнутых областей

Нам необходимо определить замкнутые области на белом фоне. Как правило здесь идет комбинация алгоритмов, но в общем случае — как правило применяют алгоритмы “заливки” белых областей и выделяют замкнутые области.
Вот здесь человек решал похожую задачу и еще. В этом месте возможны вариации. Сначала выделяются контуры, а потом проверяются на замкнутость. Возможно такой подход быстрее.

Вот так:

Или так, сначала выделили контуры, потом проверили на замкнутость:


Выделение контура

Существует несколько подходов к выделению контуров на изображении. Укажу основные найденные [3]:
1)Marr-Hildreth Edge Detector
2)Canny Edge Detector
3)Boolean function based Edge Detector
4)Euclidian distance and Vector Angle based Edge Detector
5)Depth Edge Detection using Multi-Flash Imaging
6)Sobel Edge Detector

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

Канни(нужно поиграться с параметрами алгоритма)

Собел


Выделение углов маркера

Выделив контур, его необходимо сопоставить с нашим маркером. Может быть выделено много разных контуров на изображении, нам необходимо найти что-то «похожее» на четырехугольник.
Для решения этой задачи можно применить алгоритм Дугласа-Пекера(он же алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки, алгоритм разбиения и слияния), позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек.
Например, в openCV есть функция approxPolyDP, которая уже это делает. Если ее результат дополнительно обработать, то получиться вполне подходящий результат.

Таким образом мы получили координаты углов маркера.

Преобразование координат

Теперь у нас есть координаты углов маркера, которые по сути, в идеале являются перпендикулярными, а в реальности расположены под другим углом. Кроме того, и в идеале и в реальности, стороны квадрата являются осями координат. Таким образом, мы можем определить положение «камеры» относительно нашего объекта, и точку отсчета начала координат.
На чем основан метод определения координат можно показать графически так[4]:

Т.е. Идея заключается в том, что при изменении угла с которого смотрит камера, изменяется размер проекции. Например:

Рисунки и базовая информация отсюда. Математика описана здесь[4]:
Зная положение камеры и точки отсчета, мы можем нарисовать проекцию для нашей 3D модели. В данном случае куба.
Как видим, если мы используем квадрат с чистым полем в качестве маркера, то он симметричен, и распознать вращение мы можем только лишь частично. Иногда этого достаточно. Если же нет — то мы можем внести внутрь квадрата дополнительный маркер, он тогда будет выглядеть например так

и получить в результате еще и угол поворота, используя преобразование Хафа

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

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

Продолжение: Как воспользоваться вебкамерой в эмуляторе Android

Использованная литература

1.Xiang Zhang, Stephan Fronz, Nassir Navab. Visual Marker Detection and Decoding in AR Systems: A Comparative Study.
2.Mehmet Sezgin. Survey over image thresholding techniques and quantitative performance evaluation.
3.Ehsan Nadernejad. Edge Detection Techniques: Evaluations and Comparisons.
4.Hirokazu Kato, Mark Billinghurst. Marker Tracking and HMD Calibration for a Video-based Augmented Reality Conferencing System