Наскоро се спряхме на тезата, че компресията без загуби е

Наскоро се спряхме на тезата, че компресията без загуби е в действителност основната идея в нашия действителен живот. Нека в този момент да обърнем малко повече внимание на един доста ослепителен представител на точно тази промишленост. Той е човек, който вижда света през призмата на теорията на информацията, ентропията, хаоса и закономерностите.

Съвсем малко хора са чували за финландеца Юрки Алакуйяла (Jyrki Alakuijala), само че безусловно всички използваме неговите логаритми и гениални софтуерни разработки. Изображенията във формат JPEG постоянно се генерират от модерния енкодер JPEG guetzli благодарение на психовизуални модели, а HTTP трафикът в интернет се компресира от кодека brotli, който също е най-хубавият в своя клас.

Д-р Юрки Алакуяла е един от най-великите програмисти на нашия век, деен член на open source общността и неотклонен откривател, който обаче не обича доста много да се демонстрира пред камерите и фотоапаратите, а избира да работи върху най-съвременните логаритми за мощна компресия на данните със и без загуби. Той е софтуерен специалист в Гугъл Research Europe (Швейцария). Най-новите му разработки включват логаритмите за компресия JPEG XL, WebP lossless и други

Кариерата

Преди да се причисли към Гугъл, той създава програмен продукт за неврохирургията и планирането на лъчетерапията (1990-1995 г.), а по-късно в продължение на десетилетие усъвършенства енджините за изкуствен интелект на другите игри, в това число Mephisto Chess Mobile Edition и Deep Pocket Chess. Това е забавен образец за повсеместен специалист с научно обучение, който постоянно и на всички места ще бъде издирван. В последна сметка той е поканен в Гугъл, а такива оферти мъчно се отхвърлят.

Проектите

Юрки Алакуяла е създатели и съавтор на няколко добре познати формати и логаритми за компресия, хеширане и PRNG – генератори на псевдослучайни цифри със свойства, които го вършат подобаващ за потребление в криптографията. Основните му разработки включват:

WebP lossless (2012). Формат за компресия на изображения без загуби, който е тестван и признат като доста по-добър от PNG с кодека Zopfli и малко по-добър от FLIF.

Компресията без загуби WebP е изцяло самостоятелен кодек, който не е обвързван с истинския WebP, основан на VP8. Този логаритъм употребява най-съвременни техники, в това число специфични ентропийни кодове за другите цветови канали, двуизмерна локалност на противоположните референтни дистанции и цветови кеш на неотдавна употребяваните цветове. Това е в допълнение към главните техники като речниково шифроване, шифроване по Хъфман и превръщане на цветовия показател. В този формат се употребява рекурсия. Изображенията с по-ниска разграничителна дарба с обслужваща и контролна информация (ентропийни кодове, пространствени предсказатели, преобразувания на цветовото пространство и цветови таблици) се вграждат рекурсивно в главното изображение, което значи, че се кодира, като се употребява същата контролна информация, съдържаща се в тези базови изображения с ниска резолюция. Zopfli (2013 г.) е безвъзмездна библиотека за компресиране на данни, която кодира данните във форматите DEFLATE, gzip и zlib. Тя компресира данни с по-висока степен на компресия от другите имплементации на DEFLATE и zlib, само че архивирането ѝ лишава на порядък повече време. Поради тази причина нормално се употребява за единично статично компресиране, а не за компресиране в действително време. Разработена е взаимно с Lode Vandevenne, също чиновник на Гугъл. Първата обществена версия е показана през месец февруари 2013 г. Brotli (2013) е повсеместен компресор с отворен код с общо предопределение, въведен от Гугъл, който се употребява в множеството браузъри и уеб сървъри. Той е обществено наличен в GitHub, а през юли 2016 година форматът на данните е формализиран като RFC 7932. Самият логаритъм употребява композиция от актуалната версия на LZ77 логаритъма, Хъфманово шифроване и контекстно моделиране от 2-ри ред с много висок коефициент на компресия. По скорост той е сходен на deflate, само че обезпечава по-добра компресия.

Според статистиките на Web Almanac 2021 една трета от цялото компресирано наличие в интернет е обработено от кодека Brotli. Guetzli (2017 г.). Перцептивен JPEG енкодер, който се употребява най-вече за усъвършенстване изобразяването на графиките в интернет

Guetzli усъвършенства световните таблици за квантуване на JPEG и стойностите на DCT коефициентите във всеки JPEG блок, като употребява оптимизатор със затворен силует. В научния труд се изяснява, че в процеса на оптимизация като източник на противоположна връзка Guetzli употребява специфичната метрика за перцептивното разстояние на Butteraugli, с което се реализира 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 GHz, компресията на тестовото PNG изображение с резолюция 1560×1032 пиксела лишава съвсем четири минути (3:56), с цел да се кодира в JPEG. Но Guetzli превъзхожда всички други JPEG енкодери във връзка с размера на изходния файл и качеството на компресията.

Butteraugli (2017 г.) е гореспоменатата метрика за разбиране на дистанцията за Guetzli, т.е. основата, по която се прави оценка качеството на компресията. В последна сметка колкото по-ефективна е метриката, толкоз по-ефективен е резултатът

Образно казано, в случай че учените са разкрили нови шаблони на човешкия мозък (нови психовизуални модели, когнитивни изкривявания и т.н.), то тогава имаме опция да компресираме изображенията в по-малки файлове. Допълнителното познание значи по-добра компресия.

JPEG XL (2017 г.) е кодек от последващо потомство, насочен към огромно приложение в интернет, който дейно компресира висококачествени изображения и в последна сметка заменя съществуващия патентован JPEG формат. Осигурява разнообразни преимущества пред наличните формати за изображения: По-малък размер на файла при субективно еквивалентно качество Пълноценно потребление на паралелизма в актуалните процесори при компресирането и декомпресирането Прогресивна компресия, компресия без загуби, компресия на анимации, опция за декомпресия на изображенията компресирани със остарелия JPEG алгоритъм Поддръжка на изображения с доста високо качество и огромна подробност, които могат да бъдат с доста необятен динамичен диапазон, като компресирането не внася никакви образни промени

Освен това, значимо е, че няма лицензионни такси.

Новият кодек включва принадлежности за шифроване, които понижават разноските (системните ресурси) за транспорт и предпазване на JPEG с 22%, като в същото време разрешават възобновяване на истинския JPEG с акуратност байт по байт. Кодекът е планиран по подобен метод, че да се възползва от преимуществата на многоядрените процесори и SIMD и даже декодира по-бързо от общоприетия JPEG.

CityHash (2011 г.) е фамилия хеш функционалности на Гугъл. HighwayHash (2016 г.) е нов бърз логаритъм за хеширане, основан на инструкциите за умножение и пермутация на AVX2. набора  процесорни команди. Както се споделя в описанието, той просто осъществя нов метод за разбъркване на входните данни със SIMD инструкциите. Накратко, употребяват се необратими 32×32 -> 64-битови умножения, а пермутацията изравнява разпределението на получените байтове. Вътрешното положение на функционалността е много огромно (1024 бита), само че се побира в SIMD регистрите. Поради рестриктивните мерки на набора от AVX2 инструкциите, регистрите са разграничени на две 512-битови половини, които остават самостоятелни до етапа на редуцирането. Алгоритъмът извежда 64-битови извлечения или до 256 бита без спомагателни разноски.

В допълнение към високата пропускателна дарба, логаритъмът не изисква огромни систематични запаси. Резултатът е повече от два пъти по-бърза работа от SipTreeHash.

Съществува версия за SSE4.1 (80% скорост за огромни входни данни и 95% за дребни входни данни), реализация за VSX на POWER и портативна версия (10 процентна скорост). Съществува реализация на трета страна за ARM архитектурата.

Тестовете демонстрират, че HighwayHash логаритъмът е 5,2 пъти по-бърз от SipHash при входни данни, в които доминират блокове от по 1 KB. Бенчмарковете за работата с дребни блокове във входните данни са показани по-долу:

Randen е бърз генератор на псевдослучайни цифри със отбрана против назад следене от външен наблюдаващ, който се пробва да предскаже държанието на генератора

Научни работи

Те са толкоз доста, че ще се ограничим с по-важните.

„ Brotli. Алгоритъм за компресия на данни с общо предопределение “ (2019). В публикацията за научната общественост създателите разказват обширно формата, показват пробен разбор на главните алгоритмични блокове в актуалната реализация на кодера и вършат съпоставяне с другите логаритми за компресия от разнообразни фамилии, като повдигат редица нови въпроси, свързани с алгоритмичния и софтуерния инженеринг на дизайна, които заслужават в допълнение внимание от страна на научната общественост

По-долу е дадена сравнителната таблица от тази научна работа, където се прави съпоставяне на логаритъма Brotli с най-хубавите кодеци от това време (2019 г.). Използвани са четири огромни текстови бази:

В таблицата са указани коефициента на компресия (съотношението на изходния компресиран файл към входния), скоростта на компресия и декомпресия

„ Тестове на JPEG XL – стандарт за компресиране на изображения със загуби/без загуби “ (2020). Според субективните сравнителни проби JPEG XL дава 60% понижение на размера на файла спрямо JPEG при еквивалентно образно качество. За да се възпроизведат резултатите, оповестени в този документ, изходният код на JPEG XL бе отворен през 2019 г. „ Времево кодирани шиповидни невронни автоенкодери “ (2021). Шиповидният автоенкодер се показва сходно на стандартните автоенкодери и ги превъзхожда във връзка с успеваемостта на реорганизация на изображения с инвертирана бляскавост. Резултатите демонстрират капацитета на шиповидните автоенкодери като градивни детайли за по-сложни компютърни архитектури, основани на биологични правила. С други думи, бъдещето на графичната компресия е в по-усъвършенстваните невронни мрежи.

Както може да се види, в последно време невронните мрежи интензивно се употребяват за създаването на нови логаритми за компресиране. След като се причислява към Гугъл, доктор Юрки Алакуяла в прочут смисъл се връща към корените си, защото първичната му специализация е била в региона на софтуера за неврохирургията. А в този момент се оказва, че компютърният програмен продукт от ден на ден замязва на биологичния мозък, с неврони, синапси, учене, акомодация и психовизуални модели. От друга страна, от ден на ден компютърни технологии се употребяват и в медицината. При диагностицирането на заболявания (от снимки) се ползват сходни способи за обработка на изображенията, както при графичните кодеци.