Jyrki Alakuijala 博士、Google Inc.、2023-03-09
抽象化
WebP 可逆圧縮は、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 用語
- ARRGB
- アルファ、赤、緑、青の値で構成されるピクセル値。
- ARGB 画像
- ARGB ピクセルを含む 2 次元配列。
- カラー キャッシュ
- 最近使用された色を格納して、短いコードで思い出せるようにするための、ハッシュ アドレス付きの小さな配列。
- カラー インデックス画像
- 小さい整数（WebP 可逆ロスレス内で最大 256）を使用してインデックス化できる色の 1 次元画像。
- 色変換画像
- 色成分の相関関係に関するデータを含む 2 次元の下位解像度画像。
- 距離マッピング
- 2 次元近傍のピクセル値が最小になるように LZ77 距離を変更します。
- エントロピー画像
- 画像内のそれぞれのマスにどのエントロピー コーディングを使用すべきかを示す 2 次元のサブ解像度画像。つまり、各ピクセルはメタ プレフィックス コードです。
- LZ77
- シンボルを出力するか、過去のシンボルのシーケンスとして記述する、辞書ベースのスライディング ウィンドウ圧縮アルゴリズム。
- メタ プレフィックス コード
- メタ プレフィックス テーブル内の要素をインデックスに登録する小さな整数（最大 16 ビット）。
- 予測子の画像
- 画像内の特定の正方形にどの空間予測子が使用されているかを示す 2 次元の下位解像度画像。
- プレフィックス コード
- 頻度の高いコードに対してより少ないビット数を使用するエントロピー コーディングを行う従来の方法。
- プレフィックス コーディング
- より大きな整数をエントロピーしてコード化する方法。エントロピー コードを使用して整数の数ビットをコード化し、残りのビットは未加工としてコード化します。これにより、シンボルの範囲が広い場合でも、エントロピー コードの説明を比較的小さくすることができます。
- スキャンラインの順序
- ピクセルの処理順序（左から右、上から下）。左上のピクセルから順に処理します。行が完成したら、次の行の左側の列から続行します。
3 RIFF ヘッダー
ヘッダーの先頭に RIFF コンテナがあります。これは、次の 21 バイトで構成されます。
- 文字列「RIFF」。
- チャンク長の 32 ビット値（リトル エンディアン）。これは、RIFF ヘッダーによって制御されるチャンクの全体サイズです。通常、これはペイロード サイズ（ファイルサイズから 8 バイトを引いた値: 「RIFF」識別子に 4 バイト、値自体を格納する 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 ピクセルに制限されます。
alpha_is_used ビットはヒントにすぎず、デコードには影響しません。画像内のすべてのアルファ値が 255 の場合は 0 に設定し、そうでない場合は 1 に設定します。
int alpha_is_used = ReadBits(1);
version_number は 3 ビットコードで、0 に設定する必要があります。その他の値はエラーとして処理されます。
int version_number = ReadBits(3);
4 つの変換
変換は画像データの可逆操作であり、空間と色の相関関係をモデル化することで残りのシンボリック エントロピーを低減できます。最終的な圧縮をより高密度にできます。
1 つの画像に対して行える変換は 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 | 平均 2(平均 2(L, TR), T) |
| 6 | 平均 2（L、TL） |
| 7 | 平均 2（L、T） |
| 8 | 平均 2（TL、T） |
| 9 | 平均 2（T、TR） |
| 10 | 平均 2(平均 2(L, TL), 平均 2(T, TR)) |
| 11 | 選択（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 ピクセル、左端列のすべてのピクセルは 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 緑の減算変換
緑の減算変換は、各ピクセルの赤と青の値から緑の値を減算します。この変換が存在する場合、デコーダは緑の値を赤と青の両方の値に追加する必要があります。この変換に関連付けられたデータはありません。デコーダは、次のように逆変換を適用します。
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 色以下）場合は、複数のピクセルが 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 つの異なる役割で使用されます。
- ARGB 画像: 画像の実際のピクセルを保存します。
- エントロピー画像: メタ プレフィックス コードを保存します（「Meta プレフィックス コードのデコード」」をご覧ください）。
- 予測子画像: 予測子変換のメタデータを保存します（予測子変換を参照）。
- 色変換画像: 画像のさまざまなブロックの
ColorTransformElement値（色変換で定義）によって作成されます。 - カラー インデックス画像: カラー インデックス変換のメタデータを格納するサイズ
color_table_size（最大 256 個の ARGB 値）の配列（「カラー インデックス変換」を参照）。
5.2 画像データのエンコード
画像データのエンコードは、その役割とは無関係です。
イメージはまず、固定サイズのブロック（通常は 16×16 ブロック）のセットに分割されます。これらのブロックはそれぞれ、独自のエントロピー コードを使用してモデル化されます。また、複数のブロックが同じエントロピー コードを共有する場合もあります。
理由: エントロピー コードを保存するとコストが発生します。統計的に類似したブロックがエントロピー コードを共有すると、このコストを最小限に抑えることができます。これにより、そのコードを 1 回だけ保存できます。たとえば、エンコーダは、統計的特性を使用してそれらをクラスタ化する、またはランダムに選択されたクラスタのペアを繰り返し結合することによって、画像のエンコードに必要なビット総量を減らすことによって、類似のブロックを見つけることができます。
各ピクセルは、次の 3 つの方法のいずれかを使用してエンコードされます。
- プレフィックス コーディングされたリテラル: 各チャネル（緑、赤、青、アルファ）は独立してエントロピー コーディングされます。
- LZ77 後方参照: ピクセルのシーケンスが画像の他の場所からコピーされます。
- カラー キャッシュ コード: 最近認識された色の短い乗法ハッシュコード（カラー キャッシュ インデックス）を使用します。
以降のサブセクションで、それぞれについて詳しく説明します。
5.2.1 接頭辞コード付きリテラル
ピクセルは、緑、赤、青、アルファの、プレフィックス コーディングされた値として保存されます。詳細についてはセクション 6.2.3 をご覧ください。
5.2.2 LZ77 後方参照
後方参照は、長さと距離コードのタプルです。
- 長さは、コピーするスキャンライン順のピクセル数を示します。
- 距離コードは、以前に認識されたピクセルの位置を示す数値です。このピクセルからコピーされます。正確なマッピングについては、下記をご覧ください。
長さと距離の値は、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 列あるピクセル。[そのようなピクセルの総数 =
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 は、隣接するピクセル、つまり現在のピクセルの上のピクセル（X 方向の差異 0 ピクセル、Y 方向の差異 1 ピクセル）に対する (0, 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 回だけ行われます。競合の解決は行われません。
画像のデコードまたはエンコードの開始時に、すべてのカラー キャッシュ値のすべてのエントリが 0 に設定されます。カラー キャッシュ コードは、デコード時にこの色に変換されます。カラー キャッシュの状態は、後方参照やリテラルのどちらであれ、すべてのピクセルをストリームに出現する順序でキャッシュに挿入することで維持されます。
6 エントロピー コード
6.1 概要
ほとんどのデータは正規のプレフィックス コードを使用してコーディングされます。したがって、コードは実際のプレフィックス コードとは異なり、プレフィックス コードの長さを送信することで送信されます。
特に、この形式では空間的にバリアント プレフィックス コーディングを使用します。つまり、画像のブロックごとに異なるエントロピー コードが使用される可能性があります。
理由: 画像の領域によって特徴が異なる場合があります。したがって、異なるエントロピー コードを使用できるようにすることで、柔軟性が高まり、圧縮率が向上する可能性があります。
6.2 詳細
エンコードされた画像データは、いくつかの部分で構成されます。
- プレフィックス コードのデコードと構築。
- Meta プレフィックスコード。
- エントロピー コーディングされた画像データ。
任意のピクセル（x, y）には、5 つのプレフィックス コードが関連付けられています。これらのコードは次のとおりです（ビットストリーム順）。
- プレフィックス コード #1: 緑チャンネル、後方参照長、カラー キャッシュに使用されます。
- プレフィックス コード #2、#3、#4: それぞれ赤、青、アルファ チャネルに使用されます。
- プレフィックス コード #5: 後方参照距離に使用されます。
以降は、これをプレフィックス コード グループと呼びます。
6.2.1 プレフィックス コードのデコードと構築
このセクションでは、ビットストリームからプレフィックス コード長を読み取る方法について説明します。
プレフィックス コードの長さは 2 つの方法でコーディングできます。使用されるメソッドは 1 ビット値で指定します。
- このビットが 1 の場合は、単純コード長コードです。
- このビットが 0 の場合、通常のコード長であるコードです。
どちらの場合も、未使用のコード長がストリームに残っている可能性があります。この方法は非効率的かもしれませんが、形式によっては許可されています。記述するツリーは、完全なバイナリツリーである必要があります。1 つのリーフノードは完全なバイナリツリーとみなされ、単純なコード長コードまたは通常のコード長コードを使用してエンコードできます。通常のコード長コードを使用して単一のリーフノードをコーディングする場合、コード長を 1 つ残し、それ以外はすべてゼロになり、単一のリーフノード値は長さ 1 としてマークされます。これは、その単一のリーフノードツリーが使用されたときにビットが消費されない場合でも同様です。
シンプルなコードの長さコード
このバリアントは、1 つまたは 2 つの接頭辞記号のみが [0..255] の範囲にあり、コード長が 1 の場合の特殊なケースで使用されます。他のすべてのプレフィックス コード長は暗黙的にゼロです。
最初のビットはシンボルの数を示します。
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 つの記号は異なる必要があります。重複するシンボルも使用できますが、非効率的です。
注: 別の特殊なケースとして、すべてのプレフィックス コードの長さがゼロ（空のプレフィックス コード）の場合です。たとえば、後方参照がない場合は、距離のプレフィックス コードを空にできます。同様に、同じメタ プレフィックス コード内のすべてのピクセルがカラー キャッシュを使用して生成された場合は、アルファ、赤、青のプレフィックス コードを空にできます。ただし、空のプレフィックス コードは単一のシンボル 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] の連続した 0、つまり
11 + ReadBits(7)回分を出力します。
コード長が読み取られると、各シンボルタイプ（A、R、G、B、距離）のプレフィックス コードが、それぞれのアルファベット サイズを使用して形成されます。
標準コード長コードは完全なディシジョン ツリーをコーディングしなければなりません。つまり、すべてのゼロ以外のコードの 2 ^ (-length) の合計は、正確に 1 でなければなりません。ただし、このルールには例外が 1 つあります。シングル リーフノード ツリーでは、リーフノード値は値 1 でマークされ、他の値は 0 としてマークされます。
6.2.2 Meta プレフィックス コードのデコード
前述のように、この形式では、イメージのブロックごとに異なるプレフィックス コードを使用できます。メタ プレフィックス コードは、画像のさまざまな部分で使用するプレフィックス コードを識別するインデックスです。
meta プレフィックス コードは、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 のエントロピー画像が含まれます。
Meta プレフィックス コードの解釈
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 の解釈は値によって異なります。
- S < 256 の場合
- 緑色のコンポーネントには S を使用します。
- プレフィックス コード #2 を使用して、ビットストリームから赤色を読み取ります。
- プレフィックス コード #3 を使用して、ビットストリームから青色を読み取ります。
- プレフィックス コード #4 を使用して、ビットストリームからアルファを読み取ります。
- S >= 256、S < 256 + 24 の場合
- 長さのプレフィックス コードには S - 256 を使用します。
- その長さに対応する追加ビットをビットストリームから読み取ります。
- 長さのプレフィックス コードと読み取られた追加ビットから、後方参照の長さ L を特定します。
- プレフィックス コード #5 を使用して、ビットストリームから距離プレフィックス コードを読み取ります。
- ビットストリームからの距離の追加ビットを読み取ります。
- 距離プレフィックス コードと読み取られた追加ビットから後方参照距離 D を特定します。
- 現在の位置から始まるピクセルのシーケンスから D ピクセルを引いたものから L ピクセルを（スキャンライン順で）コピーします。
- S >= 256 + 24 の場合
- カラー キャッシュのインデックスとして S - (256 + 24) を使用します。
- そのインデックスのカラー キャッシュから ARGB カラーを取得します。
7 フォーマットの全体的な構成
Augmented Backus-Naur Form（ABNF）RFC 5234 RFC 7405 の形式を以下に示します。すべての詳細を網羅しているわけではありません。画像終了（EOI）は、ピクセル数（image_width * image_height）でしか暗黙的にコーディングされません。
*element は、element を 0 回以上繰り返すことができることを意味します。5element は、element がちょうど 5 回繰り返されることを意味します。%b は 2 進値を表します。
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