Pull to refresh

Comments 30

Появится алгоритм сжатия видео для проекта «Пегий Дудочник» из «Кремниевой долины»

Ждём ИИ после такого :D

Главное, чтобы клавишу delete не зажали бутылкой текилы)

А почему с PNG-то сравнивали, а не со, скажем, lossless-режимом WebP, который даёт экономию места 15-30%?

А зачем сравнивать с форматом которому больше 10 лет и он до сих пор не всеми поддерживается?

Ну да, намного лучше, конечно, сравнивать с форматом, которому 25 лет. Ведь для алгоритмов сжатия изображений без потерь именно скорость, а не размер получившегося файла является главным критерием.

Кем, кстати, 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 значениями.

Мне кажется, значительного эффекта можно достичь, рассматривая для второй и последующей строк вместо значений самих пикселей разницу с предыдущей строкой.

… а еще можно градиенты искать, они же, в принципе, по четкой формуле генерируются. На каких-нибудь скриншотах это будет вполне эффективно работать, если вместо пикселей сохранять параметры генерации градиента.


Как я уже писал — можно разбить изображение на квадраты — и дополнительно сравнивать сами квадраты друг с другом. Если мы опять-таки возьмем скриншот, то окажется, что там значительная часть таких квадратов будет одинаковой (границы окон, рамки, кнопки, однотонные фоны и т.п.) — т.е. часть изображения можно будет кодировать отсылкой к предыдущим ранее закодированным квадратам


Но всё это уже явно не будет работать быстро и в один проход :)

Ну будет O(4n), главное чтобы предсказуемо и линейная сложность.

Хотя для скриншотов скорее всего есть уже оптимизированные алгоритмы которые специфику учитывают. Например видео для скриншотов получается гораздо качественнее и меньше если использовать специальный кодек, а не универсальный.
Собрал через MSVC… Кодирование работает, из полноцветной фотографии PNG размером 985KB получил qoi размером 679KB. А обратное декодирование… Не работает! (Couldn't load/decode filename.qoi).

Попробовал мелкую иконку 16x16 4bpp прогнал через кодер-декодер, результат тот же.

Архиватор, который сжимает файл до одного байта. Распаковщик на стадии разработки

Распаковщик в аттаче, ловите pkunzip.zip

Хм. У меня всё работает.

Компилятор:

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) 
Автор не удосужился даже использовать платформопериносимые uint8_t, uint32_t и так далее, так что очень может быть, что его int и ваш int — два разных по размеру типа данных.
Кстати, он даже для длин буферов использует 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, но промахнулся
Ну, это идея.
По умолчанию у меня собиралось в x64.
Скомпилил в x86 — ничего не изменилось. При компиляции ни ошибок, ни варнингов. Уровень оптимизации тоже не влияет.

Возможно, специфичные компилятору вещи. Постараюсь сегодня/завтра собрать с MSVC и посмотреть результат

У него на гите уже добавлены реализации для нескольких языков, надо 0xd34df00d попросить чтобы он вариант на хаскеле запил, так чтобы сишную версию порвал. Это будет успех.

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

Challenge accepted, поиграюсь на выходных.

Пока поигрался с декодером, репортинг ин:


  1. Бейзлайн сишной версии: 225 мс на тестовом файле при сборке бинаря gcc 11, 195-198 при сборке клангом 12. -O3, естественно, а вот -march=native почему-то делает только хуже. Тестовый файл — 5616 x 3744, фотография (что, вероятно, не очень релевантно для лосслесса, но зато это самый большой файл из имевшихся под рукой, и на нём легко видны даже мелкие вариации в производительности).
  2. Формат очень приятный. Писать декодер для jpeg'а я в своё время задолбался и забросил, а этот прям вот хорошо так.
  3. Написанная за 2-3 часа первая версия, без единого запуска профайлера и без серьёзного заморачивания производительностью (писал так, как писал бы по умолчанию подобные вещи) — 235 мс при сборке с кодогенератором LLVM (нативный ghc'шный на вычислительном коде обычно хуже). Явной мутабельности, чтобы в ST, даже оказалось меньше, чем я ожидал. Основное мясо в Pixel.hs и Decoder.hs. Довольно забавно в одном файле пердолиться в битики и одновременно обмазываться тайпклассами и GADTs. Ещё интересно, что замена почти всех unsafeRead/unsafeWrite (кроме unsafeWrite внутри updateRunning), на safe-версии с проверкой границ не влияет на производительность — это для меня неожиданно. С другой стороны, запись там последовательная, предиктору, наверное, проще выкинуть эти проверки, чем с относительно рандомной записью в updateRunning.
  4. Допиленная сегодня за час с утра версия, хранящая байтики пикселей последовательно в виде RGB (или RGBA), а не в трёх-четырёх массивах на R, G и B (и опциональный A), как изначально (вся разница). Я бы из разных соображений ожидал, что три массива будет эффективнее с точки зрения использования кеша и пропускной способности памяти, но почему-то один оказывается чуть быстрее. Вместе с другим мелким и незакомиченным изменением кода — 210-212 мс. Другое изменение — незакомиченное изменение индексации в ByteString, связанное со слайсами, про него я напишу потом подробнее.
  5. Допиленная ещё за два часа версия, где я выкинул Data.Vector (там аналогичная проблема со слайсами) и заменил его на Data.Array — 185-190 мс. Мог бы просто хранить пиксели подряд и предоставлять внешним пользователям API в виде тупого набора uint8_t Word8, но хаскелист во мне решил, что это недопустимо, поэтому основная сложность (и основная трата времени) там на то, чтобы к Data.Array прикрутить хранение структурированных пикселей в массиве из одних Word8'ов. Вообще, наверное, можно было бы ещё поиграться со Storable, которое подобную хрень должно делать за меня, но мне пока лень.

Надо ещё немного причесать (прикрутить там нормальные ошибки, что на производительность не повлияет, выкинуть либу store, которую я решил попробовать на этом проекте для парсинга заголовка и которая оказалась неудобной, и так далее), и можно выкатывать в продакшен на hackage. Пойду пока напишу более подробную статью в блог и сюда.

А можете описать процесс выкатки в hackage?

Это как раз просто: проверяем, что в package.yaml поля вроде категории и описания нормально заполнены, и делаем stack upload ..


И каким образом определяется, что на выделенном сервере Ryzen 7 3700X (взято из блога)?

Помню, какую машину арендовал. Ну и всегда можно посмотреть cat /proc/cpuinfo :]

Быстрое сжатие картинок без потерь - отлично, давно такое ищу.

Хотя надо отметить, что обогнать сжатие в png - невелика заслуга, там оно медленное by design, т.к. "фильтр" для строки (преобразование, улучшающее сжимаемость) выбирается методом перебора. В зависимости от степени сжатия может перебираться больше или меньше разных фильтров, поэтому на макс. сжатии png очень медленный, на минимальном, без фильтров, это фактически тот же zip.

Интересно было бы сравнить Quite OK Image с ImageZero - тоже никому не известный алгоритм. В статье на Хабре заявлено аж 35-кратное превосходство в скорости над png (хм, может быть, автор QOI переизобрёл ImageZero заново?). Когда я сравнивал ImageZero с png, ускорение получалось меньше, в 2-4 раза, но зато некоторые картинки сжимались в 1.5 раза лучше. Возможно, png тестировался не на максимальном сжатии, точно не помню.

В целом ImageZero явно лучше png (точнее, алгоритмов сжатия png), но спустя 9 лет по-прежнему никому не известен...

Only those users with full accounts are able to leave comments. Log in, please.