*Специализированная процедура голосования для поиска эллипсов
Одной из проблем применения методов голосования является резкое увеличение объема вычислений в случае, когда известна только форма искомого объекта, заданного аналитической кривой, но неизвестны ни его размер (масштаб), ни ориентация. Как отмечалось выше, стандартный метод решения задачи поиска таких объектов заключается в использовании дополнительных координат пространства параметров для ориентации и для размера. Очевидно, это ведет к стремительному росту числа ячеек, числа накапливаемых в аккумуляторе свидетельств, а также - времени накопления и поиска пиков в пространстве параметров.
Дэвисом [142] предложена методика решения этой проблемы для случая поиска эллипсов. Эллипс - анизатропная (ориентированная) фигура, и, казалось бы, поиск n возможных ориентаций эллипса требует n листов (слоев, плоскостей) пространства параметров по координате ориентации. Однако можно обойтись одним листом для накопления голосов в пользу всех возможных ориентаций.
Рассмотрим форму функции отклика, которую в пространстве параметров порождает каждая точка границы эллипса, если ориентация его произвольна и неизвестна.
Будем в начале работать в системе координат, связанной с точкой пересечения главных осей эллипса. Тогда уравнение эллипса принимает вид:
x=a cos
y=b sin,
где (x,y) – координата точки на эллипсе; a,b – полуоси эллипса; - угол наклона эллипса относительно осей координат изображений.
Отсюда ориентация нормали описывается условиями
dx/d =-a sin
dy/d = b cos,
и следовательно
dy/dx = a/b ctg.
Таким образом, ориентация нормали к эллипсу в данной точке имеет вид
tg 0=(a/b) tg
Поскольку =0- , где tg=y/x=(b/a)tg и tg=tg(0-) / (1+tg0tg), имеем:
tg=sin2(a2-b2)/2ab
2 =a2cos2+b2 sin2,
откуда следует
4-2(a2+b2)+a2b2 sec2 =0
Для получения функции отклика в голосующей точке границы, поместим теперь в нее начало координат. Обозначим новые координаты через U и V. Получим:
V2=(a2+b2)-U2-a2b2/U2.
К сожалению, эта кривая не симметрична относительно начала координат. В случае эллипса с малым эксцентриситетом, она аппраксимируется эллипсом. В случае очень большого эксцентриситета, она аппроксимируется дугами двух кругов:
=a и =a2/b.
Однако, в общем случае, эта кривая всегда будет не симметрична.
Введем два новых параметра:
c=(a+b)/2;
d=(a-b)/2.
Теперь для малых d наше выражение примет вид:
(U+c+d2/(2c)) 2/d2 +V2 /(4d2 )=1.
Пренебрегая членом d2/(2c),который мало влияет на U, мы увидим, что это уравнение эллипса с полуосями 2d и d соответственно. Это сильно упрощает вычисления, но справедливо только для эллипсов, для которых d0,1c (т.е. a1,2b). Однако если эллипсы невелики, можно потребовать только (a<2b).
Таким образом, универсальная просмотровая таблица для обнаружения эллипса может быть составлена без учета эксцентриситета (если он не слишком велик) и размера эллипса – в общем виде. Такую таблицу достаточно только передвинуть и масшабировать, чтобы получить функцию отклика для любой точки любого эллипса.
Вычислительная сложность этого алгоритма имеет оценку La 62 pcd, где p-число эллипсов, присутствующих на изображении размером N*N пиксел, c и d - параметры эллипсов.
- «Обработка изображений и распознавание образов» Визильтер Юрий Валентинович Методическое пособие-2010
- Раздел 2. Распознавание образов. 165
- 1.1. Задачи и приложения машинного зрения. Примеры практических приложений.
- Уровни и методы машинного зрения
- Растровое изображение Изображение как двумерный массив данных
- Алгебраические операции над изображениями
- Физическая природа изображений
- Изображения различных диапазонов длин волн
- Изображения различной физической природы
- Тип пикселя
- Возможности и особенности системыPisoft
- Базовые средства просмотра и анализа изображений и видеопоследовательностей
- Алгебра изображений
- Геометрические преобразования изображений
- Устройства оцифровки и ввода изображений
- Линейки и матрицы, сканеры и камеры
- Геометрия изображения
- Цифровые и аналоговые устройства
- Пространственное разрешение
- Программное обеспечение
- Обработка цветных изображений
- Цветовая модельRgb
- Цветовая модель hsv
- Цветовая модель yuv
- Цветовая сегментация изображения
- Гистограмма и гистограммная обработка изображений
- Профиль вдоль линии и анализ профиля
- Проекция и анализ проекции
- Бинаризация полутоновых изображений
- Сегментация многомодальных изображений
- Выделение и описание областей
- Выделение связных областей на бинарных изображениях
- 1. Отслеживающие алгоритмы на примере алгоритма обхода контура.
- 2. Сканируюющие алгоритмы.
- 1.3. Фильтрация. Выделение объектов при помощи фильтров
- Оконная фильтрация изображений в пространственной области
- Фильтрация бинарных изображений Модель шума «соль и перец»
- Структура оконного фильтра
- Логическая фильтрация помех
- Бинарная медианная фильтрация
- Бинарная ранговая фильтрация
- Взвешенные ранговые фильтры
- Анизотропная фильтрация
- Расширение-сжатие (простая морфология)
- Стирание бахромы
- Нелинейная фильтрация полутоновых изображений
- Ранговая оконная фильтрация
- Минимаксная фильтрация
- Задача выделения объектов интереса
- Бинарные фильтры для выделения объектов
- Метод нормализации фона
- Скользящее среднее в окне
- Гауссовская фильтрация
- Преобразование Фурье. Линейная фильтрация в частотной области
- Преобразование Фурье
- Комплексное представление преобразования Фурье
- Быстрое преобразование Фурье
- Двумерное преобразование Фурье
- Свертка с использованием преобразования Фурье
- Фильтрация изображений в частотной области
- Вейвлет-анализ
- Пирамида изображений
- Вейвлет-преобразование
- Операторы вычисления производных
- Операторы вычисления векторов градиентов
- Операторы Марра и Лапласа
- Постобработка контурного изображения Локализация края
- Утончение контура
- Сегментация полутоновых изображений
- Пороговая и мультипороговая сегментация
- Методы слияния, разбиения и слияния/разбиения областей
- Способы описания выделенных областей
- Текстурные признаки
- 1.6.Морфологические методы анализа сцен (по ю.П. Пытьеву) Методы обнаружения объектов, заданных эталонами
- Согласованная фильтрация.
- Корреляционное обнаружение.
- Морфологический подход ю.П. Пытьева.
- Форма изображения как инвариант преобразований изображений, отвечающих вариациям условий регистрации
- Сравнение изображений по форме
- Выделение отличий изображений по форме
- Обнаружение объекта по его изображению и оценка его координат
- *Морфология на базе кусочно-линейной интерполяции
- Преобразование Хафа для поиска прямых
- *Различные способы параметризации прямых
- Преобразование Хафа для поиска окружностей
- Анализ аккумулятора при поиске геометрических примитивов
- Обобщенное преобразование Хафа
- *Специализированная процедура голосования для поиска эллипсов
- *Рекуррентное преобразование Хафа в скользящем окне
- 1.8.Математическая морфология (по ж. Серра)
- Морфологические операции на бинарных изображениях
- Морфологические операции на полутоновых изображениях
- Морфологическое выделение «черт» и объектов
- Морфологический спектр
- Морфологические скелеты. Непрерывная бинарная морфология Непрерывная бинарная морфология
- Непрерывное гранично-скелетное представление изображения
- Обработка и использование скелета
- *Обобщенные скелетные представления бинарных фигур
- Алгоритмы утончения дискретного бинарного изображения
- *Регуляризация скелетов
- Типы нерегулярностей скелета
- Устранение нерегулярностей
- Регуляризация скелета по Тихонову
- *Селективные морфологии
- 1.9. Анализ движения. Выделение движущихся объектов. Разность кадров. Вычитание фона. Анализ оптических потоков. Слежение за движущимися объектами. Корреляционное слежение.
- Обучение с учителем. Детерминированные методы, основанные на «близости». Линейные решающие правила. Метод построения эталонов. Метод ближайшего соседа. Методkближайших соседей.
- Линейные решающие правила
- Метод построения эталонов
- Методы ближайших соседей
- Параметрические и непараметрические методы
- Дискриминантные и моделирующие методы обучения
- Способность распознавателя к обобщению. Регуляризация.
- Байесовская теория решений. Случай двух классов. Классификаторы, разделяющие функции и поверхности решений. Вероятности ошибок. Разделяющие функции для случая нормальной плотности.
- Дискриминантный анализ. Линейный дискриминант Фишера. Персептронная функция критерия. Линейный дискриминантный анализ (lda,дискриминант Фишера)
- Персептрон Розенблатта
- Анализ свидетельств
- Байесовское объединение свидетельств
- Структурное распознавание
- Автоматизированное конструирование алгоритмов обнаружения объектов на основе преобразований модельных описаний объектов.
- Нейросетевое распознавание
- Нейронные сети ассоциативной памяти. Сети Хопфилда.
- Многослойные персептроны. Оптимизационное обучение. Метод обратного распространения ошибки.
- Многослойные персептроны. Правило Хебба.
- *Связь с байесовским распознаванием
- Сети встречного распространения. Самоорганизующиеся сети.