МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
“Прийняття рішень в задачах розпізнавання образів” Звіт до лабораторної роботи №4 з курсу “Математичні методи дослідження операцій” Розпізнавання образів є однією з найфундаментальніших проблем теорії інтелектуальних систем. З іншого боку, задача розпізнавання образів має величезне практичне значення. Замість терміну "розпізнавання" часто використовується інший термін — "класифікація". Ці два терміни у багатьох випадках розглядаються як синоніми, але не є повністю взаємозамінюваними. Кожний з цих термінів має свої сфери застосування, і інтерпретація обох термінів часто залежить від специфіки конкретної задачі. Типові постановки задач класифікації Задача ідентифікації, яка полягає у тому, щоб вирізнити певний конкретний об'єкт серед йому подібних (наприклад, впізнати серед інших людей свою дружину). Віднесення об'єкта до того чи іншого класу. Це може бути, наприклад, задача розпізнавання літер або прийняття рішення про наявність дефекту у деякій технічній деталі. Віднесення об'єкта до певного класу відображає найтиповішу проблему класифікації, і, коли говорять про розпізнавання образів, найчастіше мають на увазі саме цю проблему. Саме вона розглядається тут у першу чергу. Кластерний аналіз, який полягає в розділенні заданого набору об'єктів на класи — групи об'єктів, схожі між собою за тим чи іншим критерієм. Цю задачу часто називають класифікацією без учителя, оскільки, на відміну від задачі 2, класи апріорно не задані. Проблеми розпізнавання легко вирішуються людьми, причому робиться це, як правило, підсвідомо. Спроби ж побудувати штучні системи розпізнавання не настільки переконливі. Основна проблема полягає у тому, що часто неможливо адекватно визначити ознаки, на основі яких слід здійснювати розпізнавання. Для задач, для яких такі ознаки вдається виділити, штучні системи розпізнавання набули значного поширення і широко використовуються. Приклади задач розпізнавання образів Розпізнавання літер. Розпізнавання штрих-кодів. Розпізнавання автомобільних номерів. Розпізнавання осіб. Розпізнавання мови. Розпізнавання зображень. Розпізнавання локальних ділянок земної кори, у яких знаходяться родовища корисних копалин. 15 Варіант А1 А2 А3 А4 А5 А6 А7 А8 А9 А10 М1 М2  B H U K P ≠ Г 3 5 8 1 3   Ознаки: S1 – кількість замальованих квадратів у 2 стовпцю. S2 – кількість замальованих квадратів у 4 рядку. S3 – чи є замальований квадрат у 1 рядку. (1 – є, 0 – нема). S4 – кількість замальованих квадратів у центральному квадраті 3х3. S5 – кількість замальованих квадратів у лівому верхньому квадраті 3х3. S6 – кількість замальованих квадратів у квадраті 11х11. Код програми #include<iostream> #include<conio.h> #include<cmath> using namespace std; short X[16][11][11]; short Y[16][11][11]; double Q[16] = {-1}; double koef[6] = {0.25,0.25,0.1,0.2,0.2}; struct DIF{ int mat[7][16]; }ForX[16]; int oznaka1(int ind, char c); int oznaka2(int ind, char c); int oznaka3(int ind, char c); int oznaka4(int ind, char c); int oznaka5(int ind, char c); int oznaka6(int ind, char c); void firstTable(); void secondTable(); void calculateDif(); void dominated(int i,int i1, int i2); main() { for(int t = 0;t<16;t++) for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) X[t][i][j]=0; for(int t = 0;t<16;t++) for(int j = 0;j<16;j++) ForX[t].mat[6][j]=1; //X1 for(int i = 1;i<10;i++) X[0][10][i]=1; for(int i = 1;i<7;i++) X[0][0][i]=X[0][8][i]=1; for(int i = 1;i<8;i++) X[0][i][3]=1; X[0][4][4]=X[0][4][5]=X[0][4][6]=X[0][3][7]=X[0][1][7]=1; X[0][2][8]=X[0][5][7]=X[0][5][8]=X[0][6][8]=X[0][7][8]=X[0][8][7]=1; //Y1 for(int i = 1;i<10;i++) Y[0][10][i]=1; for(int i = 1;i<7;i++) Y[0][0][i]=Y[0][8][i]=1; for(int i = 1;i<8;i++) Y[0][i][3]=1; Y[0][4][4]=Y[0][4][5]=Y[0][4][6]=Y[0][3][7]=Y[0][1][7]=Y[0][7][2]=1; Y[0][2][8]=Y[0][5][7]=Y[0][5][8]=Y[0][6][8]=Y[0][7][8]=Y[0][8][7]=Y[0][4][7]=1; //X2 for(int i = 1;i<10;i++) X[1][10][i]=1; for(int i = 0;i<8;i++) X[1][i][3]=X[1][i][8]=1; for(int i = 0;i<7;i++) X[1][i][2]=1; X[1][0][1]=X[1][0][4]=X[1][0][7]=X[1][0][9]=1; for(int i = 4;i<8;i++) X[1][8][i]=1; //Y2 for(int i = 1;i<10;i++) Y[1][10][i]=1; for(int i = 0;i<8;i++) Y[1][i][3]=Y[1][i][8]=1; for(int i = 0;i<7;i++) Y[1][i][2]=1; Y[1][0][0]=Y[1][0][1]=Y[1][0][4]=Y[1][0][7]=Y[1][0][9]=Y[1][0][10]=Y[1][7][4]=Y[1][7][7]=1; for(int i = 4;i<8;i++) Y[1][8][i]=1; //X3 for(int i = 1;i<10;i++) X[2][10][i]=1; for(int i = 2;i<9;i++) X[2][0][i]=1; for(int i = 1;i<9;i++) X[2][i][3]=X[2][i][4]=1; X[2][8][2]=X[2][8][5]=X[2][1][8]=1; //Y3 for(int i = 1;i<10;i++) Y[2][10][i]=1; for(int i = 2;i<9;i++) Y[2][0][i]=1; for(int i = 1;i<9;i++) Y[2][i][3]=Y[2][i][4]=1; Y[2][8][1]=Y[2][8][2]=Y[2][8][5]=Y[2][8][6]=Y[2][1][8]=1; //X4 for(int i = 2;i<9;i++) X[3][10][i]=1; X[3][0][5]=X[3][0][6]=X[3][0][7]=X[3][1][4]=X[3][2][3]=1; X[3][3][3]=X[3][3][4]=X[3][3][5]=X[3][4][6]=X[3][5][7]=1; X[3][6][7]=X[3][7][6]=X[3][8][5]=X[3][8][4]=X[3][8][3]=1; //Y4 for(int i = 2;i<9;i++) Y[3][10][i]=1; Y[3][0][5]=Y[3][0][6]=Y[3][0][7]=Y[3][1][4]=Y[3][2][3]=1; Y[3][3][3]=Y[3][3][4]=Y[3][3][5]=Y[3][4][6]=Y[3][5][7]=1; Y[3][6][7]=Y[3][7][6]=Y[3][8][5]=Y[3][8][4]=Y[3][8][3]=1; Y[3][0][4]=Y[3][0][8]=Y[3][1][8]=Y[3][7][3]=Y[3][4][5]=1; //X5 for(int i = 1;i<5;i++) X[4][i][3]=X[4][i][8]=1; for(int i = 6;i<10;i++) X[4][i][2]=X[4][i][7]=1; for(int i = 3;i<8;i++) X[4][5][i]=1; X[4][1][2]=X[4][1][4]=X[4][1][5]=X[4][1][7]=X[4][1][9]=X[4][1][10]=1; X[4][2][4]=X[4][2][9]=X[4][8][1]=X[4][8][6]=1; X[4][9][0]=X[4][9][1]=X[4][9][3]=X[4][9][5]=X[4][9][6]=X[4][9][8]=1; //Y5 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[4][i][j]=X[4][i][j]; Y[4][1][1]=Y[4][9][9]=1; //X6 X[5][1][3]=X[5][1][4]=X[5][1][5]=X[5][1][8]=X[5][1][9]=X[5][1][10]=1; X[5][2][4]=X[5][2][8]=X[5][3][4]=X[5][3][6]=X[5][3][7]=1; X[5][4][3]=X[5][4][4]=X[5][4][5]=X[5][5][3]=X[5][5][4]=X[5][5][5]=1; X[5][6][3]=X[5][6][5]=X[5][6][6]=X[5][7][2]=X[5][7][6]=1; X[5][8][2]=X[5][8][6]=X[5][8][7]=X[5][9][1]=X[5][9][2]=X[5][9][3]=1; X[5][9][6]=X[5][9][7]=X[5][9][8]=1; //Y6 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[5][i][j]=X[5][i][j]; Y[5][1][2]=Y[5][1][7]=Y[5][9][0]=Y[5][9][9]=1; //X7 for(int i = 2;i<9;i++) X[6][4][i]=X[6][7][i]=1; X[6][1][7]=X[6][2][6]=X[6][3][6]=X[6][5][5]=X[6][6][5]=1; X[6][8][4]=X[6][9][3]=X[6][10][3]=1; //Y7 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[6][i][j]=X[6][i][j]; Y[6][4][0]=Y[6][4][1]=Y[6][4][9]=Y[6][4][10]=1; Y[6][7][0]=Y[6][7][1]=Y[6][7][9]=Y[6][7][10]=1; //X8 for(int i = 4;i<11;i++) X[7][2][i]=1; X[7][3][5]=X[7][3][10]=X[7][4][5]=1; X[7][5][4]=X[7][6][4]=X[7][7][4]=X[7][7][3]=X[7][8][3]=X[7][9][3]=1; X[7][10][2]=X[7][10][3]=X[7][10][4]=1; //Y8 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[7][i][j]=X[7][i][j]; Y[7][2][2]=Y[7][2][3]=Y[7][10][1]=Y[7][10][5]=1; //X9 for(int i = 0;i<11;i++) if(i!=5) X[8][1][i]=X[8][9][i]=1; for(int i = 2;i<9;i++) X[8][i][2]=X[8][i][3]=X[8][i][7]=X[8][i][8]=1; X[8][5][4]=X[8][5][5]=X[8][5][6]=1; //Y9 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[8][i][j]=X[8][i][j]; Y[8][2][1]=Y[8][2][9]=Y[8][8][1]=Y[8][8][9]=1; //X10 for(int i = 2;i<7;i++) X[9][2][i]=X[9][10][i]=1; for(int i = 3;i<10;i++) X[9][i][3]=X[9][i][4]=1; X[9][2][7]=X[9][3][7]=X[9][3][8]=X[9][3][9]=X[9][4][8]=X[9][4][9]=1; X[9][5][7]=X[9][5][8]=X[9][5][9]=X[9][6][5]=X[9][6][6]=X[9][6][7]=1; //Y10 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[9][i][j]=X[9][i][j]; Y[9][2][1]=Y[9][2][8]=Y[9][7][5]=Y[9][10][1]=Y[9][10][7]=1; //X11 for(int i = 1;i<9;i++) X[10][3][i]=X[10][6][i]=1; X[10][0][7]=X[10][1][6]=X[10][2][6]=X[10][4][5]=X[10][5][4]=1; X[10][7][4]=X[10][8][3]=X[10][9][3]=1; //Y11 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[10][i][j]=X[10][i][j]; Y[10][3][0]=Y[10][3][9]=Y[10][3][10]=Y[10][2][5]=1; Y[10][6][0]=Y[10][6][9]=Y[10][6][10]=Y[10][7][3]=1; //X12 for(int i = 0;i<10;i++) X[11][i][1]=1; for(int i = 2;i<6;i++) X[11][0][i]=X[11][4][i]=X[11][9][i]=1; X[11][1][6]=X[11][2][7]=X[11][3][6]=X[11][5][6]=X[11][5][7]=1; X[11][6][8]=X[11][7][8]=X[11][8][7]=X[11][9][6]=1; //Y12 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[11][i][j]=X[11][i][j]; Y[11][2][6]=Y[11][4][6]=Y[11][6][7]=Y[11][7][7]=1; //X13 for(int i = 0;i<10;i++) X[12][i][1]=1; for(int i = 5;i>=0;i--) X[12][i][7-i]=X[12][i][8-i]=1; for(int i = 5;i<=9;i++) X[12][i][i-2]=X[12][i][i-1]=1; //Y13 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[12][i][j]=X[12][i][j]; Y[12][0][9]=Y[12][6][2]=Y[12][9][9]=1; //X14 for(int i = 0;i<10;i++) X[13][i][2]=1; for(int i = 3;i<9;i++) X[13][0][i]=1; //Y14 for(int i = 1;i<9;i++) Y[13][0][i]=1; for(int i = 1;i<10;i++) Y[13][i][2]=1; Y[13][1][8]=1; //X15 for(int i = 3;i<8;i++) X[14][0][i]=1; X[14][1][2]=X[14][1][8]=X[14][2][2]=X[14][2][8]=X[14][3][3]=X[14][3][7]=1; for(int i = 4;i<7;i++) X[14][4][i]=X[14][9][i]=1; X[14][5][3]=X[14][5][6]=X[14][5][7]=X[14][6][2]=X[14][6][8]=1; X[14][7][2]=X[14][7][8]=X[14][8][3]=X[14][8][7]=1; //Y15 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[14][i][j]=X[14][i][j]; Y[14][4][3]=Y[14][4][7]=Y[14][5][4]=1; //X16 X[15][1][5]=X[15][1][6]=X[15][2][4]=X[15][2][7]=X[15][3][3]=X[15][3][8]=1; X[15][4][3]=X[15][4][8]=X[15][5][3]=X[15][5][4]=X[15][5][8]=1; for(int i = 4;i<8;i++) X[15][6][i]=1; X[15][7][7]=X[15][8][6]=X[15][9][3]=X[15][9][4]=X[15][9][5]=1; //Y16 for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) Y[15][i][j]=X[15][i][j]; Y[15][1][4]=Y[15][1][7]=Y[15][2][3]=Y[15][2][8]=1; Y[15][6][8]=Y[15][8][3]=1; //--------------------------------------------------------------------------- printf("Tablucja znachen' oznak dlja etalonnuh sumvoliv:\n\n"); firstTable(); printf("\n\nTablucja znachen' oznak dlja dijsnuh sumvoliv:\n\n"); secondTable(); printf("\n\n"); calculateDif(); for(int t = 0;t<16;t++) for(int i = 0;i<16;i++) for(int j = 0;j<16;j++) if(i!=j && ForX[t].mat[6][i]==1 && ForX[t].mat[6][j]==1) dominated(t,i,j); for(int t = 0;t<16;t++) { printf("\n\ndlja X%i\n\n",t+1); for(int i = 0;i<16;i++) Q[i] = -1; for(int i = 0;i<16;i++) if(ForX[t].mat[6][i]==1) { Q[i] = 0; for(int j = 0;j<6;j++) Q[i] += (koef[j]*ForX[t].mat[j][i]); } for(int i = 0;i<6;i++) { for(int j = 0;j<16;j++) printf("%3i ",ForX[t].mat[i][j]); printf("\n"); } for(int i = 0;i<16;i++) if(Q[i]>=0) printf("%.1f ",Q[i]); else printf(" - "); printf("\n"); double min = 100; int minI = -1; for(int i = 0;i<16;i++) if(Q[i]!=-1 && Q[i]<min){ min = Q[i]; minI = i;} printf("%i %i\n",t+1,minI+1); } getch(); return 0; } int oznaka1(int ind, char c) { int k = 0; if(c=='x') for(int i = 0;i<11;i++) if(X[ind][i][2]==1) k++; if(c=='y') for(int i = 0;i<11;i++) if(Y[ind][i][2]==1) k++; return k; } int oznaka2(int ind, char c) { int k = 0; if(c=='x') for(int i = 0;i<11;i++) if(X[ind][4][i]==1) k++; if(c=='y') for(int i = 0;i<11;i++) if(Y[ind][4][i]==1)k++; return k; } int oznaka3(int ind, char c) { if(c=='x') for(int i = 0;i<11;i++) if(X[ind][0][i]==1) return 1; if(c=='y') for(int i = 0;i<11;i++) if(Y[ind][0][i]==1) return 1; return 0; } int oznaka4(int ind, char c) { int k=0; if(c=='x') for(int i = 4;i<=6;i++) for(int j = 4;j<=6;j++) if(X[ind][i][j]==1) k++; if(c=='y') for(int i = 4;i<=6;i++) for(int j = 4;j<=6;j++) if(Y[ind][i][j]==1) k++; return k; } int oznaka5(int ind, char c) { int k=0; if(c=='x') for(int i = 0;i<=2;i++) for(int j = 0;j<=2;j++) if(X[ind][i][j]==1) k++; if(c=='y') for(int i = 0;i<=2;i++) for(int j = 0;j<=2;j++) if(Y[ind][i][j]==1) k++; return k; } int oznaka6(int ind, char c) { int k = 0; if(c=='x') for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) if(X[ind][i][j]==1) k++; if(c=='y') for(int i = 0;i<11;i++) for(int j = 0;j<11;j++) if(Y[ind][i][j]==1) k++; return k; } void firstTable() { printf(" "); for(int i = 0;i<16;i++) printf(" X%i",i+1); printf("\n"); for(int i = 0;i<80;i++) printf("-"); for(int i = 0;i<6;i++) { printf(" S%i |",i+1); for(int j = 0;j<16;j++) { if(j>9) printf(" "); switch(i) { case 0: printf(" %2i",oznaka1(j,'x')); break; case 1: printf(" %2i",oznaka2(j,'x')); break; case 2: printf(" %2i",oznaka3(j,'x')); break; case 3: printf(" %2i",oznaka4(j,'x')); break; case 4: printf(" %2i",oznaka5(j,'x')); break; case 5: printf(" %2i",oznaka6(j,'x')); break; }