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

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

Перейти к: навигация, поиск

Содержание

Аннотация

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

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

Длительность курса 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 г.

Ссылки

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

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

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