Моделі пошуку та розпізнавання зображень у базах даних

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

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

УДК 004.932.2:004.93'14

АВТОРЕФЕРАТ

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

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

МОДЕЛІ ПОШУКУ ТА РОЗПІЗНАВАННЯ ЗОБРАЖЕНЬ У БАЗАХ ДАНИХ

05.13.23 - системи та засоби штучного інтелекту

КІНОШЕНКО ДМИТРО КОСТЯНТИНОВИЧ

Харків - 2008

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

Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.

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

Путятін Євгеній Петрович, доктор технічних наук, професор, завідувач кафедри інформатики Харківського національного університету радіоелектроніки (м. Харків).

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

Ахметшин Олександр Мубаркович, доктор фізико-математичних наук, професор кафедри автоматизованих систем обробки інформації Дніпропетровського національного університету (м. Дніпропетровськ);

Руденко Олег Григорійович, доктор технічних наук, професор, завідувач кафедри електронних обчислювальних машин Харківського національного університету радіоелектроніки (м. Харків);

Провідна установа: Національний технічний університет України "Одеський політехнічний інститут", кафедра технічної кібернетики, Міністерство освіти і науки України, м. Одеса.

Захист відбудеться "18" червня 2008 р. о 15 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий "25" квітня 2008 р.

Вчений секретар спеціалізованої вченої ради С.Ф. Чалий.

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки в межах держбюджетних тем "Розробка моделей та методів факторизації інформації в умовах багатозначності" (№ДР 0104U004063), "Дослідження та розробка методів аналізу зображень в умовах складних перетворень" (№ДР 0103U001572) та "Інтелектуальний аналіз і обробка даних в реальному часі на основі засобів обчислювального інтелекту" (№ДР 0104U003432), що виконуються згідно з наказом Міністерства освіти і науки України за результатами конкурсного відбору проектів наукових досліджень. У межах зазначених тем здобувачем як виконавцем було запропоновано та досліджено модель зберігання та пошуку зображень за зразком, уведено модель порівняння частково впорядкованих щодо операції вкладення фактор-множин, досліджено та реалізовано підхід до індексації зображень у базах даних на основі методу синтезу блочно-діагональної форми матриці відстаней.

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

Для досягнення поставленої мети треба розв'язати такі задачі:

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

- розробити критерії оцінки вкладеності фактор-множин, застосувати їх для забезпечення пошуку областей інтересу зображення запиту;

- розробити метод індексації для зменшення кількості операцій порівняння зображень на етапі пошуку;

- розробити метод організації, зберігання та пошуку зображень за запитом у базах даних;

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

Об'єкт дослідження - процеси сприйняття і смислова інтерпретація просторових сцен.

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

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

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

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

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

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

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

Синтезований метод організації, зберігання та пошуку зображень за зразком у базах даних підтвердив свою ефективність у задачі ідентифікації патології на ультразвукових зображеннях внутрішніх органів, що було впроваджено міською клінічною лікарнею № 8 м. Харкова. Виконання пошуку на рівні областей дозволило ідентифікувати шорсткості еталонів при впровадженні в Національному науковому центрі "Інститут метрології" м. Харкова. Наукові положення, висновки і рекомендації, викладені в дисертації, були використані в навчальному процесі Харківського національного університету радіоелектроніки, що підтверджується актами впровадження. Реалізацію результатів дисертації проведено у вигляді програмних комплексів обробки зображень та баз відеоданих, два з яких сертифіковано у системі УкрСЕПРО.

Особистий внесок здобувача. Усі положення дисертації, що виносяться на захист, основні результати теоретичних та експериментальних досліджень отримані здобувачем особисто. У роботах, опублікованих зі співавторами, здобувачу належать: у [1] - проаналізовано існуючі моделі пошуку зображень за змістом, розроблено їх класифікацію та встановлено напрямок подальшого розвитку; у [3] - розроблено та досліджено нову метрику на розбиттях; у [4] - введено функціонал, який є метрикою і дозволяє чисельно порівнювати результати кластеризації; у [5] - модифіковано відношення на зображеннях для методу морфологічної нормалізації; у [6] - запропоновано та експериментально досліджено метод пошуку зображень за результатами сегментації; у [7] - запропоновано застосовувати метрику на частково впорядкованих розбиттях для оцінки результатів кластеризації; у [8] - запропоновано метод перетворень розбиття поля зору для знаходження точної сегментації; у [9] - розглянуто питання метричного аналізу результатів сегментації; у [10] - запропоновано метод грубого кластерного аналізу для пошуку зображень у базах відеоданих; у [11] - наведено результати застосування найпоширеніших ознак кольору в задачі пошуку зображень за змістом; у [12] - удосконалено кластерний підхід до контекстного пошуку зображень у базах даних за змістом; у [13] - визначено важливість питання вибору ознакового простору в процесі пошуку зображень та надано рекомендації щодо методів цього вибору; у [15] - проаналізовано та удосконалено метод формалізації подання зображень для створення інваріантних функціоналів для однопараметричних перетворень; у [16] - розглянуто питання знаходження еталону методом нормалізації плоских контурів.

Апробація результатів дисертації. Основні результати роботи доповідалися, обговорювалися і були схвалені на 9-й Міжнародній конференції з розпізнавання образів та обробки інформації PRIP'07 (Мінськ, Білорусь, 2007), 5-й Міжнародній конференції по обробці та застосуванню інформації i.TECH'07 (Варна, Болгарія, 2007), 3-й Міжнародній конференції "Інтелектуальні системи прийняття рішень і прикладні аспекти" ISDMIT'07 (Євпаторія, 2007), 4-му Міжнародному семінарі з адаптивного пошуку мультимедіа даних AMR'06 (Женева, Швейцарія, 2006), 8-му, 9-му, 10-му Міжнародних молодіжних форумах "Електроніка і молодь у XXI столітті" (Харків, 2004, 2005, 2006), конференції з машинного навчання та інтелектуального аналізу даних MLDM'05 (Лейпциг, Німеччина, 2005), конференції по комп'ютерному зору і графіці ICCVG'04 (Варшава, Польща, 2004), 25-му симпозіумі німецької асоціації з розпізнавання образів DAGM'03 (Магдебург, Німеччина, 2003), 9-й Міжнародній науковій конференції "Теорія і техніка передачі, прийому та обробки інформації" (Туапсе, 2003).

Публікації. Основні результати дисертаційної роботи надруковано у 16 наукових працях, у тому числі 3 статті у виданнях, що входять до переліків, затверджених ВАК України, 2 статті у закордонних журналах та 11 публікацій у працях, матеріалах і тезах доповідей міжнародних наукових симпозіумів, конференцій і семінарів, з них 6 за кордоном.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел та двох додатків. Повний обсяг дисертації становить 166 сторінок; обсяг основного тексту 137 сторінок; 59 рисунків; 5 таблиць; список використаних джерел, що включає 183 найменування та займає 19 сторінок; два додатки на 6 сторінках.

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

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

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

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

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

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

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

Нехай

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

- пошук найближчих зображень, що упорядковані за схожістю;

- -пошук, тобто пошук зображень, що відрізняються від запиту не більше ніж на задане граничне обмеження (радіус пошуку);

- комбінація зазначених підходів у сенсі мажорування однієї з умов.

У роботі розглядається найпоширеніший тип пошуку - -пошук на основі аналізу матриці відстаней

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

. (1)

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

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

, . (2)

Якщо, крім того, значення знаходиться в інтервалі , то

, . (3)

Нарешті, за умови, що , отримано оцінку

. (4)

Оцінки (2) - (4) лягли в основу індексації при бінарному пошуку та пошуку на основі розбиттів.

У першому випадку вибирається опорний об'єкт , визначається медіана відстаней до інших елементів і виконується звичайна дихотомія:

і .

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

У другому випадку вибирається опорних об'єктів , які продукують розбиття у такий спосіб:

.

Далі визначаються мінімальні та максимальні відстані між розбиттями

та

відповідно, де . На етапі пошуку виключається клас , якщо , де

, ,

.

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

Фрагмент розмірності матриці відстаней розмірності

,

яка є результатом перестановки рядків і стовпців таких, що ,

,

названо -блоком. Блок є максимальним, якщо .

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

,

.

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

У розділі запропоновано і досліджено метод формування -представлень. пошук розпізнавання зображення індексація

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

, ,

де - кількість елементів, що не ввійшли в жоден з блоків, - кількість блоків розмірності , - розмірності кластерів потужності ,…, - розмірності , .

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

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

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

Нехай - довільна вимірна множина з мірою ( - довжина, площа, об'єм, у скінченновимірному випадку - кількість елементів і т.ін.), а - множина всіх (вимірних) підмножин. На множині скінченних (за кількістю елементів) розбиттів таких, що

, ,

введено метрику

, (5)

де , ,

- симетрична різниця множин.

Нехай надано два розбиття

й

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

, а .

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

Крім того, припустимо:

.

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

Твердження 1. Для будь-яких двох скінченних розбиттів довільної вимірної множини , якщо , то .

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

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

.

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

Твердження 3. На множині розбиттів функціонали й мають такі властивості:

а) якщо й , то

;

б) щодо операції вкладення функціонал спадає, а функціонал зростає, тобто якщо , то ;

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

від точки .

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

Властивість 1. Множина всіх розбиттів є обмеженою і лежить "усередині" кола із центром у "точці" та радіусом рівним .

Властивість 2. Множина є пучком "прямих", що виходе із "точки" .

Властивість 3. Будь-які два елементи пучка "прямих" нескінченну кількість разів перетинають один одного.

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

Властивість 5. Границя множини розбиттів, у яких всі елементи є рівновимірними, складається з однієї "точки" - .

Властивість 6. Діаметр "кола", у якому лежить , не перевищує , тобто .

Для випадків, коли міра задається за допомогою позитивної інтегрованої функції на (зокрема, це просто функція розподілу яскравостей), тобто:

, ,

отримано інтегральні нерівності:

,

,

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

Для довільних розбиттів отримано нерівності:

(6)

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

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

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

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

Для експериментального аналізу методу побудови блочно-діагональної форми матриці відстаней використано тестові дані з колекції Berkley, що містить понад 1000 зображень та їх відповідні ground-truth представлення. Порівняння зображень проводилося на рівні фактор-множин, що продукуються алгоритмами сегментації. Відзначено, що блочно-діагональне представлення залежить від: алгоритму сегментації, способу порівняння фактор-множин, величини . Для виявлення ступеня залежності методу від представлення фактор-множин окрім ground-truth результатів використовувалася сегментація зображень алгоритмом JSEG. Аналіз проводився на базі нормованої метрики (5) при фіксованому радіусі пошуку . Отримані блочно-діагональні представлення для двох наборів фактор-множин порівнянні як за кількістю та розмірністю блоків, так і за змістом окремих блоків, що свідчить про певну інваріантність до алгоритму сегментації. Однак на кінцевий вигляд блочно-діагонального представлення істотно впливають розташування, форма та рівень деталізації областей фона. У той же час експерименти показали, що ці недоліки метрики при порівнянні фактор-множин усуваються за умови використання інтегральної нерівності (6). Нехай на етапі завдання запиту за результатами сегментації зображення запиту , розбиття уточняється у вигляді

, ,

де відповідає області фона, а - розбиття, можливо незв'язні, що представляють область інтересу запиту (рис. 1).

Рис. 1. Приклад процесу формування області інтересу за результатом сегментації

Отримано оцінку вкладеності фактор-множин:

, (7)

,

, .

Результати дослідження властивостей оцінки свідчить про її інваріантність до ступеня деталізації фактор-множин, що відповідають фону або області інтересу, у тому випадку, коли певна (і єдина) підмножина елементів розбиття шуканих зображень збігається з областю інтересу зображення запиту (рис. 2). Інакше кажучи, чим вищий рівень "покриття" області інтересу множинами порівнюваного зразка, які розташовані в ньому цілком, тим менша відстань між розбиттями. Наведено результати пошуку в базі даних, що містить 72 зображення із колекції Berkley та їх ground-truth представлення та 36 зображень листа на різному фоні з колекції Caltech, що сегментовані алгоритмом JSEG. Використання оцінки (7) дозволило знайти схожі за формою та розташуванням об'єкти незалежно від ступеня деталізації фона або області інтересу.

Рис. 2. Зображення, які мають еквівалентне за оцінкою (7) розбиття щодо рис. 1

Результати теоретичних та експериментальних досліджень моделі порівняння вкладених фактор-множин та методу синтезу блочно-діагональних представлень матриці відстаней засвідчили значну перспективу їх використання в моделі пошуку зображень за зразком. Як результат у розділі викладено метод організації, зберігання та пошуку зображень за зразком у базах даних, що містить у собі: сегментацію зображень; уточнення отриманого розбиття за допомогою інтелектуальних методів аналізу розбиттів; добування візуальних ознак кольору і форми з областей; створення структури індексів на базі методу синтезу блочно-діагональної форми матриці відстаней; метричне порівняння фактор-множин; візуалізацію результату на етапі пошуку (рис. 3). Метод реалізовано у вигляді системи пошуку зображень за змістом PIRS (Partition Image Retrieval System) та програми Coloring, що спрямована на обробку розбиттів. Як характерну особливість PIRS зазначено можливість пошуку на рівні областей по всьому полю зору або по його частинах. Виконано порівняльний аналіз зазначених типів пошуку із сучасними аналогами - системами SIMPLIcity і blobworld - на базі даних з 2390 зображень із колекцій Berkley та Caltech. Критерієм порівняння служили повнота і точність пошуку, що за результатами експериментів виявилися вищими у розробленого програмного комплексу.

Рис. 3. Функціональна схема пошуку в PIRS.

Метричний аналіз фактор-множин поля зору зображень забезпечив впровадження результатів дисертаційного дослідження у виробництво. Так, виконання пошуку на рівні областей дозволило ідентифікувати шорсткості еталонів з бази даних при впровадженні в Національному науковому центрі "Інститут метрології". Задачу визначення патології міксоми та дефекту міжпередсерцевої перегородки на зображеннях ультразвукових перерізів серця вирішено за допомогою аналізу вкладеності фактор-множин і впроваджена в міській клінічній лікарні № 8 м. Харкова. Два розроблені програмні комплекси сертифіковані УкрСЕПРО.

ВИСНОВКИ

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

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

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

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

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

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

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

7. Результати теоретико-експериментальних досліджень реалізовано і впроваджено у вигляді прикладних та дослідницьких програмних комплексів, які використовуються при пошуку та розпізнаванні зображень у колекціях значної місткості, два з яких сертифіковані УкрСЕПРО. Метод порівняння частково впорядкованих щодо вкладення фактор-множин дозволив розв'язати задачу розпізнавання патології на ультразвукових зображеннях та розпізнавання шорсткості метрологічних еталонів.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Киношенко Д.К., Путятин Е.П. Анализ методов поиска в коллекциях изображений // Системи управління, навігації та зв'язку. - К.: Центральний науково-дослідний інститут навігації і управління, 2007. - Вип. 3. - С. 408-411.

2. Киношенко Д.К. Метрические свойства кластеризации при поиске в коллекциях изображений // Системні технології. - Дніпропетровськ: "Системні технології", 2007. - № 2(49). - С. 167-176.

3. Егорова Е.А., Киношенко Д.К., Машталир C.В., Шляхов Д.В. Метрическое сравнение результатов сегментации изображений // Радиоэлектроника и информатика. - 2006. - № 2. - С. 55-62.

4. Kinoshenko D., Mashtalir V., Shlyakhov V. A Partition metric for clustering features analysis // International Journal Information Theories and Applications. - 2007. - 14. - № 3. - Р. 230-236.

5. Kinoshenko D., Mashtalir S., Yegorova E. Image normalization via salient points of skeletons // ICGST International Journal on Graphics, Vision and Image Processing. Special Issue on Features and Analysis. - 2006. - P. 1-7.

6. Сhupikov A., Kinoshenko D., Mashtalir V., Shcherbinin K. Image retrieval with segmentation-based query // Adaptive Multimedia Retrieval: User, Context and Feedback / S. Marchand-Maillet et al. (Eds.). - Geneva, Switzerland, July 27-28, 2006. - Lecture Notes in Computer Science. - Berlin-Heidelberg: Springer-Verlag. - Vol. 4398. - 2007. - Р. 208-222.

7. Bobrowski L., Kinoshenko D., Mashtalir V., Shlyakhov V. A metric on partial ordering partitions for image segmentation evaluation // Proc. of IX-th Int. Conf. Pattern Recognition and Information Processing. - Minsk, Belarus, May 22-24, 2007. - Minsk: UIIP of NAS of Belarus. - Vol. I. - 2007. - Р. 30-34.

8. Kinoshenko D., Mashtalir S., Shcherbinin K., Yegorova E. Image partition transforms for faithful segmentation search // Proc. of Fifth International Conference on Information Research and Applications. - Varna, Bulgaria, June 26-30, 2007. - Sofia: FOI-COMMERCE. - Vol. II. - 2007. - P. 385-389.

9. Каграманян А.Г., Киношенко Д.К., Чупиков А.Н., Щербинин К.С. Мультипороговая сегментация с использованием признаков формы // Материалы международной конференции "Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий". Евпатория, 14-18 мая 2007 г. - Херсон: ПП Вышемирский В.С., 2007. - Т. 3. - С. 143-146.

10. Kinoshenko D., Mashtalir V., Yegorova E. Clustering Method for Fast Content-Based Image Retrieval // Computer Vision and Graphics / Wojciechowski K. et al. (Eds.). - Warsaw, Poland, Sept. 22-24, 2004. - Computational Imaging and Vision. - Springer. - Vol. 32. - 2006. - P. 946-952.

11. Егоров А.С., Киношенко Д.К. Анализ признаков цвета для контекстного поиска изображений // Материалы 10-го юбилейного Международного молодежного форума "Радиоэлектроника и молодежь в XXI веке". Харьков, 10-12 апреля 2006 г. - Харьков: ХНУРЭ, 2006. - С. 278.

12. Kinoshenko D., Mashtalir V., Yegorova E., Vinarsky V. Hierarchical Partitions for Content Image Retrieval from Large-Scale Database // Machine Learning and Data Mining in Pattern Recognition / Perner P., Imlya A. (Eds.). - Leipzig, Germany, July 9-11, 2005. - Lecture Notes in Artificial Intelligence. - Springer-Verlag. - Vol. 3587-2005. - P. 445-455.

13. Егоров А.С., Киношенко Д.К. Выбор признаковых пространств при контекстном поиске зображений // Материалы 9-го Международного молодежного форума "Радиоэлектроника и молодежь в XXI веке". Харьков, 19-21 апреля 2005 г. - Харьков: ХНУРЭ, 2005. - С. 410.

14. Киношенко Д.К. Контекстный поиск в базах данных изображений // Материалы 8-го Международного молодежного форума "Радиоэлектроника и молодежь в XXI веке". Харьков, 19-21 апреля 2004 г. - Харьков: ХНУРЭ, 2004. - С. 90.

15. Kinoshenko D., Mashtalir V. Orlov A., Yegorova E. Method of creating of functional invariants under one parameter geometric transformations // Pattern Recognition / Michaelis B., Krall G. (Eds.). - Magdeburg, Germany, Sept. 10-12, 2003. - Lecture Notes in Computer Science. - Berlin-Heidelberg: Springer-Verlag. - Vol. 2781. - 2003. - P. 68-75.

16. Киношенко Д.К., Путятин Е.П. Пространственное позиционирование объектов на базе нормализации плоских контуров // Матер. 9-й Международной научной конференции "Теория и техника передачи, приема и обработки информации". Туапсе, 7-10 октября 2003 г. - Х. -Туапсе. - 2003. - С. 357.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - системи та засоби штучного інтелекту. - Харківський національний університет радіоелектроніки, Харків, 2008.

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

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

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

АННОТАЦИЯ

Киношенко Д.К. Модели поиска и распознавания изображений в базах данных. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта. - Харьковский национальный университет радиоэлектроники, Харьков, 2008.

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

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

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

Исследована проблема вычислительной сложности поиска изображений по их содержанию. Выявлены пути снижения временных затрат, предложены варианты поиска на основе матриц попарных расстояний между элементами базы данных. Предложены оценки расстояний, при использовании которых на этапе поиска исключаются из рассмотрения целые семейства множеств. Синтезированы алгоритмы индексации на полной и "разреженной" матрицах расстояний, бинарного дерева и разбиений, проведен их сравнительный анализ. Установлено, что метод на полной матрице требует наименьшего количества операций сравнения, однако ввиду требуемых значительных объемов памяти в базах данных большого объема следует использовать метод разбиений с разработанным эвристическим алгоритмом выбора опорных точек. Выявлены их общие недостатки - невозможность обеспечения гарантированного числа операций сравнения и зависимость от стратегии выбора опорных точек. В связи с этим введен и исследован метод приведения матрицы расстояния к блочно-диагональному виду. На начальном этапе построения минимизируется количество блоков, что может быть использовано в задаче поиска ближайшего к запросу кластера. Далее выполняется процедура оптимального дробления блоков, направленная на минимизацию числа операций сравнения. Применение блочно-диагональной формы исследовано на изображениях из базы данных Berkley. Элементы матрицы расстояний составлены путем метрического сравнения соответствующих фактор-множеств поля зрения изображений. Показана высокая степень инвариантности метода к используемому алгоритму сегментации.

Обсуждены особенности реализации системы поиска изображений по разбиениям. Отмечено, что разработанный программный комплекс PIRS (Partition image retrieval system) является модульным, распределенным и кроссплатформенным. Система поддерживает два варианта задания запроса: по всем разбиениям поля зрения изображения запроса или по выделенной области интереса, состоящей из одного или более разбиений. Форма и вид разбиений редактируются специализированной программой Coloring. Проведенный сравнительный анализ качества и полноты поиска разработанного программного комплекса с системами-аналогами SIMPLIcity и blobworld показал преимущество PIRS.

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

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

ABSTRACT

Kinoshenko D.K. Models of image retrieval and recognition from databases. - Manuscript.

The thesis for the candidate degree in technical sciences on the specialty 05.13.23 - Artificial Intelligence Systems and Means. - Kharkiv National University of Radio Electronics, Kharkiv, 2008.

The thesis is devoted to developing of methods and models of image segmentation results processing, analysis and indexing in order to increase efficiency and effectiveness of image retrieval systems which use images as queries.

Model of quotient set comparison is introduced, grounded and studied what allows fulfilling analysis of image segmentation results for adjustment of its refining level. Integral measures of quotient sets nesting are introduced. They create ground for the developed method of searching images by regions of interest. Novel method of indexation based on block-diagonal form of distance matrix which ensures guaranteed number of matches on the retrieval stage is provided and studied. Region-based image retrieval system which performs query by the whole of image or by regions of interest is developed and introduced. Experimental comparison has shown better performance of the developed system compared to SIMPLIcity and blobworld.

Keywords: database, retrieval, segmentation, quotient set, indexing, metric.

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

...