顏色量化算法

顏色量化是利用人眼對顏色的惰性，將原圖像中不太重要的相似顏色合併為一種顏色，減少圖像中的顏色，而使量化前後的圖像對於人眼的認識誤差最小，即量化誤差最小。顏色量化是數字圖像處理的基本技術之一，傳統的量化算法有分割法和聚類法。

基本介紹

• 中文名：顏色量化算法
• 外文名：Color quantization algorithm
• 所屬學科：IT
• 所屬領域：圖像編輯

背景

現代計算機中表示圖像最常用的顏色空間是RGB,真彩色圖像三個顏色分量各有一個位元組 8 位表示，因此一個 點的空間需要三個位元組表 示， 一個1024×768的真彩圖像需要1024×768×3=2.25 MB。這樣大的空間在早期計算機上是一筆很大開銷，即使在一些記憶體空間相對小的環境中，比如手機，也顯龐大。因此，人們發明了調色板，即用一個表格存放圖像中的所有顏色，而實際圖像數據不再是 RGB 數據，而是RGB數據在那個表格中的索引，為了控制索引大小，一般這個表格大小要求小於 256 個元素，即一個位元組表示的範圍，這個位元組就可以表示這個圖像中一個點的顏色。如果表格更小，一個點所用的索引位數就更小，這樣1024 ×768 真彩圖像256色調色板僅需要1024×768×3=768.8KB。顏色量化過程往往要使用到兩類調色版，一類是真彩色或者偽真彩色圖像量化到調色板圖像；另一類是調色板圖像繼續量化，將 256 色量化到16色在早期遊戲行業非常普遍 。隨著計算
機存儲容量的不斷提升，調色板圖像逐漸淡出了個人計算機的舞台，但是在手機等一些特種設備中套用依然十分廣泛，尤其是在手機遊戲套用中。伴隨著計算機的發展，顏色量化技術也得到不斷地更新。顏色量化勢必導致圖像中的色彩空間減小，比如：真彩色RGB占一個位元組，色彩空間是256×256×256 =16777216 種顏色，而如果是調色板，最多是 256 種顏，顯然差距很大。而顏色量化目的就是要使這么大的差距對於人眼認識的差距減小到最小。

隨著計算機技術的不斷發展，圖形圖象的處理已廣泛套用於工業、農業、軍事、醫學、管理等各個領域。通過彩色掃瞄器、攝象機等設備，可採集到自然界色彩斑斕的原始圖象。而用計算機來顯示時，由於顯示設備所提供的能力和經濟的原因，可表示的顏色數目總是有限的。另 一方面 ，不同的計算機設備條件可顯示的顏色數目往往不同，而同一幅圖象我們希望在較低檔次的機器設備條件下得到較好的再現。面臨的問題是如何利用設備能力可提供的有限色彩數，儘可能完美再現其原圖象的色彩效果，這就是顏色量化的目的所在。

其問題實質是: 在只有顏色數為K的調色板上，如何選擇K種顏色為代表值設定彩色調色板，以便利用它顯示一幅顏色數量超過調色板顏色數量K的圖象。

常用方法

統一量化 ( uniform quantization )方法

這種方法對色彩空間進行劃分，挑選一組均勻分布紅藍綠成分的色彩表顏色。最簡單的表示方法是：首先分離RGB空間，使之在每一維上分成相等的片，用每個原色色彩層的相交體，產生多種基本原色的代表色，這樣可選出一組用途廣泛的顏色。最典型的情況是K為256，顯 示器有8個位面。考慮到人眼對不同顏色的敏感度，將空間中的紅軸、綠軸各分3個位面，藍軸分2個位面，這樣紅色8種、綠色8種、藍色4種，可組合得到8×8×4= 256種色彩。採用這種統一量化方法，一幅圖象選擇顏色值通過捨入某些成分而得到近似表示。這種方法使用顏色固定定義的調色板，而不是根據圖象內容選擇調色板，使得採用色彩表中有限色彩值與要顯示圖象色彩無關。由於現實中一幅圖片裡並不是包含均勻分布的所有色彩，這樣，統一量化儘管方法簡單、速度快，但實際圖象中微妙變化的層次感不能描述。

頻度序列 ( popularity algorithm)算法

頻度序列法又叫多數法。通過掃描圖象，統計圖象中所出現顏色種類數目和每種顏色出現的頻度次數，挑選其中出現頻率最高的K種顏色，其餘顏色按最小距離準則映射到調色板中。圖象中一般小亮點只覆蓋幾個象素，此顏色值在圖象中不具有足夠的代表性而不被選中，使得類如綠色草原中一朵小紅花的紅色點著色不正確。這種方法思想簡捷、算法規整、存儲量大 ,但 由於某些顏色出現頻率低而被丟失，使圖象顯示失真，效果不夠理想。

中位切割 ( mediano_ cut algorithm)算法

中位切割法簡稱中分法，試圖選擇一個色彩均衡的集合來表示圖象，其基本思想是：把色彩空間正方體分成 K個包含相等數量色素的長方體，可採用每個長方體的中心點就代表了對每一種色彩表顏色的選擇方法。具體做法是，每次將cube外圍不包含象素的無用部分切除，並沿其最長邊做一中位切割，即按此邊上所有值的有序表里取中值切割，原一個cube變成了兩個包含等量象素的小 cube，如此重複進行，直到色彩空間被分成 K個包含大致相同色素的長方體為止，每個長方體的中心點就是一個調色板顏色的最佳位置。在立方體的點密集區域，將有更多的長方體從而相應的有更多的調色板顏色處於其中；哪兒點稀少，調色板顏色也稀少。沒有哪種顏色會被忽略，但出現更頻繁的顏色將得到優先處理。這種算法考慮到具體圖象的色彩分布，所得到的圖象顯示層次感豐富，較為常用。

八叉樹量化 ( octree algorithm)方法

八叉樹量化方法順序讀入圖象檔案，其中先被讀入的前K種不同色彩表初值。一旦出現超過K種色彩的新顏色時，則將顏色色彩相近且出現頻率小的色彩歸併，以保證色彩數目不超過K。在這種方法中，藉助於八叉樹實現代表色彩選擇，每當處理源圖象檔案中的一個新色彩時，其顏色數目小於K，就在色彩八叉樹上插入一新葉子結點。若顏色數超過K，則在八叉樹上進行相鄰色彩歸併運算，以減少葉子結點數目，保證其葉子結點數目不超過K。八叉樹量化方法可分為三個步驟：

① 對源圖象檔案掃描一遍，建立一棵深度為8、有 K個葉子的色彩八叉樹。

② 對色彩八叉樹遍歷，可得到K個葉子結點組成的色彩表，建立色彩表與八叉樹的聯繫。

③ 再對源圖象檔案進行掃描，把每一個象素點映射到色彩表代表色上，產生一個新的目標圖象檔案。

由源圖象檔案對應產生了目標圖象檔案和色彩表。