Юрки Алакуйала, доктор философии, Google, Inc., 9 марта 2023 г.
Абстрактный
WebP lossless — это формат изображений для сжатия без потерь изображений 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-изображение
- Двумерный массив, содержащий пиксели ARGB.
- цветовой кэш
- Небольшой массив с хеш-адресами для хранения недавно использованных цветов, позволяющий вызывать их с помощью более коротких кодов.
- цветовое индексирование изображения
- Одномерное изображение цветов, которое можно индексировать с помощью небольшого целого числа (до 256 в формате WebP без потерь).
- цветовое преобразование изображения
- Двумерное изображение субминимального разрешения, содержащее данные о корреляциях цветовых компонентов.
- отображение расстояний
- Изменяет расстояния LZ77 таким образом, чтобы они имели наименьшие значения для пикселей, находящихся в двухмерной близости.
- энтропийное изображение
- Двумерное субразрешенное изображение, указывающее, какое энтропийное кодирование следует использовать в соответствующем квадрате изображения, то есть каждый пиксель представляет собой мета-префиксный код.
- ЛЗ77
- Алгоритм сжатия с использованием скользящего окна на основе словаря, который либо генерирует символы, либо описывает их как последовательности ранее сгенерированных символов.
- мета-префиксный код
- Небольшое целое число (до 16 бит), которое служит индексом элемента в таблице мета-префиксов.
- предсказательное изображение
- Двумерное изображение субминимального разрешения, указывающее, какой пространственный предиктор используется для конкретного квадрата на изображении.
- префиксный код
- Классический способ энтропийного кодирования, при котором для более часто встречающихся кодов используется меньшее количество битов.
- префиксное кодирование
- Способ энтропийного кодирования больших целых чисел, при котором несколько битов целого числа кодируются с помощью энтропийного кода, а оставшиеся биты кодируются в исходном виде. Это позволяет сохранять относительно небольшие описания энтропийных кодов даже при большом диапазоне символов.
- порядок строк сканирования
- Порядок обработки пикселей (слева направо и сверху вниз), начиная с верхнего левого пикселя. После завершения обработки строки, переходим к следующему пикселю с левого столбца.
3 RIFF Header
В начале заголовка находится контейнер RIFF. Он состоит из следующих 21 байта:
- Строка 'RIFF'.
- 32-битное значение длины блока в формате little-endian, которое представляет собой полный размер блока, управляемый заголовком RIFF. Обычно оно равно размеру полезной нагрузки (размер файла минус 8 байт: 4 байта для идентификатора 'RIFF' и 4 байта для хранения самого значения).
- Строка 'WEBP' (имя контейнера RIFF).
- Строка 'VP8L' (FourCC означает данные изображения, закодированные без потерь).
- 32-битное значение в формате little-endian, указывающее количество байтов в потоке без потерь.
- 1-байтовая сигнатура 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);
Номер версии (version_number) — это 3-битный код, который должен быть установлен в 0. Любое другое значение следует рассматривать как ошибку.
int version_number = ReadBits(3);
4 преобразования
Преобразования представляют собой обратимые манипуляции с данными изображения, которые могут уменьшить оставшуюся символическую энтропию за счет моделирования пространственных и цветовых корреляций. Они могут сделать итоговое сжатие более плотным.
Изображение может пройти четыре типа преобразований. Единица указывает на наличие преобразования. Каждое преобразование может быть использовано только один раз. Преобразования используются только для основного изображения ARGB; изображения более низкого разрешения (изображение с цветовым преобразованием, изображение энтропии и изображение-предиктор) не имеют преобразований, даже нулевой бит, указывающий на конец преобразований, отсутствует.
Как правило, кодировщик использует эти преобразования для уменьшения энтропии Шеннона в остаточном изображении. Кроме того, данные преобразования могут быть выбраны на основе минимизации энтропии.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
Если преобразование присутствует, то следующие два бита указывают тип преобразования. Существует четыре типа преобразований.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
За типом преобразования следуют данные преобразования. Данные преобразования содержат информацию, необходимую для применения обратного преобразования, и зависят от типа преобразования. Обратные преобразования применяются в обратном порядке по сравнению с порядком их считывания из битового потока, то есть, сначала последнее.
Далее мы опишем данные преобразования для различных типов.
4.1 Преобразование предиктора
Преобразование с предикторами позволяет уменьшить энтропию, используя тот факт, что соседние пиксели часто коррелированы. В преобразовании с предикторами текущее значение пикселя предсказывается на основе уже декодированных пикселей (в порядке строк развертки), и кодируется только остаточное значение (фактическое - предсказанное). Зеленая составляющая пикселя определяет, какой из 14 предикторов используется в конкретном блоке изображения ARGB. Режим предсказания определяет тип используемого предсказания. Мы делим изображение на квадраты, и все пиксели в квадрате используют один и тот же режим предсказания.
Первые 3 бита данных прогноза определяют ширину и высоту блока в битах.
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 transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);
Данные преобразования содержат режим предсказания для каждого блока изображения. Это изображение субразрешения, где зеленая составляющая пикселя определяет, какой из 14 предикторов используется для всех пикселей block_width * block_height в пределах конкретного блока изображения ARGB. Это изображение субразрешения кодируется с использованием тех же методов, описанных в главе 5 .
Количество столбцов блока, transform_width , используется в двумерной индексации. Для пикселя (x, y) адрес соответствующего блока фильтра можно вычислить следующим образом:
int block_index = (y >> size_bits) * transform_width +
(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 | Average2(Average2(L, TR), T) |
| 6 | Average2(L, TL) |
| 7 | Среднее значение2(L, T) |
| 8 | Average2(TL, T) |
| 9 | Average2(T, TR) |
| 10 | Average2(Average2(L, TL), Average2(T, TR)) |
| 11 | Выберите (L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Для каждого компонента ARGB Average2 определяется следующим образом:
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) {
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-пикселями.
Обращение к TR-пикселю для пикселей в крайнем правом столбце является исключением. Пиксели в крайнем правом столбце предсказываются с использованием мод [0..13], как и пиксели, не находящиеся на границе, но в качестве TR-пикселя используется крайний левый пиксель в той же строке, что и текущий пиксель.
Итоговое значение пикселя получается путем сложения каждого канала прогнозируемого значения с закодированным остаточным значением.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.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) в 8-битное знаковое (int8). Знаковое значение следует интерпретировать как 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 'cte' рассматривается как пиксель в субразрешенном изображении, альфа-компонент которого равен 255 , красный компонент — cte.red_to_blue , зеленый компонент — cte.green_to_blue , а синий компонент — cte.green_to_red .
В процессе декодирования экземпляры 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 the 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 the color table size
int color_table_size = ReadBits(8) + 1;
Таблица цветов хранится с использованием самого формата хранения изображений. Таблицу цветов можно получить, прочитав изображение без заголовка RIFF, размера изображения и преобразований, предполагая высоту в 1 пиксель и ширину, равную color_table_size . Таблица цветов всегда кодируется методом вычитания для уменьшения энтропии изображения. Разница между цветами палитры обычно содержит гораздо меньше энтропии, чем сами цвета, что приводит к значительной экономии для изображений меньшего размера. При декодировании каждый конечный цвет в таблице цветов можно получить, сложив значения предыдущих цветовых компонентов по каждому компоненту ARGB отдельно и сохранив младшие 8 бит результата.
Обратное преобразование изображения заключается в простой замене значений пикселей (которые являются индексами цветовой таблицы) фактическими значениями из цветовой таблицы. Индексация выполняется на основе зеленой составляющей цвета ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
Если индекс равен или превышает color_table_size , значение цвета argb следует установить равным 0x00000000 (прозрачный черный).
Когда цветовая таблица невелика (равна или меньше 16 цветов), несколько пикселей объединяются в один пиксель. Объединение пикселей позволяет упаковать несколько (2, 4 или 8) пикселей в один пиксель, соответственно уменьшая ширину изображения. Объединение пикселей обеспечивает более эффективное совместное распределение энтропийного кодирования соседних пикселей и дает некоторые преимущества, аналогичные арифметическому кодированию, для энтропийного кода, но его можно использовать только при наличии 16 или менее уникальных значений.
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.
После считывания этого преобразования image_width уменьшается на значение width_bits . Это влияет на размер последующих преобразований. Новый размер можно рассчитать с помощью DIV_ROUND_UP , как определено ранее .
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 Данные изображения
Изображение представляет собой массив значений пикселей, расположенных в порядке строк развертки.
5.1 Роль данных изображений
Мы используем данные изображений в пяти различных ролях:
- Изображение ARGB: хранит фактические пиксели изображения.
- Энтропийное изображение: хранит мета-префиксные коды (см. «Декодирование мета-префиксных кодов» ).
- Изображение-предиктор: хранит метаданные для преобразования предиктора (см. «Преобразование предиктора» ).
- Изображение, преобразованное по цвету: создается значениями
ColorTransformElement(определенными в параметре "Преобразование цвета" ) для разных блоков изображения. - Изображение для индексации цвета: массив размером
color_table_size(до 256 значений ARGB), в котором хранятся метаданные для преобразования индексации цвета (см. «Преобразование индексации цвета» ).
5.2 Кодирование данных изображения
Кодирование данных изображения не зависит от его роли.
Изображение сначала делится на набор блоков фиксированного размера (обычно 16x16 блоков). Каждый из этих блоков моделируется с использованием собственных энтропийных кодов. Кроме того, несколько блоков могут использовать одни и те же энтропийные коды.
Обоснование: Хранение энтропийного кода влечет за собой затраты. Эти затраты можно минимизировать, если статистически похожие блоки имеют общий энтропийный код, благодаря чему этот код хранится только один раз. Например, кодировщик может находить похожие блоки, кластеризуя их на основе их статистических свойств или многократно объединяя пару случайно выбранных кластеров, когда это уменьшает общее количество битов, необходимых для кодирования изображения.
Каждый пиксель кодируется с использованием одного из трех возможных методов:
- Префиксно-кодированные литералы: каждый канал (зеленый, красный, синий и альфа) кодируется энтропией независимо.
- Обратная ссылка LZ77: Последовательность пикселей копируется из других участков изображения.
- Код цветового кэша: Использование короткого мультипликативного хеш-кода (индекса цветового кэша) недавно увиденного цвета.
В следующих подразделах каждый из них описан подробно.
5.2.1 Литералы с префиксным кодированием
Пиксель хранится в виде префиксно закодированных значений зеленого, красного, синего и альфа-канала (в указанном порядке). Подробности см. в разделе 6.2.3 .
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таких пикселей].
Сопоставление между кодом расстояния distance_code и смещением соседнего пикселя (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 указывает на верхний левый пиксель.
Декодер может преобразовать код расстояния distance_code в порядковый номер строки развертки dist следующим образом:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
где distance_map — это указанное выше отображение, а image_width — ширина изображения в пикселях.
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 определяет размер цветового кэша ( 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 Подробности
Закодированные данные изображения состоят из нескольких частей:
- Расшифровка и построение префиксных кодов.
- Мета-префиксные коды.
- Данные изображения, закодированные с помощью энтропии.
Для каждого пикселя (x, y) существует набор из пяти связанных с ним префиксных кодов. Эти коды (в порядке битового потока):
- Префиксный код #1 : используется для зеленого канала, длины обратной ссылки и цветового кэша.
- Префиксные коды #2, #3 и #4 : используются для красного, синего и альфа-каналов соответственно.
- Префиксный код #5 : используется для обозначения расстояния обратной привязки.
Далее мы будем называть этот набор группой префиксных кодов .
6.2.1 Декодирование и построение префиксных кодов
В этом разделе описывается, как считывать длины префиксных кодов из битового потока.
Длину префиксного кода можно закодировать двумя способами. Используемый метод задается значением в 1 бит.
- Если этот бит равен 1, это простой код длины кода .
- Если этот бит равен 0, это код обычной длины .
В обоих случаях могут оставаться неиспользованные кодовые длины, которые по-прежнему являются частью потока. Это может быть неэффективно, но допускается форматом. Описываемое дерево должно быть полным бинарным деревом. Отдельный листовой узел считается полным бинарным деревом и может быть закодирован с использованием либо простого кода кодовой длины, либо обычного кода кодовой длины. При кодировании отдельного листового узла с использованием обычного кода кодовой длины все кодовые длины, кроме одной, равны нулю, и значение отдельного листового узла помечается длиной 1 — даже если при использовании этого отдельного листового узла не расходуются биты.
Простой код Длина кода
Этот вариант используется в частном случае, когда только 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 .
Код нормальной длины кода
Длина префиксного кода помещается в 8 бит и считывается следующим образом. Во-первых, num_code_lengths указывает количество длин кодов.
int num_code_lengths = 4 + ReadBits(4);
Длина кода кодируется с помощью префиксных кодов; сначала необходимо прочитать длину кода нижнего уровня, 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 , максимальное количество различных считываемых символов ( max_symbol ) для каждого типа символов (A, R, G, B и расстояние) устанавливается равным размеру алфавита:
- Канал G: 256 + 24 +
color_cache_size - Другие литералы (A, R и B): 256
- Код расстояния: 40
В противном случае, оно определяется следующим образом:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Если max_symbol превышает размер алфавита для данного типа символов, битовый поток считается недействительным.
Затем из 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 и расстояние) формируется префиксный код с использованием соответствующих размеров алфавита.
Код стандартной длины должен кодировать полное дерево решений, то есть сумма 2 ^ (-length) для всех ненулевых кодов должна быть равна единице. Однако существует одно исключение из этого правила — дерево с одним листовым узлом, где значение листового узла помечено значением 1, а остальные значения равны 0.
6.2.2 Расшифровка мета-префиксных кодов
Как отмечалось ранее, формат позволяет использовать разные префиксные коды для разных блоков изображения. Мета-префиксные коды — это индексы, определяющие, какие префиксные коды следует использовать в разных частях изображения.
Мета-префиксы могут использоваться только в том случае, если изображение используется в качестве изображения ARGB .
Для мета-префиксных кодов возможны два варианта, обозначаемые однобитным значением:
- Если этот бит равен нулю, то во всем изображении используется только один мета-префиксный код. Дальнейшее хранение данных прекращается.
- Если этот бит равен единице, изображение использует несколько мета-префиксных кодов. Эти мета-префиксные коды хранятся в виде энтропийного изображения (описано ниже).
Красная и зеленая составляющие пикселя определяют 16-битный мета-префиксный код, используемый в конкретном блоке изображения ARGB.
Изображение энтропии
Энтропийное изображение определяет, какие префиксные коды используются в разных частях изображения.
Первые 3 бита содержат значение prefix_bits . Размеры изображения энтропии определяются значением prefix_bits :
int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
DIV_ROUND_UP(image_height, 1 << prefix_bits);
где DIV_ROUND_UP определяется так, как было определено ранее .
Следующие фрагменты содержат изображение энтропии шириной prefix_image_width и высотой prefix_image_height .
Интерпретация мета-префиксных кодов
Количество групп префиксных кодов в изображении 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_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 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 Декодирование данных изображения, закодированных с помощью энтропии
Для текущей позиции (x, y) на изображении декодер сначала определяет соответствующую группу префиксных кодов (как объяснено в предыдущем разделе). Имея группу префиксных кодов, пиксель считывается и декодируется следующим образом.
Далее, считайте символ S из битового потока, используя префиксный код #1. Обратите внимание, что S — любое целое число в диапазоне 0 до (256 + 24 + color_cache_size - 1) .
Интерпретация S зависит от его значения:
- Если S < 256
- Используйте S в качестве зеленого компонента.
- Считывайте красный цвет из битового потока, используя префиксный код #2.
- Считайте синий цвет из битового потока, используя префиксный код #3.
- Считывание альфа-канала из битового потока с использованием префиксного кода #4.
- Если S >= 256 и S < 256 + 24
- Используйте S-256 в качестве префиксного кода длины.
- Из битового потока считываются дополнительные биты, указывающие длину.
- Определите длину обратной ссылки L по коду префикса длины и считанным дополнительным битам.
- Считайте префиксный код расстояния из битового потока, используя префиксный код № 5.
- Считываются дополнительные биты, указывающие на расстояние, из битового потока.
- Определите расстояние обратной привязки D по коду префикса расстояния и считанным дополнительным битам.
- Скопируйте L пикселей (в порядке строк развертки) из последовательности пикселей, начиная с текущей позиции, за вычетом D пикселей.
- Если S >= 256 + 24
- Используйте S - (256 + 24) в качестве индекса для доступа к цветовому кэшу.
- Получите цвет ARGB из цветового кэша по указанному индексу.
7. Общая структура формата
Ниже представлен пример формата в дополненной форме Бэкуса-Наура (ABNF) RFC 5234 RFC 7405. Он не охватывает всех деталей. Конец изображения (EOI) кодируется только неявно в количестве пикселей (ширина изображения * высота изображения).
Note that *element means element can be repeated 0 or more times. 5element means element is repeated exactly 5 times. %b represents a binary value.
7.1 Basic Structure
format = RIFF-header image-header image-stream
RIFF-header = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header = %x2F image-size alpha-is-used version
image-size = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version = 3BIT ; 0
image-stream = optional-transform spatially-coded-image
7.2 Structure of Transforms
optional-transform = (%b1 transform optional-transform) / %b0
transform = predictor-tx / color-tx / subtract-green-tx
transform =/ color-indexing-tx
predictor-tx = %b00 predictor-image
predictor-image = 3BIT ; sub-pixel code
entropy-coded-image
color-tx = %b01 color-image
color-image = 3BIT ; sub-pixel code
entropy-coded-image
subtract-green-tx = %b10
color-indexing-tx = %b11 color-indexing-image
color-indexing-image = 8BIT ; color count
entropy-coded-image
7.3 Structure of the Image Data
spatially-coded-image = color-cache-info meta-prefix data
entropy-coded-image = color-cache-info data
color-cache-info = %b0
color-cache-info =/ (%b1 4BIT) ; 1 followed by color cache size
meta-prefix = %b0 / (%b1 entropy-image)
data = prefix-codes lz77-coded-image
entropy-image = 3BIT ; subsample value
entropy-coded-image
prefix-codes = prefix-code-group *prefix-codes
prefix-code-group =
5prefix-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 = ; see "Normal Code Length Code" for details
lz77-coded-image =
*((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)
The following is a possible example sequence:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image