Алгоритми і апаратно-програмні засоби підвищення ефективності пошуку зображень в графічних базах даних

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

АВТОРЕФЕРАТ

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

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

Робота виконана в Державному вищому навчальному закладі “Донецький національний технічний університет” Міністерства освіти і науки України

Науковий керівник:

доктор технічних наук, професор Башков Євген Олександрович, проректор із наукової роботи, завідувач кафедри “Прикладна математика і інформатика” Державного вищого навчального закладу “Донецький національний технічний університет” МОН України, м. Донецьк

Офіційні опоненти:

доктор технічних наук, професор Погорілий Сергій Дем'янович, заступник завідувача кафедри “Напівпровідникова електроніка” Київського національного університету ім. Тараса Шевченка (м.Київ)

кандидат технічних наук, доцент Шевцов Дмитро Валерійович, доцент кафедри “Прикладна математика і теорія систем управління” Донецького національного університету (м.Донецьк)

Провідна установа: Інститут космічних досліджень Національної академії наук України і Національної космічної агенції України (м. Київ)

З дисертацією можна ознайомитись у бібліотеці Державного вищого навчального закладу “Донецький національний технічний університет” за адресою: 83000, м. Донецьк, вул. Артема, 58, корп. 2

Автореферат розісланий _6 вересня 2006 року

Вчений секретар спеціалізованої вченої ради К11.052.03 кандидат технічних наук, доцент Г.В.Мокрий

Загальна характеристика роботи

Актуальність теми. Розробка нових технічних засобів, що дозволяють представляти інформацію у вигляді зображень, привела до того, що робота з такими даними знаходиться в центрі уваги багатьох дослідників. З розповсюдженням Internet спостерігається тенденція до накопичення зображень і до створення баз даних (БД) зображень. Залежно від області застосування в такі БД включаються як довільні зображення, так і зображення обмеженого класу, і дуже актуальною для таких БД є задача пошуку зображень, що візуально подібні до заданого зразка (цей процес називають пошуком за вмістом зображень, або контекстним пошуком).

Існує ряд практичних реалізацій контекстного пошуку зображень в графічних базах даних. Найбільш вдалими є система QBIC (розробка фірми IBM) і системи WebSeek та VisualSeek (розробки Колумбійського університету, США). Пошук зображень на основі їх вмісту за технологією IBM реалізовано також на сайті Державного Ермітажу (Росія). Вказані проекти не досить якісно виконують пошук, і головним недоліком всіх практичних реалізацій цього підходу є заміна пошуку сортуванням всієї БД за зменшенням схожості зображень зі зразком, і, як наслідок, низька швидкодія і неможливість отримання відповіді на запит в реальному масштабі часу.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках держбюджетних тем № Г-9-95 “Архітектура паралельної обчислювальної системи для синтезу високоякісних зображень в реальному часі” (№ держреєстрації 0195U009057), № Г-13-2000 “Архітектура обчислювальних систем для комп'ютерного синтезу і пошуку зображень в реальному часі” (№ держреєстрації 0100U001049), № Д-2-2003 “Методи, алгоритми і архітектури реального часу для пошуку, генерації, тривимірної реконструкції і моделювання зображень складних об'єктів” (№ держреєстрації 0103U001322), № Д -2-06 “Ефективні алгоритми індексації та виконання запитів в глобальних графічних і відео- базах даних, обробки та генерації зображень“ (№ держреєстрації 0106U001265), у яких здобувач приймала участь як виконавець.

Мета та завдання досліджень. Мета роботи полягає в прискоренні і підвищенні якості пошуку зображень у графічних БД шляхом розробки нових алгоритмічних і апаратно - програмних засобів.

Для досягнення цієї мети необхідно вирішити наступні основні задачі:

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

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

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

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

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

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

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

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

Наукова новизна отриманих результатів полягає в наступному.

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

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

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

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

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

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

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

Практичне значення отриманих результатів:

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

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

Результати роботи використано НВП “АМІ” (м. Донецьк) при розробці цифрової системи безпеки для реалізації швидкого пошуку по відео архіву, зберігання інформації, її оперативного пошуку і аналізу. Запропоновані методи пошуку зображень на основі їх колірного вмісту і розроблені у відповідності з ними алгоритми і апаратно - програмні рішення впроваджено у навчальний процес у курсах “Комп'ютерний синтез і обробка зображень” і “Машинна графіка і діалогові системи” на кафедрі прикладної математики і інформатики ДонНТУ.

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

Апробація результатів роботи. Результати досліджень і основні положення роботи були повідомлені і обговорені:

І, II, III, IV Міжнародних науково-практичних конференціях "Людина і космос" (м. Дніпропетровськ, 1999, 2000, 2001, 2002 роки);

12-й Міжнародній конференції ГрафиКон'2002 (м. Нижній Новгород, Росія, 2002 рік);

4-й Міжнародній науково-технічній конференції "Кібернетика і технології XXI століття" (м. Воронеж, Росія, 2003 рік);

Всеросійській науково-технічній конференції з міжнародною участю "Комп'ютерні технології в інженерній і управлінській діяльності". (м. Таганрог, Росія, 2002 рік);

ІІ науково-практичній конференції "Донбас-2020: наука і техніка- виробництву" (м. Донецьк, 2004 рік);

Всеросійській науково-технічній конференції з міжнародною участю "Комп'ютерні і інформаційні технології в науці, інженерії і управлінні" (м. Таганрог, 2004 рік);

І Міжнародній науково-технічній конференції "Моделювання і комп'ютерна графіка" (м. Донецьк, 2005 рік).

Публікації. Основні результати дисертаційної роботи опубліковані в 18 наукових працях, з них 8 статей у виданнях, включених в перелік ВАК України, 10 публікацій в збірках матеріалів конференцій, 11 наукових праць написані без співавторів.

Структура і обсяг дисертаційної роботи. Дисертація складається з вступу, п'яти розділів, висновків, списку використаних джерел з 99 найменувань, і додатку. Повний обсяг дисертації складає 176 сторінок друкарського тексту, з них 164 сторінки основного тексту, містить 58 рисунків і 12 таблиць (у тому числі 18 - на окремих сторінках).

Основний зміст роботи

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

Задача пошуку зображень за зразком полягає в формуванні послідовності зображень з БД, які візуально подібні зразку і розташовані в порядку зменшення цієї схожості. Місце кожного зображення в такій впорядкованій послідовності визначається за результатами виконання алгоритму сортування, вихідними даними для якого є числові характеристики ступеня подібності до зразку пошуку кожного зображення з БД. При цьому кожне зображення Pk, k=1, 2..V, є матрицею M*N, елементи якої містять кольори відповідних пікселів зображення; M і N - ширина і висота зображення відповідно, а вміст кожного зображення Pk характеризується скалярною або векторною величиною Fk, k=1,2..V. Існує також зображення - зразок пошуку, колірний вміст якого характеризує аналогічна величина Fзр.

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

1) за сферою застосування;

2) за колірною гаммою оброблюваних зображень;

3) за використовуваними ознаками вмісту зображення;

4) за структурою ознак вмісту зображення;

5) за врахуванням просторової інформації;

6) за типом бази даних, що використовується.

За результатами виконаного аналізу сформована узагальнена структура системи пошуку зображень на основі їхнього вмісту, що показана на рис. 1.

На підставі проведеного аналізу сформульовані задачі дослідження.

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

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

При пошуку за колірним вмістом порівняння виконується як з урахуванням, так і без урахування просторової інформації. При цьому для представлення колірного вмісту зображення використовуються гістограмні ознаки, причому в першому випадку вміст зображення описується традиційною колірною гістограмою, що характеризує розподіл кольорів в зображенні, а в другому для опису колірного вмісту обчислюється гістограма, аналогічна текстурній, але з урахуванням співвідношення кольорів пар пікселів, а не тільки складової яскравості. Отриману таким чином характеристику вмісту зображення будемо називати двовимірною колірною гістограмою (2D-колірною гістограмою). Імовірно, використання такої характеристики може бути особливо ефективним для кольорових зображень, що мають наступні властивості: з одного боку, їх вміст можна назвати довільним, з іншого боку, рисунок характеризується певною повторюваністю. Прикладом таких зображень є зразки тканин, шпалер і т.п., а також зображення кольорових текстур. Очевидно, що для порівняння таких зображень слід ураховувати як просторову інформацію, так і інформацію про кольори точок. Традиційна колірна гістограма зображення є вектором H [1.. Cmax], кожен елемент якого обчислюється за формулою (1):

(1)

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

Запропонована в роботі характеристика колірного вмісту зображення - 2D- колірна гістограма - будується як двовимірний масив Cmax*Cmax, де Cmax - кількість кольорів базового набору, який використовується на етапі квантування кольорів. Кожен елемент 2D -колірної гістограми спочатку дорівнює кількості пар пікселів з заданим співвідношенням кольорів навколо точки згідно з заданим шаблоном. Далі виконується нормування елементів 2D -колірної гістограми, що дозволяє порівнювати зображення різного розміру. Після нормування кожен елемент 2D -колірної гістограми буде характеризувати ймовірність присутності в зображенні пари точок, що мають задані кольори.

Основні етапи контекстного пошуку зображень:

1. Квантування кольорів або рівнів яскравості (Q-quantization). Даний етап полягає в заміні кольорів (значень яскравості) найбільш близькими значеннями з базового набору, за яким надалі обчислюється гістограмна ознака.

2. Побудова гістограмної ознаки вмісту зображення (H-histogram).

3. Порівняння зображень (C-сomparison). Даний етап виконується шляхом обчислення ступенів схожості гістограмних ознак зображення-зразка і всіх зображень з БД.

4. Сортування (S) зображень за зменшенням значень ступеня схожості, що обчислюються на етапі C.

При занесенні нового зображення в БД для нього послідовно виконуються етапи Q і H. При пошуку, коли зразком є зображення з БД, виконуються етапи C і S. Якщо ж зразком пошуку є нове зображення то виконуються етапи Q, H, C і S.

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

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

Таблиця 1 Область значень різних величин для порівняння колірних гістограм

Величина	Область значень при використанні нормалізованих гістограм
Кон'юнкція гістограм (D1)
Відстань Евкліда (D2)
Косинусна відстань (D3)
Квадратична відстань (D4)

Автором запропоновано використовувати для порівняння гістограмних ознак вмісту зображення коефіцієнт їх кореляції, що обчислюється за формулою (2):

(2)

де cov(H1,H2)- коваріація гістограм H1 і H2,

у(H2) і у(H2) - середньоквадратичне відхилення елементів гістограм H1и H2 відповідно.

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

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

Оскільки для різних підходів час квантування кольорів (яскравостей) до базового набору і сортування співпадає, оцінювався сумарний час виконання етапів H і C (для визначеності розмір зображень обмежений до 512*512 пікселів).

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

В третьому розділі - “Експериментальна оцінка якості пошуку зображень з використанням покращених алгоритмів” - виконана експериментальна оцінка якості пошуку згідно з запропонованими методиками.

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

У всіх випадках при побудові гістограмних ознак виконувалось рівномірне квантування кольорів в RGB - просторі до 64 кольорів.

Для розробки програм використовувалось середовище візуального програмування Delphi 5.0.

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

Для оцінки якості пошуку зображень за конкретним алгоритмом використовувались значення характеристик recall (R) і precision (P). Характеристика P оцінює долю зображень, що відповідають запиту, серед всіх зображень, виведених як результати, а характеристика R показує, яка частина зображень, що відповідають запиту, була включена в число результуючих. Очевидно, що для якісного алгоритму значення цих характеристик мають бути як можна ближчими до одиниці, і з двох алгоритмів, за інших рівних умов, слід обирати той, для якого вказані характеристики мають більші значення.

Для експериментів застосовувалася методика, відповідно до якої для кожного зображення будується характеристика його вмісту. Далі, кожне із зображень, що містяться в базі даних, використовується як зразок пошуку для отримання набору зображень, розташованих в порядку зменшення схожості зі зразком. Після кожного циклу пошуку обчислюються значення характеристик recall (R) і precision (P). Для аналізу ефективності алгоритму використовуються середні значення вказаних характеристик, обчислені після того, як всі зображення, що містяться в БД, були використані як зразки.

Для реалізації даної методики виконується попередня розмітка всієї бази даних, що містить V зображень. В ході цієї розмітки формується матриця M [VxV], кожен елемент якої визначається таким чином:

Очевидно, застосування даної методики виправдане лише в тому випадку, якщо у складі БД є групи зображень, які візуально схожі між собою, і якщо результуючий набір зображень якимось чином обмежений. Назвемо групи зображень, які візуально схожі між собою, кластерами, кожний з яких характеризується значенням N- потужністю кластера БД, до якого належить зразок пошуку (зображення з номером i). Потужність кластера визначається як

.

Шляхом обмеження результуючого набору зображень потужністю найбільшого кластера БД були отримані криві, що відображають зміни значень характеристик якості пошуку.

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

В роботі для обмеження результуючого набору зображення використані з кроком 0.1 значення коефіцієнта кореляції, що лежать в області його значень [1; -1].

При коефіцієнті кореляції, рівному 0.8, доля зображень, які відповідають запиту, серед всіх включених в результуючий список, складає усього 0.3, тобто навіть при такому обмеженні результати характеризуються значною надмірністю. Але аналіз рисунка 6 показує, що при цьому ж пороговому значенні є деяка частина зображень, схожих зі зразком і не включених в результуючий набір (приблизно 2 %), тому встановлювати порогове значення коефіцієнта кореляції вище 0.8 недоцільно.

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

У п'ятому розділі - “Моделювання роботи спеціалізованої обчислювальної системи для контекстного пошуку зображень” - виконано дослідження запропонованої обчислювальної системи засобами математичного і імітаційного моделювання.

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

Висновки

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

1. Сформульована в загальному вигляді задача пошуку зображень на основі їхнього вмісту в базі даних, виконана класифікація систем пошуку зображень за зразком у великих базах даних. 2. Вперше запропоновано для оцінки колірного вмісту зображення використовувати 2D- колірну гістограму, що дозволяє певною мірою врахувати просторову інформацію. 3. Вперше запропоновано використання коефіцієнта кореляції гістограмних ознак зображень для порівняння їх колірного вмісту. 4. Розроблено метод пошуку зображень в БД за їх колірним вмістом, що дозволяє без істотних втрат часу врахувати при описі вмісту зображення просторову інформацію, а також обмежити результати пошуку і уникнути сортування всієї БД. 5. Запропонована і збалансована структура спеціалізованої конвейєрної обчислювальної системи для пошуку зображень. Розроблені алгоритми функціонування підсистем обчислювальної системи, обрана найбільш раціональна організація кожної з підсистем, запропоновані структури процесорних елементів, що реалізують обчислення, передбачувані алгоритмами, з мінімальними витратами часу.

Основні результати дисертаційної роботи опубліковані в наступних публікаціях

1. Шозда Н.С. Сравнительный анализ систем контекстного поиска изображений // Наукові праці Донецького державного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка", випуск 6. -Донецьк; ДонДТУ.- 1999. - С. 151-156.

2. Башков Е.А., Шозда Н.С. Использование специализированной ЭВМ для решения задачи контекстного поиска изображений // Наукові праці Донецького державного технічного університету. Серія: "Проблеми моделювання та автоматизації проектування динамічних систем", випуск 10. -Донецьк; ДонДТУ.- 1999. - С. 247-252.

3. Башков Е.А., Шозда Н.С. Алгоритмы дискретизации цветового пространства и их использование в контекстном поиске изображений. // Наукові праці Донецького державного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка", випуск 15. -Донецьк; ДонДТУ.- 2000. - С.192-197.

4. Шозда Н.С. Ускорение вычислений на этапе сравнения цветовых гистограмм в процессе контекстного поиска изображений // Наукові праці Донецького державного технічного університету. Серія: "Проблеми моделювання та автоматизації проектування динамічних систем, випуск 29. - Севастополь -Донецьк. - 2001. С. 129-134.

5. Шозда Н.С. Применение специализированной ЭВМ для решения задачи контекстного поиска изображений. // Додаток до журналу "Космічна наука і технологія" - 2001. - Т. 7, №1. - С. 109-111.

6. Шозда Н.С. Поиск изображений по текстурным признакам в больших базах данных. // Наукові праці Донецького державного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка", випуск 39. - Донецьк, ДонДТУ. -2002. - С.182-187.

7. Костюкова Н.С. Анализ эффективности функционирования конвейерной вычислительной системы для поиска изображений в базе данных по их содержимому. // Наукові праці Донецького національного технічного університету. Серія: "Проблеми моделювання та автоматизації проектування динамічних систем", випуск 78. - Донецьк, ДонНТУ. - 2005. - С.183-191.

8. Костюкова Н.С. Оценка эффективности поиска изображений. // Наукові праці Донецького національного технічного університету. Серія: "Інформатика, кібернетика та обчислювальна техніка", випуск 93. - Донецьк, ДонНТУ. - 2005. - С. 22-32.

9. Шозда Н.С. Поиск в базе данных изображений земной поверхности. // Збірник тез Всеукраїнської молодіжної науково-практичної конференції "Людина і космос". - Дніпропетровськ: НЦАОМУ, - 1999. - С.187

10. Шозда Н.С., Башков Е.А. Применение специализированной ЭВМ для решения задачи контекстного поиска изображений. // Збірник тез 2-ї Всеукраїнської молодіжної науково-практичної конференції з міжнародною участю "Людина і космос": - Дніпропетровськ, НЦАОМУ, - 2000. - С.272

11. Шозда Н.С. Модифицированный алгоритм поиска в базе данных изображений на основе их цветового содержимого. // Збірник тез 3-ї Міжнародної молодіжної науково-практичної конференції "Людина і космос", присвяченої 40-річчю першого польоту людини в космос: - Дніпропетровськ, НЦАОМУ, - 2001. - С.298.

12. Шозда Н.С. Сравнение текстурных гистограмм при поиске изображений в больших БД. // Збірник тез 4-ї Міжнародної молодіжної науково-практичної конференції "Людина і космос", присвяченої пам'яті академіка М.К.Янгеля - Дніпропетровськ, НЦАОМУ, - 2002. - С.405.

13. Башков Е.А., Шозда Н.С. Поиск изображений в больших БД с использованием коэффициента корреляции цветовых гистограмм. // Труды 12-й Международной конференции “ГрафиКон'2002”. - Нижний Новгород, - 2002. - С. 358-361.

14. Е.А.Башков, Н.С.Костюкова. Модифицированный алгоритм поиска изображений по их цветовому содержимому. // Материалы 4-й международной научно- технической конференции “Кибернетика и технологии XXI века”. - Воронеж, - 2003 - С. 460-472.

15. Е.А.Башков, Н.С.Шозда. Модифицированный алгоритм поиска близких по цветовым характеристикам изображений. // Материалы всероссийской научно- технической конференции с международным участием “Компьютерные технологии в инженерной и управленческой деятельности”. Известия ТРТУ №2. Тематический выпуск “Компьютерные технологии в инженерной и управленческой деятельности”. - Таганрог:ТРТУ, - 2002. - .С.114-116.

16. Костюкова Н.С. Модифицированный алгоритм контекстного поиска изображений в базах данных. // Материалы 2-й научно-практической конференции “Донбасс-2020: наука и техника- производству”. - Донецк: ДонНТУ, - 2004. - С. 558-565.

17. Костюкова Н.С. Использование 2D- цветовых гистограмм для представления цветового содержимого изображений. // Материалы всероссийской научно- технической конференции с международным участием “Компьютерные и информационные технологии в науке, инженерии и управлении”. Известия ТРТУ №1. Тематический выпуск “Компьютерные и информационные технологии в науке, инженерии и управлении”. - Таганрог: ТРТУ, - 2005. - С.74-78

18. Костюкова Н.С. Современные системы поиска изображений на основе их содержимого. // Материалы первой международной научно- технической конференции “Моделирование и компьютерная графика”. - Донецк: ДонНТУ, - 2005. - С. 49- 54.

Особистий внесок здобувача в публікаціях: [2] - запропоновано склад процесорних елементів для підтримки окремих етапів контекстного пошуку зображень; [3] - виконано аналіз різних алгоритмів дискретизації кольорів, висновки щодо застосовності різних методів дискретизації в процесі контекстного пошуку зображень; [10] - сформульовано структури підсистем обчислювальної системи і виконано оцінки їх швидкодії; [13] - виконано загальну постановку задачі, аналіз областей значень метрик для порівняння гістограмних ознак; [14, 15] - запропоновано модифікований алгоритм і виконано експериментальну перевірку його придатності для рішення задачі.

Анотація

Костюкова Н.С. Алгоритми і апаратно- програмні засоби підвищення ефективності пошуку зображень в графічних базах даних.- Рукопис.

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

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

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

Аннотация

Костюкова Н.С. Алгоритмы и аппаратно- программные средства повышения эффективности поиска изображений в графических базах данных. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13-Вычислительные машины, системы и сети. Государственное высшее учебное заведение “Донецкий национальный технический университет”, Донецк, 2006.

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

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

Наиболее важными являются следующие результаты:

В общем виде сформулирована задача поиска изображений по образцу в графических базах данных.

Получена возможность ограничения результирующего набора изображений при использовании предложенного в работе алгоритма..

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

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

Annotation

Kostyukova N.S. Algorihtms, software and hardware tools for image retrieval effectiveness increase in large graphical databases.- Manuscript.

Thesis for candidate's degree in technical science by speciality 05.13.13-Computer, computing systems and networks. - State Higher Education Establishment “Donetsk national technical university”, Donetsk, 2006.

The thesis is devoted to the problem of the modified algorithm for image retrieval in the large databases and specialized computing system architecture for effective realization of this algorithm. The analysis of the existing image retrieval systems is performed, their classification on some attributes is executed, necessity for the modified algorithm and architectural acceleration of its performance is proved. The modified algorithms of the search, allowing to carry out search of images to textural attributes, and also on color contents with the account an arrangement of colors inside the image and without them are offered. Texture, color histograms and also 2-D color histograms are used for image content description. For its comparison the correlation factor is applied. Using of correlation factor is enabled to limit a retrieved images set. Specialized computing system architecture for modified algorithms realization is offered. This architecture is analytically proved. Mathematical and imitation models of the proposed computing system are described. This models confirmed the accepted decisions.

Размещено на Allbest.ru

...