Минобрнауки томский государственный университет факультет информатики утверждаю
Скачать 68.99 Kb.
|
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ИНФОРМАТИКИ УТВЕРЖДАЮ Декан факультета С.П. Сущенко « » 2010 г. ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ (ОПД.В.01) РАБОЧАЯ ПРОГРАММА трудоемкость дисциплины 4 зачетные единицы НАПРАВЛЕНИЕ 010400 – ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Томск 2010
I.Организационно-методический разделЦель курса – изучение математических основ и алгоритмов представления и обработки изображений. Задача учебного курса. Студент должен понимать теорию и владеть методами построения алгоритмов обработки геометрических объектов и изображений. Требования к уровню освоения дисциплины. Студент должен знать теорию и владеть методами построения алгоритмов обработки геометрических объектов и изображений. Студент должен уметь создавать алгоритмы обработки изображений. Дисциплины-предшественники: основы дискретной математики, основы программирования, алгебра и геометрия, компьютерная графика. II.Содержание дисциплиныII.1.Лекционный курс1. Выпуклые оболочки для точек плоскости. Задача построения выпуклой оболочки, ее сложность. Алгоритм Джарвиса. Алгоритм Грэхема, его вариант “под-над”. Объединение двух выпуклых оболочек. Алгоритм “разделяй и властвуй”. Быстрый алгоритм. Приближенный алгоритм. Построение системы выпуклых оболочек, двумерная медиана. 2. Триангуляции 2.1. Общие понятия Определение триангуляции. Число ребер и число треугольников в триангуляции. Структура данных для триангуляции. Переход к соседнему треугольнику. Поиск треугольника, в который попадает точка. Обход по треугольникам вокруг точки. 2.2. Триангуляция Делоне Мозаика Вороного. Определение триангуляции Делоне. Ее свойства. Критерий Делоне. Итерационный алгоритм построения триангуляции Делоне. Алгоритм “разделяй и властвуй”. Алгоритм с кэш-таблицей (статический и динамический). Оценка средней длины ребра для равномерного распределения. Полосовой алгоритм и его оптимизация для равномерного распределения. 2.3. Оптимальная триангуляция Критерий оптимальности. Жадный алгоритм для построения приближенно оптимальной триангуляции. Приближенные алгоритмы: перестроение треугольников по длине диагонали в 4-угольнике, перестроение четверок треугольников, перестроение треугольников в окрестности точки. Оптимальная триангуляция для однозначной поверхности. Критерий оптимальности – минимальная площадь триангуляции. 2.4. Триангуляция с ограничениями Выделение монотонных многоугольников. Триангуляция монотонных многоугольников. Вставка ребер в готовую триангуляцию. Триангуляция с ограничениями с использованием кэш-таблицы. 3. Графический поиск Прямолинейный плоский планарный граф. Поиск точки на планарном подразбиении. Метод полос. Детализация триангуляции Киркпатрика. Поиск на триангуляции с поисковой таблицей, оценка средней величины поиска. Многоуровневая поисковая таблица. Региональный поиск. D-дерево поиска. Дерево регионов. R-деревья для поиска. Региональный поиск на триангуляции с поисковой таблицей. 4. Интерполяция поверхностей. Интерполяция однозначной поверхности. Билинейная поверхность на регулярной сетке. Бикубическая поверхность. Локальная поверхность Кунса. Параметрическая поверхность. Треугольное разбиение регулярной сетки. Последовательное приближение треугольниками гладкой однозначной поверхности. 5. Изолинии и разрезы однозначной поверхности. Построение разрезов по регулярному и нерегулярному представлению однозначной поверхности. Изолинии и их отслеживание по регулярной и треугольной сеткам. Сглаживание изолиний коридорными ломаными и локальными сплайнами. 6. Маршруты на графовой модели изображения. Графовая модель изображения. Кратчайшие пути на графовой модели. Вычисление минимального остова на плоскости с помощью триангуляции Делоне. Метрическая задача коммивояжера. Приближенные алгоритмы: алгоритм дерева, алгоритм Кристофидеса. Локальные улучшения маршрута. 7. Вычисление координат при графическом вводе. Векторизация растровых изображений. Построение графовой модели изображения. Скелетизация линий на растре. Отлеживание линий. Интерактивные методы выделения линий. Фотограмметрия. Восстановление матрицы проективного преобразования по опорным точкам на растровом изображении. Интерактивный метод ввода и вычисления трехмерных координат по двум снимкам II.2.Лабораторный практикумЗадания состоят в программировании и отладке ряда алгоритмов. Алгоритмы программируются на языке Паскаль, Си или др. 1. Алгоритм Грэхема вычисления выпуклой оболочки. 2. Алгоритм триангуляции (по выбору, приближенно оптимальной или Делоне). 3. Алгоритм последовательного приближения треугольниками гладкой однозначной поверхности. 4. Алгоритм построения изолиний однозначной поверхности со сглаживанием в коридоре на основе триангуляции. III.Распределение часов курса по темам и видам работ
IV.Учебно-методическое обеспечение курсаIV.1.Основная литература1. Роджерс Д., Адамс Дж. Математические основы машинной графики. – М.: Машиностроение, 1980. 2. Роджерс Д. Алгоритмические основы машинной графики. – М.: Мир, 1989. 3. Павлидис Т. Алгоритмы машинной графики и обработки изображений. – М.:Радио и связь, 1986. 4. Фоли Дж., ван Дэм Ф. Основы интерактивной машинной графики. В 2-х книгах. – М.: Мир, 1985. 5. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. – М.: Мир. 1989. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – закрепление теоретических знаний по теоретическим и математическим основам информатики, навыков создания и анализа программных... | | Минобрнауки томский государственный университет факультет информатики утверждаю Требования к уровню освоения дисциплины – владение методами математического анализа |
| Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – изучение методов объектно-ориентированного анализа и проектирования | | Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – изучение методов объектно-ориентированного анализа и проектирования |
| Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – изучение теории формальных языков, автоматов и методов построения трансляторов | | Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – ознакомить студентов с основными задачами компьютерной графики и методами их решения |
| Минобрнауки томский государственный университет факультет информатики утверждаю Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической... | | Минобрнауки томский государственный университет факультет информатики утверждаю Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической... |
| Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – формирование основ знаний по теории информации, принципам кодирования, изучение важнейших алгоритмов в этой области | | Минобрнауки томский государственный университет факультет информатики утверждаю Задача учебного курса – ознакомление с основными понятиями и методами математической логики и теории алгоритмов с ориентацией на... |