色彩量化

在電腦圖學中，色彩量化或彩色圖像量化是應用於色彩空間的量化；這是一個減少圖像中使用的不同顏色數量的過程，通常是為了使新圖像在視覺上儘可能與原始圖像相似。自 1970 年代以來，人們一直在研究對點陣圖執行色彩量化的電腦演算法。色彩量化對於在通常由於記憶體限制而只能顯示有限數量顏色的設備上顯示具有多種顏色的圖像至關重要，並且可以有效壓縮某些類型的圖像。

「色彩量化」這個名稱主要用於電腦圖形學研究文獻；在應用程式中，使用諸如優化調色板生成、最佳調色板生成或降低顏色深度等術語。其中一些具有誤導性，因為標準演算法生成的調色板不一定是最優的。

## 演算法

大多數標準技術將色彩量化視為三維空間中聚類點的問題，其中點代表原始圖像中的顏色，三個軸代表三個顏色通道。幾乎任何三維聚類演算法都可以應用於色彩量化，反之亦然。在定位簇之後，通常對每個簇中的點進行平均以獲得該簇中所有顏色映射到的代表顏色。三個顏色通道通常是紅色、綠色和藍色，但另一種流行的選擇是Lab 顏色空間，因為在這空間下歐氏距離更能夠感知差異。

迄今為止最流行的色彩量化演算法是 Paul Heckbert 於 1979 年發明的中值切割演算法。目前使用的許多演算法都是該方案的變體。在此之前，大多數色彩量化是使用population algorithm或population method完成的，其本質上是建立一個等大小範圍的直方圖，並將顏色分配給包含最多點的範圍。一種更現代的流行方法是使用八叉樹進行聚類，該方法首先由 Gervautz 和 Purgathofer 構思，並由Xerox PARC研究員Dan Bloomberg改進。

<image>

｜

<image>

如果調色板是固定的，就像作業系統中使用的實時色彩量化系統中經常出現的情況一樣，色彩量化通常使用「直線距離」或「最近顏色」演算法來完成，該演算法簡單地採用每個原始圖像中的顏色並找到最近的調色板條目，其中距離由三維空間中兩個對應點之間的距離確定。換句話說，如果顏色是$(r_1, g_1, b_1)$和$(r_2, g_2, b_2)$，我們想要最小化歐氏距離：

$$\sqrt{(r_1-r_2)^2 + (g_1-g_2)^2 + (b_1-b_2)^2}.$$

這有效地將顏色立方體分解為Voronoi 圖，其中調色板條目是點，單元格包含映射到單個調色板條目的所有顏色。計算幾何中有有效的演算法來計算 Voronoi 圖並確定給定點落在哪個區域；在實踐中，索引調色板太小了，以至於它們通常是矯枉過正的。

<image>

色彩量化經常結合抖色一起運用，這可以消除令人不快的偽像，例如量化平滑漸變時出現的條帶，並提供大量顏色的外觀。一些現代色彩量化方案往往是圖將調色板選擇與抖色整合為單一階段，而不是單獨執行它們。

另有其他一些較少見的方案，它們採取完全不同的作法。Local K-means 演算法由 Oleg Verevka 於 1995 年構思，設計用於窗口系統，其中一組核心的「保留顏色」被固定供系統使用，許多具有不同配色方案的圖像可能同時顯示。它是一種後聚類方案，對調色板進行初步猜測，然後迭代地對其進行細化。

在色彩量化的早期，k-means 聚類演算法因其較高的算力要求和對起始資料的敏感性而被認為是不切實際。2011 年，M. Emre Celebi 重新研究了 k-means 作為色彩量化器的性能。他證明了 k-means 的有效實現優於大多數的色彩量化方法。

高質量但速度較慢的NeuQuant演算法通過訓練Kohonen 神經網路將圖像減少到 256 種顏色，「該網路通過學習自組織以匹配輸入圖像中的顏色分布。獲取每個神經元在 RGB 空間中的位置會給出一個高質量的顏色圖，其中相鄰顏色相似。」這對於具有漸變的圖像特別有利。

最後，一種較新的方法是空間色彩量化，由波恩大學的 Puzicha、Held、Ketterer、Buhmann 和 Fellner 構想，它將抖色與調色板生成和簡化的人類感知模型相結合，即使對於很少的顏色。它並不嚴格地將調色板選擇視為聚類問題，因為原始圖像中附近像素的顏色也會影響像素的顏色。請參閱 示例圖像。

## 歷史與應用

在 PC 的早期，由於顯示記憶體的限制，顯示卡通常只支持 2、4、16 以至於 256 色；比起呈現更多顏色，開發商更願意將記憶體用在更多像素（更高解析度）的顯示。色彩量化有助於證明這種權衡的合理性，因為它可以在 16 色和 256 色模式下以有限的視覺降級顯示許多高彩色圖像。在 256 色顯示模式下查看高色彩圖像時，許多作業系統會自動執行量化和抖色處理，這在僅限於 256 色模式的影片設備占主導地位時非常重要。現代電腦現在可以同時顯示數百萬種顏色，遠遠超過人眼所能分辨的顏色，因此主要將此應用程式限制在行動裝置和舊硬體上。

如今，色彩量化主要用於GIF和PNG圖像。GIF 一直以來都是全球資訊網上最流行的無損動畫點陣圖格式，但其最多只支持 256 色，因而大多數圖像都須經過量化。一些早期的網路瀏覽器限制圖像使用稱為網路顏色的特定調色板，導致與最佳優化的調色板相比有更大程度的顏色失真。PNG 圖像支持 24 位顏色，但通常可以通過應用色彩量化使文件大小變得更小而不會犧牲太多視覺效果，因為 PNG 格式對調色圖像使用的每像素位數更少。

相機鏡頭所能呈現的無數種顏色是不可能在電腦螢幕上顯示出來的；因此將任何照片轉換為數位的過程中必然涉及一些量化。實際上，24 位顏色已相當豐富，可以表示人類可感知的幾乎所有顏色，並且在可用顏色空間內具有足夠小的誤差，在視覺上完全相同（如果忠實呈現）。然而，無論是在相機檢測器中還是在螢幕上，顏色的數字化必然會限制可用的顏色空間。因此，無論使用多少位來表示顏色，都有許多顏色可能無法再現。例如，在典型的 RGB 色彩空間（電腦顯示器上常見）中就無法完全再現人眼所能感知的全部綠色。

由於早期電腦上可用的顏色很少，不同的量化算法會產生非常不同的輸出圖像。因此，大量時間花在編寫複雜的演算法上，以使其更逼真。

### 用於圖像壓縮的色彩量化

許多影像檔案格式都支持索引色。

整個圖像調色板通常為整個圖像選擇 256 種「代表性」顏色，其中每個像素引用調色板中的任何一種顏色，如 GIF 和 PNG 文件格式。

區塊調色板通常為每個 4x4 像素塊選取 2 或 4 種顏色，用於BTC、 CCC、 S2TC和S3TC。

### 編輯器支持

許多位圖圖形編輯器包含對色彩量化的內置支持，並且在將具有多種顏色的圖像轉換為具有較少顏色的圖像格式時會自動執行它。這些實現中的大多數都允許用戶準確設置所需顏色的數量。此類支持的示例包括：

- Photoshop 的模式→索引顏色功能提供了許多量化演算法，從固定的 Windows 系統和 Web 調色板到專有的本地和全局演算法，用於生成適合特定圖像的調色板。
- Paint Shop Pro 在其顏色→減少顏色深度對話框中提供三種標準色彩量化演算法：中值切割、八叉樹和固定的標準「網路安全」調色板。
- 在 GIMP 2.8 中，Convert Image to Indexed Colors 選項（Image → Mode → Indexed..）允許生成最佳調色板，可選擇 2 到 256 種顏色，使用 web 優化調色板的選項，使用黑白調色板（1 位）或使用自定義調色板。它允許從調色板中刪除未使用的顏色，並提供多種抖動選項：無、Floyd-Steinberg（正常）、Floyd-Steinberg（減少顏色滲色）和定位以及啟用透明度抖動的能力。

色彩量化也用於創建色調分離效果，儘管色調分離的目標略有不同，即儘量減少同一色彩空間中使用的顏色數量，並且通常使用固定的調色板。

一些矢量圖形編輯器還利用色彩量化，特別是光柵到矢量技術，這些技術在邊緣檢測的幫助下創建位圖圖像的描摹。

- Inkscape 的Path→Trace Bitmap: Multiple Scans: Color函數使用八叉樹量化來創建顏色軌跡。

## 也可以看看

- 索引顏色
- 調色盤 (電腦圖形學)
- 軟體調色板列表#自適應調色板部分。
- 抖動 (數位訊號處理)
- 量化 (圖像處理)
- 圖像分割

## 延伸閱讀

- 保羅·S·赫克伯特。幀緩衝器顯示的彩色圖像量化。ACM SIGGRAPH '82 論文集。首次發布中值切割演算法。
- 丹布隆伯格。使用八叉樹進行色彩量化。輕音。
- 奧列格·韋列夫卡。Windows 系統中使用局部 K 均值演算法的彩色圖像量化。95 年西方電腦圖形學研討會論文集。
- J. Puzicha、M. Held、J. Ketterer、JM Buhmann 和 D. Fellner。關於彩色圖像的空間量化。（全文 .ps.gz）技術報告 IAI-TR-98-1，波恩大學。1998.