Исследование возможностей кластеризации
и гистограммных признаков для
поиска картинок в базах данных

Автореферат

Введение

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

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

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

1. Существующие системы поиска изображений в БД

     1.1 QBIC - "query by image content". система QBIC - самая большая система, предназначенная для поиска изображений. Создатели - IBM Almaden Research center. Система дает возможность поиска по следующим характеристикам: " Средний цвет " Гистограммный цвет " Текстура " Форма " Положение " Положение цвета на картинке " Положение граней на картинке Система QBIC была написана на языках С, X11/Motif и реализована на платформе IBM RISC/6000

     1.2 Photobook Photobook, cистема, построенная в Масачусеттском университете технологий Алексом Пентландом, в основном берет все свои идеи от системы QBIC, но обладает возможностью деления картинки на сегменты, и более точно работает с текстурой картинки.

     1.3 Digital library Project. Разработка университета Беркли, от авторов Ginger Ogle и Chad Carson, содержит более чем 600,000 картинок. Более 50,000 из них, включая фотографии поверхностей и фотографий с воздуха, доступны онлайн на официальном сайте Digital library Project. Система позволяет поиск не только по регионам, цвету и гистограммам, но также по текстовому запросу. К сожалению, количество текстовых запросов, на которые адекватно реагирует проект, довольно мало, но система активно развивается.

2 Задача контекстного поиска изображений

При поиске изображений по их содержимому можно выделить несколько задач: контекстный поиск изображений по их содержимому, поиск по содержимому областей внутри изображения, пространственный запрос- относительный либо абсолютный (учитывается расположение областей внутри изображения), а также поиск, объединяющий все указанные признаки. Взаимосвязь этих подходов проиллюстрирована на рисунке

Рисунок 1. Взаимосвязь между запросами и поиском

Рассмотрим более подробно суть каждого из этих подходов

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

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

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

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

Рисунок 2. Пространственный запрос

     Пространственный запрос для поиска изображений с похожим относительным расположением областей заключается в том, что в БД отыскиваются изображения, в которых по крайней мере R объектов характеризуются таким же относительным расположением, как и R объектов изображения- образца. При абсолютном пространственном поиске критерием является функция расстояния D. В БД находяятся K изображений, для которых справедливо соотношение D(TQ,TF) , где - некоторое пороговое значение, а TQ,TF-множества выделенных объектов для образца запроса и изображения из БД соответственно.

2.1 Представление характеристик изображения

     Для представления как цвета, так и текстуры используются многомерные характеристики: цвет определяется как значение в трехмерном цветовом пространстве, текстура - как распределение энергии по девяти пространственно- частотным каналам. Значения признаков преобразовываются и дискретизируются с целью их представления в едином пространстве векторов с 166 цветами и 512 элементами текстуры. Для такого представления как цвета, так и текстуры изображения используются гистограммы и двоичные векторы. Такой подход предполагает выбор наиболее подходящего цветового пространства (с помощью преобразования T), последующую дискретизацию цветов (с помощью преобразования Q) и выбор метрики для определения расхождения гистограмм. В настоящее время не существует единого мнения о том, какое цветовое пространство является наилучшим для представления содержимого изображений, и на практике используются различные пространства цветов.

     Например, Swain and Ballard используют для представления цветов систему координат с противоположно направленными осями, позволяющую представить 2048 цветов. В системе QBIC, разработанной IBM, RGB- пространство дискретизируется до 4096 цветов (16 уровней по каждой составляющей), после чего цвета преобразуются к пространству Munsell с помощью преобразования МТМ. После этого выбираются k наиболее значимых цветов (как правило, k=64). Pass, Zabih and Miller просто используют RGB- пространство, применяя равномерную дискретизацию до 64 цветов, И, наконец, Gray выполняет преобразование из RGB пространства вначале в CIE-LUV, а затем выполняет дискретизацию до 512 цветов.

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

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

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

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

     Преобразования T и Q строятся таким образом, чтобы выполнялись все перечисленные свойства. Эти условия, как правило, специфичны для каждой предметной области. Например, медицинские изображения и изображения спутников требуют использования цветовых пространств, отличных от тех, которые используются для произвольных изображений, для поддержки указанных свойств. Первоначально точка определяется координатами вектора в пространстве RGB v=(r, g, b). Преобразования Q и T обрабатывают этот вектор с целью построения результирующего набора из M цветов.

Преобразование цвета Т выполняется над вектором V RGB с целью получения преобразованного вектора w. Простейшим является линейное преобразование цветов (например, для RGB- пространства это преобразование к пространствам YIQ, YUV, YcrCb, OPP). К другим цветовым пространствам (например, HSV) переход выполняется с помощью нелинейных преобразований. Поскольку все цветовые пространства непрерывны, необходимо выполнить дискретизацию цветового пространства для уменьшения количества цветов.

3. Заключение

Дальнейшими этапами исследования являются:

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

Список литературы

1.      Integrated Spatial and Feature Image Systems: Retrieval, Analysis and Compression by John R. Smith.
2.      J. R. Smith and S.-F. Chang. Joint adaptive space and frequency graph basis selection. In Proc. Int. Conf. Image Processing. IEEE, June 1997. Submitted.
3.      Scientific American, June 1997. Searching for Digital Pictures, David A. Forsyth, Jitendra Malik, Robert Wilensky
4.      T. Caelli and D. Reye. On the classification of image regions by colour, texture and shape. Pattern Recog., 26(4), 1993.
5.      S.-K. Chang and T. L. Kunii. Pictorial data-base systems. IEEE Computer, November 1981.
6.      V. N. Gudivada and V. V. Raghavan. Design and evaluation of algorithms for image retrieval by spatial similarity. ACM Trans. on Information Systems, 13(2), April 1995.