Описание

Теория по поиску изображений

Российской академии наук

Н.С.Байгарова, Ю.А.Бухштаб, Н.Н.Евтеева, Д.А.Корягин

Некоторые подходы к организации содержательного

поиска изображений и видеоинформации

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

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

The paper discusses various questions connected with content-based visual information description on differen levels of abstraction. The access technology for image and video collections is developed on the base of corresponding visual primitives. Once the distance between the template image and each target image is computed, target images can be ranked in order of their similarity with the template image.

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант N 01-01-00267.

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

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

Визуальные примитивы и механизм поиска по образцу

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

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

3. Методы анализа изображений

Различными группами исследователей уже накоплен определенный опыт реализации алгоритмов, позволяющих автоматически описывать изображения в терминах простых вычислимых визуальных свойств, а также определять меру их отличия. Авторами был подготовлен обзор этих алгоритмов [8].

Наши текущие исследования в этой области направлены на дальнейшее развитие методов вычисления и сравнения визуальных примитивов. Реализован метод количественной оценки близости статичных изображений по их цветовым гистограммам. Решена задача пространственного сегментирования изображения. Разработан и реализован алгоритм, осуществляющий вычисление параметров форм для выделенных объектов картинки и сравнение форм по их параметрам. Проводятся работы и имеются результаты, которые позволят выполнять локальное индексирование, отражающее распределение на изображении цветовых множеств. С целью вычисления измерений текстур исследуются возможности использования метода функций Габора и характеристик матрицы взаиморасположения оттенков серого цвета. (Методы обработки текстур изложены в [10, 20, 22, 26].)

3.1. Цветовые гистограммы

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

Идея метода цветовых гистограмм для индексирования и сравнения изображений сводится к следующему. Все множество цветов разбивается на набор непересекающихся, полностью покрывающих его подмножеств Vi, 0<=i<N. Будем называть такое разбиение множества цветов базовой палитрой. Для изображения формируется гистограмма, отражающая долю каждого подмножества цветов в общей цветовой гамме изображения - массив H[i]=N[i]/ ? N[i], где N[i] - число точек с цветом из множества Vi. Для сравнения гистограмм вводится понятие расстояния между ними. Известны различные способы построения и сравнения цветовых гистограмм [1, 2, 8, 19, 20], отличающиеся между собой изначальной цветовой схемой(RGB, CMY, HSV, grayscale и т. д.), размерностью гистограммыиопределением расстояния между гистограммами.

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

1) Разбиение RGB-цветов по яркости.

В базовой палитре Vi (0<=i<N) определяется как множество цветов C. C ?Vi?i/N*Imax<=I(C)< (i+1)/N*Imax, где I(C) – интенсивность цвета C, нормализованная так, что 0<=I(C)<Imax. Интенсивность вычисляется по классической формуле:

где R, G и B – красная, зеленая и синяя компоненты цвета C. Imax=256; 0<=I(C)<256. В частности, для черно-белых полутоновых изображений наNподмножеств разбивается исходное множество оттенков. Значение N выбиралось практически произвольно, сейчас установлено N=16.

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

R3(i)=?H1[i]-H2[i+1]?(для i=0 и i=N вместо невычислимых разностей подставляются заведомо большие значения), итоговое же расстояние равно:

Этот способ не годится для произвольной базовой палитры, т. к. предполагает строгую упорядоченность множества цветов, как в случае с разбиением по яркости. Заметим, что так определенное S не является расстоянием в математическом смысле из-за несимметричности (нельзя гарантировать, что S(H1,H2)= S(H2,H1)). Основное преимущество алгоритма состоит в том, что он слабо чувствителен к изменению освещенности, что ощутимо улучшает результаты его применения на широком классе изображений.

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

2) Разбиение RGB-цветов по прямоугольным параллелепипедам.

Цветовое RGB-пространство рассматривается как трехмерный куб, каждая ось которого соответствует одному из трех основных цветов (красному, зеленому или синему), деления на осях пронумерованы от 0 до 255 (большее значение соответствует большей интенсивности цвета). При таком рассмотрении любой цвет RGB-изображения может быть представлен точкой куба. Для построения цветовой гистограммы каждая сторона делится на n (n=4) равных интервалов, соответственно RGB-куб делится на N (N=64) прямоугольных параллелепипедов. Vi – множество цветов, все компоненты которых попадают в определенные интервалы. Гистограмма изображения отражает распределение точек RGB-пространства, соответствующих цветам пикселов изображения, по параллелепипедам.

Выбор размерности гистограммы определялся из следующих соображений. При n=2 (N=8) считались бы одинаковыми, например, <126,128,126> и <0, 255, 0>, что, естественно, недопустимо. Установка n=8 (N=512) приводит к тому, что базовая палитра становится более строгой, чем 8-битная. Такая точность не только автоматически дает некорректную обработку 256-цветных изображений, но и на остальных изображениях приводит к неестественным результатам. Очевидно, что при росте n ситуация только ухудшается. Поэтому было установлено n=4.

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

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

3.2. Объекты изображения

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

Контур - граница объекта - представляет собой замкнутую последовательность точек (xs, ys),где1<=s<=N. Удобно считать, что (xs+N, ys+N) = (xs, ys). Задача выявления контуров связана с локализацией на изображении резких перепадов яркости цвета или изменений параметров, характеризующих текстуру.

Определение границ объектов изображения выполняется нами по следующей схеме: цветное изображение переводитсяв черно-белое полутоновое и сглаживается, осуществляется пространственное дифференцирование - вычисляется градиент функции интенсивности в каждой точке изображения и, наконец, подавляются значения меньше установленного порога. За основу взят метод Собеля[23], использующий для вычисления градиента первого порядка функции интенсивности специальные ядра, известные как «операторы Собеля»:

Ядра применяются к каждому пикселу изображения: он помещается в центр ядра, и значения интенсивности в соседних точках умножаются на соответствующие коэффициенты ядра, после чего полученные значения суммируются. Х- оператор Собеля, примененный к 3х3 матрице исходного изображения, дает величину горизонтальной составляющей градиента интенсивности в центральной точке этой матрицы, а Y-оператор Собеля дает величину вертикальной составляющей градиента. Коэффициенты ядра выбраны так, чтобы при его применении одновременно выполнялось сглаживание в одном направлении и вычисление пространственной производной – в другом.

Величина градиента определяется как квадратный корень из суммы квадратов значений горизонтальной и вертикальной составляющих градиента.

В результате образуется массив чисел, характеризующих изменения яркости в различных точках изображения. Затем выполняется операция сравнения с порогом и определяется положение элементов изображения с наиболее сильными перепадами яркости. Выбор порога является одним из ключевых вопросов выделения перепадов. В нашей реализации он отличается от оригинального метода Собеля. В качестве основного порога берется средняя для изображения величина градиента - Smid. Для достаточно большого изображения с малым числом точек, обладающих сильным перепадом яркости, данной пороговой величины недостаточно, т.к. оказывается весьма сильным влияние шума. Для ликвидации этой проблемы для каждой точки изображения считается величинаSlocal, равная средней величине градиента в области 3х3 вокруг анализируемой точки. Пороговое условие выглядит так:

(G(i, j)>=Smid) AND (Slocal >= Smid)

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

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

Следующий этап – сегментация изображения. Целью сегментации является выделение на изображении контуров объектов. В бинарной матрице единицами представлены точки, принадлежащие искусственно утолщенным на предыдущем этапе границам объектов. Для выделения границы одного объекта в матрице по определенному алгоритму ищется элемент, равный единице, не отнесенный ранее ни к какому другому объекту; далее считается, что все соседние элементы, равные единице, также принадлежат этому объекту; и т. д. Для выделения точек внешнего контура используется обход полученного объекта по внешней его стороне, начиная с нижней левой точки объекта и заканчивая ею же. Обход точек ведется последовательно против часовой стрелки. В результате получаем массив точек, образующий замкнутый контур объекта. Из него равномерно выбирается 128 точек (xs, ys), где 1<=s<=128, которые используются для вычисления предназначенных для индексирования характеристик формы. (Небольшие объекты исключаются из рассмотрения.)

3.3. Характеристики формы

Существует практика использования формы объектов для индексирования изображений с целью их дальнейшего сравнения [2, 8, 26].

Для точек выделенного контура объекта в данной работе вводятся две функции.

Ф
ункция расстояния от точек контура до центра фигуры:

где (xc=? xs /N, yc=? ys/N ) - центр масс контура

Для обеспечения инвариантности относительно поворотов и масштаба, выполняется нормирование величин, а в качестве начальной точки контура берется та, расстояние до центра от которой наименьшее, соответственно упорядочиваются элементы векторов.

Предлагается способ сравнения форм объектов на основании вычисления общего расстояния между парами соотвествующих векторов.

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

4. Методы анализа видеоданных

4.1. Временное сегментирование видеофильма

Временное сегментирование может выполняться путем автоматического анализа изображения, соответствующие приемы известны [3, 6, 12, 25]. Достаточно эффективны для выделения кадров, на которых происходит значительное изменение видеоизображения, методы, основывающиеся на вычислении низкоуровневых характеристик изображения.

Предлагается алгоритм, основанный на сравнении цветовых гистограмм соседних кадров. Система вычисляет цветовую гистограмму очередного кадра и сравнивает с предыдущей. Построение и сравнение гистограмм осуществляются идентично работе со статичными изображениями. Есть дополнительная возможность “выравнивания” гистограмм, применение которой имеет смысл только в случае разбиения множества цветов по яркости. Целью ее является приведение гистограммы к виду, при котором верно:

После этого все точки гистограммы пересчитываются, исходя из соотношения:

H'[i]=(H[k/(N/2)*i]+ H[k/(N/2)*i+1])/2, при 0<=i<N/2 и аналогичного выражения для N/2<=i<N. Оригинальная гистограмма заменяется на H'. Потребность такой обработки объясняется тем, что во многих реальных образцах видео (особенно черно-белых и/или плохого качества) часто встречаются практически идентичные соседние кадры, отличающиеся только по яркости среднего освещения. Семантически они должны попадать в один фрагмент, но их первоначальные гистограммы могут существенно различаться, что и приводит к необходимости выравнивания. Прием не дает полного решения проблемы, но, по крайней мере, существенно улучшает результаты на широком классе изображений.

Результатом сравнения гистограмм последовательных кадров является массив R[i] чисел от 0 до 2, где i-ый компонент – расстояние между гистограммами i-ого и (i+1)-ого кадров. Опираясь на эти данные, фильм разбивается на фрагменты. Граница фрагментов считается обнаруженной, если разница гистограмм рассматриваемых соседних кадров выше некоторого абсолютного порога и одновременно в определенное число раз превышает среднее значение разницы гистограмм соседних кадров, посчитанное по кадрам от начала выделяемого фрагмента (относительный порог).

Попытка ограничиться абсолютным порогом L не привела к успеху. Значение порога, дающее желаемые результаты, существенно зависит от качества записи фильма, динамики его связных фрагментов и средней освещенности, а эти характеристики могут быть различны в разных фрагментах одного и того же фильма (т. е. для их вычисления потребуются уже готовые результаты временной сегментации), а кроме того, определение, например, качества записи - трудная задача, и зависимость от нее неизбежно внесет дополнительную погрешность в итоговый результат. Аналогично, не удалось решить задачу и введением относительного порога, т. е. такого M, что при R[i]>M*?R[j]/(i-1-k) (сумма берется от k до i-1, k-й кадр – первый в текущем фрагменте), (i+1)-й кадр считается началом следующего фрагмента. Проблема заключается в возможности практически полного совпадения первых нескольких гистограмм фрагмента и минимального отличия от них следующей - условие порога будет выполнено, и программа выдаст лишний фрагмент. Наиболее эффективной оказалась комбинация этих подходов, т. е. для принятия решения о том, что (i+1)-й кадр – начало нового фрагмента требуется выполнение обоих условий:

Результаты сегментирования, разумеется, сильно зависят от выбора параметров. Они установлены эмпирически для достижения приемлемых результатов с точки зрения минимизации числа ошибок, связанных с обнаружением ложной границы и пропуском действительной. (При уменьшении вероятности одной из ошибок, неизбежно повышается вероятность другой.) Текущие значения L=0.15 иM=3 подобраны так, чтобы ложные обнаружения встречались примерно на порядок чаще, чем пропуск переходов. Вызвано это тем, что на“двойном” видеофрагменте невозможно корректно вычислить оптический поток, что является одной из главных целей временного сегментирования, в то время как два фрагмента вместо одного дают лишь некоторое увеличение требуемых для дальнейшей обработки ресурсов.

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

1 - Палитра разбивается по интенсивности.

2 - Палитра разбивается на RGB-параллелепипеды.

3 – Квадродерево & палитра разбивается по интенсивности.

4 – Квадродерево & палитра разбивается на RGB-параллелепипеды.

5 - Палитра разбивается по интенсивности, применяется усложненная формула расстояния и выравнивание гистограмм.

(Процент ошибок – отношение числа ошибок к сумме ошибок и верно обнаруженных переходов, умноженное на 100%.)

4.2. Индексирование видеофрагментов

После того как видеопоток разбивается на фрагменты, из них выделяются для исследования ключевые стоп-кадры. Стратегия извлечения представительных стоп-кадров из каждого выделенного фрагмента может быть, например, такой[1]: если фрагмент короче секунды, берется один центральный кадр, для более длинных фрагментов берется по одному в секунду. Для каждого выделенного кадра вычисляются с целью индексирования визуальные примитивы: цветовые гистограммы, характеристики формы и цвета объектов изображения, измерения текстуры; для этого применяются те же методы, что и для анализа статичных изображений. Кроме того, представляется важным индексировать фрагмент также характеристиками движения камеры/сцены и движения объектов, определяемыми на основании совокупности кадров видеофрагмента[3, 6].

4.3. Вычисление оптического потока

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