cluster.cpp

图像模式识别的聚类器设计

// Cluster.cpp: implementation of the CCluster class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "mode.h"
#include "Cluster.h"

#include "math.h"
#include "DlgInfor.h"
#include "DlgMohu.h"
#include "DlgFuzzyDistance.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

const int MAX=1000;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CCluster::CCluster()
{
	centernum=0;
	patternnum=0;
	m_pattern=NULL;
	m_center=NULL;

}

CCluster::~CCluster()
{

}
//***********************************************************//
//函数名称		GetFeature()
//参数			void
//返回值		void
//函数功能		将含有数据的图像标号、分割、编号及提取特征值，
//				特征值存入数组m_pattern中。
//************************************************************//	
void CCluster::GetFeature()
{
	////////////////////以下对数据区域标号whx/////////////////////
	
	BYTE * p_temp;
	int stop;
	int i,j;
	int counter;//记录相互独立的连通区域的个数；
	int present;//记录当前点的值1,2,...,counter.

	height=GetHeight();//图像高
	wide=GetWidth();//图像宽，

	stop=0;
	counter=0;
    p_temp=new BYTE[wide*height];//开辟一个临时内存区
	memset(p_temp,255,wide*height);//置白
	
	//从左到右、从上到下标号
	const int T=5;//T为阈值，RGB值小于该阈值被认为是黑，
	for(i=0; i<wide; i++)//将第零行置白
		*(m_pData+(height-1)*wide+i)=255;
	for(j=0;j<height;j++)//将第零列置白
		*(m_pData+(height-j-1)*wide)=255;
	for( j=1;j<height-1;j++)	// 从第一行开始搜索
	{
		if(stop==1)//判断连通区是否太多
			break;
		for( i=1;i<wide-1;i++)	// 从第一列开始搜索
		{
			if(counter>255)
			{
				AfxMessageBox("连通区数目太多，请减少样品个数");
				stop=1;
				return;
			}
			if(*(m_pData+(height-j-1)*wide+i)<T)//若当前点为黑点
			{
				if(*(m_pData+(height-j-1+1)*wide+i+1)<T)//若当前点的右上点为黑点
				{
					*(p_temp+(height-j-1)*wide+i)=*(p_temp+(height-j-1+1)*wide+i+1);//当前点标号应该与右上点相同
					present=*(p_temp+(height-j-1+1)*wide+i+1);//记录当前点的标号
					
					if(*(m_pData+(height-j-1)*wide+i-1)<T && *(p_temp+(height-j-1)*wide+i-1)!=present)//左前与右上点都为黑且标号不同
					{
						int temp=*(p_temp+(height-j-1)*wide+i-1);//记录左前点的标号
						if (present>temp)//当前点标号记录两者中的较小值
						{
							present=temp;
							temp=*(p_temp+(height-j-1+1)*wide+i+1);
						}
						counter--;//合并左前和右上标号，标号总数减一
						for(int m=1;m<=height-1;m++)
							for(int n=1;n<=wide-1;n++)
							{
								if(*(p_temp+(height-m-1)*wide+n)==temp)//将较大标号该成较小标号
								{	
									*(p_temp+(height-m-1)*wide+n)=present;
								}
								else if (*(p_temp+(height-m-1)*wide+n)>temp)//将较大标号以后的所有标号减一，以保持标号的连续性
								{
									*(p_temp+(height-m-1)*wide+n)-=1;
								}
							}
					}//end//左前
					if( *(m_pData+(height-j-1+1)*wide+i-1)<T && *(p_temp+(height-j-1+1)*wide+i-1)!=present)//左上与右上点都为黑且标号不同
					{
						counter--;//合并左上和右上标号，标号总数减一
						int temp=*(p_temp+(height-j-1+1)*wide+i-1);//记录左上点的值
						if (present<temp)//当前点标号记录两者中的较小值
						{
							temp=present;
							present=*(p_temp+(height-j-1+1)*wide+i-1);
						}

						for(int m=1;m<=height-1;m++)
							for(int n=1;n<=wide-1;n++)
							{
								if(*(p_temp+(height-m-1)*wide+n)==present)//将较大标号该成较小标号
								{	
									*(p_temp+(height-m-1)*wide+n)=temp;
								}
								else if (*(p_temp+(height-m-1)*wide+n)>present)//将较大标号以后的所有标号减一，以保持标号的连续性
								{
									*(p_temp+(height-m-1)*wide+n)-=1;
								}
							}
						present=temp;
					}//end//左上
				}
				else if(*(m_pData+(height-j-1+1)*wide+i)<T)//当前点黑，右上不为黑，正上为黑
				{
					*(p_temp+(height-j-1)*wide+i)=*(p_temp+(height-j-1+1)*wide+i);//当前标号＝正上标号
					present=*(p_temp+(height-j-1+1)*wide+i);
				}
				else if(*(m_pData+(height-j-1+1)*wide+i-1)<T)//左上
				{
					*(p_temp+(height-j-1)*wide+i)=*(p_temp+(height-j-1+1)*wide+i-1);
					present=*(p_temp+(height-j-1+1)*wide+i-1);
				}
				else if(*(m_pData+(height-j-1)*wide+i-1)<T)//左前
				{
					*(p_temp+(height-j-1)*wide+i)=*(p_temp+(height-j-1)*wide+i-1);
					present=*(p_temp+(height-j-1)*wide+i-1);
				}
				else//产生新标号
				{				
					++counter;
					present=counter;
					*(p_temp+(height-j-1)*wide+i)=present;
				}
			}//end if
		}// 列
	}//end 行
 // //////////////////////以上对数据区域标号//////////////////////////
				  
					
 //////////////////////以下获得各个样品所在位置及编号///////////////////
	patternnum=counter;//样品总数

	if (m_pattern!=NULL)
		delete []m_pattern;
	m_pattern=new Pattern[patternnum];				
						  
	for( i=0;i<patternnum;i++) 
	{
		m_pattern[i].index=i+1;
		m_pattern[i].category=0;
		m_pattern[i].lefttop.x=wide;
		m_pattern[i].lefttop.y=height;
		m_pattern[i].rightbottom.x=0;
		m_pattern[i].rightbottom.y=0;
	}

	for(int t=1;t<=patternnum;t++)//记录每个样品（独立连通区域）的左上、右下点坐标
	{	
		for(int j=1;j<height-1;j++)//搜索整幅图像
			for(int i=1;i<wide-1;i++)
			{
				if(*(p_temp+(height-j-1)*wide+i)==t)
				{
					if (m_pattern[t-1].lefttop.x>i)//get the lefttop point
						m_pattern[t-1].lefttop.x=i;
					if (m_pattern[t-1].lefttop.y>j)
						m_pattern[t-1].lefttop.y=j;
					if (m_pattern[t-1].rightbottom.x<i)//get the rightbottom point
						m_pattern[t-1].rightbottom.x=i;
					if (m_pattern[t-1].rightbottom.y<j)
						m_pattern[t-1].rightbottom.y=j;
				}				
			}
	}
	
	delete []p_temp;
	//////////////////////以下获得所有样品特征放入m_pattern中//////////////////////////////
	for ( i=0;i<patternnum;i++)//=patternnum
	{
		CalFeature(&m_pattern[i]);//调用函数计算第i号模板的值
	}
	
	//////////////////////以上获得所有样品特征放入m_pattern中//////////////////////////////

}
/***********************************************************
*函数名称		CalFeature(CCluster::Pattern *m_pattern)
*参数			CCluster::Pattern *m_pattern
*返回值	    	void
*函数功能		计算样品m_pattern的特征值，存入m_pattern－>feature中
*************************************************************/
void CCluster::CalFeature(CCluster::Pattern *m_pattern)
{
	int w,h,count;
	int i,j;

	w=(int)(m_pattern->rightbottom.x-m_pattern->lefttop.x)/N;//特征值中每个特征的宽
	h=(int)(m_pattern->rightbottom.y-m_pattern->lefttop.y)/N;//特征值中每个特征的高

	for ( j=0;j<N;j++)//col
	{
		for ( i=0;i<N;i++)//line
		{
			count=0;//每个特征内黑点的个数
            for(int m= height-m_pattern->rightbottom.y+h*j;m<height-m_pattern->rightbottom.y+h*j+h;m++)//col
				for (int n=m_pattern->lefttop.x+i*w; n<m_pattern->lefttop.x+i*w+w; n++)//line
					if (*(m_pData+m*wide+n)==0)
						count++;
			m_pattern->feature[j*N+i]=(double)count/(double)(w*h);
		}
	}
}

/*********************************************************
*函数名称		CalCenter(CCluster::Center *pcenter)
*参数			CCluster::Center *pcenter
*返回值		    void
*函数功能		计算中心pcenter的特征值（本类所有样品的均值），及样品个数
************************************************************/	
void CCluster::CalCenter(CCluster::Center *pcenter)
{
	double temp[N*N];//临时存储中心的特征值
	int a=0;//记录该类中元素个数
	for (int i=0;i<N*N;i++)//中心清空
		temp[i]=0;
	for (i=0;i<patternnum;i++)
		if (m_pattern[i].category==pcenter->index)//累加中心所有样品
		{
			a++;
			for (int j=0;j<N*N;j++)
				temp[j]+=m_pattern[i].feature[j];
		}
	pcenter->patternnum=a;
	for ( i=0;i<N*N;i++)
			if(a!=0)
			{
				pcenter->feature[i]=(double)(temp[i]/(double)a);//取均值
			}
			else
			{
				pcenter->feature[i]=temp[i];
			}

}

/***********************************************************
*函数名称		GetDistance( CCluster::Pattern pattern1, CCluster::Pattern  pattern2, const int distype)
*参数			CCluster::Pattern pattern1   样品1
*				CCluster::Pattern pattern2	 样品2
*				const int distype	         距离模式  1：欧氏距离；2：夹角余弦距离；
*													   3：特征是二值时的夹角余弦距离；4：具有二值特征的Tanimoto测度
*返回值	    	double
*函数功能		计算样品1和样品2间的距离，距离模式由参数distype给定
*************************************************************/
double CCluster::GetDistance( CCluster::Pattern pattern1, CCluster::Pattern  pattern2, const int distype)
{

	double   result;
	result=0;

	if (distype==1)//欧氏距离
	{
		for (int i=0; i<N*N; i++)
			result+=(pattern1.feature[i]-pattern2.feature[i])*(pattern1.feature[i]-pattern2.feature[i]);
		return (double)sqrt(result);
	}
	else if (distype==2)//夹角余弦
	{
		double	a,b1,b2;
		a=0;
		b1=0;
		b2=0;
		for (int i=0; i<N*N; i++)
		{
			a+=pattern1.feature[i]*pattern2.feature[i];
			b1+=pattern1.feature[i]*pattern1.feature[i];
			b2+=pattern2.feature[i]*pattern2.feature[i];
		}
		if (b2*b1!=0)
		result=a/sqrt(b1*b2);
		else 
		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==3)//二值夹角余弦
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=pattern1.feature[i]>0.2? 1:0;
			t2[i]=pattern2.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if (b2*b1!=0)
		result=(double)(a/sqrt(b1*b2));
		else 
		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==4)//Tanimoto
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=pattern1.feature[i]>0.2? 1:0;
			t2[i]=pattern2.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if ((b2*b1-a)!=0)
		result=(double)(a/(b1+b2-a));
		else 
		{
			return -1;
		}
		return (1-result);
	}
	else
		return -1;

}
/***************************************************************
*函数名称		GetDistance(CCluster::Pattern pattern,  CCluster::Center center, const int distype)
*参数			CCluster::Pattern pattern  样品
*				CCluster::Center center    中心
*				const int distype	         距离模式  1：欧氏距离；2：夹角余弦距离；
*													   3：特征是二值时的夹角余弦距离；
*													   4：具有二值特征的Tanimoto测度
*返回值			double
*函数功能		计算样品和聚类中心间的距离，距离模式由distype给定
************************************************************/
double CCluster::GetDistance(CCluster::Pattern pattern,  CCluster::Center center, const int distype)
{
	double   result;
	result=0;

	if (distype==1)//欧氏距离
	{
		for (int i=0; i<N*N; i++)
			result+=(pattern.feature[i]-center.feature[i])*(pattern.feature[i]-center.feature[i]);
		return (double)sqrt(result);
	}
	else if (distype==2)//夹角余弦
	{
		double	a,b1,b2;
		a=0;
		b1=0;
		b2=0;
		for (int i=0; i<N*N; i++)
		{
			a+=pattern.feature[i]*center.feature[i];
			b1+=pattern.feature[i]*pattern.feature[i];
			b2+=center.feature[i]*center.feature[i];
		}
		if (b2*b1!=0)
		result=a/sqrt(b1*b2);
		else 
		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==3)//二值夹角余弦
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=pattern.feature[i]>0.2? 1:0;
			t2[i]=center.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if (b2*b1!=0)
		result=a/sqrt(b1*b2);
		else 
		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==4)//Tanimoto
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=pattern.feature[i]>0.2? 1:0;
			t2[i]=center.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if ((b2*b1-a)!=0)
		result=(double)(a/(b1+b2-a));
		else 
		{
			return -1;
		}
		return (1-result);
	}
	else
		return -1;
}
/*************************************************************
*函数名称		GetDistance(CCluster::Center mCenter1,CCluster::Center mCenter2,int distype)
*参数			CCluster::Center mCenter1   中心1
*				CCluster::Center mCenter2   中心2
*				const int distype	         距离模式   1：欧氏距离；2：夹角余弦距离；		
*											            3：特征是二值时的夹角余弦距离；
*														4：具有二值特征的Tanimoto测度
*返回值			double
*函数功能		计算两个聚类中心间的距离，距离模式由distype给定
*************************************************************/
double CCluster::GetDistance(CCluster::Center mCenter1,CCluster::Center mCenter2,int distype)
{
	double result;
	result=0;

	if (distype==1)//欧氏距离
	{
		for ( int m=0;m<N*N;m++)
		result+=(mCenter1.feature[m]-mCenter2.feature[m])*(mCenter1.feature[m]-mCenter2.feature[m]);
		return (double)sqrt(result);
	}
	else if (distype==2)//夹角余弦
	{
		double	a,b1,b2;
		a=0;
		b1=0;
		b2=0;
		for (int i=0; i<N*N; i++)
		{
			a+=mCenter1.feature[i]*mCenter2.feature[i];
			b1+=mCenter1.feature[i]*mCenter1.feature[i];
			b2+=mCenter2.feature[i]*mCenter2.feature[i];
		}
		if (b2*b1!=0)
		result=a/sqrt(b1*b2);
		else 
		{
			return -1;
		}

		return (1-result);
	}
	else if (distype==3)//二值夹角余弦
	{
		int *t1,*t2;
		int a,b1,b2;
		 
		a=0;b1=0;b2=0;
		t1=new int [N*N];
		t2=new int [N*N];
		for(int i=0; i<N*N; i++)
		{
			t1[i]=mCenter1.feature[i]>0.2? 1:0;
			t2[i]=mCenter2.feature[i]>0.2? 1:0;
		}
		
		for ( i=0; i<N*N; i++)
		{
			a+=t1[i]*t2[i];
			b1+=t1[i]*t1[i];
			b2+=t2[i]*t2[i];
		}
		delete	[]t1;
		delete	[]t2;
		if (b2*b1!=0)
		result=(double)(a/sqrt(b1*b2));
		else