Введение

Постоянное увеличение мощностей, пропускной скорости каналов связи и объемов дискового пространства привело к накоплению огромного числа больших электронных библиотек, которые публично доступны в сети Интернет.

С каждым годом количество оцифрованной видеоинформации увеличивается. Необходимы эффективные методы автоматической индексации и поиска видеоданных.

Исследователи в данной сфере предлагают различные подходы от текстовой индексации видеоданных до выделения характеристик движущихся объектов. Особый вклад в разработку эффективных методов индексации внесли Байгарова Н.С., Бухштаб Ю.А (Институт прикладной математики им. М.В. Келдыша РАН, Москва), E. Ardizzone, M. La Cascia (University of Palermo).

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

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

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

В данной ситуации возникает проблема обеспечения эффективного поиска информации в огромных массивах данных. Эта проблема знакома каждому, кто пробовал найти определенное изображение или видео, при этом используя ключевые слова, которые задаются при традиционном поиске. Этот способ поиска осуществляется с использованием аналогичных веб-поиску алгоритмов ранжирования, разбора запросов и т.п. Однако, поиск по названию, авторам, теме, словам описания содержания и по другой текстовой информации, ассоциированной с видеоданными, представляется недостаточным. Этот метод является трудоёмким и не может обеспечить законченное описание видеоинформационного наполнения. Неоднозначность соответствия между визуальным содержанием и текстовым описанием снижает показатели точности и полноты поиска. Так же этот способ поиска исключает возможность поиска видео по отрывку или ключевому кадру, сделанному с оригинального видео [1].

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

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

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

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

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

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

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

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

Практическая ценность

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

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

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

Методы поиска видеоинформации

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

1. Метод цветовых гистограмм.

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

Идея метода цветовых гистограмм для индексирования и сравнения изображений сводится к следующему. Все множество цветов разбивается на набор непересекающихся, полностью покрывающих его подмножеств. Будем называть такое разбиение множества цветов базовой палитрой. Для изображения формируется гистограмма, отражающая долю каждого подмножества цветов в общей цветовой гамме изображения – массив, хранящий число точек с цветом из множества цветов базовой палитрой. Для сравнения гистограмм вводится понятие расстояния между ними [1].

Данный метод плохо работает с изображениями, имеющими однородный фон и небольшое количество объектов. Гистограмма не отразит перемещение объекта из одной части кадра в другую, если этот объект не перекроет другой. Более точных результатов сравнения можно достичь, разбив изображения на 9 равных частей. И сравнивать соответствующие части двух изображений.

Сравнение изображений основывается на расстоянии, определенном как Евклидово в пространстве расстояний между гистограммами частей, итоговым результатом считается корень из суммы их квадратов.

2. Метод оптического потока.

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

Существуют разные алгоритмы вычисления оптического потока, но наиболее распространенным является дифференциальный метод расчета оптического потока. Основные принципы данного метода: а) при движении объекта интенсивность составляющих его точек не изменяется; б) гладкое изменение значения скорости от точки к точке.

Сложные данные о движении, полученные после вычисления оптического потока, должны быть приведены к простой и пригодной для индексирования и поиска форме [2].

3. Методы сегментации изображений.

Сегментацией изображения называется разбиение изображения на непохожие по некоторому признаку области [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 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.