Преобразование Хафа — это метод обнаружения прямых и изогнутых линий на изображениях в оттенках серого или цветных изображениях.
Метод позволяет задать параметры семейства кривых и обеспечивает поиск набора кривых заданного семейства на изображении.
Мы рассмотрим его использование для поиска изображений отрезков прямых и дуг окружностей.
Алгоритм преобразования Хафа использует массив аккумуляторов, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых.
Например, при обнаружении линий, описываемых уравнением y=m*x+b, для каждой линии необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность присутствия прямой y=m*x+b на изображении, где M и B соответствуют дискретным значениям м и б.
Массив A используется в алгоритме Хаффа для проверки каждого пикселя изображения и его окружения.
Определяется, имеет ли данный пиксель выраженный край.
Если он присутствует, то вычисляются параметры искомой кривой, проходящей через данный пиксель.
После того, как параметры линии в данном пикселе оценены, они отбираются для получения соответствующих значений M и B, а значение массива A[M,B] увеличивается.
В некоторых реализациях увеличение осуществляется на единицу, в других на величину мощности фронта в обрабатываемом пикселе.
После обработки всех пикселей производится поиск локальных максимумов в массиве аккумуляторов.
Точки локальных максимумов соответствуют параметрам наиболее вероятных прямых на изображении.
Массив аккумуляторов позволяет определять параметры бесконечно длинных прямых или кривых, но с его помощью невозможно точно определить, где начинаются и заканчиваются отрезки этих линий.
Чтобы получить эту информацию, вы можете создать другую структуру данных PTLIST. Элемент PTLIST[M,B] содержит список координат всех пикселей, которые внесли вклад в значение массива аккумуляторов A[M,B].
Основываясь на содержимом этих списков, вы можете найти сегменты или кривые, присутствующие на изображении.
Сейчас мы рассмотрели общие принципы метода Хафа, но не рассмотрели некоторые важные детали, которые необходимо знать при его реализации в программном обеспечении.
Уравнение линии y=m*x+b не подходит для представления вертикальных линий.
Линии удобнее представлять в виде d=x*cos(f)+y*sin(f), где d — длина перпендикуляра к линии, а f — угол между перпендикуляром и горизонтальной осью.
.
В системе координат изображения оси направлены вдоль строк и столбцов изображения.
Так координата c соответствует x, а координата r соответствует координате (-y), тогда уравнение прямой принимает вид: d=c*cos(f)-r*sin(f).
Индексы массива аккумуляторов A соответствуют дискретным значениям d и f. В серии экспериментов 1976 года О'Горман и Кловс дискретизировали значения d с шагом 3 и значения f с шагом 10. Ниже, в виде процедуры накопления_линий, О'Горман и Приведен алгоритм Кловса для заполнения массива аккумуляторов A и массива списков PTLIST. Алгоритм работает в двумерном координатном пространстве.
Функции row_gradient и columns_gradiet обрабатывают окрестности пикселей для оценки компонентов градиента в направлениях строк и столбцов.
Функция градиента объединяет эти два компонента для получения значения градиента.
Функция atan2 возвращает, учитывая компоненты градиента, угол в соответствующем квадранте.
Процедура аккумулирования_лайнов представляет собой версию преобразования Хафа.
Оригинальный метод Хафа не обеспечивает стандартного метода выбора отрезков линии.
Поэтому была разработана процедура find_lines. Функция Pick_greestest_bin возвращает максимальное значение из массива аккумуляторов, устанавливая параметры DQ и THETAQ в соответствующие дискретные значения d и f. Функция чтения упорядочивает список точек в элементе массива по координатам столбца для f<45 or f> 135 и по координате строки для 45<=f<=135. The D and THETA arrays for pixels are assumed to contain discrete values. Similarly, the GRADIENT array should contain the calculated values of the gradient value. The merge procedure merges the list of points of a neighboring pixel with the list of points for a given pixel. At the same time, the spatial ordering of the points is preserved. The set_to_zero procedure zeroes out an element of the accumulator array so that it is not found again. Finally, the create_segments procedure looks through the final ordered list of points and looks for gaps longer than one pixel in it. It is important to understand that the Hough transform can detect extraneous discontinuities or fictitious lines, such as those formed by a shadow. 
Для обнаружения кругов нам придется добавить к массиву А еще одно измерение, т.к.
стандартное описание круга содержит три параметра: r=r0+d*sin(f) с=c0-d*cos(f) где d — радиус круга, а r и c — вертикальная и горизонтальная координаты центра круга.
Фактически, метод Хафа можно использовать для обнаружения любой кривой, которую можно описать аналитически.
пусть кривая будет представлена как f(x,a)=0, где x — точка изображения, а a — вектор параметров.
Процедура поиска подобных кривых состоит из трех этапов: 1. Инициализируйте массив A нулевыми значениями.
2. Для каждого краевого пикселя x определяется вектор a такой, что f(x,a)=0, и значение соответствующего элемента массива A[a]:=A[a]+1 увеличивается.
3. Локальные максимумы в массиве батарей A соответствуют вероятным кривым f на изображении.
Если вектор a содержит m параметров и каждый из этих параметров принимает M дискретных значений, то временная сложность алгоритма равна O(M^(m-2)).
На самом деле существует множество методов выделения разных линий на изображениях.
Если тема интересна, то могу о них рассказать.
Спасибо за внимание.
Теги: #распознавание образов #алгоритм Хафа #Алгоритмы
-
Эстонский Язык
19 Oct, 24
