Первым шагом в разработке приложения дополненной реальности является выбор тега и его последующее распознавание в реальном времени.
Ряд алгоритмов предлагают использовать специально созданные метки, некоторые обучаются на подходящем изображении, но мы решили сосредоточиться на том, что практически всегда есть у каждого под рукой — монетах.
Их выбор в качестве меток привел нас к задаче поиска эллипсов.
Конечно, из-за дисторсии камеры и небольшой цилиндричности монета на изображении не всегда представляет собой точный эллипс, но по форме достаточно близка к этой кривой.
В качестве целевой платформы был выбран современный телефон с процессором ARM. Для аугментации в реальном времени требуется не менее 20 кадров в секунду, поэтому на обработку каждого кадра вы можете потратить не более 50 миллисекунд. 
Итак, задача — найти на изображении эллипсы.
Сначала мы поискали готовые реализации и нашли вот такую: детектор .
Его алгоритм следующий:
- Выделяем контуры детектором Кенни
- Разделим отрезки границы на 2 группы (1, 3 и 2, 4) по направлению градиента, затем каждую еще на две в зависимости от направления выпуклости
- Выбираем три достаточно близких сегмента из разных групп.
- Если это части одного эллипса, то прямые (черные), проведенные через центры хорд (красной и синей), пройдут через центр эллипса.
Для каждой пары соседних отрезков построим две такие прямые и получим центр каждой пары.
Если центры расположены достаточно близко, то мы нашли эллипс:
- Вычислите уравнение эллипса, используя три сегмента.
Вскоре был найден другая работа , детектор которого можно протестировать В сети .
На его основе в итоге был создан приемлемый алгоритм работы, состоящий из следующих ключевых этапов:
Размытие по Гауссу, получение горизонтальных, вертикальных градиентов и градиентов величины с помощью оператора Прюитта.
Этот шаг был описан много раз, но именно его модификация позволила существенно повысить производительность решения.
Сначала мы написали прямо: посчитали коэффициенты с плавающей запятой, обработали по 25 пикселей на каждый пиксель (с матрицей 5х5, так как мы использовали ядро размера 5) — умножили на коэффициенты, сложили и нормализовали.
Затем мы рассчитали оператор Прюитта — здесь для получения значения в каждой точке в одном направлении необходимо обработать 6 пикселей, но из-за общности кода на вычисление вертикали и вертикальных «набежало» 9 (3х3).
горизонтальные градиенты.
В результате этот шаг уже превысил необходимый порог для картинки с разрешением 320х240. Мы переписали размытие с float на uin32_t на 9 (матрица 3х3 — уменьшили ядро до 3) пикселей, а при вычислении оператора Прюитта избавились от общности кода и тоже вычисляли на целых числах.
На более позднем этапе оказалось, что размытие вообще можно не делать, так как при выбранном нами для обработки разрешении оно не оказывает существенного влияния на конечный результат. Вычисление величины оператором Прюитта можно ускорить, используя SIMD-инструкции (для ARM — NEON), но это тоже оказалось не особо необходимо — предыдущих шагов оптимизации было вполне достаточно.
На рисунках ниже показаны величины, вертикальные и горизонтальные градиенты: 
Построение граничных сегментов
В выбранном для реализации алгоритме поиск границ осуществляется авторским методом — методом рисования ребер.Этот шаг в работа описано крайне туманно, после нескольких реализаций мы пришли к следующему:
- выбрать ключевые точки (якоря) – точки с величиной больше пороговой и соседей;
- отсортируйте их по убыванию величины;
- начиная со следующей неиспользуемой точки, соберите отрезок границы следующим образом:
- выбрать одно из четырех направлений (вправо/влево/вверх/вниз), учитывая направление градиента в текущей точке и величину соседей;
- выбираем три точки в заданном направлении и идем к неиспользуемой точке с наибольшей величиной, проверяя на каждом шаге, изменилось ли направление градиента;
- если направление изменилось, анализируем 6 точек (по три соседа с каждой стороны) и снова выбираем неиспользованную точку с большей магнитудой;
- мы остановимся, если больше некуда идти.
Отсеивание несущественных сегментов по принципу Гельмгольца
Фильтрация значимых сегментов хорошо описана в оригинальной статье; для полного понимания можете прочитать статью «Обнаружение края по принципу Гельмгольца» или книга «От гештальт-теории к анализу изображений.Вероятностный подход»
.Приведу только формулы и последовательность действий:
- Гистограмму (H) строим таким образом, что для каждого значения величины вычисляем количество пикселей, величина которых больше или равна заданной;
- вычислить Np, где l – длина отрезка;
- значимость отрезка зависит от наименьшей величины входящих в него точек и его длины.
Подставляем в формулу длину – L и минимальную величину – m. Если NPA меньше 1, то оставляем отрезок, иначе делим его на два в самом слабом месте и повторяем процедуру.
Линеаризация сегментов
- Берем несколько точек из ранее найденного отрезка границы и проверяем, что они лежат примерно на одной прямой.
- Добавляем баллы, пока не уложимся в ошибку
Построение дуг
В оригинальной статье предлагалось строить дуги окружностей, но здесь мы решили строить дуги эллипсов, так как иногда можно сразу получить достаточно большую часть эллипса, и это не оказывает существенного влияния на время вычислений.Для построения находим три и более прямых, расположенных подряд на одном отрезке, причем углы между прямыми должны находиться в определенном диапазоне, а вращение должно быть в одном направлении.
В полученные точки вписываем дугу эллипса методом наименьших квадратов (описан ниже) и проверяем ошибку.
Объединение дуг в эллипсы
Ищем близлежащие подходящие куски эллипса и снова используем метод наименьших квадратов, вычисляя ошибку и отбрасывая кандидатов, превышающих выбранный порог ошибки.
Метод наименьших квадратов
Описано Здесь .Пришлось "прикрутить" библиотеку Эйген вычислить собственные значения матрицы, ну и перевести код с MATLAB на C++ (спасибо Октава ).
Демонстрация детектора
Вот и все действия по поиску эллипса на изображении, далее идет его отслеживание, стабилизация, фильтрация вложенных эллипсов (на 10-рублевой монете их обнаруживается до 3-х).Чтобы добавить реальности, осталось только восстановить положение плоскости и добавить крутые объекты.
Результат можно увидеть здесь - приложение-детектор (внимание: две правые кнопки записывают png в /mnt/sdcard/i).
P.S. В ходе работы мы нашли удобное расширение для Visual Studio, позволяющее просматривать изображение в режиме отладки — Просмотр изображения .
Большое спасибо Майкрософт. Теги: #распознавание образов #обработка изображений
-
Кто Построил Египетские Пирамиды?
19 Oct, 24 -
Интервью С Джеффом «Чизи» Морганом
19 Oct, 24
