k－means聚类.txt

VC k-means聚类算法源码。kmeans是一种常用的分割算法

/************************************************************************************************/
/*功能：kmeans分割 */
/*参数说明：lpDIBBits－指向DIB位图数据的指针, lWidth－BMP图像宽度,lHeight－BMP图像高度,k－聚类个数*/
void KMeans(BYTE *lpDIBBits, LONG lWidth, LONG lHeight,int k)
{
	unsigned char * lpSrc;
	LONG lLineBytes;	//图像每行的字节数
	lLineBytes=WIDTHBYTES(lWidth*8);       //计算图像每行的字节数,假设为256色
	
	int* mark=(int *)HeapAlloc(GetProcessHeap(),0,lWidth*lHeight*sizeof(int));
	float* formalCluster=(float*)HeapAlloc(GetProcessHeap(),0,k);//前次的聚类中心
	float* lastCluster=(float*)HeapAlloc(GetProcessHeap(),0,k);//本次的聚类中心
	const float e=(float)0.1;//误差
	bool flag=true;//迭代结束标志
	LONG i,j,m; //循环变量

	float sum;
	LONG totalPixel;
	BYTE inteval=255/(k+1);
	//初始的聚类中心
	formalCluster[0]=inteval;
	for(i=1;i<k;i++)
	{
		formalCluster[i]=formalCluster[i-1]+inteval;
	}
	
	//迭代计算聚类中心
	while (flag) 
	{
		//根据前次的聚类中心，把各个象素点分类
		for(m=0;m<k;m++)//每个聚类
		{
			for(i=0;i<lHeight;i++)//每个象素点
				for(j=0;j<lWidth;j++)
				{
					lpSrc=pixelValue(i,j);
					mark[i*lWidth+j]=mostSim(*lpSrc,formalCluster,k);
				}
		}
		//根据分类的象素点，重新计算聚类中心
		
		for(m=0;m<k;m++)//每个聚类
		{
			sum=0;
			totalPixel=0;
			for(i=0;i<lHeight;i++)//每个象素点
				for(j=0;j<lWidth;j++)
				{
					lpSrc=pixelValue(i,j);
					if(mark[i*lWidth+j]==m)//该点属于这个聚类
					{	
						sum=sum + *lpSrc;
						totalPixel++;
					}

				}
			lastCluster[m]=sum/totalPixel;//用所有属于这个聚类的点的灰度均值作为新的聚类中心
		}
		//比较原聚类中心和新的聚类中心的误差
		bool unchanged=true;
		for(m=0;m<k;m++)
		{
			if((float)fabs(formalCluster[m]-lastCluster[m])>e)
			{
				unchanged=false;
				break;
			}
		}
		flag=!unchanged;
		
		//用新的聚类中心代替原聚类中心，再开始下次迭代
		if(flag)
		{
			memcpy(formalCluster,lastCluster,k*sizeof(float));
		}
	}
	//根据划分好的类别，输出图像
		for(i=0;i<lHeight;i++)//每个象素点
			for(j=0;j<lWidth;j++)
			{
				lpSrc=pixelValue(i,j);
				*lpSrc=(unsigned char)lastCluster[mark[i*lWidth+j]];//mark[i][j]就是ij点的类别编号
			}
	//释放空间
	HeapFree(GetProcessHeap(),0,formalCluster);
	HeapFree(GetProcessHeap(),0,lastCluster);
	HeapFree(GetProcessHeap(),0,mark);
}
/************************************************************************************************/
/*函数功能：找到最相近的类别编号*/
/*参数含义：pixel－象素值, clusterCen－聚类中心, k聚类个数*/
/*函数返回值：返回与象素值pixel最相近的聚类编号*/
int mostSim(BYTE pixel, float *clusterCen, int k)
{
	int i,result=0;
	float* sim=(float *)HeapAlloc(GetProcessHeap(),0,k*sizeof(float));
	//cal the similarities to those clusters
	for(i=0;i<k;i++)
	{
		sim[i]=(float)fabs(clusterCen[i]-pixel*1.0);		
	}
	//find the most sim cluster
	for(i=0;i<k;i++)
	{
		if(sim[i]<sim[result])
			result=i;
	}
	HeapFree(GetProcessHeap(),0,sim);
	return result;
}