ДЕТЕКТОРЫ УГЛОВ ИЛИ КАК ПРОИСХОДИТ РАСПОЗНАВАНИЕ МАРКЕРОВ ДОПОЛНЕННОЙ РЕАЛЬНОСТИ

CORNER DETECTORS OR HOW TO IMPLEMENT MARKER DETECTION FOR AUGMENTED REALITY

Bajan Abilmazhinova

сandidate of Physical and Mathematical Sciences, associate professor at the department of Information systems Aktobe Regional State University named after K. Zhubanov,

Kazakhstan, Aktobe

Vladimir Andreyev

magistrant 1 course, Aktobe Regional State University named after K. Zhubanov, Kazakhstan, Aktobe

АННОТАЦИЯ

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

ABSTRACT

The article reviews the concept of augmented reality and emphasizes the principles and specific features of its realization. The article highlights the review of corner detectors, which are frequently used in the detection of markers. The detection of the corner points is one of the way to implement computer vision. The analysis reviews the specific features of each detector type and defines the most optimal detector, i.e. Harris corner detector.

Ключевые слова: дополненная реальность; маркер; компьютерное зрение; детектор.

Keywords: augmented reality; marker; computer vision; detector.

Дополненная реальность представляет собой дополнение реального мира цифровым при помощи компьютерных и мобильных технологий. На сегодняшний день существует большое количество программ и игр, использующих данную технологию.

Технология дополненной реальности используется в различных сферах жизнедеятельности, включая медицину, образование и рекламную отрасль [4].

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

Рисунок 1. Пример маркера дополненной реальности

В ходе обработки маркеров используются алгоритмы выделения особых точек, именуемых также ключевыми точками. В настоящее время существует множество таких алгоритмов, которые называются детекторами углов [1].

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

Углы – это такие точки, которые формируются в результате пересечения двух и более граней. Углы бывают L-, T-, Y-, X- и стреловидно – связные. Каждый детектор по-своему реагируют на каждый из видов углов.

Рисунок 2. Виды углов

Первый детектор, который необходимо рассмотреть – это детектор Моравеца. Данный детектор является самым простым из всех существующих детекторов. Для реализации алгоритма необходимо измерить изменение интенсивности пикселя  посредством смещения небольшого квадратного окна  размерностью 3x3 с центром в на один пиксель в каждом из восьми направлений. Такую операцию следует произвести с каждым пикселем на изображении. Для каждого пикселя изменение интенсивности вычисляется по формуле:

Теперь необходимо определить направление наименьшего изменения интенсивности:

Затем отсекаются все точки, значение  которых меньше заданного порога . Последним шагом является удаление повторяющихся углов.

Основным недостатком данного детектора является возникновение ошибок при наличии большого количества диагональных ребер [2; 7].

Следующим рассмотренным детектором углов является детектор Харриса. Харрис вместе со Стефенсом улучшили алгоритм Моравеца. Они ввели анизотропию по всем направлениям для того, чтобы исследовать изменение яркости по множеству направлений. Здесь также используется окно и его размерность зависит от размера изображения. Формула для вычисления изменения интенсивности принимает вид:

Функция является функцией окна . Если значение , то рассматриваемый пиксель с координатами  находится в пределах окна, если же – то за его пределами. [6]

Запишем формулу в матричном виде:

Для небольшого  получаем следующее:

Для угловых точек характерны большие по модулю собственным значениям матрицы M. Считать собственные значения этой матрицы является достаточно трудоемкой задачей, поэтому Харрис дополнительно ввел меру отклика:

,

где: значение k определяется эмпирически и чаще всего лежит в промежутке от 0.04 до 0.15. Таким образом, значение  является большим и положительным для угловых точек.

После нахождения всех угловых точек происходит их отсечение (отсекаются только те точки, значение  которых меньше заданного порога).

Детектор Харриса инвариантен к поворотам и частично инвариантен к аффинным преобразованиям. Однако, его недостатком можно считать зависимость от масштаба. Для устранения этого недостатка используется мультимасштабный детектор Харриса [3].

Еще одним из известных детекторов углов является детектор FAST. Детектор был предложен Эдвардом Ростеном и Томом Драммондом. Его отличительной особенностью является построение деревьев решений для классификации пикселей.

Вокруг каждого пикселя  на изображении рассматривается окружность, состоящая из 16 пикселей [8].

Рисунок 3. Рассматриваемая окружность пикселя p

Каждый пиксель окружности относительно центрального пикселя может находиться в одном из трех состояний:

где:  – интенсивность окрестного пикселя

 – интенсивность заданного пикселя

 – пороговое значение

Точка P является угловой, если для нее существуют не менее 9 смежных пикселей на окружности, интенсивности которых больше  или меньше .

Изначально алгоритм назывался FAST-12, но после внесения в него некоторых изменений и решения вопроса о повторяемости обнаружения особых точек стал называться FAST-ER. Алгоритм FAST-ER эффективнее, чем FAST, но скорость его выполнения намного меньше [5].

И последний детектор, который можно внести в список самых основных и достаточно популярных – это детектор SUSAN, который был предложен Смитом и Бреди в 1997 году. Данный алгоритм определения угловых точек достаточно прост. Вокруг каждого пикселя  на изображении рассматривается круговая область. Все пиксели, входящие в эту область, делятся на две категории: те, интенсивность которых схожа с интенсивностью пикселя  и на те, интенсивность которых не схожа с интенсивностью пикселя . Если площадь одной области больше другой, то рассматриваемый пиксель  является угловой точкой. Но и в этом алгоритме происходит отсечение угловых точек. Угловые точки будут находиться там, где относительная площадь схожих участков будет меньше заданного порога .

Алгоритм устойчив практически к любому виду углов. Однако, не устойчив к размытию на изображениях [9; 10].

В настоящее время появилось множество новых алгоритмов и каждый из них имеет свои особенности. В статье не были рассмотрены такие детекторы, как CSS, CPDA, детектор Ши-Томаси, детектор Трайковича и многие другие. Однако, рассмотренные детекторы могут справиться практически с любой поставленной задачей. При выборе алгоритма необходимо учесть, что является важным – эффективность или скорость выполнения. На мой взгляд, наиболее оптимальным является детектор Харриса. Он сочетает в себе достаточно высокую скорость выполнения и не менее высокую эффективность.

Список литературы:

1. Дополненная реальность – [Электронный ресурс] – Режим доступа. – URL: https://ru.wikipedia.org/wiki / Дополненная_реальность (Дата обращения 09.02.2016).
2. Corner detection – [Электронный ресурс] – Режим доступа. – URL: https://en.wikipedia.org/wiki/Corner_detection (Дата обращения 09.02.2016).
3. Harris C. and Stephens M. (1988). – “A combined corner and edge detector” (PDF). Proceedings of the 4th Alvey Vision Conference. P. 147–151.
4. Markerless Augmented Reality – [Электронный ресурс] – Режим доступа. – URL: http://www.arlab.com/blog/markerless-augmented-reality/ (Дата обращения 08.02.2016).
5. Moravec H. – “Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover”. Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute, 1980.
6. Philibert M., Kirabo N.B., Arne P., Jouni P. – Harris Corner Detector – [Электронный ресурс] – Режим доступа. – URL: http://www2.it.lut.fi/kurssit/07-08/CT20A6100/seminars/2009-2010/Harris.pdf (Дата обращения 08.02.2016).
7. Rosten E., Porter R., and Drummond T. – “Faster and better: a machine learning approach to corner detection”, 2008.
8. Rosten E. and Drummond T. – “Fusing Points and Lines for High Performance Tracking”, 2005.
9. Smith B. – “SUSAN – A new approach to low level”, 1997.
10. The SUSAN Principle for Feature Detection – [Электронный ресурс] – Режим доступа. – URL: http://users.fmrib.ox.ac.uk/~steve/susan/susan/node2.html (Дата обращения 09.02.2016).