Юдин А.К., Коцюба В.В., Тихонов А.Г.

Национальный Авиационный Университет, Украина

Анализ современных методов сжатия видеоизображений

1.     Вступление

Трудно переоценить роль информации в современном мире. Она пронизывает всю область жизни общества. Недаром существует высказывание: «Кто владеет информацией – владеет миром».

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

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

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

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

Задачей данной статьи является анализ современных методов сжатия видеоизображений.

Целью статьи является:

ü   выявление на базе проведенного анализа критериев влияния на формирование методов сжатия.

ü   выявление недостатков существующих методов.

ü   выявление направлений развития, относительно формирования новых критериев.

3.     Анализ

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

Алгоритм RLE

Первый вариант алгоритма

Данный алгоритм необычайно прост в реализации. Групповое кодирование — от английского Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем  вытягивается в цепочку байт по строкам рас­тра. Само сжатие в RLE происходит за счет того, что в исход­ном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных [2].

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Очевидно, одиночные или дважды (трижды) повторяющиеся символы кодировать не имеет смысла - их надо записывать в явном виде.

 

Второй вариант алгоритма

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

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Характеристики алгоритма RLE :

Степени сжатия: Первый вариант: 32, 2, 0,5. Вто­рой вариант: 64, 3, 128/129. (Лучшая, средняя, худ­шая степени) [2].

Скорость сжатия: 10 (по 10-бальной шкале) [4].

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: де­ловую и научную графику.

Симметричность: Примерно единица.

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

Алгоритм LZW

Название алгоритм получил по первым буквам фамилий его разработчиков — Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт [4].

 

 

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алго­ритмов, различающихся, например, методом поиска повторяю­щихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> «пропускаемых» байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархива­ции для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений «пропускаемых» байт просто копируются в выходной массив из входного потока. Данный алгоритм являет­ся несимметричным по времени, поскольку требует полного пе­ребора буфера при поиске одинаковых подстрок. В результате нам сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алго­ритма, в котором на <счетчик> ина <смещение> будет выделе­но по 2 байта (старший бит старшего байта счетчика — признак повтора строки / копирования потока), даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в бу­фере размером 64Кб.

Характеристики алгоритма LZW:

Степени сжатия: Примерно 1000, 4, 5/7 (Лучшее, среднее, худшее сжатие). Сжатие в 1000 раз достигается только на одноцветных изображениях разме­ром кратным примерно 7 Мб [2].

Скорость сжатия: 6-7 [4].

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

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

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

Алгоритм Хаффмана

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

Классический алгоритм Хаффмана практически не применяется к изобра­жениям в чистом виде, а используется как один из этапов ком­прессии в более сложных схемах( например JPEG). [1]

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксель). Полное назва­ние данного алгоритма CCITT Group 3. Это означает, что дан­ный алгоритм был предложен третьей группой по стандартиза­ции Международного Консультационного Комитета по Теле­графии и Телефонии (Consultative Committee International Tele­graph and Telephone). Последовательности подряд идущих чер­ных и белых точек в нем заменяются числом, равным их количе­ству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Характеристики алгоритма CCITT Group 3

Степени сжатия: лучшая стремится в пределе к 213.(3), средняя 2, в худшем случае увеличивает файл в 5 раз [2].

Скорость сжатия: 9 [4].

Класс изображений: Двуцветные черно-белые изо­бражения, в которых преобладают большие про­странства, заполненные белым цветом.

Симметричность: Близка к 1.

Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.

Анализ всех вышеописанных методом можно привести в виде таблицы 1.

Таблица 1. Сравнительные характеристики различных методов сжатия

Алгоритм

Степень сжатия

Скорость

Сжатие без потерь

Проходы

RLE

2-3

10

Да

1

LZW

6-8

6-7

Да

1

Хаффмана

3-5

9

Да

1

4.     Разработанные критерии

Координацией усилий по стандартизации методов сжатия видеоизображений традиционно занимается международная организация по стандартизации (ISO) в лице специальной груп­пы экспертов по фотографическим изображениям (JPEG), а также отделение стандартизации международного телекоммуникационного союза (ITU-Т) [3].

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

Такие показатели не удовлетворяют современным требования по сжатию видеоизображений. На сегодняшний день применяют алгоритмы сжатия с потерями, такие как JPEG, JPEG2000 и т.п. Такие методы оперируют с коэффици­ентами 10-200 раз. [2]

Однако следует отметить, что в своей структуре (см рис 1,2), такие методы используют вышеописанные методы.

Рис. 1 Структурная схема реализации алгоритма JPEG

Рис. 2 Структурная схема реализации алгоритма JPEG 2000

 

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

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

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

Исходя из этого можно сформировать такие критерии, по разработке новых и усовершенствование существующих методов:

ü     метод должен быть универсальным, то есть эффективным по отношению к любым типам данных.

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

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

 

 

5.     Выводы

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

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

 

Литература

1.     Мастрюков Д. Алгоритмы сжатия информации. // Монитор. – 1994. – №6. – с.12–17

2.     Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

3.     Семенюк В. В. Обзор стандарта JPEG2000. – СПб.:2002. - 11с

4.      Фомин А. А. Основы сжатия информации. – СПб.: СПГТУ, 1998. - 82с