Алгоритм сжатия LZW.

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

Пример. aabcdabcddd

Сначала bc, потом ab, потом abc. Исходная таблица состоит из четырёх двухразрядных кодов.

Длина исходного кода зависит от количества исходных символов. Есть ли какое-либо сочетание повторяющееся? Не хватает трёх разрядов, добавляем ещё. Полученный код получится избыточным. Поэтому задействованы не все комбинации. Достоинство: является не зависимым от начальной статистики. Мы получим свою таблицу кодировки для каждого набора данных. При передаче файла, таблица кодировки передаётся с данными. Используется в форматах TIFF, GIF. Пользователю математический аппарат знать не надо.

Конечно можно пользоваться и стандартными архиваторами, но в 90% случаев из 100% мы получим не уменьшение размера файла, а его увеличение. Для графики нужно пользоваться специальными методами сжатия конкретно для графики.

Формат DXF.

Представляет собой последовательность команд, которые записаны кодами ASCII. Каждая команда занимает две строки.

Строка 1 – код группы команды.

Строка 2 – сама команда.

В каждой группе могут быть различные форматы команд. Диапазон кодов команд ограничен числами от 0 до 999.

Все команды разбиты на четыре части: заголовки, таблицы, примитивы, блоки. Ни один раздел не является обязательным. Единственной обязательной командой является 0 EOF – конец файла. Открытие и закрытие секций выполняется так:

0 section

…

0 endsec

Если говорить о разделах примитивов, то они всегда помещаются в конце созданного файла.

Заголовки определяют настройки внутренних переменных языка. Текущее значение настроек используется до момента, пока их не изменяют. Если опустить заголовки, то по умолчанию возьмётся стандартный набор. Структура заголовка:

0 SECTION

HEADER

$ …

ENDSEC

Где $ – это описание переменной. Далее следует таблица (толщина линии, виды шрифтов, используемые стандартные цвета).

0 SECTION

TABLES

…

ENDTAB

TABLES

…

ENDTAB

ENDSEC

Количество таблиц не ограничено. Названия видов таблиц:

LAYER

LTYPE

STYLE

VIEW

VPORT

VCS

LAYER.

Когда слой надо сделать невидимым, то после записи такого вида добавляется команда с номером 70. Эта команда управляется одним битом под номером 6.

LTYPE

Типы линий в одном слое. Имеется возможность создавать собственные типы, например

STYLE

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

VIEW

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

VPORT

Режим задания систем координат пользователя. Задаётся направление осей X, Y, Z. Система координат может быть задана нестандартно. Можно задавать большой набор трёхмерного просмотра объёмов кусков детали. Добавляется возможность поворота, угол вращения данного вида, коэффициент увеличения данного изображения, привязка к координатной сетке и параметры этой сетке, аксонометрический и изометрический стили.

В раздел блоков заносится информация об имеющихся графических элементах.

BLOCK – простой блок.

ATT DEF – команда группы 2.

10 x – блок базовой точки.

20 y

30 z

0 ENDBLK

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

VCS

Примитивы. Все стандартные элементы изображения. К стандартным относятся 16 типов.

1. Линия.

LINE

10 x начальная

20 y начальная

30 z начальная

11 x конечная

21 y конечная

31 z конечная

ENDLIN

Атрибуты задаются в разделе блоков.

2. Точка. Для неё задаются координаты, угол наклона системы координат по отношению к мировым.

POINT

x

y

z

a

ENDPNT

3. Окружность. Тип, трёхмерные координаты центра и радиус окружности.

4. Дуга. Начальные координаты начала и конца, начальный угол и конечный.

5. TRACE. Линия, которая проводится по четырём точкам. Фигура получается замкнутой.

6. SOLID. Замыкание, заливка.

7. Текст. По умолчанию – STANDART. Можно управлять любыми параметрами шрифта и задаётся цвет шрифта.

8. SHAPE. Удаление символа или изменение параметров вывода конкретного символа.

9. INSERT. Команда вставки. Берётся ранее описанное и его можно перенести в другой слой, одновременно выполнив над ним поворот и масштабирование.

10. ATTRIBUTE. Обычно применяется в комплекте с INSERT. Этот элемент получают новые атрибуты.

11. POLIGON.

12. 3D FACE. Описание трёхмерной поверхности. Создаётся аппроксимирующая поверхность, есть флаг видимости краёв этой поверхности.

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

Формат GEM.

Этот векторный формат является стандартным для большинства объектов файлов, предусматривает работу с метафайлами, поскольку изображение хранится в виде описания, то устройство ввода/вывода используется в полную силу. Состоит из заголовка файла и части, хранящей собственно изображение. Размер заголовка постоянный – это 15 по 2 байта. 2 по 9 отведены под резерв. Это стандартный приём, учитывающий разработку новых версий формата. Кроме того, когда длина заголовка одинакова, то мы получаем своеобразную защиту от сбоев.

Смещения от 8 до E. Максимально возможная площадь объекта. Если не заполнено, то формат всё равно остаётся работоспособным.

Raster Coordinates (RC) – 2.

0 32767

Normal Device Coordinates (NDC) – 0

32767

0 32767

Любые другие значения (если не 0 или не 2) воспринимаются как ошибка. Идеальному устройству вывода присваивается 32767. У реального устройства намного меньше (800х600).

Высота страниц: задают высоты реальной страницы в десятых долях миллиметра. Очень удобная функция. Удобно согласовать коэффициент пересчёта при выводе на различные устройства.

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

· Код операции

· Количество пар x, y (количество точек)

· Количество целочисленных значений

· Первое целочисленное значение

В ряде операций целочисленные значения не используются, тогда в третьей строке пишется 0. Разделение похоже на формат DXF. Первые операции определяют подгруппу и подоперации. Количество подгрупп в группе может быть от 1 до 14. Давайте приведём группы без подгрупп.

06 – полилиния

03 – число пар

01 – точка 1

точка 2

точка 3

…

Команды закрыть сегмент здесь нет.

0B – работаем с примитивами

03 – три набора данных

01 – используем один цвет

04 – изображаем закрашенным

Xц, Yц – координаты центра окружности

a_н, a_к – начальный и конечный углы проведения

R – радиус

…

08 – номер цвета закраски

Здесь также может задаваться и шаблон заполнения. Команды шаблона заполнения 17, 18, 19. В команде с номером 17 четвёртая запись может применяться: 0 – не заполняется, 1 – залить цветом, 2 – узор, 3 – заштрихован. Должна быть ещё 7, в которую записан либо узор, либо штриховка.

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

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

РАСТРОВЫЕ ФОРМАТЫ.

Формат IMF.

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

Автоматически производится расслоение на цветовые плоскости в последовательности красный, зелёный, синий. Для каждой строки отдельно формируется запись: строка битов красного, синего, зелёного и строка интенсивности. Требуется большой объём памяти для записи. Если запоминать блок, то для размера 640х200 потребуется 512 Кб памяти.

Структура: заголовок и данные. Заголовок состоит из восьми двухбайтовых слов.

1. Версия.

2. Длина заголовка в словах.

3. Число бит на пиксел.

4. Длина шаблона заполнителя для закрашивания (0 – не используется).

5. Ширина пиксела в микрометрах.

6. Высота пиксела в микрометрах.

7. Длина строки пикселов.

8. Количество строк в выделенном участке изображения.

Сами данные могут быть сжаты одним из четырёх способов.

1. Vertical Replication Count (VRC).

2. Solid Run (SR).

3. Bitmap String (BS).

4. Pattern Run (PR).

Solid Run кодирование основано на том, что в пределах записи каждой цветовой плоскости встречаются в большом количестве группы повторяющихся пикселей. Для них легко указать счётчики повторений, для каждой записи такого типа выделяется 1 байт. Старший разряд говорит о том, уплотнено или нет, 1 – уплотнено, а 0 – не уплотнено. Следующие семь байт используются как счётчик повторений. При этом способе седьмым байтом можно уплотнить 127 бит повторяющихся данных. Если это очень длинная последовательность, то одинаковые биты объединяются в группы по 8 и тогда SR уплотнение кодирует повторяющиеся данные. 1 байт уплотняет 127 байт, а не бит. Для цветовых плоскостей характерно расположение.

Bitmap String описывает также ситуации, когда нет повторяющихся условий. Этот тип определяется тем, что байты, которые описывают неповторяющиеся последовательности, можно описать 255 байт. Для битовых картинок такая ситуация встречается крайне редко.

Pattern Run описывает элементы заполнения фигур. Первых два старших нуля, затем идёт число повторений и следом записи байт, которые описывают заполнение. Должен иметь длину кратную восьми. Длина хранения находится в заголовке. Это одно из повторений, ориентированное на повторение строк. Эти строки также характерная ситуация. Идентификаторы – это запись 00, 00, FF, число повторений строк.

Запись строки может содержать код кодировки. На ряде изображений сжимается очень хорошо, а на ряде очень плохо.

Формат CGM.

На сегодняшний день это стандарт ISO. Драйверы обязаны быть в любой операционной системе. Разрабатывается на основе стандарта GKS. Основной особенностью является наличие различных способов кодирования символов. Символы могут быть в ASCII, в чисто двоичных кодах или в стандарте ISO 0646 (4 видимых символа).

Кодирование в ASCII – удобно для редактирования изображения. Двоичное кодирование удобно для обработки в компьютере. Кодирование в ISO 0646 – это стандарт для передачи по линиям связи.

Каждая запись кратна двум байтам. Если не будет кратна двум байтам, то дополняется до двух. Структура:

q код записи

q длина списка параметров

q список параметров

Заголовок может иметь краткую и полную форму. При короткой форме записи заголовка код и длина списков помещается в сам заголовок.

15 12 11 5 4 0

Класс термов метафайла. Идентификатор – это и есть терм. Аналоги класса и подкласса.

30 байт – это максимальная длина параметров списков. Этого числа может быть недостаточно для записи параметров. Применяют расширенную форму записи заголовка. Использовано два слова.

5 4

второе слово относится к заголовку

15 14

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

Сам список заполняется так: отрицательные числа в дополнительной форме с плавающей запятой. Одну группу данных можно внести в несколько списков параметров. В двоичном кодировании используется 8 классов переменных с числом подклассов от 1 до 35. Этот способ кодирования ориентирован на загрузку файла WMF.

Такая запись ориентирована на создание или редактирование изображения с помощью текстового редактора. Любая команда имеет запись:

код операции___операнд

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

Символы ISO: (вид кодирования). Код операции вообще двухбайтовое слово, а символы ISO имеют 8 разрядов (8 бит), поэтому для одной операции необходимо записать два символа ISO 0646.

3/2; 2/0 SCALEMODE

Записать можно потоком или резервным способами. В начале задаётся длина последовательности. Если кодирование идёт с резервированием, то устанавливается флаг у последней записи в списке.

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

BEGPIC

…

ENDPIC

Особенность этого формата (наличие трёх способов кодирования) позволяет адаптировать различные задачи (оператор, машина и так далее).

Формат TIFF.

Первоначально был предназначен для издательской системы Adobe PageMaker. Затем он прижился и в других компаниях. Он стал основным форматом приёмо-передающей техники (Apple, IBM, HP, Microsoft). Внутри этого формата изображение должно быть отнесено к одному из трёх типов: Bivel, Graylevel, Color.

Структура формата – это заголовок и набор блоков данных различной длины, обращаться к которым можно с помощью индекса. Каждый отдельный блок данных называется Image File Directory (IFD). Внутри первого IFD можно записать ограниченное число информации. Когда этого объёма не хватает, то можно добавить блок чистых данных. За счёт того, что ссылки индексные, то к ним можно обращаться в любом порядке. Данные не могут быть первыми, не могут быть последними. Структура данных любая, можно организовать любые ссылки.

Заголовок

IFD1

IFD2

IFD3

Данные(*)

IFDN

Структура заголовка.

TIFF – это единственный формат, который не зависит от платформы (будь то Intel или Motorola). Например в процессорах Intel и Motorola младший и старший байты находятся противоположно друг другу, то есть, если у Intel – FF E0, то у Motorola – E0 FF.

TIFF – это единственный формат, в котором есть флаг.

В заголовке 3 строки:

1. 2 байта, в которой может быть либо II, либо ММ.

2. 2 байта. Кодирует номер версии формата.

3. 4 байта. Индекс первого блока IFD.

Структура IFD: в пределах списка, все IFD связаны указателями. Группа из 12 байт называется тэг. Количество тэгов в IFD ограничено числом, которое можно записать в 2 байта.

Начинается IFD с записи 2 байта. И здесь содержится число тэгов внутри IFD, далее группами по 12 байт идут тэги и последняя запись – это указатель на следующий IFD или 0. По каким правилам пишут тэги? Тэг хранит данные об изображении. Состоит из четырёх записей:

1) 2 байта. Тип тэга.

2) 2 байта. Тип данных.

3) 4 байта. Длина поля данных.

4) 4 байта. Либо сами данные, если не хватает четырёх байт, либо указатель на это поле.

Данные пятью видов:

0,1 – байтовые записи, если 02 – коды ASCII

0,3 – тип short.

0,4 – тип long (32 бит, целые беззнаковые).

0,5 – rational – два числа типа long. Первое – числитель дроби, второе – знаменатель.

Тип данных будет связан с длиной поля данных. В поле длины указано 10*getsize(short, long, …) по возрастанию номеров.

Тип тэга:

1) Image Organization Tag.

2) Pointer.

3) Pixel Description.

4) Data Compression.

5) Storage Management.

В каждом из них от двух до восемнадцати типов, групп. Примеры, кодируется конкретная запись тремя шестнадцатеричными цифрами. Рассмотрим эти записи. Имеется возможность организовать многостраничные изображения; задать режим с разрешением гораздо меньшим, чем максимальное. Где это удобно? Передача по факсу.

Команды.

00FF

SHORT

Для любых 1, 2, 3.

2 – вывод через

3 – многостраничное изображение.

100 – управляет шириной рисунка.

SHORT

<0¸65535> – ширина в точках.

101 – управляет высотой рисунка.

SHORT

<0¸65535> – высота в точках.

Можно задать количество бит на одну точку.

11A

Rational

Разрешение в точках на дюйм (dpi). Можно указать качество вывода.

128 – единица разрешения.

Можно задать ориентацию рисунка при выводе. Это команда 112. Тип SHORT. Диапазон <1¸8>. 1 – ориентация как у монитора (0,0 – левый верхний угол). Довольно богатые возможности для комментариев. Можно также задать типы сжатия.

Начиная с пятой версии выделяют 4 вида изображения данных:

B – 0/1 – двухуровневое изображение.

G – с оттенками серого.

P – с передаваемой палитрой цветов.

R – с RGB-палитрой.

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

Могут использоваться следующие типы сжатия:

1. Pack Bit. В начале блока данных находится заголовок.

00 ¸ 7F

81 ¸ FF

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

2. Fax-уплотнение.

Полностью повторяет стандарт. Там записана особая таблица. Она содержит сочетания чёрных и белых пикселов и к такому сочетанию присваивается код. Он всегда короче, чем сама последовательность. Вместо длинной цепочки битов идёт короткий набор кодов. Есть условности. Нельзя переходить со строки на строку. Не подлежат уплотнению первые строки. Уплотнение всегда начинается с белого цвета. Надо пользоваться маркером строки. (Есть искусственный приём – вставка белой строки).

С этим форматом может быть много нестыковок. Применяется он как для хранения, так и для передачи файлов с изображением. Вообще формат TIFF является «чемпионом» по нестыковкам собственных версий.

Формат GIF.

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

Состоит из заголовка и блоков описания. Заголовок может иметь переменную длину. Структура заголовка:

1) GIF идентификатор типа файла (3 байта).

2) Версия, причём разработчики сделали 2 цифры и букву, например, 6.2a (3 байта).

3) Блок описания логического экрана (7 байт).

4) Общая палитра цветов (может отсутствовать).

5) Блок расширения.

6) Блок описания самого изображения.

7) Временная палитра цветов.

8) Блок расширения.

9) Конец заголовка. (“3B”).

Блок описания логического экрана:

· Ширина в пикселах (2 байта)

· Высота в пикселах (2 байта)

· Флаг расширения (1 байт)

· Цвет фона (1 байт)

· 0 – обычно – название этого поля (1 байт).

Pixel Aspect Ratio.

Флаг расширения: первый и второй биты – количество бит на пиксел, 4-ый, 5-ый и 6-ой – количество бит на каждый цвет, 7-ой – если 1, то должно быть описание собственной палитры, если 0, то палитра является стандартной. Можно задать локальную палитру – это уникально. Основная палитра игнорируется, а локальная становится приоритетной.

Блоки расширения.

1. Сопутствующая информация о том, каким программным продуктом надо пользоваться, вид сканера и тому подобное. Это своего рода справка.

2. В нём могут содержаться некоторые опции для построения изображения. Структура записей похожа на тэги. Начинается с «!» – признак блока. «0 – 255» – код функции. Длина первого блока, длина второго блока, и так далее. В блоке описания иллюстрации находятся параметры для вводавывода информации и так далее.

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

Достоинство: данный формат является аппаратно-независимым. Все настройки идут вместе с файлом.