|
Державний комітет зв'язку та інформатизації України
Національна академія наук України
Державний науково-дослідний інститут інформаційної інфраструктури
Сачанюк-Кавецька Наталія Василівна
удк 681.327.11
Елементи око-процесорної обробки зображень в логіко-часовому середовищі
Спеціальність 05.13.06 – Автоматизовані системи управління та
прогресивні інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня кандидата технічних наук
Львів – 2002
Дисертацією є рукопис
Робота виконана у
Вінницькому державному технічному університеті,
Міністерство освіти та науки України
Науковий керівник:
докт. техн. наук, проф. Кожем'яко Володимир Прокопович,
Вінницький державний технічний університет, завідувач кафедрою
лазерної та оптико-електронної техніки
Офіційні опоненти:
докт. техн. наук, доц. Тимченко Олександр Володимирович, Національний університет „Львівська політехніка", професор кафедри телекомунікацій;
докт. техн. наук, ст.наук.співр. Муравський Леонід Ігорович,
Фізико-механічний інститут ім.. Г.В. Карпенка НАН України,
в.о. зав. відділом оптико-електронних інформаційних технологій
Провідна установа
Національний технічний університет України „КПІ", кафедра автоматизованих систем обробки інформації та управління (м. Київ)
Захист відбудеться 10 грудня 2002 р. о 14 годині на засіданні спеціалізованої вченої ради Д35.813.01 при Державному науково-дослідному інституті інформаційної інфраструктури (79601, м. Львів, вул. Тролейбусна 11)
З дисертацією можна ознайомитися у бібліотеці Державного НДІ інформаційної інфраструктури (79601, м. Львів, вул. Тролейбусна 11).
Автореферат розіслано 8 листопада 2002 р.
Т.в.о. вченого секретаря
Спеціалізованої вченої ради,
докт. техн. наук, проф. Воробель Р.А.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Прогресивні інформаційні технології пов'язані із необхідністю збору та обробки великих об'ємів інформації. Саме ефективна і своєчасна обробка інформації є однією з найважливіших науково-технічних проблем створення засобів обробки зображень на рівні людського сприйняття та мислення.
Сьогодні одним із основних шляхів вирішення цієї проблеми є нарощування кількості обладнання і збільшення складності алгоритмів, що приводить до необхідності паралельної обробки інформації. Однак, більшість таких методів ефективно працюють лише для конкретно визначених типів сигналів, а це веде до необхідності додаткової обробки і адаптації методів при роботі з різними даними.
Перспективні розробки систем штучного інтелекту вимагають аналітичного опису сигналів, як можливості розвитку загальних систем обробки інформації.
Тому для усунення вказаних недоліків при розробці сучасних систем штучного інтелекту актуальними є задачі створення методів обробки зображень око-процесорного типу, які використовують деяку універсальну функцію, що може описувати характеристики реального об`єкта, незалежно від типу вхідного сигналу. В ролі такої функції розглянуто логіко-часову функцію (ЛЧФ), поняття якої започатковано науковою школою професора Кожем'яко В.П., що є завершенням розробки векторно-перемикаючих функцій Рабиновича З.Л. Оскільки як основний параметр ЛЧФ використовує час, то з'являється можливість аналітичного опису сигналів шляхом перетворення будь-якого набору вхідних даних на відповідні часові інтервали. Аналітичне дослідження таких сигналів відкриває нові можливості у створенні методів їх обробки. Одним із ефективних шляхів підвищення швидкодії око-процесорного виділення контурів зображень є використання градієнтних операторів, в яких застосовується операція диференціювання ЛЧФ.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась згідно з планом наукових досліджень Вінницького державного технічного університету Міністерства освіти та науки України за держбюджетною темою: 57-Д-226 "Створення оптико-електронних перетворювачів для формування статистичних та динамічних еталонів-образів патологій мікроциркуляції в щелепно-лицьовій області" (державна реєстрація
№ ДР 0100U002933) в 2000р.
Мета та задачі досліджень. Метою роботи є розробка методів та засобів підвищення швидкості око-процесорної обробки зображень шляхом формалізації необхідних для обробки операцій над ЛЧФ та дослідження їх властивостей.
Для досягнення поставленої мети вирішенню підлягали такі задачі:
- аналіз та систематизація методів математичного представлення та обробки інформації за допомогою ЛЧФ;
- створення математичного апарату, що описує операції взаємодії ЛЧФ, необхідні для око-процесорної обробки зображень;
- аналіз можливості паралельної обробки даних, які представлені за допомогою апарату ЛЧФ;
- класифікація ЛЧФ k-значної логіки та доведення повноти системи цих функцій;
- дослідження властивостей операції диференціювання ЛЧФ, які забезпечують можливість їх реалізації на апаратному рівні;
- проведення комп'ютерного моделювання обробки ЛЧФ;
- розроблення елементів око-процесорної обробки зображень, шляхом диференціювання відповідних ЛЧФ.
Об'єкт дослідження – методологія око-процесорної обробки зображень в логіко-часовому середовищі.
Предмет дослідження – методи і моделі, які використовуються в процесі око-процесорної обробки зображень в логіко-часовому середовищі та схемотехнічний варіант пристою для обробки ЛЧФ.
Методи дослідження базуються на використанні класичної математичної та булевої теорій, теорії функцій k-значної логіки, теорії логіко-часових середовищ.
Наукова новизна одержаних результатів. В дисертаційній роботі отримано наступні наукові результати:
- розроблено формальний математичний апарат, як базис обробки образної інформації в логіко-часовому середовищі;
- доведено можливість паралельної обробки даних, які представлені за допомогою апарату ЛЧФ;
- вдосконалено поняття похідної ЛЧФ та операції диференціювання і доведено деякі властивості цієї операції, які забезпечують розробку нових методів обробки зображення та підвищують їх ефективність;
- введено поняття похідних ЛЧФ вищих порядків та доведено їх властивість про перехід у початкову функцію;
- класифіковано ЛЧФ k-значної логіки та доведено повноту системи цих функцій, що дозволяє оптимізувати технічні засоби око-процесорної обробки зображень;
- розроблено методи апаратного визначення похідної ЛЧФ k-значної логіки, як результат виконання спеціальної операції.
Практичне значення одержаних результатів полягає в тому, що вони дають можливість:
· аналітично описувати і досліджувати сигнали за допомогою апарату ЛЧФ;
· підвищити швидкодію око-процесорної обробки зображень не менш ніж у два рази;
· спростити алгоритми і схемотехнічні рішення око-процесорної обробки зображень шляхом аналітичного дослідження властивостей операцій і сигналів;
· підвищити ефективність обробки зображень, шляхом створення спеціальних схемотехнічних структур на основі властивостей похідних ЛЧФ;
· за допомогою комп'ютерного моделювання проводити дослідження властивостей диференціювання та інших операцій над ЛЧФ.
Теоретичні та практичні результати дисертації впроваджено на ВАТ "Інфракон" в рамках розробки транзакційного терміналу, а також включено у навчальний процес на кафедрі лазерної та оптоелектронної техніки Вінницького державного технічного університету в рамках спеціалізації "Лазерна та оптоелектронна техніка в системах технічного зору та штучного інтелекту".
Особистий внесок. Всі основні результати дисертаційної роботи були отримані автором особисто. У публікаціях, написаних у співавторстві здобувачеві належить: дослідження властивостей похідної ЛЧФ [3, 5, 6, 7], введення поняття похідної ЛЧФ та доведення леми про інверсію, розробка таблиці похідних [1, 3], введення поняття та дослідження первісної ЛЧФ [2, 3], оцінка точності фільтрації ЛЧФ [4], обґрунтування доцільності використання нейронних мереж для KVP-перетворень [9], дослідження характеристичних ЛЧФ спаду та зросту, доведення теореми про апаратну реалізацію похідної [10].
Апробація результатів дисертації. Основні наукові і практичні результати роботи доповідались і обговорювались на: міжнар. конф. "Optoelectronic and hybrid optical/digital systems for image/signal processing." ODS'99 (Львів, 1999), 3-й міжнар. наук.-техн. конф. „Математичне моделювання в електротехніці, електроніці та електроенергетиці" (Львів, 1999), міждержавній науково-методичній конф. „Комп'ютерне моделювання" (Дніпродзержинськ, 2000), Intern. сonf. on optoelectronic information technologies "Photonics – ODS 2000" (Вінниця, 2000), наук.-техн. конф. молодих вчених „Оптико-електронні інформаційно-енергетичні технології" (Вінниця, 2002), Міжнар. конф. з індуктивного моделювання "МКІМ-2002" (Львів, 2002).
Публікації. За матеріалами дисертації опубліковано 10 наукових праць. Із них 4 статті у наукових фахових виданнях, 2 статті у збірках наукових праць та 4 тези конференцій.
Структура та обсяг дисертації. Дисертаційна робота складається з вступу, семи розділів, висновків та списку використаних джерел. Загальний обсяг дисертації 156 сторінок, з яких основний зміст викладено на 139 сторінках друкованого тексту, 69 рисунків та три додатки. Список використаних джерел нараховує 113 найменувань.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми, визначено мету роботи, вказано задачі, які необхідно вирішити для досягнення поставленої мети, подано перелік нових наукових положень, відзначено практичну цінність одержаних результатів, їх апробацію, публікації та впровадження.
У першому розділі вказано на актуальність та необхідність аналітичного опису зображення, як можливості розвитку загальних систем обробки зображень. Показано доцільність створення для систем штучного інтелекту засобів око-процесорного типу, здатних імітувати функції зорової системи людини. Проаналізовано існуючі методи обробки зображень. Всі вони носять алгоритмічний характер і практично не дозволяють аналітично дослідити поведінку зображення при тих чи інших умовах.
У багатьох випадках, пов'язаних з обробкою чи проектуванням, необхідно описати процес алгебраїчними виразами, що враховують часові особливості зображення. Актуальною є обробка зображень у логіко-часовому середовищі, з використанням логіко-часових функцій, які можуть описувати як стаціонарні зображення, так і об'єкти в динаміці.
Більшість відомих двовимірних унітарних перетворень зображення значно складніші за градієнтні оператори, які представляють собою те чи інше диференціювання, і їх використання в око-процесорних схемах не є ефективним.
Відомі операції диференціювання, розглянуті в роботі, не враховують фактор часу, що підтверджує введення операції диференціювання та дослідження її властивостей в логіко-часовому середовищі.
В другому розділі для опису процесу обробки інформації у логіко-часовому середовищі введено вдосконалене поняття похідної ЛЧФ, яке базується на спеціальному  -розбитті, пов'язаному з поняттям  -інтервалу. Математично описано спеціальні правила такого розбиття, які враховують особливості середини  -інтервалу (фільтрацію ЛЧФ). Оскільки операція фільтрації дещо змінює тривалості відрізків існування відфільтрованих ЛЧФ, за допомогою методу кореляційного аналізу дано оцінку точності фільтрації.
Похідна ЛЧФ k-значної логіки - це k-значна логіко-часова функція, що дорівнює приросту функції на i-му проміжку D-розбиття, якщо вихідна k-значна ЛЧФ приймала різні значення на i-1 і i-му проміжках. У протилежному випадку похідна дорівнює нулю. Для спрощення аналітичного опису похідної ЛЧФ використано основні позначення класичної математики.
Нехай маємо деяку ЛЧФ k-значної логіки  , де  - часові координати,  - відповідні відрізки існування,  - амплітуди, що відповідають цим відрізкам існування. Тоді похідна вказаної функції визначається наступним чином:
(1)
Операція знаходження похідної ЛЧФ називається диференціюванням ЛЧФ.
Похідною n-го порядку ЛЧФ називається похідна від похідної ЛЧФ (n-1)-го порядку.
У випадку двійкової логіки формула (1) дещо спрощується, оскільки амплітуди можуть приймати тільки нульове або одиничне значення, тобто:
(2)
Розглянуте поняття спеціального ?-розбиття дозволило довести, що ЛЧФ належать до класу  -частково-рекурентних функцій і їх можна використовувати для розпаралелювання та попередньої обробки зображень.
Для ефективного використання ЛЧФ k-значної логіки необхідно ввести деякі спеціальні операції. Операція нерівнозначного віднімання ( ) базується на введеному попередньо понятті  -розбиття:
 , де t11, t21 – часові координати змінних,  та  - тривалості відрізків існування першої та другої функції ,  та  - відповідні амплітуди,  - кількість  - інтервалів в обраному часовому інтервалі,  - тривалість  -інтервалу,  - відповідні амплітуди на  -му  -інтервалі. Результатом цієї операції є також ЛЧФ, яку можна назвати нерівнозначною різницею.
Отримано властивості такої операції:
1) операція нерівнозначного віднімання є комутативною;
2) операція нерівнозначного віднімання є асоціативною;
3) якщо від будь-якої ЛЧФ відняти ЛЧФ, у якої всі амплітуди дорівнюють нулю, то в результаті отримуємо вихідну ЛЧФ;
4) будь-яку ЛЧФ, що має m відрізків існування можна представити, як нерівнозначну різницю m ЛЧФ, з одним відрізком існування;
5) будь-яку ЛЧФ  можна представити, як нерівнозначну різницю інверсій елементарних ЛЧФ  ;
6) якщо від довільної ЛЧФ  відняти ЛЧФ  , де  , то отримуємо ЛЧФ інверсну функції  ;
7) нехай маємо деяку ЛЧФ  , причому  ,  ,
 , або  ,
тоді    = .
Третій розділ присвячено дослідженню властивостей апарату обробки зображень на базі моделі ЛЧФ.
Серед усіх можливих класів ЛЧФ k-значної логіки виділено три замкнутих класи.
Клас ЛЧФ, що між двома нулями приймають стале значення.
Позначимо такі функції  , де  - поточне значення часу,  - часова координата,  - тривалість відрізку існування,  - амплітуда ( = ,  )
Клас цих функцій є замкнутим по відношенню до операцій логіко-часової диз'юнкції, логіко-часової кон'юнкції, логіко-часового додавання та логіко-часового віднімання.
Замкнутість цього класу випливає із визначення вказаних операцій над ЛЧФ у випадку двійкової логіки, оскільки будь-яке значення амплітуди  = можна умовно розглядати як одиничне значення.
Клас ЛЧФ, які мають m часових координат, причому їх відрізки існування не перетинаються.
Позначаються такі функції  ,  ,  . Цей клас функцій є замкнутим по відношенню до операцій диференціювання та нерівнозначного віднімання.
Замкнутість вказаного класу відносно операції диференціювання випливає з означення похідної, оскільки:
- якщо  ,  ,  , то похідна лише збільшує тривалість усіх відрізків існування на  ;
- якщо  ,  ,  , то диференціювання у два рази збільшує кількість відрізків існування, причому  стають рівними  .
В обох випадках отримуємо ЛЧФ вказаного класу.
Для підтвердження замкнутості цього класу відносно операції нерівнозначного віднімання скористаємося сьомою властивістю цієї операції. Функції  та  класу мають m часових координат, причому відповідні відрізки існування не перетинаються. Можна зробити висновок, що в результаті виконання операції нерівнозначного віднімання над скінченою кількістю ЛЧФ, які мають m часових координат, причому відрізки існування не перетинаються, ми знову отримуємо функцію даного класу.
У частковому випадку, коли  , знову можна скористатись наведеною властивістю операції нерівнозначного віднімання. В класі ЛЧФ, що мають m часових координат, причому відрізки існування не перетинаються завжди знайдеться така функція, віднявши яку від похідної функції, для якої справедлива вказана тотожність, отримуємо знову ж таки функцію цього класу.
Клас монотонних функцій. ЛЧФ  називається зростаючою (спадною) ЛЧФ, якщо часові координати, починаючи з другої, утворюються за допомогою першої часової координати та відповідних тривалостей відрізків існування  ,  і справедлива нерівність  ( ), .
ЛЧФ  називається монотонно зростаючою (монотонно спадною) ЛЧФ, якщо вона є зростаючою (спадною) і справедливі рівності  ,  ,  ( ),  .
Доведено замкнутість вказаного класу відносно операцій диференціювання та нерівнозначного віднімання.
Побудовано три класи функцій, кожен з яких повністю не містить жодного з решти класів, система ЛЧФ k-значної логіки повністю не міститься в жодному з цих класів (будь-яку ЛЧФ, яка не входить в жоден клас, можна отримати з функцій вказаних трьох класів). Скориставшись теоремою А.В. Кузнєцова можна зробити висновок, що система ЛЧФ k-значної логіки є повною.
Досліджено основні властивості операції диференціювання ЛЧФ бінарних зображень, які забезпечують розробку нових методів обробки зображень та підвищують їх ефективність. Серед досліджених та доведених властивостей є:
- ЛЧФ та її інверсія мають рівні похідні, завдяки цій властивості з'являється можливість часткової оптимізації обробки бінарного зображення;
- похідна від суми по модулю два ЛЧФ дорівнює сумі по модулю два похідних ЛЧФ, доведена властивість дозволяє підвищити швидкодію обробки бінарних зображень шляхом незалежної обробки окремих його фрагментів;
- похідна вищих порядків переходять у початкову функцію в залежності від тривалості вхідного сигналу, вираженого в  -інтервалах (при тривалості вхідного сигналу 2-4  -інтервали четверта похідна переходить у початкову функцію, 5-8  -інтервалів – восьма похідна переходить у початкову функцію і т.д.), що надає можливості розробити класифікацію ознак.
Всі властивості носять характер теорем.
Сформульовано і доведено дві теореми про апаратну реалізацію операції диференціювання.
Теорема 1. Сума по модулю два (логічна нерівнозначність) довільної ЛЧФ і цієї ж функції з затримкою на  -інтервал дорівнює похідній даної функції.
Доведення.
Теорему доводимо за допомогою методу математичної індукції. Перевіримо, чи справедлива теорема у випадку логіко-часової функції, область визначення якої складається лише з одного відрізку існування:
(3)
де t – поточне значення параметру, t1 - початок відрізку існування, T1 – тривалість відрізку існування. Доведемо справедливість теореми для двох можливих випадків.
1) Розглянемо випадок, коли  .
Ця ж функція, але з затримкою на  -інтервал має вигляд:
, (4)
де  - тривалість  - інтервалу.
Функції (3) та (4) просумуємо по модулю два. В результаті отримуємо:
(5)
Згідно означенню похідна ЛЧФ (3) має вигляд:
(6)
Праві частини виразів (5) та (6) рівні між собою, а отже рівні і ліві частини. Тобто:
 . (7)
2) Розглянемо випадок, коли  .
В цьому випадку, сума по модулю два функцій (1) та (2) має вигляд:
(8)
Знайдемо похідну ЛЧФ функції (3). За означенням маємо:
(9)
Доведемо, що рівність (10) справедлива і для випадку ЛЧФ, область визначення якої містить n+1 відрізок існування. Для цього скористаємося властивостями операції додавання по модулю два, рівністю (10) та тим фактом, що похідна від суми по модулю два ЛЧФ дорівнює сумі по модулю два похідних ЛЧФ. Маємо:
| 
