從編碼器到解碼器的畫素資料

在上一篇文章中，我們重點討論了人眼如何看到影像以及裝置如何顯示影像。現在，是時候放大並探索影像的微小構件——畫素及其背後的位元組了。

什麼是影像畫素？

要顯示一幅影像，裝置需要從資料來源獲取影像不同部分的顏色資訊。對於裝置來說，大多數影像只是網格，網格中的每個單元格都是一個畫素。畫素是一個短暫的值；它沒有大小或形狀。如何表示這些畫素，取決於硬體和軟體。

儲存畫素資料的方式有無數種，因此裝置需要理解影像格式，即資料的組織方式。在 Web 上，有幾種常見的格式：JPEG、AVIF、WebP、JPEG XL、PNG 等等。畫素有幾個重要的屬性：

它們排列成網格以形成影像，順序很重要。
每個畫素都包含顏色和亮度資訊。這些值是離散的，並受影像格式定義的位元數限制。

注意： AVIF 可以使用 8、10 或 12 位元來儲存畫素資料。一種較新的 JPEG 格式 JPEG XL，每個顏色通道支援高達 32 位元。最常見的設定是每通道 8 位元，取值範圍從 0 到 255。這為每個顏色分量只提供了 256 種可能的“色度”——總共大約有 256 × 256 × 256 ≈ 1600 萬種可能的顏色。

瞭解影像畫素和裝置畫素之間的區別很重要。影像畫素是影像資料的一部分，而裝置畫素是依賴於顯示器的物理畫素。裝置畫素的工作方式各不相同：例如，在 OLED 螢幕中，每個畫素是一個微小的發光二極體；在 LCD 中，它是由背光控制的晶體；在電子墨水屏中，它是由移動形成影像的帶電粒子組成的。

顯示卡中的影像

為了讓顯示器顯示影像，顯示卡需要將該影像作為訊號傳送到顯示器。一個簡化的解釋是，顯示卡將影像畫素資料儲存為一個數字陣列。讓我們看看如何在 JavaScript 中操作畫素資料：

html

<div class="symbols-holder"></div>

const show = (str) => {
  const holder = document.querySelector(".symbols-holder");
  holder.innerText = str;
};

css

.symbols-holder {
  font-family: monospace;
  white-space: pre;
  font-size: 5px;
  line-height: 3px;
}

const imageToSymbols = (src, showPixelsSomehow) => {
  const img = new Image(); // create an image element
  img.onload = () => {
    const width = 128;
    const height = 128;
    const canvas = new OffscreenCanvas(width, height);
    const ctx = canvas.getContext("2d");
    ctx?.drawImage(img, 0, 0);
    const resp = ctx.getImageData(0, 0, width, height); // read image data

    let str = "";

    // convert image data to string
    for (let i = 0; i < resp.data.length; i += 4) {
      // use opacity channel
      str += resp.data[i + 3] > 255 / 2 ? "*" : ".";

      if (i % (4 * width) === 0) {
        str += "\n";
      }
    }
    showPixelsSomehow(str);
  };
  img.src = src;
};

imageToSymbols("squirrel.png", show);

提取的 ImageData 是一個連續的無符號 1 位元組整數的型別化陣列。在這個例子中，影像不包含任何顏色。相反，每個影像畫素有四個分量，所有有趣的資訊都儲存在第四個分量——alpha 通道中。透過讀取每四個元素，我們可以透過 alpha 通道掃描整個影像。

注意： alpha 通道儲存有關影像透明度的資訊。值為 255 表示畫素完全不透明，而 0 表示完全透明。

影像規範

舉個例子，讓我們看一張非常小的 100×133 畫素的影像：

A photo of a squirrel sitting on a fence and eating a nut from an open hand.

如果沒有 alpha 通道——意味著每個畫素只有三個分量——並且我們使用 8 位色，那麼影像的原始大小應該在 40 KB 左右。但實際檔案不到 3 KB。很快就會明白為什麼。對於更大的影像，這種差異會變得更加顯著。

現在想象一下，不是單張影像，而是需要渲染一段 60 秒的短影片。以每秒 24 幀計算，總共有 1,440 幀。每幀 38 KB，總大小將在 55 MB 左右。顯然，需要高效地打包畫素。為了處理這個問題，已經開發了許多影像和影片格式：BMP、GIF、JPEG、PNG、JPEG2000、多個版本的 MPEG、H.264、VP8、VP9 和 AV1。

因此，資料首先被編碼，然後再被解碼——處理這個過程的東西被稱為編解碼器（coder, decoder）。編碼可以在 CPU 或 GPU 上進行。通常，影像資料存放在 RAM 中，CPU 對其進行解碼，然後結果被髮送到 GPU，以便在螢幕上顯示。但當處理量變大時——比如影片播放——上傳壓縮的影像資料會更高效。在這種情況下，GPU 會自己進行解碼。

影片由兩種型別的幀組成：內幀（intraframe）和間幀（interframe）。內幀基本上是被壓縮的完整影像，而間幀儲存的是影像部分從一幀到下一幀如何移動的資訊。

注意： 更準確地說，間幀包含運動向量。

內幀壓縮的工作原理與影像壓縮完全相同。像 AVIF、HEIF 和 WebP 這樣的格式實際上是基於相關影片編解碼器中使用的內幀壓縮技術。總的來說，編解碼器的發展速度比影像格式快，因此影像格式往往成為影片編解碼器開發的副產品。

例如，在現代影像格式還未被瀏覽器廣泛支援的過去（現在情況已不同），人們會使用單幀影片來代替影像。

影像編碼器的工作原理

編碼器生成的位元序列稱為位元流。要傳輸或儲存這些資料，需要將其分割成塊。這些塊根據格式的不同有不同的名稱。例如，在 AV1 影片和 AVIF 影像中，它們被稱為 OBU（Open Bitstream Units，開放位元流單元）。每個單元都有自己的結構，以便解碼器知道如何處理它。

但一張影像通常不僅僅是一系列位元流單元。如前所述，它還可以包含 ICC 配置檔案和其他元資料——比如影像尺寸、色彩空間、相機設定、日期、時間和地點。所有這些都需要被打包到一個容器中。

容器有自己的規範，不同的媒體格式可以重複使用同一個容器。例如：

AVIF 是一個位於 HEIF 容器中的 AV1 位元組流。
WebP 是一個位於 RIFF 容器中的 VP8 位元組流（或無損 WebP）。

有時，一種影像格式會定義自己的容器。PNG、JPEG 和 JPEG XL 將佈局作為檔案格式規範的一部分。

影像解碼器的工作原理

解碼器透過讀取檔案開頭來確定格式，檔案開頭通常包含一個幻數——幾個用於標識格式的位元組。對於 AVIF，這個幻數是 ftypavif。

然後它會遵循容器佈局來找到相關資料。通常，元資料在前，然後是實際的位元組流。讓我們用一些松鼠圖片來看看這是如何工作的 😀

A photo of a squirrel sitting on a fence and eating a nut from an open hand.

該影像在檔案開頭包含大量元資料：

width: 1536
height: 1536
bands: 3
format: uchar
coding: none
interpretation: srgb
xoffset: 0
yoffset: 0
xres: 2.83465
yres: 2.83465
filename: ./squirrel.jpg
vips-loader: jpegload
jpeg-multiscan: 1
interlaced: 1
jpeg-chroma-subsample: 4:2:0

如果大部分內容目前還看不懂，沒關係——其中一些條目稍後會解釋。如你所見，寬度和高度儲存在容器的開頭。這對瀏覽器特別有用，可以快速在頁面上為影像分配空間。

注意： 不要讓瀏覽器自己計算影像的高度和寬度——這會導致惱人的佈局偏移。相反，應該在 <img> 元素上設定 width 和 height 屬性。

深入瞭解編碼器

那麼編碼器如何能將 38 KB 的影像資料壓縮到僅 3 KB 呢？編碼器使用了一系列技術和演算法，利用了我們感知影像的方式以及影像的結構。讓我們逐一瞭解它們。

有損和無失真壓縮方法

壓縮影像有兩種方法：

有損： 編碼後的影像會改變或移除一些資訊，不再與原始影像完全相同。
無損： 影像可以被完全重建。

有損和無失真壓縮方法可以結合使用，有時可以用更少的位元組提供更好的結果。例如，alpha 通道（控制不透明度）可以無失真壓縮，而顏色通道使用有失真壓縮以提高效率。

下表總結了幾種流行的影像格式：

格式	壓縮型別	注意
PNG	無損	始終無損
JPEG	有損	始終有損
WebP	混合	可以是有損的 VP8 幀，或使用不同演算法的無損幀
AVIF	有損或無損
JPEG XL	有損或無損

色度子取樣

人類對亮度的敏感度遠高於對顏色的敏感度。YCbCr 色彩空間利用了這一事實，將亮度（luminance）與顏色資訊分開，從而實現更高效的壓縮。

編碼器不是儲存每個畫素的完整顏色細節，而是跳過部分顏色資料。然後解碼器根據附近畫素的顏色重建它。這種技術被稱為色度二次取樣。

色度二次取樣使用三個數字來描述，對應一個 4×2 的畫素網格：

第一個數字總是 4，代表區域的寬度。
第二個數字顯示第一行儲存了多少色度樣本（Cb 和 Cr）。
第三個數字顯示第二行儲存了多少色度樣本。

AVIF 支援以下色度二次取樣格式：

4:4:4 – 無二次取樣；所有顏色資訊都被保留。
4:2:2 – 一半的顏色資訊被丟棄。
4:2:0 – 僅保留原始顏色資料的四分之一。

這是一個有損變換的例子。一旦應用，原始影像就無法完全恢復，但對觀看者來說看起來仍然相當不錯，同時節省了儲存空間和頻寬。

利用空間區域性性

讓我們看一個程式碼示例來演示下一個技術。這裡有兩個畫布：一個帶有隨機畫素，另一個帶有純色。

<canvas id="first" width="100" height="100"></canvas>
<canvas id="second" width="100" height="100"></canvas>

const canvas1 = document.getElementById("first");
const canvas2 = document.getElementById("second");

const width = 100;
const height = 100;
let ctx = canvas1.getContext("2d");
for (let i = 0; i < width; i++) {
  for (let j = 0; j < height; j++) {
    ctx.fillStyle = `rgb(${Math.random() * 255}, ${Math.random() * 255}, ${
      Math.random() * 255
    })`;
    ctx.fillRect(i, j, 1, 1);
  }
}

ctx = canvas2.getContext("2d");
ctx.fillStyle = "rgba(6, 142, 110, 0.81)";
ctx.fillRect(0, 0, width, height);

嘗試分別儲存這兩張圖片：右鍵點選每張圖片並選擇“圖片另存為”。即使使用效率不高的瀏覽器編解碼器，第一張圖片的大小也約為 35 KB，而第二張圖片僅為 500 位元組。大小相差 70 倍！

原因是第一張圖片中的畫素之間沒有任何關係。在真實影像中，相鄰畫素通常以某種方式相關。它們可能共享相同的顏色、形成漸變或遵循某種模式。這個屬性被稱為空間區域性性。

A photo of a squirrel with labels pointing at different colors: black pixels of the eye, green pixels of the moss, grey pixels of the sweater.

一張影像包含的資訊越少，它就越能被更好地壓縮。編解碼器充分利用了這個屬性，將影像分成區域並分別壓縮每個區域。

例如，JPEG 總是將影像分割成 8×8 的塊。更現代的影像格式允許靈活的塊大小。例如，AVIF 使用從 4×4 到 128×128 的塊。編解碼器通常堅持使用 2 的冪次方作為塊大小，以保持計算簡單高效。

對於一張有純藍色天空的影像，將該區域劃分為更大的塊更有效率，這減少了儲存不必要細節的需求。同樣的規則適用於任何純色背景。但編碼器如何決定在何處以及如何分割影像呢？有幾種技術可以實現這一點，我們接下來可以探討。

AVIF 使用遞迴方法將影像分割成塊。它首先將影像分割成更大的塊，稱為超級塊。然後，它分析每個塊的內容，並決定是進一步分割還是保持原樣。為了管理這種分割槽，AVIF 使用一種四叉樹資料結構。四叉樹也常用於地圖應用中，用於儲存位置並高效地查詢附近的物體。

你可以透過遞迴地將影像分割成四個方塊來自己構建一個四叉樹。對於每個方塊，計算平均顏色和與平均值的偏差。如果偏差太大，就再次分割該方塊。

<canvas width="512" height="512"></canvas>

const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
const img = new Image();
const imgSrc = "squirrel-grayscale.jpg";

ctx.strokeStyle = "lime";
ctx.lineWidth = 1;
img.onload = () => {
  ctx.drawImage(img, 0, 0, canvas.width, canvas.height);
  const imgData = ctx.getImageData(0, 0, canvas.width, canvas.height);

  showSplit(imgData, canvas.width);
};
img.src = imgSrc;

function regionStd(x, y, w, h, data, totalWidth) {
  let sum = 0,
    sumSq = 0;
  for (let j = 0; j < h; j++) {
    let idx = ((y + j) * totalWidth + x) * 4;
    for (let i = 0; i < w; i++) {
      const v = data[idx];
      sum += v;
      sumSq += v * v;
      idx += 4;
    }
  }
  const n = w * h;
  const mean = sum / n;

  return Math.sqrt(sumSq / n - mean * mean);
}

function buildQuadtree(params) {
  const { x, y, w, h, forceSplitSize, minSize, threshold, data, totalWidth } =
    params;

  // always split big regions
  const forced = w > forceSplitSize && h > forceSplitSize;
  const std = regionStd(x, y, w, h, data, totalWidth);

  // if the region is too small or color varies little, stop
  if (w <= minSize || h <= minSize || (!forced && std < threshold)) return;

  ctx.strokeRect(x, y, w, h);

  const midW = (w / 2) | 0;
  const midH = (h / 2) | 0;
  if (midW === 0 || midH === 0) return;

  const nextParams = { ...params, w: midW, h: midH };

  // left top
  buildQuadtree({ ...nextParams });

  // right top
  buildQuadtree({ ...nextParams, x: x + midW, y });

  // left bottom
  buildQuadtree({ ...nextParams, x, y: y + midH });

  // right bottom
  buildQuadtree({
    ...nextParams,
    x: x + midW,
    y: y + midH,
  });
}

function showSplit(imgData, totalWidth) {
  const params = {
    threshold: 28,
    minSize: 8,
    forceSplitSize: 128,
    totalWidth,
  };

  buildQuadtree({
    x: 0,
    y: 0,
    w: totalWidth,
    h: totalWidth,
    data: imgData.data,
    ...params,
  });
}

預測模式

一個塊包含的資料越少，它就能被更好地壓縮。透過點選下面的畫布上的不同單元格來嘗試一個 8×8 畫素的塊。點選幾次後，標記為綠色的部分圖案將被重現。

與其儲存網格中的每個畫素，不如只儲存實際影像與最匹配模式之間的差異，這樣可以節省空間。

body {
  display: flex;
  align-items: start;
  column-gap: 1rem;
}

<canvas width="256" height="256"></canvas> <button>Reset</button>

const size = 256;
const totalCells = 8;
const cellSize = size / totalCells;

const canvas = document.querySelector("canvas");
canvas.width = size;
canvas.height = size;

let ctx = canvas.getContext("2d");
let empty = Array(totalCells * totalCells).fill(0);
let bitmask = [...empty];

const locate = (x, y) => {
  const cellX = Math.floor(x / cellSize);
  const cellY = Math.floor(y / cellSize);
  return cellY * totalCells + cellX;
};

const predictions = [
  Array(totalCells * totalCells).fill(0), // empty
  Array(totalCells * totalCells).fill(1), // full

  // 4 vertical strips (cols 0, 2, 4, 6)
  Array.from({ length: totalCells * totalCells }, (_, i) =>
    [0, 2, 4, 6].includes(i % totalCells) ? 1 : 0,
  ),

  // 4 horizontal strips (rows 0, 2, 4, 6)
  Array.from({ length: totalCells * totalCells }, (_, i) =>
    [0, 2, 4, 6].includes(Math.floor(i / totalCells)) ? 1 : 0,
  ),

  // main diagonal
  Array.from({ length: totalCells * totalCells }, (_, i) =>
    i % (totalCells + 1) === 0 ? 1 : 0,
  ),

  // anti-diagonal
  Array.from({ length: totalCells * totalCells }, (_, i) =>
    i % (totalCells - 1) === 0 && i !== 0 && i !== totalCells * totalCells - 1
      ? 1
      : 0,
  ),

  // cross
  Array.from({ length: totalCells * totalCells }, (_, i) =>
    Math.floor(i / totalCells) === Math.floor(totalCells / 2) ||
    i % totalCells === Math.floor(totalCells / 2)
      ? 1
      : 0,
  ),

  // border
  Array.from({ length: totalCells * totalCells }, (_, i) => {
    const x = i % totalCells;
    const y = Math.floor(i / totalCells);
    return x === 0 || x === totalCells - 1 || y === 0 || y === totalCells - 1
      ? 1
      : 0;
  }),

  // checkerboard
  Array.from({ length: totalCells * totalCells }, (_, i) => {
    const x = i % totalCells;
    const y = Math.floor(i / totalCells);
    return (x + y) % 2 === 0 ? 1 : 0;
  }),

  // top-left quadrant
  Array.from({ length: totalCells * totalCells }, (_, i) => {
    const x = i % totalCells;
    const y = Math.floor(i / totalCells);
    return x < totalCells / 2 && y < totalCells / 2 ? 1 : 0;
  }),

  // center 2x2 block
  Array.from({ length: totalCells * totalCells }, (_, i) => {
    const x = i % totalCells;
    const y = Math.floor(i / totalCells);
    return x >= 3 && x <= 4 && y >= 3 && y <= 4 ? 1 : 0;
  }),

  // Single vertical strips
  ...Array.from({ length: totalCells }, (_, col) =>
    Array.from({ length: totalCells * totalCells }, (_, i) =>
      i % totalCells === col ? 1 : 0,
    ),
  ),

  // Single horizontal strips
  ...Array.from({ length: totalCells }, (_, row) =>
    Array.from({ length: totalCells * totalCells }, (_, i) =>
      Math.floor(i / totalCells) === row ? 1 : 0,
    ),
  ),

  // Diagonals (offset from main diagonal: -7 to +7)
  ...Array.from({ length: totalCells * 2 - 1 }, (_, offset) => {
    const k = offset - (totalCells - 1); // from -7 to +7
    return Array.from({ length: totalCells * totalCells }, (_, i) => {
      const x = i % totalCells;
      const y = Math.floor(i / totalCells);
      return x - y === k ? 1 : 0;
    });
  }),

  // Anti-diagonals (offsets from 0 to 2N-2)
  ...Array.from({ length: totalCells * 2 - 1 }, (_, offset) => {
    return Array.from({ length: totalCells * totalCells }, (_, i) => {
      const x = i % totalCells;
      const y = Math.floor(i / totalCells);
      return x + y === offset ? 1 : 0;
    });
  }),
];

const getBestPrediction = () => {
  let score = 0;
  let prediction = empty;

  for (const pred of predictions) {
    let currentScore = pred.reduce((acc, val, i) => {
      if (pred[i] == bitmask[i]) {
        acc++;
      }
      return acc;
    }, 0);

    if (currentScore > score) {
      score = currentScore;
      prediction = pred;
    }
  }

  return prediction;
};

const drawPrediction = () => {
  const best = getBestPrediction();
  for (let i = 0; i < best.length; i++) {
    if (best[i] === 1) {
      const x = (i % totalCells) * cellSize;
      const y = Math.floor(i / totalCells) * cellSize;
      ctx.fillStyle = "#1279468a";
      ctx.fillRect(x, y, cellSize, cellSize);
      ctx.fillStyle = "black";
    }
  }
};

const draw = () => {
  ctx.clearRect(0, 0, size, size);
  for (let i = 0; i < bitmask.length; i++) {
    if (bitmask[i] === 1) {
      const x = (i % totalCells) * cellSize;
      const y = Math.floor(i / totalCells) * cellSize;
      ctx.fillStyle = "rgba(216,114,1,0.5)";
      ctx.fillRect(x, y, cellSize, cellSize);
      ctx.fillStyle = "black";
    }
  }

  drawPrediction();

  ctx.strokeStyle = "black";
  ctx.lineWidth = 1;
  for (let i = 0; i <= size; i += cellSize) {
    ctx.beginPath();
    ctx.moveTo(i, 0);
    ctx.lineTo(i, size);
    ctx.stroke();

    ctx.beginPath();
    ctx.moveTo(0, i);
    ctx.lineTo(size, i);
    ctx.stroke();
  }
};

const setBitmask = (x, y) => {
  bitmask[locate(x, y)] = 1;
  draw();
};

const resetBitmask = () => {
  bitmask = Array.from({ length: totalCells * totalCells }, () => 0);
  draw();
};

draw();

canvas.addEventListener("click", (e) => {
  const x = e.offsetX;
  const y = e.offsetY;
  setBitmask(x, y);
});

document.querySelector("button").addEventListener("click", resetBitmask);

現代影像編解碼器使用同樣的想法。它們為每個塊預測一個基本結構，然後只壓縮實際塊內容與預測之間的差異，稱為殘差。

大多數影像都有一些潛在的結構，編解碼器透過分析梯度或重複紋理等模式來利用這一點，以做出更好的預測。

A photo of a squirrel with labels pointing at different groups of pixels. Black group: just a color from this pixel. Pair of pixels connected with an arrow with the same pair: repeat the previous block in this direction.

塊內的畫素通常形成一個與其相鄰值相關的模式。因此，編解碼器不使用靜態模式，而是使用塊的頂行和左列作為參考來進行預測。看圖中的左邊例子：方塊內的畫素與一些周圍的畫素非常相似。

不同的編解碼器使用各種預測模式來找到表示這種結構並最小化誤差的最佳方式。例如：

該塊可以被預測為其相鄰畫素的平均值。
它可以沿特定方向重複畫素（如圖所示）。
它可能會組合多個相鄰畫素以建立更準確的預測。
更高階的預測器會考慮塊內每個畫素的座標來最佳化結果。
更高階的模式更進一步，透過遞迴地預測前幾行和前幾列的畫素。編碼器不只依賴於參考畫素，而是使用先前預測的畫素生成補丁。

透過改進這些預測，編解碼器可以顯著減少需要儲存或傳輸的資料量。例如，AVIF 的一種預測模式是基於左鄰參考畫素、右上參考畫素以及塊內畫素的座標。

預測不僅限於空間結構——顏色通道也可以相互關聯。這個想法在 AVIF 和 JPEG XL 中都有使用。相關的預測模式，色度來自亮度，是根據相應的 Y（亮度）通道資訊來預測顏色通道（UV）。一些編解碼器，不是預測畫素，而是可以儲存一條指令來複制另一個塊的內容。這對於截圖或具有重複圖案的影像特別有用，因為它減少了冗餘。

不同編解碼器的預測模式數量各不相同。AVIF 有很多（71個），WebP 較少（10個），而 JPEG 完全不使用預測。

塊變換

編解碼器進行預測，然後找出與該預測的畫素差異。接下來，編解碼器需要高效地儲存這些差異，這時候就需要丟棄一些資料，即應用有損變換。

你可以用同樣的模式類比來思考。現在有一組固定的模式，目標是找出組合它們的最佳方式，以得到接近原始塊的東西。這就像透過堆疊多個具有不同不透明度的圖層來構建影像——每個圖層都對最終結果有貢獻，訣竅是為每個圖層猜對正確的不透明度。實現這一點的數學方法叫做離散餘弦變換（DCT）。

為什麼這有助於減小檔案大小？人類對高頻分量（如微小的點或精細的紋理）不太敏感。變換將這些高頻和低頻部分分離開來，使得決定哪些細節可以安全丟棄變得更容易。

一種著名的視覺化方式是透過 DCT 基函式，它顯示了不同頻率分量如何對影像做出貢獻。

Four squares in a row with 8×8 patterns increasing in complexity from low to high: the first one fully black, the second one is filled with linear gradient, the third one has two-dimentional patern, the fourth one is checkerboard with radial gradient.

注意： 雖然這是一個有用的圖示，但請記住，現代編解碼器是對殘差而不是原始影像應用變換。

讓我們透過一個例子來看看這是如何工作的。想象一個 8×8 的塊，中間有一條水平的 2 畫素粗的線：

<div class="out"></div>

css

.out {
  font-family: monospace;
  white-space: pre;
}

const block = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1], // <- line
  [1, 1, 1, 1, 1, 1, 1, 1], // <- line
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
];

// special weight function
const alpha = (u, size) =>
  u === 0 ? 1 / Math.sqrt(size) : Math.sqrt(2 / size);

// A very naive and innefficient implementation of 2D DCT
const dct2D = (block) => {
  const size = block.length;
  // create block of the same size
  const result = Array.from({ length: size }, () => Array(size).fill(0));

  // apply DCT formula
  for (let u = 0; u < size; u++) {
    for (let v = 0; v < size; v++) {
      let sum = 0;
      for (let x = 0; x < size; x++) {
        for (let y = 0; y < size; y++) {
          sum +=
            block[x][y] *
            Math.cos(((2 * x + 1) * u * Math.PI) / (2 * size)) *
            Math.cos(((2 * y + 1) * v * Math.PI) / (2 * size));
        }
      }
      result[u][v] = alpha(u, size) * alpha(v, size) * sum;
    }
  }
  return result;
};

const out = document.querySelector(".out");
const dct = dct2D(block);
const formatNumber = (e) => {
  if (e > -0.001 && e < 0.001) {
    return ` ${Math.abs(e).toFixed(2)}`;
  }
  return `${e >= 0 ? " " : ""}${e.toFixed(2)}`;
};
out.innerHTML = dct.map((row) => row.map(formatNumber).join(" ")).join("<br>");

當然，實際的實現是高效且經過最佳化的：

編解碼器不是一次性對整個塊應用 DCT，而是首先對行使用兩個一維 DCT，然後再對列使用。
一些編解碼器支援替代變換。例如，AVIF 可以使用離散正弦變換代替 DCT。
編解碼器使用快速演算法，如基於蝶形圖的快速 DCT。
變換步驟使用 SIMD 指令進行向量運算最佳化，這讓 CPU 可以用一個命令對多個值應用相同的操作。
DCT 也可以直接在 GPU 上執行。AV1 編解碼器（AVIF 的基礎）支援這一點。

在更高階的編解碼器中，變換可以應用於塊的一部分而不是整個塊。例如，AVIF 允許一個塊被細分（最多兩次）成更小的塊，並對每個子塊分別應用變換。

在這個階段，由於浮點計算中的舍入，會引入一個小的有損誤差。但僅這一步並不會顯著減小檔案大小。

量化

為了準備影像進行壓縮，編解碼器將浮點係數轉換為整數，並用一個特定的數字去除它們。目標是在除法後得到儘可能多的零——資料越少意味著壓縮效果越好。這些數字被稱為量化引數。

在 JPEG 中使用的一組流行的量化值如下所示：

\begin{bmatrix} 16 & 11 & 10 & 16 & 24 & 40 & 51 & 61 \\ 12 & 12 & 14 & 19 & 26 & 58 & 60 & 55 \\ 14 & 13 & 16 & 24 & 40 & 57 & 69 & 56 \\ 14 & 17 & 22 & 29 & 51 & 87 & 80 & 62 \\ 18 & 22 & 37 & 56 & 68 & 109 & 103 & 77 \\ 24 & 35 & 55 & 64 & 81 & 104 & 113 & 92 \\ 49 & 64 & 78 & 87 & 103 & 121 & 120 & 101 \\ 72 & 92 & 95 & 98 & 112 & 100 & 103 & 99 \end{bmatrix}

\begin{bmatrix} 17 & 18 & 24 & 47 & 99 & 99 & 99 & 99 \\ 18 & 21 & 26 & 66 & 99 & 99 & 99 & 99 \\ 24 & 26 & 56 & 99 & 99 & 99 & 99 & 99 \\ 47 & 66 & 99 & 99 & 99 & 99 & 99 & 99 \\ 99 & 99 & 99 & 99 & 99 & 99 & 99 & 99 \\ 99 & 99 & 99 & 99 & 99 & 99 & 99 & 99 \\ 99 & 99 & 99 & 99 & 99 & 99 & 99 & 99 \\ 99 & 99 & 99 & 99 & 99 & 99 & 99 & 99 \end{bmatrix}

這些引數對於亮度和顏色通道是不同的。

量化引數儲存在影像容器中，對於 JPEG，質量取決於我們如何縮放這些引數。係數越大，應用後得到的零就越多。

在更高階的編解碼器中，這個過程要複雜得多。使用專門的演算法來正確地對量化結果進行舍入。此外，可以對不同的塊組應用不同的量化引數，從而使影像不同部分的質量有所不同。

附加內容：交錯

由於不同的係數代表不同層次的細節，因此幾乎可以免費實現交錯（也稱為漸進式渲染）。為此，係數被重新排序，以便具有粗略（基本）細節的係數被首先儲存（和載入）。

結果是，影像以多個細節層次構建，稱為掃描。第一次掃描顯示影像的粗略、通常是模糊的版本。隨後的每次掃描都會逐步新增更多細節。

對於大多數影像格式，這種重新排序不會增加檔案大小，所以這是一個有用的小技巧。但要小心交錯的 PNG——它們使用一種不同的方法，確實會增加檔案大小。

熵編碼

現在我們接近最後一步了，是時候解釋為什麼純色影像比隨機噪聲小這麼多了。原因是熵編碼。

編解碼器獲得量化係數後，下一步是儘可能地縮小二進位制大小。塊的係數按之字形順序掃描，得到的序列使用熵編碼家族中的演算法進行編碼。這個想法很簡單：為出現頻率更高的值使用更少的位元。

讓我們自己嘗試編碼一個基本版本。假設我們有這樣一串數字：

124 124 124 124 10 123 123 1 1 2

第一步是計算每個數字在序列中出現的頻率。

<code class="out"></code>

const vals = "124 124 124 124 10 123 123 1 1 1 2"
  .split(" ")
  .map((e) => parseInt(e, 10));

// count how many times each value appears
const groups = Object.groupBy(vals, (e) => e);

// sort the result, most frequent first
const freqs = Object.entries(groups)
  .map(([key, value]) => [key, value.length])
  .sort((a, b) => b[1] - a[1]);

const out = document.querySelector(".out");
out.innerHTML = freqs.map(([key, value]) => `${key} - ${value}`).join("<br>");

現在我們可以為最頻繁的值分配最短的二進位制程式碼，像這樣：

我們可以只用 24 個位元而不是 88 個位元來編碼這個字串：000011111101101010101110 🎉。這就是 JPEG 實現壓縮的方式。使用的演算法被稱為霍夫曼編碼。

一些編解碼器使用更高階的演算法，如算術編碼或非對稱數字系統。算術編碼允許壓縮更接近理論極限，與霍夫曼編碼相比，實現了更高的壓縮率。

注意： 這個極限由資料的夏農熵定義。它代表了編碼該資料所需的最少位元數。

後處理

有失真壓縮會引入各種失真，因為它移除了高頻分量。這可能導致幾種可見的效果，例如：

塊效應 – 可見的方形圖案，尤其是在平坦區域
邊緣模糊
顏色失真 – 不準確或偏移的顏色
振鈴效應 – 邊緣周圍的光暈或回聲狀圖案
蚊式噪聲 – 邊緣周圍的小閃爍點或嗡嗡聲

A photo of a squirrel with zoomed in parts of the image and labels. The fur on the forehead: blocking. A tip of the ear: blurry edges.

為了減少這些失真，一些編碼器會新增後處理濾波器。這些濾波器由解碼器在重建影像畫素時應用。濾波器的設定儲存在位元組流中，因此解碼器可以在解碼期間讀取並應用它們。

你可能還記得對影像應用高斯模糊來減少噪聲的老技巧。這與此類似，但現代編解碼器使用更高階的演算法。

去塊效應濾波器 – 例如，JPEG XL 中使用的 Gabor 濾波器
維納濾波器 – 用於 AV1 中以減少噪聲
CDEF（約束方向增強濾波器）– 有助於減少振鈴失真

通常，如果使用多個濾波器，它們會形成一個具有精確應用順序的流水線。例如，CDEF 在去塊效應濾波器之後應用。

總結

在本文中，我們探討了影像編碼的工作原理，它與人類感知的聯絡，以及解碼如何從位元中重建影像。大多數編解碼器遵循相同的核心思想，但它們使用不同的方法和技術。它們支援更多的塊大小、額外的預測模式、各種型別的變換、不同的編碼演算法，並且通常包括一個後處理流水線來完善最終影像。

顯而易見的結論是，現代編解碼器更復雜（有時更慢），但它們通常產生更好的結果。然而，“更好”並不總是容易定義。一些問題仍然存在：編解碼器複雜性與輸出質量之間有何權衡？以及在不同情況下，哪些編解碼器效果最好？