- PVSM.RU - https://www.pvsm.ru -

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь

Арифметическое кодирование по образцу Pied Piper

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 1
Предсказание коэффициентов дискретного косинусного преобразования в соседних 64-битных блоках JPEG

Компания Dropbox опубликовала исходный код [1] нового формата потокового сжатия изображений Lepton (репозиторий на Github [2]). Исходный код Lepton опубликован под свободной лицензией Apache. Всех желающих приглашают оптимизировать новый свободный алгоритм.

Lepton демонстрирует средний коэффициент компрессии 22% на файлах JPEG, предсказывая коэффициенты ДКП в JPEG-блоках и учитывая эти коэффициенты в качестве контекста для арифметического кодера, то есть кодируя дельту коэффициентов в соседних блоках.

Как работает Lepton

Как известно, формат JPEG разбивает изображения на блоки 8×8 пикселов. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП) с вычислением 10-битных коэффицентов ДКП для яркости и цветности. Таким образом, картинка 16×16 будет закодирована в четыре блока JPEG по 64 коэффициента ДКП в каждом.

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 2

Полученные 10-битные коэффициенты ДКП квантуются и пакуются с использованием кодирования серий и кодов Хаффмана.

Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования [3], однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно использовалось редко.

Алгоритм Lepton проходит по коэффициентам из блока зигзагообразным образом, кодируя данные арифметическим кодером VP8 [4].

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 3

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

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 4

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 5

Lepton осуществляет другие арифметические операции с коэффициентами. Например, дополнительное преимущество получается за счёт переноса коэффициента яркости в конец цепочки после всех коэффициента цветности. Кроме того, в этом формате значения коэффицентов записываются в более компактном бинарном представлении, отбрасывая первую единичку, потому что во всех двоичных значения больше нуля первый знак — единица.

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 6

Метод предсказания коэффициентов в соседних блоках путём их анализа с использованием этой информации для сжатия без потерь был описан в сериале «Кремниевая долина», его изобрела вымышленная компания Pied Piper. В кадре из фильма этот агоритм показан на одном из слайдов презентации с подписью «MIDDLE OUT!!»

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 7

Производительность

Кодирование только дельты коэффициента яркости позволяет уменьшить их объём на 39% в типичном файле JPEG, где коэффициенты яркости занимают обычно около 8% объёма файла. Но вместе с другими техниками сжатия общий коэффициент компрессии составляет, в среднем, 22%. На графике показан результат обработки 10 000 изображений в тестовой выборке с разных цифровых камер и смартфонов.

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 8

Сжатие файлов JPEG осуществляется на скорости 5-9 МБ/с, декомпрессия — 15-25 МБ/с, потребляя 24 МБ оперативной памяти, на компьютере Intel Xeon E5 2650 v2 2,6 ГГц, пишут разработчики.

Dropbox использовала формат Lepton для кодирования 16 миллиардов изображений на хостинге [5] Dropbox, освободив несколько петабайт. Сейчас в Dropbox быстро продвигается работа по кодированию всех старых файлов: это позволит значительно сэкономить на объёмах хранения информации. Сохранность данных гарантируется процессом кодирования: каждый файл после сжатия и декомпрессии сверяется бит-в-бит с оригиналом, и только после этого исходную копию удаляют. Для дополнительной безопасности вместе Lepton на уровне ядра Linux запускается фильтр системных вызовов seccomp, который запрещает все системные вызовы, кроме операций операции чтения и записи уже открытых файловых дескрипторов.

JPEG устарел

В настоящее время существует много форматов сжатия изображения, которые превосходят JPEG по коэффициенту сжатия и скорости работы. Например, формат WebP [6] тоже использует кодер VP8 и на голову превосходит JPEG по показателям. Формат WebP поддерживается во многих браузерах и всё чаще применяется для публикации изображений в интернете.

Есть ещё свободный формат FLIF [7], который в тестах превосходит даже WebP. Как показало сравнительное тестирование (результаты [8]), файлы FLIF в среднем:

  • на 14% меньше, чем lossless WebP,
  • на 22% меньше, чем lossless BPG,
  • на 33% меньше, чем PNG с брутфорсом через ZopfliPNG,
  • на 43% меньше типичного PNG,
  • на 46% меньше PNG, оптимизированного алгоритмом образования чересстрочного изображения Adam7,
  • на 53% меньше lossless JPEG2000,
  • на 74% меньше lossless JPEG XR.

Даже если для каждого отдельного изображения выбирать наилучший формат сжатия среди конкурентов, в зависимости от типа картинки — фотография, графика, 8 бит или больше — FLIF всё равно имеет преимущество примерно 12% по медиане (или 19% в среднем). Таким образом, ключевые преимущества FLIF — лучшая степень сжатия и универсальность, работа с любыми видами изображений. FLIF побеждает всех конкурентов на всех типах изображений. Результаты сравнительного тестирования по типам изображений см. здесь [9].

Свободный формат Lepton сжимает файлы JPEG на 22% без потерь - 9

Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение. Так что «обратно совместимый» формат Lepton может быть полезен как временное решение. Если вы храните на диске несколько 5 гигабайт фотографий, то можно быстро освободить 1 гигабайт дискового пространства, используя сжатия без потерь.

Автор: alizar

Источник [10]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/open-source/156745

Ссылки в тексте:

[1] опубликовала исходный код: https://blogs.dropbox.com/tech/2016/07/lepton-image-compression-saving-22-losslessly-from-images-at-15mbs/

[2] репозиторий на Github: https://github.com/dropbox/lepton

[3] арифметического кодирования: https://ru.wikipedia.org/wiki/Арифметическое_кодирование

[4] арифметическим кодером VP8: https://en.wikipedia.org/wiki/Arithmetic_coding

[5] хостинге: https://www.reg.ru/?rlink=reflink-717

[6] WebP: https://developers.google.com/speed/webp/

[7] FLIF: https://habrahabr.ru/post/278745/

[8] результаты: https://docs.google.com/spreadsheets/d/1LxY78fbm47VmrYGTXkBXXitGjhGl32NsuHPH2QXufgA/edit?usp=sharing

[9] здесь: https://docs.google.com/spreadsheets/d/16ghJEjf_T7TDTOg2WlelnG1SYCsHng6V-1rxdo78YL8/edit#gid=1623754371

[10] Источник: https://habrahabr.ru/post/305740/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best