К разделу 'Сжатие изображений' сайта AlgoList.

Д.С.Ватолин
Алгоритмы cжатия изображений

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

  Архивация двуцветного изображения
Изображение 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)
Выводы, которые можно сделать, анализируя таблицу:
    Алгоритм JPEG при визуально намного меньших потерях (q=100) сжал изображение в 2 раза сильнее, чем LZW с использованием перевода в изображение с палитрой. Алгоритм LZW, примененный к 24-битному изображению практически на дает сжатия. Минимальное сжатие, полученное алгоритмом RLE можно объяснить тем, что изображение в нижней части имеет сравнительно большую область однородного белого цвета (полученную после обработки изображения).

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

320х320хRGB — 307.200 байт

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

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

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

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

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

Содержание
(c) 1999 Ватолин Д.С.
(с) 1999 Лаборатория Компьютерной Графики ВМиК МГУ им. М.В. Ломоносова

    <>