ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

Шевцов Дмитро Валерійович

УДК 681.325

МЕТОДИ І МОДЕЛІ ОБРОБКИ ДИСКРЕТНИХ ЗОБРАЖЕНЬ ЗНАКІВ

В АВТОМАТИЗОВАНИХ СИСТЕМАХ ПЕРЕРОБКИ ІНФОРМАЦІЇ

05.13.06 – Автоматизовані системи управління

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

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

кандидата технічних наук

Донецьк – 2003

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

Роботу виконано в Донецькому національному університеті Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, доцент

Мишко Сергій Васильович,

завідуючий кафедрою “Прикладна математика

і теорія систем управління” Донецького

національного університету, м. Донецьк.

Офіційні опоненти: доктор технічних наук, професор

Кожем’яко Володимир Прокопович,

Вінницький державний технічний

університет, м. Вінниця

доктор технічних наук, професор

Слєпцов Анатолій Ілліч,

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

м. Донецьк.

Провідна установа: Одеський національний політехнічний

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

України, м. Одеса.

Захист відбудеться “13” червня 2003 р. о 1400 годині на засіданні спеціалізованої вченої ради К 11.051.08 Донецького національного університету за адресою: 83055, м. Донецьк, пр. Театральний, 13, корп. 4, ауд. 408.

З дисертацією можна ознайомитись у бібліотеці Донецького національного університету за адресою: 83055, м. Донецьк, вул. Університетська, 24, гол. корп.

Автореферат розісланий “8” травня 2003 г.

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

вченої ради К 11.051.08

кандидат технічних наук, доцент ______________ Григор’єв С.В.

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

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

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

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

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

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

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

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

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

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

Зв’язок роботи з науковими планами, програмами, темами. Дисертаційну роботу виконано протягом 1999-2003 рр. відповідно до наукового напрямку кафедри “Прикладна математика і теорія систем управління” математичного факультету Донецького національного університету.

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

Досягнення даної мети визначає рішення наступних основних задач:

- дослідити сучасний стан проблеми автоматизованої обробки зображень;

- вивчити основні методи автоматизованої обробки зображень;

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

- обґрунтувати перспективні напрямки обробки зображень;

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

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

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

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

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

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

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

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

Наукова новизна отриманих результатів.

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

2. Розроблено метод автоматизованої обробки зображень знаків, заданих у дискретних представленнях атомарними елементами.

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

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

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

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

7. Розроблено метод проектування систем обробки зображень знаків, заданих у дискретних представленнях атомарними елементами.

Практичне значення отриманих результатів.

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

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

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

4. Розроблено систему обробки зображень блок-схем й імітаційні моделі систем обробки зображень об’єктів процесів розкрою листів металу і фарбування плоских деталей. Зроблено аналіз результатів їхнього функціонування, який показав, що використання запропонованих методу, моделей і алгоритмів для проектування систем обробки зображень дає можливість підвищити ефективність їхнього функціонування для найпростіших знаків планіметричних фігур (наприклад, відрізки) на 1,4 % та для знаків, які є комбінаціями відрізків (паралелограми, ромби і т.ін.) – до 91,3 %.

5. Результати дисертаційної роботи прийняті до використання Донецьким металургійним заводом, інститутом “АвтоматГірМаш ім. В.А. Антипова” з метою підвищення ефективності обробки зображень у межах автоматизованих систем переробки інформації.

6. Розроблені метод, моделі й алгоритми опізнавання знаків планіметричних фігур використані в навчальному процесі при розробці робочих програм і комплексних контрольних робіт з курсів “Системи технічного зору”, “Системи автоматичного розпізнавання”, “Моделювання зображень у системах технічного зору”, “Аксіоматика моделювання знаків на дискретних множинах”, “Автоматичні системи опізнавання знаків”, “Моделювання знаків у дискретних представленнях”, “Визначення знаків геометричних фігур у термінах властивостей дискретних множин” на кафедрі “Прикладна математика і теорія систем управління” Донецького національного університету.

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

Апробація результатів дисертації. Результати дисертаційної роботи були повідомлені, обговорені і схвалені на кафедрах “Прикладна математика і теорія систем управління” і “Технічна кібернетика” Донецького національного університету (1999-2003 рр.); доповідалися на першій Міжнародній науково-практичній конференції “Обчислювальна техніка в інформаційних і управляючих системах” (Приазовський державний технічний університет, м. Маріуполь, 2000 р.); першій і другій науково-технічних конференціях молодих вчених, аспірантів і студентів “Оптоелектронні й інформаційно-енергетичні технології” (Вінницький державний технічний університет, м. Вінниця, 2001-2002 рр.); науковій конференції Донецького національного університету за підсумками науково-дослідної роботи за період 1999-2000 рр. (Донецький національний університет, м. Донецьк, 2001 р.); Міжнародній конференції студентів і аспірантів з фундаментальних наук “Ломоносов–2002” (Московський державний університет ім. Ломоносова, м. Москва, 2002 р.); Міжнародній конференції з управління “Автоматика–2002” (Донецький національний технічний університет, м. Донецьк, 2002 р.); Міжнародній конференції з комп’ютерної графіки і машинного зору “ГрафіКон–2002” (Новгородський державний університет, м. Н. Новгород, 2002 р.).

Публікації. За результатами дисертації опубліковано 11 робіт. З них 7 – у наукових виданнях, 4 – у збірниках тез конференцій.

Структура й обсяг роботи. Дисертація складається з введення, чотирьох розділів і висновків, викладених на 123 сторінках машинописного тексту; містить 11 таблиць; 30 малюнків; список використаних літературних джерел з 130 найменувань на 12 сторінках і 3 додатки на 4 сторінках. Повний обсяг роботи – 139 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтована актуальність теми, сформульована мета дослідження і перераховані основні положення, що виносяться на захист.

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

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

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

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

- розробити метод, алгоритми і програми автоматичної обробки зображень знаків планіметричних фігур;

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

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

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

У другому розділі запропоновано й обґрунтовано нову концепцію представлення знаків об’єктів опізнавання в дискретних просторах, викладено основні теоретичні положення методу моделювання об’єктів опізнавання, що відбивають властивості підмножин атомарних елементів. Для генерації конструктивних визначень знаків, що опізнаються, у дискретних представленнях задано множину А атомарних елементів (АЕ). На множині А введено функцію :(a,b)N{0}, що кожній парі АЕ a,bА ставить у відповідність єдине ціле невід’ємне число (a,b) за правилом (a,b)=|ia-ib|+|ja-jb|. Число (a,b) трактується як відстань між АЕ a,b. Показано, що задовольняє усім властивостям метрики.

Відповідно до постановки задачі даного дослідження однією з його цілей є визначення знаків планіметричних фігур у термінах властивостей дискретних множин і, зокрема, відрізка прямої. З цією метою на множині АЕ визначені поняття: зв’язних АЕ як мінімальних елементів руху; зв'язних зв'язок; шляху між парою фіксованих АЕ як упорядкованої послідовності зв'язок; незамкнутих і замкнутих шляхів; об’єднання і перетинання шляхів. Запропоновано розрізняти чотири типи зв’язок: горизонтальні – s1; вертикальні – s2; два типи діагональних зв’язок – s3, s4. Розглянуто множину (a,b) усіляких шляхів Lk з aА в bА: (a,b)={Lk}, k[1,K0], де k[1,K0], Lk= =Lk(a,b)={(,)m}, h=, mhМ={1,2,3,4}, де mh визначає тип зв’язки з номером h. Показано, що будь-який замкнутий шлях можна представити у вигляді об’єднання кінцевого числа незамкнутих шляхів.

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

Визначення 1. Мірою 1 шляху Lk(a,b), k[1,K0], будемо називати число 1(Lk): 1(Lk)=, де =k(s)=((,)m)=(,), , А – АЕ, що утворять зв’язку sLk, mhM.

Визначення 2. Мірою 2 шляху Lk(a,b)(a,b), k[1,K0], будемо називати число 2(Lk): 2(Lk)=nk, де nk – кількість утворюючих його зв’язок sLk, mhM.

Показано, що 1, 2, задовольняють усім властивостям міри. На підставі визначення міри 1 розглянута множина шляхів 1(a,b)(a,b), 1(a,b)={Lk}, kK1[1,K0]: Lk1(a,b), 1(Lk)=(a,b).

Дана підмножина має важливу метричну властивість аналітичних відрізків прямої, що доводить наступна теорема, у якій (Lk) – множина АЕ, що складають шлях Lk.

Теорема 1. Для будь-якого Lk(a,b)1(a,b), kK1, і для будь-якого АЕ p(Lk) такого, що apb, вірно (a,p)+(p,b)=(a,b).

Із теореми 1 випливає, що шляхи Lk(a,b)1(a,b), kK1 мають таку властивість, яка у просторі Е2 властива відрізкам прямих: при виборі довільної точки відрізка нерівність трикутника вироджується в рівність. На множині АЕ ця властивість полягає в тому, що для довільного шляху Lk(a,b)1(a,b) і АЕ p(Lk) сума відстаней від a до p і від p до b дорівнює відстані від a до b в обраній метриці.

Визначено критерій, що дозволяє установити приналежність деякого шляху Lk(a,b)(a,b), k[1,K0], множині 1(a,b). Для цього доведена теорема 2.

Теорема 2. Для того, щоб шлях Lk(a,b), k[1,K0]: (Lk)={d,d,d,d}, де d – кількість зв’язок s у шляху Lk, mhM, належав множині 1(a,b), необхідно і достатньо, щоб dd=0, тобто щоб він не містив у собі діагональних зв’язок двох типів одночасно.

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

На підставі визначення міри 2 для наступного визначення дискретного відрізка прямої в термінах властивостей множини АЕ введене поняття найкоротшого шляху.

Визначення 3. Шлях L(a,b) такий, що 2(L)=2(Lk), будемо називати найкоротшим шляхом від a до b (з a в b).

Із визначення 3 випливає, що найкоротші шляхи містять мінімальну кількість зв’язок на множині шляхів 1(a,b). Це визначає доцільність моделювання аналітичного відрізка прямої на множині найкоротших шляхів. Позначимо 2(a,b)1(a,b): 2(a,b)={Lk}, kK2K1 – множину найкоротших шляхів з a в b. Дана множина обмежує множину шляхів, яка містить дискретні аналоги аналітично завданих в усюди щільних просторах відрізків, що якісно відіб’ється на процедурах їхнього опізнавання в межах розглянутої системи і підвищить їхню швидкодію.

Для автоматичного виявлення і генерації найкоротших шляхів сформульовано і доведено теорему 3 – критерій найкоротшого шляху.

Теорема 3. Для того, щоб шлях Lk(a,b)1(a,b), kK1, був найкоротшим, необхідно і достатньо, щоб nk=max{|ia-ib|,|ja-jb|}, (Lk)=min{|ia-ib|,|ja-jb|}, де nk=2(Lk); (Lk) – кількість діагональних зв’язок у шляху Lk1(a,b).

Для визначення відрізка прямої в термінах властивостей множини АЕ вивчено властивості множини найкоротших шляхів. Із цією метою введено до розгляду підмножину D(a,b)А, D(a,b)=(Lk). Вона містить усі АЕ, що складають найкоротші шляхи з a в b. Його конфігурація визначається розташуванням початкового і кінцевого пунктів шляхів множини 2(a,b). Множина D містить у собі ті АЕ, що, зокрема, утворюють відрізок прямої в дискретних представленнях.

Проведені міркування і вивчені властивості шляхів із 1(a,b), найкоротших шляхів, сформульовані й доведені ствердження і критерії, достатні для генерації визначення відрізка прямої в термінах властивостей множини АЕ, що є аналогом відрізка, аналітично заданого в усюди щільному просторі. Викладені в розд. 2 основні теоретичні положення моделювання знаків у дискретних представленнях складають основу наступного визначення знаків планіметричних фігур у термінах властивостей множини атомарних елементів.

У третьому розділі на підставі введених визначень і вивчених структурних властивостей множини D атомарних елементів, що складають найкоротші шляхи між парою фіксованих АЕ, подане визначення D-відрізка прямої в термінах властивостей множини АЕ як аналога аналітично заданого відрізку в усюди щільному просторі. Нехай a,bА – довільні не зв’язані АЕ, для яких iaib, jajb, |ia-ib||ja-jb|, і нехай n1=|ja-jb|+1, n2=|ia-ib|+1, =.

Визначення 4. Шлях Lk2(a,b), kK2, будемо називати D-відрізком прямої чи просто D-відрізком між АЕ a,bА, якщо при n11, n21, n1n2, h(Lk), h[2,nk], виконано:

ih=arg|-|, jh=, де j1=min{ja,jb}+1, j2=max{ja,jb}-1, якщо n1>n2;

jh=arg|-|, ih=, де i1=min{ia,ib}+1, i2=max{ia,ib}-1, якщо n1n2.

У випадку, якщо n1=1, n21, n1n2, D-відрізком між АЕ a,bА будемо називати шлях L(a,b)={s}; якщо n11, n2=1, n1n2, – шлях L(a,b)= ={s}; якщо n11, n21, n1=n2 – шлях L(a,b)={s} при =1, чи L(a,b)={s} при =-1.

Таке визначення конструктивне і дозволяє реалізувати опізнавання знаків відрізків прямих, яке зводиться до перевірки виконання зазначених у ньому умов для довільно заданої множини АЕ. Крім того, дане визначення може бути використане для генерації знаків D-відрізків між довільно заданими АЕ a,bА, що дає можливість оцінювати його несуперечність концептам знаків відрізків прямих, що опізнаються, та їх прообразів.

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

Визначення 5. D-еліпсом із центром в АЕ QА і півосями, міри яких відповідно дорівнюють r1,r2N, будемо називати замкнутий шлях LQ(a,f)(a,f), який можна представити у вигляді LQ=Lo1(a,b)Lo2(b,c)Lo3(c,d)Lo4(d,a), де Lo1(a,b), Lo2(b,c), Lo3(c,d) і Lo4(d,a) – шляхи відповідно першої, другої, третьої і четвертої чвертей.

Визначення 6. Замкнутий шлях LQ(a,f)(a,f), будемо називати D-окружністю з центром у АЕ QА і радіусом rN, якщо він є D-еліпсом, значення перших і других мір усіх півосей якого (горизонтальних і вертикальних) однакові й дорівнюють r.

Визначення 7. Довільний незамкнутий шлях Lk(e,f)(e,f) будемо називати D-дугою, якщо існує деяка D-окружність чи D-еліпс LQ(a,f): (Lk)(LQ), (Lk)(LQ)=(Lk).

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

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

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

Визначення 8. Множину TDА будемо називати D-трикутником, якщо вона може бути представлена у вигляді TD=(ab)(bc)(ca) так, що (ab)(bc)=b, (ab)(ca)=a, (bc)(ca)=c, де ab, bc, ca – D-відрізки, a,b,cA.

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

Визначення 9. Множину AА, A={(h,h+1)m}, mhM, будемо називати опуклим знаком, якщо він є замкнутим шляхом і виконано h(В), h= sign(- -){C1,0}; sign(-){C1,0}, де значення C1 для усіх h(В) ?остійне і дорівнює 1 чи -1.

У розділі визначені D-чотирикутники і правильні опуклі D-багатокутники в термінах властивостей множини атомарних елементів.

Визначення 10. Опуклий знак CDА будемо називати D-чотирикутником, якщо він може бути представлений у вигляді СD=(ab)(bc)(cd)(da), де ab, bc, cd і da – D-відрізки, і виконані умови:

1) (ab)(da)=а, (ab)(bc)=b;

2) (bc)(cd)=c, (cd)(da)=d;

3) жодна з усіх можливих пар D-відрізків ab, bc, cd, da не утворює перетинання.

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

У визначеннях 4-10 відсутнє використання абстрактних математичних категорій, заданих в усюди щільних просторах. Їхній конструктивізм використаний для автоматичної генерації знаків і їхнього автоматичного опізнавання системою обробки зображень. Запропоновані визначення дозволяють розробити метод автоматичного опізнавання знаків планіметричних фігур без апріорного завдання множини ознак, еталонів, мір близькості, граничних констант, не застосовуючи до моделювання зображень абстрактних математичних категорій, заданих в усюди щільних просторах.

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

Рис. 1. Функціональна схема методу автоматичного опізнавання знаків

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

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

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

У висновках сформульовані основні наукові результати і практична значимість виконаної роботи.

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

ВИСНОВКИ

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

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

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

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

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

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

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

7. Результати роботи прийнято до використання Донецьким металургійним заводом, інститутом “АвтоматГірМаш ім. В.А. Антипова” з метою розробки високоефективних автоматизованих систем обробки зображень.

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

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

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мышко С.В., Шевцов Д.В. Определение кратчайших путей на множестве атомарных элементов в системах автоматического опознавания изображений // Вісник Донецького національного університету. Серія А: Природничі науки. – Донецьк: Вид-во ДонНУ. – 2001. – №2. – С. 334-341.

2. Мышко С.В., Шевцов Д.В. К определению отрезка прямой на дискретном множестве атомарных элементов // Научные труды Донецкого национального технического университета. Серия: Информатика, кибернетика и вычислительная техника (ИКВТ-2002). Выпуск 39. – Донецк: Изд-во ДонНТУ. – 2002. – С. 154-159.

3. Григорьев С.В., Мышко С.В., Шевцов Д.В. Применение путей при проектировании информационных систем обработки зрительных образов // Вісник Донецького національного університету. Серія А: Природничі науки. – Донецьк: Вид-во ДонНУ. – 2002. – №2. – C. 375-380.

4. Мышко С.В., Шевцов Д.В. Автоматическая декомпозиция изображений при их опознавании в системах технического зрения роботов // Наукові праці Донецького державного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 38. – Донецьк: РВА ДонДТУ. – 2002. – С. 216-222.

5. Шевцов Д.В. Система автоматического опознавания знаков геометрических фигур // Труды 12-й Международной конференции по компьютерной графике и машинному зрению “ГрафиКон – 2002”. – Н. Новгород: Изд-во Новгород. ун-та. 2002. – С. 262-267.

6. Мышко С.В., Шевцов Д.В., Шевчук Е.В. К вопросу об опознавании знаков в дискретных представлениях // Сборник докладов Международной научно-практической конференции “Вычислительная техника в информационных и управляющих системах”. – Мариуполь: Изд-во ПГТУ. – 2000. – С. 77–78.

7. Мышко С.В., Шевцов Д.В. Конструктивное определение прямой в терминах свойств множеств атомарных элементов // Материалы университетской научно-технической конференции по итогам НИР 1999-2000 гг. Выпуск: Естественные науки. Физические и компьютерные науки. – Донецк, Изд-во ДонНУ. – 2001. – С. 99-103.

8. Мышко С.В., Шевцов Д.В. Определение прямой на множестве атомарных элементов // Сборник тезисов докладов Международной научно-технической конференции молодых ученых, аспирантов и студентов “Оптоэлектронные информационно-энергетические технологии”. – Винница: Изд-во ВГТУ. – 2001. – С. 49.

9. Шевцов Д.В. Опознавание знаков в терминах свойств дискретных множеств как альтернатива задачи распознавания в системах технического зрения роботов // Матеріали Міжнародної конференції з управління “Автоматика – 2002”: В 2 т. – Донецьк: Вид-во ДонНТУ. – 2002. – Т.2. – С. 170-171.

10. Шевцов Д.В. Определение знаков геометрических фигур на дискретных множествах атомарных элементов в системах автоматического опознавания // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам “Ломоносов–2002”, секция “Вычислительная математика и кибернетика”. – М.: Издат. отдел факультета ВМиК МГУ. – 2002. – С. 19.

11. Шевцов Д.В. Опознавание знаков геометрических фигур, заданных в терминах свойств дискретных множеств // Сборник тезисов докладов второй Международной научно-технической конференции студентов, аспирантов и молодых ученых “Оптоэлектронные информационно-энергетические технологии – 2002”. – Винница: “УНИВЕРСУМ-Винница”. – 2002. – С. 23.

Особистий внесок автора в публікаціях: [1] – визначення найкоротшого шляху; [2] – вивчення властивостей і структури множини найкоротших шляхів; [3] – визначення і дослідження шляхів, що мають метричні властивості аналітично заданих відрізків прямих; [4-6] – розробка методу декомпозиції і опізнавання знаків у дискретних представленнях; [7, 8] – визначення D-відрізка прямої на множині атомарних елементів.

АНОТАЦІЯ

Шевцов Д.В. Методи і моделі обробки дискретних зображень знаків в автоматизованих системах переробки інформації. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – “Автоматизовані системи управління і прогресивні інформаційні технології”. – Донецький національний університет, Донецьк, 2003 р.

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

Ключові слова: знак, система обробки зображень, розпізнавання зображень, опізнавання знаків, атомарний елемент, шлях, найкоротший шлях.

АННОТАЦИЯ

Шевцов Д.В. Методы и модели обработки дискретных изображений знаков в автоматизированных системах переработки информации. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – “Автоматизированные системы управления и прогрессивные информационные технологии”. – Донецкий национальный университет, Донецк, 2003 г.

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

Ключевые слова: знак, система обработки изображений, распознавание изображений, опознавание знаков, атомарный элемент, путь, кратчайший путь.

ANNOTATION

Shevtsov D.V. Methods and models of processing of the discrete images of marks in the automated systems of the information processing. – Manuscript.

The dissertation on competition of a scientific degree of the candidate of engineering science on a speciality 05.13.06 – "Тhe automated control systems and progressive information technologies". – Donetsk national university, Donetsk, 2003.

The up to date condition of the problem of image automated processing is investigated in the dissertation, the urgency of this problem is proved. The perspective methods of the image processing are proved. The aim of research is put. The basic theoretical rules of the offered methods of mark modeling in discrete representations are stated. The discrete set of atomic elements is determined and its metric properties are investigated. The concept of a way on a set of atomic elements as a basic object in mark modeling is introduced. The shortest paths their properties and structure are studied. The models of plane figure marks in discrete representations by atomic elements are offered on the basis of the theoretical concepts of mark modeling. The segment, the circumference, ellipse and an arc are determined in the terms of properties of atomic element set as paths on a set of atomic elements. The modeling of a discrete segment