圖像顏色量化是一項非常有趣的技術(shù)，為此我花了一個月的時間研究它，其中調(diào)色板檢索是顏色量化的步驟之一。調(diào)色板檢索就是給定n個顏色的列表A(根據(jù)圖像生成或者自己選定)，輸入顏色x，輸出A中距離x最近的顏色的索引。這里的距離不一定要用歐幾里得距離，但歐幾里得距離是效果最好的，同時也難以優(yōu)化。本文將介紹一種基于歐幾里得距離調(diào)色板的優(yōu)化算法，當(dāng)n=256時，平均比較3~4次就可以找出最近顏色的索引。

有經(jīng)驗的小伙伴應(yīng)該可以想到在RGB空間建立n個泰森多面體，然后把RGB空間切分成若干個立方體，每個立方體只要比較包含的泰森多面體對應(yīng)的顏色。這種做法是最優(yōu)的，但是實現(xiàn)代價太大(可能是我比較蒻才這樣覺得)。下面我們討論另一種方法，這種方法不是最優(yōu)的，也就比最優(yōu)差那么一點點，但是實現(xiàn)簡單。

首先我們將RGB空間(256*256*256)均勻切分成K*K*K個正方體(下文稱Cube)，K的推薦值是16。然后把調(diào)色板的n個顏色分別放入對應(yīng)的Cube內(nèi)，有些Cube可能沒有任何顏色，有些可能有好幾個顏色。最終我們的目標(biāo)是為每個Cube建立索引集，當(dāng)有顏色輸入時，遍歷對應(yīng)Cube索引集里所有顏色，找出與輸入最近的顏色編號并輸出。一開始所有Cube的索引集都是空的，接下來對每個Cube進行下面的操作：

(1)?若Cube內(nèi)不存在任何顏色，則找到距離Cube最近的顏色；否則在Cube內(nèi)找到與Cube最遠(yuǎn)距離值最大的顏色。兩種情況找到的顏色都設(shè)為a，并把a加入Cube的索引集。

(2)?枚舉a的a與Cube兩倍最遠(yuǎn)距離半徑內(nèi)的顏色(不包括a)，當(dāng)前枚舉出來的顏色設(shè)為e。

? ? (2.1)?找到Cube索引集中距離e最近的顏色，設(shè)為b。

? ? (2.2)?若b與e的中垂面與Cube相交，那么e加入索引集。

(3) Cube的索引集建立完畢。

（顏色與Cube的最遠(yuǎn)距離：顏色分別與Cube的8個頂點距離的最大值）

圖解算法步驟（原諒我只會畫2d，但在3d上原理一樣）：

上述步驟中，有3個小問題有一些優(yōu)化技巧，分別是：

問題1：如何快速找到距離Cube最近的顏色？

問題2：如何快速枚舉某顏色指定半徑內(nèi)的所有顏色？

問題3：如何快速判定兩個顏色的中垂面與Cube相交？

為了解決問題1和問題2，我們創(chuàng)建一個n*n的二維數(shù)組，數(shù)組第i行第j列的內(nèi)容為：與編號為i的顏色的第j個最近顏色的編號與距離。（i和j都是從0開始）

例如有調(diào)色板：

[(0,0,0), (2,3,3), (1,1,1), (6,6,6)]

那么建立的二維數(shù)組即：

考慮到性能，實際代碼中的距離不需要開平方，并且使用整型，因此上述例子的距離沒有開平方。

問題2的解法可以很直觀的看出來，因此不過多解釋了。枚舉編號i的顏色半徑r內(nèi)的所有顏色，遍歷數(shù)組第i行，如果距離大于等于r就退出循環(huán)。但是如何解決問題1就沒有那么直觀了，畢竟從數(shù)組中不能直接看出顏色和Cube的距離關(guān)系。

問題1的解法：

(1)?從與當(dāng)前Cube相鄰的Cube中找到任一顏色，設(shè)為a，并求出a與當(dāng)前Cube的距離d1和最遠(yuǎn)距離d2；若找不到直接結(jié)束該算法，改用遍歷所有顏色的方法。

(2)?枚舉a兩倍d2半徑內(nèi)的所有顏色(不包括a)，當(dāng)前枚舉出來的顏色設(shè)為b。

? ? (2.1)?若b到Cube的距離小于a到Cube的距離，那么a←b，d1←b到Cube的距離，d2←b與Cube的最遠(yuǎn)距離，停止枚舉然后跳轉(zhuǎn)到(2)開始新的枚舉。

(3)?a即所求的與Cube距離最近的顏色。

問題3的解法：

很容易發(fā)現(xiàn)若存在某個向量vi與向量u的點積小于0（在這個算法中是這樣，通常情況下要同時出現(xiàn)正負(fù)號才能判斷為相交），那么中垂線（三維里是中垂面）與正方形（Cube）相交。

那么為什么是中垂面，為什么要判斷與Cube相交？

我們先來看一張圖

a與b的中垂線把平面分割成了兩部分，其中紅色區(qū)域到點a的距離是最近的，藍色區(qū)域到點b的距離是最近的，因此很明顯x1更接近b，x2更接近a。如果中垂面和Cube相交，那么說明Cube中有部分區(qū)域要離b更近，因此要將b加入到索引集。

之前有說過該算法不是最優(yōu)的，原因是當(dāng)索引集顏色數(shù)≥2時，有可能出現(xiàn)如下情況：

按照算法流程，c是要加入索引集的，想要最優(yōu)結(jié)果的話那么c不應(yīng)該加入索引集，因為很明顯藍色區(qū)域距離b更近而不是c。不過這種情況是個低概率事件，因此可以不用管。

另外需要注意的是，如果距離不開平方，那么算法中描述的各種兩倍距離，實際上代碼中要乘以4。

該算法在我的AMD?A10-5750M cpu(2.5GHz)上單線程運行，運行耗時情況如下。

（下面的圖已經(jīng)和本文無關(guān)了，只是欣賞一下圖像顏色量化的效果）

有空再更新顏色量化吧