Кластеризація ключів образів з метою прискорення доступу до них
У роботі розглянуто застосування методу кластеризації на основі побудови дерева згортання до розв’язування задачі зберігання та пошуку ключів, які відображають графічні образи. Порівняння групи образів, як ключів в суто графічному зображенні, з їх сукупностями інтегральних оцінок є надзвичайно склад...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2005
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/20922 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Кластеризація ключів образів з метою прискорення доступу до них / Р. Мельник, О. Алексєєв // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 172-178. — Бібліогр.: 3 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-20922 |
|---|---|
| record_format |
dspace |
| spelling |
Мельник, Р. Алексєєв, О. 2011-06-10T00:25:59Z 2011-06-10T00:25:59Z 2005 Кластеризація ключів образів з метою прискорення доступу до них / Р. Мельник, О. Алексєєв // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 172-178. — Бібліогр.: 3 назв. — укр. 1816-1545 https://nasplib.isofts.kiev.ua/handle/123456789/20922 621.38 У роботі розглянуто застосування методу кластеризації на основі побудови дерева згортання до розв’язування задачі зберігання та пошуку ключів, які відображають графічні образи. Порівняння групи образів, як ключів в суто графічному зображенні, з їх сукупностями інтегральних оцінок є надзвичайно складною задачею. Тому для кожного образу заданого типу виділяються характеристичні параметри, які можуть бути прийняті за проміжні ключі образів для швидкого їх опрацювання. У роботі зроблено висновок щодо рівнів значень критеріїв, для яких допускаються об’єднання ключів образів у спільні кластери. Метод застосовується для мінімізації часових ресурсів формування бібліотеки візуальних образів, пошуку та розпізнавання образів у бібліотеці. Method of clusterization based on construction of the rolling up tree with task to storage and to search the keys which represent graphic images is presented in this work. The group comparison of images as keys in an especially graphic image with their sets of integral estimations is an extraordinarily difficult problem. That is why for every image in the set type characteristic parameters which can be accepted for the intermediate keys of images for their express processing are selected. There is a conclusion about the levels of criteria values for which possible unites of the image’s keys in general clusters. Application of this method is intended for minimization of time-resources to form the library of visual images, search and image recognition in a library. В работе на основе построения дерева свертывания рассмотрено применение метода кластеризации к решению задачи хранения и поиска ключей, которые отображают графические образы. Сравнение группы образов, как ключей в сугубо графическом изображении, с их совокупностью интегральных оценок, является чрезвычайно сложной задачей. Поэтому для каждого образа заданного типа выделяются характеристические параметры, которые могут быть приняты за промежуточные ключи образов для быстрой их проработки. В работе делается вывод относительно уровней значений критериев, для которых допустимы объединения ключей образов в общие кластеры. Метод применяется для минимизации часовых ресурсов формирования библиотеки визуальных образов, поиска и распознавания образов в библиотеке. uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України Кластеризація ключів образів з метою прискорення доступу до них Clusterization of the Image’s Keys to Speed up Access to them Кластеризация ключей образов с целью ускоренного доступа к ним Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Кластеризація ключів образів з метою прискорення доступу до них |
| spellingShingle |
Кластеризація ключів образів з метою прискорення доступу до них Мельник, Р. Алексєєв, О. |
| title_short |
Кластеризація ключів образів з метою прискорення доступу до них |
| title_full |
Кластеризація ключів образів з метою прискорення доступу до них |
| title_fullStr |
Кластеризація ключів образів з метою прискорення доступу до них |
| title_full_unstemmed |
Кластеризація ключів образів з метою прискорення доступу до них |
| title_sort |
кластеризація ключів образів з метою прискорення доступу до них |
| author |
Мельник, Р. Алексєєв, О. |
| author_facet |
Мельник, Р. Алексєєв, О. |
| publishDate |
2005 |
| language |
Ukrainian |
| publisher |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| format |
Article |
| title_alt |
Clusterization of the Image’s Keys to Speed up Access to them Кластеризация ключей образов с целью ускоренного доступа к ним |
| description |
У роботі розглянуто застосування методу кластеризації на основі побудови дерева згортання до розв’язування задачі зберігання та пошуку ключів, які відображають графічні образи. Порівняння групи образів, як ключів в суто графічному зображенні, з їх сукупностями інтегральних оцінок є надзвичайно складною задачею. Тому для кожного образу заданого типу виділяються характеристичні параметри, які можуть бути прийняті за проміжні ключі образів для швидкого їх опрацювання. У роботі зроблено висновок щодо рівнів значень критеріїв, для яких допускаються об’єднання ключів образів у спільні кластери. Метод застосовується для мінімізації часових ресурсів формування бібліотеки візуальних образів, пошуку та розпізнавання образів у бібліотеці.
Method of clusterization based on construction of the rolling up tree with task to storage and to search the keys which represent graphic images is presented in this work. The group comparison of images as keys in an especially graphic image with their sets of integral estimations is an extraordinarily difficult problem. That is why for every image in the set type characteristic parameters which can be accepted for the intermediate keys of images for their express processing are selected. There is a conclusion about the levels of criteria values for which possible unites of the image’s keys in general clusters. Application of this method is intended for minimization of time-resources to form the library of visual images, search and image recognition in a library.
В работе на основе построения дерева свертывания рассмотрено применение метода кластеризации к решению задачи хранения и поиска ключей, которые отображают графические образы. Сравнение группы образов, как ключей в сугубо графическом изображении, с их совокупностью интегральных оценок, является чрезвычайно сложной задачей. Поэтому для каждого образа заданного типа выделяются характеристические параметры, которые могут быть приняты за промежуточные ключи образов для быстрой их проработки. В работе делается вывод относительно уровней значений критериев, для которых допустимы объединения ключей образов в общие кластеры. Метод применяется для минимизации часовых ресурсов формирования библиотеки визуальных образов, поиска и распознавания образов в библиотеке.
|
| issn |
1816-1545 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/20922 |
| citation_txt |
Кластеризація ключів образів з метою прискорення доступу до них / Р. Мельник, О. Алексєєв // Фіз.-мат. моделювання та інформ. технології. — 2005. — Вип. 2. — С. 172-178. — Бібліогр.: 3 назв. — укр. |
| work_keys_str_mv |
AT melʹnikr klasterizacíâklûčívobrazívzmetoûpriskorennâdostupudonih AT aleksêêvo klasterizacíâklûčívobrazívzmetoûpriskorennâdostupudonih AT melʹnikr clusterizationoftheimageskeystospeedupaccesstothem AT aleksêêvo clusterizationoftheimageskeystospeedupaccesstothem AT melʹnikr klasterizaciâklûčeiobrazovscelʹûuskorennogodostupaknim AT aleksêêvo klasterizaciâklûčeiobrazovscelʹûuskorennogodostupaknim |
| first_indexed |
2025-11-25T23:31:31Z |
| last_indexed |
2025-11-25T23:31:31Z |
| _version_ |
1850582343785381888 |
| fulltext |
Кластеризація ключів образів з метою
прискорення доступу до них
Роман Мельник1, Олександр Алексєєв2
1 д. т. н., професор, НУ «Львівська політехніка», кафедра ПЗ, вул. С. Бандери, 12, Львів,
e-mail: ramelnyk@polynet.lviv.ua
2 НУ «Львівська політехніка», кафедра ПЗ, вул. С. Бандери, 12, Львів, e-mail: alexa@org.lviv.net
У роботі розглянуто застосування методу кластеризації на основі побудови дерева згор-
тання до розв’язування задачі зберігання та пошуку ключів, які відображають графічні
образи. Порівняння групи образів, як ключів в суто графічному зображенні, з їх сукупностя-
ми інтегральних оцінок є надзвичайно складною задачею. Тому для кожного образу задано-
го типу виділяються характеристичні параметри, які можуть бути прийняті за проміжні
ключі образів для швидкого їх опрацювання. У роботі зроблено висновок щодо рівнів значень
критеріїв, для яких допускаються об’єднання ключів образів у спільні кластери. Метод за-
стосовується для мінімізації часових ресурсів формування бібліотеки візуальних образів,
пошуку та розпізнавання образів у бібліотеці.
Ключові слова: дерево згортання, кластеризація, програмний пакет.
Вступ. Практичні класи комбінаторних задач розпізнавання образів вимагають
значних часових затрат через високу розмірність задач та складність опису
самих образів. Скоротити їх можна шляхом виділення основних особливостей
моделей, побудовою так званих ключів образів. Ключі мають меншу розмірність,
ніж повні шукані об’єкти. У статті пропонується підхід до кластеризації ключів
візуальних образів з метою зменшення часових ресурсів пошуку та подальшої
ідентифікації.
1. Кластеризація ключів образів
Кластеризація, як специфічний засіб класифікації об’єктів, застосовується до
скінченної множини об’єктів. Відношення між об’єктами представляються си-
метричною матрицею суміжностей, елементи якої є характеристиками подібнос-
ті, несхожості, сусідства тощо. Ці характеристики набирають конкретних зна-
чень, якщо об’єктами є образи для розпізнавання, точки в n-мірному просторі і
т. п. Зокрема, ними можуть бути віддалі в евклідовому просторі, пропускна про-
відність міжоб’єктних елементів і таке інше.
Графічні образи Оі (відбитки пальців, знімки внутрішніх органів, фото лю-
дей тощо) займають значне місце в пам’яті та їх використання, як ключів
для пошуку необхідної інформації для співставлення заданого і шуканого ключів
УДК 621.38
172
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 172-178
173
(розпізнавання образів), потребує значного часу. Тому для прискорення пошуку
характеристик заданого образу застосуємо два прийоми: 1) контекстуальний —
заміна графічного образу множиною його характеристичних ознак, 2) датологіч-
ний — групування ключів з допомогою ієрархічного дерева формування
кластерів образів. Кластери — це образи, характеристики яких близькі між со-
бою згідно певного критерію. Тоді задача зберігання та пошуку образів містить
наступні етапи: знаходження характеристичних ознак та формування на їх основі
ключів, формування дерева кластерів, грубе оцінювання позиції ключа у списку,
точне співставлення ключів образів або самих образів. Кількість операцій порів-
няння буде меншою за рахунок меншої кількості ключів. Групування образів, як
ключів у чисто графічному зображенні, з їх сукупностями інтегральних оцінок є
надзвичайно складною задачею. Тому для швидкого опрацювання для кожного
образу заданого типу виділяються групи характеристичних параметрів, які
можуть бути прийняті за проміжні ключі образів. Для формування відповідних
характеристичних ознак ключів застосовують методи опрацювання образів [1-3].
Подамо всі образи, призначені до зберігання та розпізнавання, множиною
Q(Q1, Q2, Q3, … QN), де N — достатньо велике значення. Кожному образу
притаманні певні характеристичні ознаки a, b, c,… (координати центра, кількості
точок перетину ліній образу з осями координат тощо), які формують ключ образа
та виражаються числовими значеннями. Тобто кожному образу ставиться у від-
повідність множина його характеристик Q1 = Q1(а1, b1, c1,…), Q2 = Q2(а2, b2, c2, …),
Q3 = Q3(а3, b3 , c3 , …), …, QN = QN(аN, bN, cN, …). Для пришвидшення пошуку від-
повідного образу (групи образів) у списку образів останні необхідно згрупувати,
зафіксувавши місце розташування групи на дереві. Групи образів відповідають
кластерам, утвореним за певними критеріями близькості на основі дерева згор-
тання зображення [1].
Кластеризація здійснюється процедурою, на i-му кроці якої формується
множина Хi+1 вершин дерева (крім початкових образів)
(∀ Qк, Qj ∈ Xi), [F*(Qк, Qj) = optF(X´)], X´ ∈ S,
(∀ Qе = Qк ∪ Qj ∈ Ві), (1)
Сi = Хi \ Qе, тобто множина Вi формується на основі новоутворених вершин, які
задовольняють найкращим значенням функції критерію F(X´). Окрім того, в цю
множину входять вершини множини Сі попереднього рівня, які не об’єднувались,
тобто
Хі+1 = Ві ∪ Сі . (2)
Роман Мельник, Олександр Алексєєв
Кластеризація ключів образів з метою прискорення доступу до них
174
Рис. 2. Кластери у двовимірному просторі
a
b
Приклад формування множин ключів на різних рівнях дерева показано на
рис. 1. Зауважимо, що новоутворені кластери образів (ключів) позначаємо також
символом QN+k з індексом, більшим від кількості початкових образів N.
Об’єднання двох ключів образів відбувається, якщо функція для них набу-
ває мінімального значення
F* = min (Fkj), k, j ∈ I, (3)
де I — множина всіх можливих пар ключів початкових образів, кластерів та їх
комбінацій.
Функцію F утворимо як зважену суму модулів різниць між характеристи-
ками образів (кластерів), що є кандидатами на об’єднання в один спільний кластер
Fij = w1|аi – аj| + w2|bi – bj| + w3|ci – cj| + ... , (4)
або зважену суму квадратів різниць між характеристиками
Fij = w1(аi – аj)2 + w2(bi – bj)2 + w3(ci – cj)2 + ... , (5)
де сумування відбувається за всіма ознаками, які формують ключ образу.
Введенням зваженої функції критерію підкреслюємо те, що задача поділу
ключів у кластери розв’язується як задача багатокритеріальної оптимізації мето-
дом згортання декількох критеріальних функцій в одну. Важливим питанням є
масштаб значень ознак ключів аi, bi, ci, ... , на основі яких формуються кластери.
Без урахування масштабу чисел, значення менших порядків будуть знівельовані
найбільшими числами. Тому кожне зі значень ознак має нормалізуватись розки-
дами можливих значень, наперед заданих або обчислених у процесі опрацювання
ключів. Далі вважаємо, що значення ознак ключів нормалізовані.
Прискорення алгоритму полягає в тому, щоб на кожному кроці об’єднува-
лись ті пари ключів, критерії яких справджують умову
*
0F (1 + kv) ≥ Fij ≥ F0, (6)
Х6
Х5
Х4
Х3
Х2
Х1
Рис. 1. Дерево формування кластерів ключів
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 172-178
175
де F0 — найбільше значення функції критерію на даному кроці об’єднання,
kv (kv < 1) — коефіцієнт кількості об’єднань на кроці або коефіцієнт швидкості
кластеризації. У процесі побудови дерева формуються характеристики новоутво-
рених вершин шляхом осереднення характеристик складових вершин
Qк = Qк[(аi + аj)/2, (bi + bj)/2, (ci + cj)/2, ... ], (7)
або зваженого осереднення характеристик складових вершин
Qк = Qк[(kаi + rаj)/(k + r), (kbi + rbj)/(k + r), (kci +rcj)/(k + r), ... ], (8)
де k, r — кількості ключів у i-му та j-му вузлах дерева згортання.
Якщо не передбачити критерію зупинки, то в результаті роботи алгоритму
буде побудовано повне дерево з однією вершиною — коренем (рис. 1), оскільки
на кожному кроці об’єднань серед значень функції близькості завжди існуватиме
мінімальне значення. Формування кластерів ключів, що мають найближчі харак-
теристичні ознаки, відповідає дереву неповного згортання. Побудувати його з
використанням алгоритму згортання можна декількома шляхами: 1) після побу-
дови повного дерева згортання провести аналіз дерева і лінією січення розділити
дерево на бажану кількість піддерев, 2) виділити групи в процесі їх формування,
вказуючи верхню та нижню межі розмірів кластерів, 3) після побудови дерева
згортання відобразити значення функції критерію, при яких відбулось об’єднан-
ня, на осі ординат. Далі на основі характеру зміни значень функції зробити вис-
новок про рівні значень критерію, для яких допускаються об’єднання ключів
образів у спільні кластери.
2. Критерії кластеризації
Проілюструвати формування кластерів можна областями у просторі ознак, що ха-
рактеризуються розмірами, координатами, взаємним розташуванням (для двови-
мірного випадку приклад наведено на рис. 2). Введемо для кожного кластера:
діаметр — віддаль між максимально віддаленими ключами k-го кластера
Dk = max{w1|аi – аj| + w2|bi – bj| + w3|ci – cj| + ...}, i, j ∈ J, (9)
та координати центра кластера
Cк = Cк(1/2∑акi, 1/2∑bк, 1/2∑cк, ... ). (10)
Тут J — множина всіх можливих пар номерів ключів образів у k-му кластері.
Для оцінки якості результату кластеризації на основі введених ознак
сформулюємо критерій середньої питомої густини ключів результатів даної
кластеризації
S = {∑Lk/Dk}/M, (11)
Роман Мельник, Олександр Алексєєв
Кластеризація ключів образів з метою прискорення доступу до них
176
де доданками є питомі густини окремих кластерів, Lk, Dk — кількість ключів та
діаметр k -го кластера, M — кількість кластерів.
За аналогією для результатів кластеризації введемо середній питомий об’єм,
який припадає на один ключ
V = {∑Dk/Lk}/M. (12)
Близьким до вказаних є також критерій, який формується на основі пито-
мої дисперсії кластерів
E = {∑Ek}/M = {∑∑dj}/M = {∑∑(ai
* – аj)2 + (bi
* – bj)2 + (ci
* – cj)2 + ...}/M, (13)
k ∈ {1, M}, i, j ∈ J,
де ai
*, bi
*, ci
* — координати центра простору кластера, Ek — дисперсія k-го
кластера, dj — середньоквадратичне відхилення ключа від центра простору кластера.
У разі збільшення кількості кластерів величина S збільшується, а V — змен-
шується. Точку різкої зміни градієнта цих величин можна прийняти за відлік
оптимальної кількості кластерів, понад яку значення функцій критерію покращу-
ється несуттєво.
Під час тестування алгоритму були використанні послідовності випадко-
вих чисел у багатовимірному просторі з різними центрами та однаковими радіу-
сами (як частковий випадок). Критерієм якості кластеризації приймалася різниця
між максимальним та мінімальним діаметрами отриманих кластерів, тобто
R = maxDk – minDk (14)
3. Програмна реалізація
Для дослідження складності та правильності прийнятих гіпотез побудовано про-
грамний пакет. Інтерфейс пакету дозволяє керувати процесом побудови дерева
згортання. До складу пакету входять: 1) модуль керування роботою модулів
побудови дерева згортання, початкового розбиття та оптимізації; 2) модуль
введення/виведення та ініціалізації для забезпечення інтерпретації вхідних даних
програми, побудови базових масивів вхідної інформації, виведення результатів
роботи програми у внутрішньому форматі даних, збереження часової та статис-
тичної інформації про хід виконання процесу згортання, розбиття та оптимізації;
3) модуль інтерфейсу для забезпечення діалогу з користувачем, виведення допо-
міжної та статистичної інформації про хід роботи та взаємозв’язку з операційною
системою; 4) модуль побудови дерева згортання для генерації послідовності усіх
можливих пар елементів, поновлення інформації у масиві пар та перерахунку
критеріїв (керує процесом об’єднання пар елементів у кластери); 5) модуль візу-
алізації дерева згортання дає змогу отримати інформацію про його рівні та
кластери, дослідити шляхи між кластерами, його елементами та вершиною дерева.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2005, вип. 2, 172-178
177
4. Аналіз результатів
Обчислювальна складність розробленого алгоритму перевищує величину O(n2),
що підтвердили експерименти дослідження часу побудови дерева згортання за-
лежно від величини початкової вибірки.
При дослідженні алгоритму ключі генерувались у 5 кластерах за рівномір-
ним законом розподілу з різними центрами координат та однаковими дисперсія-
ми. Критерій вибору кількості кластерів приймається на основі залежностей
контрольованих характеристик: діаметра утворених кластерів від рівня дерева
згортання (рис. 3а), середніх питомих об’єму та густини від кількості кінцевих
кластерів (рис. 3б). Зміна градієнта контрольованих величин вказує на оптималь-
ну кількість кластерів — 5.
Рис. 3. Результати тестування алгоритмів
Висновки. При створенні алгоритмів кластеризації ключів великих обсягів вини-
кає задача вибору оптимальної кількості кінцевих кластерів і зменшення склад-
ності алгоритму згортання ключів. Запропоновано ряд критеріїв, оцінювання
яких має створити умови знаходження оптимального варіанту групування даних.
Для прискорення алгоритму кластеризації потрібні додаткові дії, пов’язані з
попереднім опрацюванням ключів.
Література
[1] Мельник Р. А., Алексеев О. А. Кластеризація мікрообразів для кодування зображень //
Праці міжнародної конференції Укробраз’2004. — К., 2004. — C. 81-85.
[2] Мельник Р. А., Алексеев О. А. Покриття образів прямокутниками // Комп’ютерна
інженерія та інформаційні технології. — Львів, 2004. — № 521. — C. 166-168.
[3] Мельник Р. А., Алексеев О. А. Декомпозиція візуальних образів згортанням та ска-
нуванням // Праці міжнародної конференції CADSM’2005. — Львів-Поляна, 2005. —
C. 410-412.
а б
-10
0
10
20
30
40
50
60
70
0 2 4 6 8 10 12 14 16
рівень дерева згортання
ді
ам
ет
р
ут
во
ре
ни
х
кл
ас
те
рі
в
0
0,5
1
1,5
2
2,5
0 2 4 6 8 10
кількість кінцевих кластерів
се
ре
дн
ій
п
ит
ом
ий
о
б’
єм
се
ре
дн
я
пи
то
м
а
гу
ст
ин
а
Роман Мельник, Олександр Алексєєв
Кластеризація ключів образів з метою прискорення доступу до них
178
Clusterization of the Image’s Keys to Speed up Access to them
Roman Melnyk, Alexander Alexeyeyv
Method of clusterization based on construction of the rolling up tree with task to storage and to
search the keys which represent graphic images is presented in this work. The group comparison
of images as keys in an especially graphic image with their sets of integral estimations is an
extraordinarily difficult problem. That is why for every image in the set type characteristic
parameters which can be accepted for the intermediate keys of images for their express processing
are selected. There is a conclusion about the levels of criteria values for which possible unites of
the image’s keys in general clusters. Application of this method is intended for minimization of
time-resources to form the library of visual images, search and image recognition in a library.
Кластеризация ключей образов
с целью ускоренного доступа к ним
Роман Мельник, Александр Алексеев
В работе на основе построения дерева свертывания рассмотрено применение метода
кластеризации к решению задачи хранения и поиска ключей, которые отображают гра-
фические образы. Сравнение группы образов, как ключей в сугубо графическом изображе-
нии, с их совокупностью интегральных оценок, является чрезвычайно сложной задачей. По-
этому для каждого образа заданного типа выделяются характеристические параметры,
которые могут быть приняты за промежуточные ключи образов для быстрой их прора-
ботки. В работе делается вывод относительно уровней значений критериев, для которых
допустимы объединения ключей образов в общие кластеры. Метод применяется для мини-
мизации часовых ресурсов формирования библиотеки визуальных образов, поиска и распоз-
навания образов в библиотеке.
Отримано 05.11.05
|