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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Страница создана по материалам сборника спецкурсов ВМК)
Текущая версия (08:52, 11 декабря 2013) (править) (отменить)
(Литература)
 
(18 промежуточных версий не показаны.)
Строка 1: Строка 1:
== Аннотация ==
== Аннотация ==
-
Рассматривается задача анализа формы плоских фигур и связанные с ней приложения в области распознавания изображений, компьютерной графики и геоинформатики. Исследуются вопросы аппроксимации бинарных растровых изображений многоугольными фигурами, представления фигур циркулярными графами, вычисления скелетов, сравнения и преобразования формы на основе циркулярных графов.
+
В компьютере изображения представляются прямоугольными матрицами точек, обладающих определенным цветом и яркостью. Такое дискретное представление является удобным для ввода, запоминания, обработки в компьютере. Однако для анализа формы объектов такое представление неудобно. Человеку привычнее и проще при описании формы объектов оперировать непрерывными геометрическими фигурами. Основные преимущества непрерывного представления: адекватность его с физической сущностью «сплошных» объектов реального мира, возможность использования для анализа, преобразований и распознавания формы методов «непрерывной» математики.
-
Длительность курса 32 часа. Курс рассчитан на студентов 3-4 курсов.
+
В курсе рассматриваются вопросы анализа формы плоских фигур и связанные с этим приложения в области распознавания изображений, компьютерной графики и геоинформатики. В первом семестре рассматриваются темы, относящиеся к вычислительной геометрии – геометрический поиск, выпуклые оболочки, пересечения и близость объектов. Вычислительная геометрия является теоретической основой для разработки эффективных алгоритмов работы с изображениями. Во втором семестре – темы аппроксимации бинарных растровых изображений многоугольными фигурами, представления фигур циркулярными графами, вычисления [[Скелет|скелетов]], сравнения и преобразования формы на основе циркулярных графов.
 +
 
 +
Длительность курса 64 часа (2 семестра). Курс рассчитан на студентов 2-4 курсов.
Автор курса: проф. каф. [[ММП]] д.т.н. [[Участник:Mest|Местецкий Леонид Моисеевич]].
Автор курса: проф. каф. [[ММП]] д.т.н. [[Участник:Mest|Местецкий Леонид Моисеевич]].
== Содержание курса ==
== Содержание курса ==
-
+
 
-
Непрерывные и дискретные модели формы. Модель непрерывной границы дискретной фигуры. Поиск и прослеживание границы дискретной фигуры.
+
=== Задачи и алгоритмы вычислительной геометрии (осенний семестр) ===
-
+
 
-
Линейная аппроксимация границ дискретной фигуры. Скелетизация многоугольных фигур на основе диаграмм Вороного. Графы смежности элементов многоугольных фигур. Алгоритмы скелетизации многоугольных фигур. Регуляризация скелетов. Построение базовых скелетов.
+
* Основные понятия вычислительной геометрии. Мера сложности вычислений. Асимптотический анализ сложности. Рекурсивные алгоритмы. Оценка вычислительной сложности задачи.
-
+
 
-
Циркулярные фигуры и жирные линии. Циркулярное представление изображений. Генерация признаковых описаний фигур на основе скелетов.
+
* Алгоритмическая парадигма «разделяй и властвуй». Геометрический поиск. Локализация точки в простом и в выпуклом многоугольнике при уникальном и массовом запросе. Локализация точки в планарном подразбиении.
-
+
 
-
Модели сравнения формы фигур. Преобразование формы фигур.
+
* Построение выпуклых оболочек. Алгоритмы Джарвиса, Грэхема. Слияние выпуклых оболочек. Метод редукции для оценки сложности задачи.
 +
 
 +
* Пересечения геометрических объектов. Пересечения конечного множества отрезков. Алгоритмическая парадигма плоского заметания. Структуры данных в алгоритме заметания.
 +
 
 +
* Близость геометрических объектов. Разбиения Вороного и триангуляции Делоне. Преобразования двойственных графов. Алгоритмы построения триангуляции Делоне: наивные, жадные, инкрементные, флип-флоп, рекурсивные. Обобщенные диаграммы Вороного для различных множеств сайтов – кругов, отрезков, многоугольников.
 +
 
 +
* Обобщенная диаграмма Вороного и скелет многоугольной фигуры.
 +
 
 +
=== Задачи и алгоритмы морфологического анализа изображений (весенний семестр) ===
 +
 
 +
* Бинарное изображение как результат сегментации формы. Фигура, как модель формы, открытое множество, связное множество, область, односвязная и многосвязная области, замкнутая область, жорданова кривая
 +
 
 +
* Непрерывные и дискретные модели формы. Граничное и скелетное описание фигуры, их достоинства и недостатки. Дискретные модели границы и скелета фигуры. Эквивалентность непрерывной и дискретной моделей формы.
 +
 
 +
* Непрерывные границы дискретной фигуры. Связность в дискретном пространстве, дискретная фигура. Треугольные структуры соседства, гексагональные структуры соседства (6-смежность), объектная и компонентная структуры соседства. Граничные пары, граничные треугольники, граничные коридоры дискретной сцены.
 +
 
 +
* Поиск и прослеживание границы. Постановка задачи прослеживания границ дискретной сцены. Симплексное прослеживание. Прослеживание методом подвижного моста.
 +
 
 +
* Аппроксимация граничного коридора разделяющей фигурой минимального периметра. Алгоритм вытягивания нити. Аппроксимация границы составными кривыми Безье.
 +
 
 +
* Обобщения диаграммы Вороного и триангуляции Делоне: в манхэттенской и в шахматной метриках, для сайтов-окружностей в метрике Лагерра, для разделённых сайтов-сегментов.
 +
 
 +
* Диаграмма Вороного многоугольной фигуры. Связь диаграммы Вороного многоугольника и его скелета, алгоритм построения скелета многоугольника по его диаграмме Вороного. Обобщённая триангуляция Делоне для коллекции сайтов.
 +
 
 +
* Регуляризация скелета методом стрижки. Силуэт скелетного графа, силуэт подграфа, расстояние между силуэтами. Последовательная стрижка скелета с контролем точности. Стрижка тонких элементов
 +
 
 +
* Циркулярные фигуры и жирные линии. Преобразования формы изображений в компьютерной графике и в распознавании образов. Жирная кривая, циркулярная фигура, осевой граф, функция ширины, силуэт. Деформация циркуляра и задача подгонки, аппроксимация скелета циркуляром.
== Литература ==
== Литература ==
-
# Местецкий Л.М. [[Участник:Mest#Монография|Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры.]] М.: Физматлит. 2009.
+
# Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.
 +
# Местецкий Л.М. [[Участник:Mest#Монография|Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры.]] Москва: Физматлит. 2009.
 +
# Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013. [[Media:Lectures CG.rar|Конспект [1.46 Мб]]]
 +
# Местецкий Л.М. Лекции по непрерывным морфологическим моделям [[Media:Lectures Mestetskiy.rar|Презентации PowerPoint [3.8 Мб]]]
 +
 
 +
== Библиотека программ ==
 +
 
 +
# Программа на Delphi-Pascal [[Media: SkeletonMaker Delphi.rar |Архив [500 Кб]]]
 +
# Программа на C++ [[Media: SkeletonMaker C.rar| Архив [4.4 Мб]]]
 +
 
 +
== Время и место проведения ==
 +
 
 +
Первая часть курса (осень 2011) по средам в ауд.607 ВМиК МГУ с 18 часов.
 +
Первая лекция 28 сентября 2011 г.
 +
 
 +
Вторая часть курса (весна 2012) по понедельникам в ауд.609 ВМиК МГУ с 16:20.
 +
Первая лекция 20 февраля 2012 г.
 +
 
 +
== Ссылки ==
 +
[[Семинар Л.М. Местецкого]]
 +
[[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Текущая версия

Содержание

Аннотация

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

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

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

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

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

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

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

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

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

Литература

  1. Препарата Ф., М.Шеймос М. Вычислительная геометрия: введение. Москва: «Мир», 1989.
  2. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. Москва: Физматлит. 2009.
  3. Местецкий Л.М. Лекции по вычислительной геометрии. Учебное пособие. ВМК МГУ, 2013. Конспект [1.46 Мб]
  4. Местецкий Л.М. Лекции по непрерывным морфологическим моделям Презентации PowerPoint [3.8 Мб]

Библиотека программ

  1. Программа на Delphi-Pascal Архив [500 Кб]
  2. Программа на C++ Архив [4.4 Мб]

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

Первая часть курса (осень 2011) по средам в ауд.607 ВМиК МГУ с 18 часов. Первая лекция 28 сентября 2011 г.

Вторая часть курса (весна 2012) по понедельникам в ауд.609 ВМиК МГУ с 16:20. Первая лекция 20 февраля 2012 г.

Ссылки

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

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

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