Классификация методов сжатия

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

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра информационных технологий

УТВЕРЖДАЮ

Зав. кафедрой 308

______________Шаронов А.В.

« »_________________2011 г.

Лабораторная работа

«Методы сжатия изображений»

По курсу

«Обработка аудио- и видеоинформации»

Е издание

Работу составили:

Доц., к.т.н Максимов Н.А.

Аспирант Журавлёв Ю.А.

Москва

2011

Цель работы.

Изучение алгоритмов сжатия изображений и получение практических навыков программирования.

Порядок выполнения работы.

1) Изучение теоретической части.

2) Ответы на контрольные вопросы.

3) Изучение инструкций по выполнению задания.

4) Выполнение практической части.

Теоретическая часть.

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

В данной работе сжатие будет рассматриваться применительно к изображениям.

Изображения и их структура

Изображения бывают двух основных типов: растровые и векторные.

Растровое изображение представляет собой двумерный массив (матрицу) пикселей (точек) определенного цвета. Совокупность всего множества пикселей и формирует изображение. Общее число пикселей может быть очень большим: изображение размером 800х600 пикселей, в зависимости от цветового разрешения, может занимать от 0,5 до 1,5 Мб.

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

Рассмотрим структуру файла растрового изображения на примере широко известного формата BMP(см. рис. 1).

                                           Рис . 1 Структура BMP-файла

Заголовок файла содержит идентификатор BMP- файла, его общий размер, а также зарезервированные поля.

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

       Если цветовое разрешение указано 4 или 8 бит на пиксел, то BMP-изображение всегда содержит палитру (соответственно 16 или 256 цветов). Каждый цвет обозначается тройкой RGB (интенсивности красного(R), зеленого(G) и синего(B) основных цветов) плюс один резервный канал. Поэтому палитра 256-цветного изображения будет занимать (3+1)*256=1024 байта.

       Если же цветовое разрешение составляет 15, 16, 24 или 32 бита на пиксел, то палитра не используется, и растровые данные непосредственно (в виде троек RGB или BGR) задают цвет каждого пикселя.

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

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

Классификация методов сжатия

Степень эффективности сжатия характеризуется коэффициентом сжатия, который показывет отношение объема исходных данных к объёму сжатых данных:

                                           ;                                     (1)

Если >1, то сжатие считается эффективным.

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

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

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

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

Все алгоритмы сжатия по соотношению времени на кодирование данных и на их распаковку делятся на симметричные и несимметричные.

Симметричные алгоритмы сжатия требуют одинаковое время на кодирование и распаковку данных. Несимметричные алгоритмы сжатия тратят больше времени на кодирование данных, чем на их распаковку.

В настоящее время разработано большое количество различных алгоритмов сжатия изображений: от самых простых (коэффициент сжатия k=1,1¸2) до самых изощрённых, обеспечивающих k³30. Стоит отметить, что более сложные схемы сжатия часто используют комбинацию более простых алгоритмов для достижения максимального эффекта.