Методы сжатия данных: Сжатие изображений
Приложение. Таблицы сравнения алгоритмов

Сжатие двуцветного изображения
Изображение 1000х1000х2 цвета 
125.000 байт
То же изображение с внесенными в него помехами

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


  Алгоритм RLE Алгоритм LZW CCITT
Group 3		 CCITT
Group 4
Без помех 10,6 (TIFF-CCITT RLE)
6,6 (TIFF-PackBits)
4,9 (PCX)
2,99 (BMP)
2,9 (TGA)		 12 (TIFF-LZW)
10,1 (GIF)		 9,5 (TIFF) 31,2 (TIFF)
С 
помехами		 5 (TIFF-CCITT RLE)
2,49 (TIFF-PackBits)
2,26 (PCX)
1,7 (TGA)
1,69 (BMP)		 5,4 (TIFF-LZW)

5,1 (GIF)

 4,7 (TIFF) 5,12 (TIFF)
Выводы, которые можно сделать, анализируя данную таблицу:
  1. Лучшие результаты показал алгоритм, оптимизированный для этого класса изображений CCITT Group 4 и модификация универсального алгоритма LZW.
  2. Даже в рамках одного алгоритма велик разброс значений алгоритма компрессии. Заметим, что реализации RLE и LZW для TIFF показали заметно лучшие результаты, чем в других форматах. Более того, во всех колонках все варианты алгоритмов сжатия реализованные в формате TIFF лидируют.

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

 

Изображение 619х405х16 цвета 125.350 байт
Ниже приведена степень компрессии изображений в зависимости от применяемого алгоритма:
 
  Алгоритм RLE Алгоритм LZW
Первое изображение 5,55 (TIFF-PackBits)
5,27 (BMP)
4,8 (TGA)
2,37 (PCX)		 13,2 (GIF)

11 (TIFF-LZW)

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

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

Сжатие изображения в градациях серого
Изображение 600х700х256 градаций серого сразу после сканирования. 420.000 байт.
(с) А.Андреев. Рисунок к роману Сергея Лукьяненко, "Лабиринт отражений"


На гистограмме хорошо видны равномерные большие значения в области темных и “почти белых” тонов.
То же изображение с выровненной гистограммой плотности серого.
 
 


После выравнивания, пики есть только в значениях 0 и 255. В изображении присутствуют далеко не все значения яркости.
  Алгоритм RLE Алгоритм LZW Алгоритм JPEG
Оригинал 0,99 (TIFF-PackBits)
0,98 (TGA)
0,88 (BMP)
0,74 (PCX)		 0,976 (TIFF-LZW)
0,972 (GIF)		 7,8 (JPEG q=10)

3,7 (JPEG q=30)

2,14 (JPEG q=100)
После 
обработки		 2,86 (TIFF-PackBits)
2,8 (TGA)
0,89 (BMP)
0,765 (PCX)		 3,02 (TIFF-LZW)
0,975 (GIF)*		 6,9 (JPEG q=10)

3,7 (JPEG q=30)

2,4 (JPEG q=100)
* Для формата GIF в этом случае можно получить изображение меньшего размера используя дополнительные параметры. Выводы, которые можно сделать анализируя таблицу:
  1. Лучшие результаты показал алгоритм сжатия с потерей информации. Для оригинального изображения только JPEG смог уменьшить файл. Заметим, что увеличение контрастности уменьшило степень компрессии при максимальном сжатии — врожденное свойство JPEG.
  2. Реализации RLE и LZW для TIFF опять показали заметно лучшие результаты, чем в других форматах. Степень сжатия для них после обработки изображения возросла в 3 раза(!). В то время, как GIF, PCX и BMP и в этом случае увеличили размер файла.

Сжатие полноцветного изображения


Изображение 320х320хRGB — 307.200 байт

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

  Алгоритм RLE Алгоритм LZW Алгоритм JPEG
Первое 
изображение		 1,046 (TGA)
1,037 (TIFF-PackBits)		 1,12 (TIFF-LZW)

4,65 (GIF) 
С потерями! Изображение в 256 цветах

 47,2 (JPEG q=10)

23,98 (JPEG q=30)

11,5 (JPEG q=100)

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

  1. Алгоритм JPEG при визуально намного меньших потерях (q=100) сжал изображение в 2 раза сильнее, чем LZW с использованием перевода в изображение с палитрой.
  2. Алгоритм LZW, примененный к 24-битному изображению практически на дает сжатия.
  3. Минимальное сжатие, полученное алгоритмом RLE можно объяснить тем, что изображение в нижней части имеет сравнительно большую область однородного белого цвета (полученную после обработки изображения).

Сжатие полноцветного изображения в 100 раз

 

 

320х320хRGB — 307.200 байт

Сжатие в 100 раз JPEG (3.08Кb) 

Сжатие в 100 раз (3.04Кb) 
фрактальным алгоритмом

Сжатие в 100 раз (3.04Кb) wavelet алгоритмом
(ИЗОБРАЖЕНИЯ ДЛЯ WWW-варианта лекций ПЕРЕВЕДЕНЫ В JPEG хоть и максимальным качеством, но с потерями)

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

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

Вы можете не портить глаза (и сделать приятное авторам), если купите бумажный вариант книги! Заказать его можно, например, в магазине Озон.
Книга в формате 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 вариантом.

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