Система нахождения графических примитивов на изображении на основе преобразования Хафа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?куляра опущенного на прямую из начала координат;
(x,y) - координаты точки на прямой;
? - угол между перпендикуляром к прямой и осью OX (см. Рисунок 7).
Рисунок 7 - Параметрическое представление прямой
Значение ? изменяется в пределах от 0 до 2?, R ограничено размерами входного изображения. Таким образом, функция, задающая семейство прямых, имеет вид:
(7)
Через каждую точку (x,y) изображения можно провести несколько прямых с разными значениями R и ? (см. Рисунок 8), т. е. каждой точке (x,y) изображения соответствует набор точек в фазовом пространстве (R,?), образующий синусоиду (см. Рисунок 9). В свою очередь каждой точке пространства (R,?) соответствует набор точек (x,y) на изображении, образующий прямую [9].
Рисунок 8 - Задание семейства кривых на плоскостиРисунок 9 - Фазовое пространство для семейства прямых, изображенных на рисунке 8
Каждой точке (R0,?0) пространства (R,?) можно поставить в соответствие счетчик, соответствующий количеству точек (x,y), лежащих на прямой:
(8)
Ввиду дискретности машинного представления входных данных, требуется перевести непрерывное фазовое пространство в дискретное пространство. Введем сетку на пространстве (R,?), одной ячейке которой соответствует набор прямых с близкими значениями R и ?. Теперь счетчик ставится в соответствие каждой ячейке сетки: ячейке [Ri,Ri+1][qi,qi+1] соответствует число точек, удовлетворяющих уравнению:
, (9)
где .
Размер ячеек выбирается с учетом следующих соображений. Если ячейки будут очень большими, то за "прямую" может приниматься разрозненный набор точек. Если же наоборот, ячейки будут слишком малы, есть вероятность, что ни одной прямой не найдется - все счетчики будут иметь небольшое значение.
В общем случае алгоритм поиска прямой на изображении при помощи преобразования Хафа выглядит так:
а)Обнулить счетчики всех ячеек.
б)Для каждой точки интереса.
в)Для каждой прямой, проходящей через данную точку.
г)Увеличить соответствующий счетчик.
д)Выбрать ячейку с максимальным значением счетчика.
е)Параметры прямой, проходящей через максимальное число точек принять равным координатам центра выбранной ячейки в фазовом пространстве.
Если прямых нужно найти несколько, можно отсортировать счетчики по убыванию или рассматривать точки локальных максимумов фазового пространства. На рисунке 10 изображены примеры исходных изображений и соответствующих им фазовых пространств.
графический примитив программный пользователь
Рисунок 10 - Пример работы преобразования Хафа: а) исходные изображения, б) фазовое пространство (R, ?). Величина счетчика в каждой точке фазового пространства обозначена оттенком серого (чем больше счетчик, тем светлее точка)
.3.2 Выделение окружностей на изображении
Геометрическое место точек окружности можно представить в виде формулы:
,(10)
где (a,b) - координаты центра окружности;
(x,y) - координаты точки на окружности;
R - ее радиус.
Формула, задающая семейство окружностей, имеет вид:
(11)
Если ставится задача найти окружность заранее известного радиуса, то фазовым пространством будет плоскость параметров центра окружности (a,b). В таком случае, алгоритм выделения окружностей полностью аналогичен алгоритму нахождения прямых.
Если радиус окружности заранее неизвестен, то пространство параметров будет трехмерным - (a,b,R), что существенно увеличивает вычислительную сложность решения задачи. Для сведения задачи обратно к двумерному фазовому пространству в некоторых случаях можно применить метод описанный в [4].
1.3.3 Нахождение кривых высшего порядка
Методика нахождения кривых высшего порядка (эллипсы, параболы и т.д.) отличается от предыдущих подходов размерностью фазового пространства.
Рассмотрим эту особенность на примере детектирования эллипсов. Уравнение, задающее геометрическое место точек эллипса в полярных координатах, принимает вид:
(12)
где (a,b) - координаты центра эллипса;
(x,y) - координаты точки на эллипсе;
R, ? - полярные координаты эллипса.
Формула, задающая семейство эллипсов, имеет вид:
, (13)
Для нахождения эллипсов необходимо производить операции в четырехмерном фазовом пространстве. Вычисление фазового пространства для кривых высшего порядка представляет весьма трудоемкую вычислительную задачу, поэтому базовое преобразование Хафа для таких примитивов применяется крайне редко.
1.4 Модификации преобразования Хафа
Преобразование Хафа позволяет проводить полный анализ пространства изображения, но существует ряд проблем, которые влияют на результат и производительность такого подхода:
а)Дискретизация
На шаге 1 выбирается сетка дискретизации. В связи с этим выбором возможны следующие проблемы:
1)Сетка выбрана слишком мелкой. Тогда, если в исходном облаке точек присутствовал шум, то даже точки одной кривой будут попадать в разные ячейки сетки, а значит, потенциальный максимум аккумулятора (соответствующий этой кривой) будет размыт и его будет сложнее или вообще невозможно найти.
2)Сетка выбрана слишком крупной. Тогда существует вероятность того, что в одну ячейку попадут точки, лежащие на разных кривых.
)При любой сетке дискретизации, если точки облака образуют кривую с параметром j0, лежащим на границе ячейки, то из-за шума точки этой кривой буд