Лукьянов Сергей Викторович

Автореферат

Введение

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

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

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

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

Исследования в области поиска изображений ведутся с 70-х годов прошлого века. Были разработаны методы и средства для текстового поиска изображений [1]. Каждое изображение аннотировалось, после чего помещалось в базу данных. Поиск изображения в таких системах сводился к поиску аннотаций, сопоставленных изображению. Но этот метод обладает двумя недостатками, проявляющимися при росте количества изображений (сотни тысяч).

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

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

• цвет (кореллограммы, цветовые моменты и множества цветов в различных цветовых пространствах);
• текстуры;
• контуры;
• пространственные отношения;
• выделение регионов (частей).

Созданы как исследовательские так и коммерческие системы контекстного поиска изображений. Яркими примерами таких систем являются [2]:

• QBIC (запросы по примеру и цветовым шаблонам);
• MARS (сочетание поиска по всем методам описания изображений с подсистемой индексации);
• VisialSEEK (по примеру и пространственным отношениям);
• WBIIS (Wavelet преобразование);
• SIMPLIcity (семантическое разделение, Wavelet преобразование и алгоритм сопоставления регионов) [3].

Теперь исследователи столкнулись со следующими проблемами:

• отсутствие средств и методов оценки качества работы систем контекстного поиска;
• отсутствие пути превращения исследовательских инструментов в сервисы доставки информации.

Средства оценки качества поиска помогли бы ответить на следующие вопросы [4]:

• возможно ли сравнивать текстовый поиск с поиском по содержимому?
• какой из методов контекстного поиска показывает лучшие результаты?
• какое оптимальное сочетание и каких методов позволяет добиться наиболее безошибочного поиска?
• существует ли "золотая середина" в балансировке поиска по мета-данным и поиска по содержимому?

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

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

На рисунке приведена структура системы контекстного поиска изображений [5].

_{Cтруктура системы контекстного поиска изображений}

Каждое изображение (запрос), подаваемое пользователем на вход, проходит тот же этап преобразований, что и изображения в БД. Из каждого изображения извлекается информация о визуальном наполнении (контуры, текстуры, границы) и цветовые характеристики (кореллограммы, цветовые моменты и т.п).

После чего определяется схожесть характеристик исходного и изображений из БД. Происходит индексация и ранжирование характеристик, после чего изображения извлекаются из БД.

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

Обзор существующих методов оценки результатов контекстного поиска

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

Т.е. методы оценки разделяют на два основных типа [2,5,6]:

• атоматические (человек только настраивает механизм оценки);
• неавтоматические (человек оценивает результаты поиска).

Неавтоматическая оценка

Ключевым звеном этого класса методов является человек. Сценарий проведения оценки в общем случае таков:

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

К недостаткам этой схемы необходимо отнести:

• большую длительность процесса оценки;
• малое множество запросов и как следствие, возможное, упущение оценки результатов работы некоторых внутренних механизмов системы поиска.

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

Автоматическая оценка

Автоматическая оценка предполагает существование некоторой системы (программно-аппаратного комплекса).

Структура системы автоматической оценки качества контекстного поиска

Структура системы автоматической оценки результатов работы систем контекстного поиска представлена на рисунке [7].

_{Структура системы оценки}

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

Система извлечения изображений возвращает похожие изображения.

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

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

Система знаний представляет собой экспертную систему по определению релевантности изображений. Т.е. существует набор правил (определения релевантности), в соответствии с которыми из запроса поиска формируется множество релевантных изображений в базе данных изображений.

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

Взаимодействие систем поиска осуществляется посредством недорого фиксированного протокола. Это может быть как MRML (Multimedia Retravial Markup Language) [8], так и собственные разработки, вплоть до оговоренного места в файловой системе.

Взаимодействия сервера оценки и системы извлечения изображений имеет следующий сценарий.

1. Прежде всего сервер оценки настраивает систему извлечения изображений. Здесь могут быть указаны такие параметры:
   • формат запроса (пример, набросок, категория, описание изображения);
   • формат входных изображений (размер, количество цветов, формат);
   • предпочтительный формат результирующих изображений;
   • размер порции изображений передаваемых за раз.
2. После конфигурирования сервер оценки выполняет свои задания. Каждое задание представляет собой группу запросов. По возвращению результатов запросов сервер вычисляет следующие характеристики:
   • время выполнения запроса;
   • релевантность результатов запроса (принадлежность каждого изображения к множеству релевантных изображений).
3. По результатам оценки релевантности могут формироваться дополнительные запросы.

Компоненты системы автоматической оценки

Оценка результатов поиска предполагает наличие следующих компонентов:

• коллекция документов (изображений);
• множество тестовых запросов;
• множество оценочных метрик (шкал).

Рассмотрим каждый компонент подробнее.

Коллекция документов

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

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

Тестовые запросы

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

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

1. из каждой категории представленной в коллекции выбирается 3-5 изображений;
2. на основе выбранных изображений генерируются запросы;
3. релевантные результаты модифицируются (искажаются) и отправляются как запросы.

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

Оценочные метрики

Так или иначе все оценочные метрики основываются на Отзыве (R, recall) и Точности(P, precision) [10].

Где
	N	- количество изображений в коллекции
	n	- количество изображений в результате поиска
	A	- количество релевантных изображений в коллекции
	a	- количество релевантных изображений в результате поиска

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

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

Также выделяют Осадок (F, fallout) и Общность (G, generality).

Осадок характеризует долю нерелевантных изображений в результате. Общность характеризует долю релевантных изображений в коллекций.

Было замечено, что

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

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

Было замечено,а позже доказано, что метрика

является коэффициентами косинуса. Многие специалисты соглашаются с тем, что эта метрика лучше предыдущих.

Модификации изображений

Многие системы контекстного поиска (например, SIMPLIcity [3]) устойчивы к модификациям изображений в коллекции. Следовательно, система оценки качества поиска должна проверять устойчивость системы контекстного поиска к модификациям изображений.

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

• поворот;
• масштабирование;
• добавление шума;
• применение фильтра Гауса;
• перенос объектов внутри изображения;
• отражение (горизонтально, вертикально).

Назначение проектируемой системы

Основное назначение проектируемой системы - автоматическая оценка систем контекстного поиска.

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

Дополнительные требования к изображениям БД:

1. изображения внутри одной группы не должны слишком отличаться формами представленных на них объектов;
2. внутри одной группы все изображения должны быть либо рисунками, либо фотографиями, либо текстурами; обязательно сделать группы текстурных изображений (например, текстуры - песок, текстуры-трава и т.д.);
3. каждая группа должна содержать минимум по 100 изображений; изображения в группах назвать примерно так: flower01.jpg, flower02.jpg.... car01.jpg,...car100.jpg.
4. все изображения в базе данных должны быть представлены в одном графическом формате (желательно jpg).

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

Система оценки должна предоставлять следующие возможности:

• модификация изображений;
• накопление и выдача автоматических (по модификациям и искажениям) и неавтоматических (по оценкам экспертов) оценок результатов поиска.

Должны быть реализованы следующие виды модификации изображений:

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

Структура проектируемой системы показана на рисунке 4.1.

_{Структура проектируемой системы}

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

Выводы

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

В результате анализа методов оценки контекстного поиска изображений была разработана структура проектируемой системы, сформированы основные требования как к системе в целом, так и к отдельным ее компонентам (наполнение БД изображений и функциональность модуля модификации изображений).

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

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

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

Данная задача легко масштабируется, что стоит учесть при реализации.

Список использованной литературы

1. Shi-Kuo Chang and Tosiyasu L. Kunii. Pictorial database systems. IEEE Comput. Mag., 14(11):13-21, Nov. 1981.
2. Rui Y., Huang T.S., Chang S. Image Retrieval: Current Techniques, Promising Directions and Open Issues // Journal of Visual Communication and Image Representation. - 1999. - vol.10. - P.39-62.
3. Wang J.Z., Li J. Wiederhold G. SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture Libraries // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2001. - vol. 23, №9. - P. 947-963.
4. J. Trant, Image Benchmarking Database CNI December 6, 2002.
5. Long F., Zhang H., Fang D.D. Fundamentals of Content-based Image Retrieval.
6. Schettini R., Ciocca G., Zuffi S. A Survey of Methods for Colour Image Indexing and Retrieval in Image Databases.
7. David McG. Squire. Automated benchmarking in content-based image retrieval. CSSE, Monash University, Melbourne, Australia.- 2001.
8. Multimedia Retravial Markup Language - http://www.mrml.net
9. Corinne Jorgensen. Towards an image testbed for benchmarking image indexing and retrieval systems. University at Buffalo. - 2002.
10. Peter Willett. Effectiveness Of Retrieval In Similarity Searches Of Chemical Databases: A Review Of Performance Measures.