Методы сжатия данных: Сжатие изображений Различия между форматом и алгоритмом

Дополнительный раздел

Напоследок несколько замечаний относительно разницы в терминологии, путаницы при сравнении рейтингов алгоритмов и т.п.

Посмотрите на краткий перечень форматов, достаточно часто используемых на PC, Apple и UNIX платформах: ADEX, Alpha Microsystems BMP, Autologic, AVHRR, Binary Information File (BIF), Calcomp CCRF, CALS, Core IDC, Cubicomp PictureMaker, Dr. Halo CUT, Encapsulated PostScript, ER Mapper Raster, Erdas LAN/GIS, First Publisher ART, GEM VDI Image File, GIF, GOES, Hitachi Raster Format, PCL, RTL, HP-48sx Graphic Object (GROB), HSI JPEG, HSI Raw, IFF/ILBM, Img Software Set, Jovian VI, JPEG/JFIF, Lumena CEL, Macintosh PICT/PICT2, MacPaint, MTV Ray Tracer Format, OS/2 Bitmap, PCPAINT/Pictor Page Format, PCX, PDS, Portable BitMap (PBM), QDV, QRT Raw, RIX, Scodl, Silicon Graphics Image, SPOT Image, Stork, Sun Icon, Sun Raster, Targa, TIFF, Utah Raster Toolkit Format, VITec, Vivid Format, Windows Bitmap, WordPerfect Graphic File, XBM, XPM, XWD.

В оглавлении вы можете видеть список алгоритмов компрессии. Единственным совпадением оказывается 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: Если вы не умеете пользоваться программами архивации или пользуетесь программами, в которых “для простоты использования” убрано управление параметрами алгоритмане удивляйтесь, почему для отличного алгоритма компрессии в результате получаются большие файлы.

Литература

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


[1] Wallace G.K. // Communication of ACM. Volume 34. Number 4 April 1991.
[2] Smith B., Rowe L. // Computer Graphics and applications. September 1993.
[3] Jacquin A. // Visual Comm. and Image Processing, vol. SPIE-1360, 1990.
[4] Fisher Y. // SigGraph-92.
[5] // ISO/IEC JTC1/SC2/WG9, CD 11544, September 16, 1991.
[6] Pennebaker W.B., Mitchell J.L., Langdon G.G., Arps R.B., // IBM Journal of research and development, Vol.32, No.6, November 1988, pp. 771-726.
[7] Huffman D.A. // Proc. of IRE vol.40, 1952, pp. 1098-1101.
[8] Standardisation of Group 3 Facsimile apparatus for document transmission. CCITT Recommendations. Fascicle VII.2. T.4. 1980.
[9] Александров В.В., Горский Н.Д. <Представление и обработка изображений: рекурсивный подход> // Л-д.: Наука 1985, 190 стр.
[10] Климов А.С. <Форматы графических файлов>. // С.-Петербург, Изд. <ДиаСофт> 1995.
[11] Ватолин Д.С. // Открытые системы. Номер 2. Лето 1995
[12] Ватолин Д.С. <Тенденции развития алгоритмов архивации графики> // Открытые системы. Номер 4. Зима 1995
[13] Ватолин Д.С. <Алгоритмы сжатия изображений> // ISBN 5-89407-041-4 М.: Диалог-МГУ, 1999.
[14] Добеши И. <Десять лекций по вейвлетам> // Пер. с анг. Е.В. Мищенко, под ред. А.П.Петухова. М.: Ижевск 2001, 464 стр.
[15] Яншин В.В. <Анализ и обработка изображений (принципы и алгоритмы)> // М.: Машиностроение 1995
[16] Павлидис Т. <Алгоритмы машинной графики и обработка изображений> // М.: Радио и связь 1986, 400 стр.
[17] Претт У. <Цифровая обработка изображений> в двух томах // М.: Мир 1982, 790 стр.
[18] Розеншельд А. <Распознавание и обработка изображений> // М.: Мир 1972, 232 стр.
[19] Материалы конференции <Графикон> (статьи по сжатию публиковались практически ежегодно) доступны в научных библиотеках и, частично, на
http://www.graphicon.ru
[20] Ярославский Л.П. <Введение в цифровую обработку изображений> // М.:Сов. радио 1969, 312 стр.
[21] Яблонский С.В. <Введение в дискретную математику>. // М. <Наука>, 1986. Раздел <Теория кодирования>.
[22] Более 150 статей по сжатию изображений можно найти на http://graphics.cs.msu.su/library/.
Литература по форматам изображений

[23] Климов А.С. <Форматы графических файлов> // НИПФ <ДиаСофт Лтд>, 1995.
[24] Романов В.Ю. <Популярные форматы файлов для хранения графических изображений на IBM PC> // Москва <Унитех>, 1992
[25] Сван Том <Форматы файлов Windows> // М. <Бином>, 1995
[26] Hamilton E. // Version 1.2. September 1, 1992, San Jose CA: C-Cube Microsystems, Inc.
[27] Aldus Corporation Developer's Desk. , June 3, 1992
 
 

Вы можете не портить глаза (и сделать приятное авторам), если купите бумажный вариант книги! Заказать его можно, например, в магазине Озон.

Книга в формате PDF (Acrobat Reader): Внимание! Выложенный на странице HTML вариант раздела 2 не полностью соответствует тексту книги. По возможности пользуйтесь PDF вариантом.

Обнаруженные ошибки

Раздел 1. МЕТОДЫ СЖАТИЯ БЕЗ ПОТЕРЬ
  • Глава 1. Кодирование источников данных без памяти
    • Разделение мантисс и экспонент
    • Канонический алгоритм Хаффмана
    • Арифметическое сжатие
    • Нумерующее кодирование
    • Векторное квантование
  • Глава 2. Кодирование источников данных типа "аналоговый сигнал"
    • Линейно-предсказывающее кодирование
    • Субполосное кодирование
  • Глава 3. Словарные методы сжатия данных
    • Идея словарных методов
    • Классические алгоритмы Зива-Лемпела
    • Другие алгоритмы LZ
    • Формат Deflate
    • Пути улучшения сжатия для методов LZ
    • Архиваторы и компрессоры, использующие алгоритмы LZ
    • Вопросы для самопроверки
    • Литература
    • Список архиваторов и компрессоров
  • Глава 4. Методы контекстного моделирования
    • Классификация стратегий моделирования
    • Контекстное моделирование
    • Алгоритмы PPM
    • Оценка вероятности ухода
    • Обновление счетчиков символов
    • Повышение точности оценок в контекстных моделях высоких порядков
    • Различные способы повышения точности предсказания
    • PPM и PPM*
    • Достоинства и недостатки PPM
    • Компрессоры и архиваторы, использующие контекстное моделирование
    • Обзор классических алгоритмов контекстного моделирования
    • Сравнение алгоритмов контекстного моделирования
    • Другие методы контекстного моделирования
    • Вопросы для самопроверки
    • Литература
    • Список архиваторов и компрессоров
  • Глава 5. Преобразование Барроуза-Уилера
    • Введение
    • Преобразование Барроуза-Уилера
    • Методы, используемые совместно с BWT
    • Способы сжатия преобразованных с помощью BWT данных
    • Сортировка, используемая в BWT
    • Архиваторы, использующие BWT и ST
    • Заключение
    • Литература
  • Глава 6. Обобщенные методы сортирующих преобразований
    • Сортировка параллельных блоков
    • Фрагментирование
  • Глава 7. Предварительная обработка данных
    • Препроцессинг текстов
    • Препроцессинг нетекстовых данных
    • Вопросы для самопроверки
    • Литература
    • Выбор метода сжатия
Раздел 2. МЕТОДЫ СЖАТИЯ ИЗОБРАЖЕНИЙ Раздел 3. МЕТОДЫ СЖАТИЯ ВИДЕОДАННЫХ
  • Глава 1. Введение
    • Основные понятия
    • Требования приложений к алгоритму
    • Определение требований
    • Обзор стандартов
  • Глава 2. Базовые технологии сжатия видео
    • Описание алгоритма компрессии
    • Общая схема алгоритма
    • Использование векторов смещений блоков
    • Возможности по распараллеливанию
    • Другие пути повышения степени сжатия
  • Глава 3. Стандарты сжатия видео
    • Motion-JPEG
    • MPEG-1
    • H.261
    • H.263
    • MPEG-2
    • MPEG-4
    • Сравнение стандартов
    • Вопросы для самопроверки
  • Литература
  • Ссылки на программы и реализации алгоритмов
  • Указатель терминов

Вы можете не портить глаза (и сделать приятное авторам), если купите бумажный вариант книги! Заказать его можно, например, в магазине Озон.

Книга в формате PDF (Acrobat Reader): Внимание! Выложенный на странице HTML вариант раздела 2 не полностью соответствует тексту книги. По возможности пользуйтесь PDF вариантом.

Обнаруженные ошибки