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

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

005533772

Степанов Дмитрий Юрьевич

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

Специальность 05.13.01 - «Системный анализ, управление и обработка

информации»

АВТОРЕФЕРАТ

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

Москва-2013

2 6 СЕН 2013

005533772

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

Научный руководитель:

Официальные оппоненты:

кандидат технических наук, старший научный сотрудник, ведущий научный сотрудник Вычислительного центра им. A.A. Дородницына Российской академии наук Ланге Михаил Михайлович

Местецкий Леонид Моисеевич

доктор технических наук, профессор Московского государственного университета им. М.В. Ломоносова

Гришин Владимир Александрович

кандидат технических наук, доцент, старший научный сотрудник Института космических исследований Российской академии наук

Федеральное государственное бюджетное учреждение науки Институт прикладной математики им. М.В. Келдыша Российской академии наук

Защита состоится «31» октября 2013 г. в 15:00 на заседании диссертационного совета Д212.131.03 при Московском государственном техническом университете радиотехники, электроники и автоматики (МГТУ МИРЭА) по адресу: 119454, г.Москва, пр-т Вернадского, д.78, ауд.Г-412.

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим отправлять по адресу: 119454, г.Москва, пр-т Вернадского, д.78.

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

Ведущая организация:

Ученый секретарь диссертационного

совета Д212.131.03, д.т.н., проф. ^J

O.A. Тягунов

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

Актуальность темы. Исследование и разработка методов и алгоритмов автоматического анализа и понимания изображений продиктованы активным развитием информационных технологий, используемых в системах искусственного интеллекта. Развитие таких технологий стимулируется растущим быстродействием вычислительной техники, способной быстро и с высокой точностью обрабатывать большие объемы данных. Одно из ведущих направлений в области анализа и понимания изображений составляет распознавание образов, которое тесно связано с проблематикой технического зрения. Значительный вклад в развитие методов и алгоритмов, используемых для решения задач классификации и анализа изображений, внесли как отечественные ученые Ю.И. Журавлев, К.В. Рудаков, В.Н. Вапник, А.Я. Червоненкис Н.Г. Загоруйко, Ю.П. Пытьев, А.И. Чуличков, К.В. Воронцов' Л.М. Местецкий, В.В. Моттль, В.В. Рязанов, так и зарубежные специалисты 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) исследовали процедуры установления соответствия иерархически-структурированных признаков. Подходы и методы, рассмотренные этими авторами, ориентированы на построение эффективного пространства описаний (представлений) образов, выделенных на бинарных изображениях. К подобным структурным описаниям геометрических форм относятся также скелетные представления, предложенные J1.M. Местецким (2000), и древовидные представления наборами эллиптических примитивов, разработанные М.М. Ланге и С.Н. Ганебных (2004). Древовидные представления эллиптическими примитивами обобщены М.М. Ланге и С.Н. Ганебных (2007-2009) для широкого класса образов, заданных одноканапьными полутоновыми изображениями. На множестве представлений введена мера различия полутоновых образов, и показана эффективность полученного пространства представлений для распознавания жестов руки и подписей.

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

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

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

1. Разработка модели метрического классификатора объектов по многоканальным изображениям. Построение многослойных древовидных представлений образов и введение меры различия объектов на множестве представлений. Формализация критерия классификации.

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

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность. Теоретическую ценность работы составляют многослойное представление образов с многоуровневым разрешением, мера различия на множестве многослойных представлений и модель метрического классификатора. Теоретические результаты работы включены в курс лекций по дисциплине «Синергетическая информатика» на кафедре «Прикладная синергетика» в МГТУ МИРЭА и использованы в научных отчетах по проекту Российского фонда фундаментальных исследований №09-01-00573-а, выполненному в Вычислительном центре им. A.A. Дородницына РАН.

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

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

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

■ 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 г. (работа отмечена дипломом .э-и степени).

Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований №09-01-16059-моб-з и 10-01-16048-моб-з.

Публикации. По материалам диссертационной работы опубликовано 12 печатных работ, в том числе 4 в журналах из перечня ВАК, получены 2 свидетельства о государственной регистрации программного продукта (№50200900489, 50201001618).

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, библиографического списка из 80 наименований и двух приложений. Работа содержит 170 страниц основного текста, 64 рисунка и 22 таблицы.

ОСНОВНЫЕ ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ

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

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

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

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

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

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

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

В разделе 1.2 более де'.шьно изложена проблематика метрической модели. Рассмотрены вопросы формирования пространства представлений образов и выбора меры. Обсуждены характеристики качества классификации в терминах ложных отказов (False Rejection Rate) и ложных распознаваний (False Acceptance Rate) и соотношение качества и вычислительной сложности. Выбран подход к снижению вычислительной сложности в пространстве представлений с многоуровневым разрешением.

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

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

В разделе 2.1 изложен способ представления объектов многоканальных изображений. Пусть А - множество объектов, в котором каждый объект А е А задан набором образов, выделенных на N изображениях (от N каналов наблюдения). Предполагается, что представление образа от каждого q-го канала (q=l,...,N) может быть построено с помощью известной процедуры рекурсивного разбиения образа на непересекающиеся сегменты и аппроксимации сегментов эллиптическими примитивами [М.М. Ланге, С.Н. Ганебных, 2009]. Такое представление имеет вид полного бинарного дерева глубины L, узлы которого содержат описания эллиптических примитивов. Тогда для объекта Ае А, заданного /V-канальным изображением, предлагается использовать многослойное представление

A'- ={A't; =(*»,.. „а[г. ..,а'Х-ь 0)

в котором q-й слой Aq является полным бинарным деревом глубины L, содержащим уровни a'q, l = 0,...,L. Подпоследовательность A*q =(а°,...,а/) в (1) образует поддерево глубины I. Уровень a'q задан набором эллиптических примитивов

aq ~ iQqn ~(rqii'Uqn>xq?T zqn)} / ^ > (2)

где Oqn - примитив q-ro слоя с номером п, rqn - вектор центра, (uqn,vqil)-векторы ориентации, - значение яркости примитива.

На рис.1 даны примеры однослойного древовидного представления изображения подписи по каналу I и трехслойного древовидного представления изображения лица по каналам модели HSI.

а)

(г^

Подпись, канал I /=0 /=1 1=2 1=3

1=5 1=6 1=1 1=

б)

Лицо, канал Н 1=0

Лицо, канал Э 1=0

Лицо, канал 1 1=0 /=1 1=2 1=3 1=4 1=5 1=6 1=1 1= Рис.1. Древовидно-структурированное представление с уровнями разрешения /=0,.. .,8: а) подписи; б) лица

Построение эллиптических примитивов каждого д-го слоя а'ч в собственных координатах аппроксимируемых сегментов и нормировка параметров всех примитивов относительно корневого примитива с номером п = 0 позволяют сформулировать следующее утверждение.

Утверждение 1. Многослойное представление, заданное соотношениями (1) и (2), практически инвариантно к преобразованиям поворота, смещения, изменения масштаба и уровня яркости объекта при достаточно малом размере пикселей и большом числе уровней квантования значений пикселей.

В разделе 2.2 введена мера различия пары объектов (А,А) по любому д-му слою их представлений а'ч и а'с/, построена обобщенная мера по многослойным представлениям А1 = {А1с/}^'=] и А1 = {А^}^, и

разработана модель метрического классификатора по введенной обобщенной мере. Для любой пары соответственных примитивов (<2чп е а'ч,^чп е а'с/) с номером п> 0 вводятся неотрицательные функции потерь

Р\ Шс,,пОчп) =

тах(||г9„||,||гг,„||)

(За)

ЦП \

PiiQqn-Q4n) = -

II «у-«у II | 1|уф,-у?„" л

max(||u IUI ü II) max(|| v „ ||,|| v

(36)

*Чп II»II "Ч„VII ||,|| уч„ \\> у

Рз(0,п,0Ч1,)= (Зв)

где || Г || - евклидова норма вектора Г, а |/| - модуль значения/. С учетом функций (3) для объектов А и А определяются три компоненты меры

4 И Я;

2м-2

¿¡?\А,А)= X ^,рк(Очп,Очп), А = 1,2,3, (4)

различия /-го порядка по q-м слоям А1 и Д'

н=1

и мера различия 1-го порядка вида

d¡"4A,Á)=Í4^(A,A) (5)

к= 1

на уровнях с номерами l = \,...,L. Весовые коэффициенты wn> О в (4) определяются номером п соответственных примитивов Qqn и 0 а

коэффициенты {со[ч) >0: £ = в (5) оцениваются на этапе

уЫ

обучения. С учетом (5) для пары объектов (Л, Л), представленных в форме (1), ведена обобщенная мера различия /-го порядка

dl{A,A)=Y.r^d)4\A,Á), ГЫ> 0, (6)

9=1

Л'

где q >0: = l}^=i - нормированные весовые коэффициенты,

<7=1

оценки которых также строятся на этапе обучения.

Предложена следующая модель классификатора. Пусть множество А= {А/}/=о содержит объекты, допускающие представление (1) и принадлежащие с+1 классам. Каждый класс А, с номером 0 включает

семантически однородные объекты, а класс А0 объединяет все прочие объекты. При известных априорных вероятностях классов

с с

Pj=P(Aj): £Р(А,) = 1, вероятности Р,тп = Т1 р(А,) и

/=0 /=| РаПеплают распределение «своих» (own) и «чужих» (alien) объектов на множестве А.

Для обучения используется обучающее множество В= (В, = {Ву}%1 };=] с А, составленное из семантически однородных кластеров В, с А,- мощности т} =|| В, ||. На обучающем множестве отбирается множество эталонов

МВ-Ц^^СВ, (7)

в котором т1 < т, и каждый эталонный объект By, представленный поддеревом By, является центром сферы

S, (By,D, (By)) = {BeB:d, (B,By)<D, (Ву)} (8)

с радиусом Dt (By), вычисляемым по мере 1-го порядка вида (6).

Используя э.талоны (7), заданные представлениями (1), и их сферы (8), взятые при l=L, введена мера сходства L-го порядка между любым объектом A е А и подмножеством эталонов В,. Эта мера имеет вид

'""' п 1Й \

/( «> [d^B^iDilBy)}, (9)

J=1

где {q(By)>0:^q(By) =1}'"^ - нормированные весовые коэффициенты

У=1

эталонов, [(*)]- индикатор условия (*). Мера (9) дает следующий критерий установления номера класса i* для объекта А е А

/* = /с[^А(ЛВ4)>0)], к = argmax jil(Л,В,- ), (10)

/=1

который при нулевом значении индикатора порождает отказ (/'* = 0 ),

соответствующий классу Ад. В общем случае критерий (10) определяет

правило взвешенного голосования (Weighted Vote) эталонов, дополненное функцией отказа. При замене суммы (9) наибольшим членом, критерий (10) эквивалентен правилу ближайшего эталона (Nearest Neighbor).

В разделе 2.3 оценена вычислительная сложность алгоритмов принятия решений (10) на основе стратегии иерархического поиска и полного перебора. Вычислительная сложность решающих алгоритмов измеряется числом пар вершин-примитивов, обрабатываемых при сравнении предъявляемого и эталонных объектов в форме (1). Иерархический поиск (Guided Search) базируется на сокращении числа анализируемых классов в последовательных уровнях базы эталонов, представленных сферами (8) порядка / = 1,2 ,...,L. Число классов, анализируемых на 1-м уровне (по представлениям глубины Г), задается

функцией

c,=\ç2-P^\, / = 1,2.....Z.,

где коэффициент ¡} > 0. Из с, классов отбираются см (для анализа на (/+1)-м уровне) с наибольшими значениями меры сходства /-го порядка вида (9), которая вычисляется по представлению А1 предъявляемого объекта и сферам S, (£//,£>/ (By)) эталонных объектов при единичном

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

Утверждение 2. При /? = ^-Iog2 с > 1 вычислительная сложность

переборного и иерархического алгоритмов поиска решения удовлетворяет оценкам

CES =2^(2/--1)£«,=0(с2), / = 1

С

CGS < INcL max m, = 0(c log2 c).

M

Из утверждения 2 следует, что при большом числе классов с

Q

алгоритм Guided Search дает выигрыш С = —^ в быстродействии по

^-cs

сравнению с алгоритмом Exhaustive Search порядка —-—.

Iog2 с

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

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

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

представлений деревьями глубины L для каждого кластера В, с В

мощности /и, = ||В,||, / = 1,...,с, выполняется дихотомическое разбиение на непересекающиеся сегменты В^ размера тц = |в,у||

т, А,

В, = ив)у, т; = ¿>у ,

7=I 7=1

и выбор для каждого сегмента Ву покрывающей сферы вида (8) с центром В„ = агатштаха1, (В,В) (11)

и радиусом

^(¿у) = (1-аг, + 0[тах)(^)- (12)

Здесь ог;-- параметр, выбираемый на отрезке [0, 1]; /)[тш'(/>у.) . расстояние

по заданной мере между центром В;у е В,у и наиболее удаленным

объектом 5еВ,у; £>£тах\.в(у) - наибольшее значение из пары величин:

значения ) и величины расстояния между центром В у е Ву и

наименее удаленным объектом беВ\В,. На каждом шаге дихотомии выполняется разбиение сегмента Ву, В,у —» (В,у,В,у»), имеющего

наибольшее рассеяние шах ¿/¿(5,5,.) среди сегментов текущего

разбиения кластера В,-. Сегменты Ву' и В,у» включают объекты, которые

наиболее близки по заданной мере различия ¿-го порядка к наиболее удаленным друг от друга опорным объектам В{е В,у и Ву е В,у. Пример

ТБС-покрытия кластера В, с В сферами дан на рис.2.

Рис.2. Покрытие кластера В, сферами: а) бинарное дерево сегментов; б) сферы покрытия сегментов

а)

Сегменты текущего разбиения кластера

,- опорный объект сегмента В у

VI юуп&1У1

сегмента Ву

Сегмент с наибольшим рассеянием

объест"

- объекты сегмента В /■•'

- объекты сегмента В /.» -объекты В\В,

Утверждение 3. Множество сфер с центрами вида (11) и радиусами вида (12) образует древовидно-структурированное покрытие мощности от, кластера В,. Объединение покрытий всех кластеров порождает TSC-классификатор по критерию (10).

Покрытие кластера В, образует пару множеств (B;,Dt(B,)), заданных соответственно центрами и радиусами покрывающих сфер /-го

кластера. Объединение покрытий с кластеров порождает пару множеств с ~ с

B = [JB, и D/(B) = (JDz.(B,). Проекции (B,D,(B)), / = 1,...,£-1, этой /=1 i=i

пары совместно с (B,D, (В)) образуют ¿-уровневую базу эталонов.

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

Утверждение 4. Вероятность ошибки обучения TSC-классификатора с параметрами (B,Da(B)) оценивается средним значением

ffв (В, D, (В)) = - Zе(m,,а,,), (13)

С !=1

где

= + е™(щ,а>.^Ртуп +

+ eB\Bl(",i><Xi)Palien (14)

функция ошибки скользящего контроля, s™(n~iha,) и (от,,а,)- доли

ложных отказов и ложных распознаваний при предъявлении покрытию с параметрами (/и,-,а,) «своих» (В,) и «чужих» (В\В,) объектов.

Минимум оценки (13) по параметрам {от,-,аг,},с=1 достигается в результате независимой минимизации функций (14) по переменным от,- и а,-. Оптимизация сводится к нахождению параметров

(w,,or,) = arg min {т'псс]), (15)

\<т] <m;0<a'j <1

где от определяет наибольшее заданное число эталонов.

В разделе 3.3 получены оценки параметров меры в соотношениях (5) и (6) при l=L. В качестве коэффициентов a[q) ,о}^\ со\ч) в мере (5) выбраны оценки

1О§249)(В,РЦ(В))

где £-^'(В,0^(В)) - доля ошибок вида (13), полученная на покрытиях с параметрами (15) по мере В), В е В, В е В. Аналогичный способ

использован для оценивания коэффициентов <7 = 1,...,/У, в

обобщенной мере (6). В качестве оценок выбраны величины

уЫ = ' N

1о§249)(В,0А(В))

ZIog,4')(B.D/,(B))

9=1

где ff^'iB.D/(В)) - доля ошибок вида (13), вычисляемая на покрытиях с

параметрами (15) по мере d\q){B,B), В е В, В е В.

Предложенный способ вычисления обобщенной меры различия положен в основу стратегии объединения классификаторов по ансамблю источников, которая названа GDM-стратегией (General Dissimilarity Measure). Наряду с предложенной GDM-стратегией, исследована известная WMV-стратегия (Weighted Majority Vote) объединения решений по отдельным каналам [L. Kancheva, 2004].

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

Четвертая глава содержит описание баз изображений подписей и лиц и реализованного комплекса программ для проведения экспериментов с разработанным TSC-классификатором и известным SVM-классификатором (Support Vector Machine) в версии библиотеки OpenCV.

В разделе 4.1 рассмотрены основные этапы подготовки базы подписей. Выполнен анализ доступных баз изображений подписей. Используя открытую базу подписей [Signature Verification Competition, 2004], сформирована база полутоновых I-изображений подписей от с = 25 персон по /и,- = 40 реализаций каждой персоны. Для улучшения качества применена процедура пороговой фильтрации полученных изображений.

В разделе 4.2 приведены основные этапы формирования базы изображений лиц. Проведена съемка, и сформирована база цветных HS1-изображений от с = 25 персон по ш,- = 40 реализаций от каждой персоны с вариацией ракурса съемки. Предложена процедура выделения

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

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

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

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

В разделе 5.1 описана схема проведения экспериментов. В эксперименте использованы подготовленные базы изображений подписей и лиц. Эксперименты проводились по схеме скользящего контроля с 30-кратным разбиением множества изображений источника на равные по объему обучающие и тестовые выборки (30 times 2 fold cross-validation) [5. Theodoridis, К. Koutroumbas, 2009]. На обучающих выборках моделировались классификаторы при значениях априорной вероятности Рт.„ =1,0.75,0.5. На тестовых выборках оценивались доли ошибок распознавания и их среднеквадратические отклонения при использовании алгоритмов Exhaustive Search и Guided Search в пространстве древовидных представлений с параметром разрешения 1 = 9.

В разделе 5.2 описаны результаты моделирования процедур обучения TSC-классификатора по критерию взвешенного голосования и ближайшего эталона ( TSC ш и TSC NN ) и SVM-классификатора для источников подписей, лиц и ансамбля указанных источников. Следует отметить, что в используемой версии SVM-классификатора отсутствует функция отказа, поэтому его моделирование выполнено для источников с априорной вероятностью Pm,n =1.

В разделе 5.3 продемонстрированы результаты тестирования классификаторов. Экспериментальные характеристики распознавания полутоновых изображений подписей по каналу I с использованием алгоритма Exhaustive Search приведены в табл.1.

Таблица 1. Средние значения е и среднеквадратические отклонения а ошибок классификации подписей по каналу I (алгоритм Exhaustive Search)

Канал Р = 1 1 own 1 ¡'own' 0-75 J P =05 ■own

tscnn TS С Wy svm TS Г TSC yvy TSCfjN TSCWV

I е 0.013 0.005 2E-4 0.015 0.006 0.018 0.010

а 0.005 0.003 6E-4 0.007 0.007 0.009 0.007

Согласно табл.1, при Ртп = 1 SVM-классификатор обеспечивает меньшую долю ошибок по сравнению с TSC%VV - классификатором (2Е-4 против 0.005). При значении Рт.п = 1 доля ошибок TSC ^ -классификатора значительно ниже доли ошибок TSC,^ - классификатора (0.005 и 0.013 соответственно). При значениях Ртп =0.75 и 0.5 указанное соотношение ошибок для TSC hTSCnn - классификаторов сохраняется.

Аналогичные характеристики распознавания лиц по каналам HSI-модели и по объединению этих каналов с использованием GDM и WMV-стратегий и алгоритма Exhaustive Search приведены в табл.2.

Таблица 2. Средние значения е и среднеквадратические отклонения сг ошибок классификации лиц в модели HSI (алгоритм Exhaustive Search)

Канал P =1 1 own 1 Pown 0.75-.. PownT 0.5

TSCf^ TSC^y SVM TSCNN TSCWV TSCNN TSC wy

H e 0.015 0.008 0.002 0.016 0.010 0.018 0.012

a 0.005 0.006 0.001 0.007 0.006 0.007 0.007

S £ 0.017 0.012 0.009 0.018 0.015 0.020 0.017

cr 0.006 0.003 0.004 0.008 0.005 0.008 0.008

1 s 0.022 0.012 0.017 0.025 0.014 0.027 0.020

a 0.006 0.005 0.006 0.008 0.005 0.008 0.007

e 0.007 0.001 0.001 0.012 0.005 0.015 0.007

a 0.005 0.002 0.001 0.006 0.004 0.007 0.005

HSI wmv £ 0.010 0.005 0.006 0.015 0.007 0.015 0.009

a 0.005 0.003 0.005 0.007 0.005 0.007 0.005

Из табл. 2 следует, при Рокп = 1 объединение классификаторов отдельных каналов цветовой модели НБ1 на основе вОМ-стратегии ( Н51ссм ) позволило уменьшить долю ошибок до 0.001. При Рт.п = 1, 0.75 и 0.5 результаты объединения с помощью ШМУ-стратегии ( Ш! ЖМУ ) уступают СОМ-стратегии.

Таблица 3. Средние значения s и среднеквадратические отклонения а ошибок идентификации личности по ансамблю изображений подписи пс _каналу I и лица в модели HSI (алгоритм Exhaustive Search)

Источник Р = 1 1 own 1 Р = 0 75 1 own ' P =05 1 own

TSCj^ TSCWV SVM TSCf^j TSCWV TS Г TS С \уу

Ансамбль (I. HSDgdm £ 0.003 ЗЕ-4 7Е-5 0.007 0.001 0.010 0.003

сг 0.004 7Е-4 4Е-4 0.004 0.001 0.005 0.002

Характеристики качества идентификации личности по ансамблю источников подписей и лиц с использованием GDM-стратегии объединения и алгоритма полного перебора (Exhaustive Search) даны в табл.3. Приведенные характеристики демонстрируют увеличение достоверности распознавания по сравнению с данными табл. 1-2.

Экспериментальные результаты распознавания полутоновых изображений подписей (канал I), цветных изображений лиц (модель HS1GDM) и ансамбля изображений «подписи, лица» (I, HSI)GDM с использованием алгоритма иерархического поиска решения (Guided Search) даны в табл.4. Результаты получены для TSC-классификатора в пространстве древовидных представлений объектов с уровнями разрешения / = !,...,9. Получение аналогичных характеристик SVM-классификатора требует модификации используемой версии SVM, что является предметом отдельного исследования.

Таблица 4. Среднее значение ошибок е и вычислительного выигрыша С = —— при использовании алгоритма Guided Search

gs

Источник- Р =1 ' own 1 р ' own = 0.75 P =05 1 own J

TSC^ TSC wv TSCN>N TSC™ TSCWV

Подписи £ 0.025 0.015 0.031 0.020 0.034 0.025

I С 5.228 5.362 5.631 5.975 6.722 6.274

Лица £ 0.017 0.012 0.022 0.018 0.030 0.020

^^'gdm С 5.975 5.228 7.605 8.366 8.714 8.496

Ансамбль £ 0.015 0.010 0.020 0.014 0.027 0.018

(Ь HSI)0DM С 5.542 5.400 7.967 8.184 8.556 8.366

Согласно данным табл.4, доли ошибок TSC - классификатора при использовании алгоритма Guided Search превышают аналогичные показатели алгоритма Exhaustive Search (табл. 1-3). Однако при различных априорных распределениях «своих» и «чужих» объектов иерархический поиск решения продемонстрировал более чем пятикратный выигрыш в быстродействии по сравнению с алгоритмом полного перебора.

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

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

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

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

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

числе классов с иерархический алгоритм обеспечивает в —-— раз

log2c

большее быстродействие по сравнению с алгоритмом полного перебора.

3. Разработана процедура обучения TSC-классификатора, включающая отбор эталонов и оценивание параметров. Отбор эталонов базируется на покрытии обучающего множества сферами и оптимизации покрытия (по числу и радиусам сфер) методом скользящего контроля. Предложен способ объединения классификаторов.

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Степанов Д.Ю. Предобработка и представление данных для решения задачи распознавания лиц: Сборник трудов 58-й научно-технической конференции МИРЭА, г.Москва, 13-27 мая 2009 / Московский государственный институт радиотехники, электроники и автоматики (технический университет). - М.: МИРЭА, 2009. - с.116-121.

2. Степанов Д.Ю. Выделение контура лица для решения задачи распознавания лиц / М.: Свидетельство о государственной регистрации программного продукта №50200900489 от 02.06.2009.

3. Ланге М.М., Степанов Д.Ю. Многослойное древовидное представление объектов многоканальных изображений: 14-я Всероссийская конференция «Математические методы распознавания образов», г.Суздапь, 21-26 сентября 2009.: Сборник докладов. - М.: МАКС Пресс, 2009. - с.376-378.

4. Степанов Д.Ю. Идентификация личности на основе метода древовидных представлений: Сборник конкурсных работ Всероссийского смотра-конкурса научно-технического творчества студентов высших учебных заведений «Эврика-2009», г.Новочеркасск, декабрь 2009 / ЮжноРоссийский государственный технический университет (Новочеркасский политехнический институт). - Новочеркасск: Лик, 2010. - с.54-57.

5. Степанов Д.Ю. Распознавание лиц в пространстве многослойных древовидных представлений изображений цветовой модели HSI // Труды Института системного анализа Российской академии наук (ИСА РАН) «Динамика неоднородных систем». - 2010. -т.53, №2. - с.305-314.

6. Степанов Д.Ю. Отбор эталонов на основе покрывающих сфер на этапе обучения классификатора // Естественные и технические науки. - 2010. - т.48, №4. - с.370-372.

7. Stepanov D.Y. Data preprocessing for person identification based on color face images: Proceedings of 16th International Scientific and Practical Conference of Students, Post-graduates and Young Scientists «Modern Techniques and Technologies», Tomsk, 12-16 April, 2010 / Tomsk Polytechnic University. - Tomsk: TPU Press, 2010. - pp. 121-123.

8. Степанов Д.Ю. Обучение классификатора на основе сфер покрытия / М.: Свидетельство о государственной регистрации программного продукта №50201001618 от 05.10.2010.

9. Lange M.M., Ganebnykh S.N., Stepanov D.Y. Multiresolution network of templates for fast pattern recognition: Proceedings of 10th International Conference «Pattern Recognition and Image Analysis: New Information Technologies», St. Petersburg, 5-12 December, 2010. - SPb.: Politechnika, 2010. vol.1 - pp.149-152.

10. Степанов Д.Ю. Идентификация личности на основе распознавания лиц по древовидным представлениям изображений // Информационно-измерительные и управляющие системы. - 2011. - т.9, №7. - с.13-24.

11. Степанов Д.Ю., Ланге М.М. Распознавание лиц по многослойным древовидным представлениям цветных изображений: 15-я Всероссийская конференция «Математические методы распознавания образов», г. Петрозаводск, 11-17 сентября 2011.: Сборник докладов. - М.: МАКС Пресс, 2011. - с.330-333.

12. Ganebnykh S.N., Lange М.М., Stepanov D.Y. Metric classifier using multilevel network of templates // Pattern Recognition and Image Analysis. - 2012. - vol.22, №2. - pp. 265-277.

Личный вклад автора. В работе [3] автору принадлежит мера на множестве многослойных древовидных представлений, алгоритм выделения информативной области лица на изображении и экспериментальные оценки вероятности ошибки распознавания лиц по цветным изображениям. В [9] и [11] имеет место неразделимое соавторство. В [12] автору принадлежит схема проведения экспериментов и экспериментальные оценки вероятности ошибки распознавания подписей и лиц.

Степанов Дмитрий Юрьевич

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

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

Подписано в печать 28.08.2013. Формат 60x84/16. Уч.-изд. л. 1. Усл. печ. л. 1. Тираж 100 экз. Заказ 18

Отпечатано на ротапринтах в Федеральном государственном бюджетном учреждении науки Вычислительный центр им. A.A. Дородницына Российской академии наук 119333, г.Москва, ул.Вавилова, д.40

МИНОБРНАУКИ РОССИИ

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

электроники и автоматики"

МГТУ МИРЭА

04201362841

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

Степанов Дмитрий Юрьевич

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

Специальность 05.13.01 «Системный анализ, управление и обработка информации»

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель к.т.н. Ланге М.М.

Москва-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..................................................................................................................5

ГЛАВА 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. Многослойное древовидное представление объектов..........................41

2.2. Мера различия объектов на множестве многослойных древовидных представлений и модель классификатора............................................................45

2.3. Алгоритм направленного поиска решения

и вычислительная сложность................................................................................50

2.4. Результаты и их обсуждение.......................................................................54

ГЛАВА 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. Основные функции программ.................................................................92

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК....................................................................164

ПРИЛОЖЕНИЕ........................................................................................................171

Приложение 1. Акт внедрения в МГТУ МИРЭА.............................................171

Приложение 2. Акт внедрения в ОАО «Чувашнефтепродукт».......................172

ВВЕДЕНИЕ

Актуальность темы. Исследование и разработка методов и алгоритмов автоматического анализа и понимания изображений продиктованы активным развитием информационных технологий, используемых в системах искусственного интеллекта. Развитие таких технологий стимулируется растущим быстродействием вычислительной техники, способной быстро и с высокой точностью обрабатывать большие объемы данных. Одно из ведущих направлений в области анализа и понимания изображений составляет распознавание образов, которое тесно связано с проблематикой технического зрения. Значительный вклад в развитие методов и алгоритмов, используемых для решения задач классификации и анализа изображений, внесли как отечественные ученые Ю.И. Журавлев, К.В. Рудаков, В.Н. Вапник, А .Я. Червоненкис, Н.Г. Загоруйко, Ю.П. Пытьев, А.И. Чуличков, К.В. Воронцов, J1.M. Местецкий, В.В. Моттль, В.В. Рязанов, так и зарубежные специалисты R. Gonzalez, J. Serra, R. Haralick, L. Shapiro, T. Huang, A. Rosenfeld, L. Kuncheva.

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

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

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

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

Один из первых подходов к построению структурных описаний геометрических форм на основе их иерархической декомпозиции предложен Н. Row и G. Medioni [1]. Метод рекурсивной декомпозиции использован S.

Berretti и A. Del Bimbo [2] для представления двумерных форм древовидно-структурированными наборами спектральных признаков. Для распознавания геометрических форм A. Torsello и Е. Hancock [3] исследовали процедуры установления соответствия иерархически-структурированных признаков. Подходы и методы, рассмотренные этими авторами, ориентированы на построение эффективного пространства описаний (представлений) образов, выделенных на бинарных изображениях. К подобным структурным описаниям геометрических форм относятся также скелетные представления, предложенные JI.M. Местецким [4], и древовидные представления наборами эллиптических примитивов, разработанные М.М. Ланге и С.Н. Ганебных [5]. Древовидные представления эллиптическими примитивами обобщены М.М. Ланге и С.Н. Ганебных [6-8] для широкого класса образов, заданных одноканальними полутоновыми изображениями. На множестве представлений введена мера различия полутоновых образов, и показана эффективность полученного пространства представлений для распознавания жестов руки и подписей.

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

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

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность. Теоретическую ценность работы составляют многослойное представление образов с многоуровневым разрешением, мера различия на множестве многослойных представлений и модель метрического классификатора. Теоретические результаты работы включены в курс лекций по дисциплине «Синергетическая информатика» на кафедре «Прикладная синергетика» в МГТУ МИРЭА и использованы в научных отчетах по проекту Российского фонда фундаментальных исследований №09-01 -00573-а, выполненному в Вычислительном центре имени A.A. Дородницына РАН.

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

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

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

■ 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 таблицы.

ГЛАВА 1. СОСТОЯНИЕ ПРОБЛЕМЫ И ЗАДАЧИ

ИССЛЕДОВАНИЯ

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