肖海俊

（江蘇廣播電視大學(xué) 如東學(xué)院，江蘇 南通 226400）

彩色圖像色彩聚類算法研究

肖?？?/p>

（江蘇廣播電視大學(xué) 如東學(xué)院，江蘇 南通 226400）

介紹了聚類分析方法和BMP圖像的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了圖像色彩自適應(yīng)聚類算法，目的是在充分理解圖像色彩控制原理和BMP格式的點(diǎn)陣圖像數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，完成具有根據(jù)圖像自身的色彩構(gòu)成特征，實(shí)現(xiàn)圖像色彩自適應(yīng)聚類功能的應(yīng)用程序。該算法簡(jiǎn)單有效，有很好的實(shí)用價(jià)值，值得推廣和應(yīng)用。

彩色圖像；聚類分析；BMP

一、 引言

在圖像采集過程中，由于使用攝像機(jī)、掃描儀等設(shè)備作為圖像輸入的主要手段，因此得到的往往是色彩數(shù)達(dá)到1700萬色的真彩色圖像。但是受到工藝條件的限制，紡織印染產(chǎn)品的色彩達(dá)不到這樣的程度，并且在實(shí)際的生產(chǎn)中也不需要保留這樣多的色彩，所以，就需要一種盡可能不失真的將真彩色圖像索引為偽彩色圖像的算法，利用其完成真彩色圖像的色彩聚類處理。因此，設(shè)計(jì)了一種能夠?qū)MP格式的真彩色圖像進(jìn)行色彩聚類處理，形成基本不失真的、具有最多256種色彩的偽彩色圖像的算法。

二、 聚類分析方法綜述

所謂聚類就是將物理或抽象對(duì)象的集合分組成為由類似對(duì)象組成的多個(gè)類的過程[1]。由聚類所形成的簇是一組數(shù)據(jù)對(duì)象的集合，在同一個(gè)簇中的對(duì)象具有較高的相似度，不同簇中的對(duì)象則有較低的相似度[2]。

聚類分析又稱群分析，它是研究（樣品或指標(biāo)）分類問題的一種統(tǒng)計(jì)分析方法[3]，是指按照事物的某些屬性將其聚集成類，使類間相似性盡量小，類內(nèi)相似性盡量大[4]，實(shí)現(xiàn)對(duì)數(shù)據(jù)的分類。它是直接比較各事物之間的性質(zhì)，將性質(zhì)相近的歸為一類，將性質(zhì)差別較大的歸入不同的類[5]。聚類分析起源于分類學(xué)，在古老的分類學(xué)中，人們主要依靠經(jīng)驗(yàn)和專業(yè)知識(shí)來實(shí)現(xiàn)分類，很少利用數(shù)學(xué)工具進(jìn)行定量的分類。聚類分析在數(shù)據(jù)挖掘中廣泛應(yīng)用[6]，其目的是以事物間的相似性作為類屬劃分的準(zhǔn)則，將一個(gè)數(shù)據(jù)集劃分為若干聚類，屬于無監(jiān)督分類的范疇[7]。目前，聚類分析已被廣泛應(yīng)用于許多領(lǐng)域，如模式識(shí)別、數(shù)據(jù)分析、圖像處理、客戶關(guān)系管理[8]。

三、BMP圖像的數(shù)據(jù)結(jié)構(gòu)分析

BMP文件由位圖文件頭、位圖信息頭、顏色信息表和位圖數(shù)據(jù)塊四部分組成。

（一）BMP文件頭

BMP文件頭數(shù)據(jù)結(jié)構(gòu)含有BMP文件的類型、文件大小和位圖起始位置等信息。

typedef struct tagBITMAPFILEHEADER {

WORD bfType; //位圖文件的類型，必須為“BM”

DWORD bfSize; //位圖文件的大小，以字節(jié)為單位

WORD bfReserved1; //位圖文件保留字，必須為0

WORD bfReserved2; //位圖文件保留字，必須為0

DWORD bfOffBits; //位圖數(shù)據(jù)的起始位置，以相對(duì)于位圖文件頭的偏移量表示，以//字節(jié)為單位

} BITMAPFILEHEADER;

（二）位圖信息頭

BMP位圖信息頭數(shù)據(jù)結(jié)構(gòu)用于說明位圖的尺寸等信息。

typedef struct tagBITMAPINFOHEADER {

DWORD biSize; //本結(jié)構(gòu)所占用字節(jié)數(shù)

LONG biWidth; //位圖的寬度，以像素為單位

LONG biHeight; //位圖的高度，以像素為單位

WORD biPlanes; //目標(biāo)設(shè)備的級(jí)別，必須為1

WORD biBitCount; //每個(gè)像素所需的位數(shù)，必須是1（雙色），4（16色），8（256色）//或24（真彩色）之一

DWORD biCompression; //位圖壓縮類型，必須是0（不壓縮），1（BI_RLE8壓縮類型）//或2(BI_RLE4壓縮類型)之一

DWORD biSizeImage; //位圖的大小，以字節(jié)為單位

LONG biXPelsPerMeter;//位圖水平分辨率，單位為像素?cái)?shù)每米

LONG biYPelsPerMeter;//位圖垂直分辨率，單位為像素?cái)?shù)每米

DWORD biClrUsed; //位圖實(shí)際使用的顏色表中的顏色數(shù)

DWORD biClrImportant;//位圖顯示過程中的重要的顏色數(shù)

} BITMAPINFOHEADER;

（三）顏色信息表

顏色信息表用于說明位圖中的顏色，它有若干個(gè)表項(xiàng)，每一個(gè)表項(xiàng)是一個(gè)RGBQUAD類型的結(jié)構(gòu)，定義一種顏色。

typedef struct tagRGBQUAD {

BYTE rgbBlue; //藍(lán)色的亮度（值范圍為0－255）

BYTE rgbGreen; //綠色的亮度（值范圍為0－255）

BYTE rgbRed; //紅色的亮度（值范圍為0－255）

BYTE rgbReserved; //保留，必須為0

} RGBQUAD;

顏色表中，RGBQUAD結(jié)構(gòu)數(shù)據(jù)的個(gè)數(shù)由 biBitCount來確定：當(dāng)biBitCount=1，4，8時(shí)，分別有2，16，256個(gè)表項(xiàng)；當(dāng)bitBitCount=24時(shí)，沒有顏色表項(xiàng)。

位圖信息頭和顏色信息表組成位圖信息，BITMAPINFO結(jié)構(gòu)定義如下：

typedef struct tagBITMAPINFO {

BITMAPINFOHEADER bmiHeader; //位圖信息頭

RGBQUAD bmiColors[1]; //顏色信息表

} BITMAPINFO;

顏色表一般是針對(duì)16位以下的圖像而設(shè)置的，對(duì)于16位和16位以上的圖像，由于其位圖像素?cái)?shù)據(jù)中直接對(duì)對(duì)應(yīng)像素的RGB(A)顏色進(jìn)行了描述，因而省卻了調(diào)色板。而對(duì)于16位以下的圖像，由于其位圖像素?cái)?shù)據(jù)中記錄的只是調(diào)色板索引值，因而需要根據(jù)這個(gè)索引到調(diào)色板去取得相應(yīng)的RGB(A)顏色。顏色信息表的作用就是創(chuàng)建調(diào)色板。

其中需要注意的問題是，RGBQUAD結(jié)構(gòu)中的顏色順序是B、G、R，而不是平常的R、G、B。

（四） 位圖數(shù)據(jù)塊

最后，在位圖文件頭、位圖信息頭、位圖顏色表之后，便是位圖的主體部分—位圖數(shù)據(jù)。位圖數(shù)據(jù)記錄了位圖的一個(gè)像素值，記錄順序是在掃描行內(nèi)從左到右，掃描行之間從下到上。位圖的一個(gè)像素值所占的字節(jié)數(shù)如下：

當(dāng)biBitCount=1時(shí)，8個(gè)像素占1個(gè)字節(jié)；

當(dāng)biBitCount=4時(shí)，2個(gè)像素占1個(gè)字節(jié)；

當(dāng)biBitCount=8時(shí)，1個(gè)像素占1個(gè)字節(jié)；

當(dāng)biBitCount=24時(shí)，1個(gè)像素占3個(gè)字節(jié)。

Windows規(guī)定一個(gè)掃描行所占的字節(jié)數(shù)必須是 4的倍數(shù)（即以long為單位），不足的以0填充。一個(gè)掃描行所占的字節(jié)數(shù)的計(jì)算方法如下：

DataSizePerLine=(biWidth*biBitCount+31)/8 //一個(gè)掃描行所占的字節(jié)數(shù)

DataSizePerLine=DataSizePerLine/4*4 //字節(jié)數(shù)必須是4的倍數(shù)

因而，位圖數(shù)據(jù)的大?。ú粔嚎s情況下）為

DataSize=DataSizePerLine*biHeight

四、偽彩色圖像的顯示機(jī)理

在具有顏色表的情況下，位圖點(diǎn)陣中的數(shù)據(jù)僅僅代表該像素點(diǎn)對(duì)應(yīng)的顏色表索引值，即顏色表的表項(xiàng)序號(hào)。該點(diǎn)的真實(shí)色彩取決于顏色表中與索引對(duì)應(yīng)的表項(xiàng)之具體取值。這樣的圖像一般稱為“偽”彩色圖像。偽彩色圖像的顯示過程，實(shí)際上就是一個(gè)映射的過程。將某一色彩代碼作為偏移量對(duì)一組色彩寄存器尋址時(shí)，最終的顯示色彩取決于當(dāng)前被尋址寄存器的值。寄存器組的個(gè)數(shù)決定了能夠同時(shí)使用的色彩總數(shù)，而可能使用的色彩數(shù)則取決于寄存器的位數(shù)。

如果顏色表不存在，則位圖點(diǎn)陣數(shù)據(jù)中存儲(chǔ)的是對(duì)應(yīng)像素點(diǎn)的真實(shí)色彩（以B、G、R三分量的形式描述）。

五、算法設(shè)計(jì)

在基本不失真的原則下，將真彩色圖像轉(zhuǎn)換成256色圖像的過程，實(shí)際上是依據(jù)真彩色圖像的位圖數(shù)據(jù)，索引產(chǎn)生調(diào)色板，并將真彩色圖像位圖數(shù)據(jù)中的像素點(diǎn)用調(diào)色板中的顏色的索引值代替的過程。

設(shè)想在掃描原始真彩色圖像數(shù)據(jù)區(qū)的數(shù)據(jù)的過程中按實(shí)際像素點(diǎn)的B、G、R值去填充色表區(qū)，則色表中決不會(huì)出現(xiàn)“無效色組合”。但是經(jīng)過這樣簡(jiǎn)單的處理，由于真彩色圖像的色彩多樣性，容量有限的色表區(qū)定然會(huì)“溢出”。

為了在盡可能不失真的情況下，將真彩色圖像轉(zhuǎn)換成256色圖像，可以對(duì)當(dāng)前像素點(diǎn)進(jìn)行篩選后再?zèng)Q定是否入色表。當(dāng)色表中已經(jīng)存在和當(dāng)前像素色彩“足夠”接近的色表項(xiàng)時(shí)，則當(dāng)前點(diǎn)的色彩不入色彩表，直接使用對(duì)應(yīng)色表項(xiàng)的序號(hào)為本像素點(diǎn)的索引值；否則將本像素點(diǎn)的色彩值追加到色表區(qū)中，產(chǎn)生一個(gè)新的色表項(xiàng)，并用其表項(xiàng)序號(hào)值替代對(duì)應(yīng)像素點(diǎn)的原值。倘若這種追加使色表區(qū)的表項(xiàng)總數(shù)超過了256項(xiàng)，則說明本次索引因?yàn)闃?biāo)準(zhǔn)過于苛刻而失敗。此時(shí)，色表清零，作為判斷標(biāo)準(zhǔn)的“色差”值增加一個(gè)步長(zhǎng)，重新開始上述過程。

如此反復(fù)，當(dāng)根據(jù)真彩色圖像的實(shí)際情況，色差值增加到一定程度后，可以在色表沒有溢出的前提下，將原圖像的所有像素點(diǎn)處理完畢。此時(shí)，尚需根據(jù)實(shí)際產(chǎn)生的偽彩色圖像實(shí)際數(shù)據(jù)，更新原真彩色文件的圖像文件頭、位圖文件頭和圖像的色彩表數(shù)據(jù)，生成新的索引結(jié)果文件，算法也就結(jié)束。在這一算法的實(shí)施過程中，無效色的組合被杜絕了。由于真彩色圖像的多樣性，色彩聚類過程中色表的溢出常常不可避免，因而算法的回溯不可避免，色差步長(zhǎng)也只能在逐次試探中產(chǎn)生。

考慮到色彩索引的實(shí)際過程，將此算法命名為“真彩色圖像自適應(yīng)回溯索引算法”。算法流程圖如圖1所示。

圖1 色彩回溯索引算法流程圖

六、關(guān)鍵技術(shù)問題的研究與解決

（一）色表與色差

在將真彩色圖像轉(zhuǎn)換為256色圖像時(shí)，首先要確定的是色表（即調(diào)色板的確定）。對(duì)于首次掃描，色表為空，在這種沒有對(duì)比值的情況下，有可能出現(xiàn)當(dāng)色表已滿時(shí)，后面仍有大量的像素點(diǎn)無法入表的情況。所以，就需要設(shè)置一個(gè)閾值，用來將有效的像素點(diǎn)入表，這個(gè)閾值即色差值。

在像素點(diǎn)入表時(shí)，只有符合一定條件的像素才能進(jìn)入到色表中，以此剔除無效的像素點(diǎn)。

而判斷的標(biāo)準(zhǔn)為，當(dāng)前處理點(diǎn)與色表中的最接近色的差值小于當(dāng)前所設(shè)定的色差值時(shí)，將最接近色的索引值作為當(dāng)前點(diǎn)的位圖數(shù)據(jù)，否則的話，即說明當(dāng)前點(diǎn)在色表中沒有接近的顏色，就將當(dāng)前點(diǎn)入色表。

如果處理完所有的像素點(diǎn)后，色表仍溢出，則將色差值增加1個(gè)步長(zhǎng)值，重新進(jìn)行判斷。

（二）算法效率

由于圖像數(shù)據(jù)量龐大，本算法又可能出現(xiàn)多次回溯，因此設(shè)法改進(jìn)其時(shí)間指標(biāo)至關(guān)重要。在實(shí)現(xiàn)這一算法時(shí)，從兩方面考慮了這一問題。一方面考慮到色增量是影響回溯次數(shù)的重要因素，如果固定設(shè)置則比較死板，因此采用了在程序執(zhí)行時(shí)交互設(shè)定的方法，期望以增大步長(zhǎng)，減少回溯次數(shù)來提高時(shí)間效率。試驗(yàn)證明，對(duì)于精細(xì)程度不同的圖像，步長(zhǎng)值一般可在1～15范圍選擇。另一方面，考慮到對(duì)每一像素點(diǎn)均須遍查當(dāng)前色表，因此改進(jìn)查表方式對(duì)時(shí)間指標(biāo)有很大影響。

快速查表算法形形色色，時(shí)間效率較高，但對(duì)于初始數(shù)據(jù)的要求比較苛刻，常要求數(shù)據(jù)有序或者局部有序。對(duì)于隨機(jī)的圖像數(shù)據(jù)而言，這一點(diǎn)無法滿足，因此只能采用效率比較低的順序查找算法。

但是，在對(duì)一點(diǎn)的查找過程中，實(shí)際比較次數(shù)取決于最終“命中”的時(shí)機(jī)，因此，即使是順序查找，只要能提高首次命中率，也能較大地提高工作效率。本算法中，色表是動(dòng)態(tài)生成的，色表中的末項(xiàng)是最近像素點(diǎn)的色彩值?？紤]到實(shí)際圖像所具有的“連續(xù)”性質(zhì)—“相同”，“相近”像素點(diǎn)往往是成片出現(xiàn)的，也就是說，當(dāng)前像素點(diǎn)和色表中末項(xiàng)匹配的幾率較大，所以在實(shí)現(xiàn)本算法時(shí)，采用了“倒查色表”的方法，提高了首次命中率，使算法效率有較大的提高。

（三） 位圖文件的處理

1. 文件的讀取

現(xiàn)有兩種讀取位圖文件的方法：ReadFile和ReadSection，二者不同之處是，前者使用動(dòng)態(tài)分配內(nèi)存的方法初始化和存儲(chǔ)位圖數(shù)據(jù)的指針，后者則使用 API函數(shù)，根據(jù)位圖信息初始化和存儲(chǔ)位圖數(shù)據(jù)的指針。

方法一：

m_lpDIBits=(LPBYTE)new char[m_dwImageSize];

方法二：

m_hBitmap=::CreateDIBSection(pDC-＞GetSafeHdc(),

(LPBITMAPINFO)m_lpBMPHdr,DIB_RGB_COLORS,

(LPVOID*)&m_lpDIBits,NULL,0);

2. 調(diào)色板的創(chuàng)建和調(diào)用

讀取文件的過程中，計(jì)算出調(diào)色板大小，然后調(diào)用創(chuàng)建調(diào)色板的函數(shù)：

ComputePaletteSize(m_lpBMPHdr-＞biBitCount);

SetWinPalette();

在顯示位圖之前，設(shè)置調(diào)色板的函數(shù)：

3. 位圖的顯示

位圖的顯示還是調(diào)用Windows的API函數(shù)來進(jìn)行，需要傳遞的參數(shù)包括當(dāng)前位圖信息頭、位圖數(shù)據(jù)等：

其中的m_Dest、m_DestSize、m_Src、m_SrcSize分別代表了圖像在當(dāng)前設(shè)備上顯示的左上角坐標(biāo)、范圍以及需要顯示的源圖像的左下角坐標(biāo)、范圍。此處需要說明的是，位圖數(shù)據(jù)的字節(jié)數(shù)組是從圖像的最下面一行開始逐行向上存儲(chǔ)的。

m_Dest、m_DestSize、m_Src、m_SrcSize需要在實(shí)現(xiàn)之前設(shè)置好。

4. 位圖的存儲(chǔ)

位圖的存儲(chǔ)用WriteFile實(shí)現(xiàn)。

有個(gè)存取位圖數(shù)據(jù)的字節(jié)數(shù)組的問題需要引起注意：字節(jié)數(shù)組中每個(gè)掃描行的字節(jié)數(shù)必須是4的倍數(shù)，如果不足則要用0補(bǔ)齊。

以下是處理的辦法：

這段代碼按照要求算出了用于記錄圖像數(shù)據(jù)的字節(jié)數(shù)組的大小。

七、結(jié)語

本文研究了在盡量不失真的前提下，實(shí)現(xiàn)真彩色圖像的色彩聚類，產(chǎn)生具有少得多的色彩的偽彩色圖像，具有很好的實(shí)用價(jià)值，可望在紡織品CAD/CAM領(lǐng)域中得到廣泛的應(yīng)用。

[1] 韓家煒. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京：機(jī)械工業(yè)出版社，2005.

[2] 廖志芳，李鵬，劉克準(zhǔn). 數(shù)據(jù)聚類分析新方法研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2009，（10）.

[3] 張大斌，王婧，劉桂琴，朱侯. 基于偽并行遺傳算法的聚類分析方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2009，（1）.

[4] 毛國君，段立娟，王實(shí). 數(shù)據(jù)挖掘原理與算法[M]. 北京：清華大學(xué)出版社，2006.

[5] 張建萍，劉希玉. 基于聚類分析的K-means算法研究及應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2007，（5）.

[6] 姜園，張朝陽，仇佩亮. 用于數(shù)據(jù)挖掘的聚類算法[J]. 電子與信息學(xué)報(bào)，2005，（4）.

[7] 曹文婷，鄒海，段鳳玲. 基于模糊K-Modes和免疫遺傳算法的聚類分析[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2009，（2）.

[8] 賴玉霞，劉建平，楊國興. 基于遺傳算法的K均值聚類分析[J].計(jì)算機(jī)工程，2008，（20）.

Research on Color Clustering Algorithm of Color Images

XIAO Hai-jun

The cluster analysis method and data structure of BMP images are described. And on this basis, an image color adaptive clustering algorithm is designed and implemented. The purpose is to achieve color image adaptive clustering function according to the images’ own color composition features on the basis of the full understanding of the image color control theory and of the data structure of dot matrix images of BMP format. The algorithm is simple and effective. It has a good practical value and is worthy of promotion and application.

color images; clustering analysis; BMP

TP311.1

A

1008-7427（2012）02-0158-03

2011-12-22