Передмова. Алгоритми Екстракції ознак образів

Р.А. МЕЛЬНИК

АЛГОРИТМИ Екстракції ознак образів

Для їх класифікації та пошуку

ЛЬВІВ-2010

УДК 00.000.

М 00000000

Мельник Р.А. АЛГОРИТМИ Екстракції ознак образів для їх класифікації та пошуку. Львів, Світ, 2010. - 140с.

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

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

ISBN 000000000

Рекомендовано до друку Вченою радою Державного Університету “Львівська Політехніка” (протокол № від березня 1999 року)

Рецензенти:

Доктор технічних наук, професор Різник Володимир Васильович

Доктор технічних наук, професор Мельник Анатолій Олексійович

ISBN

Ó Мельник Р.А., 2010

ПЕРЕДМОВА

Українські вчені від часу створення в Україні перших комп’ютерів в 1958 році знаходяться серед лідерів розроблення алгоритмічного забезпечення для найрізноманітніших наукових і практичних потреб, в тому числі, для моделювання і проектування. Творчі колективи під керівництвом Р. [1-7] внесли значний доробок для задач розв’язування оптимального розміщення, розрізання матеріалів, пакування, призначення тощо.

Проведення теоретичних і практичних робіт в напрямку розвитку систем штучного інтелекту взагалі і при застосуванні їх в області теорії алгоритмів і методів проектування надвеликих інтегральних схем, зокрема, є актуальним з огляду на декілька причин. Надвеликі інтегральні схеми є елементною основою комп'ютерних систем п'ятого покоління і мікропроцесорних пристроїв загального і спеціального призначення [8-21]. Теоретичні і технологічні знання в цій області впливають на інформативне забезпечення практично всіх галузей економіки, іключаючи, на соціальну сферу, освіту, медицину тощо. В даний час в Україні теоретичні ідеї і програмні засоби можуть бути конкурентноздатними і цю тенденцію слід зберегти до піднесення технологічних можливостей.

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

У першому розділі розглянуті декомпозиційні алгоритми, що базуються на методі оптимального згортання графів [24-28…………. Наведено аналіз тестових результатів, який вказує на ефективність та перспективність розробленного підходу.

Другий розділ присвячено методу …………… проаналізовані отримані результати.

У третьому розділі розглянуті алгоритми побудови мінімальних зв’язуючих дерев на основі принципу оптимального згортання, який виступає керуванням для здійснення етапу макротрасування, незалежно від способу проведення фрагментів: лініями, променями чи хвильовим алгоритмом. ……………… який застосовується при знаходженні макро- і мікроз’єднань [45-68]..

У четвертому розділі розглянуті етапні задачі мікротрасування в каналі як пакування відрізків [69-73]. Основний алгоритм базується на ієрархічній процедурі пошуку в глибину ……………………, а до початку укладання відрізків розв’язується задача оптимального їх призначення.

Зміст

ПЕРЕДМОВА.. 3

Зміст. 4

Вступ. 5

Розділ 1. Огляд існуючих методів та алгоритмів і формулювання задачі 7

1.1. Огляд та сучасний стан опрацювання зображень. 7

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

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

2.1. Підходи для декомпозиції зображень. 12

2.2. Задача Декомпозиції образів.. 13

2.3. Формування мікро кластерів та кластерів.. 15

2.4. Формування регіонів та звязних областей.. 20

2.5. Керування видом та розмірами сегментів.. 24

Розділ 3. Формування та опрацювання ключів образів. 30

3.1. Структурні властивості та коефіцієнти. 30

3.2. Інтегральні 4-вимірні структурні властивості 31

3.3. Розподілені структурні властивості 33

3.4. Представлення структурних властивостей за допомогою гістограмних моделей. 35

3.5. Формування ключів образів. 38

3.6. Кластеризація ключів образів. 38

Розділ 4. Застосування алгоритму триступеневої кластеризації 42

4.1. опрацювання зображень кластеризацією з метою пошуку ключів образів. 42

4.2. Пошук зображень за їх ключами. 43

4.3. Аналіз зображень структури і поверхні 52

Розділ 5. Ієрархічна кластеризація – інструмент екстракції данх. 57

5.1. Критерії та методи кластеризації 57

5.2. Керування точністю та складністю алгоритму кластеризації 63

2.3. Багатокаскадна декомпозиція даних. 65

2.4. Двокаскадна декомпозиція простору. 70

2.5. Дослідженння каскадної декомпозиції даних та простору. 72

Література. 77

Вступ

Задачі індексування та пошуку зображень на основі їх вмісту (Content-based image retrieval − CBIR) у великих сховищах даних із мільйонами образів є актуальними в сучасних інформаційних системах. Ефективна класифікація зображень зменшує час опрацювання зображень фільтруванням зайвих класів образів під час пошуку подібних до них. На сьогодні такі задачі стають все більш актуальними у сферах розпізнавання образів. Тому існує потреба у аналізі принципово нових методів декомпозиції та індексування, що дозволить за виділеними характеристиками образу ефективно здійснювати пошук у сучасних сховищах даних та їх розпізнавати. Однією із цілей в роботі є прискорення екстракції характеристик заданого образу.

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

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

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

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

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

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

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

Наявність ієрархічного дерева дозволяє:

1) розкладати образи на так звані шари з підобразами – фрагментами образів та розглядати постановки задач розпізнавання на різних рівнях дерева;

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