Jyrki Alakuijala 博士、Google, Inc., 2023 年 3 月 9 日
概要
WebP 非可逆圧縮は、ARGB 画像を可逆圧縮するための画像形式です。「 は、元の画像に含まれるピクセル値を正確に保存、復元 完全に透明なピクセルを表す色です。一括データの圧縮には、連続データ圧縮（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 用語
- ARGB
- アルファ、赤、緑、青の値で構成されるピクセル値。
- ARGB 画像
- ARGB ピクセルを含む 2 次元配列。
- カラーキャッシュ
- 最近使用した色を保存し、短いコードで呼び出せるようにする、小さなハッシュ アドレス アレイ。
- カラー インデックス画像
- 小数値（WebP 可逆圧縮で最大 256）を使用してインデックスを付けることができる色の一方向の画像。
- 色変換画像
- 色成分の相関に関するデータを含む 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 ビットの精度であるため、画像の最大サイズは 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);
変換データには、画像の各ブロックの予測モードが含まれます。これはサブ解像度画像で、ピクセルの緑色成分によって、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 は左を意味します。ちなみに 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 | 平均 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 ピクセル、左端の列のすべてのピクセルは 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 値を使用して、ピクセル値を新しい 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 つのピクセルにまとめられます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] であることを示します。つまり、バイナリ値です。
値は次のように緑色のコンポーネントにパックされます。
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 値、すなわち 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 つの役割で使用しています。
- ARGB 画像: 画像の実際のピクセルを保存します。
- エントロピー画像: メタ プレフィックス コードを保存します（ 「メタ プレフィックス コードのデコード」を参照）。
- 予測子画像: 予測子変換のメタデータを保存します（ 「予測子変換」）。
- 色変換画像:
ColorTransformElement値により作成 （色変換で定義） 指定します。 - カラー インデックス画像:
color_table_sizeのサイズの配列（最大 256 文字） ARGB 値など）です。これは、カラー インデックス変換のメタデータを格納します（ 「Color Indexing Transform」を参照）。
5.2 画像データのエンコード
画像データのエンコードは、その役割とは無関係です。
画像はまず、一連の固定サイズのブロック（通常は 16x16 ブロック）に分割されます。これらのブロックはそれぞれ、独自のエントロピー コードを使用してモデル化されます。また、 複数のブロックが同じエントロピー コードを共有している場合があります。
根拠: エントロピー コードの保存には費用がかかります。統計的に類似したブロックがエントロピー コードを共有し、そのコードを 1 回だけ保存すると、この費用を最小限に抑えることができます。たとえば、エンコーダは、統計特性を使用してブロックをクラスタ化するか、画像のエンコードに必要なビット数の総量を削減する場合は、ランダムに選択されたクラスタのペアを繰り返し結合することで、類似ブロックを見つけることができます。
各ピクセルは、次の 3 つの方法のいずれかでエンコードされます。
- 接頭辞が付加されたリテラル: 各チャネル（緑、赤、青、アルファ）は、 個別にエントロピー符号化されます。
- LZ77 後方参照: 画像内の別の場所からピクセル シーケンスがコピーされます。
- カラー キャッシュ コード: 最近表示された色の短い乗算ハッシュコード（カラー キャッシュ インデックス）を使用します。
以降のサブセクションでは、これらについて詳しく説明します。
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 |
| … | … | ... |
| 3,072～4,096 | 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 の場合、カラー キャッシュは size が次に読み取られます。
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 詳細
エンコードされた画像データは、次の複数の部分で構成されます。
- プレフィックス コードのデコードとビルド。
- メタ プレフィックス コード。
- エントロピーで符号化された画像データ。
特定のピクセル（x、y）には、5 つの接頭辞コードが関連付けられています。これらのコードは（ビットストリーム順に）次のとおりです。
- 接頭辞コード 1: 緑色チャンネル、後方参照長、カラー キャッシュに使用されます。
- 接頭辞コード #2、#3、#4: それぞれ赤、青、アルファ チャネルに使用されます。
- プレフィックス コード #5: 後方参照距離に使用されます。
以降、このセットをプレフィックス コードグループと呼びます。
6.2.1 接頭辞コードのデコードと作成
このセクションでは、ビットストリームからプレフィックス コード長を読み取る方法について説明します。
プレフィックス コード長は 2 つの方法でコーディングできます。使用される方法は 1 ビットの値で指定されます。
- このビットが 1 の場合、単純なコード長コードです。
- このビットが 0 の場合、通常のコード長コードです。
どちらの場合も、ストリームの一部でありながら未使用のコード長が存在する可能性があります。これは非効率的ですが、形式では許可されています。記述する木は完全二分木である必要があります。単一のリーフノードは完全なバイナリ ツリーと見なされ、単純なコード長コードまたは通常のコード長コードのいずれかを使用してエンコードできます。通常のコード長コードを使用して単一リーフノードをコーディングする場合、1 つを除くすべてのコード長はゼロになり、単一リーフノードの値は長さが 1 にマークされます。これは、単一リーフノード ツリーが使用されたときにビットが消費されない場合でも同様です。
単純なコード長のコード
このバリアントは、コード長が 1 で、範囲 [0..255] にプレフィックス記号が 1 つまたは 2 つしかない特別な場合に使用されます。他のすべてのプレフィックス コードの長さは暗黙的に 0 です。
最初のビットは記号の数を示します。
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（空の接頭辞コード）の場合も特殊なケースです。たとえば、距離のプレフィックス コードは、
後方参照はありません同様に 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 が繰り返されます。 - コード 17 は、長さ [3..10] のゼロの連続を
3 + ReadBits(3)回出力します。 - コード 18 は、長さ [11..138] のゼロの連続を
11 + ReadBits(7)回出力します。
コード長を読み取ると、各シンボルタイプ（A、R、G、B、 各文字のサイズを使用して形成されます。
通常のコード長コードは、完全なディシジョン ツリーをコード化する必要があります。つまり、ゼロ以外のすべてのコードの 2 ^ (-length) の合計が正確に 1 である必要があります。ただし、このルールには 1 つの例外があります。単一リーフノード ツリーです。リーフノード値は値 1 でマークされ、他の値は 0 です。
6.2.2 メタ接頭辞コードのデコード
前述のように、この形式を使用すると、 画像内のさまざまなブロックを 生成しますメタ接頭辞コードは、画像のさまざまな部分で使用する接頭辞コードを識別するインデックスです。
メタ接頭辞コードは、画像が ARGB 画像のロールで使用されている場合にのみ使用できます。
1 ビットで示されるメタ プレフィックス コードには 2 つの可能性が value:
- このビットが 0 の場合、すべての場所で使用されているメタ プレフィックス コードは 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];
ここでは、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 の解釈はその値によって異なります。
- S <256
<ph type="x-smartling-placeholder">
- </ph>
- 緑色のコンポーネントとして S を使用します。
- 接頭辞コード #2 を使用して、ビットストリームから赤を読み取ります。
- プレフィックス コード #3 を使用して、ビットストリームから blue を読み取ります。
- プレフィックス コード #4 を使用して、ビットストリームからアルファを読み取ります。
- S >= 256 かつS <256 + 24
<ph type="x-smartling-placeholder">
- </ph>
- 長さのプレフィックス コードとして 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 はバイナリ値を表します。
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