Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Талбонен Андрей Николаевич
МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ПОИСКА В ЭЛЕКТРОННЫХ КОЛЛЕКЦИЯХ ИСТОРИЧЕСКИХ ФОТОГРАФИЙ
Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ
Автореферат диссертации на соискание ученой степени кандидата технических наук
Петрозаводск 2012
Работа выполнена на кафедре теории вероятностей и анализа данных ФГБОУ ВПО Петрозаводский государственный университет Научный доктор технических наук, профессор руководитель: Рогов Александр Александрович Официальные Жабко Алексей Петрович, доктор оппоненты: физико-математических наук, профессор, заведующий кафедрой теории управления ФГБОУ ВПО Санкт-Петербургский государственный университет Вдовицын Владимир Трофимович, кандидат физико-математических наук, доцент, руководитель лаборатории информационных компьютерных технологий ФГБУН Института прикладных математических исследований Карельского научного центра РАН Ведущая ФГБУН Санкт-Петербургский институт организация: информатики и автоматизации РАН
Защита состоится л20 декабря 2012 г. в 10:00 часов на заседании диссертационного совета Д 212.190.03 на базе ФГБОУ ВПО Петрозаводский государственный университет по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.
С диссертацией можно ознакомиться в библиотеке Петрозаводского государственного университета.
Автореферат разослан л09 ноября 2012 г.
Ученый секретарь диссертационного совета Р. В. Воронов
Общая характеристика работы
Актуальность темы исследования.
Термин линформационный поиск был впервые введён К. Муром в конце 40-х годов. С момента появления данного термина до сегодняшних дней системы информационного поиска значительно эволюционировали от простых каталогов научной литературы до глобальных поисковых систем.
Поиск информации представляет собой процесс отыскания во множестве цифровых материалов таких, которые удовлетворяют определенным критериям (поисковый запрос). При этом источниками информации могут служить как текстовые материалы (полнотекстовый поиск), так и изображения (поиск изображений).
Значительный вклад в развитие поиска по тексту внесли ученые В.
Буш, Дж. Сэлтон, Т. Нельсон и др. Современные поисковые системы позволяют выполнять поиск по содержанию документов, а также по различным атрибутам (метаданным). На сегодняшний день существует множество коммерчески успешных продуктов, а также их бесплатных аналогов (лGoogle, Bing, Яндекс и др.).
Поиск по изображениям осуществляется на основе их аннотирования, который осуществляется двумя способами. Первый способ аннотирования, осуществляемый создателем коллекции, состоит в приписывании текстовых меток (тэгов) к изображениям (фотоколлекции Picasa, Flickr, Яндекс.Фотки и др). Второй способ реализуется на основании автоматического поиска объектов на изображениях и тесно связан с другой областью вычислений - распознаванием образов. Большой вклад в развитие теории распознавания образов внесли ученые В. Н. Вапник, В. М. Глушков, А. Л. Горелик, Ф. Розенблатт, Б. Уидроу, Л. Рабинер и др.
В настоящее время активно создаются электронные графические коллекции (базы данных для хранения изображений). Их можно разбить на две группы. Первая содержит современные цифровые фотографии, вторая - изображения, имеющие историческую ценность, как правило, это оцифрованные исторические материалы. Сканированные фотографии в исторических коллекциях могут содержать текстовое описание, изображения различных культурных артефактов, зданий, людей и пр. Современные средства оцифровки книг позволяют получать качественные изображения с разрешением свыше 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 г.
Структура и объем диссертации. Диссертация состоит из введения, глав, заключения и библиографического списка использованной литературы (105 наименований), имеет объем 112 страниц машинописного текста, включая 7 страниц приложений, содержит 37 рисунков и 12 таблиц.
Содержание работы Во введении содержится обоснование актуальности темы диссертации, формулируется цель диссертации, представлены основные результаты, научная новизна, практическая значимость работы, а также описание структуры диссертации.
В первой главе рассматриваются особенности исторических фотоальбомов, содержатся общие сведения о существующих системах поиска, в том числе, о системах поиска по изображениям, рассматривается структура типовой поисковой системы.
Исторические коллекции изначально представляют собой альбомы в бумажном виде, изображения в которых как в целом, так и по частям, имеют историческую ценность. Среди частей подобных альбомов можно выделить текстовое описание, различные культурные артефакты и элементы изображения такие, как люди, здания и др. Подобные коллекции хранятся в музеях и архивах, и оригиналы доступны для обозрения только посетителям, или только сотрудникам музея. Оцифровка изображений позволяет обойти это ограничение и открыть доступ к историческим документам широкому кругу лиц.
Данное диссертационное исследование посвящено анализу поисковых процессов, выполняющихся над цифровыми изображениями исторических коллекций. В частности в качестве возможных исходных данных рассматриваются коллекции, обладающие следующими свойствами:
1. Низкое разрешение оцифрованных изображений, менее 100 точек на дюйм.
2. Общая размытость, обусловленная как недостаточной четкостью оцифровки, так и форматом хранения цифровых изображений, предполагающим потерю информации, например, JPEG 3. Наличие шумовых эффектов в виде случайных пикселей (эффект соль и перец) и других.
4. Коллекции состоят из черно-белых изображений 5. Возраст оригинальных материалов затрудняет проведение повторной оцифровки современными средствами.
6. Возможно наличие текстового описания на оригинальных изображениях, соответствующего участку цифрового изображения.
7. Наличие объектов (лица, здания, сооружения), а также фрагментов объектов (текстуры, контуры) на изображениях.
Для данного диссертационного исследования интерес представляют поисковые машины, способные работать с изображениями в качестве исходных ресурсов. Подобные машины называются CBIR engine (Contentbased image retrieval engine, машина поиска изображений по содержанию).
Среди существующих поисковых машин, обладающих данным качеством, можно выделить TinEye, Picsearch, Google Images, Яндекс Картинки и другие.
К сожалению, существующие поисковые системы не подходят для выполнения поиска по содержанию по изображениям, обладающими описанными свойствами. Исследование существующих систем поиска по коллекциям цифровых изображений показало, что для достижения поставленной цели необходимо разрабатывать отдельную программную систему. Задачи, поставленные в данном диссертационном исследовании, являются следствием данного вывода.
Во второй главе исследуется процесс извлечения текста из изображений, рассматриваются существующие средства распознавания текста, описываются предлагаемые метод извлечения текста из изображений низкого качества и метод обработки текстовой коллекции, содержащей ошибки.
На данный момент существуют множество систем распознавания текста. Среди систем, поддерживающих русский язык, можно выделить ABBYY FineReader, CuneiForm, Google Tesseract и другие. К сожалению, низкое качество исследуемых изображений, нестандартный шрифт не позволяют использовать только существующие средства. Для повышения качества распознавания требуются дополнительные операции.
В диссертационном исследовании предлагается не обрабатывать изображения целиком, а выполнять распознавание только области, содержащей текст (пример представлен на рисунке 1). Для выделения областей, содержащих текст, можно использовать простые эвристические алгоритмы.
Рисунок 1. Область изображения, содержащая текст и подлежащая распознаванию.
Для извлечения текста из выделенных областей также недостаточно использовать только существующие системы оптического распознавания символов. В диссертационном исследовании предлагается использовать предварительно методы обработки изображений, повышающих качество.
Существует множество подобных методов, однако в данном исследовании рассматривались только 12 методов. Среди них можно выделить:
1. Эвристический метод порогового отсечения без параметров 2. Методы пространственной фильтрации, применяющие лапласиан.
3. Методы выделения границ 4. Методы сглаживания.
Поскольку каждый метод обработки изображений дает свой результат, что приводит к различным результатам распознавания, некоторые изображения могут быть распознаны лучше при помощи одного метода обработки, другие - при помощи других. А если предполагать, что текст после распознавания должен в целом сохранять свою цепочку синтагму, можно говорить о сравнении качества распознавания отдельных элементов текстовых файлов (текстовых элементов). В диссертационном исследовании предлагается метод формирования текстовой коллекции, основанный на комбинировании элементов текстовых файлов, распознанных после обработки изображений различными методами.
Обозначим через текущее изображение, тогда ( = 1,, где - число методов) - методы обработки изображений, а = ( ) - результаты обработки изображения соответствующими методами (альтернативные изображения). Применив распознавание с помощью какой-либо системы OCR, получим набор текстовых файлов (альтернативные текстовые файлы). Пусть нам известна общая цепочка синтагм текста исходного изображения. Тогда в целом та же цепочка должна сохраниться после распознавания. Применив соответствующий синтаксический анализ к каждому из полученных альтернативных текстовых файлов, получим наборы альтернативных текстовых элементов. Таким образом, можно рассматривать текстовые файлы как множества текстовых элементов размером, упорядоченных в строгом соответствии со своим местом (индексом) в цепочке синтагме. Т.е. = { | = 1, }.
Будем оценивать каждый элемент. Обозначим через оценки альтернативных текстовых элементов.
Оценки текстового элемента рассчитываются на основе веса каждого слова, входящего в данный элемент. Вес каждого слова зависит от его схожести с одним или несколькими словами из словаря, которые будем называть словами-кандидатами. Рассчитывается вес по следующей формуле:
=, где - длина слова, - расстояние Левенштейна до слова кандидата. В случае, когда > вес считается равным 0. Вес слова, найденного в словаре, будет равен 1.
Пусть - общий вес (сумма весов слов), а - количество слов элемента. Тогда оценка элемента будет рассчитываться следующим образом: = , , > 0 1 -, 2 где =, = и 0, = 0, > 2 =.
С учетом свойств множителей и получаем, что = [0; 1].
В результате сравнения определим лоптимальные элементы =, причем = argmax ( ), где = 1, и = 1,. Новый текстовый файл может быть получен в результате синтеза: = { }. Пример сравнения альтернативных текстовых элементов приведен в таблице 1.
С учетом оценок текстовых элементов будем оценивать текстовые файлы = { } следующим образом: =. Т.к. [0; 1], то [0; 1].
Таблица Пример сравнения альтернативных текстовых элементов одного файла Имя метода Оценки элементов ( ) Основной текст Дата Номер Cut 0,80 1,00 0,EALaplas 0,78 0,85 0,AELaplas 0,85 0,75 0,EAELaplas 0,82 0,90 0,В з 2.8 описываются теоретические основы анализа текстовой коллекции, рассматриваются существующие морфологические анализаторы.
В качестве основного морфологического анализатора в данном диссертационном исследовании используется программа Mystem от компании Яндекс, поддерживающая несколько тематических атрибутов.
В з 2.9 описывается предлагаемый метод анализа текстовой коллекции, содержащей ошибки. Основная цель данного метода - повышение качества текстовой коллекции, которое выражается общим весом всех файлов текстовой коллекции. Кроме того, в процессе анализа, формируются различные тематические словари.
В третьей главе рассматриваются существующие алгоритмы обнаружения и распознавания лиц, предлагается метод аннотирования изображений за счет наличия лиц людей при отсутствии базы данных лиц, описываются особенности задачи аннотирования для изображений лиц небольших размеров. В данной главе также предлагаются методы улучшения качества обнаружения лиц с помощью локальных бинарных шаблонов.
В данном исследовании предлагается следующий метод аннотирования изображений при отсутствии базы данных, состоящей из изображений лиц и соответствующих текстовых меток (далее - база данных лиц):
1. Извлечение объектов (изображения лиц).
2. Расчет попарных расстояний между объектами. С целью экономии памяти количество сохраняемых расстояний можно ограничить, например, 10-ю записями.
3. Аннотирование. Данный процесс является итеративным и может выполняться до тех пор, пока все найденные объекты не будут помечены. Итерация включает в себя следующее:
a. Эксперт выбирает очередной непомеченный объект, после чего система предлагает выбрать один из ближайших объектов в порядке возрастания расстояния до текущего объекта.
b. Если эксперт обнаруживает сходство между объектами, система создает связь между ними.
Если текущий объект и связанные с ним объекты не имеют метки, эксперт помечает данные объекты: в качестве метки может выступать ФИО.
После этого система присваивает введенную метку всем связанным объектам и далее они считаются помеченными.
Современные алгоритмы обнаружения лиц хорошо работают для объектов с размерами около 100 пикселей и выше. В таких случаях полнота и точность приближаются к 100%. Однако при оптимальных параметрах для больших объектов данные методы демонстрируют низкую полноту обнаружения небольших объектов, размером не больше 40 пикселей.
Исследование одной из исторических коллекций, коллекции строительства Беломорско-Балтийского канала, показало высокий процент содержаний объектов небольшого размера. На рисунке 2 представлено распределение размеров объектов-лиц данной коллекции. Доля объектов размером меньше 40 пикселей составляет для данной коллекции 60%. Еще 20% занимают объекты размеров от 40 до 50 пикселей.
Рисунок 2. Распределение размеров коллекции строительства Беломорско-Балтийского канала Подбор параметров алгоритма обнаружения лиц таким образом, чтобы он находил объекты небольшого размера, значительно повысит полноту результатов поиска. Однако, вместе с тем, это повысит вероятность обнаружения ложных объектов, поскольку алгоритм будет настроен на обнаружение небольших деталей на изображении, которыми могут быть не только глаза, рот и другие части лица, но также любые небольшие объекты, заметно отличающиеся по цвету от окружающих пикселей, или случайные элементы, являющиеся следствием низкого качества изображений.
Следовательно, будет снижаться точность. Будем называть результат обнаружения с параметрами, дающими наибольшую полноту для данного алгоритма, полной коллекцией. Аналогично будет называть результаты обнаружения с наибольшей точностью, точной коллекцией.
В данной работе для обнаружения лиц используется алгоритм ВиолыДжонса, один из наиболее популярных алгоритмов на данный момент, обладающий гибкостью, достаточной для манипулирования полнотой и точностью результатов с помощью параметров.
Для устранения подобной проблемы в исследовании предлагается метод улучшения качества обнаружения лиц (полноты и точности) с помощью сортировки полной коллекции одним из алгоритмов распознавания лиц на основе обучающей выборки. Суть данного метода состоит в том, чтобы сравнивать каждый найденный объект из полной коллекции с некоторым множеством изображений лиц и некоторым множеством ложных объектов. Два этих множества будут составлять обучающую выборку.
Алгоритмы распознавания лиц позволяют сравнивать между собой объекты-лица путем вычисления для каждого из них вектора признаков.
Сравнение происходит по расстоянию между данными векторами. Бинарная классификация по расстоянию выглядит предпочтительнее по сравнению с пороговым сравнением, поскольку использование пороговых значений может оказывать негативное влияние на результат сравнения. Суть бинарной классификации заключается в вычислении минимального расстояния от текущего объекта до объектов обоих множеств обучающей выборки. Если расстояние до множества объектов-лиц будет меньше расстояния до множества ложных объектов, текущий объект будет считаться лицом, иначе - ложным объектом.
В данной работе для распознавания лиц используются модификации алгоритма локальных бинарных шаблонов (Local Binary Pattern, LBP, ЛБШ).
Данный алгоритм на данный момент имеет множество различных модификаций, позволяющих с высокой точностью распознавать лица; в некоторых случаях точность может доходить до 95%.
Алгоритм LBP представляет собой фильтр, который вычисляет для каждого пикселя изображения специальный код, вычисляемый в окрестности данного пикселя. На рисунке 3 представлен пример вычисления кода для оригинальной версии алгоритма. Текущий пиксель (в центре окрестности) со значением 3 сравнивается со значениями остальных точек окрестности. В зависимости от значения каждой нецентральной точке ставится в соответствие логическое значение 0 или 1 (значение 1 бита). Образуемая при прохождении точек окрестности по кругу последовательность битов преобразуется в соответствующее десятичное число, называемое кодом LBP.
Порядок обхода не важен, однако должен быть постоянен при использовании этого алгоритма для других изображений.
Рисунок 3. Пример вычисления кода для простого LBP.
Современные модификации предполагают вычисление кодов LBP в окрестности определенного радиуса ( ) и с определенным числом точек ( ), равностоящих друг от друга на соответствующей окружности (см.
рисунок 4). В этом случае значение в точке окрестности интерполируется.
(а) (б) (в) Рисунок 4. Примеры различных окрестностей для вычисления кодов LBP: (а) - радиус 1, число точек 8; (б) - радиус 2.5, число точек 12; (в) - радиус 4, число точек 16.
Постоянное число точек окрестности задает постоянный размер соответствующей битовой последовательности, и, как следствие, фиксированное число возможных кодов LBP. Некоторые модификации предполагают одностороннюю замену кодов исходного диапазона на коды более узкого диапазона, позволяя сократить их число и время вычисления расстояний между изображениями.
В качестве вектора признаков в алгоритме LBP вычисляются распределения кодов LBP. Поскольку число кодов для одной модификации всегда конечно и постоянно, соответствующие гистограммы имеют одинаковый размер. Для распознавания лиц часто применяют матрицу весов (пример на рисунке 5), т.к. некоторые участки изображения лица (глаза, рот) имеют большее значение, чем другие. В этом случае изображение разбивается на соответствующие части, вычисляется гистограмма каждой области, после чего происходит их конкатенация (см. рисунок 6).
Рисунок 5. Матрица весов, применяемая для распознавания лиц.
Рисунок 6. Схема вычисления общей гистограммы объекта-лица с помощью матрицы весов.
Для выявления модификации, работающей лучше остальных для исследуемых коллекций, предлагается следующий метод. Важную роль в этом методе выполняют обучающие выборки. Для повышения качества результатов обнаружения необходимо дополнять множество ложных объектов часто встречающимися объектами.
Для оценки полноты и точности необходимо произвести экспертную оценку тестовой выборки (экспертная коллекция). В экспериментах использовалась выборка в 1070 изображений. Процесс оценивания был упрощен: вместо выделения всех лиц, на изображениях автоматически выделялись объекты полной коллекции, отсортированной вручную, после чего эксперту достаточно было отметить на изображении недостающие лица.
Ручная сортировка осуществлялась быстрым методом, позволяющим сортировать 100 объектов за 1 минуту.
Кроме очевидных лиц и ложных объектов, найденных в полной коллекции, были определены дополнительные правила оценивания. К ложным объектам относились лица, слабо различимые (не видно глаз или рта), и лица людей, повернувшихся к камере на угол больше 90 градусов. К лицам относились различные изображения лиц: портреты, рисунки, бюсты.
В процессе классификации объекты преобразовывались к размеру 64 64. Эксперименты проводились и использованием нескольких фильтров с различными параметрами расчета гистограммы и с различными обучающими множествами. Для вычисления векторов признаков использовались фильтры, и,. В одних случаях применялась матрица весов (рисунок 5), в других случаях вектор признаков сжимался до размера 200. В качестве множества лиц использовался набор из изображений лиц. Кроме того, было задано 2 множества ложных объектов (и 26 изображений, и соответственно).
Результатом каждого эксперимента являлась отдельная коллекция объектов. Полученные коллекции оценивались полнотой и точностью, для расчета которых объекты коллекций сопоставлялись с объектами экспертной коллекции. Результаты экспериментов, позволяющие сравнить качество полученных коллекции с соответствующими параметрами полной и точной коллекций, представлены в таблице 2 и на рисунке 7. Описание каждого эксперимента содержит параметры фильтра LBP, использованные методы расчета гистограмм, а также множество ложных объектов.
Таблица Результаты экспериментов по повышению точности и полноты Название Описание Лица Ошибки Полнота Точность F-мера ЭК Экспертная коллекция 793 0 1,000 1,000 1,0ПК Полная коллекция 540 973 0,681 0,357 0,4ТК Точная коллекция 439 289 0,554 0,603 0,5LBP_24_1 529 484 0,667 0,522 0,5 2, 24,LBP_24_2 492 294 0,620 0,626 0,6 2, 24,LBP_24_W_Q_1 522 364 0,658 0,589 0,6 2, веса, 24,сжатие, LBP_24_W_Q_2 499 319 0,629 0,610 0,6 2, веса, 24,сжатие, LBP_24_W_1 506 292 0,638 0,634 0,6 2, веса, 24,LBP_24_W_2 483 226 0,609 0,681 0,6 2, веса, 24,LBP_16_1 532 492 0,671 0,520 0,5 2, 16,LBP_16_2 512 332 0,646 0,607 0,6 2, 16,LBP_16_W_Q_1 520 370 0,656 0,584 0,6 2, веса, 16,сжатие, LBP_16_W_Q_2 499 306 0,629 0,620 0,6 2, веса, 16,сжатие, LBP_16_W_1 510 305 0,643 0,626 0,6 2, веса, 16,LBP_16_W_2 488 230 0,615 0,680 0,6 2, веса, 16,Рисунок 7. Диаграмма сравнения полноты и точности обнаружения лиц.
Проведенные эксперименты показали, что гистограммы, полученные с помощью фильтров, и,, матрицы весов и расширенной обучающей выборки обладают наилучшей селективной способностью с точки зрения F-меры. Кроме того, в большинстве случаев, расширение обучающей выборки позволило сократить количество ошибок и, следовательно, точность и F-меру отсортированной коллекции. Однако даже использованные в экспериментах небольшие выборки показали более высокие показатели по сравнению с простым алгоритмом Виолы-Джонса.
Предложенный метод аннотирования предполагает расчет расстояний между объектами с помощью одного из алгоритмов распознавания. Алгоритм локальных бинарных шаблонов позволяет распознавать объекты небольшого размера, поэтому он был выбран в данной работе для расчета расстояний между объектами. Основной задачей при этом является выбор одной из модификаций, позволяющей наилучшим образом выявлять похожие объекты.
Для определения лучшей модификации LBP разработан следующий метод. Данный метод предполагает поиск совпадений среди тестового множества объектов. Обозначим данный набор как. Совпадением будем считать пару объектов, являющихся изображениями лица одного и того же человека. Кроме того, тестовое множество включает несколько ложных объектов в качестве контрольной группы. Метод заключается в поиске для каждого объекта ближайшего к нему объекта. В результате формируются пары объектов. Каждое совпадение (релевантная пара объектов) добавляется в соответствующее множество упорядоченных пар. Обозначим за множество релевантных пар объектов-лиц, а за - множество пар ложных объектов. В зависимости от наличия совпадений рассчитывается точность для каждого использованной модификации LBP.
Для анализа работы различных фильтров LBP используется следующий алгоритм:
1. Для каждого объекта находится ближайший к нему объект . Т.е. = argmin { (, )| / }.
2. Полученное таким образом множество пар = {<, > | } сопоставляется с известными парами лиц и ложных объектов.
1, <, > 3. Обозначим через , = индикатор 0, иначе распознавания пар.
4. Тогда будем рассчитывать точность следующим образом: = (, ).
| | | | В данной работе в качестве множества использовалась выборка, представленная в таблице 3. При этом, во множестве присутствуют следующие пары лиц, соответствующих одному и тому же человеку: {3, 14}, {4, 13} и {7, 9}. Обозначим данное множество как. Кроме того, очевидна пара ложных объектов, которые должны быть близки друг к другу: {1, 15} ( ). Дополним множества и зеркально отраженными элементами данных множеств.
Таблица Тестовое множество изображений для распознавания лиц 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) В процессе исследования были рассмотрены различные варианты фильтров LBP. В таблице 4 приведены показатели точности использованных фильтров относительно заданного множества.
Таблица Результаты экспериментов по распознаванию лиц Обозначение Точность, 0,, 0,, 0,, 0,, 0,, 0,0,Взвешенный 16,0,Взвешенный 16,0,Взвешенный 16,Взвешенный, 1,Таким образом, наибольшая точность достигается для взвешенного фильтра 16,3, который можно использовать в методе аннотирования для расчета расстояний между объектами.
В четвертой главе рассматриваются методы поиска текстур, и предлагается текстурный классификатор на основе метода моментов и метод аннотирования монохромных изображений за счет наличия текстур, основанный на данном классификаторе.
В данной работе рассматривается алгоритм текстурной сегментации на основе моментов. Рассмотрим прямоугольное изображение шириной и высотой. Пусть (, ) - значение изображения в точке (, ), нормализованное на отрезке [0; 1]. Метод моментов заключается в том, что для каждой точки изображения (, ) рассчитывается набор моментов и производных от них характеристик в пределах некоторого окна с центром в данной точке. Таким образом, формируется набор изображений, соответствующих набору признаков.
Момент, с центром в точке (, ) и размером окна рассчитывается следующим образом:, (, ) = (, ) (, ) , где =, =, - окно размером с центром в точке (, ).
/ / В качестве значений векторов признаков используются значения точек изображений характеристик моментов, :
( ),, = (, ) ( ) | tanh( (,, -, )) | - значение ( ) характеристики момента порядка (, ) в точке (, ), где,, = (, ) ( ) - усредненное изображение момента,, - окно,, размером с центром в точке (, ).
Степени моментов и задаются таким образом, чтобы их сумма не превышала некоторого значения, т.е. + . Тогда общее количество ( )( ) изображений моментов и характеристик моментов будет равно.
Для поиска текстур предлагается следующий классификатор:
1. Для каждой текстуры из обучающей выборки рассчитывается центральный вектор (центр текстуры) как средний вектор среди векторов признаков всех пикселей данной текстуры.
2. Для каждой текстуры из обучающей выборки задается параметр, который подбирается так, чтобы доля правильно классифицированных пикселей была наибольшей. Если расстояние от вектора признаков данной точки до центра данной текстуры не превышает, будем считать, что данная точка соответствует данной текстуре.
3. Для каждого изображения вычисляются изображения характеристик моментов,. Значения изображений характеристик моментов в точке ( ) (, ) определяют вектор признаков следующим образом: {,, | + }. Порядок расположения значений признаков внутри вектора фиксируется, например, при = 2 вектор признаков равен {,,,,,,,,,,, }.
4. Для каждого изображения вычисляется карта текстур. Размер карты равен размеру изображения. Значением карты для данной точки является номер первой соответствующей данной точке текстуры. Если данной точке не соответствует ни одна из текстур, точка карты принимает значение -1.
5. Точки полученной карты текстур объединяются в сегменты, которые состоят из соседних точек с одинаковым номером текстуры. Точки со значением -1 в сегменты не объединятся.
6. Для каждого сегмента определяется его размер, равный количеству пикселей. Если размер сегмента равен или превышает некоторое пороговое значение, считается, что соответствующая текстура найдена на текущем изображении. В данной работе использовалось пороговое значение размера сегмента 100.
Формулы расчета моментов и признаков характеризуются сложностью ( ), где - размер окна. Однако часть выражений, заданных этими формулами, представляют собой дискретную свертку с определенным ядром, что позволяет использовать быстрые методы вычисления свертки, основанные на быстром преобразовании Фурье. В данной работе используются подобные операции, позволяющие снизить сложность вычислений до ( log ).
На основе разработанного классификатора в данной работе предлагается следующий метод аннотирования изображений:
1. Задается набор текстур, каждая из которых принадлежит одному из нескольких заданных классов.
2. Каждому классу присваивается набор меток.
3. Для каждого изображения выполняется поиск текстур из заданного набора.
4. Для каждой найденной текстуры к изображению добавляется набор меток соответствующего класса.
Для оценки качества работы классификатора был проведен следующий эксперимент. Задается некоторое множество текстур и выборка изображений.
Для каждой текстуры данного множества определяются вхождения каждой текстуры множества в каждое изображение выборки. Вхождения текстур 1, найдено в отмечаются вручную с помощью эксперта: =. С 0, иначе другой стороны с помощью классификатора автоматически определяются вхождения каждой текстуры (аналогично ), после чего определяется флаг релевантности текстуры (1-текстура найдена на изображении и при этом обнаружена экспертом), который рассчитывается как = .
Тогда полнота и точность поиска текстуры рассчитывается следующим образом: =, =.
Аналогично можно рассчитать общую полноту и точность , , поиска: =, =.
, , Для оценки работоспособности классификатора был проведен следующий эксперимент. В качестве исходных данных было использовано множество текстур, представленное в таблице 5. Были заданы следующие параметры классификатора: = 2, = 9, = 49, = 0.01.
Таблица Изображения, использованные в эксперименте по текстурному поиску Крыша дома ( ) Стена дома ( ) На рисунке 8 представлены результаты эксперимента.
Рисунок 8. Результаты эксперимента по поиску текстур.
Эксперимент показал хороший результат с точки зрения полноты и слабый результат с точки зрения точности. Поскольку для исторических коллекций более важным показателем является полнота, данный классификатор может применяться для поиска текстур. Однако для повышения точности требуется его доработка.
В пятой главе рассматриваются особенности работы поисковых систем, их структура, предлагаются методы построения поисковых систем для коллекций изображений низкого качества на основе методов извлечения текстовой информации и аннотирования изображений, предложенных в данной работе.
Современные СУБД позволяют выполнять полнотекстовый поиск и строить соответствующие индексы. В данной работе разрабатывается поисковой робот, который в сочетании с подобной СУБД образует поисковую систему. Поэтому организация полнотекстового поиска на основе СУБД является необходимым и достаточным условием работы поисковой системы.
Технически полнотекстовый поиск с ранжированием результатов по релевантности доступен в подобных СУБД с помощью SQL-запросов со специальной конструкцией. При этом для осуществления индексации необходимо и достаточно хранить текстовую информацию в реляционной таблице в одном или нескольких специальных столбцах, отмеченных как полнотекстовые. Поэтому для организации полнотекстового поиска достаточно заполнять данные столбцы.
Например, пусть в таблице
SELECT * FROM
Таким образом, изменяя содержимое столбца
Пусть - изображение, на котором присутствуют различные объекты.
Задача индексирования сводится к получению текстового описания каждого объекта в виде набора слов и добавления этого набора в индекс. Пусть - множество типов объектов. Каждому типу объекта ставится в соответствие набор <, >, где - программная функция извлечения объекта данного типа в виде изображения, - программная функция, формирующая текстовое представление данного объекта. При этом не обязательно, чтобы программные функции выполнялись строго автоматически. В качестве программных функций могут использоваться также автоматизированные, либо ручные методы.
Не учитывая зависимость каждой программной функции из набора <, > от множества глобальных объектов и параметров, определим данную программную функцию как : , где - исходное изображение, - множество объектов.
Для программной функции возможна не только зависимость от глобальных объектов и параметров, но также и зависимость от других найденных объектов, поскольку возможны различные семантические связи между объектами, которые характерны именно для текстовой информации.
Рассмотрим в качестве примера случаи, когда сходство каких-либо двух объектов порождает один и тот же текстовый набор. Пусть объект с помощью программной функции порождает текстовый набор = { } и при этом находится объект, который является сходным для объекта.
Тогда объекту может быть поставлено в соответствие текстовое множество.
Найденное множество объектов { } и соответствующее множество текстовых наборов { } будем считать глобальными объектами, тогда можно определить программную функцию следующим образом: : , где - исходный объект, - порожденный текстовый набор.
Полнотекстовые модули современных СУБД для обеспечения поиска требуют от стороннего программного обеспечения запись текста в специальную таблицу в определенном формате. Данную таблицу можно представить в виде множества записей вида {<, > | = 1, }, где - изображение (источник текстовой информации), - соответствующий текст, - число изображений. В свою очередь текст можно представить как множество слов = { | = 1, }, где - количество слов в тексте.
Тогда с учетом определенных выше обозначений получим общую модель формирования текстовой информации для изображения : = | ( )| ( ) ( ), при этом будем считать множества допускающими повторения.
В рамках общей модели предлагается метод организации поиска по лексическим правилам для выявления новых ключевых слов и уточнения поисковых запросов.
Каждое лексическое правило поиска состоит из последовательности элементов различных типов, каждый из которых выполняющий логическую операцию сопоставления слова типу данного элемента. Процедура поиска по лексическому правилу заключается в поэлементном сопоставлении текстовой строки в виде последовательности слов { | = 1, }, где - количество слов и элементов правила = { | = 1, }, где - количество элементов правила (см. рисунок 9).
w1 Е wi wi+1 Е wi+m-1 Е wn r1 r2 Е rm Рисунок 9. Схема сопоставления поискового правила.
Сопоставление выполняется строго в порядке возрастания индекса элементов. При этом первый элемент правила может сопоставляться с любым допустимым элементов текстовой последовательности { } ( - + 1).
Таким образом, поиск по всей строке требует - + 1 операций сопоставления.
Например, в материалах коллекции строительства ББК часто встречается словосочетания вида: шлюз <число>. Поиск будет точнее, если полнотекстовый индекс будет различать объекты типа шлюз друг от друга исходя из номеров, чтобы поиск объекта шлюз 16 выдал документы, где встречается упоминание шлюза именно с таким номером. Для этого можно выполнить контекстный поиск по правилу:
const шлюз, simple number, с указанием следующего преобразования:
replace from {0}, to {1} with concat {item {0}, item {1}};
add taxon into item {0} value concat {item {0}, item {1}}.
В шестой главе описывается программный комплекс, разработанный для поддержки данного диссертационного исследования.
Программный комплекс включает в себя следующие компоненты:
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. Рогов А.А., Скабин А.В., Талбонен А.Н., Штеркель И.А. Некоторые особенности создания автоматизированной системы дешифровки исторических стенограмм // Интернет и современное общество:
сборник научных статей. Материалы 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 Всероссийской научной конференции RCDL'2010. Казань: Казан.
ун-т, 2010. С. 422-429.
7. Рогов А. А., Талбонен А. А., Варфоломеев А. Г. Автоматизированная система распознавания рукописных исторических документов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды XII Всероссийской научной конференции RCDL'2010.- Казань: Казан. ун-т, 2010. С. 469-475.
8. Талбонен А. Н. Особенности создания поискового индекса к фотографиям в цифровом историческом альбоме // Доклады по компьютерным наукам и информационным технологиям. № 1, 2012 г.
Доклады всероссийской научно-практической конференции Анализ Изображений, Сетей и Текстов (АИСТ 2012). Екатеринбург, 16 - марта 2012 года. М.: Национальный Открытый Университет ИНТУИТ 2012. - 419 с., С. 263 - 278.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям