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