基于遗传算法的图像模式识别 .c

这是一个基于遗传算法的图像模式识别的程序

/**********************************************************************/
/*         基于遗传算法的图像模式识别  PATMAT.C                       */
/***********************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>

#define POP_SIZE  20
#define S_RATE   0.4
#define M_RATE   0.2
#define DEFOCUS_L  4

#define G_LENGTH  15       /* 个体遗传基因位长  */
#define XUL      100
#define YUL      250
#define GX1      360
#define GY1      66
#define GX2      360
#define GY2      257
#define GXR      250
#define GYR      100
#define GSTEP     2
/* 全局变量 */
unsigned  char  gene[POP_SIZE][G_LENGTH];    /*  个体遗传基因      */
unsigned  char  image[128][128];
double  fitness[POP_SIZE];
double  _sin[8];_cos[8];
double  max_fit,avg_fit;
int  m_num;
int  m_pnts[2][1000];
int  pnts[2][1000];

void g_draw_frame(x1,y1,x2,y2,c1,c2,c3,c4,text)
int x1,y1,x2,y2,c1,c2,c3,c4;
char *text;
{  int n,x3;
   g_rectangle(x1,y1,x2,y2,c1,1);
   g_rectangle(x1,y1,x2,y2,c2,0);
   g_rectangle(x1,y1,x2,y1+16,c3,1);
   g_rectangle(x1,y1,x2,y1+16,c2,0);
   n=strlen(text);
   x3=x1+((x2-x1-n*8)/2);
   disp_hz16(text,x3,y1,c4);
}

void g_disp_image()
{
   int i,j;
   for(i=0;i<128;i++)
     for(j=0;j<128;j++)
      g_pset(XUL+j,YUL+i,image[j][i]);
}

void g_init_frames()  /*  初始化画面  */
{
  int i,j,cx,cy,x,y;
  char text[17];
  g_draw_frame(0,0,639,399,15,0,4,15,
      "基于遗传算法的基元识别与提取");
  g_draw_frame(0,16,320,170,7,15,8,15,"基元");
  itoa(m_num,text,10);
  setcolor(9);
  disp_hz16("构成点数=",30,50,15);
  disp_hz16(text,118,50,15);
  for(i=0;i<m_num;i++)
     g_pset(m_pnts[0][i]+160,m_pnts[1][i]+110,4);
  g_draw_frame(0,170,320,399,7,15,8,15, "");
  g_draw_frame(0,170,320,399,7,15,8,15, "原图像");
  g_rectangle(XUL-1,YUL-1,XUL+128,YUL+128,15,0);
  g_disp_image();
  setcolor(9);
  disp_hz16("像素数 = 128X128",30,200,15);
  disp_hz16("灰阶数 = ",30,220,15);
  itoa(DEFOCUS_L,text,10);
  disp_hz16(text,102,220,15);
  g_draw_frame(320,16,639,207,7,15,8,15, "");
  g_draw_frame(320,16,639,207,7,15,8,15, "遗传算法适应度进化曲线");
  g_draw_frame(320,207,639,399,7,15,8,15, "随机搜索适应度变化曲线");
  }

void g_init_graphs()
{
   g_rectangle(GX1,GY1,GX1+GXR,GY1+GYR,0,1);
   g_rectangle(GX1,GY1,GX1+GXR,GY1+GYR,6,0);
   setcolor(1);
   disp_hz16("最大适应度",GX1+5,GY1-18,15);
   g_line(GX1+90,GY1-10,GX1+110,GY1-10,1);
   setcolor(4);
   disp_hz16("平均适应度",GX1+120,GY1-18,15);
   g_line(GX1+205,GY1-10,GX1+225,GY1-10,4);
   setcolor(15);
   disp_hz16("世代数",GX1+168,GY1+GYR+10,15);
   g_text(GX1-20,GY1,15,"1.0");
   g_text(GX1-20,GY1+GYR,15,"0.0");

   g_rectangle(GX2,GY2,GX2+GXR,GY2+GYR,0,1);
   g_rectangle(GX2,GY2,GX2+GXR,GY2+GYR,6,0);
   setcolor(1);
   disp_hz16("最大适应度",GX2+5,GY2-18,15);
   g_line(GX2+90,GY2-10,GX2+110,GY2-10,1);
   setcolor(4);
   disp_hz16("平均适应度",GX2+120,GY2-18,15 );
   g_line(GX2+205,GY2-10,GX2+225,GY2-10,4);
   setcolor(15);
   disp_hz16("世代数",GX2+168,GY2+GYR+10,15);
   g_text(GX2-20,GY2,15,"1.0");
   g_text(GX2-20,GY2+GYR,15,"0.0");
 }

 void  g_set_model()
{
   int n;
   int x1,y1,x2,y2,x3,y3;
   int i,j,ok,n1,n2,yn,col;
   double  rad[90],wx,wy,work;
   char choice[2];
   ok=1;
   while(ok==1)
   {
     g_cls();
     settextstyle(0,0,4);
     gprintf(220,20,4,0,"PM-GA");
     setcolor(9);
     disp_hz24("基于遗传算法的基元识别与提取",150,50,25);
     disp_hz16("河南工业大学计算机系    名字",150,100,20);
     setcolor(9);
     disp_hz16("选择基元：",10,150,20);
     disp_hz16("1:三角形，2:矩形 3:圆或椭圆，4:不规则形==>",10,300,20);
     gscanf(420,300,4,0,2,"%s",choice);
     n=atoi(choice);
     switch(n)
     {
         case 1:
           x1=345;y1=225;
           x2=x1-25-random(25);y2=y1;
           x3=x1;y3=y1-25-random(25);
           g_line(x1,y1,x2,y2,9);
           g_line(x1,y1,x3,y3,9);
           g_line(x2,y2,x3,y3,9);break;
          case 2:
           x1=345;y1=225;
           x2=x1-25-random(25);
           y2=y1-25-random(25);
           g_rectangle(x2,y2,x1,y1,9,0);break;
          case 3:
           x1=320;y1=200;
           x2=10+random(25);
           y2=10+random(25);
           g_circle(x1,y1,x2,y2,9);break;
          case 4:
           x1=320;y1=200;
           rad[0]=10+random(15);
           for(i=1;i<90;i++)
           {
	    rad[i]=rad[i-1]-4+random(9);
            if(rad[i]<10)  rad[i]=10.0; else
            if(rad[i]>25)  rad[i]=25.0;
           }
    for(i=1;i<3;i++)
      for(j=0;j<90;j++)
         {
         if((j-1)<0)  n1=89; else n1=j-1;
         if((j+1)>89)  n2=0; else n2=j+1;
         rad[j]=(rad[n1]+rad[j]+rad[n2])/3.0;
         }
      for(i=0;i<90;i++)
    {
         if((i+1)>89)  n1=0; else n1=i+1;
         x2=(int)(rad[i]*cos(i/45.0*3.14))+x1;
         y2=(int)(rad[i]*sin(i/45.0*3.14))+y1;
         x3=(int)(rad[n1]*cos((double)n1/45.0*3.14))+x1;
         y3=(int)(rad[n1]*sin((double)n1/45.0*3.14))+y1;
         g_line(x2,y2,x3,y3,9);
     }
}
  g_rectangle(260,140,380,260,4,0);
  setcolor(9);
  disp_hz16("轮廓圆滑处理满意否?  no:1  yes:2===>",10,340,20);
  gscanf(400,340,4,0,2,"%s",choice);
  ok=atoi(choice);
}
 



void  g_set_image()
{
  int ok,i;
  int cx,cy,gx,gy,x,y,col,xx,yy,xymax;
  double  angle,x1,y1;
  char choice[2];
  for(i=0;i<8;i++)
  {
  _sin[i]=sin((double)i*45.0/360.0*3.141592);
  _cos[i]=cos((double)i*45.0/360.0*3.141592);
 }
xymax=64;
cx=200;cy=100;
ok=1;
while(ok==1)
{
     g_cls();
     for(i=0;i<25;i++)  printf("\n");
     g_rectangle(cx-1,cy-1,cx+128,cy+128,9,0);
     for(i=0;i<3;i++)
      g_line(random(128)+cx,random(128)+cy,
		random(128)+cx,random(128)+cy,9);
     for(i=0;i<1;i++)
      g_circle(random(64)+cx+32,random(64)+cy+32,
		random(20)+10,random(20)+10,9);
     for(i=0;i<5000;i++)
	g_pset(random(128)+cx,random(128)+cy,0);
     for(i=0;i<200;i++)
        g_pset(random(128)+cx,random(128)+cy,9);
     gx=random(xymax)-xymax/2;
     gy=random(xymax)-xymax/2;
     angle=random(8);
     for(i=1;i<=m_num;i++)
     {
       x1=(double)m_pnts[0][i-1];
       y1=(double)m_pnts[1][i-1];
       x=(int)(_cos[angle]*x1-_sin[angle]*y1)+64+cx+gx;
       y=(int)(_sin[angle]*x1+_cos[angle]*y1)+64+cy+gy;
       g_pset(x,y,9);
     }
  setcolor(9);
  disp_hz16("绘制原图像满意否?  no:1  yes:2===>",10,240,20);
  gscanf(300,240,4,0,2,"%s",choice);
  ok=atoi(choice);
}
 for(y=0;y<128;y++)
 for(x=0;x<128;x++)
  {
   col=g_pget(x+cx,y+cy);
   if(col>0)   image[x][y]=DEFOCUS_L;
    else  image[x][y]=0;
  }
 for(y=0;y<128;y++)
{
/*   printf("%d/128\n",y+1);*/
   for(x=0;x<128;x++)
    if(image[x][y]==DEFOCUS_L)
       for(i=0;i<DEFOCUS_L;i++)
        for(gy=-i;gy<=i;gy++)
        for(gx=-i;gx<=i;gx++)
         {
           xx=x+gx;yy=y+gy;
           if(xx>=0 && xx<=127 && yy>0 && y<=127)
	      if(image[xx][yy]==(DEFOCUS_L-i))
		   image[xx][yy]=DEFOCUS_L-i;
	 }
 }
for(y=0;y<128;y++)
 for(x=0;x<128;x++)
  g_pset(x+cx,y+cy,image[x][y]);
setcolor(9);
disp_hz16("回车键结束",10,430,20);
getch();
for(i=0;i<25;i++)  printf("\n");
}

void swap_fit(n1,n2)
int n1,n2;
{
   unsigned  char c;
   double  f;
   int i;
   for(i=0;i<G_LENGTH;i++)
   {
    c=gene[n1][i];
    gene[n1][i]=gene[n2][i];
    gene[n2][i]=c;
   }
f=fitness[n1];
fitness[n1]=fitness[n2];
fitness[n2]=f;
}

 void sort_fitness(p_size)
int p_size;
{
  int i,j;
  for(i=0;i<p_size-1;i++)
  for(j=i+1;j<p_size;j++)
    if(fitness[j]>fitness[i]) swap_fit(j,i);
  max_fit=fitness[0];
  avg_fit=0;
    for(i=0;i<p_size;i++)
   avg_fit=avg_fit+fitness[i]/(double)p_size;
}

 void  gene_to_param(num,xsft,ysft,angle)
int num,*xsft,*ysft,*angle;
{
int xymax,i;
xymax=64;
*xsft=0;*ysft=0;
for(i=0;i<6;i++)
{
  *xsft=*xsft*2+gene[num][i];
  *ysft=*ysft*2+gene[num][i+6];
}
  *xsft=*xsft-xymax/2;
  *ysft=*ysft-xymax/2;
  *angle=0;
  for(i=12;i<15;i++)
   *angle=*angle*2+gene[num][i];
}

  void  calc_fitness(p_size)
int p_size;
{
 int i,j,xsft,ysft,angle,x1,y1,x2,y2;
 double sum,fitmax;
  fitmax=(double)(DEFOCUS_L*m_num);
    for(i=0;i<p_size;i++)
{
   gene_to_param(i,&xsft,&ysft,&angle);
   sum=0;
   for(j=0;j<m_num;j++)
   {
       x1=(double)m_pnts[0][j];
       y1=(double)m_pnts[1][j];
       x2=(int)(_cos[angle]*x1-_sin[angle]*y1)+64+xsft;
       y2=(int)(_sin[angle]*x1+_cos[angle]*y1)+64+ysft;
       if(x2>=0 && x2<128 && y2>=0 && y2<128)
          sum=sum+(double)image[x2][y2];
   }
       fitness[i]=sum/fitmax;
 }
}

 void g_disp_max(flg)
int flg;
{
   int i,xsft,ysft,angle,x,y;
  if(flg==1)
  {
   for(i=0;i<m_num;i++)
  {
    x=pnts[0][i]; y=pnts[1][i];
    if(x>=0 && x<128 && y>=0 && y<128)
      g_pset(XUL+x,YUL+y,image[x][y]);
  }
}
   gene_to_param(0,&xsft,&ysft,&angle);
for(i=0;i<m_num;i++)
{
       x=(double)m_pnts[0][i];       
       y=(double)m_pnts[1][i];
       pnts[0][i]=(int)(_cos[angle]*x-_sin[angle]*y)+64+xsft;
       pnts[1][i]=(int)(_sin[angle]*x+_cos[angle]*y)+64+ysft;
}
for(i=0;i<m_num;i++)
{
       x=pnts[0][i];
       y=pnts[1][i];
    if(x>=0 && x<128 && y>=0 && y<128)
      g_pset(XUL+x,YUL+y,9);
  }
}

void  make_offspring(g1,g2,g3,g4)
int g1,g2,g3,g4;
{
  int i,rnd,rndmax;
  two_crossover(gene,g1,g2,g3,g4,G_LENGTH);
  rndmax=(int)(10000.0*M_RATE);
  for(i=0;i<G_LENGTH;i++)
  {
    rnd=random(10000);
    if(rnd<=rndmax)
       if(gene[g3][i]==0) gene[g3][i]=1;
        else   gene[g3][i]=0;
    rnd=random(10000);
    if(rnd<=rndmax)
       if(gene[g4][i]==0) gene[g4][i]=1;
        else   gene[g4][i]=0;
   }
}
  void ga_reproduction()
{
  int i,n,p1,p2;
  n=(int)(POP_SIZE*S_RATE/2.0);
  for(i=0;i<n;i++)
  {
  p1=random(n*2);
  p2=random(n*2);
  while(p2==p1)
  p2=random(n*2);
  make_offspring(p1,p2,POP_SIZE-i*2-1,POP_SIZE-i*2-2);
  }
}

 void g_disp_fitness(n,gen_num,mfold,afold,mf,af) 
 int n,gen_num;
 double mfold,afold,mf,af;
 {
  int x,y,gx,gy,x_old,y_old;
  char text[8];
  if(n==1) {gx=GX1;gy=GY1;}
    else {gx=GX2;gy=GY2;}
  if(gen_num%10==0)
  {
     x=gx+(gen_num-1)*GSTEP;
     g_line(x,gy+1,x,gy+GYR-1,1);
     sprintf(text,"%d",gen_num);
     if(gen_num<100||gen_num%20==0)
      g_text(x-8,gy+GYR+7,15,text);
  }
  x_old=(int)(gx+(gen_num-1)*GSTEP);
  x=x_old+(int)GSTEP;
  y_old=(int)gy+GYR-mfold*GYR;
  y=(int)gy+GYR-mf*GYR;
  g_line(x_old,y_old,x,y,1);
  y_old=gy+GYR-(int)(afold*GYR);
  y=gy+GYR-(int)(af*GYR);
  g_line(x_old,y_old,x,y,4);
}

  void ga_search()
{
  int gen_num;
  double mfold,afold;
  initialize_gene(gene,POP_SIZE,G_LENGTH);
  calc_fitness(POP_SIZE);
  sort_fitness(POP_SIZE);
  g_disp_max(0);
  mfold=max_fit;afold=avg_fit;
  ga_reproduction();
  for(gen_num=1;gen_num<=120;gen_num++)
  {
  calc_fitness(POP_SIZE);
  sort_fitness(POP_SIZE);
  g_disp_fitness(1,gen_num,mfold,afold,max_fit,avg_fit);
  g_disp_max(1);
  mfold=max_fit;afold=avg_fit;
  ga_reproduction();
}
  g_disp_image();
}

  void  make_random_gene(p_size)
int p_size;
{
  int i,j,rnd;
    for(i=0;i<p_size;i++)
    for(j=0;j<15;j++)
     if(random(100)<50) gene[i][j]=0;
       else gene[i][j]=1;
}

void  random_search()
{
  int p_size,gen_num;
  double mfold,afold;
  p_size=(int)(POP_SIZE*S_RATE);
  make_random_gene(p_size);
  calc_fitness(p_size);
  sort_fitness(p_size);
  g_disp_max(0);
  mfold=max_fit;afold=avg_fit;
  for(gen_num=1;gen_num<=120;gen_num++)
 {
  make_random_gene(p_size);
  calc_fitness(p_size);
  sort_fitness(p_size);
  g_disp_fitness(2,gen_num,mfold,afold,max_fit,avg_fit);
  g_disp_max(1);
  mfold=max_fit;afold=avg_fit;
 }
  g_disp_image();
}

main()
{
randomize();
/* 图形界面初始化 */
g_init();
init_mouse(0,6,1);
setcolor(9);
mouse_on(0);
g_set_model();
g_set_image();
g_init_frames();
g_init_graphs();
ga_search();
random_search();
setcolor(9);
disp_hz16("回车键结束",10,430,20);
getch();
}
.