КОМПЬЮТЕРНАЯ ГРАФИКА
УДК 681.3.06
МЕТОДЫ ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ
© 2009 г. Н. С. Васильева
HP Labs Russia 191194 Санкт-Петербург, ул. Артиллерийская, 1 E-mail: nvassilieva@hp.com Поступила в редакцию 06.02.2008 г.
Создание системы поиска изображений по содержанию подразумевает решение целого ряда непростых задач, в числе которых анализ низкоуровневых характеристик изображения и построение векторов признаков, многомерное индексирование, проектирование пользовательского интерфейса системы и визуализация данных. Качество системы поиска зависит, в первую очередь, от используемых векторов признаков, описывающих содержание изображения.
В этой статье представлен обзор основных алгоритмов построения векторов признаков и метрик для соответствующих им пространств. Рассматриваются признаки для таких характеристик изображения, как цвет, текстура и форма объектов. В работе приведена подробная классификация известных на сегодняшний день признаков, а также результаты экспериментальных сравнений эффективности различных методов представления и сравнения содержания изображений применительно к задачам поиска и классификации.
1. ВВЕДЕНИЕ
Исследованию вопросов, связанных с индексированием и поиском изображений, уделяется много внимания на протяжении последних десятилетий. Этому способствуют многие факторы, среди которых рост доступных объемов памяти, широкое распространение цифровой фотографии и, как следствие, рост объемов коллекций изображений. Повышенный интерес научного сообщества к задаче поиска изображений свидетельствует об ее актуальности. Но, несмотря на разнообразие предложенных алгоритмов индексирования и поиска изображений, данную задачу все еще нельзя признать решенной. Качество работы существующих систем поиска изображений оставляет желать лучшего.
Поиск изображений по содержанию (Content Based Image Retrieval, CBIR) предполагает отсутствие какой-либо дополнительной информации о картинках, как, например, текстовые аннотации, время или место создания. Для решения задачи поиска анализируется содержание изображения - численные характеристики составляющих его пикселей. Альтернативой поиску по содержанию является поиск по текстовым
аннотациям (Description Based Image Retrieval, DBIR). Такой поиск возможен только при наличии у всех изображений коллекции аннотаций, описывающих их содержание. Тогда задача поиска изображений сводится к классической задаче текстового поиска. Рассмотрение методов поиска изображений по аннотациям вкупе с различными алгоритмами автоаннотирования выходит за рамки данного обзора.
Выделяют три основных направления исследований в области CBIR [1].
Построение векторов признаков. Поиск различных способов описания изображений и их сравнения между собой. В рамках данного направления предлагаются все новые виды векторов признаков и способы их вычисления, а также новые метрики, заданные на пространстве этих векторов.
Многомерное индексирование. Разработка алгоритмов многомерного индексирования, подходящих для задач CBIR, для которых характерна высокая размерность и большие объемы индексируемых данных.
Проектирование систем поиска. Важной особенностью любой системы является ее эрго-
51
4*
номичность - удобство работы с ней для пользователя. Для систем CBIR этот параметр играет особенную роль ввиду сложности таких систем. Как показать пользователю одновременно большое количество изображений, которые система отобрала в качестве ответа на запрос? Как предоставить пользователю возможность оценить качество поиска, чтобы в дальнейшем было возможно учесть эту оценку для уточнения результата поиска? Как построить диалог пользователя с системой? Поиск ответов на эти вопросы -задача исследователей, занимающихся проектированием систем поиска.
От алгоритмов построения векторов признаков зависит качество поиска. Многомерное индексирование позволяет сделать поиск быстрым. Эргономичный интерфейс системы поиска поможет пользователю правильно сформулировать запрос, уточнить его на последующих шагах общения с системой, облегчить работу с поисковой системой в целом.
В данном обзоре рассматриваются наиболее известные алгоритмы построения векторов признаков изображений - затрагивается только первое направление исследований из вышеперечисленных. Под векторами признаков (feature vector) (или просто признаками) будем понимать набор численных параметров, описывающих отдельно взятое изображение. Большинство таких векторов описывают какую-либо одну характеристику изображения. К характеристикам изображения относят цвет, текстуру, форму объектов на изображении. Иногда для этих же понятий используют термин признак, что на наш взгляд в данном случае является неудачным переводом англоязычного термина feature1. Вектора признаков, построенные с помощью одного и того же алгоритма, образуют пространство векторов признаков (сокращенно пространство признаков). Задав метрику на таком пространстве, можно сравнивать изображения друг с другом, вычисляя расстояние между соответствующими им векторами.
1 По наличию или отсутствию того или иного признака можно отнести объект к тому или иному классу. В нашем случае не ясно, как в роли признаков изображения могут выступать понятия цвета или текстуры. Тут речь идет не о наличии на изображении определенного цвета или текстуры, а об общих понятиях цвета, текстуры изображения.
Многие исследователи выделяют несколько уровней содержания изображений и соответствующих им характеристик [2]. Текстовые аннотации описывают семантику изображения, являясь характеристиками содержания высокого уровня (high-level features). Визуальные характеристики, такие как цвет и текстура, называют низкоуровневыми (low-level features). Некоторые исследователи относят к низкоуровневым характеристикам также и форму объектов на изображении, информация о которой может быть получена путем анализа текстуры. Другие говорят о форме как о характеристике среднего уровня.
Цвет, текстуру и форму объектов относят к общим характеристикам. Они используются в большинстве систем CBIR и подходят для поиска по коллекциям изображений разнородного содержания. В случае определенной предметной области часто можно выделить специфические для данной области характеристики. Например, форма глаз, носа, рта и овала лица при распознавании лиц, или кривые отпечатков пальцев. Можно сказать, что такие характеристики являются уточнением, частным случаем перечисленных выше общих характеристик.
Для каждой характеристики существует большое количество способов построения описывающего ее вектора признаков. Но среди них невозможно выделить абсолютных победителей. Каждый имеет свои достоинства и недостатки. И до сегодняшнего дня исследователи продолжают работать над созданием новых алгоритмов и усовершенствованием существующих.
Далее в данном обзоре будут рассмотрены наиболее известные алгоритмы построения векторов признаков для цвета (раздел 5), текстуры (раздел 6) и формы объектов (раздел 7). В разделе 4 представлена общая классификация рассматриваемых алгоритмов. Но перед тем, как приступить к обсуждению различных пространств признаков, познакомимся с традиционной архитектурой систем поиска изображений по содержанию (раздел 2) и рассмотрим основные проблемы в данной области (раздел 3). В завершение обзора в разделе 8 представлены наиболее известные на сегодняшний день системы поиска изображений по содержанию; перечислены пространства признаков, которые используются в этих системах. Раздел 9 является заключением к обзору.
Хранилище изображений
Индексирование
индексирован ие
изображения
вычисление признаков
запрос
поиск по индексу
База данных
Поиск
Рис. 1. Традиционная архитектура систем CBIR.
2. ТРАДИЦИОННАЯ АРХИТЕКТУРА СИСТЕМ СВГО,
Традиционная архитектура систем поиска изображений по содержанию (рис. 1) имеет много общего с архитектурой классических поисковых систем. Для систем CBIR также характерно выделение двух модулей: модуля индексирования и модуля поиска. Первый отвечает за обработку данных и построение индексных структур, позволяющих значительно ускорить поиск. Второй модуль занимается непосредственно поиском по запросу пользователя.
Одной из ключевых компонент системы CBIR является компонента, отвечающая за параметризацию изображения - вычисление векторов признаков. На вход данной компоненте подается изображение - матрица значений его пикселей. Изображение анализируется, и по нему вычисляются вектора признаков, передаваемые дальше в модуль индексирования. Именно по векторам признаков изображения и строится индекс. Во время поиска также необходимо участие компоненты вычисления признаков, если поиск происходит по изображению-образцу, загруженному пользователем (отсутствующему на момент начала поиска в коллекции, по которой производится поиск). Необходимо вычислить признаки для изображения-запроса, используя те же са-
мые алгоритмы, с помощью которых вычислялись признаки для изображений коллекции. Далее поиск производится по полученным векторам признаков изображения-запроса.
Традиционным подходом для поиска по содержанию является независимый поиск по различным характеристикам изображения, каждая из которых описывается точкой в соответствующем пространстве признаков. Некоторые системы используют несколько пространств признаков для описания одной и той же характеристики с целью повышения точности поиска. В таком случае поиск в каждом из пространств признаков также производится независимо, после чего используются методы синтеза данных (Data Fusion) для смешивания полученных результатов (промежуточных выдач) в одну общую выдачу. Под выдачей здесь понимается ранжированный набор объектов поиска, представляющий собой ответ поисковой системы на заданный запрос. Распространенным решением для комбинирования результатов поиска по различным признакам является использование линейной комбинации рангов элемента в каждой из промежуточных выдач для вычисления его ранга в общей выдаче. В литературе также описаны методы синтеза, изначально предложенные авторами для комбинирования промежуточных
выдач в текстовом поиске. Применимость э
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.