Савчинський Богдан Дмитрович. Контекстно-вільні граматичні конструкції для розпізнавання зображень текстових та графічних документів : дис... канд. техн. наук: 05.13.23 / НАН України; Міжнародний науково-навчальний центр інформаційних технологій та систем. — К., 2007. — 156арк. — Бібліогр.: арк. 143-152.
Анотація до роботи:
Савчинський Б. Д. Контекстно-вільні граматичні конструкції для розпізнавання зображень текстових та графічних документів. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – системи та засоби штучного інтелекту. – Міжнародний науково-навчальний центр інформаційних технологій та систем, НАН України та МОН України, Київ, 2007.
Теоретично і експериментально доведено доцільність та придатність апарату двовимірних контекстно-вільних граматичних конструкцій для розв'язання певних класів практичних задач розпізнавання семантично насичених зображень зі складною ієрархічною структурою. Сформульовано основні принципи побудови швидкодіючих програмних комплексів для розпізнавання зображень, які задаються за допомогою двовимірних контекстно-вільних граматичних конструкцій. Вперше сформульовано задачу настройки (навчання) контекстно-вільних конструкцій, як задачу відшукання таких штрафів за використання правил, що забезпечують безпомилкове розпізнавання заданої навчальної множини. Суттєва відмінність сформульованої задачі від загальновідомих задач навчання у розпізнаванні полягає у форматі навчальної множини, кожний приклад з якої є складним зображенням з ієрархічним переліком його складових фрагментів. Показано, що сформульована задача настройки контекстно-вільних конструкцій зводиться до розв’язання системи лінійних нерівностей. Незважаючи на те, що кількість нерівностей у цій системі експоненційно залежить від розміру зображень, в роботі показано її поліноміальну розв’язність і визначено ефективний скінченнокроковий алгоритм її розв’язання.
Дисертацію присвячено проблемі розпізнавання семантично насичених зображень зі складною ієрархічною структурою. В результаті дисертаційного дослідження теоретично й експериментально доведено доцільність та придатність апарату двовимірних контекстно-вільних граматичних конструкцій для вирішення практичних задач розпізнавання зображень такого типу. Цей результат дисертації є основним, і його досягнуто на основі таких окремих результатів як його складових.
Розширено структуру граматичних правил породження зображень, яка на відміну від відомих включає правила об’єднання і таких фрагментів поля зору, що перетинаються. Показано, що при такому, вочевидь доцільному розширенні задачі синтаксичного аналізу реальних зображень залишаються ефективно розв’язними. На основі аналізу функції схожості зображень показано, що для певного класу функцій таке розширення не порушує їх адитивності, котра є необхідною умовою ефективного синтаксичного аналізу реальних зображень. А саме, схожість складного зображення, як і раніше, визначається через сумарну схожість його складових частин, навіть якщо вони перетинаються.
Для дослідженого класу двовимірних контекстно-вільних граматичних конструкцій розроблено процедуру побудови виводу зображення, яка полягає у послідовному перегляді вже виведених фрагментів зображення і побудові нових згідно правил виводу. Ця процедура має поліноміальну складність, однак необхідна для її роботи пам’ять залежить від порядку перегляду фрагментів. Сформульовано та розв’язано задачу такого впорядкування фрагментів, яке забезпечує мінімальні витрати пам’яті при виконанні вказаної процедури.
Визначено підклас двовимірних контекстно-вільних граматичних конструкцій, в рамках яких синтаксичний аналіз зображення має складність, що лінійно залежить від його розміру, –– це на порядок менше, ніж складність синтаксичного аналізу у загальному випадку контекстно-вільних конструкцій. Конструкції цього підкласу можуть розумітись як двовимірне узагальнення регулярних граматик.
Сформульовано основні принципи побудови швидкодіючих програмних комплексів, придатних для вирішення практичних задач розпізнавання зображень за допомогою двовимірних контекстно-вільних граматичних конструкцій. Висока швидкодія синтаксичного аналізу у цих комплексах забезпечується тим, що:
певні фрагменти зображення виводяться в рамках таких підкласів граматик, які допускають синтаксичний аналіз більш ефективний, ніж в загальному випадку, наприклад, у рамках двовимірних регулярних граматик;
б) технологія синтаксичного аналізу зображення допускає включення сторонніх процедур розпізнавання, результат яких використовується так, що беруться до уваги лише виводи, які містять (або не містять) той чи інший фрагмент.
Побудовано програмний комплекс для розпізнавання реальних зображень нотних текстів, на якому перевірено дієспроможність вказаних моделей та алгоритмів.
Вперше сформульовано задачу настройки (навчання) контекстно-вільних конструкцій як задачу відшукання таких штрафів за використання правил, що забезпечують безпомилкове розпізнавання заданої навчальної множини. Суттєва відмінність сформульованої задачі від загальновідомих задач навчання у розпізнаванні полягає у форматі навчальної множини: кожен приклад з навчальної множини є складним зображенням з ієрархічним переліком його складових фрагментів.
Показано, що сформульована задача настройки контекстно-вільних конструкцій зводиться до розв’язання системи лінійних нерівностей. Незважаючи на те, що кількість нерівностей у цій системі експоненційно залежить від розміру зображень, у роботі показано її поліноміальну розв’язність і визначено ефективний скінченнокроковий алгоритм її розв’язання. Цей результат є найважливішим, з теоретичної точки зору, результатом роботи, оскільки вказує спосіб розв’язання задачі навчання для широкого класу задач структурного розпізнавання, і не лише тих, що пов’язані з контекстно-вільними формальними конструкціями.
Сформульовано і розв’язано нову задачу побудови еталонів літер для розпізнавання текстових зображень як задачу настройки певних числових параметрів контекстно-вільних конструкцій. Новизна цих результатів полягає в тому, що у відомих задачах йдеться про настройку системи, яка має забезпечити правильне розпізнавання окремих, ізольованих одна від одної літер, а у новій задачі йдеться про настройку системи, яка має правильно розпізнавати текстові рядки в цілому, у яких літери не відокремлені одна від одної. Областю практичного використання цих алгоритмів є розпізнавання сильно спотворених текстів, що експериментально перевірено на реальних зображеннях.
Досліджено нові задачі розпізнавання послідовностей, зокрема текстових рядків, у їх статистичних постановках і показано, що загальновідома задача пошуку найімовірнішої послідовності є лише однією з можливих і в ряді випадків не найбільш доречною. Сформульовано і розв’язано декілька прикладів задач у їх нетрадиційних постановках.
Публікації автора:
Статті у наукових фахових виданнях.
[1] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Синтаксичний аналіз та розпізнавання друкованих нотних текстів // Управляющие системы и машины. – 2003. – №4. – С. 30–38.
[2] Савчинський Б. Д. Нетрадиційні задачі розпізнавання тексту в межах байєсівської теорії прийняття рішень // Управляющие системы и машины. – 2005. – №1. – С. 8–17.
[3] Савчинський Б. Д., Камоцький О. В. Настройка алгоритму розпізнавання тексту // Управляющие системы и машины. – 2005. – №2. – С. 17–24.
[4] Павлюк О. В., Савчинський Б. Д. Ефективний синтаксичний аналіз та розпізнавання структурованих зображень // Управляющие системы и машины. – 2005. – №5. – С. 13–24.
Статті у збірниках праць конференцій.
[5] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Комп’ютерна технологія для розпізнавання типографських нотних текстів // Міжнародна конференція «Електронні зображення та візуальні мистецтва» EVA-2002. Збірник праць. – Київ: 2002. – С. 82–86.
[6] Savchynskyy B., Kamotskyy O. Character templates learning for textual images recognition as an example of learning in structural recognition // Proc. of the 2-nd Intern. Conf. on Document Image Analysis for Libraries DIAL 2006. — April 27-28 — Pp. 88–95.
Тези конференцій.
[7] Савчинський Б. Д. Синтаксичний аналіз та розпізнавання друкованих нотних текстів // Автоматика – 2004 Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. 93.
[8] Савчинський Б. Д., Камоцький О. В. Налаштування параметрів в задачах структурного розпізнавання // Автоматика – 2004 Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. 94.
