MoveDict (c) DataFile.WriteSymbol (c); 

DeletePhrase (); 

/* добавляем в словарь однуфразу, которая начинается с первого символа буфера */ 

AddPhrase (); 

/* сместим окно на 1 позицию, добавляем в конец буфера символ с */   

MoveWindow(c);  

}  

} 

CompressedFile.WriteBits (0, OFFS_LN);

Пример подтвердил, что способ формирования кодов в LZ77 является неэффективным и позволяет сжимать только сравнительно длинные последовательности. До некоторой степени сжатие небольших файлов можно улучшить, используя коды переменной длины для смещения i. Действительно, даже если мы используем словарь в 32 Кбайт, но закодировали еще только 3 Кбайт, то смещение реально требует не 15, а 12 битов. Кроме того, происходит существенный проигрыш из-за использования кодов одинаковой длины при указании длин совпадения j. Статистический анализ больших фрагментов текста (порядка нескольких мегабайт) указывает, что различные длины совпадений фраз встречаются с разной вероятностью.

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

Алгоритм декодирования может иметь следующий вид.

for (;;) {

// читаемсмещение

match_pos = CompressedFile.ReadBits (OFFS_LN);

if (!match_pos)

// найден признак конца файла, выходим из цикла

break;

// читаемдлинусовпадения

match_len = CompressedFile.ReadBits (LEN_LN); 

for (i = 0; i < match_len; i++) {

// находим в словаре очередной символ фразу, которая совпала

с = Dict (match_pos + i);

// смещаем словарь на 1 позицию, добавляем к его началу с 

MoveDict (c);

// записываем очередной раскодированный символ в исходный файл

DataFile.WriteSymbol (c); 

} 

/* читаем символ, который не совпал, добавляем его в словарь и записываем в исходный файл */

с = CompressedFile.ReadBits (8); 

MoveDict (c) DataFile.WriteSymbol (c); 

}

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

МЕТОД СЖАТИЯ LZSS

Алгоритм LZSS позволяет достаточно гибко сочетать в исходной последовательности символы и указатели (коды фраз), что в некоторой степени устраняет свойственно LZ77 расточительство, что проявляется в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski).

Идея алгоритма заключается в добавлении к каждому указателя символа однобитового префикса f, что позволяет различать эти объекты. Иначе говоря, однобитовый флажок f указывает на тип и, соответственно, длину тех данных, которые непосредственно следуют за ним. Такая техника позволяет:

· Записывать символы в явном виде, когда соответствующий код имеет большую длину. Значит, словарное кодирование только вредит;

· Обрабатывать символы, которые до этого ни разу не встречались.

Пример:

Закодируем строку "кот_ломом_колол_слона" из предыдущего примера и сравним коэффициент сжатия для LZ77 и LZSS.

Пусть мы переписываем символ в явном виде, если текущая длина максимального совпадения буфера и какой-нибудь фразы словаря меньшей или равной 1. Если мы записываем символ, то перед ним выдаем флаг со значением 0, если указатель - со значением 1. Если есть несколько фраз одинаковой длины, которая совпадает, выбираем ближайшую к буферу.

Таблица 4. Кодирование методом LZSS.

Таким образом, для кодирования строки с помощью алгоритма LZSS нам понадобилось 17 шагов: 13 раз символы были переданы в явном виде, и 4 раза мы использовали указатели. Отметим, что при работе алгоритма LZ77 нам понадобилось только 12 шагов. С другой стороны, если задаться теми же длинами для iи j, размер закодированных с помощью LZSS данных равна 13 * (1 + 8) + 4 * (1 + 5 + 3) = 153 битам. Это означает, что строка действительно была сжатой, потому что ее начальный размер – 168 битов.

Декодирование информации, сжатой алгоритмом семейства LZ на примере алгоритма LZSS:

0 'к' 0 'о' 0 'т' 0 '_' 0 'л' 0 'о' 0 'м' 1 2 2 0 '_' 1 10 2 1 8 2 0 'л' 0 '_' 0 'с' 1 5 2 0 'н' 0 'а'

Таблица 5.Декодирование информации, сжатой алгоритмом семействаLZ на примере алгоритма LZSS.

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

СЛОВАРНЫЕ МЕТОДЫ СЕМЕЙСТВА LZ С ТАБЛИЧНЫМ СЛОВАРЕМ. МЕТОД СЖАТИЯ LZ78.

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

Алгоритм работы:

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

Пример:

Пусть фраза с индексом "1" означает ситуацию, когда ни одна фраза из буфера не найдена в словаре.

Таблица 6. Кодирование методом LZ78

Для индекса достаточно 5 битов информации; символ S - 8 бит; каждый шаг кодирования - 8 + 5 = 13 бит; 13 шагов * 13 бит = 169 бит, а начальная фраза составляла 168.

АЛГОРИТМ СЖАТИЯ LZW.

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

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

Таблица 7. Кодирование методом LZW.

Необходимо 6 битов для сохранения словаря. Закодированная фраза занимает 6 * 18 = 108 бит, а начальная фраза составляла 169 бит.

Общая характеристика словарных методов: коэффициент сжатия для методов, использующих окно, которое скользит, в 2-4 раза; для методов с табличным словарем - в 2,5-5 раз. Отличие в производительности кодера и декодера в 8-10 раз. Как правило, рассмотренные методы редко применяются в чистом виде. Для достижения большего сжатия, к выходному потоку применяют этап вторичного сжатия с применением метода Хаффмана.

МЕТОДЫ ВЫЧИСЛЕНИЯ ЦИФРОВЫХ ДАЙДЖЕСТОВ.

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

Сферы применения дайджестов:

1. Проверка целочисленности информации.

2. Создание цифровой подписки.

3. Криптография (шифрование паролей).

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

АЛГОРИТМ MD5.

Логику вычисления MD5 можно изобразить схемой:

Рисунок 4. Логика вычисления MD5.

Согласно алгоритму MD5 каждый блок исходного сообщения (512 бит) обрабатывается независимо; в результате этой обработки с начального значения хэш-кода выходит новый промежуточный результат. После обработки последнего блока будет получен окончательный результат. Предварительная обработка данных осуществляется следующим образом: из исходного сообщения получают расширенное, для этого сообщения дополняют единицей и набором нулевых битов так, чтобы его длина, плюс еще 64 бита, была кратной 512. Если сообщение уже имеет такую ​​длину, то к нему все равно добавляется пустой блок. После этого к результату присоединяют 64битовую длину сообщения.

Рисунок 5. Обработка каждого 512-битного блока.

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

Используются функции:

f_F=(B∧C) ∨ (not B∧D)

f_G=(B∧D) ∨ (C∧ not D)

f_H=B xor C xor D

f_L=C xor (B ∧ not D)

Схема цикла:

Рисунок 6. Схема цикла.

Обработка 512-битного слова:

CLS - циклический сдвиг влево;

T [i] - элемент массива, используется для переименования битов.

Общая схема преобразования:

A = B + CLS_s (A + f (B₁C₁D₁) + X [k] + T [i]);

CLS_s - циклический сдвиг влево на s позиций.

Инициализация:

A = 0x1234567

B = 0x89ABCDEF

C = 0xFEDCBA98

D = 0x76543210

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

Все сложения при вычислении MD5 выполняются по модулю 2. MD5 имеет достаточную устойчивость для использования при шифровании паролей; для полного перебора понадобится 2128 вычислений хеш-функций, а для поиска коллизии 2¹²⁸/2 операций, то есть 2⁶⁴.

АЛГОРИТМ ИСЧИСЛЕНИЯ ДАЙДЖЕСТА SHA1.

Рисунок 7. Логика исчисления SHA1.

Логика построения расширенного сообщения совпадает с той, что используется в MD5.

Отличается начальная инициализация хэш-кода:

A = 0x67452301

B = 0xEFCDAB89

C = 0x98BADCFE

D = 0x10325476

E = 0xC3D2E1F0

Обработка каждого 512-битного блока:

Рисунок 8. Обработка каждого 512-битного блока.

0≤t≤1_gk₁=0xA827999

Целая часть

20≤t≤39k_t=0x6ED9EBA1

Целая часть

40≤t≤59k_t=0x8F1BBCDC

Целая часть

60≤е≤79k_t=0xCA62C1D6

Целая часть

Рисунок 9. Схема цикла.

ЛОГИКА ВЫПОЛНЕНИЯ ROUND_Х

Таблица 7. Логика выполнения ROUND_X

Слова Wt вычисляются на основании исходных данных, по которым ведется обработка.

Рисунок 10. Вычисление слов.

W_t=W_t-16 xor W_t-14 xor W_t-8 xor W_t-3

Таблица 8. Сравнение MD5 и SHA1

Реализация MD4, MD5, SHA1:

C++; OpenSSL; Java; java.security; System.Security.Cryptography

МЕТОДЫ ХРАНЕНИЯ И СЖАТИЯграфической информации. Форматы графических файлов

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

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

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

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

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

Разрешение экрана - это плотность размещения пикселей. Она зависит от качества кинескопа монитора. Принятой единицей измерения разрешения является количество точек на дюйм - dpi (Dot Per Inch). При отображении рисунков на мониторе, используют разрешение от 72 dpi до 120 dpi. При печати распространенным разрешением для вывода текста является 300 dpi, но для высококачественной печати можно использовать и более разрешение (1440 dpi).

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

Недостатки растровых изображений:

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

· Большой размер файла, поскольку включены данные про каждый пиксель изображения.

ФОРМАТ BMP

Формат bmp (от слов BitMaP - битовая карта, или, битовый массив) представляет собой несжатое изображение. Оно достаточно легко читается и выводится в ОС Windows, поскольку в нее включены специальные функции API, которые в этом помогают.

По решению разработчиков формат Bmp файла не привязан к конкретной аппаратной платформе. Этот файл состоит из четырех частей: заголовка, информационного заголовка, таблицы цветов (палитры) и данных изображения. Если в файле хранится изображение с глубиной цвета 24 бита (16 млн. цветов), то таблица цветов может отсутствовать.

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

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

Ширина и высота изображения задаются в точках растра и объяснений, пожалуй, не требуют.

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

Глубина цвета считается важнейшей характеристикой способа представления цвета в файле и измеряется в битах на точку. В данном случае она равна 8.

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

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

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

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

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

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

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

СТРУКТУРА BMP-ФАЙЛА

Таблица 9. Структура BMP-файла.

ФОРМАТ GIF

Рисунок 11. Минимально необходимый набор блоков – самый простой не анимированный gif.

Таблица 10. Таблица для разных глубин цвета изображения.

Таблица 11. Таблица для разных размеров палитр и количества цветов картинки

СЖАТИЕ РАСТРОВЫХ ИЗОБРАЖЕНИЙ

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

1. Без потерь информации

2. С потерями.

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

Краткое описание формата GIF:

GIF один из самых распространенных и популярных в Интернете форматов изображений. Такое широкое распространение GIF во многом определяется особенностями его формата

Общие данные:

• Размер картинки-от 1х1 до 65535х65535 пикселей.

• Количество цветов палитры - от 2 до 256.

• Каждый цвет палитры имеет глубину 24 бита / пиксель (выбор из 16000000 цветов).

• Карта прозрачности - 1-битная (полупрозрачных цветов нет).

• Количество повторов анимации - от 1 до 65535, а также бесконечное.

• Время показа одного кадра анимации - от 1/100 секунды до 655 секунд.

• Количество кадров анимации – неограниченное

  • Количество невидимых текстовых комментариев и размер каждого комментария – неограниченно.

Структура GIF-файла:

1. Файлы формата GIF имеют блочную структуру. Это означает, что онисостоят из отдельных блоков, которые в большинстве случаев никак не связаны друг с другом. Программы, не распознают некоторые типы блоков, могут просто пропускать их - для этого у каждого нестандартного блока в заголовке указан его размер. Блоки графики (картинки), идущие один за другим, составляют анимацию. Они меняются на экране и создают иллюзию движения. До или после них (или даже между ними) в файле могут находиться другие блоки:

1. Комментарии. Скрытый текст, его можно увидеть только с помощьюспециальных программ - например, GIF-аниматоров, таких, как UleadGIFAnimator.

2. Простой текст. Строки символов с ограниченными возможностями форматирования. Сейчас не используется.

3. Блоки управления графикой, задающие параметры вывода отдельных картинок.

4. Глобальная и локальные палитры цветов, определяющих, какие именно цвета будут у картинок.

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

Минимальный необходимый набор блоков для простогонеанимированного GIF (смотреть рис. 11):

1. Дескриптор логического экрана.

2. Глобальная палитра.

3. Дескриптор изображения.

4. Изображение.

В начале каждого файла GIF находится заголовок. поскольку сразу за ним идет дескриптор логического экрана, заголовок считается его частью. Он состоит из текста "GIF87a" или "GIF89a", в зависимости от версии

Дескриптор - это просто "описатель" или "описание". Логический экран - область реального экрана компьютера, куда выводятся все картинки данного файла GIF. Они могут иметь разный размер и занимать различное положение налогическом экране. W, H - ширина и высота логического экрана в пикселях, то есть размер области вывода картинок. Изображения, которые не умещаются налогическом экране, должны обрезаться по его размеру.

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

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

CT - наличие глобальной палитры. Если этот флажок установлен,

то сразу после дескриптора глобального экрана должна начинаться

глобальная палитра. Размер палитры определяется полем Size.

Color - цветовое разрешение начальной картинки. Число битов,

приходится на каждый из трех основных цветов. Если файл GIF создан

непосредственно с полноцветного изображения, то Color равно 7, а

если с уже индексированного, то его значение будет зависеть от глубины цвета

этой индексированной картинки, причем очень приблизительно. Например, если файл

создан на основе 16-цветной картинки, то Color должно быть равным 1, и начальная палитра должна равняться 1, начальная палитра предполагается 64 цветной.

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

 - размер палитры и количество цветов картинки. если флажок глобальной палитры

 сброшен, то должны стоять нули.

Глобальная палитра

Изображения, хранящиеся в файле GIF, индексированные. картинки состоят не из полноцветных пикселей, а из номеров цветов, а сами цвета находятся в палитре. Палитра составлена из триад, в свою очередь состоят из байтов красного , зеленого и синего основных цветов. Из всего разнообразия цветов (современные компьютеры и мониторы могут показывать на экране до 16 миллионов цветов) используется только от 2 до 256. Возведение числа цветов к минимуму без значительного ухудшения качества изображения и без потери информации - сродни искусству, и автоматизации поддается плохо. Многие графические редакторы - такие как Adobe Photoshop, например - позволяют интерактивно выбрать лучший вариант индексации картинки «на глаз»

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

Дескриптор изображения

Действует на графический блок (картинку), что идет за ним. Без него картинка выводится не будет, так что его можно считать неотъемлемой частью графического блока. Между дескриптором и блоком графики может находиться только локальная палитра.

 - ширина и высота картинки в пикселях.

 - положение картинки на логическом экране.

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

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

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

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

Локальная палитра

Если она есть, должна идти сразу за дескриптором изображения. Наличие палитры обозначается флажком , а размер – полем . Действует она только на тот графический блок (картинку), который идет сразу за ней.

Для уменьшения размера файла лучше ограничиться одной глобальной палитрой, не прибегая к локальным - особенно, если речь идет о многоцветных картинках. Максимальный размер палитры при 256 цветах - 768 байт, а если умножить на число картинок в анимации, то сумма набегает солидная.

Графический блок

Картинка, сжатая с помощью метода LZW. Она разбита на отдельные субблоки по 255 байт. Число картинок в файле, как и размер каждой картинки, ничем не ограничены. Анимированным GIF становится в том случае, если в нем больше одной картинки. Тогда при просмотре файла в браузере автоматически включается анимация.

MC - начальный размер LZW-кода. Равный глубине цвета картинки, исключая двухцветные, когда MC равен не 1, а 2.

Таблица 12. Начальный размер LZW-кода

S - размер субблока данных, не включая сам байт S. Во всех субблоках, кроме последнего, размер должен быть равен 255 байт. У последнего субблока (или если он вообще один) размер может быть любым - от 1 до 255 байт.

Расширение управления графикой

Введено в версии GIF89a. Действует на первый же графический блок (картинку), что идет за ним. Между ним и блоком графики могут быть вставлены другие блоки (например, комментарий) - это его работе не мешает.

Delay - время задержки, в 1/100 сек. Время, в течение которого эта картинка остается на экране. Минимальное значение - 1/100 секунды, максимальное - примерно 655 секунд. Таймер начинает отсчет только после того, как картинка выведена на экран, поэтому в различных программах просмотра время задержки может существенно различаться. Например, если попытаться сделать анимированный GIF - часы, то они могут, в зависимости от браузера, в минуту спешить или отставать более чем на секунду.

Tr - номер прозрачного цвета. Если есть локальная палитра, это номер цвета в ней, если же локальной палитры нет, то это номер цвета в глобальной палитре.

Disp - способ замены картинки после показа:

Таблица 13. Способ замены картинки

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

TF - флажок прозрачности. Если он установлен, эта картинка выводится с прозрачным фоном, цвет которого определяется параметром Tr.

Расширение простого текста

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

Left, Top-положение области текста на логическом экране.

W, H - размер области текста. Строки, которые выходят за ее рамки, обрезаются. Переводы строки должны быть заранее вставлены в текст.

cW, cH - размер символов. Рекомендуется использовать значение 8х8 или 8х16 пикселей, что сейчас годится только для DOS.

FG - номер цвета текста.

BG - номер цвета фона. Этим цветом заливаются области фона, где нет текста.

S - размер субблока данных, не включая сам байт S. Во всех субблоков, кроме последнего, размер должен быть равен 255 байт. У последнего субблоков (или если он вообще один) размер может быть любым - от 1 до 255 байт.

Расширение комментария

Введено в версии GIF89a. В основном сюда записывают данные об авторских правах создателей файла GIF - и людей, и программ. Длинный текст можно ожидать в том случае, если программа бесплатная или условно бесплатная. Длина текста ничем не ограничивается.

S - размер субблока данных, не включая сам байт S. Во всех субблоков, кроме последнего, размер должен быть равен 255 байт. У последнего субблоков (или если он вообще один) размер может быть любым - от 1 до 255 байт.

Расширение дополнения

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

ID - идентификатор приложения. Текст из 8 символов, по которому программа просмотра определяет, сможет ли она прочитать данные, и которого они типа.

Code - код идентификатора. Предполагалось, что программа, которая создала GIF, будет синтезировать двоичный код для подтверждения своих прав на это расширение. На деле здесь тоже находится текст с 3 символов.

S - размер субблока данных, не включая сам байт S. Во всех субблоках, кроме последнего, размер должен быть равен 255 байт. У последнего субблока (или если он вообще один) размер может быть любым - от 1 до 255.

Расширение дополнения NetScape

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

? - Здесь стоит 0x01, но это значит, неизвестно. Возможно, сначала этот байт предполагалось использовать, но затем он оказался ненужным.

Loop - количество циклов анимации, от 0 до 65535. Здесь есть некоторые особенности. Во-первых, без расширения Netscape цикл анимации срабатывает, но только один раз. Если же вставить расширения Netscape в файл и установить Loop = 1, то цикл будет прокручиваться дважды, как и при Loop = 2. А при Loop = 0 анимация крутится бесконечно, так что ее отключения, для того, чтобы выводилась только одна первая картинка, в любом случае оказывается невозможным.

Вывод

Может показаться, что формат GIF со своими 256 цветами уже окончательно устарел, однако по сравнению с другой техникой вывода изображений он даже может в чем-то и выигрывать. Например, применение для создания анимированных кнопок и баннеров вместо картинок GIF техники Flash предполагает, что на каждом браузере установлен плагин Flash или элемент ActiveX Flash нужной версии. Это может в отдельных случаях привести к тому, что пользователи не только не смогут увидеть рекламу, но и вообще не смогут попасть на этот сайт, тогда как поддержка GIF встроена во все браузеры, начиная с самых первых версий.

Формат PNG, который завоевывает все большую популярность, при всех своих неоспоримых плюсах (полноцветная картинка, прозрачность с альфаканалом), не может обеспечивать такого сильного сжатия малоцветных изображений, не говоря уже об анимации. Его анимированная модификация MNG пока не поддерживается ни одним браузером. Другие новые форматы - такие, как JPEG 2000 - ориентированы в основном на фотографические изображения и не составляют серьезной конкуренции формату GIF, тем более что пройдет еще много времени, пока браузеры во всем мире будут пользоваться поддержкой этих новых форматов. В настоящее же время GIF, вместе с JPEG, остается одним из двух основных форматов изображений, используемых в Интернете, и, скорее всего, будет служить нам еще долго.

АЛГОРИТМ JPEG

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

· Дискретное косинусное преобразование

· Этап Квантования

· Этап Вторичного сжатия

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