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

馬玉潔

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

0 前言

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

1 RGB顏色空間到Munsell顏色空間的轉(zhuǎn)換

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

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

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

2 確定初始類中心

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

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

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

對圖像的NBS距離求加權(quán)平均:

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

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

3.1 模糊核聚類方法

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

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

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

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

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

這樣,式(6)簡化為:

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

3.2 基于模糊核聚類的顏色量化實現(xiàn)步驟

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

(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是用中位切割算法量化的結(jié)果,圖1c、圖2c和圖3c是模糊C均值量化的結(jié)果,圖1d、圖2d和圖3d是用本文所提算法的量化結(jié)果。從圖1～3中可以看出:在量化級數(shù)相同的情況下,所提算法的量化效果明顯優(yōu)于中位切割算法和模糊 C均值算法。

圖3 人物圖像的濾波量化結(jié)果比較

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

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

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

5 結(jié)束語

提出了自動確定量化顏色數(shù)目的量化方法,在確定量化數(shù)目和初始類中心后,引入核函數(shù),用核模糊聚類方法對Musell空間的每個像素進行聚類從而完成量化。在量化級數(shù)相同的情況下,量化效果明顯優(yōu)于中位切割算法和模糊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] 王向陽,胡峰麗,劉春輝.一種基于圖像內(nèi)容的自適應(yīng)色彩量化算法[J].遼寧師范大學(xué)學(xué)報,2007,30(3):310-314.

[6] 伍忠東,高新波,謝維信.基于核方法的模糊聚類[J].西安電子科技大學(xué)學(xué)報,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.