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

К.А. Рогова

Петрозаводский государственный университет

Введение

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

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

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

Целью данной работы является разработка методов классификации и поиска графической информации и создание информационной системы, позволяющей создавать, управлять и анализировать коллекции графических документов. Особенностью такой информационной системы является воз­можность хранения и использования иерархии документов и значе­ний наборов признаков, зависящих от типа документа. Создаваемое в коллекции дерево для хранения иерархии графических объектов может иметь неогра­ниченное число уровней и неограниченное число узлов на каждом уровне. Не смотря на то что, создаваемая система предназначена в первую очередь для научных исследований, подобный способ описания графических объектов позволяет применять систему для создания каталога запчастей/товаров с иллюстра­циями, произведений художников и т.д. Исследования поддержаны грантом РГНФ № 08-01-12116в (руководитель Н.В. Лобанова).

Типы признаков изображений

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

В первой группе каждое изображение может быть описано по параметрам следующего вида:

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

Нами разработаны признаки для разных типов петроглифов. Приведем пример категоризированных признаков петроглифов Северной Феноскандии [1], который разработан для изображений лосей и оленей:

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

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

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

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

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

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

Во второй группе признаков выделим:

• 
  характеристики текстуры;
  
• 
  характеристики цветовосприятия.
  

Одним из стандартных способов представления цветовой характеристики изображения является цветовые гистограммы. Для ее построения пространство всех цветов разбивается на подмножества так, чтобы схожие цвета попали в один интервал. Для каждого интервала подсчитывается количество пикселей, чей цвет принадлежит данной области. Для анализа гистограмм используются различные метрики, например, сумма модулей разностей значений элементов гистограмм для каждой цветовой области [2]. Вместо гистограммы можно брать вектор цветовой когеренции [4]. Другим вариантом представления является статистическая модель: рассматривается статистическое распределение различных цветовых каналов. Сравнение распределений является оценкой схожести [3]. Кроме того, можно рассматривать не только одномерные распределения, но и трехмерные, учитывая все взаимосвязи между каналами (ковариации). Рассматриваются интервалы наиболее часто встречающихся цветов, размеры одноцветных цветовых фрагментов, перевод цветных изображений в бинарное и их анализ.

Для анализа текстур, одним из применяемых методов является анализ независимых компонент. С его помощью выделяют фильтры, которые признаны отражать основные направления текстур для той базы изображений, на основе которой они строятся [2]. Кроме этого используется спектр фрактальной размерности Реньи [1, 5].

Анализ признаков

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

Алгоритмы классификации и кластеризации

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

Классификация по цветовому и текстурному анализу может быть осуществлена несколькими методами. Примерами являются поиск по цветовым моментам и цветовым гистограмм [2]. Кроме того, существуют методы поиска нечетких дубликатов [4]. Поиск нечетких дубликатов позволяет предположить, являются ли два объекта частично одинаковыми или нет. Частично одинаковые изображения могут образовывать один кластер. Кроме того, схожесть изображений по степени цветового восприятия может быть осуществлена на: сравнительной площадь белого, при наличии большого фрагмента определенного цвета и т.д.

Алгоритмы поиска изображений

Поиск по изображениям пред­назначен для поиска изображений, похожих на данное или на его фрагмент. На вход подается исследуемое изображение, а на выходе должны появиться изображения из базы данных, наиболее похожие на исходное. Для поиска похожих графических объектов на основе текстур изображений – методы нейронных сетей (для поиска полного изображения) и геометрического программирования (для поиска фрагмента изображения).

Рассмотрим поиск на примере наскальных изображений Северной Фенноскандии. На сегодняшний день все новейшие материалы по петроглифам представляют собой набор цветных фотографий. Определен­ную сложность поиска создает фактическое отсутствие некоторых частей изображения. Поиск также осложняется тем, что часто невоз­можно определить, где верх, а где низ изображения. При этом, тре­бование, что при поиске необходимо только совпадение контура изоб­ражения, позволяет упростить поиск, а значит, изображение петро­глифа можно рассматривать, как бинарное (скале соответствует бе­лый цвет, а петроглифу - черный). В зависимости от выбранных параметров поиска (точность поиска, процент совпадений элементов изображений) будет найдено одно или несколько изображений. Для поиска используются сеть адаптивного резонанса и структурный ме­тод поиска.

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

Общие характеристики разрабатываемой системы

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

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

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

Административная и пользовательская составляющие системы

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

Рассмотрим работу этого модуля на примере создаваемой коллекции петроглифов Северной Фенноскандии. Там выделены несколько крупных местонахождения наскальных рисунков, среди которых мы рассматриваем Норвегию, Мурманскую область и Карелию. В каждом месте выделяют более мелкие группы, потом еще более мелкие и т.д., пока не доходят до сюжетных схем и отдельных петроглифов. Наглядным представлением такого расположения являются иерархические наборы карт, схем и рисунков. Для этого необходимо загрузить карты в систему и выделить соответствующие точки местонахождения. Точно так же можно работать со схемой петроглифов: квадратной областью выделяется петроглиф и в базу данных заносится вся необходимая информация о нем. Таким образом, с этой часть системы может работать специалист в любой области, без необходимости изучения языков работы с базами данных. Основными пользователями этого раздела будут создатели коллекции. Для больших научных коллективов (сетевого научного сообщества) возможна распределенная работа научного коллектива без принудительной синхронизации получающейся базы данных.

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

Заключение

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

Литература

1. 
   Рогов А.А., Рогова К.А., Спиридонов К.Н., Быстров М.Ю. Си­стема поиска в электронной коллекции изображений петрогли­фов Карелии. // Электронные библиотеки: перспективные мето­ды и технологии, электронные коллекции: Труды 10 Всероссий­ской научной конференции "RCDL-2008"(Дубна, Россия 7-11 ок­тября 2008г.). - Дубна: ОИЯИ, 2008. С. 246-251.
   
2. 
   Васильева Н., Марков И. Синтез цветовых и текстурных признаков при поиске изображений по содержанию. // Российский семинар по Оценке Методов Информационного Поиска. Труды РОМИП 2007-2008. – Санкт-Петербург: НУ ЦСИ, 2008, С. 135-144.
   
3. 
   Sticker M., Dimai A. Color Indexing with Weak Spatial Constraints. In Proceeding of the SPIE Conference, 1996.
   
4. 
   Кисель Я. Алгоритм поиска нечетких дубликатов в коллекции изображений. // Российский семинар по Оценке Методов Информационного Поиска. Труды РОМИП 2007-2008. – Санкт-Петербург: НУ ЦСИ, 2008, С. 170-173.
   
5. 
   Рогов А.А., Спиридонов К.Н. Применение спектра фрактальных размерностей Реньи как инварианта графического изображения. // Вестник Санкт-Петербургского университета. Сер. 10. 2008. Вып. 2. С. 30-43.