Непрерывные морфологические модели и алгоритмы (курс лекций, Л.М. Местецкий)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 44: Строка 44:
* Циркулярные фигуры и жирные линии. Преобразования формы изображений в компьютерной графике и в распознавании образов. Жирная кривая, циркулярная фигура, осевой граф, функция ширины, силуэт. Деформация циркуляра и задача подгонки, аппроксимация скелета циркуляром.
* Циркулярные фигуры и жирные линии. Преобразования формы изображений в компьютерной графике и в распознавании образов. Жирная кривая, циркулярная фигура, осевой граф, функция ширины, силуэт. Деформация циркуляра и задача подгонки, аппроксимация скелета циркуляром.
-
 
== Литература ==
== Литература ==
Строка 50: Строка 49:
# Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.
# Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.
# Местецкий Л.М. [[Участник:Mest#Монография|Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры.]] Москва: Физматлит. 2009.
# Местецкий Л.М. [[Участник:Mest#Монография|Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры.]] Москва: Физматлит. 2009.
 +
 +
== Время и место проведения ==
 +
 +
По средам в ауд.607 ВМиК МГУ с 18 часов.
 +
 +
Первая лекция 28 сентября 2011 г.
== Ссылки ==
== Ссылки ==

Версия 06:23, 28 сентября 2011

Содержание

Аннотация

В компьютере изображения представляются прямоугольными матрицами точек, обладающих определенным цветом и яркостью. Такое дискретное представление является удобным для ввода, запоминания, обработки в компьютере. Однако для анализа формы объектов такое представление неудобно. Человеку привычнее и проще при описании формы объектов оперировать непрерывными геометрическими фигурами. Основные преимущества непрерывного представления: адекватность его с физической сущностью «сплошных» объектов реального мира, возможность использования для анализа, преобразований и распознавания формы методов «непрерывной» математики.

В курсе рассматриваются вопросы анализа формы плоских фигур и связанные с этим приложения в области распознавания изображений, компьютерной графики и геоинформатики. В первом семестре рассматриваются темы, относящиеся к вычислительной геометрии – геометрический поиск, выпуклые оболочки, пересечения и близость объектов. Вычислительная геометрия является теоретической основой для разработки эффективных алгоритмов работы с изображениями. Во втором семестре – темы аппроксимации бинарных растровых изображений многоугольными фигурами, представления фигур циркулярными графами, вычисления скелетов, сравнения и преобразования формы на основе циркулярных графов.

Длительность курса 64 часа (2 семестра). Курс рассчитан на студентов 2-4 курсов.

Автор курса: проф. каф. ММП д.т.н. Местецкий Леонид Моисеевич.

Содержание курса

Задачи и алгоритмы вычислительной геометрии (осенний семестр)

  • Основные понятия вычислительной геометрии. Мера сложности вычислений. Асимптотический анализ сложности. Рекурсивные алгоритмы. Оценка вычислительной сложности задачи.
  • Алгоритмическая парадигма «разделяй и властвуй». Геометрический поиск. Локализация точки в простом и в выпуклом многоугольнике при уникальном и массовом запросе. Локализация точки в планарном подразбиении.
  • Построение выпуклых оболочек. Алгоритмы Джарвиса, Грэхема. Слияние выпуклых оболочек. Метод редукции для оценки сложности задачи.
  • Пересечения геометрических объектов. Пересечения конечного множества отрезков. Алгоритмическая парадигма плоского заметания. Структуры данных в алгоритме заметания.
  • Близость геометрических объектов. Разбиения Вороного и триангуляции Делоне. Преобразования двойственных графов. Алгоритмы построения триангуляции Делоне: наивные, жадные, инкрементные, флип-флоп, рекурсивные. Обобщенные диаграммы Вороного для различных множеств сайтов – кругов, отрезков, многоугольников.
  • Обобщенная диаграмма Вороного и скелет многоугольной фигуры.

Задачи и алгоритмы морфологического анализа изображений (весенний семестр)

  • Бинарное изображение как результат сегментации формы. Фигура, как модель формы, открытое множество, связное множество, область, односвязная и многосвязная области, замкнутая область, жорданова кривая
  • Непрерывные и дискретные модели формы. Граничное и скелетное описание фигуры, их достоинства и недостатки. Дискретные модели границы и скелета фигуры. Эквивалентность непрерывной и дискретной моделей формы.
  • Непрерывные границы дискретной фигуры. Связность в дискретном пространстве, дискретная фигура. Треугольные структуры соседства, гексагональные структуры соседства (6-смежность), объектная и компонентная структуры соседства. Граничные пары, граничные треугольники, граничные коридоры дискретной сцены.
  • Поиск и прослеживание границы. Постановка задачи прослеживания границ дискретной сцены. Симплексное прослеживание. Прослеживание методом подвижного моста.
  • Аппроксимация граничного коридора разделяющей фигурой минимального периметра. Алгоритм вытягивания нити. Аппроксимация границы составными кривыми Безье.
  • Обобщения диаграммы Вороного и триангуляции Делоне: в манхэттенской и в шахматной метриках, для сайтов-окружностей в метрике Лагерра, для разделённых сайтов-сегментов.
  • Диаграмма Вороного многоугольной фигуры. Связь диаграммы Вороного многоугольника и его скелета, алгоритм построения скелета многоугольника по его диаграмме Вороного. Обобщённая триангуляция Делоне для коллекции сайтов.
  • Регуляризация скелета методом стрижки. Силуэт скелетного графа, силуэт подграфа, расстояние между силуэтами. Последовательная стрижка скелета с контролем точности. Стрижка тонких элементов
  • Циркулярные фигуры и жирные линии. Преобразования формы изображений в компьютерной графике и в распознавании образов. Жирная кривая, циркулярная фигура, осевой граф, функция ширины, силуэт. Деформация циркуляра и задача подгонки, аппроксимация скелета циркуляром.

Литература

  1. Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.
  2. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. Москва: Физматлит. 2009.

Время и место проведения

По средам в ауд.607 ВМиК МГУ с 18 часов.

Первая лекция 28 сентября 2011 г.

Ссылки

Семинар Л.М. Местецкого

Математические методы прогнозирования (кафедра ВМиК МГУ)

Личные инструменты