К.т.н. Чунарева А.В., Зюбина Р.В.
Национальный
авиационный университет (НАУ), Украина
АНАЛИЗ
СОВРЕМЕННЫХ МЕТОДОВ КОМПАКТНОГО ПРЕДСТАВЛЕНИЯ ИЗОБРАЖЕНИЙ
Актуальность. Важной
особенностью всех типов данных является их избыточность. Избыточность в свою
очередь зависит от типа информации. Например, для видеоданных степень
избыточности значительно выше, нежели у
изображений, а та в свою очередь больше, нежели у текстовых документов. Для
людей, которые мало разбираются в
кодировании, избыточность проявляется в качестве информации, так как
именно это улучшает качество информации,
будь то видео или фото. Однако важно то, что данная избыточность
становится достаточно емкой и дорогостоящей для хранения и передачи ее по
каналам связи. Поэтому достаточно часто возникает проблема уменьшения
избыточности данных или же их сжатия.
Постановка задачи. Задачей
данной статьи является анализ методов сжатия изображения с потерями и без
потерь, с целью определения оптимальных алгоритмов сжатия информации.
Анализ наиболее актуальных методов
сжатия изображения
Для
рассмотрения современных методов сжатия изображения нужно сначала определить
основные классы изображений. Исходя из
особенностей избыточности информации, выделяют четыре основных класса
изображений:
1.
Монохромные – это изображения в которых количество
пикселей одного цвета имеет значительное преобладание над количеством пикселей
другого цвета. Ярким примером монохромного изображения являются отсканированные
документы.
2.
Цветные изображения с малым количеством цветов из определенной
цветовой гаммы. Зачастую содержат большие области с одним цветом, также
количество пикселей одного цвета преобладает над количеством пикселей другого
цвета. К примеру: графические презентации, эскизные модели в САПР.
3.
Изображения в градациях серого. Основной характеристикой
данного класса изображений является плавное изменение яркости между соседними
пикселями. К этому классу относятся черно-белые фотографии и рентгеновские
снимки.
4.
Фотореалистичные изображения. В этом классе значения
цветовых компонент соседних пикселей мало отличаются. К фотореалистичным
изображениям относятся фотографии.
Важно
понимать, что для одних классов изображений подходят одни алгоритмы сжатия, а
для других – совсем иные.
Под понятием сжатия данных или же компрессии будем
понимать алгоритмическое преобразование данных, производимое с целью уменьшения
их объема. Компрессия применяется для более рационального использования
устройств хранения и передачи данных в современных
информационных системах и сетях. Процесс сжатия данных происходит путем
сокращения их избыточности. На данный момент существует два основных метода
сжатия с потерями и без.
Под понятием сжатия
данных без потерь будем понимать методы компрессии, при использовании
которого данные будут полностью восстановлены. Такой вид сжатия целесообразно
использовать, в тех случаях, когда важна идентичность распакованных данных и
исходных. Данный метод может использоваться при сжатии любых данных, так как он
обеспечивает абсолютное восстановление после декодирования. В основе сжатия без
потерь лежит простое преобразование одних символов в другие, более компактные.
Существует ряд алгоритмов сжатия без потерь, но наиболее известные это
кодирование Хаффмена, сжатие LZW и RLE. Далее рассмотрим особенности существующих методов сжатия
без потерь.
Алгоритм сжатия RLE (Run-lengthencoding)
или Кодирование повторов – это алгоритм сжатия данных, который работает с сериями данных, то
есть последовательностями, где один
символ повторяется несколько раз.
Изображение
в данном алгоритме строится в ряд байт по строкам растра, а собственно сжатие
происходит за счет замены повторяющихся байт на два символа: счетчик значения и
само значение. Такая замена и производит к уменьшению избыточности изображения.
Например:
55 55
55 44 44 11
11 11 11 33 – исходная
последовательность
03 55
02 44 04 11 33 – сжатая последовательность
Исследования
особенности метода показали, что данный метод
достаточно эффективен для сжатия растровых графических изображений, потому
что они содержат очень много длинных
серий повторяющихся последовательностей байт. Недостатком этого метода сжатия
изображения является маленький коэффициент сжатия и плохая компрессия
фотографий, так как при достаточно детализированной фотографии ее размер не
только не уменьшится, а очень даже наоборот увеличится в несколько раз.
Алгоритм сжатия LZW(от
имен разработчиков Lempel, Ziw,Welch)–
это метод сжатия данных, который работает с повторяющимися цепочками данных.
Растровые изображения обычно содержат довольно много таких повторений, поэтому
данный алгоритм хорошо справляется с их сжатием и восстановлением.
Процесс
сжатия сам по себе достаточно простой, так как мы последовательно считываем
символы на входе и проверяем их на
наличие совпадающих строк со строками в
предварительно созданной нами таблице. Если имеется совпадение, то
считывается следующий символ, а если нет, то заносится в поток код для
предыдущей найденной строки, добавляем строку в таблицу и повторяем поиск с начала.
Во время своего появления, этот алгоритм давал лучший коэффициент сжатия, чем
какой-либо другой метод того времени. Именно алгоритм LWZстал
одним из первых широко использоваться для сжатия изображений в компьютерах.
Исследования показали, что
достоинствами данного метода является то, что для данного метода не требует вычисления вероятностей встречаемости символов
или кодов; для декомпрессии не надо сохранять таблицу строк в файл; не вносятся
искажения в исходный графический файл, и подходит для сжатия растровых данных
любого типа. Единственным недостатком
данного метода является то, что алгоритм не проводит анализ входных данных, поэтому не оптимален.
Алгоритм Хаффмена является одним из
самых известных алгоритмов. Данный метод базируется на использовании частоты
появления одинаковых байт в изображении. Далее символам, которые часто
встречаются, сопоставляют на входе потока цепочку бит меньшей длинны, а тем,
которые редко встречаются – цепочку большей длинны.
Однако,
важно заметить, что алгоритм Хаффмена практически не применяется к изображениям
в чистом виде, а используется как составляющая более сложных алгоритмов
компрессии изображений.
Под понятием сжатия
данных с потерями будем понимать метод
компрессии данных, использование которого влечет за собой некоторое отличие
распакованных данных и исходных.
Данный
тип сжатия имеет как ряд недостатков, так и ряд преимуществ. Одним из важных
преимуществ есть возможность выбора коэффициента сжатия, на что в данном случае
значительно влияет критерий визуального восприятия. При большом коэффициенте
сжатия изображение теряет свое качество, и
а при малом – ее размер практически не меняется, поэтому важно найти
компромисс между качеством и размером изображения. Так как процесс сжатия с
потерями есть необратимым, его предпочтительно не использовать для изображений,
которые в дальнейшем планируется использовать для печати в высоком качестве.
Наиболее популярными представителями алгоритмов сжатия с потерями стали JPEG и JPEG
2000.
Алгоритм JPEG разработан
в 1991 году группой экспертов в области фотографий, а в 1992 г. Был объявлен
международным стандартом в области графики. Как ранее уже упоминалось,
данный алгоритм есть необратимым, поэтому нужно изначально определиться
перед вопросом: что важнее - качество изображения или его размер. В основе данного
алгоритма лежит не поиск одинаковых элементов, как в RLE иLZW, а поиск разницы между пикселями (рис.1).
Рассмотрим
алгоритм работы кодера JPEG. Процесс работы данного алгоритма состоит из
четырех основных этапов:
1.
Препроцессинг
– на данном этапе происходит предварительная
обработка изображения, а именно
преобразование графического изображения из компонентного вида в
цветоразностное, яркостное представление. Также на данном этапе изображение
разбивается намеленькие блоки и происходит сдвиг основания значений цвета
относительно нуля.
1.
Дискретное
косинусное преобразование (ДКП) – используется для
преобразования изображения от его пространственного вида к спектральному виду.
Изображение разбивается на квадраты 8x8 и преобразуются по-отдельности.
2.
Следующий этап -
это округление, в результате
которого уменьшается объем информации, необходимый для хранения матрицы ДКП.
Для этого используется матрица округления, для достижения оптимальных
результатов рекомендуется использовать матрицы округления рекомендованные ISO.
3.
Сжатие –
это последний этап работы алгоритма JPG.
Сначала значения в левом верхнем углу результирующей матрицы заменяется на
относительное, затем применяется алгоритмLZW и
алгоритм Хаффмена.
Таким
образом алгоритм JPG получил широкое
распространение в результате достаточно высокой степени сжатия и простоте
реализации.
Алгоритм JPEG
2000 – это графический формат, который использует
вейвлет-преобразования, основанный на представлении сигнала в виде суперпозиции
базовых функций.
Базовая
схема работы данного алгоритма очень схожа со схемой JPEG,
правда она более усовершенствована и дополнена разработчиками (рис.2).
Основные
отличия JPEG и JPEG
2000 заключаются в следующем:
1.
Вместо дискретного косинусного преобразования
используется дискретное вейвлет преобразование.
2.
Вместо кода Хаффмена используется
арифметическое сжатие.
3.
В алгоритме заложено управление качеством областей
изображения.
4.
Явно не используется дискретизация компонентов Uи V
для преобразования цветовых пространств.
Рис.2 Блок структурная
схема работы алгоритма JPEG
2000
Алгоритм
JPEG 2000 имеет целый ряд преимуществ по
сравнению с JPEG, а именно: большая степень сжатия за
счет дискретного вейвлет-преобразования; возможность масштабирования
изображений; свободный доступ к кодовому потоку, а также гибкий формат файла и
другие.
Вывод
Поток информационных данных об изображении имеет существенное количество
излишней информации, которая может быть устранена практически без заметных для глаза
искажений. При этом различают два типа избыточности статистическую и
визуальную, которая снимается в зависимости от выбранного метода кодирования.
Данные исследования методов сжатия изображений показали, что для того,
чтобы корректно оценивать алгоритмы сжатия и восстановления изображений необходимо
задать определенные критерии:
-
значения
коэффициента
сжатия.
-
класс изображений, на который ориентирован алгоритм
-
симметричность - характеризует ресурсоемкость процессов кодирования и
декодирования (при этом наиболее важным является отношение времени кодирования
ко времени декодирования);
-
потери качества (у большинства алгоритмов сжатия с потерей информации
-
существует возможность изменения коэффициента сжатия);
-
характерные особенности алгоритма и изображений, к которым его применяют.
Литература:
1.
Юдін О.К. Кодування в інформаційно-комунікаційних
мережах: – Монографія. - К.: НАУ, 2007. — С. 308
2.
Д. Сэломон. Сжатие данных, изображения и
звука — М.: Техносфера, 2004. — С. 368
3.
Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы
сжатия данных. Устройство архиваторов, сжатие изображений и видео —
Диалог-МИФИ, 2002. — С. 384