Система нахождения графических примитивов на изображении на основе преобразования Хафа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?оизводные по направлениям OX и OY.
Важную роль при обнаружении контуров играет как модуль вектора, так и его направление. Вычисление градиента изображения состоит в получении величин частных производных для каждой точки. Одним из простейших способов нахождения первых производных в точке состоит в применении перекрестного градиентного оператора Робертса, который представляет собой маски, изображенные на рисунке 2.
Рисунок 2 - Маски оператора Робертса
Реализация масок размерами 22 неудобна, так как у них нет четко выраженного центрального элемента. С этой целью были разработан оператор Превитта, описываемый масками 33 на рисунке 3.
Рисунок 3 - Маски оператора Превитта
Небольшое видоизменение вышеуказанных масок состоит в использовании весового коэффициента для средних элементов. Это увеличенное значение используется для уменьшения эффекта сглаживания за счет придания большего веса средним точкам. Данное видоизменение реализуется при помощи оператора Собела, маски которого изображены на рисунке 4.
Рисунок 4 - Маски оператора Собела
На практике для вычисления дискретных градиентов чаще всего используются операторы Превитта и Собела. Маски оператора Превитта проще реализовать, чем маски оператора Собела, однако у последнего влияние шума угловых элементов несколько меньше, что существенно при работе с производными [7].
Лапласиан
Лапласиан двумерной функции f(x,y) представляет собой производную второго порядка, определяемую выражением:
,(4)
где 2f/x2, 2f/y2- частные производные второго порядка.
Для реализации производной второго порядка в дискретном пространстве изображения применяются маски, изображенные на рисунке 5.
Рисунок 5 - Маски лапласиана
Как правило, лапласиан напрямую не используется для обнаружения контуров, что объясняется следующими причинами. Как производная второго порядка, лапласиан является излишне чувствительным к шуму. Кроме того, использование модуля лапласиана приводит к удвоению контуров, что дает нежелательный эффект. Поэтому лапласиан обычно применяют в сочетании со сглаживанием. При использовании функции сглаживания Гаусса выводится маска лапласиана гауссиана [6].
Детектор Канни
Канни досконально исследовал проблему выделения краев различной формы на полутоновом изображении и предложил три критерия, определяющие эффективность детектора края [8]:
1.Хорошее обнаружение, т. е. минимальная вероятность пропуска реального перепада яркости и минимальная вероятность ложного определения перепада (максимизирование выходного отношения сигнал/шум).
2.Хорошая локализация (пиксели, определенные как пиксели края, должны располагаться насколько возможно ближе к центру истинного края).
.Только один отклик на один край.
Вышеперечисленные критерии были записаны в виде уравнений, которые были решены численно, и был определен путем моделирования вид оптимального (в смысле указанных выше критериев) оператора выделения края определенной формы. На рисунке 6 показана свертка изображения с достаточно большой маской, аппроксимирующей оператор [5].
Рисунок 6 - Маска Канни
1.3 Базовое преобразование Хафа
Идея преобразования Хафа состоит в поиске кривых, которые проходят через достаточное количество точек интереса [4]. Рассмотрим семейство кривых на плоскости, заданное параметрическим уравнением:
,(5)
где F() - некоторая функция;
a1, a2, тАж, an- параметры семейства кривых;
(x,y) - координаты на плоскости.
Параметры семейства кривых образуют фазовое пространство, каждая точка которого (конкретные значения параметров a1, a2, тАж, an) соответствует некоторой кривой. Ввиду дискретности машинного представления и входных данных (изображения), требуется перевести непрерывное фазовое пространство в дискретное пространство. Для этого в фазовом пространстве вводится сетка, разбивающая его на ячейки, каждая из которых соответствует набору кривых с близкими значениями параметров. Каждой ячейке фазового пространства можно поставить в соответствие число (счетчик), указывающее количество точек интереса на изображении, принадлежащих хотя бы одной из кривых, соответствующих данной ячейке. Анализ счетчиков ячеек позволяет найти на изображении кривые, на которых лежит наибольшее количество точек интереса [13].
Базовый алгоритм выделения кривых состоит из следующих шагов:
1.Выбор сетки дискретизации. На этом этапе выбирается шаг дискретизации для каждого параметра кривой. От этого выбора будет зависеть сложность (~ скорость) и эффективность алгоритма.
.Заполнение аккумулятора (матрицы счетчиков). Зачастую это самый долгий шаг алгоритма, поскольку заполнение производится путем полного перебора.
.Анализ аккумулятора (поиск пиков). В матрице аккумулятора ищется счетчик с максимальным значением.
.Выделение кривой. Каждая ячейка аккумулятора есть значение фазового пространства, а значит, она задает некоторую (искомую) кривую. Но поскольку значение на шаге 1 стало дискретным, может потребоваться уточнение кривой каким-либо иным методом по уже найденным точкам кривой.
.Вычитание из аккумулятора. Для точек выделенной кривой считается временный аккумулятор и поточечно вычитается из основного.
.Переход на шаг 3.
1.3.1 Поиск прямых
Прямую на плоскости можно задать следующим образом:
, (6)
где R - длина перпенд