Сжатие данных с помощью изображений

1656660258 szhatie dannyh s pomoshhyu izobrazhenij

Дэн Рута

qlk-XzQ2siBYh7vMIcSdDqzm0xYr8PbW85er

Первоначальной мотивацией этого побочного проекта был поиск лучшего способа хранения и загрузки весов, обученных нейронной сетью на основе браузера, при разработке jsNet. Чтобы сохранить весы, как у JSON, мне пришлось бы выйти из содержимого, на консоли или на странице, и, как вы можете представить себе, это стало очень плохо, когда сети стали большими и появилось много данных.

Решение, которое я нашел, заключалось в том, чтобы закодировать данные как изображения, которые обрабатываются гораздо лучше, чем обычный текст JSON. Случайно алгоритм, который я использовал для этого, кажется, не только сработал достаточно хорошо, но конечный размер файла был столь же мал, как сжатие gzip, даже фактически превосходя его в большинстве случаев.

Так что я подумал отшлифовать и выпустить его как отдельную библиотеку для общего использования. Эта статья служит обзором алгоритма сжатия для тех, кому интересны такие вещи.

Алгоритм

Без лишних слов, краткий, высокоуровневый обзор преобразования массива в изображение выглядит следующим образом:

  • Числа преобразуются в базу 15, где несколько первых символов являются метаданными
  • Результаты объединены
  • Затем каждая пара шестнадцатеричных символов преобразуется в значение Uint8Clamped
  • Наконец это рисуется на холсте, затем либо возвращается (браузер), либо хранится в файл (nodejs)

Что касается преобразования изображения обратно в данные массива:

  • Изображение считывается либо из файла, Uint8ClampedArray, либо из элемента HTML img
  • Каждое значение в Uint8ClampedArray преобразуется в базу 16
  • После объединения в строку исходные данные разделяются по символу метаданных f.
  • Каждая шестнадцатеричная строка затем анализируется обратно в число

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

Мета-данные

Если бы числа были преобразованы по основанию 16 (от 0 до f), используемому на изображениях, не было бы способа различить отдельные значения после объединения. Поэтому они преобразуются в основание 15 (от 0 до e), а символ f используется как разделитель для разделения значений.

wClA7AqfH99FDleLbxUKjZY-UqsUeK0-beV3
Где длинный список данных разбивается
Utj9cQNBYBgGwdANSOlNF7LUH71YXaDDTEIR
Отдельные значения после разбиения

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

Положительный или отрицательный
Первый дополнительный нужный бит метаданных – это число положительное или отрицательное. Однако было бы пустой тратой использования всего символа только для двоичного значения, поэтому это объединяется с метаданными для того, сколько базовых 15 символов сохраняет левая часть числа (слева от десятичного знака).

См. Конфигурации раздел ниже, но по умолчанию один символ используется для кодирования обоих, например:

54ixPs6sNAmnYhV3pjE5Wjdas0vb-XODMCWY
0–7 для отрицательного, 8-е для положительного

Значения 7 или ниже представляют отрицательное число, в то время как остальные представляют положительное число.

Количество базовых 15 символов для левой стороны
Кроме того, каждое из значений представляет, сколько из 15 базовых символов используются для представления левой части десятичного знака.

Так, например, 3 представляет отрицательное число с 4 цифрами слева, например -1234.xyz. И a представляет положительное число с 3 цифрами слева, например 123.xyz.

Количество начальных десятичных нулей
Наконец, по умолчанию сохраняется количество начальных нулей в десятичном смысле. Снова см. Конфигурации раздел ниже, но по умолчанию используется 1 символ, разрешающий 15 десятичных нулей в начале, например 0,00000000000000001.

Итак, с конфигурациями по умолчанию значение 1430,01623 будет преобразовано в следующее:

bF9EjCkQnIKXqZruKDPrQvhWLKvnmvGgi1rj
Fa1655733

Ф«является разделителем,»a‘ представляет положительное значение с 3 символами (655), представляющими левую часть десятичного знака, ‘1’ представляет 1 начальный нуль, в 1430 году.01623, а остальные представляют фактическую стоимость. Первые 3 символа, ‘655′ превращаются из основы 15 в 1430, а остальные, ‘733′преобразуется в 1623. Результат объединяется с добавлением начального нуля.

Конфигурации

По умолчанию только один метасимвол используется для кодирования количества шестнадцатеричных символов, используемых для представления левой части десятичного знака (655 => 1430, в примере выше). Это устанавливает ограничение на максимальное шестнадцатеричное значение eeeeeee, равное 170859374 в десятичной системе. Хотя этого должно быть достаточно для большинства случаев, все равно можно представить больше, просто используя 2 символа.

MYbd-8ua090Q5OlZjXKQVvmGl1cdvnkm0iT6
F791655733

В этом сценарии положительные числа сохраняются как любые значения выше 112, а отрицательные числа как любые значения ниже. This means there’s a theoretical maximum of 113 hex characters that can represent the left side of the number, aka 7912473587054163204202262246064660222224606482062446620828868288862844044480028440444220620006824802826420808608284080640028606608644. Though, in practice, parseInt округление становится смешным после 15 символов, поэтому 9999999999999999 должно быть точкой остановки.

Но, чтобы сэкономить еще больше места, вместо этого эту конфигурацию можно установить на 0, чтобы полностью игнорировать эти метаданные, если вы точно знаете, что числа положительны и в пределах 0–1 (вы всегда можете нормализовать/отменить нормализацию с помощью включенных вспомогательных функций ). Поэтому, 0,123 будет превращено в:

wnFehZUkLF5t0GCP8nl8AAH9J6gksedk87wR
F083

где ‘83‘ является шестнадцатеричной преобразованием 123. Для левой части десятичного знака не сохраняется символ, поскольку считается, что число равно 0.

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

vlUY8NWqqzh3tvZctNemH4ES0TyztGvxs1v3
F83

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

Эталонные показатели

Двумя наиболее интересными форматами были PNG и WebP. Оба могут быть сохранены из холста, и оба могут использовать альфа-канал, то есть они достаточно легко взаимозаменяемы (по крайней мере, в версии браузера).

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

mqSrpZuSFulDN5oLnqvswKP3-4iuSvwDWoaq
Размер файла относительно сжатия gzip

Формат PNG выполняет свою работу, но WebP действительно превосходит gzip! Приблизительно… на 98,5% размера, согласно этим 3 тестам. Использование альфа-канала не помогло уменьшить размер файла, но уменьшило размер изображения в пикселях, поэтому оставили его как конфигурацию с возможностью переключения.

Следующий набор тестов касается конфигурации емкости. Для этого и следующего набора тестов я создал случайный массив чисел в диапазоне от 0 до 1 с 1 десятичным знаком, например: 0,1, 0,4, 0,7, 0,2, и так далее, чтобы убедиться, что данные действительны для любой конфигурации, и проверил варианты PNG и WebP по выводу браузера. Для теста было использовано 80 000 номеров.

po7ntrJWjRArrBcfhXwIaKA5QL7tmnvrqbMk
Размер файла относительно gzip

WebP довольно легко победил формат PNG и даже gzip, когда емкость была установлена ​​на 0, равнялась ей, когда установлена ​​на 1, и немного больше, когда установлена ​​на 2.

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

FBqgimg6gs2QlxIG4vvYXZHz5Mvjusg-zf--
Размер файла относительно gzip

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

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

iYRRcKnxwJKTaIuP5UL7Ct1p2nMNGeUSqM6G
ACJ074tWqKwlE8CBMr1UOBec17Ij10KeOVfn
NcMgYS70Crx6uG1hOOffuCWhTf0c5l4BMb-C

Файлы тестов можно найти в хранилище GitHub.

Так что дальше?

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

Другие вещи, которые следует добавить, могут быть автоматическими конфигурациями, чтобы автоматически определять все конфигурации, сначала циклически просматривая данные, чтобы увидеть, что на самом деле нужно.

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

Но пока, чтобы завершить, вот изображение весов для нейронной сети, обученной распознавать рукописные цифры (MNIST). Если предположить, что Medium не использует собственного сжатия, вы должны иметь возможность загрузить его с помощью jsNet в структуре 784–100–10 и иметь обученную модель с изображения PNG!

MKYC2YV27sfNsvyhAdCrTjDquaEYlQHn-nir
Конфигурация по умолчанию

Страница GitHub для этого здесь, а мой Twitter — @Dan_Ruta.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *