Распознавание маркера дополненной реальности


    О дополненной реальности(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
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 37

      +3
      Мне казалось, что здесь должны были использоваться Harr-вейвлеты, а оно вон значит как.
      Спасибо, познавательно. Как раз хотел когда-нибудь разобраться в этом вопросе :)
        +2
        А как вы хотели тут применять Haar-вейвлеты?..
          0
          Наверное имелись в виду каскады Хаара (Виолы, Джонс), а не вейвлеты, это разные вещи. Каскады бы здорово ускорили детектирование, но их обучение мучительно и долго (2-3 дня на топовом Xeon).
        +2
        Оффтоп: странно, но не могу поставить плюс посту, хотя раньше всё ставилось.
          +5
          Чтобы проголосовать за пост, карма теперь должна быть ≥10.
          +3
          Светлота...?
            0
            Lighting. Посмотрел в GIMP — они перевели как «светлота». Еще можно как «освещенность». Не знаю какой термин более уместный. Выбрал «светлота» — она ближе пользователям GIMP'а
              +2
              Лучше всё-таки «освещённость» или «интенсивность света»
            0
            Когда мне понадобилось решить эту же задачу, я использовал открытую библиотеку ArUco. Качество и скорость распознования были вполне приемлимы для той задачи (игра с доп. реальностью для iPhone).
              0
              Да, я когда писал статью смотрел в исходники этой библиотеки. На основе OpenCV делаются графические преобразования, а математика как в ARToolkit. Учитывая развитие графических функций OpenCV, она может даже производительнее чем написанные реализации ARtoolkit.
              0
              Спасибо, понравилось. Продолжайте обязательно :-)
              p.s. «например так[рисунок10]» рисунок потерялся, добавьте.
                0
                спасибо, поправил.
                0
                Интересно, а для распознавания автомобильных номеров подойдёт этот метод?
                  0
                  Здесь комбинация методов. И при распознавании номеров, например для определения где на картинке находится табличка с номером, их можно попробовать.
                    +2
                    Да, сам занимаюсь этой темой, вот кстати ссылка на классную статью, которую недавно нашел:
                    citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.6036&rep=rep1&type=pdf
                    +1
                    Хорошая статья. Вот только в реальности кроме поиска и распознавания нужно еще как-то отсеивать ложные срабатывания, и что-то делать с частично закрытыми маркерами — алгоритмы, основанные на замкнутых областях, легко обмануть лишней темной черточкой на изображении, или разрывом, возникшим из-за низкого разрешения камеры. Нужны методы, основанные на интегральных храрктеристиках, а они требуют много времени…
                    Интересно, как алгоритм Дугласа-Пекера выглядит для замкнутых контуров. То, что описано по ссылке, работает только для относительно прямого сегмента, и не очень устойчиво к шуму: если алгоритму предложить три зашумленных отрезка трапеции (короткое основание и две боковых стороны), он начнет с того, что выберет в качестве вершины самую неправильную точку на основании. И больше ее не уберет.
                      +1
                      Да, есть такие проблемы. Но тут идея какая — должна быть почти идеальная ситуация — т.е. хорошо напечатанный маркер без засветов, нормальное освещение.
                      А фильтрация — да, именно потому внутрь квадрата добаляют простой идентификатор, который потом распознают. Как распознают, чтобы быстрее — это тема для отдельной статьи, притом на любителя.
                      В OpenCV есть функция approxPolyDP, которая работает по этому алгоритму. Можно с ней поиграться на разных изображениях.
                      0
                      А Вы не занимались распознованием натуральных изображений в качестве маркеров?
                      Я давно этой темой занимаюсь, и хороших людей в комманду найти не могу =(
                      вот мои результаты
                      Видео уже не новые, да и больше технического плана, сейчас все работает куда лучше 0=)
                      Все делал с нуля (то есть создаю свой фрейворк).
                      Кому интересно — ю ар велкам! =)

                      // да, видео с bmw хоть и красивое, и всеми агенствами пихается как демо — оно фейковое… монтаж, такое системы не существовало, так что поменяйте на что-нибудь хотя бы типа PTAM.
                        0
                        т.е. создание произвольного маркера. Тут проблема в том, что произвольный маркер должен обладать свойствами для «быстрого и надежного» распознавания. Т.е. он должен быть контрастным, и т.д. Отдельная песня — разная цветопередача и сегментация. Т.е. получается что для каждого изображения нужно делать свой распознаватель. И пока, то с чем я сталкивался, подсказывает мне что для разных изображений понадобятся разные комбинации простых алгоритмов.

                        А про BMW — жаль что не существовало… Вот тут автор расказывает что у американских военных разрабатывается что-то подобное. graphics.cs.columbia.edu/projects/armar/index.htm Потому я и подумал что не фейк.

                        А вообще — при распознавании всегда заужается область и ограничивается задача. Взять хоть файнридер, хоть распознавание номеров автомобиля…
                          0
                          Нет, свой «распознователь» для каждого изображения конечно не пишется, там просто совсем другие методики! Да и как ты видел, все работает, и примеров больше чем достаточно. Глвное чтобы маркер не был совсем монотонным, а так пофиг, все довольно устойчиво.

                          // насчет бмв, даже достаточно подумать над разумностью такой идеи… если в авторизованном сервис центре чуваку механику надо подскахывать какой винт крутить — нафиг такие механики… это не тот кейс где допреал будет решать
                            0
                            C механикой не все так просто. Уровень квалификации решает. Такие очки позволят снизить «порог» входа в механики. Но согласен, на вскидку — выглядит мутно. Единственное — это может помочь монополизировать сферу ремонта авто. Хочешь открыть мастерскую — купи комплект, в бумаге уже не выдаем. Только так — дорого и удобно. Эдакий макдональдс. Где работают не повара, а рабочие.
                            Плюс человеческий фактор. Наверное тонны пластиковых замочков переломаны молодыми неопытными механиками.

                            0
                            Файн ридер и поиск номеров — другого поля ягоды.
                            Например вы выше говорили о применении методики к поиску номеров… это немного абсурдно.

                            В поиске черно-белого маркера, найти границы, чтобы посчитать гомографию — дальше все тривиально

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

                            // для чб маркеров возможное применение — если только построить классификатор для предварительного сужения области, где будет работать «тяжеловестный» метод поиска контуров, чтобы все ускорить

                            В детекции натуральных маркеров (любых изображений) там ещё другое, там пляшут вокруг ключевых точек, и пытаются придумать/построить максимально инвариантное описание некоего окружения вокрут этих точек, чтобы дальше искать схожее на кадре и предоставленном маркером.
                              0
                              Вроде бы согласен, но вроде бы и не так. Пятно найти — да, согласен. А потом внутри пятна — обесцветить, перевсти в ЧБ, найти угол и т.д. Комбинация маленьких алгоритмов.
                                0
                                Вы про номера? или про поиск пятна чб маркера?
                                0
                                Ключевые точки обычно оказываются паразитными пятнами, всплесками и прочими проявлениями шума. Как и границы. Хотя сшивки панорам работают, причем вообще без подсказок — как они сопоставляют картинки?
                                  0
                                  Нет, ключевая точка — это не шум, это ярковыроженное локальное поведение функции.
                                  Сильный локальный экстремум (как в 90% случаем принимается).

                                  " как они сопоставляют картинки?" — По ключевым точкам =)
                                  а что вы подразумеваете под «подсказками»?
                                    0
                                    Самое ярковыраженное поведение функции — это битый пиксель. Или резкоочерченное пятно на матрице.
                                    «подсказки» — когда вручную «примерно» совмещаешь снимки, а алгоритм оптимизирует это совмещение.
                              0
                              //А Вы не занимались распознованием натуральных изображений в качестве маркеров?
                              //Я давно этой темой занимаюсь, и хороших людей в комманду найти не могу =(

                              Посмотрел видео — да интересно, вроде бы и здорово. Но это проект на свободную часть дня и больше ради удовольствия. А я к сожалению сейчас себе регулярно этого не могу позволить. А было бы интересно.
                                0
                                Печалька =(
                              0
                              и получить в результате еще и угол поворота, используя преобразование Хафа:

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

                              Не распарсил :) Что подразумевалось под «прозрачно, что»?
                                0
                                Преобразование Хафа: Картинка планировалась, но потом оказалось что нужно несколько картинок и еще одна страница беглого объяснения к ним. А двоеточие то осталось. Вот ссылка на хорошую статью об этом методе www.waset.org/journals/waset/v42/v42-9.pdf.

                                Прозрачно = Понятно.
                                0
                                Каюсь, Можно ссылку на статью зачем все это нужно? Спасибо.
                                  0
                                  Вот первая из цикла статей, зачем нужна дополненная реальность: habrahabr.ru/blogs/augmented_reality/118123/
                                    0
                                    Благодарю, как-раз иду в зал играть в настольный теннис, и до последнего буду сопротивляться, и играть за обычным столом, не понимаю зачем это делать перед телевизором… Желание крупных компаний обогатиться засчёт незнания людей о том что им на самом деле нужно уже вызывает неприятное жжение в горле. К сожалению тут происходит именно навязывание и игра на человеческих слабостях а не естественный отбор применения технологий.
                                • UFO just landed and posted this here

                                Only users with full accounts can post comments. Log in, please.