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

摘要：在介绍图像色彩自适应聚类算法的分析的同时，进行针对任意真彩色图像进行色彩聚类的算法。设计一种能够将BMP格式的真彩色图像进行色彩聚类处理，形成基本不失真的、最多具有256种色彩的伪彩色图像算法。

关键词：聚类算法；BMP图像；位图文件

中图分类号：TP391文献标识码：A文章编号：1009-3044(2011)17-4158-02

Color Image of Color Clustering Algorithm

WEI Yang, HE Li

(Sichuan University of Science& engineering,school of Computer Science, Zigong 643000, China)

Abstract: In this image colour adaptive clustering algorithm analysis at the same time, carries on against any true color images were color clustering algorithm. Design a can of BMP format will be true color image processing, the color clustering form basic has not really, most of his kind of colour 256 color image algorithm.

Key words: clustering algorithm; BMP image; bitmap file

在图像采集过程中，由于使用摄像机、扫描仪等涉别作为图像输入的主要手段，因此得到的往往是色彩数达到1700万色的真色彩图像。但是在现实工业生产过程当中受到工艺条件的限制，纺织印染产品的色彩达不到这样的程度，并且在实际的生产中也不需要保留这样多的色彩，所以，就需要一种尽可能不失真的将真色彩图像索引为色彩图像的算法，利用其完成真色彩图像的色彩聚类处理。聚类分析数据挖掘中的一个很活跃的研究领域，相关人员已提出了许多聚类算法。这些算法可以划分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。

1 BMP图像的数据结构

BMP数据结构分成BMP文件头：BMP文件头数据结构含有BMP文件的类型、文件大小和位图起始位置等信息。位图信息头：BMP位图信息头数据结构用于说明位图的尺寸等信息。颜色信息表：颜色信息用于说明位图的颜色，它有若干个表现，每一个表项是一个RGBQUAD类型的结构，定义一种颜色。位图数据库：位图数据记录了位图的每一个像素值，记录顺序实在扫描行内从左到右，扫描行之间从下到上。

2 伪彩色图像的现实机理

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

3 算法设计与关键技术的分析与解决

在基于不失真的原则，将真彩色图像转换成256色图像的过程，实际上是依据真色彩色图像的位图数据，索引产生调色板，并将真彩色图像位图数据中的像素点用调色板中的颜色的索引值代替的过程。设想在扫描原始真彩色图像数据区的数据的过程中按实际像素点的B、G、R值去填充色表区，则色表中决不会出现“无效色组合”。但是经过这样简单的处理，由于真彩色图像的色彩多种多样，容量有限的色表区定然会“溢出”。为了尽可能不失真的情况下，将真彩色图像转换成256色图像，可以对当前像素点进行筛选后 再决定是否入色表。当色表中已经存在和当前像素色彩“足够”接近的色表项时，则当前的色彩值追加到色表区中，产生一个新的色表项，并用其表项序号值替代对应像素点的原值。倘若这种追加使色表区的表项总数超过了256项，则说明本次索引因为标准过于苛刻而失败。此时，色表清零，作为判断标准的“色差”值增加一个步长，重新开始上述过程。如此反复，当根据真彩色图像的实际情况，色差值增加到一定程度后，可以在色表没有溢出的前提下，将源图像的所有像素点处理完毕。此时，需要根据实际产生的伪色彩图像实际数据，更新原真彩色文件的图像头文件、位图文件头和图像的色彩表数据，生成新的索引结果文件，算法也就结束了。在这一算法的实施过程中，无效色的组合被杜绝了。由于真色彩图像的多样性，色彩聚类过程中色表的溢出常常不可避免，因而算法的回溯亦不可避免，色差步长也只能在逐次试探中产生。考虑到色彩索引的实际过程，将此算法命名为“彩色图像自适应回溯索引算法”，算法流程图如图1所示。

3.1 色表与色差

在将真彩色图像转换为256色图像时，首先要确定的是色表。对于首次扫描，色表为空，在这种没有对比值的情况下，有可能出现色表已满时，后面仍有大量的像素点无法如表的情况。所以，就需要设置一个色差值来将有效的像素点入表。在像素点入表时，只有符合一定条件的像素才能进入到色表中，以此剔除无效的像素点。而判断标准为，当前处理点与色表中的最接近色的差值小于当前所设定的色差时，将最接近色的索引值作为当前点的位图数据，否则得话，即说明当前点在色表中没有接近的颜色，就将当前店入色表。如果处理完所有的像素点后，色表仍溢出，则将色差值增加1个步长值，重新进行判断。

3.2 算法效率

由于图像数据量庞大，本算法又可能出现多次回溯，因此设法改进其时间指标至关重要。在实现这一算法时，从两方面考虑了这一问题。一方面考虑到色增量是影响回溯次数的重要因素，如果固定设置则比较死板，因此采用了在程序执行时交互设定的方法，期望以增大步长，减少回溯次数来提高时间效率。试验证明，对于精细程度不同的图像，步长值一般可在1~15范围选择。另外一方面，考虑到对每一像素点均须遍查当前色表，因此改进查表方式对时间指标有很大影响。快速查表的算法有很多种，时间效率较高，但对于初始数据的要求比较苛刻，常要求数据有序或者局部有序。对于随机的图像数据而言，这一点无法满足，因此只能采取效率比较低的顺序查找算法。但是，在对一点的查找过程当中，实际比较次数取决于最终“命中”的时机，因此，即使是顺序查询，只要能提高首次命中率，也能较大地提高工作效率。本算法中，色表时动态生成的，色表中的末项时最近像素点的色彩值。考虑到实际图像所具有的“连续”性质“相同”，“相近”像素点往往是成片出现的，也就是说，当前像素点和色表中未项匹配的几率较大，所以在实现本算法时，采用“倒查色表”的方法，提高首次命中率，使算法效率有较大的提高。

3.3 位图文件的处理

3.3.1 读取位图文件的方法

m_lpDIBits = (LPBYTE)new char[m_dwImageSize];

3.3.2 调色板的创建和调用

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

ComputePaletteSize(m_lpBMPHdr->biBitCount);

SetWinPalette();

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

if(m_hPalette !=NULL){

::SelectPalette(pDC->GetSafeHdc(),m_hPalette,TRUE);}

3.3.3 位图的显示

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

::StretchDIBits(PDC->GetSafeHdc(), m_Sest.x, m_Dest.y,

m_DestSize.cx,m_DestSize.cy,

m_Src.x, m_Src.y,

m_SrcSize.cx, m_SrcSize.cy,

m_lpDIBits,(LPBITMAPINFO)m_lpBMPHdr,

DIB_RGB_COLORS,SRCCOPY);

其中的m_Dest、m_DestSize、m_Src、m_SrcSize分别代表了图像在当前设别上显示的左上角坐标，范围以及需要显示的源图像左下角坐标、范围。

3.3.4 位图的存储

DWORDdwBytes=((DWORD)m_lpBMPHdr->biWidth*m_lpBMPHdr->biBitCount()/32;

If(((DWORD)m_lpBMPHdr->biWidth*m_lpBMPHdr->biBitCount)%32){

dwBytes++;}

dwBytes = 4;

m_dwImageSize = dwBytes* m_lpBMPHdr->biHeight;

4 结束语

通过对彩色图像色彩聚类算法的研究，该方法在处理真彩色图像转换成最多256色图像和纺织等行业中有着广泛的应用。

参考文献：

[1] 张弘.数字图像处理与分析[M].北京:机械工业出版社,2007.

[2] 刘海波,沈晶,郭耸,等.Visual C++数字图像处理技术详解[M].北京:机械工业出版社,2010.

[3] 梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006.

[4] Jiawei Han,Micheline Kamber. 数据挖掘概念与技术[M].北京:机械工业出版社,2007.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文