1 Розпізнавання образів на основі мереж Байєса Виконавець роботи: студентка групи КА-46м Гуз Наталія Сергіївна Науковий керівник: к.т.н., м.н.с. асистент каф. ММСА О. М. Терентьєв НТУУ КПІ, Навчально-науковий комплекс ІПСА Київ, 2010

2 Постановка задачі дослідження Виконання огляду джерел літератури, присвячених розвязанню задач розпізнавання образів Розробка архітектури компютерної системи для розпізнавання символів з використанням мереж Байєса Розробка методики розпізнавання образів на основі мереж Байєса Реалізація компютерної програми в середовищі програмування Delphi 7на основі запропонованої архітектури компютерної системи та розробленої методики. Апробація розробленої компютерної програми на реальних прикладах.

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

4 Історія виникнення розпізнавання образів Початок XX ст. ­– створення кібернетики (Н. Вінер) 1929 р. та 1933 р.– Густав Таушек та Пол В. Хендел запатентували перші механічні OCR- машини 20-ті роки XX ст. – формування дискримінантного аналізу, як одного з розділів теорії і практики розпізнавання 40-ві роки ХХ ст. – А. М. Колмогоровим і О. Я. Хінчиним поставлена задача про розділення суміші двох розподілів ті роки ХХ ст. – Поява теорії статистичних рішень. В рамках кібернетики виникла нова наука – розпізнавання образів. Перші кроки в області електронного оптичного розпізнавання символів 1952 р. – перший пристрій розпізнавання мовлення (Davies, K.H., Biddulph, R. and Balashek, S.) 1957 р. – перцептрон Розенблатта 1969 р. – в Електротехнічній лабораторії (Японія) почалася розробка проекту "промисловий інтелектуальний робот" 1970-ті роки – розпізнавання формується як самостійний науковий напрямок

5 Методи розпізнавання образів методи, що базуються на принципі розділення статистичні методи методи, побудовані на основі "потенційних функцій" методи, що базуються на обчисленні висловлень методи обчислення оцінок (голосування) Класифікація методів розпізнавання образів

6 Методи розпізнавання образів ІнтенціональніЕкстенціональні Методи, засновані на оцінках густин розподілу значень ознак Класифікація методів розпізнавання образів Методи, засновані на припущеннях про клас вирішальних функцій Логічні методи Структурні (лінгвістичні) методи Колективи вирішальних правил Алгоритми обчислення оцінок (голосування) Метод k-найближчих сусідів Метод порівняння з прототипом

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

8 Мережі Байєса Теорія імовірностіТеорія графів Байєсівські мережі До впровадження терміну байєсівська мережа, МБ застосовувалися під назвою каузальних мереж (causal network), тобто мережі з причинно- наслідковими звязками. МБ зявилися на стику двох наук: теорії імовірності та теорії графів. Байєсівськими вони стали завдяки застосуванню в каузальних мережах теореми Байєса.

9 Мережі Байєса Мережа Байєса - це графічна модель процесу або об'єкта довільної природи, представлена парою. G – спрямований ациклический граф, що відповідає випадковим змінним об'єкта або процесу. B – множина параметрів, що визначають мережу. Кожній вершині МБ відповідає таблиця умовних імовірностей. Основним завданням мереж Байєса є представлення розподілу імовірностей над змінними в зручному для обробки та компактному вигляді

10 Навчання мереж Байєса СтруктураСпостереженняМетод ВідомаПовне Максимальна оцінка правдоподібності ВідомаЧасткове Максимізація математичного сподівання або пошук екстремума НевідомаПовнеПошук в просторі моделей НевідомаЧасткове Структурний алгоритм максимізації математичного сподівання

11 Наївний байєсівський класифікатор Теорема Байєса: Наївний байєсівський класифікатор – це простий імовірнісний класифікатор, який грунтується на застосуванні теореми Байєса зі строгим (наївним) припущенням про незалежність.

12 Алгоритм застосування наївного байєсівського класифікатора для розпізнавання символів Крок 1. Вхідні зображення перетворюються у вектори розмірності n 2. а) Зображення розбивається на n клітинок у довжину та n клітинок у ширину. б) Приведення зображення до чисельного вигляду. в) Дискретизація. Кожній клітинці ставиться у відповідність змінна ознаки Пі. Крок 2. Умовна ймовірність кожної ознаки знаходиться за формулою: де n[A=a j, Пi=p i ] – кількість появ конкретного значення p i ознаки П i для символу а j, n[A=a j ] – кількість появ символу a j Крок 3. Обчислення умовних імовірностей усіх можливих значень змінної А.

13 Наївна модель мережі Байєса А П1П1 П2П2 Пn2Пn2 Коренева вершина А впливає на вершини ознак П і. Вершини П і є незалежними. Для кожної вершини задані таблиці умовних ймовірностей. Можливі 2 випадки: 1. Задають ймовірності значень вершини А. Необхідно обчислити ймовірності значень вершин П і – прямий ймовірнісний висновок 2. По заданим ймовірностям значень вершин П і необхідно оцінити ймовірності значень вершини А – зворотний ймовірнісний висновок

14 Методика розпізнавання символів з використанням наївної мережі Байєса зі зворотним формуванням імовірнісного висновку А П1П1 П2П2 Пn2Пn2 Коренева вершина А відповідає значенню символа. П і – вершини ознак. Вершина А може набувати значення з множини П і можуть набувати значення 0 або 1. Крок 1. Вхідні зображення перетворюються у вектори розмірності n 2. а) Зображення розбивається на n клітинок у довжину та n клітинок у ширину. б) Приведення зображення до чисельного вигляду. в) Дискретизація. Кожній клітинці ставиться у відповідність змінна ознаки П і.

15 Методика розпізнавання символів з використанням наївної мережі Байєса зі зворотним формуванням імовірнісного висновку Крок 2. Побудова таблиці сумісного розподілу імовірностей всієї МБ. Крок 3. На основі значень сумісного розподілу імовірностей всієї МБ, за теоремою Байєса, відбувається побудова ТУІ для всіх вершин МБ. Крок 4. Інстанціювання залежних вершин МБ відповідними значеннями для зображення, яке розпізнається. Крок 5. Формування зворотного імовірнісного висновку. Модель множинної регресії: де Крок 6. Серед можливих значень кореневої вершини обирається значення з найбільшою імовірністю.

16 Динамічні мережі Байєса Динамічна мережа Байєса – це мережа, у якій значення вузлів змінюються із часом. Прикладом динамічної МБ є прихована модель Маркова, у якій на кожному шарі є один скритий вузол та один спостережуваний вузол. Х – приховані вузли, Y – спостережувані вузли. Параметри мережі з неперервними спостережуваними вузлами: N – загальна кількість прихованих станів. – сукупність можливих станів моделі – поточний стан моделі в момент часу t, t=1..T – матриця переходів, де – множина функцій розподілу імовірностей спостережень, деo t – спостереження в момент часу t – таблиця імовірностей початкового стану

17 Методика розпізнавання символів з використанням динамічних мереж Байєса Крок 1. Представлення зображень з навчальної та тестової вибірки у вигляді множини спостережень. Крок 2. Для кожного символа будується окрема МБ з випадковими значеннями параметрів. Крок 3. Вибір навчальної послідовності спостережень для символа. Крок 4. Корегування невідомих параметрів мережі – алгоритм Баума-Велха. а) Обчислення прямої процедури: б) Обчислення зворотної процедури:

18 Методика розпізнавання символів з використанням динамічних мереж Байєса Крок 6. Перевірка завершення алгоритму Баума-Велxа Крок 7. Крок 7. Якщо було виконано навчання МБ кожного символу, навчання завершено. Інакше обираємо МБ наступного символу та переходимо на крок 4. Крок 8. Розпізнавання. Множину спостережень з тестової вибірки предявляють МБ кожного символа. Крок 5. Перевірка виконання навчання на всіх навчальних послідовностях спостережень даного символа. Якщо всі зображення з навчальної вибірки були використані для навчання, переходимо на крок 6, інакше – на крок 3 в) Обчислення допоміжних змінних: г) Оновлення значень параметрів:

19 Структура компютерної системи для розпізнавання символів на основі мереж Байєса Користувач програми Блок вводу даних Блок зберігання інформації: -База навчальних зображень -База зображень для розпізнавання Блок розпізнавання Блок НБК Блок МБ зворотного імовірнісного висновку Блок ДБМ Блок попередньої обробки даних Блок обчислення умовних імовірностей ознак Блок розпізнавання Блок попередньої обробки даних Блок побудови МБ Блок розпізнавання Блок попередньої обробки даних Блок побудови ДБМ Блок розпізнавання Блок виведення результату розпізнавання

20 Структура блоку мережі Байєса зворотного імовірнісного висновку Блок попередньої обробки даних Представлення вхідних даних в чисельному вигляді Блок дискретизації Блок побудови МБ Побудова таблиці сумісного розподілу імовірностей всієї МБ Побудова ТУІ для всіх вершин МБ Блок розпізнавання Інстанціювання залежних вершин МБ Формування зворотного імовірнісного висновку

21 Структура блоку динамічної байєсівської мережі Блок попередньої обробки даних Представлення вхідних даних в чисельному вигляді Нормалізація Блок побудови ДБМ Побудова початкових МБ Налаштування параметрів на навчальній вибірці Блок розпізнавання символів

22 Архітектура пристрою для розпізнавання зображень на основі мереж Байєса 3. Блок обробки даних 2. Блок вводу даних: а) алфавіт б) множина навчальних зображень в) зображення для розпізнавання 4. Блок обчислення сумісного розподілу ймовірностей всієї МБ 5. Блок памяті зберігання сумісного розподілу ймовірностей всієї МБ 6. Блок побудови ТУІ 7. Блок памяті зберігання ТУІ 8. Блок зворотного імовірнісного виводу 9. Блока памяті зберігання таблиці вірогідностей значень кореневої вершини 10. Блок виводу результатів 1. Блок керування

23 Інтерфейс програми Подана заявка на отримання патенту України на корисну модель На базі запропонованої структури в середовищі програмування Delphi 7 реалізована програма для розпізнавання символів. Подана заявка на отримання авторського свідотства на програму Вигляд програми після запуску:

24 Інтерфейс програми На базі запропонованої структури в середовищі програмування Delphi 7 реалізована програма для розпізнавання символів Вкладка навчання та тестування:

25 Інтерфейс програми На базі запропонованої структури в середовищі програмування Delphi 7 реалізована програма для розпізнавання символів Вкладка розпізнавання:

26 Розпізнавання старих друкованих символів Для перевірки якості роботи системи було використано базу даних Google Patent Search, з якої було взято набір з 10 відсканованих патентів, а саме з кожного патенту використано перша сторінка. Вибірка складалася зі 700 окремих зображень для 26 друкованих маленьких літер англійського алфавіту. Вибірка розділялася на навчальну та перевірочну випадковим чином. Зображення, які використовувалися в навчальній вибірці, в тестовій вибірці не зустрічалися. Характеристики ЕОМ: - процесор Intel Core 2 Duo CPU 2,33 GHz - оперативна память 2 GB - встановлена операційна система Windows XP 2003 SP2 -Приклади зображень:

27 Розпізнавання за допомогою наївного байєсівського класифікатора. Залежність точності розпізнавання від розміру зображення. Навчальна вибірка: 500 зображень Перевірочна вибірка: 200 зображень Найкраща точність розпізнавання досягається при розмірі зображення 10х10. Подальше збільшення розміру зображення призводить лише до погіршення якості розпізнавання.

28 Розпізнавання за допомогою наївного байєсівського класифікатора. Розпізнавання за допомогою наївного байєсівського класифікатора. Залежність часу навчання та тестування від розміру зображення. Навчальна вибірка: 500 зображень Перевірочна вибірка: 200 зображень Збільшення розміру зображення призводить до збільшеня часу навчання та тестування.

29 Розпізнавання за допомогою наївної МБ зі зворотнім формуванням імовірнісного висновку. Залежність точності розпізнавання від розміру зображення. Навчальна вибірка: 450 зображень Перевірочна вибірка: 250 зображень Найкраща точність розпізнавання досягається при розмірі зображення 23х23. Подальше збільшення розміру зображення призводить лише до погіршення якості розпізнавання.

30 Розпізнавання за допомогою наївної МБ зі зворотнім формуванням імовірнісного висновку. Залежність часу навчання та тестування від розміру зображення. Навчальна вибірка: 450 зображень Перевірочна вибірка: 250 зображень Збільшення розміру зображення призводить до збільшеня часу навчання та тестування. Причому час тестування збільшується швидше, ніж час навчання.

31 Розпізнавання за допомогою динамічної мережі Байєса. Залежність точності розпізнавання від кількості прихованих станів. Навчальна вибірка: 450 зображень Перевірочна вибірка: 250 зображень Найкраща точність розпізнавання досягається при 8 прихованих станах.

32 Розпізнавання за допомогою динамічної мережі Байєса. Залежність часу навчання та тестування від кількості прихованих станів. Навчальна вибірка: 450 зображень Перевірочна вибірка: 250 зображень Збільшення кількості прихованих станів призводить до збільшення часу навчання та тестування.

33 Точність розпізнавання в залежності від розміру навчальної вибірки

34 Приклади помилок при розпізнаванні Зображення Правильн е значення Результат розпізнавання НБК МБ зворотного висновку ДБМ Fine Reader trttt daddJ bahbb tttlt

35 Порівняння результатів розпізнавання Назва методу Похибка розпізнавання (%) Середній час розпізнавання одного символа (мс) Наївний байєсівський класифікатор 214,5 Наївна МБ зі зворотним формуванням імовірнісного висновку Динамічна мережа Байєса FineReader779

36 Найкращі результати розпізнавання показала програма ABBY FineReader Реалізовані динамічна мережа Байєса та мережа зі зворотним формуванням імовірнісного висновку показали прийнятні результати Час розпізнавання одного символа для динамічної мережі Байєса є найбільшим Найгірші результати показав наївний байєсівський класифікатор Порівняння результатів розпізнавання

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

38 Рекомендації щодо подальших досліджень Поліпшення використаних для розпізнавання методів: Підбір оптимального розміру зображень Підбір оптимальної кількості прихованих станів На основі реалізованої компютерної програми реалізувати систему для розпізнавання друкованого тексту Застосування інших методів для розпізнавання образів

39 Публікації Участь у ХІI Міжнародній науково-технічній конференції Системний аналіз та інформаційні технології рік Участь у Х Міжнародній науковій конференції Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту – 2010 рік Подана для опублікування стаття в журнал Wireless Sensor Network M. Z. Zgurovskii, O.M. Terentyev, O.A. Akulinina, N.S. Guz. Methods of constructing probability inference in Bayesian networks using LS approach. Дата опублікування осінь-зима 2010 року.

40 Публікації Подана до опублікування стаття в журнал "Вісник Університету «Україна»" Бідюк П.І., Акулініна О.А., Гуз Н.С., Свердел К.О. Побудова ймовірнісного висновку в мережах Байєса на основі LS-методу. Подана заявка на одержання патенту на корисну модель Пристрій для розпізнавання символів на основі мереж Байєса» Подана заявка на одержання свідотства на програму для розпізнавання зображень BNetRecognizer. Заявка від 7 травня 2010 року

41 Дякую за увагу!