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

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

САВКИНА Анастасия Владимировна

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

Специальность 05.13.17 - Теоретические основы информатики

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

1 8 НОЯ 2010

ПЕНЗА 2010

004613067

Работа выполнена на кафедре автоматизированных систем обработки информации и управления ГОУВПО «Мордовский государственный университет имени Н. П. Огарева»

Научный руководитель - кандидат технических наук, профессор Федосин Сергей Алексеевич.

Официальные оппоненты: доктор технических наук, профессор Федотов Николай Гаврилович; кандидат физико-математических наук, доцент Борискина Ирина Петровна.

Ведущее предприятие - Федеральное государственное унитарное предприятие «Пензенский научно-исследовательский электротехнический институт» (г. Пенза).

Защита диссертации состоится 2 декабря 2010 г. в часов на заседании диссертационного совета Д 212.186.01 при Государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке Государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет». Автореферат диссертации размещен на сайте университета www.pnzgu.ru.

25".

Автореферат разослан октября 2010 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Е. И. Гурин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Среди работ, посвященных данной проблеме можно отметить труды зарубежных и отечественных исследователей: J. P. Eakins, A. Vailaya, М. Figueiredo, Т. Kato, Т. Kurita, G. Yang, Т. S. Huang, Е. J. Stolnitz, Т. Derose, Т. Salesin, Н. Г. Федотова, М. А. Щербакова, И. М. Гостева, А. В. Мирошкина, С. К. Абрамова, В. В. Лукина, А. Л. Жизнякова, Н. В. Вакунова, В. П. Дьяконова, диссертационные работы А. В. Роя, Н. Е. Козина, И. В. Корябкиной, Ä. В. Нефёдова, И. П. Тищенко и многих других. . . ,

3

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

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

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

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

2. Разработка формализованной модели на основе фрактального кодирования и комбинирования вейвлетного и фрактального методов.

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

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

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

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

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

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

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

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

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

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

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

4

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

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

Основные положения, выносимые на защиту:

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

2. Методики поиска изображений в базе данных по искомому изображению на основе предложенной формализованной модели.

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

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

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

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

Результаты работы использованы в НИОКР «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» (программа «Участник молодежного научно-инновационного конкурса 2007» Фонда содействия развитию малых предприятий в научно-технической сфере, государственные контракты 5474/7987 от 03.12.07 и 6653/9110 от 21.01.09)

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

1. IV, V Международные конференции «Методы и средства управления технологическими процессами», Саранск, 2007,2009 гг.

2. XXXIV, XXXVII Огаревские чтения, Саранск, 2006,2009 гг.

3. XI научная конференция молодых ученых, аспирантов и студентов Мордовского государственного университета имени Н. П. Огарева, Саранск, 2006 г.

4. Международная научная конференция «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50), Саратов, 2009г.

5. 6-ая Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (с участием стран СНГ), Ульяновск, 2009г.

По результатам 4-ой Международной конференции "Методы и средства управления технологическими процессами» работа «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» признана

победителем программы «Участник молодежного научно-инновационного конкурса 2007» («УМНИК»). '

Публикации. По теме диссертации опубликовано 16 работ, в том числе 13 статей, среди них 1 в журнале, рекомендованном ВАК РФ; 3 свидетельства о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 112 наименований и 12 приложений. Работа содержит 131 страницу основного текста, 62 страницы приложений, 27 рисунков, 3 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

м5 = 5(у1п, <?/т, *(17/т), Р{Ч,п), Д№т)^(<г;тп))), где У1т - множество изображений, известных поисковой системе, (¿¡т - множество поисковых запросов, F (у1гп), и;га6 ]/1т, Т7 {ц1т), д!т € (}1т - множества операций над элементами множеств изображений, известных поисковой системе и изображений - поисковых запросов, в соответствии с методом поиска изображения: фрактального кодирования (Рр) и комбинированного подхода, использующего вейвлетные и фрактальные методы (Д(Р(г>/Д v,me У1т, Чы £ С?/т - функция ранжирования, Мв - множество преобразований выполняемых над множествами изображений, известных поисковой системе У1т и поисковых запросов ()1т в зависимости от методов поиска (Бр, ¿иг-кХ =

Множество операций над элементами множеств изображений представляет собой использование конкретного метода реализуемого для поиска изображений. Процесс обработки изображения 1т представим как некоторую последовательность функций:

1Щ = АОЩ-и 0),

где /г - функции преобразования изображений, образующие множество в = От и г}2,..., Ц„) - вектор параметров из множества в.

Процесс получения множества характеристических объектов изображения ы1т = {(¡т,¡,[ = М) из 1т запишем в виде

ш1п = С(1т,Г1,в,т), 1 = ТХ),

где С - некоторый функционал, определяющий последовательность применения функций /г в процессе обработки изображения 1т, Ы— число полученных объектов из 1т, Ь - число использованных функций в (1), т = (¡^ С2,..., - вектор номеров функций /г из /% определяющий последовательность их вызова.

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

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

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

W/mi(p(*.y)) = S/miP№mi(*.y)) + Oim,. где р{х,у) — вещественная функция, представляющая собой изображение, описанное матрицей значений р^- р(х(,у;), i = 1, ..., п, j = 1, ..., m в конкретной точке, wIrn[ обратимо и (х, y)eRimr Здесь iv/m.3TO аффинное преобразование, переводящее в себя единичный квадрат:

Константа sImi расширяет или сужает диапазон значений функции р, то есть управляет контрастностью. Аналогично, константа olmi увеличивает или уменьшает значения цветности - управляет яркостью. Преобразование wIm. является пространственной составляющей преобразования wImr

Далее для каждого рангового блока R,mi ищется домен Dlm., пространственное преобразование wim., контрастность s¡т., яркость о1т., такие, чтобы w,mi(p) было бы близко к изображению р в блоке Rtmi. То есть ищется такое w!m., чтобы величина

1К1т (ЩтМх'У^ ~p(x,y))zdxdy (1)

была минимальной.

Чтобы определить оптимальную контрастность sInii и яркость о/т., находим значения sfmi и о]т., которые минимизируют выражение

SlmiU/rrijC^imi Фту °1ггц ~ rImtj) > где dlmij и rimij - значения пикселей доменной и ранговой области. Эти пиксели находятся в прямоугольных массивах с Mj строками и Nj столбцами (размер домена уже сжат для соответствия ранговой области в этой точке). Решением является

Simi = а/Р>

O/m, = ? ~ (|) d,

где

а ~ Zlmt Zimy (dimij ~ (г1ту ~ f)i

P = — d)2;

g

f =

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

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

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

1, 0<х<\/2; у/{х) = - -1, 1/2<л<1;

О, х < 0, х > 1.

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

[1, 0 < х < 1; [ 0, х<0, х>1.

Процесс получения множества характеристических объектов, представляется в виде линейной комбинации функций разложения <Pk(x)\

lmf(x) =I,jika]k<pJk(x~), где aik - коэффициенты разложения, которые являются значениями цветности пикселей изображения по каждому каналу (модель RGB), индекс к определяет положение функции <р,к(х) по строкам, индекс j - по столбцам. Структура изображения определяется как набор коэффициентов /тДх), являющихся результатом нестандартного разложения, которое представляет собой чередование операций над строками и столбцами. С помощью кратномасштабного анализа выделяются связанные области одинаковой структуры и яркости, которые изучаются при высоком или низком разрешении в зависимости от характеристик объекта. ..

После выполнения кодирования изображений при помощи вейвлет-преобразований, то есть, имея заданное изображение Im е W из пространства изображений и вейвлет-преобразование fw(Im), используем отображение доменного поддерева в ранговое поддерево fp, чтобы получить оператор fs(Im) вида

fsVm) -fpifwU171))-

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

1тПм1 = fwlUmw^_г^ биО;

= /^(ЛпгцЛ)-

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

ранговые поддеревья. Определяется составной оператор отображающий доменные поддеревья в ранговые поддеревья так, чтобы минимизировать ошибку в вейвлетной области. Далее для каждого рангового блока Я/т. ищется домен 0/т., пространственное преобразование й>/т., контрастность з1т., яркость о!т., такие, чтобы ю1ггч(1тм) было бы близко к образу изображения /??% в блоке й/т.. После выделения свойств изображения производится сравнение образца изображения с изображением, находящимся в базе по метрике (1).

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

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

2. Изображение разбивается на перекрывающиеся ранговые блоки, при этом используются квадратные ранговые блоки.

3. Изображение покрывается последовательностью доменных блоков.

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

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

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

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

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

7. Пункты 1-6 описывают поиск растрового изображения по одному каналу палитры RGB. Далее для получения поиска по полноцветному изображению необходимо проделать описанные операции для каждого канала палитры R (red - красный), G - (green - зеленый), В - (blue - синий).

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

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

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

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

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

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

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

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

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

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

следственные связи, присущие системе и существенные для достижения цели моделирования.

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

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

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

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

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

Для построения базы данных использовалась система управления Microsoft Access 2007; для реализации системы - среда программирования Turbo Delphi; для обработки изображений различными функциями вейвлетов. (Хаара, Добеши, койфлеты) - пакет Wavelet Toolbox системы MatLab.

С помощью разработанной системы поиска растровых изображений проведен анализ оптимальной глубины квадродерева при фрактальном кодировании. Для этого изображения и их коэффициенты сохранялись при различных максимальных глубинах квадродеревьев (3-7). При глубине квадродерева, равной 3 и 4 разбиение достаточно грубое, которое не несет в значениях коэффициентов необходимой информации. При глубине квадродерева, равной 5, изображение ищется только в том случае, если оно не подвергалось никаким изменениям. Анализ результатов показал, что разбиение при максимальной глубине квадродерева равной 6 наиболее приемлемо для работы такой системы с точки зрения объема занимаемых данных, времени и качестве поиска, а при глубине

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

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

В качестве методики, используемой для оценки эффективности методов поиска на основе результатов моделирования предложено:

а) использование коллекции модифицированных изображений по отношению к заданному изображению с внесенными шумами и искажениями. Материалом для анализа формализованной модели послужила коллекция изображений художника Федота Васильевича Сычкова, представленная в музее С. Д. Эрьзи, которая содержит 59 изображений различного формата;

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

в) определение времени поиска изображения по изображению-образцу;

г) вычисление параметра эффективности:

100,

где ВЕ = тах Ва - , ^ Ву - ВД1£.) - наибольшее коли-

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

Втах = тах 1<г Вц, - общее наибольшее количество веток квадро-

дерева, для метода вейвлет-преобразований Втах - количество максимальных вейвлет-коэффициентов; 1(2 Вг^ - количество всех веток квадродерева искомого изображения; Ву - количество всех веток квадродерева изображения в базе данных; ЫЬд, МЬу- количество ранговых блоков искомого изображения и изображения в базе

данных; В^е — количество не совпавших веток квадроде-ревьев; / - время поиска изображения в базе данных.

Анализируя данные поиска изображений методом фрактального кодирования можно сделать вывод, что лучшие результаты имеют изображения к которым были применены такие модификации как уменьшение и увеличение размеров картины в 2 раза, добавление шума 25%-50%, смена разрешения с 96 х 96 на 72 х 72, эффект пятна, линзы. Процент совпадения картин при указанных модификациях достаточно велик, более 80%.

Чуть хуже в процентном совпадении (60%-80%) выступают картины с модификациями: уменьшение размеров картины в 3 раза; инвертирование цве-

tob; эффекты рельефа, чеканки; фильтр размытие гаусса с радиусом 1.0-3.0; вырез (прямоугольник, эллипс); перевод изображения в оттенки серого.

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

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

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

100

90 . 80

I 70 а бо

¡2 50 о 40

Ч 30 * 20

10 0

012345678 9 1011121314151617181920212223242526272829303132 Номер модификации изображения

Вейвлет-преобразование ~~ фрактальное кодирование ............Вейвлетно-фрактальный подход

Рисунок 1 - Результаты поиска изображений различными методами

В результате, согласно введенному критерию эффективности, по сравнению с вейвлетным подходом, выигрыш дает комбинированный подход - на 16 % и фрактальный - на 10 %.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО РАБОТЕ

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

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

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

4. Разработаны алгоритмы поиска изображения на основе методик, использующих фрактальное кодирование, а также сочетание вейвлет-преобразования и фрактального подхода. На основе разработанных алгоритмов создана система поиска изображений с учетом диаграммы последовательности, концептуальной модели и богатых возможностей фрактальных и вейвлетных методов. Система реализована с помощью среды программирования Turbo Delphi, пакета Matlab и СУБД MS Access и дает возможность находить изображения, содержащиеся в базе данных в виде коэффициентов, по изображению-образцу.

5. Предложена методика оценки эффективности поиска изображений с помощью которой проведен выбор параметров фрактального кодирования и вейвлет-функций. Выявлено, что оптимальным является использование максимальной глубины квадродерева равной 6. Экспериментально подтвержден выбор вейвлет-функции Хаара, использующейся при комбинированном подходе. Проведен анализ результатов-поиска изображений, полученных с помощью разработанной системы с учетом модификаций изображений, который показал, что используя фракталы, изображение будет найдено, если система покажет более 37,5 % совпадений, а для комбинированного подхода - более 35,2 %.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикация в издании, рекомендованном ВАК РФ

1. Савкина, А. В. Реализация системы поиска растровых изображений на основе вейвлет-преобразования, фрактального кодирования и смешанного подхода / А. В. Савкина // Системы управления и информационные технологии: научно-технический журнал, №2.2(36) - Москва-Воронеж. Изд-во «Научная книга», 2009. - С. 288-293.

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

2. Савкина, А. В. Исследование применимости вейвлет-разложений к полноцветным и черно-белым изображениям / А. В. Савкина, С. Е. Иконников. - XXXVII Огаревские чтения: материалы научн. конф. : в 3 ч. - Ч. 3 : Технические науки. - Саранск : Изд-во Мордов. ун-та, 2009. - С. 143-145.

3. Савкина, А. В. Новые информационные технологии для обработки данных / А. В. Савкина П Материалы XI научной конференции молодых ученых, аспирантов и студентов Мордовского государственного университета имени Н. П. Огарева : в 3 ч. - Ч. 3 : Технические науки. - Саранск : Изд-во Мордов. ун-та, 2006. - С. 17-19.

4. Савкина, А. В. Обработка запросов изображений из базы данных / А. В. Савкина, Э. Э. Александров // Материалы XI научной конференции молодых ученых, аспирантов и студентов Мордовского государственного университета имени Н. П. Огарева : в 3 ч. -Ч. 3 : Технические науки..-Саранск : Изд-во Мордов. ун-та, 2006. - С. 15-17.

5. Савкина, А. В. Поиск изображения по изображению-запросу с помощью фрактального кодирования /. А. В. Савкина // Электроника и информационные технологии. - Выпуск 1 (3) - 2008. - http://fetmag.mrsu.ru/2008-l/pdf/7-Savkma/savkina.pdf. - 0420800067\0006. - 10 с.

6. Савкина, А. В. Применение метода вейвлет-преобразований для поис-

ка растровых изображений / А. В. Савкина // Проблемы управления, передачи и обработки информации - АТМ-ТКИ-50: сб. трудов Международ, науч. конф. / под ред. А.Г. Александрова, М.Ф. Степанова. Саратов: Сарат. гос. техн. ун-т, 2009.-С. 310-312.

7. Савкина, А. В. Разработка и реализация базового алгоритма фрактального кодирования изображений / А. В. Савкина // Электроника и информационные технологии. - Выпуск 2 (4) - 2008. - http://fetmag.mrsu.ru/2008-2/pdf719_Fractal_ Coding.pdf. -0420800067V0025.- 11 с.

8. Савкина, А. В. Разработка комплекса программ для хранения и поиска изображений с помощью вейвлет-преобразований / А. В. Савкина // Электроника и информационные технологии. - Выпуск 2 (4) - 2008. -http://fetmag.mrsu.ru/2008-2/pdf/18_Wavelet_Storage.pdf. - 0420800067\0024. -11 с.

9. Савкина, А. В. Разработка системы поиска растровых изображений на основе смешанного подхода / A.B. Савкина // Электроника и информационные технологии. - Специальный выпуск (6) - 2009. - http://fetmag.mrsu.ru/2009-2/pdfBitmap_ search_system.pdf. - 04200900067/0075. - 3 с.

10. Савкина, А. В. Разработка системы фрактального кодирования для обработки изображений / А. В. Савкина, С. Е. Иконников // Современные проблемы создания и эксплуатации радиотехнических систем: Труды шестой всероссийской научно-практической конференции (с участием стран СНГ) - Ульяновск: УлГТУ,2009.-С. 211-214.

11. Савкина, А. В. Разработка системы хранения растрового изображения / А. В. Савкина, Э. Э. Александров // XXXIV Огаревские чтения: материалы научн. конф.: в 2 ч. - Ч. 2 : Естественные и технические науки. - Саранск : Изд-во Мордов. ун-та, 2006. - С. 237-238.

12. Савкина, А. В. Реализация системы поиска растровых изображений на основе вейвлет-преобразования, фрактального кодирования и смешанного подхода / А. В. Савкина // Информационные технологии моделирования и управления: научно-технический журнал №3(55) — Воронеж. Изд-во «Научная книга», 2009.-С. 387-393.

13. Савкина, А. В. Система поиска изображений по изображению-образцу методом вейвлет-преобразований, фрактального кодирования и смешанного подхода / A.B. Савкина // Свидетельство об официальной регистрации программы для ЭВМ 2009616350 от 11 января 2010 г.

14. Савкина, А. В., Система поиска изображений по изображению-образцу методом фрактального кодирования / А. В. Савкина, Э. Э Александров., П. В. Чадин. - Свидетельство об официальной регистрации программы для ЭВМ 2006614087 от 29 ноября 2006 г.

15. Савкина, А. В.Система хранения и поиска изображений по изображению-запросу методом вейвлет-преобразований / А. В. Савкина, Э. Э. Александров. - Свидетельство об официальной регистрации программы для ЭВМ 2006614088 от 29 ноября 2006 г.

16. Савкина, А. В. Формирование поиска растровых изображений из базы

данных по изображению-запросу / А. В. Савкина, Э. Э. Александров // Материалы IV международной конференции. Методы и средства управления технологическими процессами МСУТП-2007. - Саранск : Изд-во Мордов. ун-та, 2007. - С. 277-278.

Подписано в печать 21.10.10. Объем 1,0 л. л. Тираж 100 экз. Заказ № 1567. Типография Издательства Мордовского университета 430005, г. Саранск, ул. Советская, 24

Введение.

1 Современные проблемы поиска изображений в базе данных.

1.1 Актуальность проблемы поиска изображений.

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

1.3 Формализация постановки задачи поиска изображений.

Выводы к разделу 1.

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

2.1 Формализованная модель поиска изображений.

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

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

Выводы к разделу 2.

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

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

3.2 Разработка алгоритма для поиска изображений с помощью методики, предложенной для реализации модели на основе комбини-рования вейвлетного и фрактального методов.

Выводы к разделу 3.

4 Реализация алгоритмов и анализ формализованной модели с помощью 81 компьютерного эксперимента.

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

4.2 Разработка интерфейса системы поиска растровых изображений.

4.3 Выбор программного обеспечения.

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

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

4.6 Анализ результатов поиска растровых изображений.

Выводы к разделу 4.

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

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

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

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

Среди работ, посвященных данной проблеме можно отметить труды зарубежных и отечественных исследователей: J. P. Eakins, A. Vailaya, М. Figueiredo, Т. Kato, Т. Kurita, G. Yang, Т. S. Huang, Е. J. Stolnitz, Т. Derose, Т. Salesin, Н. Г. Федотова, М. А. Щербакова, И. М. Гостева, А. В. Мирошкина, С. К. Абрамова, В. В. Лукина, A. JI. Жизнякова, Н. В. Вакунова, В. П. Дьяконова, диссертационные работы А. В. Роя, Н. Е. Козина, И. В. Корябкиной, А. В. Нефёдова, И. П. Тищенко и многих других.

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

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

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

1. Анализ современных методов и проблем поиска изображений в базе j данных.

2. Разработка формализованной модели на основе фрактального кодирования и комбинирования вейвлетного и фрактального методов.

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

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

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

Объект исследования — множество методов поиска растровых изображений.

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

2. Методики поиска изображений в базе данных по искомому изображению на основе предложенной формализованной модели.

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

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

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

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

Результаты работы использованы в НИОКР «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» (программа «Участник молодежного научно-инновационного конкурса 2007» Фонда содействия развитию малых предприятий в научно-технической сфере, государственные контракты 5474/7987 от 03.12.07 и 6653/9110 от 21.01.09)

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

1. IV, V Международные конференции «Методы и средства управления технологическими процессами», Саранск, 2007,2009 гг.

2. XXXIV, XXXVII Огаревские чтения, Саранск, 2006,2009 гг.

3. XI научная конференция молодых ученых, аспирантов и студентов Мордовского государственного университета имени Н. П. Огарева, Саранск, 2006 г.

4. Международная научная конференция «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50), Саратов, 2009г.

5. 6-ая Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (с участием стран СНГ), Ульяновск, 2009г.

По результатам 4-ой Международной конференции "Методы и средства управления технологическими процессами» работа «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» признана победителем программы «Участник молодежного научно-инновационного конкурса 2007» («УМНИК»).

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 112 наименований и 12 приложений. Работа содержит 131 страницу основного текста, 62 страницы приложений, 27 рисунков, 3 таблицы.

Выводы к разделу 4

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

2. Проведен анализ результатов поиска изображений на основе фрактального кодирования, который показал, что его использование приводит к качественному поиску изображений практически по всем отмеченным модификациям за исключением эффектов текстуры и искусственных помарок. В этом случае очень хорошие результаты поиска изображений дает комбинированный подход, сочетающий в себе вейвлетное и фрактальное кодирование изображения; причем с уверенностью утверждать, что используя фракталы, картина будет найдена, если система покажет более 37,5 % совпадений, а для комбинированного подхода - более 35,2 %.

3. Проведено сравнение разработанных подходов к поиску изображений с известным алгоритмом [48], основанном на вейвлет преобразовании, в результате чего можно констатировать, что несмотря на наибольшее время поиска изображений по сравнению с вейвлетным подходом при комбинированном подходе (около 2 %) и при фрактальном подходе (около 6 %), качество поиска оказывается выше (соответственно, на 16 % и 10 %).

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

Заключение

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

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

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

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

4. Разработаны алгоритмы поиска изображения на основе методик, использующих фрактальное кодирование, а также сочетание вейвлет-преобразования и фрактального подхода. На основе разработанных алгоритмов создана система поиска изображений с учетом диаграммы последовательности, концептуальной модели и богатых возможностей фрактальных и вейвлетных методов. Система реализована с помощью среды программирования Turbo Delphi, пакета Matlab и СУБД MS Access и дает возможность находить изображения, содержащиеся в базе данных в виде коэффициентов, по изображению-образцу.

5. Предложена методика оценки эффективности поиска изображений с помощью которой проведен выбор параметров фрактального кодирования и вейвлет-функций. Выявлено, что оптимальным является использование максимальной глубины квадродерева равной 6. Экспериментально подтвержден выбор вейвлет-функции Хаара, использующейся при комбинированном подходе. Проведен анализ результатов поиска изображений, полученных с помощью разработанной системы с учетом модификаций изображений, который показал, что используя фракталы, изображение будет найдено, если система покажет более 37,5 % совпадений, а для комбинированного подхода — более 35,2 %.

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

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

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

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

1. Абрамов, С. К. Мера содержания фона на основе энтропии для поиска и сортировки изображений в базах данных / С. К. Абрамов, В. В. Лукин, Н. Н. Пономаренко // Радиоэлектронные и компьютерные системы, 2007. — №2 (21). — С. 24-28.

2. Алексеев К. А. Обработка сигналов и изображенийУWavelet Toolbox, 2003. Электронный ресурс. : (с изм. и доп.). — Режим доступа: http://vmw.nsu.ru/matlabMatLabJRU/wavelet/index.asp.htm.

3. Архангельский, А. Я. Программирование в Delphi 7 / А. Я. Архангельский. М.: ООО «Бином-Пресс», 2003. - 1152 с.

4. Архипов, А.Е. Методы цифровой обработки изображений : учеб. пособие / А.Е. Архипов, С В . Дегтярев, С. Садыков. Курск : Курск ГКТУ, 2002. -118 с.

5. Балтазар, Г. Хранилища с контентной адресацией // PC Week/RE, 2006. № 541. Электронный ресурс. : (с изм. и доп.). - Режим доступа: http://www.pcweek.ru/themes/detail.php?II>=73040

6. Вежневец, В. Обнаружение и локализация лица на изображении. Электронный ресурс. : (с изм. и доп.). Режим доступа: http://www.ict.edu.ru/ft/002403/num2face.pdf.

7. Графические поисковики, 2009 г. Электронный ресурс. : (с изм. и доп.). — Режим доступа: http://similar-images.googlelabs.com/.

8. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. -М.: Техносфера, 2006. -1072 с.

9. ГОСТ 6.10.1 -88.Унифицированные системы документации: Основные положения Текст.: Изд.офиц. Введен 01.07.89. - М.: Изд-во стандартов, 1991. - 13 с.; 21см.

10. Гостев, И. М. Математическая модель одного класса поисковых систем / И. М. Гостев, А. В. Мирошкин // Вестник РУДН, серия «Прикладная икомпьютерная математика», 2004. Т.З, №1. - С. 93-98.

11. Гостев, И. М. О методах распознавания графических образов / И. М. Гостев//Изв. РАН ТиСУ.-№ 1.-2004-С. 138-144.

12. Гофман, В. Э. Работа с базами данных в Delphi / В. Э. Гофман, А. Д. Хоманенко. СПб.: БХВ-Петербург, 2001. - 656 е., ил.

13. Гринченко, В.Т. Введение в нелинейную динамику. Хаос и фракталы / В. Т. Гринченко, В. Т. Мацыпура, А. А. Снарский. 2-е изд.- :ЛКИ, 2007с. -264 с.

14. Дейт, К. Д. Введение в системы баз данных / К. Д. Дейт. — М,: Вильяме, 2006. -1328 с.

15. Джонсон, Д. Распространение понятий и технологий юзабилити // Юзабилити Бюллетень, 2007. Выпуск № 24. Электронный ресурс. : (с изм. и доп.). — Режим доступа: http://www.usabilityprofessionals.ru /UsabilityBulletin-24.aspx?EntryID=769

16. Добепш, И. Десять лекций по вейвлетам / И. Добеши. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 464 с.

17. Елманова, Н. Delphi 6 и технология СОМ / Н. Елманова, С. Трепалин, А. Тенцер. Питер, 2002. - 617 с.

18. Козин, Н. Е. Показатели сопряженности и мультиколлинеарности в задачах анализа и распознавания изображений : Дис. . канд. техн. наук. Самара, 2009.-113 с.

19. Корябкина, И. В. Эффективные способы и средства описания изображений в задачах распознавания : Дисканд. техн. наук. Москва, 2006. -138 с.

20. Линейный Дискриминантный Анализ. Цифровая библиотека лаборатории компьютерной графики и мультимедиа при факультете ВМиК МГУ, 2003-03-19. Электронный ресурс. : (с изм. и доп.). Режим доступа: http://libraiy.graphicon.ru/catalog/l 84/.

21. Мандельборт, Б. Фрактальная геометрия природы / Б. Мандельборт. -М.: Институт компьютерных исследований, 2002. — 656 с.

22. Метод опорных векторов. Цифровая библиотека лаборатории компьютерной графики и мультимедиа при факультете ВМиК МГУ, 2003-03-19. Электронный ресурс. : (с изм. и доп.). Режим доступа: http://library.graphicon.ru/catalog/26/.

23. Морозов, А.Д. Введение в теорию фракталов / А. Д. Морозов. Москва-Ижевск: Институт компьютерных исследований, 2002. - 160 с.

24. Нефёдов, А. В. Эффективные алгоритмы, основанные на вычислении оценок, с прямоугольными опорными множествами, для задач распознавания изображений : Дис. канд. физ.-мат. наук. Москва, 2005. -132 с.

25. Орлов, С. Технологии разработки программного обеспечения: учеб. пособие / С. Орлов. СПб.: Питер, 2003. - 480 с.

26. Поисковая система компании Recogmission LLC, 2009, Электронный ресурс. : (с изм. и доп.). Режим доступа: http://www.picollator.ru/.

27. Рабинер, Л.Р. Скрытые марковские модели и их применение в избранных приложениях при распознавании речи: Обзор / Л.Р. Рабинер // Труды ИИ-ЭР, 1989. т. 77, Номер 2. - С. 86-120.

28. Рой, А. В. Биометрический поиск информации в базе данных изображений, основанный на стохастической геометрии : Дис. . канд. техн. наук. Пенза, 2008. 188 с.

29. Савкина, А. В. Разработка системы хранения растрового изображения / А. В. Савкина, Э. Э. Александров // XXXIV Огаревские чтения: материалы научн. конф.: в 2 ч. — Ч. 2 : Естественные и технические науки. Саранск: Изд-воМордов. ун-та,2006. -С. 237-238.

30. Савкина, А. В. Система поиска изображений по изображению-образцу, методом вейвлет-преобразований, фрактального кодирования и смешанного подхода / A.B. Савкина // Свидетельство об официальной регистрации программы для ЭВМ 2009616350 от 11 января 2010 г.

31. Савкина, А. В., Система поиска изображений по изображению-образцу методом фрактального кодирования / А. В. Савкина, Э. Э Александров., П. В. Чадин. — Свидетельство об официальной регистрации программы для ЭВМ 2006614087 от 29 ноября 2006 г.

32. Савкина, А. В.Система хранения и поиска изображений по изображению-запросу методом вейвлет-преобразований / А. В. Савкина, Э. Э. Александров. -Свидетельство об официальной регистрации программы для ЭВМ 2006614088 от 29 ноября 2006 г.

33. Садыков, С. С. Некоторые подходы к скелетизации полутоновых изображений / С. С. Садыков, A. JI. Жизняков, С. П. Серков // Компьютерные технологии обработки и анализа данных. — Ташкент: НПО «Кибернетика» АН РУз, 2000.

34. Столниц Э. Вейвлеты в компьютерной графике / Э. Столниц, Т. ДеРо-уз, Д. Салезин. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. — 272 с.

35. Тищенко, И. П. Алгоритмическое и программное обеспечение мультипроцессорных систем для распознавания графических образов на основе ней-росетевого подхода : Дис. . канд. техн. наук. Переславль-Залесский, 2009. — 114 с.

36. Уэлстид, С. Фракталы и вейвлеты для сжатия изображений в действии: учебн. пособие / С. Уэлстид. М.: Триумф, 2003. - 320 с.

37. Федотов, Н. Г. Методы стохастической геометрии в распознавании образов / Н. Г. Федотов. М.: Радио и связь, 1990. - 144 с.

38. Факторный анализ. Цифровая библиотека лаборатории компьютернойграфики и мультимедиа при факультете ВМиК МГУ, 2003-03-19. Электронный ресурс. : (с изм. и доп.). Режим доступа: http://library.graphicon.ru/catalog/217/.

39. Файн, В. С. Опознавание изображений (основы непрерывно-групповой теории и ее приложение) / В. С. Файн. М.: Наука, 1970. - 299 с.

40. Фукунага, К. Введение в статистическую теонрию распознавания образов / К. Фукунага. М.: Наука Главная редакция физико-математической литературы, 1979. - 368 с.

41. Aiello, M. Fast convergence for spectral clustering / M. Aiello, F. An-dreozzi, E. Catanzariti, F. Isgro, M. Santoro // 14th International Conference on Image Analysis and Processing (ICIAP 2007), 2007. pp. 641-646.

42. Andronache, A. Non-rigid registration of multi-modal images using both mutual information and crosscorrelation / A. Andronache, M.von Siebenthal, G. Szekely, P. Cattin // Medical Image Analysis, 2008. vol. 12(1). - pp. 3-15.

43. Asgari, S. Wavelet-Based Fractal Transforms for Image Coding with No Search / S. Asgari, T. Q. Nguyen, W. A. Sethares // IEEE International Conference on Image Processing, (ICIP97), 1997. pp. 302-305.

44. Baeza-Yates, R. Modern Information Retrieval / R. Baeza-Yates, B. Ribe-rio-Neto. New York: Addison-Wesley, 1999. - 513 p.

45. Baluja, S. Finding Images and Line Drawings in Document-Scanning Systems / Shumeet Baluja, Michele Covell // Proc. International Conference on Document Analysis and Retrieval, 2009.

46. Barnard, K. Learning the Semantics of Words and Pictures / K. Barnard, D. Forsyth // International Conference on Computer Vision, 2001. pp. 408-415.

47. Barnard, K. Matching words and pictures / Kobus Barnard, Pinar Duygulu, David Forsyth, Nando de Freitas, David M. Blei, Michael I. Jordan // The Journal of Machine Learning Research, 2003. vol 3. - pp. 1107-1135.

48. Barnsley, M. Fractals Everywhere / M. Barnsley. Boston: Academic Press, 1988. - 396 p.

49. Chapelle, O. Support vector for histogram-based image classification / O. Chapelle, P. Haffiier, V.Vapnik // IEEE transactions on Neural Networks, 1999. -vol. 10(5). — pp. 1055-1065.

50. Davis, G. Implicit Image Models in Fractal Images Compression / G. Davis // Proceedings of SPIE Conference on Wavelet Applications in Signal and Image Processing IV. Denver, 1996. - vol. 2569. - pp. 88-97.

51. Davis, G. Wavelet-based Analysis Of Fractal Image Compression / G. Davis // IEEE Transactions on Image Processing, 1998. vol. 7, no. 2. - pp. 141-154.

52. Davis, G. Wavelet-based Image Coding: An Overview / G. Davis, A. No-sratinia // Applied and Computational Control, Signals, and Cercuits, 1998. vol. 1, no. l.-pp. 25-48.

53. De Bonet, J. S. Texture Recognition Using a Non-parametric Multi-Scale Statistical Model / J. S. De Bonet, P. Viola // Proceedings IEEE Conference on Computer Vision and Pattern Recognition, 1998. pp. 641-647.

54. Eakins, J. P. Similarity retrieval of trademark images / J. P. Eakins, J. M. Boardman, M. E. Graham // IEEE Multimedia, 1998. vol. 5, no. 2. - pp. 53-63.

55. Edwards, G. J. Interpreting Face Images using Active Appearance Models / G. J. Edwards, C. J. Taylor, T. F. Cootes // 3rd International Conference on Automatic on Face and Gesture Recognition, 1998. pp. 300-305.

56. Falconer, K.J. Fractal Geometry: Mathematical Foundations and Applications / K. J. Falconer. New York: J. Wiley&Sons, 1990. -288 p.

57. Fisher, Y. Fractal Image Compression / Y. Fisher. New York: SpringerVerlag, 1995.-345c.

58. Forsyth, D. Computer vision-ECCV 2008 : 10th European Conference on Computer Vision / David Forsyth, Philip H. S. Torr, Andrew Zisserman. Marseille, France, 2008. - 801 p.

59. Hacid, H. Content-based retrieval in large image databases / H. Hacid, D. A. Zighed // Proc. of International Conference on Granular Computing, 2006. pp. 498-501.

60. Hebert, D. Fast Fractal Image Compression with Triangulation Wavelets / D. Hebert, E. Soundararajan // Proceedings of SPIE Conference on Wavelet Applications in Signal and Image Processing VI. San Diego, 1998. - pp. 747-750.

61. Heisele, B. A Component-based Framework for Face Detection and Identification / Bernd Heisele, Thomas Serre, Tomaso Poggio // International Journal of Computer Vision, 2007. vol. 74(2). - pp. 167-181.

62. Hjelmas, E. Face detection: A survey / E. Hjelmas, B. K. Low // Journal of Computer Vision and Image Understanding, 2001. vol. 83. - pp. 236-274.

63. Holt, B. Query by Image Content, the QBIC Project's Applications at Davis's Art and Art History Departments / B. Holt, L. Hartwick, S. Vetter // Visual Resources Association Journal, 1995. vol. 22, no. 2. - pp. 61-65.

64. Huang, J. Image Indexing Using Color Correlograms Computer Vision and Pattern Recognition / J. Huang, S. R. Kumar, M. Mitra, W. Zhu, R; Zabih,// IEEE Computer Society Conference, 1997. p. 762.

65. Huang, J. An Automatic Hierarchical Image Classification Scheme / J. Huang, S. R. Kumar, R. Zabih // Proceedings of the Sixth ACM International Conference on Multimedia. Bristol, United Kingdom, 1998. - pp. 219-228.

66. Jacobs, C. Fast multiresolution image querying / C. Jacobs, A. Finkelstein,

67. D. Salesin I I Proc SIGGRAPH-95,1995. pp. 277-285.

68. Jolliffe, I. T. Principal Component Analysis, Series: Springer Series in Statistics /1. T. Jolliffe. 2nd ed. - New York: Springer Verlag, 2002. - 487 p.

69. Juell, P. A hierarchical neural network for human face detection / P. Juell, R. Marsh // Pattern Recognition, 1996. vol. 29, no. 5. - pp. 781-787.

70. Kato, T. A Cognitive Approach to Visual Interaction / T. Kato, T. Kurita, H. Shimogaki, T. Mizutori, K. Fujimura // Proceedings of the International Conference on Multimedia Information Systems. Singapore: McGraw Hill Book Co, 1991.-pp. 109-120.

71. Keen, L. Julia sets / L. Keen // Chaos and Fractals: The Mathematics Behind the Computer Graphics. -American Mathematical Society, Providence, 1989. -pp. 57-74.

72. Kotropoulos C. Rule-Based Face Detection in Frontal Views / C. Kotro-poulos, I. Pitas // Proc. Int'l Conf. Acoustics, Speech and Signal Processing, 1997. -vol. 4.-pp. 2537-2540.

73. Lauwerier, H.A. Fractals images of chaos / H.A. Lauwerier. - London: Penguin Books, 1991. - 209 p.

74. Lin, S.-H. Face recognition/detection by probabilistic decision-based neural network / S.-H. Lin, S.-Y. Kung, L.-J. Lin // IEEE Transactions on Neural Networks 8,1997.-pp. 114-132.

75. Lipson, P. Configuration based scene classification and image indexing / P. Lipson, E.Grimson, P. Sinha//CVPR'97, Puerto Rico, 1997.-pp. 1007-1013.

76. Malik, J. Preattentive texture discrimination with early vision mechanisms / Jitendra Malik, Pietro Perona // Journal of the Optical Society of America, 1990.vol. 7, no. 5. pp. 923-932.

77. Ogle, V. E. Chabot: retrieval from a relational database of images / V. E. Ogle, M. Stonebraker // IEEE Computer, 1995. vol. 28(9). - pp. 40-48.

78. Pass, G. Comparing Images Using Joint Histograms / G. Pass, R. Zabih // Multimedia Systems, 1999.- vol. 7.-pp. 234-240.

79. Pentland, A. Photobook: content-based manipulation of image databases / A. Pentland, R. W. Picard, S. Sclaroff // International Journal of Computer Vision, 1996. vol. 18(3)/ - pp. 233- 254.

80. Popescu, D. A Nonlinear Model for Fractal Image Coding / D. Popescu, A. Dimca, H. Yan // IEEE Transactions on Image Processing, 1997. vol. 6, no. 3. - pp. 373-382.

81. Reverse Image Search, 6 мая 2008 г. Электронный ресурс. : (с изм. и доп.). — Режим доступа: http://www.tineye.com/.

82. Rowley, H. A. Neural network-based face detection / H. A. Rowley, S. Baluja, T. Kanade // IEEE Transactions on Pattern Analysis and Machine Intelligence 20,1998.-pp. 23-38.

83. Rubner, Y. A metric for distributions with applications to image databases / Y. Rubner, C. Tomasi, L. Guibas // Proceedings of the IEEE International Conference on Computer Vision, 1998. pp. 59-66.

84. Sakai, T. Line Extraction and Pattern Detection in a Photograph / T. Sa-kai, M. Nagao, S. Fujibayashi // Pattern Recognition, 1969. vol. 1. - pp. 233-248.

85. Smith, J.R. VisualSEEk: A Fully Automated Content-Based Image Query System / J. R. Smith, S. F. Chang // ACM Multimedia Conference. Boston, 1996.-pp. 87-98.

86. Sung, К. K. Example-Based Learning for View-Based Human Face Detection / Kah Kay Sung, Tomaso Poggio // IEEE Transactions on Pattern Analysis and Machine Intelligence. vol. 20(1), 1998. - pp. 39-51.

87. Swain, M. Color Indexing / M. Swain, D. Ballard // International Journal of Computer Vision, 1991. vol. 7. - pp. 11-32.

88. Vailaya, A. Image classification for content-based indexing / A. Vailaya, M. Figueiredo, A. K. Jain, H.-J. Zhang // IEEE Transactions on Image Processing, 2001.-vol. 10.-pp. 117-130.

89. Warren, J. Binary subdivision schemes for functions over irregular knot se guences / J. Warren // Mathematical Methods in Computer Aided Geometric Design III. San Diego, Academic Press, 1995. - pp. 543-562.

90. Wei-Ying Ma, B. S. Manjunath: Texture-Based Pattern Retrieval from Image Databases / B. S. Wei-Ying Ma // Multimedia Tools Appl, 1996. vol. 2(1). -pp. 35-51.

91. Wei-Ying Ma, B. S. NETRA: A Toolbox for Navigating Large Image Databases / B. S. Wei-Ying Ma // Multimedia System, 1997. pp 184-198.

92. Yang, G. Human Face Detection in Complex Background / G. Yang, T. S. Huang // Pattern Recognition, 1994. vol. 27, no. 1. - pp. 53-63.

93. Yang, M. H. Detecting faces in images: A survey / M. H. Yang, D. J. Kriegman, N. Ahuja // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002. vol. 24, no. 1. - pp. 34-58.

94. Zhou, Z.-H. Queiy-sensitive similarity measure for content-based image retrieval / Z.-H. Zhou, H.-B. Dai // Proceedings of International conference on Data Mining, 2006. -pp. 1211-1215.