Dropbox опубликовал реализацию алгоритма сжатия изображений Lepton
Разработчики из компании Dropbox представили новый алгоритм сжатия изображений без потерь, применяемый для обеспечения экономии дискового пространства при хранении пользовательских изображений, уже сжатых в формате JPEG. Lepton позволяет сократить размер изображения JPEG в среднем на 22% без потери информации и с возможностью полностью бит в бит воссоздать исходный файл. Библиотека с реализацией алгоритма и сопутствующий набор утилит распространяется под лицензией Apache 2.0.
Реализация отличается высокой производительностью - на системе с CPU Intel Xeon E5 2650 (2.6GHz) сжатие производится со скоростью 5 мегабайт в секунду, а восстановление оригинала со скоростью 15 мегабайт в секунду, что позволяет организовать обработку изображений на лету и использовать Lepton для потоковой отдачи контента. Потребление оперативной памяти при работе с изображением составляет менее 24 Мб. Lepton применяется в Dropbox для хранения около 16 миллиардов изображений, позволяя компании экономить петабайты дискового пространства.
Используемый в Lepton алгоритм сжатия основан на предсказании коэффициентов кодирования в JPEG-блоках и использования предсказанных параметров для увеличения эффективности работы арифметического кодировщика. Напомним, что формат JPEG разбивает изображения на блоки 8×8 пикселей, которые сохраняются в виде 64 знаковых десятибитовых коэффициентов, при помощи которых можно воссоздать блок при помощи дискретного косинусного преобразования (DCT) и уточняющих параметров.
Уменьшение размера хранимых данных достигается благодаря тому, что рассчитанные коэффициенты не записываются как есть, а подвергаются дополнительному арифметическому кодированию (применяется кодировщик VP8), в котором учитываются данных ранее обработанных секций изображения, а результат сохраняется в формате унарного кодирования. Кроме того, коэффициент, отвечающий за параметры яркости (занимает до 8% размера), с высокой долей вероятности может быть предсказан на основании содержимого остальных коэффициентов. Для достижения 100% точности восстановления, Lepton оценивает разницу между предсказанным и фактическим значением и сохраняет только отличия.
Для повышения безопасности в реализации применяется фильтр seccomp, блокирующий выполнение системных вызовов, за исключением системных вызовов для чтения и записи в уже открытые файловые дескрипторы. Надёжность работы алгоритма проверена путем побитового сравнения восстановленных после кодирования изображений на коллекции из 4 миллиардов фотографий.