一種模糊核聚類的彩色圖像量化算法

馬玉潔

(商丘師范學院計算機科學系,河南商丘 476000)

0 前言

顏色量化是彩色圖像處理的重要分支,其任務是從眾多的顏色中挑選出 K種具有代表性的顏色來盡可能真實地表示原始圖像。近年來,出現了不少彩色圖像量化算法。其中有基于聚類的 C均值方法[1]和模糊 C均值方法[2],以及基于分割的中位切割量化算法[3]和八叉樹量化算法[4]等。這些算法通常情況下對顏色進行量化時都取得了不錯的量化效果,但是它們是在指定量化數目的情況下得到的。為了不需要事先給出量化數目,文獻[5]提出了一種基于圖像內容的自適應色彩量化算法,該算法根據圖像自身內容自適應確定初始聚類中心。受其啟發,本文首先用八叉樹算法把原始圖像量化為 256種顏色,這是因為每幅彩色圖像其顏色的主要種類一般不超過256。然后,在Munsell空間依據NBS距離與人類視覺對顏色差別的定量關系確定出初始聚類中心。初始類中心確定后,可以直接用模糊 C均值算法進行聚類,但由于該算法僅適合于球形或橢球形聚類的問題,而聚類的效果很大程度上取決于樣本的分布。所以,為了更適合圖像的量化,則引入支持向量機中核函數[6]的思想,利用模糊核聚類方法對Munsell空間的每個像素進行聚類以實現對顏色的修改,從而完成圖像的量化。

1 RGB顏色空間到Munsell顏色空間的轉換

顏色是圖像的一種重要視覺特性。文獻[7]證實Munsell顏色空間成功地模擬了人類的顏色視覺特征,成功地保持了顏色的視覺一致性。所以,本文的圖像量化過程選擇在Munsell顏色空間進行。

假設M=(H1,V1,C1)和N=(H2,V2,C2)為Munsell空間的顏色對,則它們的NBS距離D定義為:

文獻[8]的研究表明:當 D的值小于3.0時,認為該顏色對是相似的;當D的值大于6.0時,認為該顏色對是顯著不同的。

2 確定初始類中心

首先用中位切割算法把原始圖像量化為256色,并將其轉化到Munsell空間。接下來在Munsell空間利用NBS距離與人類視覺對顏色變化的關系,本文提出了初始聚類中心確定的實現步驟:

(1)建立數組D′=(CI1,CI2,dis)存放NBS距離大于3的顏色信息,其中,CI1,CI2表示兩種不同顏色的標號,dis為用公式(1)求得的兩個顏色對的距離,設數組大小為n。

(2)建立數組 S來存放 D′中每一個距離的權值。方法是在圖像中,統計索引號為 CI1的像素個數,記為c1,統計索引號為CI2的像素個數,記為c2。則數組S(i)為:

對圖像的NBS距離求加權平均:

(3)按照像素數目的降序重排 256種顏色,選取像素數最多的顏色作為第一個類中心,用公式(1)計算該點與其他顏色之間的 D值,以滿足 D≥A選擇第二個聚類中心,然后依次進行,最終得到一個大小設為t的顏色集合,即:

3 基于模糊核聚類的顏色量化

3.1 模糊核聚類方法

設X={xk,k=1,2,…,n}為待分類的樣本集合,C={c1,c2,…,ct}為t個類中心,uik(i=1,2,…, t,k=1,2,…,n)為第k個樣本對第i類的隸屬度函數,且滿足條件0≤uik≤1,uik=1。模糊聚類就是根據聚類準則,求得樣本集的t個聚類中心,模糊C均值的聚類準則函數為:

聚類的目標是使J(U,C)極小化。

定義非線性映射Φ:X→Q,則x∈Rp→Φ(x)∈Rq,Q為高維特征空間,模糊核聚類的準則函數為[9]:

其中,dF(xk,ci)為特征空間中的歐式距離;K(xk,ci)為核函數,本文采樣公式(8)所示的高斯核,

σ為高斯核參數,由給定樣本集確定為[10]:

這樣,式(6)簡化為:

通過Lagrange乘子法對公式(10)求解,可得

3.2 基于模糊核聚類的顏色量化實現步驟

獲得初始類中心C′={C′1,C′2,C′3,…,C′t}后,接下來利用上述的模糊核聚類算法對Munsell空間的每個像素進行聚類,從而形成合適的量化結果。具體實現步驟為:

(1)選擇迭代停止條件ε,令p=1,C′0={C′1,C′2,C′3,…,C′t},利用公式(10)計算σ。

(2)用C′p-1代入公式(11)計算Up。

(3)用C′p-1和得到的Up代入公式(12)得到C′p。

4 仿真研究

為了驗證所提算法的有效性,本文對多幅大小為 256×256真彩圖像進行了仿真研究。圖1a、圖2a和圖3a是原始真彩圖像,圖1b、圖2b和圖3b是用中位切割算法量化的結果,圖1c、圖2c和圖3c是模糊C均值量化的結果,圖1d、圖2d和圖3d是用本文所提算法的量化結果。從圖1～3中可以看出:在量化級數相同的情況下,所提算法的量化效果明顯優于中位切割算法和模糊 C均值算法。

圖3 人物圖像的濾波量化結果比較

為了進一步比較不同量化算法之間的性能,本文采用公式(13)對不同算法的平均量化誤差進行比較,結果見表1。從表1中也可以看出,本文所提算法的平均量化誤差明顯小于中位切割算法和模糊 C均值算法。

其中,d[s(i,j),q(i,j)]表示兩個像素點s(i,j)和q(i,j)的歐氏距離。

表1 圖像的平均量化誤差比較

5 結束語

提出了自動確定量化顏色數目的量化方法,在確定量化數目和初始類中心后,引入核函數,用核模糊聚類方法對Musell空間的每個像素進行聚類從而完成量化。在量化級數相同的情況下,量化效果明顯優于中位切割算法和模糊C均值算法。

[1] H ideo Kasuga.Color Quantization Using the Fast k-means algorithm[J].Systems and Computers,2000,31(8):1120-1128.

[2] Ozdemir D,Akarun L.A Fuzzy Algorithm for Color Quantization of Images[J].Pattern Recognition,2002,35,1785-1791.

[3] Heckbert P.Color Image Quantization for Frame Buffer Disp lay[J].Computer Graphics,1982,16(2):297-307.

[4] Gervautz M,Purgathofer W.A Simple Method for Color Quantization:Octree Quantization[C]//Proceeding of Graphics Gems International.San Diego:Academic Press Professional,1998,8(6):219-230.

[5] 王向陽,胡峰麗,劉春輝.一種基于圖像內容的自適應色彩量化算法[J].遼寧師范大學學報,2007,30(3):310-314.

[6] 伍忠東,高新波,謝維信.基于核方法的模糊聚類[J].西安電子科技大學學報,2004,31(4):533-537.

[7] Ma W Y,Man junath S.Edgeflow:A Framework for Boundary Detection and Image Segmentation[J].IEEE Trans on Image Processing,2000,9(8):1375-1388.

[8] Gong Y H,Proietti G.Image Indexing and Retrieval Based on Human Percep tual Color Clustering[C]//The International Conference on Computer Vision.Mumbai,1998.

[9] Zhang DQ,Chen SC.Fuzzy C-means and Possibilistic C-means Algorithms Under Kernel Based RobustMetric[J].Pattern Recognition and Artificial Intelligence,2004,17(4):390-395.

[10] Wu K L,Yang M S.Alternative C-means Clustering Algorithm[J].Pattern Recognition,2002,35(10):2267-2278.