Итак, задача – найти на изображении эллипсы. Для начала поискали готовые реализации и нашли вот такой детектор. Его алгоритм следующий:
- Выделяем контуры детектором Кэнни
- Разделяем сегменты границ на 2 группы (1, 3 и 2, 4) по направлению градиента, потом каждую еще на две в зависимости от направления выпуклости
- Выбираем три сегмента, лежащих достаточно близко, из разных групп
- Если это части одного эллипса, то прямые (черные), проведенные через центры хорд (красные и синие), будут проходить через центр эллипса. Для каждой пары из соседних сегментам строим две такие прямые и получаем центр для каждой пары. Если центры достаточно близки, то мы нашли эллипс:
- Вычисляем уравнение эллипса по трем сегментам
К сожалению, на практике алгоритм давал очень много рядом лежащих эллипсов, большую ошибку в параметрах найденных эллипсов и много ложноположительных детектов. Вскоре была найдена другая работа, детектор которой можно протестировать online. На основе нее в итоге и был создан приемлемо работающий алгоритм, состоящий из следующих ключевых этапов:
Размытие по Гауссу, получение градиента по горизонтали, вертикали и магнитуды оператором Прюитта
Многократно описанный шаг, но именно его модификация позволила значительно увеличить производительность решения. Вначале написали «в лоб»: посчитали float коэффициенты, для каждого пикселя обработали 25 пикселей (матрицей 5x5, т. к. использовали ядро размером 5) – помножили на коэффициенты, сложили и отнормировали. Потом посчитали оператор Прюитта – тут для получения значения в каждой точке по одному направлению необходимо обработать 6 пикселей, но из-за общности кода для вычисления вертикального и горизонтального градиентов «набежало» 9 (3x3).
В итоге один этот шаг уже превышал требуемый порог при для картинки разрешением 320х240. Переписали размытие с float на uin32_t для 9 (матрицей 3x3 – уменьшили ядро до 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.
Комментарии (24)
schroeder
24.06.2015 23:38Можно по подробней про магнитуды, как вы получили вот эту картинку?
Мне не ясно, как можно посчитать у обычной картинки магнитуду, т.к. она считается у комплексных чисел, насколько мне известно.
Заранее спасибо.dreamzor
25.06.2015 01:45+4Мне кажется, имеется в виду амплитуда градиента, т.е. корень из суммы квадратов градиентов в двух направлениях, как, например, тут: www.mathworks.com/help/images/ref/imgradient.html
iroln
25.06.2015 01:51+1В данном случае магнитуда градиента это просто модуль градиента. Корень квадратный из суммы квадратов векторов направления градиентов по X и Y. Короче, гипотенузу они считают: en.wikipedia.org/wiki/Hypot
Вычисление модуля градиента — это очень распространённая процедура при обработке изображений и детектировании границ.
Для уменьшения шума часто используют гауссово сглаживание. Вот, статья на тему:
habrahabr.ru/post/114489
mikhailm1 Автор
25.06.2015 11:11Уже ответили, действительно неточность, это амплитуда градиента, у нас корень из суммы квадратов.
fcoder
25.06.2015 02:33+4Зубчатое колесо в центре осталось нераспознанным.
Color
25.06.2015 11:02Тоже сразу бросилось в глаза
mikhailm1 Автор
25.06.2015 11:06Вот увеличенная и раскрашенная картинка, видно что в двух верхних секторах всего две прямые, а нам надо три. Внизу часть арки восстановили.
mikhailm1 Автор
25.06.2015 12:42+2проверил на оригинальном детекторе,
он нашел центральную звездочку,
SirWiz
25.06.2015 08:50-1Android 4.4 обязательное требование у приложения на play? Можно понизить?
mikhailm1 Автор
25.06.2015 10:24Понижу до 4.0, только google play медленно обновляется займет несколько часов. Есть еще простенькая игрушка на основе этого детекта, у нее требования с 4.0 и для win phone.
victor1234
25.06.2015 09:38+1Можете сделать сравнение с готовыми реализациями? Например в OpenCV?
mikhailm1 Автор
25.06.2015 10:34+1Если сравнивать с первоисточником то целевых изображениях результат не сильно отличается, в opencv я знаю про findContours, но он работает на бинарных изображениях, так что шансов у него немного, и HoughCircles но это не эллипсы.
victor1234
25.06.2015 10:49Детектор границ Canny работает на чб изображении. Я выделял эллипсы достаточно просто: считал площадь (contourArea) замкнутого контура, описывал вокруг него эллипс (fitEllipse) и сравнивал значение их площадей. Если они близки, значит контур похож на эллипс.
mikhailm1 Автор
25.06.2015 12:49замкнутый контур бывает далеко не всегда, вот
картинка из оригинальной статьи
victor1234
25.06.2015 12:55Есть функция аппроксимации, но в целом да, если контур после ее работы не будет целым, то мой вариант не сработает.
sergehog
25.06.2015 11:39+2Работа отличная, особенно если учесть что все в реал-тайме на мобильном устройстве. Однако есть несколько замечаний и комментов.
>> Для дополнения реальности остается лишь восстановить положение плоскости и…
Для определения плоскости вам одной монетки не хватит. Да и двух может не хватить если смотреть на них под определенными углами. Т.е. три монетки, не на одной линии, (т.е. треугольником) должны быть видны, как минимум.
Линзу вы моделируете? Lens Distortion может быть очень значительный, особенно на недорогих камерафонах.
В вашем случае решается сложная задача — поиск границ эллипсов, а что если упростить и искать целые овальчики :)
В случае с колесами велосипеда конечно не прокатит, а в случае с монетками может и прокатить, они же более-менее однородного цвета.
Вот работа моих коллег, там они используют катибрационный паттерн с нарисованными кружочками чтобы потом калибровать положение камеры.
www.ee.oulu.fi/~jkannala/bmvc.html
Проблема клнечно в том что монетка неизвестного цвета, а значит не понятно что трешхолдить. Но можно конечно и выкрутиться.mikhailm1 Автор
25.06.2015 13:05Плоскость восстанавливается частично, мы не можем восстановить поворот вокруг нормали монеты.
Проблема с поиском овалов — это необходимость удачно бинаризировать изображение.
За статью спасибо, почитаем.
tsvetkovpa
25.06.2015 12:36Не смотрели в сторону преобразования Хафа? en.wikipedia.org/?title=Hough_transform
Им тоже можно эллипсы выделятьmikhailm1 Автор
25.06.2015 13:07+1У нас большие сомнения, что детект преобразования Хафа можно сделать в течении нужного нам временного интервала.
Uranix
Можно про серидины хорд поподробнее? Похоже, что этот способ только для окружностей работает
mikhailm1 Автор
Придумал следующее доказательство: выполним описанные в статье построения для окружности, а потом растянем или сожмем изображение по одной из осей, у нас получился эллипс, прямые по-прежнему проходят через середины хорд и пересекаются в центре.