Юрки Алакуйала, доктор философии, 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.
- цветовой кэш
- Небольшой массив с хэш-адресом для хранения недавно использованных цветов, чтобы можно было вызывать их с помощью более коротких кодов.
- индексация цвета изображения
- Одномерное изображение цветов, которое можно индексировать с помощью небольшого целого числа (до 256 в WebP без потерь).
- преобразование цвета изображения
- Двумерное изображение повышенного разрешения, содержащее данные о корреляциях цветовых компонентов.
- картографирование расстояний
- Изменяет расстояния LZ77, чтобы иметь наименьшие значения для пикселей в двумерной близости.
- энтропийное изображение
- Двумерное изображение с пониженным разрешением, указывающее, какое энтропийное кодирование следует использовать в соответствующем квадрате изображения, то есть каждый пиксель представляет собой метапрефиксный код.
- LZ77
- Алгоритм сжатия скользящего окна на основе словаря, который либо генерирует символы, либо описывает их как последовательности прошлых символов.
- мета-префиксный код
- Небольшое целое число (до 16 бит), которое индексирует элемент в таблице метапрефиксов.
- предикторное изображение
- Двумерное изображение с пониженным разрешением, указывающее, какой пространственный предиктор используется для конкретного квадрата изображения.
- префиксный код
- Классический способ энтропийного кодирования, при котором меньшее количество битов используется для более частых кодов.
- префиксное кодирование
- Способ энтропийного кодирования больших целых чисел, при котором несколько бит целого числа кодируются с использованием энтропийного кода, а оставшиеся биты кодируются в исходном виде. Это позволяет описаниям энтропийных кодов оставаться относительно небольшими, даже если диапазон символов велик.
- порядок строк сканирования
- Порядок обработки пикселей (слева направо и сверху вниз), начиная с левого верхнего пикселя. Как только ряд будет завершен, продолжайте с левого столбца следующей строки.
3 Заголовок RIFF
В начале заголовка находится контейнер RIFF. Он состоит из следующих 21 байта:
- Строка «РИФФ».
- 32-битное значение длины фрагмента с прямым порядком байтов, которое представляет собой полный размер фрагмента, управляемого заголовком RIFF. Обычно это равно размеру полезной нагрузки (размер файла минус 8 байт: 4 байта для идентификатора «RIFF» и 4 байта для хранения самого значения).
- Строка «WEBP» (имя контейнера RIFF).
- Строка «VP8L» (FourCC для данных изображения, закодированных без потерь).
- 32-битное значение числа байтов в потоке без потерь с прямым порядком байтов.
- 1-байтовая подпись 0x2f.
Первые 28 бит битового потока определяют ширину и высоту изображения. Ширина и высота декодируются как 14-битные целые числа следующим образом:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
14-битная точность ширины и высоты изображения ограничивает максимальный размер изображения WebP без потерь до 16384×16384 пикселей.
Бит альфа_is_used является лишь подсказкой и не должен влиять на декодирование. Он должен быть установлен на 0, если все значения альфа на изображении равны 255, и на 1 в противном случае.
int alpha_is_used = ReadBits(1);
Номер_версии — это 3-битный код, который должен быть установлен в 0. Любое другое значение следует рассматривать как ошибку.
int version_number = ReadBits(3);
4 преобразования
Преобразования представляют собой обратимые манипуляции с данными изображения, которые могут уменьшить оставшуюся символическую энтропию за счет моделирования пространственных и цветовых корреляций. Они могут сделать окончательное сжатие более плотным.
Изображение может претерпевать четыре типа преобразований. 1 бит указывает на наличие преобразования. Каждое преобразование разрешено использовать только один раз. Преобразования используются только для изображения ARGB основного уровня; изображения с пониженным разрешением (изображение преобразования цвета, изображение энтропии и изображение-предиктор) не имеют преобразований, даже 0-бит, указывающий на конец преобразований.
Обычно кодер использует эти преобразования для уменьшения энтропии Шеннона в остаточном изображении. Кроме того, данные преобразования могут быть определены на основе минимизации энтропии.
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_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 | ТЛ |
| 5 | Среднее2(Среднее2(L, TR), T) |
| 6 | Среднее2(L, TL) |
| 7 | Среднее2(Л, Т) |
| 8 | Среднее2(TL, Т) |
| 9 | Среднее2(Т, ТР) |
| 10 | Среднее2(Среднее2(L, TL), Среднее2(T, TR)) |
| 11 | Выбрать(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Среднее2(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) {
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-пикселями, и все пиксели в крайнем левом столбце — Т-пиксель.
Обращение к 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 (по модулю 2), зеленое значение в x помещается в 4 младших бита зеленого значения в x/2, а зеленое значение в x + 1 позиционируется на 4 старших бита зеленого значения в точке x/2. -
width_bits= 2: для каждого значения x, где x ≡ 0 (по модулю 4), зеленое значение в x помещается в 2 младших бита зеленого значения в x/4, а зеленые значения в точках x + 1 до x. +3 расположены по порядку к старшим битам зеленого значения в позиции x/4. -
width_bits= 3: для каждого значения x, где x ≡ 0 (по модулю 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 .
Существует две возможности для метапрефиксных кодов, обозначенных 1-битным значением:
- Если этот бит равен нулю, везде в изображении используется только один код метапрефикса. Больше никаких данных не сохраняется.
- Если этот бит равен единице, изображение использует несколько кодов метапрефикса. Эти метапрефиксные коды хранятся в виде энтропийного изображения (описанного ниже).
Красный и зеленый компоненты пикселя определяют 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) лишь неявно закодирован в количестве пикселей (ширина_изображения * высота_изображения).
Обратите внимание, что *element означает, что element может повторяться 0 или более раз. 5element означает, что element повторяется ровно 5 раз. %b представляет двоичное значение.
7.1 Базовая структура
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 Структура преобразований
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 Структура данных изображения
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)
Ниже приведен возможный пример последовательности:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image