肖海俊

（江苏广播电视大学 如东学院，江苏 南通 226400）

彩色图像色彩聚类算法研究

肖海俊

（江苏广播电视大学 如东学院，江苏 南通 226400）

介绍了聚类分析方法和BMP图像的数据结构，并在此基础上，设计实现了图像色彩自适应聚类算法，目的是在充分理解图像色彩控制原理和BMP格式的点阵图像数据结构的基础上，完成具有根据图像自身的色彩构成特征，实现图像色彩自适应聚类功能的应用程序。该算法简单有效，有很好的实用价值，值得推广和应用。

彩色图像；聚类分析；BMP

一、 引言

在图像采集过程中，由于使用摄像机、扫描仪等设备作为图像输入的主要手段，因此得到的往往是色彩数达到1700万色的真彩色图像。但是受到工艺条件的限制，纺织印染产品的色彩达不到这样的程度，并且在实际的生产中也不需要保留这样多的色彩，所以，就需要一种尽可能不失真的将真彩色图像索引为伪彩色图像的算法，利用其完成真彩色图像的色彩聚类处理。因此，设计了一种能够将BMP格式的真彩色图像进行色彩聚类处理，形成基本不失真的、具有最多256种色彩的伪彩色图像的算法。

二、 聚类分析方法综述

所谓聚类就是将物理或抽象对象的集合分组成为由类似对象组成的多个类的过程[1]。由聚类所形成的簇是一组数据对象的集合，在同一个簇中的对象具有较高的相似度，不同簇中的对象则有较低的相似度[2]。

聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法[3]，是指按照事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大[4]，实现对数据的分类。它是直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类[5]。聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用数学工具进行定量的分类。聚类分析在数据挖掘中广泛应用[6]，其目的是以事物间的相似性作为类属划分的准则，将一个数据集划分为若干聚类，属于无监督分类的范畴[7]。目前，聚类分析已被广泛应用于许多领域，如模式识别、数据分析、图像处理、客户关系管理[8]。

三、BMP图像的数据结构分析

BMP文件由位图文件头、位图信息头、颜色信息表和位图数据块四部分组成。

（一）BMP文件头

BMP文件头数据结构含有BMP文件的类型、文件大小和位图起始位置等信息。

typedef struct tagBITMAPFILEHEADER {

WORD bfType; //位图文件的类型，必须为“BM”

DWORD bfSize; //位图文件的大小，以字节为单位

WORD bfReserved1; //位图文件保留字，必须为0

WORD bfReserved2; //位图文件保留字，必须为0

DWORD bfOffBits; //位图数据的起始位置，以相对于位图文件头的偏移量表示，以//字节为单位

} BITMAPFILEHEADER;

（二）位图信息头

BMP位图信息头数据结构用于说明位图的尺寸等信息。

typedef struct tagBITMAPINFOHEADER {

DWORD biSize; //本结构所占用字节数

LONG biWidth; //位图的宽度，以像素为单位

LONG biHeight; //位图的高度，以像素为单位

WORD biPlanes; //目标设备的级别，必须为1

WORD biBitCount; //每个像素所需的位数，必须是1（双色），4（16色），8（256色）//或24（真彩色）之一

DWORD biCompression; //位图压缩类型，必须是0（不压缩），1（BI_RLE8压缩类型）//或2(BI_RLE4压缩类型)之一

DWORD biSizeImage; //位图的大小，以字节为单位

LONG biXPelsPerMeter;//位图水平分辨率，单位为像素数每米

LONG biYPelsPerMeter;//位图垂直分辨率，单位为像素数每米

DWORD biClrUsed; //位图实际使用的颜色表中的颜色数

DWORD biClrImportant;//位图显示过程中的重要的颜色数

} BITMAPINFOHEADER;

（三）颜色信息表

颜色信息表用于说明位图中的颜色，它有若干个表项，每一个表项是一个RGBQUAD类型的结构，定义一种颜色。

typedef struct tagRGBQUAD {

BYTE rgbBlue; //蓝色的亮度（值范围为0－255）

BYTE rgbGreen; //绿色的亮度（值范围为0－255）

BYTE rgbRed; //红色的亮度（值范围为0－255）

BYTE rgbReserved; //保留，必须为0

} RGBQUAD;

颜色表中，RGBQUAD结构数据的个数由 biBitCount来确定：当biBitCount=1，4，8时，分别有2，16，256个表项；当bitBitCount=24时，没有颜色表项。

位图信息头和颜色信息表组成位图信息，BITMAPINFO结构定义如下：

typedef struct tagBITMAPINFO {

BITMAPINFOHEADER bmiHeader; //位图信息头

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

} BITMAPINFO;

颜色表一般是针对16位以下的图像而设置的，对于16位和16位以上的图像，由于其位图像素数据中直接对对应像素的RGB(A)颜色进行了描述，因而省却了调色板。而对于16位以下的图像，由于其位图像素数据中记录的只是调色板索引值，因而需要根据这个索引到调色板去取得相应的RGB(A)颜色。颜色信息表的作用就是创建调色板。

其中需要注意的问题是，RGBQUAD结构中的颜色顺序是B、G、R，而不是平常的R、G、B。

（四） 位图数据块

最后，在位图文件头、位图信息头、位图颜色表之后，便是位图的主体部分—位图数据。位图数据记录了位图的一个像素值，记录顺序是在扫描行内从左到右，扫描行之间从下到上。位图的一个像素值所占的字节数如下：

当biBitCount=1时，8个像素占1个字节；

当biBitCount=4时，2个像素占1个字节；

当biBitCount=8时，1个像素占1个字节；

当biBitCount=24时，1个像素占3个字节。

Windows规定一个扫描行所占的字节数必须是 4的倍数（即以long为单位），不足的以0填充。一个扫描行所占的字节数的计算方法如下：

DataSizePerLine=(biWidth*biBitCount+31)/8 //一个扫描行所占的字节数

DataSizePerLine=DataSizePerLine/4*4 //字节数必须是4的倍数

因而，位图数据的大小（不压缩情况下）为

DataSize=DataSizePerLine*biHeight

四、伪彩色图像的显示机理

在具有颜色表的情况下，位图点阵中的数据仅仅代表该像素点对应的颜色表索引值，即颜色表的表项序号。该点的真实色彩取决于颜色表中与索引对应的表项之具体取值。这样的图像一般称为“伪”彩色图像。伪彩色图像的显示过程，实际上就是一个映射的过程。将某一色彩代码作为偏移量对一组色彩寄存器寻址时，最终的显示色彩取决于当前被寻址寄存器的值。寄存器组的个数决定了能够同时使用的色彩总数，而可能使用的色彩数则取决于寄存器的位数。

如果颜色表不存在，则位图点阵数据中存储的是对应像素点的真实色彩（以B、G、R三分量的形式描述）。

五、算法设计

在基本不失真的原则下，将真彩色图像转换成256色图像的过程，实际上是依据真彩色图像的位图数据，索引产生调色板，并将真彩色图像位图数据中的像素点用调色板中的颜色的索引值代替的过程。

设想在扫描原始真彩色图像数据区的数据的过程中按实际像素点的B、G、R值去填充色表区，则色表中决不会出现“无效色组合”。但是经过这样简单的处理，由于真彩色图像的色彩多样性，容量有限的色表区定然会“溢出”。

为了在尽可能不失真的情况下，将真彩色图像转换成256色图像，可以对当前像素点进行筛选后再决定是否入色表。当色表中已经存在和当前像素色彩“足够”接近的色表项时，则当前点的色彩不入色彩表，直接使用对应色表项的序号为本像素点的索引值；否则将本像素点的色彩值追加到色表区中，产生一个新的色表项，并用其表项序号值替代对应像素点的原值。倘若这种追加使色表区的表项总数超过了256项，则说明本次索引因为标准过于苛刻而失败。此时，色表清零，作为判断标准的“色差”值增加一个步长，重新开始上述过程。

如此反复，当根据真彩色图像的实际情况，色差值增加到一定程度后，可以在色表没有溢出的前提下，将原图像的所有像素点处理完毕。此时，尚需根据实际产生的伪彩色图像实际数据，更新原真彩色文件的图像文件头、位图文件头和图像的色彩表数据，生成新的索引结果文件，算法也就结束。在这一算法的实施过程中，无效色的组合被杜绝了。由于真彩色图像的多样性，色彩聚类过程中色表的溢出常常不可避免，因而算法的回溯不可避免，色差步长也只能在逐次试探中产生。

考虑到色彩索引的实际过程，将此算法命名为“真彩色图像自适应回溯索引算法”。算法流程图如图1所示。

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

六、关键技术问题的研究与解决

（一）色表与色差

在将真彩色图像转换为256色图像时，首先要确定的是色表（即调色板的确定）。对于首次扫描，色表为空，在这种没有对比值的情况下，有可能出现当色表已满时，后面仍有大量的像素点无法入表的情况。所以，就需要设置一个阈值，用来将有效的像素点入表，这个阈值即色差值。

在像素点入表时，只有符合一定条件的像素才能进入到色表中，以此剔除无效的像素点。

而判断的标准为，当前处理点与色表中的最接近色的差值小于当前所设定的色差值时，将最接近色的索引值作为当前点的位图数据，否则的话，即说明当前点在色表中没有接近的颜色，就将当前点入色表。

如果处理完所有的像素点后，色表仍溢出，则将色差值增加1个步长值，重新进行判断。

（二）算法效率

由于图像数据量庞大，本算法又可能出现多次回溯，因此设法改进其时间指标至关重要。在实现这一算法时，从两方面考虑了这一问题。一方面考虑到色增量是影响回溯次数的重要因素，如果固定设置则比较死板，因此采用了在程序执行时交互设定的方法，期望以增大步长，减少回溯次数来提高时间效率。试验证明，对于精细程度不同的图像，步长值一般可在1～15范围选择。另一方面，考虑到对每一像素点均须遍查当前色表，因此改进查表方式对时间指标有很大影响。

快速查表算法形形色色，时间效率较高，但对于初始数据的要求比较苛刻，常要求数据有序或者局部有序。对于随机的图像数据而言，这一点无法满足，因此只能采用效率比较低的顺序查找算法。

但是，在对一点的查找过程中，实际比较次数取决于最终“命中”的时机，因此，即使是顺序查找，只要能提高首次命中率，也能较大地提高工作效率。本算法中，色表是动态生成的，色表中的末项是最近像素点的色彩值。考虑到实际图像所具有的“连续”性质—“相同”，“相近”像素点往往是成片出现的，也就是说，当前像素点和色表中末项匹配的几率较大，所以在实现本算法时，采用了“倒查色表”的方法，提高了首次命中率，使算法效率有较大的提高。

（三） 位图文件的处理

1. 文件的读取

现有两种读取位图文件的方法：ReadFile和ReadSection，二者不同之处是，前者使用动态分配内存的方法初始化和存储位图数据的指针，后者则使用 API函数，根据位图信息初始化和存储位图数据的指针。

方法一：

m_lpDIBits=(LPBYTE)new char[m_dwImageSize];

方法二：

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

(LPBITMAPINFO)m_lpBMPHdr,DIB_RGB_COLORS,

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

2. 调色板的创建和调用

读取文件的过程中，计算出调色板大小，然后调用创建调色板的函数：

ComputePaletteSize(m_lpBMPHdr-＞biBitCount);

SetWinPalette();

在显示位图之前，设置调色板的函数：

3. 位图的显示

位图的显示还是调用Windows的API函数来进行，需要传递的参数包括当前位图信息头、位图数据等：

其中的m_Dest、m_DestSize、m_Src、m_SrcSize分别代表了图像在当前设备上显示的左上角坐标、范围以及需要显示的源图像的左下角坐标、范围。此处需要说明的是，位图数据的字节数组是从图像的最下面一行开始逐行向上存储的。

m_Dest、m_DestSize、m_Src、m_SrcSize需要在实现之前设置好。

4. 位图的存储

位图的存储用WriteFile实现。

有个存取位图数据的字节数组的问题需要引起注意：字节数组中每个扫描行的字节数必须是4的倍数，如果不足则要用0补齐。

以下是处理的办法：

这段代码按照要求算出了用于记录图像数据的字节数组的大小。

七、结语

本文研究了在尽量不失真的前提下，实现真彩色图像的色彩聚类，产生具有少得多的色彩的伪彩色图像，具有很好的实用价值，可望在纺织品CAD/CAM领域中得到广泛的应用。

[1] 韩家炜. 数据挖掘概念与技术[M]. 北京：机械工业出版社，2005.

[2] 廖志芳，李鹏，刘克准. 数据聚类分析新方法研究[J]. 计算机工程与应用，2009，（10）.

[3] 张大斌，王婧，刘桂琴，朱侯. 基于伪并行遗传算法的聚类分析方法[J]. 计算机工程与设计，2009，（1）.

[4] 毛国君，段立娟，王实. 数据挖掘原理与算法[M]. 北京：清华大学出版社，2006.

[5] 张建萍，刘希玉. 基于聚类分析的K-means算法研究及应用[J].计算机应用研究，2007，（5）.

[6] 姜园，张朝阳，仇佩亮. 用于数据挖掘的聚类算法[J]. 电子与信息学报，2005，（4）.

[7] 曹文婷，邹海，段凤玲. 基于模糊K-Modes和免疫遗传算法的聚类分析[J]. 计算机技术与发展，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