О дополненной реальности(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