Преобразование Хафа — это метод обнаружения прямых и кривых линий на полутоновых или цветных изображениях. Метод позволяет указать параметры семейства кривых и обеспечивает поиск на изображении множества кривых заданного семейства. Мы рассмотрим его применение для поиска на изображении прямолинейных отрезков и дуг окружностей.
В алгоритме преобразования Хафа используется аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Например, при обнаружении прямых, описываемых уравнением y=m*x+b, для каждой прямой необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность наличия на изображении прямой y=m*x+b, где M и 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. Ниже в виде процедуры accumulate_lines приведён алгоритм О'Гормана и Кловса для заполнения аккумуляторного массива A и массива списков PTLIST.
Алгоритм работает в двумерном координатном пространстве. Функция row_gradient и column_gradiet обрабатывают окрестности пикселов для оценки компонент градиента в направлении строк и столбцов. Функция gradient комбинирует комбинирует две эти компоненты для получения величины градиента. Функция atan2 возвращает по заданным компонентам градиента угол в соответствующем квадранте. Процедура accumulate_lines представляет собой версию преобразования Хафа. Оригинальный метод Хафа не предусматривает стандартного метода выделения отрезков прямых. Поэтому была разработана процедура find_lines. Функция pick_greatest_bin возвращает максимальное значение из аккумуляторного массива, присваивая параметрам DQ и THETAQ соответствующие дискретные значения d и f. Функция reader упорядочивает список точек в элементе массива по координате столбца при f<45 или f>135 и по координате строки при 45<=f<=135. Предполагается, что в массивах D и THETA для пикселов содержатся дискретные значения. Аналогично в массиве GRADIENT должны находиться вычисленные значения величины градиента. Процедура merge объединяет список точек соседнего пиксела со списком точек для данного пиксела. При этом сохраняется пространственное упорядочение точек. Процедура set_to_zero обнуляет элемент аккумуляторного массива, чтобы он не был найден повторно. Наконец, процедура create_segments просматривает окончательный упорядоченный список точек и ищет в нём промежутки длиннее одного пиксела. Важно понимать, что преобразование Хафа может обнаружить посторонние разрывные или фиктивные линии, например образованные тенью.
Для обнаружения окружностей нам придётся добавить в массив A ещё одно измерение, т.к. стандартное описание окружности содержит три параметра:
r=r0+d*sin(f)
c=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)).
На самом деле, существует множество методов выделения различных линий на изображениях. Если тема интересна, то я могу рассказать о них. Спасибо за внимание.
В алгоритме преобразования Хафа используется аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Например, при обнаружении прямых, описываемых уравнением y=m*x+b, для каждой прямой необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность наличия на изображении прямой y=m*x+b, где M и 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. Ниже в виде процедуры accumulate_lines приведён алгоритм О'Гормана и Кловса для заполнения аккумуляторного массива A и массива списков PTLIST.
Алгоритм работает в двумерном координатном пространстве. Функция row_gradient и column_gradiet обрабатывают окрестности пикселов для оценки компонент градиента в направлении строк и столбцов. Функция gradient комбинирует комбинирует две эти компоненты для получения величины градиента. Функция atan2 возвращает по заданным компонентам градиента угол в соответствующем квадранте. Процедура accumulate_lines представляет собой версию преобразования Хафа. Оригинальный метод Хафа не предусматривает стандартного метода выделения отрезков прямых. Поэтому была разработана процедура find_lines. Функция pick_greatest_bin возвращает максимальное значение из аккумуляторного массива, присваивая параметрам DQ и THETAQ соответствующие дискретные значения d и f. Функция reader упорядочивает список точек в элементе массива по координате столбца при f<45 или f>135 и по координате строки при 45<=f<=135. Предполагается, что в массивах D и THETA для пикселов содержатся дискретные значения. Аналогично в массиве GRADIENT должны находиться вычисленные значения величины градиента. Процедура merge объединяет список точек соседнего пиксела со списком точек для данного пиксела. При этом сохраняется пространственное упорядочение точек. Процедура set_to_zero обнуляет элемент аккумуляторного массива, чтобы он не был найден повторно. Наконец, процедура create_segments просматривает окончательный упорядоченный список точек и ищет в нём промежутки длиннее одного пиксела. Важно понимать, что преобразование Хафа может обнаружить посторонние разрывные или фиктивные линии, например образованные тенью.
Для обнаружения окружностей нам придётся добавить в массив A ещё одно измерение, т.к. стандартное описание окружности содержит три параметра:
r=r0+d*sin(f)
c=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)).
На самом деле, существует множество методов выделения различных линий на изображениях. Если тема интересна, то я могу рассказать о них. Спасибо за внимание.
