Дослідження алгоритмів розпізнавання образів. Алгоритм k-внутрішніх групових середніх. Звіт про виконання лабораторної роботи з Інші. Робота № 531269

Дослідження алгоритмів розпізнавання образів. Алгоритм k-внутрішніх групових середніх

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Не вказано

Інформація про роботу

Рік:

2020

Тип роботи:

Звіт про виконання лабораторної роботи

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт про виконання лабораторної роботи №8 на тему: «Дослідження алгоритмів розпізнавання образів. Алгоритм k-внутрішніх групових середніх» Львів – 2007 1.Мета роботи Вивчити принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів. Написати програму реалізації алгоритму з графічним інтерфейсом користувача. 2. Короткі теоретичні відомості 2.1. Алгоритм k-внутрішніх групових середніх розпізнавання образів КРОК 1. Вибираються к початкових центрiв кластерiв Z1(1), Z2(1),...,Zk(1). Цей вибір здiйснюється довiльно i, звичайно, в якостi початкових центрiв використовуються першi k результатiв вибiрки з заданої множини образiв. КРОК 2. На k-му кроцi iтерацiї задана множина образiв розподiляється по k кластерах за таким правилом : XєSj(k), якщо ||X-Zj(k)||<=||X-Zj(k)||, для всiх i=1,2,...,k, i(j, де Sj(k) - множина образiв, якi входять в кластер з центром Zj(k). У випадку рiвностi рiшення приймаються довiльним чином. КРОК 3. На основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, виходячи з умови, що сума квадратiв вiдстаней мiж усiма образами, що належать множині Sj(k), i новiм центром кластера повинна бути мiнiмальною. Iншими словами, новi центри кластерiв Zj(k+1) вибираються таким чином, щоб мiнiмiзувати показник якостi Jj=(||X-Zj(k+1)||^2, j=1,2,...,k. XєSj(k) Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k). Вiдповiдно, новi центри кластерiв визначаються як: Zj(k+1)=(1/Nj)(X, j=1,2,...,k, XЄSj(k), де Nj- число вибiркових образiв, що входять в множину типу Sj(k). Очевидно, що назва алгоритму "К внутрiшнiх групових" визначається способом, прийнятим для послiдовної корекцiї призначення центрiв кластерiв. КРОК 4. Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Iнакше, крок 2. Якiсть залежить: вiд кiлькостi вибираємих центрiв кластерiв; вiд вибору початкових центрiв кластерiв; вiд послiдовностi проглядання образiв; вiд геометричної особливостi даних. Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерiв. Текст програми: #include<conio.h> #include<stdio.h> #include<graphics.h> #include<stdlib.h> #include<math.h> #define k 5 #define N 18 int A[k][N]; typedef struct point {float x,y;}; typedef struct minimal {float m; int i;}; void graphic(int *x,int *y,point *Z,int *K); main() {point Z[k],Z1[k]; int X[N]={0,3,2,3,4,3,8,8,20,20,19,22,21,11,12,12,11,11}; int Y[N]={1,1,2,2,2,3,6,7,7,8,10,9,9,10,10,11,11,12}; float D; minimal min; int i,j,K[k],l,o=1,jj=0; float sumx,sumy; clrscr(); for(i=0;i<k;i++) { Z[i].x=X[i+2]; Z[i].y=Y[i+2]; } start: for(i=0;i<k;i++) K[i]=0; for(i=0;i<N;i++) { min.m=sqrt(pow(Z[0].x-X[i],2)+pow(Z[0].y-Y[i],2)); min.i=0; for(j=0;j<k;j++) {D=sqrt(pow(Z[j].x-X[i],2)+pow(Z[j].y-Y[i],2)); if(D<min.m) {min.m=D;min.i=j;} } A[min.i][K[min.i]]=i;K[min.i]++;} for(i=0;i<k;i++) { sumx=0;sumy=0; for(j=0;j<K[i];j++) { sumx=sumx+X[A[i][j]]; sumy=sumy+Y[A[i][j]]; } Z1[i].x=sumx/K[i]; Z1[i].y=sumy/K[i]; } for(i=0;i<k;i++) if((Z[i].x!=Z1[i].x)||(Z[i].y!=Z1[i].y)) goto bad; goto stop; bad: for(i=0;i<k;i++) { Z[i].x=Z1[i].x; Z[i].y=Z1[i].y; } goto start; stop: textcolor(2); cprintf("VUVID TOCHOK:"); for(i=0;i<N;i++) printf("\nX%d(%d,%d);",i+1,X[i],Y[i]); printf("\n"); cprintf("VUVID ZENTRIV:"); for(i=0;i<k;i++) printf("\nZ%d=(%4.2f,%4.2f);",i+1,Z[i].x,Z[i].y); printf("\n"); cprintf("VUVID CLASTERIV:"); for(i=0;i<k;i++) {printf("\nA%d={",i+1); for(j=0;j<K[i];j++) printf(" X%d(%d,%d)",A[i][j]+1,X[A[i][j]],Y[A[i][j]]); printf(" }");} getch(); graphic(X,Y,Z,K); return 0;} void graphic(int *x,int *y,point *Z,int *K) {int m,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,m=1;i<k;i++,m++) {d=m+8; setcolor(d); setfillstyle(1,d); for(j=0;j<K[i];j++) {circle(x[A[i][j]]*10+10,(y[A[i][j]]*20-480)*(-1)-20,4); floodfill(x[A[i][j]]*10+10,(y[A[i][j]]*20-480)*(-1)-20,d);}} 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;}

Звіт про виконання лабораторної роботи Інші

horuktaras

17.07.2020 14:44

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись