Современные информационные технологии/1. Компьютерная инженерия

Поночовний О.В., Нечипорук О.П. к.т.н., доцент

Національний авіаційний університет, Україна

Система синтактичного розпізнавання образів

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

Блок передобробки здійснює, по-перше, функції кодування і апроксимації і, по-друге, функції фільтрації, відновлення і поліпшення об'єкта. Вихідний об'єкт спочатку кодується або апроксимується так, щоб це було зручно для подальшої обробки. Чорно-біле зображення, наприклад, можна кодувати за допомогою решітки (або матриці), що складається з нулів і одиниць, а криву можна апроксимувати відліками в дискретні моменти часу або кінцевим набором коефіцієнтів Фур'є. Потім використовують методи фільтрації, відновлення і (або) поліпшення для ліквідації шуму, відновлення спотворень і (або) поліпшення якості закодованих (або апроксимованих) об'єктів. Зазвичай припускають, що на виході препроцесора є об'єкти відносно «хорошої якості». Кожен підданий передобробці об'єкт потім подають як структури мовного типу (наприклад, ланцюжки). Цей процес подання об'єкта складається, по-перше, з сегментації і, по-друге, з виділення непохідних елементів (ознак). Щоб уявити об'єкт через його підобрази, потрібно цей об'єкт сегментувати і в той же час ідентифікувати (або виділити) в ньому непохідні елементи. Іншими словами, кожен підданий передобробці об'єкт розділяється на частини і непохідні елементи на основі заздалегідь заданих синтаксичних операцій (або операцій композиції).

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

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

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

Література:

1. Фу К. Структурные методы в распознавании образов / К. Фу ; пер. с англ. Н.В. Завалишина ; под ред. М.А. Айзермана. – М. : Мир, 1977. – 319 с.

2. Журавлёв Ю.И. Распознавание образов и анализ изображений / Ю.И. Журавлёв, И.Б. Гуревич // Искусственный интеллект: Модели и методы. Т. 1. – М. : Радио и связь, 2000. – 310 с.

3. Павлидис Т. Алгоритмы машинной графики и обработки изображе- ний / Т. Павлидис ; пер. с англ. Н.В. Петрова ; под ред. М.С. Гуреви- ча. – М. : Радио и связь, 1986. – 400 с.