Система нахождения графических примитивов на изображении на основе преобразования Хафа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?т попадать в соседние ячейки и будет наблюдаться размытие пика в аккумуляторе. Это вообще фундаментальная проблема дискретизации.
б)Сложность алгоритма.
Заполнение аккумулятора на шаге 2 является самой трудоемкой частью алгоритма, сложность которой зависит от: размерности фазового пространства и сетки дискретизации. Чем больше размерность фазового пространства и меньше сетка, тем больше ячеек в аккумуляторе. Значит, тем больше требуется памяти и времени для его хранения и заполнения. Именно поэтому на практике чаще всего фазовое пространство представляет собой плоскость, а преобразование Хафа применяется, в основном, для поиска прямых на плоскости (изображениях).
В связи с вышеперечисленными проблемами были разработаны некоторые модификации стандартного алгоритма (Standard Hough Transform, SHT).
Комбинаторное преобразование Хафа (Combinatorial Hough Transform) разрабатывалось для быстрого поиска прямых линий на изображении. В таком случае у нас имеется плоское бинарное изображение (на нем точки интереса одного цвета, а точки фона другого). Поскольку производится поиск прямых линий, то размерность фазового пространства равна 2.
Идея метода состоит в изменении шага 2 (заполнение аккумулятора):
а)Исходное бинарное изображение разбивается на небольшие участки.
б)В каждом участке для каждой пары точек определяются параметры (r,q) прямой, проходящей через них.
в)Если (r,q) попадают в некоторую ячейку, и ее счетчик соответственно увеличивается.
Первый шаг модификации необходим для сокращения числа переборов.
Если точек в участке мало и сетка дискретизации фазового пространства тоже мала, количество записей в аккумуляторе получается меньше.
Иерархическое преобразование Хафа (Hierarchical Hough Transform) -это еще одна модификации для поиска линий на бинарном изображении. Приведем последовательность действий для иерархического преобразования:
а)Исходное изображение разбивается регулярной сеткой.
б)В каждом фрагменте изображения выделяются прямые преобразованием Хафа.
в)Производится иерархическое слияние. На каждом уровне рассматриваются 4 соседних фрагмента. Линии, выделенные на каждом из фрагментов, объединяются на основании преобразования Хафа для объединения фрагментов. Если линии не удалось слиться ни с одной линией из соседних фрагментов, она удаляется из рассмотрения.
г)Слияние производится до получения одного исходного изображения.
В результате сложность алгоритма снижается за счет подразбиения изображения (можно использовать более грубую сетку в фазовом пространстве и количество точек существенно меньше).
Недостаток состоит в том, что одна длинная линия может быть в результате представлена несколькими близкими линиями, поскольку разные концы отрезка могут быть неколлинеарными при близком рассмотрении, т.е. на низких уровнях иерархического слияния.
Адаптивное преобразование Хафа (Adaptive Hough Transform) - эта модификация позволяет использовать меньше места для хранения аккумулятора и быстрее выделять кривые [14]. На протяжении всего процесса поиска используется аккумулятор заранее выбранного маленького размера (например, 99 или 3333 в многомерном случае). Алгоритм выглядит следующим образом:
1)Выбор размера аккумулятора (маленький!).
2)Достижение заданной точности. На каждой итерации размер ячейки уменьшается. Цикл идет до достижения заранее заданного размера ячейки.
)Заполнение аккумулятора. Как и в стандартном варианте, однако меньшая сложность достигается за счет небольшого размера аккумулятора.
)Поиск ячейки с максимальным значением счетчика.
)Ячейка принимается за новое фазовое пространство, переход на шаг 2. Таким образом, мы уменьшаем шаг дискретизации, но только в области интереса (ячейке с максимальным счетчиком).
)Выделяем кривую.
Главными достоинствами адаптивного преобразования Хафа являются:
а)Меньшая сложность по времени и по памяти.
б)Практическое решение проблемы дискретизации, поскольку сетка дискретизации не регулярная и на каждой итерации уточняется.
Основным недостатком алгоритма является следующее. Если исходное облако точек образует несколько кривых из заданного семейства, то для выделения каждой точки необходимо повторить весь алгоритм сначала (предварительно устранив из рассмотрения точки уже выделенных кривых).
Вероятностное преобразование Хафа (Probabilistic Hough Transform) рассматривает только доля a точек из множества X, при этом результат с некоторой вероятностью получается такой же, как и у стандартного алгоритма. Доля точек выбирается случайно с равномерной вероятностью [15].
Показано, что существует athreshold такое, что при a > athreshold ошибок (относительно стандартного алгоритма) происходит очень мало, а при a < athreshold их количество резко возрастает. Поэтому рекомендуется выбирать a примерно равное athreshold, которое находится в диапазоне 5% - 15% от всего количества точек.
Очевидное достоинство модификации заключается в сокращении перебора на шаге 2 адаптивного преобразования Хафа. В качестве недостатка можно отметить недетерминированность результата относительно входных данных.
Прогрессивное вероятностное преобразование Хафа (Progressive Probabilistic Hough Transform) состоит в следующем: пусть имеется облако точек X и большое количество точек образуют искомую кривую [11]. Тогда в соответствующей ячейке фазового пространства значение счетчика будет иметь большое значение. Идея этой модификации заключается в том, чтобы выделять кривые (шаг 4) при д