Система нахождения графических примитивов на изображении на основе преобразования Хафа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
остижении счетчиком порогового значения, не заполняя аккумулятор полностью (шаг 2). Для вышеописанной кривой значение соответствующего счетчика довольно быстро наберет пороговое значение.
Алгоритм формулируется следующим образом:
а)Если в облаке нет точек, окончание.
б)Аккумулятор пополняется случайно выбранной точкой из множества X, а точка удаляется из рассмотрения.
в)Если максимальное значение аккумулятора не превосходит порога, топереход на шаг 1.
г)Находится кривая максимальной длины.
Внутри некоторого коридора (определяемого ячейкой с максимальным значением счетчика) производится поиск кривой с максимальной длиной.
д)Все точки найденной кривой удаляются с исходного изображения и аккумулятора.
е)Переход на шаг 1.
Достоинством этого метода так же является то, что он постоянно пополняет результат, т.е. его выполнение можно прекратить при достижении остаточного количества результатов или по истечении некоторого времени.
Случайное преобразование Хафа (Randomized Hough Transform) - эта модификация напоминает комбинаторную преобразованию Хафа [15, 17]. Если параметры j кривой F(j,x)=0 можно однозначно восстановить по K точкам, то алгоритм заполнения аккумулятора формулируется следующим образом (шаг 2):
а)Из облака точек X случайным образом выбирается K точек.
б)По выбранным точкам определяются параметры кривой j.
в)Значение счетчика соответствующей ячейки увеличивается.
Перед поиском следующей кривой необходимо удалить из рассмотрения все точки, ассоциированные с предыдущими кривыми, поскольку алгоритм носит случайный характер.
.5 Нахождение точечных особенностей изображения
Особая точка iены или точечная особенность (point feature) - это такая точка iены, изображение которой можно отличить от изображений всех соседних с ней точек iены.
Для сравнения и описания точек можно использовать ее окрестность. Тогда предыдущее определение уточняется следующим образом. Под точечной особенностью понимается такая точка iены M , лежащая на плоском участке поверхности iены PlaneSegment, изображение окрестности I(PlaneSegment) которой можно отличить от изображений окрестностей всех других точек iены N из некоторой другой окрестности этой точки O(M).
Воспользовавшись последним определением можно дать определение точечной особенности изображения:
Точечная особенность изображения m - это такая точка изображения, окрестность которой o(m) можно отличить от окрестности любой другой точки изображения o(n) в некоторой другой окрестности особой точки.
1.5.1 Детектор Харриса
За последние двадцать лет было создано довольно много различных детекторов точечных особенностей изображений. Чаще всего используется детектор Харриса [12].
Для каждого пикселя (x0, y0) рассчитываем следующую матрицу:
, (14)
где I(x,y) - яркость в точке (x,y);
w(x,y) - весовая функция по окрестности S(x0,y0), в качестве которой обычно берут распределение Гаусса.
У точки, окрестность которой похожа на угол, матрица (14) будет иметь два больших положительных собственных значения. Таким образом, условие похожести точки на угол запишется следующим образом:
,(15)
где l1, l2 - собственные значения матрицы (14).
Теперь остается найти локальные максимумы функции отклика угла F(x,y), которые и будут соответствовать особым точкам.
Чтобы упростить вычисления, Харрис предложил отказаться от подсчета собственных значений матрицы, и вместо них ввел следующую функцию отклика угла:
, (16)
где k - параметр Харриса, его величина обычно лежит в пределах 0,04-0,15 и определяется эмпирически.
Далее с ней проводятся аналогичные действия - поиск локальных максимумов, и введение порогового значения.
1.5.2 Масочный детектор
Данный детектор основан на применении оценочного алгоритма соответствия маске того или иного фрагмента изображения. Для этого могут использоваться маски 33, 55, 77 и т.д. Сравнение с масками большего размера позволяет добиться более точных результатов, но отрицательно сказывается на быстродействии алгоритма. Работа алгоритма заключается в следующем: для каждого пикселя изображения в соответствии с размером маски извлекается фрагмент и сравнивается непосредственно с маской. Особый случай представляет собой проверка пикселей, находящихся на границе изображения. Для этого применяют следующий подход: вокруг изображения прорисовывается мнимый контур, который закрашен фоновым цветом и позволяет корректно детектировать углы на границы изображения.
.6 Сравнительная характеристика алгоритмов детекции
Рассмотренные ранее методики имеют ряд преимуществ и недостатков, что приводит их к определенной "специализации" в области применения. Также следует отметить, что некоторые модификации преобразования Хафа эффективны для нахождения одних видов примитивов, но совершенно не подходят для поиска других. Для нахождения точечных особенностей применяется ряд подходов, в числе которых преобразование Хафа (на основе анализа найденных отрезков), детектор Харриса и масочный детектор. На рисунке 11 изображены результаты применения этих алгоритмов.
абвгРисунок 11 - Нахождение точечных особенностей изображения: а - исходное изображение, б - результат преобразования Хафа, в - результат детектора Харриса, г - результат масочного детектора
Как видно из рисунка 11 лучшие результаты продемонстрировал детектор Х