WebP Lossless Bitstream 的規格

Jyrki Alakuijala 博士Google LLC2023 年 3 月 9 日

摘要

WebP 無損是一種圖片格式，可對 ARGB 圖片進行無損壓縮。無損格式會準確儲存及還原像素值，包括完全透明像素的顏色值。大量資料的壓縮作業會使用通用演算法 (LZ77) 進行序列資料壓縮、前置字元編碼和顏色快取。WebP 的解碼速度比 PNG 快，壓縮率也比現今的 PNG 格式高出 25%。

1 簡介

本文說明 WebP 無損圖片的壓縮資料表示法。本文旨在提供 WebP 無損編碼器和解碼器實作的詳細參考資料。

本文會大量使用 C 程式設計語言語法來描述位元串流，並假設存在用於讀取位元的函式 ReadBits(n)。系統會按照包含位元組的串流自然順序讀取位元組，並以最低有效位元優先的順序讀取每個位元組的位元。同時讀取多個位元時，系統會依原始順序從原始資料建構整數。傳回整數中最重要的位元，也是原始資料中最重要的位元。因此，

b = ReadBits(2);

等同於下列兩項陳述：

b = ReadBits(1);
b |= ReadBits(1) << 1;

我們假設每個顏色分量 (即 Alpha、紅色、藍色和綠色) 都是以 8 位元組表示。我們將對應型別定義為 uint8。整個 ARGB 像素由名為 uint32 的型別表示，這是由 32 位元組成的未簽署整數。在顯示轉換行為的程式碼中，這些值會編碼為以下位元：位元 31..24 中的 Alpha、位元 23..16 中的紅色、位元 15..8 中的綠色，以及位元 7..0 中的藍色；不過，格式實作項目可自由使用其他內部表示法。

廣義來說，WebP 無損圖片包含標頭資料、轉換資訊和實際圖片資料。標頭包含圖片的寬度和高度。無損 WebP 圖片在經過熵編碼前，可以先經過四種不同類型的轉換。位元串流中的轉換資訊包含套用個別反向轉換所需的資料。

2 命名法

ARGB

由 Alpha、紅色、綠色和藍色值組成的像素值。

ARGB 圖片

包含 ARGB 像素的二維陣列。

顏色快取

小型雜湊位址陣列，用於儲存最近使用的顏色，以便使用較短的代碼回想這些顏色。

索引色圖片

一維色彩圖片，可使用小型整數建立索引 (WebP 無損壓縮最多可達 256 個)。

色彩轉換圖片

包含色彩分量相關資料的二維子解析度圖片。

距離對應

將 LZ77 距離變更為二維鄰近像素的最小值。

熵圖片

二維子解析度圖片，指出圖片中各個方格應使用的熵編碼，也就是每個像素都是元前置碼。

LZ77

以字典為基礎的滑動視窗壓縮演算法，可發出符號或將符號描述為過去符號的序列。

中繼前置碼

一個小型整數 (最多 16 位元)，用於為中繼前置字元表中的元素建立索引。

預測圖片

二維子解析度圖片，指出圖片中特定方格使用的空間預測子。

前置碼

一種經典的熵編碼方式，較常出現的代碼會使用較少的位元。

前置碼

一種熵編碼方式，可編碼較大的整數，方法是使用熵編碼對整數的幾個位元進行編碼，並以原始形式編碼其餘位元。即使符號範圍很大，熵碼的說明也能維持相對較小的狀態。

掃描線順序

像素的處理順序 (從左到右，再從上到下)，從左上角的像素開始。完成一列後，請繼續下一列的左欄。

3 RIFF 標頭

標頭開頭有 RIFF 容器。這包括下列 21 個位元組：

1. 字串「RIFF」。
2. 區塊長度的 32 位元小端序值，這是由 RIFF 標頭控制的區塊總大小。通常這會等於酬載大小 (檔案大小減去 8 個位元組：4 個位元組用於「RIFF」識別碼，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 無損圖片的最大尺寸限制為 16384✕16384 像素。

alpha_is_used 位元僅為提示，不應影響解碼。如果圖片中的所有 Alpha 值都是 255，則應設為 0，否則設為 1。

int alpha_is_used = ReadBits(1);

version_number 是 3 位元代碼，必須設為 0。其他值應視為錯誤。

int version_number = ReadBits(3);

4 種轉換

轉換是可逆的圖像資料操作，可透過模擬空間和色彩相關性，減少剩餘的符號熵。可讓最終壓縮更密集。

圖片可經過四種轉換，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).

如有轉換，接下來的兩個位元會指定轉換類型。 轉換共有四種類型。

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);

轉換資料包含圖片每個區塊的預測模式。這是子解析度圖像，其中像素的綠色元件會定義 14 個預測值中的哪一個，用於特定 ARGB 圖像區塊中的所有 block_width * block_height 像素。這個子解析度圖片是使用第 5 章所述的相同技術編碼。

區塊欄數 transform_width 用於二維索引。對於像素 (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 代表左側。預測 P 的值時，所有 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	Average2(L, TL)
7	Average2(L, T)
8	Average2(TL, T)
9	Average2(T, TR)
10	Average2(Average2(L, TL), Average2(T, TR))
11	選取(L、T、TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

每個 ARGB 元件的 Average2 定義如下：

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) 值。

與預測器轉換一樣，圖片會先分成多個區塊，且區塊中的所有像素都會使用相同的轉換模式。每個區塊都有三種顏色轉換元素。

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 位元的二補數 (也就是說，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' 都會視為子解析度圖片中的像素，其 Alpha 元件為 255、紅色元件為 cte.red_to_blue、綠色元件為 cte.green_to_blue，藍色元件則為 cte.green_to_red。

解碼期間，系統會解碼區塊的 ColorTransformElement 例項，並對像素的 ARGB 值套用反向色彩轉換。如先前所述，反轉色彩轉換只是將 ColorTransformElement 值加到紅色和藍色通道。Alpha 和綠色通道則維持不變。

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 值的陣列，然後用對應的索引取代像素值：像素的綠色管道會替換為索引，所有 Alpha 值都會設為 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 種顏色)，系統會將多個像素捆綁成單一像素。像素組合會將數個 (2、4 或 8 個) 像素組合成單一像素，藉此縮減影像寬度。像素組合可更有效率地對相鄰像素進行聯合分布熵編碼，並為熵編碼帶來類似算術編碼的優點，但只能在有 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 表示兩個像素已合併，且每個像素的範圍為 [0..15]。值為 2 表示四個像素會合併，且每個像素的範圍為 [0..3]。值為 3 表示八個像素會合併，且每個像素的範圍為 [0..1]，也就是二進位值。

這些值會封裝到綠色元件中，如下所示：

• width_bits = 1：對於每個 x 值 (其中 x ≡ 0 (mod 2))，x 的綠色值會放置在 x / 2 的綠色值中，最不重要的 4 個位元，而 x + 1 的綠色值會放置在 x / 2 的綠色值中，最重要的 4 個位元。
• width_bits = 2：對於每個 x 值 (其中 x ≡ 0 (mod 4))，x 的綠色值會放置在 x / 4 的綠色值中，最不重要的 2 個位元，而 x + 1 到 x + 3 的綠色值會依序放置在 x / 4 的綠色值中，較重要的位元。
• width_bits = 3：對於每個 x 值 (其中 x ≡ 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 圖像資料的角色

我們在五種不同角色中使用圖片資料：

1. ARGB 圖片：儲存圖片的實際像素。
2. 熵圖片：儲存中繼前置碼 (請參閱「中繼前置碼的解碼」)。
3. 預測值圖片：儲存預測值轉換的中繼資料 (請參閱「預測值轉換」)。
4. 色彩轉換圖片：由 ColorTransformElement 值建立 (定義於「色彩轉換」)，適用於圖片的不同區塊。
5. 色彩索引圖片：大小為 color_table_size 的陣列 (最多 256 個 ARGB 值)，用於儲存色彩索引轉換的中繼資料 (請參閱「色彩索引轉換」)。

5.2 圖片資料編碼

圖片資料的編碼與其角色無關。

圖片會先分成一組固定大小的方塊 (通常是 16x16 方塊)，每個區塊都會使用自己的熵編碼進行建模。此外，多個區塊可能會共用相同的熵編碼。

理由：儲存熵碼會產生費用。如果統計上相似的區塊共用一個熵編碼，則可將該編碼只儲存一次，進而將這項成本降到最低。舉例來說，編碼器可以根據統計屬性將類似區塊分組，或在減少編碼圖像所需的總位元數時，重複加入一對隨機選取的叢集，藉此找出類似區塊。

每個像素都會使用下列三種可能方法之一進行編碼：

1. 前置碼字面值：每個色頻 (綠色、紅色、藍色和 Alpha) 都會獨立進行熵編碼。
2. LZ77 向後參照：從圖片中的其他位置複製像素序列。
3. 顏色快取代碼：使用最近顯示顏色的短乘法雜湊碼 (顏色快取索引)。

以下各小節將詳細說明這些項目。

5.2.1 前置字元編碼的常值

像素會儲存為綠色、紅色、藍色和 Alpha 的前置碼值 (依此順序)。詳情請參閱第 6.2.3 節。

5.2.2 LZ77 回溯參照

反向參照是 長度和距離代碼的元組：

• 長度表示要複製的掃描線順序像素數量。
• 距離代碼是數字，表示先前看過的像素位置，像素會從該位置複製。確切的對應關係請參閱下文。

長度和距離值會使用 LZ77 前置字串編碼儲存。

LZ77 前置碼編碼會將大型整數值分成兩部分：前置碼和額外位元。前置字串代碼會使用熵碼儲存，而額外位元則會照原樣儲存 (不使用熵碼)。

理由：這種做法可減少熵編碼的儲存空間需求。此外，大值通常很少見，因此額外位元會用於圖像中的極少數值。因此，這種方法整體而言可帶來更出色的壓縮效果。

下表列出用於儲存不同值範圍的前置碼和額外位元。

注意： 向後參照的長度上限為 4096 個半形字元。因此，只有前 24 個前置碼 (以及各自的額外位元) 對長度值有意義。但距離值可使用所有 40 個前置碼。

值範圍	前置字串代碼	額外位元
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 欄的像素。[Total such pixels = 7 * (8 + 1 + 7) = 112]。
• 與目前像素位於同一列，且最多位於目前像素左側 8 個資料欄的像素。[8 such pixels]。

距離代碼 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 顏色快取編碼

色彩快取會儲存圖片中最近使用的一組顏色。

理由：這樣一來，與使用其他兩種方法 (如 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 的陣列。每個項目都會儲存一個 ARGB 顏色。顏色會依 (0x1e35a7bd * color) >> (32 - color_cache_code_bits) 建立索引，色彩快取中只會執行一次查詢，不會解決衝突。

在解碼或編碼圖片的開頭，所有色彩快取值中的所有項目都會設為零。顏色快取程式碼會在解碼時轉換為這個顏色。將每個像素 (無論是透過向後參照產生，還是以常值形式產生) 插入快取，並按照像素在串流中的顯示順序排列，即可維護色彩快取的狀態。

6 熵編碼

6.1 總覽

大部分資料都是使用標準前置字元代碼編碼。 因此，系統會傳送前置碼長度，而非實際的前置碼。

具體來說，此格式採用空間變異前置字串編碼。換句話說，圖片的不同區塊可能會使用不同的熵編碼。

理由：圖片不同區域的特徵可能不同。 因此，允許使用不同的熵編碼可提供更多彈性，並可能提高壓縮率。

6.2 詳細資料

編碼後的圖片資料包含多個部分：

1. 解碼及建構前置碼。
2. 中繼前置碼。
3. 經過熵編碼的圖片資料。

對於任何指定像素 (x, y)，都有一組五個相關聯的前置碼。這些代碼 (依位元串流順序排列) 如下：

• 前置碼 #1：用於綠色通道、向後參照長度和色彩快取。
• 前置碼 #2、#3 和 #4：分別用於紅色、藍色和 Alpha 色板。
• 前置碼 #5：用於向後參照距離。

從現在起，我們將這組號碼稱為「前置碼群組」。

6.2.1 解碼及建構前置碼

本節說明如何從位元串讀取前置碼長度。

前置碼長度可透過兩種方式編碼。所用的方法由 1 位元值指定。

• 如果這個位元是 1，則為簡單的程式碼長度程式碼。
• 如果這個位元為 0，則為正常長度代碼。

在這兩種情況下，串流中可能仍有未使用的程式碼長度。這可能效率不彰，但格式允許這麼做。 所述樹狀結構必須是完整二元樹。單一葉節點視為完整的二元樹，可使用簡單的程式碼長度程式碼或一般程式碼長度程式碼進行編碼。使用一般程式碼長度程式碼編碼單一葉節點時，除了其中一個程式碼長度外，其餘都是零，而單一葉節點值會標示長度為 1，即使使用該單一葉節點樹狀結構時不會耗用任何位元也一樣。

簡單程式碼長度程式碼

只有在範圍 [0..255] 中有 1 或 2 個前置字元，且程式碼長度為 1 時，才使用這個變體。其他所有前置碼長度都會隱含零。

第一個位元表示符號數量：

int num_symbols = ReadBits(1) + 1;

符號值如下。

第一個符號會使用 1 或 8 位元編碼，視 is_first_8bits 的值而定。範圍分別為 [0..1] 或 [0..255]。如果存在第二個符號，系統一律會假設該符號位於 [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;
}

這兩個符號應有所不同。允許使用重複符號，但效率不彰。

注意：另一種特殊情況是所有前置字元代碼長度都是零 (前置字元代碼為空)。舉例來說，如果沒有向後參照，距離的前置字元碼可以為空。同樣地，如果使用顏色快取產生相同中繼前置字元代碼中的所有像素，則 alpha、紅色和藍色的前置字元代碼可以為空。不過，這種情況不需要特別處理，因為空前置碼可以編碼為包含單一符號 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，其他值則為 0。

6.2.2 解碼 Meta 前置字串代碼

如先前所述，這個格式允許圖片的不同區塊使用不同的前置碼。中繼前置字串代碼是索引，用於識別要在圖片的不同部分使用哪些前置字串代碼。

只有在圖片用於 ARGB 圖片的角色時，才能使用 Meta 前置碼。

後設前置碼有兩種可能性，以 1 位元值表示：

• 如果這個位元為零，則映像檔中各處只會使用一個中繼前置字元代碼。系統不會再儲存資料。
• 如果這個位元為 1，表示圖片使用多個中繼前置字串碼。這些前置字串元資料代碼會儲存為熵圖片 (如下所述)。

像素的紅色和綠色元件會定義 16 位元的中繼前置碼，用於 ARGB 圖片的特定區塊。

熵圖片

熵圖片會定義圖片不同部分使用的前置字串代碼。

前 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) 表示儲存在熵圖片中的最大前置碼。

由於每個前置碼群組包含五個前置碼，因此前置碼總數為：

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 結構，代表一組五個前置碼。此外，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 的解讀方式取決於其值：

1. 如果 S < 256
   1. 使用 S 做為綠色元件。
   2. 使用前置字元代碼 #2 從位元串讀取紅色。
   3. 使用前置字元代碼 #3 從位元串讀取藍色。
   4. 使用前置字元代碼 #4 從位元串流讀取 alpha。
2. 如果 S >= 256 且 S < 256 + 24
   1. 使用 S - 256 做為長度前置字串代碼。
   2. 從位元串流讀取長度的額外位元。
   3. 根據長度前置碼和讀取的額外位元，判斷向後參照長度 L。
   4. 使用前置字元代碼 #5 從位元串流讀取距離前置字元代碼。
   5. 從位元串流讀取距離的額外位元。
   6. 根據距離前置碼和讀取的額外位元，判斷向後參照距離 D。
   7. 從目前位置減去 D 像素開始，依掃描線順序複製 L 像素。
3. 如果 S >= 256 + 24
   1. 使用 S - (256 + 24) 做為顏色快取的索引。
   2. 從該索引的顏色快取取得 ARGB 顏色。

7 格式的整體結構

以下是擴充巴科斯諾爾形式 (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