Минобрнауки томский государственный университет факультет информатики утверждаю




Скачать 68.99 Kb.
НазваниеМинобрнауки томский государственный университет факультет информатики утверждаю
Дата15.02.2013
Размер68.99 Kb.
ТипЗадача
МИНОБРНАУКИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАТИКИ


УТВЕРЖДАЮ

Декан факультета

С.П. Сущенко

« » 2010 г.


ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ

(ОПД.В.01)

РАБОЧАЯ ПРОГРАММА

трудоемкость дисциплины 4 зачетные единицы


НАПРАВЛЕНИЕ 010400 – ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ


Томск

2010


УТВЕРЖДЕНО

кафедрой теоретических основ информатики.

Протокол №05/10 от 01.09.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.Распределение часов курса по темам и видам работ


№№ пп

Наименование тем

Всего часов

Аудиторные занятия (час),

в том числе

Самостоятельная

работа










лекции

семинары

лабораторные занятия




1

Выпуклые оболочки для точек плоскости

7

6







1

2

Триангуляции

10

8







2

3

Графический поиск

6

4







2

4

Интерполяция поверхностей

6

4







2

5

Изолинии и разрезы однозначной поверхности

8

6







2

6

Маршруты на графовой модели изображения

6

4







2

7

Вычисление координат при графическом вводе

5

4







1

8

Лабораторные работы

36







36




ИТОГО




84

36




36

12



IV.Учебно-методическое обеспечение курса

IV.1.Основная литература


1. Роджерс Д., Адамс Дж. Математические основы машинной графики. – М.: Машиностроение, 1980.

2. Роджерс Д. Алгоритмические основы машинной графики. – М.: Мир, 1989.

3. Павлидис Т. Алгоритмы машинной графики и обработки изображений. – М.:Радио и связь, 1986.

4. Фоли Дж., ван Дэм Ф. Основы интерактивной машинной графики. В 2-х книгах. – М.: Мир, 1985.

5. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. – М.: Мир. 1989.

Похожие:

Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – закрепление теоретических знаний по теоретическим и математическим основам информатики, навыков создания и анализа программных...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Требования к уровню освоения дисциплины – владение методами математического анализа
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение методов объектно-ориентированного анализа и проектирования
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение методов объектно-ориентированного анализа и проектирования
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – изучение теории формальных языков, автоматов и методов построения трансляторов
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – ознакомить студентов с основными задачами компьютерной графики и методами их решения
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами неклассических логик с ориентацией на их использование в практической...
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Цель курса – формирование основ знаний по теории информации, принципам кодирования, изучение важнейших алгоритмов в этой области
Минобрнауки томский государственный университет факультет информатики утверждаю iconМинобрнауки томский государственный университет факультет информатики утверждаю
Задача учебного курса – ознакомление с основными понятиями и методами математической логики и теории алгоритмов с ориентацией на...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница