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

肖?？?/p>

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

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

肖海俊

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

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

彩色圖像；聚類分析；BMP

一、 引言

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

二、 聚類分析方法綜述

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

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

} BITMAPFILEHEADER;

（二）位圖信息頭

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

typedef struct tagBITMAPINFOHEADER {

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

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

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

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

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

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

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

LONG biXPelsPerMeter;//位圖水平分辨率，單位為像素數(shù)每米

LONG biYPelsPerMeter;//位圖垂直分辨率，單位為像素數(shù)每米

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

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

} BITMAPINFOHEADER;

（三）顏色信息表

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

typedef struct tagRGBQUAD {

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

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

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

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

} RGBQUAD;

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

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

typedef struct tagBITMAPINFO {

BITMAPINFOHEADER bmiHeader; //位圖信息頭

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

} BITMAPINFO;

顏色表一般是針對16位以下的圖像而設(shè)置的，對于16位和16位以上的圖像，由于其位圖像素數(shù)據(jù)中直接對對應(yīng)像素的RGB(A)顏色進行了描述，因而省卻了調(diào)色板。而對于16位以下的圖像，由于其位圖像素數(shù)據(jù)中記錄的只是調(diào)色板索引值，因而需要根據(jù)這個索引到調(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ù)記錄了位圖的一個像素值，記錄順序是在掃描行內(nèi)從左到右，掃描行之間從下到上。位圖的一個像素值所占的字節(jié)數(shù)如下：

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

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

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

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

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

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

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

因而，位圖數(shù)據(jù)的大小（不壓縮情況下）為

DataSize=DataSizePerLine*biHeight

四、偽彩色圖像的顯示機理

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

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

五、算法設(shè)計

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

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

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

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

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

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

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

（一）色表與色差

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

在像素點入表時，只有符合一定條件的像素才能進入到色表中，以此剔除無效的像素點。

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

如果處理完所有的像素點后，色表仍溢出，則將色差值增加1個步長值，重新進行判斷。

（二）算法效率

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

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

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

（三） 位圖文件的處理

1. 文件的讀取

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

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

ComputePaletteSize(m_lpBMPHdr-＞biBitCount);

SetWinPalette();

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

3. 位圖的顯示

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

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

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

4. 位圖的存儲

位圖的存儲用WriteFile實現(xiàn)。

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

以下是處理的辦法：

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

七、結(jié)語

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

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

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

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

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

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

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

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

[8] 賴玉霞，劉建平，楊國興. 基于遺傳算法的K均值聚類分析[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