6.Форматы графических файлов: растровые и векторные, сферы их применения. Структура форматов bmp, gif, jpeg. Алгоритмы кодирования информации: rle, lzw, по Хаффману. Сжатие с потерями.

Основные критерии выбора формата - совместимость с программами и компактность записи. Существует множество форматов для записи изображений. Условно их можно разделить на три категории: хранящие изображение в растровом виде (BMP, TIFF, PCX, PSD, JPEG), хранящие изображение в векторном виде (WMF) и те, что могут совмещать оба представления (EPS, PICT, CDR, AI, FH7 и др.).

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

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

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

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

BMP Формат BMP (от слова bitmap) был создан компанией Microsoft и широко используется в ОС Windows для растровой графики. Вам необходимо записать изображение в этом формате, если вы хотите использовать его в качестве фона вашего рабочего стола. Хотя в этом формате может применяться компрессия, большинство программ ее не используют. BMP-файлы с компрессией могут иметь расширение RLE. Без компрессии размер файла оказывается близок к максимальному. Такой же размер будет и у файла в формате PCX, предложенном компанией Z-Soft в программе PhotoFinish. Оба эти формата достаточно известны и могут быть использованы на платформе Macintosh, хотя были написаны для PC.

GIF Популярный формат GIF разработан фирмой CompuServe как не зависящий от аппаратного обеспечения. Он предназначен для хранения растровых изображений с компрессией. В одном файле этого формата может храниться несколько изображений, но обычно эта возможность не используется. GIF-формат позволяет записывать изображение "через строчку" (In-terplaced), благодаря чему, имея только часть файла, можно увидеть изображение целиком, но с меньшим разрешением. Эта возможность широко применяется в Сети. Сначала вы видите картинку с грубым разрешением, а по мере поступления новых данных ее качество улучшается. Основное ограничение формата GIF состоит в том, что цветное изображение может быть записано только в режиме 256 цветов. Для полиграфии этого явно недостаточно.

JPEG Компрессия, используемая в формате JPEG, необратимо искажает изображение. Это, как правило, не заметно при простом просмотре, но становится явным при последующих манипуляциях. Зато размер файла получается от 10 до 500 раз меньше, чем BMP! Если вы решили записать изображение в этом формате JPEG, то лучше выполнить все необходимые операции перед первой записью файла.При записи обычно предлагается выбрать степень компрессии. Здесь надо искать компромисс: чем сильнее компрессия, тем больше искажения.

Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов — простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.

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

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

Описание. Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.

Алгоритм

1. Инициализация словаря всеми возможными односимвольными фразами.Инициализация входной фразы w первым символом сообщения.

2. Считать очередной символ K из кодируемого сообщения.

3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для w, иначе

4. Если фраза wK уже есть в словаре, то присвоить входной фразе значение wK и перейти к Шагу 2, иначе выдать код w, добавить wK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.

Конец

Применение. На момент своего появления алгоритм LZW давал лучший коэффициент сжатия, для большинства приложений, чем любой другой хорошо известный метод того времени. Он стал первым широко используемым на компьютерах методом сжатия данных.Алгоритм был реализован в программе compress, которая стала более-менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.В настоящее время, алгоритм содержится в стандарте PDF.

Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

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

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

Сжатие данных с потерями — это метод сжатия данных, когда распакованный файл отличается от оригинального, но «достаточно близок» для того, чтобы быть полезным каким-то образом. Этот тип компрессии часто используется в Интернете, особенно в потоковой передаче данных и телефонии. Эти методы часто называются кодеками в этом контексте

Компрессия изображений

* Снижение глубины цвета

* Метод главных компонент

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

* JPEG (При сжатии изображение переводится в цветовую систему Jpeg. Далее каналы изображения Cb и Cr, отвечающие за цвет, уменьшаются в 2 раза (по линейному масштабу). Уже на этом этапе необходимо хранить только четверть информации о цвете изображения.

Реже используется уменьшение цветовой информации в 4 раза или сохранение размеров цветовых каналов как есть. Количество программ, которые поддерживают сохранение в таком виде, относительно невелико.Далее цветовые каналы изображения, включая черно-белый канал Y, разбиваются на блоки 8 на 8 пикселей. Каждый блок подвергается дискретно-косинусному преобразованию. Полученные коэффициенты подвергаются квантованию и упаковываются с помощью кодов Хаффмана.Матрица, используемая для квантования коэффициентов, хранится вместе с изображением. Обычно она строится так, что высокочастотные коэффициенты подвергаются более сильному квантованию, чем низкочастотные. Это приводит к огрублению мелких деталей на изображении. Чем выше степень сжатия, тем более сильному квантованию подвергаются все коэффициенты.)

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

- JPEG 2000 (— графический формат, который вместо дискретного косинусного преобразования, характерного для JPEG, использует технологию вейвлет-преобразования, основывающуюся на представлении сигнала в виде суперпозиции некоторых базовых функций — волновых пакетов.)

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

7.Аффинные преобразования координат. Системы координат трёхмерной сцены (мировая, объектная, экранная). Однородные координаты. Матрица преобразований и примеры её использования. Виды проецирования. Стереоскопическая проекция.

Афинное преобразование-отображение f:R^n->R^n,которое можно записать в виде: f(x)=M*x+v,где М-обратимая матрица и v принадл. R^n

Иначе говоря, преобразование называется аффинным, если его можно получить следующим образом:

1. Выбрать «новый» базис пространства с «новым» началом координат v;

2. Каждой точке x пространства поставить в соответствие точку f (x), имеющую те же координаты относительно «новой» системы координат, что и x в «старой».

Свойства

* При аффинном преобразовании прямая переходит в прямую.

o Если размерность пространства n>= 2, то любое преобразование пространства (то есть биекция пространства на себя), которое переводит прямые в прямые, является аффинным. Это определение используется в аксиоматическом построении аффинной геометрии

* Частным случаем аффинных преобразований являются движения и преобразования подобия.

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

Аффинное преобразование (affine maping) – точечное взаимно-однозначное отображение плоскости на себя, при котором трем точкам, лежащим на одной прямой, соответствуют три точки, также лежащие на одной прямой. Аффинное преобразование переводит пересекающиеся прямые в пересекающиеся, параллельные - в параллельные. Плоскости в трехмерном пространстве при этом также остаются плоскостями, параллельные плоскости – параллельными. За исключением вырожденных случаев все точки первичной плоскости (или пространства) преобразуются и заполняют все точки вторичной плоскости.

Рассмотрим метод однородных координат. В основе этого метода лежит представление о том, что каждая точка в N-мерном пространстве может рассматриваться как проекция точки из (N+1)-мерного пространства. В частности, точка в трехмерном пространстве представляется четырьмя составляющими, например, ее координаты будут заданы как V=(x, y, z, w). Если w не равно 1, то декартовы координаты точки (X,Y,Z) получаются из соотношения⁶:

[ X Y Z 1 ] = [ (x/w) (y/w) (z/w) 1 ]. (IV.3)

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

В виде формулы:

В матричном виде: