Вступ

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

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

Дослідники в даній галузі пропонують різні підходи від текстової індексації відеоданих до виділення характеристик рухомих об'єктів. Особливий внесок у розробку ефективних методів індексації внесли Байгарова Н.С., Бухштаб Ю.А (Інститут прикладної математики ім. М. В. Келдиша РАН, Москва), E. Ardizzone, M. La Cascia (University of Palermo).

Актуальність

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

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

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

Постановка задачі

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

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

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

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

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

Рисунок 1 - Виділення характеристик відеопотоку (анімація: об'ъєм - 19,1 КБ; розмір - 560x417; кількість кадрів - 5; затримка між кадрами - 165 мс; затримка між першим та останнім кадром - 170 мс; кількість циклів повторення - 5).

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

Практична цінність

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

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

Застосування даного програмного продукту в пошукових системах здатне істотно полегшити пошук відео в мережі Інтернет. Також доцільно застосовувати даний продукт в організаціях, що мають великі архіви відеоматеріалів.

Методи пошуку відеоінформації

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

1. Метод колірних гістограм

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

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

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

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

2. Метод оптичного потоку

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

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

Складні дані про рух, отримані після обчислення оптичного потоку, повинні бути приведені до простої та придатної для індексування та пошуку форми [2].

4. Методи сегментації зображень.

Сегментацією зображення називається розбиття зображення на несхожі за деякою ознакою області [3]. Отримані в результаті області характеризуються розташуванням на зображенні і розмірами. Крім того, вони зв'язуються зі значеннями примітивів - характеристиками форми, кольору, текстури [1].

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

Задачі автоматичної сегментації поділяються на два класи:

• виділення областей зображення з відомими властивостями
• розбиття зображення на однорідні області

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

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

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

Кластеризація - об'єднання в групи схожих об'єктів - є однією з фундаментальних завдань в галузі аналізу даних [4].

В якості ознак точки зображення можна використовувати подання її кольору в деякому колірному просторі, прикладом метрики (міри близькості) може бути Евклідова відстань між векторами в просторі ознак. Тоді результатом кластеризації буде квантування кольору для зображення [3].

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

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

Серед неієрархічних алгоритмів, не заснованих на відстані, слід виділити EM-алгоритм (Expectation-Maximization). У ньому замість центрів кластерів передбачається наявність функції щільності ймовірності для кожного кластеру з відповідним значенням математичного очікування і дисперсією [4].

Наукова новизна

Наукова новизна даної роботи полягає в наступному:

• у роботі пропонується на етапі попередньої обробки здійснити конвертацію статистичних зображень (кадрів) з колірного простору RGB в простір CIE-L*u*v*;
• при виділенні характеристик окремих кадрів аналізуються примітиви не всього зображення, а окремих кластерів;
• на етапі виділення відеофрагментів передбачається проводити сегментацію не цілого кадру, а по окремих сегментах.

Основні результати

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

1. Проведено теоретичний аналіз існуючих підходів і методів для вирішення завдання пошуку відеофрагментів.
2. Виділені основні напрямки для оптимізації проаналізованих методів.
3. Розроблена програмна система виділення сегментів відеоінформації. Дання система дозволяє:
   • вибирати відеофайли для розбору на сегменти;
   • переглядати результати сегментації;
   • зберігати результати в БД;
4. Реалізовано програму пошуку відеофрагментів з використанням примітивів колірних гістограм.

Висновок

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

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

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

Література

1. Байгарова Н.С., Бухштаб Ю.А., Евтеева Н.Н., Корягин Д.А. Некоторые подходы к организации содержательного поиска изображений и видеоинформации [Електронний ресурс] / Институт прикладной математики им. М. В. Келдыша РАН, - http://www.keldysh.ru/papers/2002/prep78/prep2002_78.html
2. Байгарова Н.С., Бухштаб Ю.А., Евтеева Н.Н. Современная технология содержательного поиска в электронных коллекциях изображений [Електронний ресурс] / Институт прикладной математики им. М.В. Келдыша РАН, - http://www.elbib.ru/index.phtml?page=elbib/rus/journal/2001/part4/BBE
3. Вежневец А., Баринова О. Методы сегментации изображений: автоматическая сегментация [Електронний ресурс]: http://cgm.computergraphics.ru/content/view/147
4. Паклин Н. Алгоритмы кластеризации на службе Data Mining [Електронний ресурс]: http://www.basegroup.ru/library/analysis/clusterization/datamining
5. Байгарова Н.С., Бухштаб Ю.А. Проект «Кинолетопись России»: представление и поиск видеоинформации // I Всероссийская конференция «Электронные библиотеки». - Санкт-Петербург, 1999. - с. 209-215.
6. Вовк О.Л. Особенности контекстного поиска кластеризированных изображений // VII международная конференция «Интеллектуальный анализ информации ИАИ-2007». – Киев, 2007. - с. 22-31.
7. Башков Е.А., Вовк О.Л. Статистическая кластеризация для выделения регионов изображений // V международная конференция «Интеллектуальный анализ информации ИАИ-2005». – Киев, 2005. - с. 50-59.
8. Башков Е.А., Вовк О.Л. Математическая модель статестического иерархического алгомеративного метода кластеризации изображений // Научные труды Донецкого национального технического университета. Серия «Информатика, кибернетика и вычислительная техника». Выпуск 8 (120) – Донецк: ДонНТУ, 2008. - с. 39-46.
9. Вовк О.Л. Новый подход к выделению визуально подобных цветов изображений // Проблемы управления и информатики Институт кибернетики В.М. Глушкова НАН Украины, институт космический исследований. – Киев, 2006 — № 6. - c. 100–105.
10. Zhong Di,Zhang Hong-Jiang,Chang Shih-Fu Clustering Methods for Video Browsing and Annotation [Електронний ресурс]: [PDF] http://www.ee.columbia.edu/dvmm/publications/96/zhong96a.pdf

Примітка

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