- PVSM.RU - https://www.pvsm.ru -
Мало кто слышал имя Юрки Алакуйяла (@jyzg [3]), но все мы используем его разработки. Картинки JPEG частенько генерируются фантастическим JPEG-энкодером guetzli [4] с применением психовизуальных моделей, а HTTP-трафик в интернете жмётся кодеком brotli [5], тоже лучшим в своём классе.
Д-р Юрки Алакуйяла — активный член опенсорсного сообщества и исследователь. Работает техлидом Google Research Europe (Швейцария). Среди последних разработок — алгоритмы сжатия JPEG XL [6], WebP lossless [7] и др.
До работы в Google он разрабатывал софт для нейрохирургии и планирования лучевой терапии [8] (1990–1995 гг.), а потом десять лет точил AI-движки мобильных настольных игр, включая Mephisto Chess Mobile Edition и Deep Pocket Chess. Это интересный пример универсального инженера с научным бэкграундом, который будет востребован всегда и везде. В итоге его пригласили в Google, а от таких предложений трудно отказаться.
Юрки Алакуйяла является (со-)автором нескольких известных форматов и алгоритмов сжатия, хеширования и ГПСЧ. Среди основных разработок:
Сжатие без потерь WebP — абсолютно независимый кодек, не связанный с оригинальным WebP, который базируется на VP8. Этот алгоритм использует самые передовые методы [10], в том числе специальные энтропийные коды для различных цветовых каналов, двумерную локальность обратных опорных расстояний и цветовой кэш недавно использованных цветов. Это вдобавок к базовым техникам типа кодирования по словарю, кодирования Хаффмана и преобразования цветовых индексов. В этом формате применяется рекурсия. Изображения меньшего разрешения со служебной и управляющей информацией (коды энтропии, пространственные предикторы, преобразование цветового пространства и таблица цветов) рекурсивно внедряются [11] внутрь основного изображения, то есть закодированы с применением той же управляющей информации, которая содержится внутри них.
По статистике Web Almanac 2021, треть всего сжатого контента в интернете обработано кодеком Brotli.
Guetzli оптимизирует глобальные таблицы квантования JPEG и значения коэффициентов DCT в каждом блоке JPEG с помощью оптимизатора с замкнутым контуром. В научной статье объясняется, что в процессе оптимизации в качестве источника обратной связи Guetzli использует специальную метрику перцептивного расстояния Butteraugli [16], за счёт которой достигается уменьшение объёма данных на 29–45% для данного перцептивного расстояния (по оценке Butteraugli) по сравнению с другими компрессорами.
Визуализация двух деталей в изображении, оригинал в левой колонке, Guetzli в средней, libjpeg в правой. В версии libjpeg больше кольцевых артефактов, чем у Guetzli
Слева пейзаж разложен на три YUV-плоскости в JPEG. Каждый квадрат 8×8 преобразуется в пространство DCT, а значения DCT квантуются. Кроме квантования, Guetzli агрессивно обнуляет малые значения
Синтаксис энкодера:
guetzli --quality 90 01.png 01.jpg
Правда, вычисления довольно медленные. Например, на компьютере Core i5-4460 3,2 ГГц тестовая картинка PNG [17] размером 1560×1032 кодировалась в JPEG [18] почти четыре минуты (3:56). Но зато по размеру/качеству сжатия Guetzli превосходит все остальные JPEG-кодировщики.
Образно говоря, если учёные обнаружили новые паттерны работы человеческого
Кроме того, важной целью является отсутствие роялти.
Новый кодек включает инструменты кодирования, позволяющие снизить затраты на передачу и хранение JPEG на 22%, при этом позволяя байт за байтом точно восстановить исходный JPEG. Кодек был разработан с учётом преимуществ многоядерности и SIMD, и даже декодирование у него осуществляется быстрее, чем у стандартного JPEG.
В дополнение к высокой пропускной способности алгоритм рассчитан на низкую стоимость финализации. Результат более чем в два раза быстрее, чем SipTreeHash.
Есть версия для SSE4.1 (80% скорости для больших входов и 95% для малых), реализация для VSX на POWER и портативная версия (10% скорости). Есть сторонняя реализация под ARM [22].
Согласно тестам, HighwayHash в 5,2 раза быстрее SipHash для входных блоков данных размером 1 КБ. Бенчмарки для малых блоков показаны ниже.
Список научных работ [23] любого исследователя показывает главные инновации, которые он привнёс в этот мир. По сути, это вклад человека в развитие опенсорса, науки и всего человечества. Будущие кирпичики цивилизации лягут поверх слоёв, которые укладываются нами прямо сейчас.
Юрки Алакуйяла указан соавтором восьми работ, в том числе ведущим автором четырёх:
Контрольные суммы и хеши вычисляются практически повсеместно — в файловых системах, архивах, бэкапах, стримах, различных криптосистемах и так далее. В отличие от реально сильных хешей, функция HighwayHash очень быстрая, поэтому её можно рекомендовать как более безопасную альтернативу слабым хешам во многих приложениях.
Некоторые существующие криптографически безопасные генераторы также отвечают этим критериям, но они слишком медленные, чтобы быть принятыми для общего использования. Как и ранее упомянутый хеш-алгоритм HighwayHash, опенсорсный ГСПЧ Randen может считаться сильным и одновременно превосходит «слабых» конкурентов по производительности (в данном случае имеются в виду Mersenne Twister, PCG, ChaCha8, ISAAC и Philox) благодаря аппаратному ускорению.
На самом деле Randen представляет собой видоизменённую версию недавно опубликованного надёжного генератора Reverie с новой перестановкой (Permute
на иллюстрации ниже), построенной на основе улучшенной обобщённой структуры Фейстеля с 16-ю ветвями: «Мы предоставляем новые границы активных s-боксов для 24-х раундов этой конструкции, что стало возможным благодаря алгоритму поиска, экономящему память», — сказано в научной работе.
Импульсная нейронная сеть с одним скрытым слоем, источник [28]
Временны́е характеристики нейронной активности необходимы биологическому
Сравнение Brotli с лучшими кодеками на четырёх текстовых базах (полные результаты [31]):
Указаны коэффициент сжатия (отношение размера архива к оригинальному размеру базы), скорости кодирования и декодирования
Как видим, для разработки алгоритмов сжатия в последнее время начали активно применять нейросети. Перейдя на работу в Google, д-р Юрки Алакуйяла в каком-то смысле возвращается к истокам, ведь его изначальная специализация — софт для нейрохирургии. И вот теперь оказалось, что компьютерный софт становится всё больше похож на биологический
Играй в наш скролл-шутер прямо в Telegram и получай призы! 🕹️🎁 [39]
Автор: Анатолий Ализар
Источник [40]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/382623
Ссылки в тексте:
[1] Image: https://habr.com/ru/company/ruvds/blog/713648/
[2] сжатие информации — главная концепция нашей жизни: https://habr.com/ru/company/ruvds/blog/712652/
[3] @jyzg: https://twitter.com/jyzg
[4] guetzli: https://github.com/google/guetzli
[5] brotli: https://github.com/google/brotli
[6] JPEG XL: https://en.wikipedia.org/wiki/JPEG_XL
[7] WebP lossless: https://developers.googleblog.com/2012/08/lossless-and-transparency-modes-in-webp.html
[8] софт для нейрохирургии и планирования лучевой терапии: https://scholar.google.com/citations?view_op=view_citation&hl=en&user=SnJNeR4AAAAJ&citation_for_view=SnJNeR4AAAAJ:u5HHmVD_uO8C
[9] тестам: https://www.ctrl.blog/entry/webp-flif-comparison.html
[10] самые передовые методы: https://developers.google.com/speed/webp/docs/webp_lossless_bitstream_specification
[11] рекурсивно внедряются: https://developers.google.com/speed/webp/docs/webp_lossless_bitstream_specification#1_introduction:~:text=recursively%20embedded
[12] Zopfli: https://github.com/google/zopfli
[13] в большинстве браузеров: https://textslashplain.com/2015/09/10/brotli/
[14] RFC 7932: https://www.rfc-editor.org/rfc/rfc7932
[15] «Оптимизация графики для веба: самое важное»: https://habr.com/ru/post/422531/
[16] Butteraugli: https://github.com/google/butteraugli
[17] PNG: https://habrastorage.org/webt/0i/cu/jn/0icujnbu_oy0gvkawhnplca_kog.png
[18] JPEG: https://habrastorage.org/webt/yf/cg/ac/yfcgacqns0qe5pa3ww1sjvmzzxo.jpeg
[19] мозга: http://www.braintools.ru
[20] CityHash: https://opensource.googleblog.com/2011/04/introducing-cityhash.html
[21] HighwayHash: https://github.com/google/highwayhash
[22] сторонняя реализация под ARM: https://github.com/minio/highwayhash
[23] Список научных работ: https://research.google/people/105344/
[24] «Быстрая хеш-функция с ключом/псевдослучайная функция с использованием SIMD-умножения и перестановки»: https://arxiv.org/abs/1612.06257
[25] «Guetzli: JPEG-кодировщик с перцептивным управлением»: https://arxiv.org/pdf/1703.04421.pdf
[26] «Randen — быстрый генератор случайных чисел, устойчивый к бэктрекингу, с использованием AES+Feistel+Reverie»: https://arxiv.org/abs/1810.02227
[27] «Временнóе кодирование в спайковых нейросетях с альфа-синаптической функцией»: https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e1f3758d022705b1c4a03fb5a7a3429cd2c6c396.pdf
[28] источник: https://commons.wikimedia.org/wiki/File:ASNN.png
[29] «Архитектура сжатия изображений следующего поколения JPEG XL и инструменты кодирования»: https://www.spiedigitallibrary.org/conference-proceedings-of-spie/11137/111370K/JPEG-XL-next-generation-image-compression-architecture-and-coding-tools/10.1117/12.2529237.full?SSO=1
[30] «Brotli. Компрессор данных общего назначения»: https://dl.acm.org/doi/10.1145/3231935
[31] полные результаты: https://pages.di.unipi.it/farruggia/dcb/
[32] «Тесты JPEG XL, стандарта сжатия изображений с потерями/без потерь»: https://research.google/pubs/pub50095/
[33] «Спайковые нейронные автоэнкодеры с временны́м кодированием»: https://research.google/pubs/pub51788/
[34] Джастин Танни: https://habr.com/ru/company/ruvds/blog/682150/
[35] Джей Фриман (saurik): https://habr.com/ru/company/ruvds/blog/688716/
[36] Михал Залевски: https://habr.com/ru/company/ruvds/blog/695386/
[37] Джон Кармак: https://habr.com/ru/company/ruvds/blog/701556/
[38] Марк Руссинович: https://habr.com/ru/company/ruvds/blog/710268/
[39] Играй в наш скролл-шутер прямо в Telegram и получай призы! 🕹️🎁: https://t.me/ruvds_community/170
[40] Источник: https://habr.com/ru/post/713648/?utm_source=habrahabr&utm_medium=rss&utm_campaign=713648
Нажмите здесь для печати.