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

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

概要

WebP 可逆圧縮は、ARGB 画像の可逆圧縮用の画像形式です。「 は、元の画像に含まれるピクセル値を正確に保存、復元 完全に透明なピクセルを表す色です。Sequential 用のユニバーサル アルゴリズム データ圧縮（LZ77）、プレフィックス コーディング、カラー キャッシュが 一括データを圧縮しますPNG よりも高速なデコード速度が、 圧縮率が 25% 高いことがわかっています 現在の PNG 形式で確認できます。

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 用語

ARRGB

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

ARGB 画像

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

カラー キャッシュ

最近使用した色を格納するためのハッシュ アドレス付きの小さな配列。これにより、 短いコードで思い出してください

カラー インデックス画像

小さな整数を使用してインデックス付けできる、色の 1 次元の画像 （WebP ロスレスでは最大 256 文字）。

色変換画像

次の相関関係に関するデータを含む 2 次元以下の解像度画像 調整できます。

距離のマッピング

LZ77 の距離が、 近接しています。

エントロピー画像

どのエントロピー コーディングを行うべきかを示す 2 次元の低解像度画像 画像内のそれぞれの正方形で使用可能。つまり、各ピクセルは プレフィックス コードです。

LZ77

ディクショナリベースのスライディング ウィンドウ圧縮アルゴリズムで、 過去の記号のシーケンスとして記述するものです。

メタ プレフィックス コード

メタ プレフィックス内の要素をインデックス化する小さな整数（最大 16 ビット） 表します。

予測子画像

どの空間予測器が何であるかを示す 2 次元以下の解像度画像 使用されます。

接頭辞コード

より少ないビット数でエントロピー コーディングを行う古典的な方法 ご確認ください

プレフィックス コーディング

大きい整数をエントロピー（数ビットの整数）コードにする方法 エントロピー符号を使用して、残りのビットを生でコード化します。これにより エントロピー コードの記述を比較的小さくすることは、 記号の範囲が大きいということです。

スキャンラインの順序

左から右、上から下へのピクセルの処理順序。 移動することもできます行が完了したら、 選択します

3 RIFF ヘッダー

ヘッダーの先頭には RIFF コンテナがあります。これは 21 バイトに続きます。

1. 文字列「RIFF」。
2. チャンク長のリトル エンディアン（32 ビット）値。 チャンクのレスポンスを返します。通常これは ペイロードのサイズ（ファイルサイズから 8 バイトを引いた値：「RIFF」は 4 バイト） 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 ビットの精度であるため、画像の最大サイズは 16384×16384 ピクセルの WebP 可逆画像。

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 予測子変換

予測器変換を使用すると、事実を利用してエントロピーを 隣接するピクセル間の相関関係があることが わかります予測器変換では （スキャンラインで）デコードされたピクセルから現在のピクセル値が予測されます。 残差値（実際 - 予測値）のみがエンコードされます。グリーン 成分を使用して、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 抽出しますこの低解像度の画像は、 第 5 章で説明したものと同じ手法を使用します。

ブロック列の数 transform_width は、2 次元の 説明します。ピクセル (x, y) について、それぞれのフィルタ ブロックを計算できます。 アドレス指定方法:

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

14 種類の予測モードがあります。各予測モードでは、現在の 近傍のピクセルから予測され、その値が ことを知っています。

現在のピクセル (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 は左を意味します。ちなみに O、TL、T、TR、L ピクセルのすべてについて、 P ピクセルとすべての X ピクセルが未知です。

先行する隣接ピクセルが与えられると、各予測モードは 定義します。

モード	現在のピクセルの各チャネルの予測値
0	0xff000000（ARGB で黒一色を表す）
1	L
2	T
3	TR
4	TL
5	平均 2（平均 2（L、TR）、T）
6	平均 2（L、TL）
7	平均 2（L、T）
8	平均 2（TL、T）
9	平均 2（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)

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 ピクセル、左端の列はすべて 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）値を 赤の値、緑の値で表示されています。

予測器変換の場合と同様に、まず画像は 1 つずつ ブロック内のすべてのピクセルに対して同じ変換モードが使用されます。対象 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 は、符号付き 8 ビット整数を使用して計算されます。 3.5 固定小数点数と符号付き 8 ビット RGB カラーチャンネル (c) [-128..127] これは次のように定義されます。

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

8 ビットの符号なし表現（uint8）から符号付き 8 ビットへの変換 ColorTransformDelta() を呼び出す前に 1 つ（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 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;

カラーテーブルは、画像保存形式自体を使用して保存されます。カラーテーブル RIFF ヘッダー、画像サイズ、 （高さ 1 ピクセル、幅 color_table_size と仮定）。 カラーテーブルは、画像のエントロピーを下げるために常に減算符号化されます。デルタ パレットの色は通常、色よりもエントロピーが 小さい画像で大幅な費用削減につながっています。デコードでは、 カラーテーブルの最後の色はすべて、 各 ARGB 成分ごとに色成分を別々に格納し、最小の 結果の上位 8 ビットで表します。

画像の逆変換は、単純にピクセル値（つまり、 カラーテーブルのインデックス）を実際のカラーテーブルの値に置き換えます。インデックス登録 ARGB カラーの緑成分に基づいて行われます。

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

インデックスが color_table_size 以上の場合、引数の色値 0x00000000（透明な黒）に設定する必要があります。

カラーテーブルが小さい（16 色以下の）場合、数ピクセル 1 つのピクセルにまとめられますGoogle Pixel のバンドルには複数（2、4、8）パック を 1 ピクセルに変換し、それぞれ画像の幅を縮小します。Google Pixel エントロピー符号化によって、より効率的な 隣接画素を表現し、画像処理に算術符号化のような エントロピー コードがありますが、使用できるのは一意の値が 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] であることを示します。 つまりバイナリ値になります

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

• width_bits = 1: すべての x 値、すなわち x Promote 0 (mod 2) の場合、緑 x の値が x の最下位 4 ビットに x / 2 の緑の値、x + 1 の緑の値は x / 2 の緑値の上位 4 ビット。
• width_bits = 2: すべての x 値、すなわち x had 0 (mod 4) の緑 x の値が x の最下位 2 ビットに x / 4 の緑の値と x + 1 から x + 3 の緑の値は、 x / 4 における緑値の上位ビットの順序付けになります。
• width_bits = 3: すべての x 値、すなわち x had 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 画像データの役割

Google は、次の 5 つの役割で画像データを使用します。

1. ARGB 画像: 画像の実際のピクセルを保存します。
2. エントロピー画像: メタ プレフィックス コードを保存します（ 「メタ プレフィックス コードのデコード」を参照）。
3. 予測子画像: 予測子変換のメタデータを保存します（ 「予測子変換」）。
4. 色変換画像: ColorTransformElement 値により作成 （色変換で定義） 指定します。
5. カラー インデックス画像: サイズ color_table_size の配列（最大 256 の ARGB） 色インデックス変換のメタデータを格納します（ 「Color Indexing Transform」を参照）。

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

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

画像はまず固定サイズのブロックのセット（通常は 16x16 ブロックなど）が使用されます。これらの各ブロックは、独自のエントロピー コードを使用してモデル化されます。また、 複数のブロックが同じエントロピー コードを共有している場合があります。

根拠: エントロピー コードの保存には費用がかかります。このコストは 統計的に類似したブロックがエントロピー コードを共有し、 1 回だけです。たとえば、エンコーダはそれらをクラスタ化して、類似したブロックを見つけることができます。 モデルのペアの統計的特性を使用するか、ランダム性が エンコーディングに必要なビット総量を削減できる場合に、 表示されます。

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

1. 接頭辞が付加されたリテラル: 各チャネル（緑、赤、青、アルファ）は、 個別にエントロピー符号化されます。
2. LZ77 後方参照: 一連のピクセルは、 表示されます。
3. カラー キャッシュ コード: 短い乗法ハッシュコード（カラー キャッシュ）を使用 インデックスなど）が使用されます。

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

5.2.1 接頭辞コード化されたリテラル

ピクセルは、緑色、赤色、青色、アルファの接頭辞でコーディングされた値として できます。セクション 6.2.3 をご覧ください。 表示されます。

5.2.2 LZ77 後方参照

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

• Length は、スキャンライン順にコピーするピクセル数を示します。
• 距離コードは、以前に見た画像の位置を示す数字です。 コピー元のピクセルを指定します。正確なマッピングは 後述します。

長さと距離の値は LZ77 プレフィックス コーディングを使用して保存されます。

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

理論的根拠: このアプローチにより、エントロピーのストレージ要件が軽減されます。 できます。また、大きな値は通常まれなので、非常に大きなデータには追加のビットが使用されます。 いくつかの値が含まれています。したがって、このアプローチでは圧縮率が向上します。 見てきました。

次の表に、格納に使用される接頭辞コードと追加ビットを示します。 値の範囲が異なります。

値の範囲	接頭辞コード	追加ビット
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 * (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 方向の差と 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 の場合は、単純なコード長コードです。
• このビットが 0 の場合は、正規コード長コードです。

どちらの場合も、未使用のコード長が 。これは非効率かもしれませんが、この形式では許可されています。 記述されるツリーは、完全なバイナリツリーである必要があります。単一のリーフノードは 完全なバイナリツリーと見なされ、単純な 指定することもできます。単一のリーフをコーディングする場合 通常のコード長コードを使用するノード。1 つのコード長以外はすべてゼロです。 単一リーフノードの値には長さ 1 が指定されます。 ビットが消費されます。

単純なコード長のコード

このバリアントは、1 つまたは 2 つの接頭辞記号のみが コード長 1 の範囲 [0..255]その他のプレフィックス コード長はすべて ゼロになります。

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

int num_symbols = ReadBits(1) + 1;

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

この最初のシンボルは、 is_first_8bits。範囲はそれぞれ [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 つの記号は異なっている必要があります。重複する記号は使用できますが、 非効率的です

注: その他の特殊なケースとして、すべてのプレフィックス コード長がゼロ（ プレフィックス コードが空です）。たとえば、距離のプレフィックス コードは、 後方参照はありません同様に alpha、red、または 同じメタ プレフィックス コード内のすべてのピクセルが生成された場合、青は空になる可能性があります。 カラー キャッシュを使用します。ただし、このケースでは特別な処理を行う必要はありません。 空の接頭辞コードは、単一の記号 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 の場合、異なる読み取りシンボルの最大数 各シンボルタイプ（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 が出力されます。
• Code 17 は、長さ [3..10] のゼロのストリークを 3 + ReadBits(3) 回出力します。
• Code 18 は、長さ [11..138] のゼロのストリークを出力します。 11 + ReadBits(7) 回。

コード長を読み取ると、各シンボルタイプ（A、R、G、B、 各文字のサイズを使用して形成されます。

通常のコード長のコードは、完全なディシジョン ツリー、つまり ゼロ以外のすべてのコードの 2 ^ (-length) は 1 である必要があります。ただし、 このルールの例外が 1 つあります。1 つのリーフノード ツリーは、リーフノードが 値は値 1 でマークされ、他の値は 0 とマークされます。

6.2.2 メタプレフィックスコードのデコード

前述のように、この形式を使用すると、 画像内のさまざまなブロックを 生成しますメタ プレフィックス コード 接頭辞コードを指定します。

メタ プレフィックス コードは、画像が ARGB イメージの role。

1 ビットで示されるメタ プレフィックス コードには 2 つの可能性が value:

• このビットが 0 の場合、すべての場所で使用されているメタ プレフィックス コードは 1 つだけです。 表示されます。これ以上データは保存されません。
• このビットが 1 の場合、イメージでは複数のメタ プレフィックス コードが使用されます。これらのメタ プレフィックス コードはエントロピー画像として保存されます（後述）。

ピクセルの赤と緑のコンポーネントは、以下で使用される 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];

ここでは、PrefixCodeGroup 構造の存在を前提としています。 は 5 つのプレフィックス コードのセットを表します。また、prefix_code_groups は PrefixCodeGroup（サイズ num_prefix_groups）。

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

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 を使用して、ビットストリームから blue を読み取ります。
   4. プレフィックス コード #4 を使用して、ビットストリームからアルファを読み取ります。
2. S >= 256 かつS <256 + 24
   1. 長さのプレフィックス コードとして S - 256 を使用します。
   2. ビットストリームからその長さの余分なビットを読み取る。
   3. 長さ接頭コードと後方参照長さ L を 余分なビットが読み取られます
   4. プレフィックス コード #5 を使用して、ビットストリームから距離プレフィックス コードを読み取ります。
   5. ビットストリームからの距離の追加ビットを読み取る。
   6. 距離接頭辞コードから後方参照距離 D を求める 余分なビットが読み取られます
   7. 先頭のピクセル シーケンスから L ピクセル（スキャンライン順）をコピーします （現在の位置から D ピクセルを引いた値）
3. S >= 256 + 24 の場合
   1. S - (256 + 24) をカラー キャッシュへのインデックスとして使用します。
   2. そのインデックスのカラー キャッシュから ARGB カラーを取得します。

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

以下は、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