Арифметическое кодирование по образцу 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 гигабайт дискового пространства, используя сжатие без потерь.
Комментарии (55)
hdfan2
15.07.2016 14:01+2А с чего это вдруг Lepton «обратно совместимый»? Где такое написано?
Old_Chroft
15.07.2016 15:17Здесь вроде как сказано, что Lepton сначала сжимает файл по своему алгоритму, а потом обратно конвертирует его в JPEG:
It compresses JPEG files at a rate of 5 megabytes per second and decodes them back to the original bits at 15 megabytes per second, securely, deterministically, and in under 24 megabytes of memory
SHVV
15.07.2016 15:24+3На сколько я понимаю, здесь только говориться о скорости кодирования-декодирования. Просто делает он это не над сырыми битмапами, а над уже сжатыми jpeg-ами, не внося никаких дополнительных потерь. При декодировании получается ровно тот же jpeg, что и был до кодирования, байт в байт, ни больше ни меньше.
Alexufo
15.07.2016 14:11DjOnline дождался наконец.
DjOnline
17.07.2016 12:12+2Если честно, то я ничерта не понял, чем это отличается от того же PackArc, WinZip или StuffIt, которые пережимают jpeg в arithmetic jpeg без потерь и так же обеспечивают совпадение бит в бит при обратной конвертации.
>>Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования, однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно использовалось редко.
Все патенты давным давно закончились, сколько можно нести эту чепуху годами? https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents
И в итоге всё равно кодируют арифметическим кодером из VP8, к чему тогда был этот ненужный пассаж про патенты?
Вообщем как я понял это абсолютно то же самое что и PackArc, WinZip, StuffIt и arithmetic jpeg, только вместо того чтобы добавить поддержку arithmetic jpeg во все брузеры и libjpeg придумываются очередные «временные упаковщики».
Абзац про FLIF вообще абсолютно лишний, FLIF это аналог gif/png а не jpeg, там даже в табличке не сранивают его с jpeg. Что курил автор чтобы впихнуть это абзац? А, ну да, это же Ализар, он не умеет думать.
И вообще, уже была статья про это https://geektimes.ru/post/261058/, ничего с тех пор не изменилось.avost
18.07.2016 10:29>Если честно, то я ничерта не понял, чем это отличается от того же PackArc, WinZip или StuffIt, которые пережимают jpeg в arithmetic jpeg без потерь и так же обеспечивают совпадение бит в бит при обратной конвертации.
Может быть процессорной нагрузкой? Я не утверждаю, это предположение.
>>однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно использовалось редко
>Все патенты давным давно закончились, сколько можно нести эту чепуху годами?
Патенты закончились, но на практике арифметическое кодирование всё равно до сих пор используется редко (потом что раньше оно было под патентами). Что не так?
>только вместо того чтобы добавить поддержку arithmetic jpeg во все брузеры и libjpeg придумываются очередные «временные упаковщики».
э-э-э, как вы себе это представляете? Пришёл такой дропбокс и встроил поддержку арифметического кодирования во все браузеры? Дропбокс просто решил свои конкретные проблемы. Решить «вместо этого» проблемы браузеров он просто не в состоянии.DjOnline
18.07.2016 14:36Хотелось бы увидеть тогда тесты процессорной нагрузки, а не пустую статью.
В браузерах уже лет 5 открыты тикеты на поддержку arithmetic jpeg, но воз и ныне там. В libjpeg поддержка arithmetic jpeg давно есть, с 2009 года.
homm
18.07.2016 15:50Браузеры можно понять. Введение нового обратно не совместимого формата означает, что половину бразуеров перестанут открывать некоторые картинки. Это ничем не отличается от поддержки нового формата. А зачем нам еще один новый формат без альфаканала? Лучше уже бросить силы на поддержку действительно нового формата врде webp.
Artima
15.07.2016 14:16Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение.
Проблема не в том, чтобы отказаться, а в том, чтобы перейти на новый. Мы же до сих пор не можем использовать даже WebP нормально. Была бы возможность, давно бы уже использовали.
PaulZi
15.07.2016 14:16WebP побеждает FLIF как минимум по функциональности, но прогрессу мешает уже политика корпораций. Вот и будем сидеть на старом JPEG, пока либо кто-то не одумается, либо кто-то почти всю долю рынка не захватит.
Alexufo
15.07.2016 14:18Например, формат WebP тоже использует кодер VP8 и на голову превосходит JPEG по показателям.
Есть одно но.
WebP кодек адаптивный, а jpg равномерный. Когда начал экспериментировать по сжатию паспортов, был удивлен насколько нагло webp себя ведет с тем что считает лишним т.е бледные лица на фотографии загранника он замылил мама не горюй. И тут jpg мне прекрасно равномерно все пожал без всех этих умных алгоритмов.
Другими словами, если ваш документ прыгает по яркости. Например, печати бледные, а где контрастные, то webp будет выдавать вам непредсказуемый результат в отличие от jpg. Кстати, не понимаю, почему декодеры jpg еще не умеют убирать квадраты, то есть jpg вполне себе имеет капельку качества через восстановление артефактов.RomanArzumanyan
15.07.2016 14:46+2Декодер jpg не может убрать квадраты, потому что кодер jpg их поместил в поток.
Постобработка с устранением артефактов блочности — пожалуйста, но декодеру этим заниматься нельзя, он должен обеспечивать результат «бит в бит».
ComradeAndrew
15.07.2016 15:23-1Я может что-то не так понял, но кажется только декодеры lossless должны декодировать"бит в бит". Декодеры изображений, сжатых с потерями, по определению не смогут добиться результата "бит в бит". Так почему бы не убирать квадраты?
RomanArzumanyan
15.07.2016 17:16Если мы декодируем один и тот же jpeg 2мя разными декодерами, результаты их работы (несжатые картинки в YCbCr) будут побитово идентичны. Т. е. что кодер положил в битовый поток (квадраты, шумы и прочее), то мы и достали.
Улучшайзеры декодированной картинки, безусловно, имеют право на жизнь — но отдельно от кодеков.
Indexator
16.07.2016 07:04Потери вносит только кодировщик (именно поэтому и удается добиться высоких коэффициентов сжатия). Декодер должен декодировать без потерь, «бит в бит», всегда! Картинка получается хуже оригинала из-за потерь информации во время кодирования, но одинаковая абсолютно везде! А постфильтры уже добавляются по вкусу и не имеют к декодерам никакого отношения…
jamezzz
15.07.2016 15:28Когда-то я решил сравнить разные JPEG-декодеры (Adobe Photoshop, класс Image из System.Drawing, MS Paint, XnView) и был немного удивлён, что все они дают разный результат, различимый на глаз.
iOrange
15.07.2016 21:17Я думаю, что скорее всего разница в IDCT и разном способе интерполяции хроматик (Cb Cr).
Больше не вижу где они могут отличаться.
iOrange
15.07.2016 17:15Попробуйте JpegXR (бывший HD Photo) — у меня получались очень хорошие результаты.
Alexufo
15.07.2016 21:08дану, без популярности не имеет смысла)
iOrange
15.07.2016 21:18Смотря для чего вам. Я храню все фото в нем — размер меньше, качество выше. Почти все программы с ним умеют работать.
sim31r
16.07.2016 02:18Фотоаппарат по умолчанию делает jpeg 4912x3264, при перекодировании может потеряться информация, jpeg теряет одну часть информации, JpegXR другую. Но при кодировании напрямую из raw имеет смысл выбрать формат под свои нужды.
lockywolf
15.07.2016 15:47На Хабре пробегала статья где-то год-два назад с примерами сжатия одного и того же изображения разными кодеками, где и указывалась «несовременность» JPEG.
Но в комментариях народ довольно позитивно воспринял мысль, что почему-то все, кроме JPG форматы «мылят» картинку. Да, JPG создаёт неприятные блоки, но «резкость» краёв этих блоков воспринимается приятнее, чем «мыльные» варианты, которые формально ближе к оригиналу.sim31r
16.07.2016 02:29-1Возможно резкость краев стала привычной, как шумы в «теплом ламповом звуке», просто отмечаешь про себя что в картинке дефицит информации, сжатие с потерями.
А новые форматы слишком интеллектуальные, были примеры, когда на скане паспорта алгоритм решал что черно белая фотография с низкой контрастностью второстепенный элемент и замыливал фотографию до состояния фона. Старинный Jpeg более честен в этом плане, дефекты видны сразу, все части изображения равноправны, сюрпризов не возникает.
Alexey2005
15.07.2016 16:50Чем нужно жать в WebP, чтобы получить меньший размер файла при том же качестве? Попробовал взять пачку jpeg и пропустить через imagemagick convert, так на выходе размер во всех случаях увеличивается.
maolo
15.07.2016 19:39Я пользуюсь официальной утилитой отсюда developers.google.com/speed/webp/docs/precompiled
Там либа под разные операционные системы есть, я на Linux'е конвертирую.
Но, как выше сказали, результат не всегда предсказуем — надо смотреть каждую картинку, по крайней мере, пока статистику для себя не наработаете. Иной раз, картинка в jpg и качественнее, и меньше.
Suntechnic
15.07.2016 22:43+2А почему он должен уменьшится если вы жмете jpeg? Аналогия конечно не совсем точная, но все равно — вы же не ожидаете что сжав документ rar, а потому zip получите меньший размер? Возьмите исходную картинку без потерь, да хоть в bmp и жмите в jpeg и webp и сравнивайте результат. И то это не совсем корректно будет, потому что могут использоваться разные параметры.
sumanai
15.07.2016 22:47> А почему он должен уменьшится если вы жмете jpeg?
Наверное потому что разработчики формата его только этим и нахваливают- «Лучшее качество при меньшем размере» и тому подобное? Поневоле ждёшь обещанного, и плохо, когда это обещание не выполняется.
Хотя странно, обычно jpeg всё таки меньше.
Denai
16.07.2016 00:56Я гонял десяток разных PNG через один из конвертеров в WebP и на выходе при равном качестве jpeg всегда оказывался меньше весом. Может мне конвертер попался старый, может картинки не те, может я с параметрами не совладал, но я ожидал более очевидный и простой результат.
HOMPAIN
15.07.2016 19:15Если у нового формата выигрыш 22% по сравнению с jpeg при том же качестве, то на это даже отвлекаться не стоит. Ввод такого формата ничего в корне не поменяет, а ввести его будет крайне сложно.
Что у вас на втором графики изображено? Почему PNG/PNG не равно 1? PNG разве вообще позволяет задавать степень сжатия?sumanai
15.07.2016 19:40+1> PNG разве вообще позволяет задавать степень сжатия?
Да, плюс удаление служебных метаданных, плюс оптимизаторы, так же есть различные инструменты типа Zopfli для большего сжатия.
netgoblin
16.07.2016 18:59Можно оптимизировать палитру цветов (как в GIF), а еще удаляются цвета из полностью прозрачных пикселей.
amarao
15.07.2016 19:16-1Но получающийся файл не поддерживается большинством софта. Это убивает весь смысл кодирования, кроме совсем уж адского архивирования.
TheShock
16.07.2016 06:06+3Я так понимаю, что пользователям отдается JPEG, а Lepton используется только для хранения. Процы все равно на файлопомойках простаивают, потому совершенно не проблема его при каждом запросе разархивировать из Липтона обратно в Жпег.
geekmetwice
15.07.2016 23:29Любой стандарт практически ничего не стоит поддержать, но почему-то ресурсы тратятся на всякие перделки, даже у коммерческих компаний. Была бы поддержка FLIF у «большой тройки» браузеров, а за год все дизайнеры перекодировали картинки, юзеры бы даже не заметили этой маленькой-большой революции!
Denai
16.07.2016 00:49+1Откуда взяться поддержке FLIF у «большой тройки» браузеров, если он слишком медленный для нынешнего веба? ДКПВ от этого поста уже сейчас можно сжать без потерь на 25%, не меняя формат. На моём ПК на это уходит больше 5 минут времени. Разжиматься она будет очень быстро. Можно перерисовать в SVG, будет вообще чудесно, но этого не сделает Ализар. FLIF быстрее сожмёт растр, но у него и на декодирование уходит уйма времени в текущей реализации, вы готовы ждать 10+ секунд каждую картинку в посте?
Само собой при высокой поддержке может оказаться что кодер и декодер станут быстрее, но сомневаюсь что настолько.
zartdinov
16.07.2016 02:33-110 мин процессорного времени для экономии 1 гигабайта.
Потом каждый раз по 5 мин с кэшированием и надеждой переложить на пользователей и их браузеры.
Если не ошибаюсь, тут пропорционально увеличиваются риски, так как возрастает ценность битов…
Не тоже самое, конечно, что реплику отключить на несколько петабайт, но все равно))
Old_Chroft
16.07.2016 11:09+4Все всё напутали (в посте — предпосылки, а в комментариях «ну началось...»). Начали примерять новый формат для web-а. Он НЕ для этого. DropBox разрабатывал его для своих нужд, и вроде как достиг цели:
Dropbox использовала формат Lepton для кодирования 16 миллиардов изображений на хостинге Dropbox, освободив несколько петабайт
За приемлимое кол-во времени и ресурсов. Точка.homm
17.07.2016 03:21Формат конечно не для этого. Но обида берет, что разработчики оригинального JPEG не додумались до этой простой идеи, не освободив тем самым несколько эксабайт.
homm
17.07.2016 03:19Таким образом, ключевые преимущества FLIF — лучшая степень сжатия и универсальность, работа с любыми видами изображений. FLIF побеждает всех конкурентов на всех типах изображений. Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение.
Господи, alizar, каким боком вы вообще сюда FLIF приплели? Про FLIF в оригинальной статье Дропбокса ни слова не было. FLIF не побеждает всех конкурентов на всех типах изображений, потому что он предназначен только для сжатия без потерь. Никто никогда не откажется от JPEG в пользу FLIF, это полный бред.
Anton_Shevtsov
18.07.2016 07:33-2до тех пор пока порно в интернете в jpeg, любой самый прогрессивный и современный алгоритм обречен остаться лишь строчкой в википедии.
webmasterx
А точнее только в хром-like и штатном андроид браузерах
Или firefox не официально поддерживает?
cy-ernado
Mozilla, Apple и Microsoft крайне маловероятно когда-нибудь задумаются о поддержке этого формата, и по большому счету это только политическое решение.
Никаких технических ограничений нет, в багтрекере мозиллы поддержка webp висит уже давно.
Но даже в такой ситуации "только" 70% поддержки.
cy-ernado
Хотя нет, Safari "по слухам" "going to support WebP in iOS 10 and macOS Sierra", так что скоро ситуация может измениться.
Shannon
Уже даже не по слухам, а на бетах webp работает
«WebP is now supported on Safari 10 both on macOS sierra and iOS 10»
https://groups.google.com/a/webmproject.org/forum/#!topic/webp-discuss/J8HLhTaklYE
Lain_13
Всё ещё нет: https://bugzilla.mozilla.org/show_bug.cgi?id=856375
В то же время WebM уже поддерживается. Так что есть все шансы, что и это сделают. Но вот когда?
Denai
Firefox умеет частично через JS
Denai
Но это не заслуга firefox, конечно. http://webpjs.appspot.com/