Міністерство освіти та науки України Національний університет “Львівська політехніка”
Звіт про виконання лабораторної роботи №7 на тему: «Дослідження алгоритмів розпізнавання образів. Алгоритм максимінної відстані» Львів – 2007 1.Мета роботи Вивчити принципи роботи максимінного алгоритму розпізнавання образів. Написати програму реалізації алгоритму з графічним інтерфейсом користувача. 2. Короткі теоретичні відомості 2.1. Максимінний алгоритм розпізнавання образів Алгоритм використовує евклiдову вiдстань. Алгоритм, у принципi, аналогiчний схемi евристичного алгоритму порогової величини, за виключенням тiєї обставини, що, в першу чергу, вин виявляє найвiддаленiшi кластори. Один з об'єктiв (X1) довiльним чином назначається центром першого кластера. Потiм вiдшукується образ, розмiщений вiд образа X1 найдалi, який призначається центром кластера Z2. На третьому кроцi алгоритму здiйснюється обчислення вiдстаней мiж всiма iншими образами вибiрки i центрами кластерiв Z1 i Z2. В кожнiй парi цих вибірок вибирається мiнiмальне. Пiсля цього видiляється максимальне з цих мiнiмальних вiдстаней. Якщо останнє складає значну частину вiдстанi мiж кластерами Z1 i Z2 (половина цiєї вiдстанi), вiдповiдний образ призначається центром кластера Z3. Iнакше - виконання алгоритму припиняється. В загальному випадку описана процедура повторюється до тих пiр, поки на якомусь кроцi не буде отримане максимальне значення вiдстанi, для якої умова, що викликає видiлення кластера, не виконується. ( 1. Z1=X1 2. Обчислити Di1 3. Вибрати Ki(1)=max{Di1} ( i(1 ; L1=Ki(1) ( 4. Z2=Xi 5. Обчислити Di1, Di2 ( i(1,2 6. Обчислити Ai=min{Di1,Di2} ( i(1,2 7. Обчислити Ki(2)=max{Ai} ( i(1,2 ; L2=Ki(2) ( 8. Якщо L2>0.5L1, тодi Z3=Xi. Iнакше - STOP. 9. Визначити середню арифметичну величину попереднiх максимальних вiдстаней: Lc.a.=(L1+L2)/2 10. Обчислити Di1, Di2, Di3 ( i(1,2,3 11. Обчислити Ai=min{Di1, Di2, Di3} 12. Обчислити Ki(3)=max{Ai} ; L3=Ki(3) ( 13. Якщо Li>0.5La.c., тодi Z4=Xi. Iнакше - STOP. 14. Обчислити Lc.a.=(L1+L2+L3)/3 Індивідуальне завдання Здійснити розпізнавання образів із застосуванням максимінного алгоритму. 4.10. Х1(2,10), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(11,11). Текст програми: #include<conio.h> #include<stdio.h> #include<graphics.h> #include<math.h> #define N 11 typedef struct point {int i; float x,y;}; typedef struct meas {int i; float d;}; void graphic(float *x,float *y,point *z,int k); main() {float X[N]={2,3,3,3,4,9,9,10,10,10,11}; float Y[N]={10,3,4,9,8,5,6,5,5,6,11}; point Z[N]; float D[N][N],sum; meas K[N],A,L[11]; int i,j,k; clrscr(); Z[0].i=0;Z[0].x=X[0];Z[0].y=Y[0]; K[0].i=1;K[0].d=D[i][0]=sqrt(pow(Z[0].x-X[1],2)+pow(Z[0].y-Y[1],2)); for(i=1;i<N;i++) {D[i][0]=sqrt(pow(Z[0].x-X[i],2)+pow(Z[0].y-Y[i],2)); if(D[i][0]>K[0].d) {K[0].d=D[i][0];K[0].i=i;};} L[0]=K[0]; Z[1].x=X[K[0].i];Z[1].y=Y[K[0].i];Z[1].i=K[0].i;k=1; mm: for(i=k;i<N;i++) { K[i].d=sqrt(pow(Z[0].x-X[i],2)+pow(Z[0].y-Y[i],2));K[0].i=i; for(j=1;j<=k;j++) { D[i][j]=sqrt(pow(Z[j].x-X[i],2)+pow(Z[j].x-X[i],2)); if(D[i][j]<K[i].d) {K[i].d=D[i][j];K[i].i=i;} } } A=K[k]; for(i=k;i<11;i++) if(A.d<K[i].d) A=K[i]; L[k]=A; sum=0; for(i=0;i<k-1;i++) sum=sum+L[0].d;sum=sum/k; if(L[k].d>(0.5*sum)) {Z[k+1].i=L[k].i;Z[k+1].x=X[L[k].i];Z[k+1].y=Y[L[k].i];k++;goto mm;} else goto bb; bb: textcolor(2); cprintf("VUVID TOCHOK:"); for(i=0;i<11;i++) printf("\nX%d(%2.1f,%2.1f);",i+1,X[i],Y[i]); printf("\n");cprintf("VUVID ZENTRIV:"); for(i=0;i<=k;i++) printf("\nZ[%d]=X%d(%2.1f,%2.1f);",i+1,Z[i].i+1,Z[i].x,Z[i].y); getch(); graphic(X,Y,Z,k); return 0;} void graphic(float *x,float *y,point *Z,int k) {int d,i,j; int driver=DETECT,mode; clrscr(); initgraph(&driver,&mode,""); setcolor(15); line(11,460,600,460); for(i=11;i<585;i++) if(fmod(i,10.0)==0) line(i,457,i,463); line(600,460,590,455);line(600,460,590,465); outtextxy(610,460,"X"); outtextxy(10,470,"0"); line(10,460,10,50); for(i=459;i>61;i--) if(fmod(i,20.0)==0) line(7,i,13,i); line(10,50,5,60);line(10,50,15,60); outtextxy(10,40,"Y"); setfillstyle(1,2); setcolor(2); for(i=0;i<N;i++) {circle(x[i]*10+10,(y[i]*20-480)*(-1)-20,2); floodfill(x[i]*10+10,(y[i]*20-480)*(-1)-20,2);} setfillstyle(1,4); setcolor(4); for(j=0;j<=k;j++) {circle(Z[j].x*10+10,(Z[j].y*20-480)*(-1)-20,2); floodfill(Z[j].x*10+10,(Z[j].y*20-480)*(-1)-20,4);} getch(); closegraph(); return;}