Спецификация для битового потока WebP без потерь

Юрки Алакуйяла, доктор философии, Google, Inc., 19 июня 2012 г.

Пункты, отмеченные как [ИЗМЕНЕНО], были изменены 16 сентября 2014 г.

Пункты, отмеченные как [AMENDED2], были изменены 13 мая 2022 г.

Абстрактный

WebP без потерь — это формат изображения для сжатия изображений ARGB без потерь. Формат без потерь точно сохраняет и восстанавливает значения пикселей, включая значения цвета для пикселей с нулевым альфа-каналом. Формат использует изображения с низким разрешением, рекурсивно встроенные в сам формат, для хранения статистических данных об изображениях, таких как используемые энтропийные коды, пространственные предикторы, преобразование цветового пространства и таблица цветов. LZ77, префиксное кодирование и цветовой кэш используются для сжатия больших объемов данных. Были продемонстрированы более высокие скорости декодирования, чем PNG, а также сжатие на 25% более плотное, чем может быть достигнуто при использовании современного формата PNG.

1. Введение

В этом документе описывается представление сжатых данных изображения без потерь WebP. Он предназначен в качестве подробного справочника по реализации кодировщика и декодера WebP без потерь.

В этом документе мы широко используем синтаксис языка программирования C для описания потока битов и предполагаем существование функции для чтения битов ReadBits(n) . Байты считываются в естественном порядке содержащего их потока, а биты каждого байта считываются в порядке младших значащих битов. Когда несколько битов считываются одновременно, целое число создается из исходных данных в исходном порядке. Старшие биты возвращаемого целого числа также являются старшими битами исходных данных. Таким образом, утверждение

b = ReadBits(2);

эквивалентно двум приведенным ниже утверждениям:

b = ReadBits(1);
b |= ReadBits(1) << 1;

Мы предполагаем, что каждый компонент цвета (например, альфа, красный, синий и зеленый) представлен с использованием 8-битного байта. Мы определяем соответствующий тип как uint8. Весь пиксель ARGB представлен типом uint32, целым числом без знака, состоящим из 32 бит. В коде, показывающем поведение преобразований, альфа-значение закодировано в битах 31..24, красное в битах 23..16, зеленое в битах 15..8 и синее в битах 7..0, но реализации формата могут свободно использовать другое представление внутри.

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

2 Номенклатура

АРГБ
Значение пикселя, состоящее из значений альфа, красного, зеленого и синего.
ARGB-изображение
Двумерный массив, содержащий пиксели ARGB.
цветовой кеш
Небольшой массив с хеш-адресами для хранения недавно использованных цветов, чтобы иметь возможность вызывать их с более короткими кодами.
изображение индексации цвета
Одномерное изображение цветов, которое можно индексировать с помощью небольшого целого числа (до 256 в WebP без потерь).
изображение преобразования цвета
Двумерное изображение субразрешения, содержащее данные о корреляциях компонентов цвета.
отображение расстояния
Изменяет расстояния LZ77, чтобы они имели наименьшие значения для пикселей в 2D-близости.
энтропийное изображение
Двумерное изображение с субразрешением, указывающее, какое энтропийное кодирование следует использовать в соответствующем квадрате изображения, т. е. каждый пиксель является кодом метапрефикса.
префиксный код
Классический способ энтропийного кодирования, при котором для более частых кодов используется меньшее количество битов.
ЛЗ77
Алгоритм сжатия скользящего окна на основе словаря, который либо выдает символы, либо описывает их как последовательности прошлых символов.
код метапрефикса
Небольшое целое число (до 16 бит), которое индексирует элемент в таблице метапрефиксов.
изображение-предиктор
Двумерное изображение с низким разрешением, указывающее, какой пространственный предсказатель используется для определенного квадрата изображения.
префиксное кодирование
Способ энтропийного кодирования больших целых чисел, при котором несколько битов целого числа кодируются с помощью энтропийного кода, а остальные биты кодируются необработанными. Это позволяет описаниям энтропийных кодов оставаться относительно небольшими, даже когда диапазон символов велик.
порядок строк сканирования
Порядок обработки пикселей слева направо, сверху вниз, начиная с левого верхнего пикселя и далее вправо. Как только строка завершена, продолжайте с левого столбца следующей строки.

3 Заголовок RIFF

В начале заголовка находится контейнер RIFF. Он состоит из следующих 21 байта:

  1. Струна "РИФФ"
  2. 32-битное значение длины блока с прямым порядком байтов, весь размер блока контролируется заголовком RIFF. Обычно это равно размеру полезной нагрузки (размер файла минус 8 байтов: 4 байта для идентификатора RIFF и 4 байта для хранения самого значения).
  3. Строка "WEBP" (имя контейнера RIFF).
  4. Строка «VP8L» (тег фрагмента для данных изображения, закодированных без потерь).
  5. 32-битное число байтов в потоке без потерь с прямым порядком байтов.
  6. Однобайтовая подпись 0x2f.

Первые 28 бит битового потока определяют ширину и высоту изображения. Ширина и высота декодируются как 14-битные целые числа следующим образом:

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

14-битная динамика размера изображения ограничивает максимальный размер изображения WebP без потерь до 16384✕16384 пикселей.

Бит alpha_is_used является только подсказкой и не должен влиять на декодирование. Он должен быть установлен на 0, когда все альфа-значения в изображении равны 255, и на 1 в противном случае.

int alpha_is_used = ReadBits(1);

Номер версии — это 3-битный код, который должен быть равен 0. Любое другое значение должно рассматриваться как ошибка. [ИСПРАВЛЕНО]

int version_number = ReadBits(3);

4 трансформации

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

Изображение может пройти через четыре типа преобразования. 1 бит указывает на наличие преобразования. Каждое преобразование разрешено использовать только один раз. Преобразования используются только для изображения ARGB основного уровня: изображения с субразрешением не имеют преобразований, даже нулевого бита, указывающего на окончание преобразований.

Обычно кодер использует эти преобразования для уменьшения энтропии Шеннона в остаточном изображении. Кроме того, данные преобразования могут быть определены на основе минимизации энтропии.

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 4).

Если присутствует преобразование, то следующие два бита определяют тип преобразования. Существует четыре типа преобразований.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN                  = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

За типом преобразования следуют данные преобразования. Данные преобразования содержат информацию, необходимую для применения обратного преобразования, и зависят от типа преобразования. Далее мы опишем данные преобразования для разных типов.

4.1 Преобразование предиктора

Преобразование предиктора можно использовать для уменьшения энтропии, используя тот факт, что соседние пиксели часто коррелируют. При преобразовании предиктора текущее значение пикселя предсказывается из уже декодированных пикселей (в порядке строк развертки), и кодируется только остаточное значение (фактическое — предсказанное). Режим предсказания определяет тип используемого предсказания. Мы делим изображение на квадраты, и все пиксели в квадрате используют один и тот же режим предсказания.

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

int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) ((num) + (den) - 1) / (den))
int block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);

Данные преобразования содержат режим предсказания для каждого блока изображения. Все block_width * block_height блока используют один и тот же режим предсказания. Режимы прогнозирования обрабатываются как пиксели изображения и кодируются с использованием тех же методов, которые описаны в главе 5 .

Для пикселя x, y можно вычислить соответствующий адрес блока фильтра следующим образом:

int block_index = (y >> size_bits) * block_xsize +
                  (x >> size_bits);

Существует 14 различных режимов предсказания. В каждом режиме прогнозирования текущее значение пикселя прогнозируется на основе одного или нескольких соседних пикселей, значения которых уже известны.

Мы выбираем соседние пиксели (TL, T, TR и L) текущего пикселя (P) следующим образом:

O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    TL   T    TR   O    O    O    O
O    O    O    O    L    P    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X

где TL означает верхний левый, T верхний, TR верхний правый, L левый пиксель. Во время прогнозирования значения P все пиксели O, TL, T, TR и L уже обработаны, а пиксель P и все пиксели X неизвестны.

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

Режим Прогнозируемое значение каждого канала текущего пикселя
0 0xff000000 (представляет сплошной черный цвет в ARGB)
1 л
2 Т
3 ТР
4 TL
5 Среднее2(Среднее2(L, TR), T)
6 Среднее2(L, TL)
7 Среднее2(L, T)
8 Среднее2(TL, T)
9 Среднее2(Т, ТР)
10 Среднее2(Среднее2(L, TL), Среднее2(T, TR))
11 Выбрать(L, T, TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Average2(L, T), TL)

Average2 определяется следующим образом для каждого компонента ARGB:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

Предиктор Select определяется следующим образом:

uint32 Select(uint32 L, uint32 T, uint32 TL) {
  // L = left pixel, T = top pixel, TL = top left pixel.

  // ARGB component estimates for prediction.
  int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
  int pRed = RED(L) + RED(T) - RED(TL);
  int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
  int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);

  // Manhattan distances to estimates for left and top pixels.
  int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
           abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
  int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
           abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));

  // Return either left or top, the one closer to the prediction.
  if (pL < pT) {     // \[AMENDED\]
    return L;
  } else {
    return T;
  }
}

Функции ClampAddSubtractFull и ClampAddSubtractHalf выполняются для каждого компонента ARGB следующим образом:

// Clamp the input value between 0 and 255.
int Clamp(int a) {
  return (a < 0) ? 0 : (a > 255) ?  255 : a;
}
int ClampAddSubtractFull(int a, int b, int c) {
  return Clamp(a + b - c);
}
int ClampAddSubtractHalf(int a, int b) {
  return Clamp(a + (a - b) / 2);
}

Для некоторых граничных пикселей существуют специальные правила обработки. Если есть прогнозирующее преобразование, независимо от режима [0..13] для этих пикселей, прогнозируемое значение для самого верхнего левого пикселя изображения равно 0xff000000, L-пиксель для всех пикселей в верхней строке и T- пиксель для всех пикселей в крайнем левом столбце.

[AMENDED2] Адресация TR-пикселя для пикселей в крайнем правом столбце является исключением. Пиксели в самом правом столбце предсказываются с использованием режимов [0..13], точно так же, как пиксели не на границе, но вместо этого в качестве TR-пикселя используется самый левый пиксель в той же строке, что и текущий пиксель.

4.2 Преобразование цвета

[ИЗМЕНЕНО2]

Целью преобразования цвета является декорреляция значений R, G и B каждого пикселя. Преобразование цвета сохраняет значение зеленого (G) как есть, преобразует красный (R) на основе зеленого и преобразует синий (B) на основе зеленого, а затем на основе красного.

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

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

Фактическое преобразование цвета выполняется путем определения дельты преобразования цвета. Дельта преобразования цвета зависит от ColorTransformElement , который одинаков для всех пикселей в конкретном блоке. Дельта вычитается во время преобразования цвета. Затем обратное преобразование цвета просто добавляет эти дельты.

Функция преобразования цвета определяется следующим образом:

void ColorTransform(uint8 red, uint8 blue, uint8 green,
                    ColorTransformElement *trans,
                    uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the transform is just subtracting the transform deltas
  tmp_red  -= ColorTransformDelta(trans->green_to_red_,  green);
  tmp_blue -= ColorTransformDelta(trans->green_to_blue_, green);
  tmp_blue -= ColorTransformDelta(trans->red_to_blue_, red);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

ColorTransformDelta вычисляется с использованием 8-битного целого числа со знаком, представляющего число с фиксированной точкой 3,5, и 8-битного цветового канала RGB со знаком (c) [-128..127] и определяется следующим образом:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

Перед вызовом ColorTransformDelta() . Это должно быть выполнено с использованием 8-битного дополнения до двух (то есть: диапазон uint8 [128-255] отображается в диапазон [-128, -1] его преобразованного значения int8).

Умножение должно выполняться с большей точностью (как минимум с 16-битной динамикой). Свойство расширения знака операции сдвига здесь не имеет значения: из результата используются только младшие 8 бит, и там сдвиг расширения знака и сдвиг без знака согласуются друг с другом.

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

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

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

Во время декодирования экземпляры блоков ColorTransformElement декодируются, и обратное преобразование цвета применяется к значениям ARGB пикселей. Как упоминалось ранее, это обратное преобразование цвета просто вычитает значения ColorTransformElement из красного и синего каналов.

void InverseTransform(uint8 red, uint8 green, uint8 blue,
                      ColorTransformElement *trans,
                      uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying inverse transform is just adding the
  // color transform deltas
  tmp_red  += ColorTransformDelta(trans->green_to_red, green);
  tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue +=
      ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

4.3 Вычитание зеленого преобразования

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

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

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

4.4 Преобразование индексации цвета

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

Преобразование индексации цвета проверяет количество уникальных значений ARGB в изображении. Если это число ниже порогового значения (256), он создает массив этих значений ARGB, который затем используется для замены значений пикселей соответствующим индексом: зеленый канал пикселей заменяется индексом; все альфа-значения установлены на 255; все значения красного и синего в 0.

Данные преобразования содержат размер таблицы цветов и записи в таблице цветов. Декодер считывает данные преобразования индексации цвета следующим образом:

// 8 bit value for color table size
int color_table_size = ReadBits(8) + 1;

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

Обратное преобразование для изображения просто заменяет значения пикселей (которые являются индексами таблицы цветов) фактическими значениями таблицы цветов. Индексация выполняется на основе зеленого компонента цвета ARGB.

// Inverse transform
argb = color_table[GREEN(argb)];

Если индекс равен или больше, чем color_table_size, значение цвета argb должно быть установлено на 0x00000000 (прозрачный черный). [ИСПРАВЛЕНО]

Когда таблица цветов мала (равна или меньше 16 цветов), несколько пикселей объединяются в один пиксель. Объединение пикселей упаковывает несколько (2, 4 или 8) пикселей в один пиксель, соответственно уменьшая ширину изображения. Объединение пикселей обеспечивает более эффективное энтропийное кодирование совместного распределения соседних пикселей и дает некоторые преимущества, подобные арифметическому кодированию, для энтропийного кода, но его можно использовать только при наличии небольшого количества уникальных значений.

color_table_size указывает, сколько пикселей объединяется вместе:

int width_bits;
if (color_table_size <= 2) {
  width_bits = 3;
} else if (color_table_size <= 4) {
  width_bits = 2;
} else if (color_table_size <= 16) {
  width_bits = 1;
} else {
  width_bits = 0;
}

width_bits имеет значение 0, 1, 2 или 3. Значение 0 указывает, что объединение пикселей для изображения не требуется. Значение 1 указывает, что два пикселя объединены вместе, и каждый пиксель имеет диапазон [0..15]. Значение 2 указывает, что четыре пикселя объединены вместе, и каждый пиксель имеет диапазон [0..3]. Значение 3 указывает, что восемь пикселей объединены вместе, и каждый пиксель имеет диапазон [0..1], т. е. двоичное значение.

Значения упакованы в зеленый компонент следующим образом:

  • width_bits = 1: для каждого значения x, где x ≡ 0 (mod 2), значение зеленого в x помещается в 4 младших бита значения зеленого в x/2, значение зеленого в x + 1 помещается в 4 старших бита зеленого значения x/2.
  • width_bits = 2: для каждого значения x, где x ≡ 0 (mod 4), значение зеленого в x помещается в 2 младших бита значения зеленого в x/4, значения зеленого в точках от x + 1 до x + 3 расположены в порядке старших битов зеленого значения x/4.
  • width_bits = 3: для каждого значения x, где x ≡ 0 (mod 8), зеленое значение в x помещается в младший бит зеленого значения в x / 8, зеленые значения в x + 1 до x + 7 равны позиционируется в порядке старших битов зеленого значения x/8.

5 Данные изображения

Данные изображения представляют собой массив значений пикселей в порядке строк сканирования.

5.1 Роли данных изображения

Мы используем данные изображения в пяти различных ролях:

  1. Изображение ARGB: сохраняет фактические пиксели изображения.
  2. Entropy image: хранит коды метапрефиксов . Красный и зеленый компоненты пикселя определяют код метапрефикса, используемый в конкретном блоке изображения ARGB.
  3. Predictor image: хранит метаданные для Predictor Transform . Зеленый компонент пикселя определяет, какой из 14 предикторов используется в конкретном блоке изображения ARGB.
  4. Цветное преобразование изображения. Он создается значениями ColorTransformElement (определенными в Color Transform ) для разных блоков изображения. Каждый ColorTransformElement 'cte' обрабатывается как пиксель, альфа-компонент которого равен 255 , красный компонент равен cte.red_to_blue , зеленый компонент равен cte.green_to_blue , а синий компонент равен cte.green_to_red .
  5. Изображение с индексацией цвета: массив размером color_table_size (до 256 значений ARGB), в котором хранятся метаданные для преобразования индексации цвета . Это сохраняется как изображение ширины color_table_size и высоты 1 .

5.2 Кодирование данных изображения

Кодирование данных изображения не зависит от его роли.

Изображение сначала делится на набор блоков фиксированного размера (обычно 16x16 блоков). Каждый из этих блоков моделируется с использованием собственных энтропийных кодов. Кроме того, несколько блоков могут иметь одни и те же коды энтропии.

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

Каждый пиксель кодируется одним из трех возможных способов:

  1. литерал с префиксным кодированием: каждый канал (зеленый, красный, синий и альфа) кодируется энтропийно независимо;
  2. Обратная ссылка LZ77: последовательность пикселей копируется из другого места изображения; или же
  3. Код цветового кеша: использование короткого мультипликативного хеш-кода (индекс цветового кеша) недавно увиденного цвета.

В следующих подразделах подробно описывается каждый из них.

5.2.1 Литералы с префиксным кодированием

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

5.2.2 Обратная ссылка LZ77

Обратные ссылки представляют собой кортежи кода длины и расстояния:

  • Длина указывает, сколько пикселей в порядке строк сканирования должно быть скопировано.
  • Код расстояния — это число, указывающее положение ранее увиденного пикселя, из которого пиксели должны быть скопированы. Точное отображение описано ниже .

Значения длины и расстояния сохраняются с использованием префиксного кодирования LZ77 .

Кодирование префикса LZ77 делит большие целые значения на две части: код префикса и дополнительные биты : код префикса хранится с использованием энтропийного кода, а дополнительные биты хранятся как есть (без энтропийного кода).

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

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

Диапазон значений Код префикса Дополнительные биты
1 0 0
2 1 0
3 2 0
4 3 0
5..6 4 1
7..8 5 1
9..12 6 2
13..16 7 2
... ... ...
3072..4096 23 10
... ... ...
524289..786432 38 18
786433..1048576 39 18

Псевдокод для получения значения (длины или расстояния) из кода префикса выглядит следующим образом:

if (prefix_code < 4) {
  return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;

Отображение расстояний:

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

Коды расстояния больше 120 обозначают расстояние в пикселях в порядке строк развертки со смещением на 120.

Коды наименьшего расстояния [1..120] являются специальными и зарезервированы для непосредственной близости от текущего пикселя. Эта окрестность состоит из 120 пикселей:

  • Пиксели, находящиеся на 1–7 строк выше текущего пикселя и на 8 столбцов левее или до 7 столбцов справа от текущего пикселя. [Всего таких пикселей = 7 * (8 + 1 + 7) = 112 ].
  • Пиксели, находящиеся в той же строке, что и текущий пиксель, и до 8 столбцов слева от текущего пикселя. [ 8 таких пикселей].

Сопоставление между кодом расстояния i и смещением соседнего пикселя (xi, yi) выглядит следующим образом:

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),  (-1, 2),
(2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),  (1, 3),  (-1, 3),
(3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),  (-3, 2), (0, 4),  (4, 0),
(1, 4),  (-1, 4), (4, 1),  (-4, 1), (3, 3),  (-3, 3), (2, 4),  (-2, 4),
(4, 2),  (-4, 2), (0, 5),  (3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),
(1, 5),  (-1, 5), (5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2),
(4, 4),  (-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),  (-6, 2),
(4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6), (6, 3),  (-6, 3),
(0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),  (-5, 5), (7, 1),  (-7, 1),
(4, 6),  (-4, 6), (6, 4),  (-6, 4), (2, 7),  (-2, 7), (7, 2),  (-7, 2),
(3, 7),  (-3, 7), (7, 3),  (-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5),
(8, 0),  (4, 7),  (-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),
(-6, 6), (8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),  (8, 7)

Например, код расстояния 1 указывает смещение (0, 1) для соседнего пикселя, то есть пикселя над текущим пикселем (разница в 0 пикселей в направлении X и разница в 1 пиксель в направлении Y). Точно так же код расстояния 3 указывает на левый верхний пиксель.

Декодер может преобразовать код расстояния i в расстояние dist порядка строки сканирования следующим образом:

(xi, yi) = distance_map[i]
dist = x + y * xsize
if (dist < 1) {
  dist = 1
}

где xsize distance_map ширина изображения в пикселях.

5.2.3 Кодирование цветового кэша

В кэше цветов хранится набор цветов, которые недавно использовались в изображении.

Обоснование: Таким образом, к недавно использованным цветам иногда можно обратиться более эффективно, чем к их испусканию с использованием двух других методов (описанных в 5.2.1 и 5.2.2 ).

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

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits определяет размер color_cache с помощью (1 << color_cache_code_bits ). Диапазон допустимых значений для color_cache_code_bits — [1..11]. Совместимые декодеры должны указывать поврежденный битовый поток для других значений.

Кэш цветов — это массив размером color_cache_size . Каждая запись хранит один цвет ARGB. Цвета ищутся путем индексации их (0x1e35a7bd * color ) >> (32 - color_cache_code_bits ). В цветовом кеше выполняется только один поиск; нет разрешения конфликта.

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

6 Энтропийный код

6.1 Обзор

Большая часть данных кодируется с использованием канонического кода префикса . Следовательно, коды передаются путем отправки длины кода префикса , в отличие от фактических кодов префикса .

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

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

6.2 Детали

Закодированные данные изображения состоят из нескольких частей:

  1. Расшифровка и построение префиксных кодов [ИЗМЕНЕНО2]
  2. Коды мета-префиксов
  3. Энтропийно-кодированные данные изображения

6.2.1 Декодирование и построение кодов префиксов

Есть несколько шагов в расшифровке префиксных кодов.

Расшифровка длины кода:

В этом разделе описывается, как считывать длину кода префикса из потока битов.

Длина кода префикса может быть закодирована двумя способами. Используемый метод определяется 1-битным значением.

  • Если этот бит равен 1, это код длины простого кода , и
  • Если этот бит равен 0, это код нормальной длины кода .

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

(i) Простой код длины кода:

[ИЗМЕНЕНО2]

Этот вариант используется в особом случае, когда только 1 или 2 символа префикса находятся в диапазоне [0..255] с длиной кода 1 . Все остальные длины кода префикса неявно равны нулю.

Первый бит указывает количество символов:

int num_symbols = ReadBits(1) + 1;

Ниже приведены значения символов. Этот первый символ кодируется с использованием 1 или 8 бит в зависимости от значения is_first_8bits . Диапазон составляет [0..1] или [0..255] соответственно. Предполагается, что второй символ, если он присутствует, всегда находится в диапазоне [0..255] и кодируется с использованием 8 битов.

int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
  symbol1 = ReadBits(8);
  code_lengths[symbol1] = 1;
}

Примечание. Другой особый случай — это когда все длины кода префикса равны нулю (пустой код префикса). Например, код префикса для расстояния может быть пустым, если нет обратных ссылок. Точно так же префиксные коды для альфа, красного и синего могут быть пустыми, если все пиксели в пределах одного и того же метапрефиксного кода создаются с использованием цветового кеша. Однако этот случай не требует специальной обработки, так как пустые префиксные коды могут быть закодированы как коды, содержащие один символ 0 .

(ii) Код нормальной длины кода:

Длина кода префикса укладывается в 8 бит и читается следующим образом. Во-первых, num_code_lengths указывает количество длин кода.

int num_code_lengths = 4 + ReadBits(4);

Если num_code_lengths > 18, битовый поток недействителен.

Длины кодов сами кодируются с использованием префиксных кодов: сначала должны быть прочитаны длины кодов нижнего уровня code_length_code_lengths . Остальные из этих code_length_code_lengths (в соответствии с порядком в kCodeLengthCodeOrder ) являются нулями.

int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 };  // All zeros
for (i = 0; i < num_code_lengths; ++i) {
  code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}

Далее, если ReadBits(1) == 0 , максимальное количество различных считываемых символов равно num_code_lengths . В противном случае он определяется как:

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

Затем из code_length_code_lengths строится таблица префиксов, которая используется для считывания длин кода до max_symbol .

  • Код [0..15] указывает длину буквенного кода.
    • Значение 0 означает, что символы не были закодированы.
    • Значения [1..15] указывают длину соответствующего кода в битах.
  • Код 16 повторяет предыдущее ненулевое значение [3..6] раз, т. е. 3 + ReadBits(2) раза. Если код 16 используется до того, как было передано ненулевое значение, повторяется значение 8.
  • Код 17 выдает серию нулей [3..10], т. е. 3 + ReadBits(3) раз.
  • Код 18 выдает серию нулей длиной [11..138], т. е. 11 + ReadBits(7) раз.

После считывания длин кодов префиксный код для каждого типа символа (A, R, G, B, расстояние) формируется с использованием их соответствующих размеров алфавита:

  • Канал G: 256 + 24 + color_cache_size
  • другие литералы (A,R,B): 256
  • код расстояния: 40

6.2.2 Декодирование кодов метапрефиксов

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

Коды мета-префикса можно использовать только тогда, когда изображение используется в роли изображения ARGB .

Есть две возможности для кодов префикса мета, обозначенных 1-битным значением:

  • Если этот бит равен нулю, везде в изображении используется только один код метапрефикса. Данные больше не сохраняются.
  • Если этот бит равен единице, изображение использует несколько кодов метапрефикса. Эти коды метапрефикса хранятся в виде энтропийного изображения (описано ниже).

Изображение энтропии:

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

Первые 3 бита содержат значение prefix_bits . Размеры энтропийного изображения получены из 'prefix_bits'.

int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);

где DIV_ROUND_UP определяется ранее .

Следующие биты содержат энтропийное изображение ширины prefix_xsize и высоты prefix_ysize .

Интерпретация кодов мета-префиксов:

Для любого заданного пикселя (x, y) существует набор из пяти связанных с ним префиксных кодов. Эти коды (в порядке битового потока):

  • код префикса № 1 : используется для зеленого канала, длины обратной ссылки и цветового кеша.
  • код префикса #2, #3 и #4 : используется для красного, синего и альфа-каналов соответственно.
  • код префикса #5 : используется для обозначения расстояния назад.

С этого момента мы будем называть этот набор кодовой группой префикса .

Количество групп кода префикса в изображении ARGB можно получить, найдя самый большой код префикса мета из изображения энтропии:

int num_prefix_groups = max(entropy image) + 1;

где max(entropy image) указывает наибольший код префикса, хранящийся в энтропийном изображении.

Поскольку каждая группа кодов префиксов содержит пять кодов префиксов, общее количество кодов префиксов составляет:

int num_prefix_codes = 5 * num_prefix_groups;

Учитывая пиксель (x, y) в изображении ARGB, мы можем получить соответствующие коды префикса, которые будут использоваться следующим образом:

int position =
    (y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[pos] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

где мы предположили существование структуры PrefixCodeGroup , которая представляет собой набор из пяти префиксных кодов. Кроме того, prefix_code_groups — это массив PrefixCodeGroup (размером num_prefix_groups ).

Затем декодер использует группу кода префикса prefix_group для декодирования пикселя (x, y), как описано в следующем разделе .

6.2.3 Декодирование энтропийно-кодированных данных изображения

[ИЗМЕНЕНО2]

Для текущей позиции (x, y) в изображении декодер сначала идентифицирует соответствующую группу кода префикса (как объяснялось в последнем разделе). Учитывая кодовую группу префикса, пиксель считывается и декодируется следующим образом:

Считайте следующий символ S из битового потока, используя код префикса #1. Обратите внимание, что S — это любое целое число в диапазоне от 0 до (256 + 24 + color_cache_size - 1) .

Интерпретация S зависит от его значения:

  1. если S < 256
    1. Используйте S в качестве зеленого компонента.
    2. Считайте красный цвет из битового потока, используя код префикса #2.
    3. Считайте синий цвет из битового потока, используя код префикса #3.
    4. Прочитайте альфа-канал из битового потока, используя код префикса #4.
  2. если S >= 256 && S < 256 + 24
    1. Используйте S-256 в качестве кода префикса длины.
    2. Чтение дополнительных битов длины из битового потока.
    3. Определите длину обратной ссылки L по коду префикса длины и считанным дополнительным битам.
    4. Считайте код префикса расстояния из битового потока, используя код префикса #5.
    5. Чтение дополнительных битов для расстояния от битового потока.
    6. Определите расстояние D обратной ссылки по коду префикса расстояния и считанным дополнительным битам.
    7. Скопируйте L пикселей (в порядке строк сканирования) из последовательности пикселей до них на D пикселей.
  3. если S >= 256 + 24
    1. Используйте S - (256 + 24) в качестве индекса в кэше цветов.
    2. Получите цвет ARGB из кеша цветов по этому индексу.

7 Общая структура формата

Ниже представлен вид на формат в форме Бэкуса-Наура. Он не охватывает все детали. Конец изображения (EOI) только неявно закодирован количеством пикселей (xsize * ysize).

7.1 Базовая структура

<format> ::= <RIFF header><image size><image stream>
<image stream> ::= <optional-transform><spatially-coded image>

7.2 Структура преобразований

<optional-transform> ::=
    (1-bit value 1; <transform> <optional-transform>) | 1-bit value 0
<transform> ::= <predictor-tx> | <color-tx> | <subtract-green-tx> |
                <color-indexing-tx>
<predictor-tx> ::= 2-bit value 0; <predictor image>
<predictor image> ::= 3-bit sub-pixel code ; <entropy-coded image>
<color-tx> ::= 2-bit value 1; <color image>
<color image> ::= 3-bit sub-pixel code ; <entropy-coded image>
<subtract-green-tx> ::= 2-bit value 2
<color-indexing-tx> ::= 2-bit value 3; <color-indexing image>
<color-indexing image> ::= 8-bit color count; <entropy-coded image>

7.3 Структура данных изображения

[ИЗМЕНЕНО2]

<spatially-coded image> ::= <color cache info><meta prefix><data>
<entropy-coded image> ::= <color cache info><data>
<color cache info> ::=
    1 bit value 0 | (1-bit value 1; 4-bit value for color cache size)
<meta prefix> ::= 1-bit value 0 |
                  (1-bit value 1; <entropy image>)
<data> ::= <prefix codes><lz77-coded image>
<entropy image> ::= 3-bit subsample value; <entropy-coded image>
<prefix codes> ::= <prefix code group> |
                   <prefix code group><prefix codes>
<prefix code group> ::= <prefix code><prefix code><prefix code>
                        <prefix code><prefix code>
                        See "Interpretation of Meta Prefix Codes" to
                        understand what each of these five prefix
                        codes are for.
<prefix code> ::= <simple prefix code> | <normal prefix code>
<simple prefix code> ::= see "Simple code length code" for details
<normal prefix code> ::= <code length code>; encoded code lengths
<code length code> ::= see section "Normal code length code"
<lz77-coded image> ::= ((<argb-pixel> | <lz77-copy> |
                         <color-cache-code>) <lz77-coded image>) | ""

Возможный пример последовательности:

<RIFF header><image size>1-bit value 1<subtract-green-tx>
1-bit value 1<predictor-tx>1-bit value 0<color cache info>
1-bit value 0<prefix codes><lz77-coded image>