1. Описание форматов хранения графической информации



страница1/6
Дата29.10.2016
Размер0,93 Mb.
  1   2   3   4   5   6


ВКР 0606700256.00.00.00



1.Описание форматов хранения графической информации.

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


1.1. Векторные форматы

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

Таблица 1 - Некоторые векторные форматы

Название формата

Программы, которые могут открывать файлы

WMF
Windows MetaFile

Большинство приложений WINDOWS

EPS Encapsulated PostScript

Большинство настольных издательских систем и векторных программ, некоторые растровые программы

DXF Drawing Interchange Format

Все программы САПР, многие векторные редакторы, некоторые настольные издательские системы

CGM Computer Graphics Metafile

Большинство программ редактирования векторных рисунков, САПР и издательские системы

1.2. Растровые форматы

В файлах растровых форматов запоминаются:

- размер изображения — количество видео пикселей в рисунке по горизонтали и вертикали

- битовая глубина — число битов, используемых для хранения цвета одного видео пикселя

- данные, описывающие рисунок (цвет каждого видео пикселя рисунка), а также некоторая дополнительная информация.

В файлах растровой графики разных форматов эти характеристики хранятся различными способами.

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

Изображения фотографического качества, полученные с помощью сканеров с высокой разрешающей способностью, часто занимают несколько мегабайт. Например, если размер изображения 1766 х 1528, а количество используемых цветов — 16777216, то объём растрового файла составляет около 8 Мб (информация о цвете видео пикселей в файле занимает 1766 х 1528 х 24 / 8 / 1024 / 1024 Мб).

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

Методы сжатия делятся на две категории:

• сжатие файла с помощью программ — архиваторов;

• сжатие, алгоритм которого включён в формат файла.

В первом случае специальная программа считывает исходный файл, применяет к нему некоторый сжимающий алгоритм (архивирует) и создаёт новый файл. Выигрыш в размере нового файла может быть значительным. Однако этот файл не может быть использован ни одной программой до тех пор, пока он не будет преобразован в исходное состояние (разархивирован). Поэтому такое сжатие применимо только для длительного хранения и пересылки данных, но для повседневной работы оно неудобно. В системах DOS и WINDOWS наиболее популярными программами сжатия файлов являются ZIP, ARJ, RAR и другие.

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



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

Таблица 2 - Некоторые форматы растровых изображений

Название
формата


Программы, которые могут открывать файлы

Метод сжатия

BMP
Windows Device
Independent Bitmap

Все программы WINDOWS, использующие растровую графику

RLE для 4- и 8-битных изображений (по желанию)

PCX
Z - Soft PaintBrush

Почти все графические приложения для PC

RLE (всегда)

GIF
Graphic Interchange Format

Почти все растровые редакторы; большинство издательских пакетов; векторные редакторы, поддерживающие растровые объекты

LZW (всегда)

TIFF
Tagged Image File Format

Большинство растровых редакторов и настольных издательских систем; векторные редакторы, поддерживающие растровые объекты

LZW (по желанию) и др.

TGA
TrueVision Targa

Программы редактирования растровой графики

RLE (по желанию)

PPM

Почти все программы, использующие растровую графику

-

IMG
Digital Research GEM Bitmap

Некоторые настольные издательские системы и редакторы изображений WINDOWS

RLE (всегда)

JPEG
Joint Photographic Experts Group

Последние версии программ редактирования растровой графики; векторные редакторы, поддерживающие растровые объекты

JPEG (можно выбрать степень сжатия)

JPEG-2000
Joint Photographic Experts Group

Последние версии программ редактирования растровой графики

JPEG2000 (можно выбрать степень сжатия)



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

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

В то время уже были достаточно распространены среди пользователей персональных компьютеров такие графические форматы, как BMP, PCX, GIF. Но даже уменьшение объема графической информации в два раза оказалось недостаточным для современных графических систем. В связи с этим с конца 80х годов две крупнейшие в мире организации стандартов CCITT и ISO объединили свои усилия для выработки единого стандарта формата графического файла, сжатого с потерями. Новый стандарт получил свое название JPEG по имени группы разработчиков Joint Photographic Experts Group.

Сделаем небольшое замечание: JPEG прежде всего является методом сжатия. Его нельзя рассматривать в качестве полноценного стандарта представления изображений. Поэтому в нем не задаются такие специфические параметры изображения, как геометрический размер пикселя, пространство цветов или чередование битовых строк. То же можно сказать и о JPEG2000, и о JPEG-LS — это методы сжатия, а не полноценные стандарты.

1.1. JPEG

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

a description...
Рисунок 1 - Шаги работы кодера JPEG


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

  • Дискретное косинусное преобразование (ДКП) используется кодером JPEG для преобразования изображения от его пространственного представления к спектральному.

  • Округление (квантование) — этап, на котором происходит основная потеря информации за счет округления несущественных, высокочастотных ДКП-коэффициентов.

  • Сжатие — кодирование полученных данных стандартными методами (кодирование повторов, арифметическое кодирование и т.д.)

2.1.1. Препроцессинг

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



a description...

Рисунок 2 - Пример работы ICT преобразования



a description...

Рисунок 3 - Матрица ICT преобразования

Помимо ICT преобразования, на данном этапе исходное изображение разбивается на малые квадратные блоки и выполняется сдвиг основания значений цвета относительно нуля для корректного пространственного представления изображения: [0,2p - 1] -> [-2p-1, 2p-1 - 1]. Эти шаги важны для эффективной работы кодера на следующем этапе.

2.1.2. ДКП

Являясь ключевым шагом алгоритма сжатия, дискретное косинусное преобразование (далее ДКП) представляет собой разновидность преобразования Фурье и, также как и последнее, имеет обратное преобразование (ОДКП). Если рассматривать изображение как совокупность пространственных волн, где оси X и Y соответствуют ширине и высоте картинки, а по оси Z откладываются значения цвета соответствующих пикселей, то можно перейти от пространственного представления картинки к ее спектральному представлению и обратно. ДКП преобразует матрицу пикселей размера N x N в матрицу частотных коэффициентов соответствующего размера.



a description...Рисунок 4 - Формулы ДКП

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

Из формул (на рисунке 4) видно, что вычисление одного элемента результирующей матрицы требует O(N2) времени, поэтому почти невозможно выполнить преобразование всей матрицы целиком. Группа разработчиков JPEG предложила оптимальный вариант решения этой проблемы: разбивать исходную матрицу на квадраты стандартного размера 8x8 и выполнять преобразование каждого из них. Использование блоков большего размера позволит улучшить качество сжатия, но не до бесконечности, так как слишком мала вероятность того, что сильно отдаленные точки похожи друг на друга.

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

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

2.1.3. Округление

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



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

3

5

7

9

11

13

15

17

5

7

9

11

13

15

17

19

7

9

11

13

15

17

19

21

9

11

13

15

17

19

21

23

11

13

15

17

19

21

23

25

13

15

17

19

21

23

25

27

15

17

19

21

23

25

27

29

17

19

21

23

25

27

29

31

Пример матрицы округления с фактором качества равным 2.

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



2.1.4. Сжатие

Последний этап работы алгоритма кодирования JPEG — это сжатие. После обработки матрицы ДКП с помощью МО, в результирующей матрице появляется большое количество нулей, особенно в высокочастотной области (правый нижний угол).

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

a description...

Рисунок 5 - Порядок обхода матрицы зигзагом.

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



2.1.5. Декодирование

Так как ДКП является преобразованием Фурье, к нему существует обратное дискретное косинусное преобразование (ОДКП). Алгоритм декодирования повторяет алгоритм кодирования в обратном порядке.




Поделитесь с Вашими друзьями:
  1   2   3   4   5   6


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница