Преобразование Хафа для поиска прямых
Классическое преобразование Хафа [188]было первоначально разработано для выделения на бинарном изображении не кругов, а прямых линий. Оно основывается на использовании пространства параметров, в котором и производится поиск прямых. Наиболее распространены следующие параметрические уравнения прямых:
Y = kX+b;
Xcos(q)+Ysin(q) = r. (5.2.1)
однако, поскольку прямые на плоскости характеризуются двумя параметрами, пространство параметров всегда будет иметь размерность два.
Классическое преобразование Хафа использует параметры (r,q) уравнения (5.2.1).
Пусть контурное изображение рассматривается как множество точек (x,y) в исходном пространстве Е=(X,Y). Множество прямых, проходящих через каждую точку (x,y) может быть изображено как множество точек (r,q) в пространстве {r,q}. Функция отображения точки в пространстве Хафа называется "функцией отклика".
Идея преобразования Хафа состоит в том, что для каждой точки пространства параметров суммируется количество голосов, поданных за нее, т.е. число точек исходного пространства, порождающих отклики в пространстве параметров, проходящие через данную точку (r,q). Здесь используется тот факт, что любые две синусоиды в пространстве параметров пересекутся в точке (r,q) только тогда, когда порождающие их точки в исходном пространстве лежат на прямой, описываемой уравнением Xcos(q)+Ysin(q) =rс параметрами (r,q). Введенная таким образом функция А(r,q) называетсяаккумуляторной функцией, причем абсолютное значение ее в точке (r,q) равно числу точек контурного препарата, лежащих на соответствующей прямой в исходном пространстве изображения.
В том случае, когда на изображении представлено m прямых, аккумуляторная функция A(r,q) будет иметь ровно m локальных максимумов в точках, соответствующих имеющимся прямым. Таким образом, для обнаружения прямых на исходном изображении достаточно найти все значительные локальные максимумы аккумуляторной функции. Что очень важно с практической точки зрения, такой алгоритм выделения прямых, в отличие от рассмотренных ранее методов выделения линеаментов, вовсе не опирается на предположение о связности анализируемой линии. Поэтому методы голосования хорошо работают в условиях загораживания или наличия других помех.
@Рис. 5.2.4. Процедура голосования преобразования Хафа.
Как правило, A(r,q) вычисляется не для каждой точки пространства параметров, а для каждой «ячейки аккумулятора», т.е. некоторой прямоугольной области, на которые разбивается пространство параметров, и размер которых ограничивает точность вычислений половинным значением дискреты разбиения по каждому из параметров.
Инвариантность преобразования Хафа к сдвигу, масштабированию и повороту вытекает непосредственно из определения. Более того, поскольку прямые линии при любых проективных преобразованиях трехмерного пространства всегда переходят только в прямые линии (в вырожденном случае - в точки), преобразование Хафа позволяет обнаруживать линеаменты инвариантно не только к аффинным преобразованиям плоскости, но и к группе проективных преобразований в пространстве. Это дает возможность использовать преобразование Хафа для робастного детектирования трехмерных объектов, контуры которых полностью или частично описываются линеаментами.
Легко убедиться, что в смысле результата преобразование Хафа эквивалентно интегрированию контурного изображения вдоль всех возможных прямых. Это обусловливает его фильтрующие свойства и определяет высокую степень помехозащищенности. Это замечание в полной мере относится и к обобщенному преобразованию Хафа (GHT), которое будет описано в следующем подразделе.
Эффективность преобразования Хафа, по сравнению с согласованной фильтрацией, связана с двумя основными факторами:
Удачный выбор параметров. Здесь использован тот факт, что при проективных преобразованиях прямая всегда переходит в прямую. В связи с этим сформировано пространство параметров низкой размерности (Dim = 2).
Однократное использование входной информации. Каждый пиксел изображения опрашивается только один раз. При этом дальнейшие вычисления производятся только для пикселов, несущих полезную информацию (в данном случае - контурных). Отсюда непосредственно следует, что вычислительная эффективность преобразования Хафа тем выше, чем меньше число пикселов, несущих полезную информацию, по сравнению с площадью изображения. Это обусловливает, в частности, преимущественное использование этого метода при анализе контурных препаратов, а также точечных паттернов.
- «Обработка изображений и распознавание образов» Визильтер Юрий Валентинович Методическое пособие-2010
- Раздел 2. Распознавание образов. 165
- 1.1. Задачи и приложения машинного зрения. Примеры практических приложений.
- Уровни и методы машинного зрения
- Растровое изображение Изображение как двумерный массив данных
- Алгебраические операции над изображениями
- Физическая природа изображений
- Изображения различных диапазонов длин волн
- Изображения различной физической природы
- Тип пикселя
- Возможности и особенности системыPisoft
- Базовые средства просмотра и анализа изображений и видеопоследовательностей
- Алгебра изображений
- Геометрические преобразования изображений
- Устройства оцифровки и ввода изображений
- Линейки и матрицы, сканеры и камеры
- Геометрия изображения
- Цифровые и аналоговые устройства
- Пространственное разрешение
- Программное обеспечение
- Обработка цветных изображений
- Цветовая модельRgb
- Цветовая модель hsv
- Цветовая модель yuv
- Цветовая сегментация изображения
- Гистограмма и гистограммная обработка изображений
- Профиль вдоль линии и анализ профиля
- Проекция и анализ проекции
- Бинаризация полутоновых изображений
- Сегментация многомодальных изображений
- Выделение и описание областей
- Выделение связных областей на бинарных изображениях
- 1. Отслеживающие алгоритмы на примере алгоритма обхода контура.
- 2. Сканируюющие алгоритмы.
- 1.3. Фильтрация. Выделение объектов при помощи фильтров
- Оконная фильтрация изображений в пространственной области
- Фильтрация бинарных изображений Модель шума «соль и перец»
- Структура оконного фильтра
- Логическая фильтрация помех
- Бинарная медианная фильтрация
- Бинарная ранговая фильтрация
- Взвешенные ранговые фильтры
- Анизотропная фильтрация
- Расширение-сжатие (простая морфология)
- Стирание бахромы
- Нелинейная фильтрация полутоновых изображений
- Ранговая оконная фильтрация
- Минимаксная фильтрация
- Задача выделения объектов интереса
- Бинарные фильтры для выделения объектов
- Метод нормализации фона
- Скользящее среднее в окне
- Гауссовская фильтрация
- Преобразование Фурье. Линейная фильтрация в частотной области
- Преобразование Фурье
- Комплексное представление преобразования Фурье
- Быстрое преобразование Фурье
- Двумерное преобразование Фурье
- Свертка с использованием преобразования Фурье
- Фильтрация изображений в частотной области
- Вейвлет-анализ
- Пирамида изображений
- Вейвлет-преобразование
- Операторы вычисления производных
- Операторы вычисления векторов градиентов
- Операторы Марра и Лапласа
- Постобработка контурного изображения Локализация края
- Утончение контура
- Сегментация полутоновых изображений
- Пороговая и мультипороговая сегментация
- Методы слияния, разбиения и слияния/разбиения областей
- Способы описания выделенных областей
- Текстурные признаки
- 1.6.Морфологические методы анализа сцен (по ю.П. Пытьеву) Методы обнаружения объектов, заданных эталонами
- Согласованная фильтрация.
- Корреляционное обнаружение.
- Морфологический подход ю.П. Пытьева.
- Форма изображения как инвариант преобразований изображений, отвечающих вариациям условий регистрации
- Сравнение изображений по форме
- Выделение отличий изображений по форме
- Обнаружение объекта по его изображению и оценка его координат
- *Морфология на базе кусочно-линейной интерполяции
- Преобразование Хафа для поиска прямых
- *Различные способы параметризации прямых
- Преобразование Хафа для поиска окружностей
- Анализ аккумулятора при поиске геометрических примитивов
- Обобщенное преобразование Хафа
- *Специализированная процедура голосования для поиска эллипсов
- *Рекуррентное преобразование Хафа в скользящем окне
- 1.8.Математическая морфология (по ж. Серра)
- Морфологические операции на бинарных изображениях
- Морфологические операции на полутоновых изображениях
- Морфологическое выделение «черт» и объектов
- Морфологический спектр
- Морфологические скелеты. Непрерывная бинарная морфология Непрерывная бинарная морфология
- Непрерывное гранично-скелетное представление изображения
- Обработка и использование скелета
- *Обобщенные скелетные представления бинарных фигур
- Алгоритмы утончения дискретного бинарного изображения
- *Регуляризация скелетов
- Типы нерегулярностей скелета
- Устранение нерегулярностей
- Регуляризация скелета по Тихонову
- *Селективные морфологии
- 1.9. Анализ движения. Выделение движущихся объектов. Разность кадров. Вычитание фона. Анализ оптических потоков. Слежение за движущимися объектами. Корреляционное слежение.
- Обучение с учителем. Детерминированные методы, основанные на «близости». Линейные решающие правила. Метод построения эталонов. Метод ближайшего соседа. Методkближайших соседей.
- Линейные решающие правила
- Метод построения эталонов
- Методы ближайших соседей
- Параметрические и непараметрические методы
- Дискриминантные и моделирующие методы обучения
- Способность распознавателя к обобщению. Регуляризация.
- Байесовская теория решений. Случай двух классов. Классификаторы, разделяющие функции и поверхности решений. Вероятности ошибок. Разделяющие функции для случая нормальной плотности.
- Дискриминантный анализ. Линейный дискриминант Фишера. Персептронная функция критерия. Линейный дискриминантный анализ (lda,дискриминант Фишера)
- Персептрон Розенблатта
- Анализ свидетельств
- Байесовское объединение свидетельств
- Структурное распознавание
- Автоматизированное конструирование алгоритмов обнаружения объектов на основе преобразований модельных описаний объектов.
- Нейросетевое распознавание
- Нейронные сети ассоциативной памяти. Сети Хопфилда.
- Многослойные персептроны. Оптимизационное обучение. Метод обратного распространения ошибки.
- Многослойные персептроны. Правило Хебба.
- *Связь с байесовским распознаванием
- Сети встречного распространения. Самоорганизующиеся сети.