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 バイトに続きます。
- 文字列「RIFF」。
- チャンク長のリトル エンディアン(32 ビット)値。 チャンクのレスポンスを返します。通常これは ペイロードのサイズ(ファイルサイズから 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);
変換データには、画像の各ブロックの予測モードが含まれます。これは、
は低解像度の画像です。ピクセルの緑色成分によって、
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 つの役割で画像データを使用します。
- 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 |
… | … | ... |
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 詳細
エンコードされた画像データは、次の複数の部分で構成されます。
- プレフィックス コードのデコードと構築。
- メタ プレフィックス コード。
- エントロピーで符号化された画像データ。
任意のピクセル(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 の解釈はその値によって異なります。
- 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 を求める 余分なビットが読み取られます
- 先頭のピクセル シーケンスから L ピクセル(スキャンライン順)をコピーします (現在の位置から D ピクセルを引いた値)
- S >= 256 + 24 の場合
<ph type="x-smartling-placeholder">
- </ph>
- 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