Преобразование Хафа для поиска прямых

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

Классическое преобразование Хафа было первоначально разработано для выделения на бинарном изображении не кругов, а прямых линий. Оно основывается на использовании пространства параметров, в котором и производится поиск прямых. Наиболее распространены следующие параметрические уравнения прямых: $$ Y = kX+b; $$

$$ \begin{gather}\tag{1} \end{gather} $$

$$ X \cos \theta +Y \sin \theta =\rho . $$ Однако поскольку прямые на плоскости характеризуются двумя параметрами, пространство параметров всегда будет иметь размерность два.

Классическое преобразование Хафа использует параметры $( \rho , \theta )$ уравнения (1).

Пусть контурное изображение рассматривается как множество точек $(x,y)$ в исходном пространстве $E=(X,Y)$. Множество прямых, проходящих через каждую точку $( x,y )$, может быть изображено как множество точек $( \rho , \theta )$ в пространстве $\{ \rho , \theta \}$. Функция отображения точки в пространстве Хафа называется "$\textit{функцией отклика}$".

5-2-4.jpg

Процедура голосования преобразования Хафа

Идея преобразования Хафа состоит в том, что для каждой точки пространства параметров суммируется количество голосов, поданных за нее, т. е. число точек исходного пространства, порождающих в пространстве параметров отклики, проходящие через данную точку $( \rho , \theta ) $. Здесь используется тот факт, что любые две синусоиды в пространстве параметров пересекутся в точке $( \rho , \theta )$ только тогда, когда порождающие их точки в исходном пространстве лежат на прямой, описываемой уравнением $X \cos \theta +Y\sin \theta= \rho$ с параметрами $( \rho , \theta )$. Введенная таким образом функция $A( \rho , \theta )$ называется $\textit{аккумуляторной функцией}$, причем абсолютное значение ее в точке $( \rho , \theta )$ равно числу точек контурного препарата, лежащих на соответствующей прямой в исходном пространстве изображения.

В том случае, когда на изображении представлено $m$ прямых, аккумуляторная функция $A(\rho , \theta )$ будет иметь ровно $m$ локальных максимумов в точках, соответствующих имеющимся прямым. Таким образом, для обнаружения прямых на исходном изображении достаточно найти все значительные локальные максимумы аккумуляторной функции. Что очень важно с практической точки зрения, такой алгоритм выделения прямых, в отличие от рассмотренных ранее методов выделения линеаментов, вовсе не опирается на предположение о связности анализируемой линии. Поэтому методы голосования хорошо работают в условиях загораживания или наличия других помех.

Как правило, $A(\rho , \theta )$ вычисляется не для каждой точки пространства параметров, а для каждой "ячейки аккумулятора", т. е. некоторой прямоугольной области, на которые разбивается пространство параметров и размер которых ограничивает точность вычислений половинным значением дискреты разбиения по каждому из параметров.


Инвариантность преобразования Хафа к сдвигу, масштабированию и повороту вытекает непосредственно из определения. Более того, поскольку прямые линии при любых проективных преобразованиях трехмерного пространства всегда переходят только в прямые линии (в вырожденном случае - в точки), преобразование Хафа позволяет обнаруживать линеаменты инвариантно не только к аффинным преобразованиям плоскости, но и к группе проективных преобразований в пространстве. Это дает возможность использовать преобразование Хафа для робастного детектирования трехмерных объектов, контуры которых полностью или частично описываются линеаментами.

Легко убедиться, что в смысле результата преобразование Хафа эквивалентно интегрированию контурного изображения вдоль всех возможных прямых. Это обусловливает его фильтрующие свойства и определяет высокую степень помехозащищенности. Это замечание в полной мере относится и к обобщенному преобразованию Хафа (GHT), которое будет описано в следующем подразделе.

Эффективность преобразования Хафа по сравнению с согласованной фильтрацией, связана с двумя основными факторами.

1.~Удачный выбор параметров. Здесь использован тот факт, что при проективных преобразованиях прямая всегда переходит в прямую. В связи с этим сформировано пространство параметров низкой размерности ($n = 2$).

2.~Однократное использование входной информации. Каждый пиксел изображения опрашивается только один раз. При этом дальнейшие вычисления производятся только для пикселов, несущих полезную информацию (в данном случае - контурных). Отсюда непосредственно следует, что вычислительная эффективность преобразования Хафа тем выше, чем меньше число пикселов, несущих полезную информацию, по сравнению с площадью изображения. Это обусловливает, в частности, преимущественное использование этого метода при анализе контурных препаратов, а также точечных паттернов.

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

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

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