JPEG - 構思與實踐/變換和量化

餘弦變換

使用 YCbCr 色彩表示方法，我們可以說圖片是由三張圖片組成的，其中第一張比另外兩張更重要。這三張圖片被稱為圖片的分量：Y 分量，Cb 分量和 Cr 分量。但是我們可以繼續這個過程，獲得更多重要的和更不重要的元素。假設我們有一張灰度圖片，那麼我們可以想象從一張只有一色的圖片開始，即圖片中所有顏色平均值的顏色，然後透過新增引入越來越多的變化，直到最後得到完整的圖片。然後可能結果是，我們可以忽略最後的一些操作，因為我們無法區分新的新增部分。然而，顏色函式的擴充套件（我們心中所想）在由重要性越來越小的項組成的一系列項中，只對二次圖片有效。因此，我們的圖片必須分成正方形。這些正方形必須相當小，因為計算次數隨正方形邊長的四次方增長，這意味著如果將小正方形增大一倍，計算次數將增大四倍。另一方面，如果小正方形太小，則程式的效果會減弱。小正方形的最佳邊長似乎是 8-12 畫素。在 JPEG 中，圖片被分成 8x8 的正方形，但在這裡我們將看到如果我們讓正方形的邊長與 8 不同會發生什麼：我們已經安排了程式，以便我們可以選擇 2、3、...、24 中的任意一個數字作為邊長 s。

因此，我們對圖片進行規則的 sxs 正方形劃分。在 JPEG 中，這是從左上角開始，從左到右逐行，從上到下進行，就像我們閱讀文字一樣。然而，在我們的理論演示程式中，我們將以另一種方式遍歷圖片，即從左到右逐列，以鋸齒形上下移動，這樣正方形始終有一條公共邊。我們將假設圖片的寬度和高度可以被 s 整除，或者更確切地說：我們只使用圖片中位於最大區域（從左上角開始）內的部分，該區域可以被規則地分成 sxs 的正方形。我們用來擴充套件正方形內顏色函式的方法是離散餘弦變換 (DCT)，定義如下。

我們假設我們有一個邊長為 N 的二次圖片（灰度），並且我們假設 N 很大，以便我們可以談論“真實”的圖片。這張圖片是一個 NxN 的顏色值矩陣（位元組）：f(i, j), i, j = 0, 1, ..., N-1（記住 (0, 0) 對應於左上角，因此縱座標 j 向下測量）。我們想用純雙振盪的形式表達 f(i, j)，例如 f_{u, v}(i, j) = c(i, u) ∙ c(j, v), u, v = 0, ..., N-1，其中函式 c(i, u) 由下式給出

$c(i,u)=\cos {\frac {(2i+1)u\pi }{2N}}$

請注意，f_{0, 0}(i, j) 是常數 1，函式 f_{u, v}(i, j) 的振盪幅度越大，u 或 v 越大。因此，我們想將 f(i, j) 表達為 N² 個項的雙重求和

$f(i,j)=\sum _{u=0}^{N-1}\sum _{v=0}^{N-1}h(u,v)\cdot c(i,u)\cdot c(j,v)$

其中 h(u, v) 是（實數）係數。第一個項（u = 0 和 v = 0）是一個常數函式，是 N² 個數字 f(i, j) 的平均值。後面的項（作為 i 和 j 的函式）的振盪越來越大，如果我們省略最後的一些項，我們就會得到一個沒有最高頻率的 f(i, j) 近似值。

我們可以用以下方法找到 f(i, j) 的這個級數表示式中的係數 h(u, v)。設 NxN 矩陣（實數）g(u, v)（u, v = 0, 1, ..., N-1）定義為

$g(u,v)={\frac {2\lambda (u)\lambda (v)}{N}}\sum _{i=0}^{N-1}\sum _{j=0}^{N-1}c(i,u)\cdot c(j,v)\cdot f(i,j)$

其中 λ(u) 在 u ≠ 0 時為 1，在 u = 0 時為 1/√2。矩陣 g(u, v) 被稱為矩陣 f(i, j) 的（正向）離散餘弦變換 (DCT 或 FDCT)。請注意，g(0, 0) 是顏色值的平均值的 N 倍。有一個公式，從 NxN 矩陣 g(u, v) 中，可以將我們帶回原始的 NxN 矩陣 f(i, j)，並且它具有類似的外觀

f(i, j) = (2/N)∑_{u, v = 0, ..., N-1}λ(u)λ(v) ∙ c(i, u) ∙ c(j, v) ∙ g(u, v)

$f(i,j)={\frac {N}{2}}\sum _{u=0}^{N-1}\sum _{v=0}^{N-1}\lambda (u)\cdot \lambda (v)\cdot c(i,u)\cdot c(j,v)\cdot g(u,v)$

由於這個公式具有 f(i, j) 級數展開的所需形式，因此我們看到展開是可能的，並且係數 h(u, v) 由 h(u, v) = (2λ(u)λ(v)/N) g(u, v) 給出。這個從 g(u, v) 中獲得 f(i, j) 的公式被稱為逆離散餘弦變換 (IDCT)。

如果我們假設這個公式是正確的，那麼這兩個公式是彼此的逆公式，其中 α 和 β 是奇數整數

${\frac {1}{2}}\sum _{u=0}^{N-1}\cos {\frac {\alpha u\pi }{2N}}{\frac {\beta u\pi }{2N}}=0\;\;for\;\alpha \neq \beta \;and\;{\frac {N}{2}}for\;\alpha =\beta$

現在讓我們設定 N = 280，例如，這樣我們考慮一個 280x280 畫素的（灰度）影像。我們轉換顏色值 f(i, j)（它們是位元組），並且從轉換後的值 g(u, v)（四捨五入到可以為負的整數）中，我們構建一個影像，現在是彩色的，因為數字變化很大，因此不能用位元組來衡量。新影像（也是 280x280 畫素）可能看起來像左側的影像

• 
  餘弦變換後的影像
• 
  重建後的影像

在變換之後，“顏色”值（在這個例子中）從大約 -6000 到 24000 不等，並且顏色化是透過一個小技巧來實現的：我們從這些值中減去了最小值，使其變為非負值，乘以 (max - min)/65535 並四捨五入，得到從 0 到 65535 = 256² - 1 的整數。這個區間內的整數可以寫成 a + 256xb 的形式，其中 a 和 b 是位元組，並且我們可以將它們與 RGB 三元組 (0, b, a) 關聯，例如（最小值和最大值必須在重建影像的程式中引入，但這可以透過將它們寫入 BMP 檔案頭中的某些空閒條目來完成）。上面的右側影像是重建後的影像。

如果在重建過程中，我們刪除 u > N/2 或 v > N/2 的項，這樣我們只利用四分之一的項，我們會得到一張幾乎和原始影像一樣的影像 - 只是一點模糊

• 
  所有項
• 
  四分之一的項

但是，在 JPEG 過程中，項實際上並沒有被刪除：係數被近似值所取代，其中高頻係數的近似值比低頻係數的近似值偏離原始係數更多。就是這樣量化過程執行的。

現在對於被分成 sxs 方塊的（彩色）影像。在餘弦變換之後，我們每個 sxs 方塊和每個分量（彩色影像）都有 s² 個數字。從這些數字中，我們可以重建影像，而且正是這些數字我們要在壓縮後寫入檔案。但是，如果我們沒有量化就這樣做（也就是說，沒有以某種方式使數字在數值上更小），那麼餘弦變換將一無所獲。除了下面要解釋的量化之外，我們還可以做另一件事，它可以使一些值變小，並且效果很好：我們可以用每個變換值的第一項（平均值 g(0, 0)）與其前面相同型別的第一項（即，對於同一分量的先前方塊）的差異來替換。矩陣 g(u, v) （u, v = 0, ..., s-1）的第一項 g(0, 0) 稱為 *DC* 項，而其他 s²-1 項，g(u, v)，u > 0 或 v > 0，稱為 *AC* 項。因此，我們用每個 DC 項（對於給定的 sxs 方塊和分量）與其前一個 sxs 方塊（以及同一個分量）的 DC 項的偏差來替換它。

量化

如果沒有量化過程，唯一的資訊丟失來源將是四捨五入實數以獲得整數。由於平均數 (g(u, v) 對於接近 0 的 u 或 v) 相當大，因此這些誤差並不顯著：如果我們現在製作檔案（即，使用餘弦變換，但沒有量化），並應用壓縮過程（它是無損的），那麼我們可以從檔案中重建的影像將幾乎無法與原始影像區分，但它仍然會佔用太多空間。正是量化過程縮小了尺寸並引入了偏差。透過量化，我們理解的是，將 f(i, j) 在純雙重振盪中的展開係數，即來自餘弦變換的數字 g(u, v)，透過除以取決於 (u, v) 的數字 q(u, v) 然後四捨五入到整數來使其更小。當從檔案中繪製圖像時，我們會乘以我們除以的數字。例如，如果 g(u, v) = 135.6 除以 q(u, v) = 36，結果被四捨五入，我們得到 4，當我們用 36 乘以 4 時，我們得到 144。然後我們引入了可能無關緊要的誤差，因為它們不是顏色值中的誤差，而是在餘弦變換後的數字中的誤差，並且主要項，即對於接近 0 的 u 和 v 的 g(u, v)，被比不太重要的項，即對於不接近 0 的 u 或 v 的 g(u, v)，小得多的數字 q(u, v) 量化。此外，由於 Y 分量的數字比來自 Cb 和 Cr 分量的數字更重要，因此這些數字的餘弦變換後的數字可以被更大的數字 q(u, v) 量化。

JPEG 過程中使用的 Y 分量和兩個顏色分量的 8x8 矩陣 q(u, v) (u, v = 0, ..., 7) 是根據實驗選擇的。因此，有幾種這樣的表格。精心選擇的數字意味著我們可以壓縮更多，而不會損壞影像，但我們總是會遇到影像的一部分有令人不安的缺陷，這迫使我們選擇更小的量化值。通常情況下，一個 *質量因子* qf 會被引入到製作檔案的程式中，以便可以調整量化數字。例如，我們可以安排這種依賴關係，以便最佳質量 - qf = 100 - 意味著沒有量化（所有量化數字都被設定為 1），而 qf = 75 意味著使用給定的量化表 q(u, v)。量化表 q(u, v) 和質量因子 qf 在從檔案中繪製圖像時再次應用。當然，質量因子必須出現在檔案頭中，而表格只需要出現在生成檔案和繪製圖像的程式中。

在我們的程式中，我們必須有針對不同的小方塊邊長（從 2 到 24）的量化表，因此我們必須用數學方法構建這些表 - 儘可能簡單。我們首先選擇 qf = 75 的 q(u, v) 值，然後找到一個公式，以便所有這些值在 qf = 100 時都變為 1。根據 *第二部分* 中顯示的表格，對於 qf = 75，我們為邊長 s 以及 Y 分量和顏色分量分別選擇以下值

q(u, v) = (s/8)∙12∙(1 + 4∙√(u² + v²)/ s)

q(u, v) = (s/8)∙20∙(1 + 5∙√(u² + v²)/ s)

我們安排程式，以便我們可以對 Y 分量和顏色分量使用不同的質量因子。我們根據 qf 調整數字 q(u, v)，方法如下

q(u, v)^{√(100 - qf)/5}

下面的左側影像（對於邊長 s = 8）沒有量化 (qf = 100)，檔案佔原始 BMP 檔案的 60%。在右側影像中，qf = 70，檔案現在只佔原始檔案的 6%

• 
  qf = 100
• 
  qf = 75

當我們將量化表的矩陣和餘弦變換後的量化數字的矩陣放入檔案時，我們必須以某種方式將這些數字線性排列。我們這樣做的方法是，最重要的是（對於接近 0 的 u 和 v）排在最前面，即透過應用這種之字形原理

• 
  之字形原理

如果 s 是正方形的邊長，那麼對應於點 (i, j) (i, j = 0, 1, ..., s-1) 的之字形值 m (= 1, 2, ..., s²) 可以用這個程式計算

k = i + j
if k < s then
	begin
		l = (k * (k + 1)) div 2
		if k mod 2 = 0 then
			m = l + i + 1
		else
			m = l + j + 1
	end
if k = s then
	m = (s - 2) * (s - 2) + i
if k > s then
	begin
		k = 2 * s - 1 - k
		l = s * s - (k * (k + 1)) div 2
		if k mod 2 = 0 then
			m = l + (s - i)
		else
			m = l + (s - j)
	end