Арифметическое кодирование по образцу Pied Piper
Предсказание коэффициентов дискретного косинусного преобразования в соседних 64-битных блоках JPEG
Компания Dropbox опубликовала исходный код нового формата потокового сжатия изображений Lepton (репозиторий на Github). Исходный код Lepton опубликован под свободной лицензией Apache. Всех желающих приглашают оптимизировать новый свободный алгоритм.
Lepton демонстрирует средний коэффициент компрессии 22% на файлах JPEG, предсказывая коэффициенты ДКП в JPEG-блоках и учитывая эти коэффициенты в качестве контекста для арифметического кодера, то есть кодируя дельту коэффициентов в соседних блоках.
Как работает Lepton
Как известно, формат JPEG разбивает изображения на блоки 8×8 пикселов. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП) с вычислением 10-битных коэффицентов ДКП для яркости и цветности. Таким образом, картинка 16×16 будет закодирована в четыре блока JPEG по 64 коэффициента ДКП в каждом.
Полученные 10-битные коэффициенты ДКП квантуются и пакуются с использованием кодирования серий и кодов Хаффмана.
Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования, однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно использовалось редко.
Алгоритм Lepton проходит по коэффициентам из блока зигзагообразным образом, кодируя данные арифметическим кодером VP8.
Эффективность кодирования значительно повышается, если аккуратно выбрать контекстную информацию из предыдущего 64-битного блока в изображении. Например, предсказывая значение коэффициентов для конкретных пикселов по значениям из пограничных пикселов в соседнем блоке.
Lepton осуществляет другие арифметические операции с коэффициентами. Например, дополнительное преимущество получается за счёт переноса коэффициента яркости в конец цепочки после всех коэффициента цветности. Кроме того, в этом формате значения коэффицентов записываются в более компактном бинарном представлении, отбрасывая первую единичку, потому что во всех двоичных значения больше нуля первый знак — единица.
Метод предсказания коэффициентов в соседних блоках путём их анализа с использованием этой информации для сжатия без потерь был описан в сериале «Кремниевая долина», его изобрела вымышленная компания Pied Piper. В кадре из фильма этот агоритм показан на одном из слайдов презентации с подписью «MIDDLE OUT!!»
Производительность
Кодирование только дельты коэффициента яркости позволяет уменьшить их объём на 39% в типичном файле JPEG, где коэффициенты яркости занимают обычно около 8% объёма файла. Но вместе с другими техниками сжатия общий коэффициент компрессии составляет, в среднем, 22%. На графике показан результат обработки 10 000 изображений в тестовой выборке с разных цифровых камер и смартфонов.
Сжатие файлов JPEG осуществляется на скорости 5-9 МБ/с, декомпрессия — 15-25 МБ/с, потребляя 24 МБ оперативной памяти, на компьютере Intel Xeon E5 2650 v2 2,6 ГГц, пишут разработчики.
Dropbox использовала формат Lepton для кодирования 16 миллиардов изображений на Dropbox, освободив несколько петабайт. Сейчас в Dropbox быстро продвигается работа по кодированию всех старых файлов: это позволит значительно сэкономить на объёмах хранения информации. Сохранность данных гарантируется процессом кодирования: каждый файл после сжатия и декомпрессии сверяется бит-в-бит с оригиналом, и только после этого исходную копию удаляют. Для дополнительной безопасности вместе Lepton на уровне ядра Linux запускается фильтр системных вызовов seccomp, который запрещает все системные вызовы, кроме операций операции чтения и записи уже открытых файловых дескрипторов.
JPEG устарел
В настоящее время существует много форматов сжатия изображения, которые превосходят JPEG по коэффициенту сжатия и скорости работы. Например, формат WebP тоже использует кодер VP8 и на голову превосходит JPEG по показателям. Формат WebP поддерживается во многих браузерах и всё чаще применяется для публикации изображений в интернете.
Есть ещё свободный формат FLIF, который в тестах превосходит даже WebP. Как показало сравнительное тестирование (результаты), файлы 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 побеждает всех конкурентов на всех типах изображений. Результаты сравнительного тестирования по типам изображений см. здесь.
Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение. Так что «обратно совместимый» формат Lepton может быть полезен как временное решение. Если вы храните на диске несколько 5 гигабайт фотографий, то можно быстро освободить 1 гигабайт дискового пространства, используя сжатия без потерь.
Автор: alizar
