Данный материал предназначен для тех, кто не разбирается в алгоритмах сжатия цифровой информации, но хочет получить общее представление о том, как они работают.
Мы уже давно имеем дело с архиваторами типа ZIP и RAR, которые позволяют уменьшить объём файлов. Причина проста – экономия места на носителе, уменьшение трафика при передаче по сети.
Архиваторы могут ужать объём файла до 10 раз. Например, если это текст книги. Но некоторые файлы практически не сжимаются.
Почему некоторые файлы плохо сжимаются?
Всё зависит от типа хранимой информации. Представьте себе губку, смоченную водой. Если её сжать, то вода вытечет.
Текстовые файлы содержат очень много "воды": в них всего лишь ограниченный набор букв, которые очень часто повторяются. Учитывая все эти повторения, текст можно перекодировать так, чтобы создать из него словарь буквенных комбинаций. Каждая комбинация входит в словарь только один раз, и поэтому "вода" выжимается из текста. Теперь это не текст, а словарь и набор ссылок на словарные сочетания.
Но если вы попробуете сжать сухую губку, из неё ничего не вытечет. Воды нет, и выжимать нечего. Музыка, изображения, видео плохо поддаются сжатию, потому что в них гораздо больше разных сочетаний байтов и они редко повторяются.
Раньше, когда пространство для хранения было ограничено, а скорость интернета была невысокой, проблема упаковки мультимедиа-файлов стояла очень остро.
В результате появилась такая идея: если в губке нет воды, чтобы её выжать, давайте тогда отрежем кусок от самой губки и выбросим его. Так появилось сжатие с потерями.
Где применяется сжатие с потерями?
Потери – это реально потери. То есть информация, которая была в оригинале, теряется навсегда. Это значит, что сжатие с потерями нельзя использовать для большинства типов файлов, где важна сохранность данных. Нельзя сжать с потерями программу – после этого она перестанет работать. Нельзя сжать с потерями текст – он исказится.
Но мы можем без проблем слушать слегка искаженную музыку или смотреть слегка искаженные картинки. Именно поэтому сжатие с потерями используется в сфере мультимедиа.
Когнитивные потери
Во многих случаях сжатие с потерями эксплуатирует особенности человеческого восприятия.
Каждый звук в реальной жизни это сложный набор частот, которые звучат одновременно. При этом более громкая частота маскирует более тихие частоты, если они находятся поблизости от неё – будто накрывает их зонтиком.
Это так и называется маскировкой частот. Она происходит не на самом деле, а исключительно в нашем восприятии. Наш мозг так устроен.
Любой звук можно разложить на набор частот. Проанализировав этот набор, можно выбросить из него те частоты, которые будут маскироваться. Фактически для нас они неслышимы.
Так появился формат сжатия MP3 для звуковых файлов. Из звука выбрасываются некоторые составляющие его частоты.
Аналогичным образом эксплуатируется и наше восприятие изображений.
Изображение можно разделить на две составляющие: информация о яркости и информация о цвете. Информация о яркости гораздо важнее. Например, чёрно-белая фотография содержит только яркость, но при этом мы её прекрасно воспринимаем как реалистичную.
Цвет же мы различаем гораздо хуже. Поэтому было принято решение сохранять цветовую информацию не в каждой точке (или строке) изображения, а через одну. Иначе говоря, половина цветовой информации оказалась выброшена.
Современные цифровые матрицы фотокамер (за исключением Foveon и 3CCD) создают изображение сразу с потерями: оно содержит только 50% зеленого цвета и по 25% красного и синего.
Зелёного цвета в 2 раза больше, потому что именно он несёт большую часть яркостной информации, которая нам важнее.
После получения "мозаичной" картинки с цифрового сенсора она восстанавливается до нормальной, т.е. заполняются недостающие цветовые значения. Помните, что информация уже была потеряна, восстановление всего лишь "додумывает" её.
Но на этом потери не заканчиваются. Дальше вступают в дело алгоритмы сжатия.
Но сначала мы рассмотрим их общее место:
Преобразование Фурье
Самое удивительное, что в основе современных технологий лежат достижения французского математика Жана-Батиста Жозефа Фурье, который жил аж в 18-м веке.
Фурье доказал, что кривую любой формы можно разложить на сумму обычных синусоид.
Например, записанные колебания звука выглядят как очень сложная кривая:
Но тем не менее, эту кривую можно представить в виде суммы простых синусоид с определёнными коэффициентами, примерно так:
В данном примере участвуют всего лишь три синусоиды. Увеличивая их количество и подбирая параметры для каждой, можно получать всё более и более точное приближение к исходной кривой.
Суть сжатия: вместо целого куска кривой, заданного в каждой точке, можно хранить только параметры синусоид, её описывающих.
JPEG
Алгоритм упаковки JPEG – спасение и проклятие интернета. Огромная степень сжатия, и огромное количество безнадёжно испорченных изображений.
Получив на вход картинку, первым делом JPEG опять выбрасывает из неё часть цветовой информации (повторные потери). Затем он делит картинку на блоки 8*8 пикселов и кодирует каждый блок, используя дискретное косинус-преобразование, которое также выводится из работ Фурье.
Хотя это не точное описание, но можно считать, что JPEG представляет информацию внутри блока картинки как набор синусоид.
Чем ближе сходство, тем больше дополнительных синусоид нужно для суммы, и значит размер картинки будет расти. Но чаще всего используется некий компромисс, где сумма синусоид даёт лишь приблизительное сходство с кривой, а значит синусоид нужно меньше, и сжатие получается лучше. Но – ценой качества изображения.
В самых крайних случаях мы можем наблюдать очень плохо закодированные блоки изображения:
MP3
В MP3 происходит примерно то же самое. В звуковых данных выделяется плавающее "окно", внутри которого делается анализ и также строится приближение кривой с помощью суммы синусоид. Опять же, чем больше синусоид участвует в сумме, тем лучше приближение, но и хуже сжатие.
MPEG
Названием похожий на JPEG, этот алгоритм из того же семейства и предназначен для кодирования видео. Он ещё сложнее. В видеопотоке берётся первый кадр и кодируется как обычная картинка. Следующие несколько кадров кодируются не сами по себе, а как разница между текущим и предыдущим кадром. Здесь изображение также делится на блоки, в каждом блоке назначается вектор движения, т.е. алгоритм пытается предсказать, куда сдвинется элемент изображения в следующем кадре.
Естественно, алгоритм опять-таки эксплуатирует наше восприятие движения, где можно пожертвовать цветовой информацией или детализацией, если движение быстрое.
В целом всё это существенно сложнее кодирования простой картинки.
Опасность перекодирования
Вы наверняка встречали в сети картинки или видео отвратительного качества. Проблема в том, что когда JPEG-картинку воруют с какого-то сайта и загружают на другой сайт, зачастую происходит повторное перекодирование в JPEG.
То есть берётся картинка с уже имеющимися потерями и артефактами JPEG-сжатия, и ей наносится ещё больше потерь и добавляется ещё больше артефактов.
Через несколько таких перекодирований картинка превратится в абсолютный мусор, но многих и это не останавливает. Поэтому мы и наблюдаем в сети мемы и демотиваторы ужасного качества.
То же самое относится и к видеофайлам. Они портятся от перекодирования так же, как и картинки. Из них выбрасывается ещё больше информации, и добавляется ещё больше артефактов.
Редактирование файлов, сжатых с потерями
В принципе, плевать, кто и как обращается с файлами в сети. Но что вам делать с собственными картинками и видео, которые вы сняли на свою камеру?
Как правило, любое редактирование таких файлов приводит к повторному перекодированию, и значит, к дальнейшей потере качества. Хотя само вмешательство может быть минимальным:
- добавить логотип
- повернуть изображение
- обрезать поля
- добавить музыку в видео
- обрезать / склеить видео
В некоторых случаях можно отредактировать файл без повторного перекодирования, и значит, сохранить его оригинальное качество. Как и чем это можно сделать, мы рассмотрим в следующем выпуске.
Читайте дальше:
