Приложение 4 Алгоритм распознавания окружностей со случайным поиском для робототехнической системы

Одними из основных для СТЗ мобильных роботов являются проблемы распозна­вания образов предметов и ориентиров, которые позволяют решать не только техно­логические задачи (распознавание предметов определенной формы для манипуляции с ними), но и проблемы навигации MP (распознавание искусственных ориентиров определенной формы для определения местоположения робота).

В данном разделе представлены теория, описание и экспериментальные результа­ты применения алгоритма обнаружения окружностей со случайным поиском. Алго­ритм однозначно обнаруживает окружности и дуги окружностей в цифровых изо­бражениях и дает хорошие результаты для изображений с шумом, а также для слож­ных ситуаций: пересечение, наложение и разрывы в контурах окружностей [97].

Преобразование Хоуга(Hough transform) [273] - наиболее известный подход для распознавания простых примитивов на изображении, в том числе и окружностей. Отличительной особенностью этого похода является отображение пикселей изобра­жения в пространство параметров искомого примитива. Для этого в дискретном про­странстве параметров примитива создается суммирующий массив, и отображение каждого пикселя изображения в пространство параметров приводит к увеличению на единицу значений определенного количества ячеек суммирующего массива.

• Окружность, как кривая, описывается следующими параметрами - координа­той ее центра (а, Ь) и ее радиусом г. Поэтому суммирующий массив для такого 3-х мерного пространства параметров требует значительного объема машинной памяти.

• Требуются значительные вычислительные ресурсы для выбора ячеек с наибольшими значениями в большом суммирующем массиве.

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

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

1. Алгоритм обнаружения окружностей со случайным поиском

Метод, развиваемый в данном разделе, основан на алгоритме обнаружения окружностей со случайным поиском [226]. Данный метод не требует создания суммирующего массива для учета возможных параметров искомых окружно­стей, что приводит к значительному уменьшению требований к объему машин­ной памяти и повышению его производительности. Он эффективно обнаружи­вает окружности при небольшом или умеренном уровне шума в изображении, а также в большинстве сложных случаев при пересечении или перекрытии ок­ружностей. Метод позволяет также обнаруживать объекты с прерывистым кон­туром в виде окружности.

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

Обозначим множество контурных пикселей как V, куда поместим все единич­ные пиксели из контурного изображения. При реализации алгоритма множество пикселей Vдолжно позволять выполнять эффективную произвольную выборку и последовательный перебор своих элементов. В дальнейшем все операции алгорит­ма будут выполняться над этим множеством, а не самим изображением.

Рис. 1. Определение возможной окружности по четырем пикселям

Алгоритм обнаружения окружностей со случайным поиском основан на сле­дующей идее. Известно, что через любые три произвольно выбранные пикселя изо­бражения, не лежащие на одной линии, можно провести окружность (рис.1). Таким образом, параметры окружности {a,b,r)могут быть вычислены по координатам этих трех пикселей. Если после этого мы случайно выберем четвертый пиксель контура изображения, и он будет также лежать на окружности с параметрами {a,b,r),то мы получим первое доказательство, что такая окружность действитель­но существует — на ней лежит четыре случайно выбранных пикселя.

Используя данную идею выберем случайно четыре контурных пикселя из множества V. При этом выбранные пиксели удаляются из К и помещаются во временное множество пикселей окружности V_cir.Выясним, лежат ли выбран­ные пиксели на одной окружности. Три из четырех пикселей (которые назовем опорные пиксели) используются для вычисления параметров возможной окруж­ности - координат центра и радиуса {a,b,r). Для оставшегося пикселя проверя­ем условие - находится ли он на окружности с вычисленными параметрами.

Уравнение окружности записывается как

Раскрыв уравнение (1) получим уравнение

пиксели 1, 2, 3 на рис.1), не лежащие на одной прямой, может однозначно за­дать окружность в плоскости изображения.

Решая эти уравнения относительнополучим параметры

возможной окружности. Эта система уравнений в матричной форме имеет вид

Чтобы опорные пиксели могли задать окружность они не должны лежать на одной прямой. Это условие записывается как

Координаты пикселей на изображении принимают дискретные значения, что приводит к некоторой погрешности вычисления параметров окружности. Если опорные пиксели находятся слишком близко друг к другу, то увеличивается ошибка при вычислении координат центра окружности, а система (3) может стать плохо определенной. Для минимизации указанных негативных эффектов необходимо следить, чтобы любые два опорных пикселя не лежали слишком близко друг от друга. Для этого вводится дополнительное условие на располо­жение опорных пикселей - расстояние между любыми двумя опорными пиксе­лями должно быть большее некоторого значения T_p.

Согласно алгоритму, последний из четырех случайно выбранных пикселей V4=(x4,y4)должен также лежать на окружности сформированной опорными пикселями v_i, V₂, V₃. Учитывая дискретность координат пикселей, введем усло­вие соответствия их координат уравнению окружности. Расстояние между ду-

гой окружности, заданной опорными пикселями 1, 2, 3, и произвольным пиксе­лем v_iрассчитывается как

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

где T_d- некоторое малое расстояние, заданное в пикселях.

Если расстояние, полученное в уравнении (5) для пикселяудовлетворяет условию (6) (см. рис.1), то констатируем, что все четыре случайно выбранных пикселя изображения лежат на одной окружности. Этот факт является первым доказательством того, что окружность с параметрамивозможно

присутствует на изображении.

Если условие (6) не выполняется, тогда мы возвращаем четыре пикселя из множества V_cirназад во множество Vи снова повторяем шаг случайного поис­ка возможной окружности. В процессе поиска окружностей будем подсчиты­вать число неудачных попыток обнаружить окружность. Подсчет неудачных попыток позволит избежать зацикливания алгоритма в случае отсутствия ок­ружностей на изображении.

413

тура). В общем случае число пикселей в окружности будет пропорционально величине 4τrri₂37j. Для контура малой толщины (T_d= 0,5...0,7), число пиксе­лей окружности на изображении будет пропорционально только ее радиусу, а именно: 2τrr₁₂3. Для того, чтобы алгоритм мог обнаружить неполные окружно­сти (перекрытые другими объектами) и прерывистые окружности, составлен­ные из участков дуги, число пикселей в окружности может быть меньшим, чем 2tγλj₂3∙Таким образом, возможная окружность является действительной, если для множества ее пикселей выполняется следующее условие.

где- размер множества V_cir, T_r- является относительным коэффициен­том, значение которого меньше единицы.

Если условие (7) выполняется, тогда мы утверждаем, что обнаружили дейст­вительную окружность с параметрамиI. Обнаруженная окруж­

ность сохраняется в списке найденных окружностей и начинается новая итера­ция алгоритма. При этом пиксели из временного множества V_cirудаляются. Благодаря этому размер массива V уменьшается на следующих итерациях, что ускоряет поиск и обнаружение новых окружностей по данному алгоритму.

Если условие (7) не выполняется, тогда мы утверждаем, что возможная окруж­ность таковой не является. В этом случае мы регистрируем неудачную попытку об­наружения, увеличив счетчик неудачных попыток, и возвращаем все пиксели из множества V_cirво множество Vи начинаем новую итерацию алгоритма.

Максимальное число неудачных попыток Ay_maxограничивает число итераций алгоритма. Другим условием остановки алгоритма является уменьшение размера множества контурных пикселей ниже некоторого минимального размера