| 基于遗传算法的图像模式识别 |
|
| 作者：佚名 文章来源：本站原创 点击数： 更新时间：2006-6-21 |
|
|
/**********************************************************************/
/* 基于遗传算法的图像模式识别 PATMAT.C */
/***********************************************************************/
#include
#include
#include
#include
#include
#include
#include "graph.c"
#include "operator.c"
/* 宏定义 */
#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
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);
}
setcolor(9);
disp_hz16("加入噪声否? no:1 yes:2===>",10,380,20);
gscanf(400,380,9,0,2,"%s",choice);
yn=atoi(choice);
if(yn==2)
for(i=0;i<3000;i++)
g_pset(261+random(119),141+random(119),0);
m_num=0;
for(y1=141;y1<260;y1++)
for(x1=261;x1<380;x1++)
{
col=g_pget(x1,y1);
if(col!=0)
{
m_pnts[0][m_num]=x1;
m_pnts[1][m_num]=y1;
m_num=m_num+1;
}
}
wx=0;wy=0;work=(double)m_num;
for(i=1;i<=m_num;i++)
{
wx=wx+(double)(m_pnts[0][i-1])/work;
wy=wy+(double)(m_pnts[1][i-1])/work;
}
x1=(int)wx;y1=(int)wy;
for(i=1;i<=m_num;i++)
{
m_pnts[0][i-1]=m_pnts[0][i-1]-x1;
m_pnts[1][i-1]=m_pnts[1][i-1]-y1;
}
}
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
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
{
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
for(j=i+1;j
if(fitness[j]>fitness[i]) swap_fit(j,i);
max_fit=fitness[0];
avg_fit=0;
for(i=0;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
{
gene_to_param(i,&xsft,&ysft,&angle);
sum=0;
for(j=0;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
{
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
{
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
{
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
{
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
{
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
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();
}
|
