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

    Арифметическое кодирование по образцу 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 гигабайт дискового пространства, используя сжатие без потерь.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 55

      +2
      Формат WebP поддерживается во многих браузерах и всё чаще применяется для публикации изображений в интернете.

      А точнее только в хром-like и штатном андроид браузерах
      Или firefox не официально поддерживает?
        0

        Mozilla, Apple и Microsoft крайне маловероятно когда-нибудь задумаются о поддержке этого формата, и по большому счету это только политическое решение.
        Никаких технических ограничений нет, в багтрекере мозиллы поддержка webp висит уже давно.
        Но даже в такой ситуации "только" 70% поддержки.

        0
        Всё ещё нет: https://bugzilla.mozilla.org/show_bug.cgi?id=856375
        В то же время WebM уже поддерживается. Так что есть все шансы, что и это сделают. Но вот когда?
          0
          Firefox умеет частично через JS
            0
            Но это не заслуга firefox, конечно. http://webpjs.appspot.com/
          +2
          А с чего это вдруг Lepton «обратно совместимый»? Где такое написано?
            0
            Здесь вроде как сказано, что 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
              +3
              На сколько я понимаю, здесь только говориться о скорости кодирования-декодирования. Просто делает он это не над сырыми битмапами, а над уже сжатыми jpeg-ами, не внося никаких дополнительных потерь. При декодировании получается ровно тот же jpeg, что и был до кодирования, байт в байт, ни больше ни меньше.
            0
            DjOnline дождался наконец.
              +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/, ничего с тех пор не изменилось.
                0
                >Если честно, то я ничерта не понял, чем это отличается от того же PackArc, WinZip или StuffIt, которые пережимают jpeg в arithmetic jpeg без потерь и так же обеспечивают совпадение бит в бит при обратной конвертации.

                Может быть процессорной нагрузкой? Я не утверждаю, это предположение.

                >>однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно использовалось редко
                >Все патенты давным давно закончились, сколько можно нести эту чепуху годами?

                Патенты закончились, но на практике арифметическое кодирование всё равно до сих пор используется редко (потом что раньше оно было под патентами). Что не так?

                >только вместо того чтобы добавить поддержку arithmetic jpeg во все брузеры и libjpeg придумываются очередные «временные упаковщики».

                э-э-э, как вы себе это представляете? Пришёл такой дропбокс и встроил поддержку арифметического кодирования во все браузеры? Дропбокс просто решил свои конкретные проблемы. Решить «вместо этого» проблемы браузеров он просто не в состоянии.
                  0
                  Хотелось бы увидеть тогда тесты процессорной нагрузки, а не пустую статью.

                  В браузерах уже лет 5 открыты тикеты на поддержку arithmetic jpeg, но воз и ныне там. В libjpeg поддержка arithmetic jpeg давно есть, с 2009 года.
                    0

                    Браузеры можно понять. Введение нового обратно не совместимого формата означает, что половину бразуеров перестанут открывать некоторые картинки. Это ничем не отличается от поддержки нового формата. А зачем нам еще один новый формат без альфаканала? Лучше уже бросить силы на поддержку действительно нового формата врде webp.

              0
              Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение.

              Проблема не в том, чтобы отказаться, а в том, чтобы перейти на новый. Мы же до сих пор не можем использовать даже WebP нормально. Была бы возможность, давно бы уже использовали.

                0
                Зато поддержка webm есть практически во всех распространенных браузерах.
                  0
                  Отсутствует в safari и, как следствие, во всех браузерах на iOS.
                0
                WebP побеждает FLIF как минимум по функциональности, но прогрессу мешает уже политика корпораций. Вот и будем сидеть на старом JPEG, пока либо кто-то не одумается, либо кто-то почти всю долю рынка не захватит.
                  0
                  Например, формат WebP тоже использует кодер VP8 и на голову превосходит JPEG по показателям.


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

                  Другими словами, если ваш документ прыгает по яркости. Например, печати бледные, а где контрастные, то webp будет выдавать вам непредсказуемый результат в отличие от jpg. Кстати, не понимаю, почему декодеры jpg еще не умеют убирать квадраты, то есть jpg вполне себе имеет капельку качества через восстановление артефактов.
                    +2
                    Декодер jpg не может убрать квадраты, потому что кодер jpg их поместил в поток.
                    Постобработка с устранением артефактов блочности — пожалуйста, но декодеру этим заниматься нельзя, он должен обеспечивать результат «бит в бит».
                      –1

                      Я может что-то не так понял, но кажется только декодеры lossless должны декодировать"бит в бит". Декодеры изображений, сжатых с потерями, по определению не смогут добиться результата "бит в бит". Так почему бы не убирать квадраты?

                        0
                        Если мы декодируем один и тот же jpeg 2мя разными декодерами, результаты их работы (несжатые картинки в YCbCr) будут побитово идентичны. Т. е. что кодер положил в битовый поток (квадраты, шумы и прочее), то мы и достали.

                        Улучшайзеры декодированной картинки, безусловно, имеют право на жизнь — но отдельно от кодеков.
                          0
                          Потери вносит только кодировщик (именно поэтому и удается добиться высоких коэффициентов сжатия). Декодер должен декодировать без потерь, «бит в бит», всегда! Картинка получается хуже оригинала из-за потерь информации во время кодирования, но одинаковая абсолютно везде! А постфильтры уже добавляются по вкусу и не имеют к декодерам никакого отношения…
                          0
                          Когда-то я решил сравнить разные JPEG-декодеры (Adobe Photoshop, класс Image из System.Drawing, MS Paint, XnView) и был немного удивлён, что все они дают разный результат, различимый на глаз.
                            0
                            Я думаю, что скорее всего разница в IDCT и разном способе интерполяции хроматик (Cb Cr).
                            Больше не вижу где они могут отличаться.
                          0
                          Попробуйте JpegXR (бывший HD Photo) — у меня получались очень хорошие результаты.
                            0
                            дану, без популярности не имеет смысла)
                              0
                              Смотря для чего вам. Я храню все фото в нем — размер меньше, качество выше. Почти все программы с ним умеют работать.
                                0
                                Фотоаппарат по умолчанию делает jpeg 4912x3264, при перекодировании может потеряться информация, jpeg теряет одну часть информации, JpegXR другую. Но при кодировании напрямую из raw имеет смысл выбрать формат под свои нужды.
                          0
                          На Хабре пробегала статья где-то год-два назад с примерами сжатия одного и того же изображения разными кодеками, где и указывалась «несовременность» JPEG.

                          Но в комментариях народ довольно позитивно воспринял мысль, что почему-то все, кроме JPG форматы «мылят» картинку. Да, JPG создаёт неприятные блоки, но «резкость» краёв этих блоков воспринимается приятнее, чем «мыльные» варианты, которые формально ближе к оригиналу.
                            –1
                            Возможно резкость краев стала привычной, как шумы в «теплом ламповом звуке», просто отмечаешь про себя что в картинке дефицит информации, сжатие с потерями.
                            А новые форматы слишком интеллектуальные, были примеры, когда на скане паспорта алгоритм решал что черно белая фотография с низкой контрастностью второстепенный элемент и замыливал фотографию до состояния фона. Старинный Jpeg более честен в этом плане, дефекты видны сразу, все части изображения равноправны, сюрпризов не возникает.
                              0
                              шумы в «теплом ламповом звуке»
                              Вы путаете шумы с искажениями.
                            +23
                            Хоронили JPEG, порвали 3 стандарта.
                              –3
                              Прям как в сериале " Силиконовая долина"
                                0
                                Чем нужно жать в WebP, чтобы получить меньший размер файла при том же качестве? Попробовал взять пачку jpeg и пропустить через imagemagick convert, так на выходе размер во всех случаях увеличивается.
                                  0
                                  Я пользуюсь официальной утилитой отсюда developers.google.com/speed/webp/docs/precompiled
                                  Там либа под разные операционные системы есть, я на Linux'е конвертирую.

                                  Но, как выше сказали, результат не всегда предсказуем — надо смотреть каждую картинку, по крайней мере, пока статистику для себя не наработаете. Иной раз, картинка в jpg и качественнее, и меньше.
                                    +2
                                    А почему он должен уменьшится если вы жмете jpeg? Аналогия конечно не совсем точная, но все равно — вы же не ожидаете что сжав документ rar, а потому zip получите меньший размер? Возьмите исходную картинку без потерь, да хоть в bmp и жмите в jpeg и webp и сравнивайте результат. И то это не совсем корректно будет, потому что могут использоваться разные параметры.
                                      0
                                      > А почему он должен уменьшится если вы жмете jpeg?
                                      Наверное потому что разработчики формата его только этим и нахваливают- «Лучшее качество при меньшем размере» и тому подобное? Поневоле ждёшь обещанного, и плохо, когда это обещание не выполняется.
                                      Хотя странно, обычно jpeg всё таки меньше.
                                        0
                                        Я гонял десяток разных PNG через один из конвертеров в WebP и на выходе при равном качестве jpeg всегда оказывался меньше весом. Может мне конвертер попался старый, может картинки не те, может я с параметрами не совладал, но я ожидал более очевидный и простой результат.
                                      +2
                                      Стоит ли ожидать использование этого кодера в архиваторах для эффективного упаковывания изображений совместно с другими данными?
                                        +1
                                        Предложите в 7-zip, может примут :)
                                        0
                                        Если у нового формата выигрыш 22% по сравнению с jpeg при том же качестве, то на это даже отвлекаться не стоит. Ввод такого формата ничего в корне не поменяет, а ввести его будет крайне сложно.

                                        Что у вас на втором графики изображено? Почему PNG/PNG не равно 1? PNG разве вообще позволяет задавать степень сжатия?
                                          +1
                                          > PNG разве вообще позволяет задавать степень сжатия?
                                          Да, плюс удаление служебных метаданных, плюс оптимизаторы, так же есть различные инструменты типа Zopfli для большего сжатия.
                                            0
                                            Можно оптимизировать палитру цветов (как в GIF), а еще удаляются цвета из полностью прозрачных пикселей.
                                            –1
                                            Но получающийся файл не поддерживается большинством софта. Это убивает весь смысл кодирования, кроме совсем уж адского архивирования.
                                              0
                                              Первая версия, сорцы только открыли.
                                                +3
                                                Я так понимаю, что пользователям отдается JPEG, а Lepton используется только для хранения. Процы все равно на файлопомойках простаивают, потому совершенно не проблема его при каждом запросе разархивировать из Липтона обратно в Жпег.
                                                0
                                                Любой стандарт практически ничего не стоит поддержать, но почему-то ресурсы тратятся на всякие перделки, даже у коммерческих компаний. Была бы поддержка FLIF у «большой тройки» браузеров, а за год все дизайнеры перекодировали картинки, юзеры бы даже не заметили этой маленькой-большой революции!
                                                  +1
                                                  Откуда взяться поддержке FLIF у «большой тройки» браузеров, если он слишком медленный для нынешнего веба? ДКПВ от этого поста уже сейчас можно сжать без потерь на 25%, не меняя формат. На моём ПК на это уходит больше 5 минут времени. Разжиматься она будет очень быстро. Можно перерисовать в SVG, будет вообще чудесно, но этого не сделает Ализар. FLIF быстрее сожмёт растр, но у него и на декодирование уходит уйма времени в текущей реализации, вы готовы ждать 10+ секунд каждую картинку в посте?
                                                  Само собой при высокой поддержке может оказаться что кодер и декодер станут быстрее, но сомневаюсь что настолько.
                                                  –1
                                                  10 мин процессорного времени для экономии 1 гигабайта.
                                                  Потом каждый раз по 5 мин с кэшированием и надеждой переложить на пользователей и их браузеры.

                                                  Если не ошибаюсь, тут пропорционально увеличиваются риски, так как возрастает ценность битов…
                                                  Не тоже самое, конечно, что реплику отключить на несколько петабайт, но все равно))
                                                    +4
                                                    Все всё напутали (в посте — предпосылки, а в комментариях «ну началось...»). Начали примерять новый формат для web-а. Он НЕ для этого. DropBox разрабатывал его для своих нужд, и вроде как достиг цели:
                                                    Dropbox использовала формат Lepton для кодирования 16 миллиардов изображений на хостинге Dropbox, освободив несколько петабайт
                                                    За приемлимое кол-во времени и ресурсов. Точка.
                                                      0

                                                      Формат конечно не для этого. Но обида берет, что разработчики оригинального JPEG не додумались до этой простой идеи, не освободив тем самым несколько эксабайт.

                                                      0
                                                      Таким образом, ключевые преимущества FLIF — лучшая степень сжатия и универсальность, работа с любыми видами изображений. FLIF побеждает всех конкурентов на всех типах изображений. Проблема в том, что отказаться от устаревшего JPEG в пользу WebP или FLIF очень трудно: этот формат получил слишком большое распространение.

                                                      Господи, alizar, каким боком вы вообще сюда FLIF приплели? Про FLIF в оригинальной статье Дропбокса ни слова не было. FLIF не побеждает всех конкурентов на всех типах изображений, потому что он предназначен только для сжатия без потерь. Никто никогда не откажется от JPEG в пользу FLIF, это полный бред.

                                                        –2
                                                        до тех пор пока порно в интернете в jpeg, любой самый прогрессивный и современный алгоритм обречен остаться лишь строчкой в википедии.

                                                        Only users with full accounts can post comments. Log in, please.