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


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

Преобразование Хафа — метод по извлечению элементов из изображения, используемый в анализе, обработке изображения и компьютерном видении. Данный метод предназначен для поиска объектов, принадлежащих определённому классу фигур с использованием процедуры голосования. Процедура голосования применяется к пространству параметров, из которого и получаются объекты определённого класса фигур по локальному максимуму в, так называемом, накопительном пространстве (accumulator space), которое строится при вычислении трансформации Хафа.

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

Содержание

Теория

При автоматизированном анализе цифровых изображений очень часто возникает проблема определения простых фигур, таких как прямые, круги или эллипсы. Во многих случаях используется алгоритм детектирования границ в качестве предобработки для получения точек, находящихся на кривой в изображении. Однако, либо из-за зашумлённости изображения, либо из-за несовершенства алгоритма детектирования границ могут появиться «потерянные» точки на кривой, так же как и небольшие отклонения от идеальной формы прямой, круга или эллипса. По этим причинам часто довольно сложно сгруппировать выделенные границы в соответствующий набор прямых, кругов и эллипсов. Назначение преобразования Хафа в том, чтобы разрешить проблему группировки граничных точек путём применения определённой процедуры голосования к набору параметризованных объектов изображения.

В простейшем случае преобразование Хафа является линейным преобразованием для обнаружения прямых. Прямая может быть задана уравнением y = mx + b и может быть вычислена для любой пары точек на изображении (x, y). При преобразовании Хафа главная идея — учесть характеристики прямой не как точек изображения, а в терминах её параметров, то есть m — коэффициента наклона и b — точки пересечения. Основываясь на этом факте прямая y = mx + b может быть представлена в виде точки с координатами (b, m) в пространстве параметров. Однако, есть одна проблема в том, что вертикальные прямые имеют бесконечные значения для параметров m и b[1][2]. Соответственно для удобства вычислений лучше всего представить прямую с помощью других параметров, более известных как r и \theta (тета). Параметр r представляет собой длину радиус-вектора ближайшей к началу координат точки на прямой, а \theta — это угол между этим вектором и осью координат. Таким образом уравнение прямой можно записать так

y = \left(-{\cos\theta\over\sin\theta}\right)x + \left({r\over{\sin\theta}}\right),

что может быть преобразовано в r = x \cos \theta+y\sin \theta.

Поэтому возможно связать с каждой прямой на изображении пару (r,θ) которая является уникальной при условии если \theta \in [0,\pi] и r \in \mathbf{R}, или если \theta \in [0,2\pi] и r \geq 0. Плоскость (r,θ) иногда называется Пространство Хафа для набора прямых 2-мерном случае. Это представление делает трансформацию Хафа концептуально очень близкой к 2-мерному преобразованию Радона (Radon transform).

Бесконечное число прямых может проходить через одну точку плоскости. Если эта точка имеет координаты (x_0,y_0) в изображении, то все прямые, проходящие через неё соответствуют следующему уравнению:

r(\theta) = x_{0}\cdot\cos \theta+y_{0}\cdot\sin \theta

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

Реализация

Алгоритм преобразования Хафа использует массив, называемый аккумулятором, для определения присутствия прямой y = mx + b. Размерность аккумулятора равна количеству неизвестных параметров пространства Хафа. Например, для линейной трансформации нужно использовать двумерный массив, так как имеются два неизвестных параметра: m и b. Два измерения аккумулятора соответствуют квантизированным значениям параметров m и b. Для каждой точки и её соседей алгоритм определяет достаточен ли вес границы в этой точке. Если да, то алгоритм вычисляет параметры прямой и увеличивает значение в ячейке аккумулятора, соответствующей данным параметрам.

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

Пример

Рассмотрим три точки, нарисованные черным цветом.

Hough transform diagram.png

  • Для каждой точки построено некоторое количество прямых, проходящих через эти точки, все имеют разный угол.
  • Для каждой прямой нарисован перпендикуляр, проходящий через начало координат.
  • Для каждого перпендикуляра вычислена длина и угол между осью координат. Результаты сведены в таблицу.
  • Это повторено для каждой точки.
  • Потом построено изображение пространства Хафа.

Hough space plot example.png

Точки где кривые пересекаются дают дистанцию и угол. Они, в свою очередь, определяют прямую, пересекающую проверяемую точку. В показанном изображении кривые пересекаются в пурпурной точке; это соответствует непрерывной прямой на диаграмме, которая проходит через три точки. Следующее — другой пример, показывающий результаты трансформации Хафа на растровом изображении с двумя тонкими прямыми.

Hough-example-result-en.png

Результаты этой трансформации сохраняются в матрице. Значения в ячейках матрицы представляют собой количество кривых проходящих через точку. Максимальное значение в ячейке соответствует более яркой точке изображения. Два ярких пятна — пересечение кривых двух линий. По этим пятнам можно определить угол и дистанцию до прямой во входном изображении.

Ограничения

Преобразование Хафа эффективно только при значительном количестве «попаданий» в соответствующий элемент пространства Хафа, только тогда можно с уверенностью определить фигуру пренебрегая фоновым шумом. Это значит, что размер элемента не должен быть очень маленьким, иначе некоторые значения попадут в соседние элементы, уменьшая видимость нужного элемента.

Также, когда число параметров большое (больше трёх), среднее количество «попаданий» в элемент невелико, и поэтому верный элемент не будет очень сильно отличаться от соседей. Таким образом, алгоритм должен использоваться с большой осторожностью, чтобы не определить что-то кроме прямых и кругов.

И последнее, эффективность алгоритма в большой степени обусловлена качеством входных данных: границы должны быть четко определены. Использование преобразования Хафа на зашумленных изображениях затруднено. Для зашумленных изображений необходим этап предобработки с целью подавления шума. В случае, если изображение повреждено, спекл, как в случае с изображением с радара, преобразование Радона предпочтительнее для определения линий, так как оно имеет хороший эффект шумоподавления при суммировании.

Примечания

Ссылки

См. также



Wikimedia Foundation. 2010.

Смотреть что такое "Преобразование Хафа" в других словарях:

  • Обобщённое преобразование Хафа — (Generalized Hough Transform) предложено D.H. Ballard в 1981 году это модификация преобразования Хафа, использующая принципы сравнения шаблонов (template matching). Эта модификация позволяет использовать преобразование Хафа не только для… …   Википедия

  • Преобразование Радона — интегральное преобразование функции многих переменных, родственное преобразованию Фурье. Впервые введено в работе австрийского математика Иоганна Радона 1917 го года[1]. Важнейшее свойство преобразования Радона обратимость, то есть возможность… …   Википедия

  • Дифракция отражённых электронов — Картина, полученная методом дифракции отражённых электронов (National Institute of Standards and Technology Materials Reliability Division) …   Википедия

  • Shakey — Робот Шеки в Музее компьютерной истории Робот Шеки (англ. Shakey)  первый универсальный мобильный робот, способный рассуждать над своими действиями. Пока другие роботы должны были иметь инструкцию для каждого к …   Википедия

  • Einstein@Home — Платформа BOINC Объём загружаемого ПО 43 147 МБ Объём загружаемых данных задания 6 100 МБ Объём отправляемых данных задания 15 КБ Объём места на диске 120 МБ Используемый объём памяти 80 184 МБ Графический интерфейс да Среднее время расчёта… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.