Реализация LZW алгоритма сжатия с использованием возможностей современных GPU

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Метод LZW алгоритма

1.1 Сжатие

1.2 Распаковка

1.3 Реализация

1.4 Графический формат GIF

1.5 Формат TIFF

2. Возможности использования современных GPU

2.1 Алгоритм

2.2 Исполнительные точки отсчёта

Заключение

Список используемой литературы

Приложение



Введение

Актуальность данной работы обусловлена большим интересом к теме "Реализация LZW алгоритма сжатия с использованием возможностей современных GPU" в современной науке. Рассмотрение вопросов связанных с данной тематикой носит как теоретическую, так и практическую значимость.

Цель работы - изучение темы "Реализация LZW алгоритма сжатия с использование возможностей современных GPU".

Задачи: 1) рассмотреть теоретические подходы к LZW алгоритму; 2) выявить основную проблему LZW алгоритма сжатия.

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

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

· положение повторяющейся цепочки символов в промежуточной таблице соответствий между исходным фиксированным алфавитом и кодирующими последовательностями;

· длина сжатого кода, соответствующего набору символов во входном потоке;

· битовый диапазон длин кодов, значения которого колеблются от 9 до 16 бит;

· размер хэш-таблицы, а также разбиение ячеек этой таблицы на жестко фиксированные и имеющие переменные значения.

В числе достоинств алгоритма LZW - использование целочисленной арифметики, возможность автоматической адаптации к качественному составу входного потока, возможность разделения и инициализации последовательностей, имеющих заранее известную структуру, использование плавающей длины байта (от 9 до N битов), экономное использование динамической памяти, и файловая независимость от таблицы соответствий между кодами и символами алфавита. Все это позволяет использовать алгоритм LZW в разных приложениях не только обособленно в качестве архиватора данных, но и в составе более сложных методов, таких как, например, методы шифрования или любые другие методы побайтовой обработки информации. Метод сжатия LZW (Lempel-Ziv-Welch) разработан в 1978 году израильтянами Лемпелом и Зивом и доработан позднее в США. Название алгоритм получил по первым буквам фамилий его разработчиков -- Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт. LZW - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных.

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



1. Метод LZW алгоритма

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам. Ядром LZW-алгоритма является словарь, содержащий все символы входного алфавита и некоторые строки из этих символов. До начала работы алгоритма в словарь входят элементы, в качестве строк содержащие каждый из символов входного алфавита. По мере работы алгоритма, встречающиеся во входном потоке цепочки символов заносятся в словарь. При этом в выходной поток заносится номер элемента словаря, содержащий строку максимальной длины, совпадающую со строкой входного потока. Словарь организован как совокупность двоичных деревьев и содержит по одному двоичному дереву на каждый символ входного алфавита. Каждый элемент словаря является в то же время вершиной одного из двоичных деревьев. Вершины деревьев являются элементами словаря, соответствующими символам входного алфавита. Каждая вершина соответствует некоторой строке, имеет одну входящую дугу и до двух выходящих. Первая из них указывает на вершину, которая соответствует строке, такой же, как данная, но на один символ длиннее (связь <равно>), вторая - на вершину, соответствующую строке, имеющей такую же длину, как данная, но отличающуюся последним символом (связь <не равно>). В каждой вершине графа содержится также один символ. Параллельно выборке символов из входного потока идет обход одного из деревьев. Алгоритм обхода следующий.

- выбирается первый символ из входного потока;

- выбирается соответствующее ему двоичное дерево в словаре;

- выбирается следующий символ из входного потока;

- далее для каждой вершины двоичного дерева если символ совпал с символом в вершине перейти к следующей вершине по связи <равно>; взять из входного потока следующий символ;

иначе перейти к следующей вершине по связи <не равно>, продолжать с тем же символом;

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

1.1 Сжатие

Процесс сжатия выглядит достаточно просто. Алгоритм сжатия выглядит следующим образом:

· Инициализация таблицы из 256 символов ASCII.

· Инициализация текущей строки пустой строкой.

· До тех пор, пока входной поток не пуст выполняется:

o Считывание следующего символа из входного файла.

· Если в таблице содержится комбинации "текущая строка+символ (под "+" имеется в виду конкатенация строк)", то выполняется:

o Проверка на наличие в таблице более крупной цепочки, начинающаяся с данной, поэтому присоединяем символ к строке.

· иначе (если текущая строка+символ не содержится в таблице но текущая строка при этом таблице.)

· Получаем код текущей строки в таблице.

· Выводим код в выходной файл.

· Добавляем комбинацию текущая строка+символ в таблицу.

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

· После выхода из цикла текущая строка не пуста, ее код тоже нужно вывести в выходной файл.

· Выводим код в выходной файл.

Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова. LZW реализован в форматах GIF и TIFF.

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

Арифметическое сжатие:

Арифметическое сжатие предполагает знание вероятностей появления во входном потоке символов входного алфавита. Символы входного алфавита располагают в некотором фиксированном порядке. Промежуток от 0 до 1 делят между символами на начальные интервалы в соответствии с величинами их вероятностей. Оптимальная ширина начального интервала для символа с вероятностью появления во входном потоке р равна -log2 p.

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

LZW + арифметическое сжатие:

Аналогично тому, как в алгоритмах LZH и LZARI выходной поток алгоритма LZSS дожимается статистическими методами, можно попытаться дожать выходной поток LZW-алгоритма арифметическим кодированием. Входной алфавит арифметического кодирования в этом случае будет переменным, его мощность будет колебаться от мощности входного алфавита LZW-алгоритма до размера словаря LZW-алгоритма.



Зависимости степени сжатия от уровня адаптивности.

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

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

Первой вещью, которую мы делаем при LZW-сжатии, является инициализация нашей цепочки символов. Чтобы сделать это, необходимо выбрать код размера (количество бит) и знать, сколько возможных значений могут принимать наши символы. Давайте положим код размера равным 12 битам, что означает возможность запоминания 0FFF, или 4096, элементов в нашей таблице цепочек. Давайте также предположим, что мы имеем 32 возможных различных символа. (Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела.) Чтобы инициализировать таблицу, мы установим соответствие кода #0 символу #0, кода #1 символу #1, и т.д., до кода #31 и символа #31. На самом деле мы указали, что каждый код от 0 до 31 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством.

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

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



Следует отметить, что в целях экономии памяти ЭВМ таблицу цепочек можно эффективно представлять, учитывая следующую ее особенность: если, например, цепочка ASDFK входит в таблицу цепочек, то ASDF тоже входит в нее. Это обстоятельство наводит на мысль, что вместо запоминания в таблице всей цепочки, достаточно запомнить код для ASDF, за которым следует замыкающий символ K.

Для повышения степени сжатия изображений данным методом часто используется одна "хитрость" реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значений, например 12 12 12 … или 32 32 32 … и т. П. Их непосредственное сжатие будет генерировать выходной код 12 12 258 и т.д.

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

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код - это 12, которому соответствует цвет 12. Затем читает код 258, но этого кода в его таблице нет. Такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, т.е. 12. Поэтому он добавит в свою таблицу строку 12 12 с кодом 258, а в выходной поток поместит 12 12. И так может быть раскодирована вся цепочка кодов.

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

Работа LZW декодирования.

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

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

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

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

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



1.2 Распаковка

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

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

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД

вывести СТАРЫЙ_КОД

WHILE входной поток не пуст DO

читать НОВЫЙ_КОД

СТРОКА = перевести НОВЫЙ_КОД

вывести СТРОКУ

СИМВОЛ = первый символ СТРОКИ

добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ

СТАРЫЙ_КОД = НОВЫЙ_КОД

END of WHILE



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

Входные коды: / W E D 256 E 260 261 257 B 260 T

Вход	СТАРЫЙ КОД	СТРОКА	СИМВОЛ	Новый вход таблицы
НОВЫЙ КОД		Выход
/	/	/
W	/	W	W	256 = /W
E	W	E	E	257 = WE
D	E	D	D	258 = ED
256	D	/W	/	259 = D/
E	256	E	E	260 = /WE
260	E	/WE	/	261 = E/
261	260	E/	E	262 = /WEE
257	261	WE	W	263 = E/W
B	257	B	B	264 = WEB
260	B	/WE	/	265 = B/
T	260	T	T	266 = /WET

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.

Входная строка: …JOEYNJOEYNJOEY…

Вход(символы)	Выход(коды)	Новые коды и соотв. Строки
JOEYN	288 = JOEY	300 = JOEYN
A	N	301 = NA
.	.	.
.	.	.
.	.	.
JOEYNJ	300 = JOEYN	400 = JOEYNJ
JOEYNJO	400	401 = JOEYNJO

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД

вывести СТАРЫЙ_КОД

СИМВОЛ = СТАРЫЙ_КОД

WHILE входной поток не пуст DO

читать НОВЫЙ_КОД

IF NOT в таблице перевода НОВЫЙ_КОД THEN

СТРОКА = перевести СТАРЫЙ_КОД

СТРОКА = СТРОКА+СИМВОЛ

ELSE

СТРОКА = перевести НОВЫЙ_КОД

END of IF

вывести СТРОКУ

СИМВОЛ = первый символ СТРОКИ

добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ

СТАРЫЙ_КОД = НОВЫЙ_КОД

END of WHILE

Рис. 6 Модифицированный алгоритм распаковки

1.3 Реализация

Алгоритм реализован как приложение Windows 95/98 на языке программирования C++. Структурная схема реализации приведена на рисунке. Данный вариант имеет семь логически независимых блоков, отвечающих за инициализацию хэшей и стеков, передачу, чтение, запись и буферизацию байтов данных, дополнение, очистку стеков и динамически выделяемой памяти, рекурсивный поиск по хэшу и рекурсивное кодирование повторяющихся данных хэш-таблицы (т.е. сжатие второго уровня, происходящее одновременно со сжатием основного потока, благодаря чему объем используемой памяти не только сокращается, но и становится заведомо известным). Передача кодируемых байтов между блоками осуществляется как с помощью простого вызова соответствующих функций, так и с помощью классов-интерфейсов, преобразующих восьмибитовые байты в N-битовые.

Проведенное тестирование разработанного модуля показало, что практическая реализация алгоритма LZW по качеству сопоставима с самыми современными программами сжатия информации.

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.

Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.

Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например, в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ "E". Наконец, код 256 хранится как "/" плюс "W".

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов: code_value[i], prefix_code[i] и append_character[i].

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

Хэш-функция, использованная в этой программе - простая "xor"-типа кэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице - меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.

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

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

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

Алгоритм LZW имеет несколько особенностей своей реализации в формате сжатия изображений gif. Первая особенность - это переменный размер кода таблицы цепочек, который не может превышать 12 бит, т.е. не превышать числа 4095. Вторая особенность состоит в использовании двух специальных кодов - это код обновления (реинициализации) таблицы цепочек, и код завершения потока символов.

В самом начале своей работы алгоритм определяет количество цветов, используемых в изображении. В случае GIF их максимум может быть 256, т.к. любое изображение, даже с большим набором цветов преобразуется в 256 цветовое пространство. Минимум может быть 2 цвета. Если используется только два цвета, то начальный размер кодов в таблице равен 3 битам. Причем коду 0 ставится цвет 0, а коду 1 - цвет 1. Коды 4 и 5 соответствуют коду очистки таблицы и коду. При большем количестве цветов размер кода таблицы равен числу бит N, приходящихся на один пиксел. При этом специальные коды равны и. Начальный размер кодов в таблице записывается в заголовок GIF файла.

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

Разработчики формата GIF ограничили максимальный размер кодов в таблице 12 битами. Это значит, что когда код достигает значения, то размер увеличивать уже нельзя. Но в то же время и размер кодов становится больше 12 бит.

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



Таблица: Основные варианты LZ-схемы.

Имя	Авторы	Отличия
LZ77	Ziv and Lempel [1977]	Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов.
LZR	Roden et al [1981]	Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов.
LZSS	Bell [1986]	Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов.
LZB	Bell [1987]	Аналогично LZSS, но для указателей применяется разное кодирование.
LZH	Brent [1987]	Аналогично LZSS, но на втором шаге для указателей применяется кодирование Хаффмана.
LZ78	Ziv and Lempel [1978]	Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку.
LZW	Welch [1984]	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.
LZC	Thomas et al [1985]	Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.
LZT	Tischer [1987]	Аналогично LZC, но фразы помещаются в LRU-список.
LZMW	Miller and Wegman [1984]	Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.
LZJ	Jakobsson [1985]	Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.
LZFG	Fiala and Greene [1989]	Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна.

Термин "LZ-схемы" происходят от имен их изобретателей. Обычно каждый следующий рассматриваемый вариант есть улучшение более раннего.

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



Блок-схема алгоритма LZW декодирования.

Блок-схема алгоритма LZW сжатия.



1.4 Графический формат GIF

Сотрудник компании CompuServe Inc. Боб Берри (Bob Berry), взял LZW в качестве основы для созданного им в 1987 году принципиально нового графического формата GIF (Graphic Interchange Format). Следует отметить, что созданная Терри Уэлчем компания Unisys, которой и принадлежали авторские права на алгоритм LZW, взимала плату за его использование только с производителей аппаратного обеспечения для компьютеров, в котором применялся данный стандарт, например с изготовителей модемов. Разработчики программного обеспечения "комиссионными сборами" не облагались.

Однако зимой 1994 года компания Unisys, начавшая испытывать финансовые проблемы, объявила LZW коммерческим стандартом, потребовав оплаты за его использование. Это автоматически сделало GIF единственным в мире "платным" графическим форматом, что вызвало волну недовольства среди пользователей Интернета, поскольку практически на всех современных web-сайтах, а также в 90% рекламных изображений так или иначе применяются элементы GIF. Тем не менее GIF чрезвычайно широко используется в Интернете и сейчас, причем пользователи не обязаны оплачивать кому бы то ни было возможность опубликовать во Всемирной сети изображение в данном формате, так как упомянутые выше финансовые претензии касаются в первую очередь, производителей работающего с GIF программного обеспечения.

Благодаря возможностям алгоритма LZW стандарт GIF позволяет значительно сокращать объем итогового графического файла по сравнению с исходным изображением. Достигается это методом смешения сходных оттенков в один. Если, например, в составе рисунка имеется участок, состоящий из нескольких сходных полутонов, к примеру, голубого, светло-голубого и темно-голубого цвета, они будут кодированы одним оттенком -- голубым. Информация об изображении в файле стандарта GIF записывается построчно, то есть представляет собой массив описаний строк высотой в один пиксел. Именно это свойство GIF, а также то, что данный формат оперирует фиксированной, так называемой индексированной палитрой, причем число цветов в этой палитре не превышает 256, сделало его наиболее популярным графическим форматом в современном Интернете.

Если готовится рисунок для сохранения в формате GIF, необходимо избегать следующих художественных приемов: градиентных заливок, размытий, постепенных цветовых переходов с множеством оттенков. Не следует также пользоваться графическими фильтрами! Фильтру "блик" редактора Adobe PhotoShop, для неравномерного смешения нескольких цветов на одном участке изображения, например при создании эффектов изменения интенсивности освещения. Это связано с тем, что алгоритм замещения схожих оттенков одним в формате GIF далеко не всегда работает корректно. Поэтому участки с множеством различных оттенков на небольшом фрагменте рисунка после сохранения изображения в индексированной 256-цветовой палитре будут выглядеть смазанными и "грязными". Этого можно избежать, применяя по возможности однотонные и контрастные цвета. Одно из замечательных свойств стандарта GIF -- его уникальная особенность, названная разработчиками "interlace", или, по-русски, "чересстрочность". Она позволяет загружать картинку с сервера в клиентский браузер не целиком, а частями, причем процедура считывания файла выглядит следующим образом: сначала на экране отображаются первая, пятая и десятая строки, составляющие изображение, затем -- вторая, шестая и одиннадцатая и т. д. Таким образом, для пользователя создается иллюзия постепенной загрузки графического элемента: картинка как бы медленно проявляется на странице, что не только создаст красивый визуальный эффект, но и дает возможность пользователю наблюдать за появлением графического изображения "в процессе", вмести того чтобы несколько секунд любоваться на пустой участок экрана.



1.5 Формат TIFF

Растровый формат TIFF (Tagged Image File Format) был создан для преодоления трудностей, которые возникают при переносе графических файлов с IBM-совместимых ПЭВМ на ПЭВМ Macintosh и обратно.

Спецификация TIFF была выпущена Aldus Corporation в 1986 году и представила данный формат в качестве стандартного метода хранения черно-белых изображений, созданных сканерами и программными пакетами верстки.

Широкое распространение получила разработанная в апреле 1987 года модификация формата 4.0, которая могла поддерживать обработку несжатых цветных RGB-изображений. TIFF модификации 5.0 (появившийся в августе 1988 года) позволял хранить цветные изображения с палитрой и поддерживать алгоритм сжатия LZW. Выпущенный в июне 1992 года TIFF 6.0 расширил свои функциональные возможности поддержкой цветных изображений моделей СМYK и YCbCr, а также использовал метод сжатия JPEG.

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

TIFF стал общим форматом для систем ввода изображений со сканеров, используется в издательских системах и входит в состав дистрибутивных приложений Windows.

Организация файла. Файлы TIFF состоят из трех разделов: заголовка файла изображения (Image File Header - IFH), директории файла изображений (Image File Directory - IFD) и растровых данных (Тэг). Из них необходимыми являются только IFH и IFD. Следовательно, допускается возможность существования файла TIFF, не содержащего растровых данных. Файл TIFF, содержащий несколько изображений будет включать столько же директорий файла и разделов растровых данных (по одному для каждого изображения). Структура формата представлена на рисунке.

Рис. Обобщенная структура TIFF - файла

В составе структуры TIFF - файла можно выделить:

1. Заголовок, включающий:

- идентификатор порядка байтов в файле (от старших к младшим или наоборот);

- номер версии;

- указатель на первую директорию IFD;

2. Директория (IFD) - содержит описание одного изображения:

- счетчик тэгов в директории;

- последовательность тэгов;

- указатель на следующую директорию IFD;

3. Тэг:

- идентификатор поля;

- тип поля (базовое, информационное, факсимильное и поле запоминания и восстановления документов);

- длина поля;

- смещение в файле к данным.

Начальный заголовок содержит 8 байт. Вся информация и параметры, имеющие отношение к изображению, хранятся в полях признаков. Современные версии TIFF включает 45 таких полей. Однако фактически есть два отдельных поля признака для точного определения размеров изображения, а также поля для определения ПЭВМ, программного обеспечения, даты создания файла и т. д. Несколько полей содержат значения по умолчанию и, следовательно, не требуют уточнения. TIFF снабжен полями, которые позволяют правильно отображать изображения с нестандартной разрешающей способностью

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

Каждая директория файла содержит одну или несколько структур данных, называемых тегами. Каждый тег является 12-байтовой записью, содержащей определенную информацию о растровых данных. Тег может хранить данные любого типа, и спецификация TIFF определяет свыше 70 тегов, которые применятся для представления заданной информации. Теги каждой директории объединяются в непрерывные группы.

Теги, определенные спецификацией TIFF, называются общедоступными и не могут изменяться в большей мере, чем это предусмотрено спецификацией. Теги, определенные пользователем, называются частными и предназначены для применения в пользовательских программах через Developer's Desk фирмы Aldus.

Файл TIFF может содержать любое количество изображений (включая нулевое). Каждое изображение рассматривается как отдельный растровый субфайл, данные которого описываются информацией IFD. Каждый субфайл TIFF может быть записан в виде отдельного файла или вместе с другими субфайлами объединен в один файл TIFF. Каждый растровый субфайл имеет свою директорию файла изображения и может располагаться в любом месте (после заголовка). Каждому изображению может соответствовать только одна директория.

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

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

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

Тег формата TIFF имеет следующую структуру:

алгоритм сжатие графический формат

Typedef struct _TifTag

{

WORD Tagid; /* Идентификатор тега */

WORD Datatype; /* Скалярный тип элементов данных */

DWORD DataCount; /* Количество элементов данных тега */

DWORD DataOffset; /* Смещение элементов данных */

} TIFTAG;

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

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

Изображения, записанные в формате TIFF 6.0, могут быть организованы и в виде полос, и в виде фрагментов.

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

Для определения полосы растровых данных в файле TIFF используются три тега: RowsPerStrip, StripOffsets и StripByteCounts.

Тег RowsPerStrip задает количество строк сжатых растровых данных в каждой полосе. Значение по умолчанию тега RowsPerStrip, равное 232-1, указывает максимально возможный размер изображения TIFF. Для всех полос в субфайлах TIFF применяется однотипная схема сжатия, Все они имеют одинаковые битовый и цветовой пол, пиксельную глубину и т.п. Чтобы определить количество полос в субфайле изображения, отличного от YCbCr, используются теги RowsPerStrip и ImageLenght.

Тег StripOffsets содержит массив смещений (по одному на полосу), которые указывают позицию первого байта каждой полосы в файле TIFF. Первый элемент массива указывает смещение первой полосы, второй -- смещение второй полосы и т.д. Если данные изображения разделены на плоскости (PIanarConfiguration == 2), то тег StripOffsets располагает двухмерным массивом значений -- таблицей шириной SampIesPerPixeI. В таком случае сначала записываются все колонки компонента цвета (плоскости) со значением 0, затем все колонки компонента цвета (плоскости) со значением 1 и т.д. Полосы данных изображения, организованные в виде плоскостей, могут записываться в файл TIFF в любом порядке, но обычно записываются либо по плоскостям (RRRRGGGGBBBB), либо по компонентам цвета (RGBRGBRGBRGB). Значения тега StripOffsets всегда рассматриваются как показатели смещения от начала файла.

Тег StripByteCounts описывает массив значений, указывающих размер каждой полосы в байтах. Подобно тегу StripOffsets он содержит одномерный (в случае порций) или двухмерный (в случае плоскостей) массив значений -- по одному на полосу. Каждое из этих значений характеризует количество байтов сжатых растровых данных, записанных в соответствующей полосе.

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

Программы записи TIFF обычно пытаются создавать полосы таким образом, чтобы каждая из них включала в себя одинаковое количество строк. Например, растр из 2200 строк может быть разделен на 22 полосы, каждая из которых будет содержать 100 строк растровых данных. Но такое деление не всегда возможно. Положим, растр состоит из 482 строк. Если его разделить на полосы, содержащие по пять строк, то получим 97 полос, причем 96 из них будут состоять из пяти строк данных, а 97-я - только из двух. В этом случае значение пятого тега RowsPerStrip будет корректным для всех полос, кроме последней. Программе чтения TIFF не обязательно знать количество строк в каждой полосе. Достаточно прочесть последнее значение тега StripByteCounts, чтобы определить количество байтов, которое следует прочесть для формирования последней полосы.

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

Во-вторых, создав таблицу смешений полос, можно значительно упростить произвольный доступ к растровым данным. Если необходимо отобразить, например, последние 100 строк изображения, состоящего из 480 строк, а растровые данные разделены на 48 полос по десять строк в каждой, то программа чтения TIFF может пропустить первые 380 строк и обработать только те полосы, смещения которых записаны в последних десяти элементах массива тега StripOffsets. Если смещение не указано, то для определения начальной позиции последних 100 строк необходимо читать все изображение с его начала.

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

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

Многие алгоритмы сжатия, и в частности JPEG, для сжатия данных используют двухмерные фрагменты - блоки, а не одномерные полос. Хранение сжатых данных в виде фрагментов способствует ускорению дешифровки данных. Концепции разделения данных изображения на фрагменты (сегменты) включены в спецификацию TIFF 6.0.

Если вместо полос применяются фрагменты, то три тега, описывающие полосы (RowsPerStrip, StripByteCounts и StripOffsets), заменяются тегами TileWidth, TileLenght, TileOffsets и TileByteCounts. Их предназначение и способ применения фактически те же, что и у тегов, описывающих полосы. Подобно полосам все фрагменты могут быть либо несжатыми, либо сжатыми по одной схеме. Изображения TIFF могут быть разделены либо только на полосы, либо только на фрагменты.

Теги TileWidth и TileLenght описывают размер фрагментов данных изображения. Их значения должны быть кратными 16, а все фрагменты субфайла должны иметь один размер. Это очень важно для некоторых программ особенно в случае применения ориентированной на фрагменты схемы сжатия JPEG. Спецификация TIFF 6.0 рекомендует, чтобы фрагменты были прямоугольной форма и содержали (до сжатия) от 4 до 32 Кб данных изображения.

Значения тегов TileWidth и TileLenght могут применяться для определения количества фрагментов субфайлов изображений, отличных от YCbCr:

TilesAcross = (ImageWidth + (TileWidth - 1)) / TileWidth;

TilesDown = (ImageLength + (TileLength - 1)) / TileLength;

Tileslnlmage = TilesAcross * TilesDown;

Если изображение разделено на плоскости (PIanarConnguration = 2), то количество фрагментов можно вычислить следующим образом:

Tileslnlmage == TilesAcross * TilesDown * SamplesPerPixel;

Тег TileOnffets содержит массив смещений первых байтов каждого фрагмента. Фрагменты записываются в субфайл в произвольном порядке. Каждый фрагмент имеет собственное смещение и не зависит от других фрагментов в субфайле. Смещения в этом теге указываются в направлении слева направо и сверху вниз. Если данные изображения разделены на плоскости, то вначале записываются все смещения для первой плоскости, затем все смещения для второй и т.д. Количество смещений в этом теге равно количеству фрагментов изображения (PIanarConnguration = 1) или количеству фрагментов, умноженному на значение тега SamplesPerPixel (PIanarConnguration = 2). Смещения всегда указываются от начала файла TIFF.

Последний тег -- TileByteCounts -- содержит данные о количестве байтов в каждом сжатом фрагменте. Количество значений этого тега также равно количеству фрагментов изображения, причем эти значения упорядочены тем же способом, что и значения тега TileOffsets.

Обычно размер фрагмента выбирается таким, чтобы точно разделить изображение. Изображение шириной 6400 пикселей и длиной 4800 пикселей можно точно разделить на 150 фрагментов шириной 640 пикселей и длиной 320 пикселей. Однако не все изображения имеют размеры, кратные 16. Изображение шириной 2200 пикселей и длиной 2850 пикселей нельзя точно разделить на фрагменты, размеры которых будут кратными 16. В этом случае решением может стать выбор рациональных размеров фрагмента и дополнение изображения.

Под рациональными понимаются такие размеры фрагмента, при которых размер изображения будет перекрываться минимально. При указанном выше размере изображения можно применить разбиение на фрагменты шириной 256 пикселей и длиной 320 пикселей, т.е. сохранить почти то же соотношение ширины и высоты, что и у исходного изображения. Разбиение на фрагменты таких размеров потребует применения по 104 дополнительных пикселя набивки в каждой строке и 30 дополнительных строк. Размер данных изображения с учетом набивки теперь составит 2304 пикселя в ширину и 2880 пикселей в длину, что позволит точно разделить это изображение на 81 фрагмент размером 256 х 320 пикселей.

Цвета изображения. Спецификация TIFF предлагает концепцию основных типов изображений: двухуровневое, полутоновое, цветное с палитрой и полноцветное. Для каждого основного типа изображений установлен обязательный минимальный объем тегов.

TIFF поддерживает два способа хранения цветовых данных. TIFF-P подобен GIF и использует цветовую палитру (карту) для изображения. Тогда сами данные об изображении хранятся как коды в соответствии с цветовой картой. Этот метод обеспечивает эффективность хранения, но ограничивает палитру 256 цветами. Цветовая карта создает свои элементы из 48-битовой палитры (основная структурная единица TIFF - 2-байтовое слово, следовательно, по 16 цветов предоставлено каждой из цветовых плоскостей аддитивной цветовой модели RGB: красной, зеленой и синей). TIFF-R используется для определения полных RGB-изображений. Элемент растра представляется тремя 8-битовыми RGB-значениями, что обеспечивает более 16 миллионов цветов.

Сжатие. TIFF считается хорошо сжимающим форматом. Он поддерживает несколько схем сжатия, специальные функции управления изображением и многие другие возможности. Кроме того, он позволяет применять схему сжатия, заключающуюся в добавлении необходимых тегов, определяемых пользователем. Формат TIFF 4.0 поддерживал лишь групповое кодирование (RLE) и CCITT (T.4 и Т.6). Обычно эти схемы применяются только для сжатия 8-битовых цветных и полутоновых, а также 1-битовых черно-белых изображений соответственно. В TIFF 5.0 была добавлена схема сжатия LZW, обычно используемая при работе с цветными изображениями, а в TIFF 6.0 -- метод JPEG, применяемый для сжатия многоградационных цветных и полутоновых изображений. В TIFF применяется также схема сжатия PackBits RLE, используемая инструментальными средствами Macintosh.

Еще одной особенностью TIFF является спецификация разрешающей способности оборудования, например, IBM PC, Macintosh и т.д.