КОНСПЕКТ ЛЕКЦИЙ
МОЛОДЕЖИ И СПОРТА УКРАИНЫ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ,
Запорожский национальный технический университет
Кафедра защиты информации
по дисциплине
«Современные методы преобразования и сжатия информации»
для студентов специальности 8.160103 – «Системы защиты от несанкционированного доступа» всех форм обучения
Конспект лекций по дисциплине «Современные методы преобразования и сжатия информации» для студентов специальности 8.160103 – «Системы защиты от несанкционированного доступа» всех форм обучения. Составители: С.Н. Романенко, Запорожье, ЗНТУ, 2012.
Составили: доц., к.ф.-м.н. С.Н. Романенко
Ответственный за выпуск: доц., к.ф.-м.н. С.Н. Романенко
Рецензент: проф., д.т.н. Л.М. Карпуков
УТВЕРЖДЕНО
На заседании кафедры «Защита информации»
Протокол № от мая 2012 г.
Развитие цифрового телевидения, цифровой фотографии, систем цифровой передачи видеосигналов по стандартным телефонным каналам делают все более актуальной задачу компактного представления изображений в цифровой форме. Количество бит, необходимое для хранения стандартного изображения весьма велико и ограничивает возможность использования графической информации в системах обработки и передачи информации.
|
|
Рассмотрим, например, передачу данных по телефонному каналу с помощью стандартного модема со скоростью 33600 бит/с. Если необходимо передать изображение размером 240 на 352 точек, и для представления каждой точки необходимо 3 байта, то, нетрудно подсчитать, что на передачу одного изображения потребуется около минуты. В то же время, уже существуют и зарегистрированы в качестве международных стандартов алгоритмы сжатия изображений, позволяющие использовать телефонный канал для проведения видеоконференции.
В качестве второго примера рассмотрим запись подвижного изображения (видеосигнала) на компакт-диски. Одна секунда полноэкранного видеофильма с разрешением 480 на 720 точек при записи со скоростью 30 кадров в секунду потребует 20,736 Мбайт. Таким образом, только 31с фильма может быть записана на диск ёмкостью 650 Мбайт. Использование современных алгоритмов сжатия подвижных изображений позволяет записать на такой компакт-диск 74-минутный фильм.
Системы сжатия изображений можно разделить на два больших класса:
- сжатие изображений без потери качества,
- сжатие с потерей качества.
При сжатии без потерь восстановленные на приемной стороне данные в точности совпадают с входным сигналом кодера. Для сжатия изображений без потерь можно использовать известные из теории информации алгоритмы кодирования источников, в частности,
|
|
- кодирование кодом Хаффмана,
· арифметическое кодирование,
· кодирование на основе алгоритмов Зива-Лемпела и другие алгоритмы.
Кодирование с потерей качества предполагает устранение из изображения некоторых избыточных компонент, которое не ведет к существенному ухудшению качества по сравнению с исходным сигналом. Сюда относятся:
- методы сжатия изображения, основанные на кодировании коэффициентов различных преобразований (дискретное преобразование Фурье, дискретное косинусное преобразование, вейвлетная фильтрация и т.д.),
- методы сжатия во временной области (дифференциальное кодирование).
Для оценивания качества алгоритма сжатия необходимо принимать во внимание следующие его характеристики:
· эффективность кодирования (коэффициент сжатия),
· качество восстановленного изображения,
· сложность кодирования,
· задержка кодирования.
Эффективность кодирования обычно оценивается в битах на отсчет или в битах в секунду. Распространенным критерием качества при кодировании с потерями является отношение сигнал/шум (SNR) на выходе декодера
SNR =10∙log10(Einp / En) (дБ),
где Einp – энергия входного сигнала кодера, En – энергия шумового сигнала.
Под энергией шумового сигнала здесь понимается энергия разности между входным сигналом кодера и выходным сигналом декодера. Отношение сигнал/шум измеряется в децибелах. В случае обработки изображений вместо SNR часто используется пиковое отношение сигнал/шум, которое определяется по формуле
PSNR = 10∙log10(2552/ En),
где 255 – максимальное десятичное значение беззнакового 8-битового числа, соответствующего одной точке черно-белого изображения.
Рассмотрим стандартные форматы, используемые для представления цветных изображений. В цифровой форме любое изображение представляется в виде двумерного поля отсчетов (точек), называемых пикселями. Большинство цветных сканеров генерируют изображения с красной, зеленой и голубой цветовыми компонентами или так называемые изображения в формате RGB. В простейшем варианте каждому пикселю сопоставляется 3 числа, характеризующие интенсивность красной, зеленой и голубой составляющих изображения в данной точке. Таким образом, изображение описывается тремя цветовыми компонентами, каждая из которых представляет собой прямоугольный массив чисел. Значение интенсивности компоненты в одной точке характеризуется целым числом из интервала 0…255 и для ее хранения отводится 1 байт. Всего изображение размера M*N в формате RGB занимает 3 M*N байт в памяти компьютера.
В типичных изображениях в формате RGB имеется существенная корреляция между цветными компонентами и с точки зрения сжатия изображений формат RGB является заведомо избыточным. Как известно, в стандартах телевизионного вещания используется другое представление изображений, при котором также используются 3 компоненты сигнала, но эти три компоненты почти некоррелированы друг с другом. Компоненты R,G и B преобразуются в яркостную компоненту Y и две цветоразностных компоненты U и V, формата YUV.
Преобразование формата RGB в формат YUV выполняется по формулам
Y = 0.299 R + 0.587 G + 0.114 B,
U = (B - Y)0.5643+ 128,
V = (R - Y)0.7132 +128.
Обратное преобразование выполняется по формулам
G = Y - 0.714(V -128) - 0.334(U -128),
R = Y + 1.402(V -128),
B = Y + 1.772(U - 128).
В формате YUV компоненты слабо коррелированы. Более того, так как большая часть информации сосредоточена в яркостной компоненте, то мы теряем мало информации, если выполним децимацию (прореживание) компонент U и V с коэффициентом 2. При таком прореживании 4 соседние точки изображения, образующие квадрат размера 2*2, описываются 4 значениями яркостных компонент Y, одним значением компоненты U и одним значением компоненты V. Каждая из цветоразностных компонент вычисляется как округленное до ближайшего целого среднее арифметическое соответствующих четырех значений рассматриваемого квадрата. Результатом является стандартный формат YUV 4:1:1, который, как правило, является входным для большинства видеокодеров. Нетрудно подсчитать, что на квадрат 2*2 будет затрачено уже не 12, а 6 байт. Таким образом, получается сжатие в 2 раза без сколько-нибудь заметного искажения изображения.
|
|
Описанное выше представление цветных изображений в виде RGB является фактически вариантом более общей конструкции - формата BMP (от Bitmap). Этот формат, будучи одним из самых распространенных форматов хранения растровой графической информации, является стандартным для операционных систем Windows. В формате BMP изображение может храниться как без сжатия, так и со сжатием без потерь с использованием метода кодирования длинами серий. Изображения могут быть монохромными (1 бит/пиксел) или цветными (4,8,16,24 или 32 бита/пиксел).
Файл в формате BMP состоит из четырех частей:
BITMAPFILEHEADER |
BITMAPINFOHEADER |
RGBQUADS |
Pixels |
В BITMAPFILEHEADER и BITMAPINFOHEADER содержатся параметры файла и изображения, в RGBQUADS записывается цветовая палитра, а затем хранятся собственно пикселы изображения (как индексы палитры или как величины красной, зеленой и голубой составляющей цвета). Формат BITMAPFILEHEADER:
Название поля | Число байт | Комментарий |
bfType | Тип файла. Должен быть “BM”. | |
bfSize | Размер файла в байтах | |
bfReserved1 | Зарезервировано. Должно быть 0. | |
bfReserved2 | Зарезервировано. Должно быть 0. | |
BfOffBits | Расстояние в байтах от BITMAPFILEHEADER до пикселов изображения |
Формат BITMAPINFOHEADER:
Название поля | Число байт | Комментарий |
biSize | Размер структуры BITMAPINFOHEADER в байтах | |
biWidth | Ширина изображения в пикселах. | |
biHeight | Высота изображения в пикселах. | |
biPlanes | Число плоскостей на устройстве вывода. Должно быть 1. | |
biBitCount | Число бит на пиксел (1,4,8,16,24,32). | |
biCompression | Метод хранения пикселов (BI_RGB,BI_RLE8,BI_RLE4, BI_BITFIELDS). | |
biSizeImage | Размер изображения в байтах (Может быть 0, если biCompression=BI_RGB). | |
biXPelsPerMeter | Горизонтальное разрешение устройства вывода (в пикселах/метр). | |
biYPelsPerMeter | Вертикальное разрешение устройства вывода (в пикселах/метр). | |
biClrUsed | Число цветовых индексов в таблице цветов, которые используются в изображении. | |
biClrImportant | Число цветовых индексов, которые считаются важными при выводе изображения. |
Если величина biHeight положительна, то изображение записано снизу-вверх и начало изображения – левый нижний угол. Если величина biHeight отрицательна, то изображение записано сверху-вниз и начало изображения в левом нижнем углу.
|
|
Поле biCompression может принимать следующие значения:
BI_RGB (0)- формат без сжатия.
BI_RLE8 (1)- сжатие длинами серий, 8 бит/пиксел. Каждая запись состоит из 2х байтов, в первом байте хранится число цветовых индексов в серии, во втором байте цветовой индекс.
BI_RLE4 (2) - сжатие длинами серий, 4 бит/пиксел. BI_BITFIELDS (3) - изображение хранится без сжатия, цветовая таблица состоит из трех четырехбайтовых масок для выделения красной, зеленой и голубой составляющей каждого пиксела. Этот режим используется при 16 и 32 битах/пиксел
RGBQUADS состоит из четверок байт rgbBlue,rgbGreen,rgbRed,rgbReserved, которые определяют голубую, зеленую и красную составляющую цвета. Размер массива RGBQUADS зависит от числа бит на пиксел и метода сжатия.
biBitPerPixel | Значение |
Изображение монохромное. RGBQUADS содержит две четверки, определяющие цветовые компоненты “черных” и “белых” пикселов. В этом случае каждый бит массива задает один пиксел. | |
Изображение содержит до 16 цветов, в RGBQUADS записано до 256 четверок, определяющих палитру изображения. | |
В изображении до 256 цветов. RGBQUADS содержит до 256 четверок, определяющих палитру изображения. | |
До 216 цветов. Если biCompression=BI_RGB, то массив RGBQUADS пуст, на каждый пиксел изображения отводится 2 байта, в которых записаны B,G,R цветовые компоненты (5 бит/компоненту, старший бит двухбайтового слова не используется). Если biCompression=BI_BITFIELDS, то RGBQUADS состоит из трех четырехбайтовых масок, определяющих R,G,B компоненты. | |
Если biBitPerPixel=24, то массив RGBQUADS пуст и пикселы изображения хранятся в виде троек байт Blue,Green,Red. | |
Аналогично biBitPerPixel=16, только на пиксел отводится 4 байта, три байта на R,G и B, старший байт не используется. |
В настоящее время в файлах BMP изображения обычно хранятся без сжатия в формате либо 8 бит/пиксел (с палитрой), либо 24 бит/пиксел.
Пикселы изображения хранятся в файле строка за строкой. Представление каждой строки должно быть выравнено на четырехбайтовую границу. Недостающие байты заполняются нулями.