“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Мохамед Хашим Мохамед Румі

(Шри-Ланка)

УДК 621.325.5

Організація процесів обробки зображень

(на прикладі штрихових зображень)

Спеціальність – 05.13.13 – Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Київ 2001

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

Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” на кафедрі обчислювальної техніки.

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

Бузовський Олег Володимирович

НТУУ “КПІ”, професор кафедри ОТ

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

Брюхович Євген Іванович,

ведучий науковий співробітник

Інституту кібернетики ім. Глушкова

НАН України

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

Вишневський Віталій В’ячеславович,

старший науковий співробітник

Інституту математичних систем і

машин НАН України

Провідна установа: Інститут проблем реєстрації інформації

НАН України, відділ

проблемно-орієнтованих

інформаційно-обчислювальних систем

Захист відбудеться “15” січня 2002 р. о 14-30 на засіданні спеціалізованої ради Д 26.002.02 у НТУУ ”КПІ” (м.Київ, просп.Перемоги 37, корп.18, ауд. 306)

Відзиви на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати на адресу: 03056, м.Київ, просп. Перемоги 37, вченому секретарю НТУУ “КПІ”

З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України “Київський політехнічний інститут”

Автореферат розісланий “12” грудня 2001 р.

Вчений секретар

спеціалізованої вченої ради Орлова М.М.

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

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

Зв’язок роботи з науковими програмами, планами, темами.

Роботу виконано за тематикою, що обумовлено планом науково-дослідних робіт кафедри ОТ НТУУ “КПІ” у відповідності до державної науково-технічної програми “Образний комп’ютер”.

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

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

Предметом дослідження є моделі зображень, методи та засоби комп’ютерної обробки візуальної інформації (на прикладі штрихових зображень).

Основні задачі дослідження у відповідності до поставленої мети полягають у наступному.

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

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

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

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

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

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

Наступні положення конкретизують наукову новизну одержаних результатів.

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача полягає в розробці рекомендацій щодо організації уніфікованого процесу обробки візуальної інформації, алгоритмів та програмних засобів, що забезпечують розв’язок задач обробки штрихових зображень. Всі основні результати роботи одержані автором особисто. В публікаціях, написаних в співавторстві, здобувачеві належить: в роботі [1] – виділення ознак сигнальних та семантичних моделей зображень, в роботі [2] – модель зображеного об’єкту та методи обчислення характеристичної функції та серединної вісі зв’язної геометричної площини, в роботі [3] – постановка задачі узгодження форматів даних для САПР ЗОТ та ідея її розв’язання за допомогою засобів обробки зображень, а також виділення ознак класу штрихових зображень.

Апробація результатів дисертації. Основні результати дисертації доповідались та обговорювались на науково-технічних семінарах кафедри обчислювальної техніки НТУУ “КПІ” (жовтень 1999, вересень 2000, вересень 2001), а також на міжнародних наукових конференціях: “Systemy komputerowe i sieci”, Rzeszow, 26-27 червня 1997, “Information Technologies and Simulation – 2001” , ITS-2001, 6-8 червня 2001, Алушта, Україна.

Публікації. По темі дисертації опубліковано три наукові роботи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

H(i)=1(I1,i)+ 2(I2,i),

де I1, I2 – значення інтенсивності для фону та штрихів відповідно;

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

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

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

Виходячи з потреб обробки таких зображень, можна конкретизувати множину часткових задач (рис.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.

3. Бузовский О.В., Болдак А.А., Мохамед Руми М.Х. Компьютерная обработка изображений. К., “Корнійчук”, 2001, 180 с.

АНОТАЦІЇ

Мохамед Хашим Мохамед Румі Організація процесів обробки зображень

(на прикладі штрихових зображень).– рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13. – “Комп’ютерні машини, системи та мережі”. – рукопис.

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

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

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

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

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

Mohamed Hashim Mohamed Rumie The organization of image processing (on an example of the shaped images). – manuscript.

Thesis for the candidate’s degree by the specialty 05.13.13. - Computers, system and network. National Technical University of Ukraine " Kiev Polytechnic Institute ", Kiev, 2001.

Thesis is devoted to development of universal remedies of computer processing of the images.

On the basis of the analysis of known methods of the decision of tasks of processing of the images the generalized approach is offered, which essence consists in realization of system of an open type having an opportunity of updating of hardware-software components, achievable as a result of use of the unified interfaces of their interaction.

On the basis of the analysis of known models of the images the generalized diagram is offered, within the framework of which the classes of alarm and semantic models of the images are allocated. Their properties are investigated and the set of tasks effectively solved with their help is determined.

The class of the shaped images is allocated and the models, appropriate to it, of the images are developed which are fixed in a basis of the developed methods of reception of the planimetric description of the image. Computing complexity develops the appropriate algorithms with polynomial by computing complexity.

The architecture of computing processes realizing function of universal system of processing of the images is offered, which basis makes use of set of the unified interfaces of interaction a separate hardware-software component.

Key words: the image, the image processing, model of the represented object, characteristic function, and skeleton.

Мохамед Хашим Мохамед Руми Организация процессов обработки изображений (на примере штриховых изображений). – рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13. – Вычислительные машины, системы и сети. Национальный технический институт Украины “Киевский политехнический институт”, Киев, 2001.

Диссертация посвящена разработке универсальных средств компьютерной обработки изображений.

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

На основе анализа известных моделей изображений предложена обобщенная диаграмма, в рамках которой выделены классы сигнальных и семантических моделей изображений. Исследованы их свойства и определено множество задач, эффективно решаемых с их помощью.

Выделен класс штриховых изображений, для которого предложена модель изображенного объекта, основанная на определении связной геометрической области, которая задается границей и характеристической функцией. Предложен метод вычисления характеристической функции объекта по известной аппроксимации его границы, которая рассматривается как годограф вектор-функции, начало которой фиксировано в заданной точке Соответствующий алгоритм вычисления характеристической функции имеет линейную вычислительную сложность. Предложен метод вычисления скелета изображенного объекта, в основе которого лежит использование кусочно-плоскостной аппроксимации функции расстояния. В отличие от методов, использующих растровое представление, метод отличается использованием модели меньшей размерности. В отличие от методов, использующих триангуляцию, предложенный метод учитывает свойства функции расстояния и, следовательно, имеет меньшую сложность. Соответствующий алгоритм скелетизации изображения имеет вычислительную сложность nlog(n).

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

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