Энтропия Шеннона и сжатие данных. Часть 2

Предыдущая запись: Энтропия Шеннона и сжатие данных. Часть 1.

Как и обещал, сейчас я рассмотрю конкретный пример оценки энтропии в файле изображения в формате PNG. Возьмём для примера вот это чёрно-белое изображение:

Брызги чёрной краски на белой бумаге.
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей

Характеристики файла представлены в таблице:

Характеристика	Значение	Блок метаданных	Комментарий
Ширина (W)	478 пикселей	IHDR	Ширина изображения
Высота (M)	305 пикселей	IHDR	Высота изображения
Гамма	Grayscale (Type 0)	IHDR	Изображение чёрно-белое
Глубина (B)	8 бит	IHDR	256 оттенков серого
Размер (Scomp)	24,279 байт	IDAT	Размер после сжатия

( Read more... )

6. Выводы

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


2. Предположение о независимости каждого байта данных (такой источник данных называется источником без памяти, memoryless) в нашем случае оказывается далёким от реальности, и соответственно, энтропия первого порядка H₁ не является точным приближением теоретического значения. Эта оценка в нашем случае оказалась гораздо хуже, чем оценка информационной плотности: H₁ > R.


3. Именно вследствие наличия паттернов данные оказываются хорошо сжимаемыми, что и отражает низкое значение R среднего количества информации на пиксель. Тем более, в PNG используются эффективные алгоритмы сжатия данных:
   
   
   1. Фильтрация удаляет пространственную избыточность, учитывая корреляцию цветов соседних пикселей.
   
   
   2. Алгоритм Lempel-Ziv (LZ77) как часть алгоритма Deflate, используемого в PNG, сжимает достаточно длинные последовательности одинаковых байт (просмотр вплоть до 50-пиксельных блоков).
   
   
   3. Также используется кодирование Хаффмана, при котором итоговый поток данных кодируется на основе частот символов.
   
   


4. По определению, энтропия — характеристика распределения символов в потоке данных, x_i в формуле Шеннона — переменные (цвета или оттенки серого в чёрно-белых файлах), характеризующие символы (пиксели). Часто символом выступает байт данных. Однако для файлов изображений символом удобно считать пиксель. Для 8-битовых пикселей значения энтропии на байт и на пиксель совпадают. Однако если анализировать, например, 24-битовое цветное изображение, максимальное значение энтропии на пиксель составляет 24 бита (глубина), тогда как максимальная энтропия на байт составляет 8 бит/байт.

В следующей записи мы рассмотрим, что такое спецификация и что такое криптографическое хэширование данных.