Обработка сигналов и изображений

Программа курса

ОБРАБОТКА СИГНАЛОВ И ИЗОБРАЖЕНИЙ

Курс реализуется в рамках направления 552800 «Информатика и вычислительная техника», относится к циклу специальных дисциплин.

Курс «Цифровая обработка сигналов и изображений» предназначен для изучения классических и современных методов анализа и обработки временных последовательностей и дискретных изображений, реализация которых основана на использовании современных инструментальных систем программирования.

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

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

По окончании изучения курса студент должен:

·  иметь представление о теоретических основах построения базовых алгоритмов цифровой обработки сигналов;

·  знать параметрические описания детерминированных и случайных сигналов, методы оценивания параметров (в частности, корреляционных и спектральных характеристик данных сигналов) и эффективные вычислительные алгоритмы дискретных Фурье - и вейвлет- преобразований;

·  уметь применять полученные знания об основных моделях временных последовательностях и методах цифровой обработки одномерных сигналов при решении конкретных задач, требующих реализации эффективных алгоритмов цифровой обработки сигналов;

·  знать содержание основных задач анализа и обработки сигналов (подавление помех, восстановление искаженных сигналов, обнаружение сигналов с заданными свойствами);

·  иметь представление о теоретических основах и методах решения указанных задач.

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

Содержание дисциплины

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

Курс рассчитан на два семестра и предполагает знакомство студентов с основами математического анализа, линейной алгебры и теории вероятностей

Наименование разделов и тем	К о л и ч е с т в о ч а с о в
Лекции	Семинары	Лаборатор- ные работы	Самостоятель-ная работа	Всего часов
Первый семестр
1. Классификация сигналов и способы их описания. Информативные характеристики детерминированных сигналов (энергия, мощность, моменты, автокорреляционная функция, спектральный состав). Гармонический анализ импульсной последовательности. Скважность, меандр, эффективная ширина спектра, база сигнала. Примеры.	2			4	6
2. Процесс дискретизации сигналов (аналого-цифровое преобразование). Спектр. Дискретное преобразование Фурье (ДПФ). Основные свойства ДПФ. дискретизованного сигнала. Восстановление аналогового сигнала по множеству отсчетов. Теорема Котельникова-Шеннона. Частота Найквиста. Эффект появления «ложных частот» (aliasing). Примеры.	2			4	6
3. Использование ДПФ для восстановления исходного сигнала и для вычисления отсчетов «непрерывного» спектра (интерполяция спектра). Вычисление линейной свертки при помощи ДПФ. Эффект «растекания» спектра и весовые функции (окна). Алгоритмы быстрого преобразования Фурье (БПФ).	2			4	6
4. Ограничения и недостатки преобразования Фурье. Проблемы частотно-временной локализации нестационарных сигналов. Оконное преобразование Фурье. Идея вейвлет-преобразования. Основы теории. Базисные функции непрерывного вейвлет – преобразования (WAVE - , MHAT - , DOG – вейвлеты). Примеры применения.	2			2	4
5. Дискретный вейвлет-анализ. Кратномасштабное представление сигналов. Скейлинг-функция и материнский вейвлет. Вейвлеты Хаара и Добеши. Быстрое вейвлет-преобразование (алгоритм Малла). Примеры применения.	2			2	4
6. Стохастическая модель сигналов и изображений (статистический ансамбль, совместное распределение, статистические моменты). Дискретные стационарные (однородные) случайные процессы и поля. Среднее, автокорреляция, автоковариация. Виды стационарности случайных процессов и полей. Спектральная плотность мощности (СПМ) случайных процессов. Взаимосвязь с автоковариационной последовательностью (АКП) - теорема Винера-Хинчина. Свойства АКП и СПМ стационарных случайных процессов.	2			2	4
7. Некоторые модели случайных сигналов. Гармонический процесс со случайной фазой. Дискретный гауссовский случайный процесс. Марковское свойство. Винеровский процесс (броуновское движение) как пример гаусс-марковского случайного процесса. Случайный фототелеграфный сигнал (сканирование черно-белого изображения): вероятностная модель, автокорреляционная функция, спектральная плотность мощности.	2			4	6
8. Эргодичность. Основные принципы теории оценок (несмещенность, состоятельность). Оценивание автокорреляции и взаимной корреляции. Свойства оценок. Коррелограммный метод оценки СПМ. Метод Блэкмана-Тьюки. Периодограммные оценки СПМ. Свойства оценок. Спектральные окна. Метод Уэлча.	2			4	6
9. Линейные преобразования (фильтрация) стационарных случайных сигналов: свойства выходного сигнала (существование, моменты, автоковариационная функция). Описание фильтра в виде дискретной линейной системы: импульсная характеристика, частотная характеристика, фильтры с линейной фазовой характеристикой. Прямое Z-преобразование дискретных последовательностей. Область сходимости. Свойства Z-преобразования. Z-свертка последовательностей. Передаточная функция дискретной системы.	2			6	8
10. Линейные разностные уравнения с постоянными коэффициентами как модели цифровых (рекурсивных) фильтров. Численное интегрирование как пример рекурсивной фильтрации. Бегущий усредняющий фильтр, авторегрессионный фильтр. Обратное Z-преобразование. Нули и полюсы дискретной системы, минимально-фазовое свойство. Авторегрессионная (параметрическая) модель стационарных случайных процессов как универсальная модель стохастических сигналов. Взаимосвязь параметров авторегрессионной (АР-) модели с автокорреляционной последовательностью. Нормальные уравнения Юла-Уолкера. СПМ авторегрессионного процесса.	2			6	8
11. Оптимальный линейный прогноз стационарных случайных процессов. Принцип ортогональности. Разложение Вольда (регулярная и сингулярная составляющие случайного сигнала). Понятие «обновления». Алгоритм Левинсона рекуррентного оценивания параметров АР-модели. Спектральное оценивание. Характеристики АР-оценок СПМ.	2			4	6
12. Оценивание случайного процесса по наблюдениям стохастически связанного с ним случайного сигнала (дискретное уравнение Винера-Хопфа). Метод восстановления дискретного (полезного) сигнала в линейной модели наблюдений на основе оптимального линейного фильтра Винера-Колмогорова. Ошибка восстановления сигнала в простейших вариантах.	2			4	6
13. Аппроксимация (сглаживание) сигналов и метод наименьших квадратов (МНК). Алгебра и геометрия МНК. Нормальное решение. Метод псевдообратной матрицы. SVD-решение. Статистические свойства оценок МНК. Проверка гипотез при спецификации аппроксимирующей модели сигнала (основы проверки статистических гипотез). Проверка линейных гипотез. Критерии удаления (включения) переменных в описание сигнала.	2			2	4
14. Модели дискретных систем в пространстве состояний (уравнение состояния системы, уравнение измерения). Пример на основе авторегрессионной схемы описания. Построение алгоритма рекуррентной фильтрации Калмана для дискретной линейной динамической системы: коэффициент усиления фильтра, оптимальный выбор параметров фильтрации. Двумерная дискретная фильтрация (примеры построения винеровского и калмановского фильтров). Сравнительный анализ.	2			4	6
15. Распознавание образов (сигналов). Разделяющие функции. Алгоритмы классификации выборочных объектов. Байесовский метод распознавания. Дискриминантный анализ (распознавание) для двух многомерных нормальных выборок. Вероятности ошибок классификации. Виды и свойства оценок.	2			2	4
16. Применение методов классификации в алгоритмах сегментации изображений двумерных сцен.	2			1	3
Второй семестр
1. Математическое описание непрерывных изображений. Двумерные системы, их представление в виде двумерных операторов. Линейные двумерные системы, понятие импульсного отклика (функции рассеяния точки) системы. Пространственно-независимые системы. Операция свертки. Теорема о спектре свертки.	2			1	3
2. Идеальная дискретизация изображений. Восстановление непрерывного изображения по множеству отсчетов. Реальные системы дискретизации изображений, их отличие от идеальной. Влияние конечности размеров дискретизирующей решетки. Влияние конечной ширины дискретизирующего импульса.	2			2	4
3. Квантование изображений. Понятие порогов и уровней квантования. Среднеквадратичная ошибка (СКО) квантования. Оценка СКО при большом количестве порогов квантования. Выбор уровней квантования, минимизирующих СКО при этом условии. Минимизация СКО квантования при равномерном распределении амплитуды сигнала.	2			2	4
4. Преобразования яркости изображений. Гистограмма яркостей. Коррекция амплитудных характеристик. Линейное изменение контраста. Преобразование гистограмм. Адаптивное преобразование яркости.	2			1	3
5. Восстановление изображений. Линейная пространственно-инвариантная система с аддитивным шумом. Инверсная фильтрация. Неустойчивость инверсного фильтра к действию шума.	2			2	4
6. Восстановление с помощью метода наименьших квадратов (восстановление при неизвестных характеристиках сигнала и шума; восстановление при известной корреляционной матрице шума)	2			1	3
7. Оптимальный фильтр для восстановления искаженных изображений. Фильтр Винера для линейной пространственно-инвариантной системы с аддитивным шумом. Амплитудно-частотная характеристика фильтра Винера. Сопоставление его с инверсным фильтром.	2			2	4
8. Обнаружение сигнала. Постановка задачи обнаружения сигнала как задачи построения линейного фильтра, обеспечивающего максимальное отношение сигнал/шум на выходе. Понятие согласованного фильтра. Импульсный отклик согласованного фильтра.	2			2	4
9. Улучшение визуального восприятия изображений как задача фильтрации. Линейные методы подавления шума и подчеркивания границ. Масочная фильтрация. Нелинейные фильтры, используемые для подавления импульсного шума. Медианный фильтр.	2				2
10. Выделение контуров. Определение контура. Дифференциальные методы. Адаптивное выделение контуров как перепадов яркости.	2			1	3
11. Геометрические преобразования изображений. Евклидовы, аффинные, полиномиальные преобразования. Восстановление изображений в преобразованных координатах. Билинейная интерполяция.	2			2	4
12. Координатная привязка изображений. Оценивание параметров преобразования координат. Сдвиг изображений и корреляционная привязка.	2				2
13. Задача предсказания значений дискретного сигнала. Линейный прогноз как задача построения линейного фильтра. Использование линейного прогноза для точной привязки дискретных изображений.	2			2	4
14. Реконструкция внутренней структуры объекта по проекциям (томография). Преобразование Радона. Классическая томография. Обратное проецирование. Теорема о центральном сечении. Фурье-алгоритм восстановления.	2			2	4
15. Алгоритм свертки и обратного проецирования. Алгоритм восстановления посредством обратного проецирования и двумерной фильтрации. Ошибки восстановления, обусловленные шумами в исходных данных.	2			2	4
16. Восстановление трехмерных рельефов по плоским изображениям (стереовидение). Модель регистрирующей камеры. Стандартная система координат камеры. Модель стереоскопической системы, оценивание трехмерных координат сцены по простейшей стереопаре.	2			2	4
17. Калибровка камер. Взаимное ориентирование камер. Поиск сопряженных точек. Восстановление структуры сцены и траектории движения камеры по последовательности изображений (ортографическая и слабоперспективная модели камеры).	2			2	4
18. Применение методов математической морфологии для описания и обработки изображений. Операции математической морфологии. Фильтрация бинарных изображений. Описание формы объектов.	2			1	3
Итого по курсу:	68			55	123

Задания на самостоятельную работу

Первый семестр

1.  Вычислить коэффициенты ряда Фурье для последовательности прямоугольных импульсов. Охарактеризуйте изменение спектра последовательности импульсов при увеличении периода их следования.

2.  Вычислить спектр и автокорреляционную функцию гармонического сигнала , учитывая, что период такого сигнала равен .

3.  Вывести взаимосвязь спектров аналогового сигнала и дискретной последовательности отсчетов этого сигнала. Как проявляется эффект «ложных частот.

4.  Установить изменение спектра дискретного сигнала, состоящего из N отсчетов, при добавлении к нему N нулей.

5.  Охарактеризовать суть эффекта «растекания» спектра и привести методы его уменьшения.

6.  Как правильно вычислить линейную свертку с помощью БПФ?

7.  Привлекая принцип неопределенности, определить вид частотно-временных окон Фурье и вейвлет базисов на плоскости время-частота.

8.  Определить скейлинг-функцию и коэффициенты вейвлет-преобразования базиса Хаара.

9.  Показать, что гармонический сигнал со случайной фазой является стационарным случайным процессом.

10.  Вывести автокорреляционную функцию фототелеграфного сигнала.

11.  Стационарная последовательность (дискретный сигнал) определена соотношением , где - случайный параметр со средним значением и дисперсией , - центрированный дискретный белый шум с дисперсией , не коррелированный с . Доказать, что среднее значение , n>1, является несмещенной и состоятельной оценкой для .

12.  Показать, что для оценки АКП оценка СПМ имеет вид.

13.  Пусть дано N отсчетов данных . Показать, что коррелограммная оценка СПМ в которой используется смещенная (альтернативная) оценка при максимальном числе возможных временных сдвигов, и выборочный энергетический спектр (периодограмма)

, идентичны.

14.  Процесс наблюдения формируется по следующей схеме: , где f(k) – полезный нестационарный случайный сигнал, а- центрированный белый шум с дисперсией . Для оценивания сигнала f(k) наблюдаемая последовательность подвергается преобразованию, которое называется фильтром экспоненциального сглаживания и имеет вид где - параметр фильтра. Показать, что данный фильтр является линейным преобразованием вида .

15.  Пусть при некотором последовательность . Показать, что данное соотношение является линейным стационарным фильтром, и найти среднее, дисперсию и автоковариационную функцию последовательности .

16.  Найти область сходимости Z-преобразования последовательности .

17.  Найти представление автоковариационной последовательности через последовательность авторегрессионных параметров.

18.  Пусть в АР-модели первого порядка белый шум является стационарным. Найти математическое ожидание и дисперсию АР(1)-последовательности и показать ее стационарность.

19.  Показать, что выход АР(p)-фильтра является регулярной последовательностью.

20.  Охарактеризовать связь между фильтром линейного предсказания (прогноза) и АР – процессом.

21.  Описать метод выбора порядка АР-модели в алгоритме Левинсона.

22.  Дать геометрическую интерпретацию проблемы винеровской фильтрации.

23.  Определить передаточную функцию фильтра Винера-Колмогорова.

24.  Построить фильтр Калмана для скалярной модели наблюдений вида

где - стационарные и центрированные белые шумы.

Второй семестр

Выясните, при каких условиях, используя дискретное изображение, можно без потерь восстановить непрерывное? Докажите, что двумерный фильтр с прямоугольной частотной характеристикой идеально восстанавливает непрерывное изображение из дискретного. Учитывая, что спектры реальных изображений не являются финитными функциями, предложите метод расчета ошибок восстановления, вызванных нарушением требований , . Поясните, в чем состоит задача поиска оптимального квантователя изображения? Чем объясняется стремление использовать небольшое число уровней квантования и что препятствует этой тенденции? Поясните механизм возникновения ложных контуров при малом числе уровней квантования изображения. С какой целью применяют нелинейное предискажение изображения при его равномерном квантовании? Какой должна быть характеристика нелинейного элемента? В чем состоит сущность поэлементной обработки изображений? Как определяются параметры преобразования изображения при его линейном контрастировании? Каков механизм появления ложных контуров при применении пилообразного контрастирования? При каких еще процедурах могут возникать ложные контуры? Докажите, что применение линейного контрастирования не изменяет вида плотности вероятности изображения. Как при этом изменяются параметры плотности вероятности? Поясните, почему при эквализации изображения не удается привести гистограмму к идеальному равномерному виду? В каком случае ухудшение четкости изображения описывается интегралом свертки исходного изображения и импульсной характеристики искажающей системы? В чем принципиальное различие между расфокусировкой и смазом? Почему нельзя абсолютно точно восстановить изображения, сформированные реальными системами? Назовите условия, при выполнении которых инверсная фильтрация обеспечивает высокое качество восстановления изображений. Почему помехоустойчивость фильтра Винера выше чем инверсного? Охарактеризуйте круг проблем, решение которых приводит к привязке последовательности изображений и их взаимной геометрической коррекции. Выстройте иерархию геометрических преобразований. Какие из них сохраняют параллельность прямых? Постройте матрицу поворота (в однородных координатах) вокруг точки плоскости на угол (указание: совместить центр поворота с началом координат, повернуть, вернуть центр поворота в прежнее положение и перемножить полученные матрицы элементарных преобразований). В каких ситуациях рекомендуется применять полиномиальную аппроксимацию (в том числе и полиномы Чебышева) для описания геометрических деформаций? Опишите процедуру восстановления изображения в преобразованных координатах. Какие используются методы интерполяции и в чем их различие? В чем состоит задача реконструкции объектов по их проекциям? Опираясь на теорему о центральном сечении, докажите эквивалентность между методом свертки и обратного проецирования и методом обратного проецирования и двумерной фильтрации. Для дискретного случая, предполагая известными количество проекций и их размер (в отсчетах), а также количество отсчетов в восстанавливаемом сечении, оцените необходимое количество операций типа “сложение-умножение” для восстановления структуры сечения. (В этом и двух следующих пунктах номера рисунков и формул соответствуют номерам в /1/.) Обратимся к рис. 6.3. Какой вид будут иметь матрицы , , и вектор в выражении (6.9) для ситуации, приведенной на рисунке? Пусть в ситуации, изображенной на рис. 6.3, векторы и внутренних координат проекций точки в плоскостях изображений левой и правой камер известны. Получите оценки трехмерных координат точки в системах координат правой и левой камер, пользуясь выражениями (6.11) и (6.12). Сравните полученный результат с (6.6) и (6.7). Объясните отличия. Опишите структуру калибровочной матрицы и выведите соотношения (6.17). Докажите справедливость соотношений (6.18). На рис. 6.6 точки и являются изображениями оптических центров камер. Полагая, что матрицы , , и вектор известны, найдите координаты этих точек в плоскостях изображений соответствующих камер. Где будут находиться точки и , если камеры расположены, как показано на рис. 6.3? Дайте определение основным операциям математической морфологии. Какую операцию и какой структурный элемент можно использовать, чтобы сместить все множество на вектор ? Докажите справедливость соотношений и , принимая во внимание определения пополнения и заполнения и учитывая, что . Пусть на дискретной решетке граничными точками множества считаются точки , такие, что среди их соседей найдется хотя бы одна точка . Предложите способ выделения всех граничных точек. Какие структурные элементы на гексагональной решетке позволяют выделять с помощью HM-преобразования концевые точки линий (структурные элементы, отличающиеся только ориентацией, считать идентичными)? Какую операцию и какой структурный элемент следует использовать для устранения изолированных черных точек на изображении, заданном на гексагональной решетке?

Рекомендуемая литература

Сергиенко обработка сигналов. – СПб.: Питер, 2002. Марпл-мл. спектральный анализ и его приложения. – М., Мир, 1990. , и др. Цифровая обработка изображений в информационных системах. Учебное пособие. Новосибирск, 2001. Методы компьютерной обработки изображений. /Под ред. . – М.: Физматлит, 2001. . Вейвлет-анализ: основы теории и примеры применения. //Успехи физических наук. Т.166, №11, 1996. Интернет-страничка «Теория и практика вейвлет-преобразования»: http://www. autex. *****/techsupt/wavelet/ МАТЛАБ. Обработка сигналов и изображений. Специальный справочник. – СПб., Питер, 2002. Балакришнан фильтрации Калмана. – М., Мир, 1988. Теория сигналов.– М., Советское радио, 1974. Введение в статистическую теорию распознавания образов. – М., Наука, 1979.

Второй семестр

Цифровая обработка изображений в информационных системах. Новосибирск, НГТУ, 2002 г. Цифровая обработка изображений, в 2-х томах.: Мир, Москва, 1982. П. Зрение роботов.: Мир, Москва, 1989. Д. Даджион, Р. Мерсеро. Цифровая обработка многомерных сигналов. М., Мир, 1988 г. Методы компьютерной обработки изображений / Под ред. .- М.: Физматлит, 2001.

Программу подготовили:

к. т.н., доцент

к. т.н., доцент

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16.

Декан ФИТ НГУ,

д. ф.-м. н.

Программа курса

ПРОГРАММИРУЕМЫЕ СИСТЕМЫ ВИЗУАЛИЗАЦИИ

Курс реализуется в рамках направления 552800 «Информатика и вычислительная техника», относится к циклу специальных дисциплин.

Курс «Программируемые системы визуализации» предназначен для подготовки специалистов в области разработки программных средств современных информационных технологий. Основной целью освоения курса является обучение базовым знаниям, современным технологиям и практическим навыкам для работы с двумерной и трехмерной компьютерной графикой.

Для достижения поставленной цели выделяются следующие задачи:

·  базовые понятия компьютерной графики (цвет, свет, пиксел, 3D-сцена и пр.);

·  методы визуализации 3D-сцен;

·  алгоритмы построения изображений;

·  алгоритмы обработки и сжатия изображений;

·  практический опыт создания и визуализации 3D-сцен.

По окончании изучения курса студент должен:

-  иметь представление о:

o  процессе восприятия человеком визуальной информации;

o  методах построения фотореалистичных изображений 3D-сцен (алгоритмы растрирования, модели освещенности, текстурирование, тени);

o  современных алгоритмах сжатия изображений;

o  характерных искажениях, возникающих при обработке и передаче графической информации;

-  знать:

o  форматы представления графической информации;

o  базовые алгоритмы построения 2D и 3D-изображений (растрирование линии, многоугольника; векторизация кривой; Z-буфер; интерполяция цвета методами Гуро и Фонга; выбор цветов палитры, дизеринг);

o  традиционные алгоритмы сжатия изображений (RLE, LZW, JPEG, MPEG);

-  уметь:

o  создать анимированную 3D-сцену средствами OpenGL;

моделировать физические или иные процессы средствами OpenGL.

Для контроля усвоения курса учебным планом предусмотрен дифференцированный зачет. Оценка выставляется по результатам выполнения контрольных заданий и ответа на вопросы по теории.

Содержание дисциплины

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

Наименование разделов и тем	К о л и ч е с т в о ч а с о в
Лекции	Семинары	Лабораторные работы	Самостоятель-ная работа	Всего часов
Двумерная графика	4		2		6
Телевизионная графика	2		2		4
Алгоритмы сжатия изображений	4		2		6
Растрирование на плоскости	2		2		4
Законы визуального восприятия	2		2		4
Трехмерная графика.	4		2		6
Знакомство с OpenGL	2		2		4
Создание модели в OpenGL			2		2
Растрирование граней	4		4		8
Растрирование в OpenGL			2		2
Глобальная и локальная модель освещения	4		4		8
Интерполяция цвета в OpenGL	2		2		4
Текстурирование	4				4
Текстурирование в OpenGL			2		2
Прозрачность в OpenGL			2		2
Задание №1				6	6
Методы построения теней.	2		2		4
Сложные модели в OpenGL			2		2
Задание №2				6	6
Итого по курсу:	36		36	55	127

Содержание отдельных разделов и тем

2D-графика (лекции)

1.  Двумерная графика. Физиология цветового зрения. Цветовые системы координат. Векторная и растровая графика. Пространственное разрешение. Размеры изображения. Палитра, цветовое разрешение. Методы уменьшения цветового разрешения (подбор палитры), дизеринг: цветовой срез, метод упорядоченного возбуждения, распространение ошибки, метод цветовых кубов, комбинированные методы.

2.  Телевизионная графика. Стандарты цветного телевидения: NTSC, PAL, SECAM. Уплотнение спектра (гребенчатый фильтр). Искажения, возникающие при передаче телевизионных изображений.

3.  Алгоритмы сжатия изображений: RLE, LZW, JPEG, Wavelet. Алгоритмы сжатия последовательностей изображений: MPEG (1,2,4).

4.  Растрирование на плоскости. Алгоритм Брезенхема для растрирования отрезка и дуги. Кривые Безье. Векторизация кривых. Растрирование контуров.

5.  Законы визуального восприятия: иерархия отношений зрения и слуха, принцип избыточности, принцип группировки, восприятие пространства, восприятие движения и событий.

3D-графика (лекции)

6.  Трехмерная графика. Векторная арифметика. Аффинные пространства. Обобщенные координаты. Преобразования пространства. Видовые преобразования и преобразования проекции. Грань, проекция грани, клиппирование. Геометрический конвейер.

7.  Растрирование граней. Алгоритмы клиппирования, алгоритм Сазерленда-Коэна, алгоритм Лианга-Барского. Односторонние поверхности, отбраковка односторонних поверхностей. Заливка, алгоритм построчного сканирования. Понятия первичного и вторичных буферов. Алгоритмы удаления невидимых поверхностей. Алгоритм художника, Z буфер. Сортировка для алгоритма художника.

8.  Глобальная и локальная модель освещения. Общая теория метода трассировки лучей (первичные лучи, отраженные лучи, тени, преломление, дерево лучей). Метод излучательности. Локальная модель освещения. Физика света, восприятие цветов, модели распространения света. Нормаль в вершине. Источники освещения. Преобразование нормали из одной системы координат в другую. Интерполяция Гуро и Фонга.

9.  Текстурирование. Отображение двухмерной текстуры на трехмерную поверхность. Текстурные координаты, билинейная, трилинейная и анизотропная фильтрации. Пертурбация нормалей. Трехмерные текстуры. Продвинутые методики текстурирования (spherical environment mapping, cubic environment mapping, environment bump mapping, emboss bump mapping, per pixel lighting, polynomial texture maps).

10.  Методы построения теней (проективные тени, stencil shadows, shadow maps, perspective shadow map).

3D-графика (семинары)

1.  Знакомство с OpenGL. Фреймы и абстрактные типы данных. Фреймы в OpenGL. Матрицы преобразований в OpenGL. Видовое преобразования в OpenGL. Проективные преобразования в OpenGL (перспективное и параллельное преобразование).

2.  Создание модели в OpenGL. Примитивы и атрибуты. Обработка многоугольников общего вида. Описание моделей средствами OpenGL (модель разноцветного куба).

3.  Растрирование в OpenGL. Буферы OpenGL. Удаление нелицевых граней. Растровое преобразование с использованием Z-буфера. Сортировка по глубине.

4.  Интерполяция цвета в OpenGL. Описание источников света в OpenGL. Спецификация материалов в OpenGL. Закрашивание модели сферы. Эффект тумана и создание иллюзии глубины пространства.

5.  Текстурирование в OpenGL. Проективное наложение текстуры в системе OpenGL. Сглаживание погрешностей дискретизации. Смешивание изображений в OpenGL.

6.  Прозрачность в OpenGL. Тонирование сцен с множеством полупрозрачных объектов.

7.  Сложные модели в OpenGL. Иерархические графические модели (модель руки робота). Обход древовидных структур. Граф сцены. Анимация.

Задания

1.  Задание № 1. Моделирование средствами OpenGL цветного куба. Анимация матриц видового, проективного и модельного преобразования. Анимация параметров источника света и материалов. Применение эффекта тумана для создания иллюзии глубины пространства. Текстурирование куба с применением билинейной и трилинейной интерполяции. Текстурирование куба одной из продвинутых техник текстурирования, например, emboss bump mapping.

2.  Задание № 2. Выполнение на выбор одного из вариантов:

·  Моделирование броуновского движения средствами OpenGL.

·  Реализация трехмерного представления статистических данных. Реализация «облета» и модификации параметров.

·  Моделирование одного из природных феноменов: водная поверхность, огонь, облака.

·  Моделирование столкновения твердых тел на примере игры биллиард.

Образцы вопросов для подготовки к дифференцированному зачету

1.  Понятие о цвете. Физиология цветового зрения. Цветовые системы координат. Форматы хранения растровых изображений. Пространственное разрешение. Размеры изображения.

2.  Стандарты цветного телевидения. Искажения, возникающие при передаче изображений.

3.  Палитра, цветовое разрешение. Методы уменьшения цветового разрешения:

·  подбор палитры методом цветового куба;

·  цветовой срез;

·  дизеринг возбуждением;

·  распространение ошибки;

·  комбинированные методы.

4.  Алгоритмы сжатия изображений: RLE-кодирование, LZW-кодирование.

5.  Алгоритмы сжатия изображений: JPEG-кодирование, WaveLet-кодирование.

6.  Алгоритмы сжатия последовательности изображений: MPEG-кодирование. Стандарты MPEG1, MPEG2, MPEG4.

Список литературы

1.  Певзнер цветных телевизионных изображений. М.: Радио и связь, 19с.

2.  Компьютерная анимация: возвращение на землю. Мир ПК № 9, 1993, стр. 95-104.

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

4.  Интерактивная компьютерная графика. Вводный курс на базе OpenGL, 2 изд.: М: Издательский дом Вильямс, 2001.

5.  Marc Stamminger, George Drettakis. Perspective Shadow Maps Proceedings of ACM SIGGRAPH 2002 July 2002.

6.  Tom Malzbender, Dan Gelb, Hans Wolters. Polynomial Texture Mapping (PTM) Hewlett-Packard Laboratories http://www. hpl. /ptm.

7.  Cass Everitt and Mark J. Kilgard. Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering, NVIDIA Corporation, Copyright 2002 http://developer. .

8.  D. Sim Dietrich Jr. Per-Pixel Lighting NVIDIA Corporation, Copyright 2002 http://developer. .

Программу подготовили:

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16.

Декан ФИТ НГУ,

д. ф.-м. н.