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 次元配列。

カラー キャッシュ

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

カラー インデックス画像

小数値（WebP 可逆圧縮で最大 256）を使用してインデックスを付けることができる色の一方向の画像。

色変換画像

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

距離のマッピング

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

エントロピー画像

画像内の各正方形で使用すべきエントロピー コーディング（各ピクセルがメタプレフィックス コード）を示す 2 次元のサブ解像度画像。

LZ77

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

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

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

予測子画像

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

接頭辞コード

エントロピー コーディングを行う古典的な方法。頻度の高いコードには少ないビット数を使用します。

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

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

スキャンラインの順序

左上のピクセルから始まるピクセルの処理順序（左から右、上から下）。行が完了したら、 選択します。

3 RIFF ヘッダー

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

1. 文字列「RIFF」。
2. チャンクの長さのリトルエンディアン 32 ビット値。これは、RIFF ヘッダーによって制御されるチャンクの全体サイズです。通常これは ペイロードのサイズ（ファイルサイズから 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 ビットであるため、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 つの変換

変換は、画像データを可逆的に操作することで、 残存するシンボリック エントロピーを、空間相関と色の相関をモデル化することによって導き出します。Google 最終的な圧縮の密度が高くなります

画像は 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	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)

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）値を 赤の値、緑の値で表示されています。

予測変換の場合と同様に、まず画像がブロックに分割され、ブロック内のすべてのピクセルに同じ変換モードが使用されます。対象 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;
}

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 緑色を差し引く変換

「緑の減算」変換は、次のフィールドの赤と青の値から緑の値を減算します。 です。この変換が存在する場合、デコーダは 値を赤と青の両方の値にマッピングします。これに関連するデータはありません 説明します。デコーダは、次のように逆変換を適用します。

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 proxima 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 値）の配列。カラー インデックス変換のメタデータを格納します（「カラー インデックス変換」をご覧ください）。

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) のオフセットを示します（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 の場合は、単純なコード長コードです。
• このビットが 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 画像のロールで使用されている場合にのみ使用できます。

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

• このビットがゼロの場合、イメージ内のすべての場所で使用されるメタ接頭辞コードは 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