Національна академія наук України

Міністерство освіти і науки України

Міжнародний науково-навчальний центр

інформаційних технологій та систем

Савчинський Богдан Дмитрович

УДК 004.93'1:[519.76+519.814+519.168+519.857]

КОНТЕКСТНО-ВІЛЬНІ ГРАМАТИЧНІ КОНСТРУКЦІЇ ДЛЯ РОЗПІЗНАВАННЯ ЗОБРАЖЕНЬ ТЕКСТОВИХ ТА ГРАФІЧНИХ ДОКУМЕНТІВ

05.13.23 – системи та засоби штучного інтелекту

Автореферат

дисертації на здобуття наукового ступеня
кандидата технічних наук

Київ - 2007

Дисертацією є рукопис.

Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій і систем НАН України та МОН України у відділі обробки та розпізнавання зображень.

Науковий керівник: | Доктор фізико-математичних наук, професор
Шлезінгер Михайло Іванович, Міжнародний науково-навчальний центр інформаційних технологій та систем, головний науковий співробітник.

Офіційні опоненти: | Доктор фізико-математичних наук, професор
Кириченко Микола Федорович, Інститут кібернетики ім Глушкова НАН України, провідний науковий співробітник.

Кандидат технічних наук Калмиков Володимир Григорович, Інститут проблем математичних машин і систем НАН України, старший науковий співробітник.

Провідна установа: |

Національний технічний університет України „Київський політехнічний інститут”

Захист відбудеться "7" червня 2007 року о __12_ годині на засіданні спеціалізованої вченої ради Д 26.171.01 в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України за адресою:

03680, Київ, проспект акад. Глушкова, 40.

З дисертацією можна ознайомитися в бібліотеці Міжнародного науково-навчального центру інформаційних технологій та систем НАН України та МОН України: 03680, Київ, проспект акад. Глушкова, 40.

Автореферат розісланий "4" _травня_ 2007 р.

Вчений секретар спеціалізованої

вченої ради |

ТАРАСОВ В. О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

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

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

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

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

Вирішення вказаних актуальних питань полягає в:

· таких модифікаціях відомих формально-граматичних схем, які б зменшили часову та просторову складність розв’язання прикладних задач;

· постановці та розв’язанні задач навчання та настройки параметрів алгоритмів структурного розпізнавання;

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України.

Результати роботи є складовою частиною:

· науково-дослідної роботи “Дослідження контекстно-вільних формальних конструкцій та ієрархічних моделей зображень” на замовлення Національної Академії наук України, 2004-2006 рр. ( № держреєстрації 0104U000952), яка виконувалась відповідно до планів наукових досліджень відділу № 120 “Розпізнавання зображень” Міжнародного науково-навчального центру інформаційних технологій та систем;

· робіт за міжнародним науково-дослідним проектом “Принципи розпізнавання образів у сигналах, послідовностях символів та зображеннях на основі відмінностей (Principles of Dissimilarity-based Pattern Recognition in Signals, Symbolic Sequences and Images (acronym PRINCESS)) INTAS Ref. Nr 04-77-7347” на замовлення європейської грантової організації INTAS.

Особисто автором було розроблено:

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

· програмний комплекс для розпізнавання зображень нотних текстів;

· архітектуру програмного комплексу для розпізнавання зображень за заданою загальною структурною конструкцією;

· постановку та розв’язання задачі настройки (навчання) для довільної загальної структурної конструкції;

· архітектуру програмного комплексу для настройки еталонів в задачі розпізнавання текстових зображень;

· постановку та розв’язання ряду нетрадиційних байєсівських задач розпізнавання текстових зображень.

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

Завданнями роботи є:

· модифікувати відомі формально-граматичні схеми так, щоб зменшити часову та просторову складність розв’язання прикладних задач;

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

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

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

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

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

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

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

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

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

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

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

Практичне значення одержаних результатів. Результати роботи впроваджено в Державній науково-технічній програмі “Образний комп’ютер” для розробки систем розпізнавання креслярсько-графічних зображень та Центрі машинного бачення Чеського технічного університету (Прага) для розпізнавання зображень математичних формул і використовувались при виконанні таких контрактів:

· “Апаратно-програмний комплекс для автоматичної обробки креслярсько – графічних та текстових зображень” в рамках Державної науково-технічної програми “Образний комп’ютер”, 2001 р. (№ держреєстрації U007950);

· “Розроблення інтелектуальних засобів розуміння зображень та створення на їх основі дослідних зразків підсистем ОК та приладів” в рамках Державної науково-технічної програми “Образний комп’ютер”, 2002 р. (№ держреєстрації U006897);

· “Розробити базову інтелектуальну технологію сприйняття, розпізнавання та розуміння зображень та створити на цій основі прикладні технології розпізнавання та зразки наукомістких виробів” в рамках Державної науково-технічної програми “Образний комп’ютер”, 2003 р. (№ держреєстрації U005769);

· “Розробити інтелектуальні технології “Бачу і розумію, що бачу” і виготовити експериментальні зразки пристроїв, що їх реалізують” в рамках Державної науково-технічної програми “Образний комп’ютер”, 2004 р. (№ держреєстрації U008471).

Особистий внесок здобувача. Наукові результати, представлені в дисертації та статтях, отримані автором самостійно. В статтях, написаних разом із співавторами, внесок дисертанта є таким:

· в статті [1] дисертанту належить формулювання моделі лінійних граматик з фіксованими розмірами нетерміналів, аналіз ефективності відповідного алгоритму розпізнавання та ідея застосування цієї моделі до розпізнавання друкованих нотних текстів;

· в статті [3] дисертанту належить постановка та алгоритм розв’язання задачі настройки еталонів літер тексту;

· в статті [4] дисертанту належить модель двовимірної контекстно-вільної граматики з перекриттям сегментів та відповідний алгоритм синтаксичного аналізу зображень.

Експериментальні дослідження виконані за допомогою програмного забезпечення, реалізованого автором разом із співавторами статей Анохіною М. О., Камоцьким О. В. та Павлюк О. В.

Апробація результатів дисертації. Результати дисертації оприлюднено на таких конференціях: Міжнародна конференція “Document Image Analysis for Libraries (DIAL’06)”, Ліон, Франція; Автоматика - 2004: 11-а міжнародна конференція з автоматичного управління; Міжнародна конференція “Електронні зображення та візуальні мистецтва” EVA 2002 Київ;

Результати роботи неодноразово доповідались на семінарі Державної науково-технічної програми “Образний комп’ютер”, на семінарах в Інституті штучного інтелекту Дрезденського технічного університету, Центрі машинного бачення Чеського технічного університету, Інституті космічних досліджень НАНУ та у відділі розпізнавання зображень Міжнародного науково-навчального центру інформаційних технологій та систем.

Публікації. Матеріали дисертації оприлюднено у 8 наукових публікаціях. Серед них 4, одна з яких без співавторів, опубліковано у фахових журналах, затверджених ВАК України, 2 доповіді та 2 тез – у збірниках праць конференцій, в тому числі міжнародної конференції “Document Image Analysis for Libraries (DIAL’06)”, Лiон, Францiя.

Структура дисертації. Дисертація складається зі вступу, 4 розділів, висновків, списку використаних джерел (9 сторінок, 75 найменувань) та додатку. Робота містить 28 рисунків. Загальний обсяг дисертації 130 сторінок. Повний обсяг дисертації (включаючи список використаних джерел, рисунки та додаток) становить 155 сторінок.

ЗМІСТ РОБОТИ

Перший розділ “Аналіз сучасного стану і вибір напрямків досліджень” складається з трьох підрозділів, присвячених відповідно трьом наступним розділам дисертації.

В першому підрозділі “Структурні методи розпізнавання зображень документів” здійснено стислий огляд двох найпоширеніших підходів – графового та граматичного – до побудови моделей та розпізнавання зображень текстових і графічних документів. Другий підрозділ, “Настройка та навчання алгоритмів розпізнавання документів”, містить опис традиційного підходу до налаштування параметрів алгоритмів розпізнавання структурованих документів та вказує на його недоліки.

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

Другий розділ “Контекстно-вільна конструкція з виділеними сегментами” присвячено такому узагальненню двовимірних контекcтно-вільних граматик та удосконаленню відповідних алгоритмів синтаксичного аналізу, які необхідні для їх практичного застосування при розпізнаванні зображень.

Нехай – поле зору, і його висота і ширина відповідно. Фрагментом поля зору називатимемо його прямокутну підмножину вигляду . Розміром фрагмента називатимемо кількість елементів, що входять до його складу. Нехай також . Множину усіх можливих фрагментів позначатимемо . Зокрема, .

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

Нехай - скінчена множина імен. Одне з імен називатимемо аксіомою. Певну підмножину називатимемо множиною термінальних імен. Поіменований фрагмент називатимемо сегментом. Множину всіх сегментів позначатимемо . Ім’я та фрагмент сегмента позначатимемо відповідно та . Множину сегментів з термінальними іменами називатимемо множиною термінальних сегментів. Сегмент називатимемо аксіомним і позначатимемо . Нехай – предикат, який визначає множину правил виводу. Вважатимемо, що якщо , то: (1) і , (2) . Кількість елементів у множині називатимемо кількістю правил виводу і позначатимемо . Введемо також предикат , який визначає множину правил іменування.

Контекстно-вільною конструкцією називатимемо п’ятірку .

Виводом сегмента в конструкції за умови зображення називатимемо таку підмножину сегментів, для якої виконуються наступні чотири умови: (1) , (2) , (3) для всіх , існує єдина пара , що , (4) для всіх , . Множину всіх виводів сегмента за умови зображення позначатимемо , а множину позначимо .

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

Алгоритм розв’язання цієї задачі полягає в послідовній побудові списку сегментів, впорядкованого за їх розмірами. Для позначимо .

Алгоритм 1. Розпізнавання в контекстно-вільних конструкціях.

1. Внести до списку всі такі сегменти , що .

2. Рухатись списком від менших сегментів до більших. На кожному кроці для поточного сегмента виконати дії кроку 3. Якщо оброблено всі сегменти з , то кінець.

3. Вставити в таку множину сегментів .

Зображення виводиться в даній граматиці т. і т. т., коли .

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

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

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

1. , що ;

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

Можна показати, що часова складність алгоритму у випадку двовимірних контекстно-вільних граматик дорівнює , а просторова – .

Практичне застосування наведених означення контекстно-вільної граматики та постановки задачі розпізнавання як задачі на точний збіг суттєво обмежуються такими їхніми властивостями:

· важко знайти галузь розпізнавання, де зображення розділяються на змістовно осмислені прямокутні фрагменти, які не перетинаються;

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

· в постановці задачі розпізнавання не враховується наявність шуму на зображеннях.

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

(1)

Задача, еквівалентна), могла би бути поставлена на основі апарату двовимірних контекстно-вільних конструкцій таким чином:

1. , виконується єдина з трьох альтернатив: (1) ; (2) ; (3) ;

2. ;

3. кожному термінальному імені , поставлено у відповідність еталонне зображення ;

4. , .

Задача розпізнавання, еквівалентна), полягає в обчисленні

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

(2)

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

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

Для розв’язання задачі розпізнавання, яка полягає в обчисленні

(3)

може бути використано алгоритм .

Алгоритм 2. Розв’язання задачі) в контекстно-вільних конструкціях.

1. Внести до списку всі . Для кожного з них обчислити і зберегти величину .

2. Рухатись списком від менших сегментів до більших. На кожному кроці для поточного сегмента виконати дії кроку . Якщо оброблено всі сегменти з , то кінець.

3. Для всіх обчислити ; вставити всі в і покласти для них ; для покласти .

Зображення виводиться в даній граматиці т. і т. т., коли . Якість найкращого виводу дорівнює .

Алгоритм 2, як і алгоритм 1, має часову складність в найгіршому випадку. Ця величина може бути як надзвичайно великою (), так і порівняно малою залежно від конкретного предикату .

В дисертації визначено лінійний за складністю () підклас конструкцій, які можуть вважатися двовимірними узагальненнями класичних регулярних граматик Хомського. Окрім цього, в дисертації наведено схему декомпозиції алгоритму синтаксичного аналізу, яка дозволяє використовувати для виводу окремих сегментів алгоритми, що є ефективнішими за загальний алгоритм 2. Ця ж схема використовується і для зниження витрат пам’яті алгоритму 2. Цю схему буде розглянуто одразу після ще одного зауваження щодо складності алгоритму 2.

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

У підрозділі “Контексто-вільна конструкція з виділеними сегментами. Мінімізація пам’яті, необхідної для синтаксичного аналізу” наведено схему декомпозиції алгоритму синтаксичного аналізу, яка дозволяє використовувати для виводу окремих сегментів алгоритми, що є ефективнішими за загальний алгоритм 2. Нехай множина виділених сегментів і . Ми будуватимемо алгоритм розпізнавання таким чином, що для кожного сегмента з цієї множини обов’язково підраховуватиметься якість його найкращого виводу. Наведемо цей алгоритм і вкажемо на його переваги перед алгоритмом 2. Для його формулювання визначимо орієнтований граф з множиною вершин і множиною ребер . Покладемо . Множину ребер визначимо так: , якщо

Неважко бачити, що граф задає частковий порядок на множині . Для виконання алгоритму цей порядок слід доповнити до лінійного, тобто ввести взаємнооднозначне відображення: таке, що з випливає . Позначимо через , множину , а через – звуження на множину .

Алгоритм 3. Розпізнавання в контекстно-вільних конструкціях з виділеними сегментами.

1. Покласти і обчислити .

2. Якщо , покласти , інакше обчислити за допомогою алгоритму 2 в граматиці .

3. Якщо обчислено , то кінець. Інакше покласти і перейти на крок 2.

Коментар: Якість найкращого виводу дорівнює .

Алгоритм має такі властивості:

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

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

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

Третій розділ “Настройка параметрів контекстно-вільних конструкцій” присвячено налаштуванню параметрів контекстно-вільних конструкцій. Ця задача має такий формат: задано навчальну множину , яка складається з навчальних зображень з множини зображень та відповідних їм виводів з множини виводів. Введемо також певну множину векторів параметрів. Нехай , , — параметризована за вектором функція, яка визначає штраф за вивід зображення .

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

Виконання умови задачі означає правильне розпізнавання усіх зображень з навчальної множини.

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

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

Ця система є еквівалентною системі лінійних нерівностей

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

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

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

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

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

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

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

(4)

За допомогою позначено ймовірність сегментації при умові зображення .

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

(5)

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

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

ВИСНОВКИ

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

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

2. Для дослідженого класу двовимірних контекстно-вільних граматичних конструкцій розроблено процедуру побудови виводу зображення, яка полягає у послідовному перегляді вже виведених фрагментів зображення і побудові нових згідно правил виводу. Ця процедура має поліноміальну складність, однак необхідна для її роботи пам’ять залежить від порядку перегляду фрагментів. Сформульовано та розв’язано задачу такого впорядкування фрагментів, яке забезпечує мінімальні витрати пам’яті при виконанні вказаної процедури.

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

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

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

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

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

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

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

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

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

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Статті у наукових фахових виданнях.

[1] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Синтаксичний аналіз та розпізнавання друкованих нотних текстівУправляющие системы и машины. – 2003. – №4. – С. –38.

[2] Савчинський Б. Д. Нетрадиційні задачі розпізнавання тексту в межах байєсівської теорії прийняття рішеньУправляющие системы и машины. – 2005. – №1. – С. –17.

[3] Савчинський Б. Д., Камоцький О. В. Настройка алгоритму розпізнавання текстуУправляющие системы и машины. – 2005. – №2. – С. –24.

[4] Павлюк О. В., Савчинський Б. Д. Ефективний синтаксичний аналіз та розпізнавання структурованих зображеньУправляющие системы и машины. – 2005. – №5. – С. 13–24.

Статті у збірниках праць конференцій.

[5] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Комп’ютерна технологія для розпізнавання типографських нотних текстів // Міжнародна конференція “Електронні зображення та візуальні мистецтва” EVA-2002. Збірник праць. – Київ: 2002. – С. –86.

[6] SavchynskyyKamotskyy 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. –95.

Тези конференцій.

[7] Савчинський Б. Д. Синтаксичний аналіз та розпізнавання друкованих нотних текстівАвтоматика – Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. .

[8] Савчинський Б. Д., Камоцький О. В. Налаштування параметрів в задачах структурного розпізнаванняАвтоматика – Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. .

АНОТАЦІЯ

Савчинський Б. Д. Контекстно-вільні граматичні конструкції для розпізнавання зображень текстових та графічних документів. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – системи та засоби штучного інтелекту. – Міжнародний науково-навчальний центр інформаційних технологій та систем, НАН України та МОН України, Київ, 2007.

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

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

АННОТАЦИЯ

Савчинский Б. Д. Контекстно-свободные грамматические конструкции для распознавания изображений текстовых и графических документов. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта. - Международный научно-учебный центр информационных технологий и систем, НАН Украины и МОН Украины, Киев, 2007.

Теоретически и экспериментально доказано целесообразность и применимость аппарата двумерных контекстно-свободных грамматических конструкций для решения определённых классов практических задач распознавания семантически насыщенных изображений со скложной иерархической структурой. Сформулированы основные принципы построения быстродействующих программных комплексов для распознавания изображений, задаваемых при помощи двумерных контекстно-свободных конструкций. Впервые сформулировано задачу настройки (обучения) контекстно-свободных конструкций как задачу отыскания таких штрафов за использование правил, которые обеспечивают безошибочное распознавание заданого обучающего множества. Существенное отличие сформулированной задачи от общеизвестных задач обучения в распознавании состоит в формате обучающего множества, каждый пример из которого является сложным изображением с иерархическим перечнем его составляющих фрагментов. Показано, что сформулированная задача настройки контекстно-свободных конструкций сводится к решению системы линейных уравнений. Несмотря на то, что количество уравнений в этой системе экспоненциально зависит от размера изображений, в работе показано полиномиальную разрешимость задачи и разработан эффективный конечношаговый алгоритм её решения.

Ключевые слова: распознавание изображений документов, контекстно-свободные грамматические конструкции, настройка контекстно-свободных конструкций, обучение в структурном распознавании.

ABSTRACT

SavchynskyyContext-free grammar constructions for recognition of textual and graphical document images. – Manuscript.

Thesis for scientific degree of candidate of technical sciences on speciality 05.13.23 - systems and tools of artificial intelligence. - International Research and Training Center for Information Technologies and Systems, National Academy of Sciences and Ministry of Science and Education of Ukraine, Kyiv, 2007.

Advisability and applicability of two-dimensional context-free grammatical constructions for recognition of complex hierarchically structured images have been theoretically and practically proved. The following particular results have been achieved: the structure of grammatical rules has been extended, namely, such rules are introduced, which allow image fragments to intersect. It is demonstrated that after such obviously expedient extension the task of real image parsing remains still effectively solvable. It is proved that for a certain class of similarity functions such extension does not violate their additivity, which is a necessary condition of an effective parsing. Namely, similarity of a complex image is determined by a total similarity of its constituents, even if they intersect.

For the investigated class of two-dimensional grammar constructions an image derivation procedure was build, which consists in reviewing already derived image fragments and creating the new ones according to derivation rules. This procedure has a polynomial complexity, however its space complexity depends on an order of image fragments review. The task of optimal review ordering to minimize space complexity was formulated and solved.

A subclass of two-dimensional context-free grammar constructions was defined, which has a linear parsing complexity with respect to an image size. This complexity is much less then the corresponding one in a general case of context-free constructions. Constructions of this subclass can be considered as a