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

Краткое описание

Рой Алексей Владимирович. Биометрический поиск информации в базе данных изображений, основанный на стохастической геометрии : диссертация ... кандидата технических наук : 05.13.17 / Рой Алексей Владимирович; [Место защиты: Пенз. гос. ун-т].- Пенза, 2008.- 187 с.: ил. РГБ ОД, 61 09-5/364

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
U4200951J59
Рой Алексей Владимирович
БИОМЕТРИЧЕСКИЙ ПОИСК ИНФОРМАЦИИ В БАЗЕ ДАННЫХ ИЗОБРАЖЕНИЙ, ОСНОВАННЫЙ НА СТОХАСТИЧЕСКОЙ ГЕОМЕТРИИ
Специальность 05.13.17 - «Теоретические основы информатики»
Диссертация на соискание ученой степени кандидата технических наук
Научный руководитель: доктор технических наук, профессор Федотов Н. Г.
Пенза 2008 
ВВЕДЕНИЕ 5
ГЛАВА 1. ОБЗОР МЕТОДОВ РАСПОЗНАВАНИЯ ЧЕЛОВЕЧЕСКИХ ЛИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ИЗОБРАЖЕНИЯ ПО ФОТОРОБОТУ 15
1.1. АСПЕКТЫ ФИЗИОЛОГИЧЕСКОГО ВОСПРИЯТИЯ ЧЕЛОВЕЧЕСКОГО ЛИЦА 15
1.2. ВЫБОР ПОДХОДОВ К РАСПОЗНАВАНИЮ ДЛЯ РЕАЛИЗАЦИИ БИОМЕТРИЧЕСКОГО ПОИСКА ИЗОБРАЖЕНИЙ ЧЕЛОВЕЧЕСКИХ ЛИЦ ПО ФОТОРОБОТУ 21
1.3. Выводы И РЕЗУЛЬТАТЫ 3 5
ГЛАВА 2. МЕТОД БИОМЕТРИЧЕСКОГО ПОИСКА НА ОСНОВЕ СТОХАСТИЧЕСКОЙ ГЕОМЕТРИИ И ФУНКЦИОНАЛЬНОГО АНАЛИЗА ■ 37
2.1. ОБОСНОВАНИЕ ВЫБОРА МЕТОДА 37
2.2. ОПИСАНИЕ ПРОСТРАНСТВА ПРИЗНАКОВ, ИСПОЛЬЗУЕМЫХ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ИЗОБРАЖЕНИЙ 41
2.2.1. TRACE-ФУНКЦИОНАЛЫ (Т-ФУНКЦИОНАЛЫ) 41
2.2.2 ДИАМЕТРАЛЬНЫЕ ФУНКЦИОНАЛЫ (Р-ФУНКЦИОНАЛЫ) 72
2.2.3. КРУГОВЫЕ ФУНКЦИОНАЛЫ (0-ФУНКЦИОНАЛЫ) 75
2.3. ФУНКЦИОНАЛЫ, ПРИМЕНЯЕМЫЕ ДЛЯ ФОРМИРОВАНИЯ ТРИПЛЕТНЫХ ПРИЗНАКОВ ПОИСКА ИНФОРМАЦИИ 7 7
2.4. ИССЛЕДОВАНИЕ СВОЙСТВ ИНВАРИАНТНОСТИ К МАСШТАБНЫМ ПРЕОБРАЗОВАНИЯМ ИЗОБРАЖЕНИЙ ОБЪЕКТА 84
2.5. Выводы И РЕЗУЛЬТАТЫ 98
ГЛАВА 3. ТЕХНИЧЕСКАЯ РЕАЛИЗАЦИЯ ПОИСКА ПОРТРЕТНЫХ ИЗОБРАЖЕНИЙ ПО ФОТОРОБОТУ 99
3.1. АРХИТЕКТУРА поисковой СИСТЕМЫ 99
3.2. ПРИМЕР РАСЧЕТА ТРИПЛЕТНЫХ ПРИЗНАКОВ в ДИСКРЕТНОМ ВИДЕ. 103
3.3. РАБОТА ПОИСКОВОЙ СИТЕМЫ 123
Qv/
3.4. ОСНОВНЫЕ МОДУЛИ СИСТЕМЫ 133
3.5. ВЗАИМОДЕЙСТВИЕ ОСНОВНЫХ ОБЪЕКТОВ ПОИСКОВОЙ СИСТЕМЫ 134
3.6. ВЗАИМОДЕЙСТВИЕ ГЛАВНОГО И ВСПОМОГАТЕЛЬНОГО ОКОН ПОИСКОВОЙ СИСТЕМЫ 136
3.7. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДУЛЕЙ ОСНОВНЫХ ОКОН ПРИЛОЖЕНИЙ 13 7
3.7.1. ОПИСАНИЕ МОДУЛЯ ОБМЕНА ДАННЫМИ 139
3.7.2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДУЛЯ ПРИМЕНЕНИЯ ФУНКЦИОНАЛОВ 140
3.7.3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДУЛЯ СКАНИРОВАНИЯ 142
3.7.4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДУЛЯ СЕГМЕНТАЦИИ 143
3.8. Выводы И РЕЗУЛЬТАТЫ 145
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СИСТЕМЫ ПОИСКА ПОРТРЕТНЫХ ИЗОБРАЖЕНИЙ ПО ФОТОРОБОТУ 146
4.1. ОБЪЕКТЫ ЭКСПЕРИМЕНТАЛЬНОГО ИССЛЕДОВАНИЯ 146;
4.2. ОЦЕНКА ИНФОРМАТИВНОСТИ ПРИЗНАКОВОГО ПРОСТРАНСТВА . 146
4.3. УПОРЯДОЧЕНИЕ ИЗОБРАЖЕНИЙ 154
4.4. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ 163
4.5. СРАВНЕНИЕ С СУЩЕСТВУЮЩИМИ СИСТЕМАМИ 170
4.6. Выводы и РЕЗУЛЬТАТЫ 175
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 176
ЛИТЕРАТУРА 179
СПРАВКА О ВНЕДРЕНИИ 188
Актуальность проблемы. В настоящее время на передний план теоретической информатики выдвигается проблема поиска информации по изображениям. Наряду с общетеоретическим значением, она исключительно важна для приложений в таких областях, как геология, аэрокосмические исследования, медицина, криминалистика.
Актуальность данной темы усилилась в связи с настоятельной
необходимостью осуществлять биометрический поиск в больших базах
данных изображений. Решение этой актуальной задачи имеет большое к
социальное значение в связи с растущим в мире криминалом и терроризмом.
Для задач сравнения лиц, их поиска и, в общем портретной идентификации, характерна значительная вариабельность биометрических параметров, обусловленная различием форм, уровнем яркости, наличием фоновых шумов изображений на фотоснимках. В этих условиях придать большую устойчивость и надежность автоматического поиска изображений лиц позволяет опора на большое количество признаков распознавания. Применение теории распознавания образов, основанной на стохастической геометрии, позволяет осуществить формирование большого количества признаков* распознавания. Экстракция необходимых признаков распознавания с учетом анатомии портретного изображения даёт возможность достаточно надежно решать эту актуальную задачу.
Цель диссертационной работы. Разработка методов поиска биометрической информации в базе данных на основе признаков, базирующихся на стохастической геометрии; построение программной системы для реализации процедуры поиска портретных изображений.
Поставленная цель достигается решением следующих задач:
• реализация процедур предварительной обработки цветных
фотографических изображений для приведения к бинарному виду;
ч-5
• реализация процедуры сегментации бинарного изображения человеческого лица с целью выделения наиболее информативных областей;
• построение трейс-преобразований биометрических изображений как источника формирования поисковых признаков нового класса, со структурой в виде композиции трех функционалов — триплетных признаков;
• выбор функционалов, обеспечивающих получение триплетных признаксв распознавания портретных изображений;
• определение решающего правила поиска биометрической информации;
• разработка алгоритма поиска изображений по фотороботу;
• разработка программной системы для поиска изображений по фотороботу;
• экспериментальная проверка эффективности алгоритма поиска изображений по фотороботу.
Объектом исследования является биометрический поиск изображений человеческих лиц по фотороботу.
Предмет исследования составляют математические методы ‘ распознавания человеческих лиц и их программная реализация.
Методы исследования. При решении поставленных задач применены теория распознавания образов, теория признаков распознавания образов, базирующаяся на стохастической геометрии и функциональном анализе, методы теории вероятностей, математической статистики, цифровой обработки изображений.
Проверка эффективности предложений, исследованных в диссертации, проводилась на разработанных математических моделях и по результатам работы программной системы, осуществляющей поиск реальной
биометрической информации.
б
Научная новизна работы:
1. Впервые предложено для построения системы биометрического поиска использовать математический аппарат стохастической геометрии, дающий возможность достигнуть высокую эффективность информационного поиска.
2. Впервые предложены новые конструктивные поисковые признаки, имеющие структуру в виде композиции трех функционалов (триплетные признаки). Благодаря такой структуре возможно получение большого количества поисковых признаков, что позволяет получить высокую гибкость и интеллектуальность поисковой системы, а также упростить решающие правила.
3. Предложено определение триплетных признаков по областям - изображения соответствующим элементам человеческого лица, что позволило повысить надежность биометрического поиска.
4. Разработан алгоритм биометрического поиска на основе стохастической геометрии, позволяющий достичь поставленной в работе цели.
5. Разработана программная система интеллектуального биометрического поиска фотоизображений по фотороботу, что позволило автоматизировать этот процесс.
Практическая ценность. Предложенные в диссертации методы и
программная система позволяют автоматизировать процесс поиска таких
биометрических объектов, как человеческие лица, по составленному
субъективному портрету (фотороботу). Разработанный алгоритм,
базирующийся на методах стохастической геометрии, даёт возможность
осуществить поиск изображений лиц по фотороботу с опорой на большое і
количество признаков, что повышает гибкость и надежность поиска. Диссертационная работа осуществлялась по трем программам РФФИ и Минобразования.
Реализация и внедрение результатов.
Результаты исследований используются при работе 2 полка милиции УВО при ГУВД по г. Москве.
к
Основные положения, выносимые на защиту:
1. Обоснование целесообразности построения системы биометрического поиска как обучающейся системы (класса «обучения с учителем»).
2. Обоснование целесообразности использования математического аппарата стохастической геометрии для решения задачи биометрического поиска.
3. Новые конструктивные поисковые признаки, имеющие структуру в виде композиции трех функционалов (триплетные признаки).
4. Повышение надежности биометрического поиска с помощью определения триплетных признаков по областям соответствующим элементам человеческого лица.
5. Реализация алгоритма биометрического поиска на основе стохастической геометрии.
6. Реализация программной системы интеллектуального биометрического поиска фотоизображений по фотороботу.
Апробация работы. Основные положения диссертации докладывались на следующих научных конференциях:
• 2-й | Международная конференция молодых ученых и студентов «Актуальные проблемы современной науки» (г. Самара, 2001),
• 6-й Международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» РОАИ-6-2002 (г.
Великий Новгород, 2002),
• Международная научно-техническая конференция «Математические методы в экономике» (г. Пенза, 2002),
• Международная конференция по мягким вычислениям и измерениям SCM' 2002 (г. Санкт-Петербург, 2002),
• Международная научная конференция «Интеллектуализация обработки информации» ИОИ-2004 (Крым, г. Алушта, 2004).
По итогам работы на 2-й Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки» в г. Самара, 2001 г. был награкден грамотой за лучшую работу.
Публикации. По теме диссертационной работы опубликовано 16 печатных работ, включая 7 статей, 9 тезисов докладов, из них 1 статья опубликована в журнале, аккредитованном ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 97 наименований. Общий объем диссертации 187 с, в том числе 177 с. основного текста, 7 с. списка литературы, 72 таблицы, 59 рисунков.
і СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность выбранной темы; сформулирована научная проблема, дана общая постановка решаемых задач, приведено краткое содержание диссертационной работы.
В первой главе дан обзор методов распознавания человеческих лиц для решения задачи поиска изображений по фотороботу. Существуют научные школы, рассматривающие распознавание человеческих лиц в тесной связи с физиологией зрительного восприятия: научная школа НИИ нейрокибернетики имени А.Б. Когана Ростовского университета (Шапошников Д.Т., Головань Ю.Ф., Литовченко Е.В., Гусанова В.И., Калинин К.В., Петрушан М.В., Самарин А.И.), научная школа Института автоматики РАН (О. Белоцерковский, А. Глазунов). В работах этих научных коллективов решается задача улучшения поиска и распознавания слабоконтрастного объекта, которым является человеческое лицо.
Согласно психофизической теории восприятия и распознавания при восприятии изображения человеческих лиц происходит независимое выявление отдельных частей портрета, т.е. выделение групп структурных элементов или организованных структур. При этом процесс носит многосвязный характер, структура управления им имеет обратные связи.
Вышеуказанные физиологические процессы восприятия человеческих лиц дают возможность сделать в первой главе вывод о том, что построению системы поиска изображений по фотороботу в наибольшей степени соответствует модель распознающих систем с обучением (обучение с учителем). Кроме того, установлено, что перемещение глаза носит стохастический характер с фиксацией на области наибольшей информативности (глаза, нос, рот, овал лица, причем именно в такой последовательности). Рассматриваемый процесс зрительного восприятия, на наш взгляд, имеет аналогию с развиваемыми в диссертационной работе методами поиска биометрической информации на основе методов стохастической геометрии.
Также в работе рассмотрены известные методы получения признаков изображений. Обоснована целесообразность применения методов, базирующихся на стохастической геометрии. В работе проводится аналитический обзор методов распознавания образов: рассматривается исторически одним из первых появившийся персептронный (Ф. Розенблат) метод распознавания зрительной информации, позже получивший мощное развитие в нейронных сетях (А. Г. Ивахненко, Т. Кохонен, С. Гроссберг); методы, основанные на анализе контуров (X. Фримен, Я. А. Фурман) и топологическом описании; интегральные методы, связанные со спектральными отсчетами и другие интегральные методы; структурный подход (К. Фу, Т. Павлидис, И. Б. Мучник).
Многие из вышеупомянутых методов оказались непригодны для решения Задачи поиска биометрической информации. Так рассмотренные структурные методы не обеспечивают инвариантность к группе движений и линейных деформаций изображений. Искусственно придать им это свойство можно лишь ценой больших вычислительных затрат.
Многие интегральные методы свободны от этого недостатка. Однако большинство методов узко специализированы и используют незначительную часть информации об объектах. Например, метод моментов использует
ю
только функцию яркостной интенсивности точки, не включает в распознающие инварианты информацию об окрестностях точек. Метод дескрипторов Фурье пригоден лишь для распознавания контурных изображений.
Теория распознавания образов, основанная на стохастической
геометрии, включающая теорию триплетных признаков и новое
геометрическое трейс-преобразование изображений, позволяет избежать этих
недостатков за счет большого числа новых конструктивных признаков
распознавания. Поэтому для решения задачи биометрического поиска была
выбрана эта теория.
Во второй главе содержится описание алгоритма биометрического
поиска, представлено применение методов стохастической геометрии для
формирования поисковых признаков распознавания, имеющих характерную
структуру в виде композиции трех функционалов.
В работе, на основании анализа физиологических принципов восприятия
и распознавания человеческих лиц, была построена система биометрического
поиска изображений человеческих лиц по эскизу или фотороботу, по типу і
обучение с учителем. Во второй главе описаны следующие этапы работы системы:
1. Обучение, целью которого является формирование признаков, их предварительный анализ, выдвижение гипотезы об их информативности и выбор решающего правила.
2. Поиск изображения лица по эскизу или фотороботу и идентификация.
Режим обучения. Путем генерации триплетных признаков каждого
портретного изображения, хранящегося в базе данных, был построен набор
поисковых триплетных признаков, число которых в данном случае достигает I
1080. Эти признаки вычислялись в режиме обучения для 100 портретных изображений и для 10 образцов фотороботов, причем вычисления осуществлялись по всем перечисленным выше областям наибольшей информативности.
и
Результаты вычислений в режиме обучения показали, что значения некоторые триплетных признаков попадают в непересекающиеся или частично пересекающиеся множества значений признаков. Эти признаки обеспечивают наиболее важную информацию об изучаемых изображениях, их следует использовать при построении решающей функции. Остальные признаки считают малоинформативными, их влияние при принятии решения в системе снижается с помощью весовых коэффициентов.
Режим обучения. Путем генерации триплетных признаков каждого портретного изображения, хранящегося в базе данных, был построен набор поисковых триплетных признаков, число которых в данном случае достигает 1080. Эти^ признаки вычислялись в режиме обучения для 150 портретных изображений и для 15 образцов фотороботов, причем вычисления осуществлялись по всем перечисленным выше областям наибольшей информативности.
Результаты вычислений в режиме обучения показали, что значения некоторых триплетных признаков попадают в непересекающиеся или частично пересекающиеся множества значений признаков. Эти признаки обеспечивают наиболее важную информацию об изучаемых изображениях, их следует использовать при построении решающей функции. Остальные признаки ^читают малоинформативными, их влияние при принятии решения в системе снижается с помощью весовых коэффициентов.
Режим поиска. Процесс поиска в системе строится следующим образом: выбирают в первую очередь те портретные изображения, которые имеют наименьшее расстояние между двумя наборами поисковых признаков для фоторобота и анализируемого изображения. Эти расстояния характеризуют степень близости. Далее происходит упорядочение всех изображений по выбранному критерию близости.
Как уже упоминалось выше, в режиме обучения были выбраны весовые коэффициенты для каждого из поисковых признаков, чтобы снизить влияние малоинформативных поисковых признаков и усилить влияние высокоинформативных. Это позволяет повысить надежность поиска.
Кроме того, в системе предусмотрена возможность в автоматическом режиме определять компактность наборов точек поисковых признаков и их разнесённЬсть в пространстве поисковых признаков, позволяющая системе самостоятельно оценивать информативность триплетных признаков.
Далее во второй главе рассмотрены этапы преобразования информации для реализации биометрического поиска.
Предварительная обработка изображений. Поскольку в процессе поиска приходится сравнивать черно-белое изображение фоторобота с изображением лиц из базы данных, необходима предварительная обработка изображений с целью приведения их к бинарному виду. Исходные цветные фотографические портреты переводятся в черно-белые специальной процедурой бинаризации, описанной в главе 3.
Сегментация. На этом этапе происходит выделение (разбиение изображения) наиболее информативных областей: глаза, нос, рот, овал лица и др. В данном случае применен разработанный автором метод, основанный на рекурсивной функции заливки заданным цветом произвольной замкнутой области изображения. Описание и результаты применения метода приведены в главе 3.
Вычисление триплетных признаков. Сканирование решеткой параллельных прямых изображения для его Трейс-преобразования, получения цирка, а затем и вычисление триплетного признака.
Третья глава содержит описание программной реализации алгоритма биометрического поиска на основе стохастической геометрии, включающий предварительную обработку информации, его сегментации, формирование геометрических трейс-преобразований изображений, и вычисление по ним триплетных признаков, решающие процедуры, а также осуществлена проверка работоспособности полученных во второй главе функционалов, используемых для вычисления поисковых триплетных признаков в среде
к
MathCAD. Система биометрического поиска была выполнена в виде автономных модулей. При написании основных модулей применялся объектно-ориентированный подход и использовалась библиотека визуальных компонент C++ Builder’а.
Четвертая глава содержит исследование решающего правила, согласно которому оценивается, как анализируемое изображение соотносится с фотороботом. Анализируется информативность признакового пространства, характер Ьшибок распознавания, реализации решения задач сравнения и поиска, а также исследуются результаты работы решающего правила на релевантность. Кроме того, полученные параметры разработанной системы сравниваются полученные результаты с зарубежными аналогами по результатам исследований проекта Feret.

Список литературы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
1. На основе анализа физиологии восприятия и распознавания человеческих лиц предложено построить систему биометрического поиска как обучающуюся, по типу обучения с учителем. Это дает возможность достигнуть высокой адаптивности системы.
2. Впервые предложено для построения биометрического поиска использовать математический аппарат стохастической геометрии, что дает возможность достигнуть высоких показателей эффективности: гибкости, универсальности, надежности поиска, большего быстродействия.
3. Впервые предложены поисковые признаки, имеющие структуру в виде композиции трех функционалов (триплетные признаки). Благодаря такой структуре возможно получение большого количества поисковых признаков, что позволяет достичь высокой гибкости и интеллектуальной поисковой системы, а также упростить решающие правила.
4. При определенном выборе свойств функционалов, входящих в триплетный признак можно добиться инвариантности поисковых признаков по отношению к группе движений и линейным искажениям изображений, что повышает надежность поиска фотоизображений.
5. Для повышения надежности биометрического поиска предложено определение триплетных признаков, по областям изображений соответствующим элементам человеческого лица. С этой целью разработана процедура сегментации.
6. Разработан алгоритм биометрического поиска на основе
стохастической геометрии, включающий предварительную обработку
информации, его сегментации, формирование геометрических трейс-
преобразований изображений, и вычисление по ним триплетных признаков,
решающие процедуры. і
7. Разработана программная система интеллектуально биометрического поиска фотоизображений по фотороботу в неупорядоченных базах данных на 1020 фотоучетов. Осуществлена экспериментальная проверка, которая показала ^ысокую эффективность поиска, причём точность идентификации составила:
• 73% для БД на 150 фотоучетов (I) и 48% для БД на 870 фотоучетов (II), когда изображение, сопоставляемое фотороботу попадает на первое место списка;
• соответственно 93% (I) и 74%) (И), когда изображение,
сопоставляемое фотороботу, попадает в первую десятку списка;
• 100% для обеих БД, когда изображение, сопоставляемое фотороботу попадает в первую сотню списка.
Анализ результатов работы системы поиска биометрической информации показал, что точность поиска будет уменьшаться при увеличении БД изображениями более низкого качества приблизительно в 1,5¬2 раза при увеличении объёма БД в несколько раз. При этом полнота выдачи уменьшится немного — на 1-2%, что является хорошим результатом для информационно-поисковых систем, для которых характеристика «точность поиска - полнота выдачи» является ценным интегральным критерием эффективности.