Мокрый Валерий Юрьевич,

Российский государственный педагогический университет имени А.И.Герцена

ИСТОРИЧЕСКИЙ ОБЗОР РАЗВИТИЯ МЕТОДОВ СЖАТИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

Исследования алгоритмов сжатия данных, начавшись в 50 годы прошлого века, остаются сегодня одной из актуальных областей информатики. Цель фундаментальных исследований в этой области состоит в разработке стандартов сжатия информации для использования в различных устройствах и приложениях. Алгоритмы сжатия информации применяются для сокращения избыточности данных и применяются при хранении информации, передаче данных по сетям связи и обработке мультимедиа данных (графики и видео). В тестах на производительность компьютерных систем в качестве одного из критерия выступает время архивирования определенного объема данных или кодирования видео из одного формата в другой.

Первые алгоритмы сжатия информации (например, алгоритм Хаффмана), разрабатывались в 50-х годах XX века. Основой для практического применения является работа Клода Шеннона (одного из ученых, внесших вклад в развитие теории информации) по математическим основам теории связи (1948). В результате исследований в области сжатия информации сегодня известно большое количество алгоритмов сжатия данных; аппарат теории сжатия информации применяется кроме архивирования данных в других областях, например обработке изображений и разработке устройств безопасности и видеонаблюдения.  Первыми стали разрабатываться алгоритмы сжатия текстовых данных (например, алгоритм Хаффмана в 1952 году и алгоритм LZ-77 в 1977 году). Примерно тогда же начали появляться и первые устройства для хранения данных. В процессе развития средств вычислительной техники, полученные результаты стали применяться и при разработке подходов к сжатию информации других типов, потому что поняли,  что для каждого типа информации необходимо применять разные подходы к кодированию текста, звука изображений и видео.

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

Комитет JPEG (объединенная группа экспертов по обработке изображений) был сформирован в 1986 году. Результатом работы комитета является стандарт сжатия графических изображений JPEG, разработанный, в том числе и при содействии международного консультативного комитета по телеграфии и телефонии. Благодаря этому стало возможным появление цифровых фотоаппаратов (алгоритм симметричен, то есть время кодирования равно времени декодированию), сохранять свои снимки с приемлемым качеством. Алгоритмы сжатия JPEG применяются в различных случаях (кроме сжатия информации), например фотографии на веб-страницах размещаются  в формате JPEG. Но из-за того, что при задании высоких значений параметров  сжатия (коэффициента квантования и качества кодирования) увеличиваются потери в  кодировании.

Примерно в тоже время проводились разработки алгоритмов фрактального кодирования. Основателем теории фракталов считают французского и американского математика Бенуа Мандельброта. Математические основы разрабатывались Джоном Хатчинсоном (теория систем итерируемых функций и использование аффинных преобразований для построения  геометрических фракталов). Метод сжатия, основанный на передаче в файл коэффициентов преобразований вместо кодирования изображения в явном виде, стал известен благодаря работам Майкла Барнсли (разработавшего основы фрактального метода), Ювала Фишера (предложившего способ кодирования с использованием метода квадродерева). Основополагающие теоремы (теорема коллажа и теорема о сжимающих отображениях) были сформулированы в 1987 году, метод сжатия разработан и запатентован в 1993 году.  На практике фракталы (кроме сжатия изображения) применяются при создании фрактальных антенн, исследовании процессов, протекающих в атмосфере Земли и информационном пространстве.

Как в нашей стране, так и за рубежом (Waterloo Fractal Coding and Analysis Group) создаются научные сообщества и объединения, целью которых является исследование и разработка новых подходов к сжатию информации.

Еще один подход к сжатию изображений – сжатие на основе вейвлет-преобразований. Функции типа «маленькой волны» (другое название вейвлетов) возникли давно и применялись при исследовании функциональных пространств[2]. Практическое применение вейвлеты получили в последние десятилетия и используются в обработке сигналов и изображений[3]. Это направление исследований является сегодня одним из популярных (наряду с изучением алгоритмов фрактального кодирования). Теория вейвлет-преобразований использует достаточно сложный математический аппарат, в частности технику рядов Фурье и преобразование Фурье (алгоритм JPEG использует дискретное косинусное преобразование, являющееся модификацией преобразования Фурье). Известны вейвлеты Добеши, Хаара, Мейра, Котельникова-Шеннона и другие. При сжатии изображений с использованием теории вейвлетов используется дискретное преобразование Фурье (ДПФ), а для анализа сигналов – непрерывное преобразование Фурье (НПФ). ДПФ используется в стандарте сжатия графических изображений JPEG-2000.  

 Можно отметить работы Д.С.Ватолина, А.Ратушняка, М.Смирнова, В.Юкина,  Д.Шкарина. Алгоритмы сжатия графики и аспектов компьютерной графики изучаются в технологических институтах и университетах, курсы Массачусетского технологического института, Вашингтонского университета и других. В некоторых странах изучение технологических дисциплин (в том числе и фундаментальных дисциплин, относящихся к области обработки информации) поддерживается программами, разработанными правительствами государств.  Обратим внимание на  национальную программу расширенного обучения, поддерживаемую министерством развития человеческих ресурсов Индии (The Ministry of Human Resource Development). В реализации программы участвуют технологические институты в разных городах Индии.

Анализ исторического пути развития подходов к сжатию графики, образовательных программ вузов подтверждает актуальность выбранной темы исследования - «Методическая система обучения алгоритмам сжатия мультимедиа данных в условиях непрерывного обучения» и необходимость обучения алгоритмам сжатия данных не только в технических, но и в педагогических вузах[1].

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

1.    Мокрый В.Ю.  Технология обучения магистров алгоритмам сжатия мультимедиа данных// в сб. материалов конференции «Новые образовательные стратегии в современном информационном пространстве». РГПУ имени А.И.Герцена, 2011.

2.    Смоленцев И.К. Основы теории вейвлетов. Вейвлеты в MATLAB. – М.:ДМК Пресс, 2008.

3.     Штарк Г.-Г. Применение вейвлетов для ЦОС. Москва: техносфера, 2007. – 192 с. ISBN 978-5-94836-108-6.