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

Классическое преобразование Хафа [188]было первоначально разработано для выделения на бинарном изображении не кругов, а прямых линий. Оно основывается на использовании пространства параметров, в котором и производится поиск прямых. Наиболее распространены следующие параметрические уравнения прямых:

Y = kX+b;

Xcos(q)+Ysin(q) = r. (5.2.1)

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

Классическое преобразование Хафа использует параметры (r,q) уравнения (5.2.1).

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

Идея преобразования Хафа состоит в том, что для каждой точки пространства параметров суммируется количество голосов, поданных за нее, т.е. число точек исходного пространства, порождающих отклики в пространстве параметров, проходящие через данную точку (r,q). Здесь используется тот факт, что любые две синусоиды в пространстве параметров пересекутся в точке (r,q) только тогда, когда порождающие их точки в исходном пространстве лежат на прямой, описываемой уравнением Xcos(q)+Ysin(q) =rс параметрами (r,q). Введенная таким образом функция А(r,q) называетсяаккумуляторной функцией, причем абсолютное значение ее в точке (r,q) равно числу точек контурного препарата, лежащих на соответствующей прямой в исходном пространстве изображения.

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

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

Как правило, A(r,q) вычисляется не для каждой точки пространства параметров, а для каждой «ячейки аккумулятора», т.е. некоторой прямоугольной области, на которые разбивается пространство параметров, и размер которых ограничивает точность вычислений половинным значением дискреты разбиения по каждому из параметров.

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

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

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

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

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