WebP ロスレス ビットストリームの仕様

Jyrki Alakuijala 博士、Google, Inc.、2023 年 3 月 9 日

概要

WebP lossless は、ARGB 画像の可逆圧縮用の画像形式です。ロスレス形式では、完全に透明なピクセルのカラー値を含め、ピクセル値が正確に保存され、復元されます。一括データの圧縮には、シーケンシャル データ圧縮（LZ77）、プレフィックス コーディング、カラー キャッシュ用のユニバーサル アルゴリズムが使用されます。PNG よりも高速なデコード速度が実証されており、現在の PNG 形式で実現できるよりも 25% 密度の高い圧縮も可能です。

1 はじめに

このドキュメントでは、WebP ロスレス画像の圧縮データ表現について説明します。これは、WebP 可逆エンコーダとデコーダの実装に関する詳細なリファレンスとして使用することを目的としています。

このドキュメントでは、ビットストリームを説明するために C プログラミング言語の構文を多用し、ビットを読み取る関数 ReadBits(n) が存在することを前提としています。バイトは、それらを含むストリームの自然な順序で読み取られ、各バイトのビットは最下位ビットから順に読み取られます。複数のビットが同時に読み取られる場合、整数は元のデータから元の順序で構築されます。返される整数の最上位ビットは、元のデータの最上位ビットでもあります。したがって、ステートメント

b = ReadBits(2);

は、次の 2 つのステートメントと同等です。

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

各色コンポーネント（アルファ、赤、青、緑）は 8 ビット バイトで表されると仮定します。対応する型を uint8 として定義します。ARGB ピクセル全体は uint32 という型で表されます。これは 32 ビットの符号なし整数です。変換の動作を示すコードでは、これらの値は次のビットでコード化されています。アルファはビット 31..24、赤はビット 23..16、緑はビット 15..8、青はビット 7..0 です。ただし、フォーマットの実装では、内部で別の表現を使用しても構いません。

一般的に、WebP 可逆圧縮画像には、ヘッダーデータ、変換情報、実際の画像データが含まれています。ヘッダーには、画像の幅と高さが含まれています。WebP の可逆圧縮画像は、エントロピー エンコードされる前に 4 種類の変換を行うことができます。ビットストリーム内の変換情報には、それぞれの逆変換を適用するために必要なデータが含まれています。

2 用語

ARGB

アルファ、赤、緑、青の値で構成されるピクセル値。

ARGB 画像

ARGB ピクセルを含む 2 次元配列。

カラー キャッシュ

最近使用した色を保存し、短いコードで呼び出せるようにするための、小さなハッシュ アドレス指定配列。

カラー インデックス画像

小さな整数（WebP 可逆圧縮では最大 256）を使用してインデックス登録できる色の 1 次元画像。

カラー変換画像

色成分の相関関係に関するデータを含む 2 次元のサブ解像度画像。

距離マッピング

LZ77 距離を、2 次元近接のピクセルに対して最小値になるように変更します。

エントロピー画像

画像内のそれぞれの正方形で使用するエントロピー コーディングを示す 2 次元の低解像度画像。つまり、各ピクセルはメタ接頭辞コードです。

LZ77

シンボルを出力するか、過去のシンボルのシーケンスとして記述する、辞書ベースのスライディング ウィンドウ圧縮アルゴリズム。

メタ接頭辞コード

メタ接頭辞テーブル内の要素をインデックスする小さな整数（最大 16 ビット）。

予測子画像

画像内の特定の正方形に使用される空間予測子を示す 2 次元のサブ解像度画像。

プレフィックス コード

頻繁に使用されるコードに少ないビット数を使用するエントロピー コーディングの古典的な方法。

接頭辞コーディング

大きな整数をエントロピー コード化する方法。エントロピー コードを使用して整数の数ビットをコード化し、残りのビットを未加工のままコード化します。これにより、シンボルの範囲が広い場合でも、エントロピー コードの説明を比較的小さく保つことができます。

スキャンラインの順序

左上のピクセルから始まり、左から右、上から下へとピクセルを処理する順序。1 行が完了したら、次の行の左側の列から続けます。

3 RIFF ヘッダー

ヘッダーの先頭には RIFF コンテナがあります。これは次の 21 バイトで構成されます。

1. 文字列「RIFF」。
2. チャンクの長さのリトルエンディアンの 32 ビット値。これは、RIFF ヘッダーによって制御されるチャンクの全体のサイズです。通常、これはペイロード サイズ（ファイルサイズから 8 バイトを引いた値。4 バイトは「RIFF」識別子、4 バイトは値の保存用）に等しくなります。
3. 文字列「WEBP」（RIFF コンテナ名）。
4. 文字列「VP8L」（ロスレス エンコードされた画像データの FourCC）。
5. ロスレス ストリームのバイト数を示すリトル エンディアンの 32 ビット値。
6. 1 バイトのシグネチャ 0x2f。

ビットストリームの最初の 28 ビットは、画像の幅と高さを指定します。幅と高さは、次のように 14 ビットの整数としてデコードされます。

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

画像の幅と高さの 14 ビットの精度により、WebP ロスレス画像の最大サイズは 16,384✕16,384 ピクセルに制限されます。

alpha_is_used ビットはヒントにすぎず、デコードに影響を与えるべきではありません。画像のすべてのアルファ値が 255 の場合は 0 に、それ以外の場合は 1 に設定する必要があります。

int alpha_is_used = ReadBits(1);

version_number は 3 ビットのコードで、0 に設定する必要があります。その他の値はエラーとして扱う必要があります。

int version_number = ReadBits(3);

4 変換

変換は、空間と色の相関関係をモデル化することで残りのシンボル エントロピーを削減できる、画像データの可逆的な操作です。最終的な圧縮をより高密度にすることができます。

画像は 4 種類の変換を行うことができます。1 ビットは、変換の存在を示します。各変換は 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).

変換が存在する場合、次の 2 ビットは変換タイプを指定します。変換には 4 種類あります。

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

変換タイプに続いて変換データが続きます。変換データには、逆変換の適用に必要な情報が含まれており、変換タイプによって異なります。逆変換は、ビットストリームから読み取られた順序と逆の順序で適用されます（つまり、最後から最初）。

次に、さまざまなタイプの変換データについて説明します。

4.1 予測変換

予測子変換は、隣接するピクセルが相関していることが多いという事実を利用して、エントロピーを削減するために使用できます。予測子変換では、現在のピクセル値はすでにデコードされたピクセル（スキャンライン順）から予測され、残差値（実際の値 - 予測値）のみがエンコードされます。ピクセルの緑色のコンポーネントは、ARGB 画像の特定のブロック内で使用される 14 個の予測子のうちのどれを定義します。予測モードによって、使用する予測のタイプが決まります。画像を正方形に分割し、正方形内のすべてのピクセルで同じ予測モードを使用します。

予測データの最初の 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);

変換データには、画像の各ブロックの予測モードが含まれています。これは、ピクセルの緑色のコンポーネントが、ARGB 画像の特定のブロック内のすべての block_width * block_height ピクセルに使用される 14 個の予測子のうちのどれを定義するかを示す、低解像度の画像です。このサブ解像度画像は、第 5 章で説明したのと同じ手法を使用してエンコードされます。

ブロック列の数 transform_width は、2 次元インデックスで使用されます。ピクセル（x、y）の場合、次の式で対応するフィルタ ブロック アドレスを計算できます。

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

予測モードは 14 種類あります。各予測モードでは、値がすでにわかっている 1 つ以上の隣接ピクセルから現在のピクセル値が予測されます。

現在のピクセル（P）の隣接ピクセル（TL、T、TR、L）は次のように選択しました。

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	L
2	T
3	TR
4	TL
5	Average2(Average2(L, TR), T)
6	Average2(L, TL)
7	Average2(L, T)
8	Average2(TL, T)
9	Average2(T, TR)
10	Average2(Average2(L, TL), Average2(T, TR))
11	Select(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）の値が変換されます。

予測子変換の場合と同様に、まず画像がブロックに分割され、ブロック内のすべてのピクセルに同じ変換モードが使用されます。各ブロックには、3 種類のカラー変換要素があります。

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 は、3.5 固定小数点数を表す符号付き 8 ビット整数と符号付き 8 ビット RGB カラーチャンネル（c）[-128..127] を使用して計算され、次のように定義されます。

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

ColorTransformDelta() を呼び出す前に、8 ビットの符号なし表現（uint8）から 8 ビットの符号付き表現（int8）への変換が必要です。符号付きの値は、8 ビットの 2 の補数として解釈する必要があります（つまり、uint8 の範囲 [128..255] は、変換された int8 値の範囲 [-128..-1] にマッピングされます）。

乗算は、より高い精度（少なくとも 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 Subtract Green 変換

緑の減算変換では、各ピクセルの赤と青の値から緑の値を減算します。この変換が存在する場合、デコーダは緑の値を赤と青の両方の値に追加する必要があります。この変換に関連付けられたデータはありません。デコーダは、次のように逆変換を適用します。

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;

カラーテーブルは、画像保存形式自体を使用して保存されます。高さが 1 ピクセル、幅が color_table_size であると仮定すると、RIFF ヘッダー、画像サイズ、変換なしで画像を読み取ることで、カラーテーブルを取得できます。カラー テーブルは常に減算コード化され、画像のエンティティを削減します。パレットの色のデルタは、通常、色自体よりもエントロピーがはるかに少ないため、小さい画像では大幅な節約につながります。デコードでは、カラー テーブルの各最終色は、各 ARGB コンポーネントごとに前の色のコンポーネント値を加算し、結果の最下位 8 ビットを保存することで取得できます。

画像の逆変換は、ピクセル値（カラーテーブルのインデックス）を実際のカラーテーブル値に置き換えるだけです。インデックス登録は、ARGB カラーの緑のコンポーネントに基づいて行われます。

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

インデックスが color_table_size 以上の場合、argb カラー値は 0x00000000（透明な黒）に設定されるべきです。

カラーテーブルが小さい場合（16 色以下）、複数のピクセルが 1 つのピクセルにバンドルされます。ピクセル バンドリングは、複数の（2、4、8）ピクセルを 1 つのピクセルにまとめ、画像の幅をそれぞれ縮小します。ピクセル バンドリングにより、隣接するピクセルの結合分布エントロピー コーディングをより効率的に行うことができ、エントロピー コードに算術コーディングのようなメリットがもたらされますが、使用できるのは固有値が 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 は、2 つのピクセルが結合され、各ピクセルの範囲が [0..15] であることを示します。値 2 は、4 つのピクセルが結合され、各ピクセルの範囲が [0..3] であることを示します。値 3 は、8 個のピクセルが結合され、各ピクセルの範囲が [0..1]（バイナリ値）であることを示します。

値は次のように緑色のコンポーネントにパックされます。

• width_bits = 1: x ≡ 0（mod 2）となるすべての x 値について、x の緑の値は x / 2 の緑の値の最下位 4 ビットに配置され、x + 1 の緑の値は x / 2 の緑の値の最上位 4 ビットに配置されます。
• width_bits = 2: x ≡ 0（mod 4）となるすべての x 値について、x の緑の値は x / 4 の緑の値の最下位 2 ビットに配置され、x + 1 から x + 3 の緑の値は x / 4 の緑の値の上位ビットに順に配置されます。
• width_bits = 3: x ≡ 0（mod 8）のすべての x 値について、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 画像データの役割

画像データは、次の 5 つの異なる役割で使用されます。

1. ARGB 画像: 画像の実際のピクセルを保存します。
2. エントロピー画像: メタ接頭辞コードを保存します（「メタ接頭辞コードのデコード」を参照）。
3. 予測子イメージ: 予測子変換のメタデータを保存します（「予測子変換」を参照）。
4. 色変換画像: 画像のさまざまなブロックの ColorTransformElement 値（「色変換」で定義）によって作成されます。
5. カラー インデックス登録画像: カラー インデックス登録変換のメタデータを保存する color_table_size サイズの配列（最大 256 個の ARGB 値）（「カラー インデックス登録変換」を参照）。

5.2 画像データのエンコード

画像データのエンコードは、その役割とは無関係です。

画像はまず、固定サイズのブロック（通常は 16x16 ブロック）のセットに分割されます。これらのブロックはそれぞれ、独自のエントロピー コードを使用してモデル化されます。また、複数のブロックで同じエントロピー コードを共有することもあります。

理由: エントロピー コードを保存すると費用が発生します。統計的に類似したブロックがエントロピー コードを共有し、そのコードを 1 回だけ保存することで、このコストを最小限に抑えることができます。たとえば、エンコーダは、統計的プロパティを使用して類似のブロックをクラスタリングするか、画像をエンコードするために必要なビットの総量を削減するときに、ランダムに選択されたクラスタのペアを繰り返し結合することで、類似のブロックを見つけることができます。

各ピクセルは、次の 3 つの方法のいずれかを使用してエンコードされます。

1. プレフィックス コード化されたリテラル: 各チャネル（緑、赤、青、アルファ）は個別にエントロピー コード化されます。
2. LZ77 後方参照: ピクセルのシーケンスが画像の別の場所からコピーされます。
3. カラー キャッシュ コード: 最近使用された色の短い乗法ハッシュコード（カラー キャッシュ インデックス）を使用します。

以降のセクションでは、それぞれについて詳しく説明します。

5.2.1 プレフィックス コード化リテラル

ピクセルは、緑、赤、青、アルファのプレフィックス コード化された値として（この順序で）保存されます。詳しくは、セクション 6.2.3 をご覧ください。

5.2.2 LZ77 後方参照

後方参照は、長さと距離コードのタプルです。

• Length は、スキャンライン順にコピーするピクセル数を示します。
• 距離コードは、以前に表示されたピクセルの位置を示す数値です。この位置からピクセルがコピーされます。正確なマッピングについては、下記をご覧ください。

長さと距離の値は、LZ77 接頭辞コーディングを使用して保存されます。

LZ77 プレフィックス コーディングでは、大きな整数値を 2 つの部分（プレフィックス コードと追加ビット）に分割します。プレフィックス コードはエントロピー コードを使用して保存され、追加のビットはそのまま（エントロピー コードなしで）保存されます。

理由: このアプローチにより、エントロピー コードのストレージ要件が削減されます。また、大きな値は通常まれであるため、追加のビットは画像内のごくわずかな値に使用されます。したがって、このアプローチでは全体的に圧縮率が向上します。

次の表に、さまざまな値の範囲の保存に使用されるプレフィックス コードと追加ビットを示します。

注: 後方参照の最大長は 4,096 に制限されています。したがって、長さの値に対して意味があるのは、最初の 24 個の接頭辞コード（およびそれぞれの追加ビット）のみです。ただし、距離値については、40 個のプレフィックス コードがすべて有効です。

値の範囲	プレフィックス コード	追加のビット
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) を示します。つまり、現在のピクセルの上のピクセル（X 方向のピクセル差が 0、Y 方向のピクセル差が 1）です。同様に、距離コード 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 カラー キャッシュ コーディング

カラー キャッシュには、画像で最近使用された一連の色が保存されます。

理由: この方法では、最近使用した色を、他の 2 つの方法（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 の配列です。各エントリには 1 つの ARGB カラーが保存されます。色は (0x1e35a7bd * color) >> (32 - color_cache_code_bits) でインデックス登録してルックアップされます。カラー キャッシュでは 1 回のルックアップのみが行われ、競合の解決は行われません。

画像のデコードまたはエンコードの開始時に、すべてのカラー キャッシュ値のすべてのエントリがゼロに設定されます。カラー キャッシュ コードは、デコード時にこの色に変換されます。カラー キャッシュの状態は、後方参照またはリテラルとして生成されたすべてのピクセルを、ストリームに現れる順にキャッシュに挿入することで維持されます。

6 エントロピー コード

6.1 概要

データのほとんどは、正規の接頭辞コードを使用してコード化されます。したがって、実際のプレフィックス コードではなく、プレフィックス コードの長さを送信することでコードが送信されます。

特に、この形式では空間的に変化する接頭辞コーディングが使用されます。つまり、画像のブロックごとに異なるエントロピー コードを使用できる可能性があります。

理由: 画像の領域によって特徴が異なる場合があります。そのため、異なるエントロピー コードを使用できるようにすることで、柔軟性が高まり、圧縮率が向上する可能性があります。

6.2 詳細

エンコードされた画像データは、次の複数の部分で構成されています。

1. プレフィックス コードのデコードとビルド。
2. メタ接頭辞コード。
3. エントロピー コーディングされた画像データ。

任意のピクセル（x、y）には、関連付けられた 5 つの接頭辞コードのセットがあります。これらのコードは（ビットストリーム順に）次のとおりです。

• 接頭辞コード #1: グリーン チャネル、後方参照の長さ、カラー キャッシュに使用されます。
• 接頭辞コード #2、#3、#4: それぞれ赤、青、アルファ チャネルに使用されます。
• 接頭辞コード #5: 後方参照距離に使用されます。

以降、このセットをプレフィックス コード グループと呼びます。

6.2.1 プレフィックス コードのデコードと構築

このセクションでは、ビットストリームからプレフィックス コードの長さを読み取る方法について説明します。

接頭辞コードの長さは 2 つの方法でコード化できます。使用されるメソッドは 1 ビットの値で指定されます。

• このビットが 1 の場合、単純なコード長コードです。
• このビットが 0 の場合、通常のコード長コードです。

どちらの場合も、ストリームの一部である未使用のコード長が存在する可能性があります。これは非効率的ですが、形式上は許可されています。記述されたツリーは完全なバイナリ ツリーである必要があります。単一のリーフノードは完全なバイナリツリーと見なされ、単純なコード長コードまたは通常のコード長コードのいずれかを使用してエンコードできます。通常のコード長コードを使用して単一のリーフノードをコーディングする場合、1 つのコード長を除いてすべてゼロになり、単一のリーフノード ツリーが使用されるときにビットが消費されない場合でも、単一のリーフノード値は長さ 1 でマークされます。

Simple Code Length Code

このバリアントは、コード長が 1 で、接頭辞記号が 1 つまたは 2 つのみ [0..255] の範囲にある特殊なケースで使用されます。他のすべてのプレフィックス コードの長さは暗黙的にゼロになります。

最初のビットはシンボルの数を示します。

int num_symbols = ReadBits(1) + 1;

シンボルの値は次のとおりです。

最初のシンボルは、is_first_8bits の値に応じて 1 ビットまたは 8 ビットを使用してコード化されます。範囲はそれぞれ [0..1] または [0..255] です。2 番目のシンボルが存在する場合、常に [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;
}

2 つの記号は異なるものにする必要があります。重複するシンボルは許可されますが、効率的ではありません。

注釈: もう 1 つの特殊なケースは、すべての接頭辞コードの長さが 0（空の接頭辞コード）の場合です。たとえば、後方参照がない場合、距離のプレフィックス コードは空にできます。同様に、同じメタ接頭辞コード内のすべてのピクセルがカラー キャッシュを使用して生成される場合、アルファ、赤、青の接頭辞コードは空にできます。ただし、空の接頭辞コードは単一の記号 0 を含むものとしてコード化できるため、このケースで特別な処理は必要ありません。

Normal Code Length Code

接頭辞コードのコード長は 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 の場合、各シンボルタイプ（A、R、G、B、距離）の異なる読み取りシンボルの最大数（max_symbol）がアルファベット サイズに設定されます。

• 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、距離）の接頭辞コードがそれぞれのアルファベット サイズを使用して形成されます。

Normal Code Length Code は、完全な決定木をコード化する必要があります。つまり、ゼロ以外のすべてのコードの 2 ^ (-length) の合計は 1 になる必要があります。ただし、このルールには 1 つの例外があります。単一のリーフノード ツリーでは、リーフノードの値は 1 でマークされ、他の値は 0 になります。

6.2.2 メタ接頭辞コードのデコード

前述のように、この形式では、画像のブロックごとに異なる接頭辞コードを使用できます。メタ接頭辞コードは、画像のさまざまな部分で使用する接頭辞コードを識別するインデックスです。

メタ接頭辞コードは、ARGB 画像の役割で画像が使用されている場合にのみ使用できます。

メタ接頭辞コードには、1 ビットの値で示される次の 2 つの可能性があります。

• このビットがゼロの場合、イメージ全体で 1 つのメタ プレフィックス コードのみが使用されます。これ以上のデータは保存されません。
• このビットが 1 の場合、画像は複数のメタ接頭辞コードを使用します。これらのメタ接頭辞コードは、エントロピー画像（後述）として保存されます。

ピクセルの赤と緑のコンポーネントは、ARGB 画像の特定のブロックで使用される 16 ビットのメタ接頭辞コードを定義します。

エントロピー画像

エントロピー画像は、画像のさまざまな部分で使用されるプレフィックス コードを定義します。

最初の 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) はエントロピー画像に保存されている最大のプレフィックス コードを示します。

各プレフィックス コード グループには 5 つのプレフィックス コードが含まれているため、プレフィックス コードの合計数は次のようになります。

int num_prefix_codes = 5 * num_prefix_groups;

ARGB 画像のピクセル (x, y) が与えられた場合、次のように使用する対応するプレフィックス コードを取得できます。

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];

ここで、5 つの接頭辞コードのセットを表す PrefixCodeGroup 構造の存在を想定しています。また、prefix_code_groups は PrefixCodeGroup（サイズ num_prefix_groups）の配列です。

次に、デコーダは接頭辞コード グループ prefix_group を使用して、「エントロピー符号化された画像データのデコード」で説明されているように、ピクセル（x、y）をデコードします。

6.2.3 エントロピー符号化された画像データのデコード

画像内の現在の位置（x、y）について、デコーダはまず対応するプレフィックス コード グループを特定します（最後のセクションで説明したとおり）。プレフィックス コード グループが指定されると、ピクセルは次のように読み取られ、デコードされます。

次に、接頭辞コード #1 を使用してビットストリームからシンボル S を読み取ります。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. 現在の位置から D ピクセルを引いた位置から始まるピクセルのシーケンスから、L ピクセル（スキャンライン順）をコピーします。
3. S >= 256 + 24 の場合
   1. カラー キャッシュのインデックスとして S - (256 + 24) を使用します。
   2. そのインデックスのカラー キャッシュから ARGB カラーを取得します。

7 フォーマットの全体構造

以下は、Augmented Backus-Naur Form（ABNF）RFC 5234 RFC 7405 の形式の例です。すべての詳細が含まれているわけではありません。画像終了（EOI）は、ピクセル数（image_width * image_height）に暗黙的にのみコード化されます。

*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