Разработка методики сравнительного анализа алгоритмов сжатия информации

Дистанционное зондирование Земли (ДЗЗ) является одним из самых перспективных способов получения геопространственной информации среди различных видов космической деятельности. Спутник, делающий снимки поверхности Земли в разных частотных диапазонах, передает информацию на Землю, которая затем помещается в хранилище изображений, откуда используется геоинформационными системами для разных целей. При этом постоянный рост объемов телеметрической информации (ТМИ) в системах дистанционного зондирования земли, предъявляемые требования к скорости, качеству и объему передаваемой информации от искусственных спутников Земли к наземным комплексам управления (НКУ) приводят к дополнительным сложностям при оперативной обработке данных [10]. Примерно та же ситуация наблюдается и при передаче изображений по каналам связи с ограниченной пропускной способностью, которой не хватает,

Разработка методики сравнительного анализа алгоритмов сжатия информации

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

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

Сжатие – это, обычно, способ наиболее рационального представления данных, точнее, их кодирование, проводимое с целью уменьшения объема средств хранения данных. Все методы сжатия можно разделить на две основные группы – без потерь и с потерями. Методы сжатия без потерь сжимают и восстанавливают данные без искажений, т. е. закодированные данные могут быть полностью восстановлены с точностью до бита. Существует много разных практических методов сжатия без потерь информации, которые, как правило, имеют разную эффективность для разных типов данных и разных их объемов. Можно упомянуть следующую основную совокупность алгоритмов сжатия без потерь: алгоритмы RLE и Хаффмана, а также алгоритмы, основанные на методах Лемпеля – Зива – Уэлча (LZW) и арифметического кодирования [2; 3].

Современные тенденции развития компьютерных и информационных технологий

Сжатие данных с потерями – это метод компрессии данных, при использовании которого сжатые данные отличаются от исходных, однако степень отличия не является существенной с точки зрения их дальнейшего использования. Чаще всего методы сжатия с потерями используется для сжатия аналоговых (аудио, видео) и графических данных, но они никогда не используется при архивации. Наиболее известные алгоритмы сжатия с потерями – это алгоритм JPEG с использованием дискретного косинусного преобразования и алгоритм JPEG2000 с использованием дискретного вейвлет-преобразования, а также алгоритм, основанный на фрактальном методе сжатия и рекурсивный (волновой) алгоритм.

Поскольку статья ориентирована на работу с видеоснимками, получаемыми с КА дистанционного зондирования Земли (КА ДЗЗ), то согласно [7; 9] с точки зрения оперативности их нужно обрабатывать алгоритмами сжатия с потерями.

Анализ типовых алгоритмов сжатия с потерями

Алгоритм JPEG

Алгоритм был разработан фирмой Joint Photographic Experts Group, целью которой было создание метода сжатия с необходимым качеством фотографических изображений до размеров, приемлемых для передачи по различным каналам и сетям [9]. При использовании алгоритма удаление избыточной информации приводит к уменьшению размера изображения, которое занимает гораздо меньше места, чем исходное. Тем самым достигается компромисс между размером и качеством изображений.

Алгоритм оперирует с областями изображений размером 8×8 пикселей, на которых яркость и цвет меняются сравнительно плавно, за счет чего и осуществляется компрессия.

Сжатие при использовании алгоритма JPEG происходит в несколько этапов.

Дискретизация. На этом шаге происходит преобразование изображения из цветового пространства в яркостное пространство.

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

Дискретное косинусное преобразование (ДКП). Этот этап является ключевым, так как именно в этот момент происходит потеря данных. ДКП представляет собой разновидность преобразования Фурье. Суть данного преобразования состоит в том, что оно позволяет от пространственного представления изображения переходить к спектральному представлению и наоборот. Каждая компонента разбивается на блоки по 8×8 пикселей, которые называются единицами данных. После разбиения для каждой матрицы отдельно применяют ДКП. В итоге матрица пикселей преобразуется в матрицу частотных коэффициентов (сумму косинусных функций) соответствующего размера [9].

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

Разработка методики сравнительного анализа алгоритмов сжатия информации

Кодирование Хаффмана . На этой стадии кодируются коэффициенты дискретизации, при этом исключаются серии нулевых значений. Полученный новый блок 8×8 после процедуры квантования сканируется по зигзагу и переводится в 64-элементный вектор.

Таким образом, получаем вектор, в котором происходит сортировка пространственной частоты: в начале вектора находятся коэффициенты матрицы, соответствующие низким частотам, в конце – высоким. Полученный вектор с последовательностью нулей кодируется с помощью алгоритма RLE [2; 3], образованные пары кодируются по Хаффману.

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

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

Отрицательные стороны алгоритма: при высокой степени сжатия изображение распадается на блоки пикселей размером 8×8, при этом в некоторых случаях проявляется так называемый эффект Гиббса [1; 5]. Кроме того, этот формат сжатия имеет ограничения на полосу пропускания.

Коэффициенты сжатия: 2-200 (задается пользователем).

Алгоритм JPEG-2000

Данный алгоритм разработан той же группой экспертов, что и алгоритм JPEG, и является его усовершенствованной альтернативой.

Основные отличия алгоритма JPEG-2000 от JPEG заключаются в следующем [8].

• 1.    Лучшее качество изображения при сильной степени сжатия.

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

• 3.    Алгоритм основан на вейвлет-преобразовании [2; 3]. Вместо дискретного косинусного преобразования (ДКП) используется дискретное вейвлет-преобразование, которое имеет ряд преимуществ по сравнению с ДКП, а именно: увеличение коэффициента сжатия и избавление от блочной структуры изображения (8×8), возникающей в сильно сжатых JPEG-файлах. Вейвлет-преобразование представляет собой разложение входного сигнала в виде совокупности волновых пакетов – так называемых вейвлетов.

• 4.    Бит-ориентированное арифметическое кодирование, при котором стало возможным повысить степень сжатия за счет применения данного алгоритма [3; 8].

• 5.    Алгоритм может осуществлять сжатие как с потерями, так и без потерь, что делает его универсальным.

• 6.    Поддержка сжатия однобитных (2-цветных) изображений.

Алгоритм сжатия JPEG-2000 ориентирован на полноцветные 24-битные изображения и изображения в градациях серого цвета без резких переходов цветов. Широко используется в цифровых системах видеонаблюдения.

Положительные стороны: алгоритм JPEG-2000 превосходит по эффективности своего предшественника примерно в 2 раза при сжатии с потерями и на 5…20 % при сжатии без потерь. Позволяет получить качественное изображение при больших коэффициентах

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

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

Коэффициент сжатия: 2-200 (задается пользователем).

Алгоритм фрактального сжатия

Данный алгоритм сжатия основан на устранении избыточности информации, возникающей в изображениях вследствие их самоподобия. Название алгоритма происходит от понятия «фрактал», то есть математический объект, обладающий свойством самоподобия [5; 8].

Алгоритм сжатия включает в себя следующие этапы.

• 1.    Изображение делится на небольшие неперекрывающиеся квадратные области, которые называются ранговыми блоками.

• 2.    Строится пул всех возможных перекрывающихся блоков, которые по своим размерам превосходят ранговые в четыре раза. Такие блоки называются доменными.

• 3.    Далее каждый ранговый блок сопоставляется с доменным блоком, чтобы найти такое преобразование, которое делает доменный блок наиболее похожим на текущий ранговый.

• 4.    Пара «преобразование – доменный блок» ставится в соответствие ранговому блоку. В итоге в сжатом изображении сохраняются коэффициенты преобразования и координаты доменного блока. Метод фрактального сжатия ориентирован на полноцветные изображения и изображения в градациях серого цвета без резких цветовых переходов.

Преимущества алгоритма : высокие коэффициенты сжатия, малое время, застрачиваемое на декомпрессию, широкие возможности в выборе параметров сжатия и возможность свободно масштабировать изображение при распаковке, увеличивая его в 2…4 раза.

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

Коэффициенты сжатия: 2-2000 раз.

Рекурсивный (волновой) алгоритм

Название алгоритма происходит от уже упоминавшегося английского слова wavelet, или, если переводить дословно, «волновое сжатие». В отличие от алгоритмов JPEG и фрактального данный алгоритм не оперирует блоками пикселей размером, например, 8×8. В работе алгоритма заложены идеи использования когерентности областей. А сама идея алгоритма заключается в сохранении в файле разницы в виде числа между средними значениями соседних блоков изображения, которая обычно принимает значения, близкие к нулю.

Ориентирован алгоритм на цветные и черно-белые изображения с плавными цветными переходами.

Преимущества алгоритма: легко позволяет реализовать возможность постепенного «проявления» изображения при передаче его по сети. При этом можно применять wavelet-преобразование 4 и более раз.

Недостатки алгоритма: при попытке задать большой коэффициент сжатия проявляется «лестничный эффект» – ступеньки разной яркости размером в несколько пикселей, а при более высокой степени сжатия изображение распадается на отдельные блоки.

Коэффициенты компрессии: 2-200 (задается пользователем).

Разработка методики сравнительного анализа алгоритмов сжатия информации

Основы методики сравнительного анализа алгоритмов сжатия информации

Постановка задачи

Дано:

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

Требуется:

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

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

• 3.    Оценить влияние степени сжатия информации на скорость или время ее пересылки в системах передачи информации на большие расстояния.

В общем виде вербальная формулировка решения задачи разработки методики анализа алгоритмов сжатия информации сводится к следующему.

Шаг 1. Определить необходимый метод сжатия из двух основных групп – без потерь и с потерями

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

Шаг 2. Сравнительный анализ

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

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

Таблица1

Сравнительная характеристика алгоритмов сжатия

Алгоритмы сжатия	Коэффициенты сжатия (разы)	Количество бит, определяющих цветность изображения	Потери
Групповое кодирование (RLE)	32, 2, 0.5	3, 4-битные	Нет

Современные тенденции развития компьютерных и информационных технологий

Окончание таблицы1

LZW	100, 7, 4	1…8-битные	Нет
Хаффмана	8, 3, 1	1-битные	Нет
Рекурсивное сжатие (Wavelet)	до 20	серые	Да
JPEG	до 200	24-битные	Да
JPEG-2000	до 200	24-битные	Да
Фрактальный	до 2000	24-битные	Да

Из таблицы 1 видно, что при компрессии изображений с 16 миллионами цветов (24 бита) ни один формат не приведет к созданию файла меньшего размера, чем у алгоритмов JPEG, JPEG-2000 и фрактального метода сжатия. Эти методы сжатия с потерей данных жертвуют качеством изображения для сохранения максимально возможного пространства памяти. Преимуществом данных алгоритмов является то, что можно управлять количеством данных, которое может потеряться во время операции сохранения. При этом у пользователя появляется возможность самому устанавливать коэффициент сжатия, и таким образом решать насколько важна информация, которая может потеряться. Поэтому, например, алгоритм JPEG лучше всего использовать при сжатии изображений с непрерывным тоном (изображения, в которых цветовой контраст между ближайшими пикселями невелик). Поскольку алгоритм JPEG – не самый лучший вариант для сжатия снимков с экрана, векторных рисунков и других высококонтрастных изображений, эти изображения лучше обрабатывать в формате TIFF, используя алгоритм LZW-сжатия. Также из таблицы видно, что большой коэффициент сжатия достигается при использовании фрактального метода сжатия изображений, поскольку остальные методы либо не дают достаточно высокого коэффициента сжатия, либо ориентированы на изображения с минимальным количеством цветов (меньшее количество бит).

Интересно сравнить алгоритмы компрессии графической информации JPEG и фрактального метода сжатия. Оба этих алгоритма ориентированы на 8-битные изображения (в градациях серого) и 24-битные полноцветные изображения. Сжатие происходит с потерями при очень близких значениях коэффициентов сжатия. Рассматриваемые методы компрессии дают возможность пользователю увеличивать степень сжатия за счет увеличения потерь. Кроме того, алгоритмы очень хорошо распараллеливаются.

Различие алгоритмов заключается в степени асимметричности их работы по времени, которое они затрачивают на архивацию и разархивацию. Так, фрактальный алгоритм сжимает в сотни и даже тысячи раз дольше, чем алгоритм JPEG, а распаковка изображения, наоборот, происходит в 5…10 раз быстрее. Поэтому если изображение необходимо сжать только один раз, а передать по сети и распаковать множество раз, то выгодней использовать фрактальный алгоритм. Если важно качество изображения, особенно когда его необходимо распечатать, то алгоритм JPEG уступает фрактальному сжатию, так как использует разложение изображения по косинусоидальным функциям, потери при применении которого (даже при заданных минимальных коэффициентах) проявляются в виде эффекта Гиббса [8]. Несмотря на превосходство фрактального алгоритма над алгоритмом JPEG, замена последнего в практическом применении произойдет еще не скоро. Сегодня фрактальный алгоритм активно применяется только в области приложений мультимедиа, компьютерных играх и др.

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

Разработка методики сравнительного анализа алгоритмов сжатия информации тод, использующий алгоритм JPEG-2000, основанный на вейвлет-преобразованиях. Важной спецификой рассмотренных методов компрессии является то, что они малоэффективны либо даже неприменимы для гиперспектральных изображений [6].

В целом использование компрессии позволяет:

• –    снизить стоимость систем хранения и передачи информации;

• –    увеличить количество каналов связи при сохранении заданной скорости передачи;

• –    хранить больший объем информации;

• –    сравнивать хранимую информацию (одинаковые участки данных, сжатые одним и тем же образом, не различаются) [1; 2].

Методы сжатия с потерями позволяют достичь коэффициента высокого сжатия без значительного ухудшения качества изображения, но не позволяют воспроизвести первоначальное изображение с точностью до пиксела. Широко известны сжатия с потерями в форматах алгоритма JPEG для неподвижных изображений. Проще обстоит дело с растровыми данными. Человеческий глаз не воспринимает все тонкие оттенки цвета в обычном растровом изображении. Таким образом, некоторые детали могут быть опущены без видимого нарушения информационного содержания картинки.

Шаг 3 . Определение используемого набора характеристик алгоритмов сжатия данных

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

Коэффициент сжатия ( K _сж ) – основная характеристика алгоритма сжатия.

Коэффициент сжатия определяется через отношение объема исходных данных Q _иcx к объему сжатых данных Q _сж :

K _сж = Q _иcx / Q _cж.

Степень сжатия k характеризует относительное уменьшение объема данных:

k = {( Q _исх – Q _сж) / Q _исх} × 100 %.

Коэффициент сжатия K _сж и степень сжатия k характеризуют один и тот же критерий эффективности, но имеют разную размерность.

Скорость сжатия V _с определяется по формуле

Vс = Qисх/ tсж где tcж – время сжатия исходных данных.

Скорость распаковки V _p определяется по формуле

Vр = Qисх / tр, где tp – время распаковки исходных данных.

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

Симметричность во времени (γ) – важнейшая характеристика алгоритма сжатия. Это отношение времени сжатия исходных данных ко времени распаковки:

γ = t _сж / t _р..

Симметричность показывает область применения алгоритма.

Некоторые алгоритмы (например, фрактальный алгоритм сжатия изображений) обеспечивают большой коэффициент сжатия, но затрачивают много времени на сжатие изо-

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

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

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

Расчет оценки влияния степени сжатия информации на время передачи её между объектами (например, между центром обработки данных (ЦОД) и системой хранения данных (СХД))

При расчете принимаем во внимание, что 1 байт = 8 бит, тогда 1 терабайт = 8×1012× 10 ⁹ = 8096 × 10 ⁹ бит.

Дано:

• 1.    Пусть исходный объем данных Q _исх составляет 50 Тбайт.

• 2.    Пропускная способность канала q передачи данных – 10 Гбит/с.

• 3.    Коэффициент сжатия K _сж – 10 раз.

Требуется:

• 1.    Определить объем данных сжатой информации Q _cж .

• 2.    Определить время пересылки Т _исх и Т _сж объемов данных Q _исх и Q _cж из ЦОДавСХД.

• 3.    Сравнить время пересылки Q _исх и Q _cж данных.

Расчет начинается с определения объемасжатой информации Q _cж :

Q _cж = Q _исх/ K _сж= 50 / 10 = 5 Тбайт.

В общем случае расчет времени пересылки информации Т определяется отношением объема данных Q к пропускной способности канала q :

T = Q / q .

Тогда

Т _исх = Q _исх / q = (50 × 8096 × 10⁹) / (10 × 10⁹) = 5 × 8096 с. ≈ 11,2 ч.

Т _сж = Q _сж / q = (5 × 8096 × 10⁹) / (10 × 10⁹) = 0,5 × 8096 с. ≈ 1,12 ч.

Время пересылки сжатого объема Q _сж в 10 раз быстрее исходного Q _исх.

Расчет проводился с учетом предположения об одноканальной передаче данных. При многоканальной передаче это время существенно уменьшится.

Заключение

Методика решения задачи анализа алгоритмов сжатия информации сводится к детализации и конкретизации шагов в виде следующих этапов.

Этап 1. Анализ и выбор метода сжатия из двух основных групп: без потерь и с потерями.

Этап 2. Оценка положительных и отрицательных сторон соответствующего алгоритма для сжатия информации.

Этап 3. Учет целевого назначения необходимого класса изображений, их размера и других параметров.

Этап 4. Сравнение характеристик алгоритмов сжатия изображений (таблица1).

Разработка методики сравнительного анализа алгоритмов сжатия информации

Этап 5. Оценка эффективностиалгоритмов сжатия по следующим численным показателям: – коэффициент сжатия ( K _сж );

– степень сжатия ( k );

– скорость сжатия ( V _с );

– скорость распаковки ( V _p );

– симметричность работы во времени (γ).

Этап 6. Оценка времени пересылки данных между объектами.

Этап 7. Окончательный выбор алгоритма сжатия информации.

Предложенная методика выбора алгоритма сжатия снимков изображений с КА ДЗЗ позволяет:

• –    использовать сжатие с потерями и возможность за счет потерь регулировать качество изображений (алгоритмы JPEG или JPEG-2000);

  –ориентироваться на фотореалистичные изображения с 16 миллионами цветов (24 бита);

• –    использовать избыточность изображений в двух измерениях;

• –    обрабатывать существенно несимметричные алгоритмы;

• –    за счет комплексных и комбинированных подходов увеличивать степень сжатия изображений.

В заключение отметим, что статья имеет научно-прикладную направленность и ориентирована на лиц, занимающихся проектированием и эксплуатацией упомянутых систем.