利用自適應空間分割進行色彩縮減

演算法說明 • 測量色彩縮減誤差

本文件描述 ImageMagick 如何對影像執行色彩縮減。要完全理解以下內容，您應該具備基本的影像處理技術以及樹狀資料結構和術語的知識。

演算法說明

為了進行色彩分配，影像是一組 n 個像素，其中每個像素都是 RGB 空間中的一個點。RGB 空間是一個三維向量空間，每個像素 p(i) 由一個有序的三元組定義，表示紅色、綠色和藍色的座標，(r(i), g(i), b(i))。

每個原色分量（紅色、綠色 或 藍色）代表一個強度值，從 0 線性變化到最大值 Cmax，對應於該顏色的完全飽和度。色彩分配定義在 RGB 空間中的一個立方體域上，其相對頂點位於 (0, 0, 0) 和 (Cmax, Cmax, Cmax)。ImageMagick 要求 Cmax >= 255。

該演算法將此域映射到一棵樹，其中每個節點代表該域內的一個立方體。在以下討論中，這些立方體由兩個相對頂點的座標定義：RGB 空間中最靠近原點的頂點和距離原點最遠的頂點。

樹的根節點代表整個域，從 (0,0,0) 到 (Cmax, Cmax, Cmax)。樹中的每個較低層級都是透過將一個節點的立方體細分為八個大小相等的較小立方體而生成的。這相當於使用穿過每條邊中點的平面將父立方體一分為二。

基本演算法分為三個階段

1. 分類
2. 縮減
3. 分配

分類

分類階段為影像建立一個色彩描述樹。縮減階段則將樹收合，直到它表示的數量最多為輸出影像中所需的顏色數量。分配階段定義輸出影像的調色盤，並透過在縮減後的樹中重新分類來設置每個像素的顏色。我們的目標是最小化原始顏色和量化顏色之間的數值差異。要瞭解更多有關量化誤差的資訊，請參閱測量色彩縮減誤差。

分類階段首先初始化一個深度足以在葉節點中表示每個可能輸入顏色的色彩描述樹。然而，對於實際的 Cmax 值，在分類階段生成一個完全形成的色彩描述樹是不切實際的。如果輸入影像中的顏色分量以 k 位元精度量化，則 Cmax = 2^k-1，樹需要在根節點下方有 k 個層級，才能在葉節點中表示每個可能的輸入顏色。這變得不可行，因為樹的節點總數

total nodes = 1+Sum(8^i), i=1,k

For k=8,
nodes = 1 + (8^1+8^2+....+8^8)
      = 1 + 8(8^8 - 1)/(8 - 1)
      = 19,173,961 

因此，為了避免建立一個完全填充的樹，ImageMagick

1. 僅在需要時才初始化節點的資料結構；
2. 選擇樹的最大深度作為輸出影像中所需顏色數量的函數（目前為 Cmax 的 以 2 為底的對數）。

For Cmax=255,
maximum tree depth = log2(256)
                   = 8 

這種深度的樹通常可以用最快的計算速度和最少的記憶體來最佳地表示原始影像。然而，預設深度對於某些影像並不適用。因此，呼叫者可以請求特定的樹深度。

對於輸入影像中的每個像素，分類階段會從色彩描述樹的根節點向下掃描。在樹的每個層級，它都會識別表示包含像素顏色的 RGB 立方體的單一節點。它會更新每個此類節點的以下資料

n1

顏色包含在此節點表示的 RGB 立方體中的像素數量；

n2

樹中較低深度節點中未表示顏色的像素數；最初，對於除樹葉之外的所有節點，n2=0。

Sr、Sg、Sb

未在較低深度分類的所有像素的 紅色、綠色 和 藍色 分量值的總和。這些總和與 n2 的組合最終將表徵此節點所代表的一組像素的平均顏色。

E

節點中包含的每個像素與節點中心的 RGB 空間距離平方。這表示節點的量化誤差。

縮減

「縮減」會重複修剪樹，直到 n2 > 0 的節點數小於或等於輸出影像中允許的最大顏色數。在樹的任何給定迭代中，它會選擇那些 E 值最小的節點進行修剪，並將其顏色統計信息向上合併。它使用修剪閾值 Ep 來控制節點選擇，如下所示

Ep = 0
while number of nodes with (n2 > 0) > required maximum number of colors
   prune all nodes such that E <= Ep
   Set Ep  to minimum E in remaining nodes 

這具有在合併兩個節點時最小化任何量化誤差的效果。

當要修剪的節點具有子節點時，修剪程序會遞迴調用自身，以便從葉節點向上修剪樹。被修剪節點中的 n2、Sr、Sg 和 Sb 的值始終會添加到該節點父節點中的相應數據中。這會保留修剪節點的顏色特性以供稍後平均。

對於每個節點，存在 n2 個像素，該節點表示包含這些像素顏色的 RGB 空間中的最小體積。當 n2 > 0 時，節點將唯一地定義輸出影像中的顏色。在縮減開始時，對於除表示輸入影像中存在的顏色的樹葉之外的所有節點，n2 = 0。

另一個像素計數 n1 表示節點所代表的立方體積內的顏色總數。這包括 n1 - n2 個像素，其顏色應由樹中較低級別的節點定義。

分配

「分配」從修剪後的樹生成輸出影像。輸出影像由兩部分組成

1. 顏色映射，它是輸出影像中存在的每種顏色的顏色描述（RGB 三元組）數組。
2. 像素數組，它將每個像素表示為顏色映射數組中的索引。

首先，「分配」階段對修剪後的顏色描述樹進行一次遍歷，以建立影像的顏色映射。對於每個 n2 > 0 的節點，它將 Sr、Sg 和 Sb 除以 n2。這將產生在此節點以下未分類的所有像素的平均顏色。這些顏色中的每一種都成為顏色映射中的一個條目。

最後，「分配」階段會對修剪後的樹中的每個像素重新分類，以識別包含像素顏色的最深節點。像素數組中的像素值成為此節點平均顏色在顏色映射中的索引。

經验证據表明，與 RGB 空間中的距離相比，YUV 或 YIQ 等顏色空間中的距離更接近於感知顏色差異。這些顏色空間在對影像進行顏色縮減時可能會產生更好的結果。這裡的算法如上所述，只是每個像素都是替代顏色空間中的一個點。為了方便起見，顏色分量被標準化到 0 到最大值 Cmax 的範圍內。然後可以如上所述進行顏色縮減。

測量顏色縮減誤差

根據影像的不同，顏色縮減誤差可能很明顯，也可能不可見。具有高空間頻率的影像（例如頭髮或草地）顯示的誤差遠小於具有大片平滑陰影區域的圖片（例如面部）。這是因為顏色縮減過程引入的高頻輪廓邊緣被影像中的高頻掩蓋了。

為了衡量原始影像與減色後影像之間的差異（總減色誤差），ImageMagick 會將影像中所有像素在 RGB 色彩空間中，每個原始像素值与其減色後值的距離平方加總起來。ImageMagick 會列印多種誤差測量值，包括每個像素的平均誤差、標準化平均誤差和標準化最大誤差。

標準化誤差測量值可用於比較影像。一般而言，平均誤差越接近零，量化後的影像就越接近原始影像。理想情況下，誤差的評估應以人眼感知為準，因為人眼才是量化品質的最終評判者。

當在 magick 命令列中指定 -colors 和 -verbose 選項時，就會測量並列印這些誤差值。