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

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