Структура та об'єм роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків та додатку. Робота містить 116 сторінок друкованого тексту, 39 малюнків, 6 таблиць і список використаної літератури на 82 найменування.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай - множина елементів моделі i-ого рівня, тоді перехід від моделі i-ого рівня до моделі i+1-ого рівня пов'язаний з розв'язанням задачі пошуку функціонального відображення , де . Відображення v визначає процес ідентифікації множини можливих об'єктів , кожен з яких розглядається як вектор у просторі . Зрозуміло, що важко обмежити складність можливих структур на i-ому рівні подання моделі (тобто і розмірність параметричного простору) без врахування семантики елементів моделі i+1-ого рівня. Тому доцільним є введення правил, на множину відношень , що допускаються. В цьому випадку задачу ідентифікації об'єктів буде зведено до перевірки їх відповідності до множини правил що визначають класи елементів моделі i+1-ого рівня.

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

В межах такого підходу до розв'язання задач ідентифікації зображень може бути розроблена узагальнена структура відповідного обчислювального процесу (рис.2), для якого роль параметрів грають моделі i та i+1-ого рівня подання.

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

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

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

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

· використання простих геометричних примітивів;

· використання обмеженої множини умовних графічних позначень (УГП), які ставляться в однозначну відповідність до елементів структури ОП;

· наявність правил оформлення схем, які однозначно визначають відповідність між відношеннями на множені елементів ОП та геометричними співвідношеннями між примітивами та УГП на кресленні.

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

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

Наведене вище семантичне визначення класу штрихових зображень дозволяє дослідити властивості, які можна відобразити у залежності елементів моделі сигнального рівня (у даному випадку - матричного подання зображення).

Ідентифікація штрихів можлива за умови використання рівномірного фону, тобто гістограма такого зображення повинна мати вигляд функції:

H(i)=₁(I₁,i)+ ₂(I₂,i),

де I₁, I₂ - значення інтенсивності для фону та штрихів відповідно;

(x,y) - функція Кронекера;

₁, ₂ - вагові коефіцієнти (₁+₂=1).

Характерним для штрихових зображень є також специфічне розподілення I(x,y), де I - інтенсивність, x,y - геометричні координати, яке уявляє собою кусочно-постійну функцію з рівнями I₁ та I₂. При цьому штрихам відповідають зв'язні геометричні множини пікселів з однаковим рівнем інтенсивності. Більш того, можна вказати мінімальну потужність такої множини - вона є рівною площині пера.

Виходячи з потреб обробки таких зображень, можна конкретизувати множину часткових задач (рис.4).

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

Нехай - впорядковані множини, а . Тоді бінарним зображенням є , в якому - координати елемента зображення, а - його колір. Зрозуміло, що множина може бути подана у вигляді

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

У просторі може бути введено 2-норму векторів, яка визначає його метрику. -сусідством () буде називатись відношення, отримане наступним чином: нехай , тоді . Зрозуміло,що , яке визначається мамою метрикою та є відношенням еквівалентності. Також легко встановити, що відношення є нетранзитивним. Таким чином, на відміну від , відношення не може використовуватись для визначення класів еквівалентності. Однак воно може бути подано у вигляді , де - підмножина , в якому виконується умова транзитивності, а - межа об'єкту.

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

.

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

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

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

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

.

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

.

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

Запропонований метод пошуку серединної вісі зв'язної геометричної множини базується на визначенні функції відстані. Незалежно від вибору, норма визначає поверхню у просторі , властивості якої відповідають обмеженням, накладеним на норму. Зрозуміло, що ця поверхня є правильним конусом з верхівкою у точці (0,0). Також легко встановлюється, що форма цього конусу інваріантна до афінних перетворень у . Виходячи з цього, можна констатувати, що для множини функція відстані уявляє собою суперпозицію норм у лінійному просторі . Якщо відома межа об'єкту, тоді задача пошуку серединної вісі набуває вигляду: , де - зображений об'єкт, - його межа.

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

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

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

Відповідно до висновків першого розділу розробка універсальних засобів обробки зображень повинна базуватись на архітектурі системи відкритого типу, що передбачає специфікації інтерфейсів взаємодії окремих компонентів (апаратних в тому числі). Зображена на рис.6 діаграма розміщення пояснює принципи взаємодії окремих компонентів (C0,…,C3) системи за допомогою інтерфейсів I0-I3. Компонент C0 та асоційований з ним інтерфейс відповідають реалізації активності “Реєстрація”(рис.4). Компоненти C1-C3 реалізують перетворення, пов'язані з попередньою обробкою зображень. Взаємодія з компонентами ідентифікації здійснюється за допомогою інтерфейсу I3.

Множина інтерфейсів I0-I3 дає можливість використання різних конфігурацій апаратних засобів для ефективної організації обчислень. Наприклад, під класом процесору TSensor0 розуміється традиційний периферійний пристрій, який реалізує активність “Реєстрація”, під класом TSensor1 - периферійний пристрій, який реалізує додатковий набір функцій попередньої обробки, а під класом TPreparator - спеціалізований пристрій попередньої обробки зображень, який входить в склад ЕОМ. Множина варіантів конфігурації апаратних засобів визначається множиною розміщення компонентів C0,…,C3 у процесорах системи обробки зображень.

Важливим є також узагальнення програмних компонентів, яке полягає у визначенні типів компонентів C0,…,C3 (рис.7). Це забезпечує можливість адаптації системи до особливостей прикладних задач, яка полягає в тому, що компоненти, які розробляються, повинні відповідати певній зовнішній специфікації, тобто реалізовувати та(або) використовувати уніфіковані інтерфейси. В цьому випадку такі компоненти можуть бути розташовані у репозіторії системи, функції керування яким здійснює керуючий модуль за допомогою інтерфейсу I5.

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

ОСНОВНІ ВИСНОВКИ ТА РЕЗУЛЬТАТИ РОБОТИ

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

Формулювання узагальненого підходу базується на наступному.

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

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

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

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

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

· Запропоновано метод обчислення характеристичної функції зв'язної геометричної множини по відомій апроксимації її межі, яка розглядається як годограф вектор-функції, початок якої фіксовано в точці геометричної площини. На відміну від відомих, запропонований метод не має обмежень на форму зображеного об'єкту. Відповідний алгоритм обчислення характеристичної функції має обчислювальну складність O=n, де n - кількість сегментів апроксимації.

· Запропоновано метод обчислення серединної вісі зображеного об'єкту, в основі якого лежить використання кусочно-площинної апроксимації функції відстані. На відміну від відомих методів, які використовують растрове подання зв'язної геометричної множини, запропонований метод відрізняється меншою розмірністю моделі. На відміну від методів, заснованих на використанні тріангуляції, цей метод враховує властивості функції відстані, а отже, має меншу складність. Відповідний алгоритм обчислення серединної вісі для класу штрихових зображень має обчислювальну складність O=nlog(n).

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

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

1. Болдак А.А., Р. Мохамед Хашим. Параметрический контроль аппаратных компонент СВТ. // Вісник національного технічного університету України “КПІ”, Інформатика, управління та обчислювальна техніка. - 2000. -№ 34. -С. 38-45.

2. Болдак А.А., Р. Мохамед Хашим. Метод скелетизации изображений. // Вісник національного технічного університету України “КПІ”, Інформатика, управління та обчислювальна техніка. - 2000. -№ 36. -С. 65-80.