Энтропия Шеннона и сжатие данных. Часть 2
Oct. 21st, 2025 03:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mns2012Предыдущая запись: Энтропия Шеннона и сжатие данных. Часть 1.
Как и обещал, сейчас я рассмотрю конкретный пример оценки энтропии в файле изображения в формате PNG. Возьмём для примера вот это чёрно-белое изображение:
Брызги чёрной краски на белой бумаге.
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей
Характеристики файла представлены в таблице:
1. Расчёт размера файла исходных данных до сжатия
Размер исходных данных изображения — это общее количество байтов до сжатия и после этапа фильтрации PNG (который добавляет один байт фильтра на каждую строку сканирования). Высоту файла в пикселях обозначим M, ширину — W:
B' = 8 [бит/пиксель] = 1 [байт/пиксель].
2. Вычислим, сколько имеется байтов данных на строку сканирования (всего имеется M строк, шириной W каждая):
Ss = W * B' = 478 пикселей * 1 [байт/пиксель] = 478 [байтов/строка сканирования]
3. Фильтрация в PNG предназначена для выявления пространственной корреляции между значениями пикселей в разных строках сканирования. Строка сканирования имеет высоту в один пиксель и ориентирована по ширине изображения. Вычислим, сколько байтов добавляет фильтр PNG. Каждая из M строк сканирования имеет префикс фильтра размером в 1 байт. Итого фильтр добавляет M = 567 байтов.
4. Таким образом, общий размер файла исходных данных до сжатия равен сумме числа байтов на строку сканирования, умноженному на число строк (высоту), и числу байтов, добавленных в результате фильтрации:
Размер файла исходных данных (до сжатия):
5. Наконец, коэффициент сжатия данных CR есть отношение размера исходного файла Sraw к размеру файла, после сжатия алгоритмами PNG.
Размеры файла до и после сжатия Sraw и Scomp условимся измерять в байтах.
2. Расчёт оценки энтропии по степени сжатия
В предыдущей записи мы вывели выражение для энтропии H как функции глубины изображения B и степени сжатия CR:
3. Расчёт оценки среднего количества информации на символ (информационной плотности)
Ту же самую оценку H можно получить иначе, без непосредственного вычисления исходного размера файла Sraw до сжатия.
Как мы видели:
где CR = Sraw / Scomp.
Введём среднее количество информации на символ (информационную плотность) после сжатия, измеряемую в битах на пиксель, и обозначим её R:
3.1 Информационная плотность приблизительно равна энтропии
Покажем, что R ≈ H.
Исходный размер файла в байтах до сжатия есть число пикселей, помноженное на число байтов на пиксель плюс байты, добавленные фильтрацией:
Если файл достаточно большой, то слагаемым Sf можно пренебречь. Поэтому:
Отсюда:
Подставим теперь Np ≈ α Sraw / B в выражение для R:
R = α Scomp / Np ≈ α Scomp / [α Sraw / B] = B * Scomp / Sraw = B / CR = H.
Отсюда, кстати, следует, что коэффициент сжатия равен отношению энтропии после сжатия к максимальной энтропии, поскольку B = Hmax:
Итак, с точностью до байтов, добавленных фильтрацией:
Поэтому в оценке энтропии мы можем пользоваться формулой для R, в которой размер файла до сжатия не присутствует явно:
3.2 Вычисление информационной плотности для файла
Подставим данные для нашего примера:
R = 8 бит/байт * 24,279 байтов / 145,790 пикселей ≈ 1.332 бит/пиксель.
Вычисленные в пп.2 и 3 значения H и R приблизительно равны. Обычно фотографии характеризуются значениями энтропии в пределах 3–5 бит/пиксель. В нашем примере энтропия достаточно низка, поскольку в нём относительно много белых и чёрных областей, что делает его очень сжимаемым.
4. Оценка энтропии с использованием метаданных файла PNG
Как мы уже знаем, в разделе метаданных в файле PNG есть энтропийная гистограмма, которую можно также использовать для оценки энтропии. Давайте посмотрим, какова оценка энтропии по гистограмме PNG.
Чтобы извлечь гистограмму, требуется программное обеспечение, способное декомпрессовать данные PNG (фрагмент IDAT), а затем вычислить частоту всех 256 значений байтов (0–255) в исходных пиксельных данных. Гистограмма нашего чёрно-белого PNG-файла представляет собой распределение частот значений пикселей в оттенках серого, полученная в предположении отсутствия паттернов, то есть что каждый пиксель независим. Это представление так называемой энтропии первого порядка H1. В более точных оценках учитываются корреляции значений пикселей (наличие паттернов).
В моём анализе я использовал скрипт на языке Python с библиотекой PIL/Pillow, сгенерированный Gemini. Он небольшой, поэтому я приведу его полностью:
Вот как выглядят распределение частот оттенков пикселей и соответствующие вероятности значений цвета (оттенка) пикселя.
Различие между двумя графиками тривиально: на графике справа вероятность отдельного оттенка есть частота значения оттенка из гистограммы слева, делённая на общее число пикселей в файле.
Как и ожидалось, наибольшие частоты (вероятности) соответствуют оттенкам пикселей, близких к белому цвету. Второй пик — около нуля (чёрный) — гораздо меньше (вероятность не достигает и 0.05). Понятно, почему файл так хорошо сжимаем.
Оценка энтропии в предположении о независимости каждого пикселя (так наз. энтропия первого порядка H1), вычисленная по формуле Шеннона по гистограмме, извлечённой из файла PNG с помощью библиотеки PIL/Pillow, составляет:
5. Анализ
Первый вопрос: почему R < H1? H1 — всего-лишь оценка, причём довольно грубая, поскольку учитывает только энтропию отдельных пикселей. Не учитываются корреляции между пикселями (наличие паттернов в изображении). Поэтому то, что она оказалась больше R, не должно нас смущать, что меня, помню, как раз и смутило: как так получилось, что простой оценочный расчёт R даёт оценку лучше, чем по гистограмме?!
Далее, почему оценки H1 и R так сильно отличаются друг от друга?
6. Выводы
В следующей записи мы рассмотрим, что такое спецификация и что такое криптографическое хэширование данных.
Как и обещал, сейчас я рассмотрю конкретный пример оценки энтропии в файле изображения в формате PNG. Возьмём для примера вот это чёрно-белое изображение:
Брызги чёрной краски на белой бумаге.
Формат: PNG. Изображение чёрно-белое, глубина 8 бит/пиксель.
Размеры: 478 x 305 пикселей
Характеристики файла представлены в таблице:
| Характеристика | Значение | Блок метаданных | Комментарий |
| Ширина (W) | 478 пикселей | IHDR | Ширина изображения |
| Высота (M) | 305 пикселей | IHDR | Высота изображения |
| Гамма | Grayscale (Type 0) | IHDR | Изображение чёрно-белое |
| Глубина (B) | 8 бит | IHDR | 256 оттенков серого |
| Размер (Scomp) | 24,279 байт | IDAT | Размер после сжатия |
1. Расчёт размера файла исходных данных до сжатия
Размер исходных данных изображения — это общее количество байтов до сжатия и после этапа фильтрации PNG (который добавляет один байт фильтра на каждую строку сканирования). Высоту файла в пикселях обозначим M, ширину — W:
- M = 305 пикселей;
- W = 478 пикселей.
B' = 8 [бит/пиксель] = 1 [байт/пиксель].
2. Вычислим, сколько имеется байтов данных на строку сканирования (всего имеется M строк, шириной W каждая):
Ss = W * B' = 478 пикселей * 1 [байт/пиксель] = 478 [байтов/строка сканирования]
3. Фильтрация в PNG предназначена для выявления пространственной корреляции между значениями пикселей в разных строках сканирования. Строка сканирования имеет высоту в один пиксель и ориентирована по ширине изображения. Вычислим, сколько байтов добавляет фильтр PNG. Каждая из M строк сканирования имеет префикс фильтра размером в 1 байт. Итого фильтр добавляет M = 567 байтов.
4. Таким образом, общий размер файла исходных данных до сжатия равен сумме числа байтов на строку сканирования, умноженному на число строк (высоту), и числу байтов, добавленных в результате фильтрации:
Sraw = Ss * M + M.
Размер файла исходных данных (до сжатия):
Sraw = Ss * M + M = 478 * 305 + 305 = 146,095 байтов.
5. Наконец, коэффициент сжатия данных CR есть отношение размера исходного файла Sraw к размеру файла, после сжатия алгоритмами PNG.
CR = Sraw / Scomp = 146,095 / 24,279 байтов ≈ 6.017.
Размеры файла до и после сжатия Sraw и Scomp условимся измерять в байтах.
2. Расчёт оценки энтропии по степени сжатия
В предыдущей записи мы вывели выражение для энтропии H как функции глубины изображения B и степени сжатия CR:
H = B / CR,
то есть:
H = 8 бит/пиксель / 6.017 ≈ 1.329 бит/пиксель.
3. Расчёт оценки среднего количества информации на символ (информационной плотности)
Ту же самую оценку H можно получить иначе, без непосредственного вычисления исходного размера файла Sraw до сжатия.
Как мы видели:
H = Hmax / CR = B / CR,
где CR = Sraw / Scomp.
Введём среднее количество информации на символ (информационную плотность) после сжатия, измеряемую в битах на пиксель, и обозначим её R:
R = α Scomp / Np,
где:- α = 8 [бит/байт]: коэффициент для перевода размера файла в биты;
- Np = M * W = 567 * 850 = 481950: число пикселей в файле.
3.1 Информационная плотность приблизительно равна энтропии
Покажем, что R ≈ H.
Исходный размер файла в байтах до сжатия есть число пикселей, помноженное на число байтов на пиксель плюс байты, добавленные фильтрацией:
Sraw = 1/α * M * W * B + M = 1/α * Np * B + Sf.
Если файл достаточно большой, то слагаемым Sf можно пренебречь. Поэтому:
Sraw ≈ 1/α * Np * B.
Отсюда:
Np ≈ α Sraw / B.
Подставим теперь Np ≈ α Sraw / B в выражение для R:
R = α Scomp / Np ≈ α Scomp / [α Sraw / B] = B * Scomp / Sraw = B / CR = H.
Отсюда, кстати, следует, что коэффициент сжатия равен отношению энтропии после сжатия к максимальной энтропии, поскольку B = Hmax:
CR = Scomp / Sraw = H / Hmax.
Итак, с точностью до байтов, добавленных фильтрацией:
R ≈ H.
Поэтому в оценке энтропии мы можем пользоваться формулой для R, в которой размер файла до сжатия не присутствует явно:
R = α Scomp / Np.
3.2 Вычисление информационной плотности для файла
Подставим данные для нашего примера:
R = 8 бит/байт * 24,279 байтов / 145,790 пикселей ≈ 1.332 бит/пиксель.
Вычисленные в пп.2 и 3 значения H и R приблизительно равны. Обычно фотографии характеризуются значениями энтропии в пределах 3–5 бит/пиксель. В нашем примере энтропия достаточно низка, поскольку в нём относительно много белых и чёрных областей, что делает его очень сжимаемым.
4. Оценка энтропии с использованием метаданных файла PNG
Как мы уже знаем, в разделе метаданных в файле PNG есть энтропийная гистограмма, которую можно также использовать для оценки энтропии. Давайте посмотрим, какова оценка энтропии по гистограмме PNG.
Чтобы извлечь гистограмму, требуется программное обеспечение, способное декомпрессовать данные PNG (фрагмент IDAT), а затем вычислить частоту всех 256 значений байтов (0–255) в исходных пиксельных данных. Гистограмма нашего чёрно-белого PNG-файла представляет собой распределение частот значений пикселей в оттенках серого, полученная в предположении отсутствия паттернов, то есть что каждый пиксель независим. Это представление так называемой энтропии первого порядка H1. В более точных оценках учитываются корреляции значений пикселей (наличие паттернов).
В моём анализе я использовал скрипт на языке Python с библиотекой PIL/Pillow, сгенерированный Gemini. Он небольшой, поэтому я приведу его полностью:
Вот как выглядят распределение частот оттенков пикселей и соответствующие вероятности значений цвета (оттенка) пикселя.
Слева: Распределение частот различных оттенков пикселей в файле (0 — чёрный, 255 — белый).
Справа: соответствующее распределение вероятностей оттенков серого.
Справа: соответствующее распределение вероятностей оттенков серого.
Различие между двумя графиками тривиально: на графике справа вероятность отдельного оттенка есть частота значения оттенка из гистограммы слева, делённая на общее число пикселей в файле.
Как и ожидалось, наибольшие частоты (вероятности) соответствуют оттенкам пикселей, близких к белому цвету. Второй пик — около нуля (чёрный) — гораздо меньше (вероятность не достигает и 0.05). Понятно, почему файл так хорошо сжимаем.
Оценка энтропии в предположении о независимости каждого пикселя (так наз. энтропия первого порядка H1), вычисленная по формуле Шеннона по гистограмме, извлечённой из файла PNG с помощью библиотеки PIL/Pillow, составляет:
H1 = 2.2174 бит/пиксель.
5. Анализ
Первый вопрос: почему R < H1? H1 — всего-лишь оценка, причём довольно грубая, поскольку учитывает только энтропию отдельных пикселей. Не учитываются корреляции между пикселями (наличие паттернов в изображении). Поэтому то, что она оказалась больше R, не должно нас смущать, что меня, помню, как раз и смутило: как так получилось, что простой оценочный расчёт R даёт оценку лучше, чем по гистограмме?!
Далее, почему оценки H1 и R так сильно отличаются друг от друга?
- Обе эти оценки являются, как мы уже выяснили, оценками сверху.
- В данном случае структура изображения представляет собой относительно большие участки чёрного и белого цветов, то есть имеются паттерны. Поэтому с большой вероятностью значение интенсивности пикселя такое же, как у соседних пикселей.
6. Выводы
- Оценивать энтропию по степени сжатия или по информационной плотности возможно, когда известно, что сжатие производилось без потери информации. Это условие удовлетворяется форматом PNG, поэтому я и выбрал пример именно с этим форматом данных.
- Предположение о независимости каждого байта данных (такой источник данных называется источником без памяти, memoryless) в нашем случае оказывается далёким от реальности, и соответственно, энтропия первого порядка H1 не является точным приближением теоретического значения. Эта оценка в нашем случае оказалась гораздо хуже, чем оценка информационной плотности: H1 > R.
- Именно вследствие наличия паттернов данные оказываются хорошо сжимаемыми, что и отражает низкое значение R среднего количества информации на пиксель. Тем более, в PNG используются эффективные алгоритмы сжатия данных:
- Фильтрация удаляет пространственную избыточность, учитывая корреляцию цветов соседних пикселей.
- Алгоритм Lempel-Ziv (LZ77) как часть алгоритма Deflate, используемого в PNG, сжимает достаточно длинные последовательности одинаковых байт (просмотр вплоть до 50-пиксельных блоков).
- Также используется кодирование Хаффмана, при котором итоговый поток данных кодируется на основе частот символов.
- По определению, энтропия — характеристика распределения символов в потоке данных, xi в формуле Шеннона — переменные (цвета или оттенки серого в чёрно-белых файлах), характеризующие символы (пиксели). Часто символом выступает байт данных. Однако для файлов изображений символом удобно считать пиксель. Для 8-битовых пикселей значения энтропии на байт и на пиксель совпадают. Однако если анализировать, например, 24-битовое цветное изображение, максимальное значение энтропии на пиксель составляет 24 бита (глубина), тогда как максимальная энтропия на байт составляет 8 бит/байт.
В следующей записи мы рассмотрим, что такое спецификация и что такое криптографическое хэширование данных.
