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

Спосіб розпізнавання плоских геометричних фігур, який полягає в тому, що перетворюють зображення в послідовність сигналів, проектують зображення фігури на фоточутливий елемент, виділяють вершини фігури і визначають відстані між сусідніми вершинами, визначають периметр фігури, формують вектор ознак, до якого входять величини периметра, кількості вершин та величин відстаней між сусідніми вершинами, порівнюють значення отриманого вектора із значеннями еталонних векторів, за ступенем співпадання векторів визначають фігуру, що розпізнають, який відрізняється тим, що зображення фігури проектують на клітинний автомат, виділяють контур зображення, з крайньої клітини якого формують сигнал збудження, який передається сусіднім клітинам і розповсюджується по всьому полю клітинного автомата, згідно з вибраною околицею, в момент надходження сигналу збудження до найближчої клітини, що належить контуру зображення, формують сигнал обнуління збудженнях клітин, що не належать контуру зображення, здійснюють передачу сигналу збудження від збудженої клітини, що U 2 61795 1 3 зсуву і постійного обчислення та порівняння функції перерізу площин та її копії. Відомо спосіб розпізнавання зображень з окопроцесорним виділенням визначників (Патент України на винахід №52616,G06K9/00, Бюл. №1, 2003p.), який полягає у використанні паралельного накопичення (додавання) одночасно всієї інформації, що надходить, та паралельного виділення загальних частин, незалежно від типу інформації всі сигнали перетворюють на логіко-часові функції та виділяють одразу декілька загальних частин, які обробляють за допомогою певного ієрархічного додавання, згідно з ієрархічною побудовою блока синтезатора - генератора визначників, вводять якісні визначники зображень, кожен з яких діє на вихідну функцію за допомогою оператора впливу, який являє собою певну функціональну залежність, за якою він діє на функції виходу, після закінчення обробки утворюється цільовий кодер, його вихід постійно аналізують та порівнюють з раніше відомими та записаними в пам'яті у вигляді логіко-часових функцій еталонними зразками бази знань, за допомогою яких виконують кінцеве розпізнавання зображень, у випадку відсутності відповідного еталонного зразка, отриманий результат, після експериментальної ідентифікації, записують як новий еталон та представляють як раніше невідому еталонну логіко-часову функцію для інтерактивного уточнення, потім визначають найбільш близький еталон згідно з операцією порівняння. Недоліком даного способу є низька швидкодія, яка залежить від витрат часу на ієрархічне додавання, синтез - генерацію сигналів та аналіз логікочасових функцій. Крім того, спосіб має низьку надійність та достовірність функціонування за рахунок використання великих об'ємів апаратури та високих вимог до генерації та формування імпульсних послідовностей у часі, що впливає на результат паралельно ієрархічному додаванню по часу та амплітуді. Найбільш близьким за змістом є спосіб розпізнавання плоских геометричних фігур (Патент України №51190А Опубл. 2002 - Бюл. №11), що полягає у перетворенні зображення фігури в набір сигналів, проектують зображення фігури на фоточутливий елемент, виділяють вершини фігури і визначають відстані між сусідніми вершинами, визначають площу та периметр фігури шляхом підрахунку точок, що належать контуру та площині зображення фігури, формують вектор ознак, до якого входять величини площини, периметра, кількості вершин та величин відстаней між сусідніми вершинами, порівнюють значення отриманого вектора із значеннями еталонних векторів, за ступенем співпадіння векторів визначають фігуру, що розпізнають. Недоліком даного способу є низька швидкодія, в зв'язку з витрачанням великої кількості часу на визначення та формування вектора ознак, а також необхідність витрат часу на порівняння векторів з великою кількістю ознак. Недоліком способу є низька інформативність за рахунок використання великої кількості ознак, що описують зображення. В основу корисної моделі поставлена задача створення способу для розпізнавання плоских 61795 4 фігур, який дозволяє зменшити час, що витрачається на розпізнавання та підвищити інформативність. Це досягається за рахунок визначення його геометричної форми, шляхом обігу його контуру сигналом збудження та формування відповідної імпульсної послідовності, по формі якої судять про фігуру, що розпізнається. Висока інформативність способу досягається тим, що фігура подається часовими характеристиками імпульсної послідовності та амплітудами імпульсів. Поставлена задача вирішується тим, що, згідно зі способом, розпізнавання плоских геометричних фігур, перетворюють зображення в послідовність сигналів, проектують зображення фігури на фоточутливий елемент, виділяють вершини фігури і визначають відстані між сусідніми вершинами, визначають периметр фігури, формують вектор ознак, до якого входять величини периметра, кількості вершин та величин відстаней між сусідніми вершинами, порівнюють значення отриманого вектора із значеннями еталонних векторів, за ступенем співпадіння векторів визначають фігуру, що розпізнають, зображення фігури проектують на клітинний автомат, виділяють контур зображення, з крайньої клітини якого формують сигнал збудження, який передається сусіднім клітинам і розповсюджується по всьому полю клітинного автомата, згідно з вибраною околицею, в момент надходження сигналу збудження до найближчої клітини, що належать контуру, формують сигнал обнуління збудженнях клітин, що не належать контуру зображення, здійснюють передачу сигналу збудження від збудженої клітини, що належить контуру зображення, до сусідніх клітин, що належать контуру зображення в одному з напрямків від початкової збудженої клітини, що належить контуру зображення, під час передачі сигналу збудження до сусідньої клітини, що належить контуру зображення, формують одиничний імпульс на виході клітинного автомата, при зміні напрямку розповсюдження сигналу збудження, інакше імпульс не формується, обходять сигналом збудження усі клітини контуру та формують відповідну послідовність, видаляють імпульси, які мають амплітуди, менші заданої порогової амплітуди, по отриманій послідовності імпульсів визначають форму фігури, згідно з якою величини амплітуд указують на вершину та величину кута в ній, а по часу між імпульсами визначають відстані між сусідніми вершинами, перетворюють імпульсну послідовність у послідовність чисел, яку порівнюють з послідовністю чисел, що зберігаються у пам'яті як еталонні, якщо відбулося співпадіння з еталонною послідовністю, то фігура розпізнана, а якщо співпадіння не відбулося, то здійснюють зсув вхідної послідовності в одному з напрямків і отриману послідовність порівнюють з еталонними послідовностями чисел, зсув вхідної послідовності здійснюють циклічно до співпадіння з еталонною послідовністю, якщо після повного циклічного зсуву співпадіння не відбулося, то вхідну послідовність записують у пам'ять, по кількості зсувів до співпадіння визначають орієнтацію фігури. На фіг.1 представлена графічна послідовність розповсюдження та формування сигналів у кліти 5 нах клітинного автомата (КА), що належать фону, на фіг.2 - графічна послідовність розповсюдження та формування сигналів у клітинах клітинного автомата (КА), що належать зображенню, на фіг.3 приклад сформованої імпульсної послідовності, на фіг.4 - структурна схема пристрою розпізнавання плоских геометричних фігур, що реалізує спосіб, на фіг.5 - фрагмент середовища КА, на фіг.6 схематичне зображення однієї клітини КА, на фіг.7 - функціональна схема клітини КА, а на фіг.8 - приклад інтерфейсу роботи комп'ютерної програми, що моделює спосіб. Структурна схема пристрою розпізнавання плоских геометричних фігур (фіг.4) складається з блока 1 перетворення та переносу зображення на КА (БППЗ), клітинний автомат 2 (КА), двомірний диз'юнктор 3, блок 4 обробки імпульсної послідовності (БОІП), блок 5 порівняння (БП) та блок 6 зберігання еталонів (БЕ), вихід якого підключений до першого входу 7 БП5, другий вхід 8 якого підключений до виходу БОІП 4 та до першого входу 9 БЕ 6. Другий вхід 10 БЕ 6 підключений до виходу БП 5 та до виходу 11 пристрою розпізнавання. Інформаційний вхід 12 пристрою розпізнавання підключений до входу БППЗ 1, вихід якого підключений до інформаційного входу КА 2, інформаційні виходи кожної клітини якого підключені до відповідних входів двомірного диз'юнктора 3. Фрагмент середовища КА 2(фіг.5) містить клі13i 1, j, тини 13 з чотирикутною мозаїчною формою, які 13i  та 13i 1, j, мають зв'язки по входах 1, j, виходах з найближчими сусіднімиi 1, j, 13 клітинами по, вертикалі, горизонталі 13i 1, j 13i 1, j 1, та вертикалі. Крім того, кожна клітина має інфор13 13i 1, j, 13i 1, j, 13i 14 13i  15. 13 i  j , маційний вхід1, j,та вихід 1, j 1, i 1,1, j1, зі i 1, j 1, i13,1 1, 13i 1,1, j, , 13i Згідно 13схематичним, jзображенням (фіг.6), jклі13i 1 , 13 1i j, 13i  j 1 1, j, тина містить інформаційні входи 16, які підключа13i 1, 1, 13i   j, 13i13,1, j 1, 13i1,11,1, 13i 1, j 1, 13i   ютьсяj до 13i1,1, j 1, 15 1iвідповіднихj, jклітин околиці виходів  j, 13i 1, j, 1, 13i 1,1, j 1, i13i , j,1, 13ji1, j 1, 13i 1, j 1,  13i  j, 13 1, j 11 13i, 1 13i 1, j, 1, 13i 1,1, j1,1, i13,,jj1,, 13i1, 1, j 1, 13i 1, j 1,  13i  j   13 1i 1 13i j 1 , вхід 17 обну13i 1 1, 13i 1 j 1, ління, jклітиниi, j,1, 13входи ,18 13i 1, j 1, збудження, 1, j j 1   13 фону, i13i1,1 сигналів 13i 1, j 1, які підключені до ,виходів 19 формування13 сигналів 13i,,1, 1, 13i 1, j 1 13i 1, j 1, 13i, j 1, i, j 1, j 1 j  13i збудження клітин околиці 13i1, j 1 13i 1, j 1, 13i, j 1, 13i j  13i 1, , 13 j 13 13ii1,1jj1 1,i 1 j,13i 1 j 113i 1 j 1,13i 1 j 1,13i 1 j1, 1, 1 , , , , , , 13i 1, j 1, 13i, j 1, 13i1, j 1 13i, j 1,13i1, j  1 . 13i, jКрім 13i1, j 1 1, того, кожна клітина 13 середовища КА має, jвихід 20 формування сигналу обнуління, який 13i1 1 здійснює обнуління клітин фону, а також вихід 21 формування імпульсу, який підключений до відповідного входу двомірного диз'юнктора 3 (фіг.4). Клітина КА (фіг.7) містить два блоки аналізу клітин околиці (БАКО) 22, 233, блок 24 формування сигналу збудження (БФСЗ), елемент 25 пам'яті стану зображення (ЕП), блок 26 формування вихідного імпульсу (БФВІ), та чотири кон'юнктори 2730, виходи перших трьох кон'юнкторів 27-29 підключені до відповідних входів диз'юнктора 31, вихід якого підключений до першого входу БФСЗ 24, другий вхід якого підключений до виходу четвертого кон'юнктора 30, інверсний вхід якого підключений до інверсного входу першого кон'юнктора 27, а другий вхід підключений до входу 17 обнуління клітини фону, а вихід БФСЗ 24 підключений до 61795 6 виходу 19 формування сигналу збудження клітини, вихід ЕП 25 підключений до інверсного входу першого кон'юнктора 27, перших входів другого та третього кон'юнкторів 28,29 та першому керуючому входу 32 другого БАК 23, другий керуючий вхід 33 якого з'єднаний з виходом третього кон'юнктора 29, вихід другого кон'юнктора 28 підключений до виходу 20 формування сигналу обнуління, інформаційний вихід 21 клітини, підключений до виходу БФВІ 26, вхід якого підключений до виходу другого БАКО 23, інформаційні входи 16 якого підключені до виходів 15 ЕП 25 клітин околиці, другі входи другого та третього кон'юнкторів 28, 29 підключені, відповідно, до першого та другого виходів 34, 35 першого БАКО 22, інформаційні входи якого підключені до виходів 15 ЕП 25 клітин околиці, а керуючі входи 18 підключені до виходів 19 клітин околиці, інформаційний вхід 14 клітини підключений до входу установки в одиничний стан ЕП 25. Суть способу розпізнавання плоских геометричних фігур полягає в наступному. Після попередньої обробки реального зображення фігури його бінаризують і шляхом сканування або паралельно по всім входах, записують зображення у КА (фіг.1,а). З лівого краю (або з будь-якої клітини середовища КА) КА, починають розповсюджуватися сигнали збудження по клітинах, що належать фону (фіг.1,б-є). Розповсюдження відбувається доти, поки сигнал збудження не досягне однієї з клітин, що належать контуру фігури (фіг.1,є). В цей момент формується сигнал на виході КА, який обнуляє усі збуджені клітини, що належать фону. Сигнал збудження починає розповсюджуватись по крайніх клітинах фігури (клітини, що належать контуру), формуючи на виході імпульсні сигнали (фіг.2). В результаті проходження сигналу збудження формується імпульсна послідовність, яка подана на фіг.3,а. Амплітуди імпульсів Ui (під час проходження сигналу збудження відповідної і-ї клітини) формуються згідно з аналізом клітин околиці даної клітини та зміни напрямку переходу сигналу збудження. По тривалості часу Ti судять про довжину сторони між відповідними клітинами, що належать сусіднім вершинам. Над отриманою імпульсною послідовністю здійснюють порогову обробку по амплітуді (фіг.3,б). Для надійності подання фігури, амплітуди імпульсів, які вищі за порогові амплітуди, зростають прямо пропорційно кількості попередніх імпульсів, амплітуди яких менші за порогові амплітуди. Амплітуда і-го імпульсу збільшується на величину кількості імпульсів, які розташовані у часовому інтервалі Ti 1 (фіг.3,а). Пристрій для розпізнавання плоских геометричних фігур працює в такий спосіб. Початкове зображення плоскої фігури зчитується БППЗ 1 і проектується на поле КА 2. Прикладом БППЗ 1 може бути сканер, фотокамера або паралельна матриця фотоперетворювачів. В результаті запису зображення у КА 2, клітини його, що належать фону, встановлюються у нульовий стан, а клітини, на які проектується зображення фігури переходять у одиничний стан. 7 Процес формування імпульсної послідовності КА 2 описано на фіг.1-3. Кожний сформований імпульсний сигнал в часі з відповідного виходу КА 2 подається на відповідний вхід двомірного диз'юнктора 3 і з його виходу подається на вхід БОІП 4, який здійснює усунення зайвих імпульсів (фіг.3). На виході БОІП 4 формується кінцева імпульсна послідовність, яка подається на вхід 8 БП 5 та вхід 9 БЕ 6. БЕ 6 починає пошук еталонних форм, які подаються на вхід 7 БП 5. БП 5 здійснює порівняння форм на входах 7, 8 і при співпадінні формує на виході 11 сигнал про геометрію фігури. Якщо еталонної форми у БЕ 6 не знайдено, то сигнал з виходу 11, що подається на вхід 10 БЕ 6, указує занесення форми з входу 9 до БЕ 6 та надання їй геометричного ідентифікатора. Інформація записується у кожну клітину 13 по інформаційному входу 14 (фіг.5), а стан клітини 13 визначається сигналом на виході 15. Оскільки спосіб використовується для аналізу бінарних зображень, то належність клітини 13 фону визначається нульовим сигналом на виході 15, а належність клітини 13 зображенню - одиничним сигналом. Клітина працює у двох режимах. 1. Режим належності клітини фону. 2. Режим належності клітини контуру зображення. Перший режим встановлюється надходженням нульового сигналу на інформаційний вхід 14 клітини 13 (фіг.7). На виході 15 ЕП 25 встановлюється значення логічного "0", який подається на інверсний вхід першого кон'юнктора 27, на виході якого з'являється сигнал логічної "1", якщо на другий його вхід подається одиничний сигнал з першого виходу 34 першого БАКО 22. Одиничний сигнал на першому виході 34 першого БАКО 22 формується тоді, коли на його одному з керуючих входів 18 присутній сигнал логічної "1" (сигнал збудження). Одиничний сигнал з виходу першого кон'юнктора 27, через диз'юнктор 31, подається на перший вхід БФС 24, який формує на виході 19 одиничний сигнал (сигнал збудження). Отже клітина фону переходить у збуджений стан і формує сигнал збудження на виході 19. Така клітина буде знаходитись у збудженому стані доти, поки на вході 17 не з'явиться сигнал логічної "1", який подається на другий вхід БФС 24 і переводить його у нульовий стан. На виході 19 клітини формується нульовий сигнал. Другий режим стану клітини (режим приналежності клітинам зображення) встановлюється одиничним сигналом з інформаційного входу 14. ЕП 25 встановлюється у стан логічної "1", яка формується на його виході 15 та подається на перший вхід другого кон'юнктора 28. Якщо на першому виході 33 першого БАКО 22 присутній одиничний сигнал, який подається на другий вхід другого кон'юнктора 28, то на виході другого кон'юнктора 28 формується сигнал логічної "1". З виходу другого кон'юнктора сигнал логічної "1" подається на вихід 20 обнуління для клітин фону, який подається також на входи 17 обнуління сусідніх клітин, що належать околиці. На першому виході 33 першого БАКО 22 одиничний сигнал формується тоді, коли 61795 8 хоча б на одному з його керуючих входів 18 присутній сигнал логічної одиниці, який надходить з виходів 19 сусідніх клітин околиці. Поява одиничного сигналу на виході 20 однієї з клітин, що належить зображенню, здійснює обнуління збуджених клітин, які належать фону. Якщо сигнал збудження подається на керуючі входи 18 першого БАКО 22 від клітин, що належать контуру зображення, то на його другому виході 35 формується одиничний сигнал, який подається на другий вхід третього кон'юнктора 29. На виході третього кон'юнктора 29 формується сигнал логічної одиниці, який подається на другий керуючий вхід 33 другого БАКО 23, на першому керуючому вході 32 якого також присутній сигнал логічної "1" з виходу 15 ЕП25. Наявність двох одиниць на керуючих входах 32,33 другого БАКО 23 дозволяє йому проводити аналіз станів клітин околиці, які належать контуру. Оскільки в околиці присутні дві клітини околиці, що належать контуру зображення, то одиничний сигнал на виході другого БАКО 23 формується тоді, коли сусідні клітини контуру не розташовані на одній прямій (по горизонталі, вертикалі та діагоналі). Якщо клітини розташовані на діагоналі, то на виході другого БАКО 23 присутній сигнал логічного "0". Якщо клітини околиці, що належать контуру, мають розташування, яке формує гострий кут, то формується імпульс з вищою амплітудою за одиничну. Алгоритм функціонування клітини має наступну послідовність кроків. 1. Визначення належності клітини зображенню або фону. 1.1.Клітина належить фону. Перехід до пункту 2. 1.2.Клітина належить контуру зображення. Перехід до пункту 7. 2. Визначення присутності сигналу збудження від клітин околиці. 2.1.Сигнал збудження не надійшов. Перехід до пункту 1. 2.2.Сигнал збудження надійшов. Перехід до пункту 3. 3. Перехід клітини у збуджений стан. На виході з'являється сигнал збудження. Перехід до пункту 4. 4. Визначення присутності сигналу обнуління. 4.1.Сигнал обнуління не надійшов. Перехід до пункту 4. 4.2.Сигнал обнуління надійшов. Перехід до пункту 5. 5. Обнуління клітини. Перехід клітини у нульовий стан. Перехід до пункту 6. 6. Кінець. 7. Визначення присутності сигналу збудження. 7.1.Сигнал збудження не надійшов. Перехід до пункту 7. 7.2. Сигнал збудження надійшов. Перехід до пункту 8. 8. Визначення клітини, від якої надійшов сигнал збудження. 8.1.Сигнал збудження надійшов від клітини фону. Перехід до пункту 9. 9 8.2.Сигнал збудження надійшов від клітини контуру зображення. Перехід до пункту 11. 9. Формування сигналу обнуління для клітин фону. Перехід до пункту 10. 10. Передача сигналу збудження клітині околиці, яка належить контуру і розташована першою по часовій стрілці від клітин фону. Перехід до пункту 6. 11. Передача сигналу збудження клітині околиці, яка належить контуру і є не збудженою. Перехід до пункту 12. 12. Визначення стану околиці. 12.1. Якщо клітини околиці, що належать контуру розташовані на одній прямій, то перехід до пункту 6. 12.2. Клітини околиці, що належать контуру, не розташовані на одній прямій, то перехід до пункту 13. 13.Формування імпульсу на виході клітини, амплітуда якого відповідає стану околиці. Перехід до пункту 6. 61795 10 Клітини, що розташовані на одній прямій мають наступне кодування (фіг.4). Кодування прямої по горизонталі 13i 1 j ;13i 1 j . Кодування прямої по вертикалі , ,   13i, j 1;13i, j 1 . Кодування прямої по діагоналях 13i 1, j 1;13i 1, j 1 або 13i 1, j 1;13i 1, j 1 . Даний спосіб розпізнавання плоских геометричних фігур дозволяє зменшити час на його реалізацію за рахунок використання КА, який дозволяє самостійно провести обробку зображення та сформувати відповідну послідовність імпульсів, по якій судять про фігуру. У способі не використовуються арифметичні операції для обчислення відповідних параметрів, оскільки у одній послідовності імпульсів мітиться інформація про основні параметри фігури. За рахунок подання зображення послідовністю імпульсів підвищується інформативність зображення та досягається можливість розпізнавати зображень, інваріантних до повороту та масштабу. 11 61795 12 13 61795 14 15 61795 16 17 Комп’ютерна верстка М. Ломалова 61795 Підписне 18 Тираж 23 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601