.

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

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 2352
Скачать документ

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ

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

АДАМЕНКО ВІРА АНАТОЛІЇВНА

УДК 519.7; 519.81;
007.001.362; 681.327.12.001.362

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

01.05.04— системний аналіз та теорія оптимальних рішень

АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук

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

Робота виконана в Харківському державному технічному університеті
радіоелектроніки, Міністерство освіти України

Науковий керівник— доктор технічних наук, професор Тевяшев Андрій Дмитрович, завідуючий кафедрою Прикладної математики Харківського державного технічного університету радіоелектроніки.

Офіційні опоненти:
—доктор технічних наук, доцент Любчик Леонід Михайлович, професор кафедри системного аналізу і управління Харківського державного політехнічного університету
—кандидат технічних наук, старший науковий співробітник Бобух Анатолій Олексійович, доцент каф. ТХС і автоматичного управління Харківської державної академії міського господарства

Провідна установа: Державний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, кафедра конструювання та виробництва радіоапаратури, Міністерство освіти України, м.Харків

Захист відбудеться “25” березня 1999 р. о 13.10 год. на засіданні
спеціалізованої вченої ради Д 64.052.01 в Харківському державному технічному університеті радіоелектроніки за адресою:
310726, м.Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського державного технічного університету радіоелектроніки за адресою:
310726, м.Харків, пр. Леніна, 14.

Автореферат розісланий “_____” __________ 1999 р.

Вчений секретар
спеціалізованої вченої ради
професор __________________ Левикін В.М.

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

Актуальність теми. За останні кілька років у зв’язку з масовою появою достатньо потужної та відносно недорогої техніки: ПЕОМ, автоматичних скануючих пристроїв і т.д. з’явилась можливість з високим дозволянням і великою кількістю кольорів сканувати зображення і, у зв’язку з цим, з’явилась можливість автоматичного вводу у ПЕОМ різних зображень графічних документів (ГД) з нанесеними на них кривими, графіками залежностей, які раніше призначалися для ручної обробки людиною. Після автоматичного вводу графічного зображення документу у ПЕОМ (після сканування документу), одержане растрове зображення (РЗ) необхідно обробити, а саме— розпізнати криву що знаходиться на ньому, тобто одержати табличну форму графіку однозначної функції, що відповідає розпізнаваної кривої. Таким чином, у теперішній час з’явилась необхідність вирішати велику кількість задач, пов’язаних з розпізнаванням образів на кольорових растрових зображеннях (КРЗ) ГД, а саме— з розпізнаванням кривих на КРЗ ГД.
Розпізнавання кривих на КРЗ є необхідною вимогою для автоматизації процесу рішення задач, що з’являються у різних галузях народного господарства України: у газовій промисловості, у медицині, для комп’ютерної обробки результатів наукових експериментів і т.д. Одною з найважливіших задач, що вирішуються у газовій промисловості на Україні та інших країнах СНД, є обчислення витрат газу за добу (місяць, рік і т.д.) по кожному споживачу, групі споживачів, регіону і усій країні. Витрати газу обчислюються в основному на основі непрямих вимірювань температури, тиску і перепаду тиску газу на соплі Вентури протягом доби, що реєструються самописними приборами на кругових діаграмах. Кругова діаграма (КД) являє собою ГД з кривою (температури, перепаду або тиску газу), що записується на нього самописними вимірювачами протягом доби. У теперішній час обробка КД проводиться людиною вручну пропорційними і кореневими планіметрами на спеціальному круглому столику що крутиться. Така обробка діаграм потребує не тільки великих затрат часу, але і погрішність обчислень виходить досить велика. Таким чином, обробка діаграм здійснюється неефективними методами, які припускають активну участь людини. У зв’язку з цим з’явилась необхідність в автоматичній обробці КД. Ідея створення нової технології автоматичної обробки КД полягає у наступному: КД закладаються у сканер і скануються. У результаті сканування створюються растрові зображення КД у вигляді PCX-файлів. Ці зображення надходять до автоматизованої системи обробки кольорових діаграм (АСОКД), яка здійснює розпізнавання кривих на растрових зображеннях КД для одержання таблиць залежностей “вимірювана величина—час”. Задача автоматичного одержання таблиць залежностей “вимірювана величина—час” на КД являє собою задачу розпізнавання образів, тому що необхідно “виділити” точки кривої серед усіх інших точок КРЗ. Задача ускладнюється тим, що окрім точок кривої, окружностей і дуг часу, КД може містити багато перешкод: плями, дряпини, випадкові обриви кривої і т.д. Тому проблема розпізнавання кривих на КРЗ у теперішній час є надзвичайно актуальною як у науковому, так і в практичному плані.
Зв’язок роботи з науковими програмами, планами, темами. Дослідження, отримані у дисертаційній роботі, тісно пов’язані з виконанням держбюджетних і держдоговірних НДДКР кафедри ПМ за участю здобувача: “Інтелектуальна система підтримки прийняття рішень в імунологічних дослідженнях” (№ 469—0197U008896), “Інформаційні ресурсозберігаючі технології добування, підготовки, транспорту та розподілу нафти і природного газу” (№ 496—0197U014153), “Аналіз газотранспортної мережі дочірнього підприємства “Харьковтрансгаз” та впровадження інформаційно-аналітичної системи центральної диспетчерської служби згідно єдиної системи оперативного диспетчерського управління АТ “Укргазпром”” (№ 780131—0198U004447).
Мета та задачі дослідження. Метою дисертаційної роботи є розробка та дослідження ефективного методу рішення задач розпізнавання кривих на КРЗ графічних документів. Це можуть бути кругові діаграми, стрічкові діаграми або інший вид графічних документів, на котрих якимось чином була нанесена крива, яку необхідно розпізнати.
Задачами досліджень є:
1. Постановка задачі розпізнавання кривих на кольорових растрових зображеннях графічних документів.
2. Розробка ефективного методу рішення задач розпізнавання кривих на кольорових растрових зображеннях графічних документів.
3. Деталізація розробленого методу для розпізнавання кривих на кольорових растрових зображеннях кругових діаграм самописних приборів, що використовуються у газовій промисловості для обчислення витрат газу.
4. Програмна реалізація розробленого методу розпізнавання кривих на КРЗ кругових діаграм у вигляді автоматизованої системи.
5. Дослідження залежності ефективності розробленого методу від зміни статистичних властивостей перешкод на реальних даних і за допомогою імітаційного моделювання.
Наукова новизна одержаних результатів.
1. Сформульовано новий клас задач розпізнавання кривих на кольорових растрових зображеннях графічних документів, рішення яких дозволяє одержати табличну форму графіку однозначної функції, що відповідає розпізнаваної кривої.
2. Розроблено ефективний метод рішення задач розпізнавання кривих на кольорових растрових зображеннях графічних документів, який відрізняється від відомих тим , що ураховує таку специфіку класу вирішуємих задач: криві являють собою графіки однозначної функції у деякій системі координат, і, в той же час, криві— це реалізації одного і того ж випадкового процесу з неперервним часом і незалежними приростами, причому, статистичні властивості цього процесу наперед невідомі, але постійні або змінюються поступово від одного графічного документу до другого для усіх кривих одного потоку кольорових растрових зображень графічних документів.
Реалізація розробленого методу основана на виконанні таких етапів:
1) Побудова аналітичної моделі системи координат, у якої знаходиться розпізнавана крива, для графічного документу.
2) Виділення системи ланок (припущених фрагментів кривої).
3) Знаходження якостей стиковки між кожною парою ланок.
4) Знаходження маршруту з максимальною якістю шляхом рішення задачі пошуку оптимальної путі на графі.
Показано, що етапи 3—4 є інваріантними до виду графічних документів, а етапи 1—2 потребують розробки конкретних алгоритмів для кожного виду графічних документів. У дисертаційній роботі була проведена конкретизація етапів 1—2 відповідно до кругових діаграм самописних приборів, що використовуються у газовій промисловості для обчислення витрат газу.
Показано, що система, побудована за розробленим методом, може самонавчатися і адаптуватися до статистичних властивостей кривих потоку кольорових растрових зображень графічних документів.
3. Розроблений у дисертаційній роботі метод програмно реалізовано у вигляді автоматизованої системи обробки кольорових діаграм у середовищі Windows з використанням інструментальних засобів Borland Pascal 7.0 і Delphi.
4. Проведені дослідження ефективності розробленого методу за результатами обробки реальних кругових діаграм і за допомогою імітаційного моделювання, яке дозволило промоделювати такі ситуації, які на реальних зображеннях КД зустрічаються рідко, і тому оцінка ефективності розробленого методу була проведена більш повно. Проведені дослідження підтвердили високу ефективність розробленого методу.
Практична цінність отриманих результатів.
Отримані теоретичні результати реалізовані у АСОКД, яка використовується у науково-дослідницькому учбовому центрі обліку газу і метрології газовимірювань ДП НДПІАСУтрансгаз у вигляді прикладної системи для навчання і підвищення кваліфікації інженерів по обліку витрат газу, спеціалістів КВПіА і метрологів “Укргазпрому” і “Укргазу”. Крім того, АСОКД була передана в опитну експлуатацію у ВАТ “Харьковгоргаз” для автоматичної обробки поперед відсканованих зображень кругових діаграм ДП і ДК самописних вимірювачів витрат природного газу, що установлені на газовимірювальних станціях.
Розроблений метод можна використовувати не тільки у газовій промисловості, але і у багатьох інших галузях народного господарства України (наприклад, у медицині, для комп’ютерної обробки результатів наукових експериментів і т.д.).
Особистий внесок здобувача. Усі наукові і практичні результати отримані автором особисто. У роботі [1] автором розглянута проблема розпізнавання графіків залежностей на кольорових растрових зображеннях кругових діаграм і наведені основні етапи алгоритму виділення системи ланок для кругових діаграм. Роботи [2—4] виконані здобувачем сумісно із співавторами. У роботі [2] здобувачем отримані рівняння переходу із прямокутної системи координат, пов’язаної з растровим зображенням КД, у систему координат “вимірювана величина—час” і назад для кожної точки, що забезпечують інваріантність цього переходу до масштабу растрового зображення. Побудову аналітичної моделі було здійснено для випадку, коли час на діаграмі відраховувався за годинною стрілкою. У роботі [3] здобувачем розглянута проблема розпізнавання графіків залежностей на растрових зображеннях кругових діаграм. У роботі [4] здобувачем наведені результати дисертаційної роботи, що реалізовані у вигляді інформаційно-аналітичної системи обробки кольорових діаграм для забезпечення ефективного обліку витрат газу.
Апробація результатів дисертації. Основні результати проведених досліджень доповідались та обговорювались на: II Міжнародній конференції “Теорія і техніка передачі, прийому та обробки інформації” (Туапсе, 1996 г.); III Міжнародній конференції “Теорія і техніка передачі, прийому та обробки інформації” (Туапсе, 1997 г.); Міжрегіональному науково-практичному семінарі по обміну досвідом “Інформаційні і енергозберігаючі технології для трубопровідних систем енергетики” (м. Яремча, Івано-Франківськ— 1997).
Публікації. Основні результати дисертаційної роботи опубліковані у 4 наукових статтях [1, 2, 3, 4], 3 тезах доповідей [5, 6, 7], 1 звіті по НДР.
Структура та обсяг дисертаційної роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних літературних джерел (75 найменувань) та двох додатків. Обсяг дисертації без додатків 151 с. Загальний обсяг роботи становить 181 с. Загальна кількість рисунків 78, таблиць— 3.

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

У вступі обгрунтовано актуальність теми дисертаційної роботи, сформульована мета та задачі досліджень, наведені відомості щодо наукової новизни, практичної цінності та впровадження результатів роботи, публікацій автора та апробації роботи.
У першому розділі проведено огляд стану проблеми розпізнавання образів. У загальних рисах розглянуто два основних підходи, що існують у теорії розпізнавання образів, а саме: статистичний і синтаксичний (структурно-лінгвістичний) підходи. При цьому відмічається, що теорія розпізнавання образів як наукова дисципліна почала розвиватися ще з середини 50-х років. І хоча у 1987—1989 роках вже існувала достатньо струнка теорія розпізнавання образів, однак, між сильно розвиненою теорією розпізнавання образів і практикою розпізнавання зображень існував достатньо помітний розрив, а теорії розпізнавання зображень взагалі не існувало. Це все приводило до того, що розробники конкретних прикладних систем змушені були іти кожен своїм шляхом, при цьому вони багато у чому дублювали один одного і не мали загальних концепцій. Починаючи приблизно з початку 90-х років почала масово з’являтися достатньо потужна і відносно недорога нова техніка: ЕОМ, автоматичні скануючі пристрої (сканери). Крім того, за останні кілька років значно виріс об’єм пам’яті на ЕОМ. Тому з’явилась можливість з високим дозволянням і великою кількістю кольорів сканувати зображення і, у зв’язку з цим, з’явилась необхідність вирішати задачі розпізнавання образів на РЗ. Наприклад, у 90-их роках практикою була висунута проблема обробки структурно-складних семантично насичених ГД (конструкторської документації, різного типу карт, ескізів, фотошаблонів, графічних матеріалів медичної діагностики та ін.). Для рішення таких задач використовувались структурно-лінгвістичні методи розпізнавання. Крім того, за останній час з’явилося достатньо багато програмних продуктів, у яких вирішуються задачі розпізнавання образів на РЗ (наприклад, найкрупніші серед таких програмних продуктів— CorelDRAW, FineReader та ін.). У теперішній час існує достатньо багато робот по розпізнаванню печатних символів, рукописного тексту, рукописних цифр, китайських ієрогліфів і т.п. Таким чином, у цьому розділі робиться висновок, що за останні 5—8 років з’явилася можливість автоматизації рішення широкого кругу задач, пов’язаних з розпізнаванням образів на КРЗ ГД, а саме— з розпізнаванням кривих на КРЗ ГД.
У другому розділі розроблено метод розпізнавання кривих на КРЗ ГД.
У підрозділі 2.1 уводяться визначення кольорового растрового зображення, кривої, цифрової моделі кривої і формулюється постановка задачі розпізнавання кривої на КРЗ.
Нехай — система координат (с.к.), пов’язана з РЗ ГД.
Крива (К)— яка-небудь плоска безперервна лінія певного кольору, яка у деякій системі координат являє собою графік однозначної функції , де — область визначення функції , що являє собою відрізок, тобто . Крім того, функція подається як випадковий процес з безперервним часом, де часом служить , і незалежними приростами.
Цифрова модель кривої (ЦМК) у с.к. B— це будь-яка конечна численність точок виду
, .
Ступінь відповідності ЦМК Kr кривої K задається функцією якості цифрової моделі кривої . Чим менше значення функції , тим більше ЦМК Kr відповідає кривої K. Наприклад, за можна вибрати максимальне відхилення кусочно-лінійної апроксимації, що побудована по точкам із Kr, від функції , що відповідає кривої K:
,

Постановка задачі. Дано: потік кольорових растрових зображень графічних документів, які містять однотипні криві у деякій системі координат (КРЗ одержується шляхом сканування).
Для кожного графічного документу необхідно вирішити задачу розпізнавання кривої на КРЗ виду:
, (1)
при таких обмеженнях:
1. , тобто задано обмеження на розмірність ЦМК;
2. Крива K невідома, але на неї накладаються обмеження, які важко формалізувати:
2.1. Існує інформація про криву у вигляді КРЗ.
2.2. Відомо основний базовий колір кривих даного потоку КРЗ графічних документів.
2.3. Криві являють собою реалізації одного і того ж випадкового процесу з неперервним часом і незалежними приростами. Статистичні властивості цього процесу наперед невідомі, але постійні або змінюються поступово від одного ГД до другого для усіх кривих одного потоку.
2.4. Крім точок кривої, на КРЗ можуть бути інші об’єкти (наприклад, сітка, надписи, інші криві і т.п.), а також багато перешкод: плями, дряпини (того ж кольору, що і крива), випадкові обриви кривої і т.п., що ускладнює задачу розпізнавання. Колір кожного пікселу кривої може відхилятися від основного базового кольору.
Як видно із (1), результатом рішення задачі розпізнавання кривої на КРЗ є оптимальна ЦМК , тобто таблична форма графіку однозначної функції, що відповідає розпізнаваної кривої.
Визначення с.к. B, у якій подана розпізнавана крива, є окремою задачею. Визначити с.к. B означає задати тип с.к. B (наприклад, прямокутна, полярна і т.д.) та її положення на КРЗ ГД відносно фіксованої прямокутної с.к. A, пов’язаної з КРЗ (наприклад, зміщення початку відліку с.к. B, кут повороту с.к. B). Для визначення с.к. B достатньо побудувати формули переходу із прямокутної с.к. A у с.к. B і назад для кожної точки:
(2)
(3)
де — координати довільної точки K у с.к. A; — координати тієї ж самої точки K у с.к. B; — параметри, що характеризують тип і положення с.к. B відносно с.к. A. Формули (2)—(3) називаються аналітичною моделлю с.к. B для ГД, тобто під аналітичною моделлю системи координат B для ГД називаються формули переходу із прямокутної с.к. A, пов’язаної з РЗ графічного документу, у с.к. B, у якій подана розпізнавана крива, і назад для кожної точки, що забезпечують інваріантність цього переходу до масштабу РЗ. Ці формули переходу повинні бути однаковими для усіх ГД одного потоку з точністю до значень параметрів , тобто формули (2)—(3) будуються один раз для усіх ГД одного потоку, а параметри можуть бути або однаковими (що на практиці можна забезпечити, наприклад, однаково закладаючи у сканер усі ГД одного потоку), або можуть змінюватися від одного ГД потоку до другого. В цьому випадку необхідно рішати ще одну задачу розпізнавання образів, а саме: необхідно розпізнавати початок відліку с.к. B і її зміщення відносно с.к. A, що виходить за рамки дисертаційної роботи.
У підрозділі 2.2 розроблено метод рішення сформульованого класу задач.
Суть запропонованого методу полягає у побудові конкретних математичних моделей для формалізації початкової напівформалізованої задачі (1) і подання її у вигляді таких простіших підзадач:
1. Задача виділення системи ланок (припущених фрагментів оптимальної ЦМК).
2. Задача максимізації імовірності того, що маршрут (ланцюжок ланок) є оптимальним. Ця задача розпадається на дві задачі: задачу знаходження якостей стиковки між кожною парою ланок і задачу знаходження маршруту з максимальною якістю.
Загальна схема запропонованого методу складається з таких етапів:
1. Побудова аналітичної моделі системи координат B, у якій подана розпізнавана крива, для графічного документу.
2. Виділення системи ланок (припущених фрагментів оптимальної ЦМК).
3. Знаходження якостей стиковки між кожною парою ланок.
4. Знаходження маршруту з максимальною якістю шляхом рішення задачі пошуку оптимальної путі на графі.
Ланка Z— це численність точок, яка міститься в оптимальної ЦМК , або не пересікається з нею, тобто . Ланка являє собою припущений фрагмент оптимальної ЦМК. У дисертаційній роботі наведені визначення начала ланки і кінця ланки . На численності всіляких ланок задано симетричне іррефлексивне відношення: “не перекриваються”. У роботі дається визначення “ланки і не перекриваються” (позначається ).
Системою ланок називається численність ланок, у якій існує хоча б одна така підчисленність ланок , які не перекриваються, причому об’єднання ланок із збігається з оптимальною ЦМК, і в входять так звані “перша” ( ) і “остання” ( ) фіктивні ланки, тобто
.
Маршрут у системі ланок — це численність ланок із , причому ці ланки не перекриваються, тобто
.
— це ланки, які належать будь-якому маршруту і будь-якої системи ланок. — ланки, які містять одну точку у с.к. B.
Численність всіляких маршрутів у системі ланок позначується , тобто .
Маршрут у системі ланок називається оптимальним, якщо йому належать усі ланки, що містяться в оптимальної ЦМК, і тільки вони, тобто якщо предикат приймає значення істини, то маршрут оптимальний.
На системі ланок задано асиметричне іррефлексивне відношення: “є продовженням у заданому маршруті”. У роботі дається визначення “ланка є продовженням ланки у заданому маршруті ” (позначається ).
Хай задана система ланок . Оптимальна ЦМК і сама крива К невідомі, але відомо, що крива К являє собою реалізацію випадкового процесу з неперервним часом і незалежними приростами. У загальному випадку оптимальних ЦМК (і, відповідно, оптимальних маршрутів) для одної кривої К може вийти декілька. Оскільки крива К випадкова, то оптимальна ЦМК і, відповідно, оптимальний маршрут, також будуть випадковими. Ідея запропонованого методу полягає у тому, що вводиться поняття якості маршруту і проводиться пошук маршруту з максимальною якістю. Якість маршруту являє собою імовірність того, що маршрут є оптимальний, тобто .
Таким чином, від постановки задачі виду (1) здійснено перехід до задачі максимізації імовірності того, що маршрут є оптимальний у заданій системі ланок:
; (4)
і задачі виділення системи ланок .
Для рішення задачі (4) визначається якість маршруту :

де умова означає, що ланка є продовженням ланки в оптимальному маршруті:
,
тобто на системі ланок задано відношення “є продовженням в оптимальному маршруті”, обумовлене постановкою задачі (1), а також припущенням, що система ланок задана, а крива, оптимальна ЦМК і оптимальний маршрут невідомі.
Ланка належить оптимальному маршруту (позначається ), якщо .
У дисертаційній роботі показано, що якість маршруту визначається через добуток якостей стиковки ланок із цього маршруту

,
де — якість стиковки ланки з ланкою .
Якість стиковки ланки з ланкою позначається і являє собою імовірність того, що ланка є продовженням ланки в оптимальному маршруті при умові, що належить оптимальному маршруту, тобто . Після знаходження усіх якостей стиковки між усіма парами ланок, можна скласти всілякі маршрути і для кожного маршруту знайти якість маршруту. У дисертаційній роботі показано, що задача (4) зводиться до задачі пошуку оптимальної путі на графі:
. (5)
Система ланок подається у вигляді графу, де вершинами графу є ланки, а дугами— всілякі стиковки ланок. Кожній дузі ставиться у відповідність ваговий коефіцієнт .
У пункті 2.2.1 відмічається, що етап побудови аналітичної моделі системи координат потребує конкретизації, тому що на різних ГД крива може бути подана у різних системах координат.
У пункті 2.2.2 відмічається, що на вході алгоритму виділення системи ланок (АВСЛ): КРЗ, задана с.к. B; на виході АВСЛ: система ланок, що задовольняє умові (6), і вектор параметрів, що описує кожну пару ланок.
. (6)
АВСЛ залежить від виду ГД, на якому знаходиться крива, яку необхідно розпізнати.
У пункті 2.2.3 пропонується підхід до знаходження якостей стиковки між парою ланок. На вході алгоритму знаходження якостей стиковки між кожною парою ланок: система ланок, що задовольняє умові (6), і вектор параметрів, одержаний для кожної пари ланок алгоритмом виділення системи ланок. На виході цього алгоритму: система ланок і якості стиковки між кожною парою ланок. Для знаходження якостей стиковки між кожною парою ланок розглядається підзадача, яка називається задачею знаходження якостей стиковки між даною ланкою і списком ланок (ЗЗЯС).
Формальна постановка ЗЗЯС полягає у наступному.
Дано: ланка i, ланки . Виконуються умови , .
Знайти: .
Кожної парі ланок i, ставиться у відповідність вектор параметрів (це параметри, передані алгоритмом виділення системи ланок для пари ланок ).
У дисертаційній роботі доказується, що
,
де — випадковий вектор параметрів, який являє собою значення параметрів тих пар ланок, які потрапили до оптимального маршруту, а —
функція щільності розподілу випадкового вектору .
Крім того, приводиться відміна ЗЗЯС від стандартних задач розпізнавання образів, що розглядаються у статистичній теорії розпізнавання образів. Запропоновано підхід до знаходження функції щільності розподілу випадкового вектору . При цьому було показано, що система, побудована за розробленим методом, може самонавчатися і адаптуватися до статистичних властивостей кривих потоку КРЗ графічних документів.
У пункті 2.2.4 розглянута проблема пошуку оптимальної путі на графі, дано рекомендації щодо доцільності використання наведених алгоритмів.
У третьому розділі проведена конкретизація етапів 1—2 розробленого методу відповідно до кругових діаграм самописних приборів, що використовуються у газовій промисловості для обчислення витрат газу.
У підрозділі 3.1 розроблена і наведена математична постановка задачі побудови аналітичної моделі системи координат B для КД. Одержані аналітичні вираження для переходу із прямокутної с.к. A, пов’язаної з РЗ кругових діаграм, у с.к. B, у якій подана розпізнавана крива, і назад для кожної точки. Для спрощення задачі побудови аналітичної моделі уводиться проміжна полярна с.к. A1, і будуються для довільної точки K рівняння переходу із прямокутної с.к. A у проміжну полярну с.к. A1, із A1 у B, із B у A1, із A1 в A. Побудова аналітичної моделі с.к. B було здійснено для КД з рівномірними і нерівномірними шкалами, а також для діаграм, час на яких відраховується за годинною і проти годинної стрілки. Одержана форма завдання аналітичної моделі через параметри КД.
У підрозділі 3.2 запропоновано один із можливих варіантів АВСЛ для КД. У запропонованому АВСЛ для КД кожна ланка являє собою одну точку у с.к. B. Для знаходження системи ланок було розроблено: алгоритм виконання січення уздовж маркеру, процедура знаходження зваженого центру полоси, обчислення ваги пікселів полоси. Крім системи ланок, АВСЛ для КД повинен сформувати вектор параметрів, що описує кожну пару ланок. Вибір параметрів пар ланок залежить від АВСЛ. Показано, що необхідно вибирати такі параметри для пари ланок, які найбільше характеризують розпізнавану криву, тобто щоб за цими параметрами крива найбільше відрізнялася від усіх інших об’єктів графічного документу. За такі параметри пропонується вибрати геометричні характеристики пари ланок i,j та усереднений модуль відхилення (за красною, зеленою і синію складовою) від базового кольору для ланки j.
У четвертому розділі була проведена оцінка ефективності методу, розробленого у розділах 2, 3. До оцінки ефективності було застосовано два підходи. У першому випадку ефективність оцінювалась за результатами обробки реальних КД. Оскільки оброблювались тільки реальні зображення КД, а вони були в основному або з малим числом перешкод, або перешкоди сильно відрізнялися від розпізнаваної кривої, то ефективність розробленого методу була у всіх випадках 100%. Тому у дисертаційній роботі ефективність ще оцінювалась за допомогою імітаційного моделювання, яке дозволило промоделювати не тільки дуже велику кількість перешкод на ГД, але також ситуації, у яких перешкоди розташовувались поблизу від розпізнаваної кривої, були на неї схожі і т.п. Таким чином, імітаційне моделювання дозволило промоделювати такі ситуації, які на реальних зображеннях КД зустрічаються рідко, і тому оцінка ефективності розробленого методу була проведена більш повно.
У підрозділі 4.1 розглядаються критерії, які можна застосувати до оцінки ефективності. Під час імітаційного моделювання ефективність розробленого методу оцінювалась з використанням критерію, названого якістю розпізнавання. Наведено обгрунтування такого вибору критерію оцінки ефективності.
У підрозділі 4.2 наведена оцінка ефективності розробленого методу за результатами обробки реальних кругових діаграм.
У підрозділі 4.3 ефективність оцінюється за допомогою імітаційного моделювання. При цьому якість розпізнавання ( ) визначається таким чином:
,
де — функція, що відповідає розпізнаваної кривої, а — кусочно-лінійна апроксимація, побудована за оптимальною ЦМК , яка отримана у результаті розпізнавання.
Дослідження якості розпізнавання кривих на КРЗ графічних документів у залежності від зміни параметрів перешкод проводились за допомогою імітаційного моделювання з використанням пакету Mathematica 3.0. Метою імітаційного моделювання є дослідження залежності якості розпізнавання від зміни статистичних властивостей перешкод.
Об’єктами імітаційного моделювання є:
• абстрактний графічний документ, який містить криву і перешкоди, тобто моделюються статистичні властивості кривої і перешкод;
• варіант алгоритму розпізнавання, побудованого на основі розробленого методу розпізнавання кривих на КРЗ.
У роботі наведено обгрунтування такого імітаційного моделювання і алгоритм моделювання. Нехай — випадковий вектор параметрів, який являє собою значення параметрів тих пар ланок, які не потрапили до оптимального маршруту, а
— функція щільності розподілу випадкового вектору . У спрощеному вигляді можна сказати, що імітаційне моделювання полягало у тому, що генерувалися ланки, які складають оптимальний маршрут (за законом ). Для цього генерувалися такі параметри ланок: , де — геометричні характеристики ланок i та j, — усереднений модуль відхилення (за красною, зеленою і синію складовою) від базового кольору для ланки j. Ці параметри генерувалися програмно за допомогою генератора випадкових чисел за деякими обраними законами. При цьому для простоти вважалося, що
,
де . Тобто параметри для пари ланок i,j генерувались за законом , — за законом , , , — за законами , , відповідно.
Перешкоди для кожної ланки, яка включалася до маршруту, отриманого за допомогою розробленого методу, генерувалися за законом
.
Таким чином, за допомогою розробленого методу розпізнавання кривих на КРЗ, через нанесені перешкоди і “правильні” ланки прокладався маршрут. По відхиленню оптимального маршруту від маршруту, отриманого за допомогою розробленого методу, обчислювалась якість розпізнавання.
Кількість перешкод, які генерувалися на кожну ланку, характеризує кількість перешкод на одиницю площі ГД. Розподіляння перешкод по , (тобто функції , ) характеризують розташування перешкод відносно кривої (наприклад, близько або далеко перешкоди знаходяться від кривої), а розподіляння перешкод по , , (тобто функції , , ) характеризують, наскільки колір перешкод близько або далеко знаходиться від кольору розпізнаваної кривої.
Під час імітаційного моделювання обиралися такі закони розподілу випадкових величин (ВВ) і :
1. ВВ , , , мали напівнормальні розподіляння, ВВ — нормальні розподіляння; ВВ , , , , були розподілені за рівномірним законом;
2. ВВ мала напівнормальне розподіляння, ВВ , , — експоненціальне розподіляння, ВВ — нормальне; ВВ , , , , були розподілені за рівномірним законом;
3. ВВ , , , мали напівнормальне розподіляння, ВВ — нормальне розподіляння; ВВ , , , були розподілені за напівнормальним законом, ВВ — за нормальним.
У дисертаційній роботі наведені графіки залежності якості розпізнавання від всіляких параметрів перешкод. На рис. 1 показана залежність якості розпізнавання від зміни інтервалу, на якому розподілена ВВ (ВВ і мають закони розподілу такі, як у випадку 1).

Рис. 1. Залежність якості розпізнавання від зміни інтервалу, на якому розподілена ВВ
Результати досліджень якості розпізнавання кривих на КРЗ ГД у залежності від зміни статистичних властивостей перешкод підтвердили, що для гарної якості розпізнавання функція повинна відрізнятися від функції . Якщо виявиться, що функція збігається з функцією , то це говорить про те, що за обраними признаками крива схожа на перешкоду, і може статися, що навіть людині важко буде відрізнити криву від перешкоди. Таким чином, дослідження підтвердили припущення, що чим менше перешкоди будуть схожі на розпізнавану криву, тим краще буде якість розпізнавання, і, крім того, навіть якщо за якимось параметрами (не за усіма, а за одним або двома параметрами) перешкода буде схожа на криву, то якість розпізнавання все одно виходить доволі високою. Кількість перешкод, які генерувалися на кожну ланку, характеризує кількість перешкод на одиницю площі ГД. Чим більше на ГД буде знаходитися перешкод, тим якість розпізнавання повинна бути гірше. Це підтвердили проведені дослідження, тобто при збільшенні кількості перешкод якість розпізнавання була гіршою. Проведене імітаційне моделювання показало, що якість розпізнавання у широкій області зміни параметрів перешкод не менше 99.5%, а зменшується воно тільки у вузької області зміни параметрів перешкод (у тiєї області, де статистичні властивості перешкод збігаються або близькі до статистичних властивостей кривої), або при значному збільшенні кількості перешкод на ГД. Тому метод, розроблений для рішення задач розпізнавання кривих на КРЗ (розділи 2, 3), є ефективним і його можна широко використовувати для рішення практичних задач розпізнавання.

ВИСНОВКИ

1. Сформульовано новий клас задач розпізнавання кривих на КРЗ графічних документів, рішення яких дозволяє одержати табличну форму графіку однозначної функції, що відповідає розпізнаваної кривої.
2. Розроблено ефективний метод рішення задач розпізнавання кривих на КРЗ графічних документів, основними етапами якого є: 1) побудова аналітичної моделі системи координат, у якої знаходиться розпізнавана крива, для ГД; 2) виділення системи ланок; 3) знаходження якостей стиковки між кожною парою ланок; 4) знаходження маршруту з максимальною якістю шляхом рішення задачі пошуку оптимальної путі на графі. Показано, що етапи 3—4 є інваріантними до виду ГД, а етапи 1—2 потребують розробки конкретних алгоритмів для кожного виду ГД.
3. Проведена конкретизація етапів 1—2 відповідно до кругових діаграм самописних приборів, що використовуються у газовій промисловості для обчислення витрат газу, тобто здійснено побудову аналітичної моделі системи координат B для КД і розроблено один із можливих варіантів алгоритму виділення системи ланок для КД.
4. Здійснено розробку етапів 3—4 для будь-якого виду ГД. Запропоновано підхід до знаходження якостей стиковки між парою ланок, при цьому показано, що система, побудована за розробленим методом, може самонавчатися і адаптуватися до статистичних властивостей кривих потоку КРЗ ГД. Розглянута проблема пошуку оптимальної путі на графі.
5. Проведені дослідження ефективності розробленого методу за результатами обробки реальних КД і за допомогою імітаційного моделювання, яке дозволило промоделювати такі ситуації, які на реальних зображеннях КД зустрічаються рідко, і тому оцінка ефективності розробленого методу була проведена більш повно. Під час імітаційного моделювання ефективність розробленого методу оцінювалася з використанням критерію, названого якістю розпізнавання. Наведено обгрунтування такого вибору критерію оцінки ефективності. Імітаційна модель була розроблена з використанням пакету Mathematica 3.0 для дослідження залежності якості розпізнавання кривих на КРЗ ГД від зміни статистичних властивостей перешкод. Дослідження підтвердили припущення, що чим менше перешкоди будуть схожі на розпізнавану криву, тим якість розпізнавання буде краще, і чим більше на ГД буде знаходитися перешкод, тим якість розпізнавання буде гірше. Крім того, проведене імітаційне моделювання показало, що якість розпізнавання у широкій області зміни параметрів перешкод не менше 99.5%, а зменшується воно тільки у вузької області зміни параметрів перешкод (у тієї області, де статистичні властивості перешкод збігаються або близькі до статистичних властивостей кривої), або при значному збільшенні кількості перешкод на ГД. Тому метод, розроблений для рішення задач розпізнавання кривих на КРЗ є ефективним і його можна широко використовувати для рішення практичних задач розпізнавання кривих на КРЗ.
6. Розроблений у дисертаційній роботі метод програмно реалізовано у вигляді АСОКД у середовищі Windows з використанням інструментальних засобів Borland Pascal 7.0 і Delphi. АСОКД використовується у науково-дослідницькому учбовому центрі обліку газу і метрології газовимірювань ДП НДПІАСУтрансгаз, і, крім того, АСОКД була передана в опитну експлуатацію у ВАТ “Харьковгоргаз”.
7. Розроблений метод розпізнавання кривих на КРЗ графічних документів можна використовувати не тільки у газовій промисловості, але і у багатьох інших галузях народного господарства України (наприклад, у медицині, для комп’ютерної обробки результатів наукових експериментів і т.д.).

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

1. Адаменко В. А. Распознавание графиков зависимостей на цветных растровых изображениях диаграмм// Радиоэлектроника и информатика.— 1998.— №1.— С. 84-85.
2. Тевяшев А. Д., Адаменко В. А., Адаменко А. В., Пономарьов Ю. В. Комплекс задач автоматизованого планіметрування колових діаграм// Нафтова і газова промисловість.— 1997.— №2.— С. 45-47.
3. Тевяшев А.Д., Адаменко В.А. Алгоритм автоматического распознавания кривых на цветных изображениях круговых диаграмм// Информационные технологии: наука, техника, технология, образование, здоровье: Сборник научных трудов ХГПУ. Вып. 6. В четырех частях. Ч. 1.— Харьков: Харьк. гос. политехн. ун-т.— 1998.— C. 332-335.
4. А.Тевяшев, В.Адаменко, Ю.Пономарев. Информационно-аналитическая система обработки цветных диаграмм самопишущих расходомеров природного газа// Транспортування, контроль якостi та облiк енергоносiiв.— Львiв: Державний унiверситет “Львiвська полiтехнiка”.— 1998.— С. 217-222.
5. Пономарев Ю. В., Адаменко В. А., Адаменко А. В. Комплекс задач автоматизированного планиметрирования круговых диаграмм// 2 межд. конф. “Теория и техника передачи, приема и обработки информации” в г. Туапсе.— Ч. 2.— Харьков: ОНТИ ХТУРЭ.— 1996.— С. 217.
6. Адаменко В. А., Адаменко А. В. Автоматизированная система учета расхода газа на газораспределительных станциях// 3 межд. конф. “Теория и техника передачи, приема и обработки информации” в г. Туапсе.— Харьков: ОНТИ ХТУРЭ.— 1997.— С. 195.
7. Тевяшев А.Д., Адаменко В.А., Адаменко А.В., Пономарев Ю.В. Автоматизированная система обработки цветных диаграмм самопишущих средств измерения// “Інформаційні і енергозберігаючі технології для трубопровідних систем енергетики”: Тез доп. і повід.— Івано-Франківськ: ЦНТЕІ.— 1997.— С. 65-77.
АНОТАЦІЯ

Адаменко В. А. Розробка та дослідження ефективного методу рішення задач розпізнавання кривих на кольорових растрових зображеннях.— Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.04— системний аналіз та теорія оптимальних рішень.— Харківський державний технічний університет радіоелектроніки, Харків, 1998.
У дисертації сформульовано новий клас задач розпізнавання кривих на кольорових растрових зображеннях графічних документів, рішення яких дозволяє одержати табличну форму графіку однозначної функції, що відповідає розпізнаваної кривої, і розроблено метод рішення таких задач, основними етапами якого є: побудова аналітичної моделі системи координат, у якої знаходиться розпізнавана крива, для графічного документу; виділення системи ланок; знаходження якостей стиковки між кожною парою ланок; знаходження маршруту з максимальною якістю шляхом рішення задачі пошуку оптимальної путі на графі. Проведені дослідження ефективності розробленого методу за результатами обробки реальних кругових діаграм і за допомогою імітаційного моделювання, яке дозволило промоделювати такі ситуації, які на реальних зображеннях кругових діаграм зустрічаються рідко, і тому оцінка ефективності розробленого методу була проведена більш повно. Проведені дослідження підтвердили високу ефективність розробленого методу.
Ключові слова: кольорове растрове зображення, розпізнавання кривих, аналітична модель системи координат для графічного документу, система ланок, якість стиковки між парою ланок, імітаційне моделювання, кругова діаграма.

АННОТАЦИЯ

Адаменко В. А. Разработка и исследование эффективного метода решения задач распознавания кривых на цветных растровых изображениях.— Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.04— системный анализ и теория оптимальных решений.— Харьковский государственный технический университет радиоэлектроники, Харьков, 1998.
В диссертации разработана и приведена постановка нового класса задач распознавания кривых на цветных растровых изображениях (ЦРИ) графических документов. Для этого вводятся понятия кривой, цифровой модели кривой (ЦМК), аналитической модели системы координат для графического документа и др. Показано, что результатом решения задачи распознавания кривой на ЦРИ является оптимальная ЦМК, т.е. табличная форма графика однозначной функции, соответствующей распознаваемой кривой. При этом предполагается, что кривые представляют собой реализации одного и того же случайного процесса с непрерывным временем и независимыми приращениями. Статистические свойства этого процесса заранее неизвестны, но постоянны или меняются постепенно от одного графического документа к другому для всех кривых одного потока. Разработан метод решения сформулированного класса задач, суть которого состоит в построении конкретных математических моделей для формализации исходной полуформализованной задачи и представления ее в виде более простых подзадач.
Основными этапами разработанного метода являются:
1. Построение аналитической модели системы координат B, в которой представлена распознаваемая кривая, для графического документа.
2. Выделение системы звеньев (предполагаемых фрагментов оптимальной ЦМК).
3. Нахождение качеств стыковки между каждой парой звеньев.
4. Нахождение маршрута с максимальным качеством путем решения задачи поиска оптимального пути на графе.
Показано, что этапы 3—4 являются инвариантными к виду графических документов, а этапы 1—2 требуют разработки конкретных алгоритмов для каждого вида графических документов. В диссертационной работе была проведена конкретизация этапов 1—2 применительно к круговым диаграммам (КД) самопишущих приборов, применяемых в газовой промышленности для вычисления расхода газа. Т.е. в работе была разработана и приведена математическая постановка задачи построения аналитической модели системы координат B для КД и был разработан алгоритм выделения системы звеньев для КД. Аналитическая модель системы координат B для КД представляет собой формулы перехода из прямоугольной с.к. A, связанной с растровым изображением КД, в с.к. B, в которой представлена распознаваемая кривая, и обратно для каждой точки, обеспечивающие инвариантность этого перехода к масштабу растрового изображения. Для нахождения системы звеньев были разработаны алгоритм выполнения сечения вдоль маркера, процедура нахождения взвешенного центра полосы, вычисление весов пикселов полосы.
В диссертации был предложен подход для нахождения качеств стыковки между парой звеньев. Для этого дается формальная постановка задачи нахождения качеств стыковки между данным звеном и списком звеньев, находится аналитическое выражение для качества стыковки пары звеньев, предлагается подход к нахождению функции плотности распределения случайного вектора , который представляет собой значения параметров тех пар звеньев, которые попали в оптимальный маршрут. При этом было показано, что система, построенная по разработанному методу, может самообучаться и адаптироваться к статистическим свойствам кривых потока ЦРИ графических документов. Рассмотрена проблема поиска оптимального пути на графе.
В работе были проведены исследования эффективности разработанного метода, при этом к оценке эффективности было применено два подхода. В первом случае эффективность оценивалась по результатам обработки реальных круговых диаграмм. Поскольку обрабатывались только реальные изображения круговых диаграмм, а они были в основном либо с малым числом помех, либо помехи сильно отличались от распознаваемой кривой, то эффективность разработанного метода получилась во всех случаях 100%. Поэтому в диссертации эффективность еще оценивалась с помощью имитационного моделирования, которое позволило промоделировать не только очень большое количество помех на графическом документе, но и ситуации, когда помехи располагались вблизи распознаваемой кривой, были на нее похожи и т.д. Таким образом, имитационное моделирование позволило промоделировать такие ситуации, которые на реальных изображениях КД встречаются редко, и поэтому оценка эффективности разработанного метода была проведена более полно. Во время имитационного моделирования эффективность разработанного метода оценивалась с использованием критерия, названного качеством распознавания. Приведено обоснование такого выбора критерия оценки эффективности. Имитационная модель была разработана с применением пакета Mathematica 3.0 для исследования зависимости качества распознавания кривых на ЦРИ графических документов от изменения статистических свойств помех. Исследования подтвердили предположение, что чем меньше помехи будут похожи на распознаваемую кривую, тем качество распознавания будет лучше, и чем больше на графическом документе будет находиться помех, тем качество распознавания будет хуже. Кроме того, проведенное имитационное моделирование показало, что качество распознавания в широкой области изменения параметров помех не менее 99.5%, а уменьшается оно только в узкой области изменения параметров помех (в той области, где статистические свойства помех совпадают или близки к статистическим свойствам кривой), либо при значительном увеличении количества помех на графическом документе. Поэтому метод, разработанный для решения задач распознавания кривых на ЦРИ, является эффективным и его можно широко использовать для решения практических задач распознавания кривых на ЦРИ.
Ключевые слова: цветное растровое изображение, распознавание кривых, аналитическая модель системы координат для графического документа, система звеньев, качество стыковки между парой звеньев, имитационное моделирование, круговая диаграмма.

ABSTRACT

Adamenko V. A. Development and research of an effective method for decision of the tasks of curve recognition on the color raster images. — Manuscript.
The thesis presented for a candidate degree of engineering science on a specialty 01.05.04 — System analysis and theory of the optimum decisions. — Kharkov State Technical University of Radioelectronics, Kharkov, 1998.
In the thesis the new class of tasks of curve recognition on the color raster images of the graphic documents is formulated. Decision of these tasks allows receiving the tabulated form of the diagram of unequivocal function that appropriate to a curve recognized. The method of the decision of such tasks has been developed. The basic stages of method presented are: construction of analytical model of coordinate system, in which the recognized curve is submitted on the graphic document; allocation of system of parts; a finding of link qualities between each pair of parts; a finding of a route with the maximal quality by the decision of a task of search of an optimum way on the graph. The researches of efficiency of the developed method have been carried out by results of processing the real circular diagrams and with the help of imitating modeling. This imitating modeling has allowed modeling out such situations that rarely meet on the real images of the circular diagrams, and consequently the estimation of efficiency has been carried out more full. The carried out researches have confirmed high efficiency of the developed method.
Keywords: color raster image, curve recognition, analytical model of coordinate system on the graphic document, system of parts, link quality between each pair of parts, imitating modeling, circular diagram.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020