Алгоритмические основы мультимедийных технологий. Лекция 1

Отчетность
Экзамен
Лекций – 18 ч (9 шт)
Практика – 34 ч – ФОМ -180510
18 ч – ФОМ- 181001

Темы
Введение. Основные понятия
Статистические методы сжатия данных
Словарные методы
Вейвлетные методы сжатия
Сжатие изображений
Сжатие видео
Сжатие аудио
Практика – OpenCV

Введение
Проблема коммуникации
Основные понятия

Проблема коммуникации
«Главное свойство системы связи заключается в том, что она должна точно или приближенно воспроизвести в определенной точке пространства и времени некоторое сообщение, выбранное в другой точке. Обычно, это сообщение имеет какой-то смысл, однако это совершенно неважно для решения поставленной и инженерной задачи. Самое главное заключается в том, что посылаемое сообщение выбирается из некоторого семейства возможных сообщений»
Клод Шеннон, 1948 г.

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

Основные понятия
Система связи
Шум
Кодирование источника

Кодирование источника
Мера компактности представления данных – информационная энтропия
Информационная энтропия - мера непредсказуемости появления какого-либо символа первичного алфавита.

Определение Информационной энтропии по Шеннону
Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:
мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.

Формула энтропии

Пример

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

Избыточность данных
Текст
Код ASCII является избыточным, т.к. вероятности появления букв в тексте разная
Если зашифровать часто встречающиеся буквы коротким кодом, а редкие буквы – длинным, то уберем избыточность
Изображения
Есть основные цвета и дополнительные, а кодируются одинаково – избыточность
Соседние пиксели обычно имеют близкие цвета - избыточность

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

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

Термины
Симметричное сжатие – это когда и кодер, и декодер ис­пользуют один и тот же базовый алгоритм, но используют его в противоположных направлениях.

Термины

Тест
Что предложил Шеннон для решения проблемы передачи информации через зашумленный канал?
Белый шум не имеет избыточности. Можно ли его сжать?
Исходный алфавит представляет 4 символа TGRD c вероятностями появления 0,80; 0,10; 0,05; 0,05. Рассчитайте минимальное количество бит, необходимое для кодирования следующей строки TGTGTTTRDD