WebP Lossless Bitstream 的規格

Jyrki Alakuijala 博士、Google, Inc., 2023-03-09

摘要

WebP 無損壓縮是一種圖片格式,用於無損壓縮 ARGB 圖片。無損格式會完全儲存及還原像素值,包括全透明像素的顏色值。依序資料壓縮 (LZ77)、前置字元編碼和色彩快取的通用演算法,會用來壓縮大量資料。此外,我們還示範瞭解碼速度比 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 無失真圖片包含標頭資料、轉換資訊和實際的圖片資料。標頭包含圖片的寬度和高度。無損圖片進行編碼之前,可以通過四種不同類型的轉換。位元串流中的轉換資訊包含套用個別反向轉換所需的資料。

2 字詞

ARGB
像素值,由 Alpha、紅色、綠色和藍色值組成。
ARGB 圖片
包含 ARGB 像素的二維陣列。
顏色快取
小型雜湊地址陣列,用於儲存最近使用的顏色,以便使用較短的代碼回電。
色彩索引圖片
可使用小整數 (在 WebP 無損壓縮中最多 256) 建立索引的 1 維色彩圖片。
色彩轉換圖片
二維子解析度圖片包含色彩元件的相關資料。
距離對應
變更 LZ77 距離,設為 2 維鄰近區域的像素最小值。
熵圖片
2D 變解析度圖片,指出應在圖片的各個正方形中使用哪個熵編碼,也就是每個像素都是中繼前置字元代碼。
LZ77
以字典為基礎的滑動視窗壓縮演算法,會發出符號或將其描述為過去的符號序列。
中繼前置字串碼
用於為中繼前置字串資料表中的元素建立索引的小整數 (最多 16 位元)。
預測器圖片
2D 子解析度圖片,指出圖片中特定正方形使用哪個空間預測工具。
首碼
這是進行熵編碼的傳統方法,其中的位元數較少,用於執行頻率較高的程式碼。
字首編碼
對較大的整數進行編碼的方法,可使用熵代碼編碼少數整數,並統一其餘的位元。如此一來,即使符號範圍較大,該熵代碼的說明也相對較小。
掃描行順序
像素的處理順序 (從左到右、由上而下),從左上像素開始。資料列完成之後,請從下一列的左欄繼續。

3 RIFF 標頭

標頭的開頭含有 RIFF 容器。當中包含以下 21 個位元組:

  1. 字串「RIFF」。
  2. 小端的 32 位元值區塊長度,也就是由 RIFF 標頭控制的區塊完整大小。通常相當於酬載大小 (檔案大小減 8 個位元組:「RIFF」ID 為 4 個位元組,儲存值本身則為 4 個位元組)。
  3. 字串「WEBP」(RIFF 容器名稱)。
  4. 字串「VP8L」(適用於無損編碼的圖片資料)。
  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 位元。

一般來說,編碼器會使用這些轉換來減少殘差圖片中的 Shannon 熵。此外,轉換資料也可以根據熵最小化原則決定。

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 預測者轉換

預測者轉換可用來減少鄰近像素通常彼此關聯的事實,藉此減少熵。在預測器轉換中,目前像素值是以已解碼的像素 (以掃描行順序為準) 預測,且只有殘差值 (實際 - 預測) 經過編碼。像素的綠色元件會定義 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 像素。本變解圖片採用與第 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 平均 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 Select(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;
}

「選取預測工具」的定義如下:

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

系統會為每個 ARGB 元件執行 ClampAddSubtractFullClampAddSubtractHalf 函式,如下所示:

// 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-pixel,最左欄中的所有像素都是 T-pixel。

針對最右側欄中的像素處理 TR-pixel 是很例外的情況。最右欄的像素是使用模式 [0..13] 預測,就像邊框不在邊框上的像素一樣,但目前像素與當前像素上最左邊的像素會改為 TR-pixel。

將預測值的每個管道加到經過編碼的剩餘值,即可取得最終像素值。

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 位元 RGB 色彩通道 (c) [-128..127] 的帶正負號 8 位元整數計算,其定義如下:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

呼叫 ColorTransformDelta() 前,必須先將 8 位元無正負號表示法 (uint8) 轉換為 8 位元帶正負號 (int8)。已簽署值應解讀為 8 位元二的互補數值 (也就是 uint8 範圍 [128..255] 會對應至其轉換 int8 值的 [-128..-1] 範圍)。

乘法的精確度會提高 (至少 16 位元精確度)。在這裡,Shift 作業的正負號擴充功能屬性並不重要;只會從結果中使用最低的 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) 像素封裝成一個像素,藉此分別縮減圖片寬度。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,表示有兩個像素合併,且每個像素的範圍都是 [0..15]。值為 2 表示結合了四個像素,而每個像素的範圍則是 [0..3]。值 3 表示合併 8 個像素,而每個像素的範圍都是 [0..1],也就是二進位值。

這些值會封裝至綠色元件中,如下所示:

  • width_bits = 1:對於每個 x 值,其中 x が 0 (mod 2),將 x 的綠色值放在綠色值的 4 位元 (至少 x / 2) 內,而 x + 1 的綠色值則位於 x / 2 最重要的 4 位元。
  • width_bits = 2:對於每個 x 值,其中 x 🙂? 0 (模組 4) 會將 x 的綠色值放在綠色值的 2 個最小位元 (x / 4) 內,而設為 x + 1 到 x + 3 的綠色值則依序為 x / 4 到 4 個重要的位元。
  • width_bits = 3:對於每個 x 值,其中 x 🙂? 0 (模組 8) 會將一個綠色值設為 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 值 (如 "Color Transform" 所定義) 建立。
  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 背面參考資料

反向參照是 lengthdistance code 的元組:

  • 長度則代表掃描行順序中要複製多少像素的像素。
  • 距離代碼是一個數字,指出先前偵測到的像素要從這個位置複製像素。對應關係如下所述。

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

LZ77 前置字串編碼會將大型整數值分為兩個部分:前置字元代碼額外位元。前置字串會使用熵程式碼儲存,其他位元則會直接儲存 (沒有熵程式碼)。

理由:這個方法可降低熵程式碼的儲存需求。此外,大型值通常很少用,因此多餘的位元會用於圖片中的極少數的值。因此,這種做法可以提升整體壓縮效率。

下表說明用來儲存不同範圍值的前置字串代碼和額外位元。

值範圍 前置字串程式碼 額外位元
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 欄的像素。[此類像素總數 = 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 色彩快取編碼

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

理由:相較於使用其他兩種方法 (如 5.2.15.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 的長度,即使在使用單一分葉節點樹狀結構時也不會使用任何位元。

簡易程式碼長度代碼

當只有 1 或 2 個前置字元符號位於代碼長度為 1 的 [0..255] 範圍內時,這個變化版本就會用於特殊情況。所有其他前置字串碼長度一律為零。

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

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 必須先讀取。根據 kCodeLengthCodeOrder 中的順序,其餘 code_length_code_lengths 則為零。

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 會發出長度為 0 的連續 [3..10],也就是 3 + ReadBits(3) 次。
  • 代碼 18 會發出長度為 0 的連續數字 [11..138],也就是 11 + ReadBits(7) 次。

系統讀取程式碼長度之後,每個符號類型 (A、R、G、B 和距離) 的前置字元代碼都會以各自的字母大小組成。

一般代碼長度代碼必須編寫完整的決策樹狀圖,也就是所有非零代碼的 2 ^ (-length) 總和都必須剛好一個。但是此規則有一個例外情況,也就是單一分葉節點樹狀結構,其中分葉節點值會標示為值 1,其他值則為 0。

6.2.2 解碼中繼前置字串程式碼

如前文所述,這種格式允許針對圖片的不同區塊使用不同的前置字元代碼。「中繼前置字元代碼」是一種索引,用來識別圖片不同部分要使用的前置字元代碼。

「只有」ARGB 圖片角色中使用圖片時,才能使用中繼前置字元代碼。

使用 1 位元值表示的中繼前置字元代碼有兩種可能:

  • 如果位元為零,圖片中每一處都只會使用一個中繼前置字元代碼。沒有儲存其他資料。
  • 如果位元為一個,圖片會使用多個中繼前置字元代碼。這些中繼前置字串碼會儲存為 entropy 映像檔 (如下所述)。

像素的紅色和綠色元件定義了 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) 代表熵映像檔中儲存的最大前置字串。

每個前置字串代碼群組都包含五個前置字串代碼,因此前置字串總數為:

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_groupsPrefixCodeGroup 的陣列 (大小為 num_prefix_groups)。

接著,解碼器會使用前置字串程式碼群組 prefix_group 將像素 (x, y) 解碼,詳情請見「解碼 Entropy-Coded Image Data」。

6.2.3 解碼工程編碼圖片資料

針對圖片中的目前位置 (x, y),解碼器會先找出對應的前置碼群組 (如上一節所述)。在開頭為前置字串代碼群組的情況下,系統會將像素讀取及解碼,如下所示。

接著,讀取位元串流中的符號 S 並使用前置字元 #1。請注意,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) 格式 (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