Векторизация растровых изображений. Метод Хафа

Задача: поиск примитивов в растровом изображении.

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

f(x, y, p) = 0

где

x, y — координаты [граничного] пикселя,

p — набор параметров (вектор, обычно вещественный), с изменением которого получаются разные примитивы.

Алгоритм:

1 Строится ассоциативный массив А (“аккумулятор”), размерность которого равна количеству элементов в p. В начале массив полностью состоит из нулей (или просто пуст).

○ Например, для прямой y = kx + b нужно использовать двумерный массив, так как имеются два неизвестных параметра: p₁ = k и p₂ = b. Два измерения массива А соответствуют различным значениям параметров k и b.

2 Для каждой точки <и её соседей> алгоритм определяет, достаточен ли вес границы в этой точке. Если да, то вычисляются параметры всех возможных примитивов, проходящих через эту точку в заданном направлении (используем направление градиента), и увеличиваются соответствующие этим параметрам значения в ячейках аккумулятора.

3 Среди значений массива А находятся те, которые превосходят некоторый порог. Соответствующие им параметры p определяют искомые примитивы.

Замечания (Босик Босикович)

● С математической точки зрения, множество параметров p может быть бесконечным (например, через одну точку можно провести бесконечно много прямых), поэтому в практической реализации потребуется сделать это множество ограниченным и дискретным.

● Возможно, на третьем шаге перед поиском максимумов придётся сначала сгладить (“размыть”) массив p.

Случай отрезков

Проблемы:

● Может быть очень большой массив А

● Эффективность зависит от того, каким образом задано уравнение примитива, т.е. сколько параметров в векторе р.

● Для одного (x,y) находим множество (a,b)