[Из песочницы] Детектор эллипсов в реальном времени
Первым шагом при разработке приложения, работающего с дополненной реальностью, является выбор метки с ее последующим распознаванием в реальном времени. Ряд алгоритмов предлагает использовать специально созданные метки, ряд обучается на подходящем изображении, мы же решили остановиться на том, что почти всегда есть у всех под рукой — монетах. Их выбор в качестве меток и привел нас к задаче поиска эллипсов. Конечно, из-за искажений камеры и небольшой цилиндричности монета на изображении не всегда является точно эллипсом, но достаточно близка по форме к этой кривой. В качестве целевой платформы был выбран современный телефон на ARM-процессоре. Для дополнения в реальном времени требуется не меньше 20 кадров в секунду, так что можно тратить не более 50 миллисекунд на обработку каждого кадра.
Итак, задача — найти на изображении эллипсы. Для начала поискали готовые реализации и нашли вот такой детектор. Его алгоритм следующий:
- Выделяем контуры детектором Кэнни
- Разделяем сегменты границ на 2 группы (1, 3 и 2, 4) по направлению градиента, потом каждую еще на две в зависимости от направления выпуклости
- Выбираем три сегмента, лежащих достаточно близко, из разных групп
- Если это части одного эллипса, то прямые (черные), проведенные через центры хорд (красные и синие), будут проходить через центр эллипса. Для каждой пары из соседних сегментам строим две такие прямые и получаем центр для каждой пары. Если центры достаточно близки, то мы нашли эллипс:
- Вычисляем уравнение эллипса по трем сегментам
К сожалению, на практике алгоритм давал очень много рядом лежащих эллипсов, большую ошибку в параметрах найденных эллипсов и много ложноположительных детектов. Вскоре была найдена другая работа, детектор которой можно протестировать online. На основе нее в итоге и был создан приемлемо работающий алгоритм, состоящий из следующих ключевых этапов:
Размытие по Гауссу, получение градиента по горизонтали, вертикали и магнитуды оператором Прюитта
Многократно описанный шаг, но именно его модификация позволила значительно увеличить производительность решения. Вначале написали «в лоб»: посчитали float коэффициенты, для каждого пикселя обработали 25 пикселей (матрицей 5×5, т. к. использовали ядро размером 5) — помножили на коэффициенты, сложили и отнормировали. Потом посчитали оператор Прюитта — тут для получения значения в каждой точке по одному направлению необходимо обработать 6 пикселей, но из-за общности кода для вычисления вертикального и горизонтального градиентов «набежало» 9 (3×3).
В итоге один этот шаг уже превышал требуемый порог при для картинки разрешением 320×240. Переписали размытие с float на uin32_t для 9 (матрицей 3×3 — уменьшили ядро до 3-х) пикселей, а при вычислении оператор Прюитта избавились от общности кода и тоже посчитали на целых числах.
На более позднем этапе выяснилось, что размытие можно не делать вовсе, поскольку при выбранном нами для обработки разрешении существенного влияния на итоговый результат оно не оказываетJ. Расчет магнитуды оператором Прюитта можно ускорить за счет использования SIMD-инструкций (для ARM-ов — NEON), но это тоже оказалось не очень-то и нужно — предыдущих шагов по оптимизации было вполне достаточно.
На рисунках ниже отображены магнитуда, вертикальный и горизонтальный градиенты:
Построение сегментов границ
В выбранном к реализации алгоритме границы ищутся авторским методом — методом рисования ребер (edge drawing). Этот шаг в работе описан крайне туманно, после нескольких реализаций пришли к следующей:
- выбираем ключевые точки (anchors) — точки с магнитудой, большей порога и соседей;
- сортируем их по убыванию магнитуды;
- начиная со следующей неиспользованной точки, собираем сегмент границы следующим образом:
- выбираем одно из четырех направлений (вправо/влево/вверх/вниз), учитывая направление градиента в текущей точке и магнитуды соседей;
- выбираем три точки в данном направлении и идем в неиспользованную точку с наибольшей магнитудой, на каждом шаге проверяя, не поменялось ли направление градиента;
- если направление поменялось, анализируем 6 точек (трех соседей с каждой стороны) и опять выбираем неиспользованную точку с большей магнитудой;
- останавливаемся если больше идти некуда.
Отсев незначимых сегментов по принципу Гельмгольца
Фильтрация значимых сегментов в оригинальной статье описана неплохо, для полного понимания можно почитать статью «Edge Detection by Helmholtz Principle» или книгу «From Gestalt Theory to Image Analysis. A Probabilistic Approach». Приведу только формулы и последовательность действий:
- cтроим гистограмму (H), таким образом, что для каждого значения магнитуды вычисляем количество пикселей, у которых магнитуда больше или равна данной;
- вычисляем Np, где l — длинна сегмента;
- значимость сегмента зависит от наименьшей магнитуды входящих в него точек и длины. Подставляем в формулу длину — L и минимальную магнитуду — m. Если NPA меньше 1 то сегмент оставляем, иначе делим по самой слабой точке на два и повторяем процедуру.
Вот что получаем после фильтрации:
Линеаризация сегментов
- Берем несколько точек из ранее найденного сегмента границ и поверяем, что они лежат примерно на одной прямой
- Добавляем точки, пока укладываемся в погрешность
Построение дуг
В оригинальной статье предлагается строить дуги окружностей, но тут мы решили строить дуги эллипсов, так как иногда можно сразу получить достаточно большую часть эллипса, а существенного влияния на время вычислений это не оказывает. Для построения находим три или более прямые расположенные подряд на одном сегменте, причем углы между прямыми должны находиться в определенном диапазоне, и поворот должен быть в одном направлении. Вписываем в получившиеся точки дугу эллипса при помощи метода наименьших квадратов (описан ниже) и проверяем ошибку.
Объединение дуг в эллипсы
Ищем расположенные рядом подходящие кусочки эллипса и снова используем метод наименьших квадратов, считая ошибку и отбрасывая кандидатов, превосходящих выбранный порог ошибки.
Метод наименьших квадратов
Описан здесь. Пришлось «прикрутить» библиотеку Eigen для расчета собственных значений матрицы, ну и перевести код с MATLAB на C++ (спасибо Octave).
Демонстрация детектора
Вот и все шаги по нахождению эллипса на изображении, дальше идет его трекинг, стабилизация, фильтрация вложенных эллипсов (на монетке достоинством в 10 рублей их детектируется до 3-х штук). Для дополнения реальности остается лишь восстановить положение плоскости и добавить прикольные объекты.
Результат можно посмотреть здесь — приложение с детектором (осторожно: две правые кнопки пишут png на /mnt/sdcard/i).
P.S. В процессе работы было найдено удобное расширение к Visual Studio, которое позволяет просматривать изображение в debug режиме — Image Watch. Большое спасибо Microsoft.
