Какой предел сжатия данных без потерь? (если такой предел существует)

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

До сих пор единственным источником, который я мог найти по этой теме, была Википедия:

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

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

Я не уверен, что кто-то еще объяснил, почему магическое число кажется точно 1: 2, а не, например, 1: 1.1 или 1:20.

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

Я сделал очень простой эксперимент:

• Я взял серую карту . Для человеческого глаза это выглядит как обычный нейтральный кусок серого картона. В частности, нет информации .

• А потом я взял обычный сканер - именно то устройство, которое люди могли бы использовать для оцифровки своих фотографий.

• Я отсканировал серую карту. (На самом деле, я отсканировал серую карту вместе с открыткой. Открытка была там для проверки работоспособности, чтобы я мог убедиться, что программное обеспечение сканера не делает ничего странного, например, автоматически добавляет контраст, когда он видит безликую серую карту.)

• Я обрезал часть серой карты размером 1000x1000 пикселей и преобразовал ее в оттенки серого (8 бит на пиксель).

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

Однако при большем увеличении это выглядит так:

Нет четко видимого рисунка, но он не имеет однородного серого цвета. Частично это, скорее всего, вызвано несовершенством серой карты, но я бы предположил, что большая часть этого - просто шум, создаваемый сканером (тепловой шум в сенсорной ячейке, усилителе, аналого-цифровом преобразователе и т. Д.). Очень похоже на гауссовский шум; Вот гистограмма (в логарифмическом масштабе):

Теперь, если мы предположим, что каждый пиксель имеет свой оттенок, выбранный из этого распределения, сколько энтропии у нас будет? Мой скрипт на Python сказал мне, что у нас целых 3,3 бит энтропии на пиксель . И это много шума.

Если бы это действительно было так, это означало бы, что независимо от того, какой алгоритм сжатия мы используем, битовая карта 1000x1000 пикселей будет в лучшем случае сжиматься в файл размером 412500 байт. И что происходит на практике: я получил PNG-файл размером 432018 байт, довольно близко.

Если мы немного преувеличим, кажется, что независимо от того, какие черно-белые фотографии я отсканирую с помощью этого сканера, я получу сумму следующего:

• «полезная» информация (если есть),
• шум, ок. 3 бита на пиксель.

Теперь, даже если ваш алгоритм сжатия сжимает полезную информацию в << 1 бит на пиксель, вы все равно будете иметь до 3 бит на пиксель несжимаемого шума. И несжатая версия составляет 8 бит на пиксель. Таким образом, степень сжатия будет в пределах 1: 2, независимо от того, что вы делаете.

Другой пример, с попыткой найти чрезмерно идеализированные условия:

• Современная камера DSLR, использующая самую низкую чувствительность (минимум шума).
• Сфокусированный снимок серой карты (даже если на серой карте была какая-то видимая информация, она была бы размыта).
• Преобразование файла RAW в 8-битное изображение в оттенках серого без добавления контраста. Я использовал типовые настройки в коммерческом конвертере RAW. Конвертер пытается уменьшить шум по умолчанию. Более того, мы сохраняем конечный результат в виде 8-битного файла - по сути, мы отбрасываем биты младшего разряда необработанных показаний датчика!

И каков был конечный результат? Это выглядит намного лучше, чем то, что я получил от сканера; шум менее выражен, и ничего не видно. Тем не менее, гауссовский шум есть:

А энтропия? 2,7 бит на пиксель . Размер файла на практике? 344923 байта для 1M пикселей. В действительно лучшем сценарии с некоторыми изменениями мы увеличили степень сжатия до 1: 3.

Конечно, все это не имеет ничего общего с исследованиями TCS, но я думаю, что хорошо иметь в виду, что действительно ограничивает сжатие оцифрованных данных в реальном мире. Достижения в разработке более изящных алгоритмов сжатия и сырых ресурсов процессора не помогут; если вы хотите сохранить весь шум без потерь, вы не можете сделать намного лучше, чем 1: 2.

Вы уже знаете о теореме Шеннона о бесшумном кодировании ? Эта теорема устанавливает теоретические пределы сжатия без потерь. Некоторые из комментариев других, кажется, предполагают, что вы знаете об этой теореме, но из этого вопроса, я думаю, это может быть ответ, который вы ищете.

$n>0$

1. $n$

2. Обычное практическое решение состоит в использовании 8 битов, если единственные целые числа, которые вы когда-либо будете кодировать, все будут между 1 и 256 (обобщите до 16, 32 и 64 бит, если хотите).

3. $n+1$$n$$n$

4. $\lceil\log_2 n\rceil$$\lceil\log_2 n\rceil+1$$n$$\lceil\log_2 n\rceil-1$$\lceil\log_2 n\rceil$$2\lceil\log_2 n\rceil-1$$n$$\lg n=\max(1,\lceil\log_2 n\rceil)$

5. $2\lceil\log_2 n\rceil-1$

6. Тем не менее, принимая «оппортунистический» подход к своему пределу, существует бесконечное количество схем сжатия, использующих различные гипотезы. Один из способов справиться с этой бесконечностью оппортунистических кодировок (т.е. схем сжатия) состоит в том, чтобы требовать кодирования самой гипотезы и учитывать размер кодирования гипотезы в общем размере сжатия. Формально это соответствует кодированию как сжатых данных, так и декодера или, в более общем случае, кодированию программы, которая при выполнении выводит несжатый объект: наименьший размер такой программы называется сложностью Колмогорова. $K$, Это очень теоретическая конструкция в том смысле, что без ограничения времени выполнения программы$K$не вычислимо Простой способ обойти это понятие дается программами саморазграничения Левина , где вы рассматриваете только программы с ограниченным временем выполнения (например, в пределах постоянного фактора длины исходного экземпляра, который является нижней границей сложность алгоритма, который должен записывать каждый символ).

Существует целое сообщество, работающее над сложностью Колмогорова и его вариантами, и другое сообщество, работающее над сжатием без потерь (пример с целыми числами, который я использовал, имеет эквивалент для многих других типов данных), я едва поцарапал поверхность, а другие могли бы добавить точности (Колмогоров на самом деле не моя специальность), но я надеюсь, что это может помочь вам уточнить ваш вопрос, если не обязательно даст вам ответ, на который вы надеялись :)

(просто продолжение моего комментария)

(Как указал Джо в своем ответе) Шеннон - в своей статье 1948 года « Математическая теория коммуникации » сформулировал теорию сжатия данных и установил, что существует фундаментальный предел сжатия данных без потерь. Этот предел, называемый скоростью энтропии, обозначается буквой H. Точное значение H зависит от источника информации, в частности, от статистической природы источника. Можно сжимать источник без потерь со скоростью сжатия, близкой к H. Математически невозможно сделать лучше, чем H.

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

JPEG-LS и JPEG2000, похоже, являются стандартами для хранения медицинских изображений без потерь. См. Эту таблицу для сравнения коэффициентов сжатия (JPEG-LS достигает немного лучшего сжатия).

Используя «сжатие медицинских изображений без потерь», я нашел следующие статьи, которые могут вам помочь:

Недавний (2011 г.) обзор медицинских методов сжатия изображений: двумерные медицинские методы сжатия изображений - обзор

... В этой статье представлен обзор различных методов сжатия на основе DCT, DWT, ROI и нейронных сетей для двумерных (2D) медицинских изображений.

Подробное представление двух стандартных алгоритмов сжатия без потерь: JPEG-LS и JPG2000 в режиме без потерь: Сжатие без потерь медицинских изображений в градациях серого. Эффективность традиционных и современных подходов

... Было протестировано три тысячи шестьсот семьдесят девять (3679) однокадровых изображений в градациях серого из разных анатомических областей, условий и поставщиков. ...

Другой опрос: обзор современных медицинских методов сжатия изображений

РЕДАКТИРОВАТЬ

Возможно, вы все еще задаетесь вопросом "Что, черт возьми, энтропия изображения?" ... Хорошо, это объем информации, содержащейся в изображении ... но чтобы лучше понять это, вы должны прочитать кое-что о 3 фазах, обычно используемых при сжатии изображений :

• преобразование (например, дискретное вейвлет-преобразование)
• квантование
• энтропийное кодирование

Вы можете использовать Google для поиска учебника или книги по сжатию изображений (например, быстрого учебника ) или попробовать посмотреть онлайн-техническое видео (например, лекция 16 - Введение в кодирование изображений и видео ).

Думайте о файле как о строке.

Вы никогда не можете сделать лучше, чем колмогоровская сложность строки (это по определению сложности Комогорова).

Исправьте длину строки. Так что теперь мы смотрим только на строки длины n.

Половина всех таких строк может быть сжата не более чем на 1 бит. 1/4 всех строк можно сжать максимум на 2 бита. 1/8 всех таких строк можно сжать максимум на 3 бита.

Так какую часть строк (изображения, файлы и т. Д.) Можно сжать в соотношении 2: 1 - очень, очень мало. Так почему же сжатие работает? Потому что почти все данные, которые реальные люди на самом деле пытаются сжать, очень структурированы - это не похоже на случайный файл. Чем больше случайных данных, тем сложнее их сжать. Они идут рука об руку. Большинство строк выглядят случайными.

Чтобы увидеть это в действии, создайте случайный файл, используя некоторый случайный процесс. Я имею в виду действительно очень случайный файл. Теперь попробуйте сжать его, используя ваш любимый алгоритм сжатия. Он либо останется прежним, либо увеличится почти все время.

С другой стороны, есть очень сжимаемые струны. Возьмем следующую строку: 100000..000 (1, за которым следует миллион нулей). Описание этого вписывается в предыдущее предложение, и компьютер может восстановить его по этому описанию (или одному очень похожему). И все же это описание далеко не миллион цифр.

Дело в том, что строки с этим свойством (высокой степени сжимаемости) крайне редки среди всех возможных строк. Вторичный факт заключается в том, что почти все данные, созданные человеком, являются супер, супер сжимаемыми, потому что они так структурированы.