Преобразование Хафа для поиска окружностей

Материал из Техническое зрение
Перейти к: навигация, поиск

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

Например, в уже рассмотренной нами задаче поиска окружностей заданного радиуса $R$ мы можем считать, что имеем дело с двухпараметрическим семейством кривых $(x-x_{0})^{2}+(y-y_{0})^{2}=R^{2}$, и производить поиск максимума аккумуляторной функции $A(x,y)$ в пространстве параметров $(x,y)$. Заметим, что пространство параметров в этом случае практически совпадает с исходным $(x,y)$. Поскольку набор центров всех возможных окружностей радиуса $R$, проходящих через заданную точку, образует окружность радиуса $R$ вокруг этой точки, функция отклика в преобразовании Хафа для поиска окружностей известного размера представляет собой окружность такого же размера с центром в голосующей точке. Максимум аккумулятора соответствует положению центра окружности на изображении, как и было показано на рис. 3.

Опишем теперь алгоритм обнаружения окружностей заданного радиуса на полутоновых изображениях, использующий оценку ориентации нормали в голосующих контурных точках. Первым шагом процесса является обнаружение пикселов края, окружающих периметр объекта. Например, может использоваться оператор Собела, дающий оценку амплитуды и направления вектора-градиента. Голосующими контурными точками считаются точки с высоким значением модуля градиента. Для каждого обнаруженного краевого пиксела используется оценка положения и ориентации контура с целью оценки центра кругового объекта радиуса $R$ путем движения на расстояние $R$ от краевого пиксела в направлении нормали к контуру (то есть в направлении вектора-градиента). Если эту операцию повторять для каждого краевого пиксела, будет найдено множество положений предполагаемых точек центра, которое может быть усреднено для определения точного местонахождения центра.



5-2-5.jpg

Принцип обнаружения окружности неизвестного радиуса на полутоновом изображении методом голосования

Если радиус окружности является неизвестным или переменным, необходимо включить $R$ в качестве дополнительной переменной в параметрическое пространство-аккумулятор: тогда процедура поиска пика должна определить радиус, так же как и положение центра путем рассмотрения изменений вдоль третьего измерения параметрического пространства. Если размер обнаруженной окружности нас не интересует и требуется обнаружить только ее центр, то можно обойтись и без увеличения размерности пространства параметров. Пусть для каждого возможного направления на "центр" контурная точка голосует не точкой на расстоянии $R$, а лучом в этом направлении (рис. 5 $\textit{а}$). Таким образом, окажутся задействованы все возможные положения "центра" при любом масштабе объекта, и это позволит искать окружности независимо от их радиуса (рис. 5 $\textit{б}$).


5-2-6.jpg

Принцип обнаружения окружности неизвестного радиуса в бинарном точечном множестве методом голосования

На втором этапе анализа, после обнаружения потенциальных центров окружностей, можно будет повторно обратиться к изображению и уточнить радиус окружностей с центрами в найденных точках. Запомним эту идею - она нам еще пригодится ниже при описании методов построения вычислительно эффективных процедур анализа свидетельств. Заметим также, что рис. 5 $\textit{а}$ демонстрирует интересную связь описанного современного алгоритма анализа полутоновых изображений с задачей из школьного курса о построении окружности по трем точкам (рис. 3). В самом деле, ведь направление градиента в точке контура контрастной окружности на изображении есть не что иное как предел срединного перпендикуляра к секущей окружности при стремлении длины секущей к нулю. Если бы у нас не было непрерывного контура окружности, а было лишь точечное множество (как в примере на рис. 3), то мы могли бы реализовать голосование пар точек в пользу соответствующих серединных перпендикуляров, и, таким образом, решить задачу выделения окружностей неизвестного размера в бинарном точечном множестве (рис. 6).


В настоящее время разработаны также эффективные модификации преобразования Хафа для выделения эллипсов и других известных видов аналитических кривых.

Полезные ссылки

  1. ☝ К началу
  2. ☜ Преобразование Хафа, его обобщения и модификации
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты