顏色量化色彩退化算法

摘 要:顏色量化是利用人眼對顏色的惰性，將原圖像中不太重要的相似顏色合并為一種顏色，減少圖像中的顏色，而使量化前后的圖像對于人眼的認(rèn)識誤差最小即量化誤差最小。在此從揭示八叉樹顏色量化算法的優(yōu)缺點(diǎn)開始，優(yōu)化八叉樹結(jié)構(gòu)，進(jìn)化為以二叉堆和數(shù)組索引數(shù)據(jù)結(jié)構(gòu)，對最不重要顏色不斷地進(jìn)行退化，最終達(dá)到量化要求的顏色數(shù)量。實(shí)踐證明，在相同情況下，二叉堆比八叉樹顏色量化對圖像的量化誤差更小。

關(guān)鍵詞:顏色量化;八叉樹;二叉堆;退化算法

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2010)06-163-05

Degradation of Color Quantization Algorithm

DU Weiwei1，ZHANG Aixia1，QU Chunliu2

(1.Institute of Scientific and Technical Information of China，Beijing，100038，China;2.WAPDN，Beijing，100083，China)

Abstract:Color quantization is to use the human eye on the color of inertia，the original image is similar to the less important colors into a color，then reduce the image color，the images before and after quantization of the human eye that is，the smal-lest error of the minimum quantization error.The octree color quantization algorithm of the advantages and disadvantages of starting to abandon the algorithm octree structure，and evolution to a binary heap data structure and the array index of the most important degradation of color continue to carry out，and ultimately to achieve the volume of the number of colors required，and demonstrate the algorithm code.

Keywords:color quantization;octree;binary heap;degradation

0 引 言

現(xiàn)代計算機(jī)中表示圖像最常用的顏色空間是RGB，真彩色圖像三個顏色分量各有一個字節(jié)8位表示，因此一個點(diǎn)的空間需要三個字節(jié)表示，一個1 024×768的真彩圖像需要1 024×768×3=2.25 MB[1]。這樣大的空間在早期計算機(jī)上是一筆很大開銷，即使在一些內(nèi)存空間相對小的環(huán)境中，比如手機(jī)，也顯龐大。因此，人們發(fā)明了調(diào)色板，即用一個表格存放圖像中的所有顏色，而實(shí)際圖像數(shù)據(jù)不再是RGB數(shù)據(jù)，而是RGB數(shù)據(jù)在那個表格中的索引，為了控制索引大小，一般這個表格大小要求小于256個元素，即一個字節(jié)表示的范圍，這個字節(jié)就可以表示這個圖像中一個點(diǎn)的顏色。如果表格更小，一個點(diǎn)所用的索引位數(shù)就更小，這樣1 024×768真彩圖像256色調(diào)色板僅需要1 024×768×3=768.8 KB[2]。顏色量化過程往往要使用到兩類調(diào)色版，一類是真彩色或者偽真彩色圖像量化到調(diào)色板圖像;另一類是調(diào)色板圖像繼續(xù)量化，將256色量化到16色在早期游戲行業(yè)非常普遍[3]。隨著計算機(jī)存儲容量的不斷提升，調(diào)色板圖像逐漸淡出了個人計算機(jī)的舞臺，但是在手機(jī)等一些特種設(shè)備中應(yīng)用依然十分廣泛，尤其是在手機(jī)游戲應(yīng)用中。

伴隨著計算機(jī)的發(fā)展，顏色量化技術(shù)也得到不斷地更新。顏色量化勢必導(dǎo)致圖像中的色彩空間減小，比如:真彩色RGB占一個字節(jié)，色彩空間是256×256×256=16 777 216種顏色，而如果是調(diào)色板，最多是256種顏色，顯然差距很大。而顏色量化目的就是要使這么大的差距對于人眼認(rèn)識的差距減小到最小。

1 回顧

顏色量化算法發(fā)展到今天，出現(xiàn)了許多不同的算法。最簡單的色彩量化技術(shù)就是直接減少RGB三個顏色分量表示的位數(shù)，通常不使用調(diào)色板技術(shù)，常見方法分別有555分法，565分法和444分法等，統(tǒng)稱為直接量化法[4]，即指RGB三個分量實(shí)際使用的位數(shù)，5+5+5=15，5+6+5=16，都可以用兩個字節(jié)表示，當(dāng)然還有其他的分法。這樣就使顏色空間減少到256×256=65 536種顏色。通常做法是保留顏色分量的高位，去除低位。因為位數(shù)所在位置越高，證明這個位的重要性就越高。這種算法簡單且快速，但是該量化算法沒有選擇性，比較盲目，量化的空間有限，適合在內(nèi)存空間相對大一點(diǎn)的環(huán)境，它通常是其他量化算法的預(yù)處理算法，隱藏于其他算法之中。另外一種顏色量化算法是，選擇圖像中使用最多的顏色作為調(diào)色板顏色，而其他顏色是在這個調(diào)色板中選擇一個最接近的顏色作為原顏色的替換色[5]，這個算法具有選擇性，但是算法本身需要的空間復(fù)雜度比較大，需要對顏色信息(顏色的數(shù)量)進(jìn)行排序，另外替換色的選擇通常會導(dǎo)致圖像失真度比較大，這種算法現(xiàn)在很少使用。本文稱該算法為樸素量化法。

目前常用算法是八叉樹顏色量化算法，該算法比較常用，另外本文在一定程度上也受到該算法的啟發(fā)。八叉樹顏色量化算法是把RGB顏色的8位分布到不同的8層八叉樹結(jié)構(gòu)中，如果加上八叉樹的根節(jié)點(diǎn)，一共九層八叉樹，離根越近表示越重要，越遠(yuǎn)表示越不重要[6]。根節(jié)點(diǎn)一個，第一層有8個節(jié)點(diǎn)，第二層有8×8個節(jié)點(diǎn)，第三層有8×8×8個節(jié)點(diǎn)，依此類推。如果全部構(gòu)建這些節(jié)點(diǎn)，則非常龐大。因此實(shí)際算法有兩點(diǎn)關(guān)鍵優(yōu)化，第一，不全部構(gòu)建這九層，設(shè)置一個閥值L，低于閥值L的更低層在量化過程中將刪除，構(gòu)建它們沒有意義，直接歸并到L層，實(shí)際上就是直接量化法的應(yīng)用;第二，即使是在閥值L層之上，也不全部構(gòu)建，節(jié)點(diǎn)在量化過程中構(gòu)建，只有出現(xiàn)該節(jié)點(diǎn)才構(gòu)建;第三，在量化過程中如果實(shí)際顏色節(jié)點(diǎn)數(shù)超過量化要求的節(jié)點(diǎn)數(shù)，就歸并最底層且最近插入的節(jié)點(diǎn)到其雙親節(jié)點(diǎn)，來減少實(shí)際顏色的節(jié)點(diǎn)數(shù)。因此，對于256色的量化，除根節(jié)點(diǎn)、第一層和第二層節(jié)點(diǎn)外，其他每層最壞也不過256個節(jié)點(diǎn)。這里用C++簡單描述:

struct Node

{

unsigned int pixelCount_ : 31，isLeaf_ : 1;

unsigned int redSum_，greenSum_，blueSum_;

struct Node * next_;

struct Node * children_[8];

};

其中pixelCount_表示這個節(jié)點(diǎn)顏色代表的圖像點(diǎn)的數(shù)量;isLeaf_表示是否為葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)表示實(shí)際量化后的顏色;redSum_/greenSum_/blueSum_表示節(jié)點(diǎn)代碼的RGB顏色值匯總;pixelCount_/isLeaf_和redSum_/greenSum_/blueSum_構(gòu)成顏色節(jié)點(diǎn)信息。next_表示節(jié)點(diǎn)的下一個節(jié)點(diǎn)，主要用于節(jié)點(diǎn)歸并，就是選擇哪個節(jié)點(diǎn)開始?xì)w并，本文不使用該方法，所以這里不展開這個字段的解釋;children_表示它的8個子節(jié)點(diǎn)，這個很容易理解。

下面簡單描述八叉樹顏色量化具體算法步驟:

遍歷所有的圖像點(diǎn)，選擇RGB值代碼的節(jié)點(diǎn)。選擇方法是從RGB三分量中最高位(最重要)開始，每次各取出一位，合成一個數(shù)，三位表示一個數(shù)從0~7，正好是八叉樹子節(jié)點(diǎn)中的一個子節(jié)點(diǎn)。然后是第二層，依此類推，直到最低位，或者到了層數(shù)閥值限制。在選擇過程中如果節(jié)點(diǎn)不存在就創(chuàng)建該節(jié)點(diǎn)，最后一個節(jié)點(diǎn)是葉子節(jié)點(diǎn)，同時把RGB分量分別累加到相應(yīng)分量中。如果新建的葉子節(jié)點(diǎn)導(dǎo)致實(shí)際顏色數(shù)超過量化要求的顏色節(jié)點(diǎn)數(shù)，就要?dú)w并最底層中某個葉子節(jié)點(diǎn)到它的雙親節(jié)點(diǎn)，并將雙親節(jié)點(diǎn)轉(zhuǎn)化為葉子節(jié)點(diǎn)，節(jié)點(diǎn)的顏色分量匯總和顏色點(diǎn)數(shù)匯總累加到雙親節(jié)點(diǎn)。最后把所有葉子節(jié)點(diǎn)各個顏色的平均值作為該節(jié)點(diǎn)的顏色值，并保存目標(biāo)調(diào)色板，遍歷所有圖像點(diǎn)，在調(diào)色板中找到一個最接近該顏色的索引值作為該點(diǎn)的顏色索引值，整個量化過程結(jié)束[9]。這里就不再詳述。

2 退化算法

退化是指顏色的退化，而算法本身是其他算法改進(jìn)而來，是算法的進(jìn)化，色彩退化算法是從樸素量化算法和八叉樹量化算法進(jìn)化而來。直接算法、樸素算法和八叉樹算法有自己固有的優(yōu)缺點(diǎn)。直接算法非常直接，但是量化能力有限;樸素量化算法，需要的算法空間復(fù)雜度等于圖像顏色數(shù)，可能非常大，另外算法比較耗時;八叉樹量化算法的量化過程選擇具有一定盲目性，量化開始于最低層節(jié)點(diǎn)。但是最低層節(jié)點(diǎn)未必是最不重要節(jié)點(diǎn)，它在量化信息不完整的情況下，過早地量化，另外，量化和圖像點(diǎn)遍歷的順序有關(guān)，不同的輸入順序到達(dá)量化開始的時間是不一致的，這樣相同圖像可以輸出不同的量化結(jié)果。色彩退化算法兼有直接算法、樸素算法和八叉樹算法的特性，是幾種常用算法改進(jìn)過來，或者說是進(jìn)化而來。在圖像顏色空間研究領(lǐng)域，最開始人們研究黑白圖像，接著開始有了紅綠藍(lán)，從此顏色開始豐富，細(xì)節(jié)更加精彩。而顏色量化是要減少顏色，減少細(xì)節(jié)，甚至可以退回到黑白世界。這正像是生物的進(jìn)化和退化。而本文顏色量化算法就是要把顏色空間中最不重要的顏色退化回去，回到他進(jìn)化前的顏色，因此取名曰退化算法。

顏色量化實(shí)質(zhì)必然要減少顏色，那減少什么顏色就涉及到顏色的選擇，這其實(shí)也是目前各種顏色量化算法區(qū)別之所在。顏色對于一副圖像來講，從感性上理解，所以得出這樣的結(jié)論，就是顏色出現(xiàn)次數(shù)越多，那么它的重要性也就越高，事實(shí)的確也是這樣，這也是樸素量化算法的核心，這符合人眼對世界的一般認(rèn)識。人眼對顏色的認(rèn)知，是一個不斷學(xué)習(xí)的過程。首先是黑白，然后不斷細(xì)化和豐富，這也是人眼對于形狀認(rèn)識總是先于對顏色的認(rèn)識，人從一生下來就開始認(rèn)識父母的臉，不過他最先認(rèn)識的是形狀，是父母臉的輪廓。那么對于一個RGB顏色來講，RGB中8位顏色數(shù)中是顏色分量最高位最重要，最低位最不重要，這是八叉樹量化算法的關(guān)鍵。有了這兩點(diǎn)，即可知道量化需要處理的方向，就是減少不太重要的顏色，或者把不太重要的顏色合并為一種顏色，從而達(dá)到減少顏色的目的。

針對八叉樹量化算法的過早和盲目性，顯然要推遲量化的時機(jī)，這個是必然，否則將重蹈覆轍，推遲量化，就要增加空間復(fù)雜度，需要更多的空間來保存中間過程。針對樸素量化算法的空間復(fù)雜度，就要減少保存中間結(jié)果，必須提前進(jìn)行量化。這是一對矛盾，就像進(jìn)化和退化，也是一對矛盾，似乎沒有好的解決方法。其實(shí)不然，當(dāng)常規(guī)方法無法解決的時候，就要變相優(yōu)化算法結(jié)構(gòu)，在這里尤其是要優(yōu)化算法的數(shù)據(jù)結(jié)構(gòu)。一般思路是，算法耗時或者耗空間時，使用特別數(shù)據(jù)結(jié)構(gòu)可以加快算法，也可以減少開銷。因此數(shù)據(jù)結(jié)構(gòu)合理地運(yùn)用到算法中，將使簡單的算法也能煥發(fā)精彩。

3 信息采集

解決問題，就和看病吃藥一樣道理，一定要對癥下藥。同一種病，幼兒和成人用藥都不一樣。算法也一樣，都是顏色量化，情況不一樣，使用的數(shù)據(jù)結(jié)構(gòu)也可能不一樣，算法復(fù)雜度也不一樣。前面提到過一種是真彩色或者偽真彩色的量化，這種圖像數(shù)據(jù)保存的是RGB分量值，為了表示方便稱其為TrueColor量化;另外一種是調(diào)色板圖像，圖像數(shù)據(jù)是顏色RGB分量調(diào)色板中的索引，稱其為Palette量化。精細(xì)化的操作，是為了解決算法空間和時間問題。其實(shí)解決這個問題，就是要解決上文中的那一對矛盾。兩種情況數(shù)據(jù)結(jié)構(gòu)的C++描述如下:

template//TrueColor

{

struct Node

{

unsigned int weight_ : 31，leaf_ : 1;

unsigned int r_，g_，b_;

struct Node * parent_;

struct Node * children_[8];

};

Node root_;

Node * weights_;

};

template // Palette

{

struct Node

{

unsigned int key_ : 24，level_ : 8;

unsigned int weight_;

unsigned int r_，g_，b_;

};

enum { maxColorSize = 256 };

Node colors_;

unsigned char keys_;

unsigned char weights_;

};

這樣安排數(shù)據(jù)結(jié)構(gòu)，是為了方便圖像信息采集(顏色點(diǎn)的數(shù)量和顏色RGB三分量的匯總)。對于TrueColor量化，采用八叉樹的數(shù)據(jù)結(jié)構(gòu)，之所以采用八叉樹TrueColor量化顏色數(shù)是未知的，這種顏色節(jié)點(diǎn)數(shù)未知，為了快速且高效的采集圖像信息，八叉樹是非常理想的一種結(jié)構(gòu)，八叉樹通過8組位運(yùn)算就準(zhǔn)確定位到顏色節(jié)點(diǎn)。Palette量化，采用最大256個節(jié)點(diǎn)的數(shù)組，圖像數(shù)據(jù)直接作為數(shù)組的索引，信息的采集非常直接。

回過頭來，比較節(jié)點(diǎn)的細(xì)節(jié)。其中都有weight_，類似八叉樹算法，是該顏色節(jié)點(diǎn)所代表的圖像點(diǎn)數(shù);r_/g_/b是該節(jié)點(diǎn)所代表顏色點(diǎn)的RGB分量匯總。leaf_是TrueColor量化八叉樹結(jié)構(gòu)獨(dú)有的，需要指出節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，因為只有葉子節(jié)點(diǎn)才能最終成為目標(biāo)顏色，而Palette量化數(shù)組結(jié)構(gòu)中的所有節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，因此不需要這個字段。另外八叉樹，還要有它的8個孩子節(jié)點(diǎn)，這個是非常顯然的。而Palette量化的節(jié)點(diǎn)結(jié)構(gòu)也有自己獨(dú)特的字段，它需要知道顏色節(jié)點(diǎn)所在的層數(shù)，所以有l(wèi)evel_字段表示，而八叉樹結(jié)構(gòu)中本身就包含了層的信息。另外，Palette量化節(jié)點(diǎn)結(jié)構(gòu)還有key_，占用24位，涵蓋RGB三個分量，表示所代表的顏色。key的RGB組合順序是精心安排的，類似于八叉樹位運(yùn)算，最高三位有RGB分量的最高位(最重要)組成，接著是RGB分量的次高位，依此類推，直到最低三位有RGB分量的最低位組成，這樣安排是為了算法的排序和顏色分量的退化。算法中keys_數(shù)組就是在key_上建立的升序索引。這樣排序還帶來額外的信息，就是節(jié)點(diǎn)的細(xì)節(jié)(稱之子孫)就在緊挨著它之后的不遠(yuǎn)處，而它本身又是節(jié)點(diǎn)之前不遠(yuǎn)處的某個節(jié)點(diǎn)(稱之為祖先)的細(xì)節(jié)。因此，在完成遍歷圖像點(diǎn)，匯總節(jié)點(diǎn)數(shù)量和RGB分量后，可以高效地檢索量化的節(jié)點(diǎn)、節(jié)點(diǎn)的子孫和祖先。使用索引是出于性能考慮，因為節(jié)點(diǎn)數(shù)組在量化過程中需要刪除節(jié)點(diǎn)，必然造成節(jié)點(diǎn)前移，如果只是移動索引，這個開銷必然要小很多，這是另外一個層面的細(xì)節(jié)。

下面簡單描述圖像信息采集算法:

template//TrueColor

{

a歷圖像顏色點(diǎn)

b重復(fù)8次計算顏色所在節(jié)點(diǎn)

b.1果節(jié)點(diǎn)不存在，則創(chuàng)建它

c得到顏色對于的葉子節(jié)點(diǎn)，累加節(jié)點(diǎn)數(shù)，和RGB顏色分量

};

template // Palette

{

a遍歷圖像顏色點(diǎn)

b據(jù)調(diào)色板得到顏色點(diǎn)對應(yīng)的顏色

c累加到索引對應(yīng)節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)，和RGB顏色分量

};

在TrueColor量化時，類似八叉樹算法，可以在查找節(jié)點(diǎn)過程中應(yīng)用一次直接量化，就是設(shè)置一個層數(shù)閥值，或者說是細(xì)節(jié)(粒度)，比如5或者6，那么就不需要重復(fù)8次計算找節(jié)點(diǎn)了，這樣可以減少一點(diǎn)節(jié)點(diǎn)，從而減少顏色空間，但其也帶來了過早量化的矛盾，實(shí)際應(yīng)用是可以靈活選擇。Palette量化也可以控制粒度，可以通過key_來實(shí)現(xiàn)，但是實(shí)際意義不大。

4 精確量化

前面提到了兩種情況的區(qū)別，是該算法的第一步，信息采集算法還是比較簡單和直觀的。現(xiàn)在，敘述他們的共同特點(diǎn)，也是本文稱之為退化算法的核心。退化是指丟失顏色的細(xì)節(jié)，為了使細(xì)節(jié)丟失最小，就要丟失最不重要的細(xì)節(jié)，而這些細(xì)節(jié)應(yīng)該從更粗的顏色進(jìn)化(細(xì)化)而來，丟掉這些細(xì)節(jié)，就使顏色(退化)到原來的顏色，也許這樣講比較形象。

區(qū)別于八叉樹量化算法的關(guān)鍵是八叉樹量化發(fā)生在信息采集過程中，葉子節(jié)點(diǎn)數(shù)超過量化節(jié)點(diǎn)數(shù)時發(fā)生，在信息采集不完整時就進(jìn)行。而算法量化發(fā)生在所有信息采集完成之后。量化發(fā)生在weight_(w_)最小的節(jié)點(diǎn)，就是顏色數(shù)量最少的節(jié)點(diǎn)，是最不重要的節(jié)點(diǎn)，這符合樸素量化算法，節(jié)點(diǎn)量化是一步步退化到雙親節(jié)點(diǎn)，或者到達(dá)一個量化閥值，這也是本算法的核心之所在。為了便于查找weight_最小節(jié)點(diǎn)，這里采用二叉堆。把所有葉子節(jié)點(diǎn)在weight_上建立一個二叉堆weights_，最小值在根，每次量化都是取出根節(jié)點(diǎn)，這樣就優(yōu)化了查找量化節(jié)點(diǎn)的算法，快速精確地找到量化節(jié)點(diǎn)[10]。

5 量化

顏色量化過程就是不重要顏色節(jié)點(diǎn)不斷退化的過程。從二叉堆中取出節(jié)點(diǎn)，歸并節(jié)點(diǎn)信息到它祖先(雙親)節(jié)點(diǎn)。如果祖先節(jié)點(diǎn)沒有子節(jié)點(diǎn)，就把它標(biāo)定為葉子節(jié)點(diǎn)，并加入二叉堆。直到到達(dá)量化層數(shù)閥值L或者達(dá)到量化要求的顏色節(jié)點(diǎn)數(shù)，或者二叉堆中沒有節(jié)點(diǎn)為止。量化層數(shù)閥值L是用來控制防止過度退化，細(xì)節(jié)丟失太嚴(yán)重而設(shè)置，通常為1或者2;0表示不控制。

下面描述一下量化算法:

template//TrueColor

{

a對于所有葉子節(jié)點(diǎn)，在weight_上建立二叉堆，關(guān)鍵字是weight_，節(jié)點(diǎn)是顏色節(jié)點(diǎn)指針，指向顏色節(jié)點(diǎn)

b如果葉子顏色節(jié)點(diǎn)數(shù)大于量化要求的顏色數(shù)，且二叉堆中還有節(jié)點(diǎn)

b.1取出二叉堆根節(jié)點(diǎn)

b.2確保顏色節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)層數(shù)大于層數(shù)量化閥值L，否則回到b

b.3歸并顏色信息到其雙親節(jié)點(diǎn)

b.4刪除此節(jié)點(diǎn)

b.5如果其雙親節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)了，則把其雙親節(jié)點(diǎn)加入到二叉堆中。

c如果葉子顏色節(jié)點(diǎn)數(shù)大于量化要求的顏色數(shù)，表示量化失敗，需要減小層數(shù)量化閥值L。

};

template // Palette

{

a包所有節(jié)點(diǎn)，根據(jù)key_值升序排序，建立索引

b對于所有葉子節(jié)點(diǎn)，在weight_上建立二叉堆，關(guān)鍵字是weight_，節(jié)點(diǎn)是顏色節(jié)點(diǎn)在數(shù)組中的索引

c如果葉子顏色節(jié)點(diǎn)數(shù)大于量化要求的顏色數(shù)，且二叉堆中還有節(jié)點(diǎn)

c.1取出二叉堆根節(jié)點(diǎn)，其值是顏色節(jié)點(diǎn)數(shù)組的索引，取出顏色節(jié)點(diǎn)

c.2確保顏色節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)層數(shù)大于層數(shù)量化閥值L，否則回到c

c.3確保找到顏色節(jié)點(diǎn)在keys_排序索引的位置j，否則表示節(jié)點(diǎn)已經(jīng)不存在了，回到c

c.4根據(jù)節(jié)點(diǎn)key_值計算它的祖先節(jié)點(diǎn)的key_值

c.5從該節(jié)點(diǎn)j開始在排序索引中往回找到第一個小于祖先節(jié)點(diǎn)key_值的節(jié)點(diǎn)，該節(jié)點(diǎn)的下一個必是要找節(jié)點(diǎn)的祖先節(jié)點(diǎn)i

c.6找到的祖先節(jié)點(diǎn)i的key_值和實(shí)際祖先的key_一致，且i

c.7如果其雙親節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)，則把其雙親節(jié)點(diǎn)加入到二叉堆中。

d如果葉子顏色節(jié)點(diǎn)數(shù)大于量化要求的顏色數(shù)，表示量化失敗，需要減小層數(shù)量化閥值L。

};

TrueColor量化算法還是非常簡單易懂的，而Palette量化則稍顯復(fù)雜，這里展開一下。這里首先是二叉堆，保存的是顏色節(jié)點(diǎn)在數(shù)組中的索引，而二叉堆是建立在weight_基礎(chǔ)上的，因此從二叉堆中取出的是數(shù)組索引，索引顏色節(jié)點(diǎn)數(shù)組中才找到真正的顏色節(jié)點(diǎn)。然后是建立在key_值上的升序索引，保存的也是顏色節(jié)點(diǎn)在數(shù)組中的索引，同樣需要索引顏色節(jié)點(diǎn)數(shù)組中才找到真正的顏色節(jié)點(diǎn)。這樣安排的原因是出于性能考慮，排序索引在整個量化過程中會不斷地調(diào)整移動，移動索引比移動節(jié)點(diǎn)時間和空間復(fù)雜度都要小的多，因為索引只是一個字節(jié)，而顏色節(jié)點(diǎn)達(dá)到了20個字節(jié)。

接著是節(jié)點(diǎn)祖先怎么查找的問題。祖先節(jié)點(diǎn)先對于其子孫該key_值肯定要小，因為子孫除了和祖先有一致的高位信息外，還有更多的低位細(xì)節(jié)。但是在key_的排序索引中，與其子孫最接近的祖先肯定在“緊挨”著它子孫的“不遠(yuǎn)處”，因此只要從子孫開始往回找，找到第一個小于它的祖先key_值索引的下一個索引就可能是它的祖先，或者是它的平輩。再檢查一下確保索引到的顏色節(jié)點(diǎn)key_值和祖先的節(jié)點(diǎn)值一致，且不是開始查找節(jié)點(diǎn)本身，那么就表示找到了j節(jié)點(diǎn)的祖先i，他已經(jīng)存在于顏色節(jié)點(diǎn)數(shù)組中，索引就是i。另外，這里為什么沒有寫孩子的雙親，而是子孫的祖先呢?是因為這個i節(jié)點(diǎn)有可能是跨了多層，比如key_=012300040(八進(jìn)制表示，為了方便表述)，該節(jié)點(diǎn)如果是在第0層，那么它的祖先的key_=012300040，就是它的雙親;如果是在第一層，那么它祖先的key_=012300000，顯然已經(jīng)跨了3代。因此此處用祖先和子孫比雙親和孩子更加精確一點(diǎn)。如果沒有找到子孫的祖先，表示祖先還不在顏色節(jié)點(diǎn)數(shù)組中，此時使這個子孫節(jié)點(diǎn)變成祖先節(jié)點(diǎn)，這樣此后這個祖先的子孫再找它的祖先就比較容易。

最后是怎么去判斷一個祖先是否還有子孫節(jié)點(diǎn)原理和子孫找祖先類似，只是更加簡單。只要判斷計算祖先下一個平輩的key_值，比如還是那個key_=012300040，它在第一層，那么它的下一個平輩就是key_=012300050。如果在排序索引中，存在祖先i的下一個索引j，同時j對應(yīng)的顏色節(jié)點(diǎn)的key_值小于那個祖先的平輩，那么表示祖先至少存在一個子孫j，否則就表示不存在子孫。

6 結(jié) 語

顏色量化之色彩退化算法，是常用顏色量化算法演進(jìn)而來，摒棄缺點(diǎn)，保留優(yōu)點(diǎn)，并加入了二叉堆來精確制導(dǎo)量化節(jié)點(diǎn)，還有排序數(shù)組索引等相關(guān)數(shù)據(jù)結(jié)構(gòu)技術(shù)。該算法是在研究并實(shí)現(xiàn)一個手機(jī)游戲引擎的過程中不斷實(shí)踐并完善的。并且，還有發(fā)展空間。

顏色的重要性，或者稱為權(quán)重weight_，二叉堆就是建立在那個基礎(chǔ)之上。這里選用的是最樸素的一種，是感性的認(rèn)識中最直觀的一種。還有其他選擇，比如，顏色梯度，是指兩種顏色的差值，可以這樣想象一下，如果兩個顏色很接近，那么是否可以用一種顏色替代呢?當(dāng)然可以，有些算法確實(shí)是這么做的。最后，引入一個公式，也是本文惟一的公式作為結(jié)束，weight_=m+n×k。簡單描述一下，weight_表示權(quán)重，和前面一樣是二叉堆建立的依據(jù)，m表示顏色點(diǎn)數(shù)量，n表示顏色梯度最小值，是最接近的兩個顏色的差值，k表示梯度系數(shù)，就是顏色梯度在weight_中的比重。公式應(yīng)用于本文的樸素權(quán)重計算就是k等于0，也就是不考慮梯度。

參考文獻(xiàn)

[1][美] Rafael C Gonzalez，Richard E Woods.數(shù)字圖像處理[M].2版.北京:電子工業(yè)出版社，2008.

[2][美] Maria Petrou，Panagiota Bosdogianni.數(shù)字圖像處理疑難解析[M].北京:機(jī)械工業(yè)出版社，2005.

[3]趙志誠，蔡安妮.圖像顏色矢量量化算法[J].北京郵電大學(xué)學(xué)報，2007，30(5):131-134.

[4]陸宗騏.C/C++圖像處理編程[M].北京:清華大學(xué)出版社，2005.

[5]周鮮成，申群太，王俊年.基于微粒群的顏色量化算法[J].微電子學(xué)與計算機(jī)，2008，25(3):51-54.

[6]任智斌，隋永新，楊英慧，等.在均勻顏色空間中實(shí)現(xiàn)彩色圖像的顏色量化[J].光學(xué)精密工程，2002，10(4):340-345.

[7]胡新榮，李德華，王天珍.基于蟻群優(yōu)化算法的彩色圖像顏色聚類的研究[J].小型微型計算機(jī)系統(tǒng)，2004，25(9):1 641-1 643.

[8]張學(xué)習(xí)，楊宜民.彩色圖像工程中常用顏色空間及其轉(zhuǎn)換[J].計算機(jī)工程與設(shè)計，2008，29(5):1 210-1 212.

[9][美] Tony F Chan，Jianhong Shen.圖像處理與分析(變分.PDE.小波及隨機(jī)方法)[M].北京:科學(xué)出版社，2009.

[10][美] Thomas H Cormen，Charles E Leiserson.算法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社，2006.