Лекции - Технологии Мультимедиа, страница 8

Ситуация, когда файл увеличивает-43ся в два раза, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Последовательностьдействий при групповом кодировании следующая:Начиная с первой строки, программа группового кодирования просматривает значения пикселей слева направо и ищет отрезки повторяющихся пикселей. Всякий раз, когдавстречаются три или более идущих подряд пикселей с одинаковым значением, программазаменяет их парой чисел: первое число указывает длину отрезка, второе - значение пикселей.Число, определяющее длину отрезка, будем называть меткой отрезка.Графическая программа декодирует изображение, считывая сжатый файл и восстанавливая отрезки повторяющихся значений пикселей.

Заметим, что восстановленное изображение полностью совпадает с оригиналом.К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он нетребует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритмна изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.LZWСобственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародованв 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. LZW - код(Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы.

Существует довольно большое семейство LZподобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек.Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит.

Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей. Реализация алгоритма LZW жестко зафиксирована международным стандартом и Американским Национальным институтом стандартов (ANSI), однако существуют достаточно интересные его модификации, которые дают больший коэффициентсжатия некоторых специфичных типах файлов - например, на исходных текстах программ.Коэффициенты сжатия: 1/1000, 1/4, 7/5.

Коэффициент 1/1000 достигается только наодноцветных изображениях размером больше 4 Мб. Ориентирован LZW на 8-битные изображения, построенные на компьютере. Ситуация, когда алгоритм увеличивает изображение,встречается крайне редко.44Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии.

Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксельь. В начале GIF - файла находитсяпалитра. Это таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.Таким образом, этот формат можно назвать форматом без потерь лишь в том смысле,что все потери информации происходят до LZW-кодирования - при преобразовании исходной картинки в 8-битную с индексированной палитрой.Несомненным достоинством этого формата является возможность хранить в одномфайле последовательности изображений, образующих примитивную анимацию. Именно благодаря этой особенности он нашел широкое применение в Internet.Алгоритм компрессии с кодом переменной длины LZW является разновидностью алгоритма компрессии Lempel - Ziv, в котором коды переменной длиной используются для замены сочетаний, обнаруженных в исходных данных.

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

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

Если количество комбинаций, обнаруженных программой компрессии в исходном потоке данных, превышает количество образцов, которое можно было бы записать в таблицу при данном размере кода в соответствии45с алгоритмом LZW, то количество бит, предоставляемых для записи кода LZW, автоматически увеличивается на единицу.Алгоритм ХаффманаКодирование Хаффмана, вероятно, самый известный и классический метод сжатияданных.

Простота и элегантность способа сделали его на долгое время академическим фаворитом. Но коды Хаффмана имеют и практическое применение; например, статические кодыХаффмана используются на последнем этапе сжатия JPEG. Кодирование Шеннона - Фано(Shannon - Fano), довольно близкое к кодированию Хаффмана, используется как один из этапов в мощном "imploding" - алгоритме программы PKZIP.Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавитASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чащевстречаться, чем буква q, хотя мы используем для их представления одинаковое количествобит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.Использует только частоту появления одинаковых байт в изображении.

Сопоставляетсимволам входного потока, которые встречаются большее число раз, цепочку бит меньшейдлины, и напротив - встречающимся редко - цепочку большей длины. Для сбора статистикитребует двух проходов по изображению. Коэффициенты сжатия: 1/8, 2/3, 1. Требует записи вфайл таблицы соответствия кодируемых символов и кодирующих цепочек.На практике используются его разновидности. Так, в некоторых случаях резонно либоиспользовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.Близкая модификация алгоритма используется при сжатии черно-белых изображений.Последовательности подряд идущих черных и белых точек заменяются числом, равным ихколичеству с признаком цвета, а этот ряд уже, в свою очередь, сжимается по Хаффману сфиксированной таблицей.

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

Кодирующее дерево является двоичным деревом с однимлистом для каждого символа. Чтобы построить дерево, компрессор начинает с двух символовнаименьшей вероятности. Затем он объединяет их как два листа двумя ветвями в узел; этомуузлу, в свою очередь, назначается сумма двух вероятностей. Компрессор затем рассматривает этот узел вместе с оставшимися символами в списке вероятностей, и снова выбирает дванаименее вероятных элемента. Он продолжает строить и объединять узлы, пока не построитединое дерево с вероятностью корня, равной 1.Полученное дерево имеет листья с различным расстоянием от корня. Листья, которыепредставляют символы с наивысшей вероятностью, самые близкие к корню, тогда как символы с наименьшей вероятностью вынесены подальше.Для кодировки символа компрессор находит путь от корня дерева к листу символа.Предположим, что компрессор хочет закодировать букву s.

Он начинает с листа, соответствующего букве s, и переходит в родительский узел, отмечая при этом, по какой ветви онпро шел (по 0 или по 1). Он продолжает идти вверх по дереву, пока не достигнет корня. Список ветвей в обратном порядке описывает путь от корня до s: это и есть код Хаффмана дляэтого символа.Символы с большой вероятностью находятся ближе к корню, так что их коды короткие.