Реализация LZW алгоритма сжатия с использованием возможностей современных GPU
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ели адресуют ранее разобранную подстроку.LZWWelch [1984]Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину.LZCThomas et al [1985]Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку.LZTTischer [1987]Аналогично LZC, но фразы помещаются в LRU-список.LZMWMiller and Wegman [1984]Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз.LZJJakobsson [1985]Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов.LZFGFiala 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 году и представила данный формат в качестве стандартного метода хранения черно-белых изображений, созданных сканерами и программными пакетами верстки.