Преобразование Хафа

Один из методов распознавания образов. Данное преобразование, позволяет находить объекты на бинаризованном изображении, чаще всего используется для поиска эллипсов, окружностей и прямых.

История

Изначально метод был сформулирован для поиска прямых линий на изображений самим Хафом и запатентован в 1962 [1]. Далее идея метода была популяризована в статье Дуды и Харта "Use of the Hough Transformation to Detect Lines and Curves in Pictures" [2] в 1972 году, используемая терминология данного преобразования пришла из этой статьи. Позже, в 1981 году, данный метод был обобщен (Generalised Hough Transform или GHT) Данной Баллард для поиска различных объектов. Подробнее про история метода можно прочесть в [3].

Алгоритм

Рассмотрим метод Хафа для поиска прямой на бинаризованном изображении. Прямую можно задать через полярные координаты:

ρ = x * cos(θ) + y * sin(θ)

где ρ - радиус вектор от начала координат до прямой, а θ - угол между ρ и осью абсцисс.

Практическое применение

Как упоминалось выше, метод предназначен распознавания образов, на практике, для поиска эллипсов и прямых линий. Пример поиска прямых линий может быть полезным в задачах Optical Character Recognition (OCR), оптического распознавания символов для поиска базовых линий строк текста (как рукописного, так и машинного).

Преимущества и недостатки

Пример реализации

Пример реализации функции построения пространства Хафа на языке Си можно посмотреть в функции ocr_segm_get_hough_image в https://github.com/comrat/ocr-toolkit/blob/master/ocr_segm.c.

Литература

1. Hough, P. Method and means for recognizing complex patterns / P. Hough. — 1962. — https://www.google.c....
2. Duda, R. O. Use of the Hough Transformation to Detect Lines and Curves in Pictures / R. O. Duda, P. E. Hart. — O'Reilly, 1971. — http://www.ai.sri.co....
3. Hart, P. E. How the Hough Transform was Invented / P. E. Hart // IEEE Signal Processing Magazine, Vol 26. — November, 2009. — pp. 18 — 22.