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

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

История

Изначально метод был сформулирован для поиска прямых линий на изображений самим Хафом и запатентован в 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), оптического распознавания символов для поиска базовых линий строк текста (как рукописного, так и машинного).

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

Данный метод хорошо зарекомендовал себя для поиска параметрически задаваемых объектов, таких как прямые и эллипсы, т.к. по сути метод заключается в том, что искомый объект накладывается на изображение повсюду в поисках совпадений. К недостаткам можно отнести время вычисления, т.к. перебираются все возможные прямые, заданные через ρ и , где ρ пробегает значения от 0 до величины диагонали изображения, а от 0 до , и для каждой пары (ρ, ) нужно построить искомый объект в декартовых координатах, проанализировать и сохранить полученную информацию в виде точки в пространстве Хафа. Для оптимизации метода, часто выбирают определенные границы для ρ, θ и шаги их приращения, исходя из условий задачи. Например, для поиска базовой линии текстовой строки, можно допустить, что в среднем θ будет равным и будет отклоняться не больше чем на 10 градусов. Также время тратится на вычисление значений тригонометрических функций, для получения декартовых координат на изображении, но если здесь также задать фиксированный диапазон значений углов с фиксированным шагом, то можно заранее построить таблицу поиска для и , чтобы в дальнейшем просто использовать вычисленные значения.

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

Пример реализации функции построения пространства Хафа на языке Си можно посмотреть в здесь: https://github.com/comrat/samples/tree/master/hough

Литература

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.