Комментарии 42
Появится алгоритм сжатия видео для проекта «Пегий Дудочник» из «Кремниевой долины»
Ждём ИИ после такого :D
Главное, чтобы клавишу delete не зажали бутылкой текилы)
Это что, так «Pied Piper» на русской озвучке перевели, вместо «Крысолова»?
Нечто подобное появилось от китайцев, lossless пережатие до 20%, первая ссылка в этом комментарии https://habr.com/ru/post/570694/#comment_24833064
Но поиграться пока нечем, релиза нет (
А зачем сравнивать с форматом которому больше 10 лет и он до сих пор не всеми поддерживается?
Кем, кстати, WebP-то не поддерживается? Вы про IE 11, что ли?
Partial support in Safari refers to being limited to macOS 11 Big Sur and later.
Во-вторых, мир не ограничивается браузерами, нужны ещё и библиотеки для разных языков (здесь проблем вроде как нет), и программы, которые эти библиотеки используют — вот здесь начинаются приключения, например, на Windows вы не сможете просто так поставить WebP изображение как фон рабочего стола, каким бы красивым оно не было.
для алгоритмов сжатия изображений без потерь именно скорость, а не размер получившегося файла является главным критерием.BMP с RLE должен быть ещё быстрее, но, видимо, одной скорости недостаточно? Кстати, скорость чего — сжатия, распаковки, или обоих операций?
Если мы говорим исключительно про веб-сценарии, то мне всегда казалось, что хотят добиться сжатия получше при той же скорости распаковки, чтоб быстрее передавать по сети и не тратить батарейку пользователя слишком долгой обработкой. Если это действительно так (могу и ошибаться), то многие предпочли бы условный ABCPack, который сжимает в 10 раз дольше, но даёт файл на дополнительные 10% компактнее (при той же скорости распаковки) — тогда пользователю будет ещё комфортнее.
Это конечно хоршо, но без замеров на обширной базе изображений — это такое себе. Магии никакой тут нет, просто RLE плюс несколько евристик. Насколько оно хорошо работает на не тестовых изображениях — большой вопрос.
Меня немного смущает что алгоритм одномерный. Можно ведь как-то учитывать декодированые пиксели в кернел-окне.
Я бы еще и учитывал направление перебора в картинке, ну т.е. сверху-вниз или слева-направо. Т.к. в некоторых картинках повторение цвета как раз скорее вертикальное, чем горизонтальное.
А еще можно картинку порезать на блоки и каждый кодировать независимо.
Да и, наверное, можно собрать повторяющиеся последовательности закодированных пикселей вторым проходом и закодировать повторно — но это уже надо тестировать, не факт, что будет заметный эффект в итоговом размере файла. Ну и, понятно, что скорость работы уменьшится.
Потому что алгоритм и быстрый из за того что идет линейно по памяти.
И на сколько алгоритм станет медленней если если использовать не только пиксель слева, но и пиксель сверху?
Для этого придется хранить буфер в ширину изображения (строка "над"). И хождение будет уже не один раз на пиксель, а два, причем в разные кэш-линии. Так что будет медленее, но надо замерять критично ли медленнее.
Вопрос как для этого всего поменяется алгоритм и формат.
Наименее инвазивным видится добавление верхнего пикселя в кэш с 64 значениями.
… а еще можно градиенты искать, они же, в принципе, по четкой формуле генерируются. На каких-нибудь скриншотах это будет вполне эффективно работать, если вместо пикселей сохранять параметры генерации градиента.
Как я уже писал — можно разбить изображение на квадраты — и дополнительно сравнивать сами квадраты друг с другом. Если мы опять-таки возьмем скриншот, то окажется, что там значительная часть таких квадратов будет одинаковой (границы окон, рамки, кнопки, однотонные фоны и т.п.) — т.е. часть изображения можно будет кодировать отсылкой к предыдущим ранее закодированным квадратам
Но всё это уже явно не будет работать быстро и в один проход :)
Попробовал мелкую иконку 16x16 4bpp прогнал через кодер-декодер, результат тот же.
Архиватор, который сжимает файл до одного байта. Распаковщик на стадии разработки
Хм. У меня всё работает.
Компилятор:
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=C:/msys64/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/11.2.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Configured with: ../gcc-11.2.0/configure --prefix=/mingw64 --with-local-prefix=/mingw64/local --build=x86_64-w64-mingw32 --host=x86_64-w64-mingw32 --target=x86_64-w64-mingw32 --with-native-system-header-dir=/mingw64/x86_64-w64-mingw32/include --libexecdir=/mingw64/lib --enable-bootstrap --enable-checking=release --with-arch=x86-64 --with-tune=generic --enable-languages=c,lto,c++,fortran,ada,objc,obj-c++,jit --enable-shared --enable-static --enable-libatomic --enable-threads=posix --enable-graphite --enable-fully-dynamic-string --enable-libstdcxx-filesystem-ts --enable-libstdcxx-time --disable-libstdcxx-pch --disable-libstdcxx-debug --enable-lto --enable-libgomp --disable-multilib --disable-rpath --disable-win32-registry --disable-nls --disable-werror --disable-symvers --with-libiconv --with-system-zlib --with-gmp=/mingw64 --with-mpfr=/mingw64 --with-mpc=/mingw64 --with-isl=/mingw64 --with-pkgversion='Rev2, Built by MSYS2 project' --with-bugurl=https://github.com/msys2/MINGW-packages/issues --with-gnu-as --with-gnu-ld --with-boot-ldflags='-pipe -Wl,--dynamicbase,--high-entropy-va,--nxcompat,--default-image-base-high -Wl,--disable-dynamicbase -static-libstdc++ -static-libgcc' 'LDFLAGS_FOR_TARGET=-pipe -Wl,--dynamicbase,--high-entropy-va,--nxcompat,--default-image-base-high' --enable-linker-plugin-flags='LDFLAGS=-static-libstdc++\ -static-libgcc\ -pipe\ -Wl,--dynamicbase,--high-entropy-va,--nxcompat,--default-image-base-high\ -Wl,--stack,12582912'
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (Rev2, Built by MSYS2 project) Кстати, он даже для длин буферов использует int:
int size = ftell(f);
...
int bytes_read = fread(data, 1, size, f);Хотя мне VS Code подсказывает, что ftell возвращает long, а fread принимает и, что более важно, возвращает size_t. Я использую MSYS MinGW 64bit, и у меня size_t — это unsigned long long.
Так себе качество кода, в общем.
UPD хотел ответить qw1, но промахнулся
Ну или хотя бы по размеру кода, при сопоставимой производительности.
Вижу в блоге https://0xd34df00d.me/posts/2021/12/haskell-is-quite-ok-decoding.html . А можете описать процесс выкатки в hackage?
И каким образом определяется, что на выделенном сервере Ryzen 7 3700X (взято из блога)?
Быстрое сжатие картинок без потерь - отлично, давно такое ищу.
Хотя надо отметить, что обогнать сжатие в png - невелика заслуга, там оно медленное by design, т.к. "фильтр" для строки (преобразование, улучшающее сжимаемость) выбирается методом перебора. В зависимости от степени сжатия может перебираться больше или меньше разных фильтров, поэтому на макс. сжатии png очень медленный, на минимальном, без фильтров, это фактически тот же zip.
Интересно было бы сравнить Quite OK Image с ImageZero - тоже никому не известный алгоритм. В статье на Хабре заявлено аж 35-кратное превосходство в скорости над png (хм, может быть, автор QOI переизобрёл ImageZero заново?). Когда я сравнивал ImageZero с png, ускорение получалось меньше, в 2-4 раза, но зато некоторые картинки сжимались в 1.5 раза лучше. Возможно, png тестировался не на максимальном сжатии, точно не помню.
В целом ImageZero явно лучше png (точнее, алгоритмов сжатия png), но спустя 9 лет по-прежнему никому не известен...
Добрался до скачивания плагина для Paint.Net - не удалось получить ни один файл который был бы меньше PNG по размеру, в среднем QOI больше на 15% стабильно. Причем скриншот этого браузера аж в 1,5 раза больше по размеру в формате QOI чем в PNG, хотя много одноцветных пикселов, куда лучше условия?
Хотелось бы понять - всё же проблема формата или плагина для Paint.Net, кто-то пользовался не плагином для сравнения?
Hidden text
Эта статья:
Разработчик Доминик Саблевски (Dominic Szablewski) представил алгоритм QOI (Quite OK Image), который позволяет без потерь сжимать RGB и RGBA изображения до размера файла, аналогичного для формата PNG, но в 20-50 раз быстрее.
Статья Доминика:
to a similar size of PNG
С Github:
and 20% better compression
Собственно я об этом.
Compared to stb_image and stb_image_write QOI offers 20x-50x faster encoding, 3x-4x faster decoding and 20% better compression. It's also stupidly simple and fits in about 300 lines of C.
Не сравнение эффективных способов сохранения в png (например, ect), а сравнение с библиотекой stb_image_write для C для работы с изображениями.
Это как в анекдоте - мне не нужно бежать быстрее медведя, достаточно бежать быстрее тебя.
Вопрос не про скорость.
Понимаю, но "граммар-наци" живущий во мне клокочет и на такие темы, так как написано одно, а материал про другое.
На самом деле тут должно быть сравнение с BMP RLE, что напрямую бы соответствовало и скорости и используемому методу кодирования, вот там и сравнивать и скорости и степени сжатия. PNG тут абсолютно не в тему, ибо PNG, хоть и является O(n) алгоритмом, но он никогда не был скоростным из-за особенностей кодирования цвета. Например есть ПО Pingo и сравнительные тесты, и поиски лучшего сжатия - это можно сказать уже целое искусство.
Разработчик представил Quite OK Image, алгоритм сжатия без потерь со сложностью O(n)