8.7. Алгоритмы вычерчивания отрезков.

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

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

Алгоритм Брезенхема для генерации окружностей. Вначале необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0° до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = О для завершения построения.

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

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

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

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

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

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

Более подробно математическая реализация вопросов визуализации графических объектов приведена в [7].

9. Форматы хранения графической информации

9.1. Форматы

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

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

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

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

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

Форматы можно разделить на три категории:

1. Форматы, хранящие изображение в растровом виде;

2. Форматы, хранящие изображение в векторном виде;

3. Универсальные форматы, совмещающие растровое и векторное представление.

Формат имеет право на существование только по двум причинам:

- хорошо сжимать данные, т.е. уменьшать размер файла;

- содержать дополнительную информацию о сохраненном изображении.

9.2. Векторные форматы файлов

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

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

Векторный формат EPS (Encapsulated PostScript) является вариантом PostScript-файла. Он разработан фирмой Adobe как универсальный формат для нужд цифровой графики и полиграфии.

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

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

Векторный формат PDF (Portable Document Format – (переносимый формат документов) - это еще один формат на базе языка PostScript. А именно, его оптимизированная версия, ориентированная как межплатформенный формат, интегрирующий макет страницы с иллюстрациями, как векторными, так и пиксельными, шрифтами, гипертекстовыми ссылками, звуками и анимационными фрагментами. Для обеспечения небольшого размера используются разные способы компрессии.

Формат AI принадлежит фирме Adobe и является внутренним форматом векторного редактора Adobe Illustrator.

Векторный формат CDR принадлежит фирме Corel и является внутренним форматом векторного редактора CorelDRAW.

Векторные форматы DWG и DXF является внутренним форматом векторного редактора Автокад.

Векторный формат FH с порядковым номером версии принадлежит фирме Macromedia и является внутренним форматом векторного редактора FreeHand.

9.3. Растровые форматы графических изображений

9.3.1. Формат PCX

Формат PCX - один из первых растровых форматов, создан фирмой Zsoft для программы Paintbrush. Основной недостаток формата наличие большого числа версий. В настоящее время не имеет широкого распространения, и используется только для совместимости со старыми программами. Основные характеристики графических форматов смотрите в таблице 7.

9.3.2. Формат BMP

BMP (Windows Bitmap) – растровый рисунок Windows – собственный формат MA Paint. Поддерживается большинством приложений и графических пакетов. Поддерживается всеми графическими редакторами, работающими в ОС Windows. Можно задавать глубину цвета от 1 до 32 бит. Возможно применение сжатия RLE, причем только с глубиной цвета 4 или 8 бит. Но делать этого не рекомендуется, т.к. некоторые программы используют файлы с таким расширением.

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

Основной недостаток – большой размер файла. Из-за примитивной обработки изображения (изображение хранится в виде "снимка с экрана") расходуется много системных ресурсов.

9.3.3. Формат TIFF

TIFF (Togged Image File Format) – формат создан фирмами Aldus и Microsoft специально для хранения сканированных изображений. Название формата означает "теговый изобразительный файл".

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

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

Кроме общеизвестных алгоритмов сжатия может использовать экзотический алгоритм PackBits, созданный для платформы Macintosh, но реализуемый и в РС.

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

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

В последних версиях программы Adobe Photoshop этот формат позволяет сохранять документы со слоями, что ранее было возможно только во внутреннем формате программы PSD. Кстати, появилась возможность выбирать метод сжатия (LZW, Deflate или JPEG) и сохранять копии изображения с разным разрешением (функция "image pyramid").

Совокупность таких тегов образует область IFD, что означает Image File Directory - "указатель изображений файла". Формат позволяет включать в документ несколько таких указателей, а, следовательно, и несколько изображений.

Модифицированный формат TIFF фактически мало уступает собственному формату Adobe Photoshop – PSD.

9.3.4. Формат PSD

В последнее время формат PSD поддерживается несколькими программами (Adobe Illustrator, Corel PHOTO-PAINT и др.), поэтому можно уже говорить о некоторой его универсальности. О последних версиях формата можно долго не говорить – он поддерживает почти все, что используется в растровых форматах. Основные недостатки – очень большой объем файла и ограниченность применения.

9.3.5. Формат GIF

GIF (Graphic Interchange Format) – формат графического обмена, разработан фирмой CompuServe в 1987 году как экономный формат для хранения пиксельных изображений для глобальных сетей. Формат GIF ориентирован на максимальную компактность. Используется только по своему первоначальному назначению – в Интернете. В последней версии 89а позволяет сохранять несколько картинок с указанием времени показа каждой. Результатом является простейшая анимация. Имеется возможность постепенного появления изображения – сначала появляется каждая 8 картинка, затем каждая 4, 2 и т.д. Плюсом является многоплатформенность. Кроме того, формат достаточно эффективно использует память.

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

Формат GIF сходит со сцены из-за своей убогости – 256 цветов, проблемы со сжатием (только LZW), не поддерживает полутоновые изображения и др.

9.3.6. Формат PNG

PNG – (Portable Network Graphics) – преемник формата GIF - переносимая графика для сети, произносится как "пинг". Является форматом, который специально создан для размещения графики на Web-страницах. Поддерживает 48 бит/пиксель. Используется не запатентованный алгоритм сжатия Deflection, поддерживает прозрачность слоев, сохраняет текстовые вставки.

Существует два варианта формата: PNG8 и PNG24, цифры в названии формата означают максимальную глубину цвета. В варианте PNG24 реализована поддержка градационной прозрачности за счет альфа канала с 256 оттенками серого.

Недостатками являются: отсутствие сжатия с потерями, и формат не сохраняет информацию о нескольких изображениях.

9.3.7. Формат JPEG

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

Существует несколько разновидностей формата. Формат baseline лучше сжимается, но не поддерживается некоторыми браузерами. Формат progressive JPEG несколько хуже сжимает, но поддерживает чересстрочный вывод изображения, значительно сокращая время передачи и вывода изображения. Существует еще несколько малораспространенных разновидностей (ariphmetic и loseless).

Недостатками JPEG являются:

• ограничения сжатия из-за ограничения размера блока 8х8;

• на высоких уровнях сжатия проявляется блочность структуры изображения;

• закругление острых углов изображения;

• размывание тонких элементов изображения;

• невозможность отображения по частям (как в GIF).

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

9.3.8. Формат RAW

RAW – (Read After Write) – представляет самые широкие возможности для фотографии. Другие форматы, используемые в фотографии, записывают вместе с изображением и информацию о балансе белого, цветовой насыщенности, резкости и др. В формат RAW записывается само, не обработанное изображение. Отдельно в заголовке указываются параметры, выбранные фотографом. В программах, называемых RAW-конверторами можно решать, применять ли выбранные при съемке установки или применить другие. Формат позволяет даже скорректировать неверно выбранную экспозицию, благодаря некоторой избыточности информации в файле (глубина цвета 16 бит против 8 бит в JPEG и TIFF). Некоторые производители фотоаппаратуры привносят свои изменения в формат RAW, поэтому для работы с ним требуется уникальный RAW-конвертор. Универсальным RAW-конвертором является Adobe Photoshop CS8. Размеры файла в формате RAW меньше, чем в формате TIFF, т.к. изображение не проходит обработку, а вся интерполяция осуществляется на компьютере.

В таблице 7 приведена краткая характеристика основных растровых графических форматов.

Таблица 7

Формат	Особенности	Бит/ пикс	Макс. число цветов	Цветовые модели	Сжатие	Кодирование нескольких изображений	Поддержка
PCX	Формат примитивен, исп. DOS программами	24	16.7х10^6	RGB	нет	-
BMP	Потоковая запись пикселей	24	16.7х10^6	RGB	RLE	-	Индексированные цвета
TIFF	Запись изображений в поля	24	16.7х10^6	Все известные	LZW, RLE, PackBits JPEG	+	Альфа-каналы, предварительное. цветоделение, слои, прозрачность
PSD	Максимальные возможности обработки изображения	24 48	16.7х10^6 281,4x10^12	Все известные	RLE	+	Альфа-каналы, слои, контуры, прозрачность, цветовые профили, векторная графика, маски, плашечные цвета
GIF	Использование только в Интернете, эффективное использование памяти	8	256	RGB	LZW	+	Альфа-канал, прозрачность
PNG	Использование только в Интернете	48	281,4x10^12	RGB	Deflec- tion	-	Альфа-канал, прозрачность. Сохранение текстовых вставок
JPEG	Самое широкое использование	24	16.7х10^6	RGB	JPEG	-	Монохромные изображения, выделение приоритетных областей, сжатие без потерь
RAW	Большие возможности по обработке фотографий	24	16.7х10^6	RGB	-	-	Нет

11. Краткие сведения о движущихся изображениях

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

Под анимацией (animation – оживление) изображений понимается автоматизированный процесс визуализации последовательности изображений – кадров (frames). Каждый кадр фиксирует определенные изменения состояния сцены. Базовым принципом компьютерной анимации (как, собственно говоря, и любой другой) является быстрая смена последовательности кадров, фиксирующих промежуточные фазы движения, перед глазами наблюдателя.

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

Обычно частота воспроизведения кадров не должна быть ниже 12 кадров в секунду. При выборе той или иной целевой платформы важно правильно выбрать покадровую частоту анимации. Так, кинематограф работает с частотой 24 кадра в секунду, в телевизионных форматах PAL/SECAM и NTSC частота кадров равняется 25 и 30 соответственно.

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

С другой стороны, ключевая анимация не всегда является оптимальным выбором. Например, если необходимо заставить объект совершить сложный пируэт в пространстве, то, наверное, проще нарисовать для него нужную сплайновую траекторию, чем определять десятки (а то и сотни!) ключевых кадров. Такая, не требующая задания большого количества ключевых кадров, анимация называется параметрической анимацией. Обычно она реализована как набор предустановленных анимационных эффектов, plug-in-модулей, например случайного изменения параметра или движения по траектории. Достаточно задать время начала и завершения такого эффекта, настроить его параметры, а обо всем остальном позаботится анимационная программа.

Итоговая визуализация (rendering) - заключительный этап работы со сценой.

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

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

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

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

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

- в блестящих поверхностях могут присутствовать отражения других объектов;

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

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

- трассирование лучей;

- излучение.

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

Если поверхность не зеркальная и не прозрачная, за ней образуется тень. Цвет самой поверхности в точке пересечения вычисляется с учетом характеристик источников освещения.

Для зеркальных поверхностей делается оценка дальнейшего прохождения отраженного света.

Для прозрачных материалов - пропущенного света.

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

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

Однако он имеет два существенных недостатка:

- высокая сложность и, как следствие, малая скорость вычислений;

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

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

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

- большие затраты памяти при вычислениях;

- отсутствие в полученном изображении отражений и преломлений света в прозрачных поверхностях.

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

Отдельный кадр анимации ничем не отличается от рассмотренных нами ранее изображений, созданных либо с помощью программ векторной графики (3ds max, Maya), либо программ растровой графики (Flash Macromedia).

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

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

Другой группой движущихся изображений является цифровое кино и телевидение.

Важнейшими процедупами здесь являются:

- создание цифрового кино – этот процесс прекрасно реализуется современными цифровыми устройствами – цифровыми фото- и видеокамерами;

- видеомонтаж изображений. Существуют профессиональные и любительские программы видеомонтажа (Canopus, Ulead, Pinnacle), но для тех и других можно рекомендовать универсальную программу фирмы Adobe – Adobe Premier.

- сжатие движущихся изображений.

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

Стандарты сжатия движущихся изображений MPEG (Motion Picture Experts Group) разрабатываются и принимаются имеющей такое же название группой экспертов при Международной организации стандартизации ISO. Все форматы сжатия семейства MPEG (MPEG I, MPEG 2, MPEG 4, MPEG 7, MPEG 21) используют высокую избыточность информации в изображениях, разделенных малым интервалом времени. Между двумя соседними кадрами обычно изменяется только малая часть сцены - например, происходит плавное смещение небольшого объекта на фоне фиксированного заднего плана. В этом случае полная информация о сцене сохраняется выборочно - только для опорных изображений. Для остальных кадров достаточно передавать разностную информацию: о положении объекта, направлении и величине его смещения, о новых элементах фона, открывающихся за объектом по мере его движения. Причем эти разности можно формировать не только по сравнению с предыдущими изображениями, но и с последующими (поскольку именно в них по мере движения объекта открывается ранее скрытая часть фона).

Стандарт MPEG-1, используемый в основном при записи видеопрограмм на компакт-диски, был окончательно утвержден в 1993 г., а стандарт MPEG-2, предназначенный в первую очередь для телевизионного вещания, был принят в ноябре 1994 г.

Форматы сжатия семейства MPEG сокращают объем информации следующим образом:

- Устраняется временная избыточность видео (учитывается только разностная информация).

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

- Устраняется часть информации о цветности.

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

Определены три основных части стандарта MPEG-2:

- 13818-1 - Systems - устанавливает правила объединения потоков;

- 13818-3 - Audio - определяет кодовое представление сигналов звукового сопровождения;

- 13818-2 - Video - регламентирует кодовое представление и процесс декодирования, сжатие потока за счет устранения пространственной и временной избыточности.

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

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

- группа изображений;

- изображение;

- срез;

- макроблок;

- слайс;

- блок.

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

Определены три типа изображений, в соответствии с методом дифференциального кодирования:

I (Intra-coded picture) - изображение кодируется с использованием только той информации, которая заложена в нем самом; устраняется пространственная избыточность – внутренний кадр;

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

В (Bidirectional predictive coded picture) - изображение, при кодировании которого используется предсказание, сформированное на основе предшествующих и последующих I или Р кадров - двунаправленный кадр.

При кодировании Р и В кадров используется межкадровое кодирование, устраняющее и пространственную и временную избыточность. Серия изображений, содержащих одно I, называется группой изображений, стрелками показывается направление предсказания. Чем больше группа - тем больше компрессия. На рисунке 52 показана видеопоследовательность трех изображений с предсказаниями.

С информационной точки зрения, каждое изображение представляет собой три прямоугольных матрицы отсчетов изображений: яркостную Y и две цветности Св и Cr. Стандарт MPEG-2 допускает различные структуры матриц (4:2:0; 4:2:2; 4:4:4).

Каждое изображение делится на срезы, которые состоят из макроблоков. Макроблок содержит блоки размером 8x8 элементов изображения (реже 16x16 элементов); группу из четырех блоков с отсчетами яркости и группы блоков с отсчетами цветности, число которых зависит от формата (по 1, по 2, по 4). Группа следующих друг за другом макроблоков называется слайсом. Число макроблоков в слайсе может быть произвольным, главное, чтобы слайсы в изображении не перекрывались.

Рисунок 52

Форматы сжатия MPEG сжимают только опорные кадры - I-кадры. В промежутки между ними включаются кадры, содержащие только изменения между двумя соседними 1-кадрами - Р-кадры. Для того чтобы сократить потери информации между I-кадром и Р-кадром, b вводятся так называемые В-кадры. В них содержится информация, которая берётся из предшествующего и последующего кадров. При кодировании в форматах сжатия MPEG формируется цепочка кадров разных типов. Типичная последовательность кадров выглядит следующим образом: IBBPBBIBBPBBIBB... Соответственно, последовательность кадров в соответствии с их номерами будет воспроизводиться в следующем порядке: 1423765...

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

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

Стандарт предполагает сокращение не только пространственной, но и временной избыточности. После компрессии объем изображения Р типичных видео сюжетов составляет 35% от I, В - 25% от I. Таким образом, в три раза уменьшается скорость потока данных при приблизительно тех же искажениях. Артефакты же связанные с движением (в отличие от JPEG и DV) замечаемы тем меньше, чем быстрее движутся изображения.

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

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

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

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

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

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

Если запись компрессионного потока производится не в условиях реального времени, то можно использовать и другие способы управления скоростью. Например, выполнять компрессию в два прохода. На первом подбираются параметры, обеспечивающие максимальное качество; на втором - производится компрессия с найденными параметрами. Есть и другие способы: возможно выделение заранее кадров с большим количеством детальных быстродвижущихся объектов и помещение их для принудительного кодирования типа I. Такой способ используется в DVD.

Т.к. стандарт MPEG не регламентирует сам процесс кодирования, а изображения (блоки представления) рассматриваются как результат декодирования блоков доступа, то декодер может приступить к декодированию изображения типа В только после того, как получены предыдущие и последующие блоки. Во избежание установки буферов, кодирование изображений выстраивается в порядке декодирования, т.е. вместо I-B-B-P формируют I-P-B-B, что и было продемонстрировано на рисунке 45.

Для наибольшей эффективности применения на практике и совместимости оборудования стандарта MPEG-2 от разных производителей, выделено несколько подмножеств, называемые профилями. Профиль - это подмножество стандарта для специализированного применения, задающее алгоритмы и средства компрессии. Уровни внутри каждого профиля связаны с параметрами компрессии изображения (табл. 8). Профили MPEG-2: Simple - простой; Main - основной; SNR (Signal to Noise Ratio) - с масштабируемым квантованием; Spatial - с масштабируемым пространственным разрешением; High -высокий; 422 - студийный.

Таблица 8

	Уровень	Simple	Main	SNR	Spatial	High	422
Профиль	Изображения	1иР	1,РиВ	I, Р и В	I, Р и В	I, Ри В	1,РиВ
	Формат	4:2:0	4:2:0	4:2:0	4:2:0	4:2:0 4:2:2	4:2:2
High	Отсч. в стр.	-	1920	-	-	1920	-
	Стр. в кадре		1152			1152
	Кадров в сек		60			60
	Vmax, Мбит/с		80			100
High 1440	Отсч. в стр.	-	1440	-	1440	1440	-
	Стр. в кадре		1152		1152	1152
	Кадров в сек		60		60	60
	Vmax, М6ИТ/С		60		60	80
Main	Отсч. в стр.	720	720	720	-	720	720
	Стр. в кадре	576	576	576		576	608
	Кадров в сек	30	30	30		30	30
	Vmax, М6ИТ/С	15	15	15		20	50
Low	Отсч. в стр.	-	352	352	-	-	-
	Стр. в кадре		288	288
	Кадров в сек		30	30
	Vmax, М6ИТ/С		4	4

Например, профиль SNR, как и Spatial, поддерживают все типы изображений, используя обычное кодирование на основе предсказания с компенсацией движения; 422 обеспечивает полное разрешение, соответствующее рекомендации ITU-R 601, монтаж с точностью до кадра, допускает многократную перезапись.

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

Предусмотрены следующие виды масштабируемости :

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

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

3. Масштабируемость по времени позволяет получать от одного источника видеоинформации с двумя уровнями разрешающей способности по времени - чересстрочной разверткой 25 Гц, или прогрессивной 50 Гц;

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

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

Упрощенная структура потока данных на выходе кодера MPEG-2 приведена на рисунке 53.

Регламентированы две возможные формы единого потока - программный и транспортный потоки.

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

В начале заголовка идет 32 битный код старта, состоящий из стартового префикса и идентификатора. Спецификация определяет разрешенные значения чисел в поле идентификатора для 32 элементов потока звука и 16 элементов потока видеоданных.

Рисунок 53

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

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

- первый байт каждого РЕ5-пакета должен быть первым байтом полезной нагрузки;

- каждый транспортный пакет может содержать данные лишь одного РЕ5-пакета;

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

Структура транспортного потока оптимизирована для условий передачи данных в каналах связи с шумами. Для разрешения проблем, связанных с действием шума, добавляются 16 проверочных байтов, что позволяет исправить 8 битов. Пакет начинается с 4-байтного заголовка, который не является уникальным, однако в купе с определенной длиной пакета 188 байт, упрощает определение. Для опознавания пакетов, принадлежащих одному элементарному потоку, используется 13 - битный идентификатор. Важный компонент структуры - счетчик непрерывности, который инкрементирует последовательности элементарных пакетов, принадлежащих одному потоку. Это позволяет определить потерю одного из пакетов и маскировать ошибки

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

Определено три вида таблиц с программной информацией:

- таблица соединения программ PAT (сообщает список номеров всех программ);

- таблица плана программ РМТ (сведения о программе и её элементарные потоки);

- таблица условного доступа CAT.

Все вместе таблицы образуют иерархический индексный механизм.

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

Компенсацию задержек и синхронизацию обеспечивают метки времени, которые ставятся в соответствии каждому блоку доступа и сообщается декодеру точное время извлечения блока. Текущее системное время обеспечивается опорным генератором, однако, должен быть некоторый сдвиг, т.к. метка сообщает время в будущем. Сдвиг должен быть достаточно большим, чтобы блок доступа прошел буфер. Для синхронизации времени текущее время кодера регулярно передается декодеру (в единицу периода частоты 27 МГц). Метки программного времени должны появляться не реже, чем раз в 0,1 сек. Метки не должны сопровождать каждый блок доступа, они переносятся в заголовках PES-пакетов.

Основной целью создания стандарта MPEG-2 было желание работать с потоком видеоданных как с любым потоком данных. Благодаря этому, возможен монтаж программы, компрессированной MPEG-2, однако смонтированная программа должна обладать всеми свойствами потока данных MPEG-2. Возможности монтажа предоставляет студийный профиль 422, реализованный в формате видеозаписи ВЕТАСАМ SX. Данный профиль позволяет выполнить монтаж путем дописывания нового потока без нарушения непрерывности смонтированного потока в точках монтажа. Такой способ, основанный на перекодировании кадров с двунаправленным предсказанием в сочетании с опережающим считыванием, позволяет выбирать точку монтажа в любом месте и выполнять монтаж с кадровой точностью.

Транскодирование (изменение скорости потока с использованием параметров первоначального кодирования) позволяет минимизировать искажения процесса.

Широкое распространение видеокомпрессии делает все более необходимым объединение кодированных программ не только без декодирования, но и без изменения содержания блоков доступа. По своей сути это, конечно, не просто коммутация, а сращивание потоков, при котором полученный поток будет соответствовать синтаксису и семантике MPEG-2 - склейка потоков. Но есть и проблемы коммутации потоков:

- Р и В кадры не могут быть восстановлены без опорных изображений, а это возможно при коммутации;

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

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

Эти и другие проблемы приводят к тому, что только некоторые точки подходят для склейки.

В стандартах MPEG не описано построение кодера, а лишь определено описание потока данных на его выходе.

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

Выходной сигнал кодера может формироваться в одном или нескольких общепринятых стандартов - наиболее широко используется DVB-ASI, реже используют DVB-SPI, RS-422. Максимальная скорость потока на выходе кодера определяется выбранным профилем и уровнем компрессии, например: MP@ML скорость составляет 15 Мбит/сек; 4:2:2 MP@ML - 50 Мбит/сек. Из проведенных исследований видно, что для скоростей меньше 10 Мбит/сек, нет смысла использовать качество 4:2:2, особенно для быстроменяющихся картин, учитывая, что использование скоростей 15 - 20 Мбит/сек на сегодняшний день не принято (и слишком дорого).

По сравнению с MPEG 1, формат сжатия MPEG 2 обеспечивает лучшее разрешение изображения при более высокой скорости передачи видео данных за счёт использования новых алгоритмов сжатия и удаления избыточной информации, а также кодирования выходного потока данных. Также формат сжатия MPEG 2 даёт возможность выбора уровня сжатия за счёт точности квантования. Для видео с разрешением 352x288 пикселей формат сжатия MPEG 1 обеспечивает скорость передачи 1,2-3 Мбит/с, a MPEG 2 - до 4 Мбит/с.

По сравнению с MPEG 1, формат сжатия MPEG 2 обладает следующими преимуществами:

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

- В формате сжатия MPEG 2 точность векторов движения увеличена до 1/2 пикселя.

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

- В формат сжатия MPEG 2 включены дополнительные режимы прогнозирования.

Несмотря на все плюсы стандарта MPEG-2, главным его минусом является то, что гибкость стандарта оборачивается трудностями в обеспечении эксплуатации и совместимости.

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

Диапазон скоростей передачи данных, который поддерживает формат сжатия видео изображений MPEG 4, гораздо шире, чем в MPEG 1 и MPEG 2. Дальнейшие разработки специалистов направлены на полную замену методов обработки, используемых форматом MPEG 2. Формат сжатия видео изображений MPEG 4 поддерживает широкий набор стандартов и значений скорости передачи данных. MPEG 4 включает в себя методы прогрессивного и чересстрочного сканирования и поддерживает произвольные значения пространственного разрешения и скорости передачи данных в диапазоне от 5 Кбит/с до 10 Мбит/с. В MPEG 4 усовершенствован алгоритм сжатия, качество и эффективность которого повышены при всех поддерживаемых значениях скорости передачи данных.

В октябре 1996 года группа MPEG приступила к разработке формата сжатия MPEG 7, призванным определить универсальные механизмы описания аудио и видео информации. Этот формат получил название Multimedia Content Description Interface. В отличие от предыдущих форматов сжатия семейства MPEG, MPEG 7 описывает информацию, представленную в любой форме (в том числе в аналоговой форме) и не зависит от среды передачи данных. Как и его предшественники, формат сжатия MPEG 7 генерирует масштабируемую информацию в рамках одного описания.

Формат сжатия MPEG 7 использует многоуровневую структуру описания аудио и видео информации. На высшем уровне прописываются свойства файла, такие как название, имя создателя, дата создания и т.д. На следующем уровне описания формат сжатия MPEG 7 указывает особенности сжимаемой аудио или видео информации - цвет, текстура, тон или скорость. Одной из отличительных особенностей MPEG 7 является его способность к определению типа сжимаемой информации. Если это аудио или видео файл, то он сначала сжимается с помощью алгоритмов MPEG I, MPEG 2, MPEG 4, а затем описывается при помощи MPEG 7. Такая гибкость в выборе методов сжатия значительно снижает объем информации и ускоряет процесс сжатия. Основное преимущество формата сжатия MPEG 7 над его предшественниками состоит в применении уникальных дескрипторов и схем описания. Это делает возможным автоматическое выделение информации, как по общим, так и по семантическим признакам, связанным с восприятием информации человеком. Процедура занесения в каталог и поиска данных находятся вне сферы рассмотрения этого формата сжатия.

Разработка формата сжатия MPEG 21 - это долговременный проект, который называется "Система мультимедийных средств" (Multimedia Framework). Над разработкой этого формата сжатия эксперты начали работать в июне 2000 г. На первых этапах планировалось провести расширение, унификацию и объединение форматов MPEG 4 и MPEG 7 в единую обобщающую структуру. Подразумевалось, что она будет обеспечивать глубокую поддержку управления правами и платежными системами, а также качеством предоставляемых услуг.

Форматы сжатия видео семейства MPEG являются открытым стандартом, дополнения и переработки в который вносятся постоянно.

Список литературы

1. Айден К., Фибельман X., Крамер М. Аппаратные средства PC. - СПб.: BHV - Санкт-Петербург, 1996.

2. Айриг С., Айриг Э. Подготовка цифровых изображений для печати. -Минск: Попурри, 1997.

3. Кодеры и декодеры MPEG, А. Ануфриев. Информационно-технический журнал - изд. ООО «Издательство 625», №7, 2003.

4. Банах Д.Т., Джонс Т. Autodesk Inventor – М. Лори. 2002.

5. Барг П. Цифровая фотография. – М. Гранд.2005.

6. Информатика. Базовый курс. Под ред. Симоновича С.М. - Санкт-Петербург. Питер, 2001.

7. Люкшин Б.А. Компьютерная графика. Учебное пособие. – Томск, 2005.

8. Мак-Клелланд Д. Adobe Photoshop 7. Библия пользователя. – М. Диалектика, 2001.

9. Маров М. 3ds max 4. – Санкт-Петербург. Питер, 2002.

10. Петров М.Н., Молочков В.П. Компьютерная графика. Учебник для вузов. - Санкт-Петербург. Питер, 2006.

11. Пономаренко С. И. Adobe Photoshop 6 в подлиннике. - СПб.: БХВ-Петербург, 2001.

12. Шлихт Г. Ю. Цифровая обработка цветных изображений. - М.: ЭКОМ, 1997.