Інформаційний синтез системи автоматичного розпізнавання бланків документів

1.1 Огляд методів розпізнавання образів

Найбільш ефективними методами виведення нових знань є методи розпізнавання образів на основі навчання (самонавчання) [1, 2, 3].

Виділяють такі способи відображення знань:

1. Інтенсіональне відображення - у вигляді схеми зв'язків між атрибутами (ознаками).

2. Екстенціональне відображення - за допомогою конкретних фактів (об'єкти, приклади).

Інтенсіональне відображення фіксує закономірності і зв'язки, якими пояснюється структура даних. Відповідно до діагностичних задач така фіксація полягає у визначенні операцій над атрибутами (ознаками) об'єктів, що призводять до потрібного діагностичного результату. Інтенсіональне зображення реалізуються за допомогою операцій над значенням атрибутів і не припускають операцій над відповідними інформаційними фактами (об'єктами).

У свою чергу, екстенціональне відображення знань пов'язане з описом і фіксацією конкретних об'єктів з предметної галузі і реалізоване в операціях, елементами котрих являються об'єкти як цілісні системи.

Описані вище два фундаментальні способи зображення знань дозволяють запропонувати таку класифікацію методів розпізнавання образів (табл. 1.1):

Таблиця 1.1 Класифікація методів розпізнавання

Аналіз перспективних напрямів розвитку методів розпізнавання показує, що для успішного досягнення мети дослідження необхідно вирішити (або обійти) такі проблеми:

1) комбінаторного вибуху;

2) досягнення незалежності часу розпізнавання від обсягу навчальної вибірки;

3) корекція зниження розмірності простору ознак без відчутної втрати значимої інформації;

4) досягнення високої валідності результатів аналізу;

1.2 Методи оброблення та розпізнавання рукописних символів

Надійність розпізнавання значною мірою залежить від якості зображення символів, яке визначається формою символів або стилем написання і способом виконання.

Алгоритм двомірного дискретного косинусного перетворення [4, 5, 7] реалізується наступним виразом:

,

де , ;

;

Функція B=dct2(A) повертає результат двомірного дискретного косинусного перетворення для матриці А. Матриця В має той же розмір, що і матриця А, і відображає коефіцієнти дискретного косинусного перетворення.

Функція B=dct2(A,m,n) повертає результат двомірного дискретного косинусного перетворення для матриці А розміром mхn. Якщо розмір матриці А менший, вона доповнюється нульовими елементами до заданого розміру.

Матриця А може включати елементи класу double або любого класу integer. Матриця В має елементі класу double.

1.2.2 Двовимірне зворотнє дискретне косинусне перетворення

Алгоритм зворотного дискретного косинусного перетворення [4, 5, 8] реалізується наступним виразом:

,

де , ,

,

Функція B=idct2(A) повертає результат двомірного зворотного дискретного косинусного перетворення для матриці А. Результат повертає у вигляді матриці В.

Функція B=idct2(A,m,n) повертає результат двомірного зворотного дискретного косинусного перетворення з розміром матриць А і В mхn. Якщо розмір матриці А менший, вона доповнюється нульовими елементами до заданого розміру.

Матриця А може включати елементи класу double або любого класу integer. Матриця В має елементі класу double.

1.2.3 Пряме перетворення Радона

Пряме перетворення Радона [4, 6, 8] використовується для полутонового зображення, представленого матрицею І. У результаті перетворення отримаємо матрицю проекцій R. Дане перетворення зводиться до обчислення проекцій зображення на осі, що задаються кутом відносно горизонталі по часовій стрілці.

Матриця І повинна мати елементи, що відносяться до класу double або любому іншому класу integer. Алгоритм прямого перетворення Радона заключається в обчисленні проекцій зображення відносно конкретних напрямків. Так, проекція функцій двох змінних f(x,y) на вісь задається лінійним інтегралом:

,

де осі та задаються поворотом проти часової стрілки на кут з використанням наступного виразу:

.

Базове полутонове зображення І розглядається як функція двох змінних з початком в координатах в місті центрального піксела зображення в піксельній системі координат.

1.2.4 Зворотнє перетворення Радона

Методи розпізнавання рукописних символів, що розглядатимуться далі, історично являються ранніми. Вони передбачають попередню детальну обробку зображень, що розпізнаються. На основі такої обробки виділяють найбільш характерні особливості зображень для їх класифікації. Потім ці особливості перетворюються в коди, зручні для введення в систему розпізнавання.

Так як опис зображень формується з врахуванням конкретної задачі, системи розпізнавання такого типу є непридатні, коли якісно змінюється множина зображень, які необхідно класифікувати, а також коли класифікація набуває новий зміст. В такого типу системах практично відсутнє навчання, так як всі її параметри відразу жорстко задаються конструктором.

1.2.5 Метод суміщення з еталонами

Метод суміщення з еталонами [9, 10] є одинм з перших найпростіших методів розпізнавання образів. Основна ідея методу полягає в співставленні зображення, що розпізнається, з набором ідеальних еталонів, попередньо сформованих конструктором. Належність зображення до певного образу визначається по мірі його збіжності з еталонами. Системи розпізнавання, побудовані за даним методом, можна класифікувати за способом зберігання еталонних наборів:

1) системи, що використовують фотографічні маски;

2) системи, що використовують електричні моделі еталонів;

В системах розпізнавання з фотомасками застосовують безпосередньо оптичне накладання зображення на еталонну маску. Такі системи використовуються для розпізнавання зорових образів. Зображення, що розпізнається, проектується на еталонні маски, набір котрих включає всю множину образів. Степінь збіжності цього зображення з кожним із еталонів фіксується за допомогою еталонного множника, що розміщується за еталонною маскою, за мінімумом світлового потоку, що пройшов скрізь маску. Якщо еталонні маски представленні негативним зображенням знаків, що розпізнаються, то при повній збіжності знака з еталоном вихідний сигнал фотомножника дорівнює нулю. Вхідне зображення відноситься до того образу, з еталоном котрого виявлена найбільша збіжність.

В системах розпізнавання, що використовують для зберігання еталона його електричну модель, зображення попередньо перетворюється в послідовність дискретних за рівнем і часом електричних сигналів. Кожен сигнал з певною точністю відповідає коефіцієнту відображення однієї клітини рецепторного поля. В даній ситуації накладання зображення на еталон відбувається шляхом сумування сигналів від клітин рецепторного поля на еталонних матрицях опору або феритових сердечників. Значення сумарного сигналу відображає степінь збіжності зображення і еталона.

Область застосування методу обмежена в силу необхідності створення для кожного образу точно відтвореного еталону. При цьому зображення, що розпізнаються, повинні мати строго фіксоване положення відносно еталона. Такі системи не можуть перенавчитися для розпізнавання інших образів. Для цього потрібно формувати нові еталони, які б відповідали тим образам, яуі необхідно розпізнати в нових умовах.

1.2.6 Метод зондів

Серед відомих методів розпізнавання букв і символів метод зондів [9, 10, 11] виділяється своєю простотою. Даний метод базується на аналізі певних ознак, суттєвих для даного зображення, і дає можливість класифікувати рукописні знаки, написані з певними невеликими відмінностями в розмірі і стилі написання.

Система розпізнавання потребує написання знаків, що розпізнаються, спеціальними струмопровідними чорнилами. Листок паперу повинен бути розмічений на клітинки, всередині кожної із яких ставляться дві точки. Знак, що розпізнається, повинен розміщуватися певним чином відносно цих двох точок і не виходити за межі клітинки. На знак накладається спеціально підібрана система електронів-зондів, а по чорнилам пропускається струм. Кожний зонд являється ознакою зображення, що розпізнається. Сигнали від електродів, що торкаються ліній знаку, подаються на дешифратор, котрий в залежності від того, які електроди перетнулися, видає код, відповідний певному знаку розпізнавання.

На рецепторному полі знаходяться декілька доріжок-зондів, які можна розглядати як групи або ланцюги одиничних фоторецепторів. Зонди можна розглядати в якості координат простору ознак. У цьому випадку кожне зображення може бути представлене у вигляді вектора , складові котрого приймають значення 0 або 1. Для того, щоб система розпізнавання могла безпомилково класифікувати зображення, необхідно підібрати відповідну систему зондів. При виборі зондів необхідно врахувати можливі зсуви зображення по рецепторному полю, а також їх невелику деформацію. Вплив викривлень, які не перевищують певного значення, може бути відображено в записах кодів зондів.

При побудові системи зондів необхідно врахувати два основні факти: ліміт допустимих перетворень зображень і належність в зображеннях частин, що включають найбільшу для розпізнавання інформацію. Враховуючи ці фактори, потрібно вибирати зонди так, щоб, по-перше, при будь-яких допустимих перетвореннях зображення даного образу система зондів видавала одну і ту саму реакцію, по-друге, при представлені зображень різних образів реакція системи зондів в значній мірі змінювались.

1.2.7 Метод маркування зображень

Метод маркування зображень [9, 11, 12] полягає в тому, що зображенню штучно надаються ознаки, що визначають його в процесі розпізнавання. В натуральних зображеннях дуже важко автоматично виділити ознаки для якісного розпізнавання любого зображення. Разом з тим присутня можливість промаркувати кожне із зображень, що розпізнається.

Припустимо, що при друкуванні цифр біля кожної з них буде надрукована група точок з різним для кожної точки інтервалом. Тоді система розпізнавання може аналізувати не самі зображення, а супроводжуючі їх групи точок. Поява кожної точки фіксується, наприклад, одиничним фоторецептором, а вся група перетворюється в послідовність імпульсів. Цю послідовність подають на дешифратор, котрій видає сигнал, що характеризує дану цифру. На формування сигналу не впливають ні якість надрукованої літери, ні зміна її положення в рядку, ні зміна стилю написання. Задача розпізнавання зображень зводиться до задачі розпізнавання кодів, подібних азбуці Морзе.

Основний недолік методу заключається в тому, що кожне зображення, яке необхідно розпізнати, повинно до представлення системі пройти спеціальну обробку в маркувальному приладі. Тому даний метод не знайшов широкого застосування на практиці.

1.2.8 Квазітопологічний метод розпізнавання

Основна складність розпізнавання полягає в тому, що один і той же образ може бути представлений зображеннями, що суттєво відрізняються між собою. Наприклад, для одного і того ж алфавіту існує велика кількість написання одних і тих же знаків. Не дивлячись на це, система розпізнавання повинна завжди ототожнювати всі написання однієї літери в один образ. Для цього необхідно скласти таке описання зображення, яке було б інваріантним до вказаних змін.

Для аналізу зображень можна використати математичний апарат топології. Так як проекційні перетворення, що розглядаються в топології, дуже широкі, то використовується лише одна математична категорія - графи. Граф - це множина, що складається з підмножини елементів, що називаються ребрами, і підмножини елементів, що називаються вершинами. Кожному кінцю ребра відповідає одна вершина, а кожному ребру відповідає дві вершини. Якщо є можливим взаємно неперервне і взаємно однозначне відображення графа на граф , то таке відображення називається гомеоморфним.

Такі зображення, як літери латинського алфавіту, можна розглядати як плоскі графи, а різні написання однієї і тієї ж літери - як гомеоморфні перетворення деякого ідеального знаку.

Гомеоморфність двох графів встановлюється за допомогою топологічних інваріантів, тобто ознак, які не змінюються при гомеоморфних перетвореннях. Простіше всього користуватися інваріантами, котрі можуть бути виражені за допомогою чисел. Для цього необхідно встановити правило, за яким кожному графу ставиться у відповідність деяке число, що залишається незмінним при гомеоморфних перетвореннях. Частіше всього в якості топологічного інваріанту використовують індекс вершини, котрий визначається як кількість ребер, що входять у вершину. Індекс вершин встановлюється при послідовному обході графа за певним правилом. Це правило може бути сформоване так: обхід відбувається по ребрам, при чому напрям обходу змінюється на протилежний у випадку попадання на вершину з індексом 1; у випадку, якщо індекс вершини більше 2, далі рух з цієї вершини необхідно продовжувати по першому ребру, розміщеного за годинниковою стрілкою відносно ребра, по якому рухома точка потрапила в цю вершину. Таке правило дозволяє проводити послідовний обхід любого графа по зовнішнім ребрам при умові, що обхід почався з випадкової точки будь-якого зовнішнього ребра.

Метод квазітопологічного розпізнавання [9, 13] може бути реалізований за допомогою слідкуючої розгортки, коли обхід відбувається по зовнішньому контуру зображення. До слідкуючої розгортки повинен бути добавлений пристрій, який визначає індекси вершин в місцях згину зовнішнього контуру. Далі схема логіки повинна проводити декодування отриманих кодових комбінацій. Крім цього, повинен бути присутній або пристрій для фіксації початку обходу, або пристрій, який би забезпечував декодування кодових комбінацій в циклічних перестановках.

Таким чином квазітопологічний метод можна успішно застосовувати для побудови читаючих автоматів. Але використання цього методу не може принципово забезпечити повного розподілу літер алфавіту, так як деякі зображення літер є гомеоморфними одному і тому ж еталонному графу. Це стосується літер П, С, Г. Вони є гомеоморфними відрізку прямої. Крім того, метод не може забезпечити якісного розпізнавання при наявності нечіткого зображення літери, що розпізнається, та потребує багато часу.

1.3 Постановка задачі та формування завдань дослідження

Виходячи з аналізу методів розпізнавання образів (табл. 1.1), та перспектив розвитку методів розпізнавання [14, 17], в даній роботі запропоновано розробляти систему розпізнавання рукописних символів у рамках інформаційно екстремальної інтелектуальної технології (ІЕІТ), що ґрунтується на максимізації інформаційної спроможності системи, шляхом оптимізації її параметрів функціонування за умов апріорної невизначеності інформаційних і ресурсних обмежень. В рамках ІЕІТ, завдяки самонавчанню системи та шляхом оптимізації просторово-часових параметрів функціонування системи розпізнавання, можна побудувати безпомилкові вирішальні правила.

Розглянемо постановку задачі загального синтезу систами розпізнавання. Нехай ефективність навчання розпізнаванню реалізацій класу , характеризується значенням критерію функціональної ефективності. Відома навчальна матриця де кількість ознак розпізнавання і випробувань відповідно. Рядок матриці утворює -ту реалізацію образу, а стовпець навчальну вибірку з генеральної сукупності значень -ї ознаки розпізнавання. Треба для структурованого вектора параметрів функціонування системи розпізнавання , які будемо називати параметрами навчання і для яких відомі обмеження , шляхом організації послідовних ітераційних процедур знайти екстремальні значення координат вектора , що забезпечують максимум КФЕ навчання системи розпізнавання:

,

де область допустимих значень параметрів навчання.

Треба на етапі екзамену визначити з наближеною до асимптотичної повної достовірності належність зображення, що розпізнається до одного з класів розпізнавання із сформованого на етапі навчання алфавіту класів .

Об'єктом дослідження є слабо формалізований процес розпізнавання зображень.

Предметом дослідження є метод розпізнавання зображень у рамках МФСВ.

Метою роботи є підвищення достовірності та оперативності розпізнавання рукописних символів у рамках ІЕІТ.

Для досягнення поставленої мети необхідно вирішити такі завдання:

- розробити базовий алгоритм навчання та екзамену за ІЕІТ;

- сформувати навчальну матрицю для зображень в декартових і полярних координатах;

- розробити та програмно реалізувати алгоритм навчання системи розпізнавання рукописних символів за ІЕІТ з оптимізацією контрольних допусків на ознаки розпізнавання;

- програмно реалізувати алгоритм екзамену та оцінити достовірність результатів;

2 ОПИС МЕТОДУ РОЗПІЗНАВАННЯ РУКОПИСНИХ СИМВОЛІВ

2.1 Основні ідеї інформаційно-екстремального методу розпізнавання рукописних символів

Базовим методом ІЕІТ є метод функціонально-статистичних випробувань (МФСВ) [18, 19, 20] - непараметричний інформаційно-екстремальний метод аналізу та синтезу здатної навчатися системи керування, який ґрунтується на прямій оцінці інформаційної здатності системи за умов нечіткої компактності реалізацій образу, та обмеження навчальної вибірки, яка є прийнятною для задач контролю і керування. Метод призначено для розв'язання практичних задач контролю та управління слабо формалізованими системами і процесами шляхом автоматичної класифікації їх функціональних станів за умови невизначеності.

МФСВ окрім системних та специфічних принципів ґрунтується також на 2-х дистанційних принципах:

- максимально-дистанційному, який вимагає максимальної міжцентрової відстані між класами;

- мінімально-дистанційному, вимагає мінімальної середньої відстані реалізацій від центру свого класу:

Класом розпізнавання (образом) називається відбиття властивостей m-го функціонального стану системи розпізнавання і відношень між елементами системи. Клас розпізнавання топологічна категорія, яка задається в просторі ознак розпізнавання областю _Б.

Детерміновано-статистичний підхід [21, 22] до моделювання систем вимагає завдання систем нормованих (експлуатаційних) і контрольних допусків на ОР. Нехай базовий клас, який характеризує максимальну функціональну ефективність, тобто є найбільш бажаним для розробника інформаційного забезпечення системи. Нормованим називається поле допусків , в якому значення і-ї ОР знаходиться з імовірністю або , за умови, що функціональний стан відноситься до класу . Контрольним називається поле допусків , в якому значення і-ї ОР знаходиться з імовірністю за умови, що функціональний стан відноситься до класу .

В ІЕІТ система контрольних допусків вводиться з метою рандомізації процесу прийняття рішень, оскільки для повного дослідження об'єкту контролю та управління необхідно використовувати як детерміновані, так і статистичні характеристики. Зрозуміло, що і базова (відносно класу) СКД є сталою для всієї абетки класів розпізнавання.

Реалізацією образу називається випадковий структурований бінарний вектор , де і-та координата вектора, яка приймає одиничне значення, якщо значення і-ї ОР знаходиться в полі допусків , і нульове значення, якщо не знаходиться; мінімальна кількість випробувань, яка забезпечує репрезентативність реалізацій образу.

При обґрунтуванні гіпотези компактності (чіткої, або нечіткої) реалізацій образу за геометричний центр класу приймається вершина бінарного еталонного вектору х_m.

Еталонний вектор x_m це математичне сподівання реалізацій класу .

Він подається у вигляді детермінованого структурованого бінарного вектора , де х_m,і і-та координата вектора, яка приймає одиничне значення, якщо значення і-ї ОР знаходиться в нормованому полі допусків, і нульове значення, якщо не знаходиться.

Основною задачею етапу навчання за МФСВ є розбиття простору ознак розпызнавання за поданою навчальною матрицею на області класів розпізнавання деяким оптимальним в інформаційному сенсі способом, який забезпечує на етапі екзамену прийняття рішень з достовірністю, наближеною до максимальної асимптотичної достовірності.

Параметром функціонування називається характеристика інформаційного забезпечення, яка прямо або непрямо впливає на функціональну ефективність системи. Такими параметрами можуть бути параметри навчання, перетворення образу, впливу середовища та інші, які безпосередньо впливають на асимптотичну достовірність.

Як критерій оптимізації процесу навчання системи прийняттю рішень в рамках МФСВ застосовується статистичний інформаційний КФЕ, який є природною мірою різноманітності (або схожості) класів розпізнавання і одночасно функціоналом асимптотичних точнісних характеристик СР. При цьому важливо, щоб параметри навчання були оптимальними в інформаційному розумінні, тобто забезпечували максимальну функціональну ефективність СР, яка визначається достовірністю прийняття рішень на екзамені.

Достовірність класифікатора залежить від геометричних параметрів роздільних гіперповерхонь класів розпізнавання.

У загальному випадку, коли класи розпізнавання перетинаються, розглянемо відносний коефіцієнт нечіткої компактності реалізації образу для класу

(2.1.1)

Процес навчання полягає в мінімізації цього виразу.

В МФСВ, який ґрунтується на допущенні гіпотези компактності (чіткої або нечіткої) реалізацій образу, як наближення точної роздільної гіперповерхні для класу розглядається гіперсфера, центром якої є еталонний вектор , а радіусом кодова відстань, яка у просторі Хеммінга визначається як

(2.1.2)

де і-та координата вектора i-тa координата деякого вектора m, вершина якого знаходиться на роздільні гіперповерхні класу ; операція складання за модулем два.

Оптимальною кодовою відстанню (радіусом) між вектором і контейнером називається екстремальне значення , яке визначає максимум інформаційного КФЕ , де {d} - послідовність збільшень радіуса контейнера .

Побудова оптимальної в інформаційному сенсі РГП у вигляді гіперсфери за МФСВ зводиться до оптимізації радіуса роздільної гіперсфери dm, яка відбувається за ітераційним алгоритмом

(2.1.3)

де k змінна числа збільшень радіуса РГП; h крок збільшення.

Процедура закінчується при знаходженні екстремального значення критерію , де множина радіусів концентрованих гіперсфер, центр яких визначається вершиною еталонного вектора еталонний вектор найближчого (до ) класу .

2.2 Математична модель системи розпізнавання рукописних символів

Категоріальну модель процесу навчання системи розпізнавання символів [19] при нечіткому розбитті за МФСВ подамо у вигляді діаграми відображень множин:

(2.2.1)

де

- множина сигналів на вході СР

- множина моментів зчитування інформації з рецепторів;

- множина можливих станів СР;

- простір ОР;

- множина сигналів після первинної обробки інформації;

- покриття, що визначає абетку класів розпізнавання;

- - нечітке розбиття;

- множина гіпотез;

- множина точнісних характеристик;

- множина значень КФЕ;

За діаграмою (2.2.1) оператори контуру

реалізують базовий алгоритм начання, який безпосередньо визначає екстремальні значення геометричних параметрів контейнерів шляхом пошуку максимуму критерію .

Оператор регламентує процес навчання і дозволяє оптимізувати параметри плану навчання.

Діаграма відображень множин на екзамені має такі відмінності від діаграм оптимізаційного навчання за МФСВ:

· зворотний зв'язок у діаграмі не містить контурів оптимізації параметрів функціонування СР, а призначенням оператора U_Е є регламентація екзамену;

· замість оператора вводиться оператор Р відображення вибіркової множини X , що розпізнається, на побудоване на етапі навчання розбиття ;

· комутативне кільце утворюється між розбиттям , множиною гіпотез I^|M+1| і покриттям ;

· оператор класифікації утворює композицію двох операторів: ₁:F, де F - множина функцій належності, і оператор дефазіфікації ₂ : FI^|M+1|, який вибирає гіпотезу за максимальним значенням функції належності.

З урахуванням наведених відмінностей діаграма відображень множин на екзамені набуває вигляду

(2.2.2)

У діаграмі (2.2.2) оператор Ф₁ відображає універсум випробувань на вибіркову множину Х, яка утворює екзаменаційну матрицю , аналогічну за структурою, процедурою та параметрами формування навчальній матриці.

2.3 Критерій оптимізації параметрів функціонування системи розпізнавання

Як критерій оптимізації параметрів навчання системи розпізнавання може розглядатися будь-яка статистична інформаційна міра, яка є функціоналом від точнісних характеристик. Так, широкого використання в алгоритмах навчання за МФСВ набула модифікація інформаційної міри Кульбака [19], в якій розглядається відношення правдоподібності у вигляді логарифмічного відношення повної ймовірності правильного прийняття рішень до повної ймовірності помилкового прийняття рішень :

де безумовні ймовірності появи реалізацій класів і відповідно, а умовні ймовірності точнісні характеристики: перша достовірність , помилка першого роду помилка другого роду і друга достовірність Для рівноймовірних гіпотез, що характеризує найбільш важкий у статистичному розумінні випадок прийняття рішень, міру Кульбака подамо у вигляді

(2.3.1)

Отже, критерій (2.3.1) є нелінійним функціоналом від точнісних характеристик процесу навчання. Крім того він є неоднозначним, що потребує знання робочої області його визначення. Оскільки навчальна вибірка є обмеженою за обсягом, то замість, наприклад, помилок першого та другого роду розглянемо їх оцінки: де кількість реалізацій класу , які не належать контейнеру ; кількість реалізацій класу , які належать контейнеру . Після підстановки цих оцінок у (2.3.1) отримаємо робочу формулу КФЕ за Кульбаком:

(2.3.2)

де - кількість реалізацій класу , які не знаходяться в k-му контейнері цього класу; кількість “чужих” реалізацій, які знаходяться в k-му контейнері. У виразі (2.3.2) любе мале позитивне число, яке дозволяє уникнути появи нуля в знаменнику дробу. На практиці доцільно брати рівним кількості знаків у мантисі значення критерію. Нормований критерій Кульбака можна подати у вигляді де - максимальне значення критерію при і

2.4 Базовий алгоритм навчання

Вхідною інформацією для навчання за базовим алгоритмом є дійсний, в загальному випадку, масив реалізацій образу ; система полів контрольних допусків і рівні селекції , які за умовчанням дорівнюють 0,5 для всіх класів розпізнавання.

Розглянемо етапи реалізації алгоритму:

1.Формування бінарної навчальної матриці , елементи якої дорівнюють

(2.4.1)

2.Формування масиву еталонних двійкових векторів , елементи якого визначаються за правилом:

(2.4.2)

де рівень селекції координат вектору .

3. Розбиття множини еталонних векторів на пари найближчих сусідів: =<x_m , x_l >, де x_l еталонний вектор сусіднього класу , за таким алгоритмом:

а) структурується множина еталонних векторів, починаючи з вектора x₁ базового класу , який характеризує найбільшу функціональну ефективність системи розпізнавання;

б) будується матриця кодових відстаней між еталонними векторами розмірності M M;

в) для кожної строки матриці кодових відстаней знаходиться мінімальний елемент, який належить стовпчику вектора найближчого до вектора, що визначає строку. При наявності декількох однакових мінімальних елементів вибирається з них будь-який, оскільки вони є рівноправними;

г) формується структурована множина елементів попарного розбиття , яка задає план навчання.

4. Оптимізація кодової відстані dm відбувається за рекурентною процедурою. При цьому приймається .

5.Процедура закінчується при знаходженні максимуму КФЕ в робочій області його визначення: де множина радіусів концентрованих гіперсфер, центр яких визначається вершиною .

Таким чином, базовий алгоритм навчання :

(2.4.3)

На рис.2.4.1 наведено структурну схему базового алгоритму навчання. Тут показано такі вхідні дані: {Y[J,I,K]} масив навчальних вибірок, J=1..NM змінна кількості випробувань, де NM мінімальний обсяг репрезентативної навчальної вибірки, I=1..N змінна кількості ознак розпізнавання, K=1..M змінна кількості класів розпізнавання; {NDK[I]}, {VDK[I]} масиви нижніх і верхніх контрольних допусків на ознаки відповідно. Результатом реалізації алгоритму є: {DOPT[K]} цілий масив оптимальних значень радіусів контейнерів класів розпізнавання у кодовій відстані Хеммінга; {EV[K]} масив еталонних двійкових векторів класів розпізнавання; {EM[K]} дійсний масив максимальних значень інформаційного КФЕ процесу навчання; {D1[K]}, {A[K]}, {B[K]}, {D2[K]} дійсні масиви оцінок екстремальних значень точнісних характеристик процесу навчання для відповідних класів розпізнавання: перша вірогідність, помилки першого та другого роду і друга вірогідність відповідно.

Змінна D є робочою змінною кроків навчання, на яких послідовно збільшується значення радіуса контейнера. У структурній схемі алгоритму (рис. 2.4.1) блок 3 формує масив навчальних двійкових вибірок {X[J,I,K]} шляхом порівняння значень елементів масиву {Y[J,I,K]} з відповідними контрольними допусками за правилом (1) і формує масив еталонних двійкових векторів {EV[K]} шляхом статистичного усереднення стовпців масиву {X[J,I,K]} за правилом (2) при відповідному рівні селекції, який за умовчанням дорівнює . Блок 4 здійснює розбиття множини еталонних векторів на пари “найближчих сусідів”. Блок 11 обчислює на кожному кроці навчання значен

Рисунок 2.4.1 Структурна схема базового алгоритму навчання

ня інформаційного КФЕ і оцінки точнісних характеристик процесу навчання. При невиконанні умови блоку порівняння 12 блок 13 оцінює належність поточного значення критерію робочій області визначення його функції і при позитивному рішенні блоку 13 це значення запам'ятовується блоком 14. При негативному рішенні блока порівняння 15, в якому величина дорівнює кодовій відстані між парою сусідніх еталонних векторів, блок 16 здійснює у робочій області пошук глобального максимуму КФЕ - EM[K] і визначає для нього екстремальне значення радіуса гіперсфери - DOPT[K]. Аналогічно будуються оптимальні контейнери для інших класів. Якщо параметри навчання {DOPT[K]} і {EV[K]} є вхідними даними для екзамену, то значення КФЕ та екстремальних оцінок точнісних характеристик використовуються для аналізу ефективності процесу навчання. Таким чином, основною процедурою базового алгоритму навчання за МФСВ є обчислення на кожному кроці навчання статистичного інформаційного КФЕ і організація пошуку його глобального максимуму в робочій області визначення функції критерію.

2.5 Алгоритм екзамену

Алгоритми екзамену за МФСВ можуть мати різну структуру залежно від розподілу реалізацій образу, що розпізнаються. Обов'язковою умовою їх реалізації є забезпечення однакових структурованості і параметрів формування як для навчальної, так і для екзаменаційної матриць.

Для нечіткого розбиття алгоритм екзамену за МФСВ ґрунтується на аналізі значень функції належності, яка має вигляд (2.5.1) і обчислюється для кожної реалізації, що розпізнається. Розглянемо кроки реалізації алгоритму екзамену при нечіткому розбитті:

1. Формування лічильника класів розпізнавання.

2. Формування лічильника числа реалізацій, що розпізнаються: .

3. Обчислення кодової відстані .

4. Обчислення функції належності за виразом:

(2.5.1)

5. Порівняння: якщо j n , то виконується крок 2, інакще - крок 6.

6. Порівняння: якщо m M, то виконується крок 1, інакще - крок 7.

7. Визначення класу , до якого належить екзаменаційна реалізація, наприклад, за умови , де усереднене значення функцій належності для реалізацій класу , або видача повідомлення: «Клас не визначено», якщо . Тут с порогове значення.

3 ІНФОРМАЦІЙНЕ ТА ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ СИСТЕМИ РОЗПІЗНАВАННЯ РУКОПИСНИХ СИМВОЛІВ