МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ВОВК ОЛЬГА ЛЕОНІДІВНА
УДК 681.3
СТАТИСТИЧНІ МЕТОДИ КЛАСТЕРИЗАЦІЇ ДЛЯ СИСТЕМ КОНТЕКСТНОГО ПОШУКУ ЗОБРАЖЕНЬ
05.13.06 – автоматизовані системи управління та прогресивні інформаційні технології
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Донецьк- 2006
Дисертацією є рукопис.
Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України.
Науковий керівник – |
доктор технічних наук, професор
Башков Євген Олександрович,
проректор із наукової роботи, завідувач кафедри “Прикладна математика і інформатика”, Донецький національний технічний університет.
Офіційні опоненти: |
доктор технічних наук, професор
Скобцов Юрій Олександрович,
завідувач кафедри “Автоматизовані системи управління”, Донецький національний технічний університет.
кандидат технічних наук, старший науковий співробітник
Михайлюк Антон Юрійович,
доцент кафедри “Спеціалізовані комп’ютерні системи”, НТУУ “Київський політехнічний інститут”.
Провідна установа – | Інститут космічних досліджень НАНУ та НКАУ, відділ космічних інформаційних технологій, м. Київ.
Захист відбудеться 09.02. 2007 р. о 14_годині на засіданні спеціалізованої вченої ради К 11.051.08 Донецького національного університету за адресою: 83055, м. Донецьк, вул. Університетська, 24, корп. 4, ауд. 416.
З дисертацією можна ознайомитись у бібліотеці Донецького національного університету за адресою: 83055, м. Донецьк, вул. Університетська, 24, корп.
Автореферат розісланий 08.12.2006р.
Вчений секретар
спеціалізованої вченої ради К 11.051.08
кандидат технічних наук, доцент Д.В. Шевцов
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Постійне збільшення кількості галузей застосування інформаційних технологій призвело до накопичення великих обсягів візуальної інформації. На сучасному етапі розвитку обчислювальних засобів збереження електронних колекцій зображень не становить проблему з технічної точки зору. Особливу увагу дослідники приділяють розв’язанню проблеми забезпечення ефективного змістового пошуку в базах даних зображень. Найбільш часто такі задачі вирішуються при контекстному пошуку зображень в електронних колекціях, а також при змістовній класифікації зображень (медична діагностика, віддалене спостереження, аналіз документів).
Найбільш простий та розповсюджений засіб пошуку зображень в базах даних зображень – пошук за текстовими описами, що асоціюються із зображеннями. Не кожне зображення можна однозначно описати за допомогою текстових асоціацій (наприклад, зображення абстракцій), тому дана технологія застосовується тільки для пошуку серед зображень обмежених класів. Менш обмеженими є методи контекстного пошуку, що базуються на автоматичному аналізі колірних характеристик пікселів зображень. Серед них можна виділити методи, які базуються на аналізі всього зображення цілком (методи колірних та текстурних гістограм, методи пошуку за колірним плануванням) та методи, що ґрунтуються на порівнянні візуальних примітивів окремих груп пікселів (регіонів, областей, кластерів). Однак коректне задоволення запитів пошуку зображень необмежених класів можливе тільки за умови використання методів аналізу примітивів кластерів зображень у зв’язку з такими недоліками інших методів: відсутність стабільних результатів при масштабуванні зображень та повороті об’єктів усередині зображень, залежність результатів від варіацій параметрів освітленості зображень, неможливість виділення характеристик форми об’єктів без виділення самих об’єктів зображень.
Таким чином, найбільш перспективними для наукових досліджень методами контекстного пошуку можна вважати методи, що базуються на порівнянні характеристик кластерів зображень. Однак ефективність цих методів прямо пов’язана з якістю виділення аналізованих кластерів. Одним з основних шляхів вирішення задачі аналізу регіонів зображень є використання статистичних методів кластеризації для групування пікселів зображень.
Значний внесок у дослідження та розвиток статистичних методів кластеризації для контекстного пошуку зображень зроблений групою американських дослідників під керівництвом Дж.З. Ванга. В Україні розпізнаванням зображень займаються М.І. Шлезінгер, Є.П. Путятін. Розробці ефективних методів змістового пошуку візуальної інформації присвячено фундаментальні роботи А. Гупти, С. Карсона, Дж.П. Ейкінса, Н.С. Байгарової, Ю.О. Бухштаб.
Отже, виділення регіонів зображень за допомогою статистичних методів кластеризації є актуальною науково-технічною проблемою, вирішення якої визначає побудову ефективного механізму контекстного пошуку в електронних колекціях зображень.
Зв’язок дисертаційної роботи з планами науково-дослідних робіт. Дисертаційна робота пов’язана з планами науково-дослідної та навчальної роботи Донецького національного технічного університету та виконувалась у межах держбюджетних тем № Д-2-03 “Методи, алгоритми та архітектури реального часу для пошуку, генерації, тривимірної реконструкції й моделювання зображень складних об'єктів” (реєстраційний номер 0103U001322) та № Д-2-06 “Методи, алгоритми та архітектури реального часу для пошуку, статистичної кластеризації, генерації, тривимірної реконструкції та моделювання зображень складних об’єктів” (реєстраційний номер 0106U001265).
Мета та задачі дослідження. Мета роботи полягає в розробці ефективного, з точки зору витрат часу, методу виділення регіонів зображень необмежених класів на базі статистичних методів кластеризації об’єктів, побудова на його базі системи змістового пошуку зображень в базах даних візуальної інформації.
Для досягнення поставленої мети було визначено та вирішено наступні головні задачі:
1.
Проведення теоретичного аналізу існуючих методів контекстного пошуку зображень в електронних колекціях (зокрема вивчення статистичних методів розпізнавання регіонів зображень) з метою виділення найбільш перспективних напрямків дослідження. Розгляд основних оцінок контекстного пошуку зображень у базах даних, а також основних оцінок якості кластеризації зображень для подальшого порівняння методів, що аналізуються в роботі.
2.
Розробка швидкодіючого методу виділення кластерів зображень на базі існуючих статистичних методів кластеризації з урахуванням специфіки об’єктів, що кластеризуються. Створення експериментальної програмної системи кластеризації для порівняння методів виділення регіонів зображень.
3.
Адаптація створеного методу кластеризації для побудови ефективного механізму контекстного пошуку зображень у базах даних. Розробка експериментальної програмної системи пошуку.
4.
Оцінка часової та просторової складності та характеристик якості методів виділення кластерів зображень, що аналізуються; дослідження способів збільшення швидкодії запропонованого в роботі методу для кластеризації набору зображень.
5.
Оцінка основних показників якості контекстного пошуку зображень в електронних колекціях для підтвердження достовірності запропонованого методу.
Об’єктом дослідження дисертаційної роботи є цифрові зображення, які задано матрицею колірних характеристик.
Предметом дослідження є статистичні методи кластеризації об’єктів для побудови системи змістового пошуку зображень.
Методи дослідження. Основними методами дослідження є: теорія цифрової обробки зображень та методи статистичного кластерного аналізу (для розробки методу кластеризації зображень); методи контекстного пошуку зображень (для побудови механізму контекстного пошуку кластеризованих зображень); теорія проектування комп’ютерних систем; теорія та методи розпаралелювання алгоритмів; методи об’єктно-орієнтованого програмування та методи доступу до баз даних (для створення експериментальних систем).
Наукова новизна одержаних результатів. На базі проведених досліджень вирішено важливу науково-технічну задачу – створено систему контекстного пошуку кластеризованих зображень в електронних колекціях. При цьому отримано такі нові результати:
-
вперше запропоновано бітову маску взаємозв’язків та рангів колірних характеристик центрів кластерів, яка використовується для первісного розділення об’єктів за кластерами та як критерій завершення процедури кластеризації;
-
на базі методів статистичної кластеризації розроблено статистичний ієрархічний агломеративний (СІА) метод кластеризації зображень;
-
введено умову “порівняльності” кластерів для припинення процедури кластеризації (в основі якої підрахунок кількості еквівалентних ненульових біт маски взаємозв’язків та рангів);
-
запропоновано для усунення кластерів незначного розміру (шумів, дефектів зображень) у першу чергу обробляти (об’єднувати) кластери з мінімальною площею;
-
проведено оцінку можливості збільшення показників швидкодії запропонованого методу шляхом розробки розподіленої системи кластеризації;
-
запропоновано враховувати значимість (пріоритетність) характеристик виділених кластерів, що аналізуються, у процесі пошуку (характеристик кольору, текстури, форми, розташування).
Обґрунтованість і достовірність наукових положень, висновків і рекомендацій. Обґрунтованість та достовірність результатів, отриманих у дисертації, підтверджується коректним застосуванням теорії цифрової обробки зображень, статистичних методів кластерного аналізу, методів контекстного пошуку зображень, теорії проектування комп’ютерних систем.
Практичне застосування розробленого статистичного ієрархічного агломеративного методу для виділення регіонів зображень та як етапу для контекстного пошуку зображень підтверджує його достовірність .
Практичне значення отриманих результатів. Запропонований метод виділення регіонів зображень, який в експериментах на аналізованому наборі показав у середньому прискорення в 10,1 рази без втрати в якості (порівняння проводилося з методом k-середніх), дозволяє на практиці:
1. Ефективно виконувати розбивку зображень на однорідні як за колірною подібністю регіони (для контекстного пошуку зображень необмежених класів), так і для виділення специфічних областей (медична діагностика, аналіз механічних пошкоджень металевих поверхонь, віддалене спостереження).
2. Створити систему контекстного пошуку зображень, призначену для знаходження зображень необмежених класів; а також може застосовуватися працівниками музеїв, архівів, бібліотек (для пошуку інформації, що цікавить відвідувачів), створювачами логотипів (для перевірки унікальності розробленого логотипу), дизайнерами (для оформлення сайтів, статей).
3. Модернізувати цифрову систему безпеки “Drakar” (НПП “АМІ”, Донецьк), у якій СІА метод використовується для виділення об’єктів зображень окремих знімків відеоінформації, а побудована на базі запропонованого методу система контекстного пошуку – для пошуку окремих знімків відеоінформації.
4. Використовувати результати дисертаційної роботи в навчальному процесі кафедри прикладної математики та інформатики ДонНТУ у курсах “Комп’ютерний синтез і обробка зображень” і “Машинна графіка і діалогові системи”.
Особистий внесок здобувача. Основні результати, які виносяться на захист, отримано здобувачем самостійно та опубліковано в 14 наукових працях. При цьому роботи [2,3,5,6,9-12,14] написано самостійно. У роботах, що написано у співавторстві, автору належать: [1] – метод класифікації засобів опису текстурних властивостей зображень, [4,7,13] – статистичний ієрархічний агломеративний метод кластеризації зображень, [8] – аналіз існуючих технологій для розрахунку властивостей зображень.
Апробація роботи. Основні результати дисертаційних досліджень доповідались та обговорювались на V Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології” (Національний технічний університет України “Київський політехнічний інститут”, Київ, Україна, 2003), II науково-практичній конференції “ДОНБАС-2020: наука і техніка – виробництву” (Донецький національний технічний університет, Донецьк, Україна, 2004), Всеросійській науково-технічній конференції з міжнародною участю “Компьютерные и информационные технологии в науке, инженерии и управлении” (Таганрозький державний радіотехнічний університет, Таганрог, Росія, 2004), VI Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології” (Національний технічний університет України “Київський політехнічний інститут”, Київ, Україна, 2004), XIV Міжнародній конференції з комп’ютерної графіки та зору “GraphiCon’2004” (Московський державний університет, Москва, Росія, 2004), XI Міжнародній конференції з автоматичного управління “Автоматика – 2004” (Національний університет харчових технологій, Київ, Україна, 2004), VI Міжнародному науково-практичному семінарі “Практика і перспективи розвитку партнерства у сфері вищої школи” (Донецький національний технічний університет, Донецьк, Україна, 2005), V Міжнародній науковій конференції “Інтелектуальний аналіз інформації” (Національний технічний університет України “Київський політехнічний інститут”, Київ, Україна, 2005), I Міжнародній науково-технічній конференції “Моделювання та комп’ютерна графіка” (Донецький національний технічний університет, Донецьк, Україна, 2005).
Впровадження результатів роботи.
Результати, отримані у ході виконання дисертаційної роботи, використовуються в навчальному процесі кафедрою прикладної математики та інформатики Донецького національного технічного університету у викладанні дисциплін “Комп’ютерний синтез і обробка зображень ” та “ Машинна графіка і діалогові системи ”.
У процесі модернізації цифрової системи безпеки “Drakar” НПП “АМІ” впроваджувалися запропоновані в дисертаційної роботі методи кластеризації та змістового пошуку зображень.
Публікації. Основні результати дисертаційного дослідження викладено в 14 публікаціях, серед яких: 7 – у виданнях, що входять до переліку ВАК України [1-7], 7 – у збірниках матеріалів наукових конференцій та семінарів [8-14].
Структура та обсяг роботи. Дисертація складається зі вступу, 4 розділів, переліку використаної літератури з 124 джерел та 4 додатків. Загальний обсяг дисертації складає 137 сторінок, ілюстрацій – 58, таблиць – 15.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У першому розділі подається огляд існуючих методів і систем контекстного пошуку зображень у базах даних, у результаті критичного аналізу яких, як напрямок досліджень, обрано методи змістового пошуку, що базуються на порівнянні характеристик регіонів зображень. Розглянуто засоби оцінки якості контекстного пошуку зображень.
Стисло наведено основні методи розпізнавання однорідних областей зображень (для розрахунку їх властивостей при контекстному пошуку), серед яких виділені методи статистичної кластеризації. Досліджено можливості використання існуючих груп методів статистичної кластеризації об’єктів для виділення регіонів зображень за колірними характеристиками. Найбільш розповсюдженим методом розділення зображень на регіони виділяється метод k-середніх. Однак проведений аналіз недоліків методу k-середніх зумовив виділення невирішених цим методом питань, пов’язаних з кластеризацією зображень, а саме: відсутність однозначного критерію закінчення процедури кластеризації, наявність великої кількості нерезультативних перегрупувань об’єктів між кластерами. Це дозволило сформувати головну проблему дослідження – розробка методу статистичної кластеризації з діючим критерієм вибору кількості кластерів. Як найбільш придатна для вирішення цієї задачі пропонується ієрархічна технологія кластеризації. Для можливості порівняння конкуруючих статистичних методів розглянуті основні оцінки якості виділення кластерів зображень.
Визначено засоби вдосконалення показників швидкодії обчислювальних систем – розглянуто існуючі багатопроцесорні архітектури та характеристики їх ефективності.
Другий розділ присвячений визначенню математичної моделі задачі контекстного пошуку зображень та створенню статистичного ієрархічного агломеративного методу кластеризації для розпізнавання регіонів зображень.
На вхід системи контекстного пошуку зображень подається база даних Т, що складається з n зображень (T={t1,t2,…,tn}), та зразок пошуку to.
Зображення ti має розмір wi?hi пікселів. Кожному пікселю pijk зображення ti відповідає три колірних складових pijk={rijk, gijk, bijk}, що відображають інтенсивності червоного, зеленого та синього кольорів відповідно, крім того j, k відповідають координатам пікселя зображення (,
ti =pijk={rijk, gijk, bijk} |, , , | (1)
Зображення зразок пошуку to можна визначити як:
to =={} |, , . | (2)
В основі порівняння зображення to та зображень ti бази даних – відстань di D між характеристиками Сi={ci1, ci2, …,ciM} кожного із зображень tiT та характеристиками зображення зразка Со={}. Для обчислення di найбільш розповсюдженою є середня Евклідова відстань.
Набір відстаней D упорядковується за зростанням. Результатом контекстного пошуку є набір R={ti | }, де L – задана користувачем кількість результатів контекстного пошуку. Слід зазначити, що кожному зображенню ti відповідає відстань di, та при упорядкуванні за зростанням елементів множини D відбувається відповідне упорядкування елементів множини T.
При обчисленні характеристик зображень Ci на рівні окремих регіонів для пікселів pijk аналізованого зображення ti спочатку відбувається їх групування в окремі регіони (кластери) aif, f[1,Cli], Крім того, Cli, залежно від використовуваних методів кластеризації може як задаватися апріорі, так й обчислюватися у процесі кластеризації. Таким чином, зображення може бути задано у вигляді:
. | (3)
Аналогічною буде форма представлення зображення зразка пошуку to.
Відстань між кластеризованими зображеннями можна обчислити як:
, , , |
(4)
де Clo – кількість кластерів зображення зразка to, Cli – кількість кластерів i-го зображення бази даних T, – міра розрізнення u-го кластера зображення зразка to та відповідного кластера i-го зображення ti бази даних Т, – відстань між и-м кластером зображення зразка to та b-м кластером зображення бази даних ti , Сb={cb1, cb2, …,cbM} – вектор характеристик b-ого кластера зображення бази даних ti, Сu={} – вектор характеристик u-го кластера зображення зразка пошуку to.
В основі запропонованого автором методу є бітова маска взаємозв’язків та рангів характеристик кольору центрів кластерів, яка складається з двох груп біт, умовно означених як молодші та старші біти. Молодші біти визначаються шляхом аналізу пар колірних характеристик центрів кластерів на наявність відношень типу: менше, більше та дорівнює. При розгляді тривимірного колірного простору маємо 9 молодших біт. Для визначення старших біт маски увесь діапазон зміни кожної з колірних компонент [] розділяється на декілька інтервалів, кожний з яких відповідає рівню колірної компоненти. При введенні трьох рівних інтервалів [xl …GL], (GL…GH], (GH… xh], отримуємо три основних рівні: низький, середній та високий, та загалом маємо 9 старших біт.
Слід відзначити, що в роботі усі дослідження проводилися для колірного простору RGB. Правила побудови молодших та старших біт маски наведено у таблиці 1.
Пропонується використання параметра eps для реалізації можливості врахування декількох зв’язків для однієї пари характеристик кольору та декількох рангів для однієї характеристики.
Формальний опис побудови бітової маски взаємозв'язків і рангів кластера з центром {R,G,B} можна записати в такий спосіб.
Визначимо дану маску у вигляді багатовимірного вектора: |
(5)
причому компоненти векторів можуть приймати тільки два значення: 0 або 1.
Умовно позначимо вектори рангів вектором (), який можна подати як: |
(6)
Компоненти вектора визначаються за формулами: |
(7)
Таблиця 1
Маска взаємозв’язків та рангів компонент простору RGB
Старші біти | Молодші біти
Межі зміни компоненти | Ранг | Маска | Зв’язок колірних характеристик | Маска
B | [xl …GL] | низький | 0 0 0 0 0 0 0 0 1 | R та G | R>G | 0 0 0 0 0 0 0 0 1
(GL…GH] | середній | 0 0 0 0 0 0 0 1 0 | R=G | 0 0 0 0 0 0 0 1 0
(GH… xh] | високий | 0 0 0 0 0 0 1 0 0 | R<G | 0 0 0 0 0 0 1 0 0
G | [xl …GL] | низький | 0 0 0 0 0 1 0 0 0 | R та B | R>B | 0 0 0 0 0 1 0 0 0
(GL…GH] | середній | 0 0 0 0 1 0 0 0 0 | R=B | 0 0 0 0 1 0 0 0 0
(GH… xh] | високий | 0 0 0 1 0 0 0 0 0 | R<B | 0 0 0 1 0 0 0 0 0
R | [xl …GL] | низький | 0 0 1 0 0 0 0 0 0 | G та B | G>B | 0 0 1 0 0 0 0 0 0
(GL…GH] | середній | 0 1 0 0 0 0 0 0 0 | G=B | 0 1 0 0 0 0 0 0 0
(GH… xh] | високий | 1 0 0 0 0 0 0 0 0 | G<B | 1 0 0 0 0 0 0 0 0
Умовно позначимо вектори взаємозв'язків вектором, який можна подати у вигляді: |
(8)
Компоненти вектора визначаються за формулами:
| (9)
На основі розглянутої бітової маски взаємозв'язків і рангів у роботі розроблено статистичний ієрархічний агломеративний метод для виділення окремих кластерів зображень, основний зміст якого полягає в такому.
Передбачається, що спочатку кожен піксель зображення t є окремим кластером (властивість агломеративності). Спочатку проводиться групування точок зображення з однаковими бітовими масками в окремі кластери. Для цього кожному пікселю зображення ставиться у відповідність бітова маска взаємозв'язків і рангів, потім пікселі з різними масками розносяться в різні кластери (відповідно, пікселі з однаковими масками об'єднуються в один кластер).
Зображення t розміром [wxh] пікселів можна визначити так само, як зазначено у формулах (1), (2).
Тоді формально об'єднання пікселів з однаковими бітовими масками в кластери можна записати у такий спосіб:
| (10)
У формулі (2.15): mv – кількість елементів групи (кластера) з індексом v; q – кількість кластерів; – бітова маска пікселя pjk з координатами (j, k) зображення t; l, e – індекси пікселів усередині кластера.
Результатом об'єднання пікселів з однаковими бітовими масками буде набір кластерів:
| (11)
Для формального опису методу кожному елементу av множини А ставиться у відповідність такий багатовимірний вектор:
| (12)
де: – набір пікселів v-го кластера, – маска v-го кластера.
Для подальшого ієрархічного об'єднання кластерів будується симетрична щодо головної діагоналі матриця відстаней ? розміром [vхv], елементи якої розраховуються як: |
(13)
У формулах (13): – кількість пікселів кластера з індексом ?, – кількість пікселів кластера з індексом ?, – Евклідова відстань між колірними компонентами пікселя з індексом у кластера з індексом ? і пікселя з індексом z кластера з індексом ?.
У побудованій матриці ? проводиться пошук мінімального елемента:
| (14)
Для кластерів з мінімальною відстанню (, ) перевіряється задоволення умови “порівняльності”, в основі якої підрахунок кількості еквівалентних ненульових біт масок Kb(v1,v2): |
(15)
де “·” – знак скалярного добутку векторів, вектора , обчислюються за формулами:
| (16)
Для задоволення умови “порівняльності” необхідно, щоб:
Kb(v1,v2) Kopt, | (17)
де Kopt є другим параметром пропонованого методу (першим позначений параметр eps) і підбирається експериментально залежно від аналізованого набору зображень.
Якщо для кластерів з мінімальною відстанню (, ) задовольняється умова (17), то відбувається об'єднання даних кластерів та перерахунок маски для нового кластера згідно з формулами (6-9): |
(18)
зменшення загальної кількості кластерів:
Якщо для кластерів з мінімальною відстанню (, ) не задовольняється умова (17), то проводиться пошук іншого мінімуму:
| (19)
Потім проводиться перепризначення змінних: v1=v3, v2=v4. І повторюються дії, описані формулами (17) -(19).
Обчислення за методом припиняються, коли виконується умова:
| (20)
Для обчислення раціональних параметрів запропонованого методу (eps, Kopt) використовується ентропія площі відокремлених кластерів, кількісне значення якої повинно зростати зі зростанням кількості кластерів.
Експериментальне визначення раціональних параметрів реалізовувалося на розрахунку ентропії площі відокремлених кластерів зображень бази даних Ванга. Цей тестовий набір вміщує 1000 24-бітних зображень у форматі JPEG, розміром 384х256 пікселів, які умовно розділено на 10 семантичних груп.
У ході проведення експериментів аналізувались наступні значення параметрів: {5, 6}. Вибір кількісних значень параметрів обмежується заданими межами згідно з відомим припущенням, що оптимальними є методи кластеризації, які відокремлюють від 2 до 16 кластерів. Згідно з результатами експериментів раціональними є такі значення параметрів методу кластеризації: eps=0,1 та Kopt=6.
У третьому розділі визначено розроблені автором експериментальні системи. Перша з них призначена для оцінки основних характеристик (часової та просторової складності та якості кластеризації) методів кластеризації та можливості вдосконалення швидкодії запропонованого методу шляхом реалізації розподіленої системи кластеризації зображень; друга – для оцінки характеристик точності контекстного пошуку зображень, що кластеризовані.
Розглядаються базові модулі розроблених програмних систем, приведено інформаційні потоки між модулями.
На рис. 1 подано загальну схему зв’язків модулів експериментальної системи оцінки характеристик методів кластеризації зображень. Під параметрами кластеризації позначено метод кластеризації та кількісні значення його параметрів.
Рис.1. Загальна схема зв’язків модулів експериментальної системи оцінки характеристик методів кластеризації
Розподілені обчислювальні системи кластеризації відрізняються від означеної вище програмної системи насамперед наявністю на кожній фазі модулів Transport, які здійснюють транспортування даних між вузлами.
Запропоновано технологію контекстного пошуку зображень, що базується на врахуванні ступеня впливу характеристик кластерів (таких, як характеристики кольору, форми, місцезнаходження та текстури) на результати пошуку зображень в електронних колекціях. Тобто, залежно від цілей пошуку можливі різні пріоритети для різних типів характеристик. Крім того, для підвищення якості змістового пошуку розглядається розділення зображень бази даних на два види: текстуровані та нетекстуровані зображення.
Для характеристик форми та текстури запропоновано такі способи їх урахування: не враховувати, враховувати на рівні з колірними, враховувати як другорядні, враховувати як базові, враховувати без колірних. Для характеристик місцезнаходження розглядаються два варіанти їх урахування: враховувати, не враховувати. Виходячи з запропонованих ступенів врахування характеристик кластерів, міра близькості зображення зразка пошуку to та i-го зображення бази даних ti (4) буде відрізнятися методом обчислення (відстані між и-м кластером зображення зразка to та b-м кластером зображення бази даних ti).
Для нетекстурованих зображень бази даних обчислюються як: |
(21)
Для зображень, відзначених як текстуровані, пропонується обчислювати за наступною формулою: |
(22)
Коефіцієнти врахування характеристик розраховуються як:
Як найбільш ефективні обрано наступні типи характеристик кластерів: для характеристик текстури – характеристики міри нерівномірності регіонів, для характеристик форми – перший момент інваріації, для характеристик місцезнаходження – вектор часток регіону у кожній з частин зображення (зображення умовно поділяються на 4 частини: південно-західну, південно-східну, північно-західну та північно-східну).
Для аналізу ефективності запропонованої технології пошуку на базі розробленої програмної системи кластеризації створено експериментальну систему контекстного пошуку зображень, яка має такі можливості: занесення зображень до бази даних, пошук зображення-зразка у базі даних та розрахунок характеристики точності пошуку. Порівняно з описаною вище системою кластеризації зображень запропонована система має такі нові модулі: Database (модуль містить у собі функції для роботи з базою даних зображень), Search (модуль реалізує оцінку близькості зображень), Analyze (формування файлу-звіту оцінки точності контекстного пошуку). Крім того, модуль Capture має додатково нову функцію – виконує обчислення характеристик виділених кластерів (таких, як характеристики форми, текстури, місцезнаходження).
Також у цьому розділі запропоновано використовувати тестовий набір зображень Ванга для оцінки методів виділення кластерів зображень, який було модифіковано шляхом додання двох груп текстур для тестування системи контекстного пошуку зображень.
У четвертому розділі наведено основні результати експериментів для кожної з експериментальних систем, що описані у третьому розділі.
Для системи, що призначена для обчислення основних характеристик методів кластеризації, проводилися такі експерименти: з розрахунку часової та просторової складності, з вибору оптимальної архітектури розподіленої системи кластеризації зображень (згідно з розробленим методом), з обчислення характеристик якості кластеризації зображень. Наведено аналітичні оцінки витрат процесорного часу та об’єму оперативного простору для виділення регіонів зображень за допомогою методів, що аналізуються.
Експериментальні дослідження проводились на основі означеної вище бази даних Ванга. Перший та останній з наведених вище експериментів проводилися для двох методів: запропонованого статистичного ієрархічного агломеративного методу та найбільш розповсюдженого методу k-середніх.
На рис. 2 подано результати експериментального порівняння конкуруючих методів при оцінюванні витрат процесорного часу та об’єму оперативної пам’яті. Вісь абсцис становить собою зміну ентропії (як колірної складності) зображень бази даних, вісь ординат – демонструє усереднене значення показника, що аналізується, для кожного з виділених інтервалів зміни ентропії. Слід зазначити, що порівняння проводилося для однакової кількості виділених кожним з методів кластерів. Для тестування використовувалась електрона обчислювальна машина з процесором Intel Celeron 2.7 ГГц та об’ємом оперативної пам’яті 512 Мб.
Рис. 2. Результати експериментальної оцінки часової та просторової складності методів кластеризації
Необхідно відзначити, що значна перевага запропонованого СІА методу при оцінюванні процесорного часу на обробку зображень пов’язана, насамперед, з першим етапом методу – етапом рознесення пікселів з однаковими бітовими масками за кластерами.
Для аналізу можливості підвищення показників швидкодії обробки бази даних зображень розглянуто три базові системи розподіленої обробки на двох вузлах: конвейєрна система, система з однаковими копіями програм на вузлах без здійснення розподілення завдань та система з однаковими копіями програм на вузлах з виконанням розподілення завдань між вузлами.
Результати експериментальної оцінки характеристик аналізованих систем показали перевагу конвейєрної системи перед системою з клонами програм без розподілення завдань за прискоренням, але недоліки по показниками завантаження вузлів. Цей факт зумовлений тим, що на другій стадії конвейєра можлива черга у зв’язку з нерівномірною тривалістю стадій конвеєра для зображень з високою ентропією. Відставання у прискоренні другої з наведених систем можна пояснити нерівномірністю розподілення складності зображень між вузлами. Безумовно, найбільш оптимальною за всіма наведеними показниками є розподілена система з копіями програм на вузлах та зі здійсненням розподілення завдань між вузлами. Для більш докладного аналізу порівнюються зміни основних показників у часі.
Також розглянуто можливості розширення обраної оптимальної розподіленої системи шляхом збільшення кількості вузлів та шляхом модифікування для індексації ресурсів мережі Internet.
Як критерії якості методів відокремлення регіонів зображень застосовуються такі оцінки: модифікована оцінка якості Хараліка та Шапіро, оцінка оптимальності розбивки за колірною подібністю пікселів отриманих кластерів та міра віддаленості центрів виділених кластерів.
У ході експериментального порівняння методів згідно з цими показниками було виявлено, що ієрархічний агломеративний та k-середніх методи мають в середньому однакові результати відповідно до оцінки якості Хараліка та Шапіро, та запропонований метод перевершує метод k-середніх у випадку порівняння з використанням критеріїв оптимальності розбивки за колірною подібністю пікселів та міри віддаленості центрів кластерів. На рис. 3 подано у графічному вигляді експериментальні результати порівняння конкуруючих методів відповідно до двох останніх (з вище наведених) показників. Слід зазначити, що при порівнянні методів згідно з оцінкою віддаленості центрів відокремлених кластерів більш ефективним є метод з найвищим показником, а при аналізі методів відповідно з оцінкою оптимальності розбивки – метод з найнижчим показником.
У процессі тестування системи контекстного пошуку зображень результати експериментальної оцінки точності змістового пошуку зображень (рис. 4), точні копії яких містяться в аналізованій базі даних, показали перевагу пошуку кластеризованих за допомогою запропонованого СІА методу зображень для семантичних груп, які найбільш відрізняються за ентропією зображень. Слід зазначити, що на рис. 4а – наведено результати контекстного пошуку без текстурної класифікації, а на рис. 4б – з текстурною класифікацією.
Рис.3. Експериментальне порівняння показників якості статистичних методів кластеризації
а) б)
Рис. 4. Результати експериментів з контекстного пошуку зображень, точні копії яких містяться у базі даних
Необхідно відзначити, що хоча наявність текстурної класифікації й поліпшує результати оцінки точності, але значно погіршує показники швидкодії пошуку зображень (окремі дослідження цих показників не проводилися, але виявлено, що тривалість пошуку одного зображення у базі даних з текстурною класифікацією перебільшує тривалість пошуку зображення у базі даних без текстурної класифікації в середньому в 1,57 рази).
Також виконано експерименти з оцінки точності контекстного пошуку модифікованих зображень бази даних. Як основні було обрано такі модифікації: збільшення яскравості, переворот, відображення, масштабування, пікселізація зображення та перенесення й поворот частини зображення. Проведені експерименти показали обмеженість розробленого методу при здійсненні пошуку зображень, до яких були застосовані модифікації, в основі яких – значна зміна колірних характеристик. Це пов’язано, насамперед, з тим, що в основі СІА методу – бітова маска взаємозв’язків та рангів колірних компонент, значна зміна яких впливає на результати кластеризації. Однак розроблений метод показав свою ефективність при пошуку зображень, до яких застосовувались наступні модифікації: переворот, відображення, масштабування, пікселізація зображення та перенесення частини зображення.
ВИСНОВКИ
У дисертаційній роботі вирішено важливу прикладну задачу – розробка статистичного ієрархічного агломеративного методу кластеризації для виділення регіонів зображень, на базі якого створено систему контекстного пошуку кластеризованих зображень. При цьому отримано такі основні результати:
1.
Вперше розроблено бітову маску взаємозв’язків та рангів колірних компонент центрів кластерів для можливості попереднього розділення пікселів за кластерами та припинення процедури кластеризації.
2.
Запропоновано статистичний ієрархічний агломеративний метод кластеризації зображень на базі означеної бітової маски взаємозв’язків та рангів.
3.
На базі створеного СІА методу розроблено експериментальну програмну систему оцінки основних характеристик методу та можливості збільшення швидкодії кластеризації бази даних зображень шляхом реалізації розподіленої системи обробки колекції зображень.
4.
Розроблено систему контекстного пошуку зображень на базі СІА методу, у якій запропоновано враховувати значимість характеристик кластерів для ефективної обробки запитів різних рівнів. Крім того, розглядається можливість попередньої класифікації зображень на текстуровані та нетекстуровані. Однак, останнє введення показало свою обмеженість з точки зору витрат процесорного часу.
5.
Аналітично показано та експериментально доведено перевагу розробленого методу при оцінюванні витрат процесорного часу на кластеризацію зображень порівняно з найбільш розповсюдженим статистичним методом k-середніх кластеризації (розроблений метод перевершує k-середніх метод у середньому в 10.1 рази). Однак при оцінюванні затрат оперативної пам’яті було виявлено перевагу методу k-середніх, яка для тестового набору, що розглядається, в середньому становить 13% (для аналізованих зображень цей показник не перевищує 3 Мб).
6.
Означено найбільш ефективну (з точки зору швидкодії обробки набору зображень) з трьох проаналізованих систем розподіленої кластеризації зображень. Експериментально показано лінійне прискорення кластеризації колекції зображень залежно від кількості вузлів за допомогою обраної розподіленої системи.
7.
Проведено експерименти з оцінки якості кластеризації зображень конкуруючими методами, проаналізовано результати розрахунку трьох показників: модифікованої оцінки якості Хараліка та Шапіро, оцінки оптимальності розбивки за колірною подібністю пікселів отриманих кластерів та міри віддаленості центрів виділених кластерів. Було визначено перевагу запропонованого методу за двома останніми показниками, у той час як модифікована оцінка якості Хараліка та Шапіро методів, що порівнюються, в середньому дала однакові результати.
8.
Виконано експерименти з оцінки показника точності контекстного пошуку як зображень, точна копія яких є в базі даних, так і модифікованих зображень. Результати експериментів з пошуку точних копій зображень показали перевагу змістового пошуку зображень, що кластеризувалися за допомогою розробленого методу (порівняння проводилося з k-середніх методом), при аналізі точності пошуку зображень груп, що найбільш відрізняються з точки зору середньої ентропії в групах (перевага в середньому становить 5%). Запропонований метод показав свою стійкість до модифікацій зображень зразків пошуку, які значно не впливають на колірні характеристики зображень.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Башков Є.О., Вовк О.Л. Класифікація методів опису текстурних характеристик зображень // Наукові праці Донецького національного технічного університету: “Інформатика, кібернетика та обчислювальна техніка”. – ДНТУ, Донецьк. – 2003. – Випуск 70. – С. 5-19.
2.
Vovk O.L. Evaluation of Statistical Features for Texture Classification // Вісник Сумського державного університету, серія: технічні науки. – СДУ, Суми. – 2004. – №12(71). – С. 98-105.
3.
Вовк О.Л. Совокупные количественные оценки качества выделения регионов изображений с помощью статистических алгоритмов // Автоматика. Автоматизация. Электротехнические комплексы и системы. – ХНТУ, Херсон. – 2004. – №2. – С. 116-122.
4.
Башков Е.А., Вовк О.Л. Кластеризация изображений методом дендрограмм // Наукові праці Донецького національного технічного університету: “Проблеми моделювання та автоматизації проектування динамічних систем”. – ДНТУ, Донецьк. – 2005. – Випуск 78. – С. 152-161.
5.
Вовк О.Л. Методы расчета меры близости кластеризированных изображений при контекстном поиске визуальной информации // Наукові праці Донецького національного технічного університету: “Інформатика, кібернетика та обчислювальна техніка”. – ДНТУ, Донецьк. – 2005. – Випуск 93. – С. 33-40.
6.
Вовк О.Л. Характеристики формы регионов изображений для контекстного поиска // Інформаційні технології та комп’ютерна інженерія. – ВНТУ, Вінниця. – 2005. – №1. – С. 104-108.
7.
Башков Е.А., Вовк О.Л. Оценка эффективности нового статистического иерархического агломеративного алгоритма кластеризации для распознавания регионов изображений // Системні дослідження та інформаційні технології. – Інститут прикладного системного аналізу НАН України, Київ. – 2005. – №2. – С. 117-130.
8.
Вовк О.Л., Енин Д.С. Оценка эффективности использования вейвлетов для кодирования изображений // Матеріали II науково-практичної конференції “ДОНБАС-2020: наука і техніка – виробництву”. – ДНТУ, Донецьк. – 2004. – С. 570-579.
9.
Вовк О.Л. Иерархический агломеративный алгоритм кластеризации для выделения регионов изображений // Труды XIV Международной конференции по компьютерной графике и зрению “GrapiCon’2004”. – МГУ, Москва. – 2004. – С. 245-248.
10.
Вовк О.Л. Автоматическое управление базами данных изображений // Матеріали XI Міжнародної конференції по автоматичному управлінню “Автоматика – 2004”. – НУХТ, Київ. – 2004. – С. 24.
11.
Вовк О.Л. Система управления электронными коллекциями кластеризированных изображений // Материалы XI Международного научно-практического семинара “Практика и перспективы развития партнерства в высшей школе”. – ДНТУ, Донецьк. – 2005. – С. 257-262.
12.
Вовк О.Л. Кластеризация для контекстного поиска в сети Internet // Известия ТРТУ. Тематический выпуск: Материалы Всероссийской научно-технической конференции с международным участием “Компьютерные и информационные технологии в науке, инженерии и управлении”. – ТРТУ, Таганрог. – 2005. – С. 148-150.
13.
Башков Е.А., Вовк О.Л. Статистическая кластеризация для выделения регионов изображений // Збірник праць V Міжнародної наукової конференції “Інтелектуальний аналіз інформації”. – “Просвіта”, Київ. – 2005. – С. 50-59.
14.
Вовк О.Л. Применение процедуры кластеризации для содержательного поиска изображений // Матеріали I Міжнародної науково-технічної конференції “Моделювання та комп’ютерна графіка”. – ДНТУ, Донецьк. – 2005. – С. 55-58.
АНОТАЦІЯ
Вовк О.Л. Статистичні методи кластеризації зображень для контекстного пошуку в електронних колекціях. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – “Автоматизовані системи управління та прогресивні інформаційні технології” – Донецький національний університет, Донецьк, 2006.
Дисертацію присвячено розробці статистичного ієрархічного агломеративного (СІА) методу для виділення регіонів зображення за колірною подібністю. Запропонований метод базується на бітовій масці взаємозв’язків та рангів колірних компонент центрів кластерів. У роботі подано аналітичні та експериментальні оцінки часової та просторової складності за допомогою розробленого методу. Також проведено експериментальні дослідження з оцінки якості кластеризації зображень. Розглянуто порівняння СІА методу з найбільш використовуваним для виділення регіонів зображень статистичним методом k-середніх. У результаті порівняння доведено перевагу СІА методу при оцінюванні затрат процесорного часу на кластеризацію зображень та недоліки при оцінюванні затрат оперативного простору. При оцінюванні якості кластеризації зображень конкуруючими методами виявлена перевага СІА методу за двома з трьох критеріїв, результати оцінки згідно з третім критерієм у середньому однакові для обох методів. На базі СІА методу створено систему контекстного пошуку зображень в електронних колекціях. Проведено експерименти з оцінки точності контекстного пошуку зображень.
Ключові слова: статистичні методи кластеризації зображень, часова та просторова складність, якість кластеризації, контекстний пошук зображень, точність пошуку.
АННОТАЦИЯ
Вовк О.Л. Статистические методы кластеризации изображений для контекстного поиска в электронных коллекциях. – Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – “Автоматизированные системы управления и прогрессивные информационные технологии”. – Донецкий национальный университет, Донецк, 2006.
Диссертация посвящена разработке статистического иерархического агломеративного (СИА) метода для выделения регионов изображений по цветовому подобию. Предлагаемый метод базируется на битовой маске взаимосвязей
