Обобщенное преобразование Хафа
Обобщенное преобразование Хафа ( GHT ), введенное Даной Х. Баллард в 1981 году, является модификацией преобразования Хафа с использованием принципа сопоставления шаблонов . [1] Преобразование Хафа изначально было разработано для обнаружения аналитически определенных форм (например, линии , круга , эллипса и т. д .). В этих случаях мы знаем форму и стремимся выяснить ее расположение и ориентацию на изображении. Эта модификация позволяет использовать преобразование Хафа для обнаружения произвольного объекта, описанного его моделью.
Задача нахождения объекта (описанного моделью) на изображении может быть решена путем нахождения положения модели на изображении. С помощью обобщенного преобразования Хафа проблема нахождения положения модели преобразуется в проблему нахождения параметра преобразования, отображающего модель в изображение. Зная значение параметра преобразования, можно определить положение модели на изображении.
Первоначальная реализация GHT использовала информацию о краях для определения отображения ориентации точки края на контрольную точку формы. В случае бинарного изображения , где пиксели могут быть черными или белыми, каждый черный пиксель изображения может быть черным пикселем желаемого шаблона, создавая таким образом геометрическое место опорных точек в пространстве Хафа. Каждый пиксель изображения голосует за соответствующие контрольные точки. Максимальные точки пространства Хафа указывают на возможные опорные точки паттерна на изображении. Этот максимум можно найти, сканируя пространство Хафа или решая упрощенную систему уравнений , каждое из которых соответствует черному пикселю. [2]
Мерлин и Фарбер [3] показали, как использовать алгоритм Хафа, когда искомые кривые невозможно описать аналитически. Это был предшественник алгоритма Балларда, который ограничивался перемещением и не учитывал изменения поворота и масштаба . [4]
Алгоритм Мерлина-Фарбера нецелесообразен для данных реального изображения, поскольку в изображении с большим количеством краевых пикселей он обнаруживает много ложных срабатываний из-за повторяющихся расположений пикселей.
Чтобы обобщить алгоритм Хафа на неаналитические кривые, Баллард определяет следующие параметры для обобщенной формы: a={y,s,θ}, где y — исходная точка формы, θ — ее ориентация, а s = (s x , s y ) описывает два ортогональных масштабных коэффициента. Алгоритм может вычислить наилучший набор параметров для заданной формы на основе данных о краевых пикселях. Эти параметры не имеют равного статуса. Исходное положение ссылки y описывается в терминах таблицы шаблонов, называемой таблицей R возможных ориентаций краевых пикселей. Расчет дополнительных параметров s и Затем θ достигается прямым преобразованием этой таблицы. Ключевым обобщением произвольных форм является использование информации о направлении. При любой форме и фиксированной опорной точке на ней вместо параметрической кривой информация, предоставляемая граничными пикселями, сохраняется в виде R-таблицы на этапе преобразования. Для каждой краевой точки на тестовом изображении свойства точки просматриваются в R-таблице, извлекается опорная точка и увеличивается соответствующая ячейка в матрице, называемой матрицей-аккумулятором. Ячейка с максимальным количеством «голосов» в матрице Аккумулятора может быть возможной точкой существования фиксированной привязки объекта на тестовом изображении.
