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

005059200

На правах рукописи

ДЕСЯТНИКОВ ИГОРЬ ЕВГЕНЬЕВИЧ

МОДЕЛЬ И АЛГОРИТМЫ ПОИСКА ИЗОБРАЖЕНИЙ В ГРАФИЧЕСКИХ БАЗАХ ДАННЫХ НА ОСНОВЕ ТЕОРИИ АКТИВНОГО ВОСПРИЯТИЯ

Специальность 05.13.17, — «Теоретические основы информатики» по техническим наукам

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 6 МАЯ ¿013

Нижний Новгород, 2013 г.

005059200

Работа выполнена на кафедре «Вычислительные системы и технологии» федерального государственного бюджетного образовательного учреждения высшего профессионального образования Нижегородский государственный технический университет им. P.E. Алексеева.

Научный Утробин Владимир Александрович,

руководитель: доктор технических наук, профессор

Официальные Моругин Станислав Львович, оппоненты: доктор технических наук, профессор

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

Авербух Михаил Леонидович,

кандидат технических наук, общество с ограниченной ответственностью ООО "Газпром трансгаз Нижний Новгород", ведущий инженер Ведущая Федеральное государственное бюджетное учреждение

организация: науки Институт прикладной физики Российской академии наук (ИПФ РАН), г. Нижний Новгород

Защита диссертации состоится «6» июня 2013 года в 13-00 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева. Автореферат разослан «29» апреля 2013 года.

Ученый секретарь диссертационного совета

A.C. Суркова

Общая характеристика работы

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

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

Среди работ, посвященных проблеме поиска изображений в базах данных можно отметить труды зарубежных и отечественных исследователей: J. Eakins, G. Yang, T.S. Huang, F. Long, H. Zhang, R.C. Veitkamp, M. Tañase, Y. Rai, С. Абрамова, В. Лукина, Н. Васильевой, А. Левашкиной, К. Боенко, А. Дольника, И. Маркова и многих других.

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

Проблемы формирования эталонных изображений рассматриваются в теории активного восприятия.

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

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

Задачи работы.

Для достижения поставленной цели необходимо решить следующие задачи:

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

• обзор и анализ существующих систем поиска изображений и их архитектур;

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

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

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

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

Методы исследования.

Для решения поставленных задач в работе использованы методы распознавания образов, теории активного восприятия, методов цифровой обработки изображений, теории баз данных. Для практической апробации разработанных алгоритмов применено компьютерное моделирование, реализованное на языке программирования С++ под управлением СУБД Ро5г§ге8<ЗЬ.

Научная новизна работы состоит в следующем:

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

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

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

Практическая ценность и рекомендации по использованию результатов.

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

Реализация результатов работы.

Разработанные в диссертационной работе алгоритмы поиска изображений по визуальному подобию внедрены и используются в проекте «Гарда Предприятие» компании ООО «МФИ Софт», что подтверждается актом о внедрении. Они также используются в учебном процессе с магистрантами направления «Информатика и вычислительная техника» по программам «Теоретическая информатика» и «Диагностические и информационно-

5

поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева. Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ.

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

На защиту выносятся:

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

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

3. Алгоритм поиска изображения, часть которого потеряна, загорожена другим объектом или стерта.

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

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

• XV международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2009;

• XVI международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2010;

• XVII международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2011;

• Вторая Всероссийская конференция «Нелинейная динамика в когнитивных исследованиях», г. Н. Новгород, 2011;

• XVI Нижегородская сессия молодых ученых (технические науки), «Красный плес» Нижегородская обл., 2011;

• X Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», г. Таганрог, 2012.

• XIX международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2013.

Публикации. По теме диссертации опубликовано 9 работ, в том числе 2 статьи в рецензируемых изданиях, свидетельство о государственной регистрации программы для ЭВМ. Статьи [1-2] написаны в соавторстве. В работах [1-2] автору принадлежит построение информационной модели системы и алгоритмов поиска изображений, Утробину В.А. - описание элементов теории активного восприятия, на основе которых строится поисковая система.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, библиографического списка и приложений. Общий объём работы 127 страниц текста, содержащего 62 рисунка и 3 таблицы. Список литературы содержит 105 наименований.

Содержание работы

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

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

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

Алгоритмы поиска изображений и модель поисковой системы предлагается разработать с позиции теории активного восприятия, разработанной на кафедре «Вычислительные системы и технологии» НГТУ им. P.E. Алексеева. Основания использования теории активного восприятия:

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

• одномоментность восприятия — восприятие на малом числе признаков;

• наличие врожденных эталонов, вокруг которых образуется пространство классов.

Изображение М — это множество пространственно-распределенных и координатно-упорядоченных элементов (пикселей), каждый из которых в фиксированный момент времени имеет неотрицательное целое значение в замкнутой области определения G (поле зрения):

м = [/<(*> У), если (х, y)eG cR2 [О, если (x,y)iG,

где ц(х,у) - входная функция изображения.

Всё изображение в целом и любая его подобласть определения G, допускают преобразование проектирования:

пЩ)= ^/j{x,y)dxdy Vi (1)

(x,y)sG,

Преобразование (1) применимо к любому объекту исследования типа изображений в любом диапазоне частот и в теории активного восприятия определено визуальной массой.

Для выявления структурных связей на множестве структурных элементов {m(Gj)} необходимо провести операцию пространственного

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

А т(С) = м1=т(С1)-т(С2), (2)

где О = О, и - дихотомия области (7 на пару непересекающихся подобластей, для которых значения т(С1) определены по (1).

Реализовать преобразование (2) можно с помощью маски F как покрытия изображения М. Результатом являются следующие возможные значения:

>0, если т(С1)>т(02) = • < 0, если т(С1) < т(С2) = 0, если т(Сг1) = т(01)

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

2я

соответствии с положениями булевой алгебры необходимо 2 дихотомий, где п - число переменных. Для двумерного изображения п - 2, поэтому число дихотомий равно 16 (включая нулевую). В результате имеем 15 независимых направлений в многомерном векторном пространстве. Каждому направлению соответствует компонента а множеству направлений - 15-мерный вектор >"=(А'1е1.//2е2>-.А5е15). описывающий изображение в поле зрения или любой его подобласти. Компонента ца, соответствующая нулевому направлению, является визуальной массой всего изображения.

Конструктивно множество масок, покрывающих область определения изображения (7, определено на системе базисных функций Уолша системы Хармута и упорядочено на двумерной решетке. Маски-покрытия (их нумерация условна) построены на квадратном клеточном пространстве (рис. 1).

Если в области определения <7 задать декартову прямоугольную систему координат (дг, у), то 15-ти направлениям будет соответствовать 15-ть дифференциальных операторов:

/='9, ^10, Я,, ^12, ^13, ^14, ^и) ~

(А А _Ё!_ 53 а4 а3

а*' ф/ эл%' а*2' 8у2' ах2а/ &ау2' дх2ду2' а*3'

а3 а4 а4 а5 а5 а6 ду3' аьс3а>'' дхду}' а*3ау2' &2^3' а*3 V

Ло Лз

Р5 Л Ра

Р0 Р\ Рис. 1. Фильтры-покрытия

Использование функций Уолша в силу их бинарности обеспечивает простоту анализа отношений на множестве т(С¡), упорядоченном на матрице [т^4х4, так как используются простейшие операции - сложение (1) и вычитание (2). Эта система преобразований имеет высокую производительность (малое время отклика системы) в отличие от стандартных преобразований, требующих реализации свёртки, а на уровне весовых коэффициентов - операции арифметического умножения. Схема информационных преобразований на операциях (1) и (2) может использоваться для любой подобласти изображения. Число уровней пирамиды переменного разрешения определяется необходимой точностью решения, а вариант выделения необходимой подобласти - стратегией восприятия.

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

1. проводим дихотомию изображения как множества Мна 16 равных частей и подсчитываем визуальную массу каждой из них - получаем матрицу ||ту|| изображения;

2. накладываем на матрицу ||/и,у|| маски, выявляющие 15-ть пространственных бинарных отношений на 15-ти базисных

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

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

ИЦпопп)

Мо

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

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

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

• пространство операторов У- [У¡};

• пространство полных групп Р„ = {Рл(}. Полные группы - Р„„ образованные на тройках операторов (К„ V}, К*), для которых справедливы соотношения: Уі + У/ + Р* = е\ - единица; УіУ/Уц - образ и описание группы Рш;

• пространство замкнутых групп Р, = {Р„}. Замкнутые группы — Р5І, образованные на четверке операторов (У„ Уи Ур, Уп), где (У, V/, Ук) є Рш, (У„, Ут, Уц) є Рф с описанием У ¡У] + УРУт (необходимое число инверсий операторов нечетно) и единицей - У/+ У}+ Ур+ Ут = е1.

Множества У, Ры, и Р„ конечны и имеют мощности 30, 140 и 840 соответственно.

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

Правило 1. Два изображения Мі и Мг принадлежат одному классу, если они имеют один образ в базисе {И,} в независимости от значений визуальных масс, но с учётом сохранения знаков компонент вектора разложения.

Правило 2. Два изображения М\ и Мг принадлежат одному классу, если они имеют один образ в базисе {Р^} в независимости от значений визуальных масс, но с учётом сохранения знаков компонент вектора разложения.

Правило 3. Два изображения М\ и Мг принадлежат одному классу, если они имеют один образ в базисе {Р,,} в независимости от значений визуальных масс, но с учётом сохранения знаков компонент вектора разложения.

М, ~ М, » 0(М= <9(А/у),

где ~ - эквивалентность; <=> — «тогда и только тогда, когда».

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

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

Г = л/(*! - УхУ + (*2 - Уг)2 + - + (*15 - Ум)2 = Je (xi - У'У ,

где {х,} - координаты наблюдаемой точки, {у,} - координаты эталона для данного класса изображений.

Для обоснованности применения врожденных эталонов в качестве центров классов автор работы провел исследование робастности множеств {Vi}, {P„i}, {Ps,}. Под робастностью понимается помехоустойчивость множеств врожденных эталонов к наложению равномерных шумов и помех на изображение. Из результатов экспериментов (рис. 2) видно, что все множества являются робастными даже к сильным шумам и изменениям исходного изображения. Достоверность на графике определяет вероятность того, что максимальная группа или оператор (врожденные эталоны) останется таким же при наложении шумов или помех.

Рис. 2. Робастность врожденных эталонов к воздействию аддитивного шума и изменению яркости изображения

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

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

Изображение (или его подобласть)

Множество М

Признаковое описание изображения

Этап 1 Интегральное преобразование — выявление структурных элементов Этап 2 Дифференциальное преобразование -выявление структурных связей

15-мерный вектор

Символьное описание изображения

Вывод найденного изображения лицу, принимающему решение

Сравнение с эталонным описанием в пространстве классов {Рпі}

Сравнение с эталонным

описанием в пространстве классов {VI}

Множества {\Л}, {Рпі}. {Рзї>

Пространство {Рпі}

Сравнение с эталонным описанием в пространстве классов {Реї}

Построение пространства классов

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

На практике часто возникает необходимость выполнить поиск для отредактированного, поврежденного или частично загороженного изображения (рис. 5а). В этих случаях, чтобы успешно выполнить задачу поиска, необходимо перейти на следующий уровень пирамиды разрешения. В результате механизм «грубого» поиска выполняется не для всего изображения в целом, а для его подобластей. В работе были использованы четыре центральные подобласти изображения (рис. 56) для построения вектора на втором уровне описания, т.к. обычно в этой области и находится значимая часть изображения.

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

Изображение как множество пикселей

Проведение дихотомии изображения на 16 равных частей и вычисление визуальной массы каждой из них

Матрица

Наложение на матрицу 15 масок-

фильтров

15-мерный вектор

Нормирование вектора по его нулевой составляющей

Нормированный 15-мерный вектор

Вычисление замкнутых групп

Множество {Р5/}

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

Сортированное множество {Р5/}

Выборка п изображений из максимальных по вкладу в изображение групп {Р31)

пизображений

Сравнение с эталонным описанием (критерий: Евклидово расстояние) и поиск ближайшего

Найденное изображение_

/Вывод найденного /

изображения /

Конец

Рис. 4. Алгоритм «грубого» поиска изображения 15

Рис. 5. а) часть изображения потеряна, б) подобласти изображения для описания на втором уровне пирамиды разрешения

В работе исследование производилось на тестовой выборке 107 изображений. Для данного объема данных необходимо детализированное разбиение множества входных изображений, поэтому было принято решение использовать для разбиения пространства изображений множество замкнутых групп. С учетом всех возможных инверсий знаков для замкнутых групп получаем 840 классов. Логическая структура базы данных представлена на рис. 6. Именно простота обработки изображения с использованием «грубого» поиска обеспечивает простоту структуры базы данных.

1тадез_1 Ітаде5_зесопї1_1

Ю изображения 1 ГО изображения

15-мерный вектор на 1-ом уровне Ссылка на изображение 15-мерный вектор на 2-ом уровне (1) 15-мерный вектор на 2-ом уровне (2) 15-мерный вектор на 2-ом уровне (3) 15-мерный вектор на 2-ом уровне (4)

1тадеэ_2

ІтадеБ_8ЄСопсІ_2

ГО изображения 1 ГО изображения

15-мерный вектор на 1-ом уровне Ссылка на изображение 15-мерный вектор на 2-ом уровне (1) 15-мерный вектор на 2-ом уровне (2) 15-мерный вектор на 2-ом уровне (3) 15-мерный вектор на 2-ом уровне (4)

Ітадез_840

Ітаде8_весопс1_840

ГО изображения 1 ГО изображения

15-мерный вектор на 1-ом уровне Ссылка на изображение 15-мерный вектор на 2-ом уровне (1) 15-мерный вектор на 2-ом уровне (2) 15-мерный вектор на 2-ом уровне (3) 15-мерный вектор на 2-ом уровне (4)

Рис. 6. Логическая структура базы данных 16

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

Основными требованиями к системе поиска изображений являются:

• высокая производительность и достоверность поиска (малое время отклика системы на запрос, корректность результата);

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

• поиск изображений, часть которых была потеряна или отредактирована;

• поиск похожих изображений.

Для заполнения базы данных разработан модуль, предназначенный для автоматического обхода страниц интернет-сайтов с целью занесения информации о изображениях, которые располагаются на них, в базу данных поисковой системы. Всего было проиндексировано примерно 107 изображений произвольного размера и содержания. Ниже представлены результаты разработанных алгоритмов для конфигурации ПК AMD Phenom II Х4 945 3 ГГц, 2Гб ОЗУ.

«Грубый» поиск изображения выполняется в среднем за 40 мс. Автор считает этот результат отличным, поскольку скорость распознавания простого изображения мозгом человека составляет по разным оценкам 40-250 мс — это время, необходимое кратковременной памяти человека, чтобы сравнить свое содержимое с запасами долговременной. Как видим, разработанный алгоритм успешно укладывается в указанные временные рамки. Следует отметить, что непосредственно сама обработка изображения занимает 1-2 мс, все остальное -расходы на выполнение запросов в базу данных.

Помехоустойчивый поиск изображений с наложенным шумом, помехами, искажениями, поворотом на небольшой угол и т.д. (рис. 7) реализован аналогично «грубому» поиску, за исключением того, что первоначальная выборка объектов п из базы гораздо больше. Это необходимо, чтобы искомые

изображения на первоначальном этапе не были отброшены, как «не свои».

17

Среднее время поиска 400 мс. Все примеры изображений на рис. 7 были успешно найдены в базе данных (сопоставлены с оригинальным изображением, хранящимся в базе). Результаты работы алгоритма для разных типов помех и искажений (изменение яркости и наложение аддитивного шума) представлены на рис. 8.

ж) ШШШШШЯШШШ з) шшишшШШШИШШ и) ШШшШШШШтШШ

Рис. 7. Примеры зашумлённых и отредактированных изображений: оригинальное изображение, б) аддитивный шум, в) поворот изображения, г) искажение «вмятины», д) искажение «кристаллизация», е) размытие «раздвоение», ж) сепия, з) эффект «стеклянная плита», и) размытие

1Э% 25% 30% 40%

Шум "соль-пере^

и Достоверность иОшиЗка I рода □ Ошибка » рода |

| а Достоверность ■ Ошибка) рода □ Ошдбха {родз |

а) б)

Рис. 8. Результаты поиска изображения а) воздействие аддитивного шума,

б) изменение яркости исходного изображения

Также имеется возможность выполнять поиск поврежденных изображений, например, часть изображения была повреждена или стерта. При этом может быть повреждено до 75% исходного изображения. Для поиска таких изображений разработан «многоуровневый» поиск изображений, который выполняет переход на более низкий уровень разрешения и более детально сравнивает изображения. В работе были использованы 4 центральные подобласти изображения для построения вектора на втором уровне описания. Для каждой из подобластей выполняется алгоритм помехоустойчивого поиска и, если 2 или больше найденных изображений указывают на одно и то же в базе данных - это и есть искомое изображение.

«Многоуровневый» алгоритм поиска устойчив сразу ко всем отклонениям от оригинального изображения: наложение шума, помех, редактирование, наложение художественных эффектов, потеря части изображения, загораживание части изображения. Среднее время поиска 700 мс.

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

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

Далее приводится сравнение разработанной поисковой системы с коммерческими системами поиска изображений: Google Search, TinEye, WeSEE Search. Все указанные поисковые системы индексируют различное количество изображений, различного содержания и формата, поэтому сравнение проводилось только в достоверности поиска, производительность не учитывалась. В целом, разработанная в данной работе поисковая система доказала свою эффективность. Она может соперничать с известными поисковыми системами по производительности и достоверности.

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

Приложение содержит:

• акт о внедрении разработанной системы поиска изображений в проекте «Гарда Предприятие» компании ООО «МФИ Софт»,

• акт о внедрении результатов диссертационной работы в учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программам «Теоретическая информатика» и «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева.

Основные результаты работы

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

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

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

3. Разработаны алгоритмы поиска оригинальных, а также зашумлённых изображений.

4. Разработан алгоритм поиска изображения, часть которого потеряна, загорожена другим объектом или стерта.

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

6. На основе предложенных модели поисковой системы и алгоритмов поиска изображений разработан прототип поисковой системы, в которой реализованы разработанные алгоритмы поиска изображений.

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

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

Список опубликованных работ по теме диссертации Публикации в рецензируемых изданиях [1] Десятников, И.Е. Алгоритмы поиска изображений в базах видеоданных [Текст] / И.Е. Десятников, В.А. Утробин // Журнал «Компьютерная оптика». -Самара - 2011,-Том 35, №3. - С. 416-422.

[2] Десятников, И.Е. Построение архитектуры баз данных для задачи поиска изображений [Текст] / И.Е. Десятников, В.А. Утробин // Журнал «Вестник Нижегородского государственного университета». — Нижний Новгород — 2012. — №5(2).- С. 319-325.

Публикации в других изданиях

[3] Десятников, И.Е. Алгоритмы и методы поиска заданного объекта на множестве фотопортретов [Текст] / И.Е. Десятников // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009)», 17 апреля 2009 г. - Н. Новгород: НГТУ, 2009. -С. 318.

[4] Десятников, И.Е. Методы поиска заданного объекта на множестве фотопортретов [Текст] / И.Е. Десятников // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2010)», 23 апреля 2010 г. - Н. Новгород: НГТУ, 2010. - С. 351.

[5] Десятников, И.Е. Поиск портретных изображений в базах видеоданных [Текст] / И.Е. Десятников // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2011)», 22 апреля 2011 г. - Н. Новгород: НГТУ, 2011. - С. 392.

[6] Десятников, И.Е. Алгоритмы и методы поиска изображений в базах видеоданных. Теория активного восприятия и ее применение для задачи поиска изображений [Текст] / И.Е. Десятников // Материалы Нижегородской сессии молодых ученых (технические науки), февраль 2011 г. - Н. Новгород: Гладкова О.В., 2011.-С. 179-182.

[7] Десятников, И.Е. Система поиска изображений по визуальному подобию в сети Интернет [Текст] / И.Е. Десятников // Сборник трудов X Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (ИТСАИУ-2012), декабрь 2012 г. - Таганрог: Издательство Южного федерального университета, 2012.— С. 176-180.

[8] Десятников, И.Е. Поиск изображений по визуальному подобию в сети Интернет [Текст] / И.Е. Десятников // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2013)», 19 апреля 2013 г. - Н. Новгород: НГТУ, 2013. - С. 240-241.

22

[9] Десятников, И.Е. Программа поиска изображений по визуальному подобию в графических базах данных / И.Е. Десятников // Свидетельство об официальной регистрации программ для ЭВМ № 2013613855. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 17 апреля 2013 г.

Подписано в печать 24.04.13. Формат 60 х 84 /16. Бумага офсетная. Печать трафаретная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 348.

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

Министерство образования Российской федерации Нижегородский государственный технический университет им. P.E. Алексеева

На правах рукописи

04201360754

Десятников Игорь Евгеньевич

МОДЕЛЬ И АЛГОРИТМЫ ПОИСКА ИЗОБРАЖЕНИЙ В ГРАФИЧЕСКИХ БАЗАХ ДАННЫХ НА ОСНОВЕ ТЕОРИИ АКТИВНОГО ВОСПРИЯТИЯ

Специальность: 05.13.17 - Теоретические основы информатики Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., профессор Утробин В.А.

Нижний Новгород, 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................................................................4

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ И СИСТЕМ ПОИСКА ИЗОБРАЖЕНИЙ.........................................................................................................9

1.1. Обзор методов поиска изображений...............................................................9

1.1.1. Методы на базе цветовой классификации..............................................13

1.1.2. Методы на базе анализа текстур..............................................................18

1.1.3. Методы на базе анализа формы объектов..............................................26

1.1.4. Методы на базе комбинации признаков.................................................37

1.2. Обзор существующих систем........................................................................38

1.2.1. Архитектура СВГО.-систем.......................................................................38

1.2.2. Сравнительный анализ СВЖ-систем......................................................39

1.3. Цель и задачи исследования...........................................................................42

ГЛАВА 2. ТЕОРЕТИЧЕСКИЙ ПОДХОД К ПОСТРОЕНИЮ СИСТЕМЫ ПОИСКА ИЗОБРАЖЕНИЙ НА ОСНОВЕ ТЕОРИИ АКТИВНОГО ВОСПРИЯТИЯ..........................................................................................................45

2.1. Основные подходы при построении систем поиска изображений............45

2.2. Формирование признакового описания изображения.................................54

2.3. Формирование пространства классов изображений....................................60

2.4. Разработка информационной модели системы поиска...............................76

2.5. Выводы.............................................................................................................87

ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ..........................................................................................................88

3.1. Программная реализация комплекса поиска изображения.........................88

3.2. Алгоритм «Грубый» поиск изображений.....................................................93

3.3. Алгоритм помехоустойчивого поиска изображений...................................94

3.4. Алгоритм «Многоуровневый» поиск изображений.....................................99

3.5. Алгоритм поиска похожих изображений....................................................101

3.6. Сравнение разработанной поисковой системы с существующими аналогами..............................................................................................................104

Выводы..................................................................................................................110

ЗАКЛЮЧЕНИЕ........................................................................................................112

БИБЛИОГРАФИЯ...................................................................................................114

Приложение А. Акты о внедрении результатов кандидатской диссертационной работы.......................................................................................................................125

ВВЕДЕНИЕ

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

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

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

По некоторым подсчетам, количество изображений в сети Интернет на

13

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

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

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

Возможность поиска изображений по их содержанию может стать еще одним связующим звеном в создании той самой информационной структуры, которую Б. Гейтс назвал «электронной нервной системой» [1]. Благодаря этой системе можно будет быстро реагировать на любые изменения в окружающем мире и своевременно принимать правильные решения.

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

2. обзор и анализ существующих систем поиска изображений и их архитектур;

3. разработка информационной модели системы поиска для графических баз данных;

4. разработка алгоритмов поиска оригинальных, а также зашумлённых и похожих по визуальному подобию изображений;

5. разработка алгоритмов поиска поврежденных изображений;

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

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

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

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

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

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

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

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

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

• XV международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2009;

• XVI международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2010;

• XVII международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2011;

• Вторая Всероссийская конференция «Нелинейная динамика в когнитивных исследованиях», г. Н. Новгород, 2011;

• 16-я Нижегородская сессия молодых ученых (технические науки), г. Семенов, 2011;

• X Всероссийская научная конференция молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», г. Таганрог, 2012.

• XIX международная научно-техническая конференция «Информационные системы и технологии», г. Н.Новгород, 2013. Публикации. По теме диссертации опубликовано 9 работ, в том числе 2

статьи в рецензируемых изданиях, свидетельство о государственной регистрации программы для ЭВМ.

На защиту выносятся следующие результаты работы:

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

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

3. Алгоритм поиска изображений, часть которых потеряна, загорожена другим объектом или стерта.

4. Алгоритм поиска похожих по визуальному подобию изображений, который по производительности и достоверности не уступает

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

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

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ И СИСТЕМ ПОИСКА

ИЗОБРАЖЕНИЙ 1.1. Обзор методов поиска изображений

Задача поиска изображений в последние годы активно развивается и привлекает всё больше исследователей. Для проверки гипотезы о росте количества публикаций, автор провел простое упражнение - выполнялся поиск публикаций, содержащих в своей теме фразу «Image Retrieval» с помощью Google Scholar [2]. Результат исследования показан на рис. 1.1.

8000

Рис. 1.1. Количество публикаций по теме поиска изображений

'= 6000 32

г 5000 с

I 4000

о

о

$> 3000

г

| 2000 *

1000

о

1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011

Год

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

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

Во-первых, неоднозначность соответствия между визуальным содержанием и текстовым описанием снижает показатели точности и полноты

поиска. Американский физиолог Леон Хармон в свое время провел серию экспериментов, которыми доказал, что люди по-разному словесно описывают один и тот же портрет человека [3]. Конечно, длинный нос для одного лица станет вполне обыкновенным или даже коротким для другого, так что составление словесных описаний - искусство.

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

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

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

Рис. 1.2. Методы поиска изображений в базах данных

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

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

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

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

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

Рис. 1.3. Классификация методов поиска по содержанию

Важную роль в построении систем поиска изображений играет выбор метрики сравнения признаков изображения. Наиболее распространенными из них являются следующие [6]:

• евклидово расстояние;

• манхеттенское расстояние;

• пересечение гистограмм;

• взвешенное пли квадратичное расстояние.

Рассмотрим основные алгоритмы построения векторов признаков для цвета, текстуры и формы объектов.

1.1.1. Методы на базе цветовой классификации

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