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

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

Талбонен Андрей Николаевич

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ПОИСКА В ЭЛЕКТРОННЫХ КОЛЛЕКЦИЯХ ИСТОРИЧЕСКИХ ФОТОГРАФИЙ

Специальность 05.13.18 -Математическое моделирование, численные методы и комплексы программ

Автореферат

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

2 2 НОЯ 2012

Петрозаводск 2012

005055764

005055764

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

Научный доктор технических наук, профессор

руководитель: Рогов Александр Александрович

Официальные Жабко Алексей Петрович, доктор

оппоненты: физико-математических наук, профессор,

заведующий кафедрой теории управления ФГБОУ ВПО «Санкт-Петербургский государственный университет»

Вдовицын Владимир Трофимович, кандидат физико-математических наук, доцент, руководитель лаборатории информационных компьютерных технологий ФГБУН Института прикладных математических исследований Карельского научного центра РАН

Ведущая ФГБУН Санкт-Петербургский

организация: информатики и автоматизации РАН

институт

Защита состоится «20» декабря 2012 г. в 10:00 часов на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО «Петрозаводский государственный университет» по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

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

Автореферат разослан «09» ноября 2012 г.

Ученый секретарь

диссертационного совета Р. В. Воронов

Общая характеристика работы Актуальность темы исследования.

Термин «информационный поиск» был впервые введён К. Муром в конце 40-х годов. С момента появления данного термина до сегодняшних дней системы информационного поиска значительно эволюционировали от простых каталогов научной литературы до глобальных поисковых систем. Поиск информации представляет собой процесс отыскания во множестве цифровых материалов таких, которые удовлетворяют определенным критериям (поисковый запрос). При этом источниками информации могут служить как текстовые материалы (полнотекстовый поиск), так и изображения (поиск изображений).

Значительный вклад в развитие поиска по тексту внесли ученые В. Буш, Дж. Сэлтон, Т. Нельсон и др. Современные поисковые системы позволяют выполнять поиск по содержанию документов, а также по различным атрибутам (метаданным). На сегодняшний день существует множество коммерчески успешных продуктов, а также их бесплатных аналогов («Google», «Bing», «Яндекс» и др.).

Поиск по изображениям осуществляется на основе их аннотирования, который осуществляется двумя способами. Первый способ аннотирования, осуществляемый создателем коллекции, состоит в приписывании текстовых меток (тэгов) к изображениям (фотоколлекции «Picasa», «Flickr», «Яндекс.Фотки» и др). Второй способ реализуется на основании автоматического поиска объектов на изображениях и тесно связан с другой областью вычислений — распознаванием образов. Большой вклад в развитие теории распознавания образов внесли ученые В. Н. Вапник, В. М. Глушков, А. Л. Горелик, Ф. Розенблатт, Б. Уидроу, JI. Рабинер и др.

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

Современные поисковые системы («Google Images», «Яндекс.Картинки» и др.) позволяют выполнять поиск в электронных графических коллекциях первого типа. Ограничения, накладываемые на изображения коллекций второго типа, не позволяют автоматически использовать их методы для организации поиска.

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

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

1. Разработка алгоритма извлечения текстовой информации из коллекции изображений низкого качества.

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

3. Анализ существующих систем поиска по изображениям и методов аннотирования изображений

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

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

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

7. Компьютерная реализация вышеперечисленных алгоритмов и создание комплекса программ для построения поисковой системы.

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

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

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

2. Метод извлечения текстовой информации, содержащей ошибки, из коллекции изображений низкого качества.

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

4. Программный комплекс для построения поисковой системы для коллекции исторических фотографий

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

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

Степень достоверности.

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

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

1. XII Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (RCDL'2010) (Казань, 2010).

2. XIII Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (RCDL'2011) (Воронеж, 2011).

3. Всероссийская научно-практическая конференция «Анализ Изображений, Сетей и Текстов» (АИСТ 2012) (Екатеринбург, 2012). По теме диссертации опубликовано 8 научных работ, 2 из них входят в список ВАК.

Разработанное программное обеспечение было апробировано на коллекции фотографий строительства Беломорско-Балтийского канала, а построенная по ней поисковая система внедрена в Национальный музей республики Карелия. Данный программный комплекс был зарегистрирован в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 18562 от 08.10.2012 г.

Структура и объем диссертации. Диссертация состоит из введения, 6 глав, заключения и библиографического списка использованной литературы (105 наименований), имеет объем 112 страниц машинописного текста, включая 7 страниц приложений, содержит 37 рисунков и 12 таблиц.

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

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

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

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

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

1. Низкое разрешение оцифрованных изображений, менее 100 точек на дюйм.

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

3. Наличие шумовых эффектов в виде случайных пикселей (эффект «соль и перец») и других.

4. Коллекции состоят из черно-белых изображений

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

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

7. Наличие объектов (лица, здания, сооружения), а также фрагментов объектов (текстуры, контуры) на изображениях.

Для данного диссертационного исследования интерес представляют поисковые машины, способные работать с изображениями в качестве исходных ресурсов. Подобные машины называются «CBIR engine» (Content-based image retrieval engine, машина поиска изображений по содержанию). Среди существующих поисковых машин, обладающих данным качеством, можно выделить «TinEye», «Picsearch», «Google Images», «Яндекс Картинки» и другие.

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

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

На данный момент существуют множество систем распознавания текста. Среди систем, поддерживающих русский язык, можно выделить «ABBYY FineReader», «CuneiForm», «Google Tesseract» и другие. К сожалению, низкое качество исследуемых изображений, нестандартный

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

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

¡3 48. Сентября 17,1931г. Поселок С 4/Зодорзздед/.Зы- ^ ход какала в губу ВодЛоз. я

Рисунок 1. Область изображения, содержащая текст и подлежащая распознаванию.

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

1. Эвристический метод порогового отсечения без параметров

2. Методы пространственной фильтрации, применяющие лапласиан.

3. Методы выделения границ

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

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

Обозначим через / текущее изображение, тогда Мг (i = 1 ,п, где п — число методов) - методы обработки изображений, а /; = М;(/) - результаты обработки изображения / соответствующими методами (альтернативные изображения). Применив распознавание с помощью какой-либо системы OCR, получим набор текстовых файлов (альтернативные текстовые файлы) F;. Пусть нам известна общая цепочка синтагм текста исходного изображения. Тогда в целом та же цепочка должна сохраниться после распознавания. Применив соответствующий синтаксический анализ к каждому из полученных альтернативных текстовых файлов, получим наборы альтернативных текстовых элементов. Таким образом, можно рассматривать текстовые файлы F; как множества текстовых элементов размером т, упорядоченных в строгом соответствии со своим местом (индексом) в цепочке синтагме. Т.е. Fj = {tij\j = 1 ,т}.

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

Оценки текстового элемента рассчитываются на основе веса каждого слова, входящего в данный элемент. Вес каждого слова зависит от его схожести с одним или несколькими словами из словаря, которые будем называть словами-кандидатами. Рассчитывается вес по следующей формуле: IV = -—, где п - длина слова, Ь — расстояние Левенштейна до слова-кандидата. В случае, когда Ь> п вес считается равным 0. Вес слова, найденного в словаре, будет равен 1.

Пусть У/ц - общий вес (сумма весов слов), а Му - количество слов элемента £у. Тогда оценка элемента Гу будет рассчитываться следующим образом: Я у = 5у

где

■0у,

(о, ыи = О

О, Иц >2-Ц

Ы,

N¡ = ^1.

1 п

С учетом свойств множителей 5у и Оу получаем, что Ду = [0; 1]. В результате сравнения определим «оптимальные» элементы = {¡.у, причем £* = а^тах^Ду), где £ = 1,п и _/ = 1, т. Новый текстовый файл может быть получен в результате синтеза: Р* = Пример сравнения альтернативных текстовых элементов приведен в таблице 1.

С учетом оценок текстовых элементов будем оценивать текстовые

файлы Г/ = {Су} следующим образом: Д4 = т.к. Ду е [0; 1], то Д,- е [0; 1].

Таблица 1

Имя метода Оценки элементов

Основной текст Дата Номер

СШ 0,80 1,00 0,60

ЕАЬар1а$ 0,78 0,85 0,80

АЕЬаркэ 0,85 0,75 0,75

ЕАЕЬар1аз 0,82 0,90 0,90

В § 2.8 описываются теоретические основы анализа текстовой коллекции, рассматриваются существующие морфологические анализаторы. В качестве основного морфологического анализатора в данном диссертационном исследовании используется программа «МуБ1ет» от компании «Яндекс», поддерживающая несколько тематических атрибутов.

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

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

В данном исследовании предлагается следующий метод аннотирования изображений при отсутствии базы данных, состоящей из изображений лиц и соответствующих текстовых меток (далее — база данных лиц):

1. Извлечение объектов (изображения лиц).

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

3. Аннотирование. Данный процесс является итеративным и может выполняться до тех пор, пока все найденные объекты не будут помечены. Итерация включает в себя следующее:

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

b. Если эксперт обнаруживает сходство между объектами, система создает связь между ними.

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

Современные алгоритмы обнаружения лиц хорошо работают для объектов с размерами около 100 пикселей и выше. В таких случаях полнота и точность приближаются к 100%. Однако при оптимальных параметрах для больших объектов данные методы демонстрируют низкую полноту обнаружения небольших объектов, размером не больше 40 пикселей. Исследование одной из исторических коллекций, коллекции строительства Беломорско-Балтийского канала, показало высокий процент содержаний объектов небольшого размера. На рисунке 2 представлено распределение размеров объектов-лиц данной коллекции. Доля объектов размером меньше 40 пикселей составляет для данной коллекции 60%. Еще 20% занимают объекты размеров от 40 до 50 пикселей.

канала

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

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

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

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

текущего объекта до объектов обоих множеств обучающей выборки. Если расстояние до множества объектов-лиц будет меньше расстояния до множества ложных объектов, текущий объект будет считаться лицом, иначе — ложным объектом.

В данной работе для распознавания лиц используются модификации алгоритма локальных бинарных шаблонов (Local Binary Pattern, LBP, ЛБШ). Данный алгоритм на данный момент имеет множество различных модификаций, позволяющих с высокой точностью распознавать лица; в некоторых случаях точность может доходить до 95%.

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

5 4 3

4 3 1

2 0 3

Порог =3

1 1 1

■ ■ •

0 0 1

Двоичное: 11101001 Десятичное: 233

Рисунок 3. Пример вычисления кода для простого ЬВР.

Современные модификации предполагают вычисление кодов ЬВР в окрестности определенного радиуса (Я) тл с определенным числом точек (Р), равностоящих друг от друга на соответствующей окружности (см. рисунок 4). В этом случае значение в точке окрестности интерполируется.

Рисунок 4. Примеры различных окрестностей для вычисления кодов ЬВР: (а) - радиус 1, число точек 8; (б) — радиус 2.5, число точек 12; (в) — радиус 4, число точек 16.

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

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

_1_ _1____!__

_1____1__0_

_!_ _±_ Л. -1 _!__2_ 0 111110

Рисунок 5. Матрица весов, применяемая для распознавания лиц.

Рисунок 6. Схема вычисления общей гистограммы объекта-лица с помощью матрицы

весов.

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

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

Кроме очевидных лиц и ложных объектов, найденных в «полной» коллекции, были определены дополнительные правила оценивания. К

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

В процессе классификации объекты преобразовывались к размеру 64 х 64. Эксперименты проводились и использованием нескольких фильтров с различными параметрами расчета гистограммы и с различными обучающими множествами. Для вычисления векторов признаков использовались фильтры ЬВР[£^ и ¿ВРДи32. В одних случаях применялась матрица весов (рисунок 5), в других случаях вектор признаков сжимался до размера 200. В качестве множества лиц использовался набор из 18 изображений лиц. Кроме того, было задано 2 множества ложных объектов (8 и 26 изображений, Е1 и Е2 соответственно).

Результатом каждого эксперимента являлась отдельная коллекция объектов. Полученные коллекции оценивались полнотой и точностью, для расчета которых объекты коллекций сопоставлялись с объектами экспертной коллекции. Результаты экспериментов, позволяющие сравнить качество полученных коллекции с соответствующими параметрами «полной» и «точной» коллекций, представлены в таблице 2 и на рисунке 7. Описание каждого эксперимента содержит параметры фильтра ЬВР, использованные методы расчета гистограмм, а также множество ложных объектов.

Таблица 2

Результаты экспериментов по повышению точности и полноты_

Название Описание Лица Ошибки Полнота Точность И-мера

ЭК Экспертная коллекция 793 0 1,000 1,000 1,000

ПК Полная коллекция 540 973 0,681 0,357 0,468

ТК Точная коллекция 439 289 0,554 0,603 0,577

ЬВР_24_1 529 484 0,667 0,522 0,586

ЬВР_24_2 ЬВРЩ, Е2 492 294 0,620 0,626 0,623

ЬВР_24_\¥_0_1 ¿ВР"4"з, веса, сжатие, 522 364 0,658 0,589 0,622

ЬВР_24_\У_0_2 ЬВРг2'£, веса, сжатие, Е2 499 319 0,629 0,610 0,619

ЬВР_24_\у_1 1ВРГ2'£, веса, 506 292 0,638 0,634 0,636

ЬВР_24_\у_2 1ВРГ1£, веса, Ег 483 226 0,609 0,681 0,643

ЬВР_16_1 532 492 0,671 0,520 0,586

ЬВР_16_2 1ВР^1Е2 512 332 0,646 0,607 0,626

ЬВР_16_\¥_0_1 1ВРГЦз2, веса, сжатие, ЕЛ 520 370 0,656 1 0,584 0,618

ЬВР_16_\У_0_2 ЬВРТ^}, веса, сжатие, Ег 499 306 0,629 0,620 0,625

ЬВР_16_\У_1 1ВР^1, веса, Е1 510 305 0,643 0,626 0,634

ЬВР_16_Ш_2 ЬВР[%веса, Е2 488 230 0,615 0,680 0,646

Рисунок 7. Диаграмма сравнения полноты и точности обнаружения лиц.

Проведенные эксперименты показали, что гистограммы, полученные с помощью фильтров ЬВР^з и Р-24^3 1 матрицы весов и расширенной обучающей выборки обладают наилучшей селективной способностью с точки зрения Б-меры. Кроме того, в большинстве случаев, расширение обучающей выборки позволило сократить количество ошибок и, следовательно, точность и Б-меру отсортированной коллекции. Однако даже использованные в экспериментах небольшие выборки показали более высокие показатели по сравнению с простым алгоритмом Виолы-Джонса.

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

Для определения «лучшей» модификации ЬВР разработан следующий метод. Данный метод предполагает поиск совпадений среди тестового множества объектов. Обозначим данный набор как Т. Совпадением будем считать пару объектов, являющихся изображениями лица одного и того же человека. Кроме того, тестовое множество включает несколько ложных объектов в качестве контрольной группы. Метод заключается в поиске для каждого объекта ближайшего к нему объекта. В результате формируются пары объектов. Каждое совпадение (релевантная пара объектов) добавляется в соответствующее множество упорядоченных пар. Обозначим за Т+ множество релевантных пар объектов-лиц, а за 1 - множество пар ложных объектов. В зависимости от наличия совпадений рассчитывается точность для каждого использованной модификации ЬВР.

Для анализа работы различных фильтров ЬВР используется следующий алгоритм:

1. Для каждого объекта ^ £ Т находится ближайший к нему объект б Т. Т.е. С* = аг§гшпС;{рД£г, е Г/Сг}.

2. Полученное таким образом множество пар Тр = {< > |гг е Т} сопоставляется с известными парами лиц и ложных объектов.

{1, < Ь-, Ь- >£ Т+ и Т~

11 ' индикатор

О, иначе

распознавания пар.

4. Тогда будем рассчитывать точность ке следующим образом: Яе =

|Г+|+|Т"| "

В данной работе в качестве множества Т использовалась выборка, представленная в таблице 3. При этом, во множестве присутствуют следующие пары лиц, соответствующих одному и тому же человеку: {3, 14}, {4, 13} и {7, 9}. Обозначим данное множество как Т+. Кроме того, очевидна пара ложных объектов, которые должны быть близки друг к другу: {1, 15} (Т+). Дополним множества Т+ и Т~ зеркально отраженными элементами данных множеств.

Таблица 3

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

Таблица 4

Результаты экспериментов по распознаванию лиц

Обозначение Точность Re

LBPel 0,38

LBP161 0,25

1ВР82 0,50

LBP 16 2 0,50

LBPe. з 0,50

LBP163 0,75

Взвешенный LBP"63 0,50

Взвешенный LBP"Hf 0,38

Взвешенный ¿BP"6 3 0,63

Взвешенный LBP16 3 1,00

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

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

В данной работе рассматривается алгоритм текстурной сегментации на основе моментов. Рассмотрим прямоугольное изображение шириной W и высотой Н. Пусть fix,у) - значение изображения в точке (х,у), нормализованное на отрезке [0; 1]. Метод моментов заключается в том, что для каждой точки изображения fix,у) рассчитывается набор моментов и производных от них характеристик в пределах некоторого окна с центром в данной точке. Таким образом, формируется набор изображений, соответствующих набору признаков.

Момент Mpq с центром в точке (i,/) и размером окна WM рассчитывается следующим образом: Mpq(i,j) = Y.(a,b)eWif ' ха ' Уь >

где Ха = Уь ~ Sir Wif ' окно РазмеРом Wm с центром в точке (ij).

В качестве значений векторов признаков используются значения точек изображений характеристик моментов Fp q:

Fp.qii,j) = Z(a,b)ew^ I tanh(ff(Mp„(a, b) - M^)) | - значение характеристики момента порядка (р, q) в точке ([,;'), где Mpq{i,j} = b^ew'j MPfq(.a, b) - усредненное изображение момента Mp q, Wfi - окно

размером WFc центром в точке (t,y).

Степени моментов р и q задаются таким образом, чтобы их сумма не превышала некоторого значения Та, т.е. р + q <Т0. Тогда общее количество

, - (Г„+1)(Г0+2)

изображении моментов и характеристик моментов будет равно---.

Для поиска текстур предлагается следующий классификатор:

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

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

3. Для каждого изображения вычисляются изображения характеристик моментов Fp q. Значения изображений характеристик моментов в точке (i,j) определяют вектор признаков следующим образом: {Fpq(i,j)\ р + q < Тв}. Порядок расположения значений признаков внутри вектора фиксируется, например, при Т0 = 2 вектор признаков равен {Fo.o, Fo.I. h.0, F2 0}.

4. Для каждого изображения вычисляется карта текстур. Размер карты равен размеру изображения. Значением карты для данной точки является номер первой соответствующей данной точке текстуры. Если данной точке не соответствует ни одна из текстур, точка карты принимает значение -1.

5. Точки полученной карты текстур объединяются в сегменты, которые состоят из соседних точек с одинаковым номером текстуры. Точки со значением -1 в сегменты не объединятся.

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

Формулы расчета моментов и признаков характеризуются сложностью 0(W ■ Н • М2), где М - размер окна. Однако часть выражений, заданных этими формулами, представляют собой дискретную свертку с определенным ядром, что позволяет использовать быстрые методы вычисления свертки, основанные на быстром преобразовании Фурье. В данной работе используются подобные операции, позволяющие снизить сложность вычислений до 0(W • Н • log WH).

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

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

2. Каждому классу присваивается набор меток.

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

4. Для каждой найденной текстуры к изображению добавляется набор меток соответствующего класса.

отмечаются

вручную с помощью эксперта: Etj =

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

Г1, Г,- найдено в L

.С

[О, иначе

другой стороны с помощью классификатора автоматически определяются вхождения каждой текстуры (аналогично Ец), после чего определяется флаг релевантности текстуры Ду (1-текстура 7) найдена на изображении и при этом обнаружена экспертом), который рассчитывается как Д;;- = Е■ Fy. Тогда полнота Де;- и точность Pry поиска текстуры Tj рассчитывается

следующим образом: Де,- = 11, Prj = 4.

2J i^ij LiFij

Аналогично можно рассчитать общую полноту Re и точность Рг поиска: Re

_ Ei.iRij pr _ Zi,iRij

Для оценки работоспособности классификатора был проведен следующий эксперимент. В качестве исходных данных было использовано множество текстур, представленное в таблице 5. Были заданы следующие параметры классификатора: Та = 2, = 9,1Ур = 49, а = 0.01.

Таблица 5

■

Крыша дома (Тг) Стена дома (Г2)

На рисунке 8 представлены результаты эксперимента.

Рисунок 8. Результаты эксперимента по поиску текстур.

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

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

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

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

Например, пусть в таблице <tbl> создано полнотекстовое поле <text>, тогда для поиска по всему тексту достаточно выполнить запрос:

SELECT * FROM <tbl> WHERE FREETEXT (<text>, '<query>'),

где в качестве <query> подставляется поисковой запрос в виде текстовой строки (набор слов с пробелами).

Таким образом, изменяя содержимое столбца <text>, можно влиять на результат поиска. В данном диссертационном исследовании рассматривается общая модель формирования полнотекстового индекса за счет списка слов.

Пусть I - изображение, на котором присутствуют различные объекты. Задача индексирования сводится к получению текстового описания каждого объекта в виде набора слов и добавления этого набора в индекс. Пусть К — множество типов объектов. Каждому типу объекта ставится в соответствие набор < Ffc, Ft >, где Fg - программная функция извлечения объекта данного типа в виде изображения, - программная функция, формирующая текстовое представление данного объекта. При этом не обязательно, чтобы программные функции выполнялись строго автоматически. В качестве программных функций могут использоваться также автоматизированные, либо ручные методы.

Не учитывая зависимость каждой программной функции из набора <Fk>Fk> от множества глобальных объектов и параметров, определим данную программную функцию как Fg\I -*Т, где / — исходное изображение, Г — множество объектов.

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

Рассмотрим в качестве примера случаи, когда сходство каких-либо двух объектов порождает один и тот же текстовый набор. Пусть объект с помощью программной функции порождает текстовый набор W± = {w1;} и при этом находится объект t2, который является сходным для объекта tt. Тогда объекту t2 может быть поставлено в соответствие текстовое множество Щ.

Найденное множество объектов и соответствующее множество текстовых наборов {W{] будем считать глобальными объектами, тогда можно определить программную функцию FЦ следующим образом: F^-. t —> W, где t — исходный объект, W — порожденный текстовый набор.

Полнотекстовые модули современных СУБД для обеспечения поиска требуют от стороннего программного обеспечения запись текста в специальную таблицу в определенном формате. Данную таблицу можно представить в виде множества записей вида {< /¡, Tt > |t = 1 ,N], где -изображение (источник текстовой информации), - соответствующий текст, N - число изображений. В свою очередь текст можно представить как множество слов 7j = {w^-\j = l,Mi], где Mi - количество слов в тексте 7^. Тогда с учетом определенных выше обозначений получим общую модель формирования текстовой информации для изображения /¡: Гг =

Uj^7^'(/¡)у), при этом будем считать множества допускающими повторения.

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

Каждое лексическое правило поиска состоит из последовательности элементов различных типов, каждый из которых выполняющий логическую операцию сопоставления слова типу данного элемента. Процедура поиска по лексическому правилу заключается в поэлементном сопоставлении текстовой строки в виде последовательности слов {w,-|t = 1 ,п}, где п - количество слов и элементов правила R = {rj\j = 1, т}, где т - количество элементов правила R (см. рисунок 9).

ы

Н ЕЗ

ыы

W,+m-l

Рисунок 9. Схема сопоставления поискового правила.

Сопоставление выполняется строго в порядке возрастания индекса элементов. При этом первый элемент правила может сопоставляться с любым допустимым элементов текстовой последовательности {и/;} (£ < п — т + 1). Таким образом, поиск по всей строке требует п — т+ 1 операций сопоставления.

Например, в материалах коллекции строительства ББК часто встречается словосочетания вида: «шлюз» <число>. Поиск будет точнее, если полнотекстовый индекс будет различать объекты типа «шлюз» друг от друга исходя из номеров, чтобы поиск объекта «шлюз 16» выдал документы, где встречается упоминание шлюза именно с таким номером. Для этого можно выполнить контекстный поиск по правилу:

const шлюз, simple number, с указанием следующего преобразования:

replace from {0}, to {1} with concat {item {0}, item {!}}; add taxon into item {0} value concat {item {0}, item {I}}. В шестой главе описывается программный комплекс, разработанный для поддержки данного диссертационного исследования.

Программный комплекс включает в себя следующие компоненты:

1. Программная система для обработки изображений, включающая:

1. Инструменты поиска текстур методом моментов

2. Редактор текстурного классификатора

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

4. Редактор коллекций лиц

5. База данных лиц

2. Утилита извлечения подписей к фотографиям

3. Программная система для обработки текстовых коллекций, включающая

1. Инструменты обработки коллекции подписей

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

3. Инструменты анализа текстовых коллекций

4. Инструмент формирования полнотекстового индекса

5. Редакторы тематических словарей, морфологического словаря и полнотекстового индекса

4. Программная система для тестирования методов обработки изображений, включающая

1. Метод моментов (обработка, сегментация, анализ параметров)

2. Метод LBP

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

Заключение

Основными результатами диссертационного исследования являются:

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

2. Разработан метод извлечения текстовой информации, содержащей ошибки, из коллекции изображений низкого качества.

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

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

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

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

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

Публикации по тебе диссертации

1. Талбонен А. Н., Рогов А. А. Анализ машинописных подписей к фотографиям в цифровом историческом альбоме // Ученые записки Петрозаводского государственного университета. Серия «Естественные и технические науки». 2012. № 2 (123). С. 109-113.

2. Талбонен А. Н., Рогов А. А. Модели и методы поиска людей на фотографиях из исторического альбома // Ученые записки Петрозаводского государственного университета. Серия «Естественные и технические пауки». 2012. № 6 (127). С. 113-117.

3. Рогов A.A., Скабин A.B., Талбонен А.Н., Штеркель И.А. Некоторые особенности создания автоматизированной системы дешифровки исторических стенограмм // Интернет и современное общество: сборник научных статей. Материалы XIV Всероссийской объединенной конференции «Интернет и современное общество». Санкт-Петербург, 12-14 октября 2011 г. СПб.: Из-во ООО «МультиПрожектСистемСервис». 2011. С. 132-138.

4. Талбонен А. Н. Построение поисковой системы для узкоспециализированной цифровой коллекции // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды XIII Всероссийской научной конференции RCDL'2011 (Воронеж, Россия, 19-22 октября 2011 г.). Воронеж: ИПЦ Ворон. Гос. ун-т. 2011. С. 393-394.

5. Талбонен А. Н. Создание поисковой системы основанной на информации, извлеченной из машинописных подписей к фотографиям в цифровом альбоме // Информационный бюллетень ассоциации «История и компьютер», № 37. Труды международной конференции. Июль 2011 г. Петрозаводск: Изд-во ПетрГУ, 2011. С. 106-109.

6. Талбонен А. Н., Рогов А. А. Анализ машинописных подписей к фотографиям в цифровом альбоме // Электронные библиотеки:

перспективные методы и технологии, электронные коллекции: Труды XII Всероссийской научной конференции ЯСБЬ^ОЮ. Казань: Казан, ун-т, 2010. С. 422-429.

7. Рогов А. А., Талбонен А. А., Варфоломеев А. Г. Автоматизированная система распознавания рукописных исторических документов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды ХП Всероссийской научной конференции ЯСОЬ'гОЮ,- Казань: Казан, ун-т, 2010. С. 469-475.

8. Талбонен А. Н. Особенности создания поискового индекса к фотографиям в цифровом историческом альбоме // Доклады по компьютерным наукам и информационным технологиям. № 1, 2012 г. Доклады всероссийской научно-практической конференции «Анализ Изображений, Сетей и Текстов» (АИСТ 2012). Екатеринбург, 16-18 марта 2012 года. М.: Национальный Открытый Университет «ИНТУИТ» 2012. - 419 е., С. 263 - 278.

Подписано в печать 30.10.2012. Формат 60x84 Чк. Бумага офсетная. 1,0 уч.-изд. л. Тираж 100 экз. Изд. № 285.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Отпечатано в Издательстве ПетрГУ 185910, г. Петрозаводск, пр. Ленина, 33

Введение.

Глава 1. Описание предметной области.

1.1. Особенности исторических фотоальбомов.

1.2. Обзор поисковых систем.

Актуальность темы. Термин «информационный поиск» [19] был впервые введён К. Муром в 1948 г. и употребляется в литературе с 1950 г. С момента появления данного термина до сегодняшних дней системы информационного поиска значительно эволюционировали от простых каталогов научной литературы до глобальных поисковых систем. Поиск информации представляет собой процесс отыскания во множестве цифровых материалов таких, которые удовлетворяют определенным критериям (поисковый запрос). При этом источником информации может быть как текстовое описание (полнотекстовый поиск), так и содержание изображения (поиск изображений).

Значительный вклад в развитие поиска по тексту внесли ученые В. Буш, Дж. Сэлтон, Т. Нельсон и др. Современные поисковые системы позволяют выполнять поиск по содержанию документов, а также по различным атрибутам (метаданным). На сегодняшний день существует множество коммерчески успешных продуктов, а также их бесплатных аналогов («Google» [67], «Bing» [58], «Яндекс» [53] и др.).

Поиск по изображениям осуществляется на основе их аннотирования, который осуществляется двумя способами. Первый способ аннотирования, осуществляемый создателем коллекции, состоит в приписывании текстовых меток (тэгов) к изображениям (фотоколлекции «Picasa» [91], «Flickr» [103], «Яндекс.Фотки» [55] и др). Второй способ реализуется на основании автоматического поиска объектов на изображениях и тесно связан с распознаванием образов. Большой вклад в развитие теории распознавания образов внесли ученые В. Н. Вапник, Ю. И. Журавлев, В. М. Глушков, А. JI. Горелик, Ф. Розенблатт, Б. Уидроу, JL Рабинер и др.

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

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

Степень разработанности темы исследования. Существующие поисковые системы («Google Images» [14], «Яндекс.Картинки» [54] и др.) позволяют выполнять поиск в электронных графических коллекциях первого типа. Ограничения, накладываемые на изображения коллекций второго типа, не позволяют использовать существующие алгоритмы для организации поиска.

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

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

Для достижения цели были поставлены следующие задачи:

1. Разработка алгоритма извлечения текстовой информации из коллекции изображений «низкого» качества.

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

3. Анализ существующих систем поиска по изображениям и методов аннотирования изображений

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

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

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

7. Компьютерная реализация вышеперечисленных алгоритмов и создание комплекса программ для построения поисковой системы.

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

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

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

2. Метод извлечения текстовой информации, содержащей ошибки, из коллекции изображений низкого качества.

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

4. Программный комплекс для построения поисковой системы для коллекции исторических фотографий

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

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

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

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

1. XII Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (ЯСШЛОЮ) (Казань, 2010).

2. XIII Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (КСБЬ'2011) (Воронеж, 2011).

3. Всероссийская научно-практическая конференция «Анализ Изображений, Сетей и Текстов» (АИСТ 2012) (Екатеринбург, 2012).

По теме диссертации опубликовано 8 научных работ, 2 из них входят в список ВАК.

Разработанное программное обеспечение было апробировано на коллекции фотографий строительства Беломорско-Балтийского канала, а построенная по ней поисковая система внедрена в Национальный музей республики Карелия. Данный программный комплекс был зарегистрирован в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 18562 от 08.10.2012 г.

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

1. Гасфилд, Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Д. Гасфилд // Пер. с англ. И. В. Романовского. — СПб.: Невский Диалект; БХВ-Петербург. — 2003.654 с.

2. Гонсалес, Р. Цифровая обработка изображений / Р. Гонесалес, Р. Вудс.

3. М.: Техносфера. — 2005. — 1072 с.

4. Горский, Н. Распознавание рукописного текста: От теории к практике / Н. Горский, В. Анисимов, JI. Горская // СПб.: Политехника. — 1997. — 126 С.

5. Государственный музей архитектуры имени А. В. Щусева Электронный ресурс]. — Режим доступа: http://www.muar.ru/ve/leonidov/prosoft/indl.htm.

6. Гудков, В. Ю. Скоростная обработка изображения отпечатка пальца / В. Ю. Гудков, М. В. Боков // Вестник Челябинского государственного университета. Математика, Механика, Информатика. Выпуск 13. — 2011. —№26 (241). —С. 109-120.

7. Десятников, И. Е. Алгоритмы поиска изображений в базах видеоданных Электронный ресурс] / И. Е. Десятников, В. А. Утробин. — Режим доступа: http://www.computeroptics.smr.ru/KO/PDF/K035-3/350317.pdf

8. Каньковски, П. Как работают фильтры размытия Электронный ресурс] / П. Каньковски. — Режим доступа: http://www.computerra.ru/gid/rtfm/graphic/35934/.

9. Картинки Google Электронный ресурс]. — Режим доступа: http://images.google.com/.

10. Компонент Full-Text Search (SQL Server) Электронный ресурс]. — Режим доступа: http://msdn.microsoft.com/ru-ru/library/msl42571.aspx.

11. Кручинин, А. Распознавание образов с использованием OpenCV Электронный ресурс] / А. Кручинин. — Режим доступа: http://recog.ru/library/opencv/opencvkruchinin.pdf.

12. Кулешов, С. В. Методы сегментации ОСЯ-систем в задачах автоматической обработки архивных документов / С. В. Кулешов, С. В. Смирнов // Труды СПИИРАН. — 2011.

13. Лифшиц, Ю. Методы распознавания лиц Электронный ресурс] / Ю. Лифшиц. — Режим доступа: http://yury.name/modern/08modernnote.pdf.

14. Маннинг, К. Д. Введение в информационный поиск / К. Д. Манниг, П. Рагхаван, X. Шютце // М.: Вильяме. — 2011. — 528 с.

15. Маслий, Р. В. Использование локальных бинарных шаблонов для распознавания лиц на полутоновых изображениях Электронный ресурс] / Р. В. Маслий. — Режим доступа: http://www.nbuv.gov.ua/e-journals/vntu/2008-4/2008-4ш.flles/ru/08rvmgsiru.pdf.

16. Машинописные шрифты. Скачать машинописные шрифты бесплатно — Fontov.net Электронный ресурс]. — Режим доступа: http://www.fontov.net/мaшинoпиcныe-шpифты.

17. Мицель, А. А. Непараметрический алгоритм текстурного анализа аэрокосмических снимков / А. А. Мицель, Н. В. Колодникова, К. Т. Протасов // Известия Томского политехнического университета, Т. 308, № 1.-2005.

18. Модули машинной морфологии. Морфологический анализ. Машинная морфология в поисковых системах Электронный ресурс]. — Режим доступа: http://asknet.ru/Technology/morpho.htm.

19. Нигма интеллектуальная поисковая система Электронный ресурс]. — Режим доступа: http://www.nigma.ru/.

20. О программе mystem — Компания Яндекс Электронный ресурс]. — Режим доступа: http://company.yandex.ru/technology/mystem/.

21. Павлидис, Т. Алгоритмы машинной графики и обработки изображений / Т. Павлидис. — М.: Радио и связь. — 1986.

22. Паначев, М. А. Об одной задаче семантической классификации цифровых изображений / М. А. Паначев, Б. В. Парфенков // Доклады по компьютерным наукам и информационным технологиям. № 1, 2012 г.

23. Доклады всероссийской научно-практической конференции «Анализ Изображений, Сетей и Текстов» (АИСТ 2012). Екатеринбург, 16-18 марта 2012 года. М.: Национальный Открытый Университет «ИНТУИТ». — 2012. — 419 с. — С 352-361.

24. Петрук, В. И. Применение локальных бинарных шаблонов к решению задачи распознавания лиц / В. И. Петрук, А. В. Самородов, И. Н. Спиридонов // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. Спец. вып. Биометрические технологии. — 2011. — С. 58-63.

25. Программа для распознавания текста ABBYY FineReader Электронный ресурс]. — Режим доступа: http://www.abbyy.ru/finereader/.

26. Программы анализа и лингвистической обработки текстов Электронный ресурс]. — Режим доступа: http://www.rvb.ru/sofl/catalogue/cO 1 .html.

27. Прэтт, У. К. Цифровая обработка изображений: В. 2 т. / У. К. Претт // Пер. с анг.; Под ред. Д. С. Лебедева. — М.: Мир. — 1982. — Т.2.

28. Рамблер Электронный ресурс]. — Режим доступа: http://www.rambler.ru/.

29. Рогов, А. А. Информационно-поисковая система петроглифов Карелии / А. А. Рогов, К. А. Рогова, К. Н. Спиридонов, М. Ю. Быстров // Вестник компьютерных и информационных технологий. —2008. —№6. —с. 6-12.

30. Форсайт, Д. Компьютерное зрение. Современный подход.: Пер. с. англ. / Д. Форсайт, Ж. Понт // М.: Издательский дом «Вильяме». — 2004. — 928 е.: ил. — Парал. тит. Англ.

31. Харалик, Р. М. Статистический и структурный подходы к описанию текстур / Р. М. Харалик // ТИИЭР. — 1979. — Т. 67. — № 5. — С. 98-121.

32. Цисарж, В.В. Математические методы компьютерной графики / В. В. Цисарж, Р. И. Марусик, К.:Факт. — 2004. — 466 с.

33. Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции Электронный ресурс]. — Режим доступа: http://www.rcdl.ru/.

34. Электронные музейные коллекции Электронный ресурс]. — Режим доступа: http://www.museum.ru/W370/.

35. Яндекс Электронный ресурс]. — Режим доступа: http://www.yandex.ru/.

36. Яндекс.Картинки Электронный ресурс]. — Режим доступа: http://images.yandex.ru/.

37. Яндекс.Фотки Электронный ресурс]. — Режим доступа: http://fotki.yandex.ru/.

38. Ahonen, Т. Face Recognition with Local Binary Patterns Электронный ресурс] / Т. Ahonen, A. Hadid, M. Pietikainen. — Режим доступа: http://masters.donntu.edu.ua/2011/frt/dyrul/library/article8.pdf.

39. Apache Lucene Welcome to Apache Lucene Электронный ресурс]. — Режим доступа: http://lucene.apache.org/.

40. Bing Электронный ресурс]. — Режим доступа: http://www.bing.com/.

41. Bing Images Search the web for pictures, photos & images Электронный ресурс]. — Режим доступа: http://www.bing.com/images.

42. Brodatz, P. Textures: a Photographic Album for Artists and Designers / P. Brodatz // New York: Dover Publications. — 1966.

43. Cascade Classification — opencv v2.1 documentation Электронный ресурс]. — Режим доступа: http://opencv.willowgarage.com/documentation/cpp/cascadeclassification.ht ml#cv-cascadeclassifier-detectmultiscale.

44. Cross, G. С. Markov random field texture models / G. C. Cross, A. K. Jain // IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5. — 1983. —pp. 25-39.

45. CuneiForm — бесплатная программа для распознавания текста документов Электронный ресурс]. — Режим доступа: http://cognitiveforms.ru/products/cuneiform/.-t

46. Degtyarev, N. Comparative Testing of Face Detection Algorithms Электронный ресурс] / N. Degtyarev, О. Seredin. — Режим доступа: http://lda.tsu.tula.ru/papers/degtyarev-2010-icisp-ctfd.pdf.

47. Edge Detection Электронный ресурс]. — Режим доступа: http://www.cse.unr.edu/~bebis/CS79 lE/Notes/EdgeDetection.pdf.

48. Flusser, J. Moment Invariants in Image Analysis Электронный ресурс]. — Режим доступа:http://citeseerx.ist.psu.edu/viewdoc/download?doi=l 0.1.1.187.8110&rep=rep l&type=pdf.

49. Google Электронный ресурс]. — Режим доступа: https://www.google.ru/.

50. Guo, Z., Rotation invariant texture classification using LBP variance (LBPV) with global matching Электронный ресурс] / Z. Guo, L. Zhang, D. Zhang. — Режим доступа: http://www4.comp.polyu.edu.hk/~cslzhang/paper/PR10MarLBPV.pdf.

51. Haralick, R. M. Statistical and Structural approaches to texture / R. M. Haralick // Proceedings of the IEEE. — 1979. — pp. 786-804.

52. Haralick, R. M. Textural Features for Image Classification / R. M. Haralick, K. Shanmugam, I. Distein // IEEE Transactions on systems, man and cybernetics.— 1973. —V. SMC-3. — № 6. — pp. 610-621.

53. Howarth, N. Abstract Syntax Tree Degisn Электронный ресурс] / N. Howarth. — Режим доступа:http://www.ansa.co.Uk/ANSATech/95/Primary/l 55101 .pdf.

54. Hu, M. К. Visual pattern recognition by moment invariants / M. К. Ни // IRE Trans, on Information Theory, IT-8. — pp. 179-187. — 1962.

55. Image Filtering — opencv v2.1 documentation Электронный ресурс]. — Режим доступа:http://opencv.willowgarage.com/documentation/cpp/imagefiltering.html#cv-filter2d).

56. Jain, А. К. Algorithms for Clustering Data / A. K. Jain, R. C. Dubes // Prentice Hall, Englewood Cliffs, New Jersey. — 1988.

57. JSON Электронный ресурс]. — Режим доступа: http://json.org/.

58. Lexxe Search Engine Home page Электронный ресурс]. — Режим доступа: http://www.lexxe.com/.

59. Liao, S. Image Analysis by Moments Электронный ресурс]. — Режим доступа: http://zernike.uwinnipeg.ca/~sliao/pdf/thesis.pdf.

60. Liu, X. Texture classification using spectral histograms Электронный ресурс] / X. Liu, D. Wang. — Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/download?doi=l 0.1.1.78.3 024&rep=rep 1 &type=pdf

61. Maenpaa, T. The local binary pattern approach to texture analysis -extensions and applications Электронный ресурс] / Т. Maenpaa . — Режим доступа:http://herkules.oulu.fi/isbn9514270762/isbn9514270762.pdf.

62. Mirmehdi, M. Handbook of texture analysis / M. Mirmehdi, X. Xie, J. S. Suri // London: Imperial College Press. — 2008. — 413 P.

63. My Excite Электронный ресурс]. — Режим доступа: http://www.excite.com/.

64. Ojala, Т. A Comparative Study of Texture Measures with Classification Based on Feature Distributions / T. Ojala, M. Pietikainen, D. Harwood // Pattern Recognition. — 1996. — T. 29. — № 1. — C. 51-59.

65. Ojala, Т. Multiresolution Gray-Scale and Rotation Invariant Texture Classification with Local Binary Patterns Электронный ресурс] / Т. Ojala, M. Pietikainen, Т. Maenpaa. — Режим доступа: http://www.outex.oulu.fi/publications/pami02opm.pdf.

66. Ojala, Т. Nonparametric Texture Analysis with complementary spatial operators Электронный ресурс] / Т. Ojala, M. Pietikainen. — Режим доступа: http://www.outex.oulu.fi/publications/texture99280599.pdf.

67. Ojala, Т. Unsupervised texture segmentation using feature distributions Электронный ресурс] / Т. Ojala, M. Pietikainen. — Режим доступа: http://www.ee.oulu.fi/research/imag/texture/publications/PR323.fm.pdf.

68. Picasa Электронный ресурс]. — Режим доступа: http://picasa.google.com/.

69. Pictures Электронный ресурс]. — Режим доступа: http://www.picsearch.com/.

70. Scharr, Н. Optimal Operators in Digital Image Processing Электронный ресурс] / H. Scharr. — Режим доступа: http://archiv.ub.uni-heidelberg.de/volltextserver/volltexte/2000/962/.

71. Tamura, Н. Textural Features Corresponding to Visual Perception / H. Tamura, S. Mori, T. Yamawaki // IEEE Transaction on Systems, Man and Cybernetics, Vol. SMC-8, No. 6. — 1978. — pp. 460-472.

72. Tesseract-ocr An OCR Engine that was developed at HP Labs between 1985 and 1995. and now at Google. - Google Project Hosting Электронный ресурс]. — Режим доступа: http://c0de.g00gle.c0m/p/tesseract-0cr/.

73. TinEye Reverse Image Search Электронный ресурс]. — Режим доступа: http://www.tineye.com/.

74. Tuceryan, М. Moment Based Texture Segmentation / M. Tuceryan. — Режим доступа: http://cs.iupui.edu/~tuceryan/pdf-repository/Tuceryan1992.pdf.

75. Tushabe, F. Content-Based Image Retrieval Using Combined 2D Attribute Pattern Spectra Электронный ресурс] / F. Tushabe, M. H. F. Wilkinson. — Режим доступа: http://iwi.eldoc.ub.rug.nl/FILES/root/2008/LNCSTushabe/2008LNCSTushab e.pdf.

76. Understanding image-interpolation techniques Электронный ресурс]. — Режим доступа: http://www.vision-systems.com/articles/print/volume-12/issue-10/departments/wilsons-websites/understanding-image-interpolation-techniques.html

77. Viola, P. Robust Real-time Object Detection Электронный ресурс] / P. Viola, M. Jones. — Режим доступа: http://research.microsoft.com/en-us/um/people/viola/Pubs/Detect/violaJonesIJCV.pdf.

78. Wagner, R. A. The String-to-string correction problem Электронный ресурс] / R. A. Wagner, M. J. Fischer. — Режим доступа: http://www.daimi.au.dk/~cstorm/courses/AiBSe08/papers/WagnerFisherEd itDist.pdf.

79. Wechsler, H. Reliable face recognition methods: system design, implementation and evaluation Электронный ресурс] / H. Wechsler. — Режим доступа: http://books.google.ru/books?id=r-efsB92dvEC&printsec=frontcover&hl=ru&source=gbsatb#v=onepage&q&f =false.

80. Welcome to Flickr Photo Sharing Электронный ресурс]. — Режим доступа: http://www.flickr.com/.

81. Wikianswers Find and edit the best answers. Add your questions here Электронный ресурс]. — Режим доступа: http://answers.wikia.com/wiki/Wikianswers.

82. Yahoo! Russia Электронный ресурс]. — Режим доступа: http://ru.yahoo.com/?p=us.