К разделу 'Сжатие изображений' сайта 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 Лаборатория Компьютерной Графики ВМиК МГУ им. М.В. Ломоносова

    <>
На правах рекламы
Думаете где можно купить петарды ? Звоните: 8(495) 609-20-14