Содержание к диссертации
Введение
ГЛАВА 1. Состояние проблемы и задачи исследования 12
1.1. Обзор методов распознавания образов 14
1.1.1. Байесовские методы 15
1.1.2. Линейные методы 18
1.1.3. Метрические методы 22
1.2. Особенности метрических методов и требования к исходным данным и алгоритмам классификации 25
1.2.1. Исходные данные и их представление 25
1.2.2. Меры различия и сходства и способы объединения решений 30
1.2.3. Типы ошибок и обучение 32
1.2.4. Сложность и эффективность алгоритмов распознавания 34
1.3. Цель и задачи исследования 36
ГЛАВА 2. Древовидное представление многоканальных изображений и модель метрического классификатора 38
2.1. Построение многослойных древовидных представлений 38
2.1.1. Однослойное древовидное представление объектов 39
2.1.2. Многослойное древовидное представление объектов
2.2. Мера различия объектов на множестве многослойных древовидных представлений и модель классификатора 45
2.3. Алгоритм направленного поиска решения и вычислительная сложность 50
2.4. Результаты и их обсуждение
ГЛАВА 3. Обучение и объединение классификаторов 56
3.1 Построение древовидно-структурированных покрытий 56
3.2 Функция ошибки скользящего контроля
и оптимизация покрытий 61
3.3 Объединение классификаторов 65
3.3.1. Оценки параметров меры 65
3.3.2. Стратегия обобщенной меры различия
для классификации по ансамблю источников 67
3.3.3. Стратегия взвешенного большинства голосов
для объединения по ансамблю решений 70
3.4 Результаты и их обсуждение 73
ГЛАВА 4. База изображений и комплекс программ для моделирования классификаторов 75
4.1. Подготовка базы изображений подписей 75
4.1.1. Анализ общедоступных баз подписей 76
4.1.2. Пороговая фильтрация изображений 77
4.2. Формирование базы изображений лиц 78
4.2.1. Анализ общедоступных баз лиц 78
4.2.2. Получение цветных изображений 79
4.2.3. Выделение информативной области на изображении 82
4.2.4. Нормализация информативной области 84
4.2.5. Эквализация изображений по каналам представления 85
4.3. Основные функции и структура комплекса программ 87
4.3.1. Трехуровневая структура описания программ 88
4.3.2. Централизованная схема вызова приложений 89
4.3.3. Основные функции программ
4.4. Настройка программ для проведения экспериментов 111
4.5. Результаты и их обсуждение 113
ГЛАВА 5. Методика проведения экспериментов и результаты распознавания подписей и лиц 114
5.1. Состави схема проведения экспериментов 114
5.1.1. Источники одноканальных изображений 117
5.1.2. Источники многоканальных изображений 121
5.1.3. Ансамбль источников 124
5.2. Результаты моделирования процедуры обучения классификаторов 127
5.2.1. Источник полутоновых изображений подписей 128
5.2.2. Источник цветных изображений лиц 130
5.2.3. Ансамбль источников изображений подписей и лиц 134
5.3. Результаты тестирования классификаторов 137
5.3.1. Распознавание полутоновых изображений подписей с использованием переборного поиска решения 137
5.3.2. Распознавание цветных изображений лиц с использованием переборного поиска решения 141
5.3.3. Распознавание по ансамблю изображений подписей и лиц 152
Основные результаты и выводы 162
Библиографический список
- Особенности метрических методов и требования к исходным данным и алгоритмам классификации
- Многослойное древовидное представление объектов
- Оценки параметров меры
- Получение цветных изображений
Введение к работе
Актуальность темы. Исследование и разработка методов и алгоритмов автоматического анализа и понимания изображений продиктованы активным развитием информационных технологий, используемых в системах искусственного интеллекта. Развитие таких технологий стимулируется растущим быстродействием вычислительной техники, способной быстро и с высокой точностью обрабатывать большие объемы данных. Одно из ведущих направлений в области анализа и понимания изображений составляет распознавание образов, которое тесно связано с проблематикой технического зрения. Значительный вклад в развитие методов и алгоритмов, используемых для решения задач классификации и анализа изображений, внесли как отечественные ученые Ю.И. Журавлев, КВ. Рудаков, В.Н. Вапник, А.Я. Червоненкис, Н.Г. Загоруйко, Ю.П. Пытьев, А.И. Чуличков, КВ. Воронцов, Л.М. Местецкий, В.В. Моттль, В.В. Рязанов, так и зарубежные специалисты R. Duda, R. Gonzalez, J. Serra, R. Haralick, L. Shapiro, T. Huang, A. Rosenfeld, L. Kuncheva.
В диссертационной работе исследуется задача распознавания объектов, заданных многоканальными изображениями. В этом случае объекты задаются наборами образов, которые выделяются на изображениях, получаемых по различным информационным каналам. Особенность рассматриваемой задачи характеризуется большим числом классов. Примером такого источника являются изображения биометрических данных (лиц, отпечатков пальцев, радужных оболочек глаз, подписей, рисунков ладоней и т.п.), которые используются в системах идентификации личности. Число классов в таких системах определяется числом персон, информация о которых хранится в базе данных, и может составлять величины порядка тысяч и более. Подобный источник образуют также цветные изображения, которые являются трехканальными изображениями в стандартных моделях RGB, HSI и др.
Многоканальные изображения обладают существенно большим количеством информации о распознаваемых объектах и позволяют повысить достоверность классификации за счет уменьшения доли ошибочных решений. Однако многоканальность источника в сочетании с большим числом классов порождает большие объемы данных, которые в реальных системах должны обрабатываться за достаточно малое время. Поэтому указанная специфика задачи распознавания, наряду с высокими требованиями к достоверности решений, выдвигает особые требования к быстродействию классификатора, причем показатели достоверности и быстродействия, как правило, связаны обратным соотношением.
Для достижения компромисса между достоверностью и быстродействием задачу распознавания целесообразно решать в терминах соотношения характеристик качества и вычислительной сложности, требуя минимизации вероятности ошибок при заданном ограничении на объем вычислений. В такой постановке актуальной задачей является разработка и исследование универсальной модели классификатора с метрическим решающим правилом в пространстве структурных представлений образов с многоуровневым разрешением. Универсальность предполагает высокую эффективность такого классификатора для различных источников многоканальных изображений, а структура представлений образов должна обеспечить высокое быстродействие за счет иерархического поиска решений в базе эталонов с многоуровневым разрешением.
Один из первых подходов к построению структурных описаний геометрических форм на основе их иерархической декомпозиции предложен Н. Row и G. Medioni (1993). Метод рекурсивной декомпозиции использован S. Berretti и A. Del Bimbo (2004) для представления двумерных форм древовидно-структурированными наборами спектральных признаков. Для распознавания геометрических форм А. Torsello и Е. Hancock (2004) исследовали процедуры установления соответствия иерархически-структурированных признаков. Подходы и методы, рассмотренные этими авторами, ориентированы на построение эффективного пространства описаний (представлений) образов, выделенных на бинарных изображениях. К подобным структурным описаниям геометрических форм относятся также скелетные представления, предложенные Л.М. Местецким (2000), и древовидные представления наборами эллиптических примитивов, разработанные М.М. Ланге и С.Н. Ганебных (2004). Древовидные представления эллиптическими примитивами обобщены М.М. Ланге и С.Н. Ганебных (2007-2009) для широкого класса образов, заданных одноканальными полутоновыми изображениями. На множестве представлений введена мера различия полутоновых образов, и показана эффективность полученного пространства представлений для распознавания жестов руки и подписей.
Развитием структурных методов распознавания является обобщение метода древовидного представления эллиптическими примитивами для источников многоканальных изображений и построение эффективного и быстрого классификатора в пространстве обобщенных древовидных представлений. Актуальность этого подхода обусловлена его универсальностью и широкими практическими приложениями.
Цель работы и задачи исследования. Цель диссертационного исследования заключается в разработке универсального метрического классификатора в пространстве древовидных представлений образов с многоуровневым разрешением для источников многоканальных
изображений. Область исследования включает разработку методов и алгоритмов решения задачи распознавания образов и проведение вычислительных экспериментов по распознаванию объектов, заданных изображениями. В соответствии с поставленной целью решаются следующие задачи:
-
Разработка модели метрического классификатора объектов по многоканальным изображениям. Построение многослойных древовидных представлений образов и введение меры различия объектов на множестве представлений. Формализация критерия классификации.
-
Построение процедуры обучения классификатора на основе отбора эталонов и оптимизации параметров. Получение сравнительных оценок вычислительной сложности иерархического и переборного алгоритмов поиска решений.
-
Подготовка базы изображений, разработка комплекса программ и проведение экспериментов по идентификации личности с использованием многоканальных данных, заданных полутоновыми изображениями подписей и цветными изображениями лиц.
Основные положения, выносимые на защиту.
-
Модель метрического классификатора по критериям взвешенного голосования и ближайшего эталона в пространстве многослойных древовидных представлений образов, заданных многоканальными изображениями. Модель включает способ представления объектов, меру различия на множестве представлений и критерии классификации.
-
Процедура обучения классификатора на основе построения древовидно-структурированного покрытия обучающего множества сферами в пространстве представлений с заданной мерой. Функция ошибок и численная оптимизация параметров покрытия и меры методом скользящего контроля.
-
Способ комплексирования решений по обобщенной мере различия объектов на множестве многослойных древовидных представлений.
-
Программный комплекс для реализации процедур обучения и тестирования классификатора. Экспериментальные оценки качества идентификации личности по полутоновым изображениям подписей, цветным изображениям лиц и по ансамблю изображений подписей и лиц.
Методы исследования. В выполненных разработках и исследованиях использовались методы теории информации, теории вероятности и теории распознавания образов, элементы математического моделирования, численных методов оптимизации и прикладного программирования.
Научная новизна работы состоит в построении пространства универсальных древовидно-структурированных представлений двумерных объектов, заданных многоканальными изображениями; разработке метрической модели классификатора в указанном пространстве представлений; получении оценок вычислительной сложности, демонстрирующих выигрыш в быстродействии иерархического алгоритма поиска решения по сравнению с алгоритмом полного перебора; предложении процедуры обучения метрического классификатора; разработке способа объединения решений по обобщенной мере различия объектов; получении экспериментальных оценок эффективности разработанного классификатора для источников многоканальных биометрических изображений.
Теоретическая и практическая ценность. Теоретическую ценность работы составляют многослойное представление образов с многоуровневым разрешением, мера различия на множестве многослойных представлений и модель метрического классификатора. Теоретические результаты работы включены в курс лекций по дисциплине «Синергетическая информатика» на кафедре «Прикладная синергетика» в МГТУ МИРЭА и использованы в научных отчетах по проекту Российского фонда фундаментальных исследований №09-01-00573-а, выполненному в Вычислительном центре им. А.А. Дородницына РАН.
Практическую ценность выполненных исследований составляют результаты экспериментов по классификации биометрических изображений. Полученные оценки качества распознавания демонстрируют высокую эффективность разработанной модели классификатора и уменьшение доли и дисперсии ошибок при расширении состава источников (увеличении числа информационных каналов). Разработанный комплекс программ внедрен в системе контроля доступа в помещения организации ОАО «Чувашнефтепродукт».
Достоверность полученных результатов обоснована
математическими выкладками, модельными экспериментами и согласованностью полученных оценок качества распознавания с аналогичными характеристиками известного классификатора на основе метода опорных векторов. Теоретическая и практическая ценность выполненных разработок подтверждена актами о внедрении.
Апробация работы. Результаты диссертационной работы обсуждены и получили положительные отзывы на следующих научных конференциях, конкурсах и семинарах:
11-й научно-практической конференции «Современные информационные технологии в управлении и образовании», г.Москва, ФГУП НИИ «Восход», 2012 г. (работа отмечена дипломом 2-й степени и премией имени д.т.н. B.C. Корсакова-Богаткова);
научном семинаре «Морфологический анализ данных» под руководством д.ф.-м.н., проф. Ю.П. Пытьева, г.Москва, Физический ф-тМГУ,2011г.;
14, 15-й Всероссийской конференции «Математические методы распознавания образов», г.Суздаль, 2009 г., г.Петрозаводск, 2011 г.;
10-й Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии», г.Санкт-Петербург, 2010 г.;
16-й Международной научно-практической конференции студентов и молодых ученых «Современные техника и технологии», г.Томск, 2010 г.;
3-й Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации», г.Москва, 2009 г. (работа отмечена дипломом);
58, 59, 60-й научно-технической конференции МИРЭА, г.Москва, МИРЭА, 2009-2011 гг.;
конкурсе «Лучшая научная работа студентов и молодых ученых МИРЭА 2009», г.Москва, МИРЭА, 2009 г. (работа отмечена почетной грамотой);
открытом конкурсе инновационных идей «Стремление», г.Москва, МИРЭА, 2009 г. (работа отмечена дипломом 2-й степени);
Всероссийском смотре-конкурсе научно-технического творчества студентов и аспирантов высших учебных заведений «Эврика-2009», г.Новочеркасск, ЮРГТУ НПИ, 2009 г. (работа отмечена дипломом 3-й степени).
Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований №09-01-16059-моб-з и 10-01-16048-моб-з.
Публикации. По материалам диссертационной работы опубликовано 12 печатных работ, в том числе 4 в журналах из перечня ВАК, получены 2 свидетельства о государственной регистрации программного продукта (№50200900489, 50201001618).
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, библиографического списка из 80 наименований и двух приложений. Работа содержит 170 страниц основного текста, 64 рисунка и 22 таблицы.
Пусть изображение определяется целочисленной функцией, заданной на двумерной прямоугольной решетке с конечным числом элементов (пикселей). Под информационным каналом наблюдения
понимается способ отображения реальных предметов в их изображения. Изображение на выходе заданного канала называется одноканальним изображением. Набор одноканальных изображений, полученных по различным каналам наблюдения, образует многоканальное изображение. Источник определяется множеством одноканальных или многоканальных изображений семантически однотипных предметов, которые принадлежат заданному числу классов, снабженных семантическими признаками (именами). Подмножество изображений, принадлежащих одному классу, образует кластер. Полутоновые изображения предметов образуют источники одноканальных изображений, цветные изображения содержат три канала и являются примером многоканальных изображений. В общем случае любой набор источников порождает многоканальные изображения. Образом называется информативный набор пикселей, выделенный на одноканальном изображении, полученном от заданного канала наблюдения. Объект определяется совокупностью образов, выделенных на наборе одноканальных изображений, образующих многоканальное изображение. Для источников одноканальных изображений понятия образа и объекта тождественны. Представление объекта определяется набором описаний образов, составляющих этот объект, в заданной системе признаков. Представление объекта, заданного одноканальным изображением, определятся описанием образа этого объекта на изображении.
Особенности метрических методов и требования к исходным данным и алгоритмам классификации
Нахождение оптимальной разделяющей гиперплоскости сводится к максимизации ширины зазора и, следовательно, к минимизации квадрата нормы w при условиях, ограничивающих попадание в зазор объектов обучающего множества X". Вводя переменные ,к 0, которые соответствуют ?п ошибкам на объектах хк,к = ],...,п, с учетом нормировки 6w = l в (1.1.6), задача сводится к минимизации функционала 1 ]2 " тН1 + ffE&- min, .zkg(xk) \-Sk,k = \,...,n, (1.1.7) 4 (U = l,...,« при указанных ограничениях, где = (,,...,„). Параметр д 0 введен для обеспечения компромисса между максимизацией ширины зазора и минимизацией суммарной ошибки. Поиск минимума функционала при заданных ограничениях в (1-1.7) является задачей квадратичного программирования, которая решается методом множителей Лагранжа [19]. Величина д выбирается путем применения процедуры скользящего контроля (Cross-Validation) [20] или путем многократной фильтрации объектов хк, имеющих наибольшие ошибки д к, что позволяет свести задачу обучения к линейно разделимым классам [16].
Благодаря высокой эффективности (малым ошибкам), SVM-классификаторы имеют широкое практическое применение. Решение задачи оптимизации разделяющей гиперплоскости вычисляется на малом числе объектов, называемых опорными векторами, и может быть получено при малых мощностях rij,i = \,...,c, кластеров обучающего множества X". Вычислительная сложность переборного алгоритма принятия решения в SVM-классификаторе, использующем с{с —1)/2 элементарных классификаторов ( по одному для каждой пары классов у, и со, ), при размерности векторного пространства признаков, пропорциональной с, имеет порядок 0(съ). Для SVM классификатора, построенного на ансамбле из с элементарных классификаторов (по одному для каждой пары со{ и Q. \ a i), вычислительная сложность может быть уменьшена до 0(с ).
В ряде прикладных задач распознавания образов меры сходства объектов с классами строятся с использованием функции расстояния d(x, х ) 0 на множестве объектов X. Классификаторы, использующие такие меры, называются метрическими, даже в тех случаях, когда функция расстояния не является метрикой [16]. Функция d(x,x ) должна обеспечивать малые расстояния между объектами одного класса и большие расстояния между объектами разных классов, что принято называть свойством компактности.
Будем считать, что обучающее множество X" = \хк,к = \,...,п\ разбито на кластеры Xй = (ху,у = 1,...,и, мощности щ : иг- -п, и в кластерах отобраны 2=1 наборы представителей Х" = (х,у, f = 1,...,«,) мощности «,:() «, «,, i = l,...,с. Тогда мера сходства объекта хєХ с классом co Q. определяется функцией /(х) = Zlxy = ij]v(xij)Kd(x xij),i = l,...,c, (1.1.8) 7=1 где [( )] - индикатор, принимающий значение 1 и 0 соответственно при выполнении и невыполнении условия ( ), w(x ) О - вес объекта X , Kd (х, х ) 0 - потенциальная функция (ядро по мере d(x, х )), которая не возрастает с ростом d(x,x ) и определяет потенциал объекта x:j с единичным весом в точке х. По существу, значения функции вида (1.1.8) определяют голоса кластеров X" ,/ = 1,...,с, относительно принадлежности объекта х соответствующим классам и дают решающее правило щ : i = argmaxg,-(х). (1.1.9)
Отметим некоторые наиболее распространенные метрические методы классификации. Метод ближайшего эталона (Nearest Neighbor) базируется на отборе единственного ближайшего представителя к предъявляемому объекту и вычислении меры сходства (1.1.8) при w(xy)-l и Kd(x,x ) = 1. В этом случае с X", =1 и решение (1.1.9) принимается в пользу единственного класса, для которого значение меры сходства положительно. Метод к - ближайших эталонов (k-Nearest Neighbors) строится на отборе к ближайших представителей и использовании меры сходства с весовой с функцией w(xv) 0 и Kd(x,xy) = l. В этом случае ", =к и решение (1.1.9) /-і принимается в пользу класса с наибольшим суммарным весом (голосом). Весовые коэффициенты w(xv) могут принимать одинаковые или различные значения для всех объектов обучающего множества. При к = 1, метод kNN совпадает с методом NN и неустойчив к шуму. При к = п, метод kNN обладает чрезмерной устойчивостью и может привести к переобучению. Поэтому возникает проблема выбора оптимального значения к методом скользящего контроля с исключением объектов по одному элементу (Leave-One-Out) [16].
Многослойное древовидное представление объектов
Используя эталоны (2.2.6), заданные представлениями (2.1.4), и их сферы влияния с радиусами (2.2.7), взятыми при 1 = L, вводится мера сходства L-ro порядка между любым объектом Л є А и набором эталонов В, /-го класса. Эта мера имеет вид -dL{A,Bij) і Г) (ИЛ ML(A,B{)= I q(Bij)2 l( ij [dL{AM DL{B )\ (2.2.8) где {q(Bjj) 0: q(Bjj) =l}Ji] - нормированные весовые коэффициент, [( )] 7=1 индикатор, принимающий значения 1 или 0 при выполнении или невыполнении условия ( ). Правило классификации объекта А є А сводится к нахождению набора эталонов В , для которого достигается максимальное значение меры сходства (2.2.8) HL{A,Bk) = m?KnL(A,Bi), (2.2.9) и выбору класса А, , если объект А принадлежит сфере влияния хотя бы одного эталона в В,, либо класса AQ в противном случае. Это правило определяет номер класса і = к[Мь(А,Вк) 0)], (2.2.10) который при единичном значении индикатора дает і = к, а при нулевом значении индикатора порождает отказ (г = 0), соответствующий классу AQ. В общем случае соотношения (2.2.9) и (2.2.10) определяют правило взвешенного голосования эталонов (Weighted Vote), дополненное функцией отказа [34]. Если в мере сходства (2.2.8) вместо суммы использовать единственный член max2 J с весом q(Bu)-\, правило классификации У=і (2.2.9) соответствует критерию ближайшего эталона (Nearest Neighbor) [35, 36].
Рассматриваемые критерии классификации рекомендованы для использования компанией Automatic Classification Research Group [37]. Используя априорные вероятности Pown и Раце„ «своих» и «чужих» объектов, введем вероятность ошибочных решений при предъявлении классификатору с решающим правилом (2.2.10) объектов из подмножества А с А V(B,D,(B)) = Pown +4"en)jPaiien, (2.2.11) где Є . и »en) - доли (частоты) ошибок при предъявлении «своих» и А А «чужих» объектов из подмножества А [38]. При А =В и А =А\В формула (2.2.11) дает вероятности ошибок обучения B(B,DI(B)) и тестирования "А\В(В, DZ(B)) соответственно. Суть задачи сводится к построению классификатора, обеспечивающего достаточно малую величину переобучения А\В (В, D (В) - ъ (В, DL (В)). Более того, многоуровневая структура многослойных представлений (2.1.4) позволяет реализовать критерий (2.2.10) с использованием иерархического алгоритма на основе стратегии направленного поиска решения в базе эталонов с уровнями разрешения l = l,...,L. Такая стратегия базируется на сужении зоны поиска на последовательных уровнях базы эталонов и существенно понижает вычислительную сложность по сравнению с алгоритмом полного перебора эталонов на уровне L с наибольшим разрешением.
Формирование модели метрического классификатора сводится к построению покрытий кластеров В(, i — \,...c, сферами, центры которых образуют набор эталонов B = {Bi={Bij}%x)U-В пространстве многослойных представлений вида (2.1.4) с уровнями разрешения / = 1, 2,..., L множество В порождает L-уровневую сеть эталонов Радиусы сфер влияния эталонов задают последовательность D,(B),D2(B),...,D/(B),...,Di(B). Пары В ,D/(B), / = 1, 2,..., L, используются для вычисления меры сходства /-го порядка М4В,) = -dl(A,Btj) т „ DI(BI;) М (2.3.1) -dl(A,Bjj) ШЩ)2 1{В [d,(A,B(i)Dl(B9)],l = L 7=1 между предъявляемым объектом А и группой эталонов В, с соответствующими представлениями А и В,-. Для отбора классов, по которым вычисляется мера (2.3.1), используется иерархическая стратегия, рассмотренная в [39]. Согласно этой стратегии, число классов, анализируемых на 1-м уровне сети эталонов, определяется функцией ct = [с2 (/-1)J / = 1,2,..., L, (2.3.2) с параметром /? 0. Используя функцию (2.3.2), алгоритм направленного поиска решения (Guided Search) на 1-м уровне вычисляет значения //Д В,-) для С[ классов и отбирает с/+1 классов с наибольшими значениями вычисленной меры, для которых рассчитываются значения ///+1(Л,В,-) на (/+1)-м уровне. На последнем L-м уровне принимается решение в соответствии с (2.2.9) и (2.2.10) по cL классам, отобранным на (Z+1)-M уровне (рис.2.5). Согласно стратегии (2.3.2) при /? 0 выполняются неравенства с = сх с2 ... с, ... cL, что приводит к уменьшению числа классов, по которым принимается решение на последнем L-м уровне. При /? = 0 имеет место равенство cL - с, что эквивалентно полному перебору эталонов для принятия решения на L-м уровне.
S1 B ,D,(B) B2,D2(B) B3,D3(B) Bi_l,Di_1(B) Bi,DA(B) c3 Ці решение 1=1 = 2 1 = 3 l = L-1 Многоуровневая структура сети эталонов и стратегия иерархического отбора классов
Вычислительная сложность решающих алгоритмов применительно к методу древовидного представления измеряется числом пар вершин-примитивов, обрабатываемых при сравнении предъявляемого и эталонных объектов, заданных полными деревьями в форме (2.1.4). Поскольку 1-й уровень разрешения содержит 2 примитивов, / = 1, 2,..., L, вычислительная сложность алгоритма полного перебора (Exhaustive Search) определяется величиной [40] CES = JV(2u,-2)Xm, = 2Nc(2L-\) mean ml i=i (2.3.3) где N - число слоев представления, L — максимальный уровень разрешения, с 1 с mean т, = — Щ - среднее число эталонов в кластерах обучающего множества. i=l с 1=1 Верхняя оценка вычислительной сложности алгоритма направленного поиска решения (Guided Search) с учетом стратегии (2.3.2) определяется неравенством (i-)z Q}S NcY 2P(l-l)2l max m, 2Nc ——= max m,. (2.3.4) ых =i 21_/?-l !=i
Отношение соотношений (2.3.3) и (2.3.4) дает нижнюю оценку вычислительного выигрыша алгоритма Guided Search относительно алгоритма Exhaustive Search. Эта оценка определяется неравенством Зависимости вычислительного выигрыша (2.3.6) от уровня разрешения / = 1,2,...,9 для значений коэффициента /? в диапазоне [0,1] представлены семейством графиков на рис.2.6. Согласно приведенным графикам, использование алгоритма Guided Search позволяет обеспечить более чем пятидесятикратный вычислительный выигрыш по сравнению с алгоритмом Exhaustive Search. С учетом ограничений, связывающих величины /?, L и с, оценки (2.3.3) и (2.3.4) приводят к следующему утверждению.
Оценки параметров меры
Исходными данными системы классификации лиц служат цветные изображения лиц. Требуется выполнить анализ доступных баз изображений лиц на предмет возможности их использования в экспериментах с моделируемыми классификаторами, и при необходимости сформировать собственную базу изображений лиц. Следует предусмотреть использование механизмов предобработки изображений для увеличения достоверности распознавания на этапе классификации.
Изображения лиц могут быть получены за счет использования общедоступных баз, либо путем проведения собственной фото - и видеосъемки. Базы изображений, опубликованные на интернет-портале [13] и в книге [14], посвященной распознаванию лиц, анализировались на соответствие требованиям раздела 1.2. Перечень наиболее используемых баз изображений лиц для решения задач распознавания представлен в табл.4.2. Таблица 4.2. Перечень основных баз изображений лиц № Наименование базы -_ Ссылка 1 FERET http://www.itl.nist.gov/iad/humanid/feret/ 2 MIT ftp ://whitechapel .media.mit. edu/pub/images/ 3 M2VTS http://www.tele.ucl.ac.be/M2VTS/ 4 Yale http://www.cvc.yale.edu/projects/yalefaces/ 5 Yale В http://www.cvc.yale.edu/projects/yalefacesB/ 6 XM2TVS http ://www. ее. surrey .ас .uk/Research/VS SP/xm2 vtsdb/ 7 BioID http://www.bioid.com/support/downloads/ 8 Surveillance Cameras http://www.scface.org/ 9 CMU Multi-PIE http ://www.multipie.org/ Большинство рассмотренных баз оказалось малоинформативными в силу недостаточного числа реализаций по отдельным классам, что не позволяет сформировать на этих базах достаточно информативные выборки для обучения и тестирования моделируемых классификаторов. Кроме того, многие базы имеют коммерческий характер и не доступны по экономическим соображениям. Указанные ограничения привели к необходимости формирования собственной базы изображений лиц.
Выполнение фото - и видеосъемки персон и последующее формирование базы изображений лиц осуществлялось на основе следующих требований и рекомендаций: требования к исходным данным (раздел 1.2); ГОСТ Р ИСО/МЭК 19794-5-2006 [55]; лучшие мировые практики подготовки данных для проведения соревнований по распознаванию лиц [56]; рекомендации обзорных статей по распознаванию лиц [57-59]. 7Q
Зададим положение объекта съемки в декартовых координатах X, Y, Z с плоскостью изображения в координатах X, Y (рис.4.3). На рис.4.4 продемонстрированы изображения объекта, полученные при различных углах поворота относительно осей X, Y, Z. Координатное пространство X, Y, Z позволяет задать ракурс съемки, ограничив положение объекта на изображении.
Примеры изображений при различных углах поворота объекта относительно осей Y, Z: а) (0;0;0); б) (+15;0;0); в) (-15;0;0); г) (0;+15;0); д) (0;-15;0); е) (0;0;+15); ж) (0;0;-15) Съемка персон с вариацией ракурса проводилась в течение трех месяцев. В съемке принимало участие 25 персон мужского и женского пола. Цвет глаз и волос не был фиксирован. Выражение лиц было нейтральным. Положение глаз персон относительно угла съемки было произвольным. Для проведения фотосъемки использовался цифровой фотоаппарат Olympus [60], а для видеосъемки - цифровая видеокамера Sony [61]. Изображения лиц были получены при искусственном источнике освещения, в результате чего на изображениях лиц присутствовали затемненные участки. Обобщенная информация условий проведения съемки представлена в табл.4.3.
Исходная база содержала с = 25 персон (классов) по w,- = 40 реализаций в каждом классе. Пример изображений лиц сформированной базы продемонстрирован на рис.4.5.
В большинстве рассмотренных работ по распознаванию лиц [62-64] отсутствует четкая формулировка процедуры выделения информативной области лица. Необходимо выделить информативную область, на основе которой будет выполняться представление и классификация лиц базы изображений.
Воспользуемся следующей процедурой. Найдем положение левого и правого глаза (х, у і )(XR, уц) в координатах изображения (Х,У) (рис.4.6а). Найденные координаты используются для нахождения расстояния r = 4{xR-xLf+{yR-yL)2 (4.2.1) и вычисления параметров маски-овала, ограничивающей информативную область лица на изображении.
Маска задается в координатах (U,V) (рис.4.66), выбираемых следующим образом: ось U проходит через центр линии глаз и перпендикулярна этой линии; центр координат задается точкой на оси U, отстоящей от линии глаз на величину fir с параметром /? 0; ось V проходит через выбранный центр и опережает ось U.
Основные шаги выделения информативной части лица: а) поиск координат глаз; б) вычисление геометрических характеристик; в) выделение информативной области В координатах (U, V) границы маски задаются параметрическим овалоидом ттт ут + 1 (4.2.2) (ДгГ (Pvr)m с параметром формы т 2, радиусами j3ur и /3vr, определяемыми параметрами /?ц 0, /?v 0, и расстоянием г, определенным в (4.2.1). Координаты маски (U,V) связаны с координатами изображения (X,Y) преобразованием поворота и смещения [65] ал f-s me cos#Yx-x0 У-У0 cos# -sin# (4.2.3) где x0 = }/i(xR+xL) +fir sin0 , y0 = y.(yL+yR)-fir cose , s m9 = —= - , cos6 = XR XL При заданных параметрах fi, fiu, fiv соотношения (4.2.1-4.2.3) позволяют выделить на изображении информативную область лица, ограниченную параметрическим овалоидом (рис.4.6в). Выделенная область инвариантна к поворотам и смещениям объекта в плоскости изображения. Инвариантность к масштабу и уровню окраски обеспечивается на последующем этапе древовидного представления выделенной области в соответствии с процедурой, описанной в главе 2, за счет нормировки параметров эллиптических примитивов.
Получение цветных изображений
Эксперименты проводились с классификаторами TSC и SVM для источника подписей, заданного полутоновыми изображениями по каналу интенсивности (канал I) и источника лиц, заданного цветными изображениями по каналам тональности, насыщенности и интенсивности (модель HSI). Кроме того, строился ансамбль источников «подписи, лица», используя GDM-стратегию комплексирования (схема (I, HSI)GDM). Формирование TSC-классификаторов выполнялось при значениях Pown = 1, 0.75, 0.5 и 0.25 с использованием алгоритмов полного перебора (Exhaustive Search) и направленного поиска (Guided Search) решения. Результаты обучения и тестирования SVM-классификатора приведены для переборного алгоритма в случае Pown=\.
Исходные объекты базы подписей и лиц были преобразованы в изображения размера 512 х 512 и 600 х 800 пикселей соответственно. Представления объектов строились в виде полных деревьев с параметром L = 9. В экспериментах использовалось А = 1000 объектов подписей и лиц от с — 25 персон по nij = 40 реализаций каждой персоны заданного источника. Множество объектов источника разбивалось тридцатикратно на равные по
Источник полутоновых изображений подписей Метод скользящего контроля позволил оценить весовые коэффициенты {бгк }к=\ TSC и SVM-классификаторов (табл.5.3). Найденные значения коэффициентов использовались для построения классификаторов, заданных каналом интенсивности I.
Обучение выполнено для одноканального источника в соответствии с методикой, описанной в подразделе 5.1.1 (случай М=1: 5 = «Sign», q = «I», NSi -1 ). Полученные на основе скользящего контроля оценки весовых коэффициентов {щ )ы\ по "Фем компонентам меры различия для TSC и SVM-классификаторов сведены в табл.5.3.
На рис.5.1 даны матрицы попарных различий, вычисленные на множестве древовидных представлений подписей по отдельным компонентам меры (а, б, в) и по мере с найденными оценками весовых коэффициентов для полутонового 1-канала (г). Элементы диагональных миноров в матрицах соответствуют внутриклассовым различиям (темные области), остальные элементы соответствуют межклассовым различиям (светлые области). Матрица (г) демонстрирует более высокую компактность меры по сравнению с матрицами (а, б, в), а именно существенно меньшие значения внутриклассовых расстояний по сравнению со значениями межклассовых расстояний.
Используя меру различия с весовыми коэффициентами, полученными в табл.5.3, на обучающих выборках {В }г=1 при соответствующих значениях Pown построены TSC и SVM-классификаторы. Характеристики тестирования этих классификаторов в терминах ошибок є и среднеквадратических отклонений а, заданных соотношениями (5.1.5) и (5.1.6), приведены в разделе 5.3.
Обучение выполнено для трехканального источника в соответствии с методикой, описанной в подразделе 5.1.2 (случай М=1: = «Face», q= «Н», «S», «I», NFace = 3). На основе скользящего контроля получены оценки весовых коэффициентов {eg. } -] меРы по каналам q= «Н», «S», «I» для TSC и SVM-классификаторов. В случае TSC-классификатора указанные оценки вычислены для критерия ближайшего соседа (TSC ) и критерия взвешенного голосования (TSCWV). Результаты представлены в табл.5.4-5.7 соответственно для значений параметра Pown =1,0.75,0.5,0.25. Полученные оценки коэффициентов {щя }к=1, 7=«Н», «S», «I», использовались для вычисления меры различия лиц по соответствующим слоям представления в модели HSI. Обучение SVM и TSC-классификаторов, выполненное согласно методики подраздела 5.1.2 по каналам Н, S и I, дало коэффициенты {у , q=«H», «S», «I»} обобщенной меры различия (табл.5.8).
На рис.5.2 даны матрицы попарных различий, вычисленные на множестве древовидных представлений лиц по мерам каналов Н, S, I и по обобщенной мере на основе GDM-стратегии комплексирования каналов (схема HSIGDM). Матрица (г) демонстрирует более высокую компактность меры по сравнению с матрицами (а, б, в).
Используя меры различия с весовыми коэффициентами, полученными в табл.5.4-5.8, на обучающих выборках {B(r }r=l при соответствующих значениях Powrl построены SC и SVM-классификаторы. Характеристики тестирования этих классификаторов в терминах ошибок є и среднеквадратических отклонений а для GDM и WMV-стратегий комплексирования каналов приведены в разделе 5.3.
Обучение выполнено для ансамбля из двух источников («подписи, лица») в соответствии с методикой, описанной в подразделе 5.1.3 (случай М=2: s = «Sign», q = «I», NSign=l ; 5= «Face», q = «H», «S», «I», NFace-3).
Полученные на основе скользящего контроля оценки коэффициентов Г] lgn и TjFace даны в табл.5.9. Расчеты выполнены при использовании GDM-стратегии комплексирования, выбор которой мотивирован лучшими результатами (меньшими ошибками по сравнению с WMV-стратегией), полученными для трехканального источника лиц.
На рис.5.3 даны матрицы попарных различий, вычисленные по соответствующим мерам на множестве древовидных представлений подписей (а), лиц (б) и ансамбля «подписи, лица» (в). Матрица (в) демонстрирует более высокую компактность меры по сравнению с матрицами (а, б).
Используя обобщенную меру различия по ансамблю «подписи, лица» с коэффициентами rj lgn, Face, полученными в табл.5.9 при указанных значениях Pown, на обучающих выборках {В(г)} ] построены TSC и SVM-классификаторы. Характеристики тестирования этих классификаторов (усредненные по выборкам ошибки є и их среднеквадратические отклонения а ) для случая GDM-стратегии комплексирования приведены в разделе 5.3.
