Преобразование Хафа для поиска прямых
Классическое преобразование Хафа было первоначально разработано для выделения на бинарном изображении не кругов, а прямых линий. Оно основывается на использовании пространства параметров, в котором и производится поиск прямых. Наиболее распространены следующие параметрические уравнения прямых: $$ 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{функцией отклика}$".
Процедура голосования преобразования Хафа
Идея преобразования Хафа состоит в том, что для каждой точки пространства параметров суммируется количество голосов, поданных за нее, т. е. число точек исходного пространства, порождающих в пространстве параметров отклики, проходящие через данную точку $( \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.~Однократное использование входной информации. Каждый пиксел изображения опрашивается только один раз. При этом дальнейшие вычисления производятся только для пикселов, несущих полезную информацию (в данном случае - контурных). Отсюда непосредственно следует, что вычислительная эффективность преобразования Хафа тем выше, чем меньше число пикселов, несущих полезную информацию, по сравнению с площадью изображения. Это обусловливает, в частности, преимущественное использование этого метода при анализе контурных препаратов, а также точечных паттернов.
