Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

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

Между этими двумя множествами нет взаимно однозначного соответствия. Так, различные модификации алгоритма RLE реализованы в огромном количестве форматов. В том числе в TIFF, BMP, PCX. И, если в определенном формате какой-либо файл занимает много места, это не означает, что плох соответствующий алгоритм компрессии. Это означат, зачастую лишь то, что реализация алгоритма, использованная в этом формате, дает для данного изображения плохие результаты. Не более того. (См. примеры в приложении.)

В то же время многие современные форматы поддерживают запись с использованием нескольких алгоритмов архивации, либо без использования архивации. Например, формат TIFF 6.0 может сохранять изображения с использованием алгоритмов RLE-PackBits, RLE-CCITT, LZW, Хаффмана с фиксированной таблицей, JPEG, а может сохранять изображение без архивации. Аналогично форматы BMP и TGA позволяют сохранять файлы как с использованием алгоритма компрессии RLE (разных модификаций!), так и без использования оной.

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

Можно пополнить перечень ситуаций некорректного сравнения алгоритмов. При сохранении абсолютно черного изображения в формате 1000х1000х256 цветов в формате BMP без компрессии мы получаем, как и положено, файл размером чуть более 1000000 байт, а при сохранении с компрессией RLE, можно получить файл размером 64 байта. Это был бы превосходный результат — сжатие в 15 000 раз(!), если бы к нему имела отношение компрессия. Дело в том, что данный файл в 64 байта состоит только из заголовка изображения, в котором указаны все его данные. Несмотря на то, что такая короткая запись изображения стала возможна именно благодаря особенности реализации RLE в BMP, еще раз подчеркну, что в данном случае алгоритм компрессии даже не применялся. И то, что для абсолютно черного изображения 4000х4000х256 мы получаем коэффициент компрессии 250 тысяч раз, совсем не повод для продолжительных эмоций по поводу эффективности RLE. Кстати — данный результат возможен лишь при определенном положении цветов в палитре и далеко не на всех программах, которые умеют записывать BMP с архивацией RLE (однако все стандартные средства, в т.ч. средства системы Windows, читают такой сжатый файл нормально).

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

Дело в том, что даже для простых форматов одно и то же изображение в одном и том же формате с использованием одного и того же алгоритма архивации можно записать в файл несколькими корректными способами. Для сложных форматов и алгоритмов архивации возникают ситуации, когда многие программы сохраняют изображения разными способами. Такая ситуация, например, сложилась с форматом TIFF (в силу его большой гибкости). Долгое время по-разному сохраняли изображения в формат JPEG, поскольку соответствующая группа ISO (Международной Организации по Стандартизации) подготовила только стандарт алгоритма, но не стандарт формата. Сделано так было для того, чтобы не вызывать “войны форматов”. Абсолютно противоположное положение сейчас с фрактальной компрессией, поскольку есть стандарт “де-факто” на сохранение фрактальных коэффициентов в файл (стандарт формата), но алгоритм их нахождения (быстрого нахождения!) является технологической тайной создателей алгоритма. В результате для вполне стандартной программы-декомпрессора могут быть подготовлены файлы с коэффициентами, существенно различающиеся как по размеру, так и по качеству получающегося изображения.

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

Вывод 2: Если вы не умеете пользоваться программами архивации или пользуетесь программами, в которых “для простоты использования” убрано управление параметрами алгоритма — не удивляйтесь, почему для отличного алгоритма компрессии в результате получаются большие файлы.

Указатель терминов

B

BMP 30; 31

Broadcasting 5

C

CCITT Group 3 6; 15; 16; 17

G

GIF 6; 12; 22; 30

I

IFS 23; 25; 26; 27

Internet 6

ISO 17; 20; 22; 31; 32; 33

Iterated Function System 23

J

JBIG 17; 18; 29

JPEG
5; 6; 7; 15; 18; 19; 20; 21; 22; 27; 29; 30; 31; 32

L

L₂ мера 26

Lossless JPEG 18

LZ 9; 10

LZW 6; 7; 9; 10; 11; 12; 13; 26; 29; 31

M

MMX 6

P

PCX 8; 9; 30

Pixel 3; 27

PSNR 19

Q

Quantization 20

R

RLE 7; 8; 9; 18; 29; 30; 31

RMS 19

T

TGA 9; 31

TIFF 9; 12; 17; 30; 31

W

Wavelet 6; 28

WWW 4; 33

Y

YCrCb 20

YUV 20

А

Алгоритм Хаффмана
3; 14; 15; 16; 18; 28; 29; 31

Д

Двумерное аффинное преобразование
4

ДКП 20

З

Зигзаг-сканирование 21

К

Класс изображений 3

Класс приложений 4

Код завершения серии 15

Код конца информации 10

Код с минимальной избыточностью 14

Код слова 13

Кодирование 13

Л

Лестничный эффект 28

М

Машина Барнсли 23

Н

Неподвижная точка (аттрактор) 24

П

Палитрa 3

Папоротник Барнсли 23

Префикс слова 13

Р

Рекурсивное сжатие 28; 29

С

Свойство префикса 13

Серия 15

Система RGB 3

Системы цветопредставления 3

Составные (дополнительные) коды 15

Схема 13

Т

Треугольник Серпинского 23

Ф

Фрактал 23

Фрактальный алгоритм 23

Э

Элементарный код 13

Эффект Гиббса 22

Литература

Литература по алгоритмам сжатия

1. [1] G.K.Wallace. “The JPEG still picture compression standard.” Communication of ACM. Volume 34. Number 4 April 1991.

2. [2] B.Smith, L.Rowe. “Algorithm for manipulating compressed images.” Computer Graphics and applications. September 1993.

3. [3] A. Jacquin, “Fractal image coding based on a theory of iterated contractive image transformations”, Visual Comm. and Image Processing, vol. SPIE-1360, 1990.

4. [4] Y. Fisher, “Fractal image compression”, SigGraph 92.

5. [5] “Progressive Bi-level Image Compression, Revision 4.1”, ISO/IEC JTC1/SC2/WG9, CD 11544, September 16, 1991.

6. [6] W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, R.B. Arps, “An overview of the basic principles of the Q-coder adaptive binary arithmetic coder”, IBM Journal of research and development, Vol.32, No.6, November 1988, pp. 771-726.

7. [7] D.A. Huffman, “A method for the construction of minimum redundancy codes.” In processing. IRE val.40 1962 pp. 1098-1101.

8. [8] Standardisation of Group 3 Facsimile apparatus for document transmission. CCITT Recommendations. Fascicle VII.2. T.4. 1980.

9. [9] С.В Яблонский “Введение в дискретную математику”. М. “Наука”, 1986. Раздел “Теория кодирования”.

10. [10] А.С. Климов. “Форматы графических файлов”. С.-Петербург, Изд. “ДиаСофт” 1995.

11. [11] Д.С. Ватолин. “Сжатие статических изображений” Открытые системы сегодня. Номер 8 (29) Апрель 1995

12. [12] Д.С. Ватолин. “MPEG - стандарт ISO на видео в системах мультимедиа” Открытые системы. Номер 2. Лето 1995

13. [13] Д.С. Ватолин. “Применение фракталов в машинной графике” ComputerWorld-Россия. Номер 15. 12 декабря 1995

14. [14] Д.С. Ватолин. “Тенденции развития алгоритмов архивации графики” Открытые системы. Номер 4. Зима 1995

15. [15] Д.С. Ватолин. “Фрактальное сжатие изображений” ComputerWorld-Россия. Номер 6 (23). 20 февраля 1996

16. [16] Д.С. Ватолин. “Использование графики в WWW” ComputerWorld-Россия. Номер 15 (32). 23 апреля 1996

Литература по форматам изображений

1. [17] А.С. Климов “Форматы графических файлов”,НИПФ “ДиаСофт Лтд”, 1995.

2. [18] В.Ю. Романов “Популярные форматы файлов для хранения графических изображений на IBM PC”, Москва “Унитех”, 1992

3. [19] Том Сван “Форматы файлов Windows”, М. “Бином”, 1995

4. [20] E. Hamilton. “JPEG File Interchange Format”. Version 1.2. September 1, 1992, San Jose CA: C-Cube Microsystems, Inc.

5. [21] Aldus Corporation Developer’s Desk. “TIFF - Revision 6.0, Final”, June 3, 1992

Приложение. Таблицы сравнения алгоритмов

Архивация двуцветного изображения

Ниже приведена степень компрессии изображений в зависимости от применяемого алгоритма:

Выводы, которые можно сделать, анализируя данную таблицу:

1. Лучшие результаты показал алгоритм, оптимизированный для этого класса изображений CCITT Group 4 и модификация универсального алгоритма LZW.

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

Архивация 16-цветного изображения

Изображение 619х405х16 цвета 125.350 байт

Ниже приведена степень компрессии изображений в зависимости от применяемого алгоритма:

Выводы, которые можно сделать, анализируя данную таблицу:

Не смотря на то, что данное изображение относится к классу изображений, на которые ориентирован алгоритм RLE (отвечает критериям “хороше­го” изображения для алгоритма RLE), заметно лучшие результаты для него дает более универсальный алгоритм LZW.

Архивация изображения в градациях серого

* Для формата GIF в этом случае можно получить изображение меньшего размера используя дополнительные параметры.

Характеристики

Список файлов книги